OctoInformBeta

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

The box grid, face cycles and edge groups: The grid {0,…,n}3\{0,\dots,n\}^3 over 𝔽3\mathbb{F}_3, its boundary map with ∂cf=0\partial c^f=0, and the Heisenberg-type group PeP_e of each edge

The box grid, its face cycles and its edge groups.

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) is separated from polynomial time on grid structures AbA_b, one for each charge bb, a labelling of the vertex set VV of a three-dimensional box grid by elements of 𝔽=𝔽3\mathbb{F} = \mathbb{F}_3, that is, a vector b∈𝔽Vb \in \mathbb{F}^V. This page fixes the grid and the linear algebra over 𝔽\mathbb{F} beneath these structures: the boundary map with the signed cycles around the unit squares, and, for each edge ee, a group PeP_e of Heisenberg type built from the squares at ee and the symplectic form on 𝔽2\mathbb{F}^2.

The Box Grid

Fix a natural number nn, let L=n+1L = n+1, and let indices i,j,ki,j,k range over {0,…,n}\{0,\dots,n\}. The vertex set VV of the box grid of side LL is {0,…,n}3\{0,\dots,n\}^3.✦

An edge of the box grid is a unit step along one of the three coordinate axes, oriented in the increasing direction.✦ The edges eijkxe^x_{ijk} along xx have i<ni < n✦, the edges eijkye^y_{ijk} along yy have j<nj < n, the edges eijkze^z_{ijk} along zz have k<nk < n✦, and the edge set EE is the disjoint union of these three families.✦ Each edge ee runs from its tail e−e^- to its head e+e^+: (eijkx)−=(i,j,k),(eijkx)+=(i+1,j,k),(eijky)−=(i,j,k),(eijky)+=(i,j+1,k),(eijkz)−=(i,j,k),(eijkz)+=(i,j,k+1).\begin{aligned} (e^x_{ijk})^- &= (i,j,k), & (e^x_{ijk})^+ &= (i+1,j,k),\\ (e^y_{ijk})^- &= (i,j,k), & (e^y_{ijk})^+ &= (i,j+1,k),\\ (e^z_{ijk})^- &= (i,j,k), & (e^z_{ijk})^+ &= (i,j,k+1). \end{aligned}(1)

A face of the box grid is a unit square in one of the three coordinate planes, indexed by its corner with the smallest coordinates.✦ In the xyxy-plane the faces are the fijkxyf^{xy}_{ijk} with i,j<ni,j < n✦; in the xzxz-plane, the fijkxzf^{xz}_{ijk} with i,k<ni,k < n✦; in the yzyz-plane, the fijkyzf^{yz}_{ijk} with j,k<nj,k < n.✦ Together they form the face set FF.✦

A labelling of the edges is a vector w∈𝔽Ew \in \mathbb{F}^E with value wew_e at the edge ee, and 1e∈𝔽E1_e \in \mathbb{F}^E and 1v∈𝔽V1_v \in \mathbb{F}^V are the vectors that are 11 at ee, or at vv, and 00 elsewhere. The face cycle cf∈𝔽Ec^f \in \mathbb{F}^E of a face ff is the signed sum of the four sides of the square, taken once around it, with value cefc^f_e at ee: cfijkxy=1ei,j,kx+1ei+1,j,ky−1ei,j+1,kx−1ei,j,ky,cfijkxz=1ei,j,kx+1ei+1,j,kz−1ei,j,k+1x−1ei,j,kz,cfijkyz=1ei,j,ky+1ei,j+1,kz−1ei,j,k+1y−1ei,j,kz.\begin{aligned} c^{f^{xy}_{ijk}} &= 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}},\\ c^{f^{xz}_{ijk}} &= 1_{e^x_{i,j,k}} + 1_{e^z_{i+1,j,k}} - 1_{e^x_{i,j,k+1}} - 1_{e^z_{i,j,k}},\\ c^{f^{yz}_{ijk}} &= 1_{e^y_{i,j,k}} + 1_{e^z_{i,j+1,k}} - 1_{e^y_{i,j,k+1}} - 1_{e^z_{i,j,k}}. \end{aligned}(2)✦

