Lagmental Vicfred

Möbius Inversion Extracts Primitive Necklaces by Vicfred

Last updated: Sun 30 April 2023

tags: mathematics, Polya enumeration, combinatorial species, symmetry

Aperiodic words are obtained by removing repetitions of shorter primitive words. This is a compact note, but the quantifiers and hypotheses stay on the page.

Notation

A group \(G\) acting on positions identifies colorings that differ by symmetry. Cycle indices record the cycle structure of each \(g\in G\) and support systematic substitution of color inventories.

$$ q^n=\sum_{d\mid n}P_q(d) $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in \(\mathcal A\) may change ambient meaning, so I keep \(\mathsf D\) separate from \(\mathsf C\).

$$ P_q(n)=\sum_{d\mid n}\mu(d)q^{n/d} $$

Stress the formula

Now evaluate one representative case. The result should agree with the structural law above, but it is obtained without assuming the conclusion.

$$ N_q^{\mathrm{primitive}}(n)=\frac1n\sum_{d\mid n}\mu(d)q^{n/d} $$

Interpretation

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad q^n=\sum_{d\mid n}P_q(d),\\[5pt] \mathsf{C}\;&:\quad P_q(n)=\sum_{d\mid n}\mu(d)q^{n/d}. \end{aligned} $$

Limit of the argument

Burnside counts orbits under the specified group only. Adding reflections changes necklaces into bracelets and requires a different cycle index.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] P_q(n)=\sum_{d\mid n}\mu(d)q^{n/d} \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Fri 05 January 2018. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.