Editing Necklace polynomial

{{short description|Counts the number of necklaces of n colored beads picked from α available colors}}
In [[combinatorics|combinatorial]] mathematics, the '''necklace polynomial''', or '''Moreau's necklace-counting function,'''  introduced by {{harvs|txt|authorlink=Charles Paul Narcisse Moreau|first=C.|last=Moreau|year=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 [[Chromatic polynomial#Examples|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  <math>M(\alpha,n)</math> in the variable <math>\alpha</math> such that
:<math>\alpha^n \ =\ \sum_{d\,|\,n} d \, M(\alpha, d).</math>

By [[Möbius inversion]] they are given by
: <math> M(\alpha,n) \ =\ {1\over n}\sum_{d\,|\,n}\mu\!\left({n \over d}\right)\alpha^d,</math>
where <math>\mu</math> is the classic [[Möbius function]]. 

A closely related family, called the '''general necklace polynomial''' or '''general necklace-counting function''', is:
:<math>N(\alpha,n)\ =\ \sum_{d\,|\,n} M(\alpha,d)\ =\ \frac{1}{n}\sum_{d\,|\,n}\varphi\!\left({n \over d}\right)\alpha^d,</math>
where <math>\varphi</math> is [[Euler's totient function]].

==Applications==
The necklace polynomials <math>M(\alpha,n)</math> and <math>N(\alpha,n)</math> appear as:
* The number of [[Necklace (combinatorics)#aperiodic necklaces|aperiodic necklaces]] (or equivalently [[Lyndon word]]s), which are cyclic arrangements of ''n'' colored beads having ''α'' available colors. Two such necklaces are considered equal if they are related by a rotation (not considering reflections). ''Aperiodic'' refers to necklaces without rotational symmetry, having ''n'' distinct rotations.  Correspondingly, <math>N(\alpha,n)</math> gives the number of necklaces including the periodic ones: this is easily computed using [[Pólya enumeration theorem|Pólya theory]].
* The dimension of the degree ''n'' component of the [[free Lie algebra]] on ''α'' generators ("Witt's formula"<ref name="L7984">{{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | others=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 | title=Combinatorics on words | edition=2nd | series=Encyclopedia of Mathematics and Its Applications | volume=17 | publisher=[[Cambridge University Press]] | year=1997 | isbn=978-0-521-59924-5 | zbl=0874.20040 | mr = 1475463 | pages=79,84 }}</ref>), or equivalently the number of [[Hall set|Hall words]] of length ''n''. Correspondingly, <math>N(\alpha,n)</math> should be the dimension of the degree ''n'' component of a free [[Jordan algebra]].
* The number of monic irreducible polynomials of degree ''n'' over a [[finite field]] with ''α'' elements (when <math>\alpha=p^d</math> is a [[prime power]]). Correspondingly, <math>N(\alpha,n)</math> is the number of polynomials which are [[Primary ideal|primary]] (a power of an irreducible).
* The exponent in the [[cyclotomic identity]]:  <math>\textstyle {1 \over 1-\alpha z}\ =\  \prod_{j=1}^\infty\left({1 \over 1-z^j}\right)^{\! M(\alpha,j)}  </math>.
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.<ref>
Amy Glen, (2012) ''Combinatorics of Lyndon words'', [https://amyglen.files.wordpress.com/2012/03/melbourne_talk_feb2012.pdf Melbourne talk]
</ref> 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 <math>\alpha^n</math> elements. One may choose an element <math>x\in L</math> such that <math>\{x,\sigma x, ...,\sigma^{n-1} x\}</math> is an ''F''-basis for ''L'' (a [[normal basis]]), where ''σ'' is the [[Frobenius endomorphism|Frobenius automorphism]] <math>\sigma y = y^\alpha</math>. Then the bijection can be defined by taking a necklace, viewed as an [[equivalence class]] of functions <math>f:\{1,...,n\}\rightarrow F</math>, to the irreducible polynomial<blockquote><math>\phi(T)=(T-y)(T-\sigma y)\cdots (T-\sigma^{n-1}y) \in F[T]</math>    for    <math>y=f(1)x+f(2)\sigma x+\cdots+f(n)\sigma^{n-1} x</math>.</blockquote>Different cyclic rearrangements of ''f'', i.e. different representatives of the same necklace equivalence class, yield cyclic rearrangements of the factors of <math>\phi(T)</math>, so this correspondence is well-defined.<ref>
Adalbert Kerber, (1991) ''Algebraic Combinatorics Via Finite Group Actions'', [https://books.google.com/books?id=Fe7uAAAAMAAJ]
</ref>

==Relations between ''M'' and ''N''==
The polynomials for ''M'' and ''N'' are easily related in terms of [[Dirichlet convolution]] of arithmetic functions <math>f(n)*g(n)</math>, regarding <math>\alpha</math> as a constant.
* The formula for ''M'' gives <math> n\,M(n) \,=\, \mu(n)*\alpha^n</math>,
* The formula for ''N'' gives <math> n\,N(n) \,=\,  \varphi(n)*\alpha^n \,=\, n*\mu(n)*\alpha^n</math>.
* Their relation gives  <math>N(n)\,=\,1*M(n)</math> or equivalently <math> n\,N(n) \,=\, n*(n\,M(n))</math>, since the function <math>f(n)=n</math> is [[Completely multiplicative function#Properties|completely multiplicative]].

Any two of these imply the third, for example:
:<math>
n*\mu(n)*\alpha^n \,=\, n\,N(n) \,=\, n*(n\,M(n)) \quad\Longrightarrow\quad  \mu(n)*\alpha^n
= n\,M(n)</math>
by cancellation in the Dirichlet algebra.

==Examples==
: <math>
\begin{align}
M(1,n) & = 0 \text{ if }n>1 \\[6pt]
M(\alpha,1) & = \alpha \\[6pt]
M(\alpha,2) & = \tfrac12 (\alpha^2-\alpha) \\[6pt]
M(\alpha,3) & = \tfrac13 (\alpha^3-\alpha) \\[6pt]
M(\alpha,4) & = \tfrac14 (\alpha^4-\alpha^2) \\[6pt]
M(\alpha,5) & = \tfrac15(\alpha^5-\alpha) \\[6pt]
M(\alpha,6) & = \tfrac16(\alpha^6-\alpha^3-\alpha^2+\alpha) \\[6pt]
M(\alpha,p) & = \tfrac1p (\alpha^{p}-\alpha) & \text{ if }p\text{ is prime} \\[6pt]
M(\alpha,p^N) & = \tfrac1{p^N}(\alpha^{p^N}-\alpha^{p^{N-1}}) & \text{ if }p\text{ is prime}
\end{align}
</math>

For <math>\alpha=2</math>, starting with length zero, these form the [[integer sequence]]
:1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... {{OEIS|A001037}}

==Identities==
{{main | Necklace ring }}
The polynomials obey various combinatorial identities, given by Metropolis & Rota:
:<math>
M(\alpha\beta, n) =\sum_{\operatorname{lcm}(i,j)=n} \gcd(i,j)M(\alpha,i)M(\beta,j),
</math>
where "gcd" is [[greatest common divisor]] and "lcm" is [[least common multiple]].  More generally,

:<math>
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),
</math>
which also implies:
:<math>
M(\beta^m, n) =\sum_{\operatorname{lcm}(j,m)=nm} \frac{j}{n} M(\beta,j).
</math>

==References==
{{reflist}}
* {{citation | last1=Moreau | first1=C. |authorlink=Charles Paul Narcisse Moreau | title=Sur les permutations circulaires distinctes (On distinct circular permutations) | url=http://www.numdam.org/item?id=NAM_1872_2_11__309_0 | language=French | jfm=04.0086.01 | year=1872 | journal=Nouvelles Annales de Mathématiques |series=Série 2 | volume=11 | pages=309–31}}
* {{Citation | last1=Metropolis | first1=N. | author1-link=Nicholas Metropolis | last2=Rota | first2=Gian-Carlo | author2-link=Gian-Carlo Rota | title=Witt vectors and the algebra of necklaces | doi=10.1016/0001-8708(83)90035-X | mr=723197 | zbl=0545.05009 | year=1983 | journal=[[Advances in Mathematics]] | issn=0001-8708 | volume=50 | issue=2 | pages=95–125 | doi-access=free }}
* {{cite journal |last1=Reutenauer |first1=Christophe |title=Mots circulaires et polynomies irreductibles |journal=Ann. Sc. Math. Quebec |date=1988 |volume=12 |issue=2 |pages=275–285}}

[[Category:Combinatorics on words]]
[[Category:Enumerative combinatorics]]