Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words. - MathOverflow

Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.

2009-10-16T17:42:46Z

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?

Answer by Alon Amit for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.

2009-10-16T18:30:06Z

I believe such a bijection is presented in

S. Golomb. Irreducible polynomials, synchronizing codes, primitive necklaces and cyclotomic algebra. In Proc. Conf Combinatorial Math. and Its Appl., pages 358– 370, Chapel Hill, 1969. Univ. of North Carolina Press.

but I don't have immediate access to this paper - I'm pretty sure it's in there though.

Answer by Diego de Estrada for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.

2009-10-22T03:53:30Z

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ⁿ elements; it is a vector space of dimension n over F, so there exists in K an element θ such that the set {θ, θ^q, ..., θ^{q^n-1}} is a linear basis of K over F.

With each word w = a₀...a_n-1 of length n on the alphabet F, associate the element β of K given by β = a₀θ + a₁θ^q + ... + a_n-1 θ^{q^n-1}. It is easily shown that to conjugate words w, w' correspond conjugate elements β, β' in the field extension K/F, and that w \mapsto β 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.

Answer by jj-joerg-arndt for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.

2009-10-31T09:13:35Z

See section 38.10 "Generating irreducible polynomials from Lyndon words" of http://www.jjj.de/fxt/#fxtbook

Answer by potap for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.

2012-04-26T01:36:48Z

The correspondence invented by Golomb relies on the choice of a primitive element a in the field of order q^n. Then, to each Lyndon word L=(l_0,l_1,...,l_{n-1}) one assigns the primitive polynomial having as a root the element a^{m(L)} where m(L) is the integer sum of l_i*q^i over i=0,1,...,n-1.