OctoInformBeta

OpenAI preprint, September 2026 · §3. Small orbits have sparse supports · §3

The central extension H, its central flows K, and K-supports: In H=CF×KH = C_F \times K the flows K=ker⁡∂K = \ker\partial are central and contain all commutators; supports of hereditarily finite objects by tuples of atoms

The central extension by grid flows, and 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

Choiceless polynomial time with counting (CPT) computes with hereditarily finite objects over the atoms of its input structure, and its lower bounds are arguments about the supports of these objects under a group acting on the atoms.

The group of this item is built on the cubic grid of side L=n+1L = n+1, with chains over 𝔽3\mathbb{F}_3: it is a central extension HH, by the flows on the edges of the grid, of the group of labellings that put a point of the plane 𝔽32\mathbb{F}_3^2 on each face. Next to HH and its commutators, the item defines supports of objects under any group acting on atoms, with their hereditary form.

The Grid

A vertex of the grid of side L=n+1L = n+1 is a triple (i,j,k)(i,j,k) of integers in {0,…,L−1}\{0,\dots,L-1\}, and the vertex set VV has L3L^3 elements.✦ An edge of the grid is a unit segment between two vertices parallel to a coordinate axis: 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), while ey(i,j,k)e_y(i,j,k) and ez(i,j,k)e_z(i,j,k) run from (i,j,k)(i,j,k) to (i,j+1,k)(i,j+1,k) and to (i,j,k+1)(i,j,k+1).✦ The edge set EE is the disjoint union of these three families.✦ The tail t(e)t(e) of an edge ee is its lower end✦, and its head h(e)h(e) is its upper end.✦

A face of the grid is a unit square between vertices parallel to a coordinate plane, given by its lowest corner (i,j,k)(i,j,k); its opposite corner is (i+1,j+1,k)(i+1,j+1,k) in the xyxy plane, (i+1,j,k+1)(i+1,j,k+1) in the xzxz plane and (i,j+1,k+1)(i,j+1,k+1) in the yzyz plane.✦ The face set FF is the disjoint union of the three families.✦

An edge chain is a function z:E→𝔽3z \colon E \to \mathbb{F}_3, with values in the field 𝔽3\mathbb{F}_3 of integers modulo 33, and the edge chains form the vector space 𝔽3E\mathbb{F}_3^E; the vertex chains form 𝔽3V\mathbb{F}_3^V in the same way. The boundary map ∂\partial of the grid is the linear map from 𝔽3E\mathbb{F}_3^E to 𝔽3V\mathbb{F}_3^V given by ∂z=∑e∈Ez(e)(𝟏h(e)−𝟏t(e)),\partial z = \sum_{e \in E} z(e)\,\bigl(\mathbf{1}_{h(e)} - \mathbf{1}_{t(e)}\bigr),(1)✦ where 𝟏v\mathbf{1}_v is the indicator vector of the vertex vv, and 𝟏e\mathbf{1}_e that of an edge ee.

The face cycle γf\gamma_f of a face ff is the edge chain that goes once around the boundary of ff.✦ For the face ff 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)},(2)✦ and the faces in the xzxz and yzyz planes are traversed in the same way, with the axes x,yx, y replaced by x,zx, z and by y,zy, z.

Face Labellings and the Group HH

The plane 𝔽32\mathbb{F}_3^2 is the vector space of pairs u=(u1,u2)u = (u_1,u_2) of elements of 𝔽3\mathbb{F}_3, added and scaled coordinatewise.✦ The symplectic form ω\omega on 𝔽32\mathbb{F}_3^2 is ω(u,v)=u1v2−u2v1.\omega(u,v) = u_1 v_2 - u_2 v_1.(3)✦

Let FF be a finite set, such as the faces of the grid, KK a vector space over 𝔽3\mathbb{F}_3 whose elements are called flows, and γ:F→K\gamma \colon F \to K a map, with γf=γ(f)\gamma_f = \gamma(f). A face labelling is a map a:F→𝔽32a \colon F \to \mathbb{F}_3^2, with value afa_f at ff, and the face labellings form the group CF=(𝔽32)FC_F = (\mathbb{F}_3^2)^F under pointwise addition. The group HH attached to γ\gamma is a central extension of CFC_F by KK whose elements are the pairs (a,k)(a,k) of a face labelling aa and a flow kk.✦

Hereditarily Finite Objects

The set HF(A)\mathrm{HF}(A) of hereditarily finite objects over a set AA of atoms is the least set that contains the atoms and every finite set of its own elements.✦ The transitive closure tc⁡(x)\operatorname{tc}(x) of an object xx is the set of objects yy with y∈y1∈⋯∈yr=xy \in y_1 \in \cdots \in y_r = x for some r≥1r \ge 1.

