OctoInformBeta

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

The analysis expansion Ā_b and the counting logic C^h: A preorder from a fixed order of class labels and relations DδD_\delta expand AbA_b; the counting logic ChC^h defines types of tuples

The analysis expansion of the grid structure and counting types.

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

Let 𝔽=𝔽3\mathbb{F} = \mathbb{F}_3 and consider the cubic grid of side L=n+1L = n + 1, whose vertex set VV consists of the triples (i,j,k)(i,j,k) of integers with 0≤i,j,k≤L−10 \le i,j,k \le L - 1.✦ A charge b∈𝔽Vb \in \mathbb{F}^V gives the grid structure AbA_b, whose elements are atoms attached to the edges and to the vertices of the grid and whose relations interpret the vocabulary τ\tau of eight binary relation symbols. Its analysis expansion A‾b\bar A_b adds to AbA_b relations built from the face data and the flows of the atoms. Structures of this kind are compared in the counting logic ChC^h with hh variable names, through the types of tuples of atoms.

The Grid Structure

A grid edge is a unit segment between two vertices, parallel to a coordinate axis and oriented from its tail to its head, the end whose coordinate in the edge’s direction is the larger; EE is the set of edges.✦ The edges at a vertex vv, written e∋ve \ni v, are those with vv as head or tail✦, and the edge vertex incidence ε(v,e)∈𝔽\varepsilon(v,e) \in \mathbb{F} is 11 if vv is the head of ee, −1-1 if vv is its tail, and 00 otherwise.✦

A grid face is a unit square parallel to a coordinate plane, and FF is the set of faces.✦ The face cycle γf∈𝔽E\gamma_f \in \mathbb{F}^E of a face ff goes once around its boundary: it is 11 on the two sides 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) \neq 0, the squares having ee as a side; they form the set FeF_e.✦

The local group HeH_e of an edge ee is the central extension of the group of face labellings Fe→𝔽2F_e \to \mathbb{F}^2 by 𝔽\mathbb{F} attached to the local cycle f↦γf(e)f \mapsto \gamma_f(e) of ee.✦ Its elements are the pairs (u,z)(u,z) of a face labelling u:Fe→𝔽2u \colon F_e \to \mathbb{F}^2 and a flow z∈𝔽z \in \mathbb{F}.✦

A local state ss at a vertex vv assigns to each edge e∋ve \ni v an element s(e)=(ue,ze)s(e) = (u_e, z_e) of HeH_e.✦ A configuration at vv is a local state ss at vv that is compatible, in that ue(f)=ue′(f)u_e(f) = u_{e'}(f) for any two edges e,e′∋ve, e' \ni v and any face ff on both, and whose divergence is the charge at vv: ∑e∋vε(v,e)ze=b(v).\sum_{e \ni v} \varepsilon(v,e)\, z_e = b(v).(1)✦

The atoms of AbA_b are of two disjoint sorts: an edge atom (e,s)(e,s) is an edge ee with an element s∈Hes \in H_e, and a configuration atom (v,s)(v,s) is a vertex vv with a configuration ss at vv.✦ The relations of AbA_b interpret the 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\}. 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 on the same edge and VB\mathrm{VB} any two configuration atoms at the same vertex; II relates a configuration atom (v,s)(v,s) to the edge atom (e,s(e))(e,s(e)) for each edge e∋ve \ni v; and ZδZ_\delta, for δ∈𝔽\delta \in \mathbb{F}, relates edge atoms on one edge through the flow of a product in HeH_e: Zδ((e,s),(e,t))⇔the flow of s−1t is δ.Z_\delta\bigl((e,s),(e,t)\bigr) \iff \text{the flow of } s^{-1}t \text{ is } \delta.(2)✦

The Definition

Definition 1. For a vocabulary σ\sigma of binary relation symbols, a σ\sigma-structure SS is a set UU, its universe, with a binary relation rSr^S on UU for each r∈σr \in \sigma: S=(U,(rS)r∈σ),rS⊆U×U.S = \bigl(U, (r^S)_{r \in \sigma}\bigr), \qquad r^S \subseteq U \times U.(3)✦

