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

Question

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.

Answer 1

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})$.

Answer 2

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. $$