OctoInformBeta

OpenAI preprint, September 2026 · §4. Counting equivalence and homogeneity

Proposition 13: For n≥1n \ge 1, rr-tuples of atoms of A‾b\bar A_b with equal CMC^M-types and 7r+7(6r/c)3/2+1≤M7r + 7(6r/c)^{3/2} + 1 \le M differ by a flow in KK

Counting types of short grid tuples determine their flow orbit.

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 does not capture polynomial time, and the structures that show it are built from the cubic grid of side L=n+1L = n + 1 and a charge bb, a labelling of its vertices by the field 𝔽=𝔽3\mathbb{F} = \mathbb{F}_3. Each charge gives an analysis structure A‾b\bar A_b on a set of atoms, and the flows of the grid act on these atoms. The question is when two tuples of atoms that no formula of counting logic with MM variables tells apart are carried one onto the other by a flow, and how long such tuples may be against MM.

The Grid

The scalars form the field 𝔽\mathbb{F} of integers modulo 33, in which 1/2=21/2 = 2. The grid of side L=n+1L = n + 1 has the vertex set V={0,…,L−1}3V = \{0, \dots, L-1\}^3, with L3L^3 elements.✦ Its edges are the unit segments parallel to the axes, each running from its lower end, the tail, to its upper end, the head: ex(i,j,k)e_x(i,j,k) runs from (i,j,k)(i,j,k) to (i+1,j,k)(i+1,j,k), with 0≤i≤L−20 \le i \le L-2 and 0≤j,k≤L−10 \le j, k \le L-1, while ey(i,j,k)e_y(i,j,k) and ez(i,j,k)e_z(i,j,k) 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 its head or its tail✦, and ε(v,e)∈𝔽\varepsilon(v,e) \in \mathbb{F} is 11 if vv is the head of ee, −1-1 if it is the tail, and 00 otherwise.✦

The faces are the unit squares parallel to the coordinate planes, each given by its lowest corner, and the face set FF is the disjoint union of the faces in the xyxy, xzxz and yzyz planes.✦ Write 𝟏x\mathbf{1}_x for the indicator vector of an edge or a vertex xx. The face cycle γf∈𝔽E\gamma_f \in \mathbb{F}^E of a face ff goes once around its boundary, with +1+1 on the two sides crossed in their own direction, −1-1 on the other two and 00 elsewhere; for the face in the xyxy plane with lowest corner (i,j,k)(i,j,k), γf=𝟏ex(i,j,k)+𝟏ey(i+1,j,k)−𝟏ex(i,j+1,k)−𝟏ey(i,j,k),\gamma_f = \mathbf{1}_{e_x(i,j,k)} + \mathbf{1}_{e_y(i+1,j,k)} - \mathbf{1}_{e_x(i,j+1,k)} - \mathbf{1}_{e_y(i,j,k)},(1)✦ and the faces in the other two planes are traversed in the same way. The faces on an edge ee are the faces ff with γf(e)≠0\gamma_f(e) \ne 0, the squares having ee as a side.✦

The boundary map ∂:𝔽E→𝔽V\partial \colon \mathbb{F}^E \to \mathbb{F}^V is the linear map ∂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),(2) The kernel ker⁡∂\ker \partial of the boundary map is the space of flows, the labellings of the edges whose boundary vanishes at every vertex, and the central flow group KK is ker⁡∂\ker \partial written multiplicatively.✦

Local Groups and Configurations

The local cycle of an edge ee is the map on the faces on ee that sends ff to the nonzero scalar γf(e)\gamma_f(e).✦ The local group HeH_e of ee is the support group attached to this cycle, the central extension by the flows 𝔽\mathbb{F} of the group of labellings of the faces on ee by points of the plane 𝔽2\mathbb{F}^2.✦ The elements of HeH_e are the pairs s=(u,κ)s = (u, \kappa) of a labelling uu of the faces on ee by points of 𝔽2\mathbb{F}^2, the face part of ss, and a scalar κ=κ(s)\kappa = \kappa(s), the flow of ss.✦ The central element of a flow z∈𝔽z \in \mathbb{F} is (0,z)(0, z)✦, and the local shift of ss by zz is the product (0,z)s(0, z)\,s.✦

