Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — MachineLearning_CayleyCensusGraphSymmetry

Definition
MachineLearning_CayleyCensusGraphSymmetry

by raver1975 · Sep 17, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogmachinelearning

Definition bundle for the Aether Catalog module MachineLearning.CayleyCensusGraphSymmetry, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.

Definition code
-- Def bundle generated from MachineLearning/CayleyCensusGraphSymmetry.lean by skeleton subtraction
import Mathlib
import Definitions.Def_MachineLearning_CayleyCensusMoments

/-!
# Beyond group symmetry: graph automorphisms, and the failure of the converse

`MachineLearning.CayleyCensusInvariance` shows that the census
`walkCount S n g` is invariant under inversion and under `S`-preserving group
automorphisms.  Two natural questions remain, and both are settled here.

**Is group symmetry the only source of census invariance?**  No.  The census is
invariant under every *graph* automorphism of `Cay(G, S)` fixing the identity —
a strictly larger supply of symmetries in general, since such a permutation need
not respect the multiplication of `G` at all.  This is `walkCount_graphAut`,
proved through the adjacency-power bridge `walkCount_eq_adj_pow`: the inductive
step is a reindexing of the intermediate vertex along the permutation.  The
group-automorphism theorem is recovered as the corollary
`walkCount_mulAut_of_graphAut`.

**Is the converse of the main theorem true — do equal census rows force census
equivalence?**  No, and the failure is already visible in a group of order 8.
For `G = ℤ/8` (written multiplicatively) with connection set the four odd
residues, `Cay(G, S)` is the complete bipartite graph `K₄,₄`.  Its census has
exactly two distinct rows,

`n = 0..4`:  `[1,0,0,0,0,0,0,0]`, `[0,1,0,1,0,1,0,1]`, `[4,0,4,0,4,0,4,0]`,
`[0,16,0,16,0,16,0,16]`, `[64,0,64,0,64,0,64,0]`,

whereas `⟨inversion, Aut(G,S)⟩` has four orbits `{0}, {4}, {2,6}, {1,3,5,7}`.
Concretely `2` and `4` have identical censuses but are *not* census-equivalent:
`4` is an involution and `2` is not, and `CensusEquiv_sq_eq_one_iff` shows that
census equivalence must preserve being an involution.  The extra coincidence is
explained instead by the transposition `(2 4)`, a graph automorphism of `K₄,₄`
fixing the identity that is not induced by any group automorphism.

## Main results

* `adjPow_graphAut`, `walkCount_graphAut`
* `walkCount_mulAut_of_graphAut`
* `CensusEquiv_sq_eq_one_iff`
* `census_eq_but_not_censusEquiv` — the converse of the invariance theorem is
  false; the census orbits are strictly coarser than the `⟨inv, Aut(G,S)⟩`
  orbits.
-/

namespace CayleyCensus

variable {G : Type*} [Group G] [Fintype G] [DecidableEq G]

/-! ### Invariance under graph automorphisms fixing the identity -/




/-! ### An invariant of census equivalence -/


/-! ### The converse fails: `K₄,₄` as a Cayley graph on `ℤ/8` -/

open Multiplicative

/-- `ℤ/8` written multiplicatively. -/
abbrev Z8 := Multiplicative (ZMod 8)

/-- The four odd residues; the resulting Cayley graph is `K₄,₄`. -/
def oddSet : Finset Z8 := {ofAdd 1, ofAdd 3, ofAdd 5, ofAdd 7}


/-- The transposition exchanging `2` and `4`.  It fixes the identity and
preserves the bipartition of `K₄,₄`, hence is a graph automorphism; it is not a
group automorphism, since `2` and `4` have different orders. -/
def swap24 : Z8 ≃ Z8 := Equiv.swap (ofAdd (2 : ZMod 8)) (ofAdd (4 : ZMod 8))





end CayleyCensus

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me