AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_clique_arc

theoremverified

For n at least 3k+1, every nonempty clique of the k-th cycle power lies in a forward arc of k+1 vertices whose first vertex belongs to the clique.

Statement

theorem simple_graph_cycle_power_clique_arc
    (n k : ℕ) [NeZero n] (hn : 3 * k + 1 ≤ n)
    (K : Finset (ZMod n)) (hK : K.Nonempty)
    (hc : ∀ u ∈ K, ∀ v ∈ K, u ≠ v → (simple_graph_cycle_power n k).Adj u v) :
    ∃ p ∈ K, ∀ u ∈ K, ∃ a : ℕ, a ≤ k ∧ u = p + (a : ZMod n)
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 5
Used by 7

The proof, explained

Fix an arbitrary vertex m in the clique K and represent each vertex of K by its signed offset e ∈ [-k, k] from m along the cycle. Since K is a clique and 3k + 1 ≤ n, every vertex in K has a unique such offset, and the difference between any two offsets has absolute value at most k. Choosing p = m + min(S) to be the vertex corresponding to the minimum offset, every other vertex in K lies at a forward distance a ≤ k along the cycle from p.

  1. Choose a base vertex m ∈ K, observe k < n, and define the set of offsets S ⊆ [-k, k] representing vertices of K relative to m.

    Since K is nonempty, we fix an arbitrary element m ∈ K. The inequality 3k + 1 ≤ n implies k < n and the same bound over the integers. We define S as the finite set of integers e ∈ [-k, k] such that m + e ∈ K.

    lines 8–11

      obtain ⟨m, hm⟩ := hK
      have hkn : k < n := by omega
      have hnZ : 3 * (k : ℤ) + 1 ≤ (n : ℤ) := by exact_mod_cast hn
      let S : Finset ℤ := (Icc (-(k : ℤ)) (k : ℤ)).filter (fun e => m + (e : ZMod n) ∈ K)
  2. Every offset e ∈ S satisfies -k ≤ e ≤ k and m + e ∈ K.

    By definition of S as a filtered sub-interval of integers, any element e ∈ S belongs to [-k, k] and satisfies the condition m + e ∈ K.

    lines 12–15

    uses mem_filter, mem_Icc

      have hmem : ∀ e ∈ S, -(k : ℤ) ≤ e ∧ e ≤ k ∧ m + (e : ZMod n) ∈ K := by
        intro e he
        obtain ⟨he, hu⟩ := mem_filter.mp he
        exact ⟨(mem_Icc.mp he).1, (mem_Icc.mp he).2, hu⟩
  3. Every vertex u ∈ K can be represented as m + e for some offset e ∈ S.

    If u = m, we choose e = 0, which is in [-k, k] and satisfies m + 0 = m ∈ K, so 0 ∈ S. If u ≠ m, then because K is a clique, m and u are adjacent in the k-th cycle power. Since k < n, adjacency means u = m + e for some non-zero integer e with |e| ≤ k. Thus -k ≤ e ≤ k and m + e = u ∈ K, so e ∈ S.

    lines 16–28

    uses simple_graph_cycle_power_adj_iff_of_bandwidth_lt, Ne.symm, abs_le.mp, mem_filter, mem_Icc

      have hsurj : ∀ u ∈ K, ∃ e ∈ S, m + (e : ZMod n) = u := by
        intro u hu
        by_cases hum : u = m
        · subst u
          refine ⟨0, ?_, by simp⟩
          simp only [S, mem_filter, mem_Icc]
          exact ⟨⟨by omega, by omega⟩, by simpa using hm⟩
        · obtain ⟨e, _, he, heq⟩ :=
            (simple_graph_cycle_power_adj_iff_of_bandwidth_lt n k hkn m u).mp
              (hc m hm u hu (Ne.symm hum))
          refine ⟨e, ?_, heq.symm⟩
          simp only [S, mem_filter, mem_Icc]
          exact ⟨abs_le.mp he, by simpa only [← heq] using hu⟩
  4. The representation map e ↦ m + e from S to K is injective.

    Suppose m + a = m + b in ZMod n for a, b ∈ S. Canceling m gives a = b modulo n. Since a, b ∈ [-k, k], their difference satisfies |a - b| ≤ 2k < 3k + 1 ≤ n. Because |a - b| < n, equality in ZMod n forces equality in ℤ, so a = b.

    lines 29–36

    uses abs_cases, zmod_intCast_eq_intCast_iff_of_abs_sub_lt, add_left_cancel

      have hinj : ∀ a ∈ S, ∀ b ∈ S,
          m + (a : ZMod n) = m + (b : ZMod n) → a = b := by
        intro a ha b hb heq
        have ha' := hmem a ha
        have hb' := hmem b hb
        have hab : |a - b| < (n : ℤ) := by
          rcases abs_cases (a - b) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega
        exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b hab).mp (add_left_cancel heq)
  5. The diameter of S in ℤ is at most k: for all a, b ∈ S, |a - b| ≤ k.

    If a = b, the difference is 0 ≤ k. If a ≠ b, injectivity implies m + a ≠ m + b. Since both vertices belong to the clique K, they are adjacent in the k-th cycle power, so m + b = (m + a) + e for some integer e with |e| ≤ k. In ZMod n, this gives b - a = e. Since a, b ∈ [-k, k] and |e| ≤ k, the triangle inequality gives |(b - a) - e| ≤ 2k + k = 3k < n. By the injectivity lemma modulo n, equality holds in ℤ, so b - a = e. Taking absolute values gives |a - b| = |e| ≤ k.

    lines 37–57

    uses simple_graph_cycle_power_adj_iff_of_bandwidth_lt, abs_le.mp, abs_cases, zmod_intCast_eq_intCast_iff_of_abs_sub_lt, abs_sub_comm

      have hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ (k : ℤ) := by
        intro a ha b hb
        have ha' := hmem a ha
        have hb' := hmem b hb
        by_cases hab : a = b
        · subst b
          simp
        have hne : m + (a : ZMod n) ≠ m + (b : ZMod n) := fun h => hab (hinj a ha b hb h)
        obtain ⟨e, _, he, heq⟩ :=
          (simple_graph_cycle_power_adj_iff_of_bandwidth_lt n k hkn _ _).mp
            (hc _ ha'.2.2 _ hb'.2.2 hne)
        have he' := abs_le.mp he
        have heqmod : ((b - a : ℤ) : ZMod n) = (e : ZMod n) := by
          push_cast
          calc (b : ZMod n) - a = (m + b) - (m + a) := by ring
               _ = e := by rw [heq]; ring
        have hsmall : |(b - a) - e| < (n : ℤ) := by
          rcases abs_cases ((b - a) - e) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega
        have hei := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (b - a) e hsmall).mp heqmod
        rw [← hei] at he
        simpa only [abs_sub_comm] using he
  6. The offset set S is nonempty and has a well-defined minimum element lo ∈ S.

    Since m ∈ K, surjectivity gives an offset z ∈ S such that m + z = m, showing S is nonempty. We let lo be the minimum element of S, which belongs to S.

    lines 58–61

    uses min'_mem

      obtain ⟨z, hz, _⟩ := hsurj m hm
      have hS : S.Nonempty := ⟨z, hz⟩
      let lo := S.min' hS
      have hlo : lo ∈ S := min'_mem S hS
  7. With p = m + lo ∈ K, every vertex u ∈ K has the form p + a for some natural number a ≤ k.

    Since lo ∈ S, the vertex p = m + lo belongs to K. For any u ∈ K, surjectivity provides e ∈ S with u = m + e. Because lo is the minimum of S, we have lo ≤ e, so e - lo ≥ 0. By the diameter bound, e - lo = |e - lo| ≤ k. Setting a = e - lo as a natural number, we have a ≤ k and p + a = (m + lo) + (e - lo) = m + e = u in ZMod n.

    lines 62–75

    uses min'_le, abs_of_nonneg, Int.toNat_of_nonneg, Int.cast_natCast

      refine ⟨m + (lo : ZMod n), (hmem lo hlo).2.2, ?_⟩
      intro u hu
      obtain ⟨e, he, heq⟩ := hsurj u hu
      have hle : lo ≤ e := min'_le S e he
      have hbound : e - lo ≤ (k : ℤ) := by
        have hh := hdiam e he lo hlo
        rw [abs_of_nonneg (by omega)] at hh
        exact hh
      refine ⟨(e - lo).toNat, ?_, ?_⟩
      · omega
      · have ht : (((e - lo).toNat : ℕ) : ℤ) = e - lo := Int.toNat_of_nonneg (by omega)
        rw [← heq, ← Int.cast_natCast, ht]
        push_cast
        ring
