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.

  • 4
    $\begingroup$ See necklace polynomials: en.wikipedia.org/wiki/Necklace_polynomial $\endgroup$ Apr 11, 2018 at 21:50
  • 2
    $\begingroup$ Also relevant mathoverflow.net/questions/26031/… $\endgroup$ Apr 11, 2018 at 22:34
  • 2
    $\begingroup$ I suggest keeping the question open as a reference even though the answer is well known to specialists in Number Theory and Combinatorics because people in other areas of math sometimes need this too. $\endgroup$
    – user6976
    Apr 12, 2018 at 11:04

2 Answers 2


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

  • $\begingroup$ 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. $\endgroup$
    – KConrad
    Apr 12, 2018 at 6:04
  • $\begingroup$ I hope the authoritative reference for this field is Lidl and Neiderreiter's $\textit{Finite Fields}$ $\endgroup$
    – vidyarthi
    Sep 25, 2019 at 19:26
  • $\begingroup$ @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. $\endgroup$ Sep 25, 2019 at 20:28

You must log in to answer this question.

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