Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3, Lemma 3.3, Theorem 4.4 — deterministic O∗(T)O^*(T)O∗(T) time, palettes, short lists and the table of induced list subinstances

Definition
KColoringFaster_ListBootstrap_Supplement_DetTime

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

exponential-time-algorithmslist-coloringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

This definition adds to the published definitions Instances and Algorithms the objects that Lemma 3.3 (p. 9) and Theorem 4.4 (p. 19) of the paper need.

  1. Deterministic O∗(T)O^*(T)O∗(T) time. A property Good\mathrm{Good}Good of outputs is computed deterministically in time O∗(T)O^*(T)O∗(T) on a class Dom\mathrm{Dom}Dom of inputs if there are one program PPP of the published integer RAM and polynomials p,qp,qp,q with natural coefficients, all fixed before the input, such that on every input a∈Doma\in\mathrm{Dom}a∈Dom with encoding xxx and budget
B=⌈p(σ(x))⋅T(a)⌉,B=\big\lceil p(\sigma(x))\cdot T(a)\big\rceil,B=⌈p(σ(x))⋅T(a)⌉,

the run without coins and without oracle halts with cost at most BBB, keeps every register within q(σ(x))q(\sigma(x))q(σ(x)) bits, and its output satisfies Good(a,⋅)\mathrm{Good}(a,\cdot)Good(a,⋅). Here σ(x)\sigma(x)σ(x) is the bit size of the input. Deciding a property Yes\mathrm{Yes}Yes means outputting [1][1][1] on yes-instances and [0][0][0] on no-instances, without error; finding a solution means that whenever a solution exists, the output is one. 2. Instances over a palette. For a finite set P⊆NP\subseteq\mathbb NP⊆N of colors, a list instance (G,L)(G,L)(G,L) is over PPP if L(v)⊆PL(v)\subseteq PL(v)⊆P for every vertex vvv. 3. Short lists. b(G,L)=#{v:∣L(v)∣≤2}b(G,L)=\#\{v : |L(v)|\le 2\}b(G,L)=#{v:∣L(v)∣≤2}, the number of vertices whose list has at most two colors (sizes 000, 111, 222 all count). 4. Induced list subinstances. For X⊆V(G)X\subseteq V(G)X⊆V(G), G[X]G[X]G[X] is list colorable if some map ccc satisfies c(v)∈L(v)c(v)\in L(v)c(v)∈L(v) for every v∈Xv\in Xv∈X and c(u)≠c(v)c(u)\ne c(v)c(u)=c(v) for every edge uvuvuv with u,v∈Xu,v\in Xu,v∈X. The subset table of (G,L)(G,L)(G,L) on nnn vertices is the word of length 2n2^n2n whose iii-th entry (0≤i<2n0\le i<2^n0≤i<2n) is 111 if G[Xi]G[X_i]G[Xi​] is list colorable and 000 otherwise, where Xi={v:bit v of i is 1}X_i=\{v : \text{bit } v \text{ of } i \text{ is } 1\}Xi​={v:bit v of i is 1}.

These objects let Lemma 3.3 and Theorem 4.4 be stated on the same machine, budget and encodings as the rest of the mission.

Formalization Note The deterministic predicate is the coin-free run of the published machine with the published budget budget p x T; it is the deterministic analogue of RandDecides/RandFinds of Algorithms, which has only a polynomial-time deterministic predicate (DetPolyComputes). X∅X_\emptysetX∅​ (i=0i=0i=0) is the empty set, whose induced instance is colorable.

Definition code
import Mathlib
import Definitions.Def_KColoringFaster_ListBootstrap_Instances
import Definitions.Def_KColoringFaster_ListBootstrap_Algorithms

open Classical

namespace KColoringFaster.ListBootstrap.Supplement

open CongruencyTU
open KColoringFaster.ListBootstrap

/-! # Deterministic `O*(T)` time, fixed palettes, short lists, and the induced-subinstance table

Zamir, *k-Coloring is Faster than Computing the Chromatic Number*, arXiv:2607.25973 (revision of
9 Sep 2026), §3 (p. 7), Lemma 3.3 (p. 9) and Theorem 4.4 (p. 19).