mem_filter
An element belongs to Finset.filter p s if and only if it belongs to s and satisfies the predicate p.
mem_Icc
An element belongs to the closed interval Finset.Icc a b if and only if it lies between a and b inclusive.
simple_graph_cycle_power_adj_iff_of_bandwidth_lt
In the cycle power graph on ZMod n with k < n, two vertices u and v are adjacent if and only if v = u + e for some non-zero integer e with |e| ≤ k.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
abs_le.mp
If |x| ≤ y, then -y ≤ x and x ≤ y.
abs_cases
For any element a in an ordered group, either |a| = a with 0 ≤ a, or |a| = -a with a < 0.
zmod_intCast_eq_intCast_iff_of_abs_sub_lt
For integers a and b with |a - b| < n, their residue classes modulo n are equal if and only if a = b in ℤ.
add_left_cancel
In an additive group or cancellative structure, a + b = a + c implies b = c.
abs_sub_comm
The absolute value of a difference is symmetric: |a - b| = |b - a|.
min'_mem
The minimum element min'(s) of a nonempty finite set s belongs to s.
min'_le
The minimum element min'(s) of a finite set s is less than or equal to every element in s.
abs_of_nonneg
If 0 ≤ a, then |a| = a.
Int.toNat_of_nonneg
For any integer a ≥ 0, converting a to ℕ and casting back to ℤ yields a.
Int.cast_natCast
Casting a natural number to ℤ and then into a ring is equivalent to casting directly from ℕ.

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

