Automorphism invariance of the census.
ProvedCayleyCensus.walkCount_mulAutaether-catalogmachinelearning
Automorphism invariance of the census. Any automorphism of G that
preserves the connection set preserves all walk counts.
theorem CayleyCensus.walkCount_mulAut{S : Finset G} {σ : MulAut G} (h : Preserves σ S)
(n : ℕ) (g : G) : walkCount S n (σ g) = walkCount S n g := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source MachineLearning/CayleyCensusInvariance.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from MachineLearning/CayleyCensusInvariance.lean
import Mathlib
import Definitions.Def_MachineLearning_CayleyCensusInvariance
/-!
# The Cayley walk census is a class function up to inversion
Let `G` be a finite group and `S : Finset G` a *connection set*. The
**census function** of the pair `(G, S)` is the two–parameter counting function
`walkCount S n g = #{ (s₁, …, s_n) ∈ Sⁿ : s₁ ⋯ s_n = g }`,
i.e. the number of walks of length `n` from the identity to `g` in the (directed)
Cayley graph `Cay(G, S)`.
This file proves that the census is a **class function up to inversion**:
* `walkCount_inv` — if `S` is closed under inversion then
`walkCount S n g⁻¹ = walkCount S n g`;
* `walkCount_mulAut` — if `σ : MulAut G` preserves `S` then
`walkCount S n (σ g) = walkCount S n g`;
* `walkCount_conj` — consequently, if `S` is a union of conjugacy classes the
census is a genuine class function;
* `CensusEquiv` — the equivalence relation generated by inversion and
`S`-preserving automorphisms, together with `walkCount_of_censusEquiv`, which
shows the census is constant on its classes. This is exactly the orbit
structure visible in a census table, and `card_census_image_le` turns it into
a quantitative bound on the number of distinct rows.
The technical heart is `walkCount_succ_right`, the "last-step" recursion, which
is *not* definitional: the definition peels off the first letter of a word, while
the inversion symmetry needs the reversed recursion.
## Main results
* `walkCount_succ_right`
* `walkCount_inv`
* `walkCount_mulAut`, `walkCount_conj`
* `walkCount_of_censusEquiv`, `card_census_image_le`
* `sum_walkCount` — total mass: `∑ g, walkCount S n g = |S| ^ n`.
-/
open CayleyCensus
variable {G : Type*} [Group G]
/-! ### Symmetry data of a connection set
Neither of the two symmetry notions below refers to the census; they are pure
group theory, and they are what the census will turn out to be blind to. -/
/-! ### The census equivalence relation -/
open CensusEquiv
variable {S : Finset G}
/-! ### The census function -/
variable [DecidableEq G]
/-! ### Invariance under inversion -/
/-! ### Invariance under `S`-preserving automorphisms -/Formal statement
theorem CayleyCensus.walkCount_mulAut{S : Finset G} {σ : MulAut G} (h : Preserves σ S)
(n : ℕ) (g : G) : walkCount S n (σ g) = walkCount S n g := by sorrySource