AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_adj_iff_of_bandwidth_lt

theoremverified

When k<n, two vertices of the k-th cycle power are adjacent exactly when their difference has a nonzero signed integer representative of absolute value at most k.

Statement

theorem simple_graph_cycle_power_adj_iff_of_bandwidth_lt (n k : ℕ) [NeZero n] (hn : k < n) (u v : ZMod n) :
    (simple_graph_cycle_power n k).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ k ∧ v = u + e
Source
Uniform graph-to-class-model bridge for OP-205 / RT-1, arXiv:2610.15635. Generalizes the fixed-bandwidth integer-lifting helpers used for radii four and eight. This is geometric bookkeeping, not a research advance.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 7

The proof, explained

The theorem shows that for $k < n$, two vertices $u, v \in \mathbb{Z}/n\mathbb{Z}$ are adjacent in the $k$-th cycle power graph if and only if $v = u + e$ for some nonzero integer $e$ with $|e| \le k$. In the forward direction, adjacency means $u \ne v$ and $\min((u - v)\text{.val}, (v - u)\text{.val}) \le k$; taking $e = -((u - v)\text{.val})$ or $e = (v - u)\text{.val}$ gives the required witness. In the backward direction, the condition $|e| \le k < n$ guarantees that $u \ne u + e$ by injectivity of the quotient map on small intervals, and a case split on the sign of $e$ bounds the modular distance by $|e| \le k$.

  1. Assuming $u$ and $v$ are adjacent in the cycle power graph, we have $u \ne v$ and either $(u - v)\text{.val} \le k$ or $(v - u)\text{.val} \le k$.

    We split the iff goal into both directions. In the forward direction, adjacency in the cycle power graph means $u \ne v$ and $\min((u - v)\text{.val}, (v - u)\text{.val}) \le k$. Applying `min_le_iff.mp` decomposes the minimum inequality into two cases: $(u - v)\text{.val} \le k$ or $(v - u)\text{.val} \le k$.

    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)\text{.val} \le k$, the signed integer $e = -((u - v)\text{.val})$ satisfies $e \ne 0$, $|e| \le k$, and $v = u + e$.

    We provide $e = -((u - v)\text{.val} : \mathbb{Z})$ as the witness. If $e = 0$, then $(u - v)\text{.val} = 0$, which implies $u = v$ by `ZMod.val_eq_zero` and `sub_eq_zero`, contradicting $u \ne v$. The absolute value bound $|e| \le k$ follows from the case assumption using `abs_neg` and `Nat.abs_cast`. In $\mathbb{Z}/n\mathbb{Z}$, casting $e$ and applying `ZMod.natCast_zmod_val` gives $u + e = u - (u - v) = v$.

    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)\text{.val} \le k$, the signed integer $e = (v - u)\text{.val}$ satisfies $e \ne 0$, $|e| \le k$, and $v = u + e$.

    We provide $e = ((v - u)\text{.val} : \mathbb{Z})$ as the witness. If $e = 0$, then $(v - u)\text{.val} = 0$, giving $v = u$ by `ZMod.val_eq_zero` and `sub_eq_zero`, which contradicts $u \ne v$. The absolute value $|(v - u)\text{.val}| = (v - u)\text{.val} \le k$ follows by `Nat.abs_cast` from the case hypothesis. Finally, $u + e = u + (v - u) = v$ in $\mathbb{Z}/n\mathbb{Z}$ by `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, given $e \ne 0$ with $|e| \le k$ and $v = u + e$, the vertices $u$ and $v$ are distinct.

    Assume for contradiction that $u = u + e$. Subtracting $u$ yields $(e : \mathbb{Z}/n\mathbb{Z}) = 0$. Since $|e - 0| = |e| \le k < n$, `zmod_intCast_eq_intCast_iff_of_abs_sub_lt` shows that the integer cast modulo $n$ is injective, implying $e = 0$ in $\mathbb{Z}$. This contradicts the hypothesis $e \ne 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 $e \ge 0$, the cycle distance between $u$ and $u + e$ is at most $k$.

    Rewriting $|e| \le k$ with `abs_le` gives $-k \le e \le k$. We split into cases $0 \le e$ and $e < 0$ with `le_or_gt`. When $0 \le e$, using `add_sub_cancel_left` and `Int.toNat_of_nonneg` shows $(u + e - u) = (e\text{.toNat} : \mathbb{Z}/n\mathbb{Z})$. By `min_le_of_right_le`, it suffices to bound the second term of the minimum. Using `ZMod.val_natCast` and `Nat.mod_eq_of_lt` (since $e\text{.toNat} \le k < n$), its representative is $e\text{.toNat} \le k$.

    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 $e < 0$, the cycle distance between $u$ and $u + e$ is at most $k$.

    When $e < 0$, we have $-e > 0$, and `Int.toNat_of_nonneg` gives $((-e)\text{.toNat} : \mathbb{Z}) = -e$. Using `sub_add_cancel_left` and `Int.cast_natCast`, we rewrite $u - (u + e) = ((-e)\text{.toNat} : \mathbb{Z}/n\mathbb{Z})$. By `min_le_of_left_le`, it suffices to bound this first term of the minimum. By `ZMod.val_natCast` and `Nat.mod_eq_of_lt` (since $(-e)\text{.toNat} \le k < n$), its value is $(-e)\text{.toNat} \le k$.

    lines 36–41

    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
If the minimum of two values is at most $a$, then at least one of them is at most $a$.
ZMod.val_eq_zero
An element of $\mathbb{Z}/n\mathbb{Z}$ has numerical representative $0$ if and only if it is the zero element.
sub_eq_zero
The difference $a - b$ is zero 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\text{.val} \in \mathbb{N}$ back to $\mathbb{Z}/n\mathbb{Z}$ recovers $a$.
zmod_intCast_eq_intCast_iff_of_abs_sub_lt
Two integers whose difference has absolute value less than $n$ are congruent modulo $n$ if and only if they are equal.
abs_le
The absolute value $|a|$ is at most $b$ if and only if $-b \le a \le b$.
le_or_gt
In a linear order, either $a \le b$ or $b < a$.
add_sub_cancel_left
Adding $a$ and $b$ and then subtracting $a$ leaves $b$.
Int.toNat_of_nonneg
For a nonnegative integer $a$, 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 in $\mathbb{Z}/n\mathbb{Z}$ of a natural number $a$ is $a \pmod n$.
Nat.mod_eq_of_lt
If $a < b$, then $a \pmod b = a$.
sub_add_cancel_left
Subtracting $a + b$ from $a$ leaves $-b$.
Int.cast_natCast
Casting a natural number to an integer and then to 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_adj_iff_of_bandwidth_lt (n k : ℕ) [NeZero n] (hn : k < n) (u v : ZMod n) :    (simple_graph_cycle_power n k).Adj u v ↔ ∃ e : ℤ, e ≠ 0 ∧ |e| ≤ k ∧ 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