OctoInformBeta

OpenAI preprint, September 2026 · §6. Encoding complete choiceless computations

Lemma 19: For 2≤B2 \le B, j≤Bj \le B and an input and states of at most BB elements, a transitive, automorphism-invariant family of at most 9B39B^3 objects

A bounded interpretation program leaves a small invariant trace.

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

A choiceless computation on a finite structure builds hereditarily finite objects over the atoms of its input and never chooses among them. Fix a bound B≥2B \ge 2, run a program on an input of at most BB elements whose states up to a stage j≤Bj \le B have at most BB elements each, and code every element of every state by a hereditarily finite object over the input. The question is how many objects the run touches, counting the input atoms, the codes and everything that occurs in a code as a member, a member of a member and so on, and whether they fit in one small transitive family, that is, a family closed under membership, which the automorphisms of the input also leave invariant. On the grid structures on which choiceless polynomial time with counting is separated from polynomial time, the further question is how many atoms it takes to support each such object. The library answers both for interpretation programs, whose steps are two-dimensional interpretations in Härtig logic.

Hereditarily Finite Objects and Structures

The set HF(A)\mathrm{HF}(A) of hereditarily finite objects over a set AA of atoms consists of the atoms of AA and the finite sets whose elements lie in HF(A)\mathrm{HF}(A), two sets being equal when they have the same elements.✦ A map f:A→A′f\colon A \to A' extends to the map f:HF(A)→HF(A′)f\colon \mathrm{HF}(A) \to \mathrm{HF}(A') that replaces each atom aa occurring in an object by f(a)f(a).✦

