OctoInformBeta

OpenAI preprint, September 2026 ยท ยง3. Small orbits have sparse supports

Lemma 7: On the grid of side LL, a labelling with nonzero curl on tt faces differs from a gradient on at most LtLt edges

An edge labelling with sparse curl is nearly a gradient.

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 proof that choiceless polynomial time with counting does not capture polynomial time works with grid structures AbA_b, built on the cubic grid of side LL from a charge bโˆˆ๐”ฝVb \in \mathbb{F}^V on its vertex set VV, over the field ๐”ฝ=๐”ฝ3\mathbb{F} = \mathbb{F}_3 of integers modulo 33. This lemma belongs to the step where small orbits are shown to have sparse supports, and it is linear algebra on the grid alone. Label the edges of the grid by elements of ๐”ฝ\mathbb{F}, and suppose that the signed sum of the labels around a face is nonzero for only tt faces: on how few edges must the labelling differ from the differences of a vertex function along the edges? The answer is a vertex function whose differences along the edges, subtracted from the labelling, leave a labelling that is nonzero on few edges, together with a bound on the number of those edges for an explicit choice of the vertex function.

The Grid

Fix the side Lโ‰ฅ1L \ge 1. A grid vertex of the cubic grid of side LL is a triple (i,j,k)(i,j,k) of integers in {0,โ€ฆ,Lโˆ’1}\{0,\dots,L-1\}, so that the vertex set VV has L3L^3 elements.โœฆ

A grid edge is a unit segment between two grid vertices, parallel to a coordinate axis and named 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), 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) from (i,j,k)(i,j,k) to (i,j+1,k)(i,j+1,k) and ez(i,j,k)e_z(i,j,k) from (i,j,k)(i,j,k) to (i,j,k+1)(i,j,k+1) are indexed in the same way, the coordinate that moves running up to Lโˆ’2L-2 and the other two up to Lโˆ’1L-1. The edge set EE is the disjoint union ExโŠ”EyโŠ”EzE_x \sqcup E_y \sqcup E_z of the three families.โœฆ The tail eโˆ’e^- of an edge ee is its lower endpointโœฆ, and its head e+e^+ is its upper endpoint, where the coordinate in the edgeโ€™s direction is replaced by its successor.โœฆ

A grid face is a unit square with its corners at grid vertices, parallel to a coordinate plane and named by its lowest corner.โœฆ The face fxy(i,j,k)f_{xy}(i,j,k) in the xyxy plane 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โœฆ; the faces fxz(i,j,k)f_{xz}(i,j,k) and fyz(i,j,k)f_{yz}(i,j,k) have (i,j,k)(i,j,k) opposite (i+1,j,k+1)(i+1,j,k+1) and (i,j+1,k+1)(i,j+1,k+1) respectively, the two coordinates that move running up to Lโˆ’2L-2 and the third up to Lโˆ’1L-1. The face set FF is the disjoint union FxyโŠ”FxzโŠ”FyzF_{xy} \sqcup F_{xz} \sqcup F_{yz}.โœฆ

Gradient and Curl

An edge labelling of the grid is a function โ„“:Eโ†’๐”ฝ\ell \colon E \to \mathbb{F}, an element of ๐”ฝE\mathbb{F}^E, and a vertex function is a function ฯ†:Vโ†’๐”ฝ\varphi \colon V \to \mathbb{F}. The gradient of a vertex function ฯ†\varphi is the edge labelling โˆ‚๐–ณฯ†\partial^{\mathsf T}\varphi given by (โˆ‚๐–ณฯ†)(e)=ฯ†(e+)โˆ’ฯ†(eโˆ’).(\partial^{\mathsf T}\varphi)(e) = \varphi(e^+) - \varphi(e^-).(1)โœฆ

The face cycle of a face ff is the edge labelling ฮณf\gamma_f that goes once around the boundary of ff: it is +1+1 on the two sides crossed in their own direction, โˆ’1-1 on the other two and 00 elsewhere.โœฆ For a face in the xyxy plane, with ๐Ÿe\mathbf{1}_e the indicator vector of the edge ee, ฮณfxy(i,j,k)=๐Ÿex(i,j,k)+๐Ÿey(i+1,j,k)โˆ’๐Ÿex(i,j+1,k)โˆ’๐Ÿey(i,j,k),\gamma_{f_{xy}(i,j,k)} = \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, the first axis of the plane taking the part of xx and the second the part of yy.

The curl of an edge labelling โ„“\ell is the function curl⁡โ„“โˆˆ๐”ฝF\operatorname{curl}\ell \in \mathbb{F}^F whose value at a face is the signed sum of โ„“\ell around it: (curl⁡โ„“)(f)=โˆ‘eโˆˆEฮณf(e)โ„“(e).(\operatorname{curl}\ell)(f) = \sum_{e \in E} \gamma_f(e)\,\ell(e).(3) The support supp⁡g\operatorname{supp} g of a function gg from a finite set into ๐”ฝ\mathbb{F} is the set of points at which gg is nonzero.โœฆ

