# All Polynomials Such That All Roots of $f(x)$ are in $f(x^2)$

Let there be a polynomial, $$f(x)$$ and denote $$g(x) = f(x^2)$$.

Find all monic polynomials, f, with complex coefficients, such that for all $$r_i$$ satisfying $$f(r_i) = 0$$, $$g(r_i) =0$$ as well. (source: An Old (first written in 1985) Indian Math Book Filled With Interesting Problems)

What I've basically broken the problem down to is that if all roots of $$f$$ are in $$g$$, then $$f$$ must be divisible by $$g$$.

Starting off with degree $$1$$, it's pretty easy to see that the possibilities are $$f(x) = x$$ and $$f(x) = x-1$$.

For degree $$2$$, I used polynomial long division to get the following polynomials: $$f(x) = x^2, x(x-1), x^2 - 1, x^2 + x + 1,$$ and $$(x-1)^2.$$

Afterwards, I realized that if $$p(x)$$ and $$q(x)$$ both work, then so much $$p(x) \cdot q(x)$$.

Furthermore, I saw that all cyclotomic polynomials work.

Other than polynomial long division (which can get quite tedious and long), are there any easier ways to determine all functions $$f$$ that work for higher degrees (such as $$3$$ or $$4$$ or $$5$$)?

"If all roots of $$f$$ are in $$g$$, then $$f$$ must be divisible by $$g$$" is not quite right; first, you mean $$f$$ must divide $$g$$, and second, it's possible that the multiplicities of the roots of $$f$$ are bigger than those of $$g$$. E.g. we could have $$f(z) = z^2, g(z) = z$$.

Anyway, the question is to find all monic polynomials $$f$$ such that the set of roots of $$f$$ is closed under the squaring operation $$r \mapsto r^2$$. $$f$$ can have the root $$0$$ with any multiplicity; we now restrict our attention to nonzero roots $$r$$ only. If $$|r| \neq 1$$ then repeated squaring $$k \mapsto r^{2^k}$$ rapidly sends the absolute value to either $$0$$ or $$\infty$$, and in particular would imply that $$f$$ has infinitely many roots, so all roots of $$f$$ must have absolute value exactly $$1$$. If $$r = e^{2 \pi i t}$$ then $$r^{2^k} = e^{2^{k+1} \pi i t}$$ which takes on infinitely many distinct values unless $$t$$ is rational.

So all of the roots of $$f$$ must be roots of unity, and moreover if a primitive $$d^{th}$$ root of unity $$\zeta_d$$ is a root then $$\zeta_d^{2^k}$$ must all be a root for all $$k \ge 1$$. So the answer is exactly the products of copies of $$f(z) = z$$ and polynomials of the form

$$f(z) = \prod_{k=0}^{n-1} (z - \zeta_d^{2^k})^{m_k}$$

where $$\zeta_d$$ is some primitive $$d^{th}$$ root of unity and $$n$$ is the smallest positive integer such that $$2^n \equiv 2^i \bmod d$$ for some $$i < n$$ and the multiplicities $$m_k \ge 1$$ are arbitrary positive integers. ($$i = 0$$ if $$d$$ is odd but not otherwise.)

The answer is much nicer if we ask for $$f$$ to have integer coefficients. Then if $$f(z)$$ has $$\zeta_d$$ as a root of multiplicity $$m$$ it must be divisible by the cyclotomic polynomial $$\Phi_d(z)$$ with multiplicity $$m$$. If $$d$$ is odd then the roots of $$\Phi_d(z)$$ are already closed under squaring; otherwise, if $$d$$ is even then squaring the roots of $$\Phi_d(z)$$ produces exactly the roots of $$\Phi_{\frac{d}{2}}(z)$$, so $$f$$ must also be divisible by $$\Phi_{\frac{d}{2}}(z)$$. Continuing in this way we conclude that $$f$$ is a product of copies of $$z$$ and cyclotomic polynomials $$\Phi_{d_i}(z)$$ with the property that the set of $$d_i$$ which occur is closed under division by $$2$$. This can be restated in a slightly nicer way as follows: if $$d$$ is odd then

$$\Phi_d(z) \Phi_{2d}(z) \Phi_{4d}(z) \dots \Phi_{2^k d}(z) = \Phi_d(z^{2^k})$$

so equivalently $$f$$ is a product of copies of $$z$$ and polynomials of the form $$\Phi_d(z^{2^k})$$ where $$d$$ is odd.

In particular, your claim that all cyclotomic polynomials work is not quite right, and $$\Phi_2(z) = z + 1$$ is the smallest counterexample.

• thanks! so in your equation involving f(z) = the product, why did you put the $2^k$ exponent? I didn't get that part... Also, what does $e_k$ mean? – user855084 Jan 5 at 4:59
• @Arjun: those are the values you get from repeatedly squaring $\zeta_d$. The $e_k$ are arbitrary positive integers (which I'm renaming $m_k$ for "multiplicity"; sorry for the confusion). – Qiaochu Yuan Jan 5 at 5:01
• That makes sense. For curiosity sake, let's say I needed $f$to divide $g$. Then, would all of the roots need to have multiplicity $1$ (and so, all of the $m_k = 1$?) – user855084 Jan 5 at 5:04
• sorry for the double comment but I realized there was another thing I didn't quite get. I didn't really understand the logic behind why each of the roots must have absolute value of $1$. If $f(r) = 0$, and I take $g(x) = f(x^2)$, why am I squaring $r$? Aren't the roots of $f(x^2)$ just the roots of $f(x)$ square rooted? Where does the squaring come from? – user855084 Jan 5 at 5:07
• @Arjun: 1) no, it's a bit more annoying than that. If we consider $d^{th}$ roots of unity for $d$ odd then the roots would all need to have the same multiplicity, which could be bigger than $1$. For $d$ even the condition on multiplicities is more annoying to state (basically because squaring is no longer invertible). – Qiaochu Yuan Jan 5 at 5:10