OctoInformBeta

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

Proposition 8: For L≥2L \ge 2, objects of HF(Ab)\mathrm{HF}(A_b) with HH-orbit of at most NqN^q elements are KK-supported by ⌈2L(qlog⁡3N)2⌉\lceil 2L(q\log_3 N)^2\rceil atoms

Objects with small orbits are supported by few atoms.

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 computes with hereditarily finite objects over the atoms of its input, and a group acting on the atoms moves each such object along its orbit. The inputs here are the grid structures AbA_b, one for each charge bb on the vertices of the cubic grid of side LL with values in 𝔽3\mathbb{F}_3, and the group acting is the box group HH, which contains the group KK of flows on the grid as a central subgroup. The question is how the size of an object’s orbit under HH bounds its supports under KK: if the orbit has at most NqN^q elements, for a positive integer NN and a real number q≥0q \ge 0, how few atoms can be chosen so that every flow fixing them fixes the object?

The Grid

Fix n≥0n \ge 0 and let L=n+1L = n+1. Scalars lie in the field 𝔽=𝔽3\mathbb{F} = \mathbb{F}_3 of integers modulo 33.✦ A grid vertex 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.✦

A grid edge is a unit segment between grid vertices parallel to a coordinate axis, given by its lower endpoint: 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), the edge ey(i,j,k)e_y(i,j,k) along yy to (i,j+1,k)(i,j+1,k) and the edge ez(i,j,k)e_z(i,j,k) along zz to (i,j,k+1)(i,j,k+1).✦ In each family the coordinate along the edge ranges over {0,…,L−2}\{0,\dots,L-2\} and the other two over {0,…,L−1}\{0,\dots,L-1\}, and the edge set EE is the disjoint union of the three families.✦ The tail t(e)t(e) of an edge is the endpoint it starts from✦ and its head h(e)h(e) the endpoint it ends at.✦ A vertex vv is incident to ee when it is the head or the tail of ee✦, and the edges at vv are the edges incident to it.✦ The orientation sign ε(v,e)∈𝔽\varepsilon(v,e) \in \mathbb{F} is 11 if v=h(e)v = h(e), −1-1 if v=t(e)v = t(e) and 00 otherwise.✦

A grid face is a unit square parallel to a coordinate plane, given by its lowest corner (i,j,k)(i,j,k): a face in the xyxy plane has the opposite corner (i+1,j+1,k)(i+1,j+1,k), one in the xzxz plane (i+1,j,k+1)(i+1,j,k+1) and one in the yzyz plane (i,j+1,k+1)(i,j+1,k+1), the two coordinates that move ranging over {0,…,L−2}\{0,\dots,L-2\} and the third over {0,…,L−1}\{0,\dots,L-1\}.✦ The face set FF is the disjoint union of the three families.✦ The face cycle γf∈𝔽E\gamma_f \in \mathbb{F}^E of a face ff goes once around its boundary: it is +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=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)✦ where 1e∈𝔽E1_e \in \mathbb{F}^E is the indicator vector of ee; 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, and they form the set FeF_e.✦

The boundary map ∂:𝔽E→𝔽V\partial : \mathbb{F}^E \to \mathbb{F}^V is the linear map ∂z=∑e∈Ez(e)(1h(e)−1t(e)),\partial z = \sum_{e \in E} z(e)\,\bigl(1_{h(e)} - 1_{t(e)}\bigr),(2)✦ with 1v∈𝔽V1_v \in \mathbb{F}^V the indicator vector of a vertex vv. The flow space K=ker⁡∂K = \ker\partial is the subspace of flows, the edge labellings whose boundary vanishes at every vertex.✦ Read as flows, the face cycles give the map γ:F→K\gamma : F \to K, f↦γff \mapsto \gamma_f.✦

For labellings l,zl, z of a finite set II by 𝔽\mathbb{F}, the pairing is ⟨l,z⟩=∑i∈Il(i)z(i)\langle l, z\rangle = \sum_{i \in I} l(i)\,z(i), linear in zz✦, and the nonzero set of zz is supp⁡z={i∈I:z(i)≠0}\operatorname{supp} z = \{i \in I : z(i) \ne 0\}.✦ The curl of an edge labelling l∈𝔽El \in \mathbb{F}^E is the labelling of the faces by 𝔽\mathbb{F} (curl⁡l)(f)=∑e∈Eγf(e)l(e).(\operatorname{curl} l)(f) = \sum_{e \in E} \gamma_f(e)\,l(e).(3)✦

The Support Group

