Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.8 (used in the proof of Theorem 1.3) — general terminal-algorithm combination

Open
FasterExactColoring.ThreeColor.Supplement.terminal_algorithm_combination

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

exact-algorithmsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Fix γ≥0\gamma\ge0γ≥0, r>1r>1r>1, weights satisfying all of Appendix D, arbitrary finite parameter and algorithm counts p,ap,ap,a, fixed matrices M∈R3×pM\in\mathbb R^{3\times p}M∈R3×p and R∈Ra×pR\in\mathbb R^{a\times p}R∈Ra×p, and a polynomial-time computable nonnegative vector x(P)x(P)x(P) for each valid terminal restricted instance. Assume

Mx(P)=(∣S∣,nK3,nK4)⊤.Mx(P)=(|S|,n_{K_3},n_{K_4})^\top.Mx(P)=(∣S∣,nK3​​,nK4​​)⊤.

For each row RiR_iRi​, assume one actual uniform terminal algorithm with time O∗(exp⁡(Rix(P)+γn))O^*(\exp(R_i x(P)+\gamma n))O∗(exp(Ri​x(P)+γn)), where nnn is the original input order. Let η∈Ra\eta\in\mathbb R^aη∈Ra satisfy

η≥0,1⊤η=1,η⊤R≤(ln⁡r)(ωc3,ωk3,ωk4)M\eta\ge0,\quad\mathbf1^\top\eta=1,\quad \eta^\top R\le(\ln r)(\omega_{c3},\omega_{k3},\omega_{k4})Mη≥0,1⊤η=1,η⊤R≤(lnr)(ωc3​,ωk3​,ωk4​)M

componentwise. Then one uniform finite program decides four-colorability of every graph in time

O∗((reγ)n).O^*((r e^\gamma)^n).O∗((reγ)n).

If the finite portfolio is deterministic, so is the resulting program. If its algorithms are one-sided Monte Carlo, the program has success at least 1/21/21/2 on yes-instances, never accepts no-instances, and has charged worst-case time on every tape. All needed amplification is included. Constants can depend on the fixed weights, matrices, parameter routine and finite portfolio, but never on a graph or its order. The conclusion is algorithm existence, not just the dual scalar inequality. It is not restricted to the eleven-parameter application.

Differences from the source:

  • encoding: polynomial-time computable nonnegative real parameter vectors → one deterministic finite program computes dyadic approximations to error 2^(-q) in time polynomial in n+q+1; reason: an explicit precision interface represents real-valued computation without an uncharged exact-real oracle; all finite exact source parameter vectors admit this representation
  • generalization: deterministic terminal algorithms → the composition is stated in deterministic and one-sided Monte Carlo modes; reason: the deterministic specialization is the printed lemma; the randomized extension is the same composition used in the source Theorem 1.4 application, charging independent amplification
Preamble
import Mathlib
import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_Portfolio

set_option autoImplicit false
Formal statement
namespace FasterExactColoring.ThreeColor.Supplement

theorem terminal_algorithm_combination (mode : Mode) {p a : ℕ}
    (γ r : ℝ) (w : Weights) (M : Matrix (Fin 3) (Fin p) ℝ)
    (R : Matrix (Fin a) (Fin p) ℝ) (x : {n : ℕ} → Restricted n → Fin p → ℝ)
    (η : Fin a → ℝ) (hγ : 0 ≤ γ) (hr : 1 < r) (hw : appendixD r w)
    (hcompute : parametersComputable x) (hx : parameterIdentity x M)
    (hportfolio : terminalPortfolio mode γ x R) (hdual : dualComparison r w M R η) :
  ∃ (A : Program) (C : ℝ) (d : ℕ), 0 < C ∧
    graphSolver mode 4 A C d (r*Real.exp γ) := by sorry

end FasterExactColoring.ThreeColor.Supplement
Source
Ryosuke Yamano, Tetsuo Shibuya, STOC 2027 submission #727 (October 2026), Lemma 5.8, p. 15 (PDF p. 17)

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