Lemma 4.5 — Entropy from the mean
ProvedLinearSetReconciliation327.Main.lemma_4_5linear-sketchp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1set-reconciliationsparse-recovery
For any law of a nonnegative-integer random variable with finite mean, including infinite support and mean zero, , with the entropy an extended nonnegative sum.
Differences from the source:
- encoding: a random variable T with distribution p → a PMF on ℕ; reason: entropy and mean depend only on the law
Preamble
import Mathlib import Definitions.Def_LinearSetReconciliation327_Main_Basic open scoped ENNReal open Finset
Formal statement
namespace LinearSetReconciliation327.Main
/-- Lemma 4.5 (Entropy from the mean), PDF p.17 (printed p.16): any law on the nonnegative integers
with finite mean, including infinite support and mean zero. -/
theorem lemma_4_5 (T : PMF ℕ) (hmean : ∑' k : ℕ, (k : ℝ≥0∞) * T k ≠ ⊤) :
entropy (fun k => (T k).toReal) ≤
ENNReal.ofReal (lg (Real.exp 1 * (1 + (∑' k : ℕ, (k : ℝ≥0∞) * T k).toReal))) := by sorry
end LinearSetReconciliation327.Main
Source
Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou, STOC 2027 submission #327 (October 2026), Lemma 4.5, PDF p.17 (printed p.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.