AFTD Auto-Formalizing Theoretical Domains

accumulating_prefix_scales

theoremverifiedformalization

Accumulating prefix edge lengths across dyadic scales (Lemma 7). Let E be a finite set of edges with weights w_e > 0, and for a fixed phase θ ∈ [0, 1), let q_e = down_θ(w_e) and R_θ = {2^{θ+j} : j ∈ ℤ}. For any scale r, let W_θ(r) = ∑_{e ∈ E, q_e ≤ r} w_e, and let H = ∑_{e ∈ E} w_e / q_e. Then for any positive cutoff level B ∈ R_θ and any N ∈ ℕ, the sum of prefix scale weights over the first N dyadic scales descending from B satisfies ∑_{j=0}^{N-1} W_θ(B / 2^j) ≤ H B.

Statement

open Classical in
theorem accumulating_prefix_scales {α : Type*} (E : Finset α) (w : α → ℝ)
    (hw : ∀ e ∈ E, 0 < w e) (θ : ℝ) (hθ : 0 ≤ θ ∧ θ < 1)
    (B : ℝ) (hB : B ∈ shifted_dyadic_scales θ) (hB_pos : 0 < B) (N : ℕ) :
    ∑ j ∈ Finset.range N, prefix_scale_weight E w θ (B / (2 : ℝ) ^ j) ≤
      harmonic_scale_weight E w θ * B
Formalizes
arXiv:2611.17090 Lemma 7 -- Online Transportation via Shifted Geometric Scales
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • shifted_dyadic_scalesThe set of shifted dyadic scales R_θ = {2^{θ+j} : j ∈ ℤ} for a fixed phase θ ∈ ℝ.
  • down_scaleDownward rounding down_θ(z) to the nearest scale in R_θ bounded by z: 0 if z ≤ 0, and 2^{θ + ⌊log₂ z - θ⌋} if z > 0.
  • prefix_scale_weightThe accumulated weight W_θ(r) = ∑_{e ∈ E, down_θ(w_e) ≤ r} w_e of edges whose rounded length is at most r.
  • harmonic_scale_weightThe harmonic weight sum H(θ) = ∑_{e ∈ E} w_e / down_θ(w_e).
  • nat_succ_le_two_powFor every natural number j, (j + 1 : ℝ) ≤ 2^j.

Read back from the Lean