A group GG acting on AA acts on HF(A)\mathrm{HF}(A) through the atoms. For an object xx of HF(A)\mathrm{HF}(A), the stabilizer GxG_x of xx in GG is the subgroup of GG of the elements that fix xx; for a tuple α=(α1,…,αm)\alpha = (\alpha_1,\dots,\alpha_m) of atoms, the pointwise stabilizer G(α)G_{(\alpha)} of α\alpha is the subgroup of GG of the elements that fix each αi\alpha_i.

The Claim

Definition 1. The flow space KK of the grid of side L=n+1L = n+1 is the space of edge chains with zero boundary: K=ker⁡∂={z∈𝔽3E:∂z=0}.K = \ker\partial = \{\, z \in \mathbb{F}_3^E : \partial z = 0 \,\}.(4)✦ Sending each face to its face cycle gives the flow cycle map of the grid, F→K,f↦γf.F \to K, \qquad f \mapsto \gamma_f.(5)✦ The box group of the grid is the group HH attached to the flow cycle map: H=CF×K,CF=(𝔽32)F,K=ker⁡∂.H = C_F \times K, \qquad C_F = (\mathbb{F}_3^2)^F, \quad K = \ker\partial.(6)✦ In the box group, as in the group HH attached to any map γ\gamma from a finite set FF to a vector space KK over 𝔽3\mathbb{F}_3, the central element of a flow kk is (0,k)(0,k).✦ It commutes with every element of HH, x(0,k)=(0,k)x(x∈H,k∈K),x\,(0,k) = (0,k)\,x \qquad (x \in H,\ k \in K),(7)✦ and the commutator of two elements x=(a,k)x = (a,k) and y=(a′,k′)y = (a',k') is a central element: xyx−1y−1=(0,∑f∈Fω(af,af′)γf).x y x^{-1} y^{-1} = \Bigl(0,\ \sum_{f \in F} \omega(a_f, a'_f)\,\gamma_f\Bigr).(8)✦ The central group of the grid is the flow space KK as a group, with the sum of flows as its product, k⋅l=k+l(k,l∈K),k \cdot l = k + l \qquad (k, l \in K),(9)✦ and the central embedding is the group homomorphism from the central group to the box group ι:K→H,ι(k)=(0,k).\iota \colon K \to H, \qquad \iota(k) = (0,k).(10)✦ Let a group GG act on a set AA of atoms. A tuple α\alpha of atoms supports an object x∈HF(A)x \in \mathrm{HF}(A) when its pointwise stabilizer fixes xx: G(α)⊆Gx.G_{(\alpha)} \subseteq G_x.(11)✦ For s∈ℕs \in \mathbb{N}, an object xx is ss-supported when some tuple of ss atoms, repetitions allowed, supports it, G(α)⊆Gxfor some α∈As,G_{(\alpha)} \subseteq G_x \quad \text{for some } \alpha \in A^s,(12)✦ and hereditarily ss-supported when xx and every object of its transitive closure are ss-supported: for every y∈{x}∪tc⁡(x) there is α∈As with G(α)⊆Gy.\text{for every } y \in \{x\} \cup \operatorname{tc}(x) \text{ there is } \alpha \in A^s \text{ with } G_{(\alpha)} \subseteq G_y.(13)✦

In the paper, the result reads: the group H=CF×KH = C_F \times K, with CF=(𝔽32)FC_F = (\mathbb{F}_3^2)^F, K=ker⁡∂K = \ker\partial and product (a,k)(a′,k′)=(a+a′,k+k′+B(a,a′))(a,k)(a',k') = (a+a', k+k'+B(a,a')) for a map B:CF×CF→KB \colon C_F \times C_F \to K, has as commutator of (a,k)(a,k) and (a′,k′)(a',k') the element (0,∑fω(af,af′)γf)(0, \sum_f \omega(a_f,a'_f)\,\gamma_f), the paper’s cfc^f being γf\gamma_f, and a tuple α\alpha of atoms is a KK-support of an object xx when every k∈Kk \in K fixing α\alpha fixes xx, the action on hereditarily finite objects being applied recursively to their elements.

For G=KG = K, the supports of (11) are the KK-supports.

What Is Checked

The definitions are stated over the grid of side L=n+1L = n+1 with its vertices, edges and faces, its boundary map ∂\partial and its face cycles γf\gamma_f over 𝔽3\mathbb{F}_3; over the plane 𝔽32\mathbb{F}_3^2 with the form ω\omega and the group HH attached to a map from a finite set to a vector space over 𝔽3\mathbb{F}_3; and, for supports, over a group acting on a set of atoms and the hereditarily finite objects over them.

The library proves ∂γf=0\partial\gamma_f = 0 for every face ff of the grid.✦