AFTD Auto-Formalizing Theoretical Domains

simple_graph_cycle_power_dyadic_layer_weight_le

theoremverified

In 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 weight (two for endpoint-distance pairs, one for other dyadic long distances) is at most n.

Statement

theorem simple_graph_cycle_power_dyadic_layer_weight_le
    (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) :
    (∑ i : ZMod n,
      (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))) ≤ n
Source
Uniform weighted-cover reduction for OP-205 / RT-1 following arXiv:2610.15635. This is the arbitrary-bandwidth analogue of the proved k=3 and k=7 layer-weight helpers; no research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • 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…
  • zmod_intCast_eq_intCast_iff_of_abs_sub_ltTwo integers a, b with |a − b| < n are equal modulo n only if they are equal.
  • FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via ZMod.
Used by 4

The proof, explained

The proof proceeds by partitioning the vertices of the cycle into fibers of the labelling c (the sets of vertices sharing each label) and bounding the layer weight on each fiber individually. For any nonempty fiber F = c⁻¹(l), the hypothesis ensures that F is a clique in the cycle power graph, which by `simple_graph_cycle_power_clique_arc` must lie entirely within an arc of length 2^m - 1. Because n ≥ 3(2^m - 1) + 1, this arc does not wrap around the cycle, allowing F to be identified with a subset of integers T' ⊂ ℤ of diameter at most 2^m - 1 where dyadic jump conditions correspond exactly to integer shifts. Applying the integer bound `cycle_power_dyadic_int_weight_le_card` shows that the layer weight of each fiber is at most its cardinality |F|. Summing this bound over all labels yields a total weight of at most ∑_l |F_l| = n.

  1. For a fixed label l, the fiber problem reduces to showing that the sum of the layer weight W over the fiber F = c⁻¹(l) is at most |F|.

    We define F as the fiber of vertices in ℤ/nℤ with label l, and define W(i) as the layer weight at vertex i. Rewriting the goal using these definitions restates the inequality as ∑_{i ∈ F} W(i) ≤ |F|.

    lines 13–19

      classical
      set F := Finset.univ.filter (fun i : ZMod n => c i = l) with hFdef
      set W : ZMod n → ℕ := fun i =>
        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) with hWdef
      change (∑ i ∈ F, W i) ≤ F.card
  2. We split into cases depending on whether the fiber F is nonempty.

    If F is empty, the sum and cardinality are both 0. We first analyze the primary case where F is nonempty.

    line 20

      by_cases hne : F.Nonempty
  3. The fiber F is a clique and is therefore contained in an arc of length 2^m - 1 starting at some vertex p ∈ F.

    Since all vertices in F share the same label l, the coloring hypothesis hc implies that every pair of distinct vertices in F is adjacent in the cycle power graph, meaning F is a clique. Since n ≥ 3(2^m - 1) + 1, `simple_graph_cycle_power_clique_arc` guarantees that F is contained in an arc: there exists p ∈ F such that every u ∈ F can be expressed as p + a with a ≤ 2^m - 1.

    lines 21–25

    uses simple_graph_cycle_power_clique_arc, Finset.mem_filter, Finset.mem_univ, true_and

      · obtain ⟨p, hpF, harc⟩ := simple_graph_cycle_power_clique_arc n (2 ^ m - 1) hn F hne (by
          intro u hu v hv huv
          rw [hFdef] at hu hv
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu hv
          exact hc u v huv (by rw [hu, hv]))
  4. The fiber F is parameterized by natural offsets T ⊆ {0, ..., 2^m - 1} and integer offsets T' ⊂ ℤ.

    We define T as the set of offsets a < 2^m such that p + a ∈ F, and T' as its cast into ℤ. Since m ≥ 1 and n ≥ 3(2^m - 1) + 1, we establish several arithmetic bounds: 2^m - 1 < n and 2(2^m - 1) < n, ensuring no modular wraparound occurs on the arc. We also verify that membership of an integer in T' is equivalent to its underlying natural number belonging to T.

    lines 26–50

    uses Nat.one_lt_two_pow, Nat.cast_sub, Finset.mem_range, Finset.mem_image, Int.ofNat_inj.mp

        set T : Finset ℕ := (Finset.range (2 ^ m)).filter (fun a => p + (a : ZMod n) ∈ F) with hTdef
        set T' : Finset ℤ := T.image (fun a : ℕ => (a : ℤ)) with hT'def
        have h1 : 1 ≤ 2 ^ m := by have := Nat.one_lt_two_pow (by omega : m ≠ 0); omega
        have hKlt : 2 ^ m - 1 < n := by omega
        have h2Klt : 2 * (2 ^ m - 1) < n := by omega
        have hsub : ((2 ^ m - 1 : ℕ) : ℤ) = (2 ^ m : ℤ) - 1 := by
          rw [Nat.cast_sub h1]; norm_num
        have hmemF : ∀ u : ZMod n, u ∈ F ↔ c u = l := by
          intro u; rw [hFdef]; simp
        have hpF' : c p = l := (hmemF p).mp hpF
        have hW' : ∀ i : ZMod n, W i =
            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) := by
          intro i; rw [hWdef]
        have hT_mem : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F := by
          intro a; rw [hTdef]; simp [Finset.mem_range]
        have hT'_mem : ∀ e : ℕ, ((e : ℤ) ∈ T') ↔ e ∈ T := by
          intro e
          rw [hT'def, Finset.mem_image]
          constructor
          · rintro ⟨b, hb, hbe⟩
            have hbe' : b = e := Int.ofNat_inj.mp hbe
            rwa [hbe'] at hb
          · intro he; exact ⟨e, he, rfl⟩
  5. The map a ↦ p + a is a bijection from T to F, so |F| = |T| = |T'| and the sum over F equals the sum over T.

    Since a, b < 2^m < n, p + a = p + b in ℤ/nℤ implies a = b in ℕ, so the shift map is injective on T. Because F is contained in the arc of length 2^m - 1 starting at p, F is precisely the image of T under this map. Consequently, |F| = |T| = |T'|, and the sum of W over F is identical to the sum of W(p + a) over a ∈ T.

    lines 51–76

    uses add_left_cancel, ZMod.natCast_eq_natCast_iff, Nat.ModEq.eq_of_lt_of_lt, Finset.card_image_of_injOn, Finset.sum_image, Int.ofNat_inj.mp

        have hinj : Set.InjOn (fun a : ℕ => p + (a : ZMod n)) ↑T := by
          intro a ha b hb hab
          have ha_lt : a < 2 ^ m := ((hT_mem a).mp ha).1
          have hb_lt : b < 2 ^ m := ((hT_mem b).mp hb).1
          have hcast : (a : ZMod n) = (b : ZMod n) := add_left_cancel hab
          have han : a < n := by omega
          have hbn : b < n := by omega
          rw [ZMod.natCast_eq_natCast_iff] at hcast
          exact Nat.ModEq.eq_of_lt_of_lt hcast han hbn
        have hF_eq : F = T.image (fun a : ℕ => p + (a : ZMod n)) := by
          ext u
          rw [Finset.mem_image]
          constructor
          · intro hu
            obtain ⟨a, ha_le, ha_eq⟩ := harc u hu
            refine ⟨a, ?_, ha_eq.symm⟩
            rw [hT_mem]
            exact ⟨by omega, by rw [← ha_eq]; exact hu⟩
          · rintro ⟨a, ha, rfl⟩
            exact ((hT_mem a).mp ha).2
        have hcard1 : F.card = T.card := by
          rw [hF_eq, Finset.card_image_of_injOn hinj]
        have hcard2 : T'.card = T.card := by
          rw [hT'def, Finset.card_image_of_injOn (by intro x _ y _ h; exact Int.ofNat_inj.mp h)]
        have hsum1 : ∑ i ∈ F, W i = ∑ a ∈ T, W (p + (a : ZMod n)) := by
          rw [hF_eq, Finset.sum_image hinj]
  6. For any offset d < 2^m and a ∈ T, the condition c(p + a) = c(p + a + d) is equivalent to a + d ∈ T' in ℤ.

    Because p + a ∈ F, c(p + a) = l, so the label condition holds if and only if p + (a + d) ∈ F. Since a < 2^m and d < 2^m, the sum a + d is strictly less than n. Since F is entirely contained in the arc from p, p + (a + d) ∈ F if and only if a + d ∈ T, which translates directly to (a : ℤ) + (d : ℤ) ∈ T'.

    lines 77–110

    uses add_left_cancel, ZMod.natCast_eq_natCast_iff, Nat.ModEq.eq_of_lt_of_lt, eq_comm, Nat.cast_add, if_congr

        have hshift : ∀ a d : ℕ, a < 2 ^ m → d < 2 ^ m →
            (p + ((a + d : ℕ) : ZMod n) ∈ F ↔ (a + d) ∈ T) := by
          intro a d ha hd
          constructor
          · intro hmem
            obtain ⟨b, hb_le, hb_eq⟩ := harc _ hmem
            have hcast : ((a + d : ℕ) : ZMod n) = (b : ZMod n) := add_left_cancel hb_eq
            have hadn : a + d < n := by omega
            have hbn : b < n := by omega
            rw [ZMod.natCast_eq_natCast_iff] at hcast
            have hab : a + d = b := Nat.ModEq.eq_of_lt_of_lt hcast hadn hbn
            rw [hT_mem]
            exact ⟨by omega, hmem⟩
          · intro hmem
            exact ((hT_mem (a + d)).mp hmem).2
        have hif : ∀ d : ℕ, d < 2 ^ m → ∀ a ∈ T,
            (if c (p + (a : ZMod n)) = c (p + (a : ZMod n) + (d : ZMod n)) then (1:ℕ) else 0)
            = (if (a : ℤ) + (d : ℤ) ∈ T' then 1 else 0) := by
          intro d hd a ha
          have ha_lt : a < 2 ^ m := ((hT_mem a).mp ha).1
          have haF : p + (a : ZMod n) ∈ F := ((hT_mem a).mp ha).2
          have hca : c (p + (a : ZMod n)) = l := (hmemF _).mp haF
          have hstep : p + (a : ZMod n) + (d : ZMod n) = p + ((a + d : ℕ) : ZMod n) := by
            push_cast; ring
          have hiff : c (p + (a : ZMod n)) = c (p + (a : ZMod n) + (d : ZMod n)) ↔
              ((a : ℤ) + (d : ℤ) ∈ T') := by
            rw [hstep, hca]
            have e1 : l = c (p + ((a + d : ℕ) : ZMod n)) ↔ p + ((a + d : ℕ) : ZMod n) ∈ F := by
              rw [hmemF]; exact eq_comm
            have e2 : p + ((a + d : ℕ) : ZMod n) ∈ F ↔ (a + d) ∈ T := hshift a d ha_lt hd
            have e3 : (a + d) ∈ T ↔ ((a + d : ℕ) : ℤ) ∈ T' := (hT'_mem (a + d)).symm
            have e4 : ((a + d : ℕ) : ℤ) ∈ T' ↔ ((a : ℤ) + (d : ℤ)) ∈ T' := by rw [Nat.cast_add]
            exact e1.trans (e2.trans (e3.trans e4))
          exact if_congr hiff rfl rfl
  7. The fiber sum ∑_{a ∈ T} W(p + a) equals the integer layer weight of the set T' ⊂ ℤ.

    Applying the indicator shift equivalence to the bandwidth d = 2^m - 1 and each dyadic offset d = 2^m - 2^j for j ≥ 1, each term W(p + a) matches the corresponding integer dyadic layer weight term at a. Reindexing the sum from T ⊂ ℕ to T' ⊂ ℤ expresses the fiber sum as the integer layer weight of T'.

    lines 111–134

    uses Nat.two_pow_pos, Finset.sum_congr, if_neg, Int.ofNat_inj.mp, Finset.sum_image

        have hterm : ∀ a ∈ T, W (p + (a : ZMod n)) =
            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
          intro a ha
          rw [hW', hif (2 ^ m - 1) (by have := Nat.two_pow_pos m; omega) a ha]
          congr 1
          apply Finset.sum_congr rfl
          intro j hj
          by_cases hj0 : j = 0
          · simp [hj0]
          · rw [if_neg hj0, if_neg hj0]
            exact hif (2 ^ m - 2 ^ j) (by have := Nat.two_pow_pos m; have := Nat.two_pow_pos j; omega) a ha
        have hinjT' : Set.InjOn (fun a : ℕ => (a : ℤ)) ↑T := by
          intro x _ y _ h; exact Int.ofNat_inj.mp h
        have hsum2 : ∑ a ∈ T, W (p + (a : ZMod n)) =
            ∑ e ∈ T', (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) +
              (Finset.range m).sum (fun j => if j = 0 then 0 else
                if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)) := by
          rw [Finset.sum_congr rfl hterm,
            ← Finset.sum_image (f := fun e => 2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) +
              (Finset.range m).sum (fun j => if j = 0 then 0 else
                if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)) hinjT',
            ← hT'def]
  8. The diameter of T' in ℤ is at most 2^m - 1, which bounds the fiber sum by |T'| = |F|.

    Since every element e ∈ T' satisfies 0 ≤ e ≤ 2^m - 1, any two elements have distance |a - b| ≤ 2^m - 1. Applying `cycle_power_dyadic_int_weight_le_card` to T' shows that its integer dyadic layer weight is at most |T'|. Since |T'| = |F|, this proves ∑_{i ∈ F} W(i) ≤ |F| for nonempty fibers.

    lines 135–156

    uses abs_le, cycle_power_dyadic_int_weight_le_card

        have hdiam : ∀ a ∈ T', ∀ b ∈ T', |a - b| ≤ ((2 ^ m - 1 : ℕ) : ℤ) := by
          intro a ha b hb
          rw [hT'def, Finset.mem_image] at ha hb
          obtain ⟨a', ha', rfl⟩ := ha
          obtain ⟨b', hb', rfl⟩ := hb
          have ha'_lt : a' < 2 ^ m := ((hT_mem a').mp ha').1
          have hb'_lt : b' < 2 ^ m := ((hT_mem b').mp hb').1
          have ha'_le : (a' : ℤ) ≤ (2 ^ m : ℤ) - 1 := by
            have : (a' : ℤ) < (2 ^ m : ℤ) := by exact_mod_cast ha'_lt
            omega
          have hb'_le : (b' : ℤ) ≤ (2 ^ m : ℤ) - 1 := by
            have : (b' : ℤ) < (2 ^ m : ℤ) := by exact_mod_cast hb'_lt
            omega
          rw [abs_le, hsub]
          constructor <;> omega
        have hbound := cycle_power_dyadic_int_weight_le_card m hm T' hdiam
        rw [hsum1, hsum2]
        calc (∑ e ∈ T', (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) +
              (Finset.range m).sum (fun j => if j = 0 then 0 else
                if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)))
            ≤ T'.card := hbound
          _ = F.card := by rw [hcard2, ← hcard1]
  9. If the fiber F is empty, the inequality holds trivially as 0 ≤ 0.

    When F = ∅, the sum over F is the empty sum (0) and the cardinality of F is 0, closing the remaining case of the fiber lemma.

    lines 157–158

    uses Finset.not_nonempty_iff_eq_empty

      · rw [Finset.not_nonempty_iff_eq_empty] at hne
        simp [hne]
  10. Summing the fiber bounds over all labels proves that the total dyadic layer weight is at most n.

    Using `Finset.sum_fiberwise`, we partition the sum over all vertices i ∈ ℤ/nℤ into a sum of fiber sums over all labels l ∈ ℤ/nℤ. Applying `simple_graph_cycle_power_dyadic_layer_weight_le_fiber` to each fiber via `Finset.sum_le_sum` bounds the total weight by the sum of fiber cardinalities. Finally, the sum of all fiber cardinalities equals the total number of vertices |ℤ/nℤ| = n, by `Finset.card_eq_sum_card_fiberwise` and `ZMod.card`.

    lines 170–186

    uses Finset.sum_fiberwise, Finset.sum_le_sum, simple_graph_cycle_power_dyadic_layer_weight_le_fiber, Finset.card_eq_sum_card_fiberwise, ZMod.card

      classical
      calc (∑ i : ZMod n,
            (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)))
          = ∑ 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)) := by
            rw [Finset.sum_fiberwise]
        _ ≤ ∑ l : ZMod n, (Finset.univ.filter (fun i => c i = l)).card :=
            Finset.sum_le_sum (fun l _ =>
              simple_graph_cycle_power_dyadic_layer_weight_le_fiber m n hm hn c hc l)
        _ = n := by
            rw [← Finset.card_eq_sum_card_fiberwise (s := Finset.univ) (t := Finset.univ)
                  (f := c) (by intro x _; simp)]
            simp [ZMod.card]
simple_graph_cycle_power_clique_arc
In a cycle power graph on ℤ/nℤ with bandwidth k, if n ≥ 3k + 1, any nonempty clique K is contained in an arc of length k: there exists p ∈ K such that every u ∈ K can be written as p + a with a ≤ k.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set.
true_and
Conjunction with True simplifies to the proposition itself.
Nat.one_lt_two_pow
For any nonzero natural number n, 2^n > 1.
Nat.cast_sub
Subtraction of natural numbers casts to subtraction in an additive group with one, provided the subtrahend is at most the minuend.
Finset.mem_range
A natural number m belongs to the range {0, ..., n-1} if and only if m < n.
Finset.mem_image
An element is in the image of a finite set under f if and only if it is the image of some element in that set.
Int.ofNat_inj.mp
The canonical injection from natural numbers into integers is injective.
add_left_cancel
Left addition in a cancellation group is injective: a + b = a + c implies b = c.
ZMod.natCast_eq_natCast_iff
The natural number casts into ℤ/cℤ are equal if and only if the numbers are congruent modulo c.
Nat.ModEq.eq_of_lt_of_lt
If two natural numbers strictly less than m are congruent modulo m, they are equal.
Finset.card_image_of_injOn
The image of a finite set under a function injective on that set has the same cardinality as the set.
Finset.sum_image
A sum over the image of a set under an injective map equals the sum over the original set composed with the map.
eq_comm
Equality is symmetric.
Nat.cast_add
The cast of a sum of natural numbers into an additive monoid with one equals the sum of the casts.
if_congr
Two conditional expressions are equal if their conditions are equivalent and their corresponding branches are equal.
Nat.two_pow_pos
Any power of 2 is strictly positive.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on all elements.
if_neg
A conditional expression evaluates to its false branch when the condition is false.
abs_le
The absolute value |a| is at most b if and only if -b ≤ a ≤ b.
cycle_power_dyadic_int_weight_le_card
For any finite set of integers S with diameter at most 2^m - 1 (where m ≥ 1), the dyadic layer weight of S is at most |S|.
Finset.not_nonempty_iff_eq_empty
A finite set is not nonempty if and only if it is empty.
Finset.sum_fiberwise
Summing a function over a set can be computed by partitioning into fibers of a map g and summing over all fibers.
Finset.sum_le_sum
If one summand is pointwise bounded by another on a finite set, the total sum is bounded by the sum of the upper bounds.
simple_graph_cycle_power_dyadic_layer_weight_le_fiber
In a clique labelling of a cycle power with bandwidth 2^m - 1 and n ≥ 3(2^m - 1) + 1, the dyadic layer weight summed over any single fiber c⁻¹(l) is at most the cardinality of that fiber.
Finset.card_eq_sum_card_fiberwise
The cardinality of a finite set equals the sum of the cardinalities of its fibers under any map.
ZMod.card
The number of elements in the ring ℤ/nℤ is 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

private theorem simple_graph_cycle_power_dyadic_layer_weight_le_fiber    (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  set F := Finset.univ.filter (fun i : ZMod n => c i = l) with hFdef  set W : ZMod n → ℕ := fun i =>    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) with hWdef  change (∑ i ∈ F, W i) ≤ F.card  by_cases hne : F.Nonempty  · obtain ⟨p, hpF, harc⟩ := simple_graph_cycle_power_clique_arc n (2 ^ m - 1) hn F hne (by      intro u hu v hv huv      rw [hFdef] at hu hv      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hu hv      exact hc u v huv (by rw [hu, hv]))    set T : Finset ℕ := (Finset.range (2 ^ m)).filter (fun a => p + (a : ZMod n) ∈ F) with hTdef    set T' : Finset ℤ := T.image (fun a : ℕ => (a : ℤ)) with hT'def    have h1 : 1 ≤ 2 ^ m := by have := Nat.one_lt_two_pow (by omega : m ≠ 0); omega    have hKlt : 2 ^ m - 1 < n := by omega    have h2Klt : 2 * (2 ^ m - 1) < n := by omega    have hsub : ((2 ^ m - 1 : ℕ) : ℤ) = (2 ^ m : ℤ) - 1 := by      rw [Nat.cast_sub h1]; norm_num    have hmemF : ∀ u : ZMod n, u ∈ F ↔ c u = l := by      intro u; rw [hFdef]; simp    have hpF' : c p = l := (hmemF p).mp hpF    have hW' : ∀ i : ZMod n, W i =        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) := by      intro i; rw [hWdef]    have hT_mem : ∀ a, a ∈ T ↔ a < 2 ^ m ∧ p + (a : ZMod n) ∈ F := by      intro a; rw [hTdef]; simp [Finset.mem_range]    have hT'_mem : ∀ e : ℕ, ((e : ℤ) ∈ T') ↔ e ∈ T := by      intro e      rw [hT'def, Finset.mem_image]      constructor      · rintro ⟨b, hb, hbe⟩        have hbe' : b = e := Int.ofNat_inj.mp hbe        rwa [hbe'] at hb      · intro he; exact ⟨e, he, rfl⟩    have hinj : Set.InjOn (fun a : ℕ => p + (a : ZMod n)) ↑T := by      intro a ha b hb hab      have ha_lt : a < 2 ^ m := ((hT_mem a).mp ha).1      have hb_lt : b < 2 ^ m := ((hT_mem b).mp hb).1      have hcast : (a : ZMod n) = (b : ZMod n) := add_left_cancel hab      have han : a < n := by omega      have hbn : b < n := by omega      rw [ZMod.natCast_eq_natCast_iff] at hcast      exact Nat.ModEq.eq_of_lt_of_lt hcast han hbn    have hF_eq : F = T.image (fun a : ℕ => p + (a : ZMod n)) := by      ext u      rw [Finset.mem_image]      constructor      · intro hu        obtain ⟨a, ha_le, ha_eq⟩ := harc u hu        refine ⟨a, ?_, ha_eq.symm⟩        rw [hT_mem]        exact ⟨by omega, by rw [← ha_eq]; exact hu⟩      · rintro ⟨a, ha, rfl⟩        exact ((hT_mem a).mp ha).2    have hcard1 : F.card = T.card := by      rw [hF_eq, Finset.card_image_of_injOn hinj]    have hcard2 : T'.card = T.card := by      rw [hT'def, Finset.card_image_of_injOn (by intro x _ y _ h; exact Int.ofNat_inj.mp h)]    have hsum1 : ∑ i ∈ F, W i = ∑ a ∈ T, W (p + (a : ZMod n)) := by      rw [hF_eq, Finset.sum_image hinj]    have hshift : ∀ a d : ℕ, a < 2 ^ m → d < 2 ^ m →        (p + ((a + d : ℕ) : ZMod n) ∈ F ↔ (a + d) ∈ T) := by      intro a d ha hd      constructor      · intro hmem        obtain ⟨b, hb_le, hb_eq⟩ := harc _ hmem        have hcast : ((a + d : ℕ) : ZMod n) = (b : ZMod n) := add_left_cancel hb_eq        have hadn : a + d < n := by omega        have hbn : b < n := by omega        rw [ZMod.natCast_eq_natCast_iff] at hcast        have hab : a + d = b := Nat.ModEq.eq_of_lt_of_lt hcast hadn hbn        rw [hT_mem]        exact ⟨by omega, hmem⟩      · intro hmem        exact ((hT_mem (a + d)).mp hmem).2    have hif : ∀ d : ℕ, d < 2 ^ m → ∀ a ∈ T,        (if c (p + (a : ZMod n)) = c (p + (a : ZMod n) + (d : ZMod n)) then (1:ℕ) else 0)        = (if (a : ℤ) + (d : ℤ) ∈ T' then 1 else 0) := by      intro d hd a ha      have ha_lt : a < 2 ^ m := ((hT_mem a).mp ha).1      have haF : p + (a : ZMod n) ∈ F := ((hT_mem a).mp ha).2      have hca : c (p + (a : ZMod n)) = l := (hmemF _).mp haF      have hstep : p + (a : ZMod n) + (d : ZMod n) = p + ((a + d : ℕ) : ZMod n) := by        push_cast; ring      have hiff : c (p + (a : ZMod n)) = c (p + (a : ZMod n) + (d : ZMod n)) ↔          ((a : ℤ) + (d : ℤ) ∈ T') := by        rw [hstep, hca]        have e1 : l = c (p + ((a + d : ℕ) : ZMod n)) ↔ p + ((a + d : ℕ) : ZMod n) ∈ F := by          rw [hmemF]; exact eq_comm        have e2 : p + ((a + d : ℕ) : ZMod n) ∈ F ↔ (a + d) ∈ T := hshift a d ha_lt hd        have e3 : (a + d) ∈ T ↔ ((a + d : ℕ) : ℤ) ∈ T' := (hT'_mem (a + d)).symm        have e4 : ((a + d : ℕ) : ℤ) ∈ T' ↔ ((a : ℤ) + (d : ℤ)) ∈ T' := by rw [Nat.cast_add]        exact e1.trans (e2.trans (e3.trans e4))      exact if_congr hiff rfl rfl    have hterm : ∀ a ∈ T, W (p + (a : ZMod n)) =        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      intro a ha      rw [hW', hif (2 ^ m - 1) (by have := Nat.two_pow_pos m; omega) a ha]      congr 1      apply Finset.sum_congr rfl      intro j hj      by_cases hj0 : j = 0      · simp [hj0]      · rw [if_neg hj0, if_neg hj0]        exact hif (2 ^ m - 2 ^ j) (by have := Nat.two_pow_pos m; have := Nat.two_pow_pos j; omega) a ha    have hinjT' : Set.InjOn (fun a : ℕ => (a : ℤ)) ↑T := by      intro x _ y _ h; exact Int.ofNat_inj.mp h    have hsum2 : ∑ a ∈ T, W (p + (a : ZMod n)) =        ∑ e ∈ T', (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) +          (Finset.range m).sum (fun j => if j = 0 then 0 else            if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)) := by      rw [Finset.sum_congr rfl hterm,        ← Finset.sum_image (f := fun e => 2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) +          (Finset.range m).sum (fun j => if j = 0 then 0 else            if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)) hinjT',        ← hT'def]    have hdiam : ∀ a ∈ T', ∀ b ∈ T', |a - b| ≤ ((2 ^ m - 1 : ℕ) : ℤ) := by      intro a ha b hb      rw [hT'def, Finset.mem_image] at ha hb      obtain ⟨a', ha', rfl⟩ := ha      obtain ⟨b', hb', rfl⟩ := hb      have ha'_lt : a' < 2 ^ m := ((hT_mem a').mp ha').1      have hb'_lt : b' < 2 ^ m := ((hT_mem b').mp hb').1      have ha'_le : (a' : ℤ) ≤ (2 ^ m : ℤ) - 1 := by        have : (a' : ℤ) < (2 ^ m : ℤ) := by exact_mod_cast ha'_lt        omega      have hb'_le : (b' : ℤ) ≤ (2 ^ m : ℤ) - 1 := by        have : (b' : ℤ) < (2 ^ m : ℤ) := by exact_mod_cast hb'_lt        omega      rw [abs_le, hsub]      constructor <;> omega    have hbound := cycle_power_dyadic_int_weight_le_card m hm T' hdiam    rw [hsum1, hsum2]    calc (∑ e ∈ T', (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ T' then 1 else 0) +          (Finset.range m).sum (fun j => if j = 0 then 0 else            if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ T' then 1 else 0)))        ≤ T'.card := hbound      _ = F.card := by rw [hcard2, ← hcard1]  · rw [Finset.not_nonempty_iff_eq_empty] at hne    simp [hne]theorem simple_graph_cycle_power_dyadic_layer_weight_le    (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) :    (∑ i : ZMod n,      (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))) ≤ n := by  classical  calc (∑ i : ZMod n,        (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)))      = ∑ 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)) := by        rw [Finset.sum_fiberwise]    _ ≤ ∑ l : ZMod n, (Finset.univ.filter (fun i => c i = l)).card :=        Finset.sum_le_sum (fun l _ =>          simple_graph_cycle_power_dyadic_layer_weight_le_fiber m n hm hn c hc l)    _ = n := by        rw [← Finset.card_eq_sum_card_fiberwise (s := Finset.univ) (t := Finset.univ)              (f := c) (by intro x _; simp)]        simp [ZMod.card]
See it in the graphDiscuss this resultChallenge it