AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_ge

theoremverifiedformalization

For k ≥ 1 and n ≥ 2k + 2, eq(C_n^k) ≥ 1 + ⌈log₂(k + 1)⌉.

Statement

theorem simple_graph_equivalence_covering_number_cycle_power_ge (n k : ℕ) (hk : 1 ≤ k)
    (hn : 2 * k + 2 ≤ n) :
    1 + Nat.clog 2 (k + 1) ≤
      simple_graph_equivalence_covering_number (simple_graph_cycle_power n k)
Formalizes
arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs), Lemma 2.2 (the lower bound of Theorem 1.2).
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

The theorem establishes that covering the edges of the cycle power graph C_n^k (for k ≥ 1 and n ≥ 2k + 2) with t equivalence subgraphs requires 2k + 2 ≤ 2^t, which implies eq(C_n^k) ≥ 1 + ⌈log₂(k + 1)⌉. The proof uses the polynomial rank method: from any equivalence cover of size t, one constructs a product polynomial φ(u, v) that vanishes whenever u = v or u is adjacent to v, but is nonzero on distinct non-adjacent pairs. Evaluating φ on 2k + 2 carefully chosen pairs (x_i, y_j) produces an upper triangular matrix M with nonzero diagonal, forcing rank(M) = 2k + 2. On the other hand, expanding φ over the 2^t subsets of equivalence relations factors M into a product of matrices through a 2^t-dimensional space, bounding its rank by 2^t and yielding the result.

  1. Vertices at forward distance d ∈ [1, k] are adjacent in the cycle power C_n^k.

    We verify the definition of adjacency in C_n^k for u and u + d. Since d < n, the value of d in ℤ/nℤ is d itself by ZMod.val_cast_of_lt. Because 1 ≤ d, d cannot be 0 in ℤ/nℤ, so u ≠ u + d (proved by linear combination and ZMod.val_zero). The cyclic distance between u and u + d is min (u - (u + d)).val (u + d - u).val; since (u + d - u) = d and d ≤ k, min_le_of_right_le ensures this minimum is at most k.

    lines 5–13

    uses ZMod.val_cast_of_lt, ZMod.val_zero, min_le_of_right_le

      have hval : ((d : ZMod n)).val = d := ZMod.val_cast_of_lt hdn
      refine ⟨?_, ?_⟩
      · intro h
        have h0 : (d : ZMod n) = 0 := by linear_combination -h
        rw [h0, ZMod.val_zero] at hval
        omega
      · have h1 : (u + (d : ZMod n)) - u = (d : ZMod n) := by ring
        rw [h1, hval]
        exact min_le_of_right_le hdk
  2. Vertices at forward distance k + 1 are distinct and non-adjacent in C_n^k when n ≥ 2k + 2.

    Since 2k + 2 ≤ n, we have k + 1 < n, so the value of k + 1 in ℤ/nℤ is k + 1 by ZMod.val_cast_of_lt. Because k ≥ 1, this value is nonzero, so u ≠ u + (k + 1). For non-adjacency, the forward difference is k + 1 and the backward difference is -(k + 1), which has value n - (k + 1) ≥ k + 1 by ZMod.val_neg_of_ne_zero. The minimum distance is thus at least k + 1 > k, contradicting adjacency.

    lines 21–32

    uses ZMod.val_cast_of_lt, ZMod.val_zero, ZMod.val_neg_of_ne_zero

      have hval : (((k + 1 : ℕ) : ZMod n)).val = k + 1 := ZMod.val_cast_of_lt (by omega)
      have hnz : NeZero (((k + 1 : ℕ) : ZMod n)) :=
        ⟨fun h => by rw [h, ZMod.val_zero] at hval; omega⟩
      refine ⟨?_, ?_⟩
      · intro h
        have h0 : ((k + 1 : ℕ) : ZMod n) = 0 := by linear_combination -h
        exact hnz.out h0
      · rintro ⟨-, hmin⟩
        have h1 : (u + ((k + 1 : ℕ) : ZMod n)) - u = ((k + 1 : ℕ) : ZMod n) := by ring
        have h2 : u - (u + ((k + 1 : ℕ) : ZMod n)) = -((k + 1 : ℕ) : ZMod n) := by ring
        rw [h1, h2, ZMod.val_neg_of_ne_zero, hval] at hmin
        omega
  3. Every finite simple graph has an equivalence cover of size |V × V|.

    We enumerate the ordered pairs of vertices via Fintype.equivFin. For each pair (x, y), we define an equivalence relation (via a projection map) that merges y into x if {x, y} is an edge of G, leaving all other vertices as singletons. Each non-trivial equivalence class is a single edge (hence a clique in G), and every edge {u, v} is covered by the pair (u, v). This guarantees the set of cover sizes is nonempty.

    lines 38–51

    uses Fintype.equivFin

      classical
      let e := Fintype.equivFin (V × V)
      refine ⟨fun s w => if G.Adj (e.symm s).1 (e.symm s).2 ∧ w = (e.symm s).2 then (e.symm s).1
        else w, ?_, ?_⟩
      · intro s u v huv h
        simp only at h
        split_ifs at h with h1 h2 h2
        · exact absurd (h1.2.trans h2.2.symm) huv
        · rw [h1.2, ← h]; exact h1.1.symm
        · rw [h2.2, h]; exact h2.1
        · exact absurd h huv
      · intro u v huv
        refine ⟨e (u, v), ?_⟩
        simp [huv, huv.ne]
  4. Any equivalence cover of C_n^k has size t ≥ 1, and we define the test product φ(u, v) = ∏ (c s u - c s v).

    Since k ≥ 1, vertices 0 and 1 are adjacent by the forward adjacency lemma, so some equivalence relation c s must cover this edge; hence the cover size t cannot be 0, so 1 ≤ t by Nat.one_le_iff_ne_zero.mpr. We then define the rational-valued function φ(u, v) as the product over all s ∈ Fin t of (val(c s u) - val(c s v)).

    lines 60–66

    uses simple_graph_equivalence_covering_number_cycle_power_ge_adj, le_rfl, Nat.one_le_iff_ne_zero.mpr

      classical
      have ht : 1 ≤ t := by
        obtain ⟨s, -⟩ := hc2 0 (0 + ((1 : ℕ) : ZMod n))
          (simple_graph_equivalence_covering_number_cycle_power_ge_adj n k 0 1 le_rfl hk (by omega))
        exact Nat.one_le_iff_ne_zero.mpr (fun h => by subst h; exact s.elim0)
      set phi : ZMod n → ZMod n → ℚ :=
        fun u v => ∏ s : Fin t, (((c s u).val : ℚ) - ((c s v).val : ℚ)) with hphi
  5. The function φ(u, v) vanishes whenever u = v or u is adjacent to v.

    If u = v, then c s u = c s v for all s (in particular for s = 0, since t ≥ 1). If u is adjacent to v, the covering condition hc2 guarantees there is some s such that c s u = c s v. In either case, the factor for that s is (val(c s u) - val(c s v)) = 0 by sub_self, so the entire product φ(u, v) is zero by Finset.prod_eq_zero.

    lines 67–75

    uses Finset.prod_eq_zero, Finset.mem_univ, sub_self

      have hphi0 : ∀ u v, (u = v ∨ (simple_graph_cycle_power n k).Adj u v) → phi u v = 0 := by
        intro u v h
        have hs : ∃ s, c s u = c s v := by
          rcases h with rfl | h
          · exact ⟨⟨0, ht⟩, rfl⟩
          · exact hc2 u v h
        obtain ⟨s, hs⟩ := hs
        simp only [hphi]
        exact Finset.prod_eq_zero (Finset.mem_univ s) (by rw [hs, sub_self])
  6. The function φ(u, v) is nonzero whenever u ≠ v and u is not adjacent to v.

    By Finset.prod_ne_zero_iff, the product φ(u, v) is nonzero if and only if every factor is nonzero. If some factor s were zero, then val(c s u) = val(c s v) by sub_eq_zero.mp, so c s u = c s v by ZMod.val_injective. Since u ≠ v, condition hc1 would imply that u and v are adjacent, contradicting the assumption that they are not.

    lines 76–84

    uses Finset.prod_ne_zero_iff, ZMod.val_injective, sub_eq_zero.mp

      have hphine : ∀ u v, u ≠ v → ¬ (simple_graph_cycle_power n k).Adj u v → phi u v ≠ 0 := by
        intro u v hne hna
        simp only [hphi]
        rw [Finset.prod_ne_zero_iff]
        intro s _ h
        apply hna
        apply hc1 s u v hne
        apply ZMod.val_injective
        exact_mod_cast sub_eq_zero.mp h
  7. The (2k + 2) × (2k + 2) evaluation matrix M_i,j = φ(x_i, y_j) has nonzero diagonal entries.

    We set x_i = i mod n and y_j = j + k + 1 mod n for i, j ∈ Fin (2k + 2). On the diagonal i = j, y_i = x_i + (k + 1). By the non-adjacency lemma simple_graph_equivalence_covering_number_cycle_power_ge_nadj, x_i ≠ y_i and x_i is not adjacent to y_i. Hence φ(x_i, y_i) ≠ 0 by the non-vanishing property.

    lines 85–96

    uses simple_graph_equivalence_covering_number_cycle_power_ge_nadj

      let x : Fin (2 * k + 2) → ZMod n := fun i => ((i.val : ℕ) : ZMod n)
      let y : Fin (2 * k + 2) → ZMod n := fun j => ((j.val + k + 1 : ℕ) : ZMod n)
      let M : Matrix (Fin (2 * k + 2)) (Fin (2 * k + 2)) ℚ := fun i j => phi (x i) (y j)
      have hdiag : ∀ i, M i i ≠ 0 := by
        intro i
        have hy : y i = x i + ((k + 1 : ℕ) : ZMod n) := by
          simp only [x, y]
          push_cast
          ring
        have hh := simple_graph_equivalence_covering_number_cycle_power_ge_nadj n k hn (x i)
        rw [← hy] at hh
        exact hphine _ _ hh.1 hh.2
  8. The matrix M is upper triangular: M_i,j = 0 whenever j < i.

    Assume j < i with 0 ≤ j < i ≤ 2k + 1. If i ≤ j + k + 1, the forward distance from x_i to y_j is d = j + k + 1 - i. Since j < i, d ≤ k; if d = 0 then x_i = y_j, and if d ≥ 1 then x_i and y_j are adjacent by simple_graph_equivalence_covering_number_cycle_power_ge_adj. If i > j + k + 1, the forward distance from y_j to x_i is d = i - (j + k + 1) ≤ (2k + 1) - (k + 1) = k, so y_j and x_i are adjacent. In every case, x_i = y_j or x_i is adjacent to y_j, so φ(x_i, y_j) = 0.

    lines 97–126

    uses Fin.lt_def, Nat.cast_add, simple_graph_equivalence_covering_number_cycle_power_ge_adj

      have htri : M.BlockTriangular id := by
        intro i j hji
        simp only [id] at hji
        rw [Fin.lt_def] at hji
        have hi := i.isLt
        have hj := j.isLt
        apply hphi0
        by_cases hle : i.val ≤ j.val + k + 1
        · have hy : y j = x i + ((j.val + k + 1 - i.val : ℕ) : ZMod n) := by
            simp only [x, y]
            rw [← Nat.cast_add]
            congr 1
            omega
          by_cases hd : j.val + k + 1 - i.val = 0
          · left
            rw [hy, hd]
            simp
          · right
            rw [hy]
            exact simple_graph_equivalence_covering_number_cycle_power_ge_adj n k _ _
              (by omega) (by omega) (by omega)
        · have hx : x i = y j + ((i.val - (j.val + k + 1) : ℕ) : ZMod n) := by
            simp only [x, y]
            rw [← Nat.cast_add]
            congr 1
            omega
          right
          rw [hx]
          exact (simple_graph_equivalence_covering_number_cycle_power_ge_adj n k _ _
            (by omega) (by omega) (by omega)).symm
  9. The determinant of M is nonzero, so M has full rank 2k + 2.

    Because M is upper triangular, its determinant equals the product of its diagonal entries by Matrix.det_of_isUpperTriangular. Since all diagonal entries are nonzero, det M ≠ 0 by Finset.prod_ne_zero_iff. Therefore M is invertible by Matrix.isUnit_iff_isUnit_det, and by Matrix.rank_of_isUnit its rank equals its dimension 2k + 2.

    lines 127–133

    uses Matrix.det_of_isUpperTriangular, Finset.prod_ne_zero_iff, Matrix.rank_of_isUnit, Matrix.isUnit_iff_isUnit_det

      have hdet : M.det ≠ 0 := by
        rw [Matrix.det_of_isUpperTriangular htri]
        exact Finset.prod_ne_zero_iff.mpr (fun i _ => hdiag i)
      have hrank : M.rank = 2 * k + 2 := by
        rw [Matrix.rank_of_isUnit M ((Matrix.isUnit_iff_isUnit_det M).mpr
          (isUnit_iff_ne_zero.mpr hdet))]
        simp
  10. M factors as U * W where U has 2^t columns, implying 2k + 2 ≤ 2^t.

    Expanding each product φ(x_i, y_j) over subsets S ⊆ Fin t using sub_eq_add_neg, Finset.prod_add, and Finset.powerset_univ expresses M as U * W by Matrix.mul_apply, where U_i,S = ∏_{s ∈ S} val(c s (x_i)) and W_S,j = ∏_{s ∉ S} -val(c s (y_j)). By Matrix.rank_mul_le_left and Matrix.rank_le_card_width, rank(M) ≤ rank(U) ≤ 2^t (via Fintype.card_finset). Since rank(M) = 2k + 2, we obtain 2k + 2 ≤ 2^t.

    lines 134–147

    uses Matrix.mul_apply, sub_eq_add_neg, Finset.prod_add, Finset.powerset_univ, Matrix.rank_mul_le_left, Matrix.rank_le_card_width, Fintype.card_finset

      let U : Matrix (Fin (2 * k + 2)) (Finset (Fin t)) ℚ :=
        fun i S => ∏ s ∈ S, ((c s (x i)).val : ℚ)
      let W : Matrix (Finset (Fin t)) (Fin (2 * k + 2)) ℚ :=
        fun S j => ∏ s ∈ Finset.univ \ S, (-((c s (y j)).val : ℚ))
      have hMUW : M = U * W := by
        ext i j
        rw [Matrix.mul_apply]
        simp only [M, U, W, hphi]
        simp_rw [sub_eq_add_neg]
        rw [Finset.prod_add, Finset.powerset_univ]
      have h1 := Matrix.rank_mul_le_left U W
      have h2 := Matrix.rank_le_card_width U
      rw [← hMUW, hrank] at h1
      simpa [Fintype.card_finset] using h1.trans h2
  11. The equivalence covering number of C_n^k is at least 1 + ⌈log₂(k + 1)⌉.

    By definition, the covering number is the infimum of valid cover sizes t. By le_csInf, it suffices that the set of sizes is nonempty (guaranteed by simple_graph_equivalence_covering_number_cycle_power_ge_exists) and that every valid cover size t satisfies 1 + Nat.clog 2 (k + 1) ≤ t. For any valid cover of size t, simple_graph_equivalence_covering_number_cycle_power_ge_bound gives 2(k + 1) ≤ 2^t. Since t ≥ 1 by Nat.eq_zero_or_pos, we write t = m + 1; then 2(k + 1) ≤ 2^(m + 1) = 2 * 2^m by pow_succ, so k + 1 ≤ 2^m. Thus Nat.clog 2 (k + 1) ≤ m by Nat.clog_le_of_le_pow, which yields 1 + Nat.clog 2 (k + 1) ≤ t.

    lines 153–169

    uses le_csInf, simple_graph_equivalence_covering_number_cycle_power_ge_exists, simple_graph_equivalence_covering_number_cycle_power_ge_bound, Nat.eq_zero_or_pos, pow_succ, Nat.clog_le_of_le_pow

      classical
      have : NeZero n := ⟨by omega⟩
      unfold simple_graph_equivalence_covering_number
      apply le_csInf
      · exact ⟨_, simple_graph_equivalence_covering_number_cycle_power_ge_exists _⟩
      · rintro t ⟨c, hc1, hc2⟩
        have hb := simple_graph_equivalence_covering_number_cycle_power_ge_bound n k hk hn t c hc1 hc2
        have ht : 1 ≤ t := by
          rcases Nat.eq_zero_or_pos t with h | h
          · subst h; simp at hb
          · exact h
        obtain ⟨m, rfl⟩ : ∃ m, t = m + 1 := ⟨t - 1, by omega⟩
        have : Nat.clog 2 (k + 1) ≤ m := by
          apply Nat.clog_le_of_le_pow
          rw [pow_succ] at hb
          omega
        omega
