AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_weighted_threshold_tight

theoremverified

For positive dyadic exponent, every common-threshold profile below total mixture mass is tight when all original profiles of the natural-weighted finite mixture are tight.

Statement

theorem cycle_power_dyadic_weighted_threshold_tight
    {ι : Type*} (m : ℕ) (hm : 1 ≤ m) (S : Finset ι) (w : ι → ℕ)
    (B : ι → ℕ → Bool)
    (htight : ∀ i ∈ S, cycle_power_dyadic_class_weight m (B i) =
      (range (2^m)).sum (fun a => (B i a).toNat)) :
    let N := S.sum w
    let c := fun j => S.sum (fun i => w i * (B i j).toNat)
    ∀ r < N, cycle_power_dyadic_class_weight m (fun j => decide (r < c j)) =
      (range (2^m)).sum (fun a => (decide (r < c a)).toNat)
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 4

The proof, explained

The proof establishes that every common-threshold profile $T_r$ below the total mixture weight $N$ is tight by a squeezing contradiction argument. Marginal preservation shows that the total cardinality of all threshold profiles equals the weighted cardinality of the original profiles, which equals the total weighted class weight because all original profiles are tight. A general threshold bound then ensures that this total cardinality is at most the total class weight of the threshold profiles. Since each individual threshold profile's class weight cannot exceed its cardinality, any profile failing to be tight would force the sum of class weights to be strictly less than the sum of cardinalities, producing a contradiction.

  1. Set up notation for the mixture mass, column counts, and threshold profiles, restating the goal in terms of threshold profiles $T_r$.

    We introduce abbreviations for the total mixture mass $N = \sum_{i \in S} w_i$, column counts $c(j) = \sum_{i \in S} w_i B_i(j)$, and threshold indicator profiles $T_r(j) = [r < c(j)]$. The target statement is that for every threshold $r < N$, the profile $T_r$ is tight, meaning its dyadic cycle-power class weight equals its cardinality $\sum_{a < 2^m} T_r(a)$.

    lines 14–19

      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)
      change ∀ r < N, cycle_power_dyadic_class_weight m (T r) =
        (range (2^m)).sum (fun a => (T r a).toNat)
  2. The total size of the threshold profiles equals the weighted total size of the original profiles: $\sum_{r < N} |T_r| = \sum_{i \in S} w_i |B_i|$.

    By marginal preservation (`bool_weighted_mixture_threshold_dominates`), summing threshold indicators over all $r < N$ yields the column count: $\sum_{r < N} T_r(a) = c(a)$. Exchanging the order of summation (`sum_comm`) transforms the total threshold size $\sum_{r < N} \sum_{a < 2^m} T_r(a)$ into $\sum_{a < 2^m} c(a)$. Substituting the definition of $c(a)$, swapping sums again (`sum_comm`), and distributing the weights (`mul_sum`) yields the weighted sum of original profile sizes $\sum_{i \in S} w_i \sum_{a < 2^m} B_i(a)$.

    lines 20–27

    uses bool_weighted_mixture_threshold_dominates, sum_comm, mul_sum

      have hmargin := (bool_weighted_mixture_threshold_dominates S w B).1
      have hcard : (range N).sum (fun r => (range (2^m)).sum (fun a => (T r a).toNat)) =
          S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := by
        rw [sum_comm]
        simp_rw [show ∀ a, (range N).sum (fun r => (T r a).toNat) = c a from hmargin]
        dsimp only [c]
        rw [sum_comm]
        simp only [mul_sum]
  3. The weighted class weight of the mixture is at most the total threshold class weight, and equals the weighted sum of original sizes.

    By `cycle_power_dyadic_weighted_threshold_weight_ge`, the total threshold class weight upper-bounds the weighted original class weight: $\sum_{i \in S} w_i \mathrm{weight}(B_i) \le \sum_{r < N} \mathrm{weight}(T_r)$. Furthermore, because each original profile $B_i$ is tight by hypothesis (`htight`), we have $\mathrm{weight}(B_i) = |B_i|$, so by congruence (`sum_congr`, `congrArg`) the weighted sum of original class weights equals the weighted sum of their sizes.

    lines 28–31

    uses cycle_power_dyadic_weighted_threshold_weight_ge, sum_congr, congrArg

      have hW := cycle_power_dyadic_weighted_threshold_weight_ge m S w B
      have hOld : S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) =
          S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := by
        exact sum_congr rfl (fun i hi => congrArg (fun z => w i * z) (htight i hi))
  4. The total cardinality of all threshold profiles is at most their total class weight: $\sum_{r < N} |T_r| \le \sum_{r < N} \mathrm{weight}(T_r)$.

    We chain the equalities and inequality established in the preceding steps: the sum of threshold sizes equals the weighted sum of original sizes, which equals the weighted sum of original class weights, which is bounded above by the sum of threshold class weights.

    lines 32–37

      have hTotal : (range N).sum (fun r => (range (2^m)).sum (fun a => (T r a).toNat)) ≤
          (range N).sum (fun r => cycle_power_dyadic_class_weight m (T r)) := by
        calc
          _ = S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := hcard
          _ = S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) := hOld.symm
          _ ≤ _ := hW
  5. If any threshold profile $T_r$ (for $r < N$) were not tight, its class weight would be strictly less than its cardinality.

    Fix $r < N$. For any profile, its class weight is at most its cardinality by `cycle_power_dyadic_class_weight_le`. Assuming for contradiction that $T_r$ is not tight, the weight cannot equal the cardinality, so linear arithmetic (`omega`) deduces that the strict inequality $\mathrm{weight}(T_r) < |T_r|$ must hold.

    lines 38–42

    uses cycle_power_dyadic_class_weight_le

      intro r hr
      have hle := cycle_power_dyadic_class_weight_le m hm (T r)
      by_contra hne
      have hlt : cycle_power_dyadic_class_weight m (T r) <
          (range (2^m)).sum (fun a => (T r a).toNat) := by omega
  6. Every threshold profile $T_r$ for $r < N$ is tight.

    Summing the pointwise weak bounds $\mathrm{weight}(T_q) \le |T_q|$ across all $q < N$ together with the strict inequality $\mathrm{weight}(T_r) < |T_r|$ at index $r \in \mathrm{range}(N)$ (`mem_range`) via `sum_lt_sum` yields a strict inequality on total sums: $\sum_{q < N} \mathrm{weight}(T_q) < \sum_{q < N} |T_q|$. This contradicts the aggregate lower bound $\sum_{r < N} |T_r| \le \sum_{r < N} \mathrm{weight}(T_r)$ established earlier. Linear arithmetic (`omega`) closes the contradiction.

    lines 43–46

    uses sum_lt_sum, cycle_power_dyadic_class_weight_le, mem_range

      have hs := sum_lt_sum
        (fun q (_ : q ∈ range N) => cycle_power_dyadic_class_weight_le m hm (T q))
        ⟨r, mem_range.mpr hr, hlt⟩
      omega
