9
$\begingroup$

Let $p$ be a prime number. The number of monic irreducible polynomial $P\in{\mathbb F}_p[X]$, in terms of the degree $d$, begins with $${\rm irr}(1)=p,\qquad{\rm irr}(2)=\frac{p(p-1)}2,\qquad{\rm irr}(3)=\frac{p(p^2-1)}3,\qquad{\rm irr}(4)=\frac{5p^2(p^2-1)}{12}.$$ This seems to be the beginning of a nice sequence of polynomials in $p$. Does someone know the general formula?

Motivation. As F. Brunault pointed out to me, there is a polynomial $\Pi_{n,p}$ that vanishes over ${\bf M}_n({\mathbb F}_p)$. Just take the lcm of all the polynomials of degree $n$ over $F_p$. In closed form, it is the product of all the irreducible polynomials of degree $d\le n$, to the power $[\frac{n}{d}]$ (integral part). The degree of $\Pi_{n,p}$ is $$\delta(n)=\sum_{d\le n}d[\frac{n}{d}]{\rm irr}(d).$$ In terms of $n$, this degree is $$\delta(1)=p,\quad\delta(2)=p(p+1),\quad\delta(3)=p(p^2+p+1),\quad\delta(4)=\frac13p(p+1)(5p^2-2p+3).$$

Edit. The values given above for $n=4$ are erroneous.

$\endgroup$
3

2 Answers 2

17
$\begingroup$

The product of all monic irreducible polynomials of degree dividing $d$ in $\mathbb F_q[x]$ is $$x^{q^d}-x,$$ so from Mobius inversion we get the number of irreducible polynomials of degree $d$ is $$M _d (q) = \frac{1}{d} \sum _{k | d} \mu(k) q ^{d/k} $$ This is known as the necklace polynomial.

$\endgroup$
6
  • 2
    $\begingroup$ Should be $\mu(d)$ in the sum, I assume. $\endgroup$ Jul 6, 2012 at 8:48
  • 1
    $\begingroup$ And now (after the edit) it should be $\mu(k)$ in the sum, I assume. $\endgroup$ Jul 6, 2012 at 9:08
  • 1
    $\begingroup$ Ah, I can't seem to type a single equation right. Thanks for the correction. $\endgroup$ Jul 6, 2012 at 9:12
  • 2
    $\begingroup$ Thanks; I see the reason: $x^{q^d}-x=0$ is the equation of $K={\mathbb F}_{q^d}$ over $k={\mathbb F}_q$, and every element of $K$ has a unique mimimal polynomial. $\endgroup$ Jul 6, 2012 at 9:14
  • 1
    $\begingroup$ And, as I'm sure everyone knows, in this sum for $M_d(q)$, the $q^d$ term is strictly larger than $\sum_{k|d,k>1} q^{d/k}$, which is one way to prove that for every $d\ge1$ and every prime power $q$ there exists an irreducible polynomial of degree $d$, and hence there exists a field with $q^d$ elements. $\endgroup$ Jul 6, 2012 at 14:02
13
$\begingroup$

Gjergji Zaimi already said it all, but I want to point out a tiny bit longer but equally cute way to derive the same formula. Every monic polynomial over $\mathbb{F}\_q$ decomposes into a product of irreducibles uniquely, hence we have a formal power series equality $$ \frac{1}{1-qt}=\prod_{k\ge 1}\frac{1}{(1-t^k)^{M_k(q)}} $$ (indeed, the coefficient of $t^n$ on the left is the number of monic polynomials of degree $n$, and the coefficient of $t^n$ on the right counts the decompositions into irreducibles with multiplicities). Taking logarithmic derivatives, one can do the M\"obius inversion and arrive at the formula pointed out by Gjergji.

$\endgroup$
1
  • 7
    $\begingroup$ This is of course the infinite product formula for the Weil zeta function of $\mathbb A^1$. $\endgroup$
    – Will Sawin
    Jul 6, 2012 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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