AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_weighted_threshold_weight_ge

theoremverified

Common-threshold coupling of any finite natural-weighted mixture of dyadic profiles cannot decrease total dyadic class weight.

Statement

theorem cycle_power_dyadic_weighted_threshold_weight_ge
    {ι : Type*} (m : ℕ) (S : Finset ι) (w : ι → ℕ) (B : ι → ℕ → Bool) :
    let N := S.sum w
    let c := fun j => S.sum (fun i => w i * (B i j).toNat)
    S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) ≤
      (range N).sum (fun r => cycle_power_dyadic_class_weight m
        (fun j => decide (r < c j)))
Source
Standard finite common-threshold coupling, formalized as a helper for OP-205 / RT-1, arXiv:2610.15635. Used to compress whole-class linear relaxations. This does not prove the remaining shape implication and is not claimed novel or research-level.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The dyadic class weight of a profile is a positive linear combination of pairwise bit conjunctions: a boundary term at distance 2^m - 1, and dyadic block terms at distances 2^m - 2^j. By threshold coupling dominance (bool_weighted_mixture_threshold_dominates), the co-occurrence frequency of any coordinate pair under the threshold coupling bounds from above its weighted co-occurrence in the original mixture. Summing this pairwise dominance term-by-term across all pairs occurring in the definition of the dyadic class weight shows that coupling cannot decrease the total weight.

  1. Define the total weight N, marginal counts c, and threshold profiles T, and establish coordinate-pair domination.

    We introduce the total weight N = ∑_{i ∈ S} w_i, the weighted marginal counts c(j) = ∑_{i ∈ S} w_i B_i(j), and the threshold profiles T_r(j) = [r < c(j)] for r < N. By bool_weighted_mixture_threshold_dominates, threshold coupling dominates the mixture on every pair of coordinates: for all a and b, the weighted sum of conjunctions ∑_{i ∈ S} w_i (B_i(a) ∧ B_i(b)) is bounded above by the threshold sum ∑_{r < N} (T_r(a) ∧ T_r(b)).

    lines 12–16

    uses bool_weighted_mixture_threshold_dominates

      dsimp only
      let N := S.sum w
      let c := fun j => S.sum (fun i => w i * (B i j).toNat)
      let T := fun r j => decide (r < c j)
      have hdom := (bool_weighted_mixture_threshold_dominates S w B).2.1
  2. The weighted sum of the boundary ("ends") terms is bounded by the threshold coupled sum.

    Instantiating pairwise domination at coordinates 0 and 2^m - 1 and multiplying by 2 yields 2 ∑_{i ∈ S} w_i (B_i(0) ∧ B_i(2^m - 1)) ≤ 2 ∑_{r < N} (T_r(0) ∧ T_r(2^m - 1)). Distributing the scalar 2 inside the summations gives the desired bound for the boundary term.

    lines 17–20

    uses Nat.mul_le_mul_left, mul_sum, mul_left_comm

      have hends : (S.sum (fun i => w i * (2 * (B i 0 && B i (2^m-1)).toNat))) ≤
          (range N).sum (fun r => 2 * (T r 0 && T r (2^m-1)).toNat) := by
        have h := Nat.mul_le_mul_left 2 (hdom 0 (2^m-1))
        simpa only [mul_sum, T, c, N, mul_left_comm] using h
  3. To bound the remaining dyadic terms, it suffices to prove the inequality scale-by-scale for each j < m.

    Distributing the weights w_i into the summation over j and swapping the order of summation between the mixture index i ∈ S (respectively, the threshold index r) and the scale index j ∈ {0, …, m - 1} reduces the inequality to comparing the summands for each j individually.

    lines 21–29

    uses mul_sum, sum_comm, sum_le_sum

      have hrest :
          S.sum (fun i => w i * (range m).sum (fun j => if j=0 then 0 else
            (range (2^j)).sum (fun a => (B i a && B i (a+2^m-2^j)).toNat))) ≤
          (range N).sum (fun r => (range m).sum (fun j => if j=0 then 0 else
            (range (2^j)).sum (fun a => (T r a && T r (a+2^m-2^j)).toNat))) := by
        simp only [mul_sum]
        conv_lhs => rw [sum_comm]
        conv_rhs => rw [sum_comm]
        apply sum_le_sum
  4. The inequality holds for each dyadic scale j.

    We split into cases on j. When j = 0, both sides vanish. When j ≠ 0, swapping the summation over the mixture index and the offset a ∈ {0, …, 2^j - 1} allows us to apply pairwise domination to each coordinate pair (a, a + 2^m - 2^j) individually.

    lines 30–36

    uses mul_sum, sum_comm, sum_le_sum

        intro j hj
        by_cases hj0 : j=0
        · simp [hj0]
        · simp only [hj0, ↓reduceIte, mul_sum]
          conv_lhs => rw [sum_comm]
          conv_rhs => rw [sum_comm]
          exact sum_le_sum (fun a ha => hdom a (a+2^m-2^j))
  5. The total weighted dyadic class weight is bounded by the threshold coupled dyadic class weight.

    Unfolding cycle_power_dyadic_class_weight decomposes the total weight into the boundary term and the dyadic block sums. Adding the boundary inequality hends and the internal blocks inequality hrest yields the result.

    lines 37–38

    uses cycle_power_dyadic_class_weight, mul_add, sum_add_distrib, add_le_add

      simp only [cycle_power_dyadic_class_weight, mul_add, sum_add_distrib]
      exact add_le_add hends hrest
