TheoremStatement: Literature-sourcedProof: Literature-sourcedaudited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The cycle index of the cyclic group C_n

Statement

Let $C_{n}$ act on the vertices of a labelled $n$ -gon by rotation, with $n \geq 1$ . Then

$Z (C_{n}) = \frac{1}{n} \sum_{d ∣ n} φ (d) s_{d}^{n / d} .$

Facts & Assumptions

Given: an integer $n \geq 1$ and the rotation action of $C_{n}$ on the vertices of a labelled $n$ -gon.

[A1]

A rotation by $r$ steps sends each vertex $i$ to $i + r (m o d n)$ .

[L1]

Euler's totient satisfies $φ (d) = ∣ (Z / d)^{\times} ∣$ (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

Proof

technique · direct

1.1A1algebra

A rotation by $r$ steps decomposes the $n$ vertices into $\gcd (n, r)$ cycles, each of length $n / \gcd (n, r)$ . Therefore its cycle-index monomial is $s_{n / \gcd (n, r)}^{\gcd (n, r)}$ .

2.1step 1.1L1algebra

Fix a divisor $d$ of $n$ . A rotation contributes the monomial $s_{d}^{n / d}$ exactly when its cycles have length $d$ , equivalently when its step size has the form $r = (n / d) a$ with $a$ coprime to $d$ . Indeed, the order of the rotation by $r$ is the least positive $m$ with $m r \equiv 0 (m o d n)$ , and for $r = (n / d) a$ this least $m$ is exactly $d$ when $\gcd (a, d) = 1$ . Therefore the rotations of order $d$ are in bijection with the units $a \in (Z / d)^{\times}$ , so there are $φ (d)$ of them by [L1].

3.1step 2.1∎

Average the monomials over all $n$ rotations. Grouping them by the divisor $d$ from step 2.1 yields $Z (C_{n}) = \frac{1}{n} \sum_{d ∣ n} φ (d) s_{d}^{n / d}$ .

Depends on

Used by

Necklace count from the cyclic-group cycle index Corollary
The cycle index of C₄ Example
Two-colour necklaces of length 6 by Pólya Example
The cycle index of the dihedral group D₂ₙ Theorem

Dependency tree · two levels

13 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ben Lynn, Polya Theory: The Cycle Index Polynomial (standard reference, not scraped)
Eric W. Weisstein, Cycle Index, Wolfram MathWorld (standard reference, not scraped)