simple_graph_cycle_power_dyadic_class_model_vertex_layers
For an optimal (m+1)-layer dyadic cover, with ell(p) the unique layer covering the endpoint pair (p, p+2^m-1) and the class of p cut to the arc of length 2^m, exactly m+1 of the rooted classes at a fixed vertex v are active.
Statement
theorem simple_graph_cycle_power_dyadic_class_model_vertex_layers (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)) (hellroot : ∀ p : ℤ, c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n)) (helluniq : ∀ (p : ℤ) (s : Fin (m + 1)), c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p) (v : ℤ) : (Finset.range (2 ^ m)).sum (fun a => (decide (a < 2 ^ m ∧ c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) = c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n)))).toNat) = m + 1
- Source
- step towards simple_graph_cycle_power_dyadic_cover_class_model
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- simple_graph_cycle_power_dyadic_cover_layer_root_uniqueIn an optimal (m+1)-layer cover of C_n^{2^m-1}, for each layer s and each vertex v, there is a unique offset a ≤ 2^m-1 such that v-a is…
- simple_graph_cycle_power_dyadic_cover_fibre_endpoint_uniqueIn any clique labeling of the cycle power C_n^{2^m-1} with n ≥ 3(2^m-1)+1, each clique contains at most one pair at distance 2^m-1.
- 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…
- simple_graph_cycle_power_dyadic_cover_class_spanningEvery label class of an optimal m+1-layer cover at dyadic bandwidth is spanned by an endpoint-distance pair: each vertex lies in a class…
- bool_sum_eq_card_filterA Boolean profile summed through toNat over a natural range counts exactly its true offsets in that range.
- simple_graph_cycle_power_dyadic_class_model_disjoint_coloursTwo active rooted classes at a common vertex with distinct offsets have distinct layer colours.
- Used by 2
- 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…
- simple_graph_cycle_power_dyadic_class_model_tight_weightsEvery rooted dyadic class of an optimal cover is tight: the dyadic class weight of the arc equals its cardinality.
The proof, explained
The proof counts the active rooted classes at vertex v by reinterpreting the indicator sum as the cardinality of the subset S of active offsets a < 2^m. It establishes that the assignment mapping an offset a to its layer ℓ(v - a) is a bijection from S to Fin(m + 1). Injectivity is guaranteed by the fact that distinct active classes at v must have different colors, while surjectivity follows from the spanning property of dyadic covers. Since Fin(m + 1) has size m + 1, exactly m + 1 rooted classes are active at v.
The sum of boolean indicators equals the cardinality of the set S of active offsets a < 2^m at vertex v, reducing the problem to showing |S| = m + 1.
We define P(a) to be the condition that a < 2^m and the vertex v = (v - a) + a belongs to the same monochromatic class as the root v - a in layer ℓ(v - a). Let S be the subset of offsets in {0, ..., 2^m - 1} satisfying P(a). By `bool_sum_eq_card_filter`, summing the boolean indicator of P(a) over a < 2^m equals |S|. Thus, it suffices to prove |S| = m + 1.
uses
bool_sum_eq_card_filterclassical let P : ℕ → Prop := fun a => a < 2^m ∧ c (ell (v-(a : ℤ))) (((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n)) = c (ell (v-(a : ℤ))) ((v-(a : ℤ) : ℤ) : ZMod n) let S := (range (2^m)).filter (fun a => decide (P a) = true) change (range (2^m)).sum (fun a => (decide (P a)).toNat) = m+1 rw [bool_sum_eq_card_filter] change S.card = m+1
To show |S| = m + 1, it suffices to establish that a ↦ ℓ(v - a) is a bijection from S to Fin(m + 1), and the codomain condition holds trivially.
We apply `card_bij` with the mapping a ↦ ℓ(v - a) from S to the universe of Fin(m + 1). For every a ∈ S, the image ℓ(v - a) is automatically in the universe `univ` of Fin(m + 1) by `mem_univ`.
uses
card_bij,mem_univhave hcard : S.card = (univ : Finset (Fin (m+1))).card := by apply card_bij (s := S) (t := (univ : Finset (Fin (m+1)))) (fun (a : ℕ) _ => ell (v-(a : ℤ))) · intro a ha exact mem_univ _
The layer assignment a ↦ ℓ(v - a) is injective on S.
Assume a, b ∈ S satisfy ℓ(v - a) = ℓ(v - b). Since a, b ∈ S, both P(a) and P(b) hold. If a ≠ b, the lemma `simple_graph_cycle_power_dyadic_class_model_disjoint_colours` states that distinct active classes at v cannot share the same layer color, i.e., ℓ(v - a) ≠ ℓ(v - b). This contradicts our equality, so we must have a = b.
uses
decide_eq_true_eq,simple_graph_cycle_power_dyadic_class_model_disjoint_colours· intro a ha b hb he have hPa : P a := by simpa only [decide_eq_true_eq] using (mem_filter.mp ha).2 have hPb : P b := by simpa only [decide_eq_true_eq] using (mem_filter.mp hb).2 by_contra hne exact (simple_graph_cycle_power_dyadic_class_model_disjoint_colours m n hm hn c hc hcov ell hellroot helluniq v a b hPa.1 hPb.1 hne hPa.2 hPb.2) he
The layer assignment a ↦ ℓ(v - a) is surjective onto Fin(m + 1).
Given any layer s ∈ Fin(m + 1), the spanning property `simple_graph_cycle_power_dyadic_cover_class_spanning` yields an offset a ≤ 2^m - 1 such that in layer s, v - a shares the color of v, and v - a shares the color of its endpoint (v - a) + (2^m - 1). By the uniqueness hypothesis `helluniq`, s must be the unique layer ℓ(v - a) for root v - a. Since a ≤ 2^m - 1, we have a < 2^m by arithmetic (`Nat.two_pow_pos`), and v = (v - a) + a shares the color of root v - a in layer s = ℓ(v - a), so P(a) holds and a ∈ S maps to s.
uses
simple_graph_cycle_power_dyadic_cover_class_spanning,Int.cast_sub,Int.cast_natCast,Nat.two_pow_pos,decide_eq_true_eq· intro s hs obtain ⟨a, ha, hra, hend⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning m n hm hn c hc hcov s (v : ZMod n) have he : s = ell (v-(a : ℤ)) := helluniq (v-(a : ℤ)) s (by simpa only [Int.cast_sub, Int.cast_natCast] using hend.symm) have hv : ((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n) = (v : ZMod n) := by push_cast; ring have haD : a < 2^m := by have hpow := Nat.two_pow_pos m omega have hPa : P a := by refine ⟨haD, ?_⟩ rw [← he, hv] simpa only [Int.cast_sub, Int.cast_natCast] using hra.symm refine ⟨a, mem_filter.mpr ⟨mem_range.mpr haD, ?_⟩, he.symm⟩ simpa only [decide_eq_true_eq] using hPa
The cardinality of S is m + 1, completing the proof.
The bijection established that |S| equals the cardinality of `univ` on Fin(m + 1). By `card_univ` and `Fintype.card_fin`, the cardinality of Fin(m + 1) is m + 1, so |S| = m + 1.
uses
card_univ,Fintype.card_finsimpa only [card_univ, Fintype.card_fin] using hcard
bool_sum_eq_card_filter- The sum of a boolean predicate over {0, ..., N - 1} equals the cardinality of the sub-finset of elements satisfying the predicate.
card_bij- Two finsets s and t have the same cardinality if there is a function from s to t that maps into t, is injective on s, and is surjective onto t.
mem_univ- Every element of a finite type belongs to the universal finset `univ`.
decide_eq_true_eq- A decidable proposition p is true if and only if decide p = true.
simple_graph_cycle_power_dyadic_class_model_disjoint_colours- In an optimal dyadic cover of a cycle power graph, two distinct offsets a ≠ b at vertex v that define active monochromatic rooted classes cannot share the same layer color.
simple_graph_cycle_power_dyadic_cover_class_spanning- In an optimal dyadic cover, for every layer s and vertex v, there exists an offset a ≤ 2^m - 1 such that v - a has the same color as v in layer s, and v - a has the same color as the endpoint (v - a) + (2^m - 1).
Int.cast_sub- Integer subtraction commutes with casting into an additive group with one, such as ℤ/nℤ.
Int.cast_natCast- Casting a natural number to integers and then into a ring is equal to casting the natural number directly.
Nat.two_pow_pos- The power 2^w is strictly positive for every natural number w.
card_univ- The cardinality of the universal finset `univ` of a finite type equals the cardinality of the type.
Fintype.card_fin- The finite type Fin n has cardinality n.
- The arithmetic equality showing that offset a satisfies a < 2^m given a ≤ 2^m - 1 is closed by omega using the positivity of 2^m.
- Casting and ring operations between ℤ, ℕ, and ℤ/nℤ are handled by push_cast and ring.
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/-- Constant active count: exactly m+1 rooted classes are active at each vertex of an optimal dyadic cover. -/theorem simple_graph_cycle_power_dyadic_class_model_vertex_layers (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)) (hellroot : ∀ p : ℤ, c (ell p) ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c (ell p) (p : ZMod n)) (helluniq : ∀ (p : ℤ) (s : Fin (m + 1)), c s ((p : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) = c s (p : ZMod n) → s = ell p) (v : ℤ) : (Finset.range (2 ^ m)).sum (fun a => (decide (a < 2 ^ m ∧ c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) = c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n)))).toNat) = m + 1 := by classical let P : ℕ → Prop := fun a => a < 2^m ∧ c (ell (v-(a : ℤ))) (((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n)) = c (ell (v-(a : ℤ))) ((v-(a : ℤ) : ℤ) : ZMod n) let S := (range (2^m)).filter (fun a => decide (P a) = true) change (range (2^m)).sum (fun a => (decide (P a)).toNat) = m+1 rw [bool_sum_eq_card_filter] change S.card = m+1 have hcard : S.card = (univ : Finset (Fin (m+1))).card := by apply card_bij (s := S) (t := (univ : Finset (Fin (m+1)))) (fun (a : ℕ) _ => ell (v-(a : ℤ))) · intro a ha exact mem_univ _ · intro a ha b hb he have hPa : P a := by simpa only [decide_eq_true_eq] using (mem_filter.mp ha).2 have hPb : P b := by simpa only [decide_eq_true_eq] using (mem_filter.mp hb).2 by_contra hne exact (simple_graph_cycle_power_dyadic_class_model_disjoint_colours m n hm hn c hc hcov ell hellroot helluniq v a b hPa.1 hPb.1 hne hPa.2 hPb.2) he · intro s hs obtain ⟨a, ha, hra, hend⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning m n hm hn c hc hcov s (v : ZMod n) have he : s = ell (v-(a : ℤ)) := helluniq (v-(a : ℤ)) s (by simpa only [Int.cast_sub, Int.cast_natCast] using hend.symm) have hv : ((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n) = (v : ZMod n) := by push_cast; ring have haD : a < 2^m := by have hpow := Nat.two_pow_pos m omega have hPa : P a := by refine ⟨haD, ?_⟩ rw [← he, hv] simpa only [Int.cast_sub, Int.cast_natCast] using hra.symm refine ⟨a, mem_filter.mpr ⟨mem_range.mpr haD, ?_⟩, he.symm⟩ simpa only [decide_eq_true_eq] using hPa simpa only [card_univ, Fintype.card_fin] using hcard