Operational terminal solvers and the exact exponential factors
DefinitionFasterExactColoring_ThreeColor_Supplement_TerminalBoundsThe two modes are deterministic decision and one-sided Monte Carlo decision. Both use the published finite program and charged execution model. A graph solver handles every graph; a terminal solver handles every valid terminal instance with its supplied valid maximal star packings. The same execution supplies the Boolean output and its charged cost. Polynomial coefficients and exponents are fixed before all inputs.
The terminal factors are
Here is the published exact root of , and
For the path algorithm,
These are numerical functions of computed data, with no assumed solver correctness. The subexponential term is represented explicitly by the triangle-cover envelope, not absorbed into a polynomial.
Formalization Note Only , are used. Formula defaults outside those indices have no theorem meaning. Monte Carlo execution rejects every no-instance, succeeds with probability at least on yes-instances, and has the stated worst-case bound on every coin tape. Terminal polynomial overhead is measured in the charged encoded input size, polynomially bounded in on valid packings.
import Mathlib
import Definitions.Def_FasterExactColoring_ThreeColor_Execution
import Definitions.Def_FasterExactColoring_ThreeColor_CSP
import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_StarPackings
import Definitions.Def_FasterExactColoring_ThreeColor_Supplement_TriangleLists
set_option autoImplicit false
namespace FasterExactColoring.ThreeColor.Supplement
inductive Mode where
| det
| rand
/-- Correctness and work refer to one execution, with the published coin-tape semantics. -/
noncomputable def decides (mode : Mode) (A : Program) (x : List ℕ) (B : ℝ)
(P : Prop) : Prop :=
match mode with
| .det => deterministic A ∧ runWithin A x B (answers P)
| .rand => monteCarlo A x B P
noncomputable def graphSolver (mode : Mode) (k : ℕ) (A : Program) (C : ℝ) (d : ℕ)
(base : ℝ) : Prop :=
∀ (n : ℕ) (G : GraphInput n),
decides mode A (graphCode G) (C * (n+1 : ℕ)^d * base^n) (colorable G k)
noncomputable def terminalSolver (mode : Mode) (A : Program) (C : ℝ) (d : ℕ)
(factor : {n : ℕ} → Restricted n → StarPackings n → ℝ) : Prop :=
∀ (n : ℕ) (P : Restricted n) (K : StarPackings n),
P.valid → P.terminal → K.valid P →
let x := terminalCode P K
decides mode A x (polynomial C d x * factor P K) P.colorable
noncomputable def threeColorFactor {n : ℕ} (P : Restricted n) (τ : ℝ) : ℝ :=
(3 : ℝ)^(P.nClique 3) * (4 : ℝ)^(P.nClique 4) *
τ^(P.S.card + 2*P.nClique 3 + 3*P.nClique 4)
/-- Lemma 5.4: in particular g(3,0)=9/2 and g(4,0)=6. -/
noncomputable def g (m i : ℕ) : ℝ :=
if i = 0 then 3*(m : ℝ)/2
else if i = 1 then cspBase^(m-1) * (3+cspBase^3)
else 6/(Nat.factorial (4-i) : ℝ) * (4-(i : ℝ)+(i : ℝ)*cspBase^3)
noncomputable def cspTerminalFactor {n : ℕ} (P : Restricted n) (K : StarPackings n) : ℝ :=
(3 : ℝ)^((K.firstVertices.card : ℝ)/4) *
(∏ i : Fin 4, (g 3 i.val)^(cliqueCount P K 3 i.val)) *
(∏ i : Fin 5, (g 4 i.val)^(cliqueCount P K 4 i.val)) *
cspBase^((K.remainingS P).card) * Real.exp (coverEnvelope (cliqueCount P K 3 0))
noncomputable def treeTerminalFactor {n : ℕ} (P : Restricted n) (K : StarPackings n) : ℝ :=
(24 : ℝ)^((K.firstVertices.card : ℝ)/4) *
(18 : ℝ)^(P.nClique 3) * (24 : ℝ)^(P.nClique 4)
noncomputable def Qentry (i : ℕ) : ℝ :=
if i = 0 then 1 else
6*(8 : ℝ)^i/(Nat.factorial (4-i) : ℝ) * (4-(i : ℝ)+27*(i : ℝ)/8)
noncomputable def Qfactor {n : ℕ} (P : Restricted n) (K : StarPackings n) : ℝ :=
(24 : ℝ)^((K.firstVertices.card : ℝ)/4) *
(∏ i : Fin 4, (Qentry i.val)^(cliqueCount P K 3 i.val)) *
(∏ i : Fin 5, (Qentry i.val)^(cliqueCount P K 4 i.val))
noncomputable def pathTerminalFactor {n : ℕ} (P : Restricted n) (K : StarPackings n)
(ε : ℝ) : ℝ :=
Qfactor P K * (3 : ℝ)^(
(10/3 : ℝ)*cliqueCount P K 4 0 +
2*((cliqueCount P K 3 0 : ℝ)+cliqueCount P K 4 1) +
((cliqueCount P K 3 1 : ℝ)+cliqueCount P K 4 2) +
(1/2 : ℝ)*((cliqueCount P K 3 2 : ℝ)+cliqueCount P K 4 3) + ε*n)
end FasterExactColoring.ThreeColor.Supplement