Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The bottom-up computation of Theorem 1.16 on a word RAM in time fσ(w,∣φ∣)⋅bf_\sigma(w,|\varphi|)\cdot bfσ​(w,∣φ∣)⋅b

Open
CoDecompFO.fold_program

by emmgaml · Nov 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

co-decompositionsfirst-order-logicmodel-checkingparameterized-complexityword-ram

Fix a finite relational signature σ\sigmaσ. This is the algorithmic half of Theorem 1.16: it asks for the program and its running time, and describes the output through the bottom-up computation instead of through the truth of the sentence.

There are one word-RAM program PPP and one computable function fff such that, for every first-order σ\sigmaσ-sentence φ\varphiφ with equality, every tree co-decomposition T\mathcal TT of σ\sigmaσ-structures with bbb bags and width at most www, and every word width that holds the number f(w,∣φ∣)⋅bf(w,|\varphi|)\cdot bf(w,∣φ∣)⋅b, the program PPP started on the code of (φ,T)(\varphi,\mathcal T)(φ,T) halts within

f(w,∣φ∣)⋅bf(w,|\varphi|)\cdot bf(w,∣φ∣)⋅b

steps, with the following output.

  1. If lim⁡T\lim\mathcal TlimT is non-empty, let ℓ\ellℓ be the number of quantifiers of φ\varphiφ and let ψ\psiψ be the matrix of its alternating form ∀x1∃y1⋯∀xℓ∃yℓ ψ\forall x_1\exists y_1\cdots\forall x_\ell\exists y_\ell\,\psi∀x1​∃y1​⋯∀xℓ​∃yℓ​ψ over σ\sigmaσ with ∘\circ∘. For some root rrr and some table HHH of ℓ\ellℓ-hypotheticals on 2ℓ2\ell2ℓ variables obtained at rrr by the bottom-up computation over T∘\mathcal T^\circT∘ (the induced hypotheticals of the full strategy on the bags, then one reduced pullback and one projection per edge), PPP prints 111 if HHH passes alternating evaluation of ψ\psiψ, and 000 otherwise.
  2. If lim⁡T\lim\mathcal TlimT is empty, PPP prints 111 if lim⁡T⊨φ\lim\mathcal T\models\varphilimT⊨φ and 000 otherwise.

Together with the correctness of the bottom-up computation, this is Theorem 1.16. What is asked here is the implementation and its analysis: reading the code, ordering the tree from the leaves towards the root, representing the tables, whose number and size are bounded in www and ∣φ∣|\varphi|∣φ∣ by Lemma 5.81, and computing pullbacks, projections and the final evaluation, with each node processed once.

Formalization Note The machine is the published word RAM with the multiplication instruction set, in the run layer LovaszECCKernel.RunsWithin, and the input is the code input φ T of CoDecompFO.theorem_1_16; the limit is not part of the input. The matrix is altMatrix φ with ℓ\ellℓ = quantCount φ, the bottom-up computation is CoDecomp.IsFold on T.withEq, and alternating evaluation is eval. The program may choose the root and the order in which the children of a node are joined. On an empty limit every universal quantifier holds and the alternating form is not equivalent to φ\varphiφ, so that case is stated directly on the limit.

Preamble
import Mathlib
import Definitions.Def_CoDecompFO_AltMatrix
import Definitions.Def_CoDecompFO_Fold
import Definitions.Def_LovaszECCKernel_RunsWithin
import Definitions.Def_CoDecompFO_Codes

set_option autoImplicit false
Formal statement
namespace CoDecompFO

open FirstOrder

/-- **The bottom-up computation in linear time** (Bumpus et al., *Co-Decompositions and FO Model
Checking*, arXiv:2611.04658, held file sha256 d550d7af…, proof of Theorem 1.16, p.41): "By Lemma 5.81, the
number and size of the reduced hypotheticals considered at any one node are bounded by a function of w and
|φ|. Since each node is processed once, the total running time is f_σ(w,|φ|)·b." Equality is handled on
`T°` (A.8, p.53: "lim(T°) = (lim(T))°"; A.9, p.53).

For each `σ` there are one word-RAM program `P` and one computable `f` such that on the code of `(φ, T)`,
on every word width that holds `f(w,|φ|)·b`, `P` halts within `f(w,|φ|)·b` steps and: if the limit is
non-empty, it prints the result of alternating evaluation of the matrix `altMatrix φ` on the table `H`
of some root `r`, for some bottom-up computation `T°.IsFold r (2ℓ) ℓ r univ H` over the co-decomposition
`T°` with equality, `ℓ = quantCount φ`; if the limit is empty, it prints whether `φ` holds in it.

**Formalization Note** This is the machine half of Theorem 1.16: its conclusion refers to the limit only
when the limit is empty, where every `∀` holds and the alternating form is not available. The program
may choose the root and the order in which children are joined. The machine and the code of the input
are those of `theorem_1_16`. -/
theorem fold_program (σ : Sig) :
    ∃ (P : LovaszECCKernel.Program) (f : ℕ → ℕ → ℕ), Computable₂ f ∧
      ∀ (T : CoDecomp σ) (φ : σ.lang.Sentence) (w : ℕ), width T ≤ w →
        ∀ W : WordRAM.Width, LovaszECCKernel.WordFits W (f w (sentLen φ) * T.b) →
          (IsEmpty T.Lim →
            (T.Lim ⊨ φ → LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b) [1]) ∧
            (¬ T.Lim ⊨ φ → LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b) [0])) ∧
          (Nonempty T.Lim →
            ∃ (r : Fin T.b)
              (H : HTh (sigmaEq σ) (Fin (T.withEq.bag r).n) (2 * quantCount φ) (quantCount φ)),
              T.withEq.IsFold r (2 * quantCount φ) (quantCount φ) r Set.univ H ∧
              (eval (altMatrix φ) (quantCount φ) H →
                LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b) [1]) ∧
              (¬ eval (altMatrix φ) (quantCount φ) H →
                LovaszECCKernel.RunsWithin P W (input φ T) (f w (sentLen φ) * T.b) [0])) := by sorry

end CoDecompFO
Source
Bumpus, Gomes, Larios-Jones, Turner, Co-Decompositions and FO Model Checking, arXiv:2611.04658 (held file sha256 d550d7af…), proof of Theorem 1.16, p.41; Observation 5.79 and ¶5.80, p.41; Lemma 5.81 and ¶5.82, p.41; A.7–A.9, p.53

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