OctoInformBeta

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

Proposition 11: When the grid is large against MM, A‾b0\bar A_{b^0} and A‾b1\bar A_{b^1} satisfy the same CMC^M sentences and have equal empty-tuple types

On large grids no counting sentence separates the two charges.

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

A charge bb on the cubic grid of side L=n+1L = n + 1 is a vector b∈𝔽Vb \in \mathbb{F}^V indexed by the set VV of vertices of the grid, that is, a value in the field 𝔽=𝔽3\mathbb{F} = \mathbb{F}_3 of integers modulo 33 at each vertex. Each charge gives a finite structure A‾b\bar A_b, its analysis expansion, whose atoms sit on the edges and the vertices of the grid, the charge fixing the net flow at each vertex. Take the zero charge b0=0b^0 = 0 and the unit charge b1=1v*b^1 = 1_{v^*} at a single vertex v*v^*. The question is whether a sentence of the counting logic CMC^M, with MM variable names, can tell A‾b0\bar A_{b^0} from A‾b1\bar A_{b^1} when the grid is large against MM.

Counting Logic and Types

A binary relational structure SS over a vocabulary RR with universe AA interprets each symbol r∈Rr \in R as a binary relation rSr^S on AA.✦ The counting formulas over RR with variable names from a set II are built by φ::=⊥∣x=y∣r(x,y)∣¬φ∣φ∧ψ∣∃xφ∣∃=kxφ\varphi ::= \bot \mid x = y \mid r(x,y) \mid \neg\varphi \mid \varphi \wedge \psi \mid \exists x\,\varphi \mid \exists^{=k} x\,\varphi(1) with x,y∈Ix, y \in I, r∈Rr \in R and k∈ℕk \in \mathbb{N}, and CMC^M is the set of those whose names come from a fixed set of MM names. The free variables of a formula are the names that occur in it outside the scope of a quantifier binding them; a sentence is a formula without free variables.✦

Satisfaction S⊨φ[σ]S \models \varphi[\sigma] under an assignment σ:I→A\sigma \colon I \to A is the standard one, the counting quantifier holding when exactly kk elements witness it: S⊨∃=kxφ[σ]⇔|{a∈A:S⊨φ[σ[x↦a]]}|=k.S \models \exists^{=k} x\,\varphi\,[\sigma] \iff \bigl|\{a \in A : S \models \varphi[\sigma[x \mapsto a]]\}\bigr| = k.(2)✦

The type of an assignment σ\sigma in SS relative to a finite set PP of names is the set of formulas with free variables in PP that SS satisfies under σ\sigma, tp⁡SP(σ)={φ:free⁡(φ)⊆P,S⊨φ[σ]}.\operatorname{tp}^P_S(\sigma) = \{\varphi : \operatorname{free}(\varphi) \subseteq P,\ S \models \varphi[\sigma]\}.(3)✦ The counting type tp⁡S(a‾)\operatorname{tp}_S(\bar a) in SS of a tuple a‾=(aj)j∈J\bar a = (a_j)_{j \in J}, indexed by a set JJ with entries in a nonempty universe AA and placed at names by an injection ι:J→I\iota \colon J \to I, is the type, relative to the names ι(J)\iota(J) of the tuple, of the assignment that gives aja_j to ι(j)\iota(j) and a fixed default element of AA to every other name. The empty tuple has no names, and its counting type tp⁡S()\operatorname{tp}_S() is the set of sentences that SS satisfies.

The Grid

The vertex set of the grid is V={0,…,L−1}3V = \{0,\dots,L-1\}^3, with L3L^3 elements.✦ An edge is a unit segment parallel to an axis, given by its lower end: 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), and ey(i,j,k)e_y(i,j,k) and ez(i,j,k)e_z(i,j,k) run along yy and zz in the same way.✦ The tail of an edge is its lower end✦ and its head its upper end✦, and EE is the set of edges. A vertex vv is incident to an edge when it is its head or its tail✦, and the edges at vv are the edges incident to vv.✦ A face is a unit square parallel to the xyxy, xzxz or yzyz plane.✦