The boundary map ∂:𝔽E→𝔽V\partial : \mathbb{F}^E \to \mathbb{F}^V is the linear map that sends each edge to its head minus its tail: ∂w=∑e∈Ewe(1e+−1e−).\partial w = \sum_{e \in E} w_e\,(1_{e^+} - 1_{e^-}).(3)✦

The Claim

Definition 1. Let nn be a natural number and consider the box grid of side n+1n+1. For every face ff, the face cycle cfc^f has boundary zero: ∂cf=0.\partial c^f = 0.(4)✦ The incidence sign of a vertex vv and an edge ee is the element εve=[e+=v]−[e−=v]\varepsilon_{ve} = [e^+ = v] - [e^- = v](5)✦ of 𝔽\mathbb{F}, where [P][P] is 11 when PP holds and 00 otherwise. The symplectic form ω\omega on the plane 𝔽2\mathbb{F}^2 is ω((a,b),(a′,b′))=ab′−ba′.\omega\bigl((a,b),(a',b')\bigr) = ab' - ba'.(6)✦ Let II be a finite set, KK a vector space over 𝔽\mathbb{F} and γ=(γf)f∈I\gamma = (\gamma_f)_{f \in I} a family in KK. The correction term of u,u′∈(𝔽2)Iu, u' \in (\mathbb{F}^2)^I is the vector κγ(u,u′)=2∑f∈Iω(uf,uf′)γf\kappa_\gamma(u,u') = 2 \sum_{f \in I} \omega(u_f, u'_f)\,\gamma_f(7)✦ of KK, and the group HγH_\gamma is the set (𝔽2)I×K(\mathbb{F}^2)^I \times K of pairs of a face part and a flow part, with the product (u,z)(u′,z′)=(u+u′,z+z′+κγ(u,u′)).(u,z)(u',z') = \bigl(u+u',\; z+z'+\kappa_\gamma(u,u')\bigr).(8)✦ For an edge ee of the grid, the set of faces at ee is F(e)={f∈F:cef≠0},F(e) = \{\, f \in F : c^f_e \neq 0 \,\},(9)✦ the local cycle of ee is the family (cef)f∈F(e)(c^f_e)_{f \in F(e)} in 𝔽\mathbb{F}✦, and the edge group PeP_e is the group HγH_\gamma of the local cycle, with I=F(e)I = F(e) and K=𝔽K = \mathbb{F}: Pe=H(cef)f∈F(e).P_e = H_{(c^f_e)_{f \in F(e)}}.(10)✦

In the paper, the result reads: the grid is G=(V,E)G = (V,E) with V={0,…,L−1}3V = \{0,\dots,L-1\}^3 and its edges oriented positively, ∂:𝔽E→𝔽V\partial : \mathbb{F}^E \to \mathbb{F}^V is its incidence map, the face cycles cfc^f satisfy ∂cf=0\partial c^f = 0, ω((a,b),(a′,b′))=ab′−ba′\omega((a,b),(a',b')) = ab' - ba', and the edge group PeP_e is (𝔽2)F(e)×𝔽(\mathbb{F}^2)^{F(e)} \times \mathbb{F} with (u,z)(u′,z′)=(u+u′,z+z′+12∑fcefω(uf,uf′))(u,z)(u',z') = \bigl(u+u',\, z+z'+\tfrac12\sum_f c^f_e\,\omega(u_f,u'_f)\bigr), where L=n+1L = n+1 and 12=2\tfrac12 = 2 in 𝔽\mathbb{F}.

What Is Checked

The definitions and the identity (4) are stated over the box grid of side n+1n+1 for every natural number nn, with its vertices, its edges along the three axes with their tails and heads, its faces in the three coordinate planes and the field 𝔽=𝔽3\mathbb{F} = \mathbb{F}_3, and the group HγH_\gamma over every finite set II, vector space KK over 𝔽\mathbb{F} and family γ\gamma in KK.