LemmaStatement: Literature-sourcedProof: Literature-sourcedjudge pass (gpt-5.6-terra)audited 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.

Fixed colourings factor by cycle type

Statement

Let a finite group element $g$ act on a finite set $X$ , and let $j_{d} (g)$ denote the number of $d$ -cycles of the induced permutation of $X$ .

If $C$ is a finite colour set with $m = ∣ C ∣$ , then the number of colourings $f : X \to C$ fixed by $g$ is

$m^{\sum_{d \geq 1} j_{d} (g)} .$
More generally, if $w : C \to R$ is a weight function into a commutative ring and

$p_{d} : = \sum_{c \in C} w (c)^{d},$

then

$\sum_{\begin{array}{c} f : X \to C \\ g \cdot f = f \end{array}} wt (f) = \prod_{d \geq 1} p_{d}^{j_{d} (g)} .$

Facts & Assumptions

Given: a finite set $X$ , a colour set $C$ , and an element $g$ acting on $X$ .

[F1]

The induced action on colourings is $(g \cdot f) (x) = f (g^{- 1} x)$ , and the weight of a colouring is the product of the weights of its colours over all positions (Colourings, weight functions, and the pattern inventory).

Proof

technique · direct

1.1F1

A colouring $f$ is fixed by $g$ exactly when it is constant on every cycle of the permutation of $X$ induced by $g$ . Indeed, $g \cdot f = f$ means $f (x) = f (g^{- 1} x)$ for every $x$ , and iterating this equality around a cycle forces one common colour on that whole cycle. Conversely, a colouring constant on each cycle is unchanged by the action.

2.1step 1.1

If $g$ has $j_{d} (g)$ cycles of length $d$ , then each cycle may be assigned any one of the $m$ colours independently, so the number of fixed colourings is $m^{\sum_{d} j_{d} (g)}$ .

3.1step 1.1F1∎

In the weighted setting, a fixed colouring contributes on a $d$ -cycle the factor $w (c)^{d}$ for the single colour $c$ chosen on that cycle. Summing over all colour choices on that cycle gives $p_{d}$ . Independence across cycles from step 1.1 therefore yields the product $\prod_{d} p_{d}^{j_{d} (g)}$ .

Depends on

Used by

Dependency tree · two levels

9 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)
Ben Lynn, Polya Theory: Pólya's Inventory Theorem (standard reference, not scraped)