The boundary map ∂:𝔽E→𝔽V\partial \colon \mathbb{F}^E \to \mathbb{F}^V is the linear map ∂z=∑e∈Ez(e)(1head(e)−1tail(e)),\partial z = \sum_{e \in E} z(e)\,\bigl(1_{\mathrm{head}(e)} - 1_{\mathrm{tail}(e)}\bigr),(4)✦ and the orientation sign ε(v,e)∈𝔽\varepsilon(v,e) \in \mathbb{F} of a vertex vv and an edge ee is 11 if vv is the head of ee, −1-1 if vv is its tail, and 00 otherwise.✦

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 of ff crossed in their own direction, −1-1 on the other two, and 00 elsewhere.✦ 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 the local cycle of ee is the map from the faces on ee to 𝔽\mathbb{F} that sends each such face ff to γf(e)\gamma_f(e).

For a set TT of edges, the component CT(v)C_T(v) of a vertex vv off TT is its connected component in the graph on VV whose edges are the grid edges outside TT.✦ A vertex vv is giant off TT when this component holds more than half of the vertices: |V|<2|CT(v)|.|V| < 2\,|C_T(v)|.(5)✦

The giant bound for nn and MM is the inequality (12Mc)3/2<L3,c=1−2−1/3,\Bigl(\frac{12M}{c}\Bigr)^{3/2} < L^3, \qquad c = 1 - 2^{-1/3},(6)✦ where cc is the box isoperimetric constant.

Atoms and the Analysis Expansion

For a finite set FF of faces, a group KK of flows and a map γ:F→K\gamma \colon F \to K, the support group H=CF×KH = C_F \times K is the central extension of the group CFC_F of face labellings u:F→𝔽32u \colon F \to \mathbb{F}_3^2 by KK attached to γ\gamma✦, where the plane 𝔽32\mathbb{F}_3^2 is the set of pairs of scalars.✦ Its elements are the pairs (u,k)(u,k) of a face labelling and a flow, the flow of (u,k)(u,k) being kk✦, and the central element of k∈Kk \in K is (0,k)(0,k).✦ The local group HeH_e of an edge ee is the support group over the faces on ee, with flows in 𝔽\mathbb{F} and the local cycle of ee as γ\gamma.✦

