OctoInformBeta

OpenAI preprint, September 2026 · §6. Encoding complete choiceless computations

Lemma 21: For relations of arity at most mm, uniform definability in CmC^m survives ∃\exists, exact counting and bounded Härtig quantifiers

Program formulas translate into counting logic with mm names.

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

Lower bounds for choiceless polynomial time with counting (CPT) are proved through the counting logic CmC^m, first-order logic with equality, existential and exact counting quantifiers and mm variable names: a computation whose answer is given by a sentence of CmC^m answers alike on any two structures that CmC^m does not distinguish. Encoding the complete run of a choiceless computation in this way substitutes the formulas of the program into one another, and the number of names the result needs has to stay bounded.

This item bounds that number for interpretation programs, whose formulas are in first-order logic with the Härtig quantifier (FO+H), and it counts names through the relations that a fixed palette of names x0,…,xm−1x_0,\dots,x_{m-1} can define, wherever their arguments are placed on it.

Counting Logic and Definability

A binary relational structure 𝔇\mathfrak D over a vocabulary σ\sigma is a set DD, its universe, with a binary relation r𝔇r^{\mathfrak D} on DD for each symbol r∈σr\in\sigma.✦ The formulas of CmC^m over σ\sigma are built from ⊥\bot, the equations xj=xlx_j=x_l and the atoms r(xj,xl)r(x_j,x_l) with r∈σr\in\sigma and j,l<mj,l<m, by negation, conjunction, the existential quantifier ∃xj\exists x_j and, for each k∈ℕk\in\mathbb N, the counting quantifier ∃=kxj\exists^{=k}x_j.✦ The free variables of a formula of CmC^m are the names that occur in it outside the scope of a quantifier binding them.✦ Satisfaction 𝔇⊨φ[v]\mathfrak D\models\varphi[v] of a formula φ\varphi of CmC^m under an assignment vv of elements of DD to the names is defined as usual, with ∃=kxjφ\exists^{=k}x_j\,\varphi true when exactly kk elements a∈Da\in D satisfy φ\varphi under vv changed to send xjx_j to aa.✦

An nn-ary relation PP on the universe DD of 𝔇\mathfrak D is definable with mm names if for every map α:{0,…,n−1}→{0,…,m−1}\alpha\colon\{0,\dots,n-1\}\to\{0,\dots,m-1\}, injective or not, there is a formula φα\varphi_\alpha of CmC^m over σ\sigma, with free variables among xα(0),…,xα(n−1)x_{\alpha(0)},\dots,x_{\alpha(n-1)}, such that 𝔇⊨φα[v]⇔P(v(xα(0)),…,v(xα(n−1)))for every assignment v of elements of D to x0,…,xm−1.\mathfrak D\models\varphi_\alpha[v]\iff P\bigl(v(x_{\alpha(0)}),\dots,v(x_{\alpha(n-1)})\bigr) \quad\text{for every assignment } v \text{ of elements of } D \text{ to } x_0,\dots,x_{m-1}.(1)✦ A family (Pi)i∈I(P_i)_{i\in I} of nn-ary relations, each PiP_i on the universe DiD_i of a binary relational structure 𝔇i\mathfrak D_i over σ\sigma, is uniformly definable with mm names if for every map α:{0,…,n−1}→{0,…,m−1}\alpha\colon\{0,\dots,n-1\}\to\{0,\dots,m-1\} there is one formula φα\varphi_\alpha of CmC^m, with free variables among xα(0),…,xα(n−1)x_{\alpha(0)},\dots,x_{\alpha(n-1)}, that satisfies (1) in every 𝔇i\mathfrak D_i with PiP_i in place of PP.✦

Härtig Logic, Width and Programs

A finite structure 𝔄\mathfrak A over a set RR of binary relation symbols is a finite set V(𝔄)V(\mathfrak A), its universe, with a binary relation r𝔄r^{\mathfrak A} on it for each r∈Rr\in R.✦ The formulas of FO+H over RR in nn variables x1,…,xnx_1,\dots,x_n are generated from ⊥\bot, the equations xj=xlx_j=x_l and the atoms r(xj,xl)r(x_j,x_l) with r∈Rr\in R by negation and conjunction, and by ∃yφ\exists y\,\varphi and the Härtig quantification 𝖧y(φ,ψ)\mathsf Hy\,(\varphi,\psi) for formulas φ\varphi and ψ\psi in the n+1n+1 variables y,x1,…,xny,x_1,\dots,x_n.✦ Satisfaction 𝔄⊨φ[a‾]\mathfrak A\models\varphi[\bar a] of a formula φ\varphi of FO+H in nn variables at a tuple a‾∈V(𝔄)n\bar a\in V(\mathfrak A)^n is defined as usual, with 𝖧y(φ,ψ)\mathsf Hy\,(\varphi,\psi) true at a‾\bar a when as many elements b∈V(𝔄)b\in V(\mathfrak A) satisfy φ[b,a‾]\varphi[b,\bar a] as satisfy ψ[b,a‾]\psi[b,\bar a].✦

