AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_seven_cover_four_layer_weight_eq

theoremverified

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
Used by 2

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.

  1. 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).

    lines 7–22

    uses simple_graph_cycle_power_seven_adj_iff

      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)
  2. 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.

    lines 24–35

    uses simple_graph_cycle_power_seven_layer_weight_le, sum_le_card_nsmul, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul

      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
    
  3. 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.

    lines 36–65

    uses Finset.single_le_sum, Nat.zero_le, mem_univ, if_pos

      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
  4. 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.

    lines 67–82

    uses sum_comm, sum_add_distrib, mul_sum, card_nsmul_le_sum, ZMod.card, Nat.nsmul_eq_mul

      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
  5. 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.

    lines 84–94

    uses sum_const, card_univ, Fintype.card_fin, Nat.nsmul_eq_mul, lt_of_le_of_ne, Finset.sum_lt_sum, mem_univ

      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
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

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
See it in the graphDiscuss this resultChallenge it