Exhibe una biyección explícita entre polinomios irreducibles sobre campos finitos y palabras de Lyndon.

Question

Sea $q$ una potencia de un primo. Es bien sabido que la función $B(n, q) = \frac{1}{n} \sum_{d | n} \mu \left( \frac{n}{d} \right) q^d$ cuenta tanto el número de polinomios irreducibles de grado $n$ sobre $\mathbb{F}_q$ como el número de palabras de Lyndon de longitud $n$ sobre un alfabeto de tamaño $q$. ¿Existe una biyección explícita entre los dos conjuntos?

Answer 1

La correspondencia inventada por Golomb se basa en la elección de un elemento primitivo a en el campo de orden q^n. Entonces, a cada palabra de Lyndon L=(l_0,l1,...,l{n-1}) se le asigna el polinomio primitivo que tiene como raíz el elemento a^{m(L)} donde m(L) es la suma entera de l_i*q^i sobre i=0,1,...,n-1.

Answer 2

Creo que tal biyección se presenta en

S. Golomb. Polinomios irreducibles, códigos sincronizadores, collares primitivos y álgebra ciclotómica. En Proc. Conf Combinatorial Math. and Its Appl., páginas 358– 370, Chapel Hill, 1969. Univ. de North Carolina Press.

pero no tengo acceso inmediato a este documento, aunque estoy bastante seguro de que está allí.

Answer 3

Ver sección 38.10 "Generación de polinomios irreducibles a partir de palabras de Lyndon" de http://www.jjj.de/fxt/#fxtbook