ZMod.val_cast_of_lt
For a < n, the canonical cast of a to ℤ/nℤ has numerical value a.
ZMod.val_zero
The numerical value of 0 in ℤ/nℤ is 0.
min_le_of_right_le
If c ≤ a, then min b c ≤ a.
ZMod.val_neg_of_ne_zero
For a nonzero element a in ℤ/nℤ with n > 0, the value of -a is n - val(a).
Fintype.equivFin
Any finite type α of cardinality m is in bijection with Fin m.
simple_graph_equivalence_covering_number_cycle_power_ge_adj
In the cycle power C_n^k, u and u + d are adjacent whenever 1 ≤ d ≤ k and d < n.
le_rfl
The reflexivity of inequality: a ≤ a.
Nat.one_le_iff_ne_zero.mpr
A natural number is at least 1 if and only if it is nonzero.
Finset.prod_eq_zero
A product over a finite set is zero if at least one factor is zero.
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.
sub_self
Subtracting any group element from itself yields zero: a - a = 0.
Finset.prod_ne_zero_iff
A product over a finite set in an integral domain is nonzero if and only if every factor is nonzero.
ZMod.val_injective
The valuation map from ℤ/nℤ to ℕ is injective for n > 0.
sub_eq_zero.mp
If a - b = 0, then a = b.
simple_graph_equivalence_covering_number_cycle_power_ge_nadj
In C_n^k with n ≥ 2k + 2, vertices u and u + (k + 1) are distinct and not adjacent.
Fin.lt_def
The strict order on Fin n agrees with the strict order on the underlying natural numbers.
Nat.cast_add
The canonical cast to a semiring preserves addition: ↑(m + n) = ↑m + ↑n.
Matrix.det_of_isUpperTriangular
The determinant of an upper triangular square matrix is the product of its diagonal entries.
Matrix.rank_of_isUnit
An invertible (unit) square matrix over a commutative ring with the strong rank condition has full rank equal to its dimension.
Matrix.isUnit_iff_isUnit_det
A square matrix over a commutative ring is invertible if and only if its determinant is invertible.
Matrix.mul_apply
The (i, k)-th entry of a matrix product M * N is the sum ∑ j, M i j * N j k.
sub_eq_add_neg
Subtraction equals addition of the negation: a - b = a + (-b).
Finset.prod_add
Expands a product of sums ∏ i ∈ s, (f i + g i) into the sum over all subsets t ⊆ s of (∏ i ∈ t, f i) * (∏ i ∈ s \ t, g i).
Finset.powerset_univ
The powerset of Finset.univ is Finset.univ of the powerset type.
Matrix.rank_mul_le_left
The rank of a matrix product A * B is at most the rank of A.
Matrix.rank_le_card_width
The rank of a matrix is at most its number of columns (width).
Fintype.card_finset
The cardinality of the powerset of a finite type α is 2^(card α).
le_csInf
In a conditionally complete lattice, a ≤ sInf s if s is nonempty and a ≤ b for all b ∈ s.
simple_graph_equivalence_covering_number_cycle_power_ge_exists
Every finite simple graph has an equivalence cover (specifically of size |V|²).
simple_graph_equivalence_covering_number_cycle_power_ge_bound
Any cover of C_n^k by t equivalence subgraphs satisfies 2k + 2 ≤ 2^t when k ≥ 1 and n ≥ 2k + 2.
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive.
pow_succ
Powers satisfy a^(n + 1) = a^n * a.
Nat.clog_le_of_le_pow
If x ≤ b^y, then the ceiling logarithm Nat.clog b x ≤ y.

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

