OctoInformBeta

OpenAI preprint, September 2026 · The direct lower bound for the BGS-style language (no numbered counterpart)

Operational machines, and Lemmas 19 and 20 for machine states: Machine runs have traces of polynomial size, hereditarily supported on the grid structure AbA_b; store values, cardinality and comprehension are uniformly definable in CmC^m

Programs and their compiled machines accept within the same bounds.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Choiceless polynomial time with counting (CPT), in the style of Blass, Gurevich and Shelah, computes on a finite structure over a set of atoms AA by firing one rule again and again on a store of dynamic functions whose arguments and values are hereditarily finite objects over AA. A program accepts within polynomial bounds when it halts and accepts after polynomially many steps in |A||A|, having made only polynomially many objects occur.✦

Three questions about a run up to a step hh bear on lower bounds for CPT on grid structures: how many objects the run touches, how small a support each of them has under a group acting on the atoms, and whether each dynamic function after hh steps is definable in a counting logic with few variables by one formula for all inputs at once. Here they are put to operational machines, which fire a closed rule and are watched by an observer term, and into which every program compiles.

Hereditarily Finite Objects and Supports

The hereditarily finite objects over a set of atoms AA form the least set HF(A)\mathrm{HF}(A) that contains the atoms of AA, which have no elements, and every finite set of its members.✦ The von Neumann ordinals are [0]=0[0] = 0, the empty set, and [j+1]=[j]∪{[j]}[j+1] = [j]\cup\{[j]\}✦, and the truth value 1=[1]={0}1 = [1] = \{0\} stands for true.✦ When AA is finite, Atoms\mathrm{Atoms} is the set of all atoms.✦ The closure of an object xx is the finite set cl(x)={x}∪⋃y∈xcl(y)\mathrm{cl}(x) = \{x\}\cup\bigcup_{y\in x}\mathrm{cl}(y).✦

Let a group GG act on AA, and through it on HF(A)\mathrm{HF}(A). A tuple α\alpha of atoms supports an object xx if every g∈Gg\in G that fixes each entry of α\alpha fixes xx.✦ The object xx is ss-supported if some tuple of ss atoms supports it✦, and hereditarily ss-supported if every member of cl(x)\mathrm{cl}(x) is ss-supported; HSsG\mathrm{HS}^G_s is the set of hereditarily ss-supported objects.✦

Machines and Their Runs

Fix a vocabulary RR of binary relation symbols. An input over a finite set of atoms AA gives each r∈Rr\in R a binary relation ρr\rho_r on AA.✦

A machine PP over RR consists of a finite set of dynamic function symbols, each with an arity, and a closed rule ΠP\Pi_P over RR, a rule in the sense defined below that has no free variables, whose function symbols are the dynamic ones and the two control flags halt\mathrm{halt} and accept\mathrm{accept}, of arity 00✦; ar(f)\mathrm{ar}(f) denotes the arity of a function symbol ff.✦

A location over AA is a function symbol ff with a tuple of arguments in HF(A)ar(f)\mathrm{HF}(A)^{\mathrm{ar}(f)}.✦ A store of PP is a machine state for its function symbols✦: a map σ\sigma from locations to HF(A)\mathrm{HF}(A) whose support, the set of locations at which σ\sigma is not 00, is finite.✦ A control flag cc holds in σ\sigma when σ(c)=1\sigma(c) = 1.✦ The critical objects of σ\sigma are the arguments and the values at the locations of its support✦, and its active objects are act(σ)=⋃{cl(x):x∈crit(σ)∪{Atoms,0,1}∪A}.\mathrm{act}(\sigma) = \bigcup\big\{\mathrm{cl}(x) : x\in\mathrm{crit}(\sigma)\cup \{\mathrm{Atoms},0,1\}\cup A\big\}.(1)✦

