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.

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Should be $\mu(d)$ in the sum, I assume. $\endgroup$
    – Vladimir Dotsenko
    Commented Jul 6, 2012 at 8:48
  • 1
    $\begingroup$ And now (after the edit) it should be $\mu(k)$ in the sum, I assume. $\endgroup$
    – Tom De Medts
    Commented Jul 6, 2012 at 9:08
  • 1
    $\begingroup$ Ah, I can't seem to type a single equation right. Thanks for the correction. $\endgroup$
    – Gjergji Zaimi
    Commented 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$
    – Denis Serre
    Commented 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$
    – Joe Silverman
    Commented Jul 6, 2012 at 14:02
14
$\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.

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

You must log in to answer this question.

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