Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 43 — improved single-step lifting: a (Ut,q)(Ut,q)(Ut,q)-cover lifts to a ((U+13000)t, q−t−100)((U+\frac1{3000})t,\,q-t^{-100})((U+30001​)t,q−t−100)-cover

Proved
GaussLocalMaxColoring.Main.lemma_43

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

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

Section 5 setting under the analysis convention (exact edge constraint), any nested core sequence V=F0⊇F1⊇⋯V=F_0\supseteq F_1\supseteq\cdotsV=F0​⊇F1​⊇⋯, any root rrr, and nnn (hence ttt) sufficiently large. Let 1≤j≤ℓ1\le j\le\ell1≤j≤ℓ and W⊆FjW\subseteq F_jW⊆Fj​ (fixed independently of ggg), and suppose {ux}x∈W\{u_x\}_{x\in W}{ux​}x∈W​ is a (Ut,q)(Ut,q)(Ut,q)-cover for some 0<U≤H0<U\le\sqrt H0<U≤H​. Assume pFj−1(x)≤e−t2/2p_{F_{j-1}}(x)\le e^{-t^2/2}pFj−1​​(x)≤e−t2/2 and Pg[MFj−1(x)>1.968t]≤t−4Φ‾(t/2)\mathbb P_g[M_{F_{j-1}}(x)>1.968t]\le t^{-4}\overline\Phi(t/2)Pg​[MFj−1​​(x)>1.968t]≤t−4Φ(t/2) for every x∈Wx\in Wx∈W, and set W′=NFj−1(W)W'=N_{F_{j-1}}(W)W′=NFj−1​​(W). Then {uy}y∈W′\{u_y\}_{y\in W'}{uy​}y∈W′​ is a ((U+1/3000)t, q−t−100)((U+1/3000)t,\ q-t^{-100})((U+1/3000)t, q−t−100)-cover.

Differences from the source:

  • generalization: the cores F₀ ⊇ ⋯ ⊇ F_ℓ produced by Algorithm 2 → any ℕ-indexed nested sequence F with F 0 = V; reason: the lemma's proof uses only the stated hypotheses on the cores; Algorithm 2's cores extended by F_j = F_ℓ for j > ℓ are an instance
  • reading: "for sufficiently large t" (t = √((1−β) log n), Table 3) → ∃ N₀, ∀ n ≥ N₀, with N₀ chosen before every graph, vector family, core sequence and parameter; reason: the asymptotic convention of the paper (uniform thresholds); t is increasing in n
  • encoding: §5 analysis convention: the edge constraint of Lemma 34 is treated as exact (p. 35) → ExactSDPVectors G v: unit vectors, −1/2 ≤ ⟨v_i, v_j⟩ ≤ 1, ⟨v_i, v_j⟩ = −1/2 on edges, the third constraint of Lemma 34; reason: the analysis of §5.4–5.5 is stated under this convention (justified in Appendix B.2)
  • generalization: §5 analysis convention also treats Γ_rx(X) ⪰ 0 as exact → no Γ hypothesis; reason: the proof (via Lemmas 44, 45, 39, 29, 30) does not use Γ; the convention's setting is an instance
  • encoding: {u_y}{y∈W′}, W′ = N{F_{j−1}}(W); W fixed independently of g → Finset image of u over W.biUnion (nbr G (F (j−1))); W a Finset chosen before the probability; reason: repeated vectors do not change the maximum
  • encoding: §5 standing assumptions (G 3-colorable, every degree ≤ n^β, β = 0.692601; Table 3 parameters as functions of n) → binders G.Colorable 3, maxDegOn G univ ≤ n^beta5, and the Table 3 definitions of the Section5 module; reason: the section states them once (pp. 31, 35); they are hypotheses of every §5 lemma
  • 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
Preamble
import Mathlib
import Definitions.Def_GaussLocalMaxColoring_Main_Bands

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

/-- **Lemma 43** (Improved single-step lifting; p. 48, PDF 50). Section 5 setting (analysis
convention: exact edge constraint), any nested core sequence, any root `r`, and `n` (hence `t`)
sufficiently large. Let `1 ≤ j ≤ ℓ` and `W ⊆ F_j` (fixed independently of `g`), and suppose
`{u_x}_{x ∈ W}` is a `(Ut, q)`-cover for some `0 < U ≤ √H`. Assume `p_{F_{j−1}}(x) ≤ e^{−t²/2}`
and `P_g[M_{F_{j−1}}(x) > 1.968t] ≤ t^{−4}Φ̄(t/2)` for every `x ∈ W`, and set
`W′ = N_{F_{j−1}}(W)`. Then `{u_y}_{y ∈ W′}` is a `((U + 1/3000)t, q − t^{−100})`-cover. -/
theorem lemma_43 :
    ∃ N₀ : ℕ, ∀ n : ℕ, N₀ ≤ n →
    ∀ (d : ℕ) (G : SimpleGraph (Fin n)), G.Colorable 3 →
      (maxDegOn G Finset.univ : ℝ) ≤ (n : ℝ) ^ beta5 →
      ∀ v : Fin n → Space d, ExactSDPVectors G v →
      ∀ F : ℕ → Finset (Fin n), F 0 = Finset.univ → (∀ i, F (i + 1) ⊆ F i) →
      ∀ (r : Fin n) (j : ℕ), 1 ≤ j → j ≤ numLevels n →
      ∀ W : Finset (Fin n), W ⊆ F j →
      ∀ U q : ℝ, 0 < U → U ≤ Real.sqrt H5 →
      IsCover (W.image (uvec v r)) (U * t5 n) q →
      (∀ x ∈ W, pLocal G v (F (j - 1)) x ≤ Real.exp (-(t5 n ^ 2 / 2)) ∧
        gaussProb {g : Space d |
            ((1968 / 1000 * t5 n : ℝ) : WithBot ℝ) < nbrMax G v (F (j - 1)) x g} ≤
          (t5 n ^ 4)⁻¹ * PhiTail (t5 n / 2)) →
      IsCover ((W.biUnion (nbr G (F (j - 1)))).image (uvec v r)) ((U + 1 / 3000) * t5 n)
        (q - (t5 n ^ 100)⁻¹) := 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 43, printed p. 48 (PDF 50)
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