Aether Catalog definitions — MachineLearning_CayleyCensusInvariance
DefinitionMachineLearning_CayleyCensusInvarianceaether-catalogmachinelearning
Definition bundle for the Aether Catalog module MachineLearning.CayleyCensusInvariance, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from MachineLearning/CayleyCensusInvariance.lean by skeleton subtraction
import Mathlib
/-!
# 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`.
-/
namespace 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. -/
/-- A connection set is *inversion closed* (equivalently, the Cayley graph is
undirected) if it is stable under `x ↦ x⁻¹`. -/
def InvClosed (S : Finset G) : Prop := ∀ ⦃s : G⦄, s ∈ S → s⁻¹ ∈ S
instance decidableInvClosed [DecidableEq G] [Fintype G] (S : Finset G) :
Decidable (InvClosed S) :=
decidable_of_iff (∀ s ∈ S, s⁻¹ ∈ S) ⟨fun h _ hs => h _ hs, fun h _ hs => h hs⟩
/-- Reindexing a sum over an inversion-closed connection set by `s ↦ s⁻¹`. -/
theorem InvClosed.sum_inv {S : Finset G} (hS : InvClosed S) (f : G → ℕ) :
∑ s ∈ S, f s⁻¹ = ∑ s ∈ S, f s :=
Finset.sum_nbij' (i := fun s => s⁻¹) (j := fun s => s⁻¹)
(fun _ ha => hS ha) (fun _ ha => hS ha)
(fun a _ => inv_inv a) (fun a _ => inv_inv a) (fun _ _ => rfl)
/-- An automorphism `σ` of `G` *preserves* the connection set `S` if it maps `S`
onto itself. -/
def Preserves (σ : MulAut G) (S : Finset G) : Prop := ∀ s : G, σ s ∈ S ↔ s ∈ S
instance decidablePreserves [DecidableEq G] [Fintype G] (σ : MulAut G) (S : Finset G) :
Decidable (Preserves σ S) :=
decidable_of_iff (∀ s : G, σ s ∈ S ↔ s ∈ S) Iff.rfl
/-! ### The census equivalence relation -/
/-- The equivalence relation on `G` generated by inversion `g ↦ g⁻¹` and by the
automorphisms of `G` preserving the connection set `S`. Its classes are the
orbits visible in a Cayley census table. -/
inductive CensusEquiv (S : Finset G) : G → G → Prop
| refl (g : G) : CensusEquiv S g g
| inv {g h : G} : CensusEquiv S g h → CensusEquiv S g h⁻¹
| aut {g h : G} (σ : MulAut G) (hσ : Preserves σ S) :
CensusEquiv S g h → CensusEquiv S g (σ h)
namespace CensusEquiv
variable {S : Finset G}
end CensusEquiv
/-! ### The census function -/
section Census
variable [DecidableEq G]
/-- `walkCount S n g` is the number of words of length `n` in the letters of the
connection set `S` whose product is `g`; equivalently the number of length-`n`
walks from `1` to `g` in the Cayley graph `Cay(G, S)`. -/
def walkCount (S : Finset G) : ℕ → G → ℕ
| 0, g => if g = 1 then 1 else 0
| (n + 1), g => ∑ s ∈ S, walkCount S n (s⁻¹ * g)
@[simp] theorem walkCount_zero (S : Finset G) (g : G) :
walkCount S 0 g = if g = 1 then 1 else 0 := rfl
theorem walkCount_succ (S : Finset G) (n : ℕ) (g : G) :
walkCount S (n + 1) g = ∑ s ∈ S, walkCount S n (s⁻¹ * g) := rfl
@[simp] theorem walkCount_one (S : Finset G) (g : G) :
walkCount S 1 g = if g ∈ S then 1 else 0 := by
rw [walkCount_succ]
simp only [walkCount_zero, inv_mul_eq_one]
rw [Finset.sum_ite_eq' S g]
/-- **Last-step recursion.** The definition of `walkCount` strips the *first*
letter of a word; this lemma shows one may equally strip the *last* letter.
The proof is an induction with an exchange of the two summations. -/
theorem walkCount_succ_right (S : Finset G) (n : ℕ) (g : G) :
walkCount S (n + 1) g = ∑ s ∈ S, walkCount S n (g * s⁻¹) := by
induction n generalizing g with
| zero =>
have hrhs : ∑ s ∈ S, walkCount S 0 (g * s⁻¹) = if g ∈ S then 1 else 0 := by
simp only [walkCount_zero, mul_inv_eq_one]
rw [Finset.sum_ite_eq S g]
rw [hrhs]
exact walkCount_one S g
| succ n ih =>
rw [walkCount_succ (n := n + 1)]
calc ∑ s ∈ S, walkCount S (n + 1) (s⁻¹ * g)
= ∑ s ∈ S, ∑ t ∈ S, walkCount S n (s⁻¹ * g * t⁻¹) :=
Finset.sum_congr rfl fun s _ => ih _
_ = ∑ t ∈ S, ∑ s ∈ S, walkCount S n (s⁻¹ * (g * t⁻¹)) := by
rw [Finset.sum_comm]
exact Finset.sum_congr rfl fun t _ =>
Finset.sum_congr rfl fun s _ => by rw [mul_assoc]
_ = ∑ t ∈ S, walkCount S (n + 1) (g * t⁻¹) := rfl
/-! ### Invariance under inversion -/
/-- **Inversion symmetry of the census.** If the connection set is closed under
inversion then `g` and `g⁻¹` have the same walk counts, for every length.
The underlying bijection is `(s₁,…,s_n) ↦ (s_n⁻¹,…,s₁⁻¹)`; formally the
induction alternates between the first-letter and last-letter recursions. -/
theorem walkCount_inv {S : Finset G} (hS : InvClosed S) (n : ℕ) (g : G) :
walkCount S n g⁻¹ = walkCount S n g := by
induction n generalizing g with
| zero => simp [inv_eq_one]
| succ n ih =>
rw [walkCount_succ, walkCount_succ_right]
have hcongr : ∀ s ∈ S, walkCount S n (s⁻¹ * g⁻¹) = walkCount S n (g * s) := by
intro s _
have hrw : s⁻¹ * g⁻¹ = (g * s)⁻¹ := by rw [mul_inv_rev]
rw [hrw, ih]
rw [Finset.sum_congr rfl hcongr]
exact (hS.sum_inv (fun s => walkCount S n (g * s))).symm
/-! ### Invariance under `S`-preserving automorphisms -/
/-! ### The orbit structure of the census -/
/-- The census vector of a group element: the whole row of the census table. -/
def census (S : Finset G) (g : G) : ℕ → ℕ := fun n => walkCount S n g
variable [Fintype G]
end Census
end CayleyCensus