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?
$\begingroup$
$\endgroup$
1
asked Oct 16, 2009 at 17:42
-
$\begingroup$ What was your motivation for this? $\endgroup$– Robert FrostCommented Jul 12, 2023 at 14:57
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
3
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.
answered Oct 16, 2009 at 18:30
-
$\begingroup$ I don't seem to have access to it either, but at least one other paper (<a href="jstor.org/stable/2001573">Berstel and Reutenauer</a>) suggests that this is an open problem. Indeed I have essentially the same motivation as them for asking this question, so I suppose I should've read this paper more carefully. $\endgroup$ Commented Oct 16, 2009 at 18:43
-
$\begingroup$ A tiny bit of additional evidence (still not conclusive): springerlink.com/index/P6X9P2BV73L2X2GG.pdf "As there exists a bijection between Lyndon words over an alphabet of cardinality k and irreducible polynomials over Fk [10]..." where the reference [10] is to Golomb's paper. $\endgroup$ Commented Oct 16, 2009 at 19:12
-
1$\begingroup$ To get the bijection from algebraic numbers greater than one to base 2 Lyndon words you can just repeatedly chop a square off the long side of rectangle until you get a repeating rectanble shape. Its periodicity gives you the length of the Lyndon word and the degree of the polynomial. The cycle has an associated polynomial. Does this help with your possibly open problem? Also, maybe if you truncate cubes off cuboids it gives you the same over base three and so forth for any base = dimension. I have evidence the golden ratio and zero/infinity in $\Bbb R$ correspond with the field identities. $\endgroup$ Commented Jul 12, 2023 at 14:56
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Does your assignment correspond with the lexicographical order of the Lyndon words? i.e. $\endgroup$ Commented Jul 12, 2023 at 14:45
$\begingroup$
$\endgroup$
See section 38.10 "Generating irreducible polynomials from Lyndon words" of http://www.jjj.de/fxt/#fxtbook