bool_weighted_mixture_threshold_dominates
For a weighted mixture of boolean profiles, the threshold profiles preserve marginal column sums, dominate pairwise intersections, and preserve subset inclusions.
sum_comm
Swapping the order of two finite summations preserves the sum: $\sum_x \sum_y f(x, y) = \sum_y \sum_x f(x, y)$.
mul_sum
Multiplication distributes over a finite sum: $a \cdot \sum_i f(i) = \sum_i a \cdot f(i)$.
cycle_power_dyadic_weighted_threshold_weight_ge
The weighted sum of dyadic cycle-power class weights of the constituent profiles is bounded above by the sum of class weights of the threshold profiles.
sum_congr
Two finite sums are equal if their index sets are equal and their summands agree at every element of the index set.
congrArg
Equal inputs to a function yield equal outputs ($a_1 = a_2 \implies f(a_1) = f(a_2)$).
cycle_power_dyadic_class_weight_le
For dyadic exponent $m \ge 1$, the dyadic cycle-power class weight of a boolean profile is bounded above by its cardinality (number of true entries).
sum_lt_sum
If $f(i) \le g(i)$ for all elements of a finite set and $f(i) < g(i)$ for at least one element, then the sum of $f$ is strictly less than the sum of $g$.
mem_range
A natural number $m$ belongs to `Finset.range n` if and only if $m < 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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_weighted_threshold_tight    {ι : Type*} (m : ℕ) (hm : 1 ≤ m) (S : Finset ι) (w : ι → ℕ)    (B : ι → ℕ → Bool)    (htight : ∀ i ∈ S, cycle_power_dyadic_class_weight m (B i) =      (range (2^m)).sum (fun a => (B i a).toNat)) :    let N := S.sum w    let c := fun j => S.sum (fun i => w i * (B i j).toNat)    ∀ r < N, cycle_power_dyadic_class_weight m (fun j => decide (r < c j)) =      (range (2^m)).sum (fun a => (decide (r < c a)).toNat) := 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)  change ∀ r < N, cycle_power_dyadic_class_weight m (T r) =    (range (2^m)).sum (fun a => (T r a).toNat)  have hmargin := (bool_weighted_mixture_threshold_dominates S w B).1  have hcard : (range N).sum (fun r => (range (2^m)).sum (fun a => (T r a).toNat)) =      S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := by    rw [sum_comm]    simp_rw [show ∀ a, (range N).sum (fun r => (T r a).toNat) = c a from hmargin]    dsimp only [c]    rw [sum_comm]    simp only [mul_sum]  have hW := cycle_power_dyadic_weighted_threshold_weight_ge m S w B  have hOld : S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) =      S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := by    exact sum_congr rfl (fun i hi => congrArg (fun z => w i * z) (htight i hi))  have hTotal : (range N).sum (fun r => (range (2^m)).sum (fun a => (T r a).toNat)) ≤      (range N).sum (fun r => cycle_power_dyadic_class_weight m (T r)) := by    calc      _ = S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := hcard      _ = S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) := hOld.symm      _ ≤ _ := hW  intro r hr  have hle := cycle_power_dyadic_class_weight_le m hm (T r)  by_contra hne  have hlt : cycle_power_dyadic_class_weight m (T r) <      (range (2^m)).sum (fun a => (T r a).toNat) := by omega  have hs := sum_lt_sum    (fun q (_ : q ∈ range N) => cycle_power_dyadic_class_weight_le m hm (T q))    ⟨r, mem_range.mpr hr, hlt⟩  omega
See it in the graphDiscuss this resultChallenge it