simple_graph_cycle_power_dyadic_cover_class_spanning
Every label class of an optimal m+1-layer cover at dyadic bandwidth is spanned by an endpoint-distance pair: each vertex lies in a class beginning at some offset at most 2^m-1 behind it and containing the corresponding far endpoint.
Statement
theorem simple_graph_cycle_power_dyadic_cover_class_spanning
(m n : ℕ) [NeZero n] (hm : 1 ≤ m)
(hn : 3 * (2 ^ m - 1) + 1 ≤ n)
(c : Fin (m + 1) → ZMod n → ZMod n)
(hc : ∀ s u v, u ≠ v → c s u = c s v →
(simple_graph_cycle_power n (2 ^ m - 1)).Adj u v)
(hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v →
∃ s, c s u = c s v) :
∀ (s : Fin (m + 1)) (v : ZMod n),
∃ a : ℕ, a ≤ 2 ^ m - 1 ∧
c s (v - (a : ZMod n)) = c s v ∧
c s (v - (a : ZMod n)) =
c s (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n))- Source
- Uniform class-model bridge for OP-205 / RT-1 following arXiv:2610.15635. Transfers the proved Boolean tight-class spanning certificate to actual cycle-power cover classes; no research advance is claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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_cycle_power_clique_arcFor n at least 3k+1, every nonempty clique of the k-th cycle power lies in a forward arc of k+1 vertices whose first vertex belongs to the…
- 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…
- 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…
- cycle_power_dyadic_int_weight_le_cardFor a finite integer set of diameter at most 2^m-1, weight its endpoint-distance pairs by two and its other dyadic long-distance pairs by…
- cycle_power_dyadic_tight_class_spanningA nonempty subset attaining equality in the uniform dyadic weight bound contains both endpoints of its arc.
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- 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…
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- Used by 4
- simple_graph_cycle_power_dyadic_class_model_vertex_layersFor an optimal (m+1)-layer dyadic cover, with ell(p) the unique layer covering the endpoint pair (p, p+2^m-1) and the class of p cut to…
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
- simple_graph_cycle_power_dyadic_cover_layer_root_uniqueIn an optimal (m+1)-layer cover of C_n^{2^m-1}, for each layer s and each vertex v, there is a unique offset a ≤ 2^m-1 such that v-a is…
- simple_graph_cycle_power_dyadic_class_model_ordinary_coverFor every distance 1 ≤ d < 2^m and every integer vertex v there is a rooted offset a < 2^m - d whose class is active at both v-a and v-a+d.
The proof, explained
To show that every color class in an optimal (m+1)-layer clique cover of the cycle power C_n^(2^m-1) is spanned by an arc of length 2^m-1, the proof applies a double-counting argument. Summing the dyadic weights across all layers and vertices shows that each layer must achieve maximal weight n, which in turn forces every individual monochromatic color class to achieve maximal weight equal to its size. By the tightness of dyadic class weights, any class achieving this maximum must contain both endpoints of its bounding arc, which provides the desired offset behind any vertex in the class.
For T ⊆ {0, ..., 2^m - 1}, the endpoint offset sum ∑_{a ∈ T} [a + 2^m - 1 ∈ T] equals 1 if 0 ∈ T and 2^m - 1 ∈ T, and 0 otherwise.
If 0 ∈ T and 2^m - 1 ∈ T, then a = 0 gives a valid offset 2^m - 1 ∈ T. Any non-zero element a ∈ T satisfies a ≥ 1, so a + 2^m - 1 ≥ 2^m, which cannot belong to T because all elements of T are strictly less than 2^m. If either 0 ∉ T or 2^m - 1 ∉ T, no term can equal 1, making the sum zero.
uses
Nat.one_le_two_pow,if_pos,Finset.sum_eq_single,if_neg,Finset.sum_eq_zeroclassical have h2m : 1 ≤ 2 ^ m := Nat.one_le_two_pow have hA : (∑ a ∈ T, if a + 2 ^ m - 1 ∈ T then 1 else 0) = if (0 ∈ T ∧ 2 ^ m - 1 ∈ T) then 1 else 0 := by by_cases h : 0 ∈ T ∧ 2 ^ m - 1 ∈ T · rw [if_pos h] rw [Finset.sum_eq_single (0 : ℕ)] · simp [h.2] · intro b hb hb0 have hb_lt := hT b hb have hnot : ¬ (b + 2 ^ m - 1 ∈ T) := by intro hc have hc_lt := hT _ hc omega simp [hnot] · intro h0; exact absurd h.1 h0 · rw [if_neg h] refine Finset.sum_eq_zero ?_ intro a ha have hnot : ¬ (a + 2 ^ m - 1 ∈ T) := by intro hc have ha_lt := hT a ha have hc_lt := hT _ hc have ha0 : a = 0 := by omega subst ha0 exact h ⟨ha, by simpa using hc⟩ simp [hnot]
For each 1 ≤ j < m, the sum ∑_{a ∈ T} [a + 2^m - 2^j ∈ T] equals ∑_{i < 2^j} [i ∈ T ∧ i + 2^m - 2^j ∈ T].
Any element a ∈ T for which a + 2^m - 2^j ∈ T must satisfy a + 2^m - 2^j < 2^m, which implies a < 2^j. Therefore, filtering T for this condition is identical to filtering the range {0, ..., 2^j - 1} for elements in T whose shifted offset also lies in T.
uses
Nat.pow_lt_pow_right,Finset.sum_congr,Finset.card_filter,Finset.mem_filter,Finset.mem_rangehave hB : ∀ j, 1 ≤ j → j < m → (∑ a ∈ T, if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0) = ∑ i ∈ Finset.range (2 ^ j), (decide (i ∈ T) && decide (i + 2 ^ m - 2 ^ j ∈ T)).toNat := by intro j hj1 hjm have hjlt : 2 ^ j < 2 ^ m := Nat.pow_lt_pow_right (by norm_num) hjm have hbterm : ∀ i : ℕ, (decide (i ∈ T) && decide (i + 2 ^ m - 2 ^ j ∈ T)).toNat = if (i ∈ T ∧ i + 2 ^ m - 2 ^ j ∈ T) then 1 else 0 := by intro i by_cases h1 : i ∈ T <;> by_cases h2 : i + 2 ^ m - 2 ^ j ∈ T <;> simp [h1, h2] rw [Finset.sum_congr rfl (fun i _ => hbterm i)] rw [← Finset.card_filter, ← Finset.card_filter] congr 1 ext a simp only [Finset.mem_filter, Finset.mem_range] constructor · rintro ⟨haT, hadT⟩ exact ⟨by have := hT a haT; have := hT _ hadT; omega, haT, hadT⟩ · rintro ⟨_, haT, hadT⟩ exact ⟨haT, hadT⟩
The total offset sum over T equals the dyadic class weight of the indicator vector of T.
Unfolding the definition of cycle_power_dyadic_class_weight, we distribute the summation, factor out the scalar 2, exchange summation orders, and substitute the identities for the endpoint term and the dyadic power terms.
uses
cycle_power_dyadic_class_weight,Finset.sum_add_distrib,Finset.mul_sum,Finset.sum_comm,Finset.sum_congrrw [cycle_power_dyadic_class_weight] rw [Finset.sum_add_distrib] rw [← Finset.mul_sum] rw [Finset.sum_comm] rw [hA] have hsumj : (∑ j ∈ Finset.range m, ∑ a ∈ T, if j = 0 then 0 else if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0) = ∑ j ∈ Finset.range m, if j = 0 then 0 else ∑ i ∈ Finset.range (2 ^ j), (decide (i ∈ T) && decide (i + 2 ^ m - 2 ^ j ∈ T)).toNat := by apply Finset.sum_congr rfl intro j hj by_cases hj0 : j = 0 · simp [hj0] · have hj1 : 1 ≤ j := Nat.one_le_iff_ne_zero.mpr hj0 have hjm : j < m := Finset.mem_range.mp hj rw [if_neg hj0] have hinner : (∑ a ∈ T, if j = 0 then 0 else if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0) = ∑ a ∈ T, if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0 := by apply Finset.sum_congr rfl intro a _ rw [if_neg hj0] rw [hinner] exact hB j hj1 hjm rw [hsumj] have hb : (decide (0 ∈ T) && decide (2 ^ m - 1 ∈ T)).toNat = if (0 ∈ T ∧ 2 ^ m - 1 ∈ T) then 1 else 0 := by by_cases h1 : 0 ∈ T <;> by_cases h2 : 2 ^ m - 1 ∈ T <;> simp [h1, h2] rw [hb]
Any monochromatic fiber F contained in an arc p + [0, 2^m - 1] is in bijection with a subset T ⊆ {0, ..., 2^m - 1}, with |F| = |T|.
Because 2^(m+1) ≤ n, the offset coordinates in {0, ..., 2^m - 1} are strictly smaller than n, making the shift map a ↦ p + a mod n strictly injective on T. Hence F is the image of T under this injection and |F| = |T|.
uses
Nat.pow_le_pow_right,Nat.pow_succ,add_left_cancel,Nat.ModEq.eq_of_lt_of_lt,ZMod.natCast_eq_natCast_iff,Finset.card_image_of_injOnclassical have h2m : 2 ≤ 2 ^ m := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm have hpow : 2 ^ (m+1) = 2 * 2 ^ m := by rw [Nat.pow_succ]; ring have hn2 : 2 ^ (m+1) ≤ n := by omega have hmn : 2 ^ m ≤ n := by omega have hTlt : ∀ a ∈ T, a < 2 ^ m := fun a ha => ((hT a).mp ha).1 have hφinj : Set.InjOn (fun a : ℕ => p + (a : ZMod n)) ↑T := by intro a ha b hb hab have ha_lt : a < n := by have := hTlt a ha; omega have hb_lt : b < n := by have := hTlt b hb; omega have hcast : ((a : ℕ) : ZMod n) = ((b : ℕ) : ZMod n) := add_left_cancel hab exact Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff a b n).mp hcast) ha_lt hb_lt have hF_eq : F = T.image (fun a : ℕ => p + (a : ZMod n)) := by ext u constructor · intro hu obtain ⟨a, ha, heq⟩ := harc u hu have haT : a ∈ T := (hT a).mpr ⟨by omega, by simpa [heq] using hu⟩ exact Finset.mem_image.mpr ⟨a, haT, heq.symm⟩ · intro hu obtain ⟨a, haT, heq⟩ := Finset.mem_image.mp hu simpa [heq] using ((hT a).mp haT).2 have hcard : F.card = T.card := by rw [hF_eq, Finset.card_image_of_injOn hφinj]
For any i ∈ F and offset d, the condition c(i) = c(i + d) is equivalent to i + d ∈ F.
Since F is the fiber {u | c(u) = l} and i ∈ F, we have c(i) = l. Thus c(i + d) equals c(i) if and only if c(i + d) = l, which means i + d ∈ F.
uses
eq_comm,if_pos,if_neg,Finset.sum_congrhave arc_mem : ∀ k : ℕ, k < n → (p + ((k : ℕ) : ZMod n) ∈ F ↔ k ∈ T) := by intro k hk constructor · intro hmem obtain ⟨a, ha, heq⟩ := harc _ hmem have hcast : ((k : ℕ) : ZMod n) = ((a : ℕ) : ZMod n) := add_left_cancel heq have hmod : k ≡ a [MOD n] := (ZMod.natCast_eq_natCast_iff k a n).mp hcast have ha_lt : a < n := by omega have hka : k = a := Nat.ModEq.eq_of_lt_of_lt hmod hk ha_lt exact (hT k).mpr ⟨by omega, hmem⟩ · intro hkT exact ((hT k).mp hkT).2 have hpt : ∀ i ∈ F, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)) = (2 * (if i + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) ∈ F then 1 else 0)) := by intro i hi have hci : c i = l := (hF i).mp hi have key : ∀ z : ZMod n, (c i = c z) ↔ (z ∈ F) := by intro z rw [hci, hF z] exact eq_comm congr 1 · by_cases h : i + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F · rw [if_pos h, if_pos ((key _).mpr h)] · rw [if_neg h, if_neg (fun hc => h ((key _).mp hc))] · apply Finset.sum_congr rfl intro j hj by_cases hj0 : j = 0 · rw [if_pos hj0, if_pos hj0] · rw [if_neg hj0, if_neg hj0] by_cases h : i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) ∈ F · rw [if_pos h, if_pos ((key _).mpr h)] · rw [if_neg h, if_neg (fun hc => h ((key _).mp hc))] refine ⟨hTlt, hcard, ?_⟩
The layer weight sum over fiber F equals the dyadic class weight of its associated index set T.
Transforming the sum over F into a sum over T via the shift bijection, the cyclically shifted points do not wrap around mod n due to the bandwidth bound. Applying the helper lemma simple_graph_cycle_power_dyadic_cover_class_spanning_offset_weight_eq directly equates this sum to cycle_power_dyadic_class_weight m (decide (· ∈ T)).
uses
Finset.sum_congr,Finset.sum_image,Nat.add_sub_assoc,if_congr,simple_graph_cycle_power_dyadic_cover_class_spanning_offset_weight_eqcalc (∑ i ∈ F, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = (∑ i ∈ F, (2 * (if i + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) ∈ F then 1 else 0))) := Finset.sum_congr rfl hpt _ = (∑ a ∈ T, (2 * (if a + 2 ^ m - 1 ∈ T then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0))) := by rw [hF_eq, Finset.sum_image hφinj, ← hF_eq] apply Finset.sum_congr rfl intro a ha have ha_lt : a < 2 ^ m := hTlt a ha have hjle : ∀ j ∈ Finset.range m, j ≤ m := fun j hj => by have := Finset.mem_range.mp hj; omega have hk1 : a + (2 ^ m - 1) < n := by have hd : 2 ^ m - 1 < 2 ^ m := by omega have := Nat.add_lt_add_of_lt_of_le ha_lt (Nat.le_of_lt hd) omega have hconv1 : a + 2 ^ m - 1 = a + (2 ^ m - 1) := by rw [Nat.add_sub_assoc (by omega : 1 ≤ 2 ^ m) a] have e1 : p + (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n) = p + ((a + (2 ^ m - 1) : ℕ) : ZMod n) := by push_cast; ring have h1 : (p + (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F) ↔ (a + (2 ^ m - 1) ∈ T) := by rw [e1]; exact arc_mem (a + (2 ^ m - 1)) hk1 have hsum : ∀ j ∈ Finset.range m, (if j = 0 then 0 else (if p + (a : ZMod n) + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) ∈ F then 1 else 0)) = (if j = 0 then 0 else (if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0)) := by intro j hj by_cases hj0 : j = 0 · rw [if_pos hj0, if_pos hj0] · rw [if_neg hj0, if_neg hj0] have hjd : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) (hjle j hj) have hk2 : a + (2 ^ m - 2 ^ j) < n := by have hd : 2 ^ m - 2 ^ j ≤ 2 ^ m := Nat.sub_le _ _ have := Nat.add_lt_add_of_lt_of_le ha_lt hd omega have hconv2 : a + 2 ^ m - 2 ^ j = a + (2 ^ m - 2 ^ j) := by rw [Nat.add_sub_assoc hjd a] have e2 : p + (a : ZMod n) + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) = p + ((a + (2 ^ m - 2 ^ j) : ℕ) : ZMod n) := by push_cast; ring rw [e2, hconv2] have ham := arc_mem (a + (2 ^ m - 2 ^ j)) hk2 by_cases hh : a + (2 ^ m - 2 ^ j) ∈ T · rw [if_pos (ham.mpr hh), if_pos hh] · rw [if_neg (fun hc => hh (ham.mp hc)), if_neg hh] rw [hconv1] rw [if_congr h1 rfl rfl] congr 1 exact Finset.sum_congr rfl hsum _ = cycle_power_dyadic_class_weight m (fun a => decide (a ∈ T)) := simple_graph_cycle_power_dyadic_cover_class_spanning_offset_weight_eq m hm T hTlt
The sum of boolean indicator values of T over 0 ≤ i < 2^m equals |T|.
Rewriting the boolean indicators as conditional integers (1 if i ∈ T else 0) turns the sum into the cardinality of the filtered range {i < 2^m | i ∈ T}, which equals T since all elements of T are strictly less than 2^m.
uses
Finset.sum_congr,Finset.card_filter,Finset.mem_filter,Finset.mem_rangeclassical have hb : ∀ i, (decide (i ∈ T)).toNat = if i ∈ T then 1 else 0 := by intro i; by_cases h : i ∈ T <;> simp [h] rw [Finset.sum_congr rfl (fun i _ => hb i)] rw [← Finset.card_filter (fun i : ℕ => i ∈ T) (Finset.range (2 ^ m))] congr 1 ext i simp only [Finset.mem_filter, Finset.mem_range] exact ⟨fun h => h.2, fun h => ⟨hT i h, h⟩⟩
The dyadic weight of any monochromatic fiber F in a clique cover layer is at most |F|.
If F is empty, the weight is trivially 0 ≤ 0. If F is nonempty, the clique hypothesis implies that F forms a clique in C_n^(2^m - 1). By simple_graph_cycle_power_clique_arc, F is contained in an arc of length 2^m - 1. Bridging to T, its weight equals the dyadic class weight of T, which is bounded by |T| = |F| by cycle_power_dyadic_class_weight_le.
uses
simple_graph_cycle_power_clique_arc,simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_bridge,cycle_power_dyadic_class_weight_le,simple_graph_cycle_power_dyadic_cover_class_spanning_bool_sum_card,Finset.not_nonempty_iff_eq_emptyclassical by_cases hne : (Finset.univ.filter (fun i => c i = l)).Nonempty · have hclique : ∀ u ∈ Finset.univ.filter (fun i => c i = l), ∀ v ∈ Finset.univ.filter (fun i => c i = l), u ≠ v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v := by intro u hu v hv huv have hu' : c u = l := (Finset.mem_filter.mp hu).2 have hv' : c v = l := (Finset.mem_filter.mp hv).2 exact hc u v huv (hu'.trans hv'.symm) obtain ⟨p, hpF, harc⟩ := simple_graph_cycle_power_clique_arc n (2 ^ m - 1) hn (Finset.univ.filter (fun i => c i = l)) hne hclique set F : Finset (ZMod n) := Finset.univ.filter (fun i => c i = l) with hFdef set T : Finset ℕ := (Finset.range (2 ^ m)).filter (fun a : ℕ => p + (a : ZMod n) ∈ F) with hTdef have hF : ∀ i, i ∈ F ↔ c i = l := by intro i; rw [hFdef]; simp have hTmem : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F := by intro a; rw [hTdef]; simp obtain ⟨hTlt, hcard, hcw⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_bridge m n hm hn c l F hF p hpF harc T hTmem rw [hcw] calc cycle_power_dyadic_class_weight m (fun a => decide (a ∈ T)) ≤ (Finset.range (2 ^ m)).sum (fun i => ((fun a => decide (a ∈ T)) i).toNat) := cycle_power_dyadic_class_weight_le m hm _ _ = T.card := simple_graph_cycle_power_dyadic_cover_class_spanning_bool_sum_card m T hTlt _ = F.card := hcard.symm · rw [Finset.not_nonempty_iff_eq_empty] at hne simp [hne]
If the weight of a nonempty monochromatic fiber F equals |F|, then F contains both endpoints of its arc: p ∈ F and p + 2^m - 1 ∈ F.
Equality of the fiber weight with |F| translates via the bridge lemma to equality of the dyadic class weight of T with |T|. By cycle_power_dyadic_tight_class_spanning, achieving this upper bound forces 0 ∈ T and 2^m - 1 ∈ T, which corresponds back to p ∈ F and p + 2^m - 1 ∈ F.
uses
simple_graph_cycle_power_clique_arc,simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_bridge,simple_graph_cycle_power_dyadic_cover_class_spanning_bool_sum_card,cycle_power_dyadic_tight_class_spanning,of_decide_eq_trueclassical have h2m : 2 ≤ 2 ^ m := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm have hclique : ∀ u ∈ Finset.univ.filter (fun i => c i = l), ∀ v ∈ Finset.univ.filter (fun i => c i = l), u ≠ v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v := by intro u hu v hv huv have hu' : c u = l := (Finset.mem_filter.mp hu).2 have hv' : c v = l := (Finset.mem_filter.mp hv).2 exact hc u v huv (hu'.trans hv'.symm) obtain ⟨p, hpF, harc⟩ := simple_graph_cycle_power_clique_arc n (2 ^ m - 1) hn (Finset.univ.filter (fun i => c i = l)) hne hclique set F : Finset (ZMod n) := Finset.univ.filter (fun i => c i = l) with hFdef set T : Finset ℕ := (Finset.range (2 ^ m)).filter (fun a : ℕ => p + (a : ZMod n) ∈ F) with hTdef have hF : ∀ i, i ∈ F ↔ c i = l := by intro i; rw [hFdef]; simp have hTmem : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F := by intro a; rw [hTdef]; simp obtain ⟨hTlt, hcard, hcw⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_bridge m n hm hn c l F hF p hpF harc T hTmem have hsumcard : (∑ i ∈ Finset.range (2 ^ m), (decide (i ∈ T)).toNat) = T.card := simple_graph_cycle_power_dyadic_cover_class_spanning_bool_sum_card m T hTlt have hcw' : cycle_power_dyadic_class_weight m (fun a => decide (a ∈ T)) = (Finset.range (2 ^ m)).sum (fun i => ((fun a => decide (a ∈ T)) i).toNat) := by rw [← hcw, hwt, hcard, ← hsumcard] have hne_b : ∃ i < 2 ^ m, (fun a => decide (a ∈ T)) i = true := by refine ⟨0, by omega, ?_⟩ have h0T : 0 ∈ T := (hTmem 0).mpr ⟨by omega, by simpa using hpF⟩ simp [h0T] obtain ⟨hb0, hbD⟩ := cycle_power_dyadic_tight_class_spanning m hm (fun a => decide (a ∈ T)) hcw' hne_b have h0T : 0 ∈ T := of_decide_eq_true hb0 have hDT : 2 ^ m - 1 ∈ T := of_decide_eq_true hbD have hpF' : p ∈ F := by simpa using ((hTmem 0).mp h0T).2 have hpD' : p + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F := ((hTmem (2 ^ m - 1)).mp hDT).2 exact ⟨p, hpF', hpD', harc⟩
The offsets 2^m - 1 and 2^m - 2^j are edges of the cycle power graph, so every vertex-offset pair is covered by at least one layer.
The bandwidth condition 2^m - 1 < n ensures that distance 2^m - 1 and all dyadic sub-distances 2^m - 2^j (for 1 ≤ j < m) are strictly positive and at most 2^m - 1. By the graph covering hypothesis, each of these edges must be monochromatic in at least one of the m+1 layers.
uses
simple_graph_cycle_power_adj_iff_of_bandwidth_lt,Nat.pow_lt_pow_right,Nat.one_le_two_pow,abs_of_nonnegclassical let d0 : ZMod n := ((2 ^ m - 1 : ℕ) : ZMod n) let D : ℕ → ZMod n := fun j => ((2 ^ m - 2 ^ j : ℕ) : ZMod n) let I0 : Fin (m + 1) → ZMod n → ℕ := fun s i => if c s i = c s (i + d0) then 1 else 0 let Ij : Fin (m + 1) → ℕ → ZMod n → ℕ := fun s j i => if c s i = c s (i + D j) then 1 else 0 let W : Fin (m + 1) → ℕ := fun s => ∑ i : ZMod n, (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)) let N0 : ZMod n → ℕ := fun i => ∑ s : Fin (m+1), I0 s i let Nj : ℕ → ZMod n → ℕ := fun j i => ∑ s : Fin (m+1), Ij s j i let J : Finset ℕ := (Finset.range m).filter (fun j => j ≠ 0) have hk_lt : 2 ^ m - 1 < n := by have hge : 1 ≤ 2 ^ m - 1 := by have h2 : 2 ≤ 2 ^ m := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm omega omega have hadj0 : ∀ i : ZMod n, (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + d0) := by intro i rw [show d0 = ((2 ^ m - 1 : ℕ) : ZMod n) from rfl] rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hk_lt] refine ⟨((2 ^ m - 1 : ℕ) : ℤ), ?_, ?_, ?_⟩ · have hge : 0 < 2 ^ m - 1 := by have h2 : 2 ≤ 2 ^ m := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm omega omega · rw [abs_of_nonneg (by positivity : (0:ℤ) ≤ ((2 ^ m - 1 : ℕ) : ℤ))] · push_cast; ring have hadjJ : ∀ (j : ℕ), j < m → ∀ i : ZMod n, (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + D j) := by intro j hj i rw [show D j = ((2 ^ m - 2 ^ j : ℕ) : ZMod n) from rfl] rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hk_lt] refine ⟨((2 ^ m - 2 ^ j : ℕ) : ℤ), ?_, ?_, ?_⟩ · have hpos : 0 < 2 ^ m - 2 ^ j := Nat.sub_pos_of_lt (Nat.pow_lt_pow_right (by norm_num) hj) omega · have hle : 2 ^ m - 2 ^ j ≤ 2 ^ m - 1 := by have : 1 ≤ 2 ^ j := Nat.one_le_two_pow omega have hnn : (0:ℤ) ≤ ((2 ^ m - 2 ^ j : ℕ) : ℤ) := by positivity rw [abs_of_nonneg hnn] exact_mod_cast hle · push_cast; ring have hcov0 : ∀ i : ZMod n, ∃ s : Fin (m+1), c s i = c s (i + d0) := fun i => hcov i (i + d0) (hadj0 i) have hcovJ : ∀ j ∈ J, ∀ i : ZMod n, ∃ s : Fin (m+1), c s i = c s (i + D j) := by intro j hj i have hjm : j < m := by have hh : j ∈ (Finset.range m).filter (fun j => j ≠ 0) := hj rw [Finset.mem_filter, Finset.mem_range] at hh exact hh.1 exact hcov i (i + D j) (hadjJ j hjm i)
The sum of layer weights over all m+1 layers equals exactly (m+1)n.
From above, each layer weight W(s) is at most n by simple_graph_cycle_power_dyadic_layer_weight_le, giving ∑_s W(s) ≤ (m+1)n. From below, swapping the summation order expresses the total weight as a sum over vertices i of (2 * N_0(i) + ∑_{j=1}^{m-1} N_j(j, i)), where each edge is covered at least once. This gives at least 2 + (m-1) = m+1 per vertex, yielding ∑_s W(s) ≥ (m+1)n. By antisymmetry, the sum is exactly (m+1)n.
uses
simple_graph_cycle_power_dyadic_layer_weight_le,Finset.sum_le_sum,Finset.sum_const,Finset.card_univ,Fintype.card_fin,Nat.nsmul_eq_mul,Finset.sum_add_distrib,Finset.mul_sum,Finset.sum_comm,Finset.sum_ite_irrel,Finset.card_erase_of_mem,Finset.single_le_sum,Finset.sum_filter,ZMod.card,Nat.mul_comm,le_antisymmhave hW_le : ∀ s : Fin (m+1), W s ≤ n := fun s => simple_graph_cycle_power_dyadic_layer_weight_le m n hm hn (c s) (hc s) have hsum_le : ∑ s : Fin (m+1), W s ≤ (m+1) * n := by have h := Finset.sum_le_sum (fun s (_ : s ∈ (Finset.univ : Finset (Fin (m+1)))) => hW_le s) simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] at h exact h have hT_split : ∀ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) = 2 * N0 i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i) := by intro i rw [Finset.sum_add_distrib] rw [show (∑ s : Fin (m+1), 2 * I0 s i) = 2 * N0 i by rw [Finset.mul_sum]] congr 1 rw [Finset.sum_comm] apply Finset.sum_congr rfl intro j hj rw [Finset.sum_ite_irrel] by_cases h : j = 0 · simp [h] · simp only [if_neg h]; rfl have hJcard : J.card = m - 1 := by have hmem : 0 ∈ Finset.range m := by rw [Finset.mem_range]; omega simp only [J, Finset.filter_ne', Finset.card_erase_of_mem hmem, Finset.card_range] have hN0_ge : ∀ i, 1 ≤ N0 i := by intro i rcases hcov0 i with ⟨s, hs⟩ have h := Finset.single_le_sum (f := fun x => I0 x i) (fun _ _ => Nat.zero_le _) (Finset.mem_univ s) rwa [show I0 s i = 1 by simp [I0, hs]] at h have hNJ_ge : ∀ j ∈ J, ∀ i, 1 ≤ Nj j i := by intro j hj i rcases hcovJ j hj i with ⟨s, hs⟩ have h := Finset.single_le_sum (f := fun x => Ij x j i) (fun _ _ => Nat.zero_le _) (Finset.mem_univ s) rwa [show Ij s j i = 1 by simp [Ij, hs]] at h have hJsum : ∀ i, (∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i)) = ∑ j ∈ J, Nj j i := by intro i change (∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i)) = ∑ j ∈ (Finset.range m).filter (fun j => j ≠ 0), Nj j i rw [Finset.sum_filter] apply Finset.sum_congr rfl intro j hj by_cases h : j = 0 <;> simp [h] have hT_ge : ∀ i, m + 1 ≤ ∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)) := by intro i rw [hT_split i, hJsum i] have hle : J.card ≤ ∑ j ∈ J, Nj j i := by have h := Finset.sum_le_sum (fun j hj => hNJ_ge j hj i) simpa using h have hn0 := hN0_ge i omega have hsumT : ∑ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) = ∑ s : Fin (m+1), W s := by simp only [W] rw [Finset.sum_comm] have hsum_ge : (m+1) * n ≤ ∑ s : Fin (m+1), W s := by rw [← hsumT] have h := Finset.sum_le_sum (fun i (_ : i ∈ (Finset.univ : Finset (ZMod n))) => hT_ge i) have hc : ∑ _i : ZMod n, (m+1) = (m+1) * n := by rw [Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm] rw [hc] at h exact h have hsum_eq : ∑ s : Fin (m+1), W s = (m+1) * n := le_antisymm hsum_le hsum_ge
Every individual layer s achieves maximal dyadic weight W(s) = n.
Since each layer satisfies W(s) ≤ n and their sum across all m+1 layers equals (m+1)n, if any layer had weight strictly less than n, the total sum would be strictly less than (m+1)n, a contradiction.
uses
lt_of_le_of_ne,Finset.sum_const,Finset.card_univ,Fintype.card_fin,Nat.nsmul_eq_mul,Finset.sum_lt_sum,lt_irreflintro s by_contra hne have hlt : W s < n := lt_of_le_of_ne (hW_le s) hne have hconst : ∑ _x : Fin (m+1), n = (m+1) * n := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] have hstrict : ∑ x : Fin (m+1), W x < ∑ _x : Fin (m+1), n := Finset.sum_lt_sum (fun x _ => hW_le x) ⟨s, Finset.mem_univ s, hlt⟩ rw [hconst, hsum_eq] at hstrict exact lt_irrefl _ hstrict
In each layer, every monochromatic color class achieves weight equal to its cardinality.
Partitioning the vertex sum of layer s into fiberwise sums over color classes, the sum of class weights is n, which equals the sum of class sizes. Since each individual class weight is bounded above by its cardinality, equality must hold for every class.
uses
simple_graph_cycle_power_dyadic_cover_class_spanning_layer_weight_eq,Finset.sum_fiberwise,Finset.card_eq_sum_card_fiberwise,simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_wt_le_card,Finset.sum_eq_sum_iff_of_leclassical have hlayer := simple_graph_cycle_power_dyadic_cover_class_spanning_layer_weight_eq m n hm hn c hc hcov intro s v have hsum_eq : (∑ l : ZMod n, (∑ i ∈ Finset.univ.filter (fun i => c s i = l), (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)))) = n := by rw [Finset.sum_fiberwise] simpa using hlayer s have hcard_eq : (∑ l : ZMod n, (Finset.univ.filter (fun i => c s i = l)).card) = n := by rw [← Finset.card_eq_sum_card_fiberwise (s := Finset.univ) (t := Finset.univ) (f := c s) (by intro x _; simp)] simp have hle : ∀ l, (∑ i ∈ Finset.univ.filter (fun i => c s i = l), (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) ≤ (Finset.univ.filter (fun i => c s i = l)).card := by intro l exact simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_wt_le_card m n hm hn (c s) (hc s) l have heq_each : ∀ l, (∑ i ∈ Finset.univ.filter (fun i => c s i = l), (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = (Finset.univ.filter (fun i => c s i = l)).card := by intro l have hall := (Finset.sum_eq_sum_iff_of_le (s := (Finset.univ : Finset (ZMod n))) (f := fun l => ∑ i ∈ Finset.univ.filter (fun i => c s i = l), (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) (g := fun l => (Finset.univ.filter (fun i => c s i = l)).card) (fun l _ => hle l)).mp (by rw [hsum_eq, hcard_eq]) exact hall l (Finset.mem_univ l)
For any vertex v and layer s, there is an offset a ≤ 2^m - 1 such that v - a and v - a + 2^m - 1 both belong to v's color class.
The color class of v is nonempty because it contains v, and achieves maximal weight. By the fiber endpoints lemma, this class is an arc starting at some p that contains both p and p + 2^m - 1. Because v belongs to this arc, v = p + a for some offset a ≤ 2^m - 1, meaning p = v - a, which verifies the claim.
uses
simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_endpoints,add_sub_cancel_righthave hl := heq_each (c s v) have hnev : (Finset.univ.filter (fun i => c s i = c s v)).Nonempty := ⟨v, by simp⟩ obtain ⟨p, hpF, hpD, harc⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_endpoints m n hm hn (c s) (hc s) (c s v) hnev hl have hvF : v ∈ Finset.univ.filter (fun i => c s i = c s v) := by simp obtain ⟨a0, ha0le, ha0eq⟩ := harc v hvF refine ⟨a0, ha0le, ?_, ?_⟩ · have hvc : v - (a0 : ZMod n) = p := by rw [ha0eq, add_sub_cancel_right] rw [hvc] exact (Finset.mem_filter.mp hpF).2 · have hvc : v - (a0 : ZMod n) = p := by rw [ha0eq, add_sub_cancel_right] rw [hvc] exact ((Finset.mem_filter.mp hpF).2).trans ((Finset.mem_filter.mp hpD).2).symm
Nat.one_le_two_pow- Every power of 2 is at least 1.
if_pos- An if-then-else evaluates to its first branch when the condition is true.
if_neg- An if-then-else evaluates to its second branch when the condition is false.
Finset.sum_eq_single- A finite sum is determined by a single nonzero term if all other terms are zero.
Finset.sum_eq_zero- A finite sum is zero if every summand is zero.
Nat.pow_lt_pow_right- Strict monotonicity of powers with base greater than 1.
Nat.pow_le_pow_right- Weak monotonicity of powers.
Nat.pow_succ- Successor identity for powers: a^(m+1) = a^m * a.
Finset.sum_congr- Two finite sums are equal if their index sets and summands agree.
Finset.card_filter- The size of a filtered subset equals the sum of indicator values of the predicate.
Finset.mem_filter- Characterization of elements in a filtered subset.
Finset.mem_range- Characterization of membership in Finset.range n as being strictly less than n.
cycle_power_dyadic_class_weight- Definition of the dyadic class weight of a boolean vector.
Finset.sum_add_distrib- Distributivity of finite sums over addition.
Finset.mul_sum- Factoring a constant multiple out of a finite sum.
Finset.sum_comm- Fubini's theorem: exchanging the order of summation in a double finite sum.
add_left_cancel- Left cancellation in an additive group: a + b = a + c implies b = c.
Nat.ModEq.eq_of_lt_of_lt- Two integers smaller than the modulus that are congruent modulo m must be equal.
ZMod.natCast_eq_natCast_iff- Two natural numbers have equal casts in ZMod n iff they are congruent modulo n.
Finset.card_image_of_injOn- The image of a finite set under an injective map has the same cardinality.
eq_comm- Symmetry of equality: a = b iff b = a.
Finset.sum_image- Summing a function over the image of an injective map equals summing the composite function over the domain.
Nat.add_sub_assoc- Associativity of natural addition and subtraction when subtracting a smaller number.
if_congr- Congruence of if-then-else expressions under equivalent conditions and equal branches.
simple_graph_cycle_power_clique_arc- In a cycle power graph C_n^k with 3k+1 <= n, any clique is contained in an arc of length at most k starting at some clique vertex.
cycle_power_dyadic_class_weight_le- The dyadic class weight of any boolean vector is bounded above by its Hamming weight (sum of 1s).
cycle_power_dyadic_tight_class_spanning- Tightness condition: if the dyadic class weight of a nonzero boolean vector achieves its maximum, its first and last entries must be true.
of_decide_eq_true- Extracting the underlying proposition from a decide expression returning true.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty iff it is the empty set.
simple_graph_cycle_power_adj_iff_of_bandwidth_lt- In C_n^k with k < n, adjacency between u and v is equivalent to v - u being a nonzero integer offset of absolute value at most k.
abs_of_nonneg- The absolute value of a non-negative integer is itself.
simple_graph_cycle_power_dyadic_layer_weight_le- In a cycle power clique cover, the dyadic layer weight of each individual layer is at most n.
Finset.sum_le_sum- Monotonicity of finite sums: if each term is bounded, the sum is bounded.
Finset.sum_const- The sum of a constant over a finite set equals the cardinality times the constant.
Finset.card_univ- The cardinality of the universal finset is the cardinality of the finite type.
Fintype.card_fin- The cardinality of Fin n is n.
Nat.nsmul_eq_mul- Scalar multiplication by a natural number on naturals is standard multiplication.
Finset.sum_ite_irrel- Pushing summation inside an if-then-else when the condition does not depend on the summation variable.
Finset.card_erase_of_mem- Erasing an element from a finite set decreases its cardinality by 1.
Finset.single_le_sum- A single non-negative term is bounded by the total finite sum.
Finset.sum_filter- Restricting a sum to a filtered subset equals summing an if-then-else indicator over the whole set.
ZMod.card- The cardinality of ZMod n is n.
Nat.mul_comm- Commutativity of natural multiplication: n * m = m * n.
le_antisymm- Antisymmetry of inequality: a <= b and b <= a implies a = b.
lt_of_le_of_ne- If a <= b and a != b, then a < b.
Finset.sum_lt_sum- A sum of weakly smaller terms with at least one strictly smaller term is strictly smaller.
lt_irrefl- Irreflexivity of strict inequality: no number is strictly less than itself.
Finset.sum_fiberwise- Partitioning a sum over a finite set into a sum over the fibers of a function.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum of the cardinalities of the fibers of any map on it.
Finset.sum_eq_sum_iff_of_le- If f(i) <= g(i) everywhere, their sums over a set are equal iff f(i) = g(i) everywhere.
add_sub_cancel_right- Right cancellation in an additive group: (a + b) - b = a.
simple_graph_cycle_power_dyadic_cover_class_spanning_offset_weight_eq- Helper equating offset indicator sums over a subset of [0, 2^m) to the dyadic class weight.
simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_bridge- Helper showing a monochromatic fiber contained in an arc matches an offset set T and has identical weight.
simple_graph_cycle_power_dyadic_cover_class_spanning_bool_sum_card- Helper showing that the sum of boolean indicators over [0, 2^m) equals the set cardinality |T|.
simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_wt_le_card- Helper showing the dyadic weight of any monochromatic fiber is at most its cardinality.
simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_endpoints- Helper showing that maximal weight on a monochromatic fiber forces both arc endpoints into the fiber.
simple_graph_cycle_power_dyadic_cover_class_spanning_layer_weight_eq- Helper showing that every layer in an (m+1)-layer cover achieves maximal dyadic weight n.
- The proof represents cycle vertices in ZMod n and uses the hypothesis 3 * (2^m - 1) + 1 ≤ n so that cliques cannot wrap around the cycle, ensuring each monochromatic clique is an interval arc.
- Intermediate helper lemmas translate the sum over graph vertices and color classes into an abstract boolean dyadic class weight where extremal inequalities have already been established.
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.
Lean’s trace was cut to the first 400 of 449 tactics.
set_option maxHeartbeats 3000000private theorem simple_graph_cycle_power_dyadic_cover_class_spanning_offset_weight_eq (m : ℕ) (_hm : 1 ≤ m) (T : Finset ℕ) (hT : ∀ a ∈ T, a < 2 ^ m) : (∑ a ∈ T, (2 * (if a + 2 ^ m - 1 ∈ T then 1 else 0) + ∑ j ∈ Finset.range m, if j = 0 then 0 else if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0)) = cycle_power_dyadic_class_weight m (fun a => decide (a ∈ T)) := by classical have h2m : 1 ≤ 2 ^ m := Nat.one_le_two_pow have hA : (∑ a ∈ T, if a + 2 ^ m - 1 ∈ T then 1 else 0) = if (0 ∈ T ∧ 2 ^ m - 1 ∈ T) then 1 else 0 := by by_cases h : 0 ∈ T ∧ 2 ^ m - 1 ∈ T · rw [if_pos h] rw [Finset.sum_eq_single (0 : ℕ)] · simp [h.2] · intro b hb hb0 have hb_lt := hT b hb have hnot : ¬ (b + 2 ^ m - 1 ∈ T) := by intro hc have hc_lt := hT _ hc omega simp [hnot] · intro h0; exact absurd h.1 h0 · rw [if_neg h] refine Finset.sum_eq_zero ?_ intro a ha have hnot : ¬ (a + 2 ^ m - 1 ∈ T) := by intro hc have ha_lt := hT a ha have hc_lt := hT _ hc have ha0 : a = 0 := by omega subst ha0 exact h ⟨ha, by simpa using hc⟩ simp [hnot] have hB : ∀ j, 1 ≤ j → j < m → (∑ a ∈ T, if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0) = ∑ i ∈ Finset.range (2 ^ j), (decide (i ∈ T) && decide (i + 2 ^ m - 2 ^ j ∈ T)).toNat := by intro j hj1 hjm have hjlt : 2 ^ j < 2 ^ m := Nat.pow_lt_pow_right (by norm_num) hjm have hbterm : ∀ i : ℕ, (decide (i ∈ T) && decide (i + 2 ^ m - 2 ^ j ∈ T)).toNat = if (i ∈ T ∧ i + 2 ^ m - 2 ^ j ∈ T) then 1 else 0 := by intro i by_cases h1 : i ∈ T <;> by_cases h2 : i + 2 ^ m - 2 ^ j ∈ T <;> simp [h1, h2] rw [Finset.sum_congr rfl (fun i _ => hbterm i)] rw [← Finset.card_filter, ← Finset.card_filter] congr 1 ext a simp only [Finset.mem_filter, Finset.mem_range] constructor · rintro ⟨haT, hadT⟩ exact ⟨by have := hT a haT; have := hT _ hadT; omega, haT, hadT⟩ · rintro ⟨_, haT, hadT⟩ exact ⟨haT, hadT⟩ rw [cycle_power_dyadic_class_weight] rw [Finset.sum_add_distrib] rw [← Finset.mul_sum] rw [Finset.sum_comm] rw [hA] have hsumj : (∑ j ∈ Finset.range m, ∑ a ∈ T, if j = 0 then 0 else if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0) = ∑ j ∈ Finset.range m, if j = 0 then 0 else ∑ i ∈ Finset.range (2 ^ j), (decide (i ∈ T) && decide (i + 2 ^ m - 2 ^ j ∈ T)).toNat := by apply Finset.sum_congr rfl intro j hj by_cases hj0 : j = 0 · simp [hj0] · have hj1 : 1 ≤ j := Nat.one_le_iff_ne_zero.mpr hj0 have hjm : j < m := Finset.mem_range.mp hj rw [if_neg hj0] have hinner : (∑ a ∈ T, if j = 0 then 0 else if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0) = ∑ a ∈ T, if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0 := by apply Finset.sum_congr rfl intro a _ rw [if_neg hj0] rw [hinner] exact hB j hj1 hjm rw [hsumj] have hb : (decide (0 ∈ T) && decide (2 ^ m - 1 ∈ T)).toNat = if (0 ∈ T ∧ 2 ^ m - 1 ∈ T) then 1 else 0 := by by_cases h1 : 0 ∈ T <;> by_cases h2 : 2 ^ m - 1 ∈ T <;> simp [h1, h2] rw [hb]private theorem simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_bridge (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : ZMod n → ZMod n) (l : ZMod n) (F : Finset (ZMod n)) (hF : ∀ i, i ∈ F ↔ c i = l) (p : ZMod n) (_hpF : p ∈ F) (harc : ∀ u ∈ F, ∃ a : ℕ, a ≤ 2 ^ m - 1 ∧ u = p + (a : ZMod n)) (T : Finset ℕ) (hT : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F) : (∀ a ∈ T, a < 2 ^ m) ∧ F.card = T.card ∧ (∑ i ∈ F, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = cycle_power_dyadic_class_weight m (fun a => decide (a ∈ T)) := by classical have h2m : 2 ≤ 2 ^ m := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm have hpow : 2 ^ (m+1) = 2 * 2 ^ m := by rw [Nat.pow_succ]; ring have hn2 : 2 ^ (m+1) ≤ n := by omega have hmn : 2 ^ m ≤ n := by omega have hTlt : ∀ a ∈ T, a < 2 ^ m := fun a ha => ((hT a).mp ha).1 have hφinj : Set.InjOn (fun a : ℕ => p + (a : ZMod n)) ↑T := by intro a ha b hb hab have ha_lt : a < n := by have := hTlt a ha; omega have hb_lt : b < n := by have := hTlt b hb; omega have hcast : ((a : ℕ) : ZMod n) = ((b : ℕ) : ZMod n) := add_left_cancel hab exact Nat.ModEq.eq_of_lt_of_lt ((ZMod.natCast_eq_natCast_iff a b n).mp hcast) ha_lt hb_lt have hF_eq : F = T.image (fun a : ℕ => p + (a : ZMod n)) := by ext u constructor · intro hu obtain ⟨a, ha, heq⟩ := harc u hu have haT : a ∈ T := (hT a).mpr ⟨by omega, by simpa [heq] using hu⟩ exact Finset.mem_image.mpr ⟨a, haT, heq.symm⟩ · intro hu obtain ⟨a, haT, heq⟩ := Finset.mem_image.mp hu simpa [heq] using ((hT a).mp haT).2 have hcard : F.card = T.card := by rw [hF_eq, Finset.card_image_of_injOn hφinj] have arc_mem : ∀ k : ℕ, k < n → (p + ((k : ℕ) : ZMod n) ∈ F ↔ k ∈ T) := by intro k hk constructor · intro hmem obtain ⟨a, ha, heq⟩ := harc _ hmem have hcast : ((k : ℕ) : ZMod n) = ((a : ℕ) : ZMod n) := add_left_cancel heq have hmod : k ≡ a [MOD n] := (ZMod.natCast_eq_natCast_iff k a n).mp hcast have ha_lt : a < n := by omega have hka : k = a := Nat.ModEq.eq_of_lt_of_lt hmod hk ha_lt exact (hT k).mpr ⟨by omega, hmem⟩ · intro hkT exact ((hT k).mp hkT).2 have hpt : ∀ i ∈ F, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)) = (2 * (if i + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) ∈ F then 1 else 0)) := by intro i hi have hci : c i = l := (hF i).mp hi have key : ∀ z : ZMod n, (c i = c z) ↔ (z ∈ F) := by intro z rw [hci, hF z] exact eq_comm congr 1 · by_cases h : i + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F · rw [if_pos h, if_pos ((key _).mpr h)] · rw [if_neg h, if_neg (fun hc => h ((key _).mp hc))] · apply Finset.sum_congr rfl intro j hj by_cases hj0 : j = 0 · rw [if_pos hj0, if_pos hj0] · rw [if_neg hj0, if_neg hj0] by_cases h : i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) ∈ F · rw [if_pos h, if_pos ((key _).mpr h)] · rw [if_neg h, if_neg (fun hc => h ((key _).mp hc))] refine ⟨hTlt, hcard, ?_⟩ calc (∑ i ∈ F, (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = (∑ i ∈ F, (2 * (if i + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) ∈ F then 1 else 0))) := Finset.sum_congr rfl hpt _ = (∑ a ∈ T, (2 * (if a + 2 ^ m - 1 ∈ T then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0))) := by rw [hF_eq, Finset.sum_image hφinj, ← hF_eq] apply Finset.sum_congr rfl intro a ha have ha_lt : a < 2 ^ m := hTlt a ha have hjle : ∀ j ∈ Finset.range m, j ≤ m := fun j hj => by have := Finset.mem_range.mp hj; omega have hk1 : a + (2 ^ m - 1) < n := by have hd : 2 ^ m - 1 < 2 ^ m := by omega have := Nat.add_lt_add_of_lt_of_le ha_lt (Nat.le_of_lt hd) omega have hconv1 : a + 2 ^ m - 1 = a + (2 ^ m - 1) := by rw [Nat.add_sub_assoc (by omega : 1 ≤ 2 ^ m) a] have e1 : p + (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n) = p + ((a + (2 ^ m - 1) : ℕ) : ZMod n) := by push_cast; ring have h1 : (p + (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F) ↔ (a + (2 ^ m - 1) ∈ T) := by rw [e1]; exact arc_mem (a + (2 ^ m - 1)) hk1 have hsum : ∀ j ∈ Finset.range m, (if j = 0 then 0 else (if p + (a : ZMod n) + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) ∈ F then 1 else 0)) = (if j = 0 then 0 else (if a + 2 ^ m - 2 ^ j ∈ T then 1 else 0)) := by intro j hj by_cases hj0 : j = 0 · rw [if_pos hj0, if_pos hj0] · rw [if_neg hj0, if_neg hj0] have hjd : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) (hjle j hj) have hk2 : a + (2 ^ m - 2 ^ j) < n := by have hd : 2 ^ m - 2 ^ j ≤ 2 ^ m := Nat.sub_le _ _ have := Nat.add_lt_add_of_lt_of_le ha_lt hd omega have hconv2 : a + 2 ^ m - 2 ^ j = a + (2 ^ m - 2 ^ j) := by rw [Nat.add_sub_assoc hjd a] have e2 : p + (a : ZMod n) + ((2 ^ m - 2 ^ j : ℕ) : ZMod n) = p + ((a + (2 ^ m - 2 ^ j) : ℕ) : ZMod n) := by push_cast; ring rw [e2, hconv2] have ham := arc_mem (a + (2 ^ m - 2 ^ j)) hk2 by_cases hh : a + (2 ^ m - 2 ^ j) ∈ T · rw [if_pos (ham.mpr hh), if_pos hh] · rw [if_neg (fun hc => hh (ham.mp hc)), if_neg hh] rw [hconv1] rw [if_congr h1 rfl rfl] congr 1 exact Finset.sum_congr rfl hsum _ = cycle_power_dyadic_class_weight m (fun a => decide (a ∈ T)) := simple_graph_cycle_power_dyadic_cover_class_spanning_offset_weight_eq m hm T hTltprivate theorem simple_graph_cycle_power_dyadic_cover_class_spanning_bool_sum_card (m : ℕ) (T : Finset ℕ) (hT : ∀ a ∈ T, a < 2 ^ m) : (∑ i ∈ Finset.range (2 ^ m), (decide (i ∈ T)).toNat) = T.card := by classical have hb : ∀ i, (decide (i ∈ T)).toNat = if i ∈ T then 1 else 0 := by intro i; by_cases h : i ∈ T <;> simp [h] rw [Finset.sum_congr rfl (fun i _ => hb i)] rw [← Finset.card_filter (fun i : ℕ => i ∈ T) (Finset.range (2 ^ m))] congr 1 ext i simp only [Finset.mem_filter, Finset.mem_range] exact ⟨fun h => h.2, fun h => ⟨hT i h, h⟩⟩private theorem simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_wt_le_card (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) (l : ZMod n) : (∑ i ∈ Finset.univ.filter (fun i => c i = l), (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) ≤ (Finset.univ.filter (fun i => c i = l)).card := by classical by_cases hne : (Finset.univ.filter (fun i => c i = l)).Nonempty · have hclique : ∀ u ∈ Finset.univ.filter (fun i => c i = l), ∀ v ∈ Finset.univ.filter (fun i => c i = l), u ≠ v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v := by intro u hu v hv huv have hu' : c u = l := (Finset.mem_filter.mp hu).2 have hv' : c v = l := (Finset.mem_filter.mp hv).2 exact hc u v huv (hu'.trans hv'.symm) obtain ⟨p, hpF, harc⟩ := simple_graph_cycle_power_clique_arc n (2 ^ m - 1) hn (Finset.univ.filter (fun i => c i = l)) hne hclique set F : Finset (ZMod n) := Finset.univ.filter (fun i => c i = l) with hFdef set T : Finset ℕ := (Finset.range (2 ^ m)).filter (fun a : ℕ => p + (a : ZMod n) ∈ F) with hTdef have hF : ∀ i, i ∈ F ↔ c i = l := by intro i; rw [hFdef]; simp have hTmem : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F := by intro a; rw [hTdef]; simp obtain ⟨hTlt, hcard, hcw⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_bridge m n hm hn c l F hF p hpF harc T hTmem rw [hcw] calc cycle_power_dyadic_class_weight m (fun a => decide (a ∈ T)) ≤ (Finset.range (2 ^ m)).sum (fun i => ((fun a => decide (a ∈ T)) i).toNat) := cycle_power_dyadic_class_weight_le m hm _ _ = T.card := simple_graph_cycle_power_dyadic_cover_class_spanning_bool_sum_card m T hTlt _ = F.card := hcard.symm · rw [Finset.not_nonempty_iff_eq_empty] at hne simp [hne]private theorem simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_endpoints (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : ZMod n → ZMod n) (hc : ∀ u v, u ≠ v → c u = c v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) (l : ZMod n) (hne : (Finset.univ.filter (fun i => c i = l)).Nonempty) (hwt : (∑ i ∈ Finset.univ.filter (fun i => c i = l), (2 * (if c i = c (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c i = c (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = (Finset.univ.filter (fun i => c i = l)).card) : ∃ p : ZMod n, p ∈ (Finset.univ.filter (fun i => c i = l)) ∧ p + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ (Finset.univ.filter (fun i => c i = l)) ∧ (∀ u ∈ (Finset.univ.filter (fun i => c i = l)), ∃ a : ℕ, a ≤ 2 ^ m - 1 ∧ u = p + (a : ZMod n)) := by classical have h2m : 2 ≤ 2 ^ m := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm have hclique : ∀ u ∈ Finset.univ.filter (fun i => c i = l), ∀ v ∈ Finset.univ.filter (fun i => c i = l), u ≠ v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v := by intro u hu v hv huv have hu' : c u = l := (Finset.mem_filter.mp hu).2 have hv' : c v = l := (Finset.mem_filter.mp hv).2 exact hc u v huv (hu'.trans hv'.symm) obtain ⟨p, hpF, harc⟩ := simple_graph_cycle_power_clique_arc n (2 ^ m - 1) hn (Finset.univ.filter (fun i => c i = l)) hne hclique set F : Finset (ZMod n) := Finset.univ.filter (fun i => c i = l) with hFdef set T : Finset ℕ := (Finset.range (2 ^ m)).filter (fun a : ℕ => p + (a : ZMod n) ∈ F) with hTdef have hF : ∀ i, i ∈ F ↔ c i = l := by intro i; rw [hFdef]; simp have hTmem : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F := by intro a; rw [hTdef]; simp obtain ⟨hTlt, hcard, hcw⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_bridge m n hm hn c l F hF p hpF harc T hTmem have hsumcard : (∑ i ∈ Finset.range (2 ^ m), (decide (i ∈ T)).toNat) = T.card := simple_graph_cycle_power_dyadic_cover_class_spanning_bool_sum_card m T hTlt have hcw' : cycle_power_dyadic_class_weight m (fun a => decide (a ∈ T)) = (Finset.range (2 ^ m)).sum (fun i => ((fun a => decide (a ∈ T)) i).toNat) := by rw [← hcw, hwt, hcard, ← hsumcard] have hne_b : ∃ i < 2 ^ m, (fun a => decide (a ∈ T)) i = true := by refine ⟨0, by omega, ?_⟩ have h0T : 0 ∈ T := (hTmem 0).mpr ⟨by omega, by simpa using hpF⟩ simp [h0T] obtain ⟨hb0, hbD⟩ := cycle_power_dyadic_tight_class_spanning m hm (fun a => decide (a ∈ T)) hcw' hne_b have h0T : 0 ∈ T := of_decide_eq_true hb0 have hDT : 2 ^ m - 1 ∈ T := of_decide_eq_true hbD have hpF' : p ∈ F := by simpa using ((hTmem 0).mp h0T).2 have hpD' : p + ((2 ^ m - 1 : ℕ) : ZMod n) ∈ F := ((hTmem (2 ^ m - 1)).mp hDT).2 exact ⟨p, hpF', hpD', harc⟩private theorem simple_graph_cycle_power_dyadic_cover_class_spanning_layer_weight_eq (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : Fin (m + 1) → ZMod n → ZMod n) (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v → ∃ s, c s u = c s v) : ∀ s : Fin (m+1), (∑ i : ZMod n, (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = n := by classical let d0 : ZMod n := ((2 ^ m - 1 : ℕ) : ZMod n) let D : ℕ → ZMod n := fun j => ((2 ^ m - 2 ^ j : ℕ) : ZMod n) let I0 : Fin (m + 1) → ZMod n → ℕ := fun s i => if c s i = c s (i + d0) then 1 else 0 let Ij : Fin (m + 1) → ℕ → ZMod n → ℕ := fun s j i => if c s i = c s (i + D j) then 1 else 0 let W : Fin (m + 1) → ℕ := fun s => ∑ i : ZMod n, (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)) let N0 : ZMod n → ℕ := fun i => ∑ s : Fin (m+1), I0 s i let Nj : ℕ → ZMod n → ℕ := fun j i => ∑ s : Fin (m+1), Ij s j i let J : Finset ℕ := (Finset.range m).filter (fun j => j ≠ 0) have hk_lt : 2 ^ m - 1 < n := by have hge : 1 ≤ 2 ^ m - 1 := by have h2 : 2 ≤ 2 ^ m := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm omega omega have hadj0 : ∀ i : ZMod n, (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + d0) := by intro i rw [show d0 = ((2 ^ m - 1 : ℕ) : ZMod n) from rfl] rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hk_lt] refine ⟨((2 ^ m - 1 : ℕ) : ℤ), ?_, ?_, ?_⟩ · have hge : 0 < 2 ^ m - 1 := by have h2 : 2 ≤ 2 ^ m := by calc 2 = 2 ^ 1 := by norm_num _ ≤ 2 ^ m := Nat.pow_le_pow_right (by norm_num) hm omega omega · rw [abs_of_nonneg (by positivity : (0:ℤ) ≤ ((2 ^ m - 1 : ℕ) : ℤ))] · push_cast; ring have hadjJ : ∀ (j : ℕ), j < m → ∀ i : ZMod n, (simple_graph_cycle_power n (2 ^ m - 1)).Adj i (i + D j) := by intro j hj i rw [show D j = ((2 ^ m - 2 ^ j : ℕ) : ZMod n) from rfl] rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt n (2 ^ m - 1) hk_lt] refine ⟨((2 ^ m - 2 ^ j : ℕ) : ℤ), ?_, ?_, ?_⟩ · have hpos : 0 < 2 ^ m - 2 ^ j := Nat.sub_pos_of_lt (Nat.pow_lt_pow_right (by norm_num) hj) omega · have hle : 2 ^ m - 2 ^ j ≤ 2 ^ m - 1 := by have : 1 ≤ 2 ^ j := Nat.one_le_two_pow omega have hnn : (0:ℤ) ≤ ((2 ^ m - 2 ^ j : ℕ) : ℤ) := by positivity rw [abs_of_nonneg hnn] exact_mod_cast hle · push_cast; ring have hcov0 : ∀ i : ZMod n, ∃ s : Fin (m+1), c s i = c s (i + d0) := fun i => hcov i (i + d0) (hadj0 i) have hcovJ : ∀ j ∈ J, ∀ i : ZMod n, ∃ s : Fin (m+1), c s i = c s (i + D j) := by intro j hj i have hjm : j < m := by have hh : j ∈ (Finset.range m).filter (fun j => j ≠ 0) := hj rw [Finset.mem_filter, Finset.mem_range] at hh exact hh.1 exact hcov i (i + D j) (hadjJ j hjm i) have hW_le : ∀ s : Fin (m+1), W s ≤ n := fun s => simple_graph_cycle_power_dyadic_layer_weight_le m n hm hn (c s) (hc s) have hsum_le : ∑ s : Fin (m+1), W s ≤ (m+1) * n := by have h := Finset.sum_le_sum (fun s (_ : s ∈ (Finset.univ : Finset (Fin (m+1)))) => hW_le s) simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] at h exact h have hT_split : ∀ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) = 2 * N0 i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i) := by intro i rw [Finset.sum_add_distrib] rw [show (∑ s : Fin (m+1), 2 * I0 s i) = 2 * N0 i by rw [Finset.mul_sum]] congr 1 rw [Finset.sum_comm] apply Finset.sum_congr rfl intro j hj rw [Finset.sum_ite_irrel] by_cases h : j = 0 · simp [h] · simp only [if_neg h]; rfl have hJcard : J.card = m - 1 := by have hmem : 0 ∈ Finset.range m := by rw [Finset.mem_range]; omega simp only [J, Finset.filter_ne', Finset.card_erase_of_mem hmem, Finset.card_range] have hN0_ge : ∀ i, 1 ≤ N0 i := by intro i rcases hcov0 i with ⟨s, hs⟩ have h := Finset.single_le_sum (f := fun x => I0 x i) (fun _ _ => Nat.zero_le _) (Finset.mem_univ s) rwa [show I0 s i = 1 by simp [I0, hs]] at h have hNJ_ge : ∀ j ∈ J, ∀ i, 1 ≤ Nj j i := by intro j hj i rcases hcovJ j hj i with ⟨s, hs⟩ have h := Finset.single_le_sum (f := fun x => Ij x j i) (fun _ _ => Nat.zero_le _) (Finset.mem_univ s) rwa [show Ij s j i = 1 by simp [Ij, hs]] at h have hJsum : ∀ i, (∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i)) = ∑ j ∈ J, Nj j i := by intro i change (∑ j ∈ Finset.range m, (if j = 0 then 0 else Nj j i)) = ∑ j ∈ (Finset.range m).filter (fun j => j ≠ 0), Nj j i rw [Finset.sum_filter] apply Finset.sum_congr rfl intro j hj by_cases h : j = 0 <;> simp [h] have hT_ge : ∀ i, m + 1 ≤ ∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i)) := by intro i rw [hT_split i, hJsum i] have hle : J.card ≤ ∑ j ∈ J, Nj j i := by have h := Finset.sum_le_sum (fun j hj => hNJ_ge j hj i) simpa using h have hn0 := hN0_ge i omega have hsumT : ∑ i : ZMod n, (∑ s : Fin (m+1), (2 * I0 s i + ∑ j ∈ Finset.range m, (if j = 0 then 0 else Ij s j i))) = ∑ s : Fin (m+1), W s := by simp only [W] rw [Finset.sum_comm] have hsum_ge : (m+1) * n ≤ ∑ s : Fin (m+1), W s := by rw [← hsumT] have h := Finset.sum_le_sum (fun i (_ : i ∈ (Finset.univ : Finset (ZMod n))) => hT_ge i) have hc : ∑ _i : ZMod n, (m+1) = (m+1) * n := by rw [Finset.sum_const, Finset.card_univ, ZMod.card, Nat.nsmul_eq_mul, Nat.mul_comm] rw [hc] at h exact h have hsum_eq : ∑ s : Fin (m+1), W s = (m+1) * n := le_antisymm hsum_le hsum_ge intro s by_contra hne have hlt : W s < n := lt_of_le_of_ne (hW_le s) hne have hconst : ∑ _x : Fin (m+1), n = (m+1) * n := by rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul] have hstrict : ∑ x : Fin (m+1), W x < ∑ _x : Fin (m+1), n := Finset.sum_lt_sum (fun x _ => hW_le x) ⟨s, Finset.mem_univ s, hlt⟩ rw [hconst, hsum_eq] at hstrict exact lt_irrefl _ hstricttheorem simple_graph_cycle_power_dyadic_cover_class_spanning (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (hn : 3 * (2 ^ m - 1) + 1 ≤ n) (c : Fin (m + 1) → ZMod n → ZMod n) (hc : ∀ s u v, u ≠ v → c s u = c s v → (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v) (hcov : ∀ u v, (simple_graph_cycle_power n (2 ^ m - 1)).Adj u v → ∃ s, c s u = c s v) : ∀ (s : Fin (m + 1)) (v : ZMod n), ∃ a : ℕ, a ≤ 2 ^ m - 1 ∧ c s (v - (a : ZMod n)) = c s v ∧ c s (v - (a : ZMod n)) = c s (v - (a : ZMod n) + ((2 ^ m - 1 : ℕ) : ZMod n)) := by classical have hlayer := simple_graph_cycle_power_dyadic_cover_class_spanning_layer_weight_eq m n hm hn c hc hcov intro s v have hsum_eq : (∑ l : ZMod n, (∑ i ∈ Finset.univ.filter (fun i => c s i = l), (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0)))) = n := by rw [Finset.sum_fiberwise] simpa using hlayer s have hcard_eq : (∑ l : ZMod n, (Finset.univ.filter (fun i => c s i = l)).card) = n := by rw [← Finset.card_eq_sum_card_fiberwise (s := Finset.univ) (t := Finset.univ) (f := c s) (by intro x _; simp)] simp have hle : ∀ l, (∑ i ∈ Finset.univ.filter (fun i => c s i = l), (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) ≤ (Finset.univ.filter (fun i => c s i = l)).card := by intro l exact simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_wt_le_card m n hm hn (c s) (hc s) l have heq_each : ∀ l, (∑ i ∈ Finset.univ.filter (fun i => c s i = l), (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) = (Finset.univ.filter (fun i => c s i = l)).card := by intro l have hall := (Finset.sum_eq_sum_iff_of_le (s := (Finset.univ : Finset (ZMod n))) (f := fun l => ∑ i ∈ Finset.univ.filter (fun i => c s i = l), (2 * (if c s i = c s (i + ((2 ^ m - 1 : ℕ) : ZMod n)) then 1 else 0) + (Finset.range m).sum (fun j => if j = 0 then 0 else if c s i = c s (i + ((2 ^ m - 2 ^ j : ℕ) : ZMod n)) then 1 else 0))) (g := fun l => (Finset.univ.filter (fun i => c s i = l)).card) (fun l _ => hle l)).mp (by rw [hsum_eq, hcard_eq]) exact hall l (Finset.mem_univ l) have hl := heq_each (c s v) have hnev : (Finset.univ.filter (fun i => c s i = c s v)).Nonempty := ⟨v, by simp⟩ obtain ⟨p, hpF, hpD, harc⟩ := simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_endpoints m n hm hn (c s) (hc s) (c s v) hnev hl have hvF : v ∈ Finset.univ.filter (fun i => c s i = c s v) := by simp obtain ⟨a0, ha0le, ha0eq⟩ := harc v hvF refine ⟨a0, ha0le, ?_, ?_⟩ · have hvc : v - (a0 : ZMod n) = p := by rw [ha0eq, add_sub_cancel_right] rw [hvc] exact (Finset.mem_filter.mp hpF).2 · have hvc : v - (a0 : ZMod n) = p := by rw [ha0eq, add_sub_cancel_right] rw [hvc] exact ((Finset.mem_filter.mp hpF).2).trans ((Finset.mem_filter.mp hpD).2).symm