cycle_power_dyadic_central_position_exists
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 2
- cycle_power_dyadic_model_dvd_of_endpoint_overlapA periodic optimal dyadic class model whose old active classes intersect the next endpoint class has period divisible by the dyadic…
- cycle_power_dyadic_model_dvd_of_label_periodA finite-period tight dyadic class model with proper labels, exact dyadic edges, neighbour coverage, and full-radius label period has…
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.
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}.
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
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 ℤ.
uses
ZMod.intCast_eq_iff,congrArg,Int.cast_sub,Int.cast_natCast,ZMod.natCast_zmod_valhave 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
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.
uses
pow_zero,sum_range_one,Nat.cast_zero,sub_zero,Nat.zero_addhave 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
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.
uses
sum_comm,sum_congr,zmod_sum_sub_eq_sumhave 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
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.
uses
sum_comm,sum_congr,zmod_sum_sub_eq_sum,sum_le_sum,single_le_sumhave 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
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.
uses
cycle_power_dyadic_neighbour_weight_bound,Bool.eq_false_iff.mprhave 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
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.
uses
sum_add_distriblet 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]
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.
uses
sum_comm,mul_sum,mul_ite,mul_zero,sum_congr,sum_le_sum,Nat.mul_le_mul_lefthave 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]
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.
uses
sum_add_distrib,sum_comm,sum_congr,mul_sum,mul_ite,mul_zerohave 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
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.
uses
sum_le_sumhave 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.
- The reduction from the integer configuration x on ℤ to y on ℤ/nℤ and proving shift compatibility (hval, hshift) is a formal device to turn periodic properties on ℤ into finite sums over the quotient group ℤ/nℤ.
- The final contradiction at step 10 is closed by the nonlinear arithmetic tactic nlinarith from the linear inequality n * A ≤ n + n * B, A = B + 2, and n > 0.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]