A finite structure 𝔄\mathfrak A over a set RR of binary relation symbols is a finite set AA, its universe, with a binary relation r𝔄r^{\mathfrak A} on AA for each r∈Rr \in R.✦ An isomorphism π:𝔄→𝔄′\pi\colon \mathfrak A \to \mathfrak A' of finite structures over RR is a bijection π:A→A′\pi\colon A \to A' of their universes such that r𝔄(x,y)⇔r𝔄′(πx,πy)(r∈R,x,y∈A),r^{\mathfrak A}(x,y) \iff r^{\mathfrak A'}(\pi x,\pi y) \qquad (r \in R,\ x,y \in A),(1)✦ and an automorphism of 𝔄\mathfrak A is an isomorphism of 𝔄\mathfrak A with itself.

Interpretation Programs and Their Trace

A formula of Härtig logic over RR in nn free variables is falsity, an equation x=yx = y or an atomic formula r(x,y)r(x,y) with r∈Rr \in R between two of the variables, the negation of a formula, the conjunction of two formulas, the existential quantification of a formula in one more variable, or the Härtig quantification of two formulas in one more variable, which says that they are satisfied by equally many elements.✦

An interpretation ℐ\mathcal I of structures over a set TT of binary relation symbols in structures over RR is two-dimensional and consists of formulas of Härtig logic over RR, ℐ=(φdom(x1,x2),φ≈(x1,x2,y1,y2),(φt(x1,x2,y1,y2))t∈T),\mathcal I = \bigl(\varphi_{\mathrm{dom}}(x_1,x_2),\ \varphi_{\approx}(x_1,x_2,y_1,y_2),\ (\varphi_t(x_1,x_2,y_1,y_2))_{t \in T}\bigr),(2)✦ where φdom\varphi_{\mathrm{dom}} defines the domain as a set of pairs, φ≈\varphi_{\approx} says which pairs are identified, and φt\varphi_t defines between pairs the relation named by tt. The interpretation ℐ\mathcal I defines in a structure 𝔄\mathfrak A over RR the structure ℐ(𝔄)\mathcal I(\mathfrak A) over TT, whose elements are classes of identified pairs.

An interpretation program PP over RR consists of a finite set TT of state symbols, an initial interpretation ℐinit\mathcal I_{\mathrm{init}} of structures over TT in structures over RR, a step interpretation ℐstep\mathcal I_{\mathrm{step}} of structures over TT in structures over TT, and two sentences of Härtig logic over TT, the halting condition and the output condition.✦ The state of PP after jj steps on a finite structure 𝔄\mathfrak A over RR is the finite structure Pj(𝔄)P_j(\mathfrak A) over TT given by P0(𝔄)=ℐinit(𝔄),Pj+1(𝔄)=ℐstep(Pj(𝔄)).P_0(\mathfrak A) = \mathcal I_{\mathrm{init}}(\mathfrak A), \qquad P_{j+1}(\mathfrak A) = \mathcal I_{\mathrm{step}}\bigl(P_j(\mathfrak A)\bigr).(3)✦

An element of a state, a class of identified pairs, is coded by the set of the codes of its pairs, and the code of a pair is the Kuratowski pair ⟨a,b⟩\langle a,b\rangle of the codes aa and bb of its two coordinates. The base family ℱ0(𝔄,B)\mathcal F_0(\mathfrak A,B) of a finite structure 𝔄\mathfrak A over RR with universe AA for a bound BB is the finite subset of HF(A)\mathrm{HF}(A) consisting of the atoms of AA and the von Neumann ordinals [0],…,[B][0],\dots,[B]; it opens the next paragraph, which defines the trace family.

For such a program PP, a finite structure 𝔄\mathfrak A over RR with universe AA and a bound BB, the trace family of PP on 𝔄\mathfrak A is the increasing sequence of finite sets ℱj(𝔄,B)⊆HF(A)\mathcal F_j(\mathfrak A,B) \subseteq \mathrm{HF}(A), for j≥0j \ge 0, that starts from the base family ℱ0(𝔄,B)\mathcal F_0(\mathfrak A,B) of 𝔄\mathfrak A for BB and grows by ℱj+1(𝔄,B)=ℱj(𝔄,B)∪𝒫j∪𝒞j,\mathcal F_{j+1}(\mathfrak A,B) = \mathcal F_j(\mathfrak A,B) \cup \mathcal P_j \cup \mathcal C_j,(4)✦ where 𝒫j\mathcal P_j and 𝒞j\mathcal C_j are the codes of pairs and the codes of classes that arise in coding the elements of Pj(𝔄)P_j(\mathfrak A): from 𝔄\mathfrak A and its atoms through ℐinit\mathcal I_{\mathrm{init}} when j=0j = 0, and from Pj−1(𝔄)P_{j-1}(\mathfrak A) and its codes through ℐstep\mathcal I_{\mathrm{step}} when j≥1j \ge 1.

Supports

Let a group GG act on a set AA of atoms, and through them on HF(A)\mathrm{HF}(A). A tuple α=(α0,…,αk−1)\alpha = (\alpha_0,\dots,\alpha_{k-1}) of atoms supports an object x∈HF(A)x \in \mathrm{HF}(A) when every element of GG that fixes each entry of α\alpha fixes xx: gαi=αifor all i<k⟹gx=x(g∈G).g\alpha_i = \alpha_i \ \text{for all } i < k \implies gx = x \qquad (g \in G).(5)✦ For a natural number ss, an object x∈HF(A)x \in \mathrm{HF}(A) is ss-supported when some tuple of ss atoms supports it✦, and hereditarily ss-supported when every object reached from xx in finitely many steps down membership, xx itself, its elements, their elements and so on, is ss-supported.✦

The Grid Structure

Fix n≥1n \ge 1. The grid has side L=n+1L = n + 1 and scalars in the field 𝔽=𝔽3\mathbb F = \mathbb F_3, where 1/2=21/2 = 2. Its vertex set is V={0,…,L−1}3V = \{0,\dots,L-1\}^3, with L3L^3 elements.✦ Its edges are the unit segments parallel to a coordinate axis, each running from its tail to its head: the edge ex(i,j,k)e_x(i,j,k) along xx runs from (i,j,k)(i,j,k) to (i+1,j,k)(i+1,j,k), and the edges ey(i,j,k)e_y(i,j,k) along yy and ez(i,j,k)e_z(i,j,k) along zz raise the second and the third coordinate instead. The edge set EE is the disjoint union of these three families.✦ A vertex vv is incident to an edge ee when it is the head or the tail of ee✦, and the edges at vv are those incident to it✦; the sign ε(v,e)∈𝔽\varepsilon(v,e) \in \mathbb F is 11 if vv is the head of ee, −1-1 if vv is its tail, and 00 otherwise.✦ The face set FF consists of the unit squares parallel to the xyxy, the xzxz or the yzyz plane, each given by its lowest corner.✦

The face cycle γf∈𝔽E\gamma_f \in \mathbb F^E of a face ff goes once around its boundary: it is +1+1 on the two sides of ff crossed in their own direction, −1-1 on the other two and 00 elsewhere.✦ The boundary map ∂:𝔽E→𝔽V\partial\colon \mathbb F^E \to \mathbb F^V is the linear map given, with 𝟏v∈𝔽V\mathbf 1_v \in \mathbb F^V the vector that is 11 at the vertex vv and 00 elsewhere, by ∂z=∑e∈Ez(e)(𝟏head(e)−𝟏tail(e)),\partial z = \sum_{e \in E} z(e)\,\bigl(\mathbf 1_{\mathrm{head}(e)} - \mathbf 1_{\mathrm{tail}(e)}\bigr),(6)✦ and its kernel ker⁡∂\ker\partial is the space of flows, the labellings of the edges whose boundary vanishes at every vertex.✦ The central group KK is ker⁡∂\ker\partial written multiplicatively.✦

For a set DD of faces, a vector space WW of flows over 𝔽\mathbb F and a map γ:D→W\gamma\colon D \to W, the support group HγH_\gamma attached to γ\gamma is the central extension by WW of the group CDC_D of labellings u:D→𝔽2u\colon D \to \mathbb F^2 of the faces by points of the plane; its elements are the pairs (u,w)(u,w) of a labelling uu and a flow w∈Ww \in W.✦ The faces on an edge ee are the faces ff with γf(e)≠0\gamma_f(e) \ne 0✦, and the local cycle of ee sends each face ff on ee to γf(e)\gamma_f(e).✦ The local group HeH_e of ee is the support group of its local cycle, with W=𝔽W = \mathbb F: its elements are the pairs (u,δ)(u,\delta) of a labelling uu of the faces on ee by points of 𝔽2\mathbb F^2 and a scalar δ\delta, their flow.✦

A local state ss at a vertex vv assigns to each edge ee at vv an element s(e)=(ue,δe)s(e) = (u_e,\delta_e) of HeH_e.✦ A local state ss at vv is compatible when any two edges ee and e′e' at vv on a common face ff receive labellings that agree at ff, ue(f)=ue′(f)u_e(f) = u_{e'}(f), and the divergence div⁡s\operatorname{div} s of ss is the net flow into vv, div⁡s=∑e at vε(v,e)δe.\operatorname{div} s = \sum_{e \text{ at } v} \varepsilon(v,e)\,\delta_e .(7) For a charge b∈𝔽Vb \in \mathbb F^V, a configuration at vv is a compatible local state at vv whose divergence is b(v)b(v).✦

