Polinomio de collar

Cuenta el número de collares de n cuentas de colores elegidas entre α colores disponibles

En matemáticas combinatorias , el polinomio del collar , o función de conteo de collares de Moreau, introducida por C. Moreau  (1872), cuenta el número de collares distintos de n cuentas de colores elegidas de entre α colores disponibles, dispuestos en un ciclo. A diferencia del problema habitual de coloración de grafos , se supone que los collares son aperiódicos (no consisten en subsecuencias repetidas) y se cuentan hasta la rotación (rotar las cuentas alrededor del collar cuenta como el mismo collar), pero sin darlas vuelta (invertir el orden de las cuentas cuenta como un collar diferente). Esta función de conteo también describe las dimensiones en un álgebra de Lie libre y el número de polinomios irreducibles sobre un cuerpo finito.

Definición

Los polinomios de collar son una familia de polinomios en la variable tales que ${\displaystyle M(\alpha ,n)}$ ${\displaystyle \alpha }$

${\displaystyle \alpha ^{n}\ =\ \sum _{d\,|\,n}d\,M(\alpha ,d).}$

Por inversión de Möbius se dan por

${\displaystyle M(\alpha ,n)\ =\ {1 \over n}\sum _{d\,|\,n}\mu \!\left({n \over d}\right)\alpha ^{d},}$

¿Dónde está la función clásica de Möbius ? ${\displaystyle \mu }$

Una familia estrechamente relacionada, llamada polinomio de collar general o función de conteo de collar general , es:

${\displaystyle N(\alpha ,n)\ =\ \sum _{d\,|\,n}M(\alpha ,d)\ =\ {\frac {1}{n}}\sum _{d\,|\,n}\varphi \!\left({n \over d}\right)\alpha ^{d},}$

¿Dónde está la función totiente de Euler ? ${\displaystyle \varphi }$

Aplicaciones

Los polinomios del collar aparecen como: ${\displaystyle M(\alpha ,n)}$ ${\displaystyle N(\alpha ,n)}$

• El número de collares aperiódicos (o equivalentemente, palabras de Lyndon ), que son arreglos cíclicos de n cuentas de colores que tienen α colores disponibles. Dos de estos collares se consideran iguales si están relacionados por una rotación (sin considerar las reflexiones). Aperiódico se refiere a collares sin simetría rotacional, que tienen n rotaciones distintas. En consecuencia, da el número de collares que incluyen los periódicos: esto se calcula fácilmente utilizando la teoría de Pólya . ${\displaystyle N(\alpha ,n)}$
• La dimensión del componente de grado n del álgebra de Lie libre sobre generadores α ("fórmula de Witt" ^[1] ), o equivalentemente el número de palabras de Hall de longitud n . En consecuencia, debería ser la dimensión del componente de grado n de un álgebra de Jordan libre . ${\displaystyle N(\alpha ,n)}$
• Número de polinomios mónicos irreducibles de grado n sobre un cuerpo finito con elementos α (cuando es una potencia prima). En consecuencia, es el número de polinomios que son primarios (una potencia de un irreducible). ${\displaystyle \alpha =p^{d}}$ ${\displaystyle N(\alpha ,n)}$
• El exponente en la identidad ciclotómica : . ${\displaystyle \textstyle {1 \over 1-\alpha z}\ =\ \prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{\!M(\alpha ,j)}}$

Aunque todos estos tipos de objetos se cuentan por el mismo polinomio, sus relaciones precisas siguen sin estar claras. Por ejemplo, no existe una biyección canónica entre los polinomios irreducibles y las palabras de Lyndon. ^[2] Sin embargo, existe una biyección no canónica como sigue. Para cualquier polinomio irreducible mónico de grado n sobre un cuerpo F con α elementos, sus raíces se encuentran en un cuerpo de extensión de Galois L con elementos. Se puede elegir un elemento tal que sea una F -base para L (una base normal ), donde σ es el automorfismo de Frobenius . Entonces la biyección se puede definir tomando un collar, visto como una clase de equivalencia de funciones , al polinomio irreducible ${\displaystyle \alpha ^{n}}$ ${\displaystyle x\in L}$ ${\displaystyle \{x,\sigma x,...,\sigma ^{n-1}x\}}$ ${\displaystyle \sigma y=y^{\alpha }}$ ${\displaystyle f:\{1,...,n\}\rightarrow F}$

${\displaystyle \phi (T)=(T-y)(T-\sigma y)\cdots (T-\sigma ^{n-1}y)\in F[T]}$ para . ${\displaystyle y=f(1)x+f(2)\sigma x+\cdots +f(n)\sigma ^{n-1}x}$

Diferentes reordenamientos cíclicos de f , es decir, diferentes representantes de la misma clase de equivalencia de collar, producen reordenamientos cíclicos de los factores de , por lo que esta correspondencia está bien definida. ^[3] ${\displaystyle \phi (T)}$