The edges at a vertex vv are the edges incident to it.✦ A local state ss at vv assigns to each edge ee at vv an element ses_e of HeH_e✦, and it is compatible when, for any two edges ee and e′e' at vv and any face ff on both, ses_e and se′s_{e'} have the same face part at ff.✦ The divergence of a local state ss at vv is its net flow into vv, div⁡s=∑e at vε(v,e)κ(se).\operatorname{div} s = \sum_{e \text{ at } v} \varepsilon(v,e)\,\kappa(s_e).(3)✦ For a charge b∈𝔽Vb \in \mathbb{F}^V, a configuration for bb at vv is a compatible local state at vv whose divergence is b(v)b(v).✦

For an edge vector t∈𝔽Et \in \mathbb{F}^E, the shift of a local state ss at vv by tt is the local state whose element at each edge ee at vv is the local shift of ses_e by t(e)t(e).✦ If b′b' is a second charge with (∂t)(v)=b′(v)−b(v)(\partial t)(v) = b'(v) - b(v), the shift by tt of a configuration for bb at vv is the configuration for b′b' at vv with the shifted local state.✦

Atoms and the Analysis Structure

For a charge bb, the atoms of the grid structure AbA_b come in two disjoint sorts: the edge atoms (e,s)(e, s) with e∈Ee \in E and s∈Hes \in H_e, which form the set YY, and the configuration atoms (v,s)(v, s) with v∈Vv \in V and ss a configuration for bb at vv, which form the set XX.✦

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, and the atom relations interpret them on the atoms.✦ 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 on the same edge and VB\mathrm{VB} any two configuration atoms at the same vertex. II relates each configuration atom (v,s)(v, s) to the edge atoms (e,se)(e, s_e) for the edges ee at vv, and, for δ∈𝔽\delta \in \mathbb{F}, ZδZ_\delta relates (e,s)(e, s) to (e,t)(e, t) exactly when s−1ts^{-1} t has flow δ\delta.

A face class label is either a pair of an edge ee and a labelling of the faces on ee by points of 𝔽2\mathbb{F}^2, or a pair of a vertex vv and such a labelling for each edge at vv.✦ The class label of an atom keeps its face data: (e,s)(e, s) receives ee with the face part of ss, and (v,s)(v, s) receives vv with the face parts of all the ses_e.✦ The class index of an atom is the position of its class label in a fixed enumeration of the face class labels.✦

A binary relational structure SS over a vocabulary RR is a set AA, its universe, together with a binary relation on AA interpreting each symbol of RR.✦ The analysis signature is the finite vocabulary made of a copy of each symbol of τ\tau, a preorder symbol ≼\preceq and a raw difference symbol DδD_\delta for each δ∈𝔽\delta \in \mathbb{F}.✦ The analysis structure A‾b\bar A_b of a charge bb is the binary relational structure over the analysis signature whose universe is the set of atoms of bb, in which each symbol of τ\tau is its atom relation, x≼yx \preceq y holds when the class index of xx is at most that of yy, and DδD_\delta holds of two atoms exactly when they are edge atoms (e,s)(e, s) and (e,t)(e, t) on the same edge with κ(t)−κ(s)=δ\kappa(t) - \kappa(s) = \delta.✦

For charges bb and b′b' and an edge vector t∈𝔽Et \in \mathbb{F}^E, the atom shift by tt is the relation x→tyx \xrightarrow{t} y from the atoms of bb to those of b′b' that relates each edge atom (e,s)(e, s) to (e,(0,t(e))s)(e, (0, t(e))\,s) and, at each vertex vv with (∂t)(v)=b′(v)−b(v)(\partial t)(v) = b'(v) - b(v), each configuration atom (v,s)(v, s) to (v,s′)(v, s'), where s′s' is the shift of ss by tt.✦ A flow k∈Kk \in K acts on the atoms of A‾b\bar A_b by the atom shift by kk, and k⋅xk \cdot x is the atom to which kk sends the atom xx.

Counting Types and Homogeneity

The formulas of the counting logic CC over a vocabulary RR, with variable names from a set II, are built from ⊥\bot, the equations x=yx = y and the atoms r(x,y)r(x, y) with r∈Rr \in R by negation, conjunction, existential quantification ∃xφ\exists x\, \varphi and exact counting quantification ∃=mxφ\exists^{=m} x\, \varphi for m∈ℕm \in \mathbb{N}.✦ For a natural number MM, CMC^M is the logic whose names are 0,…,M−10, \dots, M-1.

