Lemma 3.1 —
ProvedYeIPA.LP.log_sum_boundsLet , write for its Euclidean norm and , and suppose . Then
This scalar inequality controls the barrier term along a step, and is used in the analysis of every potential-reduction step of Chapter 4, in particular in Theorem 4.9.
Formalization Note This is Lemma 3.1 of Chapter 3, restated in this mission's namespace with its own norm2 and normInf, because Chapter 4 uses it and the Chapter 3 mission is a separate draft. At all three sides are .
import Mathlib import Definitions.Def_YeIPA_LP_PotentialReduction open Matrix
namespace YeIPA.LP
/-- Lemma 3.1 (Ye 1997, p. 84), restated for Chapter 4. If `d ∈ ℝⁿ` with `‖d‖_∞ < 1`, then
`eᵀd ≥ ∑ᵢ log(1 + dᵢ) ≥ eᵀd − ‖d‖² / (2(1 − ‖d‖_∞))`. -/
theorem log_sum_bounds {n : ℕ} (d : Fin n → ℝ) (hd : normInf d < 1) :
∑ i, Real.log (1 + d i) ≤ ∑ i, d i ∧
∑ i, d i - norm2 d ^ 2 / (2 * (1 - normInf d)) ≤ ∑ i, Real.log (1 + d i) := by sorry
end YeIPA.LP
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be any natural number and . Here (equal to when ) and . Assume . The statement asserts both of the following:
and
When , the hypothesis means for every . So every is positive, every logarithm is the ordinary one, and the denominator is positive.
When , the hypothesis reads and holds. Every sum and both norms are , so the two inequalities reduce to and .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.