Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 17 — pF(x)=Eg[Φ‾(MF(x)/3)]p_F(x)=\mathbb E_g[\overline\Phi(M_F(x)/\sqrt3)]pF​(x)=Eg​[Φ(MF​(x)/3​)] and Pg[MF(x)≤a]≤pF(x)/Φ‾(a/3)\mathbb P_g[M_F(x)\le a]\le p_F(x)/\overline\Phi(a/\sqrt3)Pg​[MF​(x)≤a]≤pF​(x)/Φ(a/3​)

Proved
GaussLocalMaxColoring.Main.lemma_17

by Shuze Chen · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

gaussian-roundinggraph-coloringp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithmssemidefinite-programming

Let {vx}\{v_x\}{vx​} be a strict vector 3-coloring of a graph GGG (unit vectors in Rd\mathbb R^dRd, ⟨vx,vy⟩=−12\langle v_x,v_y\rangle=-\tfrac12⟨vx​,vy​⟩=−21​ on edges), F⊆VF\subseteq VF⊆V and x∈Fx\in Fx∈F. Then for every a∈Ra\in\mathbb Ra∈R,

pF(x)=Eg[Φ‾(MF(x)/3)],Pg[MF(x)≤a]≤pF(x)Φ‾(a/3),p_F(x)=\mathbb E_g\big[\overline\Phi(M_F(x)/\sqrt3)\big],\qquad \mathbb P_g[M_F(x)\le a]\le\frac{p_F(x)}{\overline\Phi(a/\sqrt3)},pF​(x)=Eg​[Φ(MF​(x)/3​)],Pg​[MF​(x)≤a]≤Φ(a/3​)pF​(x)​,

where pF(x)=Pg[x∈IF(g)]p_F(x)=\mathbb P_g[x\in I_F(g)]pF​(x)=Pg​[x∈IF​(g)], MF(x)=max⁡y∈NF(x)⟨g,vxy⟩M_F(x)=\max_{y\in N_F(x)}\langle g,v_{xy}\rangleMF​(x)=maxy∈NF​(x)​⟨g,vxy​⟩ (−∞-\infty−∞ for an empty neighborhood, with Φ‾(−∞)=1\overline\Phi(-\infty)=1Φ(−∞)=1) and Φ‾=1−Φ\overline\Phi=1-\PhiΦ=1−Φ is the standard normal upper tail.

Differences from the source:

  • generalization: §4 standing assumptions: G is the 3-colorable input graph with every degree ≤ n^β, with a strict vector 3-coloring → any graph G on Fin n with a strict vector 3-coloring, any dimension d; reason: the proof uses only Equation (3); the §4 setting is an instance
  • encoding: vertex set V with a fixed total order breaking ties → V = Fin n with its order; reason: Lean convention; every finite ordered vertex set is relabelled this way
  • encoding: vectors in R^d, g ∼ N(0, I_d), P_g → Space d = EuclideanSpace ℝ (Fin d), any d, Mathlib stdGaussian (gaussProb); reason: Lean convention; same instances
  • encoding: M_F(x) = −∞ when N_F(x) = ∅ → nbrMax in WithBot ℝ (⊥), tailOver c ⊥ = 1 = Φ̄(−∞); reason: an empty maximum must not default to 0
Preamble
import Mathlib
import Definitions.Def_RecGaussColoring_Main_Rounding
import Definitions.Def_GaussLocalMaxColoring_Main_Basic

open scoped RealInnerProductSpace
open Filter MeasureTheory ProbabilityTheory
open RecGaussColoring.Main
open Classical
Formal statement
namespace GaussLocalMaxColoring.Main

/-- **Lemma 17** (p. 17, PDF 19). Let `{v_x}` be a strict vector 3-coloring of `G`, `F ⊆ V` and
`x ∈ F`. Then for every `a ∈ ℝ`, `p_F(x) = E_g[Φ̄(M_F(x)/√3)]` and
`P_g[M_F(x) ≤ a] ≤ p_F(x)/Φ̄(a/√3)`; `M_F(x) = −∞` (`⊥`) and `Φ̄(−∞) = 1` when `N_F(x) = ∅`. -/
theorem lemma_17 {n d : ℕ} (G : SimpleGraph (Fin n)) (v : Fin n → Space d)
    (hv : StrictVectorColoring G v) (F : Finset (Fin n)) (x : Fin n) (hx : x ∈ F) (a : ℝ) :
    pLocal G v F x =
        ∫ g, tailOver (Real.sqrt 3) (nbrMax G v F x g) ∂(stdGaussian (Space d)) ∧
      gaussProb {g : Space d | nbrMax G v F x g ≤ ((a : ℝ) : WithBot ℝ)} ≤
        pLocal G v F x / PhiTail (a / Real.sqrt 3) := by sorry

end GaussLocalMaxColoring.Main
Source
Deguchi, Kawarabayashi, Yoneda, Yoneda (2026), An O(n^0.1537)-Coloring Algorithm for 3-Colorable Graphs, arXiv:2610.35859 (SHA-256 9917b0a1…), Lemma 17, printed p. 17 (PDF 19)
Human review
  • Endorsed by Community (Bot) · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 10, 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