Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T04:16:24Z http://mathoverflow.net/feeds/question/769 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/769/exhibit-an-explicit-bijection-between-irreducible-polynomials-over-finite-fields Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words. Qiaochu Yuan 2009-10-16T17:42:46Z 2012-04-26T01:36:48Z <p>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 <a href="http://en.wikipedia.org/wiki/Lyndon_word" rel="nofollow">Lyndon words</a> of length $n$ over an alphabet of size $q$. Does there exist an explicit bijection between the two sets?</p> http://mathoverflow.net/questions/769/exhibit-an-explicit-bijection-between-irreducible-polynomials-over-finite-fields/776#776 Answer by Alon Amit for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words. Alon Amit 2009-10-16T18:30:06Z 2009-10-16T18:30:06Z <p>I believe such a bijection is presented in</p> <p>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.</p> <p>but I don't have immediate access to this paper - I'm pretty sure it's in there though.</p> http://mathoverflow.net/questions/769/exhibit-an-explicit-bijection-between-irreducible-polynomials-over-finite-fields/1800#1800 Answer by Diego de Estrada for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words. Diego de Estrada 2009-10-22T03:53:30Z 2009-10-22T03:53:30Z <p>In Reutenauer's "Free Lie Algebras", section 7.6.2:</p> <p>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<sup>n</sup> 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;<sup>q</sup>, ..., &theta;<sup>q<sup>n-1</sup></sup>} is a linear basis of K over F. </p> <p>With each word w = a<sub>0</sub>...a<sub>n-1</sub> of length n on the alphabet F, associate the element &beta; of K given by &beta; = a<sub>0</sub>&theta; + a<sub>1</sub>&theta;<sup>q</sup> + ... + a<sub>n-1</sub> &theta;<sup>q<sup>n-1</sup></sup>. 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.</p> http://mathoverflow.net/questions/769/exhibit-an-explicit-bijection-between-irreducible-polynomials-over-finite-fields/3520#3520 Answer by jj-joerg-arndt for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words. jj-joerg-arndt 2009-10-31T09:13:35Z 2009-10-31T09:13:35Z <p>See section 38.10 "Generating irreducible polynomials from Lyndon words" of <a href="http://www.jjj.de/fxt/#fxtbook" rel="nofollow">http://www.jjj.de/fxt/#fxtbook</a></p> http://mathoverflow.net/questions/769/exhibit-an-explicit-bijection-between-irreducible-polynomials-over-finite-fields/95215#95215 Answer by potap for Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words. potap 2012-04-26T01:36:48Z 2012-04-26T01:36:48Z <p>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. </p>