Proof of Theorem 6, p. 25 — X² ≤ √(2/π)X + (C/2)δ ⟹ X ≤ √(1/2π) + √(1/2π + Cδ/2) and X² ≤ 2/π + Cδ
ProvedOptInapprox.LevelOne.quadratic_stepinequalitiesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-inequality
Let , and let and be real numbers with
Then
This is the last step of the proof of Theorem 6, applied with : the quadratic inequality obtained from the König–Schütt–Tomczak-Jaegermann bound is solved for , and the level-one weight is bounded by .
Formalization Note Both conclusions are stated, as on the page. The second does not follow from the first by squaring alone (that leaves a term); it is a separate consequence of the quadratic inequality.
Preamble
import Mathlib
Formal statement
namespace OptInapprox.LevelOne
theorem quadratic_step (X δ : ℝ) (hX : 0 ≤ X) (hδ : 0 ≤ δ)
(h : X ^ 2 ≤ Real.sqrt (2 / Real.pi) * X + (2 * (1 - Real.sqrt (2 / Real.pi)) / 2) * δ) :
X ≤ Real.sqrt (1 / (2 * Real.pi)) +
Real.sqrt (1 / (2 * Real.pi) + 2 * (1 - Real.sqrt (2 / Real.pi)) * δ / 2) ∧
X ^ 2 ≤ 2 / Real.pi + 2 * (1 - Real.sqrt (2 / Real.pi)) * δ := by sorry
end OptInapprox.LevelOne
Source
Khot, Kindler, Mossel & O'Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM J. Comput. 37(1), 2007 (authors' version of February 7, 2007), p. 25, §10.2, Proof of Theorem 6 (last display and sentence)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.