Potentials and Residuals

For an edge labelling โ„“\ell and a coordinate i0โˆˆ{0,โ€ฆ,Lโˆ’1}i_0 \in \{0,\dots,L-1\}, the potentials ฯ†1,ฯ†2,ฯ†3โˆˆ๐”ฝV\varphi_1, \varphi_2, \varphi_3 \in \mathbb{F}^V of โ„“\ell at i0i_0 are prefix sums of labels along coordinate lines, and the residuals r1,r2,r3โˆˆ๐”ฝEr_1, r_2, r_3 \in \mathbb{F}^E are the edge labellings left by subtracting their gradients in turn: ฯ†1(i,j,k)=โˆ‘a<iโ„“(ex(a,j,k)),r1=โ„“โˆ’โˆ‚๐–ณฯ†1,ฯ†2(i,j,k)=โˆ‘b<jr1(ey(i0,b,k)),r2=r1โˆ’โˆ‚๐–ณฯ†2,ฯ†3(i,j,k)=โˆ‘c<kr2(ez(i0,0,c)),r3=r2โˆ’โˆ‚๐–ณฯ†3.\begin{aligned} \varphi_1(i,j,k) &= \textstyle\sum_{a<i} \ell(e_x(a,j,k)), & r_1 &= \ell - \partial^{\mathsf T}\varphi_1,\\ \varphi_2(i,j,k) &= \textstyle\sum_{b<j} r_1(e_y(i_0,b,k)), & r_2 &= r_1 - \partial^{\mathsf T}\varphi_2,\\ \varphi_3(i,j,k) &= \textstyle\sum_{c<k} r_2(e_z(i_0,0,c)), & r_3 &= r_2 - \partial^{\mathsf T}\varphi_3. \end{aligned}(4)

For an edge labelling โ„“\ell and a value i0โˆˆ{0,โ€ฆ,Lโˆ’1}i_0 \in \{0,\dots,L-1\} of the first coordinate, the set BxyB_{xy} of โ„“\ell consists of the faces in the xyxy plane at which curl⁡โ„“\operatorname{curl}\ell is nonzero, and the set BxzB_{xz} of โ„“\ell of those in the xzxz plane; the set Byz(i0)B_{yz}(i_0) of โ„“\ell consists of the pairs (j,k)(j,k) with 0โ‰คj,kโ‰คLโˆ’20 \le j,k \le L-2 for which the face fyz(i0,j,k)f_{yz}(i_0,j,k), in the plane x=i0x = i_0, has nonzero curl.

The Claim

Theorem 1. Let Lโ‰ฅ1L \ge 1, let โ„“โˆˆ๐”ฝE\ell \in \mathbb{F}^E be an edge labelling of the cubic grid of side LL, and let t=|supp⁡curl⁡โ„“|t = |\operatorname{supp}\operatorname{curl}\ell| be the number of faces at which its curl is nonzero. Then there is a vertex function ฯ†โˆˆ๐”ฝV\varphi \in \mathbb{F}^V with |supp⁡(โ„“โˆ’โˆ‚๐–ณฯ†)|โ‰คLt.|\operatorname{supp}(\ell - \partial^{\mathsf T}\varphi)| \le L\,t.(5)โœฆ Moreover, for every i0โˆˆ{0,โ€ฆ,Lโˆ’1}i_0 \in \{0,\dots,L-1\} the residual r3r_3 of โ„“\ell at i0i_0 satisfies |supp⁡r3|โ‰คL(|Bxy|+|Bxz|)+L2|Byz(i0)|.|\operatorname{supp} r_3| \le L\,\bigl(|B_{xy}| + |B_{xz}|\bigr) + L^2\,|B_{yz}(i_0)|.(6)โœฆ

In the paper, the result reads: if โ„“โˆˆ๐”ฝE\ell \in \mathbb{F}^E has nonzero curl on exactly tt faces of the Lร—Lร—LL \times L \times L box, there is a vertex function ฯ†\varphi such that โ„“โˆ’โˆ‚๐–ณฯ†\ell - \partial^{\mathsf T}\varphi is supported on at most 2Lt2Lt edges, and in particular โ„“\ell is a gradient when t=0t = 0.

What Is Checked

Both claims are stated over edge labellings of the cubic grid of side LL with values in ๐”ฝ3\mathbb{F}_3, through the gradient (1), the curl (3) taken against the face cycles (2) and the sizes of supports; (6) is stated in addition over the potentials and residuals (4) at i0i_0 and the sets BxyB_{xy}, BxzB_{xz} and Byz(i0)B_{yz}(i_0) of faces of nonzero curl.