simple_graph_cycle_power_three_cover_three_tight
If three equivalence subgraphs (labellings c_0, c_1, c_2 with clique classes) cover C_n^3, n ≥ 10, then every pair at distance 3 and every pair at distance 2 lies in exactly one of them, and in every layer every class contains a pair at distance 3 spanning it.
Statement
theorem simple_graph_cycle_power_three_cover_three_tight (n : ℕ) [NeZero n] (hn : 10 ≤ n)
(c : Fin 3 → ZMod n → ZMod n)
(hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n 3).Adj u v)
(hcov : ∀ u v, (simple_graph_cycle_power n 3).Adj u v → ∃ s, c s u = c s v) :
(∀ i, ∃! s, c s i = c s (i + 3)) ∧ (∀ i, ∃! s, c s i = c s (i + 2)) ∧
∀ s i, ∃ d : ℕ, d ≤ 3 ∧ c s (i - d) = c s (i - d + 3) ∧ c s (i - d) = c s i- Source
- Step toward simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvd (the k = 3 case of OP-205, arXiv:2610.15635): the double-counting proof found in thread RT-1.
- Verified
- 17 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_three_layer_weight_leLet n ≥ 10 and let c label the vertices of C_n^3 so that every label class is a clique. Then Σ_i (2·[i and i+3 share a class] + [i and i+2…
- simple_graph_cycle_power_three_layer_weight_eq_impIn the situation of the weight inequality, if Σ_i (2·[c i = c(i+3)] + [c i = c(i+2)]) = n then every class contains a pair at distance 3…
- simple_graph_cycle_power_three_adj_iffFor n ≥ 10, u and v are adjacent in C_n^3 iff v = u + e for an integer e with 0 < |e| ≤ 3.
- Used by 1
- simple_graph_not_has_equivalence_cover_cycle_power_three_of_not_dvdFor every n ≥ 10 not divisible by 4, the cube C_n^3 of the n-cycle cannot be covered by 3 equivalence subgraphs; with the lower bound eq ≥…
The proof, explained
The theorem is proved by a double-counting argument on the total coverage weight of edges at distances 2 and 3 in the cycle graph power C_n^3. Each layer s has an internal weight W(s) = ∑_i (2 * [c s i = c s (i+3)] + [c s i = c s (i+2)]) ≤ n, bounding the total weight of the three layers by 3n. Conversely, because every distance-3 and distance-2 edge must be covered by at least one layer, each vertex contributes at least 2(1) + 1 = 3 across the three layers, forcing the total weight to be at least 3n. Equality must therefore hold everywhere: every distance-3 and distance-2 pair is covered by exactly one layer, and each layer achieves maximal weight W(s) = n, which by a structural classification lemma implies that every vertex lies in a clique spanned by a distance-3 chord.
Every pair of vertices at distance 3 and distance 2 forms an edge in C_n^3 and is covered by at least one layer.
For each vertex i ∈ ℤ/nℤ, the difference to i + 3 (respectively i + 2) is a non-zero offset with absolute value ≤ 3 (since n ≥ 10). By simple_graph_cycle_power_three_adj_iff, the pairs {i, i + 3} and {i, i + 2} are edges of C_n^3. Because the three layers cover all edges of C_n^3 (hypothesis hcov), each such pair must be assigned the same label in at least one layer s ∈ Fin 3, yielding witnesses hcov3 and hcov2.
uses
simple_graph_cycle_power_three_adj_iffopen BigOperators Finset in have hadj3 : ∀ i : ZMod n, (simple_graph_cycle_power n 3).Adj i (i + 3) := by intro i rw [simple_graph_cycle_power_three_adj_iff n hn] exact ⟨3, by decide, by decide, by push_cast; rfl⟩ have hadj2 : ∀ i : ZMod n, (simple_graph_cycle_power n 3).Adj i (i + 2) := by intro i rw [simple_graph_cycle_power_three_adj_iff n hn] exact ⟨2, by decide, by decide, by push_cast; rfl⟩ have hcov3 : ∀ i : ZMod n, ∃ s : Fin 3, c s i = c s (i + 3) := fun i => hcov i (i + 3) (hadj3 i) have hcov2 : ∀ i : ZMod n, ∃ s : Fin 3, c s i = c s (i + 2) := fun i => hcov i (i + 2) (hadj2 i)
The sum of the layer weights over all three layers is at most 3n.
Define the weight of layer s as W(s) = ∑_i (2 * [c s i = c s (i+3)] + [c s i = c s (i+2)]). By simple_graph_cycle_power_three_layer_weight_le, each layer satisfies W(s) ≤ n. Bounding the sum over Fin 3 using sum_le_card_nsmul, card_univ, Fintype.card_fin, and Nat.nsmul_eq_mul gives ∑_s W(s) ≤ 3n.
uses
simple_graph_cycle_power_three_layer_weight_le,sum_le_card_nsmul,card_univ,Fintype.card_fin,Nat.nsmul_eq_mullet W : Fin 3 → ℕ := fun s => ∑ i : ZMod n, (2 * (if c s i = c s (i + 3) then 1 else 0) + (if c s i = c s (i + 2) then 1 else 0)) have hW_le : ∀ s : Fin 3, W s ≤ n := fun s => simple_graph_cycle_power_three_layer_weight_le n hn (c s) (hc s) have hsum_le : ∑ s : Fin 3, W s ≤ 3 * n := by have h := sum_le_card_nsmul (univ : Finset (Fin 3)) W n (fun s _ => hW_le s) simp only [card_univ, Fintype.card_fin] at h rw [Nat.nsmul_eq_mul] at h exact h
For each vertex i, the combined coverage at distance 3 and distance 2 satisfies 2 * N3(i) + N2(i) ≥ 3.
Let N3(i) and N2(i) count the number of layers covering {i, i + 3} and {i, i + 2}. Because at least one layer covers {i, i + 3}, bounding the sum of indicators from below by this single term using Finset.single_le_sum, Nat.zero_le, mem_univ, and if_pos shows 1 ≤ N3(i). The same argument shows 1 ≤ N2(i). Linear arithmetic (omega) then implies 2 * N3(i) + N2(i) ≥ 2(1) + 1 = 3.
uses
Finset.single_le_sum,Nat.zero_le,mem_univ,if_poslet N3 : ZMod n → ℕ := fun i => ∑ s : Fin 3, if c s i = c s (i + 3) then 1 else 0 let N2 : ZMod n → ℕ := fun i => ∑ s : Fin 3, if c s i = c s (i + 2) then 1 else 0 have hN3_ge : ∀ i : ZMod n, 1 ≤ N3 i := by intro i rcases hcov3 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 3) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have hN2_ge : ∀ i : ZMod n, 1 ≤ N2 i := by intro i rcases hcov2 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 2) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have h_term_ge : ∀ i : ZMod n, 3 ≤ 2 * N3 i + N2 i := fun i => by have := hN3_ge i have := hN2_ge i omega
The total weight across the three layers and the total vertex coverage both equal 3n.
Exchanging the order of summation using sum_comm, distributing the sum across addition via sum_add_distrib, and factoring out multiplication by 2 with mul_sum shows that ∑_s W(s) = ∑_i (2 * N3(i) + N2(i)). Since each of the n vertices (ZMod.card) contributes at least 3, card_nsmul_le_sum and Nat.nsmul_eq_mul give ∑_s W(s) ≥ 3n. Together with ∑_s W(s) ≤ 3n, linear arithmetic (omega) forces ∑_s W(s) = 3n and ∑_i (2 * N3(i) + N2(i)) = 3n.
uses
sum_comm,sum_add_distrib,mul_sum,card_nsmul_le_sum,ZMod.card,Nat.nsmul_eq_mulhave hsum_comm : ∑ s : Fin 3, W s = ∑ i : ZMod n, (2 * N3 i + N2 i) := by dsimp [W, N3, N2] rw [sum_comm] congr 1 ext i rw [sum_add_distrib, ← mul_sum] have hsum_ge : 3 * n ≤ ∑ s : Fin 3, W s := by rw [hsum_comm] have h := card_nsmul_le_sum (univ : Finset (ZMod n)) (fun i => 2 * N3 i + N2 i) 3 (fun i _ => h_term_ge i) have hc : card (univ : Finset (ZMod n)) = n := ZMod.card n rw [hc, Nat.nsmul_eq_mul] at h omega have hsum_eq : ∑ s : Fin 3, W s = 3 * n := by omega have hsum_term_eq : ∑ i : ZMod n, (2 * N3 i + N2 i) = 3 * n := by omega
Each layer has weight exactly n, and each vertex satisfies 2 * N3(i) + N2(i) = 3.
If any layer had W(s) ≠ n, then W(s) < n by lt_of_le_of_ne, and summing strict inequalities via Finset.sum_lt_sum, sum_const, card_univ, Fintype.card_fin, and Nat.nsmul_eq_mul would force ∑_s W(s) < 3n, a contradiction. Thus W(s) = n for each s. By the same token, if any vertex had 2 * N3(i) + N2(i) ≠ 3, then 3 < 2 * N3(i) + N2(i) (by lt_of_le_of_ne and Ne.symm), and summing over all n vertices via Finset.sum_lt_sum, sum_const, and ZMod.card would force ∑_i (2 * N3(i) + N2(i)) > 3n, a contradiction. Thus 2 * N3(i) + N2(i) = 3 for every vertex i.
uses
sum_const,card_univ,Fintype.card_fin,Nat.nsmul_eq_mul,lt_of_le_of_ne,Finset.sum_lt_sum,mem_univ,ZMod.card,Ne.symmhave hW_eq : ∀ s : Fin 3, W s = n := by intro s have hsum_const : ∑ _s : Fin 3, n = 3 * n := by simp only [sum_const, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] have hle' : ∀ s ∈ (univ : Finset (Fin 3)), W s ≤ (fun _ => n) s := fun s _ => hW_le s by_contra hne have hlt : W s < n := lt_of_le_of_ne (hW_le s) hne have : ∑ x : Fin 3, W x < ∑ _x : Fin 3, n := Finset.sum_lt_sum hle' ⟨s, mem_univ s, hlt⟩ omega have h_term_eq : ∀ i : ZMod n, 2 * N3 i + N2 i = 3 := by intro i have hsum_const : ∑ _i : ZMod n, 3 = 3 * n := by have hc : card (univ : Finset (ZMod n)) = n := ZMod.card n simp only [sum_const, hc, Nat.nsmul_eq_mul] omega have hle' : ∀ j ∈ (univ : Finset (ZMod n)), (fun _ => 3) j ≤ 2 * N3 j + N2 j := fun j _ => h_term_ge j by_contra hne have hlt : 3 < 2 * N3 i + N2 i := lt_of_le_of_ne (h_term_ge i) (Ne.symm hne) have : ∑ _x : ZMod n, 3 < ∑ x : ZMod n, (2 * N3 x + N2 x) := Finset.sum_lt_sum hle' ⟨i, mem_univ i, hlt⟩ omega
For each vertex i, exactly one layer covers {i, i + 3} and exactly one layer covers {i, i + 2}.
For each i, the natural numbers N3(i) and N2(i) satisfy 2 * N3(i) + N2(i) = 3 with N3(i) ≥ 1 and N2(i) ≥ 1. Linear arithmetic (omega) uniquely determines that N3(i) = 1 and N2(i) = 1.
have hN3_eq : ∀ i : ZMod n, N3 i = 1 := by intro i have := h_term_eq i have := hN3_ge i have := hN2_ge i omega have hN2_eq : ∀ i : ZMod n, N2 i = 1 := by intro i have := h_term_eq i have := hN3_ge i have := hN2_ge i omega
A predicate on Fin 3 whose indicator sum equals 1 has a unique satisfying element.
By sum_boole, the sum of indicator booleans for a predicate P on Fin 3 equals the cardinality of the filtered subset {s | P s}. If this sum is 1, card_eq_one implies the subset is a singleton {s}. Extensionality (Finset.ext_iff.mp, mem_filter, mem_univ, true_and, mem_singleton) then shows that P x ↔ x = s, which establishes unique existence ∃! s, P s.
uses
sum_boole,card_eq_one,Finset.ext_iff.mp,mem_filter,mem_univ,true_and,mem_singletonhave h_exists_unique : ∀ (P : Fin 3 → Prop) [DecidablePred P], (∑ s : Fin 3, (if P s then 1 else 0)) = 1 → ∃! s, P s := by intro P _ h have hcard : card (filter P univ) = 1 := by have h1 : (∑ s : Fin 3, if P s then 1 else 0 : ℕ) = card (filter P univ) := sum_boole (R := ℕ) P univ rwa [← h1] rw [card_eq_one] at hcard rcases hcard with ⟨s, hs⟩ use s have hp : ∀ x, P x ↔ x = s := by intro x have := Finset.ext_iff.mp hs x simp only [mem_filter, mem_univ, true_and, mem_singleton] at this exact this exact ⟨(hp s).mpr rfl, fun x hx => (hp x).mp hx⟩
Every distance-3 and distance-2 pair is uniquely covered, and each clique contains a distance-3 chord spanning any vertex in it.
Applying the uniqueness helper to N3(i) = 1 and N2(i) = 1 shows that for every i, exactly one layer covers {i, i + 3} and exactly one covers {i, i + 2}. Finally, because each layer achieves maximal weight W(s) = n, the tight-weight classification theorem simple_graph_cycle_power_three_layer_weight_eq_imp shows that for each layer s and vertex i, there is an offset d ≤ 3 such that c s (i - d) = c s (i - d + 3) = c s i.
uses
simple_graph_cycle_power_three_layer_weight_eq_imprefine ⟨fun i => h_exists_unique (fun s => c s i = c s (i + 3)) (hN3_eq i), fun i => h_exists_unique (fun s => c s i = c s (i + 2)) (hN2_eq i), fun s i => ?_⟩ exact simple_graph_cycle_power_three_layer_weight_eq_imp n hn (c s) (hc s) (hW_eq s) i
simple_graph_cycle_power_three_adj_iff- Two vertices u, v in ZMod n are adjacent in the 3rd power of the cycle graph (for n ≥ 10) if and only if v - u is a non-zero integer offset e with |e| ≤ 3.
simple_graph_cycle_power_three_layer_weight_le- For any layer labelling c whose monochromatic components are cliques in C_n^3 (n ≥ 10), the total layer weight ∑ i, (2 * [c(i) = c(i+3)] + [c(i) = c(i+2)]) is at most n.
sum_le_card_nsmul- If each term in a sum over a finite set s is at most n, then the sum is at most |s| * n.
card_univ- The cardinality of the universal finset on a finite type equals the cardinality of the type.
Fintype.card_fin- The finite type Fin n has cardinality n.
Nat.nsmul_eq_mul- Scalar multiplication of a natural number by another natural number equals ordinary multiplication.
Finset.single_le_sum- A single term in a sum of non-negative elements over a finite set is at most the total sum.
Nat.zero_le- Every natural number is greater than or equal to 0.
mem_univ- Every element of a finite type belongs to the universal finset.
if_pos- If a proposition c holds, then the conditional expression (if c then t else e) equals t.
sum_comm- The order of summation in a double finite sum can be swapped.
sum_add_distrib- A finite sum of sums equals the sum of the individual sums.
mul_sum- Multiplication by a factor from the left distributes over a finite sum.
card_nsmul_le_sum- If each term in a sum over a finite set s is at least n, then the sum is at least |s| * n.
ZMod.card- The cardinality of ZMod n is n.
sum_const- Summing a constant value b over a finite set s equals |s| * b.
lt_of_le_of_ne- If a ≤ b and a ≠ b, then a < b.
Finset.sum_lt_sum- If f ≤ g everywhere on a finite set s and f(x) < g(x) for at least one element x in s, then ∑ s f < ∑ s g.
Ne.symm- If a ≠ b, then b ≠ a.
sum_boole- The sum of indicator booleans for a predicate p over a finite set s equals the cardinality of the subset of elements satisfying p.
card_eq_one- A finite set has cardinality 1 if and only if it consists of a single element.
Finset.ext_iff.mp- If two finite sets are equal, they contain exactly the same elements.
mem_filter- An element belongs to the filtered subset {x ∈ s | p(x)} if and only if it belongs to s and satisfies p.
true_and- The proposition True ∧ p is logically equivalent to p.
mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
simple_graph_cycle_power_three_layer_weight_eq_imp- If a layer labelling c of C_n^3 (n ≥ 10) achieves the maximal layer weight of n, then every vertex i belongs to the same clique as a pair at distance 3 spanning it (c(i - d) = c(i - d + 3) = c(i) for some d ≤ 3).
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.
theorem simple_graph_cycle_power_three_cover_three_tight (n : ℕ) [NeZero n] (hn : 10 ≤ n) (c : Fin 3 → ZMod n → ZMod n) (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n 3).Adj u v) (hcov : ∀ u v, (simple_graph_cycle_power n 3).Adj u v → ∃ s, c s u = c s v) : (∀ i, ∃! s, c s i = c s (i + 3)) ∧ (∀ i, ∃! s, c s i = c s (i + 2)) ∧ ∀ s i, ∃ d : ℕ, d ≤ 3 ∧ c s (i - d) = c s (i - d + 3) ∧ c s (i - d) = c s i := by open BigOperators Finset in have hadj3 : ∀ i : ZMod n, (simple_graph_cycle_power n 3).Adj i (i + 3) := by intro i rw [simple_graph_cycle_power_three_adj_iff n hn] exact ⟨3, by decide, by decide, by push_cast; rfl⟩ have hadj2 : ∀ i : ZMod n, (simple_graph_cycle_power n 3).Adj i (i + 2) := by intro i rw [simple_graph_cycle_power_three_adj_iff n hn] exact ⟨2, by decide, by decide, by push_cast; rfl⟩ have hcov3 : ∀ i : ZMod n, ∃ s : Fin 3, c s i = c s (i + 3) := fun i => hcov i (i + 3) (hadj3 i) have hcov2 : ∀ i : ZMod n, ∃ s : Fin 3, c s i = c s (i + 2) := fun i => hcov i (i + 2) (hadj2 i) let W : Fin 3 → ℕ := fun s => ∑ i : ZMod n, (2 * (if c s i = c s (i + 3) then 1 else 0) + (if c s i = c s (i + 2) then 1 else 0)) have hW_le : ∀ s : Fin 3, W s ≤ n := fun s => simple_graph_cycle_power_three_layer_weight_le n hn (c s) (hc s) have hsum_le : ∑ s : Fin 3, W s ≤ 3 * n := by have h := sum_le_card_nsmul (univ : Finset (Fin 3)) W n (fun s _ => hW_le s) simp only [card_univ, Fintype.card_fin] at h rw [Nat.nsmul_eq_mul] at h exact h let N3 : ZMod n → ℕ := fun i => ∑ s : Fin 3, if c s i = c s (i + 3) then 1 else 0 let N2 : ZMod n → ℕ := fun i => ∑ s : Fin 3, if c s i = c s (i + 2) then 1 else 0 have hN3_ge : ∀ i : ZMod n, 1 ≤ N3 i := by intro i rcases hcov3 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 3) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have hN2_ge : ∀ i : ZMod n, 1 ≤ N2 i := by intro i rcases hcov2 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 2) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have h_term_ge : ∀ i : ZMod n, 3 ≤ 2 * N3 i + N2 i := fun i => by have := hN3_ge i have := hN2_ge i omega have hsum_comm : ∑ s : Fin 3, W s = ∑ i : ZMod n, (2 * N3 i + N2 i) := by dsimp [W, N3, N2] rw [sum_comm] congr 1 ext i rw [sum_add_distrib, ← mul_sum] have hsum_ge : 3 * n ≤ ∑ s : Fin 3, W s := by rw [hsum_comm] have h := card_nsmul_le_sum (univ : Finset (ZMod n)) (fun i => 2 * N3 i + N2 i) 3 (fun i _ => h_term_ge i) have hc : card (univ : Finset (ZMod n)) = n := ZMod.card n rw [hc, Nat.nsmul_eq_mul] at h omega have hsum_eq : ∑ s : Fin 3, W s = 3 * n := by omega have hsum_term_eq : ∑ i : ZMod n, (2 * N3 i + N2 i) = 3 * n := by omega have hW_eq : ∀ s : Fin 3, W s = n := by intro s have hsum_const : ∑ _s : Fin 3, n = 3 * n := by simp only [sum_const, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] have hle' : ∀ s ∈ (univ : Finset (Fin 3)), W s ≤ (fun _ => n) s := fun s _ => hW_le s by_contra hne have hlt : W s < n := lt_of_le_of_ne (hW_le s) hne have : ∑ x : Fin 3, W x < ∑ _x : Fin 3, n := Finset.sum_lt_sum hle' ⟨s, mem_univ s, hlt⟩ omega have h_term_eq : ∀ i : ZMod n, 2 * N3 i + N2 i = 3 := by intro i have hsum_const : ∑ _i : ZMod n, 3 = 3 * n := by have hc : card (univ : Finset (ZMod n)) = n := ZMod.card n simp only [sum_const, hc, Nat.nsmul_eq_mul] omega have hle' : ∀ j ∈ (univ : Finset (ZMod n)), (fun _ => 3) j ≤ 2 * N3 j + N2 j := fun j _ => h_term_ge j by_contra hne have hlt : 3 < 2 * N3 i + N2 i := lt_of_le_of_ne (h_term_ge i) (Ne.symm hne) have : ∑ _x : ZMod n, 3 < ∑ x : ZMod n, (2 * N3 x + N2 x) := Finset.sum_lt_sum hle' ⟨i, mem_univ i, hlt⟩ omega have hN3_eq : ∀ i : ZMod n, N3 i = 1 := by intro i have := h_term_eq i have := hN3_ge i have := hN2_ge i omega have hN2_eq : ∀ i : ZMod n, N2 i = 1 := by intro i have := h_term_eq i have := hN3_ge i have := hN2_ge i omega have h_exists_unique : ∀ (P : Fin 3 → Prop) [DecidablePred P], (∑ s : Fin 3, (if P s then 1 else 0)) = 1 → ∃! s, P s := by intro P _ h have hcard : card (filter P univ) = 1 := by have h1 : (∑ s : Fin 3, if P s then 1 else 0 : ℕ) = card (filter P univ) := sum_boole (R := ℕ) P univ rwa [← h1] rw [card_eq_one] at hcard rcases hcard with ⟨s, hs⟩ use s have hp : ∀ x, P x ↔ x = s := by intro x have := Finset.ext_iff.mp hs x simp only [mem_filter, mem_univ, true_and, mem_singleton] at this exact this exact ⟨(hp s).mpr rfl, fun x hx => (hp x).mp hx⟩ refine ⟨fun i => h_exists_unique (fun s => c s i = c s (i + 3)) (hN3_eq i), fun i => h_exists_unique (fun s => c s i = c s (i + 2)) (hN2_eq i), fun s i => ?_⟩ exact simple_graph_cycle_power_three_layer_weight_eq_imp n hn (c s) (hc s) (hW_eq s) i