Lemma 29 — Gaussian polyhedral Ehrhard extrapolation
ProvedGaussLocalMaxColoring.Main.lemma_29convexitygaussianprobabilitystoc-2027
Let be finite, let , and let . For standard Gaussian measure , define
Write for the standard normal CDF and . If , , and , then for every ,
This is Lemma 29 of the cited paper. The Lean encoding uses an arbitrary finite type , Space d = EuclideanSpace ℝ (Fin d), and Mathlib's stdGaussian. The hypothesis is encoded as 1 - PhiTail κ₀ ≤ gaussProb .... Closed inequalities, zero normals, and the empty family are retained.
Preamble
import Mathlib import Definitions.Def_RecGaussColoring_Main_Gaussian open scoped RealInnerProductSpace open Filter MeasureTheory ProbabilityTheory open RecGaussColoring.Main
Formal statement
theorem GaussLocalMaxColoring.Main.lemma_29 {d : ℕ} {Y : Type*} [Fintype Y]
(z : Y → RecGaussColoring.Main.Space d) (A B : Y → ℝ) (μ₀ κ₀ θ : ℝ)
(hμ : 0 ≤ μ₀) (hκ : 0 ≤ κ₀) (hθ : 0 ≤ θ)
(h₀ : gaussProb {g : RecGaussColoring.Main.Space d | ∀ y, ⟪g, z y⟫ ≤ A y} ≤ PhiTail μ₀)
(h₁ : 1 - PhiTail κ₀ ≤ gaussProb {g : RecGaussColoring.Main.Space d | ∀ y, ⟪g, z y⟫ ≤ B y}) :
gaussProb {g : RecGaussColoring.Main.Space d | ∀ y, ⟪g, z y⟫ ≤ (1 + θ) * A y - θ * B y} ≤
PhiTail (μ₀ + θ * (μ₀ + κ₀)) := by sorrySource
Deguchi, Kawarabayashi, Yoneda, Yoneda (2026), An O(n^0.1537)-Coloring Algorithm for 3-Colorable Graphs, arXiv:2610.35859; frozen STOC 2027 paper #155, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/155.pdf, SHA-256 9917b0a118555de058fe15a67d4540cda7e2214a8968b4c5dbf0e01f93e65b4b; Lemma 29, printed p. 25 (PDF p. 27).