simple_graph_cycle_power_adj_iff_of_bandwidth_lt
When k<n, two vertices of the k-th cycle power are adjacent exactly when their difference has a nonzero signed integer representative of absolute value at most k.
Statement
theorem simple_graph_cycle_power_adj_iff_of_bandwidth_lt (n k : ℕ) [NeZero n] (hn : k < n) (u v : ZMod n) :
(simple_graph_cycle_power n k).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ k ∧ v = u + e- Source
- Uniform graph-to-class-model bridge for OP-205 / RT-1, arXiv:2610.15635. Generalizes the fixed-bandwidth integer-lifting helpers used for radii four and eight. This is geometric bookkeeping, not a research advance.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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.
- Used by 7
- 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…
- 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_cover_card_boundFor dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, every equivalence cover of the cycle power uses at least m+1…
- cycle_strong_product_not_has_equivalence_cover_threeFor every m ≥ 6 and n ≥ 5, the strong product of cycles C_m and C_n (simple_graph_strong_prod of simple_graph_cycle_power m 1 and…
- 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…
- simple_graph_cycle_power_dyadic_cover_tight_long_edgesIn an m+1-layer equivalence cover at dyadic bandwidth, every endpoint-distance edge and every other positively weighted dyadic long edge…
- 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 theorem shows that for $k < n$, two vertices $u, v \in \mathbb{Z}/n\mathbb{Z}$ are adjacent in the $k$-th cycle power graph if and only if $v = u + e$ for some nonzero integer $e$ with $|e| \le k$. In the forward direction, adjacency means $u \ne v$ and $\min((u - v)\text{.val}, (v - u)\text{.val}) \le k$; taking $e = -((u - v)\text{.val})$ or $e = (v - u)\text{.val}$ gives the required witness. In the backward direction, the condition $|e| \le k < n$ guarantees that $u \ne u + e$ by injectivity of the quotient map on small intervals, and a case split on the sign of $e$ bounds the modular distance by $|e| \le k$.
Assuming $u$ and $v$ are adjacent in the cycle power graph, we have $u \ne v$ and either $(u - v)\text{.val} \le k$ or $(v - u)\text{.val} \le k$.
We split the iff goal into both directions. In the forward direction, adjacency in the cycle power graph means $u \ne v$ and $\min((u - v)\text{.val}, (v - u)\text{.val}) \le k$. Applying `min_le_iff.mp` decomposes the minimum inequality into two cases: $(u - v)\text{.val} \le k$ or $(v - u)\text{.val} \le k$.
uses
min_le_iff.mpconstructor · rintro ⟨huv, hmin⟩ rcases min_le_iff.mp hmin with h | h
When $(u - v)\text{.val} \le k$, the signed integer $e = -((u - v)\text{.val})$ satisfies $e \ne 0$, $|e| \le k$, and $v = u + e$.
We provide $e = -((u - v)\text{.val} : \mathbb{Z})$ as the witness. If $e = 0$, then $(u - v)\text{.val} = 0$, which implies $u = v$ by `ZMod.val_eq_zero` and `sub_eq_zero`, contradicting $u \ne v$. The absolute value bound $|e| \le k$ follows from the case assumption using `abs_neg` and `Nat.abs_cast`. In $\mathbb{Z}/n\mathbb{Z}$, casting $e$ and applying `ZMod.natCast_zmod_val` gives $u + e = u - (u - v) = v$.
uses
ZMod.val_eq_zero,sub_eq_zero,abs_neg,Nat.abs_cast,ZMod.natCast_zmod_val· refine ⟨-((u - v).val : ℤ), ?_, ?_, ?_⟩ · intro h0 have : (u - v).val = 0 := by omega rw [ZMod.val_eq_zero, sub_eq_zero] at this exact huv this · rw [abs_neg, Nat.abs_cast]; exact_mod_cast h · push_cast; rw [ZMod.natCast_zmod_val]; ring
When $(v - u)\text{.val} \le k$, the signed integer $e = (v - u)\text{.val}$ satisfies $e \ne 0$, $|e| \le k$, and $v = u + e$.
We provide $e = ((v - u)\text{.val} : \mathbb{Z})$ as the witness. If $e = 0$, then $(v - u)\text{.val} = 0$, giving $v = u$ by `ZMod.val_eq_zero` and `sub_eq_zero`, which contradicts $u \ne v$. The absolute value $|(v - u)\text{.val}| = (v - u)\text{.val} \le k$ follows by `Nat.abs_cast` from the case hypothesis. Finally, $u + e = u + (v - u) = v$ in $\mathbb{Z}/n\mathbb{Z}$ by `ZMod.natCast_zmod_val`.
uses
ZMod.val_eq_zero,sub_eq_zero,Nat.abs_cast,ZMod.natCast_zmod_val· refine ⟨((v - u).val : ℤ), ?_, ?_, ?_⟩ · intro h0 have : (v - u).val = 0 := by omega rw [ZMod.val_eq_zero, sub_eq_zero] at this exact huv this.symm · rw [Nat.abs_cast]; exact_mod_cast h · push_cast; rw [ZMod.natCast_zmod_val]; ring
In the reverse direction, given $e \ne 0$ with $|e| \le k$ and $v = u + e$, the vertices $u$ and $v$ are distinct.
Assume for contradiction that $u = u + e$. Subtracting $u$ yields $(e : \mathbb{Z}/n\mathbb{Z}) = 0$. Since $|e - 0| = |e| \le k < n$, `zmod_intCast_eq_intCast_iff_of_abs_sub_lt` shows that the integer cast modulo $n$ is injective, implying $e = 0$ in $\mathbb{Z}$. This contradicts the hypothesis $e \ne 0$.
uses
zmod_intCast_eq_intCast_iff_of_abs_sub_lt· rintro ⟨e, he0, he7, rfl⟩ refine ⟨fun h => he0 ?_, ?_⟩ · have h' : ((e : ℤ) : ZMod n) = ((0 : ℤ) : ZMod n) := by have : (u + e) - u = u - u := by rw [← h] simpa using this rw [zmod_intCast_eq_intCast_iff_of_abs_sub_lt n e 0 (by simp; omega)] at h' exact h'
When $e \ge 0$, the cycle distance between $u$ and $u + e$ is at most $k$.
Rewriting $|e| \le k$ with `abs_le` gives $-k \le e \le k$. We split into cases $0 \le e$ and $e < 0$ with `le_or_gt`. When $0 \le e$, using `add_sub_cancel_left` and `Int.toNat_of_nonneg` shows $(u + e - u) = (e\text{.toNat} : \mathbb{Z}/n\mathbb{Z})$. By `min_le_of_right_le`, it suffices to bound the second term of the minimum. Using `ZMod.val_natCast` and `Nat.mod_eq_of_lt` (since $e\text{.toNat} \le k < n$), its representative is $e\text{.toNat} \le k$.
uses
abs_le,le_or_gt,add_sub_cancel_left,Int.toNat_of_nonneg,min_le_of_right_le,ZMod.val_natCast,Nat.mod_eq_of_lt· rw [abs_le] at he7 rcases le_or_gt 0 e with he | he · have hv : (u + (e : ZMod n) - u) = ((e.toNat : ℕ) : ZMod n) := by simp only [add_sub_cancel_left] rw [← Int.toNat_of_nonneg he]; simp apply min_le_of_right_le rw [hv, ZMod.val_natCast, Nat.mod_eq_of_lt (by omega)] omega
When $e < 0$, the cycle distance between $u$ and $u + e$ is at most $k$.
When $e < 0$, we have $-e > 0$, and `Int.toNat_of_nonneg` gives $((-e)\text{.toNat} : \mathbb{Z}) = -e$. Using `sub_add_cancel_left` and `Int.cast_natCast`, we rewrite $u - (u + e) = ((-e)\text{.toNat} : \mathbb{Z}/n\mathbb{Z})$. By `min_le_of_left_le`, it suffices to bound this first term of the minimum. By `ZMod.val_natCast` and `Nat.mod_eq_of_lt` (since $(-e)\text{.toNat} \le k < n$), its value is $(-e)\text{.toNat} \le k$.
uses
Int.toNat_of_nonneg,sub_add_cancel_left,Int.cast_natCast,min_le_of_left_le,ZMod.val_natCast,Nat.mod_eq_of_lt· have hv : (u - (u + (e : ZMod n))) = (((-e).toNat : ℕ) : ZMod n) := by have h' : ((-e).toNat : ℤ) = -e := Int.toNat_of_nonneg (by omega) rw [sub_add_cancel_left, ← Int.cast_natCast, h']; push_cast; ring apply min_le_of_left_le rw [hv, ZMod.val_natCast, Nat.mod_eq_of_lt (by omega)] omega
min_le_iff.mp- If the minimum of two values is at most $a$, then at least one of them is at most $a$.
ZMod.val_eq_zero- An element of $\mathbb{Z}/n\mathbb{Z}$ has numerical representative $0$ if and only if it is the zero element.
sub_eq_zero- The difference $a - b$ is zero if and only if $a = b$.
abs_neg- The absolute value of $-a$ equals the absolute value of $a$.
Nat.abs_cast- The absolute value of a natural number cast into an ordered ring is itself.
ZMod.natCast_zmod_val- Casting the canonical representative $a\text{.val} \in \mathbb{N}$ back to $\mathbb{Z}/n\mathbb{Z}$ recovers $a$.
zmod_intCast_eq_intCast_iff_of_abs_sub_lt- Two integers whose difference has absolute value less than $n$ are congruent modulo $n$ if and only if they are equal.
abs_le- The absolute value $|a|$ is at most $b$ if and only if $-b \le a \le b$.
le_or_gt- In a linear order, either $a \le b$ or $b < a$.
add_sub_cancel_left- Adding $a$ and $b$ and then subtracting $a$ leaves $b$.
Int.toNat_of_nonneg- For a nonnegative integer $a$, converting to a natural number and casting back yields $a$.
min_le_of_right_le- If $c \le a$, then $\min(b, c) \le a$.
ZMod.val_natCast- The canonical representative in $\mathbb{Z}/n\mathbb{Z}$ of a natural number $a$ is $a \pmod n$.
Nat.mod_eq_of_lt- If $a < b$, then $a \pmod b = a$.
sub_add_cancel_left- Subtracting $a + b$ from $a$ leaves $-b$.
Int.cast_natCast- Casting a natural number to an integer and then to another ring is the same as casting it directly.
min_le_of_left_le- If $b \le a$, then $\min(b, c) \le a$.
- The backward direction uses explicit coercions via `Int.toNat` to translate between the signed integer offset $e$ and natural-number representatives in $\mathbb{Z}/n\mathbb{Z}$ before applying modulo reduction.
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.
theorem simple_graph_cycle_power_adj_iff_of_bandwidth_lt (n k : ℕ) [NeZero n] (hn : k < n) (u v : ZMod n) : (simple_graph_cycle_power n k).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ k ∧ v = u + e := by constructor · rintro ⟨huv, hmin⟩ rcases min_le_iff.mp hmin with h | h · refine ⟨-((u - v).val : ℤ), ?_, ?_, ?_⟩ · intro h0 have : (u - v).val = 0 := by omega rw [ZMod.val_eq_zero, sub_eq_zero] at this exact huv this · rw [abs_neg, Nat.abs_cast]; exact_mod_cast h · push_cast; rw [ZMod.natCast_zmod_val]; ring · refine ⟨((v - u).val : ℤ), ?_, ?_, ?_⟩ · intro h0 have : (v - u).val = 0 := by omega rw [ZMod.val_eq_zero, sub_eq_zero] at this exact huv this.symm · rw [Nat.abs_cast]; exact_mod_cast h · push_cast; rw [ZMod.natCast_zmod_val]; ring · rintro ⟨e, he0, he7, rfl⟩ refine ⟨fun h => he0 ?_, ?_⟩ · have h' : ((e : ℤ) : ZMod n) = ((0 : ℤ) : ZMod n) := by have : (u + e) - u = u - u := by rw [← h] simpa using this rw [zmod_intCast_eq_intCast_iff_of_abs_sub_lt n e 0 (by simp; omega)] at h' exact h' · rw [abs_le] at he7 rcases le_or_gt 0 e with he | he · have hv : (u + (e : ZMod n) - u) = ((e.toNat : ℕ) : ZMod n) := by simp only [add_sub_cancel_left] rw [← Int.toNat_of_nonneg he]; simp apply min_le_of_right_le rw [hv, ZMod.val_natCast, Nat.mod_eq_of_lt (by omega)] omega · have hv : (u - (u + (e : ZMod n))) = (((-e).toNat : ℕ) : ZMod n) := by have h' : ((-e).toNat : ℤ) = -e := Int.toNat_of_nonneg (by omega) rw [sub_add_cancel_left, ← Int.cast_natCast, h']; push_cast; ring apply min_le_of_left_le rw [hv, ZMod.val_natCast, Nat.mod_eq_of_lt (by omega)] omega