simple_graph_cycle_power_dyadic_class_model_disjoint_colours
Two active rooted classes at a common vertex with distinct offsets have distinct layer colours.
Statement
theorem simple_graph_cycle_power_dyadic_class_model_disjoint_colours
(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 : ℤ) (a b : ℕ) (ha : a < 2 ^ m) (hb : b < 2 ^ m) (hab : a ≠ b)
(hxa : c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) =
c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n)))
(hxb : c (ell (v - (b : ℤ))) (((v - (b : ℤ) : ℤ) : ZMod n) + (b : ZMod n)) =
c (ell (v - (b : ℤ))) (((v - (b : ℤ) : ℤ) : ZMod n))) :
ell (v - (a : ℤ)) ≠ ell (v - (b : ℤ))- Source
- step towards simple_graph_cycle_power_dyadic_cover_class_model
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- 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…
- Used by 3
- simple_graph_cycle_power_dyadic_class_model_vertex_layersFor 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…
- 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…
The proof, explained
We argue by contradiction, assuming that two active rooted classes at vertex v with distinct offsets a ≠ b < 2^m share a layer colour s. Under this common colour, the active class assumptions imply that c s (v - a) = c s v = c s (v - b), while both v - a and v - b satisfy the root periodicity condition of step size 2^m - 1. Uniqueness of fibre endpoints in dyadic covers then forces v - a = v - b in ℤ/nℤ. Canceling v yields a ≡ b [MOD n], which forces a = b because both offsets are strictly less than n, contradicting a ≠ b.
Under the assumption that ℓ(v - a) = ℓ(v - b), the vertices v - a and v - b have the same colour as v in this shared layer.
We argue by contradiction and assume that ℓ(v - a) = ℓ(v - b) =: s (hypothesis `he`). In ℤ/nℤ, the offsets satisfy (v - a) + a = v and (v - b) + b = v (proved as `ha0` and `hb0` by pushing casts and ring normalization). Rewriting with these identities into the hypotheses `hxa` and `hxb`, and substituting ℓ(v - b) = s, gives c s v = c s (v - a) and c s v = c s (v - b).
intro he have ha0 : ((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n) = (v : ZMod n) := by push_cast; ring have hb0 : ((v-(b : ℤ) : ℤ) : ZMod n)+(b : ZMod n) = (v : ZMod n) := by push_cast; ring rw [ha0] at hxa rw [hb0, ← he] at hxb
The vertices v - a and v - b coincide in ℤ/nℤ.
By the root condition `hellroot`, both v - a and v - b are endpoints of monochromatic intervals of length 2^m - 1 in layer s: c s (v - a) = c s ((v - a) + (2^m - 1)) and c s (v - b) = c s ((v - b) + (2^m - 1)). Since they also satisfy c s (v - a) = c s (v - b) via their common colour at v, the uniqueness theorem `simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique` applies, concluding that v - a = v - b in ℤ/nℤ.
uses
simple_graph_cycle_power_dyadic_cover_fibre_endpoint_uniquehave hpa := (hellroot (v-(a : ℤ))).symm have hpb := (hellroot (v-(b : ℤ))).symm rw [← he] at hpb have hroot := simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique m n hn (c (ell (v-(a : ℤ)))) (hc (ell (v-(a : ℤ)))) ((v-(a : ℤ) : ℤ) : ZMod n) ((v-(b : ℤ) : ℤ) : ZMod n) hpa hpb (hxa.symm.trans hxb)
The offsets a and b are equal, contradicting a ≠ b.
Simplifying integer and natural casts transforms v - a = v - b into v - a = v - b in ℤ/nℤ (`Int.cast_sub`, `Int.cast_natCast`). Canceling v on the left via `sub_right_inj.mp` gives a = b in ℤ/nℤ, which is equivalent to a ≡ b [MOD n] (`ZMod.natCast_eq_natCast_iff`). Because 1 ≤ m, a < 2^m, b < 2^m, and 3 * (2^m - 1) + 1 ≤ n, linear arithmetic shows both a < n and b < n. Thus a ≡ b [MOD n] implies a = b (`Nat.ModEq.eq_of_lt_of_lt`), which contradicts the assumption hab (a ≠ b).
uses
Int.cast_sub,Int.cast_natCast,sub_right_inj.mp,Nat.ModEq.eq_of_lt_of_lt,ZMod.natCast_eq_natCast_iffsimp only [Int.cast_sub, Int.cast_natCast] at hroot have hcast : (a : ZMod n) = (b : ZMod n) := sub_right_inj.mp hroot have hnat : a=b := Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp hcast) (by omega) (by omega) exact hab hnat
Int.cast_natCast- Casting a natural number into a ring directly or via the integers yields the same element: ↑(↑n : ℤ) = ↑n.
Int.cast_sub- Casting an integer difference into a ring preserves subtraction: ↑(m - n) = ↑m - ↑n.
Nat.ModEq.eq_of_lt_of_lt- If two natural numbers are congruent modulo m and both are strictly less than m, then they are equal.
simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique- In the cycle power graph on ℤ/nℤ with n ≥ 3(2^m - 1) + 1, if every monochromatic pair under a colouring c is adjacent, and two points p and q each have the same colour as their shift by 2^m - 1, then c p = c q implies p = q.
sub_right_inj.mp- In an additive group, if x - y = x - z, then y = z.
ZMod.natCast_eq_natCast_iff- Two natural numbers cast to the same element in ℤ/cℤ if and only if they are congruent modulo c.
- The inequalities a < n and b < n needed to deduce a = b from a ≡ b [MOD n] are proved by `omega` from 1 ≤ m, a < 2^m, b < 2^m, and 3 * (2^m - 1) + 1 ≤ 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/-- At a common vertex, two distinct active rooted classes of an optimal dyadic cover never share a layer colour. -/theorem simple_graph_cycle_power_dyadic_class_model_disjoint_colours (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 : ℤ) (a b : ℕ) (ha : a < 2 ^ m) (hb : b < 2 ^ m) (hab : a ≠ b) (hxa : c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n) + (a : ZMod n)) = c (ell (v - (a : ℤ))) (((v - (a : ℤ) : ℤ) : ZMod n))) (hxb : c (ell (v - (b : ℤ))) (((v - (b : ℤ) : ℤ) : ZMod n) + (b : ZMod n)) = c (ell (v - (b : ℤ))) (((v - (b : ℤ) : ℤ) : ZMod n))) : ell (v - (a : ℤ)) ≠ ell (v - (b : ℤ)) := by intro he have ha0 : ((v-(a : ℤ) : ℤ) : ZMod n)+(a : ZMod n) = (v : ZMod n) := by push_cast; ring have hb0 : ((v-(b : ℤ) : ℤ) : ZMod n)+(b : ZMod n) = (v : ZMod n) := by push_cast; ring rw [ha0] at hxa rw [hb0, ← he] at hxb have hpa := (hellroot (v-(a : ℤ))).symm have hpb := (hellroot (v-(b : ℤ))).symm rw [← he] at hpb have hroot := simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique m n hn (c (ell (v-(a : ℤ)))) (hc (ell (v-(a : ℤ)))) ((v-(a : ℤ) : ℤ) : ZMod n) ((v-(b : ℤ) : ℤ) : ZMod n) hpa hpb (hxa.symm.trans hxb) simp only [Int.cast_sub, Int.cast_natCast] at hroot have hcast : (a : ZMod n) = (b : ZMod n) := sub_right_inj.mp hroot have hnat : a=b := Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp hcast) (by omega) (by omega) exact hab hnat