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 '18 at 21:50
  • 2
    $\begingroup$ Also relevant mathoverflow.net/questions/26031/… $\endgroup$ Apr 11 '18 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 '18 at 11:04

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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