Satisfaction S⊨φ[v]S \models \varphi[v] in a binary relational structure SS with universe AA, under an assignment v:I→Av \colon I \to A, is the usual one, with ∃=mxφ\exists^{=m} x\, \varphi true when exactly mm elements a∈Aa \in A satisfy φ\varphi under vv updated to send xx to aa.✦ The free variables free(φ)\mathrm{free}(\varphi) of a formula are the names occurring in it outside the scope of a quantifier binding them, existential or counting.✦ The type of an assignment vv relative to a finite set NN of names is the set of formulas φ\varphi with free(φ)⊆N\mathrm{free}(\varphi) \subseteq N and S⊨φ[v]S \models \varphi[v].✦

Let SS have a nonempty universe AA, 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 ee be an injection of JJ into the names of CMC^M. The counting type tpe(a)\mathrm{tp}_e(a) of aa at ee is the type, relative to the names e(J)e(J) of the tuple, of the assignment giving each name e(j)e(j) the value aja_j: tpe(a)={φ∈CM:free(φ)⊆e(J),S⊨φ[e(j)↦aj]}.\mathrm{tp}_e(a) = \bigl\{ \varphi \in C^M : \mathrm{free}(\varphi) \subseteq e(J),\ S \models \varphi[e(j) \mapsto a_j] \bigr\}.(4)✦

Let a group GG act on the universe AA of SS. The structure SS is GG-homogeneous through rr in CMC^M when, for every ℓ≤r\ell \le r, every injection ee of {0,…,ℓ−1}\{0, \dots, \ell-1\} into the names of CMC^M and any two ℓ\ell-tuples aa and a′a' of elements of AA, tpe(a)=tpe(a′)⟹∃g∈G:g⋅aj=aj′ for all j.\mathrm{tp}_e(a) = \mathrm{tp}_e(a') \implies \exists g \in G\colon\ g \cdot a_j = a'_j \text{ for all } j.(5)✦

The box isoperimetric constant is c=1−2−1/3≈0.206c = 1 - 2^{-1/3} \approx 0.206.✦ A natural number rr meets the width condition for MM when 7r+7(6rc)3/2+1≤M.7r + 7\Bigl(\frac{6r}{c}\Bigr)^{3/2} + 1 \le M.(6)

The Claim

Theorem 1. Let n≥1n \ge 1, let MM be a natural number, and let b∈𝔽Vb \in \mathbb{F}^V be a charge such that A‾b\bar A_b has at least one atom. Let JJ be a finite set whose size r=|J|r = |J| meets the width condition (6), let ee be an injection of JJ into the names of CMC^M, and let aa and a′a' be JJ-tuples of atoms of A‾b\bar A_b with tpe(a)=tpe(a′)\mathrm{tp}_e(a) = \mathrm{tp}_e(a'). Then ∃k∈K:k⋅aj=aj′ for all j∈J,\exists k \in K\colon\ k \cdot a_j = a'_j \text{ for all } j \in J,(7)✦ and ∃k∈𝔽E:∂k=0 and aj→kaj′ for all j∈J.\exists k \in \mathbb{F}^E\colon\ \partial k = 0 \text{ and } a_j \xrightarrow{k} a'_j \text{ for all } j \in J.(8)✦ For empty JJ, any two JJ-tuples aa and a′a' of atoms of A‾b\bar A_b satisfy ∃k∈K:k⋅aj=aj′ for all j∈J=∅\exists k \in K\colon\ k \cdot a_j = a'_j \text{ for all } j \in J = \emptyset(9)✦ for every nn and every charge bb, with no other hypothesis. For every natural number RR that meets the width condition, A‾b is K-homogeneous through R in CM.\bar A_b \text{ is $K$-homogeneous through $R$ in } C^M.(10)✦

In the paper, the result reads: if r≥1r \ge 1 satisfies 7r+7(6r/c)3/2+1≤M7r + 7(6r/c)^{3/2} + 1 \le M and two rr-tuples in the same A‾b\bar A_b have equal CMC^M-types, then some k∈Kk \in K maps the first tuple to the second, and for empty tuples the statement holds without any width hypothesis.

What Is Checked

The claim is stated over the analysis structure A‾b\bar A_b of a charge bb on the grid of side n+1n + 1 and its atoms, the counting types (4) of tuples of atoms placed at the names of CMC^M, the central flow group KK acting on the atoms, the atom shift, the width condition (6) and homogeneity (5).

About these constructions, the library proves that the boundary map (2) is linear, so that ker⁡∂\ker \partial is a subspace of 𝔽E\mathbb{F}^E, and that the shift by an edge vector tt keeps a local state at vv compatible and raises its divergence by (∂t)(v)(\partial t)(v).