When is $f(x^d)$ irreducible?

Question

Let $f(x)$ be an irreducible polynomial of degree $n$ over a finite field $\mathbb F_p$. What can we say about $f(x^d)$? When is it irreducible ?

Answer 1

Here’s a stab at a partial answer. Let $n$ be the degree of the original polynomial $f(x)$ over $\Bbb F_p$, so that any root $\alpha$ generates the field $\Bbb F_q$, $q=p^n$. The polynomial $f(x^d)$, of degree $nd$, is irreducible over $\Bbb F_p$ if and only if a root $\beta$ generates the field $\Bbb F_{q^d}$. The polynomial for $\beta$ over $\Bbb F_q$ is $x^d-\alpha$, of course, and we’re asking, precisely, whether this is irreducible over that field.

So I think the question boils down to this apparently simpler one: If $\alpha\in\Bbb F_q$, under what conditions is $x^d-\alpha$ irreducible over that field?

This certainly depends crucially on the multiplicative period of $\alpha$, as commenters have already noted. If $\alpha=i\in\Bbb F_9$, then $\sqrt\alpha$ is already in the same field, (because the multiplicative group is of order $8$). On the other hand, if $\alpha=1+i$ in that field, this is a generator of the multiplicative group (period eight), and $x^2-\alpha$ is irreducible, generating the field of cardinality $9^2=81$. Just to bring this back to $\Bbb F_3$, this is saying (since the polynomial for $i$ is $x^2+1$) that $x^4+1$ is not irreducible over the prime field, but (since the polynomial for $1+i$ is $x^2+x+2$) the polynomial $x^4+x^2+2$ is irreducible over $\Bbb F_3$.

So far so good. What values of $d$ are good, which are bad? Certainly anything divisible by the characteristic is bad, and more generally anything prime to $q-1$ is bad too, because a cyclic group of order $m$ automatically has $n$-th roots of all elements if $\gcd(m,n)=1$.

Indeed, that same argument shows that if $d=d'r$ where $r$ is relatively prime to $q-1$, adjoining the $d$-th root of an element is the same thing as adjoining the $d'$-th root. So we want $d$ to have among its prime divisors only the prime divisors of $q-1$.

And I think this answers the question completely if $\alpha$ is a generator of the cyclic multiplicative group of the field $\Bbb F_q$: $d$ must have for its prime divisors only primes that occur in $q-1$. There are a couple of gaps that I believe I know how to fill, but this posting is already too long.

Answer 2

Edit: The answer is wrong (Vladimir's comment below gives a counterexample) - it only shows the following: ``Let $f(x) \in \mathbb{F}[x]$ be separable and have no root in $\mathbb{F}$. Assume $\deg(f) \geq 2$ and $d$ is coprime to the characteristic of $\mathbb{F}$. Then $f(x^d)$ is also separable and has no root in $\mathbb{F}$.'' As Loren points out, this is far from guaranteeing irreducibility.

It seems Jason's comment gives the only exceptions: assume $d$ is prime to $p$ and $\deg(f) \geq 2$. Consider the factorization of $f$ in the algebraic closure of your field $\mathbb{F}$, say $f = \prod_{i=1}^e (x-a_i)$. Since $f$ is irreducible, none of these $a_i$ are in $\mathbb{F}$ (this is where we use $\deg(f) \geq 2$) and since it is separable, $a_i \neq a_j$ for $i \neq j$. Then

$f(x^d) = \prod_{i=1}^e (x^d-a_i) = \prod_{i=1}^e \prod_{j=1}^d (x-a_{ij})$

where $a_{ij}$'s are $d$-th roots of $a_i$. None of these $a_{ij}$'s are in $\mathbb{F}$ and none of them are equal. So $f(x^d)$ is irreducible as well.