12
$\begingroup$

When is the cyclotomic polynomial $f(x)$ over a finite field $\mathrm{F}_q$ also the minimal polynomial of some element $\alpha \in \mathrm{F}_q$?

$\endgroup$
0

2 Answers 2

18
$\begingroup$

One can show that the cyclotomic polynomial $\Phi_n(X)$ is irreducible over $\mathbf F_p$ precisely when $p$ has multiplicative order $\varphi(n)$ modulo $n$. This follows from the theory of cyclotomic extensions of $\mathbf Q$.

In particular, if $(\mathbf Z/n\mathbf Z)^\times$ is not cyclic (i.e. unless $n$ is an odd prime power, twice an odd prime power, or $n=2$ or $4$), then $\Phi_n(X)$ is reducible modulo every prime $p$, despite being irreducible over $\mathbf Q$!

$\endgroup$
2
  • 4
    $\begingroup$ Do you know when is $\Phi_n$ irreducible over $\mathbf F_{p^k}$? Thanks. $\endgroup$ Oct 2, 2016 at 13:48
  • $\begingroup$ @caffeinemachine : have a look to this, for instance corollary 48 (here $q=p^r$, as written just before theorem 41). $\endgroup$
    – Watson
    Nov 8, 2016 at 19:06
9
$\begingroup$

In general, a polynomial $f\in F[X]$ is the minimal polynomial of its roots over $F$ if and only if $f$ is irreducible over $F$. Cyclotomic polynomials provide no exception.

However, while cyclotomic polymomials are irreducible over $\mathbb Q$, not all of them are irreducible when considered as a polynomial over a finite field. For example, over $\mathbb F_2$ the $7$th cyclotomic polynomial $\Phi_7 = X^6 + X^5 + X^4 + X^3 + X^2 + X + 1$ factors into two factors of degree $3$: $$ \Phi_7 = (X^3 + X + 1)(X^3 + X^2 + 1) $$ Hence $\Phi_7\in\mathbb F_2[X]$ is not irreducible and therefore not the minimal polynomial of its roots.

Note: This was written as a response to an earlier version of the question.

$\endgroup$
6
  • $\begingroup$ Please explain it for the following example. Given finite field $\mathrm{F}_q$, I have a decomposition $x^n-1=\prod_{i=0}^{m-1}f_i(x)$ over $\mathrm{F}_q$, where all $f_i(x)$ are cyclotomic. I am not sure that all $f_i(x)$ are minimal polynomials for some elements from extension $[\mathrm{F}_q^r : \mathrm{F}_q]$, where $r$ is a smallest number that $n$ divides $q^r - 1$. What is wrong in that? $\endgroup$ Oct 21, 2013 at 11:41
  • 1
    $\begingroup$ @PiotrSemenov: I've added information on cyclotomic polynomials over finite fields to my answer. $\endgroup$
    – azimut
    Oct 21, 2013 at 11:54
  • $\begingroup$ Thanks! So I did a mistake while suggesting that cyclotomic polynomials are also irreducible in case of finite fields. $\endgroup$ Oct 21, 2013 at 12:18
  • 4
    $\begingroup$ +1: In some sense an even smaller counterexample is $$\Phi_3(X)=X^2+X+1=(X-2)(X-4)\in\Bbb{F}_7[X].$$ Or even $\Phi_3(X)=(X-1)^2\in \Bbb{F}_3[X].$ $\endgroup$ Oct 22, 2013 at 7:00
  • 1
    $\begingroup$ @JyrkiLahtonen: That's true. For my example, I decided to go with an example over $\mathbb F_2$. Here, the smallest reducible one is $\Phi_4 = (X + 1)^2$, which might be a bit misleading. So I ended up with $\Phi_7$. $\endgroup$
    – azimut
    Oct 22, 2013 at 7:10

Not the answer you're looking for? Browse other questions tagged .