simple_graph_cycle_power_rooted_clique_arc
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
- simple_graph_cycle_power_dyadic_cover_fibre_endpoint_uniqueIn any clique labeling of the cycle power C_n^{2^m-1} with n ≥ 3(2^m-1)+1, each clique contains at most one pair at distance 2^m-1.
- simple_graph_cycle_power_dyadic_cover_edge_spanIf a monochromatic clique contains v and v+d with 1 ≤ d < 2^m, its root v-a (with a ≤ 2^m-1) satisfies a < 2^m - d, so the entire edge {v,…
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.
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.
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)
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.
uses
simple_graph_cycle_power_clique_arcobtain ⟨r, hr, harc⟩ := simple_graph_cycle_power_clique_arc n k hn K hK hcliqueBoth 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.
obtain ⟨a, ha, hpa⟩ := harc p ((hmem p).mpr rfl) obtain ⟨b, hb, hpb⟩ := harc (p+(k : ZMod n)) ((hmem _).mpr hp.symm)
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ℤ).
uses
add_left_cancelhave 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
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.
uses
Nat.ModEq.eq_of_lt_of_lt,ZMod.natCast_eq_natCast_iff,Nat.cast_zero,add_zerohave 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
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