AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_central_position_exists

theoremverified

In a periodic tight dyadic class model with exact dyadic coverage and coverage at all lower neighbour distances, some class uses one of the two central positions. This requires neither a full class nor a preclassified class profile.

Statement

theorem cycle_power_dyadic_central_position_exists
    (m n : ℕ) (hm : 2 ≤ m) (hn : 0 < n) (x : ℤ → ℕ → Bool)
    (hperiod : ∀ p a, x (p + (n : ℤ)) a = x p a)
    (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) =
      (Finset.range (2 ^ m)).sum (fun a => (x p a).toNat))
    (hexact : ∀ j < m, ∀ v : ℤ, (Finset.range (2 ^ j)).sum (fun a =>
      (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1)
    (hcover : ∀ j : ℕ, 1 ≤ j → j < m → ∀ v : ℤ,
      ∃ a : ℕ, a < 2 ^ j + 1 ∧ x (v - (a : ℤ)) a = true ∧
        x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j - 1) = true) :
    ∃ p : ℤ, x p (2 ^ (m - 1) - 1) = true ∨ x p (2 ^ (m - 1)) = true
Source
Uniform consequence planned for the new neighbour-weight inequality in OP-205 / RT-1, arXiv:2610.15635. It remains unproved while its weight-bound dependency is unproved; no research advance or main solution claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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.
  • cycle_power_dyadic_neighbour_weight_boundA tight rooted dyadic class satisfies a uniform weighted bound for the ordinary distances one below the dyadic long distances, with a…
  • zmod_sum_sub_eq_sumSummation of any natural function over ZMod n is invariant under subtraction by a constant residue.
  • cycle_power_dyadic_pair_countThe finite dyadic pair sum. For ranks j at most m, it counts selected pairs at distance 2^m minus 2^j in the dyadic arc.
  • cycle_power_dyadic_neighbour_pair_countThe finite neighbour pair sum. For ranks j strictly below m, it counts selected pairs at distance 2^m minus 2^j minus one in the dyadic arc.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 2

The proof, explained

The proof proceeds by contradiction, assuming that neither central position 2^(m-1) - 1 nor 2^(m-1) is active in any class. By factoring through the periodic quotient ℤ/nℤ, the exact dyadic coverage condition implies that the total pair count across all classes is identically n at every scale, whereas neighbour coverage implies the total neighbour count is at least n at each scale. Applying the neighbour weight bound for tight dyadic classes with vanishing central bits to each class and summing over all n classes yields n * A ≤ n + n * B for A = ∑_{j=1}^{m-1} 2^j and B = ∑_{j=2}^{m-1} 2^j. Since A = B + 2, this forces 2n ≤ n, contradicting n > 0.

  1. Assume for contradiction that neither central position is active in any class, and project the configuration onto ℤ/nℤ.

    We assume for contradiction that for every p : ℤ, both x p (2^(m-1) - 1) and x p (2^(m-1)) are false. Because n > 0, we can work in the quotient ring ℤ/nℤ and define y p a = x (p.val) a by evaluating x at the canonical representative p.val ∈ {0, ..., n - 1}.

    lines 14–18

      classical
      by_contra hnone
      push_neg at hnone
      letI : NeZero n := ⟨by omega⟩
      let y : ZMod n → ℕ → Bool := fun p a => x (p.val : ℤ) a
  2. The projected configuration y agrees with x under integer casting and residue subtraction: y (v : ℤ/nℤ) a = x v a and y (v - a) j = x (v.val - a) j.

    Because x(·, a) is n-periodic, every integer v differs from the representative of its mod-n residue class by a multiple of n by ZMod.intCast_eq_iff. Evaluating x across this multiple shows y (v : ℤ/nℤ) a = x v a using congrArg. Applying this to v.val - a and simplifying integer and natural casts with Int.cast_sub, Int.cast_natCast, and ZMod.natCast_zmod_val proves that subtracting in ℤ/nℤ matches subtracting in ℤ.

    lines 19–31

    uses ZMod.intCast_eq_iff, congrArg, Int.cast_sub, Int.cast_natCast, ZMod.natCast_zmod_val

      have hval (v : ℤ) (a : ℕ) : y (v : ZMod n) a = x v a := by
        obtain ⟨z, hz⟩ := (ZMod.intCast_eq_iff n v (v : ZMod n)).mp rfl
        have hp : Function.Periodic (fun p : ℤ => x p a) (n : ℤ) := fun p => hperiod p a
        have hh := hp.int_mul z (((v : ZMod n).val : ℤ))
        have he : ((v : ZMod n).val : ℤ)+z*(n : ℤ)=v := by
          calc
            _ = ((v : ZMod n).val : ℤ)+(n : ℤ)*z := by ring
            _ = v := hz.symm
        exact hh.symm.trans (congrArg (fun w : ℤ => x w a) he)
      have hshift (v : ZMod n) (a j : ℕ) :
          y (v-(a : ZMod n)) j = x ((v.val : ℤ)-(a : ℤ)) j := by
        have hh := hval ((v.val : ℤ)-(a : ℤ)) j
        simpa only [Int.cast_sub, Int.cast_natCast, ZMod.natCast_zmod_val] using hh
  3. Every class in ℤ/nℤ has both boundary bits active: y p 0 = true and y p (2^m - 1) = true.

    Specializing the exact coverage hypothesis hexact at scale j = 0 for v = p.val, the range of indices contains only a = 0 since 2^0 = 1. Simplifying with pow_zero, sum_range_one, Nat.cast_zero, sub_zero, and Nat.zero_add reduces the sum to (x (p.val) 0 && x (p.val) (2^m - 1)).toNat = 1, which implies both boolean factors must be true.

    lines 32–38

    uses pow_zero, sum_range_one, Nat.cast_zero, sub_zero, Nat.zero_add

      have hroot (p : ZMod n) : y p 0 = true ∧ y p (2^m-1) = true := by
        have hh := hexact 0 (by omega) (p.val : ℤ)
        norm_num only [pow_zero, sum_range_one, Nat.cast_zero, sub_zero,
          Nat.zero_add] at hh
        dsimp [y]
        cases h0 : x (p.val : ℤ) 0 <;>
          cases h1 : x (p.val : ℤ) (2^m-1) <;> simp_all
  4. For each scale j < m, the sum over all classes of the dyadic pair counts equals n.

    Unfolding the pair count definition and exchanging the order of summation using sum_comm, the sum runs over a < 2^j and p ∈ ℤ/nℤ. Reindexing each inner sum by the translation p ↦ v - a using zmod_sum_sub_eq_sum, and exchanging the summation back, the inner sum over a becomes the exact coverage sum at representative v.val, which equals 1 by hexact. Summing 1 over the n elements of ℤ/nℤ yields n.

    lines 39–56

    uses sum_comm, sum_congr, zmod_sum_sub_eq_sum

      have hN (j : ℕ) (hj : j < m) :
          (∑ p : ZMod n, cycle_power_dyadic_pair_count m j (y p)) = n := by
        unfold cycle_power_dyadic_pair_count
        rw [sum_comm]
        calc
          _ = ∑ a ∈ range (2^j), ∑ v : ZMod n,
              (y (v-(a : ZMod n)) a && y (v-(a : ZMod n)) (a+2^m-2^j)).toNat := by
            apply sum_congr rfl
            intro a ha
            exact zmod_sum_sub_eq_sum n _ (a : ZMod n)
          _ = ∑ v : ZMod n, ∑ a ∈ range (2^j),
              (y (v-(a : ZMod n)) a && y (v-(a : ZMod n)) (a+2^m-2^j)).toNat := sum_comm
          _ = ∑ v : ZMod n, 1 := by
            apply sum_congr rfl
            intro v hv
            simp_rw [hshift]
            exact hexact j hj (v.val : ℤ)
          _ = n := by simp
  5. For each scale 1 ≤ j < m, the sum over all classes of the neighbour pair counts is at least n.

    Exchanging sums and reindexing with sum_comm, sum_congr, and zmod_sum_sub_eq_sum, the total neighbour pair count becomes the sum over v ∈ ℤ/nℤ of the neighbour pairs at representative v.val. By the neighbour coverage hypothesis hcover, every v admits at least one witness a < 2^j + 1 where both bits are active. Bounding the sum from below by this single term using single_le_sum, each class contributes at least 1, so the sum over all n classes is at least n by sum_le_sum.

    lines 57–85

    uses sum_comm, sum_congr, zmod_sum_sub_eq_sum, sum_le_sum, single_le_sum

      have hM (j : ℕ) (hj0 : 1 ≤ j) (hj : j < m) :
          n ≤ (∑ p : ZMod n, cycle_power_dyadic_neighbour_pair_count m j (y p)) := by
        unfold cycle_power_dyadic_neighbour_pair_count
        rw [sum_comm]
        have heq : (∑ a ∈ range (2^j+1), ∑ p : ZMod n,
              (y p a && y p (a+2^m-2^j-1)).toNat) =
            ∑ v : ZMod n, ∑ a ∈ range (2^j+1),
              (x ((v.val : ℤ)-(a : ℤ)) a &&
                x ((v.val : ℤ)-(a : ℤ)) (a+2^m-2^j-1)).toNat := by
          calc
            _ = ∑ a ∈ range (2^j+1), ∑ v : ZMod n,
                (y (v-(a : ZMod n)) a &&
                  y (v-(a : ZMod n)) (a+2^m-2^j-1)).toNat := by
              apply sum_congr rfl
              intro a ha
              exact zmod_sum_sub_eq_sum n _ (a : ZMod n)
            _ = _ := by rw [sum_comm]; simp_rw [hshift]
        rw [heq]
        calc
          n = ∑ v : ZMod n, 1 := by simp
          _ ≤ _ := by
            apply sum_le_sum
            intro v hv
            obtain ⟨a, ha, ha0, ha1⟩ := hcover j hj0 hj (v.val : ℤ)
            have he := single_le_sum (fun (b : ℕ) _ => Nat.zero_le
              ((x ((v.val : ℤ)-(b : ℤ)) b &&
                x ((v.val : ℤ)-(b : ℤ)) (b+2^m-2^j-1)).toNat))
              (mem_range.mpr ha)
            simpa only [ha0, ha1, Bool.true_and, Bool.toNat_true] using he
  6. Under the contradiction assumption, each class satisfies the weighted bound ∑_{j=1}^{m-1} 2^j M(j) ≤ N(1) + ∑_{j=2}^{m-1} 2^j N(j).

    Applying cycle_power_dyadic_neighbour_weight_bound to y p using active boundary bits (hroot) and tightness (htight), the upper bound contains an extra term 2^(m-1) * (y p (2^(m-1)-1) + y p (2^(m-1))). Under the contradiction hypothesis hnone, both central bits are false by Bool.eq_false_iff.mpr, so their numeric values are 0 and this term vanishes.

    lines 86–100

    uses cycle_power_dyadic_neighbour_weight_bound, Bool.eq_false_iff.mpr

      have hb (p : ZMod n) :
          (range m).sum (fun j => if 1 ≤ j then
            2^j * cycle_power_dyadic_neighbour_pair_count m j (y p) else 0) ≤
          cycle_power_dyadic_pair_count m 1 (y p) +
            (range m).sum (fun j => if 2 ≤ j then
              2^j * cycle_power_dyadic_pair_count m j (y p) else 0) := by
        have hh := cycle_power_dyadic_neighbour_weight_bound m hm (y p)
          (hroot p) (htight (p.val : ℤ))
        change _ ≤ _ + _ + _ at hh
        have h0 : y p (2^(m-1)-1) = false := by
          exact Bool.eq_false_iff.mpr (hnone (p.val : ℤ)).1
        have h1 : y p (2^(m-1)) = false := by
          exact Bool.eq_false_iff.mpr (hnone (p.val : ℤ)).2
        simpa only [cycle_power_dyadic_pair_count, cycle_power_dyadic_neighbour_pair_count,
          h0, h1, Bool.toNat_false, zero_add, mul_zero, add_zero] using hh
  7. The coefficient sums A = ∑_{j=1}^{m-1} 2^j and B = ∑_{j=2}^{m-1} 2^j satisfy A = B + 2.

    For every index j, the indicator function for 1 ≤ j is the sum of the indicator for 2 ≤ j and the indicator for j = 1. Distributing the sum with sum_add_distrib, the j = 1 term yields 2^1 = 2 while the remaining terms sum to B.

    lines 101–113

    uses sum_add_distrib

      let A := (range m).sum (fun j => if 1 ≤ j then 2^j else 0)
      let B := (range m).sum (fun j => if 2 ≤ j then 2^j else 0)
      have hAB : A = B+2 := by
        have he (j : ℕ) : (if 1 ≤ j then 2^j else 0) =
            (if 2 ≤ j then 2^j else 0) + (if j=1 then 2 else 0) := by
          by_cases h0 : j=0
          · subst j; decide
          by_cases h1 : j=1
          · subst j; decide
          simp [show 1 ≤ j by omega, show 2 ≤ j by omega, h1]
        dsimp [A, B]
        simp_rw [he, sum_add_distrib]
        simp [show 1 < m by omega]
  8. The global sum of weighted neighbour pair counts is at least n * A.

    Exchanging the order of summation using sum_comm and distributing multiplication across terms with mul_sum, mul_ite, and mul_zero, the sum becomes ∑_{j=1}^{m-1} 2^j ∑_p M(j). Since each inner sum is at least n by hM, multiplying by 2^j preserves the inequality by Nat.mul_le_mul_left. Summing over 1 ≤ j < m via sum_le_sum gives n * A as the lower bound.

    lines 114–129

    uses sum_comm, mul_sum, mul_ite, mul_zero, sum_congr, sum_le_sum, Nat.mul_le_mul_left

      have hL : n*A ≤ ∑ p : ZMod n, (range m).sum (fun j => if 1 ≤ j then
          2^j * cycle_power_dyadic_neighbour_pair_count m j (y p) else 0) := by
        rw [sum_comm]
        calc
          n*A = (range m).sum (fun j => if 1 ≤ j then 2^j*n else 0) := by
            simp only [A, mul_sum, mul_ite, mul_zero]
            apply sum_congr rfl
            intro j hj
            split_ifs <;> ring
          _ ≤ _ := by
            apply sum_le_sum
            intro j hj
            by_cases hj0 : 1 ≤ j
            · simp only [hj0, ↓reduceIte, ← mul_sum]
              exact Nat.mul_le_mul_left (2^j) (hM j hj0 (mem_range.mp hj))
            · simp [hj0]
  9. The global sum of the dyadic pair upper bounds evaluates to n + n * B.

    Distributing the sum over classes with sum_add_distrib, the first term ∑_p N(1) evaluates to n by hN. In the second term, exchanging sums with sum_comm and substituting ∑_p N(j) = n for every j ≥ 2 via hN evaluates the sum to ∑_{j=2}^{m-1} 2^j * n = n * B, using mul_sum, mul_ite, and mul_zero. Adding both components gives n + n * B.

    lines 130–146

    uses sum_add_distrib, sum_comm, sum_congr, mul_sum, mul_ite, mul_zero

      have hR : (∑ p : ZMod n, (cycle_power_dyadic_pair_count m 1 (y p) +
            (range m).sum (fun j => if 2 ≤ j then
              2^j * cycle_power_dyadic_pair_count m j (y p) else 0))) = n+n*B := by
        rw [sum_add_distrib, hN 1 (by omega), sum_comm]
        congr 1
        calc
          _ = (range m).sum (fun j => if 2 ≤ j then 2^j*n else 0) := by
            apply sum_congr rfl
            intro j hj
            by_cases hj0 : 2 ≤ j
            · simp only [hj0, ↓reduceIte, ← mul_sum, hN j (mem_range.mp hj)]
            · simp [hj0]
          _ = n*B := by
            simp only [B, mul_sum, mul_ite, mul_zero]
            apply sum_congr rfl
            intro j hj
            split_ifs <;> ring
  10. The upper and lower bounds force 2n ≤ n, which contradicts n > 0. automation

    Summing the pointwise inequality hb over all p ∈ ℤ/nℤ with sum_le_sum shows that the global neighbour sum is at most the global pair sum. Combining this with the lower bound n * A ≤ LHS from hL and the evaluation RHS = n + n * B from hR yields n * A ≤ n + n * B. Substituting A = B + 2 from hAB gives n(B + 2) ≤ n + n * B, which simplifies to n * B + 2n ≤ n * B + n, or 2n ≤ n. Because n > 0, nlinarith closes the goal by contradiction.

    lines 147–149

    uses sum_le_sum

      have htot := sum_le_sum (s := (univ : Finset (ZMod n))) (fun p _ => hb p)
      rw [hR] at htot
      nlinarith only [hL, htot, hAB, hn]
ZMod.intCast_eq_iff
An integer casts to an element of ℤ/pℤ if and only if it differs from the representative by an integer multiple of p.
congrArg
Applying a function to equal inputs yields equal outputs.
Int.cast_sub
Casting integers into a ring preserves subtraction.
Int.cast_natCast
The natural cast into integers composed with the cast into another ring equals the direct natural cast.
ZMod.natCast_zmod_val
Casting the canonical representative in {0, ..., n - 1} back into ℤ/nℤ recovers the original element.
pow_zero
Any element raised to the zeroth power equals 1.
sum_range_one
A sum over the range {0} evaluates to the value of the summand at 0.
Nat.cast_zero
The cast of the natural number 0 into a ring is 0.
sub_zero
Subtracting 0 from an element leaves it unchanged.
Nat.zero_add
Adding 0 to a natural number leaves it unchanged.
sum_comm
The order of summation in a finite double sum can be exchanged.
sum_congr
Two finite sums are equal if their index sets are equal and their summands agree pointwise.
zmod_sum_sub_eq_sum
Summing a function over ℤ/nℤ is invariant under shifting the argument by a constant residue class.
sum_le_sum
If f ≤ g pointwise on a finite set, the sum of f is at most the sum of g.
single_le_sum
A single non-negative term in a finite sum is less than or equal to the total sum.
cycle_power_dyadic_neighbour_weight_bound
For a tight dyadic class with active endpoints, the weighted neighbour count is at most the weighted dyadic count plus 2^(m-1) times the sum of the two central position booleans.
Bool.eq_false_iff.mpr
A boolean value not equal to true is false.
sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of the first plus the sum of the second.
mul_sum
Multiplication by a constant distributes over a finite sum.
mul_ite
Multiplying an if-then-else expression by a factor multiplies both branches.
mul_zero
Multiplying any element by 0 gives 0.
Nat.mul_le_mul_left
Multiplying both sides of a natural number inequality by a factor preserves the inequality.

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

open Finsettheorem cycle_power_dyadic_central_position_exists    (m n : ℕ) (hm : 2 ≤ m) (hn : 0 < n) (x : ℤ → ℕ → Bool)    (hperiod : ∀ p a, x (p + (n : ℤ)) a = x p a)    (htight : ∀ p, cycle_power_dyadic_class_weight m (x p) =      (Finset.range (2 ^ m)).sum (fun a => (x p a).toNat))    (hexact : ∀ j < m, ∀ v : ℤ, (Finset.range (2 ^ j)).sum (fun a =>      (x (v - (a : ℤ)) a && x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j)).toNat) = 1)    (hcover : ∀ j : ℕ, 1 ≤ j → j < m → ∀ v : ℤ,      ∃ a : ℕ, a < 2 ^ j + 1 ∧ x (v - (a : ℤ)) a = true ∧        x (v - (a : ℤ)) (a + 2 ^ m - 2 ^ j - 1) = true) :    ∃ p : ℤ, x p (2 ^ (m - 1) - 1) = true ∨ x p (2 ^ (m - 1)) = true := by  classical  by_contra hnone  push_neg at hnone  letI : NeZero n := ⟨by omega⟩  let y : ZMod n → ℕ → Bool := fun p a => x (p.val : ℤ) a  have hval (v : ℤ) (a : ℕ) : y (v : ZMod n) a = x v a := by    obtain ⟨z, hz⟩ := (ZMod.intCast_eq_iff n v (v : ZMod n)).mp rfl    have hp : Function.Periodic (fun p : ℤ => x p a) (n : ℤ) := fun p => hperiod p a    have hh := hp.int_mul z (((v : ZMod n).val : ℤ))    have he : ((v : ZMod n).val : ℤ)+z*(n : ℤ)=v := by      calc        _ = ((v : ZMod n).val : ℤ)+(n : ℤ)*z := by ring        _ = v := hz.symm    exact hh.symm.trans (congrArg (fun w : ℤ => x w a) he)  have hshift (v : ZMod n) (a j : ℕ) :      y (v-(a : ZMod n)) j = x ((v.val : ℤ)-(a : ℤ)) j := by    have hh := hval ((v.val : ℤ)-(a : ℤ)) j    simpa only [Int.cast_sub, Int.cast_natCast, ZMod.natCast_zmod_val] using hh  have hroot (p : ZMod n) : y p 0 = true ∧ y p (2^m-1) = true := by    have hh := hexact 0 (by omega) (p.val : ℤ)    norm_num only [pow_zero, sum_range_one, Nat.cast_zero, sub_zero,      Nat.zero_add] at hh    dsimp [y]    cases h0 : x (p.val : ℤ) 0 <;>      cases h1 : x (p.val : ℤ) (2^m-1) <;> simp_all  have hN (j : ℕ) (hj : j < m) :      (∑ p : ZMod n, cycle_power_dyadic_pair_count m j (y p)) = n := by    unfold cycle_power_dyadic_pair_count    rw [sum_comm]    calc      _ = ∑ a ∈ range (2^j), ∑ v : ZMod n,          (y (v-(a : ZMod n)) a && y (v-(a : ZMod n)) (a+2^m-2^j)).toNat := by        apply sum_congr rfl        intro a ha        exact zmod_sum_sub_eq_sum n _ (a : ZMod n)      _ = ∑ v : ZMod n, ∑ a ∈ range (2^j),          (y (v-(a : ZMod n)) a && y (v-(a : ZMod n)) (a+2^m-2^j)).toNat := sum_comm      _ = ∑ v : ZMod n, 1 := by        apply sum_congr rfl        intro v hv        simp_rw [hshift]        exact hexact j hj (v.val : ℤ)      _ = n := by simp  have hM (j : ℕ) (hj0 : 1 ≤ j) (hj : j < m) :      n ≤ (∑ p : ZMod n, cycle_power_dyadic_neighbour_pair_count m j (y p)) := by    unfold cycle_power_dyadic_neighbour_pair_count    rw [sum_comm]    have heq : (∑ a ∈ range (2^j+1), ∑ p : ZMod n,          (y p a && y p (a+2^m-2^j-1)).toNat) =        ∑ v : ZMod n, ∑ a ∈ range (2^j+1),          (x ((v.val : ℤ)-(a : ℤ)) a &&            x ((v.val : ℤ)-(a : ℤ)) (a+2^m-2^j-1)).toNat := by      calc        _ = ∑ a ∈ range (2^j+1), ∑ v : ZMod n,            (y (v-(a : ZMod n)) a &&              y (v-(a : ZMod n)) (a+2^m-2^j-1)).toNat := by          apply sum_congr rfl          intro a ha          exact zmod_sum_sub_eq_sum n _ (a : ZMod n)        _ = _ := by rw [sum_comm]; simp_rw [hshift]    rw [heq]    calc      n = ∑ v : ZMod n, 1 := by simp      _ ≤ _ := by        apply sum_le_sum        intro v hv        obtain ⟨a, ha, ha0, ha1⟩ := hcover j hj0 hj (v.val : ℤ)        have he := single_le_sum (fun (b : ℕ) _ => Nat.zero_le          ((x ((v.val : ℤ)-(b : ℤ)) b &&            x ((v.val : ℤ)-(b : ℤ)) (b+2^m-2^j-1)).toNat))          (mem_range.mpr ha)        simpa only [ha0, ha1, Bool.true_and, Bool.toNat_true] using he  have hb (p : ZMod n) :      (range m).sum (fun j => if 1 ≤ j then        2^j * cycle_power_dyadic_neighbour_pair_count m j (y p) else 0) ≤      cycle_power_dyadic_pair_count m 1 (y p) +        (range m).sum (fun j => if 2 ≤ j then          2^j * cycle_power_dyadic_pair_count m j (y p) else 0) := by    have hh := cycle_power_dyadic_neighbour_weight_bound m hm (y p)      (hroot p) (htight (p.val : ℤ))    change _ ≤ _ + _ + _ at hh    have h0 : y p (2^(m-1)-1) = false := by      exact Bool.eq_false_iff.mpr (hnone (p.val : ℤ)).1    have h1 : y p (2^(m-1)) = false := by      exact Bool.eq_false_iff.mpr (hnone (p.val : ℤ)).2    simpa only [cycle_power_dyadic_pair_count, cycle_power_dyadic_neighbour_pair_count,      h0, h1, Bool.toNat_false, zero_add, mul_zero, add_zero] using hh  let A := (range m).sum (fun j => if 1 ≤ j then 2^j else 0)  let B := (range m).sum (fun j => if 2 ≤ j then 2^j else 0)  have hAB : A = B+2 := by    have he (j : ℕ) : (if 1 ≤ j then 2^j else 0) =        (if 2 ≤ j then 2^j else 0) + (if j=1 then 2 else 0) := by      by_cases h0 : j=0      · subst j; decide      by_cases h1 : j=1      · subst j; decide      simp [show 1 ≤ j by omega, show 2 ≤ j by omega, h1]    dsimp [A, B]    simp_rw [he, sum_add_distrib]    simp [show 1 < m by omega]  have hL : n*A ≤ ∑ p : ZMod n, (range m).sum (fun j => if 1 ≤ j then      2^j * cycle_power_dyadic_neighbour_pair_count m j (y p) else 0) := by    rw [sum_comm]    calc      n*A = (range m).sum (fun j => if 1 ≤ j then 2^j*n else 0) := by        simp only [A, mul_sum, mul_ite, mul_zero]        apply sum_congr rfl        intro j hj        split_ifs <;> ring      _ ≤ _ := by        apply sum_le_sum        intro j hj        by_cases hj0 : 1 ≤ j        · simp only [hj0, ↓reduceIte, ← mul_sum]          exact Nat.mul_le_mul_left (2^j) (hM j hj0 (mem_range.mp hj))        · simp [hj0]  have hR : (∑ p : ZMod n, (cycle_power_dyadic_pair_count m 1 (y p) +        (range m).sum (fun j => if 2 ≤ j then          2^j * cycle_power_dyadic_pair_count m j (y p) else 0))) = n+n*B := by    rw [sum_add_distrib, hN 1 (by omega), sum_comm]    congr 1    calc      _ = (range m).sum (fun j => if 2 ≤ j then 2^j*n else 0) := by        apply sum_congr rfl        intro j hj        by_cases hj0 : 2 ≤ j        · simp only [hj0, ↓reduceIte, ← mul_sum, hN j (mem_range.mp hj)]        · simp [hj0]      _ = n*B := by        simp only [B, mul_sum, mul_ite, mul_zero]        apply sum_congr rfl        intro j hj        split_ifs <;> ring  have htot := sum_le_sum (s := (univ : Finset (ZMod n))) (fun p _ => hb p)  rw [hR] at htot  nlinarith only [hL, htot, hAB, hn]
See it in the graphDiscuss this resultChallenge it