# Number of irreducible polynomials of degree $r$ in $F_2[x]$

This is admittedly, probably an easy question for the right person here, but I cannot seem to track down an answer. The question itself may not be hard, but the answer is crucial to a math paper I am writing (and I don't know enough number theory).

True or false: There are at least exp$(r)$ irreducible polynomials in $\mathbb{F}_2[x]$ of degree $r$ or less. [I don't care about the hidden constants in the exp$(r)$-notation; could be $2^{\frac{r}{100}}$ or it could be $\frac{2^r}{r}$.]

If True a reference would be terrific.

I am aware that there are roughly $n/\log n$ primes of size $n$ or less for $n$ large, I am trying to adapt that to a polynomial ring where the coefficients are in a characteristic 2 field.

Sloane's OEIS sequence A001037 counts ($n=r$ in your definition):

Number of degree-$n$ irreducible polynomials over $GF(2)$;

number of $n$-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period $n$;

number of binary Lyndon words of length $n$.

The first few terms of the sequence are (for $n=1,2,...$ ) $2,1,2,3,6,9,...$

The formula for the sequence is $$\frac{1}{n}\sum_{d|n}\mu(n/d)\cdot 2^d$$. Since the terms of the sum corresponding to strict divisors $d$ of $n$ are much smaller this almost gives what you want (leading term is $2^n/n=O(2^{n-\log n})$.

There is an old and well-known "prime number theorem" for irreducible polynomials in $\mathbb F_p[x]$ whose proof is much easier than the prime number theorem for $\mathbb Z$. You can find it in many textbooks, for example Ireland-Rosen A Classical Introduction to Number Theory Chapter 7, Section 2.

Theorem The number of monic irreducible degree $n$ polynomials in $\mathbb F_p[x]$ is $$\frac{1}{n}\sum_{d\mid n} \mu(n/d)p^d.$$ It's not hard to see that the $p^n$ term in the sum dominates, so you get $O(p^n/n)$ as desired. The proof is not hard, one first shows that if we let $F_d(x)$ be the product of the monic irreducible polynomials of degree $d$, then $$\prod_{d\mid n} F_d(x) = x^{p^n}-x.$$

• This old theorem is due to Gauss (for prime-order finite fields, the case you describe). See the start of pollack.uga.edu/gauss.pdf and reference [2] there. Maybe I & R make an attribution too, but I don't have it in front of me to check. – KConrad Apr 12 '18 at 6:04
• I hope the authoritative reference for this field is Lidl and Neiderreiter's $\textit{Finite Fields}$ – vidyarthi Sep 25 '19 at 19:26
• @vidyarthi L & N is certainly a great text for all things related to finite fields, but there are lots of other good expositions of this centuries-old theorem, including the I & R book, and I'm sure many others. – Joe Silverman Sep 25 '19 at 20:28