simple_graph_cycle_power_fifteen_adj_iff
For n at least 46, adjacency in the fifteenth power of the cycle is displacement by a nonzero integer of absolute value at most 15.
Statement
theorem simple_graph_cycle_power_fifteen_adj_iff (n : ℕ) [NeZero n] (hn : 46 ≤ n) (u v : ZMod n) :
(simple_graph_cycle_power n 15).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ 15 ∧ v = u + e- Source
- Next k = 15 step of research thread RT-1 toward OP-205, arXiv:2610.15635; experiments 3978 and 3983.
- Verified
- 24 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.
The proof, explained
The equivalence between adjacency in the 15th power of $C_n$ and displacement by an integer $e \ne 0$ with $|e| \le 15$ is proved by directly matching the cyclic distance $\min((u-v).\mathrm{val}, (v-u).\mathrm{val}) \le 15$. In the forward direction, one chooses either $e = -(u-v).\mathrm{val}$ or $e = (v-u).\mathrm{val}$ depending on which directional difference is at most 15, and $u \ne v$ guarantees $e \ne 0$. In the reverse direction, the condition $n \ge 46 > 2 \cdot 15$ ensures that no non-zero displacement $|e| \le 15$ can wrap around to 0 modulo $n$, preventing loops and ensuring the forward or backward modular distance is at most 15.
The equivalence splits into two directions; in the forward direction, adjacency implies $u \ne v$ and that either $(u - v).\mathrm{val} \le 15$ or $(v - u).\mathrm{val} \le 15$.
Line 3 splits the if-and-only-if into forward and reverse implications. Line 4 unpacks the definition of adjacency in the 15th cycle power, giving $u \ne v$ and $\min((u - v).\mathrm{val}, (v - u).\mathrm{val}) \le 15$. Line 5 applies `min_le_iff.mp` to separate into the two cases where either directional difference is bounded by 15.
uses
min_le_iff.mpconstructor · rintro ⟨huv, hmin⟩ rcases min_le_iff.mp hmin with h | h
If $(u - v).\mathrm{val} \le 15$, the integer $e = -(u - v).\mathrm{val}$ satisfies $e \ne 0$, $|e| \le 15$, and $v = u + e$.
Line 6 sets the integer displacement witness to $e = -(u - v).\mathrm{val}$. Lines 7–10 show $e \ne 0$: if $-(u - v).\mathrm{val} = 0$, then $(u - v).\mathrm{val} = 0$, which by `ZMod.val_eq_zero` and `sub_eq_zero` means $u = v$, contradicting $u \ne v$. Line 11 uses `abs_neg` and `Nat.abs_cast` to show $|e| = (u - v).\mathrm{val} \le 15$. Line 12 confirms $u + e = u - (u - v) = v$ in $\mathbb{Z}/n\mathbb{Z}$ using `ZMod.natCast_zmod_val`.
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
If $(v - u).\mathrm{val} \le 15$, the integer $e = (v - u).\mathrm{val}$ satisfies $e \ne 0$, $|e| \le 15$, and $v = u + e$.
Line 13 sets the witness to $e = (v - u).\mathrm{val}$. Lines 14–17 establish $e \ne 0$, since $(v - u).\mathrm{val} = 0$ would force $v = u$ by `ZMod.val_eq_zero` and `sub_eq_zero`. Line 18 checks $|e| \le 15$ using `Nat.abs_cast`. Line 19 verifies $u + e = u + (v - u) = v$ in $\mathbb{Z}/n\mathbb{Z}$ via `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, assuming $e \ne 0$, $|e| \le 15$, and $v = u + e$, the vertices $u$ and $v$ are distinct.
Line 20 introduces the assumed displacement $e$ and sets $v = u + e$. Line 21 splits the goal into non-identity ($u \ne u + e$) and distance bound. To prove $u \ne u + e$, lines 22–24 assume $u = u + e$, which simplifies to $e \equiv 0 \pmod n$. Since $|e - 0| = |e| \le 15 < 46 \le n$, the lemma `zmod_intCast_eq_intCast_iff_of_abs_sub_lt` implies $e = 0$, contradicting $e \ne 0$ (lines 25–26).
uses
zmod_intCast_eq_intCast_iff_of_abs_sub_lt· rintro ⟨e, he0, he15, 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 $0 \le e \le 15$, the cyclic distance $\min((u - (u+e)).\mathrm{val}, (u+e - u).\mathrm{val})$ is at most 15.
Line 27 rewrites $|e| \le 15$ as $-15 \le e \le 15$, and line 28 splits into cases $0 \le e$ and $e < 0$. For $0 \le e$, lines 29–31 simplify $(u + e) - u$ to $e.\mathrm{toNat}$ in $\mathbb{Z}/n\mathbb{Z}$ using `add_sub_cancel_left` and `Int.toNat_of_nonneg`. Line 32 applies `min_le_of_right_le` to bound the minimum by $(u + e - u).\mathrm{val}$. Lines 33–34 evaluate this representative to $e.\mathrm{toNat} \bmod n = e.\mathrm{toNat} \le 15$ using `ZMod.val_natCast` and `Nat.mod_eq_of_lt`, since $e.\mathrm{toNat} < 46 \le n$.
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 he15 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 $-15 \le e < 0$, the cyclic distance $\min((u - (u+e)).\mathrm{val}, (u+e - u).\mathrm{val})$ is at most 15.
For $e < 0$, lines 35–37 show $u - (u + e) = -e = (-e).\mathrm{toNat}$ in $\mathbb{Z}/n\mathbb{Z}$ using `Int.toNat_of_nonneg`, `sub_add_cancel_left`, and `Int.cast_natCast`. Line 38 applies `min_le_of_left_le` to bound the minimum by $(u - (u + e)).\mathrm{val}$. Lines 39–40 compute this representative as $(-e).\mathrm{toNat} \bmod n = (-e).\mathrm{toNat} \le 15$ using `ZMod.val_natCast` and `Nat.mod_eq_of_lt` because $-e \le 15 < n$.
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- a minimum is at most $c$ if and only if at least one of its arguments is at most $c$
ZMod.val_eq_zero- the canonical representative in $\{0, \ldots, n-1\}$ of an element of $\mathbb{Z}/n\mathbb{Z}$ is $0$ if and only if the element itself is $0$
sub_eq_zero- in an additive group, $a - b = 0$ 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.\mathrm{val} \in \mathbb{N}$ back to $\mathbb{Z}/n\mathbb{Z}$ yields $a$
zmod_intCast_eq_intCast_iff_of_abs_sub_lt- for integers $a$ and $b$ whose difference satisfies $|a - b| < n$, their residue classes modulo $n$ are equal if and only if $a = b$
abs_le- $|a| \le b$ if and only if $-b \le a \le b$
le_or_gt- in any linear order, either $a \le b$ or $b < a$
add_sub_cancel_left- in an additive group, $(a + b) - a = b$
Int.toNat_of_nonneg- for an integer $a \ge 0$, 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 of a natural number modulo $n$ is its remainder upon division by $n$
Nat.mod_eq_of_lt- if $a < b$, then $a \bmod b = a$
sub_add_cancel_left- in an additive group, $a - (a + b) = -b$
Int.cast_natCast- casting a natural number to an integer and then to another ring is identical to casting directly
min_le_of_left_le- if $b \le a$, then $\min(b, c) \le a$
- Linear integer arithmetic (`omega`) is used repeatedly to establish that small differences do not wrap around modulo $n$ (such as $|e| < n$ from $|e| \le 15$ and $46 \le 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.
theorem simple_graph_cycle_power_fifteen_adj_iff (n : ℕ) [NeZero n] (hn : 46 ≤ n) (u v : ZMod n) : (simple_graph_cycle_power n 15).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ 15 ∧ 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, he15, 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 he15 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