bool_weighted_mixture_threshold_dominates
For any finite weighted mixture of Boolean profiles, the threshold coupling preserves marginal frequencies and dominates the mixture's co-occurrence frequency on any coordinate pair: ∑ w_i (B_i(a) ∧ B_i(b)) ≤ ∑ (T_r(a) ∧ T_r(b)).
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers by a factor on the left preserves the inequality: n ≤ m implies k * n ≤ k * m.
mul_sum
Multiplication distributes over a finite sum: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
mul_left_comm
Multiplication in a commutative semigroup is left-commutative: a * (b * c) = b * (a * c).
sum_comm
Double finite summations may be interchanged: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
sum_le_sum
A finite sum of pointwise less-than-or-equal terms is less than or equal to the sum of the upper bounds: (∀ i ∈ s, f i ≤ g i) implies ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
cycle_power_dyadic_class_weight
The dyadic class weight of a profile is defined as twice the conjunction of its boundary bits b(0) ∧ b(2^m - 1) plus the sum over scales j ∈ {1, …, m - 1} and offsets a < 2^j of the conjunctions b(a) ∧ b(a + 2^m - 2^j).
mul_add
Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
sum_add_distrib
The sum of a termwise sum over a finite set equals the sum of the two sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
add_le_add
Addition preserves inequalities: a ≤ b and c ≤ d imply a + c ≤ b + d.

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 Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_weighted_threshold_weight_ge    {ι : Type*} (m : ℕ) (S : Finset ι) (w : ι → ℕ) (B : ι → ℕ → Bool) :    let N := S.sum w    let c := fun j => S.sum (fun i => w i * (B i j).toNat)    S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) ≤      (range N).sum (fun r => cycle_power_dyadic_class_weight m        (fun j => decide (r < c j))) := by  dsimp only  let N := S.sum w  let c := fun j => S.sum (fun i => w i * (B i j).toNat)  let T := fun r j => decide (r < c j)  have hdom := (bool_weighted_mixture_threshold_dominates S w B).2.1  have hends : (S.sum (fun i => w i * (2 * (B i 0 && B i (2^m-1)).toNat))) ≤      (range N).sum (fun r => 2 * (T r 0 && T r (2^m-1)).toNat) := by    have h := Nat.mul_le_mul_left 2 (hdom 0 (2^m-1))    simpa only [mul_sum, T, c, N, mul_left_comm] using h  have hrest :      S.sum (fun i => w i * (range m).sum (fun j => if j=0 then 0 else        (range (2^j)).sum (fun a => (B i a && B i (a+2^m-2^j)).toNat))) ≤      (range N).sum (fun r => (range m).sum (fun j => if j=0 then 0 else        (range (2^j)).sum (fun a => (T r a && T r (a+2^m-2^j)).toNat))) := by    simp only [mul_sum]    conv_lhs => rw [sum_comm]    conv_rhs => rw [sum_comm]    apply sum_le_sum    intro j hj    by_cases hj0 : j=0    · simp [hj0]    · simp only [hj0, ↓reduceIte, mul_sum]      conv_lhs => rw [sum_comm]      conv_rhs => rw [sum_comm]      exact sum_le_sum (fun a ha => hdom a (a+2^m-2^j))  simp only [cycle_power_dyadic_class_weight, mul_add, sum_add_distrib]  exact add_le_add hends hrest
See it in the graphDiscuss this resultChallenge it