A class label is a pair (e,u)(e,u) of an edge ee and a face labelling u:Fe→𝔽2u \colon F_e \to \mathbb{F}^2, or a pair (v,(ue)e∋v)(v,(u_e)_{e \ni v}) of a vertex vv and a face labelling ue:Fe→𝔽2u_e \colon F_e \to \mathbb{F}^2 for each edge e∋ve \ni v; the class labels form the finite set Θ=⨆e∈E(𝔽2)Fe⊔⨆v∈V∏e∋v(𝔽2)Fe.\Theta = \bigsqcup_{e \in E} (\mathbb{F}^2)^{F_e} \;\sqcup\; \bigsqcup_{v \in V} \prod_{e \ni v} (\mathbb{F}^2)^{F_e}.(4)✦ The class map cl\mathrm{cl} sends an atom of AbA_b to its class label in Θ\Theta, keeping its face labellings and forgetting its flows: cl(e,(u,z))=(e,u),cl(v,s)=(v,(ue)e∋v)where s(e)=(ue,ze).\mathrm{cl}(e,(u,z)) = (e,u), \qquad \mathrm{cl}(v,s) = (v,(u_e)_{e \ni v}) \quad \text{where } s(e) = (u_e, z_e).(5)✦

The analysis vocabulary τ‾\bar\tau adds to τ\tau a binary symbol ≼\preceq and a binary symbol DδD_\delta for each δ∈𝔽\delta \in \mathbb{F}: τ‾=τ⊔{≼}⊔{D0,D1,D2}.\bar\tau = \tau \sqcup \{\preceq\} \sqcup \{D_0, D_1, D_2\}.(6)✦ For δ∈𝔽\delta \in \mathbb{F}, the raw difference DδD_\delta is the binary relation on atoms that holds between two edge atoms on the same edge whose flows differ by δ\delta, and never holds of a pair with a configuration atom in it: Dδ((e,(u,z)),(e′,(u′,z′)))⇔e=e′ and z′−z=δ.D_\delta\bigl((e,(u,z)),(e',(u',z'))\bigr) \iff e = e' \text{ and } z' - z = \delta.(7)✦ Fix a bijection κ:Θ→{0,…,|Θ|−1}\kappa \colon \Theta \to \{0, \dots, |\Theta| - 1\}. The analysis expansion A‾b\bar A_b of AbA_b is the τ‾\bar\tau-structure on the atoms of AbA_b that interprets each symbol of τ\tau as AbA_b does, each DδD_\delta as in (7), and ≼\preceq as the total preorder x≼y⇔κ(cl(x))≤κ(cl(y)).x \preceq y \iff \kappa(\mathrm{cl}(x)) \le \kappa(\mathrm{cl}(y)).(8)✦

The counting formulas over σ\sigma with variable names from a set Λ\Lambda are generated by φ::=⊥∣x=y∣r(x,y)∣¬φ∣φ∧ψ∣∃xφ∣∃=axφ(x,y∈Λ,r∈σ,a∈ℕ).\varphi ::= \bot \mid x = y \mid r(x,y) \mid \neg\varphi \mid \varphi \wedge \psi \mid \exists x\, \varphi \mid \exists^{=a} x\, \varphi \qquad (x, y \in \Lambda,\ r \in \sigma,\ a \in \mathbb{N}).(9)✦ The counting logic ChC^h is the set of counting formulas over σ\sigma whose variable names come from a set Λ\Lambda with hh elements. The free names of a formula are given by free(⊥)=∅,free(x=y)=free(r(x,y))={x,y},free(¬φ)=free(φ),free(φ∧ψ)=free(φ)∪free(ψ),free(∃xφ)=free(∃=axφ)=free(φ)\{x}.\begin{gathered} \mathrm{free}(\bot) = \emptyset, \quad \mathrm{free}(x = y) = \mathrm{free}(r(x,y)) = \{x,y\}, \quad \mathrm{free}(\neg\varphi) = \mathrm{free}(\varphi), \\ \mathrm{free}(\varphi \wedge \psi) = \mathrm{free}(\varphi) \cup \mathrm{free}(\psi), \quad \mathrm{free}(\exists x\, \varphi) = \mathrm{free}(\exists^{=a} x\, \varphi) = \mathrm{free}(\varphi) \setminus \{x\}. \end{gathered}(10)✦ For an assignment α:Λ→U\alpha \colon \Lambda \to U, write α[x↦d]\alpha[x \mapsto d] for the assignment that sends xx to dd and agrees with α\alpha elsewhere. Satisfaction S⊨φ[α]S \models \varphi[\alpha] is defined by recursion on φ\varphi: ⊥\bot is never satisfied, ¬\neg and ∧\wedge are negation and conjunction, and S⊨x=y[α]⇔α(x)=α(y),S⊨r(x,y)[α]⇔(α(x),α(y))∈rS,S⊨∃xφ[α]⇔S⊨φ[α[x↦d]] for some d∈U,S⊨∃=axφ[α]⇔|{d∈U:S⊨φ[α[x↦d]]}|=a.\begin{aligned} S &\models x = y\,[\alpha] &&\iff \alpha(x) = \alpha(y), \\ S &\models r(x,y)\,[\alpha] &&\iff (\alpha(x), \alpha(y)) \in r^S, \\ S &\models \exists x\, \varphi\,[\alpha] &&\iff S \models \varphi[\alpha[x \mapsto d]] \text{ for some } d \in U, \\ S &\models \exists^{=a} x\, \varphi\,[\alpha] &&\iff \bigl|\{d \in U : S \models \varphi[\alpha[x \mapsto d]]\}\bigr| = a. \end{aligned}(11)✦

The type of an assignment α\alpha at a finite set W⊆ΛW \subseteq \Lambda of names is the set of formulas with free names in WW that SS satisfies under α\alpha: tpWS(α)={φ:free(φ)⊆W,S⊨φ[α]}.\mathrm{tp}^S_W(\alpha) = \{\varphi : \mathrm{free}(\varphi) \subseteq W,\ S \models \varphi[\alpha]\}.(12)✦ Let UU be nonempty, let c‾=(cj)j∈J\bar c = (c_j)_{j \in J} be a tuple in UU indexed by a set JJ and ι:J→Λ\iota \colon J \to \Lambda an injection placing its entries at names, and let αc‾\alpha_{\bar c} send ι(j)\iota(j) to cjc_j and every other name to a fixed element of UU. The type tpιS(c‾)\mathrm{tp}^S_\iota(\bar c) of c‾\bar c placed at ι\iota is the type of αc‾\alpha_{\bar c} at ι(J)\iota(J), a set of formulas: tpιS(c‾)=tpι(J)S(αc‾).\mathrm{tp}^S_\iota(\bar c) = \mathrm{tp}^S_{\iota(J)}(\alpha_{\bar c}).(13)✦

For a real number LL, the number M(L)M(L) of variable names is M(L)=⌊L7/4⌋.M(L) = \lfloor L^{7/4} \rfloor.(14)✦

In the paper, the result reads: A‾b\bar A_b adds to AbA_b the total preorder ≼\preceq coming from a fixed order of the classes (e,u)(e,u) and (v,(uf)f)(v,(u_f)_f), and the relations DδD_\delta between edge atoms on the same edge with z′−z=δz' - z = \delta, where zz and z′z' are the last coordinates of the two atoms; ChC^h is first-order logic with equality, ∃\exists and exact counting quantifiers ∃=a\exists^{=a} with at most hh variable names, with the ChC^h-types of tuples; and M=⌊L7/4⌋M = \lfloor L^{7/4} \rfloor.

What Is Checked

The definitions are stated over the grid structure AbA_b of a charge b∈𝔽Vb \in \mathbb{F}^V on the grid of side L=n+1L = n + 1, with its edge and configuration atoms, the local groups HeH_e and the relations of τ\tau, and, for the counting logic, over an arbitrary vocabulary of binary relation symbols and an arbitrary set of variable names.