AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_cover_class_spanning

theoremverified

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

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.

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

    lines 9–35

    uses Nat.one_le_two_pow, if_pos, Finset.sum_eq_single, if_neg, Finset.sum_eq_zero

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

    lines 36–55

    uses Nat.pow_lt_pow_right, Finset.sum_congr, Finset.card_filter, Finset.mem_filter, Finset.mem_range

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

    lines 56–84

    uses cycle_power_dyadic_class_weight, Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_comm, Finset.sum_congr

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

    lines 98–123

    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_injOn

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

    lines 124–160

    uses eq_comm, if_pos, if_neg, Finset.sum_congr

      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, ?_⟩
  6. 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)).

    lines 161–214

    uses Finset.sum_congr, Finset.sum_image, Nat.add_sub_assoc, if_congr, simple_graph_cycle_power_dyadic_cover_class_spanning_offset_weight_eq

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

    lines 218–227

    uses Finset.sum_congr, Finset.card_filter, Finset.mem_filter, Finset.mem_range

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

    lines 240–268

    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_empty

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

    lines 285–323

    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_true

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

    lines 336–389

    uses simple_graph_cycle_power_adj_iff_of_bandwidth_lt, Nat.pow_lt_pow_right, Nat.one_le_two_pow, abs_of_nonneg

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

    lines 390–451

    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_antisymm

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

    lines 452–461

    uses lt_of_le_of_ne, Finset.sum_const, Finset.card_univ, Fintype.card_fin, Nat.nsmul_eq_mul, Finset.sum_lt_sum, lt_irrefl

      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 _ hstrict
    
  13. 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.

    lines 475–508

    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_le

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

    lines 509–521

    uses simple_graph_cycle_power_dyadic_cover_class_spanning_fibre_endpoints, add_sub_cancel_right

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

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

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