Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 4.11 — Polynomial program extraction for data specifications

Open
ABHS2004V2.corollary_4_11

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

implicit-complexityprogram-extractionrealizability

An almost closed derivation of a relativized existence specification yields a program on canonical cleaned representations of data. Its reduction takes polynomially many steps in the original input syntax length. Its output represents a source data object meeting the specification, with output resource size and free-variable count at most the input totals plus a fixed constant.

Preamble
import Definitions.Def_ABHS2004V2_Realizability
Formal statement
namespace ABHS2004V2

/-- Corollary 4.11. Extraction from an almost-closed derivation of a relativized
specification gives a program on the cleaned representations of data objects.
The program normalizes in polynomially many steps and yields a representation
of an output satisfying the original specification and the additive resource bound. -/
theorem corollary_4_11 {Δ Γ : ProofContext} {M : ProofTerm}
    {xs : List Var} {y : Var} {A : Formula}
    (hdata_xs : ∀ x ∈ xs, IsDataType x.ty)
    (hdata_y : IsDataType y.ty)
    (hnodup : (xs ++ [y]).Nodup)
    (hA : IsExistAndDisjFree A)
    (hac : IsAlmostClosedDerivation M)
    (hd : Derives Δ Γ M
      (Formula.allRel xs (.ex y (.tensor (.existPred y.ty (.var y)) A))))
    (hfresh : FreshRealizerVars Δ Γ M
      (Formula.allRel xs (.ex y (.tensor (.existPred y.ty (.var y)) A)))) :
    ∃ (B : Nat → Nat) (k : Nat),
      BoundedByPolyOfDegree B (Nat.max (iterNesting (extractCleaned M)) 1) ∧
      ∀ ws : List Term,
        ValidDataInputs (extractProof M) (xs.map Var.ty) ws →
        ∃ (cleanInputs : List Term) (steps : Nat) (w cleanOutput : Term),
          CleansDataInputs (xs.map Var.ty) ws cleanInputs ∧
          RedSteps steps
            (if cleanTy y.ty == .unit then extractCleaned M
             else Term.appMany (extractCleaned M) cleanInputs)
            cleanOutput ∧
          IsDataObject y.ty w ∧
          IsDataObject (cleanTy y.ty) cleanOutput ∧
          CleansData y.ty w cleanOutput ∧
          steps ≤ B (totalTermLength ws) ∧
          dataSize w ≤ totalDataSize ws + k ∧
          freeVarCount w ≤ totalFreeVarCount ws + k ∧
          Provable (mrContext (Δ ++ Γ)) []
            (substFormulaMany A (xs.zip ws ++ [(y, w)])) := by sorry

end ABHS2004V2
Source
Klaus Aehlig, Ulrich Berger, Martin Hofmann and Helmut Schwichtenberg (2004), An arithmetic for non-size-increasing polynomial-time computation, TCS 318, Corollary 4.11. https://www.mathematik.uni-muenchen.de/~schwicht/papers/abhs01/ICC-TCS/ansipt.pdf
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)

Let Δ,Γ\Delta,\GammaΔ,Γ be assumption contexts, MMM a proof term, [x1,…,xm][x_1,\ldots,x_m][x1​,…,xm​] a list of typed variables, yyy a typed variable, and AAA a formula. Assume each xix_ixi​ and yyy has a data type, and [x1,…,xm,y][x_1,\ldots,x_m,y][x1​,…,xm​,y] has no repeated pair of identifier and type. Assume AAA is built from ordinary atoms by implication, tensor, additive conjunction, and either quantifier, including existential quantifiers. Assume every free variable of the cleaned extracted term K(M)K(M)K(M) has type ⋄\diamond⋄. Set Fm+1=∃y (Ey.ty(y)⊗A)F_{m+1}=\exists y\,(E_{y.\mathrm{ty}}(y)\otimes A)Fm+1​=∃y(Ey.ty​(y)⊗A) and Fi=∀xi (Exi.ty(xi)⊸Fi+1)F_i=\forall x_i\,(E_{x_i.\mathrm{ty}}(x_i)\multimap F_{i+1})Fi​=∀xi​(Exi​.ty​(xi​)⊸Fi+1​) for i=m,…,1i=m,\ldots,1i=m,…,1, with EρE_\rhoEρ​ the typed existence atom. Assume MMM derives F1F_1F1​ in (Δ,Γ)(\Delta,\Gamma)(Δ,Γ) and satisfies the freshness condition below for F1F_1F1​.

