simple_graph_cycle_power_clique_arc
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
- 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_adj_iff_of_bandwidth_ltWhen k<n, two vertices of the k-th cycle power are adjacent exactly when their difference has a nonzero signed integer representative of…
- zmod_intCast_eq_intCast_iff_of_abs_sub_ltTwo integers a, b with |a − b| < n are equal modulo n only if they are equal.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 7
- 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_rooted_clique_arcLet 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…
- simple_graph_cycle_power_dyadic_layer_weight_leIn any clique labelling of a cycle power with dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, the total layer…
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
- 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,…
- simple_graph_cycle_power_dyadic_cover_class_spanningEvery label class of an optimal m+1-layer cover at dyadic bandwidth is spanned by an endpoint-distance pair: each vertex lies in a class…
- simple_graph_cycle_power_dyadic_class_model_tight_weightsEvery rooted dyadic class of an optimal cover is tight: the dyadic class weight of the arc equals its cardinality.
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.
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.
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)
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.
uses
mem_filter,mem_Icchave 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⟩
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.
uses
simple_graph_cycle_power_adj_iff_of_bandwidth_lt,Ne.symm,abs_le.mp,mem_filter,mem_Icchave 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⟩
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.
uses
abs_cases,zmod_intCast_eq_intCast_iff_of_abs_sub_lt,add_left_cancelhave 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)
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.
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_commhave 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
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.
uses
min'_memobtain ⟨z, hz, _⟩ := hsurj m hm have hS : S.Nonempty := ⟨z, hz⟩ let lo := S.min' hS have hlo : lo ∈ S := min'_mem S hS
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.
uses
min'_le,abs_of_nonneg,Int.toNat_of_nonneg,Int.cast_natCastrefine ⟨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 ℕ.
- Because vertices are elements of ZMod n, the proof lifts vertices to integer offsets in [-k, k] relative to an arbitrary base vertex m. The condition 3k + 1 ≤ n ensures that differences between offsets stay strictly below n in absolute value, preventing distinct offsets from collapsing modulo n.
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 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