Alphabeta MathHow 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.
Cauchy-Frobenius orbit counting: for a finite group action
Statement
Let a finite group act on a finite set , and let denote the set of orbits. Then
Equivalently, the number of orbits is the average number of fixed points of an element of .
Facts & Assumptions
Given: A finite group acting on a finite set .
The fixed-point set of is (The fixed-point sets and of a group action).
A finite incidence relation can be counted by either family of fibres (Double counting: for a relation between finite sets).
Finite sums over finite index sets are well-defined (The sum over a finite index set, and its product form).
A finite sum splits along a finite partition of its index set (The sum rule: a finite disjoint union is finite with and , and a sum over a finite index set splits along a partition).
Proof
Let . Counting its fibres over and using [L1], [L4], and [L5] gives .
Counting the same relation over gives .
Split the second sum along the orbit partition using [L2] and [L6]. On an orbit , [L3] gives for every , so that orbit contributes .
There is one contribution for each orbit in , hence . Combining this with step 1.1 gives the stated identity.
Depends on
- The fixed-point sets $X^g$ and $X^G$ of a group action
- The orbits of a group action are the equivalence classes of $x\sim y$ iff $y=g\cdot x$ for some $g$, and hence partition the acted-on set
- Orbit-stabiliser cardinality: $|G\cdot x|=[G:G_x]$ whenever either side is finite, and $|G|=|G_x|\,|G\cdot x|$ for finite $G$
- Double counting: $\sum_{x \in X}\lvert R_x\rvert = \lvert R\rvert = \sum_{y \in Y}\lvert R^y\rvert$ for a relation between finite sets
- The sum $\sum_{i \in S} a_i$ over a finite index set, and its product form
- The sum rule: a finite disjoint union is finite with $\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert$ and $\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert$, and a sum over a finite index set splits along a partition
Used by
- A nonfree action can have |X/G|≠|X|/|G| Counterexample
- A nonfree action can have 3 orbits on 4 points Example
- Binary necklaces of length 6 from both CYC(2Z) and Burnside's lemma Example
- There are six binary necklaces of length four up to rotation Example
- There are six two-colourings of the vertices of a square up to its eight symmetries Example
- Naming conventions for Burnside, Cauchy-Frobenius, and Redfield-Pólya Remark
- Jordan's derangement theorem: every transitive action of a finite group on a finite set with more than one element has a nonidentity element with no fixed points Theorem
- Over a commutative ℚ-algebra, CYC(A) has generating function ∑_k≥ 1φ(k)/k log1/1-A(xᵏ) Theorem
- Pólya's enumeration theorem Theorem
- The weighted pattern inventory is the cycle index evaluated at the power sums Theorem
Dependency tree · two levels
31 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
- T. W. Judson, Abstract Algebra: Theory and Applications, 14.3, Burnside's Counting Theorem (standard reference, not scraped)
- K. Conrad, Group Actions, Theorem 3.29 (standard reference, not scraped)