simple_graph_cycle_power_seven_cover_four_layer_weight_eq
In any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every layer has weight exactly n: the sum over i of 2·[i ~ i+7] + [i ~ i+6] + [i ~ i+4] in that layer equals n.
Statement
theorem simple_graph_cycle_power_seven_cover_four_layer_weight_eq (n : ℕ) [NeZero n] (hn : 22 ≤ n) (c : Fin 4 → ZMod n → ZMod n) (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n 7).Adj u v) (hcov : ∀ u v, (simple_graph_cycle_power n 7).Adj u v → ∃ s, c s u = c s v) (s : Fin 4) : ∑ i : ZMod n, (2 * (if c s i = c s (i + 7) then 1 else 0) + (if c s i = c s (i + 6) then 1 else 0) + (if c s i = c s (i + 4) then 1 else 0)) = n
- Source
- helper for RT-1 (k = 7 case of OP-205, arXiv:2610.15635): the step hW_eq inside the proof of simple_graph_cycle_power_seven_cover_four_tight, exposed for one layer
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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_seven_adj_iffFor n ≥ 22, u and v are adjacent in C_n^7 iff v = u + e for an integer e with 0 < |e| ≤ 7.
- simple_graph_cycle_power_seven_layer_weight_leLet n ≥ 22 and let c label the vertices of C_n^7 so that every label class is a clique. Then Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~ i+4]) ≤…
- Used by 2
- simple_graph_cycle_power_seven_cover_four_tight_one_iff_sixIn a tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- simple_graph_cycle_power_seven_cover_four_tight_dvdA tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
The proof, explained
The theorem is proved by a double-counting argument comparing the total layer weight ∑_{s ∈ Fin 4} W(s) to 4n. A known upper bound shows that each layer has weight at most n, hence the sum over all four layers is at most 4n. Reversing the order of summation expresses the total weight as the sum over all n vertices of their coverage of chords of lengths 7, 6, and 4; since the four layers cover every edge of C_n^7, each chord is covered at least once, giving each vertex a contribution of at least 2(1) + 1 + 1 = 4 and total weight at least 4n. Since the four layer weights sum to 4n and each is at most n, every layer must have weight exactly n.
For every vertex i ∈ ℤ/nℤ, the pairs {i, i+7}, {i, i+6}, and {i, i+4} are edges in C_n^7, and each is covered by at least one layer.
Since n ≥ 22, chord differences of 7, 6, and 4 are non-zero and within distance 7, which by simple_graph_cycle_power_seven_adj_iff means {i, i+7}, {i, i+6}, and {i, i+4} are edges of C_n^7 for all i. The cover hypothesis hcov guarantees that for each vertex i and each offset d ∈ {7, 6, 4}, there is some layer s ∈ Fin 4 where c s i = c s (i + d).
uses
simple_graph_cycle_power_seven_adj_iffopen BigOperators Finset in have hadj7 : ∀ i : ZMod n, (simple_graph_cycle_power n 7).Adj i (i + 7) := by intro i rw [simple_graph_cycle_power_seven_adj_iff n hn] exact ⟨7, by decide, by decide, by push_cast; rfl⟩ have hadj6 : ∀ i : ZMod n, (simple_graph_cycle_power n 7).Adj i (i + 6) := by intro i rw [simple_graph_cycle_power_seven_adj_iff n hn] exact ⟨6, by decide, by decide, by push_cast; rfl⟩ have hadj4 : ∀ i : ZMod n, (simple_graph_cycle_power n 7).Adj i (i + 4) := by intro i rw [simple_graph_cycle_power_seven_adj_iff n hn] exact ⟨4, by decide, by decide, by push_cast; rfl⟩ have hcov7 : ∀ i : ZMod n, ∃ s : Fin 4, c s i = c s (i + 7) := fun i => hcov i (i + 7) (hadj7 i) have hcov6 : ∀ i : ZMod n, ∃ s : Fin 4, c s i = c s (i + 6) := fun i => hcov i (i + 6) (hadj6 i) have hcov4 : ∀ i : ZMod n, ∃ s : Fin 4, c s i = c s (i + 4) := fun i => hcov i (i + 4) (hadj4 i)
The sum of the weights of all four layers satisfies ∑ s, W s ≤ 4 * n.
The weight W(s) of layer s is defined as the sum over i ∈ ℤ/nℤ of 2·[c s i = c s (i+7)] + [c s i = c s (i+6)] + [c s i = c s (i+4)]. By simple_graph_cycle_power_seven_layer_weight_le, every individual layer has weight W(s) ≤ n. Summing this bound over all 4 layers via sum_le_card_nsmul yields ∑ s, W s ≤ 4 * n.
uses
simple_graph_cycle_power_seven_layer_weight_le,sum_le_card_nsmul,card_univ,Fintype.card_fin,Nat.nsmul_eq_mullet W : Fin 4 → ℕ := fun s => ∑ i : ZMod n, (2 * (if c s i = c s (i + 7) then 1 else 0) + (if c s i = c s (i + 6) then 1 else 0) + (if c s i = c s (i + 4) then 1 else 0)) have hW_le : ∀ s : Fin 4, W s ≤ n := fun s => simple_graph_cycle_power_seven_layer_weight_le n hn (c s) (hc s) have hsum_le : ∑ s : Fin 4, W s ≤ 4 * n := by have h := sum_le_card_nsmul (univ : Finset (Fin 4)) 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 ∈ ℤ/nℤ, the combined coverage weight across all four layers is at least 4: 2 * N7 i + N6 i + N4 i ≥ 4.
For each offset d ∈ {7, 6, 4}, let N_d(i) count the layers s ∈ Fin 4 where c s i = c s (i + d). Because each such edge is covered by at least one layer, the indicator for that layer is 1, so N_d(i) ≥ 1 by Finset.single_le_sum and if_pos. Linear arithmetic then immediately gives 2 * N7 i + N6 i + N4 i ≥ 2(1) + 1 + 1 = 4.
uses
Finset.single_le_sum,Nat.zero_le,mem_univ,if_poslet N7 : ZMod n → ℕ := fun i => ∑ s : Fin 4, if c s i = c s (i + 7) then 1 else 0 let N6 : ZMod n → ℕ := fun i => ∑ s : Fin 4, if c s i = c s (i + 6) then 1 else 0 let N4 : ZMod n → ℕ := fun i => ∑ s : Fin 4, if c s i = c s (i + 4) then 1 else 0 have hN7_ge : ∀ i : ZMod n, 1 ≤ N7 i := by intro i rcases hcov7 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 7) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have hN6_ge : ∀ i : ZMod n, 1 ≤ N6 i := by intro i rcases hcov6 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 6) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have hN4_ge : ∀ i : ZMod n, 1 ≤ N4 i := by intro i rcases hcov4 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 4) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have h_term_ge : ∀ i : ZMod n, 4 ≤ 2 * N7 i + N6 i + N4 i := fun i => by have := hN7_ge i have := hN6_ge i have := hN4_ge i omega
The total layer weight equals 4n: ∑ s, W s = 4 * n.
Swapping the order of summation between layers and vertices using sum_comm, sum_add_distrib, and mul_sum shows that ∑ s, W s = ∑ i, (2 * N7 i + N6 i + N4 i). Because each of the n vertices (ZMod.card) contributes at least 4, card_nsmul_le_sum gives ∑ s, W s ≥ 4 * n. Combining this with the upper bound ∑ s, W s ≤ 4 * n forces the total weight to equal 4n.
uses
sum_comm,sum_add_distrib,mul_sum,card_nsmul_le_sum,ZMod.card,Nat.nsmul_eq_mulhave hsum_comm : ∑ s : Fin 4, W s = ∑ i : ZMod n, (2 * N7 i + N6 i + N4 i) := by dsimp [W, N7, N6, N4] rw [sum_comm] congr 1 ext i rw [sum_add_distrib, sum_add_distrib, ← mul_sum] have hsum_ge : 4 * n ≤ ∑ s : Fin 4, W s := by rw [hsum_comm] have h := card_nsmul_le_sum (univ : Finset (ZMod n)) (fun i => 2 * N7 i + N6 i + N4 i) 4 (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 4, W s = 4 * n := by omega have hsum_term_eq : ∑ i : ZMod n, (2 * N7 i + N6 i + N4 i) = 4 * n := by omega
Every layer has weight exactly n, concluding the theorem for the given layer s.
The sum of the four layer weights is 4n while each layer satisfies W(s) ≤ n. If any layer had W(s) ≠ n, it would satisfy W(s) < n by lt_of_le_of_ne, and by strict monotonicity of summation (Finset.sum_lt_sum), the total sum would be strictly less than 4n, a contradiction. Therefore W(s) = n for every layer s.
uses
sum_const,card_univ,Fintype.card_fin,Nat.nsmul_eq_mul,lt_of_le_of_ne,Finset.sum_lt_sum,mem_univhave hW_eq : ∀ s : Fin 4, W s = n := by intro s have hsum_const : ∑ _s : Fin 4, n = 4 * n := by simp only [sum_const, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] have hle' : ∀ s ∈ (univ : Finset (Fin 4)), 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 4, W x < ∑ _x : Fin 4, n := Finset.sum_lt_sum hle' ⟨s, mem_univ s, hlt⟩ omega exact hW_eq s
simple_graph_cycle_power_seven_adj_iff- In the 7th power of an n-cycle with n ≥ 22, two vertices u, v ∈ ℤ/nℤ are adjacent if and only if v = u + e for some non-zero integer e with |e| ≤ 7.
simple_graph_cycle_power_seven_layer_weight_le- In C_n^7 with n ≥ 22, the weight of any layer whose monochromatic pairs are adjacent is at most n.
sum_le_card_nsmul- If each term in a finite sum over s is at most c, the sum is at most |s| · c.
card_univ- The cardinality of the universal finset univ of a finite type equals the type's cardinality.
Fintype.card_fin- The cardinality of Fin n is n.
Nat.nsmul_eq_mul- Scalar multiplication of natural numbers m • n equals m * n.
Finset.single_le_sum- A single non-negative term indexed by an element in a finite set is bounded above by the sum over the entire set.
Nat.zero_le- Zero is less than or equal to any natural number.
mem_univ- Every element of a finite type belongs to the universal finset univ.
if_pos- If condition P holds, if P then t else e simplifies to t.
sum_comm- Finite summation order can be swapped: ∑ x, ∑ y, f x y = ∑ y, ∑ x, f x y.
sum_add_distrib- A sum of sums equals the sum of terms: ∑ (f x + g x) = ∑ f x + ∑ g x.
mul_sum- Multiplication by a scalar distributes over a sum: a * ∑ f i = ∑ (a * f i).
card_nsmul_le_sum- If every term in a finite sum over s is at least c, then |s| · c is at most the sum.
ZMod.card- The cardinality of ℤ/nℤ is n.
sum_const- Summing a constant 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 pointwise on a finite set and f x < g x for at least one element, then ∑ f < ∑ g.
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_seven_cover_four_layer_weight_eq (n : ℕ) [NeZero n] (hn : 22 ≤ n) (c : Fin 4 → ZMod n → ZMod n) (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n 7).Adj u v) (hcov : ∀ u v, (simple_graph_cycle_power n 7).Adj u v → ∃ s, c s u = c s v) (s : Fin 4) : ∑ i : ZMod n, (2 * (if c s i = c s (i + 7) then 1 else 0) + (if c s i = c s (i + 6) then 1 else 0) + (if c s i = c s (i + 4) then 1 else 0)) = n := by open BigOperators Finset in have hadj7 : ∀ i : ZMod n, (simple_graph_cycle_power n 7).Adj i (i + 7) := by intro i rw [simple_graph_cycle_power_seven_adj_iff n hn] exact ⟨7, by decide, by decide, by push_cast; rfl⟩ have hadj6 : ∀ i : ZMod n, (simple_graph_cycle_power n 7).Adj i (i + 6) := by intro i rw [simple_graph_cycle_power_seven_adj_iff n hn] exact ⟨6, by decide, by decide, by push_cast; rfl⟩ have hadj4 : ∀ i : ZMod n, (simple_graph_cycle_power n 7).Adj i (i + 4) := by intro i rw [simple_graph_cycle_power_seven_adj_iff n hn] exact ⟨4, by decide, by decide, by push_cast; rfl⟩ have hcov7 : ∀ i : ZMod n, ∃ s : Fin 4, c s i = c s (i + 7) := fun i => hcov i (i + 7) (hadj7 i) have hcov6 : ∀ i : ZMod n, ∃ s : Fin 4, c s i = c s (i + 6) := fun i => hcov i (i + 6) (hadj6 i) have hcov4 : ∀ i : ZMod n, ∃ s : Fin 4, c s i = c s (i + 4) := fun i => hcov i (i + 4) (hadj4 i) let W : Fin 4 → ℕ := fun s => ∑ i : ZMod n, (2 * (if c s i = c s (i + 7) then 1 else 0) + (if c s i = c s (i + 6) then 1 else 0) + (if c s i = c s (i + 4) then 1 else 0)) have hW_le : ∀ s : Fin 4, W s ≤ n := fun s => simple_graph_cycle_power_seven_layer_weight_le n hn (c s) (hc s) have hsum_le : ∑ s : Fin 4, W s ≤ 4 * n := by have h := sum_le_card_nsmul (univ : Finset (Fin 4)) 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 N7 : ZMod n → ℕ := fun i => ∑ s : Fin 4, if c s i = c s (i + 7) then 1 else 0 let N6 : ZMod n → ℕ := fun i => ∑ s : Fin 4, if c s i = c s (i + 6) then 1 else 0 let N4 : ZMod n → ℕ := fun i => ∑ s : Fin 4, if c s i = c s (i + 4) then 1 else 0 have hN7_ge : ∀ i : ZMod n, 1 ≤ N7 i := by intro i rcases hcov7 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 7) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have hN6_ge : ∀ i : ZMod n, 1 ≤ N6 i := by intro i rcases hcov6 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 6) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have hN4_ge : ∀ i : ZMod n, 1 ≤ N4 i := by intro i rcases hcov4 i with ⟨s, hs⟩ have hle := Finset.single_le_sum (f := fun x => if c x i = c x (i + 4) then 1 else 0) (fun _ _ => Nat.zero_le _) (mem_univ s) rwa [if_pos hs] at hle have h_term_ge : ∀ i : ZMod n, 4 ≤ 2 * N7 i + N6 i + N4 i := fun i => by have := hN7_ge i have := hN6_ge i have := hN4_ge i omega have hsum_comm : ∑ s : Fin 4, W s = ∑ i : ZMod n, (2 * N7 i + N6 i + N4 i) := by dsimp [W, N7, N6, N4] rw [sum_comm] congr 1 ext i rw [sum_add_distrib, sum_add_distrib, ← mul_sum] have hsum_ge : 4 * n ≤ ∑ s : Fin 4, W s := by rw [hsum_comm] have h := card_nsmul_le_sum (univ : Finset (ZMod n)) (fun i => 2 * N7 i + N6 i + N4 i) 4 (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 4, W s = 4 * n := by omega have hsum_term_eq : ∑ i : ZMod n, (2 * N7 i + N6 i + N4 i) = 4 * n := by omega have hW_eq : ∀ s : Fin 4, W s = n := by intro s have hsum_const : ∑ _s : Fin 4, n = 4 * n := by simp only [sum_const, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] have hle' : ∀ s ∈ (univ : Finset (Fin 4)), 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 4, W x < ∑ _x : Fin 4, n := Finset.sum_lt_sum hle' ⟨s, mem_univ s, hlt⟩ omega exact hW_eq s