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

Question

Dejemos que $q$ sea 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$ en $\mathbb{F}_q$ y 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

En Reutenauer "Libre de Álgebras de Lie", la sección 7.6.2:

Directa bijection entre los primitivos collares de longitud n sobre F y el conjunto de polinomios irreducibles de grado n en F[x] puede ser descrito de la siguiente manera: sea K el campo con qⁿ elementos; es un espacio vectorial de dimensión n sobre F, de modo que existe en K un elemento θ tales que el conjunto {θ, θ^q, ..., q^qn-1} es una base lineal de K sobre F.

Con cada palabra w = ₀..._n-1 de longitud n en el alfabeto F, asociar el elemento β de K dado por β = ₀θ + ₁q^q + ... + a_n-1 q^qn-1. Es fácilmente demostrado que conjugar palabras w, w' corresponden conjugar elementos β β' en el campo de la extensión de K/F, y que w \mapsto β es un bijection. Por lo tanto, a una forma primitiva de la conjugación de la clase corresponde a una clase de conjugación de la cardinalidad de n en K; a este último le corresponde un único polinomio irreducible de grado n en F[x]. Esto le da a la deseada bijection.

Answer 2

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,l_1,...,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 3

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

Answer 4

Creo que dicha biyección se presenta en

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

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