neg_log_one_sub_two_mul_le_two_sq
theoremverifiedimported Lean
Taylor bound for the centered chi-squared log-MGF. For every real number $s$ with $\abs{s} \le 1/4$, one has \[ -s - \tfrac{1}{2}\log(1 - 2s) \;\le\; 2s^2 . \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in variable {d k : ℕ} in lemma neg_log_one_sub_two_mul_le_two_sq (s : ℝ) (hs : |s| ≤ 1 / 4) : -s - (1/2) * Real.log (1 - 2*s) ≤ 2 * s^2
- Source
- TCSlib, `neg_log_one_sub_two_mul_le_two_sq`
- Lean proof
- By Ganesh Sankar, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Ganesh Sankar. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.neg_log_one_sub_two_mul_le_two_sq← neg_log_one_sub_two_mul_le_two_sq (TCSlib/LearningTheory/JohnsonLindenstrauss/ChiSquaredMGF.lean:129): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- taylorAux_hasDerivAtDerivative of a Taylor auxiliary function. Let $h \colon \bbr \to \bbr$ be the function $h(x) = x^2 + x + \log(1 - x)$. Then at every…
- taylorAux_zeroAn auxiliary expression vanishes at zero. The real-valued expression $x^2 + x + \log(1 - x)$ takes the value $0$ at $x = 0$; that is,…
- Used by 1
- centered_chi_squared_stepCentered chi-squared MGF bound. Let $(\Omega,\mu)$ be a probability space and let $k$ be a positive natural number. Suppose…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory ProbabilityTheory Real NNReal Matrix Finset invariable {d k : ℕ} in/-- **Taylor bound** for the centered chi-squared log-MGF: for every real `s` with `|s| ≤ 1/4`, `−s − (1/2) log(1 − 2s) ≤ 2s²`. This is the log-MGF estimate in [LM00, proof of Lemma 1]. Deviation from the source: Laurent–Massart prove `−s − ½ log(1 − 2s) ≤ s²/(1 − 2s)` for `0 ≤ s < 1/2`; we restrict to `|s| ≤ 1/4`, where `s²/(1 − 2s) ≤ 2s²`, and also cover negative `s` (needed for the two-sided Bernstein bound). **Proof sketch.** Substitute `u = 2s`, so `|u| ≤ 1/2`, and set `f(u) = u² + u + log(1 − u)`; the claim is `f(u) ≥ 0 = f(0)`. Step 1: `f` is continuous on `[−1/2, 1/2]` and differentiable on its interior, with derivative `u(1 − 2u)/(1 − u)` (`taylorAux_hasDerivAt`). Step 2: the derivative is nonnegative on `[0, 1/2]`, so `f` is monotone there. Step 3: the derivative is nonpositive on `[−1/2, 0]`, so `f` is antitone there. Step 4: split on the sign of `u`; in either case `f(u) ≥ f(0) = 0` (`taylorAux_zero`). Step 5: unfold `f(2s) = 4s² + 2s + log(1 − 2s) ≥ 0` and rearrange. -/lemma neg_log_one_sub_two_mul_le_two_sq (s : ℝ) (hs : |s| ≤ 1 / 4) : -s - (1/2) * Real.log (1 - 2*s) ≤ 2 * s^2 := by -- Equivalent: 2s² + s + (1/2) log(1-2s) ≥ 0. -- Set u = 2s, |u| ≤ 1/2. Want f(u) := u² + u + log(1-u) ≥ 0 = f(0). set f : ℝ → ℝ := fun x => x ^ 2 + x + Real.log (1 - x) have hf_zero : f 0 = 0 := taylorAux_zero have h_abs : |2*s| ≤ 1/2 := by rw [abs_mul]; simp only [abs_two]; linarith [abs_nonneg s] have h_two_s : (2*s : ℝ) ∈ Set.Icc (-(1/2 : ℝ)) (1/2) := abs_le.mp h_abs -- Step 1: shared analytic scaffolding on the full interval `[-1/2, 1/2]`: -- `f` is continuous there (`1 - x > 0`) and differentiable on the interior. have hcont : ContinuousOn f (Set.Icc (-(1/2 : ℝ)) (1/2)) := by intro x hx simp only [Set.mem_Icc] at hx have h1mx : 0 < 1 - x := by linarith refine (continuous_pow 2).continuousAt.add ?_ |>.add ?_ |>.continuousWithinAt · exact continuousAt_id · exact (Real.continuousAt_log h1mx.ne').comp (continuous_const.sub continuous_id).continuousAt have hdiff : DifferentiableOn ℝ f (Set.Ioo (-(1/2 : ℝ)) (1/2)) := by intro x hx simp only [Set.mem_Ioo] at hx exact (taylorAux_hasDerivAt x (by linarith)).differentiableAt.differentiableWithinAt -- Step 2: monotone on `[0, 1/2]`, since `f'(u) = u(1-2u)/(1-u) ≥ 0` there. have h_mono : MonotoneOn f (Set.Icc (0 : ℝ) (1/2)) := by apply monotoneOn_of_deriv_nonneg (convex_Icc _ _) · exact hcont.mono (Set.Icc_subset_Icc (by norm_num) le_rfl) · rw [interior_Icc] exact hdiff.mono (Set.Ioo_subset_Ioo (by norm_num) le_rfl) · intro x hx rw [interior_Icc] at hx simp only [Set.mem_Ioo] at hx rw [(taylorAux_hasDerivAt x (by linarith)).deriv] have h1 : 0 ≤ x := hx.1.le have h2 : 0 ≤ 1 - 2 * x := by linarith have h3 : 0 < 1 - x := by linarith positivity -- Step 3: antitone on `[-1/2, 0]`, since `f'(u) ≤ 0` there. have h_anti : AntitoneOn f (Set.Icc (-(1/2 : ℝ)) 0) := by apply antitoneOn_of_deriv_nonpos (convex_Icc _ _) · exact hcont.mono (Set.Icc_subset_Icc le_rfl (by norm_num)) · rw [interior_Icc] exact hdiff.mono (Set.Ioo_subset_Ioo le_rfl (by norm_num)) · intro x hx rw [interior_Icc] at hx simp only [Set.mem_Ioo] at hx rw [(taylorAux_hasDerivAt x (by linarith)).deriv] have h1 : x ≤ 0 := hx.2.le have h2 : 0 < 1 - 2 * x := by linarith have h3 : 0 < 1 - x := by linarith have h_num : x * (1 - 2 * x) ≤ 0 := mul_nonpos_of_nonpos_of_nonneg h1 h2.le exact div_nonpos_of_nonpos_of_nonneg h_num h3.le -- Step 4: sign split — `f(2s) ≥ f(0) = 0` on either side of `0`. have h_nonneg : 0 ≤ f (2*s) := by by_cases h : 0 ≤ 2*s · -- 2s ∈ [0, 1/2] have h0_mem : (0 : ℝ) ∈ Set.Icc (0 : ℝ) (1/2) := by simp have h2s_mem : (2*s) ∈ Set.Icc (0 : ℝ) (1/2) := by refine ⟨h, ?_⟩ linarith [h_two_s.2] have : f 0 ≤ f (2*s) := h_mono h0_mem h2s_mem h linarith [hf_zero] · -- 2s ∈ [-1/2, 0) push_neg at h have h0_mem : (0 : ℝ) ∈ Set.Icc (-(1/2 : ℝ)) 0 := by constructor · linarith · rfl have h2s_mem : (2*s) ∈ Set.Icc (-(1/2 : ℝ)) 0 := ⟨h_two_s.1, h.le⟩ have : f 0 ≤ f (2*s) := h_anti h2s_mem h0_mem h.le linarith [hf_zero] -- Step 5: conclude — `f(2s) = 4s² + 2s + log(1-2s) ≥ 0`, divide by 2 and rearrange. have hf2s : f (2*s) = (2*s)^2 + 2*s + Real.log (1 - 2*s) := rfl have : 0 ≤ (2*s)^2 + 2*s + Real.log (1 - 2*s) := hf2s ▸ h_nonneg nlinarith