OctoInformBeta

OpenAI preprint, September 2026 · §5. From atom types to hereditarily finite sets

Theorem 14: For max⁡{4,m+1}s≤M\max\{4,m+1\}s\le M, CMC^M-equivalent structures homogeneous under their groups have CmC^m-equivalent domains of hereditarily ss-supported sets, applied to the grid

Transfer of counting equivalence to hereditarily supported sets.

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

Lower bounds for choiceless polynomial time with counting (CPT) compare two structures through the hereditarily finite sets built over their elements. The sets that matter have small supports hereditarily: the set, its elements, their elements and so on are each fixed by every element of a given group that fixes some short tuple of atoms. The question is when two structures A0A_0 and A1A_1 that a counting logic with MM variables cannot distinguish give universes of such sets that a counting logic with fewer variables cannot distinguish either.

The library answers it for two structures in one binary vocabulary with groups acting on them, in a form with arbitrary sets of variables, and for the grid structures on which the separation of CPT from polynomial time is built, under the central flow group.

Counting Logic and Types

A binary relational structure AA over a vocabulary RR is a set AA, its universe, with a binary relation rAr^A on AA for each symbol rr of RR.✦ The formulas of counting logic over RR with variables from a set II are built from ⊥\bot, equations x=yx = y and atoms r(x,y)r(x,y), for x,y∈Ix,y\in I and r∈Rr\in R, by negation, conjunction, existential quantification ∃x\exists x and, for each natural number nn, the counting quantifier ∃=nx\exists^{=n}x.✦ Satisfaction A⊨φ[v]A\models\varphi[v] under an assignment v:I→Av\colon I\to A is defined by recursion on φ\varphi as for first-order logic, with A⊨∃=nxφ[v]⇔|{a∈A:A⊨φ[v(x↦a)]}|=n.A\models\exists^{=n}x\,\varphi[v]\iff \bigl|\{a\in A : A\models\varphi[v(x\mapsto a)]\}\bigr| = n.(1)✦ The free variables of a formula are those occurring in it outside the scope of a quantifier binding them, and a sentence is a formula without free variables.✦ We write CMC^M for counting logic with the variables x1,…,xMx_1,\dots,x_M; two structures are CMC^M-equivalent when they satisfy the same sentences of CMC^M.

Let a=(aj)j∈Ja = (a_j)_{j\in J} be a tuple of elements of AA indexed by a finite set JJ, and let an injection e:J→Ie\colon J\to I place the entry aja_j at the variable e(j)e(j). The counting type of aa under ee is the set of formulas tpAe(a)={φ:the free variables of φ lie in e(J) and A⊨φ[e(j)↦aj]},\mathrm{tp}^e_A(a) = \{\varphi : \text{the free variables of $\varphi$ lie in $e(J)$ and } A\models\varphi[e(j)\mapsto a_j]\},(2)✦ and for the empty tuple it is the set of sentences true in AA.

A structure AA on which a group GG acts is homogeneous under GG through length rr in CMC^M when, for every k≤rk\le r and every injection ee of {1,…,k}\{1,\dots,k\} into {x1,…,xM}\{x_1,\dots,x_M\}, any two kk-tuples aa and bb of AA of the same type under ee lie in one GG-orbit: tpAe(a)=tpAe(b)⟹∃g∈G∀j:gaj=bj.\mathrm{tp}^e_A(a) = \mathrm{tp}^e_A(b) \implies \exists g\in G\ \forall j\colon\ g a_j = b_j.(3)✦

Hereditarily Supported Sets

For a set AA of atoms, HF(A)\mathrm{HF}(A) is the set of hereditarily finite objects over AA: the atoms, which have no elements, and the finite sets whose elements are again in HF(A)\mathrm{HF}(A), two sets being equal when they have the same elements.✦ Let a group GG act on AA, and with it on HF(A)\mathrm{HF}(A). A tuple α=(α1,…,αk)\alpha = (\alpha_1,\dots,\alpha_k) of atoms supports an object xx of HF(A)\mathrm{HF}(A) when gx=x for every g∈G with gαi=αi for i=1,…,k.g x = x \text{ for every } g\in G \text{ with } g\alpha_i = \alpha_i \text{ for } i = 1,\dots,k.(4)✦ An object xx of HF(A)\mathrm{HF}(A) is ss-supported when some tuple of ss atoms supports it✦, and hereditarily ss-supported when xx, its elements, their elements and so on are all ss-supported.✦ The domain Ds(A,G)D_s(A,G) is the set of hereditarily ss-supported objects of HF(A)\mathrm{HF}(A).✦

