Collar polinomio

Cuenta el número de collares de n cuentas de colores escogidas 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 entre α colores disponibles, dispuestas en un ciclo. A diferencia del problema habitual de colorear gráficos , se supone que los collares son aperiódicos (que 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 voltear (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 en un campo 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 están dados 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 general de collar o función general de conteo de collares , 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 disposiciones cíclicas 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 los reflejos). Aperiódico se refiere a collares sin simetría rotacional, que tienen n rotaciones distintas. En consecuencia, da el número de collares, incluidos 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 en 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)}$
• El número de polinomios mónicos irreducibles de grado n sobre un campo 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 distintos tipos de objetos se cuentan mediante 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 grado n polinomio mónico irreducible sobre un campo F con α elementos, sus raíces se encuentran en un campo de extensión de Galois L con elementos. Se puede elegir un elemento tal que sea una base F 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 entre M y N

Los polinomios para M y N se relacionan fácilmente en términos de convolución de funciones aritméticas de Dirichlet , considerándolos 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 equivalente , 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}$

Dos de estos implican 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 el OEIS )

Identidades

Los polinomios obedecen a varias identidades combinatorias, dadas por Metropolis & 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 . Más generalmente,

${\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. Lotario, M. (1997). Combinatoria sobre palabras . Enciclopedia de Matemáticas y sus aplicaciones. vol. 17. Perrin, D.; Reutenauer, C.; Berstel, J.; Alfiler, JE; Pirillo, G.; Foata, D.; Sakarovich, J.; Simón, yo; Schützenberger, diputado; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Prólogo de Roger Lyndon (2ª ed.). Prensa de la Universidad de Cambridge . págs.79, 84. ISBN 978-0-521-59924-5. SEÑOR  1475463. Zbl  0874.20040.
2. Amy Glen, (2012) Combinatoria de palabras de Lyndon , charla en 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
• Metrópolis, N .; Rota, Gian-Carlo (1983), "Vectores de Witt y el álgebra de collares", Avances en Matemáticas , 50 (2): 95–125, doi : 10.1016/0001-8708(83)90035-X , ISSN  0001-8708 , SEÑOR  0723197, Zbl  0545.05009
• Reutenauer, Christophe (1988). "Mots circulaires et polinomies irreductibles". Ana. Carolina del Sur. Matemáticas. Québec . 12 (2): 275–285.