simple_graph_cycle_power_dyadic_cover_layer_root_unique
In 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 the root spanning the class of v in layer s.
Statement
theorem simple_graph_cycle_power_dyadic_cover_layer_root_unique
(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)
(s : Fin (m + 1)) (v : ZMod n) :
∃! a : ℕ, a ≤ 2 ^ m - 1 ∧
c s (v - (a : ZMod n)) = c s v ∧
c s (v - (a : ZMod n)) =
c s (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : 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_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_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…
- 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 2
- 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…
The proof, explained
The proof establishes the unique existence of the root offset a ≤ 2^m - 1 spanning the layer-s color class of v. Existence is provided directly by `simple_graph_cycle_power_dyadic_cover_class_spanning`. For uniqueness, any other candidate offset b satisfies the same boundary conditions, so `simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique` forces the endpoints to coincide in ℤ/nℤ (v - b = v - a), which implies b ≡ a [MOD n]; since both a and b are bounded strictly below n, they must be equal in ℕ.
There exists an offset a ≤ 2^m - 1 spanning the layer-s class of v, reducing the goal to uniqueness.
By `simple_graph_cycle_power_dyadic_cover_class_spanning`, there exists an offset a ≤ 2^m - 1 such that v - a is monochromatic with v in layer s and spans an interval of length 2^m - 1 (that is, c_s(v - a) = c_s(v - a + 2^m - 1)). Providing this witness reduces the unique existence goal (∃!) to showing that any other offset b satisfying the same properties must equal a.
uses
simple_graph_cycle_power_dyadic_cover_class_spanningobtain ⟨a, ha⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning m n hm hn c hc hcov s v refine ⟨a, ha, ?_⟩
Any candidate offset b satisfies (b : ℤ/nℤ) = (a : ℤ/nℤ).
Let b be another offset satisfying b ≤ 2^m - 1, c_s(v - b) = c_s(v), and c_s(v - b) = c_s(v - b + 2^m - 1). By transitivity of equality, c_s(v - b) = c_s(v - a). Since both v - b and v - a are endpoints of monochromatic intervals of length 2^m - 1 in the same layer-s fiber, `simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique` applies to show v - b = v - a in ℤ/nℤ. Cancelling v from both sides via `sub_right_inj.mp` yields (b : ℤ/nℤ) = (a : ℤ/nℤ).
uses
simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique,sub_right_inj.mpintro b hb have he := simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique m n hn (c s) (hc s) (v-(b : ZMod n)) (v-(a : ZMod n)) hb.2.2 ha.2.2 (hb.2.1.trans ha.2.1.symm) have hecast : (b : ZMod n) = (a : ZMod n) := sub_right_inj.mp he
b = a as natural numbers.
The equality of the casts in ℤ/nℤ implies the modular congruence b ≡ a [MOD n] by `ZMod.natCast_eq_natCast_iff`. Since a, b ≤ 2^m - 1 and n ≥ 3*(2^m - 1) + 1 > 2^m - 1, both a and b are strictly less than n (verified by `omega`). By `Nat.ModEq.eq_of_lt_of_lt`, two natural numbers strictly less than n that are congruent modulo n are equal.
uses
Nat.ModEq.eq_of_lt_of_lt,ZMod.natCast_eq_natCast_iffexact Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp hecast) (by omega) (by omega)
simple_graph_cycle_power_dyadic_cover_class_spanning- In an optimal dyadic cover of C_n^{2^m-1}, for each layer s and vertex v, there exists an offset a ≤ 2^m - 1 such that v - a shares the layer-s color of v and spans a monochromatic interval of length 2^m - 1.
simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique- In a layer whose monochromatic pairs are graph edges, if two vertices in the same color class each equal their shift by 2^m - 1, then the two vertices must be identical.
sub_right_inj.mp- In an additive group, if x - y = x - z, then y = z.
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.
ZMod.natCast_eq_natCast_iff- The canonical casts of two natural numbers to ℤ/nℤ are equal if and only if the numbers are congruent modulo n.
- The transition from equality in ℤ/nℤ to equality in ℕ is handled formally by translating the equality of modular casts to a congruence modulo n (`ZMod.natCast_eq_natCast_iff`) and applying `Nat.ModEq.eq_of_lt_of_lt` together with linear arithmetic (`omega`) to verify that the offsets are strictly smaller than the cycle length 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/-- In 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 the root spanning the class of v in layer s. -/theorem simple_graph_cycle_power_dyadic_cover_layer_root_unique (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) (s : Fin (m + 1)) (v : ZMod n) : ∃! a : ℕ, a ≤ 2 ^ m - 1 ∧ c s (v - (a : ZMod n)) = c s v ∧ c s (v - (a : ZMod n)) = c s (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) := by obtain ⟨a, ha⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning m n hm hn c hc hcov s v refine ⟨a, ha, ?_⟩ intro b hb have he := simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique m n hn (c s) (hc s) (v-(b : ZMod n)) (v-(a : ZMod n)) hb.2.2 ha.2.2 (hb.2.1.trans ha.2.1.symm) have hecast : (b : ZMod n) = (a : ZMod n) := sub_right_inj.mp he exact Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp hecast) (by omega) (by omega)