Necklace polynomial

Appearance move to sidebar hide

In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by C. Moreau (1872), counts the number of distinct necklaces of n colored beads chosen out of α available colors, arranged in a cycle. Unlike the usual problem of graph coloring, the necklaces are assumed to be aperiodic (not consisting of repeated subsequences), and counted up to rotation (rotating the beads around the necklace counts as the same necklace), but without flipping over (reversing the order of the beads counts as a different necklace). This counting function also describes the dimensions in a free Lie algebra and the number of irreducible polynomials over a finite field.

Definition

The necklace polynomials are a family of polynomials M ( α , n ) {\displaystyle M(\alpha ,n)} in the variable α {\displaystyle \alpha } such that

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

By Möbius inversion they are given by

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

where μ {\displaystyle \mu } is the classic Möbius function.

A closely related family, called the general necklace polynomial or general necklace-counting function, is:

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

where φ {\displaystyle \varphi } is Euler's totient function.

Applications

The necklace polynomials M ( α , n ) {\displaystyle M(\alpha ,n)} and N ( α , n ) {\displaystyle N(\alpha ,n)} appear as:

Although these various types of objects are all counted by the same polynomial, their precise relationships remain unclear. For example, there is no canonical bijection between the irreducible polynomials and the Lyndon words. However, there is a non-canonical bijection as follows. For any degree n monic irreducible polynomial over a field F with α elements, its roots lie in a Galois extension field L with α n {\displaystyle \alpha ^{n}} elements. One may choose an element x ∈ L {\displaystyle x\in L} such that { x , σ x , . . . , σ n − 1 x } {\displaystyle \{x,\sigma x,...,\sigma ^{n-1}x\}} is an F-basis for L (a normal basis), where σ is the Frobenius automorphism σ y = y α {\displaystyle \sigma y=y^{\alpha }} . Then the bijection can be defined by taking a necklace, viewed as an equivalence class of functions f : { 1 , . . . , n } → F {\displaystyle f:\{1,...,n\}\rightarrow F} , to the irreducible polynomial

ϕ ( T ) = ( T − y ) ( T − σ y ) ⋯ ( T − σ n − 1 y ) ∈ F {\displaystyle \phi (T)=(T-y)(T-\sigma y)\cdots (T-\sigma ^{n-1}y)\in F} for y = f ( 1 ) x + f ( 2 ) σ x + ⋯ + f ( n ) σ n − 1 x {\displaystyle y=f(1)x+f(2)\sigma x+\cdots +f(n)\sigma ^{n-1}x} .

Different cyclic rearrangements of f, i.e. different representatives of the same necklace equivalence class, yield cyclic rearrangements of the factors of ϕ ( T ) {\displaystyle \phi (T)} , so this correspondence is well-defined.

Relations between M and N

The polynomials for M and N are easily related in terms of Dirichlet convolution of arithmetic functions f ( n ) ∗ g ( n ) {\displaystyle f(n)*g(n)} , regarding α {\displaystyle \alpha } as a constant.

Any two of these imply the third, for example:

n ∗ μ ( n ) ∗ α n = n N ( n ) = n ∗ ( n M ( n ) ) ⟹ μ ( n ) ∗ α n = n M ( n ) {\displaystyle n*\mu (n)*\alpha ^{n}\,=\,n\,N(n)\,=\,n*(n\,M(n))\quad \Longrightarrow \quad \mu (n)*\alpha ^{n}=n\,M(n)}

by cancellation in the Dirichlet algebra.

Examples

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

For α = 2 {\displaystyle \alpha =2} , starting with length zero, these form the integer sequence

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (sequence A001037 in the OEIS)

Identities

The polynomials obey various combinatorial identities, given by Metropolis & Rota:

M ( α β , n ) = ∑ lcm ⁡ ( i , j ) = n gcd ( i , j ) M ( α , i ) M ( β , j ) , {\displaystyle M(\alpha \beta ,n)=\sum _{\operatorname {lcm} (i,j)=n}\gcd(i,j)M(\alpha ,i)M(\beta ,j),}

where "gcd" is greatest common divisor and "lcm" is least common multiple. More generally,

M ( α β ⋯ γ , n ) = ∑ lcm ⁡ ( i , j , … , k ) = n gcd ( i , j , ⋯ , k ) M ( α , i ) M ( β , j ) ⋯ M ( γ , k ) , {\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),}

which also implies:

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

References

  1. ^ Lothaire, M. (1997). Combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 17. Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (2nd ed.). Cambridge University Press. pp. 79, 84. ISBN 978-0-521-59924-5. MR 1475463. Zbl 0874.20040.
  2. ^ Amy Glen, (2012) Combinatorics of Lyndon words, Melbourne talk
  3. ^ Adalbert Kerber, (1991) Algebraic Combinatorics Via Finite Group Actions,