AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_seven_adj_iff

theoremverified

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
Used by 7

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.

  1. 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.

    lines 3–5

    uses min_le_iff.mp

      constructor
      · rintro ⟨huv, hmin⟩
        rcases min_le_iff.mp hmin with h | h
  2. 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.

    lines 6–12

    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
  3. 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.

    lines 13–19

    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
  4. 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.

    lines 20–26

    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'
  5. 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.

    lines 27–34

    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
  6. 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.

    lines 35–40

    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.

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

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
See it in the graphDiscuss this resultChallenge it