# Polynomials $p(x^k)$ with an irreducible factor of bounded degree.

Characterize the polynomials $$f\in\mathbb{Z}[x]$$ with the following property:

There is $$M\in\mathbb{N}$$ such that for all $$k\in\mathbb{N}^*$$ there is an irreducible factor (over $$\mathbb{Q}$$) of $$f(x^k)$$ that has degree at most $$M$$.

If $$x\mid f(x)$$ then $$x\mid f(x^k)$$. Also if $$x-1\mid f(x)$$, then $$x-1\mid f(x^k)$$.

Question: Is it true that these are all such polynomials?

We could assume $$f$$ irreducible with $$f(0)$$ and $$f(1)$$ different from zero.

The linear case we can always make $$f(x^k)$$ itself irreducible for arbitrarily large $$k$$.

Maybe they end up not very related, but at least aesthetically this question has the same flavor as this other question [A square integer matrix with $$k$$-th roots for all $$k$$ is a projection]. Well, I invented this problem out of the linked one.

• A cool question. The cyclotomic polynomials would otherwise come close, but fail when $k$ is divisible by a key prime. For example, if $f(x)=x^4+x^3+x^2+x+1$ is the fifth cyclotomic polynomial, we have $f(x)\mid f(x^k)$ whenever $5\nmid k$. But $f(x^{5^\ell})$ is irreducible for all $\ell>0$, and therefore $f$ fails to qualify. Sep 21, 2022 at 4:51

These polynomials (i.e those for which either $$0$$ or $$1$$ is a root) are the only such polynomials.
There exists some $$c\in\mathbb R$$ for which every root $$z$$ of $$f$$ satisfies $$|z|\leq c$$, and so every root $$z_k$$ of $$f(x^k)$$ satisfies $$|z|\leq c^{1/k}$$. Suppose $$g(x)=\sum_{i=0}^d a_ix^i$$ is an irreducible factor of some $$f(x^k)$$, with $$a_d\neq 0$$. Then $$g$$ has $$d$$ roots $$\lambda_1,\dots,\lambda_d$$ in $$\mathbb C$$, and for every $$0\leq j\leq d$$ $$\left|\frac{a_j}{a_d}\right|=\left|\sum_{\substack{S\subset\{1,2,\dots,d\}\\|S|=j}}\prod_{i\in S}\lambda_i\right|\leq \binom djc^{j/k}.$$ Note that $$a_d$$ divides the leading coefficient $$C$$ of $$f$$, since $$g\in\mathbb Z[x]$$ is a factor, so $$|a_j|\leq \binom djc^{j/k}|a_d|\leq C2^dc^{d/k}.$$ Now, suppose that $$f$$ satisfies the condition, and let $$g_k\mid f(x^k)$$ be a factor of degree at most $$k$$. Every coefficient of $$g_k$$ is at most $$C2^{\deg g_k}c^{\frac{\deg g_k}k}\leq C2^Mc^{M/k}\leq Cc2^M$$ in magnitude. So, there are only finitely many possible polynomials $$g$$ of degree at most $$M$$ which may divide $$f(x^k)$$ for any $$k$$. In particular, there exists some $$g$$ which divides $$f(x^k)$$ for infinitely many $$k$$.
Fix such a $$g$$ irreducible, and let $$z$$ be any root of $$g$$. If $$g(x)$$ divides $$f(x^k)$$, then $$z$$ is a root of $$f(x^k)$$, and so $$z^k$$ is a root of $$f$$. Since there are finitely many roots of $$f$$, one must have $$z^k=z^\ell$$ for some $$k<\ell$$ (as there are infinitely many $$k$$ for which $$z^k$$ is a root of $$f$$). This means that $$z$$ is either $$0$$ or a root of unity. This implies that $$g(x)$$ is either $$x$$ (in which case $$x\mid f(x)$$ and we are done) or some cyclotomic polynomial $$\Phi_n(x)$$. This means that for all sufficiently large $$k$$, some cyclotomic polynomial of degree at most $$M$$ divides $$f(x^k)$$.
Let $$N$$ be the largest integer such that $$\deg \Phi_N\leq M$$, and consider $$f(x^{N!})$$. For every root $$z$$ of $$f(x^{N!})$$, $$z^{N!}$$ is a root of $$f$$. If some $$\Phi_n(x)$$ with $$n\leq N$$ divides $$f(x^{N!})$$, then $$z^{N!}$$ is a root of $$f$$ for every $$n$$th root of unity, but $$z^{N!}=1$$ for these roots. So, $$1$$ must be a root of $$f$$, as desired.
• Very nice! I tried to churn through the Galois theory but it looked messy. Your observation that the roots getting smaller means there are only finitely many possible $g$ is much better. Sep 22, 2022 at 17:01