For a vocabulary RR, the vocabulary RHFR^{\mathrm{HF}} consists of a membership symbol ∈\in, an atom symbol At\mathrm{At} and the symbols of RR, all binary.✦ For a structure AA over RR with GG acting on its universe, D=Ds(A,G)D = D_s(A,G) is the structure over RHFR^{\mathrm{HF}} with universe Ds(A,G)D_s(A,G) and, for x,yx,y in it and r∈Rr\in R, x∈Dy⇔x∈y,AtD(x,y)⇔x is an atom,rD(x,y)⇔x,y are atoms with rA(x,y).x\in^{D}y \iff x\in y,\qquad \mathrm{At}^{D}(x,y) \iff x \text{ is an atom},\qquad r^{D}(x,y) \iff x,y \text{ are atoms with } r^A(x,y).(5)✦

The Grid Structures

The grid of side L=n+1L = n+1, for a positive integer nn, has vertex set V={0,…,L−1}3V = \{0,\dots,L-1\}^3.✦ Its edge set EE consists of the unit segments parallel to the xx, yy and zz axes, each directed from its tail to its head, the endpoint with the larger coordinate along it✦, and its face set FF of the unit squares parallel to the xyxy, xzxz and yzyz planes✦. With 1u1_u the indicator vector of a vertex uu, the boundary map ∂:𝔽3E→𝔽3V\partial\colon\mathbb F_3^E\to\mathbb F_3^V is the linear map ∂z=∑e∈Ez(e)(1head(e)−1tail(e));\partial z = \sum_{e\in E} z(e)\,\bigl(1_{\mathrm{head}(e)} - 1_{\mathrm{tail}(e)}\bigr);(6)✦ the flows are the elements of ker⁡∂\ker\partial✦, and the central flow group KK is ker⁡∂\ker\partial written multiplicatively, so that adding flows is multiplying in KK✦. The face cycle γf∈𝔽3E\gamma_f\in\mathbb F_3^E of a face ff goes once around ff: it is 11 on the two sides crossed in their own direction, −1-1 on the other two and 00 elsewhere.✦

The local group of an edge ee is the central extension, attached to the coefficients γf(e)\gamma_f(e) of the faces ff on ee (those having ee as a side), of the group of labellings of these faces by points of the plane 𝔽32\mathbb F_3^2 by the group 𝔽3\mathbb F_3; its elements are the pairs of such a labelling, the face part, and a scalar, the flow.✦ A local state at a vertex vv assigns to each edge at vv, an edge with head or tail vv, an element of its local group.✦ A local state at vv is compatible when the elements at any two edges at vv have the same face part at every face whose boundary passes through both.✦ The divergence of a local state at vv is the net flow into vv, the sum over the edges ee at vv of ε(v,e)\varepsilon(v,e) times the flow at ee, where ε(v,e)\varepsilon(v,e) is 11 if vv is the head of ee and −1-1 if vv is its tail.✦ 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 grid structure AbA_b of a charge bb is the structure over the vocabulary τ={Ed,Cf,EB,VB,I,Z0,Z1,Z2}\tau = \{\mathrm{Ed},\mathrm{Cf},\mathrm{EB},\mathrm{VB},I,Z_0,Z_1,Z_2\} of eight binary symbols whose atoms are the edge atoms (e,g)(e,g), with gg in the local group of ee, and the configuration atoms (v,σ)(v,\sigma), with σ\sigma a configuration at vv. Here Ed\mathrm{Ed} relates each edge atom to itself and Cf\mathrm{Cf} each configuration atom to itself, EB\mathrm{EB} any two edge atoms over one edge and VB\mathrm{VB} any two configuration atoms over one vertex; II relates (v,σ)(v,\sigma) to (e,σ(e))(e,\sigma(e)) for each edge ee at vv, and, for δ∈𝔽3\delta\in\mathbb F_3, ZδZ_\delta relates (e,g)(e,g) to (e,h)(e,h) when g−1hg^{-1}h has flow δ\delta. The central flow group KK acts on the atoms of every AbA_b.

The analysis expansion A‾b\bar A_b is the structure on the same atoms over the analysis signature τ‾\bar\tau, which adds to τ\tau a preorder symbol ≼\preceq and a raw symbol Rawδ\mathrm{Raw}_\delta for each δ∈𝔽3\delta\in\mathbb F_3. The symbols of τ\tau keep their relations. The class label of an atom is obtained from the atom by keeping its edge or vertex and only the face parts of its group elements.✦ The class index of an atom is the position of its class label in a fixed enumeration of all class labels, and x≼yx\preceq y holds when the class index of xx is at most that of yy. Finally Rawδ\mathrm{Raw}_\delta relates (e,g)(e,g) to (e,h)(e,h) when the flow of hh minus that of gg is δ\delta.✦

