OctoInformBeta

OpenAI preprint, September 2026 · §4. Counting equivalence and homogeneity

Lemma 10: A nonempty set RR of at most half the vertices has at least c|R|2/3c\lvert R\rvert^{2/3} boundary edges, where c=1−2−1/3c = 1 - 2^{-1/3}

An isoperimetric inequality for the cubic grid.

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 structures behind the lower bound for choiceless polynomial time with counting (CPT) are built over the cubic grid of side LL. The question is isoperimetric. When a set RR of vertices holds at most half of the grid, how few edges can join RR to its complement? The bound is the grid analogue of the isoperimetric inequality in space, with an explicit constant.

The library states this bound and, beside it, two counting facts about the projections of a finite set of triples onto pairs of coordinates.

The Grid and Its Edge Boundary

A 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\}, and the vertex set V={0,…,L−1}3V = \{0,\dots,L-1\}^3(1)✦ has L3L^3 elements.

An edge along xx of the grid is the unit segment joining a vertex (i,j,k)(i,j,k) with i≤L−2i \le L-2 to (i+1,j,k)(i+1,j,k).✦ Edges along yy and along zz are defined likewise, joining (i,j,k)(i,j,k) to (i,j+1,k)(i,j+1,k) with j≤L−2j \le L-2, or to (i,j,k+1)(i,j,k+1) with k≤L−2k \le L-2. Write ExE_x, EyE_y and EzE_z for the three families. The edge set EE of the grid is their disjoint union, E=Ex⊔Ey⊔Ez.E = E_x \sqcup E_y \sqcup E_z .(2)✦

The tail t(e)t(e) of a grid edge ee is the vertex at its lower end✦, and its head h(e)h(e) is the vertex at its upper end: the tail with the coordinate in the direction of ee raised by one.✦

The edge boundary ∂R\partial R of a set RR of vertices is the set of grid edges with exactly one endpoint in RR, ∂R={e∈E:|{t(e),h(e)}∩R|=1}.\partial R = \{\, e \in E : \lvert \{t(e), h(e)\} \cap R \rvert = 1 \,\}.(3)✦

The box isoperimetric constant cc is the real number c=1−2−1/3.c = 1 - 2^{-1/3}.(4)✦

Projections of a Set of Triples

Let S1S_1, S2S_2, S3S_3 be sets. For a subset RR of S1×S2×S3S_1 \times S_2 \times S_3, the projection π12(R)\pi_{12}(R) of RR onto the first two coordinates is the subset of S1×S2S_1 \times S_2 π12(R)={(s1,s2):(s1,s2,s3)∈R for some s3∈S3},\pi_{12}(R) = \{\, (s_1, s_2) : (s_1, s_2, s_3) \in R \text{ for some } s_3 \in S_3 \,\},(5) and the projections π13(R)\pi_{13}(R) onto the first and third coordinates and π23(R)\pi_{23}(R) onto the last two are defined likewise.

The Claim

Theorem 1. Let L≥1L \ge 1, and let RR be a nonempty set of vertices of the cubic grid of side LL with |R|≤L3/2\lvert R \rvert \le L^3/2. Then c|R|2/3≤|∂R|.c \, \lvert R \rvert^{2/3} \le \lvert \partial R \rvert .(6)✦

Theorem 2 (Loomis-Whitney inequality). Let S1S_1, S2S_2, S3S_3 be sets and RR a finite subset of S1×S2×S3S_1 \times S_2 \times S_3. Then |R|2≤|π12(R)||π13(R)||π23(R)|.\lvert R \rvert^2 \le \lvert \pi_{12}(R) \rvert \, \lvert \pi_{13}(R) \rvert \, \lvert \pi_{23}(R) \rvert .(7)✦

Theorem 3. Let L≥1L \ge 1, and let RR be a set of vertices of the cubic grid of side LL. Then each of the three projections of RR satisfies |πij(R)|≤|R|L+|∂R|,ij∈{12,13,23}.\lvert \pi_{ij}(R) \rvert \le \frac{\lvert R \rvert}{L} + \lvert \partial R \rvert , \qquad ij \in \{12, 13, 23\}.(8)✦

What Is Checked

The inequalities (6) and (8) are stated over the cubic grid of side LL: its vertex set VV, its edges along the three axes with their tails and heads, and the edge boundary ∂R\partial R defined from them, with (6) also over the constant cc of (4). The inequality (7) is stated over an arbitrary finite set of triples and its three projections.