Lemma 4.4 — Entropy and total mass
ProvedLinearSetReconciliation327.Main.lemma_4_4linear-sketchp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1set-reconciliationsparse-recovery
For a finite family of nonnegative with , . For with , .
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_LinearSetReconciliation327_Main_Basic open scoped ENNReal open Finset
Formal statement
namespace LinearSetReconciliation327.Main
/-- Lemma 4.4 (Entropy and total mass), PDF p.17 (printed p.16). -/
theorem lemma_4_4 (N : ℕ) :
(∀ (ι : Type) [Fintype ι] (q : ι → ℝ), (∀ i, 0 ≤ q i) → 0 < ∑ i, q i → ∑ i, q i ≤ N →
∑ i, hN N (q i) =
hN N (∑ i, q i) + (∑ i, q i) * entropyFin (fun i => q i / ∑ i', q i')) ∧
(∀ u v : ℝ, 0 ≤ u → 0 ≤ v → u + v ≤ N → hN N (u + v) ≤ hN N u + hN N v) := by sorry
end LinearSetReconciliation327.Main
Source
Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou, STOC 2027 submission #327 (October 2026), Lemma 4.4, PDF p.17 (printed p.16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.