Relaciones entreMETROynorte

Los polinomios para M y N se relacionan fácilmente en términos de convolución de Dirichlet de funciones aritméticas , considerándola como una constante. ${\displaystyle f(n)*g(n)}$ ${\displaystyle \alpha }$

• La fórmula para M da , ${\displaystyle n\,M(n)\,=\,\mu (n)*\alpha ^{n}}$
• La fórmula para N da . ${\displaystyle n\,N(n)\,=\,\varphi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}}$
• Su relación da o equivalentemente , ya que la función es completamente multiplicativa . ${\displaystyle N(n)\,=\,1*M(n)}$ ${\displaystyle n\,N(n)\,=\,n*(n\,M(n))}$ ${\displaystyle f(n)=n}$

Cualquiera de estos dos implica el tercero, por ejemplo:

${\displaystyle n*\mu (n)*\alpha ^{n}\,=\,n\,N(n)\,=\,n*(n\,M(n))\quad \Longrightarrow \quad \mu (n)*\alpha ^{n}=n\,M(n)}$

por cancelación en el álgebra de Dirichlet.

Ejemplos

${\displaystyle {\begin{aligned}M(1,n)&=0{\text{ if }}n>1\\[6pt]M(\alpha ,1)&=\alpha \\[6pt]M(\alpha ,2)&={\tfrac {1}{2}}(\alpha ^{2}-\alpha )\\[6pt]M(\alpha ,3)&={\tfrac {1}{3}}(\alpha ^{3}-\alpha )\\[6pt]M(\alpha ,4)&={\tfrac {1}{4}}(\alpha ^{4}-\alpha ^{2})\\[6pt]M(\alpha ,5)&={\tfrac {1}{5}}(\alpha ^{5}-\alpha )\\[6pt]M(\alpha ,6)&={\tfrac {1}{6}}(\alpha ^{6}-\alpha ^{3}-\alpha ^{2}+\alpha )\\[6pt]M(\alpha ,p)&={\tfrac {1}{p}}(\alpha ^{p}-\alpha )&{\text{ if }}p{\text{ is prime}}\\[6pt]M(\alpha ,p^{N})&={\tfrac {1}{p^{N}}}(\alpha ^{p^{N}}-\alpha ^{p^{N-1}})&{\text{ if }}p{\text{ is prime}}\end{aligned}}}$

Para , comenzando con longitud cero, estos forman la secuencia entera ${\displaystyle \alpha =2}$

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (secuencia A001037 en la OEIS )

Identidades

Los polinomios obedecen a varias identidades combinatorias, dadas por Metropolis y Rota:

${\displaystyle M(\alpha \beta ,n)=\sum _{\operatorname {lcm} (i,j)=n}\gcd(i,j)M(\alpha ,i)M(\beta ,j),}$

donde "mcd" es el máximo común divisor y "mcm" es el mínimo común múltiplo . En términos más generales,

${\displaystyle M(\alpha \beta \cdots \gamma ,n)=\sum _{\operatorname {lcm} (i,j,\ldots ,k)=n}\gcd(i,j,\cdots ,k)M(\alpha ,i)M(\beta ,j)\cdots M(\gamma ,k),}$

Lo que también implica:

${\displaystyle M(\beta ^{m},n)=\sum _{\operatorname {lcm} (j,m)=nm}{\frac {j}{n}}M(\beta ,j).}$

Referencias

1. Lothaire, M. (1997). Combinatoria de palabras . Enciclopedia de matemáticas y sus aplicaciones. Vol. 17. Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, JE; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, MP; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Prólogo de Roger Lyndon (2.ª ed.). Cambridge University Press . págs. 79, 84. ISBN. 978-0-521-59924-5.MR 1475463.  Zbl 0874.20040  .
2. Amy Glen, (2012) Combinatoria de palabras de Lyndon , charla de Melbourne
3. Adalbert Kerber, (1991) Combinatoria algebraica mediante acciones de grupos finitos , [1]

• Moreau, C. (1872), "Sur les permutations circulaires distintivos (Sobre distintas permutaciones circulares)", Nouvelles Annales de Mathématiques , Série 2 (en francés), 11 : 309–31, JFM  04.0086.01
• Metropolis, N. ; Rota, Gian-Carlo (1983), "Los vectores de Witt y el álgebra de los collares", Advances in Mathematics , 50 (2): 95–125, doi : 10.1016/0001-8708(83)90035-X , ISSN  0001-8708, MR  0723197, Zbl  0545.05009
• Reutenauer, Christophe (1988). "Mots circulaires et polinomies irreductibles". Ana. Carolina del Sur. Matemáticas. Québec . 12 (2): 275–285.