Let $q$ be a power of a prime. It's well-known that the function $B(n, q) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d$ counts both the number of irreducible polynomials of degree $n$ over $\mathbb{F}_q$ and the number of Lyndon words of length $n$ over an alphabet of size $q$. Does there exist an explicit bijection between the two sets?
Irreducible Polynomials and Lyndon Words – Explicit Bijection
co.combinatoricsfinite-fieldsnt.number-theory
Best Answer
In Reutenauer's "Free Lie Algebras", section 7.6.2:
A direct bijection between primitive necklaces of length $n$ over $F$ and the set of irreducible polynomials of degree $n$ in $F[x]$ may be described as follows: let $K$ be the field with $q^n$ elements; it is a vector space of dimension $n$ over $F$, so there exists in $K$ an element $\theta$; such that the set $\{\theta, \theta^q, ..., \theta^{q^{n-1}}\}$ is a linear basis of $K$ over $F$.
With each word $w = a_0\cdots a_{n-1}$ of length $n$ on the alphabet $F$, associate the element $\beta$ of $K$ given by $\beta = a_0\theta + a_1\theta^q + \cdots + a_{n-1} \theta^{q^{n-1}}$. It is easily shown that to conjugate words $w, w'$ correspond conjugate elements $\beta, \beta'$ in the field extension $K/F$, and that $w \mapsto \beta$ is a bijection. Hence, to a primitive conjugation class corresponds a conjugation class of cardinality $n$ in $K$; to the latter corresponds a unique irreducible polynomial of degree $n$ in $F[x]$. This gives the desired bijection.