AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_rooted_clique_arc

theoremverified

Let n,k be natural numbers with n nonzero and n at least3k+1. Let c label the vertices of the k-th cycle power so that two distinct equal-labelled vertices are adjacent. If p and p+k have equal labels, every vertex having the label of p equals p+a for a natural offset a at most k.

Statement

theorem simple_graph_cycle_power_rooted_clique_arc
    (n k : ℕ) [NeZero n] (hn : 3*k+1 ≤ n)
    (c : ZMod n → ZMod n)
    (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n k).Adj u v)
    (p : ZMod n) (hp : c p = c (p+(k : ZMod n))) :
    ∀ u, c u = c p → ∃ a : ℕ, a ≤ k ∧ u = p+(a : ZMod n)
Source
Uniform actual-cover extraction for OP-205 / RT-1 following arXiv:2610.15635. The anchored-arc lemma is geometric bookkeeping. The saturation helpers double-count exact dyadic owners and active classes over a period; they do not classify class shapes or settle the graph covering value. No research advance is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
  • simple_graph_cycle_power_clique_arcFor 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…
Used by 2

The proof, explained

To show that every vertex sharing the color of p is of the form p + a with a ≤ k, the proof first observes that the monochromatic set K of vertices with label c(p) forms a clique in the cycle power. By an existing theorem (simple_graph_cycle_power_clique_arc), K must lie on an arc of length k starting at some root r ∈ K. Since both p and p + k belong to K, they have offsets a, b ≤ k from r, satisfying r + a + k = r + b. Modulo n, this forces a + k = b in ℕ, which is only possible for a, b ≤ k if a = 0, identifying the root r as p itself and completing the claim.

  1. The fiber K = {u : ℤ/nℤ | c(u) = c(p)} is a nonempty clique in the k-th cycle power.

    The set K of vertices having the same label as p is nonempty because it contains p. For any two distinct vertices u, v ∈ K, we have c(u) = c(p) = c(v), so by the assumption hc, u and v are adjacent in the k-th cycle power.

    lines 11–17

      classical
      let K : Finset (ZMod n) := univ.filter (fun u => c u = c p)
      have hmem (u : ZMod n) : u ∈ K ↔ c u = c p := by simp [K]
      have hK : K.Nonempty := ⟨p, (hmem p).mpr rfl⟩
      have hclique : ∀ u ∈ K, ∀ v ∈ K, u ≠ v → (simple_graph_cycle_power n k).Adj u v := by
        intro u hu v hv hne
        exact hc u v hne (((hmem u).mp hu).trans ((hmem v).mp hv).symm)
  2. The clique K is contained in an arc of length at most k starting at some root vertex r ∈ K.

    By the clique-arc theorem simple_graph_cycle_power_clique_arc, which applies since n ≥ 3k + 1, any nonempty clique in the k-th power of an n-cycle is covered by a forward arc of length at most k starting at some root vertex r ∈ K.

    line 18

    uses simple_graph_cycle_power_clique_arc

      obtain ⟨r, hr, harc⟩ := simple_graph_cycle_power_clique_arc n k hn K hK hclique
  3. Both p and p + k lie on the arc rooted at r, with natural offsets a, b ≤ k.

    Since p ∈ K, there exists a ≤ k such that p = r + a. Furthermore, by hypothesis c(p) = c(p + k), so p + k ∈ K as well, which yields an offset b ≤ k such that p + k = r + b.

    lines 19–20

      obtain ⟨a, ha, hpa⟩ := harc p ((hmem p).mpr rfl)
      obtain ⟨b, hb, hpb⟩ := harc (p+(k : ZMod n)) ((hmem _).mpr hp.symm)
  4. The offset sum a + k equals b in ℤ/nℤ.

    Using the expressions for p and p + k, we have r + (a + k) = (r + a) + k = p + k = r + b in ℤ/nℤ. Cancelling the root r from both sides using add_left_cancel gives (a + k : ℤ/nℤ) = (b : ℤ/nℤ).

    lines 21–26

    uses add_left_cancel

      have he : ((a+k : ℕ) : ZMod n) = (b : ZMod n) := by
        apply add_left_cancel (a := r)
        calc
          r+((a+k : ℕ) : ZMod n) = (r+(a : ZMod n))+(k : ZMod n) := by push_cast; ring
          _ = p+(k : ZMod n) := by rw [← hpa]
          _ = r+(b : ZMod n) := hpb
  5. The offset a is zero, so the root r is p itself.

    By ZMod.natCast_eq_natCast_iff, the equality in ℤ/nℤ implies that a + k ≡ b (mod n). Since a ≤ k, we have a + k ≤ 2k < 3k + 1 ≤ n, and b ≤ k < n. Because both a + k and b are strictly less than n, Nat.ModEq.eq_of_lt_of_lt shows that a + k = b as natural numbers. Since b ≤ k, this equation forces a = 0. Substituting a = 0 into p = r + a gives p = r.

    lines 27–30

    uses Nat.ModEq.eq_of_lt_of_lt, ZMod.natCast_eq_natCast_iff, Nat.cast_zero, add_zero

      have hen : a+k=b := Nat.ModEq.eq_of_lt_of_lt
        ((ZMod.natCast_eq_natCast_iff (a+k) b n).mp he) (by omega) (by omega)
      have ha0 : a=0 := by omega
      have hpr : p=r := by simpa only [ha0, Nat.cast_zero, add_zero] using hpa
  6. Every vertex u with c(u) = c(p) is of the form p + i for some natural offset i ≤ k.

    For any u such that c(u) = c(p), u belongs to K. By the arc property, u = r + i for some offset i ≤ k. Because p = r, this rewrites directly to u = p + i.

    lines 31–33

      intro u hu
      obtain ⟨i, hi, hui⟩ := harc u ((hmem u).mpr hu)
      exact ⟨i, hi, by simpa only [hpr] using hui⟩