The atoms of a charge bb are of two sorts: the edge atoms (e,h)(e,h), of an edge ee and an element h∈Heh \in H_e, and the configuration atoms (v,s)(v,s), of a vertex vv and a configuration ss at vv.✦ The vocabulary τ\tau consists of 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 𝔄b\mathfrak A_b of bb is the finite structure over τ\tau whose universe is the set of atoms of bb, in which Ed\mathrm{Ed} relates each edge atom to itself and Cf\mathrm{Cf} each configuration atom to itself, EB\mathrm{EB} relates any two edge atoms over the same edge and VB\mathrm{VB} any two configuration atoms over the same vertex, II relates (v,s)(v,s) to (e,s(e))(e,s(e)) for each edge ee at vv, and ZδZ_\delta relates (e,h)(e,h) to (e,h′)(e,h') when h−1h′h^{-1}h' has flow δ\delta.

The Claim

Theorem 1. Let PP be an interpretation program over RR, let 𝔄\mathfrak A be a finite structure over RR, let BB and jj be natural numbers, and write ℱj\mathcal F_j for ℱj(𝔄,B)\mathcal F_j(\mathfrak A,B).

  1. Suppose that 2≤B2 \le B and j≤Bj \le B, that 𝔄\mathfrak A has at most BB elements, and that each state Pk(𝔄)P_k(\mathfrak A) with k<jk < j has at most BB elements. Then, for every automorphism π\pi of 𝔄\mathfrak A, |ℱj|≤9B3,y∈x∈ℱj⟹y∈ℱj,π(ℱj)⊆ℱj.|\mathcal F_j| \le 9B^3, \qquad y \in x \in \mathcal F_j \implies y \in \mathcal F_j, \qquad \pi(\mathcal F_j) \subseteq \mathcal F_j.(8)✦

  2. If 𝔄\mathfrak A has at most BB elements and each state Pk(𝔄)P_k(\mathfrak A) with k<jk < j has at most BB elements, then |ℱj|≤j(3B2+4B)+2B+1.|\mathcal F_j| \le j\,(3B^2 + 4B) + 2B + 1.(9)✦

  3. If j≤Bj \le B, then y∈x∈ℱj⟹y∈ℱj.y \in x \in \mathcal F_j \implies y \in \mathcal F_j.(10)✦

  4. For every isomorphism π:𝔄→𝔄′\pi\colon \mathfrak A \to \mathfrak A' of finite structures over RR and every object xx, x∈ℱj(𝔄,B)⟹π(x)∈ℱj(𝔄′,B).x \in \mathcal F_j(\mathfrak A,B) \implies \pi(x) \in \mathcal F_j(\mathfrak A',B).(11)✦

  5. Let R=τR = \tau and let 𝔄=𝔄b\mathfrak A = \mathfrak A_b be the grid structure of a charge bb on the grid of side L=n+1L = n + 1, with n≥1n \ge 1; let NN be a positive integer and q≥0q \ge 0 a real number. Suppose that 2≤B2 \le B and j≤Bj \le B, that 𝔄b\mathfrak A_b has at most BB atoms, that each state Pk(𝔄b)P_k(\mathfrak A_b) with k<jk < j has at most BB elements, and that 9B3≤Nq9B^3 \le N^q. Then, for the action of the central group KK on the atoms of 𝔄b\mathfrak A_b, x∈ℱj(𝔄b,B)⟹x is hereditarily ⌈2L(qlog⁡3N)2⌉-supported.x \in \mathcal F_j(\mathfrak A_b,B) \implies x \text{ is hereditarily } \bigl\lceil 2L\,(q\log_3 N)^2 \bigr\rceil\text{-supported}.(12)✦

In the paper, the result reads: for either of the two inputs 𝔄b0\mathfrak A_{b^0} and 𝔄b1\mathfrak A_{b^1}, with b0=0b^0 = 0 and b1=𝟏v*b^1 = \mathbf 1_{v^*} for a vertex v*v^*, the input atoms, all vertex codes up to halting and all objects recursively occurring as members of those codes belong to an HH-invariant transitive family of at most 9B39B^3 objects, H=CF×KH = C_F \times K being the central extension of the group CFC_F of face labellings by KK.

What Is Checked

The claim is stated over interpretation programs of Härtig logic and their states (3), the trace family (4) of hereditarily finite objects over the input, isomorphisms (1) of finite structures acting on these objects through their atoms, and, in (12), the grid structure 𝔄b\mathfrak A_b of a charge, with the central group KK acting on its atoms and the supports (5) for that action.