6
$\begingroup$

The title of Sloane's A001037 is: 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(\frac{n}{d})\cdot 2^d$.

I am familiar with the derivation given by Wilf in Generatingfunctiontology on page 62. This derivation explains why the formula enumerates binary Lyndon words and equivalently the "$n$ bead necklaces" statement in the title.

I know the 2 irreducible polynomials of degree 1 are $x$ and $x+1$. The degree 2 polynomial is $x^2+x+1$. The degree 3 polynomials are $x^3+x^2+1$ and $x^3+x+1$. The degree 4 polynomials are $x^4+x+1$, $x^4+x^3+x^2+x+1$ and $x^4+x^3+1$.

The binary Lyndon words are: $a(1)=2=\#\{"0","1"\}$, $a(2)=1=\#\{"01"\}$, $a(3)=2=\#\{"001","011"\}$, $a(4)=3=\#\{"0001","0011","0111"\}$

I would like to know if there is an easy correspondence between these objects or if there is some explanation as to why the formula counts the irreducible polynomial over $GF(2)$.

$\endgroup$
  • 3
    $\begingroup$ I don't think there is an easy correspondence, but there is a non-canonical bijection; see mathoverflow.net/questions/769/… . $\endgroup$ – darij grinberg Dec 15 '15 at 0:16
  • $\begingroup$ @darijgrinberg, it's exactly as (non)canonical as finding a normal basis. Other than that it is quite easy (see answer). $\endgroup$ – zyx Dec 15 '15 at 0:56
6
$\begingroup$

Necklaces and Lyndon words (of the same size) count the same objects. Each necklace represents an equivalence class with respect to rotation, and the Lyndon word is way to choose a unique representative of each class. So the more canonical equivalence may be from necklaces to irreducible polynomials.

Monic irreducible polynomials of degree $n$ are the same as Galois orbits of size $n$. Galois groups of finite fields being cyclic, those are cyclic length $n$ Galois orbits, which (by the degree of the irreducible polynomial) are in the unique degree $n$ extension of the finite field.

What does such an orbit look like? The degree $n$ extension of finite field $F$ is an $n$ dimensional vector space over $F$. It has a basis on which the Galois group acts by permutations, in other words by a cyclic action of order $n$. Given the basis we have the correspondence: elements of $F^n$ are necklaces, elements of $F$ are the colors of the beads in the necklace, the Galois group rotates the necklaces, Galois orbits are the sets of roots of monic irreducible polynomials.

Nothing requires $|F|=2$ in this argument.

$\endgroup$

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.