The scoped width sw⁡(φ)\operatorname{sw}(\varphi) of a formula φ\varphi of FO+H is the largest number of variables in scope at an atomic subformula of φ\varphi, with ⊥\bot counted as atomic: sw⁡(θ)=nfor θ=⊥,xj=xl,r(xj,xl) in n variables,sw⁡(¬φ)=sw⁡(∃yφ)=sw⁡(φ),sw⁡(φ∧ψ)=sw⁡(𝖧y(φ,ψ))=max⁡{sw⁡(φ),sw⁡(ψ)}.\begin{aligned} \operatorname{sw}(\theta)&=n\quad\text{for } \theta=\bot,\ x_j=x_l,\ r(x_j,x_l) \text{ in } n \text{ variables},\\ \operatorname{sw}(\neg\varphi)&=\operatorname{sw}(\exists y\,\varphi)=\operatorname{sw}(\varphi),\\ \operatorname{sw}(\varphi\wedge\psi)&=\operatorname{sw}(\mathsf Hy\,(\varphi,\psi)) =\max\{\operatorname{sw}(\varphi),\operatorname{sw}(\psi)\}. \end{aligned}(2)✦

Let RR and TT be sets of binary relation symbols. A two-dimensional interpretation ℐ\mathcal I of structures over TT in structures over RR is a family of formulas of FO+H over RR: a domain formula δ(x1,x2)\delta(x_1,x_2) in two variables and, with x‾\bar x and y‾\bar y pairs of variables, an equivalence formula η(x‾,y‾)\eta(\bar x,\bar y) in four variables and, for each t∈Tt\in T, a relation formula ρt(x‾,y‾)\rho_t(\bar x,\bar y) in four variables.✦ An interpretation program Π\Pi over a set RR of binary relation symbols consists of a finite set SS of binary relation symbols, the state symbols, an interpretation ℐinit\mathcal I_{\mathrm{init}} of structures over SS in structures over RR, an interpretation ℐstep\mathcal I_{\mathrm{step}} of structures over SS in structures over SS, and two sentences of FO+H over SS, the halting condition ψhalt\psi_{\mathrm{halt}} and the output condition ψout\psi_{\mathrm{out}}.✦

The Claim

Theorem 1. Let (𝔇i)i∈I(\mathfrak D_i)_{i\in I} be a family of binary relational structures over σ\sigma with universes DiD_i.

  1. Let n<mn<m be natural numbers, and suppose the family of (n+1)(n+1)-ary relations PiP_i on DiD_i is uniformly definable with mm names. Then so is the family of nn-ary relations {a‾∈Din:Pi(x,a‾) for some x∈Di},\bigl\{\bar a\in D_i^n : P_i(x,\bar a)\text{ for some } x\in D_i\bigr\},(3)✦ and so, for each k∈ℕk\in\mathbb N, is the family {a‾∈Din:|{x∈Di:Pi(x,a‾)}|=k}.\bigl\{\bar a\in D_i^n : |\{x\in D_i : P_i(x,\bar a)\}|=k\bigr\}.(4)✦

  2. Let n<mn<m be natural numbers, and suppose the families of (n+1)(n+1)-ary relations PiP_i and QiQ_i on DiD_i are uniformly definable with mm names. Then for each bound B∈ℕB\in\mathbb N so is the family of tuples at which the two counts agree and are at most BB, the bounded Härtig comparison, {a‾∈Din:|{x∈Di:Pi(x,a‾)}|=|{x∈Di:Qi(x,a‾)}|≤B}.\bigl\{\bar a\in D_i^n : |\{x\in D_i : P_i(x,\bar a)\}| =|\{x\in D_i : Q_i(x,\bar a)\}|\le B\bigr\}.(5)✦

  3. Let mm and nn be natural numbers, let 𝔄i\mathfrak A_i, for i∈Ii\in I, be finite structures over RR with maps ei:V(𝔄i)→Die_i\colon V(\mathfrak A_i)\to D_i, and let φ\varphi be a formula of FO+H over RR in nn variables with sw⁡(φ)<m\operatorname{sw}(\varphi)<m. Then there is a family of nn-ary relations QiQ_i on DiD_i, uniformly definable with mm names, such that for every i∈Ii\in I and all a1,…,an∈V(𝔄i)a_1,\dots,a_n\in V(\mathfrak A_i) Qi(ei(a1),…,ei(an))⇔𝔄i⊨φ[a1,…,an].Q_i\bigl(e_i(a_1),\dots,e_i(a_n)\bigr)\iff\mathfrak A_i\models\varphi[a_1,\dots,a_n].(6)✦

  4. For every interpretation program Π\Pi, with state symbols SS, there is a natural number m≥6m\ge 6 such that sw⁡(ψ)<mfor ψ=δ,η,ρt(t∈S) of ℐinit and of ℐstep, and for ψ=ψhalt,ψout.\operatorname{sw}(\psi)<m\quad\text{for } \psi=\delta,\ \eta,\ \rho_t\ (t\in S) \text{ of } \mathcal I_{\mathrm{init}} \text{ and of } \mathcal I_{\mathrm{step}}, \text{ and for } \psi=\psi_{\mathrm{halt}},\ \psi_{\mathrm{out}}.(7)✦

In the paper, the result reads: substituting formulas of free-variable measure fw\mathrm{fw} at most ww into a relational formula TT, without capture, gives a formula of measure at most max⁡{fw(T),w}\max\{\mathrm{fw}(T),w\}, and a formula of measure at most ww can be renamed to use at most w+1w+1 variable names.

The box states this in semantic form, with definability with mm names in place of a count of the names a formula uses.

What Is Checked

The claims are stated over binary relational structures and the counting logic CmC^m on them, with its free variables, its satisfaction and definability with mm names in plain and uniform form, and over finite structures, the logic FO+H with its satisfaction, scoped width, two-dimensional interpretations and interpretation programs.