A local state ss at a vertex vv is an assignment to each edge ee at vv of an element s(e)=(ue,ke)s(e) = (u_e,k_e) of HeH_e.✦ A local state ss at vv is compatible when ue(f)=ue′(f)u_e(f) = u_{e'}(f) for any two edges e,e′e, e' at vv and every face ff on both.✦ The divergence of a local state ss at vv is its net flow into vv, div⁡s=∑e∋vε(v,e)ke.\operatorname{div} s = \sum_{e \ni v} \varepsilon(v,e)\,k_e .(7)✦ For a charge bb, a configuration at vv for bb is a compatible local state at vv with divergence b(v)b(v).✦

The atoms of a charge bb are of two sorts: the edge atoms (e,h)(e,h), with ee an edge and h∈Heh \in H_e, which form the set YY, and the configuration atoms (v,s)(v,s), with ss a configuration at vv for bb, which form the set XX.✦ The atom relations of bb interpret the eight binary symbols of τ={Ed,Cf,EB,VB,I,Z0,Z1,Z2}\tau = \{\mathrm{Ed}, \mathrm{Cf}, \mathrm{EB}, \mathrm{VB}, I, Z_0, Z_1, Z_2\} on these atoms. Ed\mathrm{Ed} holds of each edge atom with itself and Cf\mathrm{Cf} of each configuration atom with itself; EB\mathrm{EB} relates any two edge atoms over the same edge and VB\mathrm{VB} any two configuration atoms over the same vertex; II relates (v,s)(v,s) to (e,s(e))(e,s(e)) for each edge ee at vv; and, for each δ∈𝔽\delta \in \mathbb{F}, ZδZ_\delta relates (e,h)(e,h) to (e,h′)(e,h') when h−1h′h^{-1}h' has flow δ\delta.✦

A face class label is a pair (e,u)(e,u) of an edge and a labelling uu of the faces on ee by points of 𝔽32\mathbb{F}_3^2, or a pair (v,(ue)e∋v)(v,(u_e)_{e \ni v}) of a vertex and such a labelling for each edge at vv.✦ The class label of an atom keeps its face data: (e,(u,k))(e,(u,k)) has the label (e,u)(e,u), and (v,s)(v,s) with s(e)=(ue,ke)s(e) = (u_e,k_e) has the label (v,(ue)e∋v)(v,(u_e)_{e \ni v}).✦ The class index ci⁡(x)\operatorname{ci}(x) of an atom xx is the position of its class label in a fixed enumeration of the face class labels.✦

The analysis signature consists of the symbols of τ\tau, a preorder symbol ≼\preceq and a raw symbol DδD_\delta for each δ∈𝔽\delta \in \mathbb{F}.✦ The analysis expansion A‾b\bar A_b of a charge bb is the binary relational structure over the analysis signature with the atoms of bb as universe that interprets each symbol of τ\tau by its atom relation and the other symbols by x≼y⇔ci⁡(x)≤ci⁡(y),Dδ((e,h),(e′,h′))⇔e=e′ and k′−k=δ,x \preceq y \iff \operatorname{ci}(x) \le \operatorname{ci}(y), \qquad D_\delta\bigl((e,h),(e',h')\bigr) \iff e = e' \text{ and } k' - k = \delta,(8)✦ where kk and k′k' are the flows of hh and h′h'; DδD_\delta holds of no pair other than a pair of edge atoms.

Shifts and Compatible Assignments

Fix charges bb and b′b' and an edge vector t∈𝔽Et \in \mathbb{F}^E. The shift of an element h∈Heh \in H_e by a scalar zz is (0,z)h(0,z)\,h, its product with the central element of zz✦, and the shift of a local state at vv by tt shifts its element at each edge ee by t(e)t(e).✦ At a vertex vv with (∂t)(v)=b′(v)−b(v)(\partial t)(v) = b'(v) - b(v), the shift sts^t of a configuration ss at vv for bb is the configuration at vv for b′b' whose local state is that of ss shifted by tt.✦ The atom shift by tt is the relation x→tx′x \to_t x' from atoms of bb to atoms of b′b' that holds between (e,h)(e,h) and (e,(0,t(e))h)(e,(0,t(e))\,h) for every edge atom, and between (v,s)(v,s) and (v,st)(v,s^t) for every configuration atom at a vertex vv with (∂t)(v)=b′(v)−b(v)(\partial t)(v) = b'(v) - b(v).✦

The block of an atom is the edge or the vertex it lies over✦, and the edges touched by an atom are those of its block: ee itself for an edge atom over ee, the edges at vv for a configuration atom over vv.✦ For a finite set PP of names and an assignment α\alpha of atoms to the names, TP(α)T_P(\alpha) is the set of edges touched by the atoms α(i)\alpha(i) with i∈Pi \in P.✦

A compatible assignment on a finite set PP of names is a pair (α,α′)(\alpha,\alpha') of assignments of atoms of bb and of atoms of b′b' to the names for which there are an edge vector t∈𝔽Et \in \mathbb{F}^E and a vertex ww with w giant off TP(α),∂t=b′−b−1w,α(i)→tα′(i) for every i∈P.w \text{ giant off } T_P(\alpha), \qquad \partial t = b' - b - 1_w, \qquad \alpha(i) \to_t \alpha'(i) \text{ for every } i \in P.(9)✦

The Claim

Theorem 1. Let n≥1n \ge 1 and MM be natural numbers satisfying the giant bound (6), let v*v^* be a vertex of the grid, and let b0=0b^0 = 0 and b1=1v*b^1 = 1_{v^*}. For every sentence φ\varphi of CMC^M over the analysis signature and all assignments α\alpha of atoms of b0b^0 and α′\alpha' of atoms of b1b^1 to the MM names, A‾b0⊨φ[α]⇔A‾b1⊨φ[α′].\bar A_{b^0} \models \varphi[\alpha] \iff \bar A_{b^1} \models \varphi[\alpha'].(10)✦ If the atoms of b0b^0 and the atoms of b1b^1 form nonempty sets, the empty tuple has the same counting type in the two expansions: tp⁡A‾b0()=tp⁡A‾b1().\operatorname{tp}_{\bar A_{b^0}}() = \operatorname{tp}_{\bar A_{b^1}}().(11)✦

In the paper, the result reads: for all sufficiently large LL, the expansions A‾b0\bar A_{b^0} and A‾b1\bar A_{b^1}, where b0=0b^0 = 0 and b1=1v*b^1 = 1_{v^*}, satisfy the same CMC^M sentences, the paper’s MM being ⌊L7/4⌋\lfloor L^{7/4} \rfloor.

What Is Checked

The claim is stated over the analysis expansions (8) of the charges 00 and 1v*1_{v^*} on the grid of side n+1n + 1, the sentences of CMC^M (1) with their satisfaction, the counting type (3) of the empty tuple, and the giant bound (6).

The library proves two further facts about these constructions. The first is defect transport. Let nn and MM satisfy the giant bound, let bb and b′b' be charges, let T⊆UT \subseteq U be sets of edges with |U|≤6M|U| \le 6M, and let t∈𝔽Et \in \mathbb{F}^E satisfy ∂t=b′−b−1w\partial t = b' - b - 1_w for a vertex ww, its defect, giant off TT in the sense of (5). Then there are an edge vector t′∈𝔽Et' \in \mathbb{F}^E and a vertex w′w' with w′ giant off U,∂t′=b′−b−1w′,t′(e)=t(e) for every e∈T.w' \text{ giant off } U, \qquad \partial t' = b' - b - 1_{w'}, \qquad t'(e) = t(e) \text{ for every } e \in T.(12)✦

The second carries truth along a system of partial bijections. Let SS and S′S' be binary relational structures over RR with universes AA and BB, and let ℰ\mathcal{E} be a set of triples (P,σ,σ′)(P,\sigma,\sigma') of a finite set PP of names in II and assignments σ:I→A\sigma \colon I \to A and σ′:I→B\sigma' \colon I \to B. Suppose that for each triple in ℰ\mathcal{E} the correspondence σ(i)↦σ′(i)\sigma(i) \mapsto \sigma'(i), i∈Pi \in P, is a partial isomorphism: σ(i)=σ(j)\sigma(i) = \sigma(j) exactly when σ′(i)=σ′(j)\sigma'(i) = \sigma'(j), and rS(σ(i),σ(j))r^S(\sigma(i),\sigma(j)) exactly when rS′(σ′(i),σ′(j))r^{S'}(\sigma'(i),\sigma'(j)), for all i,j∈Pi, j \in P and r∈Rr \in R. Suppose also that for each triple in ℰ\mathcal{E} and each name ii some bijection β:A→B\beta \colon A \to B puts (P∪{i},σ[i↦a],σ′[i↦β(a)])(P \cup \{i\}, \sigma[i \mapsto a], \sigma'[i \mapsto \beta(a)]) in ℰ\mathcal{E} for every a∈Aa \in A. Then for every triple (P,σ,σ′)(P,\sigma,\sigma') in ℰ\mathcal{E} and every formula φ\varphi over RR with names from II whose free variables lie in PP, S⊨φ[σ]⇔S′⊨φ[σ′].S \models \varphi[\sigma] \iff S' \models \varphi[\sigma'].(13)✦