Necklace polynomial

In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by C. Moreau (1872), is the family of polynomials $M(\alpha ,n)$ in the variable $\alpha$ such that

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

By Möbius inversion they are given by

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

where $\mu$ is the classic Möbius function.

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

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

where $\phi$ is Euler's totient function.

Relations between M and N

The above formulas are easily related in terms of Dirichlet convolution of arithmetic functions $f(n)*g(n)$, regarding $\alpha$ as a constant.

• The formula for M gives $n\,M(n)\,=\,\mu (n)*\alpha ^{n}$,
• The formula for N gives $n\,N(n)\,=\,\phi (n)*\alpha ^{n}\,=\,n*\mu (n)*\alpha ^{n}$.
• Their relation gives $N(n)\,=\,1*M(n)$ or equivalently $n\,N(n)\,=\,n*(n\,M(n))$, since n is completely multiplicative.

Any two of these imply the third, for example:

$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

${\begin{array}{ccll}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{array}}$

Identities

Main article: Necklace ring

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

$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(\alpha \beta \cdots \gamma ,n)=\sum _{\operatorname {lcm} (i,j,\cdots ,k)=n}\gcd(i,j,\cdots ,k)M(\alpha ,i)M(\beta ,j)\cdots M(\gamma ,k),$

which also implies:

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

Cyclotomic identity

Main article: Cyclotomic identity

${1 \over 1-\alpha z}\ =\ \prod _{j=1}^{\infty }\left({1 \over 1-z^{j}}\right)^{M(\alpha ,j)}$

Applications

The necklace polynomials $M(\alpha ,n)$ appear as:

• The number of aperiodic necklaces (or equivalently Lyndon words) which can be made by arranging n colored beads having α available colors. Two such necklaces are considered equal if they are related by a rotation (but not a reflection). Aperiodic refers to necklaces without rotational symmetry, having n distinct rotations. The polynomials $N(\alpha ,n)$ give the number of necklaces including the periodic ones: this is easily computed using Pólya theory.
• The dimension of the degree n piece of the free Lie algebra on α generators ("Witt's formula"). Here $N(\alpha ,n)$ should be the dimension of the degree n piece of the corresponding free Jordan algebra.
• The number of monic irreducible polynomials of degree n over a finite field with α elements (when $\alpha =p^{d}$ is a prime power). Here $N(\alpha ,n)$ is the number of polynomials which are primary (a power of an irreducible).
• The exponent in the cyclotomic identity.

References

• Moreau, C. (1872), "Sur les permutations circulaires distinctes (On distinct circular permutations)", Nouvelles Annales de Mathématiques, Journal des Candidats Aux écoles Polytechnique et Normale, Sér. 2 (in French), 11: 309–31, JFM 04.0086.01

• Metropolis, N.; Rota, Gian-Carlo (1983), "Witt vectors and the algebra of necklaces", 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 polynomies irreductibles". Ann. Sc. Math. Quebec. 12 (2): 275–285.