simple_graph_cycle_power_three_adj_iff
For n ≥ 10, u and v are adjacent in C_n^3 iff v = u + e for an integer e with 0 < |e| ≤ 3.
Statement
theorem simple_graph_cycle_power_three_adj_iff (n : ℕ) [NeZero n] (hn : 10 ≤ n) (u v : ZMod n) :
(simple_graph_cycle_power n 3).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ 3 ∧ v = u + e- Source
- Helper for simple_graph_cycle_power_three_cover_three_tight_dvd (thread RT-1, the k = 3 case of OP-205, arXiv:2610.15635).
- Verified
- 17 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 5
- simple_graph_cycle_power_three_layer_weight_eq_impIn the situation of the weight inequality, if Σ_i (2·[c i = c(i+3)] + [c i = c(i+2)]) = n then every class contains a pair at distance 3…
- simple_graph_cycle_power_three_cover_three_tightIf three equivalence subgraphs (labellings c_0, c_1, c_2 with clique classes) cover C_n^3, n ≥ 10, then every pair at distance 3 and every…
- simple_graph_cycle_power_three_layer_weight_leLet n ≥ 10 and let c label the vertices of C_n^3 so that every label class is a clique. Then Σ_i (2·[i and i+3 share a class] + [i and i+2…
- simple_graph_has_equivalence_cover_cycle_power_three_of_mod_four_eq_twoFor every n ≥ 10 with n ≡ 2 (mod 4), the cube C_n^3 of the n-cycle is covered by 4 equivalence subgraphs: on 0..n−1, layer 0 has the…
- simple_graph_cycle_power_three_cover_three_tight_dvdIf three labellings with clique classes satisfy the tight structure (each distance-3 pair and each distance-2 pair in exactly one layer,…
The proof, explained
The theorem characterizes adjacency in the cycle power graph $C_n^3$ for $n \ge 10$: vertices $u, v \in \mathbb{Z}/n\mathbb{Z}$ are adjacent if and only if $v = u + e$ for some integer $0 < |e| \le 3$. In the forward direction, adjacency provides that $u \ne v$ and the cyclic distance $\min((u-v).\mathrm{val}, (v-u).\mathrm{val})$ is at most $3$, so choosing $e$ as $-(u-v).\mathrm{val}$ or $(v-u).\mathrm{val}$ yields the required non-zero integer offset. In the backward direction, the assumption $0 < |e| \le 3 < 10 \le n$ prevents $e$ from wrapping to $0 \pmod n$, ensuring $u \ne v$, while the cyclic distance evaluates directly to $|e| \le 3$ by analyzing the sign of $e$.
In the forward direction, assume $u$ and $v$ are adjacent in $C_n^3$, which means $u \ne v$ and either $(u - v).\mathrm{val} \le 3$ or $(v - u).\mathrm{val} \le 3$.
The equivalence is split into two directions. In the forward direction, the definition of adjacency gives $u \ne v$ and $\min((u - v).\mathrm{val}, (v - u).\mathrm{val}) \le 3$. Applying `min_le_iff.mp` decomposes the minimum inequality into two cases: $(u - v).\mathrm{val} \le 3$ or $(v - u).\mathrm{val} \le 3$.
uses
min_le_iff.mpconstructor · rintro ⟨huv, hmin⟩ rcases min_le_iff.mp hmin with h | h
When $(u - v).\mathrm{val} \le 3$, the offset $e = -((u - v).\mathrm{val} : \mathbb{Z})$ satisfies $e \ne 0$, $|e| \le 3$, and $v = u + e$.
We set $e = -(u - v).\mathrm{val}$. If $e = 0$, then $(u - v).\mathrm{val} = 0$, which by `ZMod.val_eq_zero` and `sub_eq_zero` implies $u = v$, contradicting $u \ne v$. Its absolute value is $|e| = |-((u-v).\mathrm{val})| = (u-v).\mathrm{val} \le 3$ using `abs_neg` and `Nat.abs_cast`. Finally, in $\mathbb{Z}/n\mathbb{Z}$, $u + e = u - (u - v) = v$ using `ZMod.natCast_zmod_val` and ring arithmetic.
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).\mathrm{val} \le 3$, the offset $e = ((v - u).\mathrm{val} : \mathbb{Z})$ satisfies $e \ne 0$, $|e| \le 3$, and $v = u + e$.
We set $e = (v - u).\mathrm{val}$. If $e = 0$, then $(v - u).\mathrm{val} = 0$, so $v = u$ by `ZMod.val_eq_zero` and `sub_eq_zero`, contradicting $u \ne v$. Its absolute value is $|(v-u).\mathrm{val}| = (v-u).\mathrm{val} \le 3$ by `Nat.abs_cast`. Lastly, $u + e = u + (v - u) = v$ in $\mathbb{Z}/n\mathbb{Z}$ by `ZMod.natCast_zmod_val` and ring arithmetic.
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 backward direction, given $v = u + e$ with $e \ne 0$ and $|e| \le 3$, the vertices $u$ and $v$ are distinct.
Assume $v = u + e$ with $e \ne 0$ and $|e| \le 3$. To establish adjacency, we first show $u \ne u + e$. If $u = u + e$, subtracting $u$ implies $e = 0$ in $\mathbb{Z}/n\mathbb{Z}$. Since $|e - 0| = |e| \le 3 < 10 \le n$, `zmod_intCast_eq_intCast_iff_of_abs_sub_lt` shows that $e = 0$ as integers, contradicting $e \ne 0$.
uses
zmod_intCast_eq_intCast_iff_of_abs_sub_lt· rintro ⟨e, he0, he3, 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'
To bound the cyclic distance, unpack $-3 \le e \le 3$ and divide into cases $0 \le e$ and $e < 0$.
Rewriting $|e| \le 3$ with `abs_le` yields $-3 \le e \le 3$. Applying `le_or_gt` divides the remaining goal into two subcases depending on the sign of $e$: $0 \le e$ and $e < 0$.
uses
abs_le,le_or_gt· rw [abs_le] at he3 rcases le_or_gt 0 e with he | he
When $0 \le e$, the cyclic distance between $u$ and $u + e$ is at most 3.
Because $e \ge 0$, the forward difference $(u + e) - u$ simplifies to $e$ using `add_sub_cancel_left` and `Int.toNat_of_nonneg`. To show $\min((u - (u+e)).\mathrm{val}, ((u+e) - u).\mathrm{val}) \le 3$, `min_le_of_right_le` reduces the goal to bounding $((u+e) - u).\mathrm{val}$. In $\mathbb{Z}/n\mathbb{Z}$, this representative is $e.\mathrm{toNat} \bmod n$ by `ZMod.val_natCast`, which equals $e.\mathrm{toNat}$ via `Nat.mod_eq_of_lt` since $e \le 3 < 10 \le n$. Linear arithmetic confirms $e.\mathrm{toNat} \le 3$.
uses
add_sub_cancel_left,Int.toNat_of_nonneg,min_le_of_right_le,ZMod.val_natCast,Nat.mod_eq_of_lt· 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 cyclic distance between $u$ and $u + e$ is at most 3.
Because $e < 0$, the reverse difference $u - (u + e)$ equals $-e$ by `sub_add_cancel_left`, `Int.toNat_of_nonneg`, and `Int.cast_natCast`. Applying `min_le_of_left_le` reduces the goal to bounding $(u - (u+e)).\mathrm{val}$. This canonical representative is $(-e).\mathrm{toNat} \bmod n$ by `ZMod.val_natCast`, which equals $(-e).\mathrm{toNat}$ via `Nat.mod_eq_of_lt` since $-e \le 3 < 10 \le n$. Linear arithmetic concludes $(-e).\mathrm{toNat} \le 3$.
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- The minimum of two values is at most a bound if at least one of the values is at most that bound.
ZMod.val_eq_zero- The canonical representative of an element of $\mathbb{Z}/n\mathbb{Z}$ in $\mathbb{N}$ is 0 if and only if the element 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 equals the number itself.
ZMod.natCast_zmod_val- Casting the canonical representative `a.val` back into $\mathbb{Z}/n\mathbb{Z}$ recovers the original element $a$.
zmod_intCast_eq_intCast_iff_of_abs_sub_lt- Two integers whose difference has absolute value strictly less than $n$ are equal modulo $n$ if and only if they are equal as integers.
abs_le- $|a| \le b$ is equivalent to $-b \le a \le b$.
le_or_gt- In a linear order, any two elements satisfy $a \le b$ or $b < a$.
add_sub_cancel_left- In an additive group, $(a + b) - a = b$.
Int.toNat_of_nonneg- For a non-negative integer $a$, casting its conversion to $\mathbb{N}$ back to $\mathbb{Z}$ 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 $a$ in $\mathbb{Z}/n\mathbb{Z}$ is $a \bmod 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 into 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 proof explicitly splits the backward direction into cases $e \ge 0$ and $e < 0$ in order to bridge between signed integer offsets $\mathbb{Z}$ and the non-negative canonical representatives in $\mathbb{Z}/n\mathbb{Z}$ via `Int.toNat`, allowing modular reduction lemmas for $\mathbb{N}$ to apply.
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_three_adj_iff (n : ℕ) [NeZero n] (hn : 10 ≤ n) (u v : ZMod n) : (simple_graph_cycle_power n 3).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ 3 ∧ 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, he3, 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 he3 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