simple_graph_cycle_power_adj_iff_val_lt
For a nonzero natural n, natural k, and vertices u,v of ZMod n with u.val less than v.val, adjacency in the k-th cycle power is equivalent to either v.val-u.val at most k or n-(v.val-u.val) at most k.
Statement
theorem simple_graph_cycle_power_adj_iff_val_lt
(n k : ℕ) [NeZero n] (u v : ZMod n) (huv : u.val < v.val) :
(simple_graph_cycle_power n k).Adj u v ↔
v.val-u.val ≤ k ∨ n-(v.val-u.val) ≤ k- Source
- arXiv:2610.15635, Proposition 3.2, with induced floor embedding from Lemma 3.1 and cover restriction from Lemma 2.1. This formalizes the published upper bound serving OP-205 / RT-1; no new research result is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 1
- cycle_power_floor_map_inducedFor natural n,N,k,K with n positive, N at least n, k*N at most K*n, and (K+1)*n at most (k+1)*N, the balanced floor map from ZMod n to…
The proof, explained
By definition, two vertices u and v are adjacent in the k-th cycle power of C_n if they are distinct and min((u - v).val, (v - u).val) ≤ k. Under the assumption u.val < v.val, the vertices are necessarily distinct, the clockwise distance (v - u).val is v.val - u.val, and the counterclockwise distance (u - v).val is n - (v.val - u.val). Expanding the minimum inequality into a disjunction then yields the desired equivalence.
u ≠ v
Assuming u = v would imply u.val = v.val by applying ZMod.val via congrArg, which directly contradicts the hypothesis u.val < v.val.
uses
congrArghave hne : u ≠ v := by intro h; have := congrArg ZMod.val h; omega
(v - u).val = v.val - u.val
Since u.val ≤ v.val follows from u.val < v.val, the integer representative in ℤ/nℤ of the difference v - u is simply the difference of their natural representatives, by ZMod.val_sub.
uses
ZMod.val_subhave hdiff : (v-u).val = v.val-u.val := ZMod.val_sub huv.lev - u ≠ 0
If v - u were zero, then v = u by sub_eq_zero.mp, contradicting the previously established u ≠ v.
uses
sub_eq_zero.mphave hdiffnz : v-u ≠ 0 := by intro h; exact hne (sub_eq_zero.mp h).symm
(u - v).val = n - (v - u).val
Rewriting u - v as -(v - u) using neg_sub, and using the fact that v - u ≠ 0, the representative of the negation of a nonzero element in ℤ/nℤ is n minus its representative, by ZMod.val_neg_of_ne_zero.
uses
neg_sub,ZMod.val_neg_of_ne_zerohave hneg : (u-v).val = n-(v-u).val := by rw [← neg_sub v u] letI : NeZero (v-u) := ⟨hdiffnz⟩ exact ZMod.val_neg_of_ne_zero (v-u)
The adjacency condition (simple_graph_cycle_power n k).Adj u v is equivalent to u ≠ v ∧ (n - (v.val - u.val) ≤ k ∨ v.val - u.val ≤ k).
By definition, adjacency in the k-th cycle power means u ≠ v and min (u - v).val (v - u).val ≤ k. Substituting (u - v).val = n - (v - u).val and (v - u).val = v.val - u.val, and rewriting the minimum inequality as a disjunction using min_le_iff, transforms the adjacency condition into u ≠ v ∧ (n - (v.val - u.val) ≤ k ∨ v.val - u.val ≤ k).
uses
min_le_iffchange (u ≠ v ∧ min (u-v).val (v-u).val ≤ k) ↔ _ rw [hneg, hdiff, min_le_iff]
(simple_graph_cycle_power n k).Adj u v ↔ v.val - u.val ≤ k ∨ n - (v.val - u.val) ≤ k
For the forward implication, the conjunct u ≠ v is discarded and the disjunction is commuted. For the reverse implication, the disjunction provides the second conjunct (after commuting), and the first conjunct u ≠ v holds from our earlier deduction.
constructor · intro h exact h.2.symm · intro h exact ⟨hne, h.symm⟩
congrArg- If a₁ = a₂, then f(a₁) = f(a₂) for any function f.
ZMod.val_sub- For elements a and b in ℤ/nℤ with b.val ≤ a.val, the representative of their difference is (a - b).val = a.val - b.val.
sub_eq_zero.mp- If a - b = 0 in a group, then a = b.
neg_sub- In any subtraction monoid, -(a - b) = b - a.
ZMod.val_neg_of_ne_zero- For any nonzero element a in ℤ/nℤ (with n ≠ 0), the representative of its negation is (-a).val = n - a.val.
min_le_iff- In a linear order, min b c ≤ a if and only if b ≤ a or c ≤ 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 4000theorem simple_graph_cycle_power_adj_iff_val_lt (n k : ℕ) [NeZero n] (u v : ZMod n) (huv : u.val < v.val) : (simple_graph_cycle_power n k).Adj u v ↔ v.val-u.val ≤ k ∨ n-(v.val-u.val) ≤ k := by have hne : u ≠ v := by intro h; have := congrArg ZMod.val h; omega have hdiff : (v-u).val = v.val-u.val := ZMod.val_sub huv.le have hdiffnz : v-u ≠ 0 := by intro h; exact hne (sub_eq_zero.mp h).symm have hneg : (u-v).val = n-(v-u).val := by rw [← neg_sub v u] letI : NeZero (v-u) := ⟨hdiffnz⟩ exact ZMod.val_neg_of_ne_zero (v-u) change (u ≠ v ∧ min (u-v).val (v-u).val ≤ k) ↔ _ rw [hneg, hdiff, min_le_iff] constructor · intro h exact h.2.symm · intro h exact ⟨hne, h.symm⟩