simple_graph_cycle_power_dyadic_cover_edge_span
If 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, v+d} is contained in the span of v-a.
Statement
theorem simple_graph_cycle_power_dyadic_cover_edge_span
(m n : ℕ) [NeZero n] (hn : 3 * (2 ^ m - 1) + 1 ≤ n)
(c : ZMod n → ZMod n)
(hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)
(v : ZMod n) (d : ℕ) (hd1 : 1 ≤ d) (hd2 : d < 2 ^ m)
(hcd : c v = c (v + (d : ZMod n)))
(a : ℕ) (ha : a ≤ 2 ^ m - 1)
(hroot : c (v - (a : ZMod n)) = c v)
(hend : c (v - (a : ZMod n)) = c (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n))) :
a < 2 ^ m - d ∧ c (v - (a : ZMod n)) = c (v - (a : ZMod n) + ((a + d : ℕ) : ZMod n))- Source
- step towards simple_graph_cycle_power_dyadic_cover_class_model
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_cycle_power_clique_arcFor n at least 3k+1, every nonempty clique of the k-th cycle power lies in a forward arc of k+1 vertices whose first vertex belongs to the…
- 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_rooted_clique_arcLet n,k be natural numbers with n nonzero and n at least3k+1. Let c label the vertices of the k-th cycle power so that two distinct…
- Used by 3
- 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_exact_dyadicFor 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…
- 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.
The proof, explained
The rooted monochromatic clique starting at v - a extends along the cycle to an arc of length 2^m - 1. Because v + d shares the clique's color, it lies on this arc at position (v - a) + b for some b ≤ 2^m - 1. Since n ≥ 3(2^m - 1) + 1 is large enough, the congruence (v - a) + (a + d) = (v - a) + b in ℤ/nℤ lifts to an exact integer equality a + d = b, which immediately yields a < 2^m - d. The color of (v - a) + (a + d) matches that of v - a because both equal c(v).
The vertex v + d lies on the arc of length 2^m - 1 starting at v - a, so v + d = (v - a) + b for some natural number b ≤ 2^m - 1.
By `simple_graph_cycle_power_rooted_clique_arc` applied to the root v - a, every vertex with color c(v - a) must be of the form (v - a) + b with b ≤ 2^m - 1. Since c(v + d) = c(v) = c(v - a) by transitivity, v + d has this color, yielding a witness b ≤ 2^m - 1 such that v + d = (v - a) + b.
uses
simple_graph_cycle_power_rooted_clique_archave harc := simple_graph_cycle_power_rooted_clique_arc n (2^m-1) hn c hc (v-(a : ZMod n)) hend obtain ⟨b, hb, hvb⟩ := harc (v+(d : ZMod n)) (hcd.symm.trans hroot.symm)
a + d = b in ℤ/nℤ.
In ℤ/nℤ, (v - a) + (a + d) simplifies to v + d, which equals (v - a) + b. Cancelling v - a from both sides with `add_left_cancel` yields a + d = b in ℤ/nℤ.
uses
add_left_cancelhave he : ((a+d : ℕ) : ZMod n) = (b : ZMod n) := by apply add_left_cancel (a := v-(a : ZMod n)) calc (v-(a : ZMod n))+((a+d : ℕ) : ZMod n) = v+(d : ZMod n) := by push_cast; ring _ = (v-(a : ZMod n))+(b : ZMod n) := hvb
a + d = b as natural numbers.
By `ZMod.natCast_eq_natCast_iff`, equality in ℤ/nℤ is equivalent to congruence modulo n. Since a ≤ 2^m - 1 and d < 2^m, and b ≤ 2^m - 1, both a + d and b are strictly less than n (using the hypothesis 3(2^m - 1) + 1 ≤ n, verified by `omega`). Hence `Nat.ModEq.eq_of_lt_of_lt` establishes exact equality a + d = b in ℕ.
uses
Nat.ModEq.eq_of_lt_of_lt,ZMod.natCast_eq_natCast_iffhave hen : a+d=b := Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp he) (by omega) (by omega)
a < 2^m - d. automation
Linear arithmetic (`omega`) deduces a < 2^m - d from a + d = b and b ≤ 2^m - 1, establishing the first conjunct.
refine ⟨by omega, ?_⟩
c(v - a) = c((v - a) + (a + d)).
Because (v - a) + (a + d) = v + d in ℤ/nℤ, the required equality reduces to c(v - a) = c(v + d), which follows directly from the hypotheses c(v - a) = c(v) and c(v) = c(v + d) by transitivity.
have hv : (v-(a : ZMod n))+((a+d : ℕ) : ZMod n) = v+(d : ZMod n) := by push_cast; ring rw [hv] exact hroot.trans hcd
simple_graph_cycle_power_rooted_clique_arc- In an edge coloring of the cycle power graph where monochromatic pairs are adjacent, if a vertex p shares its color with p + k, then every vertex with that color lies on the arc of length k starting at p.
add_left_cancel- In an additive structure with left cancellation, a + b = a + c implies b = c.
Nat.ModEq.eq_of_lt_of_lt- Two natural numbers that are congruent modulo m and both strictly less than m are equal.
ZMod.natCast_eq_natCast_iff- The images of two natural numbers in ℤ/cℤ are equal if and only if the numbers are congruent modulo c.
- The inequality bounds $a + d < n$ and $b < n$ needed to translate modular congruence into equality in ℕ, as well as the bound $a < 2^m - d$, are proved automatically using linear integer arithmetic (`omega`).
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/-- If 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, v+d} is contained in the span of v-a. -/theorem simple_graph_cycle_power_dyadic_cover_edge_span (m n : ℕ) [NeZero n] (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) (v : ZMod n) (d : ℕ) (hd1 : 1 ≤ d) (hd2 : d < 2 ^ m) (hcd : c v = c (v + (d : ZMod n))) (a : ℕ) (ha : a ≤ 2 ^ m - 1) (hroot : c (v - (a : ZMod n)) = c v) (hend : c (v - (a : ZMod n)) = c (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n))) : a < 2 ^ m - d ∧ c (v - (a : ZMod n)) = c (v - (a : ZMod n) + ((a + d : ℕ) : ZMod n)) := by have harc := simple_graph_cycle_power_rooted_clique_arc n (2^m-1) hn c hc (v-(a : ZMod n)) hend obtain ⟨b, hb, hvb⟩ := harc (v+(d : ZMod n)) (hcd.symm.trans hroot.symm) have he : ((a+d : ℕ) : ZMod n) = (b : ZMod n) := by apply add_left_cancel (a := v-(a : ZMod n)) calc (v-(a : ZMod n))+((a+d : ℕ) : ZMod n) = v+(d : ZMod n) := by push_cast; ring _ = (v-(a : ZMod n))+(b : ZMod n) := hvb have hen : a+d=b := Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp he) (by omega) (by omega) refine ⟨by omega, ?_⟩ have hv : (v-(a : ZMod n))+((a+d : ℕ) : ZMod n) = v+(d : ZMod n) := by push_cast; ring rw [hv] exact hroot.trans hcd