There exist B:N→NB:\mathbb N\to\mathbb NB:N→N and k∈Nk\in\mathbb Nk∈N with B(n)≤c0(n+1)max⁡(I(K(M)),1)+c1B(n)\le c_0(n+1)^{\max(I(K(M)),1)}+c_1B(n)≤c0​(n+1)max(I(K(M)),1)+c1​ for all n∈Nn\in\mathbb Nn∈N and some c0,c1∈Nc_0,c_1\in\mathbb Nc0​,c1​∈N. For every term list valid for the raw extraction E(M)E(M)E(M) and the type list [x1.ty,…,xm.ty][x_1.\mathrm{ty},\ldots,x_m.\mathrm{ty}][x1​.ty,…,xm​.ty], written [w1,…,wm][w_1,\ldots,w_m][w1​,…,wm​], there exist a list VVV of terms, a natural number qqq and terms w,w′w,w'w,w′ with these properties.

  • VVV is obtained by relating each wiw_iwi​ to a cleaned term at xi.tyx_i.\mathrm{ty}xi​.ty and discarding terms whose type parameter cleans to 111.
  • Exactly qqq ordinary steps lead to w′w'w′ from K(M)K(M)K(M) if C(y.ty)=1C(y.\mathrm{ty})=1C(y.ty)=1, and from the left-associated application of K(M)K(M)K(M) to VVV otherwise. The terms w,w′w,w'w,w′ are data objects at y.tyy.\mathrm{ty}y.ty and C(y.ty)C(y.\mathrm{ty})C(y.ty) respectively, and are related by data cleaning at y.tyy.\mathrm{ty}y.ty.
  • q≤B(∑iℓ(wi))q\le B(\sum_i\ell(w_i))q≤B(∑i​ℓ(wi​)), s(w)≤∑is(wi)+ks(w)\le\sum_i s(w_i)+ks(w)≤∑i​s(wi​)+k, and f(w)≤∑if(wi)+kf(w)\le\sum_i f(w_i)+kf(w)≤∑i​f(wi​)+k.
  • There is a proof term deriving AAA with simultaneous assignments [(x1,w1),…,(xm,wm),(y,w)][(x_1,w_1),\ldots,(x_m,w_m),(y,w)][(x1​,w1​),…,(xm​,wm​),(y,w)]. Its first context is the concatenation of Δ,Γ\Delta,\GammaΔ,Γ with each entry u=(i,G)u=(i,G)u=(i,G) replaced by (i,Ra(u)(G))(i,R_{a(u)}(G))(i,Ra(u)​(G)). Its second context is empty.

Data types are generated from 111 by lists, tensors and sums. A data object has its indicated type by the rules that require disjoint free variables at application and closed steps at iteration. It has only ⋄\diamond⋄-typed free variables and no ordinary reduct. A step is a root conversion or its placement through application and iterator children. The conversions are beta, tensor elimination on introduction, product projections on introduction, sum elimination on injections, and nil and cons iteration on a seed. Cons iteration requires a cons/nil-shaped tail. Zero steps give the start term. Valid inputs have exactly the indicated types and are data objects whose free variables are disjoint from those of the preceding application E(M) w1⋯wi−1E(M)\,w_1\cdots w_{i-1}E(M)w1​⋯wi−1​ at each iii. The empty type list permits just the empty list, with VVV empty and all three sums zero.

The length ℓ\ellℓ counts leaves and abstractions, sss counts cons constant occurrences including bare constants, and fff counts free variable occurrences with repetitions. The depth III is zero on leaves, passes through abstractions, takes the maximum at applications, and is max⁡(I(L),I(S)+1)\max(I(L),I(S)+1)max(I(L),I(S)+1) on iter(L,S)\mathsf{iter}(L,S)iter(L,S). A simultaneous assignment takes the first matching replacement at each variable. Under quantifiers and abstractions it drops assignments to the binder, renaming the binder if free in any retained replacement to the same type with identifier one above the maximum in the old binder, body, and retained keys and values.

The realizing variable of u=(i,G)u=(i,G)u=(i,G) is a(u)=(2i+1,τ(G))a(u)=(2i+1,\tau(G))a(u)=(2i+1,τ(G)). Freshness means that numerical identifiers determine the entry on the concatenation of Δ,Γ\Delta,\GammaΔ,Γ and all assumption occurrences and assumption-abstraction binders in MMM, allowing identical repeats. Each a(u)a(u)a(u) from that list must be absent from the free variables of F1F_1F1​ and of all assumption formulas in Δ,Γ\Delta,\GammaΔ,Γ. Derivability here is the relation generated by the arithmetic core axioms, assumption and implication and universal rules, passification for unit-cleaned conclusions, contraction and list induction. The raw extraction uses a(u)a(u)a(u) for an assumption, the prescribed term for an axiom, lambda and application for assumption abstraction and proof application, the same extracted proof child for term abstraction and application, and iteration for list induction.

