AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_fifteen_adj_iff

theoremverified

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

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.

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

    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).\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`.

    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).\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`.

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

    lines 20–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'
  5. 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$.

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

    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
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$

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