The box constant is c=1−2−1/3c = 1-2^{-1/3}✦, and nn and MM satisfy the giant component bound when (12M/c)3/2<(n+1)3.(12M/c)^{3/2} < (n+1)^3.(7)✦

The Claim

Theorem 1. (a) Let A0A_0 and A1A_1 be nonempty structures over one binary vocabulary RR, let groups K0K_0 and K1K_1 act on them by automorphisms, and let ss, mm and MM be positive integers with max⁡{4,m+1}s≤M\max\{4,m+1\}s\le M. Suppose that A0A_0 and A1A_1 are CMC^M-equivalent and that each AiA_i is homogeneous under KiK_i through length max⁡{2,m}s\max\{2,m\}s in CMC^M. Then every sentence φ\varphi of CmC^m over RHFR^{\mathrm{HF}} satisfies Ds(A0,K0)⊨φ⇔Ds(A1,K1)⊨φ.D_s(A_0,K_0)\models\varphi \iff D_s(A_1,K_1)\models\varphi.(8)✦

(b) Let A0A_0 and A1A_1 be nonempty structures over RR, let groups K0K_0 and K1K_1 act on them, and let ss be a positive integer, II a set of variables and VV a finite set of variables. Fix an injection e2e_2 placing the 2s2s entries of a pair of ss-tuples at distinct variables of II, and an injection eVe_V placing the entries of a family of ss-tuples indexed by VV at distinct variables of II. Suppose that in each AiA_i any two pairs of ss-tuples with the same type under e2e_2 lie in one KiK_i-orbit, as do any two such families with the same type under eVe_V, and that A0A_0 and A1A_1 satisfy the same sentences of counting logic with variables from II. Then every sentence φ\varphi over RHFR^{\mathrm{HF}} with variables from VV satisfies Ds(A0,K0)⊨φ⇔Ds(A1,K1)⊨φ.D_s(A_0,K_0)\models\varphi \iff D_s(A_1,K_1)\models\varphi.(9)✦

(c) Let nn, ss and mm be positive integers and MM a natural number, let v*v^* be a vertex of the grid of side n+1n+1, and suppose that the grid structures Ab0A_{b^0} and Ab1A_{b^1} of the charges b0=0b^0 = 0 and b1=1v*b^1 = 1_{v^*} have atoms. With r=max⁡{2,m}sr = \max\{2,m\}s, suppose that max⁡{4,m+1}s≤M\max\{4,m+1\}s\le M, that 7r+7(6r/c)3/2+1≤M7r + 7(6r/c)^{3/2} + 1\le M, and that nn and MM satisfy the giant component bound (7). Then every sentence φ\varphi of CmC^m over τ‾HF\bar\tau^{\mathrm{HF}} satisfies Ds(A‾b0,K)⊨φ⇔Ds(A‾b1,K)⊨φ.D_s(\bar A_{b^0},K)\models\varphi \iff D_s(\bar A_{b^1},K)\models\varphi.(10)✦

In the paper, the result reads: if A0A_0 and A1A_1 are nonempty finite structures in the same binary vocabulary, Ki≤Aut(Ai)K_i\le\mathrm{Aut}(A_i), and ss, mm, MM are positive integers with max⁡{4,m+1}s≤M\max\{4,m+1\}s\le M such that A0A_0 and A1A_1 satisfy the same CMC^M sentences and in each AiA_i any two tuples of length at most max⁡{2,m}s\max\{2,m\}s with the same CMC^M type lie in the same KiK_i-orbit, then the structures D0D_0 and D1D_1 of the objects xx of HF(Ai)\mathrm{HF}(A_i) such that xx and every object in its transitive closure have a KiK_i-support of length at most ss, with membership, an atom predicate and the relations of AiA_i, false on non-atoms, satisfy the same CmC^m sentences.

What Is Checked

The three statements are stated over counting logic with its satisfaction relation, free variables and types of tuples; over the hereditarily finite objects on a set of atoms, their supports under a group action and the structures Ds(A,G)D_s(A,G) with membership, atom predicate and base relations; over homogeneity through a length; and, in (10), over the grid structures AbA_b, their analysis expansions A‾b\bar A_b, the central flow group KK, the box constant cc and the giant component bound (7).