simple_graph_equivalence_covering_number_cycle_power_ge
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
- 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_has_equivalence_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- simple_graph_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- Used by 1
- simple_graph_equivalence_covering_number_cycle_power_dvdFor k ≥ 1 and q ≥ 2, the k-th power of the cycle on q(k + 1) vertices has equivalence covering number exactly 1 + ⌈log₂(k + 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.
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.
uses
ZMod.val_cast_of_lt,ZMod.val_zero,min_le_of_right_lehave 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 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.
uses
ZMod.val_cast_of_lt,ZMod.val_zero,ZMod.val_neg_of_ne_zerohave 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 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.
uses
Fintype.equivFinclassical 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]
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)).
uses
simple_graph_equivalence_covering_number_cycle_power_ge_adj,le_rfl,Nat.one_le_iff_ne_zero.mprclassical 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
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.
uses
Finset.prod_eq_zero,Finset.mem_univ,sub_selfhave 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])
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.
uses
Finset.prod_ne_zero_iff,ZMod.val_injective,sub_eq_zero.mphave 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
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.
uses
simple_graph_equivalence_covering_number_cycle_power_ge_nadjlet 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
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.
uses
Fin.lt_def,Nat.cast_add,simple_graph_equivalence_covering_number_cycle_power_ge_adjhave 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
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.
uses
Matrix.det_of_isUpperTriangular,Finset.prod_ne_zero_iff,Matrix.rank_of_isUnit,Matrix.isUnit_iff_isUnit_dethave 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
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.
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_finsetlet 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
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.
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_powclassical 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.
- In Step 3 (the existence lemma), the witness equivalence cover constructs a relation for each ordered pair in V × V, isolating non-edges and turning each edge into a two-element clique; this establishes nonemptiness so sInf is well-defined.
- In Step 8, showing upper triangularity splits into two cases based on whether i ≤ j + k + 1, corresponding to clockwise versus counterclockwise traversal on the cycle.
- In Step 10, the factorization M = U * W relies on expanding the product of differences ∏ (c s (x i) - c s (y j)) over all subsets of Fin t, which is Lean's formulation of the polynomial method / tensor rank bound.
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.
/-- 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