The type τ\tauτ sends EρE_\rhoEρ​ atoms to ρ\rhoρ, other atoms to 111, the four binary formula constructors to function, tensor, product and sum, and quantifiers to the body's type. Type cleaning CCC fixes 1,⋄1,\diamond1,⋄, recurses through lists and sums, and drops unit factors of tensors and products. An arrow cleans to 111 if its codomain does, to its cleaned codomain if just its domain cleans to 111, and to the arrow of cleaned types otherwise. The cleaning of E(M)E(M)E(M) uses weak type inference, leaving a term alone on inference failure and giving ε\varepsilonε at an inferred type cleaning to 111. Otherwise it cleans constants and variables, removes unit-cleaned binders and arguments, and cleans iterator operands. An iterator element type cleaning to 111 makes its cleaned step SSS become λd.λu.S d\lambda d.\lambda u.S\,dλd.λu.Sd with fresh d:⋄,u:1d:\diamond,u:1d:⋄,u:1 of identifiers one and two above the maximum in SSS.

The variable cleaning is b(i,ρ)=(P(i,code⁡(ρ)),C(ρ))b(i,\rho)=(P(i,\operatorname{code}(\rho)),C(\rho))b(i,ρ)=(P(i,code(ρ)),C(ρ)), with P(a,b)=b2+aP(a,b)=b^2+aP(a,b)=b2+a when a<ba<ba<b, and a2+a+ba^2+a+ba2+a+b otherwise. The type code pairs a tag with 000 for the two base types, with the child's code for a list, or with the pair of child codes for a binary type. The tags are 0,1,2,3,4,5,60,1,2,3,4,5,60,1,2,3,4,5,6 for unit, diamond, list, function, tensor, product, sum. Data cleaning relates ε\varepsilonε to itself, retains the injection of a sum while relating its payload and cleaning type tags, and changes nil's tag to the cleaned element type. It relates consρ d r l\mathsf{cons}_\rho\,d\,r\,lconsρ​drl to consC(ρ) b(d) r′ l′\mathsf{cons}_{C(\rho)}\,b(d)\,r'\,l'consC(ρ)​b(d)r′l′ for a variable d:⋄d:\diamondd:⋄ and related elements and tails. At a tensor it relates both components and returns the cleaned left when the right type cleans to 111, the cleaned right when just the left type cleans to 111, and their retagged tensor introduction otherwise.

The formula Rt(G)R_t(G)Rt​(G) replaces Eρ(r)E_\rho(r)Eρ​(r) by t=ρrt={}_\rho rt=ρ​r and preserves ordinary atoms. In a quantifier with binder free in ttt, it first renames the binder to a same-type identifier one above the maximum in the binder, ttt, and the body. The quantifier otherwise keeps its binder, and either case translates its body with term ttt. At an implication G⊸HG\multimap HG⊸H the result is ∀z (Rz(G)⊸Rt z(H))\forall z\,(R_z(G)\multimap R_{t\,z}(H))∀z(Rz​(G)⊸Rtz​(H)). At tensor and additive conjunction it is additive conjunction of the respective translations using the two tensor selectors or product projections of ttt. The tensor selectors are tensor elimination with λa.λb.a\lambda a.\lambda b.aλa.λb.a and λa.λb.b\lambda a.\lambda b.bλa.λb.b, with typed variables of identifiers 0,10,10,1. At G∨HG\lor HG∨H the result is additive conjunction of ∀z ((t=ηinl z)⊸Rz(G))\forall z\,((t={}_\eta\mathsf{inl}\,z)\multimap R_z(G))∀z((t=η​inlz)⊸Rz​(G)) and ∀v ((t=ηinr v)⊸Rv(H))\forall v\,((t={}_\eta\mathsf{inr}\,v)\multimap R_v(H))∀v((t=η​inrv)⊸Rv​(H)), with η=τ(G)+τ(H)\eta=\tau(G)+\tau(H)η=τ(G)+τ(H). The variable zzz has type τ(G)\tau(G)τ(G) and identifier one above the maximum in t,G,Ht,G,Ht,G,H in both the implication and disjunction clauses, and vvv has type τ(H)\tau(H)τ(H) and the next identifier. These maxima include bound identifiers and default to zero.

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