Harmonic block mass
ProvedBLTCounting.AccuracySpace.claim_4_4geometric-blocksp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be an integer, let , and let be the harmonic mass of the geometric block . Then, with an absolute implied constant, uniformly in ,
Each block therefore carries nearly the same harmonic mass , which is why acts on a uniform logarithmic scale.
Formalization Note. The two terms are stated as and , with one constant chosen before , and .
Differences from the source:
- generalization: the parameters , of equation (28) and block indices → all integers , all and all ; reason: the estimate depends only on these ranges; the source statement is the special case
Preamble
import Mathlib import Definitions.Def_BLTCounting_AccuracySpace_GeometricBlocks
Formal statement
namespace BLTCounting.AccuracySpace
/-- Claim 4.4, PDF p. 27: `w_i = h + O(1/R) = h(1 + O((Rh)⁻¹))`, with an absolute implied constant,
uniformly in the block index `i`, the integer `R ≥ 1` and the width `0 < h ≤ 1`. -/
theorem claim_4_4 :
∃ C : ℝ, 0 < C ∧ ∀ (R : ℕ) (h : ℝ), 1 ≤ R → 0 < h → h ≤ 1 → ∀ i : ℕ,
|blockMass R h i - h| ≤ C / R ∧ |blockMass R h i / h - 1| ≤ C / (R * h) := by sorry
end BLTCounting.AccuracySpace
Source
Monika Henzinger, Jalaj Upadhyay, Lower Bounds for Memory-Efficient Differentially Private Continual Counting, STOC 2027 submission #357 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/357.pdf, SHA-256 4bc286dfed41ddf6b1f9ec058dd7964f530cf194be79fa5d9dd129d4ae37d510, Claim 4.4, printed p. 26 (PDF p. 27)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.