AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_three_adj_iff

theoremverified

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

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

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

    lines 3–5

    uses min_le_iff.mp

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

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

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

    lines 20–26

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

    lines 27–28

    uses abs_le, le_or_gt

        · rw [abs_le] at he3
          rcases le_or_gt 0 e with he | he
  6. 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$.

    lines 29–34

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

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

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