Extremely Divisible Polynomial

We will characterize all monic polynomials, $f(x)$ such that for all positive integers $n$ , $f(x) | f(x^{n})$ . Call such a polynomial $f(x)$ , good. For now, we will only consider polynomials with nonzero roots, as multiplying a polynomial by $x^k$ does not change whether or not it is good.

We will use the following two well-known facts about cyclotomic polynomials:

1. If $p$ is a prime not dividing $k$ , then $\Phi_{k}(x^{p})=\Phi_{pk}(x)\Phi_{k} (x)$
2. If $p$ is a prime dividing $k$ , then $\Phi_{k}(x^{p})=\Phi_{pk}(x)$

Let $f(x)$ be a good polynomial with nonzero roots.

Lemma 1: Let $n$ be a positive integer, and $r$ be a root of $f(x)$ with multiplicity $k$ . Then, $r^{n}$ is also a root of $f(x)$ with multiplicity at least $k$ .

Proof: If $r^n=r$ , this is trivial. Otherwise, let $f(x)=(x-r)^{k}(x-r^{n})^{u}p(x)$ , where $r$ and $r^{n}$ are not roots of $p(x)$ . Then, as $f(x)|f(x^{n})$ , $r$ is a root $f(x^{n})$ with multiplicity at least $k$ . Thus, $(x-r)^{k} | (x^{n}-r)^{k}(x^{n}-r^{n})^{u}p(x^{n})$ . However, because $r^{n}$ is not a root of $p(x)$ , $r$ is not a root of $p(x^{n})$ . Also, as $r^{n}-r \not= 0$ , $r$ is also not a root of $x^{n}-r$ . Thus, $(x-r)^{k} | (x^{n}-r^{n})^{u}$ , so $u \geq k$ , as desired.

Lemma 2: All roots of $f(x)$ have magnitude one.

Proof: Suppose $f(x)$ has a root of magnitude greater than one. Let $r$ be a root with greatest magnitude. Then, by Lemma 1, $r^{2}$ is a root of $f(x)$ , but we picked $r$ to be a root with greatest possible magnitude, so this is a contradiction. Now, suppose that $f(x)$ has a root of magnitude less than one. Let $r$ be a root with least magnitude. Then, by Lemma 1, $r^{2}$ is a root of $f(x)$ , but we picked $r$ to be a root with least possible magnitude, so this is a contradiction.

Lemma 3: All roots of $f(x)$ are roots of unity.

Proof: Suppose $r$ is a root of $f(x)$ . Then, by Lemma 1, $r^{2^{k}}$ , is a root for all $k \geq 0$ . Thus, as $f(x)$ has a finite number of roots, there exist $i \geq 1$ , such that $r=r^{2^{i}}$ . Then, $r^{2^{i}-1}=1$ , so $r$ is a root of unity as desired.

Now, by Lemma 3, if $r$ is a root of $f(x)$ and $r \not= 1$ , then there exist relative prime positive integers $a$ and $b$ such that $r=e^{2 \pi i \frac{a}{b}}$ .

Lemma 4: $f(x)$ is a product of cyclotomic polynomials.

Proof: Let $r=e^{2 \pi i \frac{a}{b}}$ be a root of $f(x)$ with multiplicity $k$ , where $a$ and $b$ are relatively prime. Then, it suffices to show that $f(x)$ is divisible by $\Phi_{b}(x)$ with multiplicity $k$ . Let $q=e^{2 \pi i \frac{m}{b}}$ where $m$ is relatively prime to $b$ . Then, there exists some positive integer $t$ such that $q=r^{t}$ ( $t \equiv ma^{-1} \pmod{b}$ ). Thus, by Lemma 1, $q$ is a root of $f(x)$ with multiplicity at least $k$ . Further, this is true for all $m$ , so $\Phi_{b} (x)$ divides $f(x)$ with multiplicity $k$ as desired.

Lemma 5: If $p$ is a prime and $n$ is a positive integer such that $\Phi_{pn} (x)$ divides $f(x)$ with multiplicity $k$ , then, $\Phi_{n} (x)$ divides $f(x)$ with multiplicity at least $k$ .

Proof: We have $f(x)$ | $f(x^{p})$ . However, $\Phi_{pn} | \Phi_{t}(x^{p})$ if and only if $t=n$ , so as $f(x)$ is a product of cyclotomic polynomials, $\Phi_{n} (x)$ divides $f(x)$ with multiplicity at least $k$ , as desired.

We can easily see that if Lemmas 4 and 5 are satisfied, then $f(x)$ is good. Thus, in order to find all good polynomials of degree four, we start by listing all cyclotomic polynomials of degree 4 or less: $\Phi_{k}$ , for $k=1,2,3,4,5,6,8,10,12$ . We find that all the good polynomials of degree less than or equal to 4 are:

$(x^{4}-1), (x^{3}-1)(x+1), (x^{3}-1)(x-1), (x^{2}-1)^{2}, (x^{2}-1)(x-1), (x-1)^{4}, (x^{3}-1)x, (x^{2}-1)(x-1)x, (x-1)^{3}x, (x^{2}-1)x^{2}, (x-1)^{2}x^{2}, (x-1)x^{3}, x^{4}$

The one that gives the least positive integer value for $f(-3)$ is $f(x)=(x^{3}-1)(x+1)$ , which gives $f(-3)=56$ .

Clearly $f(x)$ divides $f(x^n)$ only if all four roots of $f(x)$ are also roots of $f(x^n)$ . Write $f(x)=(x-a)(x-b)(x-c)(x-d)$ . Then a must be a root of $f(x^n)$ , so we have $a^n=r$ for some root $r$ of $f(x)$ . If the magnitude of a is not zero or $1$ , there are infinitely many distinct values of $a^n$ , but we only have four distinct roots of $f(x)$ . Therefore, all the roots of $f(x)$ must either be zero or be of the form $cis\theta$ . Also, $cis n\theta$ can take on at most four distinct values, and all of these values must be roots of $f(x)$ . Using the former condition it is easy to determine that the only possible values of $\theta$ are $\theta=\frac{\pi}{2}, \pi, \frac{3\pi}{2}, 2\pi, \frac{2\pi}{3}, \frac{4\pi}{3}$ . Now it is a simple matter of testing to find that $f(-3)$ is minimized at $\boxed{56}$ when the roots are $cis\frac{2\pi}{3}, cis\frac{4\pi}{3}, cis2\pi, cis\pi$ .