AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_three_cover_three_tight

theoremverified

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

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.

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

    lines 7–17

    uses simple_graph_cycle_power_three_adj_iff

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

    lines 19–28

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

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

    lines 30–50

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

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

    lines 52–67

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

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

    lines 69–89

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

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

    lines 91–103

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

    lines 105–120

    uses sum_boole, card_eq_one, Finset.ext_iff.mp, mem_filter, mem_univ, true_and, mem_singleton

      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⟩
    
  8. 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.

    lines 121–124

    uses simple_graph_cycle_power_three_layer_weight_eq_imp

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

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