open Finsettheorem simple_graph_cycle_power_clique_arc    (n k : ℕ) [NeZero n] (hn : 3 * k + 1 ≤ n)    (K : Finset (ZMod n)) (hK : K.Nonempty)    (hc : ∀ u ∈ K, ∀ v ∈ K, u ≠ v → (simple_graph_cycle_power n k).Adj u v) :    ∃ p ∈ K, ∀ u ∈ K, ∃ a : ℕ, a ≤ k ∧ u = p + (a : ZMod n) := by  obtain ⟨m, hm⟩ := hK  have hkn : k < n := by omega  have hnZ : 3 * (k : ℤ) + 1 ≤ (n : ℤ) := by exact_mod_cast hn  let S : Finset ℤ := (Icc (-(k : ℤ)) (k : ℤ)).filter (fun e => m + (e : ZMod n) ∈ K)  have hmem : ∀ e ∈ S, -(k : ℤ) ≤ e ∧ e ≤ k ∧ m + (e : ZMod n) ∈ K := by    intro e he    obtain ⟨he, hu⟩ := mem_filter.mp he    exact ⟨(mem_Icc.mp he).1, (mem_Icc.mp he).2, hu⟩  have hsurj : ∀ u ∈ K, ∃ e ∈ S, m + (e : ZMod n) = u := by    intro u hu    by_cases hum : u = m    · subst u      refine ⟨0, ?_, by simp⟩      simp only [S, mem_filter, mem_Icc]      exact ⟨⟨by omega, by omega⟩, by simpa using hm⟩    · obtain ⟨e, _, he, heq⟩ :=        (simple_graph_cycle_power_adj_iff_of_bandwidth_lt n k hkn m u).mp          (hc m hm u hu (Ne.symm hum))      refine ⟨e, ?_, heq.symm⟩      simp only [S, mem_filter, mem_Icc]      exact ⟨abs_le.mp he, by simpa only [← heq] using hu⟩  have hinj : ∀ a ∈ S, ∀ b ∈ S,      m + (a : ZMod n) = m + (b : ZMod n) → a = b := by    intro a ha b hb heq    have ha' := hmem a ha    have hb' := hmem b hb    have hab : |a - b| < (n : ℤ) := by      rcases abs_cases (a - b) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega    exact (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n a b hab).mp (add_left_cancel heq)  have hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ (k : ℤ) := by    intro a ha b hb    have ha' := hmem a ha    have hb' := hmem b hb    by_cases hab : a = b    · subst b      simp    have hne : m + (a : ZMod n) ≠ m + (b : ZMod n) := fun h => hab (hinj a ha b hb h)    obtain ⟨e, _, he, heq⟩ :=      (simple_graph_cycle_power_adj_iff_of_bandwidth_lt n k hkn _ _).mp        (hc _ ha'.2.2 _ hb'.2.2 hne)    have he' := abs_le.mp he    have heqmod : ((b - a : ℤ) : ZMod n) = (e : ZMod n) := by      push_cast      calc (b : ZMod n) - a = (m + b) - (m + a) := by ring           _ = e := by rw [heq]; ring    have hsmall : |(b - a) - e| < (n : ℤ) := by      rcases abs_cases ((b - a) - e) with ⟨h1, h2⟩ | ⟨h1, h2⟩ <;> omega    have hei := (zmod_intCast_eq_intCast_iff_of_abs_sub_lt n (b - a) e hsmall).mp heqmod    rw [← hei] at he    simpa only [abs_sub_comm] using he  obtain ⟨z, hz, _⟩ := hsurj m hm  have hS : S.Nonempty := ⟨z, hz⟩  let lo := S.min' hS  have hlo : lo ∈ S := min'_mem S hS  refine ⟨m + (lo : ZMod n), (hmem lo hlo).2.2, ?_⟩  intro u hu  obtain ⟨e, he, heq⟩ := hsurj u hu  have hle : lo ≤ e := min'_le S e he  have hbound : e - lo ≤ (k : ℤ) := by    have hh := hdiam e he lo hlo    rw [abs_of_nonneg (by omega)] at hh    exact hh  refine ⟨(e - lo).toNat, ?_, ?_⟩  · omega  · have ht : (((e - lo).toNat : ℕ) : ℤ) = e - lo := Int.toNat_of_nonneg (by omega)    rw [← heq, ← Int.cast_natCast, ht]    push_cast    ring
See it in the graphDiscuss this resultChallenge it