Irreducible cyclotomic polynomial

I want to know if there is a way to decide if a cyclotomic polynomial is irreducible over a field $\mathbb{F}_q$?

Solution 1:

Yes there is.

Assuming $\gcd(q,n)=1,$ the $n^{th}$ cyclotomic polynomial $\Phi_n(x)\in\mathbb{Z}[x]$ will remain irreducible (after reduction mod $p$) in $\mathbb{F}_q[x]$ if and only if the residue class of $q$ generates the multiplicative group $\mathbb{Z}_n^*$ of residue classes coprime to $n$.

This is because if $z$ is a root of $\Phi_n(x)$ in an extension of $\mathbb{F}_q$, then its conjugates are $z^q, z^{q^2},$ et cetera. If you get the same number of conjugates as you would get over $\mathbb{Q}$, then you are done. But over $\mathbb{Q}$ the conjugates are exactly $z^a, \gcd(a,n)=1, 1\le a<n$.

More details. Let $z$ be a primitive $n^{th}$ root of unity in an extension $\mathbb{F}_q$. Let $\mathbb{F}_q[z]=\mathbb{F}_{q^k}$. Because the multiplicative group of $\mathbb{F}_{q^k}$ is cyclic of order $q^k-1$, we know that $k$ is the smallest positive integer with the property that $n\mid q^k-1$. By the Galois theory of finite fields the minimal polynomial of $z$ is $$ m(x)=(x-z)(x-z^q)(x-z^{q^2})\cdots(x-z^{q^{k-1}}). $$ This will always be a factor of the cyclotomic polynomial $\Phi_n(x)$. The roots of the latter are $z^a, 1\le a<n, \gcd(a,n)=1$. The polynomial $\Phi_n(x)$ is thus irreducible precisely when the two sets of roots are the same.

Here $z^{q^i}=z^a$ if and only if $q^\ell\equiv a\pmod{n}$. Therefore all the primitive roots $z^a$ are zeros of $m(x)$ only, if all the exponents $a$ are congruent to a power of $q$ modulo $n$.

All of the above assumed that $\gcd(n,q)=1$. Let us next consider the case where that is not true. Here $q$ is the order of a finite field, so it is a power of a prime number $p$. Therefore $\gcd(n,p)>1$ if and only if $p\mid n$, so we can write $n=mp^\ell$ for some integer $\ell\ge1$, $m$ coprime to $p$. Then we have in the ring $\mathbb{F}_p[x]$ the factorization $$ x^n-1=(x^m-1)^{p^a} $$ as a consequence of Freshman's dream: $$ (a+b)^p=a^p+b^p. $$ Therefore all the roots of $\Phi_n(x)$ in $\overline{\mathbb{F}_q}$ are actually roots of $x^m-1$ as well. Hence any one of them has at most $\phi(m)<\phi(n)$ conjugates. Therefore $\Phi_n(x)$ cannot be irreducible in $\mathbb{F}_q[x]$. (the part in italics is incorrect, see below)

Edit: As pointed out by Yecabel, the last claim is a touch too sweeping. We do see that any zero of $\Phi_n(x)$ has at most $\phi(m)$ conjugates. But, it is possible that $\phi(m)=\phi(n)$. As $n=mp^\ell$, $p\nmid m$, we have $\phi(n)=\phi(m) p^{\ell-1}(p-1)$. So for $\phi(n)$ to be equal to $\phi(m)$ we need that $p=2$ and $\ell=1$. Leaving the special case of $q$ even, $n=2m$, $m$ odd, to deal with. We always have $\Phi_{2m}(x)=\Phi_m(-x)$. And in characteristic two $\Phi_m(-x)=\Phi_m(x)$, so $\Phi_n(x)$ is irreducible if and only if $\Phi_m(x)$ is. The conclusion is thus

If $\gcd(q,n)>1$ then $\Phi_n(x)\in\Bbb{Z}[x]$ stays irreducible in $\Bbb{F}_q[x]$ only, if $q$ is a power of two, $n=2m$, $2\nmid m$, and $\Phi_m(x)$ stays irreducible (see the result in the main case).