The machine, the budget `⌈p(σ(x)) · T⌉` and the instance encodings are the published base
definitions `Algorithms` and `Instances`; this file adds only the deterministic `O*(T)` analogue
of their randomized predicates, and the objects of Lemma 3.3 and Theorem 4.4. -/

/-- A deterministic computation in time `O*(T)`: one program `P` and polynomials `p q`, fixed before
the input, such that on every input `a` of `Dom`, with budget `B = ⌈p(σ(enc a)) · T a⌉`, the run
without coins and without oracle halts with cost at most `B`, keeps every register within
`q(σ(enc a))` bits, and its output satisfies `Good a`. -/
def DetComputes {α : Type*} (enc : α → List ℤ) (Dom : α → Prop)
    (Good : α → List ℤ → Prop) (T : α → ℝ) : Prop :=
  ∃ (P : Program) (p q : Polynomial ℕ), ∀ a, Dom a →
    RunBounded P noOracle noCoins (enc a) (budget p (enc a) (T a)) q 0 ∧
    Good a (outputAfter P noOracle noCoins (enc a) (budget p (enc a) (T a)))

/-- Deterministic decision in time `O*(T)`, without error: the output is `[1]` on yes-instances and
`[0]` on no-instances. -/
def DetDecides {α : Type*} (enc : α → List ℤ) (Dom Yes : α → Prop) (T : α → ℝ) : Prop :=
  DetComputes enc Dom (fun a out => out = if Yes a then [1] else [0]) T

/-- Deterministic search in time `O*(T)`: on every input of `Dom` the run is within the budget, and
whenever a solution exists the output is one. Nothing is required of the output otherwise. -/
def DetFinds {α : Type*} (enc : α → List ℤ) (Dom : α → Prop) (Sol : α → List ℤ → Prop)
    (T : α → ℝ) : Prop :=
  DetComputes enc Dom (fun a out => (∃ y, Sol a y) → Sol a out) T

/-- The list instance `I` is **over the palette** `P` (§3.1, p. 7; Lemma 3.3, p. 9; Theorem 4.4,
p. 19): every list is contained in `P`. Lists may be empty, and not every color of `P` need occur. -/
def OverPalette (P : Finset ℕ) (I : ListInstance) : Prop :=
  ∀ v, I.L v ⊆ P

/-- Theorem 4.4, p. 19: `b`, the number of vertices whose list has size **at most two** (sizes `0`,
`1` and `2` all count). -/
noncomputable def binaryCount (I : ListInstance) : ℕ :=
  (Finset.univ.filter fun v : Fin I.n => (I.L v).card ≤ 2).card

/-- Lemma 3.3, p. 9: the induced subinstance `G[X]` (with the lists restricted to `X`) is list
colorable. -/
def InducedListColorable (I : ListInstance) (X : Finset (Fin I.n)) : Prop :=
  ∃ c : Fin I.n → ℕ, (∀ v ∈ X, c v ∈ I.L v) ∧ ∀ u ∈ X, ∀ v ∈ X, I.G.Adj u v → c u ≠ c v

/-- The vertex set coded by the number `i`: the vertices `v` such that bit `v` of `i` is `1`
(so `i = ∑_{v ∈ X} 2^v`). -/
def subsetOfIndex (n : ℕ) (i : ℕ) : Finset (Fin n) :=
  Finset.univ.filter fun v : Fin n => i.testBit v.val

/-- The output of Lemma 3.3: the table over all `2^n` vertex subsets, whose `i`-th entry
(`i = 0, …, 2^n − 1`) is `1` if `G[X_i]` is list colorable and `0` otherwise, with
`X_i = subsetOfIndex n i`. -/
noncomputable def encSubsetTable (I : ListInstance) : List ℤ :=
  (List.range (2 ^ I.n)).map fun i =>
    if InducedListColorable I (subsetOfIndex I.n i) then 1 else 0

end KColoringFaster.ListBootstrap.Supplement
Source
Zamir, k-Coloring is Faster than Computing the Chromatic Number, arXiv:2607.25973 (revision of 9 Sep 2026; STOC 2027 submission #73; source.pdf sha256 624fee950171ffcd169c0aa08efcb25b2de77b3219fcbdf9227d838138d1003e), p. 7 (§3, O* convention), p. 9 (Lemma 3.3), p. 19 (Theorem 4.4)

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