simple_graph_cycle_power_dyadic_cover_card_bound
For dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, every equivalence cover of the cycle power uses at least m+1 layers.
Statement
theorem simple_graph_cycle_power_dyadic_cover_card_bound
(m n t : ℕ) [NeZero n] (hm : 1 ≤ m)
(hn : 3 * (2 ^ m - 1) + 1 ≤ n)
(hcov : simple_graph_has_equivalence_cover
(simple_graph_cycle_power n (2 ^ m - 1)) t) :
m + 1 ≤ t- Formalizes
- arXiv:2610.15635, Lemma 2.2, specialized to k+1=2^m and the stronger range n>=3k+1. This helper uses the uniform dyadic tree weight proof instead of the paper rank argument. It is a known bound, not a research advance.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_cycle_power_adj_iff_of_bandwidth_ltWhen k<n, two vertices of the k-th cycle power are adjacent exactly when their difference has a nonzero signed integer representative of…
- simple_graph_cycle_power_dyadic_layer_weight_leIn any clique labelling of a cycle power with dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, the total layer…
- Used by 1
- simple_graph_cycle_power_dyadic_cover_tight_long_edgesIn an m+1-layer equivalence cover at dyadic bandwidth, every endpoint-distance edge and every other positively weighted dyadic long edge…
The proof, explained
The proof establishes that any equivalence cover of the cycle power graph requires at least m + 1 layers by double counting a dyadic weight function w(i, s) over vertices i ∈ ZMod n and layers s ∈ Fin t. An earlier theorem bounds the weight contributed by any single layer across all vertices by n. For each individual vertex, its edges to the m dyadic offsets 2^m - 2^j (0 ≤ j < m) along the cycle must each be covered by at least one layer, which forces the sum of weights over all layers at that vertex to be at least m + 1. Summing over all vertices and layers gives (m + 1) * n ≤ t * n, from which m + 1 ≤ t follows by dividing by n > 0.
Any step size d ∈ [1, 2^m - 1] along the cycle defines an edge in the cycle power graph between i and i + d.
Because n ≥ 3(2^m - 1) + 1, the bandwidth 2^m - 1 is strictly less than n. By `simple_graph_cycle_power_adj_iff_of_bandwidth_lt`, adjacency in the cycle power graph is equivalent to having a non-zero integer difference of absolute value at most 2^m - 1. Choosing the difference e = d, non-negativity gives |d| = d ≤ 2^m - 1 via `abs_of_nonneg`, establishing that i and i + d are adjacent.
uses
simple_graph_cycle_power_adj_iff_of_bandwidth_lt,abs_of_nonneghave hadj : ∀ d : ℕ, 1 ≤ d → d ≤ 2 ^ m - 1 → (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + (d : ZMod n)) := by intro d hd1 hd2 have hlt : 2 ^ m - 1 < n := by omega rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hlt i] refine ⟨(d : ℤ), by omega, ?_, ?_⟩ · have hd : (0:ℤ) ≤ (d:ℤ) := by omega rw [abs_of_nonneg hd] exact_mod_cast hd2 · push_cast; ring
If a vertex v is identified with i in at least one layer, the sum of indicator variables over all layers is at least 1.
Given a layer s₀ where c(s₀, i) = c(s₀, v), the summand at s₀ is 1. Since every term is non-negative, `Finset.single_le_sum` together with `Finset.mem_univ` ensures that the sum over all layers in Fin t is at least 1.
uses
Finset.single_le_sum,Finset.mem_univhave ind : ∀ (v : ZMod n), (∃ s, c s i = c s v) → 1 ≤ ∑ s : Fin t, (if c s i = c s v then 1 else 0) := by intro v hex obtain ⟨s₀, hs₀⟩ := hex have h1 := Finset.single_le_sum (f := fun s : Fin t => if c s i = c s v then 1 else 0) (fun s _ => by split <;> omega) (Finset.mem_univ s₀) simpa [hs₀] using h1
Every dyadic offset 2^m - 1 and 2^m - 2^j (for 0 ≤ j < m) from i is covered by some layer, so each corresponding layer indicator sum is at least 1.
From m ≥ 1, 2^m ≥ 2 by `Nat.pow_le_pow_right`, so 1 ≤ 2^m - 1. Step 1 then implies i and i + (2^m - 1) are adjacent, so the cover hypothesis provides a covering layer, showing the indicator sum hA1 is at least 1. For each j < m (via `Finset.mem_range.mp`), 2^j < 2^m by `Nat.pow_lt_pow_right` and 1 ≤ 2^j by `Nat.one_le_two_pow`, giving 1 ≤ 2^m - 2^j ≤ 2^m - 1. Step 1 again guarantees adjacency to i + (2^m - 2^j), so another covering layer exists, proving that each indicator sum hB1 is at least 1.
uses
Nat.pow_le_pow_right,le_rfl,Finset.mem_range.mp,Nat.pow_lt_pow_right,Nat.one_le_two_powhave hD1 : 1 ≤ 2 ^ m - 1 := by have : 2 ≤ 2 ^ m := by calc (2:ℕ) = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm omega have hA1 : 1 ≤ ∑ s : Fin t, (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) := ind _ (hcover _ _ (hadj (2 ^ m - 1) hD1 le_rfl)) have hB1 : ∀ j ∈ Finset.range m, 1 ≤ ∑ s : Fin t, (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) := by intro j hj have hjlt : j < m := Finset.mem_range.mp hj have h1 : 1 ≤ 2 ^ m - 2 ^ j := by have : 2 ^ j < 2 ^ m := Nat.pow_lt_pow_right (by norm_num) hjlt omega have h2 : 2 ^ m - 2 ^ j ≤ 2 ^ m - 1 := by have : 1 ≤ 2 ^ j := Nat.one_le_two_pow omega exact ind _ (hcover _ _ (hadj _ h1 h2))
For each layer s, the weighted expression 2 * [c_s(i) = c_s(i + 2^m - 1)] + ∑_{j=1}^{m-1} [c_s(i) = c_s(i + 2^m - 2^j)] equals [c_s(i) = c_s(i + 2^m - 1)] + ∑_{j=0}^{m-1} [c_s(i) = c_s(i + 2^m - 2^j)].
Letting A = [c_s(i) = c_s(i + 2^m - 1)] and B(j) = [c_s(i) = c_s(i + 2^m - 2^j)], setting j = 0 gives B(0) = A since 2^m - 2^0 = 2^m - 1. Using `Finset.sum_erase_add` at 0 ∈ Finset.range m (from `Finset.mem_range.mpr`), the sum over all j < m splits into B(0) plus the sum over non-zero j. Rewriting using `if_pos`, `Nat.add_zero`, `Finset.sum_congr`, `if_neg`, and `Finset.ne_of_mem_erase` shows the omitted-zero sum equals the sum over non-zero j. Substituting B(0) = A then turns 2A + ∑_{j≠0} B(j) into A + ∑_{j=0}^{m-1} B(j).
uses
Finset.mem_range.mpr,Finset.sum_erase_add,if_pos,Nat.add_zero,Finset.sum_congr,if_neg,Finset.ne_of_mem_erasehave key : ∀ s : Fin t, 2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + ∑ j ∈ Finset.range m, (if j = 0 then 0 else (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)) = (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + ∑ j ∈ Finset.range m, (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) := by intro s set A : ℕ := if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0 with hA set B : ℕ → ℕ := fun j => if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0 with hB have hB0 : B 0 = A := by simp [hB, hA] have hmem : 0 ∈ Finset.range m := Finset.mem_range.mpr (by omega) have e1 : ((Finset.range m).erase 0).sum B + B 0 = ∑ j ∈ Finset.range m, B j := Finset.sum_erase_add _ _ hmem have e2 : ∑ j ∈ Finset.range m, (if j = 0 then 0 else B j) = ((Finset.range m).erase 0).sum B := by have h := Finset.sum_erase_add (s := Finset.range m) (f := fun j => if j = 0 then 0 else B j) hmem rw [if_pos rfl, Nat.add_zero] at h rw [← h] exact Finset.sum_congr rfl (fun j hj => by rw [if_neg (Finset.ne_of_mem_erase hj)]) rw [← e1, e2, hB0] omega
For any vertex i, the sum of weights across all layers is at least m + 1.
Rewriting the summand using the identity from Step 4 via `Finset.sum_congr`, distributing addition using `Finset.sum_add_distrib`, and exchanging sums with `Finset.sum_comm` expresses the total weight as ∑_s A_s + ∑_{j=0}^{m-1} ∑_s B_s(j). The first sum is at least 1 by hA1, and the double sum over the m values of j is at least m by `Finset.sum_le_sum` applied to hB1. Thus the sum is at least 1 + m = m + 1.
uses
Finset.sum_congr,Finset.sum_add_distrib,Finset.sum_comm,Finset.sum_le_sumrw [Finset.sum_congr rfl (fun s _ => key s)] rw [Finset.sum_add_distrib] rw [Finset.sum_comm (s := Finset.univ) (t := Finset.range m)] have hmle : m ≤ ∑ j ∈ Finset.range m, ∑ s : Fin t, (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) := by simpa using Finset.sum_le_sum hB1 omega
Unpack the equivalence cover into layer colorings and define the vertex-layer weight function w(i, s).
The hypothesis hcov gives coloring functions c : Fin t → ZMod n → ZMod n whose fibers are cliques in each layer (`hclique`) and which cover all edges of the cycle power (`hcover`). The weight w(i, s) is defined for each vertex i and layer s as 2 * [c_s(i) = c_s(i + 2^m - 1)] plus the sum over 0 < j < m of [c_s(i) = c_s(i + 2^m - 2^j)].
theorem simple_graph_cycle_power_dyadic_cover_card_bound (m n t : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (hcov : simple_graph_has_equivalence_cover (simple_graph_cycle_power n (2 ^ m - 1)) t) : m + 1 ≤ t := by obtain ⟨c, hclique, hcover⟩ := hcov set w : ZMod n → Fin t → ℕ := fun i s => 2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + ∑ j ∈ Finset.range m, if j = 0 then 0 else (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) with hw
Each layer has total weight at most n, and each vertex receives total weight at least m + 1 across all layers.
Applying the layer weight bound `simple_graph_cycle_power_dyadic_layer_weight_le` to each layer s yields ∑_i w(i, s) ≤ n (hW). Applying the vertex lemma `simple_graph_cycle_power_dyadic_cover_card_bound_vertex` to each vertex i yields m + 1 ≤ ∑_s w(i, s) (hV).
uses
simple_graph_cycle_power_dyadic_layer_weight_le,simple_graph_cycle_power_dyadic_cover_card_bound_vertexhave hW : ∀ s : Fin t, ∑ i : ZMod n, w i s ≤ n := by intro s have := simple_graph_cycle_power_dyadic_layer_weight_le m n hm hn (c s) (hclique s) simpa [hw] using this have hV : ∀ i : ZMod n, m + 1 ≤ ∑ s : Fin t, w i s := by intro i have := simple_graph_cycle_power_dyadic_cover_card_bound_vertex m n t hm hn c hcover i simpa [hw] using this
The total number of layers t is at least m + 1.
A double counting chain shows (m + 1) * n ≤ t * n: summing the vertex bound m + 1 over all n vertices (`Finset.sum_const`, `Finset.card_univ`, `ZMod.card`, `Nat.nsmul_eq_mul`, `Nat.mul_comm`) gives (m + 1) * n ≤ ∑_i ∑_s w(i, s) via `Finset.sum_le_sum`. Exchanging the order of summation with `Finset.sum_comm` and applying the layer upper bound via `Finset.sum_le_sum` gives ∑_s ∑_i w(i, s) ≤ ∑_s n = t * n using `Finset.sum_const`, `Finset.card_univ`, `Fintype.card_fin`, and `Nat.nsmul_eq_mul`. Since n > 0 by `NeZero.pos`, `Nat.le_of_mul_le_mul_right` cancels n to conclude m + 1 ≤ t.
uses
Finset.sum_const,Finset.card_univ,ZMod.card,Nat.nsmul_eq_mul,Nat.mul_comm,Finset.sum_le_sum,Finset.sum_comm,Fintype.card_fin,Nat.le_of_mul_le_mul_right,NeZero.poshave hmain : (m + 1) * n ≤ t * n := by calc (m + 1) * n = ∑ _i : ZMod n, (m + 1) := by rw [Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm] _ ≤ ∑ i : ZMod n, ∑ s : Fin t, w i s := Finset.sum_le_sum (fun i _ => hV i) _ = ∑ s : Fin t, ∑ i : ZMod n, w i s := Finset.sum_comm _ ≤ ∑ _s : Fin t, n := Finset.sum_le_sum (fun s _ => hW s) _ = t * n := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] exact Nat.le_of_mul_le_mul_right hmain (NeZero.pos n)
simple_graph_cycle_power_adj_iff_of_bandwidth_lt- Two vertices u, v in the cycle power graph of order n and bandwidth k < n are adjacent if and only if v = u + e for some non-zero integer e with |e| ≤ k.
abs_of_nonneg- The absolute value of a non-negative element is the element itself.
Finset.single_le_sum- A single term f(a) in a sum over a finite set s is bounded by the total sum, provided all terms are non-negative.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Nat.pow_le_pow_right- For a positive base n, exponentiation n^i is monotonically non-decreasing in i.
le_rfl- The inequality relation ≤ is reflexive: a ≤ a.
Finset.mem_range.mp- An element j belongs to Finset.range m if and only if j < m (forward direction).
Nat.pow_lt_pow_right- For a base a > 1, exponentiation is strictly increasing: m < n implies a^m < a^n.
Nat.one_le_two_pow- Any power of 2 with natural exponent is at least 1.
Finset.mem_range.mpr- If j < m, then j belongs to Finset.range m (reverse direction).
Finset.sum_erase_add- A finite sum over s can be decomposed into the term at a plus the sum over s \ {a}.
if_pos- If the condition c is true, an if-then-else expression evaluates to its then branch.
Nat.add_zero- Adding zero to any natural number leaves it unchanged: n + 0 = n.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on all elements.
if_neg- If the condition c is false, an if-then-else expression evaluates to its else branch.
Finset.ne_of_mem_erase- Any element in s \ {a} is distinct from a.
Finset.sum_add_distrib- The sum of a pointwise sum distributes into the sum of the first summands plus the sum of the second summands.
Finset.sum_comm- The order of summation in a finite double sum can be swapped (Fubini's theorem for finite sums).
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set s, then ∑ i ∈ s, f(i) ≤ ∑ i ∈ s, g(i).
simple_graph_cycle_power_dyadic_layer_weight_le- For any layer whose equivalence classes are cliques in the cycle power graph with bandwidth 2^m - 1, the sum over all vertices of the dyadic weight expression is at most n.
simple_graph_cycle_power_dyadic_cover_card_bound_vertex- For any vertex i and any equivalence cover, the sum of its dyadic weights over all layers is at least m + 1.
Finset.sum_const- Summing a constant value b over a finite set s equals |s| • b.
Finset.card_univ- The cardinality of the universal finset of a finite type α equals the cardinality of α.
ZMod.card- The ring ZMod n has cardinality n.
Nat.nsmul_eq_mul- Scalar multiplication of natural numbers m • n is ordinary multiplication m * n.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
Fintype.card_fin- The standard finite set Fin n has cardinality n.
Nat.le_of_mul_le_mul_right- If a * c ≤ b * c and c > 0 for natural numbers, then a ≤ b.
NeZero.pos- An element of a type with NeZero is strictly positive.
- In the definition of the vertex weight, the offset 2^m - 1 is given a coefficient of 2 while the term j = 0 is omitted from the summation over j < m. Because 2^m - 2^0 = 2^m - 1, this equals the sum over all m dyadic offsets 2^m - 2^j (for 0 ≤ j < m) plus an additional copy of the maximum offset 2^m - 1.
- Linear integer arithmetic and simple inequalities (such as checking bandwidth conditions and range bounds) are closed by the `omega` tactic throughout the proof.
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.
private lemma simple_graph_cycle_power_dyadic_cover_card_bound_vertex (m n t : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : Fin t → ZMod n → ZMod n) (hcover : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v → ∃ s, c s u = c s v) (i : ZMod n) : m + 1 ≤ ∑ s : Fin t, (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + ∑ j ∈ Finset.range m, if j = 0 then 0 else (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)) := by have hadj : ∀ d : ℕ, 1 ≤ d → d ≤ 2 ^ m - 1 → (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + (d : ZMod n)) := by intro d hd1 hd2 have hlt : 2 ^ m - 1 < n := by omega rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hlt i] refine ⟨(d : ℤ), by omega, ?_, ?_⟩ · have hd : (0:ℤ) ≤ (d:ℤ) := by omega rw [abs_of_nonneg hd] exact_mod_cast hd2 · push_cast; ring have ind : ∀ (v : ZMod n), (∃ s, c s i = c s v) → 1 ≤ ∑ s : Fin t, (if c s i = c s v then 1 else 0) := by intro v hex obtain ⟨s₀, hs₀⟩ := hex have h1 := Finset.single_le_sum (f := fun s : Fin t => if c s i = c s v then 1 else 0) (fun s _ => by split <;> omega) (Finset.mem_univ s₀) simpa [hs₀] using h1 have hD1 : 1 ≤ 2 ^ m - 1 := by have : 2 ≤ 2 ^ m := by calc (2:ℕ) = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm omega have hA1 : 1 ≤ ∑ s : Fin t, (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) := ind _ (hcover _ _ (hadj (2 ^ m - 1) hD1 le_rfl)) have hB1 : ∀ j ∈ Finset.range m, 1 ≤ ∑ s : Fin t, (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) := by intro j hj have hjlt : j < m := Finset.mem_range.mp hj have h1 : 1 ≤ 2 ^ m - 2 ^ j := by have : 2 ^ j < 2 ^ m := Nat.pow_lt_pow_right (by norm_num) hjlt omega have h2 : 2 ^ m - 2 ^ j ≤ 2 ^ m - 1 := by have : 1 ≤ 2 ^ j := Nat.one_le_two_pow omega exact ind _ (hcover _ _ (hadj _ h1 h2)) have key : ∀ s : Fin t, 2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + ∑ j ∈ Finset.range m, (if j = 0 then 0 else (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)) = (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + ∑ j ∈ Finset.range m, (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) := by intro s set A : ℕ := if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0 with hA set B : ℕ → ℕ := fun j => if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0 with hB have hB0 : B 0 = A := by simp [hB, hA] have hmem : 0 ∈ Finset.range m := Finset.mem_range.mpr (by omega) have e1 : ((Finset.range m).erase 0).sum B + B 0 = ∑ j ∈ Finset.range m, B j := Finset.sum_erase_add _ _ hmem have e2 : ∑ j ∈ Finset.range m, (if j = 0 then 0 else B j) = ((Finset.range m).erase 0).sum B := by have h := Finset.sum_erase_add (s := Finset.range m) (f := fun j => if j = 0 then 0 else B j) hmem rw [if_pos rfl, Nat.add_zero] at h rw [← h] exact Finset.sum_congr rfl (fun j hj => by rw [if_neg (Finset.ne_of_mem_erase hj)]) rw [← e1, e2, hB0] omega rw [Finset.sum_congr rfl (fun s _ => key s)] rw [Finset.sum_add_distrib] rw [Finset.sum_comm (s := Finset.univ) (t := Finset.range m)] have hmle : m ≤ ∑ j ∈ Finset.range m, ∑ s : Fin t, (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) := by simpa using Finset.sum_le_sum hB1 omegatheorem simple_graph_cycle_power_dyadic_cover_card_bound (m n t : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (hcov : simple_graph_has_equivalence_cover (simple_graph_cycle_power n (2 ^ m - 1)) t) : m + 1 ≤ t := by obtain ⟨c, hclique, hcover⟩ := hcov set w : ZMod n → Fin t → ℕ := fun i s => 2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + ∑ j ∈ Finset.range m, if j = 0 then 0 else (if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0) with hw have hW : ∀ s : Fin t, ∑ i : ZMod n, w i s ≤ n := by intro s have := simple_graph_cycle_power_dyadic_layer_weight_le m n hm hn (c s) (hclique s) simpa [hw] using this have hV : ∀ i : ZMod n, m + 1 ≤ ∑ s : Fin t, w i s := by intro i have := simple_graph_cycle_power_dyadic_cover_card_bound_vertex m n t hm hn c hcover i simpa [hw] using this have hmain : (m + 1) * n ≤ t * n := by calc (m + 1) * n = ∑ _i : ZMod n, (m + 1) := by rw [Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm] _ ≤ ∑ i : ZMod n, ∑ s : Fin t, w i s := Finset.sum_le_sum (fun i _ => hV i) _ = ∑ s : Fin t, ∑ i : ZMod n, w i s := Finset.sum_comm _ ≤ ∑ _s : Fin t, n := Finset.sum_le_sum (fun s _ => hW s) _ = t * n := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] exact Nat.le_of_mul_le_mul_right hmain (NeZero.pos n)