Lemma 3.1 — Chernoff bound
ProvedDerandLDT.lemma_3_1low-degree-testingp2o-gran-per-chapterp2o-plan-paperp2o-v1pcppolynomial-method
Let be independent random variables taking values in (not necessarily identically distributed), let and . Then for every ,
The paper uses it for the size of the random sample of good lines and for the number of fortunate points on a line in the proof of Lemma 6.2.
Formalization Note The variables are measurable real functions on a probability space, mutually independent (iIndepFun) and almost surely or ; is the integral of their sum.
Differences from the source:
- encoding: independent {0,1}-valued random variables → measurable real functions on a probability space, mutually independent, almost surely in {0,1}; reason: standard measure-theoretic model; the same distributions
Preamble
import Mathlib set_option autoImplicit false universe u
Formal statement
namespace DerandLDT
open MeasureTheory ProbabilityTheory
/-- **Lemma 3.1** (Chernoff bound). Harsha, Kopparty, Kumar, Saptharishi, Sudan, *On derandomizing the line-point low-degree test*,
STOC 2027 submission manuscript (sha256 d57e7d6f…80df), Lemma 3.1, p.11: *Let `X₁, …, X_n` be independent
random variables taking values in `{0, 1}`, let `X` be their sum and `µ = E[X]`. Then
`Pr[|X − µ| ≥ δµ] ≤ 2·exp(−δ²µ/3)` for every `δ ∈ [0, 1]`.*
**Formalization Note.** The `Xᵢ` are measurable real functions on a probability space, mutually
independent (`iIndepFun`), and almost surely `0` or `1`; they need not be identically
distributed. `µ` is the expectation `∫ ∑ᵢ Xᵢ`. -/
theorem lemma_3_1 {Ω : Type u} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(n : ℕ) (X : Fin n → Ω → ℝ) (hXm : ∀ i, Measurable (X i)) (hind : iIndepFun X P)
(hX01 : ∀ i, ∀ᵐ ω ∂P, X i ω = 0 ∨ X i ω = 1) (δ : ℝ) (hδ0 : 0 ≤ δ) (hδ1 : δ ≤ 1) :
P.real {ω | δ * (∫ ω', ∑ i, X i ω' ∂P) ≤ |∑ i, X i ω - ∫ ω', ∑ i, X i ω' ∂P|} ≤
2 * Real.exp (-(δ ^ 2 * (∫ ω', ∑ i, X i ω' ∂P) / 3)) := by sorry
end DerandLDT
Source
Harsha–Kopparty–Kumar–Saptharishi–Sudan, On derandomizing the line-point low-degree test, STOC 2027 submission (manuscript sha256 d57e7d6f…80df), Lemma 3.1, p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.