Fact D.3 — both binary entropy bounds, with endpoints
ProvedEliasGlobalClock.LowerBound.binary_entropy_boundsinformation-theoryleader-electionp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For , let , with . Then both inequalities hold:
All logarithms are natural and both constants are exactly . The statement includes both endpoints. These estimates relate a coordinate's binary entropy to the contention weight in Lemma 4.2.
Differences from the source:
- encoding: the binary entropy h with h(0)=h(1)=0 → Mathlib Real.binEntropy on the closed unit interval; reason: its natural-log and zero-mass conventions agree exactly with the source
Preamble
import Mathlib
Formal statement
namespace EliasGlobalClock.LowerBound
/-- Fact D.3, printed p.36 / PDF p.37, including x=0 and x=1. -/
theorem binary_entropy_bounds (x : ℝ) (hx0 : 0 ≤ x) (hx1 : x ≤ 1) :
Real.binEntropy x ≤ 2 * Real.log (Real.sqrt x + Real.sqrt (1 - x)) ∧
2 * Real.log (Real.sqrt x + Real.sqrt (1 - x)) ≤
2 * Real.sqrt (x * (1 - x)) := by sorry
end EliasGlobalClock.LowerBound
Source
Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, Ben Plosk, STOC 2027 submission #1311 (October 2026), printed p.36, PDF p.37, Fact D.3 (proof continues on printed p.37, PDF p.38); https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/1311.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.