How much can we "reduce" this polynomial division?

115 Views Asked by At

Let's say we start with a univariate polynomial, $p(x)$:

$$p(x) = x^n-1$$

We can then divide by another polynomial; for instance $q(x)$. For example, if $p(x) = x^6-1$ and $q(x) = x^2-x+1$ we have:

$$\frac{p(x)}{q(x)}=\frac{x^6-1}{x^2-x+1}=1+x-x^3-x^4$$

Here $q(x)$ has 2 roots, and the resulting division yields 4 terms with nonzero coefficients. There are three numbers of interest here. The degree of $p(x)$, which we can call $n$, the number of roots, and the number of nonzero terms.

I'm interested in finding the largest (or large) ratios of $n$:(roots + nonzero terms). In the case of the above example, the ratio is $n=6$:(2 complex roots + 4 terms). Can we do better? In other words, can we find a greater $n$ with less roots and resulting terms?

If we can do better, what are $p(x)$ and $q(x)$?

IMPORTANT NOTE

$p(x)$ is always $x^n-1$.

I'm counting the number of complex roots.

1

There are 1 best solutions below

6
On

How about $x^8-1$, which we can divide by $x^4+1$ to get $x^4-1$? We have $n=8$, $4$ complex roots, and $2$ non-zero terms. Clearly the approach works for any $n$ a multiple of $2$ with ratio $\frac n{\frac n2+2}=\frac {2n}{n+4}$

Added: We can also do $x^{(2m)^2}-1$ and divide by $x^{2m}+1$, giving $x^{4m^2-2m}-x^{4m^2-4m}+x^{4m^2-6m}\dots-1$. This will give $n=4m^2, 2m$ roots and $2m+1$ non-zero terms, for a ratio of $\frac {4m^2}{4m+1}$ which get arbitrarily large with $m$. By considering the degrees, we can show this is optimal