Necklace polynomial

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

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

By Möbius inversion they are given by

${\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:

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

where ${\displaystyle \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 ${\displaystyle f(n)*g(n)}$, regarding ${\displaystyle \alpha }$ as a constant.

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

Any two of these imply the third, for example:

${\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

${\displaystyle {\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:

${\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,

${\displaystyle 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:

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

Cyclotomic identity

Main article: Cyclotomic identity

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

Applications

The necklace polynomials ${\displaystyle 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 ${\displaystyle 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"[1]). Here ${\displaystyle 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 ${\displaystyle \alpha =p^{d}}$ is a prime power). Here ${\displaystyle N(\alpha ,n)}$ is the number of polynomials which are primary (a power of an irreducible).
• The exponent in the cyclotomic identity.

References

1. Lothaire, M. (1997). Combinatorics on words. Encyclopedia of Mathematics and Its Applications. 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.

• 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.