Question A How many monic irreducible polynomials of degree 6 in $F_{5}[X]$

Question B Give an example of an irreducible polynomial of degree 6 in


Idea for a Such a polynomial would be of the form: $f(x)=x^6+bx^5+cx^4+dx^3+ex^2+fx+g$ with $b, c, d, e, f, g \in${$0, 1, 2, 3, 4$}. $f(x)$ is irreducible if it has no linear factors, yet there are too many unknowns to find them. So I am not sure how to prove this general statement

Idea for b So I need to find a polynomial of degree 6 such that $0, 1, 2, 3, 4$ are roots. Take $f(x)=x^6+b$. I tried $f(x)$ for all values $0, 1, 2, 3, 4$ and narrowed it down to $b=3$ being the only case where f(x) of this form has no roots. Hence $f(x)=x^6+3$ Is this ok?

  • $\begingroup$ You could try a generalized sieving argument using the irreducible polynomials that you know of already $\endgroup$ – TomGrubb Jan 12 '16 at 18:57
  • $\begingroup$ You may, for instance, assume right from the start that $a = 1$ and $g \neq 0$. That cuts it down a notch, but it's still not brute-forcable in practice. More theory is apparently needed. $\endgroup$ – Arthur Jan 12 '16 at 19:01
  • $\begingroup$ Calculate the irreducible polynomials of lower degree (1,2,3,4,5) and multiply them to get all the reducible polynomials of degree 6, then exclude them. Notice that you can do that inductively! $\endgroup$ – Maffred Jan 12 '16 at 19:02
  • $\begingroup$ first prove that all the polynomials of degree $1$ are independent (thus irreductible). then, find a way to transform $ax^2 + bx + c$ in $(x+d)^2+e$ and find a criterion to say if it is irreductible or not. then, count all them and check if you have enough to span all the degree $3$ polynomials or not. and do the same for degree $4$ and $5$ ? $\endgroup$ – reuns Jan 12 '16 at 19:05
  • $\begingroup$ @Maffred thanks for your replies. Is there a way to find just the number of such irreducible polynomials, in the monic case? $\endgroup$ – thinker Jan 12 '16 at 19:11

I’ll explain how to find the number of monic irreducibles of degree $6$ over $\Bbb F_5$, and I hope that the general method will be obvious from this example. On the other hand, finding one of them is another kettle of fish.

For ease in typing, I’ll call $k_n$ the field with $5^n$ elements. Then $\Bbb F_5=k_1$, $\Bbb F_{25}=k_2$, etc. I want to consider $k_6$. It has three proper subfields, namely $k_1$, $k_2$, and $k_3$. Let’s let $N_m$ be the number of elements $\alpha$ of $k_6$ with the property that $\alpha\in k_m$ but in no proper subfield of $k_m$.

Let’s notice two things: first, that we have gotten a partition of the set $k_6$ into four disjoint sets, so that $N_1+N_2+N_3+N_6=5^6$, and second, that such an element $\alpha\in k_m$ not in a proper subfield has exactly $m$ conjugates (including itself) over $\Bbb F_5$, and the monic polynomial whose roots are those conjugates will be an $\Bbb F_5$-irreducible polynomial of degree $m$. Furthermore, if we call $I_m$ the number of monic irreducibles of degree $m$, we have $mI_m=N_m$. Therefore, we have: $$ \begin{align} 5^6&=N_1+N_2+N_3+N_6&\text{and more generally}\\ 5^m&=\sum_{d|m}N_d&\text{for any $m$}\\ N_m&=\sum_{d|m}\mu(d)5^{m/d}=mI_m\,, \end{align} $$ where $\mu$ is the Möbius function. For our special case $\mu(1)=\mu(6)=1$ and $\mu(2)=\mu(3)=-1$. In particular, the number of irreducible monic sextics over $\Bbb F_5$ is $$ I_6=\frac16\bigl(5^6-5^3-5^2+5\bigr)=2580 $$

  • $\begingroup$ For the other kettle of fish: there are $5^6$ polynomials altogether, so $2580/5^6 \approx 17\%$ are irreducible. It might not take too long to guess one. $\endgroup$ – Ethan Bolker Jan 12 '16 at 20:00
  • $\begingroup$ Yes, @EthanBolker, (1): hi!, and (2) I didn’t want to worry about proving irreducibility of a polynomial I wasn’t friends with. $\endgroup$ – Lubin Jan 12 '16 at 20:03
  • $\begingroup$ (1) Hi. (2) Wolfram alpha will factor polynomials mod p so random search should be reasonably quick.If the OP trusts the software that will answer his question. Two tries ar wolframalpha.com found $x^6 + x + 2$. . $\endgroup$ – Ethan Bolker Jan 12 '16 at 20:09

Lubin showed you how to calculate the number of sextic monic irreducibles.

Here is one: $$ p(x)=x^6+x^3+1. $$ You may (should?) recognize this as the ninth cyclotomic polynomial $\Phi_9(x)=(x^9-1)/(x^3-1)$. Those are always irreducible over $\Bbb{Q}$. Over a finite field their irreducibility is not given, but it is easy to test using the following general result.

Fact. The cyclotomic polynomial $\Phi_n(x)$ of order $n$ and degree $\phi(n)$ remains irreducible modulo a prime $p, p\nmid n,$ if and only if $m=\phi(n)$ is the smallest positive integer $m$ with the property $p^m\equiv1\pmod n$.

Proof. The condition $p\nmid n$ means that there exists an $n$th primitive root of unity $\zeta$ in some extension field $K=\Bbb{F}_{p^m}$ of $\Bbb{F}_p$. The minimal polynomial $m(x)$ of $\zeta$ over $\Bbb{F}_p$ will be a factor of $\Phi_n(x)$, so we only need to find the degree of $m(x)$. But it is a basic fact about finite fields that the multiplicative group of $K$ is cyclic of order $p^m-1$. So $K$ contains a primitive $n$th root of unity if and only if $n\mid (p^m-1)$. Consequently $\deg m(x)$ is the smallest integer $m$ such that $n\mid (p^m-1)$. Q.E.D.

In your example case it is easy to see that with $n=9, p=5$ we get $m=6$. This is equivalent to showing that the residue class $\overline{5}$ modulo nine is a generator of the group $\Bbb{Z}_9^*$.

Caveat: There is no guarantee that an irreducible cyclotomic polynomial of the desired degree exists. It is just one of the first families to check, because testing is easy using the above fact.

  • $\begingroup$ nice explanation $\endgroup$ – Bhaskara-III Jan 13 '16 at 13:10

Hint: We have 5 pol of degree 1, they are irreducible. How many reducible polynomials of degree $2$ are there? They are $(x-a)(x-b)$ with $a,b \in \mathbb Z_5$ thus they are 15 (care of commutations). How many in general of degree 2? 25. So there are 10 irreducible polynomials of degree 2. How many reducible of degree 3? How many in total? $\cdots$ Go on this way!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.