simple_graph_cycle_power_seven_adj_iff
For n ≥ 22, u and v are adjacent in C_n^7 iff v = u + e for an integer e with 0 < |e| ≤ 7.
Statement
theorem simple_graph_cycle_power_seven_adj_iff (n : ℕ) [NeZero n] (hn : 22 ≤ n) (u v : ZMod n) :
(simple_graph_cycle_power n 7).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ 7 ∧ v = u + e- Source
- helper for the k = 7 case of OP-205 (arXiv:2610.15635), research thread RT-1, case k = 7 (k + 1 = 8); the analogue of simple_graph_cycle_power_three_adj_iff
- Verified
- 18 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_seven_cover_four_tight_alternateIn a tight cover of C_n^7 (n >= 22) by 4 equivalence subgraphs in which every class starting at i (the class of the distance-7 pair (i,…
- simple_graph_cycle_power_seven_cover_four_tight_one_iff_sixIn a tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- simple_graph_cycle_power_seven_layer_weight_leLet n ≥ 22 and let c label the vertices of C_n^7 so that every label class is a clique. Then Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~ i+4]) ≤…
- simple_graph_cycle_power_seven_cover_four_tight_dvdA tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- simple_graph_cycle_power_seven_cover_four_tightIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every pair at distance 7, 6 or 4 is covered by exactly one layer, and every…
- simple_graph_cycle_power_seven_layer_weight_eq_class_five_imp_one_two_imp_sixLet c label the vertices of C_n^7 (n ≥ 22) so that every label class is a clique, with total weight Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~…
- simple_graph_cycle_power_seven_cover_four_layer_weight_eqIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every layer has weight exactly n: the sum over i of 2·[i ~ i+7] + [i ~ i+6] +…
The proof, explained
Two vertices u and v in ℤ/nℤ are adjacent in the 7th power of C_n if and only if they differ by an integer offset e with 0 < |e| ≤ 7. For the forward direction, adjacency implies u ≠ v and that one of the directional distances (u - v).val or (v - u).val is at most 7, providing the desired non-zero witness ±(distance). For the reverse direction, the hypothesis n ≥ 22 guarantees that offsets bounded by 7 cannot wrap around to 0 modulo n, ensuring u ≠ u + e and that the cyclic distance is precisely |e| ≤ 7.
To prove the equivalence, split into two directions; for the forward direction, adjacency implies that either (u - v).val ≤ 7 or (v - u).val ≤ 7.
We split the if-and-only-if statement into two implications. In the forward direction, adjacency by definition means u ≠ v and min((u - v).val, (v - u).val) ≤ 7. By `min_le_iff.mp`, this minimum inequality splits into two cases: (u - v).val ≤ 7 or (v - u).val ≤ 7.
uses
min_le_iff.mpconstructor · rintro ⟨huv, hmin⟩ rcases min_le_iff.mp hmin with h | h
If (u - v).val ≤ 7, the integer witness e = -((u - v).val : ℤ) satisfies e ≠ 0, |e| ≤ 7, and v = u + e.
We choose e = -((u - v).val : ℤ). If e were 0, then (u - v).val = 0, which by `ZMod.val_eq_zero` and `sub_eq_zero` implies u = v, contradicting u ≠ v. The absolute value satisfies |-((u - v).val)| = (u - v).val ≤ 7 using `abs_neg` and `Nat.abs_cast`. Finally, casting to ℤ/nℤ, u + e = u - (u - v) = v by `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
If (v - u).val ≤ 7, the integer witness e = ((v - u).val : ℤ) satisfies e ≠ 0, |e| ≤ 7, and v = u + e.
We choose e = ((v - u).val : ℤ). If e were 0, then (v - u).val = 0, which implies v = u by `ZMod.val_eq_zero` and `sub_eq_zero`, contradicting u ≠ v. Its absolute value is |(v - u).val| = (v - u).val ≤ 7 by `Nat.abs_cast`. Finally, in ℤ/nℤ, u + e = u + (v - u) = v 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
For the reverse direction, assuming v = u + e with e ≠ 0 and |e| ≤ 7, the vertices u and v are distinct.
To show adjacency, we must first show u ≠ u + e. If u = u + e, subtracting u gives e = 0 in ℤ/nℤ. Since |e - 0| = |e| ≤ 7 < 22 ≤ n, the canonical projection ℤ → ℤ/nℤ is injective on this range by `zmod_intCast_eq_intCast_iff_of_abs_sub_lt`, forcing e = 0, which contradicts the hypothesis e ≠ 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 0 ≤ e ≤ 7, the cyclic distance between u and u + e is at most 7.
The bound |e| ≤ 7 is rewritten as -7 ≤ e ≤ 7 via `abs_le`. When 0 ≤ e (from `le_or_gt`), we have (u + e) - u = e = e.toNat in ℤ/nℤ by `add_sub_cancel_left` and `Int.toNat_of_nonneg`. To bound the minimum of the two directional distances, it suffices by `min_le_of_right_le` to bound the forward distance ((u + e) - u).val. Since e.toNat ≤ 7 < 22 ≤ n, `ZMod.val_natCast` and `Nat.mod_eq_of_lt` evaluate this representative to e.toNat, which is at most 7.
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 -7 ≤ e < 0, the cyclic distance between u and u + e is at most 7.
When e < 0, we have -e > 0, so (-e).toNat = -e by `Int.toNat_of_nonneg`. Thus u - (u + e) = -e = (-e).toNat in ℤ/nℤ by `sub_add_cancel_left` and `Int.cast_natCast`. By `min_le_of_left_le`, it suffices to bound the backward distance (u - (u + e)).val. Since (-e).toNat ≤ 7 < 22 ≤ n, `ZMod.val_natCast` and `Nat.mod_eq_of_lt` show that this representative is (-e).toNat, which is at most 7.
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- For any quantities a, b, c, min(a, b) ≤ c implies a ≤ c or b ≤ c.
ZMod.val_eq_zero- An element of ℤ/nℤ has canonical representative 0 in ℕ if and only if it is equal to 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 coerced to an ordered ring equals the number itself.
ZMod.natCast_zmod_val- Casting the canonical representative of a ∈ ℤ/nℤ back to ℤ/nℤ yields a.
zmod_intCast_eq_intCast_iff_of_abs_sub_lt- Two integers whose difference has absolute value strictly less than n are equal in ℤ/nℤ if and only if they are equal in ℤ.
abs_le- For an element a and bound b, |a| ≤ b if and only if -b ≤ a and a ≤ b.
le_or_gt- In a linear order, either a ≤ b or b < a.
add_sub_cancel_left- In an additive group, (a + b) - a = b.
Int.toNat_of_nonneg- If an integer a is non-negative, coercing its natural conversion a.toNat back to ℤ gives a.
min_le_of_right_le- If c ≤ a, then min(b, c) ≤ a.
ZMod.val_natCast- The canonical representative in ℤ/nℤ of a natural number a is a mod n.
Nat.mod_eq_of_lt- If natural numbers satisfy a < b, then a mod b = a.
sub_add_cancel_left- In an additive group, a - (a + b) = -b.
Int.cast_natCast- Casting a natural number to ℤ and then to a ring with one is the same as casting directly from ℕ.
min_le_of_left_le- If b ≤ a, then min(b, c) ≤ a.
- The hypothesis n ≥ 22 is used via linear arithmetic (`omega`) only to ensure 7 < n, which guarantees that integer differences bounded by 7 do not wrap around in ℤ/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_seven_adj_iff (n : ℕ) [NeZero n] (hn : 22 ≤ n) (u v : ZMod n) : (simple_graph_cycle_power n 7).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ 7 ∧ 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