Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.1 — eTd≥∑log⁡(1+di)≥eTd−∥d∥2/(2(1−∥d∥∞))e^Td\ge\sum\log(1+d_i)\ge e^Td-\|d\|^2/(2(1-\|d\|_\infty))eTd≥∑log(1+di​)≥eTd−∥d∥2/(2(1−∥d∥∞​))

Proved
YeIPA.LP.log_sum_bounds

by Shuze Chen · Oct 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

inequalityinterior-pointlogarithmic-barrier

Let d∈Rnd\in\mathbb R^nd∈Rn, write ∥d∥\|d\|∥d∥ for its Euclidean norm and ∥d∥∞=max⁡i∣di∣\|d\|_\infty=\max_i|d_i|∥d∥∞​=maxi​∣di​∣, and suppose ∥d∥∞<1\|d\|_\infty<1∥d∥∞​<1. Then

eTd ≥ ∑i=1nlog⁡(1+di) ≥ eTd−∥d∥22(1−∥d∥∞).e^Td\ \ge\ \sum_{i=1}^n\log(1+d_i)\ \ge\ e^Td-\frac{\|d\|^2}{2(1-\|d\|_\infty)}.eTd ≥ i=1∑n​log(1+di​) ≥ eTd−2(1−∥d∥∞​)∥d∥2​.

This scalar inequality controls the barrier term −∑log⁡xj-\sum\log x_j−∑logxj​ 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 n=0n=0n=0 all three sides are 000.

Preamble
import Mathlib
import Definitions.Def_YeIPA_LP_PotentialReduction

open Matrix
Formal statement
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
Source
Ye, Interior Point Algorithms: Theory and Analysis, Wiley 1997, p. 84, Lemma 3.1
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let nnn be any natural number and d∈Rnd\in\mathbb{R}^nd∈Rn. Here ∥d∥∞=sup⁡i∣di∣\|d\|_\infty=\sup_i|d_i|∥d∥∞​=supi​∣di​∣ (equal to 000 when n=0n=0n=0) and ∥d∥=∑idi2\|d\|=\sqrt{\sum_i d_i^2}∥d∥=∑i​di2​​. Assume ∥d∥∞<1\|d\|_\infty<1∥d∥∞​<1. The statement asserts both of the following:

∑ilog⁡(1+di)  ≤  ∑idi\sum_i\log(1+d_i)\;\le\;\sum_i d_ii∑​log(1+di​)≤i∑​di​

and

∑idi−∥d∥22 (1−∥d∥∞)  ≤  ∑ilog⁡(1+di).\sum_i d_i-\frac{\|d\|^2}{2\,(1-\|d\|_\infty)}\;\le\;\sum_i\log(1+d_i).i∑​di​−2(1−∥d∥∞​)∥d∥2​≤i∑​log(1+di​).

When n≥1n\ge1n≥1, the hypothesis means ∣di∣<1|d_i|<1∣di​∣<1 for every iii. So every 1+di1+d_i1+di​ is positive, every logarithm is the ordinary one, and the denominator 2(1−∥d∥∞)2(1-\|d\|_\infty)2(1−∥d∥∞​) is positive.

When n=0n=0n=0, the hypothesis reads 0<10<10<1 and holds. Every sum and both norms are 000, so the two inequalities reduce to 0≤00\le00≤0 and 0−0≤00-0\le00−0≤0.

Human review
  • Endorsed by Community (Bot) · Oct 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 20, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me