simple_graph_cycle_power_dyadic_class_model_layer_choice
There is a periodic integer layer map ell assigning to each integer p the unique layer covering the endpoint pair (p, p+2^m-1), with uniqueness among all layers.
Statement
theorem simple_graph_cycle_power_dyadic_class_model_layer_choice
(m n : ℕ) [NeZero n] (hm : 1 ≤ m)
(hn : 3 * (2 ^ m - 1) + 1 ≤ n)
(c : Fin (m + 1) → ZMod n → ZMod n)
(hc : ∀ s u v, u ≠ v → c s u = c s v →
(simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)
(hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v →
∃ s, c s u = c s v) :
∃ ell : ℤ → Fin (m + 1),
(∀ p : ℤ, ell (p + (n : ℤ)) = ell p) ∧
(∀ p : ℤ,
c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n)) ∧
(∀ (p : ℤ) (s : Fin (m + 1)),
c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p)- Source
- step towards simple_graph_cycle_power_dyadic_cover_class_model
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- simple_graph_cycle_power_dyadic_cover_tight_long_edgesIn an m+1-layer equivalence cover at dyadic bandwidth, every endpoint-distance edge and every other positively weighted dyadic long edge…
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
- Used by 1
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
The proof, explained
The theorem establishes the existence of an n-periodic layer map ℓ : ℤ → Fin(m+1) assigning to each integer p the unique layer covering (p, p + 2^m - 1). By a previously established lemma on cycle power covers, each residue class i ∈ ℤ/nℤ admits a unique layer identifying i with i + 2^m - 1. The map ℓ is constructed by choosing this unique layer on ℤ/nℤ and pulling it back along the quotient projection ℤ → ℤ/nℤ. Periodicity holds because n ≡ 0 (mod n), and the covering and uniqueness properties on ℤ follow directly from the residue-level uniqueness.
We define the candidate layer map ℓ : ℤ → Fin(m+1) by choosing the unique covering layer for each residue class in ℤ/nℤ, reducing the theorem to periodicity, covering, and uniqueness.
By simple_graph_cycle_power_dyadic_cover_tight_long_edges, for each vertex i ∈ ℤ/nℤ there exists a unique layer s ∈ Fin(m+1) such that c(s, i) = c(s, i + 2^m - 1). Choosing this unique layer gives a map f : ℤ/nℤ → Fin(m+1) and its specification hf. We define the candidate map ℓ : ℤ → Fin(m+1) by ℓ(p) = f(p mod n). Providing ℓ as the existential witness reduces the theorem to three subgoals: showing that ℓ is n-periodic, that ℓ(p) covers (p, p + 2^m - 1), and that ℓ(p) is unique among all layers.
uses
simple_graph_cycle_power_dyadic_cover_tight_long_edgesclassical have ht := (simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov).1 let f : ZMod n → Fin (m+1) := fun p => (ht p).choose have hf (p : ZMod n) := (ht p).choose_spec refine ⟨fun p => f (p : ZMod n), ?_, ?_, ?_⟩
The layer map ℓ is periodic with period n: ℓ(p + n) = ℓ(p) for all p ∈ ℤ.
For any integer p, the integer p + n projects in ℤ/nℤ to (p mod n) + (n mod n). Since n mod n = 0, this simplifies to p mod n, so f((p + n) mod n) = f(p mod n). This simplification is performed by rewriting with Int.cast_add, Int.cast_natCast, ZMod.natCast_self, and add_zero.
uses
Int.cast_add,Int.cast_natCast,ZMod.natCast_self,add_zero· intro p simp only [Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero]
For every integer p, the layer ℓ(p) covers the endpoint pair (p, p + 2^m - 1).
By construction, ℓ(p) = f(p mod n). The covering property of f(p mod n) states that c(f(p mod n), p mod n) = c(f(p mod n), (p mod n) + 2^m - 1). Symmetrizing this equality establishes that c(ℓ(p), p + 2^m - 1) = c(ℓ(p), p).
· intro p exact (hf (p : ZMod n)).1.symm
The covering layer ℓ(p) is unique: any layer covering (p, p + 2^m - 1) must equal ℓ(p).
Let s ∈ Fin(m+1) be any layer such that c(s, p + 2^m - 1) = c(s, p). Symmetrizing this hypothesis yields c(s, p) = c(s, p + 2^m - 1). The uniqueness clause in the specification of f(p mod n) then implies s = f(p mod n) = ℓ(p).
· intro p s hs exact (hf (p : ZMod n)).2 s hs.symm
add_zero- Adding zero to any element leaves it unchanged: a + 0 = a.
Int.cast_add- The canonical cast from integers to an additive group with one distributes over addition: ↑(a + b) = ↑a + ↑b.
Int.cast_natCast- Casting a natural number to the integers and then into an additive group with one is the same as casting directly from the natural numbers.
simple_graph_cycle_power_dyadic_cover_tight_long_edges- In any (m + 1)-layer cover of the cycle power C_n^{≤ 2^m - 1}, each vertex i ∈ ℤ/nℤ has a unique layer s such that c(s, i) = c(s, i + 2^m - 1), and similarly for dyadic distances 2^m - 2^j.
ZMod.natCast_self- The modulus n is zero when cast into ℤ/nℤ: ↑n = 0.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000/-- Canonical layer assignment: the unique covering layer of each endpoint-distance pair, extended periodically to the integers. -/theorem simple_graph_cycle_power_dyadic_class_model_layer_choice (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : Fin (m + 1) → ZMod n → ZMod n) (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v → ∃ s, c s u = c s v) : ∃ ell : ℤ → Fin (m + 1), (∀ p : ℤ, ell (p + (n : ℤ)) = ell p) ∧ (∀ p : ℤ, c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n)) ∧ (∀ (p : ℤ) (s : Fin (m + 1)), c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p) := by classical have ht := (simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov).1 let f : ZMod n → Fin (m+1) := fun p => (ht p).choose have hf (p : ZMod n) := (ht p).choose_spec refine ⟨fun p => f (p : ZMod n), ?_, ?_, ?_⟩ · intro p simp only [Int.cast_add, Int.cast_natCast, ZMod.natCast_self, add_zero] · intro p exact (hf (p : ZMod n)).1.symm · intro p s hs exact (hf (p : ZMod n)).2 s hs.symm