Let FF be any finite set of faces, KK any vector space of flows over 𝔽\mathbb{F} and γ:F→K\gamma : F \to K any map. The plane 𝔽2\mathbb{F}^2 carries the symplectic form ω(u,v)=u1v2−u2v1,\omega(u,v) = u_1 v_2 - u_2 v_1,(4) and CF=(𝔽2)FC_F = (\mathbb{F}^2)^F is the space of face labellings. The support group H(γ)H(\gamma) is the central extension of CFC_F by KK attached to γ\gamma: its elements are the pairs (a,k)(a,k) of a face labelling a∈CFa \in C_F and a flow k∈Kk \in K✦, and the central element of k∈Kk \in K is (0,k)(0,k).✦

For a weight w:F→𝔽w : F \to \mathbb{F}, the diagonal form βw\beta_w is the bilinear form on CFC_F given by βw(a,a′)=∑f∈Fw(f)ω(af,af′),\beta_w(a,a') = \sum_{f \in F} w(f)\,\omega(a_f, a'_f),(5)✦ and a subspace UU of CFC_F is isotropic for βw\beta_w when βw(a,a′)=0\beta_w(a,a') = 0 for all a,a′∈Ua, a' \in U. For a subgroup SS of H(γ)H(\gamma), the projection π(S)\pi(S) is the subspace of face labellings aa with (a,k)∈S(a,k) \in S for some kk✦, and the central part Z(S)Z(S) is the subspace of flows kk with (0,k)∈S(0,k) \in S.✦

The Box Group and the Atoms

The box group HH of the grid is the support group H(γ)H(\gamma) of the grid faces FF, the flow space K=ker⁡∂K = \ker\partial and the face cycles γ\gamma.✦ The central flow group of HH is the additive group of KK, and the central embedding of KK into HH is the map K→HK \to H, k↦(0,k)k \mapsto (0,k). For a subgroup SS of HH, the face codimension and the flow codimension are codim⁡FS=dim⁡CF−dim⁡π(S),codim⁡KS=dim⁡K−dim⁡Z(S).\operatorname{codim}_F S = \dim C_F - \dim \pi(S), \qquad \operatorname{codim}_K S = \dim K - \dim Z(S).(6)

The local group HeH_e of an edge ee is the support group H(γe)H(\gamma^e) of the faces FeF_e on ee, the flows 𝔽\mathbb{F} and the local cycle γe(f)=γf(e)\gamma^e(f) = \gamma_f(e), a nonzero scalar; its elements are the pairs (a,c)(a,c) of a labelling aa of FeF_e by points of 𝔽2\mathbb{F}^2 and a scalar flow cc.✦ A local state ss at a vertex vv assigns to each edge ee at vv an element se=(ae,ce)s_e = (a_e, c_e) of HeH_e.✦ A local state ss at vv is compatible when (ae)f=(ae′)f(a_e)_f = (a_{e'})_f for any two edges e,e′e, e' at vv and any face ff on both; the divergence div⁡s\operatorname{div} s of a local state ss at vv is the net flow into vv, div⁡s=∑e at vε(v,e)ce.\operatorname{div} s = \sum_{e \text{ at } v} \varepsilon(v,e)\,c_e.(7)

For a charge b∈𝔽Vb \in \mathbb{F}^V, a configuration at vv is a compatible local state at vv with divergence b(v)b(v).✦ The atoms of the grid structure AbA_b are of two disjoint sorts: the edge atoms, the pairs (e,g)(e,g) of an edge ee and an element g∈Heg \in H_e, and the configuration atoms, the pairs (v,s)(v,s) of a vertex vv and a configuration ss at vv.✦ The groups HH and KK act on the atoms of AbA_b.

Supports

The hereditarily finite objects over a set AA of atoms are the finite sets whose elements are atoms of AA or again such sets; they form the set HF(A)\mathrm{HF}(A).✦ Let a group GG act on AA, and so on HF(A)\mathrm{HF}(A). A tuple α=(α0,…,αs−1)\alpha = (\alpha_0,\dots,\alpha_{s-1}) of atoms is a GG-support of x∈HF(A)x \in \mathrm{HF}(A) when every g∈Gg \in G with gαi=αig\alpha_i = \alpha_i for all ii satisfies gx=xgx = x, and xx is ss-supported for the action of GG when some tuple of ss atoms is a GG-support of it.

The Claim

Theorem 1. Let b∈𝔽Vb \in \mathbb{F}^V be a charge, NN a positive integer and q≥0q \ge 0 a real number.

Let HH act on a set XX and let x∈Xx \in X have an HH-orbit of at most NqN^q elements. Then there is a set TT of edges with |T|≤2L(qlog⁡3N)2and(0,k)x=x for every flow k vanishing on T.|T| \le 2L\,(q\log_3 N)^2 \quad\text{and}\quad (0,k)\,x = x \text{ for every flow } k \text{ vanishing on } T.(8)✦ If L≥2L \ge 2 and x∈HF(Ab)x \in \mathrm{HF}(A_b) has an HH-orbit of at most NqN^q elements, then x is ⌈2L(qlog⁡3N)2⌉-supported for the action of K.x \text{ is } \lceil 2L\,(q\log_3 N)^2 \rceil\text{-supported for the action of } K.(9)✦ Let HH act on a set XX, let TT be a set of edges and let x∈Xx \in X satisfy (0,k)x=x(0,k)\,x = x for every flow kk vanishing on TT. Then there is a tuple α\alpha of |T||T| atoms of AbA_b with (0,k)x=xfor every k∈K with kαi=αi for all i.(0,k)\,x = x \quad\text{for every } k \in K \text{ with } k\alpha_i = \alpha_i \text{ for all } i.(10)✦

Every subgroup SS of HH has a set TT of edges with |T|≤Lcodim⁡FScodim⁡KSand(0,k)∈S for every flow k vanishing on T.|T| \le L\,\operatorname{codim}_F S\,\operatorname{codim}_K S \quad\text{and}\quad (0,k) \in S \text{ for every flow } k \text{ vanishing on } T.(11)✦ Let SS be a subgroup of HH and λ:K→𝔽\lambda : K \to \mathbb{F} a linear form vanishing on Z(S)Z(S). There is an edge labelling r∈𝔽Er \in \mathbb{F}^E with ⟨r,k⟩=λ(k) for all k∈Kand|supp⁡r|≤Lcodim⁡FS,\langle r, k\rangle = \lambda(k) \text{ for all } k \in K \quad\text{and}\quad |\operatorname{supp} r| \le L\,\operatorname{codim}_F S,(12)✦ and every l∈𝔽El \in \mathbb{F}^E with ⟨l,k⟩=λ(k)\langle l, k\rangle = \lambda(k) for all k∈Kk \in K satisfies |supp⁡(curl⁡l)|≤codim⁡FS.|\operatorname{supp}(\operatorname{curl} l)| \le \operatorname{codim}_F S.(13)✦

For any finite set FF, vector space KK and map γ:F→K\gamma : F \to K, let SS be a subgroup of H(γ)H(\gamma) and λ:K→𝔽\lambda : K \to \mathbb{F} a linear form vanishing on Z(S)Z(S). Then π(S)\pi(S) is isotropic for βλ∘γ\beta_{\lambda\circ\gamma}: ∑f∈Fλ(γ(f))ω(af,af′)=0for all a,a′∈π(S).\sum_{f \in F} \lambda(\gamma(f))\,\omega(a_f, a'_f) = 0 \quad\text{for all } a, a' \in \pi(S).(14)✦ For a weight w:F→𝔽w : F \to \mathbb{F}, every subspace UU of CFC_F isotropic for βw\beta_w satisfies |{f∈F:w(f)≠0}|≤dim⁡CF−dim⁡U.|\{f \in F : w(f) \ne 0\}| \le \dim C_F - \dim U.(15)✦ If KK is finite-dimensional, every subgroup SS of H(γ)H(\gamma) has index [H(γ):S]=3(dim⁡CF−dim⁡π(S))+(dim⁡K−dim⁡Z(S)).[H(\gamma) : S] = 3^{(\dim C_F - \dim \pi(S)) + (\dim K - \dim Z(S))}.(16)✦

In the paper, the result reads: for N=|Ab|N = |A_b|, a real q≥0q \ge 0 and x∈HF(Ab)x \in \mathrm{HF}(A_b) whose HH-orbit has at most NqN^q elements, xx has a KK-support of at most 2L(qlog⁡3N)22L(q\log_3 N)^2 edge atoms, possibly empty.

What Is Checked

The claim is stated over the support group H(γ)H(\gamma), with the projection and the central part of its subgroups and the forms ω\omega and βw\beta_w; over the grid of side LL, with its edges, faces, face cycles, boundary map, flows and curl; over the box group HH, the central embedding of KK and the codimensions of subgroups; and over the atoms of AbA_b and the supports of hereditarily finite objects built on them.

The library proves that every face cycle is a flow, ∂γf=0\partial\gamma_f = 0✦, and that the central embedding is a homomorphism, (0,k)(0,l)=(0,k+l)(0,k)(0,l) = (0,k+l). It proves too that the projection and the central part of a subgroup of H(γ)H(\gamma) contain zero and are closed under addition and negation.