simple_graph_cycle_power_clique_arc
In the k-th power of an n-cycle with n ≥ 3k + 1, every nonempty clique is contained in an arc of length at most k; that is, there is a root vertex p in the clique such that every clique vertex is p + a for some natural offset a ≤ k.
add_left_cancel
In an additive structure with left cancellation, a + b = a + c implies b = c.
Nat.ModEq.eq_of_lt_of_lt
If two natural numbers are congruent modulo m and both are strictly less than m, they are equal.
ZMod.natCast_eq_natCast_iff
The natural number casts of two numbers into ℤ/cℤ are equal if and only if the numbers are congruent modulo c.
Nat.cast_zero
The cast of 0 from ℕ into any additive monoid with one is 0.
add_zero
Adding 0 on the right preserves the element (a + 0 = 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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_cycle_power_rooted_clique_arc    (n k : ℕ) [NeZero n] (hn : 3*k+1 ≤ n)    (c : ZMod n → ZMod n)    (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n k).Adj u v)    (p : ZMod n) (hp : c p = c (p+(k : ZMod n))) :    ∀ u, c u = c p → ∃ a : ℕ, a ≤ k ∧ u = p+(a : ZMod n) := by  classical  let K : Finset (ZMod n) := univ.filter (fun u => c u = c p)  have hmem (u : ZMod n) : u ∈ K ↔ c u = c p := by simp [K]  have hK : K.Nonempty := ⟨p, (hmem p).mpr rfl⟩  have hclique : ∀ u ∈ K, ∀ v ∈ K, u ≠ v → (simple_graph_cycle_power n k).Adj u v := by    intro u hu v hv hne    exact hc u v hne (((hmem u).mp hu).trans ((hmem v).mp hv).symm)  obtain ⟨r, hr, harc⟩ := simple_graph_cycle_power_clique_arc n k hn K hK hclique  obtain ⟨a, ha, hpa⟩ := harc p ((hmem p).mpr rfl)  obtain ⟨b, hb, hpb⟩ := harc (p+(k : ZMod n)) ((hmem _).mpr hp.symm)  have he : ((a+k : ℕ) : ZMod n) = (b : ZMod n) := by    apply add_left_cancel (a := r)    calc      r+((a+k : ℕ) : ZMod n) = (r+(a : ZMod n))+(k : ZMod n) := by push_cast; ring      _ = p+(k : ZMod n) := by rw [← hpa]      _ = r+(b : ZMod n) := hpb  have hen : a+k=b := Nat.ModEq.eq_of_lt_of_lt    ((ZMod.natCast_eq_natCast_iff (a+k) b n).mp he) (by omega) (by omega)  have ha0 : a=0 := by omega  have hpr : p=r := by simpa only [ha0, Nat.cast_zero, add_zero] using hpa  intro u hu  obtain ⟨i, hi, hui⟩ := harc u ((hmem u).mpr hu)  exact ⟨i, hi, by simpa only [hpr] using hui⟩
See it in the graphDiscuss this resultChallenge it