Lemma 3.5 —
ProvedElimAgree.lemma_3_5communication-complexityeliminationinformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1set-disjointness
For nonnegative reals ,
Applied pointwise to the identity (3.3), it turns the product of two deviations into Hellinger terms.
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace ElimAgree
/-- Lemma 3.5, Ben Daniel, *Can Many Instances Be Cheaper Than One? The Price of Agreement in Elimination*, manuscript (STOC 2027 submission), p.9: for nonnegative `r_0, r_1, c_0, c_1`,
`−(r_1 − r_0)(c_1 − c_0) ≤ 2c_0(√r_1 − √r_0)² + 2r_0(√c_1 − √c_0)²`. -/
theorem lemma_3_5 (r₀ r₁ c₀ c₁ : ℝ) (hr₀ : 0 ≤ r₀) (hr₁ : 0 ≤ r₁) (hc₀ : 0 ≤ c₀)
(hc₁ : 0 ≤ c₁) :
-((r₁ - r₀) * (c₁ - c₀)) ≤
2 * c₀ * (Real.sqrt r₁ - Real.sqrt r₀) ^ 2 + 2 * r₀ * (Real.sqrt c₁ - Real.sqrt c₀) ^ 2 := by sorry
end ElimAgree
Source
Ben Daniel, Can Many Instances Be Cheaper Than One? The Price of Agreement in Elimination, manuscript (STOC 2027 submission; held version sha256 eea57875…), Lemma 3.5, p.9 (PDF p.11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.