/-- Vertices at forward distance `d ∈ [1, k]` are adjacent in `C_n^k`. -/theorem simple_graph_equivalence_covering_number_cycle_power_ge_adj (n k : ℕ) [NeZero n]    (u : ZMod n) (d : ℕ) (hd1 : 1 ≤ d) (hdk : d ≤ k) (hdn : d < n) :    (simple_graph_cycle_power n k).Adj u (u + (d : ZMod n)) := by  have hval : ((d : ZMod n)).val = d := ZMod.val_cast_of_lt hdn  refine ⟨?_, ?_⟩  · intro h    have h0 : (d : ZMod n) = 0 := by linear_combination -h    rw [h0, ZMod.val_zero] at hval    omega  · have h1 : (u + (d : ZMod n)) - u = (d : ZMod n) := by ring    rw [h1, hval]    exact min_le_of_right_le hdk/-- Vertices at forward distance `k + 1` are distinct and not adjacent in `C_n^k`when `n ≥ 2k + 2`. -/theorem simple_graph_equivalence_covering_number_cycle_power_ge_nadj (n k : ℕ) [NeZero n]    (hn : 2 * k + 2 ≤ n) (u : ZMod n) :    u ≠ u + ((k + 1 : ℕ) : ZMod n) ∧      ¬ (simple_graph_cycle_power n k).Adj u (u + ((k + 1 : ℕ) : ZMod n)) := by  have hval : (((k + 1 : ℕ) : ZMod n)).val = k + 1 := ZMod.val_cast_of_lt (by omega)  have hnz : NeZero (((k + 1 : ℕ) : ZMod n)) :=    ⟨fun h => by rw [h, ZMod.val_zero] at hval; omega⟩  refine ⟨?_, ?_⟩  · intro h    have h0 : ((k + 1 : ℕ) : ZMod n) = 0 := by linear_combination -h    exact hnz.out h0  · rintro ⟨-, hmin⟩    have h1 : (u + ((k + 1 : ℕ) : ZMod n)) - u = ((k + 1 : ℕ) : ZMod n) := by ring    have h2 : u - (u + ((k + 1 : ℕ) : ZMod n)) = -((k + 1 : ℕ) : ZMod n) := by ring    rw [h1, h2, ZMod.val_neg_of_ne_zero, hval] at hmin    omega/-- Every finite simple graph has an equivalence cover (one class per ordered pair). -/theorem simple_graph_equivalence_covering_number_cycle_power_ge_exists {V : Type*}    [Fintype V] [DecidableEq V] (G : SimpleGraph V) :    simple_graph_has_equivalence_cover G (Fintype.card (V × V)) := by  classical  let e := Fintype.equivFin (V × V)  refine ⟨fun s w => if G.Adj (e.symm s).1 (e.symm s).2 ∧ w = (e.symm s).2 then (e.symm s).1    else w, ?_, ?_⟩  · intro s u v huv h    simp only at h    split_ifs at h with h1 h2 h2    · exact absurd (h1.2.trans h2.2.symm) huv    · rw [h1.2, ← h]; exact h1.1.symm    · rw [h2.2, h]; exact h2.1    · exact absurd h huv  · intro u v huv    refine ⟨e (u, v), ?_⟩    simp [huv, huv.ne]/-- The rank bound: a cover of `C_n^k` (`n ≥ 2k + 2`) by `t` equivalence subgraphshas `2k + 2 ≤ 2^t`. -/theorem simple_graph_equivalence_covering_number_cycle_power_ge_bound (n k : ℕ) (hk : 1 ≤ k)    (hn : 2 * k + 2 ≤ n) [NeZero n] (t : ℕ) (c : Fin t → ZMod n → ZMod n)    (hc1 : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n k).Adj u v)    (hc2 : ∀ u v, (simple_graph_cycle_power n k).Adj u v → ∃ s, c s u = c s v) :    2 * k + 2 ≤ 2 ^ t := by  classical  have ht : 1 ≤ t := by    obtain ⟨s, -⟩ := hc2 0 (0 + ((1 : ℕ) : ZMod n))      (simple_graph_equivalence_covering_number_cycle_power_ge_adj n k 0 1 le_rfl hk (by omega))    exact Nat.one_le_iff_ne_zero.mpr (fun h => by subst h; exact s.elim0)  set phi : ZMod n → ZMod n → ℚ :=    fun u v => ∏ s : Fin t, (((c s u).val : ℚ) - ((c s v).val : ℚ)) with hphi  have hphi0 : ∀ u v, (u = v ∨ (simple_graph_cycle_power n k).Adj u v) → phi u v = 0 := by    intro u v h    have hs : ∃ s, c s u = c s v := by      rcases h with rfl | h      · exact ⟨⟨0, ht⟩, rfl⟩      · exact hc2 u v h    obtain ⟨s, hs⟩ := hs    simp only [hphi]    exact Finset.prod_eq_zero (Finset.mem_univ s) (by rw [hs, sub_self])  have hphine : ∀ u v, u ≠ v → ¬ (simple_graph_cycle_power n k).Adj u v → phi u v ≠ 0 := by    intro u v hne hna    simp only [hphi]    rw [Finset.prod_ne_zero_iff]    intro s _ h    apply hna    apply hc1 s u v hne    apply ZMod.val_injective    exact_mod_cast sub_eq_zero.mp h  let x : Fin (2 * k + 2) → ZMod n := fun i => ((i.val : ℕ) : ZMod n)  let y : Fin (2 * k + 2) → ZMod n := fun j => ((j.val + k + 1 : ℕ) : ZMod n)  let M : Matrix (Fin (2 * k + 2)) (Fin (2 * k + 2)) ℚ := fun i j => phi (x i) (y j)  have hdiag : ∀ i, M i i ≠ 0 := by    intro i    have hy : y i = x i + ((k + 1 : ℕ) : ZMod n) := by      simp only [x, y]      push_cast      ring    have hh := simple_graph_equivalence_covering_number_cycle_power_ge_nadj n k hn (x i)    rw [← hy] at hh    exact hphine _ _ hh.1 hh.2  have htri : M.BlockTriangular id := by    intro i j hji    simp only [id] at hji    rw [Fin.lt_def] at hji    have hi := i.isLt    have hj := j.isLt    apply hphi0    by_cases hle : i.val ≤ j.val + k + 1    · have hy : y j = x i + ((j.val + k + 1 - i.val : ℕ) : ZMod n) := by        simp only [x, y]        rw [← Nat.cast_add]        congr 1        omega      by_cases hd : j.val + k + 1 - i.val = 0      · left        rw [hy, hd]        simp      · right        rw [hy]        exact simple_graph_equivalence_covering_number_cycle_power_ge_adj n k _ _          (by omega) (by omega) (by omega)    · have hx : x i = y j + ((i.val - (j.val + k + 1) : ℕ) : ZMod n) := by        simp only [x, y]        rw [← Nat.cast_add]        congr 1        omega      right      rw [hx]      exact (simple_graph_equivalence_covering_number_cycle_power_ge_adj n k _ _        (by omega) (by omega) (by omega)).symm  have hdet : M.det ≠ 0 := by    rw [Matrix.det_of_isUpperTriangular htri]    exact Finset.prod_ne_zero_iff.mpr (fun i _ => hdiag i)  have hrank : M.rank = 2 * k + 2 := by    rw [Matrix.rank_of_isUnit M ((Matrix.isUnit_iff_isUnit_det M).mpr      (isUnit_iff_ne_zero.mpr hdet))]    simp  let U : Matrix (Fin (2 * k + 2)) (Finset (Fin t)) ℚ :=    fun i S => ∏ s ∈ S, ((c s (x i)).val : ℚ)  let W : Matrix (Finset (Fin t)) (Fin (2 * k + 2)) ℚ :=    fun S j => ∏ s ∈ Finset.univ \ S, (-((c s (y j)).val : ℚ))  have hMUW : M = U * W := by    ext i j    rw [Matrix.mul_apply]    simp only [M, U, W, hphi]    simp_rw [sub_eq_add_neg]    rw [Finset.prod_add, Finset.powerset_univ]  have h1 := Matrix.rank_mul_le_left U W  have h2 := Matrix.rank_le_card_width U  rw [← hMUW, hrank] at h1  simpa [Fintype.card_finset] using h1.trans h2theorem simple_graph_equivalence_covering_number_cycle_power_ge (n k : ℕ) (hk : 1 ≤ k)    (hn : 2 * k + 2 ≤ n) :    1 + Nat.clog 2 (k + 1) ≤      simple_graph_equivalence_covering_number (simple_graph_cycle_power n k) := by  classical  have : NeZero n := ⟨by omega⟩  unfold simple_graph_equivalence_covering_number  apply le_csInf  · exact ⟨_, simple_graph_equivalence_covering_number_cycle_power_ge_exists _⟩  · rintro t ⟨c, hc1, hc2⟩    have hb := simple_graph_equivalence_covering_number_cycle_power_ge_bound n k hk hn t c hc1 hc2    have ht : 1 ≤ t := by      rcases Nat.eq_zero_or_pos t with h | h      · subst h; simp at hb      · exact h    obtain ⟨m, rfl⟩ : ∃ m, t = m + 1 := ⟨t - 1, by omega⟩    have : Nat.clog 2 (k + 1) ≤ m := by      apply Nat.clog_le_of_le_pow      rw [pow_succ] at hb      omega    omega
See it in the graphDiscuss this resultChallenge it