simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique
In 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.
Statement
theorem simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique
(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)
(p q : ZMod n)
(hp : c p = c (p + ((2 ^ m - 1 : ℕ) : ZMod n)))
(hq : c q = c (q + ((2 ^ m - 1 : ℕ) : ZMod n)))
(hpq : c p = c q) : p = q- Source
- step towards simple_graph_cycle_power_dyadic_cover_class_model
- Verified
- 04 Nov 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 5
- 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…
- 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_class_model_disjoint_coloursTwo active rooted classes at a common vertex with distinct offsets have distinct layer colours.
The proof, explained
In a clique labeling of the cycle power C_n^k with k = 2^m - 1 and n ≥ 3k + 1, any clique containing a pair at distance k is shown to have at most one such pair. By a known rooted-arc lemma, any clique containing {p, p + k} is entirely confined to the forward arc [p, p + k]. Consequently, if another pair {q, q + k} shares the same clique, both vertices must lie on this arc, giving q = p + a and q + k = p + b with 0 ≤ a, b ≤ k. Cancelling p yields a + k ≡ b (mod n), which lifts to an equality a + k = b in ℕ because 2k < n. Since b ≤ k, this forces a = 0 and thus p = q.
Both q and q + (2^m - 1) lie on the forward arc of length 2^m - 1 starting at p.
Because c(p) = c(p + (2^m - 1)) and n ≥ 3(2^m - 1) + 1, the lemma simple_graph_cycle_power_rooted_clique_arc ensures that any vertex in the clique of p has the form p + x for some natural number x ≤ 2^m - 1. Since c(q) = c(p) and c(q + (2^m - 1)) = c(q) = c(p), this yields natural numbers a, b ≤ 2^m - 1 such that q = p + a and q + (2^m - 1) = p + b in ℤ/nℤ.
uses
simple_graph_cycle_power_rooted_clique_archave harc := simple_graph_cycle_power_rooted_clique_arc n (2^m-1) hn c hc p hp obtain ⟨a, ha, hqa⟩ := harc q hpq.symm obtain ⟨b, hb, hqb⟩ := harc (q+((2^m-1 : ℕ) : ZMod n)) (hq.symm.trans hpq.symm)
In ℤ/nℤ, the residue of a + (2^m - 1) equals the residue of b.
Expanding p + (a + (2^m - 1)) in ℤ/nℤ gives (p + a) + (2^m - 1) = q + (2^m - 1) = p + b. Cancelling p from the left using add_left_cancel yields the equality a + (2^m - 1) = b in ℤ/nℤ.
uses
add_left_cancelhave he : ((a+(2^m-1) : ℕ) : ZMod n) = (b : ZMod n) := by apply add_left_cancel (a := p) calc p+((a+(2^m-1) : ℕ) : ZMod n) = (p+(a : ZMod n))+((2^m-1 : ℕ) : ZMod n) := by push_cast; ring _ = q+((2^m-1 : ℕ) : ZMod n) := by rw [← hqa] _ = p+(b : ZMod n) := hqb
The equality a + (2^m - 1) = b holds in the natural numbers ℕ.
By ZMod.natCast_eq_natCast_iff, equality in ℤ/nℤ means a + (2^m - 1) ≡ b (mod n). Since a, b ≤ 2^m - 1 and n ≥ 3(2^m - 1) + 1, both a + (2^m - 1) ≤ 2(2^m - 1) < n and b < n are strictly less than n. By Nat.ModEq.eq_of_lt_of_lt, two natural numbers strictly less than n that are congruent modulo n must be equal in ℕ.
uses
Nat.ModEq.eq_of_lt_of_lt,ZMod.natCast_eq_natCast_iffhave hen : a+(2^m-1)=b := Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp he) (by omega) (by omega)
a = 0. automation
Since a + (2^m - 1) = b and b ≤ 2^m - 1 for natural numbers a and b, linear arithmetic forces a ≤ 0, so a = 0. This deduction is closed by omega.
have ha0 : a=0 := by omega
p = q.
Substituting a = 0 into q = p + a simplifies via Nat.cast_zero and add_zero to q = p, which symmetrically gives p = q.
uses
Nat.cast_zero,add_zerohave : q=p := by simpa only [ha0, Nat.cast_zero, add_zero] using hqa exact this.symm
simple_graph_cycle_power_rooted_clique_arc- In a clique coloring of the cycle power C_n^k with n ≥ 3k + 1, if c(p) = c(p + k), then every vertex u in the same clique (c(u) = c(p)) lies on the forward arc from p, meaning u = p + a for some natural number a ≤ k.
add_left_cancel- In an algebraic structure with left-cancellative addition, a + b = a + c implies b = c.
Nat.ModEq.eq_of_lt_of_lt- If two natural numbers a and b are congruent modulo m, and both are strictly less than m, then a = b.
ZMod.natCast_eq_natCast_iff- The natural casts of a and b into ℤ/cℤ are equal if and only if a ≡ b (mod c).
Nat.cast_zero- The cast of the natural number 0 into an additive monoid with one equals 0.
add_zero- Adding zero on the right leaves an element unchanged: a + 0 = a.
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 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. -/theorem simple_graph_cycle_power_dyadic_cover_fibre_endpoint_unique (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) (p q : ZMod n) (hp : c p = c (p + ((2 ^ m - 1 : ℕ) : ZMod n))) (hq : c q = c (q + ((2 ^ m - 1 : ℕ) : ZMod n))) (hpq : c p = c q) : p = q := by have harc := simple_graph_cycle_power_rooted_clique_arc n (2^m-1) hn c hc p hp obtain ⟨a, ha, hqa⟩ := harc q hpq.symm obtain ⟨b, hb, hqb⟩ := harc (q+((2^m-1 : ℕ) : ZMod n)) (hq.symm.trans hpq.symm) have he : ((a+(2^m-1) : ℕ) : ZMod n) = (b : ZMod n) := by apply add_left_cancel (a := p) calc p+((a+(2^m-1) : ℕ) : ZMod n) = (p+(a : ZMod n))+((2^m-1 : ℕ) : ZMod n) := by push_cast; ring _ = q+((2^m-1 : ℕ) : ZMod n) := by rw [← hqa] _ = p+(b : ZMod n) := hqb have hen : a+(2^m-1)=b := Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff _ _ n).mp he) (by omega) (by omega) have ha0 : a=0 := by omega have : q=p := by simpa only [ha0, Nat.cast_zero, add_zero] using hqa exact this.symm