OctoInformBeta

OpenAI preprint, September 2026 · §2. The grid structures

Proposition 5: The grid structure of zero charge satisfies QQ for every LL, and for L≥2L \ge 2 every grid structure satisfying it has total charge 00

For L≥2L \ge 2, QQ separates zero charge from a point charge.

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

The result that choiceless polynomial time with counting does not capture polynomial time turns on a separating query QQ, a query on finite structures over a vocabulary τ\tau of eight binary relations. It asks whether a system of linear equations over the field 𝔽3\mathbb{F}_3 of integers modulo 33, the field of scalars, has a solution, the unknowns being weights on the atoms of the structure. It is tested on grid structures: for a charge bb on the vertices of the cubic grid of side LL, the grid structure AbA_b has atoms of two sorts, attached to the edges and to the vertices of the grid. The question is how QQ answers on the zero charge and on a point charge, which is 11 at one vertex and 00 at all others.

The Grid

The cubic grid of side L=n+1L = n + 1 has the vertex set V={0,…,L−1}3V = \{0, \dots, L-1\}^3 of L3L^3 vertices.✦ A charge bb on the grid is a map b:V→𝔽3b : V \to \mathbb{F}_3, and the total charge of bb is the sum ∑v∈Vbv\sum_{v \in V} b_v.

The edges of the grid are the unit segments parallel to the axes. 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), for 0≤i≤L−20 \le i \le L-2 and 0≤j,k≤L−10 \le j, k \le L-1; 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 step in the second and in the third coordinate instead. The edge set EE is the disjoint union of these three families.✦ The tail of an edge is its lower endpoint (i,j,k)(i,j,k)✦, and its head is its upper endpoint✦. A vertex vv is incident to an edge ee when it is the head or the tail of ee✦, and E(v)E(v) is the set of edges at vv✦. The incidence ε(v,e)\varepsilon(v,e) of a vertex vv and an edge ee is the scalar 11 if vv is the head of ee, −1-1 if vv is its tail, and 00 otherwise.✦

The faces of the grid are the unit squares parallel to the coordinate planes, each given by its lowest corner: the face in the xyxy plane at (i,j,k)(i,j,k) has opposite corners (i,j,k)(i,j,k) and (i+1,j+1,k)(i+1,j+1,k), for 0≤i,j≤L−20 \le i, j \le L-2 and 0≤k≤L−10 \le k \le L-1✦, and the faces in the xzxz and yzyz planes are placed the same way; FF is the set of all faces. The face cycle γf:E→𝔽3\gamma_f : E \to \mathbb{F}_3 of a face ff goes once around its boundary. For the face in the xyxy plane at (i,j,k)(i,j,k), with 1e1_e the indicator of an edge ee, γf=1ex(i,j,k)+1ey(i+1,j,k)−1ex(i,j+1,k)−1ey(i,j,k),\gamma_f = 1_{e_x(i,j,k)} + 1_{e_y(i+1,j,k)} - 1_{e_x(i,j+1,k)} - 1_{e_y(i,j,k)},(1)✦ and the faces in the other two planes are traversed in the same way, with eze_z for their sides along zz. The set F(e)F(e) of faces on an edge ee is the set of faces ff with γf(e)≠0\gamma_f(e) \ne 0.✦ The local cycle of an edge ee is the map ρe:F(e)→𝔽3\rho_e : F(e) \to \mathbb{F}_3 sending ff to γf(e)\gamma_f(e).✦

Local Groups and Configurations

The plane 𝔽32\mathbb{F}_3^2 is the set of pairs of scalars, added and scaled coordinatewise.✦ Let Φ\Phi be a set of faces, KK a space whose elements are called flows, and γ:Φ→K\gamma : \Phi \to K a cycle map. The support group H=CΦ×KH = C_\Phi \times K is the central extension, attached to γ\gamma, of the group CΦC_\Phi of face labellings u:Φ→𝔽32u : \Phi \to \mathbb{F}_3^2 by KK.✦ The elements of the support group HH are the pairs h=(uh,κh)h = (u_h, \kappa_h) of a face labelling uhu_h and a flow κh\kappa_h. The local group HeH_e of an edge ee is the support group of its local cycle ρe\rho_e, with the faces F(e)F(e) and flows in 𝔽3\mathbb{F}_3.✦

