simple_graph_cycle_power_dyadic_class_model_exact_dyadic
For every j < m and every integer vertex v there is exactly one offset a < 2^j such that the rooted class at a from v is active at both a and a+(2^m-2^j).
Statement
theorem simple_graph_cycle_power_dyadic_class_model_exact_dyadic (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) (j : ℕ) (hj : j < m) (v : ℤ) : (Finset.range (2 ^ j)).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)) && decide (a + 2 ^ m - 2 ^ j < 2 ^ m ∧ c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + ((a + 2 ^ m - 2 ^ j : ℕ) : ZMod n)) = c (ell (v - (a : ℤ))) ((v - (a : ℤ) : ℤ) : ZMod n))).toNat) = 1
- Source
- step towards simple_graph_cycle_power_dyadic_cover_class_model
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- simple_graph_cycle_power_dyadic_cover_edge_spanIf a monochromatic clique contains v and v+d with 1 ≤ d < 2^m, its root v-a (with a ≤ 2^m-1) satisfies a < 2^m - d, so the entire edge {v,…
- 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_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…
- zmod_intCast_eq_intCast_iff_of_abs_sub_ltTwo integers a, b with |a − b| < n are equal modulo n only if they are equal.
- 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_class_model_disjoint_coloursTwo active rooted classes at a common vertex with distinct offsets have distinct layer colours.
- simple_graph_cycle_power_dyadic_class_model_ordinary_coverFor every distance 1 ≤ d < 2^m and every integer vertex v there is a rooted offset a < 2^m - d whose class is active at both v-a and v-a+d.
- 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 theorem shows that for every scale j < m and integer vertex v, exactly one offset a < 2^j yields a rooted class active at both a and a + (2^m - 2^j). The proof first reformulates the summation as counting offsets satisfying this joint activity predicate for step distance d = 2^m - 2^j. Existence of an active offset a < 2^j is supplied by an ordinary covering lemma. Uniqueness follows because any active offset forces its color to cover the tight long edge between v and v + d, which has a unique monochromatic color, whereas distinct active offsets are known to have distinct colors.
Define the scale parameters D = 2^m, R = 2^j, and d = D - R, and establish the bounds 0 < R < D and 1 ≤ d < D.
We assume classical logic. Because j < m, the inequality R < D follows from strict monotonicity of powers of 2 (Nat.pow_lt_pow_right), and R > 0 holds since powers of 2 are strictly positive (Nat.two_pow_pos). These bounds imply 1 ≤ d < D for d = D - R by linear integer arithmetic.
uses
Nat.pow_lt_pow_right,Nat.two_pow_posclassical let D := 2^m let R := 2^j let d := D-R have hRD : R < D := Nat.pow_lt_pow_right (by decide) hj have hR : 0 < R := Nat.two_pow_pos j have hd : 1 ≤ d := by dsimp [d]; omega have hdD : d < 2^m := by change D-R < D; omega
Define the joint activity predicate T(a) and rephrase the goal as ∑_{a < R} (T(a)).toNat = 1.
We define x(p, a) to be the boolean test for whether the rooted class at p is active at offset a, and T(a) to test whether the class rooted at v - a is active at both a and a + d. Since a + 2^m - 2^j = a + d, the summation in the theorem simplifies to summing (T(a)).toNat over a ∈ Finset.range R.
let x : ℤ → ℕ → Bool := fun p a => decide (a < D ∧ c (ell p) ((p : ZMod n)+(a : ZMod n)) = c (ell p) (p : ZMod n)) let T : ℕ → Bool := fun a => x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+d) have hnat (a : ℕ) : a+2^m-2^j = a+d := by dsimp [D, R, d]; omega change (range R).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1 simp_rw [hnat] change (range R).sum (fun a => (T a).toNat) = 1
There exists an offset a < R such that T(a) = true.
Applying simple_graph_cycle_power_dyadic_class_model_ordinary_cover to the distance d = D - R provides an offset a < D - d = R whose rooted class at v - a is active at both a and a + d. Unfolding T and simplifying with Bool.true_and shows T(a) = true.
uses
simple_graph_cycle_power_dyadic_class_model_ordinary_cover,Bool.true_andobtain ⟨a, ha, h0, h1⟩ := simple_graph_cycle_power_dyadic_class_model_ordinary_cover m n hm hn c hc hcov ell hellroot helluniq d hd hdD v have haR : a < R := by change a < D-(D-R) at ha; omega have hTa : T a = true := by simp only [T, x, D] at *; simp only [h0, h1, Bool.true_and]
Any offset b with T(b) = true makes the pair (v, v + d) monochromatic under color ℓ(v - b).
If T(b) = true, both activity conditions hold (Bool.and_eq_true_iff.mp, of_decide_eq_true). The first condition gives c_{ℓ(v - b)}((v - b) + b) = c_{ℓ(v - b)}(v - b), which simplifies to c_{ℓ(v - b)}(v) = c_{ℓ(v - b)}(v - b). The second gives c_{ℓ(v - b)}((v - b) + (b + d)) = c_{ℓ(v - b)}(v - b), simplifying to c_{ℓ(v - b)}(v + d) = c_{ℓ(v - b)}(v - b). By transitivity and symmetry, c_{ℓ(v - b)}(v) = c_{ℓ(v - b)}(v + d).
uses
Bool.and_eq_true_iff.mp,of_decide_eq_truehave hcovering (b : ℕ) (hTb : T b = true) : c (ell (v-(b : ℤ))) (v : ZMod n) = c (ell (v-(b : ℤ))) ((v : ZMod n)+(d : ZMod n)) := by have hbits : x (v-(b : ℤ)) b = true ∧ x (v-(b : ℤ)) (b+d) = true := Bool.and_eq_true_iff.mp hTb have hb0 := (of_decide_eq_true hbits.1).2 have hb1 := (of_decide_eq_true hbits.2).2 have hv0 : ((v-(b : ℤ) : ℤ) : ZMod n)+(b : ZMod n) = (v : ZMod n) := by push_cast; ring have hv1 : ((v-(b : ℤ) : ℤ) : ZMod n)+((b+d : ℕ) : ZMod n) = (v : ZMod n)+(d : ZMod n) := by push_cast; ring rw [hv0] at hb0 rw [hv1] at hb1 exact hb0.trans hb1.symm
There is a unique color s ∈ Fin (m + 1) such that c_s(v) = c_s(v + d).
By simple_graph_cycle_power_dyadic_cover_tight_long_edges, tight long edges are covered by a unique color class. If j = 0, d = 2^m - 1 (using pow_zero), which matches the first clause of the lemma; if j > 0, then 1 ≤ j < m and the second clause applies.
uses
simple_graph_cycle_power_dyadic_cover_tight_long_edges,pow_zerohave hu : ∃! s : Fin (m+1), c s (v : ZMod n) = c s ((v : ZMod n)+(d : ZMod n)) := by have hh := simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov by_cases hj0 : j=0 · subst j simpa only [d, D, R, pow_zero] using hh.1 (v : ZMod n) · simpa only [d, D, R] using hh.2 j (by omega) hj (v : ZMod n)
Any active offset b < R must equal a.
If b < R and T(b) = true, both ℓ(v - b) and ℓ(v - a) make (v, v + d) monochromatic. The uniqueness of such a color implies ℓ(v - b) = ℓ(v - a). If b ≠ a, then since both offsets are strictly less than D and their classes are active at v, simple_graph_cycle_power_dyadic_class_model_disjoint_colours would force ℓ(v - b) ≠ ℓ(v - a), a contradiction. Hence b = a.
uses
Bool.and_eq_true_iff.mp,of_decide_eq_true,simple_graph_cycle_power_dyadic_class_model_disjoint_colourshave huniq (b : ℕ) (hb : b < R) (hTb : T b = true) : b=a := by have he : ell (v-(b : ℤ)) = ell (v-(a : ℤ)) := hu.unique (hcovering b hTb) (hcovering a hTa) have hbitsb := (Bool.and_eq_true_iff.mp hTb).1 have hbitsa := (Bool.and_eq_true_iff.mp hTa).1 have hPb := (of_decide_eq_true hbitsb).2 have hPa := (of_decide_eq_true hbitsa).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 b a (by dsimp [D] at hRD; omega) (by dsimp [D] at hRD; omega) hne hPb hPa) he
The sum over a < R evaluates to 1.
Using sum_eq_single a, the sum over Finset.range R reduces to the single term at a. At a, T(a) = true contributes 1 (Bool.toNat_true). For every other b in Finset.range R (mem_range.mp), uniqueness implies T(b) = false (Bool.eq_false_iff.mpr), which contributes 0 (Bool.toNat_false). Lastly, a ∈ Finset.range R holds because a < R (mem_range.mpr).
uses
sum_eq_single,Bool.toNat_true,Bool.eq_false_iff.mpr,mem_range.mp,Bool.toNat_false,mem_range.mprrw [sum_eq_single a] · simp only [hTa, Bool.toNat_true] · intro b hb hba have he : T b = false := Bool.eq_false_iff.mpr (fun hTb => hba (huniq b (mem_range.mp hb) hTb)) simp only [he, Bool.toNat_false] · intro hnot exact (hnot (mem_range.mpr haR)).elim
Nat.pow_lt_pow_right- For base a > 1, m < n implies a^m < a^n
Nat.two_pow_pos- For any natural number w, 2^w > 0
simple_graph_cycle_power_dyadic_class_model_ordinary_cover- For any distance 1 ≤ d < 2^m, there exists an offset a < 2^m - d whose rooted class is active at both a and a + d
Bool.true_and- The boolean expression true && b evaluates to b
Bool.and_eq_true_iff.mp- If b₁ && b₂ = true, then both b₁ = true and b₂ = true
of_decide_eq_true- If decide P = true, then proposition P holds
simple_graph_cycle_power_dyadic_cover_tight_long_edges- Tight long edges of length 2^m - 1 or 2^m - 2^j (1 ≤ j < m) are covered by a unique color class s ∈ Fin (m + 1)
pow_zero- Any element raised to the power 0 equals 1
simple_graph_cycle_power_dyadic_class_model_disjoint_colours- Distinct active offsets a ≠ b < 2^m passing through v have distinct colors ℓ(v - a) ≠ ℓ(v - b)
sum_eq_single- A finite sum over a set where all terms except a evaluate to 0 equals the value at a
Bool.toNat_true- The numerical conversion of true is 1
Bool.eq_false_iff.mpr- A boolean not equal to true is false
mem_range.mp- Membership in Finset.range n implies being strictly less than n
Bool.toNat_false- The numerical conversion of false is 0
mem_range.mpr- Being strictly less than n implies membership in Finset.range n
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/-- Exact dyadic coverage: for each j < m and each vertex, exactly one rooted class is active at both offsets a and a+(2^m-2^j). -/theorem simple_graph_cycle_power_dyadic_class_model_exact_dyadic (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) (j : ℕ) (hj : j < m) (v : ℤ) : (Finset.range (2 ^ j)).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)) && decide (a + 2 ^ m - 2 ^ j < 2 ^ m ∧ c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + ((a + 2 ^ m - 2 ^ j : ℕ) : ZMod n)) = c (ell (v - (a : ℤ))) ((v - (a : ℤ) : ℤ) : ZMod n))).toNat) = 1 := by classical let D := 2^m let R := 2^j let d := D-R have hRD : R < D := Nat.pow_lt_pow_right (by decide) hj have hR : 0 < R := Nat.two_pow_pos j have hd : 1 ≤ d := by dsimp [d]; omega have hdD : d < 2^m := by change D-R < D; omega let x : ℤ → ℕ → Bool := fun p a => decide (a < D ∧ c (ell p) ((p : ZMod n)+(a : ZMod n)) = c (ell p) (p : ZMod n)) let T : ℕ → Bool := fun a => x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+d) have hnat (a : ℕ) : a+2^m-2^j = a+d := by dsimp [D, R, d]; omega change (range R).sum (fun a => (x (v-(a : ℤ)) a && x (v-(a : ℤ)) (a+2^m-2^j)).toNat) = 1 simp_rw [hnat] change (range R).sum (fun a => (T a).toNat) = 1 obtain ⟨a, ha, h0, h1⟩ := simple_graph_cycle_power_dyadic_class_model_ordinary_cover m n hm hn c hc hcov ell hellroot helluniq d hd hdD v have haR : a < R := by change a < D-(D-R) at ha; omega have hTa : T a = true := by simp only [T, x, D] at *; simp only [h0, h1, Bool.true_and] have hcovering (b : ℕ) (hTb : T b = true) : c (ell (v-(b : ℤ))) (v : ZMod n) = c (ell (v-(b : ℤ))) ((v : ZMod n)+(d : ZMod n)) := by have hbits : x (v-(b : ℤ)) b = true ∧ x (v-(b : ℤ)) (b+d) = true := Bool.and_eq_true_iff.mp hTb have hb0 := (of_decide_eq_true hbits.1).2 have hb1 := (of_decide_eq_true hbits.2).2 have hv0 : ((v-(b : ℤ) : ℤ) : ZMod n)+(b : ZMod n) = (v : ZMod n) := by push_cast; ring have hv1 : ((v-(b : ℤ) : ℤ) : ZMod n)+((b+d : ℕ) : ZMod n) = (v : ZMod n)+(d : ZMod n) := by push_cast; ring rw [hv0] at hb0 rw [hv1] at hb1 exact hb0.trans hb1.symm have hu : ∃! s : Fin (m+1), c s (v : ZMod n) = c s ((v : ZMod n)+(d : ZMod n)) := by have hh := simple_graph_cycle_power_dyadic_cover_tight_long_edges m n hm hn c hc hcov by_cases hj0 : j=0 · subst j simpa only [d, D, R, pow_zero] using hh.1 (v : ZMod n) · simpa only [d, D, R] using hh.2 j (by omega) hj (v : ZMod n) have huniq (b : ℕ) (hb : b < R) (hTb : T b = true) : b=a := by have he : ell (v-(b : ℤ)) = ell (v-(a : ℤ)) := hu.unique (hcovering b hTb) (hcovering a hTa) have hbitsb := (Bool.and_eq_true_iff.mp hTb).1 have hbitsa := (Bool.and_eq_true_iff.mp hTa).1 have hPb := (of_decide_eq_true hbitsb).2 have hPa := (of_decide_eq_true hbitsa).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 b a (by dsimp [D] at hRD; omega) (by dsimp [D] at hRD; omega) hne hPb hPa) he rw [sum_eq_single a] · simp only [hTa, Bool.toNat_true] · intro b hb hba have he : T b = false := Bool.eq_false_iff.mpr (fun hTb => hba (huniq b (mem_range.mp hb) hTb)) simp only [he, Bool.toNat_false] · intro hnot exact (hnot (mem_range.mpr haR)).elim