Proof of Lemma 3.3, p.17 — −log_{3/2}(k/(k−1)) ≥ −(1/ln(3/2))·1/(k−1) ≥ −5/k
ProvedTemporalAgg.lemma_3_3_log_boundadaptive-adversarydynamic-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmstemporal-aggregation
For every integer :
- ;
- ;
- ;
- ;
- .
When the adversary samples another member of a group of size , the potential term of every other member drops by ; this estimate shows the drop is paid by the coins each member receives.
Formalization Note is cast to before is formed.
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace TemporalAgg
/-- **The logarithmic estimate in the proof of Lemma 3.3** (Haeupler, Paramonov, *Temporal Aggregation: Maintaining Randomness against Adaptive
Adversaries*, STOC 2027 submission, manuscript of 2026-11-03, sha256 42ebf866…, p.17: "The first term changes
by −log_{3/2} k/(k−1) ≥ −1/ln(3/2) · 1/(k−1) ≥ −5/k, using ln k/(k−1) ≤ 1/(k−1) ≤ 2/k and
1/ln(3/2) < 2.5.").
For every integer `k ≥ 2` (the size of the group, "whose size was k ≥ 2"):
1. `−log_{3/2}(k/(k−1)) ≥ −(1/ln(3/2))·(1/(k−1))`;
2. `−(1/ln(3/2))·(1/(k−1)) ≥ −5/k`;
3. `ln(k/(k−1)) ≤ 1/(k−1)`;
4. `1/(k−1) ≤ 2/k`;
5. `1/ln(3/2) < 2.5`.
**Formalization Note** `k` is cast to `ℝ` before the subtraction `k − 1`; `ln` is
`Real.log` and `log_{3/2}` is `Real.logb (3/2)`. -/
theorem lemma_3_3_log_bound (k : ℕ) (hk : 2 ≤ k) :
-Real.logb (3 / 2) ((k : ℝ) / ((k : ℝ) - 1)) ≥
-(1 / Real.log (3 / 2)) * (1 / ((k : ℝ) - 1)) ∧
-(1 / Real.log (3 / 2)) * (1 / ((k : ℝ) - 1)) ≥ -5 / (k : ℝ) ∧
Real.log ((k : ℝ) / ((k : ℝ) - 1)) ≤ 1 / ((k : ℝ) - 1) ∧
1 / ((k : ℝ) - 1) ≤ 2 / (k : ℝ) ∧
1 / Real.log (3 / 2) < 2.5 := by sorry
end TemporalAgg
Source
Haeupler, Paramonov, Temporal Aggregation: Maintaining Randomness against Adaptive Adversaries, STOC 2027 submission (manuscript of 2026-11-03, sha256 42ebf866…), proof of Lemma 3.3, p.17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.