A local state ss at a vertex vv is an assignment to each edge e∈E(v)e \in E(v) of an element ses_e of HeH_e.✦ A local state ss at vv is compatible when the elements it assigns to edges sharing a face agree on that face: use(f)=use′(f)for all e,e′∈E(v) and f∈F(e)∩F(e′).u_{s_e}(f) = u_{s_{e'}}(f) \quad \text{for all } e, e' \in E(v) \text{ and } f \in F(e) \cap F(e').(2)✦ The divergence divs\mathrm{div}\, s of a local state ss at vv is the scalar given by the net flow into vv, divs=∑e∈E(v)ε(v,e)κse.\mathrm{div}\, s = \sum_{e \in E(v)} \varepsilon(v,e)\, \kappa_{s_e}.(3) For a charge bb, a configuration at a vertex vv is a compatible local state ss at vv with divs=bv\mathrm{div}\, s = b_v.✦

The Grid Structure

The vocabulary τ\tau consists of the binary relation symbols Ed\mathrm{Ed}, Cf\mathrm{Cf}, EB\mathrm{EB}, VB\mathrm{VB}, II and ZδZ_\delta for each scalar δ\delta, eight in all.✦ A τ\tau-structure SS with universe UU interprets each symbol of τ\tau as a binary relation on UU.✦

The grid structure AbA_b of a charge bb is the τ\tau-structure whose universe is the disjoint union of two sorts of atoms: the edge atoms, the pairs (e,h)(e,h) of an edge ee and an element h∈Heh \in H_e, and the configuration atoms, the pairs (v,s)(v,s) of a vertex vv and a configuration ss at vv.✦ In AbA_b, 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.✦ The relation II joins a configuration atom (v,s)(v,s) to the edge atoms (e,se)(e,s_e) for e∈E(v)e \in E(v), and ZδZ_\delta joins edge atoms (e,h)(e,h) and (e,h′)(e,h') over the same edge exactly when h−1h′h^{-1}h' has flow δ\delta.

The Query

In a τ\tau-structure SS with universe UU, the edge atoms form the set Y={y∈U:Ed(y,y)}Y = \{y \in U : \mathrm{Ed}(y,y)\}✦ and the configuration atoms the set X={a∈U:Cf(a,a)}X = \{a \in U : \mathrm{Cf}(a,a)\}✦; for t∈Xt \in X, Xt={a∈X:VB(t,a)}X_t = \{a \in X : \mathrm{VB}(t,a)\}. A configuration atom tt and an edge atom yy are incident when there are a∈Xa \in X and x∈Yx \in Y with VB(t,a)\mathrm{VB}(t,a), I(a,x)I(a,x) and EB(y,x)\mathrm{EB}(y,x).✦ The coefficient c(y,a)c(y,a) of an edge atom y∈Yy \in Y at a configuration atom a∈Xa \in X is the scalar c(y,a)=∑x∈Y,I(a,x)∑δ∈𝔽3,Zδ(y,x)δ.c(y,a) = \sum_{x \in Y,\ I(a,x)} \ \sum_{\delta \in \mathbb{F}_3,\ Z_\delta(y,x)} \delta.(4)✦

Weights λ:X→𝔽3\lambda : X \to \mathbb{F}_3 are normalized when ∑a∈Xtλ(a)=1for every t∈X,\sum_{a \in X_t} \lambda(a) = 1 \quad \text{for every } t \in X,(5)✦ and weights λ:X→𝔽3\lambda : X \to \mathbb{F}_3 and μ:Y→𝔽3\mu : Y \to \mathbb{F}_3 are consistent when μ(y)=∑a∈Xtλ(a)c(y,a)for every t∈X and every y∈Y incident to t.\mu(y) = \sum_{a \in X_t} \lambda(a)\, c(y,a) \quad \text{for every } t \in X \text{ and every } y \in Y \text{ incident to } t.(6)✦ The separating query QQ holds of SS when there are weights λ\lambda on XX and μ\mu on YY such that λ\lambda is normalized and λ\lambda and μ\mu are consistent.✦

The Claim

Theorem 1. Let L=n+1L = n + 1 be the side of the cubic grid, let AbA_b be the grid structure of a charge bb, and let b0=0b^0 = 0 be the zero charge.

(i) If n≥1n \ge 1, v*v^* is a vertex and b1=1v*b^1 = 1_{v^*} is the point charge at v*v^*, then Ab0⊨QandAb1⊭Q.A_{b^0} \models Q \quad \text{and} \quad A_{b^1} \not\models Q.(7)✦

(ii) If n≥1n \ge 1 and AbA_b satisfies QQ, then ∑v∈Vbv=0.\sum_{v \in V} b_v = 0.(8)✦

(iii) For every nn, including n=0n = 0, Ab0⊨Q.A_{b^0} \models Q.(9)✦

What Is Checked

The three statements are made over the grid structures AbA_b of charges bb on the cubic grid of side L=n+1L = n + 1, built from the local groups HeH_e of the edges and the configurations at the vertices, and over the separating query QQ, defined by normalized and consistent weights on the configuration atoms and edge atoms of a τ\tau-structure.