CommunicationComplexity.mul_le_klFun_add_exp_sub_one
theoremverifiedimported Lean
A Fenchel-type inequality for the Kullback–Leibler function. For every real number $u \ge 0$ and every real number $y$, \[ u\,y \;\le\; \left(u\ln u - u + 1\right) + e^{y} - 1, \] where the term $u\ln u$ is taken to be $0$ at $u = 0$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory in open ProbabilityTheory in open scoped ENNReal in theorem CommunicationComplexity.mul_le_klFun_add_exp_sub_one {u y : ℝ} (hu : 0 ≤ u) : u * y ≤ InformationTheory.klFun u + Real.exp y - 1
- Source
- TCSlib, `CommunicationComplexity.mul_le_klFun_add_exp_sub_one`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. 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.CommunicationComplexity.mul_le_klFun_add_exp_sub_one← CommunicationComplexity.mul_le_klFun_add_exp_sub_one (TCSlib/CommunicationComplexity/NewmanTheorem/Pinsker.lean:332): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- CommunicationComplexity.variational_integral_mul_le_integral_klFun_add_cgfA variational inequality for the mean of a random variable. Let $\mu$ be a probability measure on a measurable space $\Omega$, let…
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 inopen ProbabilityTheory inopen scoped ENNReal in/-- The pointwise Fenchel–Young-type inequality `u · y ≤ klFun u + exp y − 1` for `u ≥ 0`, where `klFun u = u log u − u + 1` is the integrand of the KL divergence; it follows from `log z ≤ z − 1` applied to `z = exp y / u`. -/theorem CommunicationComplexity.mul_le_klFun_add_exp_sub_one {u y : ℝ} (hu : 0 ≤ u) : u * y ≤ InformationTheory.klFun u + Real.exp y - 1 := by rcases hu.eq_or_lt with rfl | hu_pos · simp [InformationTheory.klFun, (Real.exp_pos y).le] · have hlog := Real.log_le_sub_one_of_pos (div_pos (Real.exp_pos y) hu_pos) rw [Real.log_div (Real.exp_pos y).ne' hu_pos.ne', Real.log_exp] at hlog have hmul := mul_le_mul_of_nonneg_left hlog hu have hmul' : u * (y - Real.log u) ≤ Real.exp y - u := by calc u * (y - Real.log u) ≤ u * (Real.exp y / u - 1) := hmul _ = Real.exp y - u := by field_simp [hu_pos.ne'] rw [InformationTheory.klFun] nlinarith