accumulating_prefix_scales
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.
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.
uses
if_neg,not_le.mprrw [down_scale] simp only [if_neg (not_le.mpr hz)]
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 - θ⌋.
uses
accumulating_prefix_scales_ds_eq,Real.rpow_natCast,Real.rpow_sub,Real.strictMono_rpow_of_base_gt_onerw [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
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.
uses
accumulating_prefix_scales_ds_le_div_iff,accumulating_prefix_scales_ds_eq,Real.rpow_subset 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]
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.
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_natCastby_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]
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.
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) _
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.
uses
accumulating_prefix_scales_card_filter_le,Finset.sum_filter,Finset.sum_const,nsmul_eq_mul,mul_le_mul_of_nonneg_right,le_of_ltobtain ⟨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)]
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.
uses
Finset.sum_congr,Finset.sum_filter,Finset.sum_comm,Finset.sum_le_sum,Finset.sum_mulhave 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.
- The Lean file proves three auxiliary lemmas (lines 3–70) establishing the algebraic form of down_scale, the equivalence of scale inequalities, and the cardinality bound on valid dyadic scales before proving the main theorem (lines 74–107).
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 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