The terms are the variables, the constants [j][j] for j∈ℕj\in\mathbb{N}, the term Atoms\mathrm{Atoms}, the applications f(t1,…,tar(f))f(t_1,\dots,t_{\mathrm{ar}(f)}), and the terms built from smaller ones by pairing, union ⋃t\bigcup t, the unique element, the cardinality Card(t)\mathrm{Card}(t), the tests t=t′t = t', t∈t′t\in t', tt is an atom and r(t,t′)r(t,t') for r∈Rr\in R, negation, conjunction, the conditional, and the comprehension {t2:x∈t0,t1}\{t_2 : x\in t_0,\ t_1\}, which binds xx in its guard t1t_1 and its body t2t_2.✦

In a store σ\sigma, with values for its free variables, a term evaluates to an object of HF(A)\mathrm{HF}(A): a variable to its value, [j][j] to the ordinal [j][j], Atoms\mathrm{Atoms} to the set of all atoms, f(t1,…,tar(f))f(t_1,\dots,t_{\mathrm{ar}(f)}) to the value of σ\sigma at ff and the values of the tit_i, a pairing, a union and the unique element to the pair, the union and the unique element of the values of its parts, Card(t)\mathrm{Card}(t) to the ordinal of the number of elements of tt, a test, a negation and a conjunction to 11 when it holds and to 00 otherwise, a conditional to the value of its first or its second branch according as its condition is 11 or not, and the comprehension to the set of values of t2t_2 at the elements xx of t0t_0 at which t1t_1 is 11.✦ The test r(t,t′)r(t,t') holds when tt and t′t' are atoms related by ρr\rho_r✦, and negation, conjunction and the conditional read 11 as true and every other object as false.

The rules are skip\mathrm{skip}, the update f(t1,…,tar(f)):=tf(t_1,\dots,t_{\mathrm{ar}(f)}) := t, the parallel composition Π∥Π′\Pi\parallel\Pi', the conditional 𝒊𝒇t𝒕𝒉𝒆𝒏Π𝒆𝒍𝒔𝒆Π′\mathbf{if}\ t\ \mathbf{then}\ \Pi\ \mathbf{else}\ \Pi', the parallel loop 𝒇𝒐𝒓𝒂𝒍𝒍x∈t𝒅𝒐Π\mathbf{forall}\ x\in t\ \mathbf{do}\ \Pi and the local definition 𝒍𝒆𝒕x=t𝒊𝒏Π\mathbf{let}\ x = t\ \mathbf{in}\ \Pi, the last two binding xx in Π\Pi; a rule is closed when it has no free variables.✦

The initial state σ0\sigma_0 is the store that is 00 at every location. One step of ΠP\Pi_P from a store σj\sigma_j performs the updates that ΠP\Pi_P prescribes in σj\sigma_j, and is defined when they are consistent. The run of PP on an input ρ\rho starts at σ0\sigma_0, and σj+1\sigma_{j+1} is the store produced from σj\sigma_j by one step of ΠP\Pi_P, as long as each step is defined.✦ The active objects of the run of PP on ρ\rho up to step hh form the set ActP(ρ,h)\mathrm{Act}_P(\rho,h), the union of the sets (1) of the defined stores σj\sigma_j with j≤hj\le h.✦ The evaluation trace of a term tt in a store σ\sigma, with values for its free variables, is the finite set of objects that occur while tt is evaluated in σ\sigma. The evaluation trace trσ(Π)\mathrm{tr}_\sigma(\Pi) of a rule in σ\sigma collects those of its terms: the value and the arguments of an update, both parts of a parallel composition, the condition and both branches of a conditional, the bound of a loop with the body at every element of the bound, and the defining term of a local definition with the body at its value.✦ The run trace up to step hh is TrP(ρ,h)=ActP(ρ,h)∪⋃j≤htrσj(ΠP).\mathrm{Tr}_P(\rho,h) = \mathrm{Act}_P(\rho,h)\cup\bigcup_{j\le h}\mathrm{tr}_{\sigma_j}(\Pi_P).(2)✦

Each term tt has a bound βt∈ℕ[X]\beta_t\in\mathbb{N}[X], a polynomial in XX that bounds the size of its evaluation trace, and a width w(t)∈ℕw(t)\in\mathbb{N}, both defined by recursion on tt. The bound β(Π)\beta(\Pi) of a rule is the polynomial with β(skip)=0\beta(\mathrm{skip}) = 0 and β(f(t‾):=t)=βt+∑iβti,β(Π∥Π′)=β(Π)+β(Π′),β(𝒊𝒇t𝒕𝒉𝒆𝒏Π𝒆𝒍𝒔𝒆Π′)=βt+β(Π)+β(Π′),β(𝒍𝒆𝒕x=t𝒊𝒏Π)=βt+β(Π)(X+βt),β(𝒇𝒐𝒓𝒂𝒍𝒍x∈t𝒅𝒐Π)=βt+βtβ(Π)(X+βt),\begin{aligned} \beta\big(f(\bar t) := t\big) &= \beta_t + \textstyle\sum_i\beta_{t_i}, & \beta(\Pi\parallel\Pi') &= \beta(\Pi) + \beta(\Pi'),\\ \beta(\mathbf{if}\ t\ \mathbf{then}\ \Pi\ \mathbf{else}\ \Pi') &= \beta_t + \beta(\Pi) + \beta(\Pi'), & \beta(\mathbf{let}\ x = t\ \mathbf{in}\ \Pi) &= \beta_t + \beta(\Pi)(X+\beta_t),\\ \beta(\mathbf{forall}\ x\in t\ \mathbf{do}\ \Pi) &= \beta_t + \beta_t\,\beta(\Pi)(X+\beta_t), \end{aligned}(3)✦ and βP=β(ΠP)\beta_P = \beta(\Pi_P). The width w(Π)w(\Pi) of a rule is 66 for skip\mathrm{skip} and otherwise 66 plus the widths of its terms and of its subrules.✦

Programs and Their Compiled Machines

A CPT program Π\Pi over RR consists of a finite set of dynamic function symbols, each with an arity, and a CPT rule, its body, over RR and the dynamic symbols together with halt\mathrm{halt} and accept\mathrm{accept}.✦ CPT terms and rules are built like those of a machine, with named variables xnx_n for n∈ℕn\in\mathbb{N} and with disjunction among the term constructions. The stores of Π\Pi are the machine states for its function symbols✦, with control flags read as for a machine✦; its run σ0,σ1,…\sigma_0,\sigma_1,\dots on an input ρ\rho starts at the initial state and applies one step of Π\Pi at a time, as long as the step is defined✦, and ActΠ(ρ,h)\mathrm{Act}_\Pi(\rho,h) is the union of the active objects of σ0,…,σh\sigma_0,\dots,\sigma_h.✦

The roots of a CPT term evaluated in a store, with values for its variables, form a finite set of objects, defined by recursion on the term. The roots of a CPT rule are those of the terms on the branches it executes: the value and the arguments of an update, both parts of a parallel composition, the condition of a conditional and the branch it selects, the bound of a loop with the body at every element of the bound, and the defining term of a local definition with the body at its value.✦ The roots roots(σ)\mathrm{roots}(\sigma) of one step from σ\sigma are none when halt\mathrm{halt} holds in σ\sigma, and otherwise the roots of the body with every variable set to 00.✦ The objects occurring up to step hh are OccΠ(ρ,h)=ActΠ(ρ,h)∪⋃j<h⋃x∈roots(σj)cl(x),\mathrm{Occ}_\Pi(\rho,h) = \mathrm{Act}_\Pi(\rho,h)\cup\bigcup_{j<h}\ \bigcup_{x\in\mathrm{roots}(\sigma_j)}\mathrm{cl}(x),(4)✦ the union running over the defined stores. For polynomials p,p′∈ℕ[X]p,p'\in\mathbb{N}[X], Π\Pi accepts ρ\rho within (p,p′)(p,p'), written Accp,p′(Π,ρ)\mathrm{Acc}_{p,p'}(\Pi,\rho), if for some h≤p(|A|)h\le p(|A|) the store σh\sigma_h is defined, halt\mathrm{halt} and accept\mathrm{accept} hold in it, and |OccΠ(ρ,h)|≤p′(|A|)|\mathrm{Occ}_\Pi(\rho,h)|\le p'(|A|).✦

An observer of a machine PP is a closed term OO over its symbols, with value OσO^\sigma in a store σ\sigma.✦ The objects observed by OO in the run of PP on ρ\rho up to step hh form the set ObsP,O(ρ,h)=ActP(ρ,h)∪⋃j<h⋃y∈Oσjcl(y),\mathrm{Obs}_{P,O}(\rho,h) = \mathrm{Act}_P(\rho,h)\cup\bigcup_{j<h}\ \bigcup_{y\in O^{\sigma_j}}\mathrm{cl}(y),(5) and PP observed by OO accepts ρ\rho within (p,p′)(p,p'), written Accp,p′(P,O,ρ)\mathrm{Acc}_{p,p'}(P,O,\rho), under the condition defining Accp,p′(Π,ρ)\mathrm{Acc}_{p,p'}(\Pi,\rho) with (5) in place of (4).✦

The compiled machine PΠP_\Pi of a program Π\Pi has the dynamic function symbols and arities of Π\Pi, and its rule is the body of Π\Pi translated construct by construct✦: a variable becomes a reference to the binder of that name around it, or the constant 00 when there is none, and a disjunction of tt and t′t' becomes ¬(¬t∧¬t′)\neg(\neg t\wedge\neg t').✦ The collecting term coll(Π′)\mathrm{coll}(\Pi') of a CPT rule Π′\Pi' is defined by recursion on Π′\Pi', merging the collecting terms of its terms with those of the subrules it executes, the body of a loop being collected at every element of the bound and that of a local definition at its value.✦ The root observer OΠO_\Pi is the compiled form of 𝒊𝒇halt𝒕𝒉𝒆𝒏0𝒆𝒍𝒔𝒆coll(Π0)\mathbf{if}\ \mathrm{halt}\ \mathbf{then}\ 0\ \mathbf{else}\ \mathrm{coll}(\Pi_0), where Π0\Pi_0 is the body of Π\Pi.✦

The Grid Structures

The grid of side LL has vertex set V={0,…,L−1}3V = \{0,\dots,L-1\}^3✦, edge set EE made of the unit segments along the three axes, each directed from its tail to its head, the endpoint with the larger coordinate✦, and face set FF made of the unit squares parallel to the three coordinate planes.✦ The edges at a vertex vv are those with vv as head or tail, and ε(v,e)\varepsilon(v,e) is 11 if vv is the head of ee, −1-1 if it is the tail, and 00 otherwise.✦ The boundary map ∂:𝔽3E→𝔽3V\partial:\mathbb{F}_3^E\to\mathbb{F}_3^V sends a chain zz to ∑ez(e)(1head(e)−1tail(e))\sum_e z(e)\,(1_{\mathrm{head}(e)}-1_{\mathrm{tail}(e)}), where 1v∈𝔽3V1_v\in\mathbb{F}_3^V is the indicator vector of a vertex vv.✦ The central flow group KK is the kernel of ∂\partial, the space of flows, written multiplicatively.✦ The face cycle γf∈𝔽3E\gamma_f\in\mathbb{F}_3^E of a face ff goes once around its boundary, with value ±1\pm1 on its four sides and 00 elsewhere.✦

For an edge ee, the faces on ee are the faces ff with γf(e)≠0\gamma_f(e)\neq0.✦ The local group HeH_e of ee is the central extension attached to the local cycle f↦γf(e)f\mapsto\gamma_f(e) on the faces on ee✦; its elements pair a labelling of the faces on ee by points of the plane 𝔽32\mathbb{F}_3^2 with a flow in 𝔽3\mathbb{F}_3.✦ A local state ss at a vertex vv assigns an element se∈Hes_e\in H_e to each edge ee at vv.✦ The local state ss is compatible when ses_e and se′s_{e'} have the same component at every face on both ee and e′e'✦, and its divergence is the net flow ∑eε(v,e)flow(se)\sum_e\varepsilon(v,e)\,\mathrm{flow}(s_e) into vv, where flow(se)∈𝔽3\mathrm{flow}(s_e)\in\mathbb{F}_3 is the flow of ses_e.✦ For a charge b∈𝔽3Vb\in\mathbb{F}_3^V, a configuration at vv is a compatible local state at vv with divergence b(v)b(v).✦

The vocabulary τ\tau has the eight binary symbols Ed\mathrm{Ed}, Cf\mathrm{Cf}, EB\mathrm{EB}, VB\mathrm{VB}, II, Z0Z_0, Z1Z_1, Z2Z_2.✦ The grid structure AbA_b of a charge b∈𝔽3Vb\in\mathbb{F}_3^V on the grid of side LL is the input over τ\tau whose atoms are the edge atoms (e,s)(e,s) with s∈Hes\in H_e and the configuration atoms (v,c)(v,c) with cc a configuration at vv for bb. In AbA_b, Ed\mathrm{Ed} holds between each edge atom and itself and Cf\mathrm{Cf} between each configuration atom and itself, EB\mathrm{EB} relates edge atoms on the same edge and VB\mathrm{VB} configuration atoms at the same vertex, II relates (v,c)(v,c) to the edge atom (e,ce)(e,c_e) for every edge ee at vv, and, for δ∈𝔽3\delta\in\mathbb{F}_3, ZδZ_\delta relates (e,s)(e,s) to (e,t)(e,t) when s−1ts^{-1}t has flow δ\delta.✦ The group KK acts on the atoms of AbA_b: a flow κ∈K\kappa\in K moves an edge atom (e,s)(e,s) to (e,sκ(e))(e,s\,\kappa(e)) and a configuration atom (v,c)(v,c) to (v,c′)(v,c') with ce′=ceκ(e)c'_e=c_e\,\kappa(e) for every edge ee at vv.

Counting Logic and Uniform Definability

A binary relational structure SS with universe DD interprets each symbol of its vocabulary as a binary relation on DD.✦ For m∈ℕm\in\mathbb{N}, the formulas of the counting logic CmC^m with mm variables over that vocabulary are built from ⊥\bot, the equations x=yx = y and the atoms r(x,y)r(x,y) between the variables x0,…,xm−1x_0,\dots,x_{m-1} by negation, conjunction, the quantifiers ∃x\exists x and the counting quantifiers ∃=ax\exists^{=a}x for a∈ℕa\in\mathbb{N}, where ∃=axφ\exists^{=a}x\,\varphi holds when exactly aa values of xx satisfy φ\varphi.✦ Free variables and satisfaction S⊨φ[v]S\models\varphi[v] under an assignment vv of elements of DD to the variables are the usual ones.

Throughout, (Si)i∈I(S_i)_{i\in I} is a family of such structures over one vocabulary, the universe of SiS_i being a set Di⊆HF(Ai)D_i\subseteq\mathrm{HF}(A_i) of hereditarily finite objects over a set of atoms AiA_i. A family of relations Ui⊆DinU_i\subseteq D_i^n is uniformly definable with mm variables if for every map α:{0,…,n−1}→{0,…,m−1}\alpha:\{0,\dots,n-1\}\to\{0,\dots,m-1\} there is one formula φ\varphi of CmC^m, with free variables among xα(0),…,xα(n−1)x_{\alpha(0)},\dots,x_{\alpha(n-1)}, such that Si⊨φ[v]⇔(v(xα(0)),…,v(xα(n−1)))∈UiS_i\models\varphi[v] \iff \big(v(x_{\alpha(0)}),\dots,v(x_{\alpha(n-1)})\big)\in U_i(6)✦ for every i∈Ii\in I and every assignment vv of elements of DiD_i to x0,…,xm−1x_0,\dots,x_{m-1}.

The Claim

Theorem 1. Let h,k,m∈ℕh,k,m\in\mathbb{N}.

  1. For every CPT program Π\Pi over RR, every input ρ\rho over a finite set of atoms AA and all polynomials p,p′∈ℕ[X]p,p'\in\mathbb{N}[X], Accp,p′(PΠ,OΠ,ρ)⇔Accp,p′(Π,ρ).\mathrm{Acc}_{p,p'}(P_\Pi,O_\Pi,\rho) \iff \mathrm{Acc}_{p,p'}(\Pi,\rho).(7)✦

  2. Let PP be a machine over RR and ρ\rho an input over a finite set of atoms AA, such that σj\sigma_j has at most kk active objects for every j≤hj\le h at which the run of PP on ρ\rho is defined. Then |TrP(ρ,h)|≤(h+1)(k+βP(k)).\big|\mathrm{Tr}_P(\rho,h)\big| \le (h+1)\,\big(k+\beta_P(k)\big).(8)✦

  3. Let L≥2L\ge2, b∈𝔽3Vb\in\mathbb{F}_3^V, N≥1N\ge1 an integer and q≥0q\ge0 a real number, and let PP be a machine over τ\tau such that σj\sigma_j has at most kk active objects for every j≤hj\le h at which the run of PP on AbA_b is defined, and (h+1)(k+βP(k))≤Nq(h+1)(k+\beta_P(k))\le N^q. Then, for the action of KK on the atoms of AbA_b, TrP(Ab,h)⊆HSsK,s=⌈2L(qlog⁡3N)2⌉.\mathrm{Tr}_P(A_b,h)\subseteq\mathrm{HS}^K_s, \qquad s = \big\lceil 2L\,(q\log_3 N)^2\big\rceil.(9)✦

  4. Let PP be a machine over RR and, for each i∈Ii\in I, let ρi\rho_i be an input over AiA_i on which the run of PP is defined up to step hh, with stores σi,0,…,σi,h\sigma_{i,0},\dots,\sigma_{i,h}. Suppose that m≥6m\ge6, that m≥ar(f)+2+w(ΠP)m\ge\mathrm{ar}(f)+2+w(\Pi_P) for every function symbol ff of PP, and that for every ii and every j<hj<h each object of trσi,j(ΠP)\mathrm{tr}_{\sigma_{i,j}}(\Pi_P) lies in DiD_i and has at most kk elements. Then for every function symbol ff of PP the family {(z,x‾)∈Di1+ar(f):z=σi,h(f,x‾)},i∈I,\big\{(z,\bar x)\in D_i^{1+\mathrm{ar}(f)} : z = \sigma_{i,h}(f,\bar x)\big\}, \qquad i\in I,(10)✦ is uniformly definable with mm variables.

  5. Suppose that every AiA_i is finite, that every DiD_i contains the elements of its members and every ordinal [j][j], that the membership relation and the property of being a set are uniformly definable with mm variables, and that m≥6m\ge6. Then the family {(z,x)∈Di2:|x|≤k,z=[|x|]},i∈I,\big\{(z,x)\in D_i^2 : |x|\le k,\ z = [\,|x|\,]\big\}, \qquad i\in I,(11)✦ is uniformly definable with mm variables.

  6. Let ℓ∈ℕ\ell\in\mathbb{N} with ℓ+5≤m\ell+5\le m, and let the families Bi⊆Di1+ℓB_i\subseteq D_i^{1+\ell} and Qi,Ti⊆Di2+ℓQ_i,T_i\subseteq D_i^{2+\ell} be uniformly definable with mm variables. Then so is the family of relations Zi⊆Di1+ℓZ_i\subseteq D_i^{1+\ell} given, with all quantifiers over DiD_i, by Zi(z,y‾)⇔∃u(Bi(u,y‾)∧∀x∈u∃g∃y(Qi(g,x,y‾)∧Ti(y,x,y‾))∧z is a set∧∀y(y∈z↔∃x∈u(Qi(1,x,y‾)∧Ti(y,x,y‾)))).\begin{aligned} Z_i(z,\bar y) \iff \exists u\,\Big(&B_i(u,\bar y)\ \wedge\ \forall x\in u\ \exists g\,\exists y\,\big(Q_i(g,x,\bar y)\wedge T_i(y,x,\bar y)\big)\\ &\wedge\ z\text{ is a set}\ \wedge\ \forall y\,\big(y\in z\leftrightarrow \exists x\in u\,(Q_i(1,x,\bar y)\wedge T_i(y,x,\bar y))\big)\Big). \end{aligned}(12)✦

What Is Checked

The theorem is stated over operational machines with their stores, runs, active objects, evaluation traces, bounds and widths, over CPT programs with their occurring objects, compiled machines and root observers, over the grid structures AbA_b with the action of KK on their atoms, and over uniform definability in CmC^m for families of structures on hereditarily finite objects.