For any type α, finite set E ⊆ α, weight function w : α → ℝ such that w(e) > 0 for all e ∈ E, real number θ with 0 ≤ θ < 1, real number B belonging to shifted_dyadic_scales θ with B > 0, and natural number N: the sum over j from 0 to N - 1 of prefix_scale_weight E w θ (B / 2^j) is less than or equal to harmonic_scale_weight E w θ * B.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof bounds the accumulated prefix scale weight across the first N dyadic scales descending from B by exchanging the order of summation. For each edge e, the condition that its rounded dyadic scale q_e = down_scale θ (w e) is at most B / 2^j is equivalent to j ≤ d_e, where d_e is the difference between the cutoff exponent and the edge exponent. Bounding the number of valid scale indices j by d_e + 1 ≤ 2^(d_e) = B / q_e establishes that edge e contributes at most w_e * (B / q_e) across all scales. Swapping the sums over scales and edges and factoring out B yields the total bound H * B, where H is the harmonic scale weight.

  1. For any z > 0, down_scale θ z = 2^(θ + ⌊log₂ z - θ⌋).

    By definition, down_scale θ z checks whether z ≤ 0. Since z > 0, the condition z ≤ 0 is false (via not_le.mpr), so the if-then-else expression evaluates to 2^(θ + ⌊log₂ z - θ⌋) by if_neg.

    lines 5–6

    uses if_neg, not_le.mpr

      rw [down_scale]
      simp only [if_neg (not_le.mpr hz)]
  2. For B = 2^(θ + m) and z > 0, down_scale θ z ≤ B / 2^j is equivalent to j ≤ m - ⌊log₂ z - θ⌋.

    Using the explicit formula for down_scale on positive inputs, the left-hand side is 2^(θ + ⌊log₂ z - θ⌋). Rewriting 2^j as a real power via Real.rpow_natCast and applying Real.rpow_sub expresses B / 2^j as 2^(θ + m - j). Because 2 > 1, the exponential base 2 is strictly monotonic by Real.strictMono_rpow_of_base_gt_one, so the inequality between powers reduces to an inequality between exponents, which linear arithmetic rearranges to j ≤ m - ⌊log₂ z - θ⌋.

    lines 11–16

    uses accumulating_prefix_scales_ds_eq, Real.rpow_natCast, Real.rpow_sub, Real.strictMono_rpow_of_base_gt_one

      rw [accumulating_prefix_scales_ds_eq hz]
      have hdiv : B / 2 ^ j = 2 ^ (θ + (m:ℝ) - (j:ℝ)) := by
        rw [hB, ← Real.rpow_natCast (2:ℝ) j, ← Real.rpow_sub (by norm_num : (0:ℝ) < 2)]
      rw [hdiv]
      rw [(Real.strictMono_rpow_of_base_gt_one (by norm_num : (1:ℝ) < 2)).le_iff_le]
      constructor <;> intro h <;> linarith
  3. With k = ⌊log₂ z - θ⌋ and d = m - k, down_scale θ z ≤ B / 2^j is equivalent to j ≤ d, and B / down_scale θ z = 2^d.

    The scale inequality down_scale θ z ≤ B / 2^j simplifies to j ≤ d by applying accumulating_prefix_scales_ds_le_div_iff and expanding d = m - k. Similarly, dividing B = 2^(θ + m) by down_scale θ z = 2^(θ + k) gives 2^((θ + m) - (θ + k)) = 2^d by Real.rpow_sub and exponent cancellation.

    lines 22–34

    uses accumulating_prefix_scales_ds_le_div_iff, accumulating_prefix_scales_ds_eq, Real.rpow_sub

      set k : ℤ := ⌊Real.logb 2 z - θ⌋ with hk
      set d : ℤ := m - k with hd
      have hmem : ∀ j : ℕ, (down_scale θ z ≤ B / 2 ^ j) ↔ (j:ℝ) ≤ (d:ℝ) := by
        intro j
        rw [accumulating_prefix_scales_ds_le_div_iff hB hz j]
        have h1 : (m:ℝ) - (⌊Real.logb 2 z - θ⌋ : ℝ) = (d:ℝ) := by
          rw [hd]; push_cast; ring
        rw [h1]
      have hBq : B / down_scale θ z = 2 ^ (d:ℝ) := by
        rw [accumulating_prefix_scales_ds_eq hz, hB, ← Real.rpow_sub (by norm_num : (0:ℝ) < 2)]
        congr 1
        rw [hd, hk]; push_cast; ring
      rw [hBq]
  4. If d ≥ 0, the number of scale indices j < N such that down_scale θ z ≤ B / 2^j is at most 2^d.

    When d ≥ 0, we can convert d to a natural number d.toNat. Any index j satisfying the condition must satisfy j ≤ d, so j < d.toNat + 1. The filtered set of indices is therefore a subset of Finset.range (d.toNat + 1), which has cardinality d.toNat + 1. Applying the inequality n + 1 ≤ 2^n (nat_succ_le_two_pow) to d.toNat bounds the cardinality by 2^(d.toNat) = 2^d.

    lines 35–58

    uses Int.toNat_of_nonneg, Finset.mem_range, Finset.mem_filter, Finset.card_le_card, Finset.card_range, Nat.cast_add, Nat.cast_one, nat_succ_le_two_pow, Real.rpow_natCast

      by_cases hd0 : 0 ≤ d
      · have hdcast : (d.toNat : ℝ) = (d:ℝ) := by
          have h := Int.toNat_of_nonneg hd0
          exact_mod_cast h
        have hsub : Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N) ⊆
            Finset.range (d.toNat + 1) := by
          intro j hj
          rw [Finset.mem_range]
          rw [Finset.mem_filter] at hj
          have hle : (j:ℝ) ≤ (d:ℝ) := (hmem j).mp hj.2
          rw [← hdcast] at hle
          have hle' : j ≤ d.toNat := by exact_mod_cast hle
          omega
        have hcard : (Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N)).card ≤
            d.toNat + 1 := by
          calc (Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N)).card
              ≤ (Finset.range (d.toNat + 1)).card := Finset.card_le_card hsub
            _ = d.toNat + 1 := Finset.card_range _
        have h2 : ((d.toNat + 1 : ℕ) : ℝ) ≤ (2:ℝ) ^ d.toNat := by
          rw [Nat.cast_add, Nat.cast_one]; exact nat_succ_le_two_pow d.toNat
        calc ((Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N)).card : ℝ)
            ≤ ((d.toNat + 1 : ℕ) : ℝ) := by exact_mod_cast hcard
          _ ≤ (2:ℝ) ^ d.toNat := h2
          _ = 2 ^ (d:ℝ) := by rw [← Real.rpow_natCast (2:ℝ) d.toNat, hdcast]
  5. If d < 0, the set of scale indices j < N such that down_scale θ z ≤ B / 2^j is empty, so its cardinality is 0 ≤ 2^d.

    If d < 0, no natural number j can satisfy j ≤ d because j ≥ 0. Hence the filtered set is empty by Finset.filter_eq_empty_iff.mpr. Its cardinality is 0, which is at most 2^d since powers of 2 are always non-negative by Real.rpow_nonneg.

    lines 59–70

    uses lt_of_not_ge, Finset.filter_eq_empty_iff.mpr, Nat.cast_nonneg, Finset.card_empty, Nat.cast_zero, Real.rpow_nonneg

      · have hdneg : (d:ℝ) < 0 := by
          have hdlt : d < 0 := lt_of_not_ge hd0
          exact_mod_cast hdlt
        have hempty : Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N) = ∅ := by
          apply Finset.filter_eq_empty_iff.mpr
          intro j _ hj
          have hle : (j:ℝ) ≤ (d:ℝ) := (hmem j).mp hj
          have : (0:ℝ) ≤ (j:ℝ) := Nat.cast_nonneg j
          linarith
        rw [hempty]
        simp only [Finset.card_empty, Nat.cast_zero]
        exact Real.rpow_nonneg (by norm_num) _
  6. For each edge e ∈ E, the sum over j < N of the indicator of down_scale θ (w e) ≤ B / 2^j times w e is at most w e * (B / down_scale θ (w e)).

    For each edge e with positive weight w e, let S be the set of scale indices j < N where down_scale θ (w e) ≤ B / 2^j. The sum of the indicator times w e equals |S| * w e. By accumulating_prefix_scales_card_filter_le, |S| ≤ B / down_scale θ (w e). Multiplying both sides by the positive weight w e preserves the inequality and gives the edge-level bound.

    lines 79–92

    uses accumulating_prefix_scales_card_filter_le, Finset.sum_filter, Finset.sum_const, nsmul_eq_mul, mul_le_mul_of_nonneg_right, le_of_lt

      obtain ⟨m, hm⟩ := hB
      have key : ∀ e ∈ E, ∑ j ∈ Finset.range N,
          (if down_scale θ (w e) ≤ B / (2 : ℝ) ^ j then w e else 0)
            ≤ w e * (B / down_scale θ (w e)) := by
        intro e he
        have hz : 0 < w e := hw e he
        set S := Finset.filter (fun j => down_scale θ (w e) ≤ B / 2 ^ j) (Finset.range N) with hS
        have hcard : (S.card : ℝ) ≤ B / down_scale θ (w e) :=
          accumulating_prefix_scales_card_filter_le hm hz N
        have hsum : ∑ j ∈ Finset.range N,
            (if down_scale θ (w e) ≤ B / (2 : ℝ) ^ j then w e else 0) = (S.card : ℝ) * w e := by
          rw [← Finset.sum_filter, ← hS, Finset.sum_const, nsmul_eq_mul]
        rw [hsum]
        nlinarith [mul_le_mul_of_nonneg_right hcard (le_of_lt hz)]
  7. The total sum of prefix scale weights across the first N dyadic scales is at most harmonic_scale_weight E w θ * B.

    Each prefix scale weight is by definition a sum over edges e ∈ E satisfying the scale threshold. Summing across j < N gives a double sum over scales and edges. Swapping the summation order using Finset.sum_comm places the sum over scales inside. Applying the edge-level bound to each edge and then factoring B out of the sum yields (∑ e ∈ E, w e / down_scale θ (w e)) * B, which is precisely the harmonic scale weight times B.

    lines 93–107

    uses Finset.sum_congr, Finset.sum_filter, Finset.sum_comm, Finset.sum_le_sum, Finset.sum_mul

      have hstart : ∑ j ∈ Finset.range N, prefix_scale_weight E w θ (B / (2 : ℝ) ^ j)
          = ∑ j ∈ Finset.range N, ∑ e ∈ E,
              (if down_scale θ (w e) ≤ B / (2 : ℝ) ^ j then w e else 0) := by
        apply Finset.sum_congr rfl
        intro j _
        rw [prefix_scale_weight, Finset.sum_filter]
      rw [hstart, Finset.sum_comm]
      calc ∑ e ∈ E, ∑ j ∈ Finset.range N,
            (if down_scale θ (w e) ≤ B / (2 : ℝ) ^ j then w e else 0)
          ≤ ∑ e ∈ E, w e * (B / down_scale θ (w e)) := Finset.sum_le_sum key
        _ = harmonic_scale_weight E w θ * B := by
            rw [harmonic_scale_weight, Finset.sum_mul]
            apply Finset.sum_congr rfl
            intro e he
            ring
accumulating_prefix_scales_ds_eq
For any positive real z, down_scale θ z equals 2^(θ + ⌊log₂ z - θ⌋).
accumulating_prefix_scales_ds_le_div_iff
For B = 2^(θ + m) and z > 0, down_scale θ z ≤ B / 2^j holds if and only if j ≤ m - ⌊log₂ z - θ⌋.
accumulating_prefix_scales_card_filter_le
For B = 2^(θ + m) and z > 0, the number of scale indices j < N satisfying down_scale θ z ≤ B / 2^j is at most B / down_scale θ z.
Finset.card_empty
The cardinality of the empty set is 0.
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.card_range
The range {0, ..., n - 1} has cardinality n.
Finset.filter_eq_empty_iff.mpr
A filtered set is empty if and only if no element of the ambient set satisfies the predicate.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the ambient set and satisfies the filter condition.
Finset.mem_range
An element m belongs to Finset.range n if and only if m < n.
Finset.sum_comm
Fubini's theorem for finite sums: swapping the order of a double finite summation preserves the total sum.
Finset.sum_congr
If two finite sets are equal and their summands agree on every element, their sums are equal.
Finset.sum_const
The sum of a constant c over a finite set s is equal to |s| • c.
Finset.sum_filter
Summing f over the filtered set {x ∈ s | p x} is equal to summing the if-then-else indicator over all x ∈ s.
Finset.sum_le_sum
If f i ≤ g i for all i in a finite set s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
Finset.sum_mul
Multiplication distributes over finite summation from the right: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
if_neg
If a condition c is false (¬c), then (if c then t else e) evaluates to e.
Int.toNat_of_nonneg
For a non-negative integer a, casting the natural number a.toNat back to the integers yields a.
le_of_lt
If a < b, then a ≤ b.
lt_of_not_ge
For real numbers in a linear order, if not b ≤ a, then a < b.
mul_le_mul_of_nonneg_right
If b ≤ c and a is non-negative, then b * a ≤ c * a.
nat_succ_le_two_pow
For any natural number j, j + 1 ≤ 2^j.
Nat.cast_add
Natural numbers cast to an ordered semiring are non-negative.
Nat.cast_one
The natural number 1 cast to a ring equals 1.
Nat.cast_nonneg
Natural numbers cast to the real numbers are non-negative.
Nat.cast_zero
The natural number 0 cast to a ring equals 0.
not_le.mpr
If a < b, then not b ≤ a.
nsmul_eq_mul
Multiplying by a natural number n via scalar action n • a equals (n : ℝ) * a.
Real.rpow_natCast
Real powers with a natural exponent agree with standard natural powers: x^(n:ℝ) = x^n.
Real.rpow_nonneg
For non-negative base x ≥ 0 and any real exponent y, x^y ≥ 0.
Real.rpow_sub
For base x > 0 and reals y and z, x^(y - z) = x^y / x^z.
Real.strictMono_rpow_of_base_gt_one
For base b > 1, the power function x ↦ b^x is strictly monotonic.

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 Classicallemma accumulating_prefix_scales_ds_eq {θ z : ℝ} (hz : 0 < z) :    down_scale θ z = 2 ^ (θ + (⌊Real.logb 2 z - θ⌋ : ℝ)) := by  rw [down_scale]  simp only [if_neg (not_le.mpr hz)]lemma accumulating_prefix_scales_ds_le_div_iff {θ : ℝ} {B : ℝ} {m : ℤ}    (hB : B = 2 ^ (θ + (m:ℝ))) {z : ℝ} (hz : 0 < z) (j : ℕ) :    down_scale θ z ≤ B / 2 ^ j ↔ (j:ℝ) ≤ (m:ℝ) - (⌊Real.logb 2 z - θ⌋ : ℝ) := by  rw [accumulating_prefix_scales_ds_eq hz]  have hdiv : B / 2 ^ j = 2 ^ (θ + (m:ℝ) - (j:ℝ)) := by    rw [hB, ← Real.rpow_natCast (2:ℝ) j, ← Real.rpow_sub (by norm_num : (0:ℝ) < 2)]  rw [hdiv]  rw [(Real.strictMono_rpow_of_base_gt_one (by norm_num : (1:ℝ) < 2)).le_iff_le]  constructor <;> intro h <;> linarithlemma accumulating_prefix_scales_card_filter_le {θ B : ℝ} {m : ℤ}    (hB : B = 2 ^ (θ + (m:ℝ))) {z : ℝ} (hz : 0 < z) (N : ℕ) :    ((Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N)).card : ℝ) ≤      B / down_scale θ z := by  set k : ℤ := ⌊Real.logb 2 z - θ⌋ with hk  set d : ℤ := m - k with hd  have hmem : ∀ j : ℕ, (down_scale θ z ≤ B / 2 ^ j) ↔ (j:ℝ) ≤ (d:ℝ) := by    intro j    rw [accumulating_prefix_scales_ds_le_div_iff hB hz j]    have h1 : (m:ℝ) - (⌊Real.logb 2 z - θ⌋ : ℝ) = (d:ℝ) := by      rw [hd]; push_cast; ring    rw [h1]  have hBq : B / down_scale θ z = 2 ^ (d:ℝ) := by    rw [accumulating_prefix_scales_ds_eq hz, hB, ← Real.rpow_sub (by norm_num : (0:ℝ) < 2)]    congr 1    rw [hd, hk]; push_cast; ring  rw [hBq]  by_cases hd0 : 0 ≤ d  · have hdcast : (d.toNat : ℝ) = (d:ℝ) := by      have h := Int.toNat_of_nonneg hd0      exact_mod_cast h    have hsub : Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N) ⊆        Finset.range (d.toNat + 1) := by      intro j hj      rw [Finset.mem_range]      rw [Finset.mem_filter] at hj      have hle : (j:ℝ) ≤ (d:ℝ) := (hmem j).mp hj.2      rw [← hdcast] at hle      have hle' : j ≤ d.toNat := by exact_mod_cast hle      omega    have hcard : (Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N)).card ≤        d.toNat + 1 := by      calc (Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N)).card          ≤ (Finset.range (d.toNat + 1)).card := Finset.card_le_card hsub        _ = d.toNat + 1 := Finset.card_range _    have h2 : ((d.toNat + 1 : ℕ) : ℝ) ≤ (2:ℝ) ^ d.toNat := by      rw [Nat.cast_add, Nat.cast_one]; exact nat_succ_le_two_pow d.toNat    calc ((Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N)).card : ℝ)        ≤ ((d.toNat + 1 : ℕ) : ℝ) := by exact_mod_cast hcard      _ ≤ (2:ℝ) ^ d.toNat := h2      _ = 2 ^ (d:ℝ) := by rw [← Real.rpow_natCast (2:ℝ) d.toNat, hdcast]  · have hdneg : (d:ℝ) < 0 := by      have hdlt : d < 0 := lt_of_not_ge hd0      exact_mod_cast hdlt    have hempty : Finset.filter (fun j => down_scale θ z ≤ B / 2 ^ j) (Finset.range N) = ∅ := by      apply Finset.filter_eq_empty_iff.mpr      intro j _ hj      have hle : (j:ℝ) ≤ (d:ℝ) := (hmem j).mp hj      have : (0:ℝ) ≤ (j:ℝ) := Nat.cast_nonneg j      linarith    rw [hempty]    simp only [Finset.card_empty, Nat.cast_zero]    exact Real.rpow_nonneg (by norm_num) _open Classical in/-- Accumulating prefix edge lengths across dyadic scales bounded by B (Lemma 7). -/theorem accumulating_prefix_scales {α : Type*} (E : Finset α) (w : α → ℝ)    (hw : ∀ e ∈ E, 0 < w e) (θ : ℝ) (hθ : 0 ≤ θ ∧ θ < 1)    (B : ℝ) (hB : B ∈ shifted_dyadic_scales θ) (hB_pos : 0 < B) (N : ℕ) :    ∑ j ∈ Finset.range N, prefix_scale_weight E w θ (B / (2 : ℝ) ^ j) ≤      harmonic_scale_weight E w θ * B := by  obtain ⟨m, hm⟩ := hB  have key : ∀ e ∈ E, ∑ j ∈ Finset.range N,      (if down_scale θ (w e) ≤ B / (2 : ℝ) ^ j then w e else 0)        ≤ w e * (B / down_scale θ (w e)) := by    intro e he    have hz : 0 < w e := hw e he    set S := Finset.filter (fun j => down_scale θ (w e) ≤ B / 2 ^ j) (Finset.range N) with hS    have hcard : (S.card : ℝ) ≤ B / down_scale θ (w e) :=      accumulating_prefix_scales_card_filter_le hm hz N    have hsum : ∑ j ∈ Finset.range N,        (if down_scale θ (w e) ≤ B / (2 : ℝ) ^ j then w e else 0) = (S.card : ℝ) * w e := by      rw [← Finset.sum_filter, ← hS, Finset.sum_const, nsmul_eq_mul]    rw [hsum]    nlinarith [mul_le_mul_of_nonneg_right hcard (le_of_lt hz)]  have hstart : ∑ j ∈ Finset.range N, prefix_scale_weight E w θ (B / (2 : ℝ) ^ j)      = ∑ j ∈ Finset.range N, ∑ e ∈ E,          (if down_scale θ (w e) ≤ B / (2 : ℝ) ^ j then w e else 0) := by    apply Finset.sum_congr rfl    intro j _    rw [prefix_scale_weight, Finset.sum_filter]  rw [hstart, Finset.sum_comm]  calc ∑ e ∈ E, ∑ j ∈ Finset.range N,        (if down_scale θ (w e) ≤ B / (2 : ℝ) ^ j then w e else 0)      ≤ ∑ e ∈ E, w e * (B / down_scale θ (w e)) := Finset.sum_le_sum key    _ = harmonic_scale_weight E w θ * B := by        rw [harmonic_scale_weight, Finset.sum_mul]        apply Finset.sum_congr rfl        intro e he        ring
See it in the graphDiscuss this resultChallenge it