Necklace polynomial


In combinatorial mathematics, the necklace polynomial, or Moreau's necklace-counting function, introduced by, 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, and counted up to rotation, but without flipping over. 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 in the variable such that
By Möbius inversion they are given by
where is the classic Möbius function.
A closely related family, called the general necklace polynomial or general necklace-counting function, is:
where is Euler's totient function.

Applications

The necklace polynomials appear as:
  • The number of aperiodic necklaces, which are cyclic arrangements of n colored beads having α available colors. Two such necklaces are considered equal if they are related by a rotation. Aperiodic refers to necklaces without rotational symmetry, having n distinct rotations. Correspondingly, gives the number of necklaces including the periodic ones: this is easily computed using Pólya theory.
  • The dimension of the degree n component of the free Lie algebra on α generators, or equivalently the number of Hall words of length n. Correspondingly, 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. Correspondingly, is the number of polynomials which are primary.
  • The exponent in the cyclotomic identity: .
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 elements. One may choose an element such that is an F-basis for L, where σ is the Frobenius automorphism. Then the bijection can be defined by taking a necklace, viewed as an equivalence class of functions, to the irreducible polynomial
for .
Different cyclic rearrangements of f, i.e. different representatives of the same necklace equivalence class, yield cyclic rearrangements of the factors of, 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, regarding as a constant.
  • The formula for M gives,
  • The formula for N gives.
  • Their relation gives or equivalently, since the function is completely multiplicative.
Any two of these imply the third, for example:
by cancellation in the Dirichlet algebra.

Examples

For, starting with length zero, these form the integer sequence

Identities

The polynomials obey various combinatorial identities, given by Metropolis & Rota:
where "gcd" is greatest common divisor and "lcm" is least common multiple. More generally,
which also implies: