OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

The separating query Q: A structure over eight binary relations satisfies the separating query when normalized weights on configuration atoms and weights on edge atoms solve the consistency equations

The separating query asks for consistent weights over 𝔽3\mathbb{F}_3..

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 separating query QQ is the query used to show that choiceless polynomial time with counting does not capture polynomial time. It is a property of finite structures over a vocabulary of eight binary relations. Two kinds of element, edge atoms and configuration atoms, index the unknowns of a system of linear equations over the three-element field 𝔽3=ℤ/3ℤ\mathbb{F}_3 = \mathbb{Z}/3\mathbb{Z} whose coefficients are read off the relations, and QQ holds when that system has a solution.

Input Structures

The vocabulary τ\tau is the set of eight binary relation symbols τ={Ed,Cf,EB,VB,I,Z0,Z1,Z2},\tau = \{\mathrm{Ed}, \mathrm{Cf}, \mathrm{EB}, \mathrm{VB}, \mathrm{I}, \mathrm{Z}_0, \mathrm{Z}_1, \mathrm{Z}_2\},(1)✦ with one symbol Zδ\mathrm{Z}_\delta for each δ∈𝔽3\delta \in \mathbb{F}_3.

An input structure SS on a set AA is a τ\tau-structure with universe AA: it interprets each symbol R∈τR \in \tau as a binary relation RSR^S on AA, S=(A,(RS)R∈τ),RS⊆A×A.S = \bigl(A, (R^S)_{R \in \tau}\bigr), \qquad R^S \subseteq A \times A .(2)✦ With SS fixed, R(x,y)R(x,y) means (x,y)∈RS(x,y) \in R^S.

An isomorphism from an input structure SS on AA to an input structure TT on BB is a bijection π:A→B\pi \colon A \to B that preserves every relation of τ\tau in both directions: (πx,πy)∈RT⇔(x,y)∈RSfor all R∈τ and x,y∈A.(\pi x, \pi y) \in R^T \iff (x, y) \in R^S \qquad \text{for all } R \in \tau \text{ and } x, y \in A .(3)✦

The edge atoms of an input structure SS on AA are the elements that Ed\mathrm{Ed} relates to themselves, and its configuration atoms are those that Cf\mathrm{Cf} relates to themselves: Y={y∈A:Ed(y,y)},Y = \{\, y \in A : \mathrm{Ed}(y,y) \,\},(4)✦ X={a∈A:Cf(a,a)}.X = \{\, a \in A : \mathrm{Cf}(a,a) \,\}.(5)✦ For a configuration atom t∈Xt \in X we write Xt={a∈X:VB(t,a)}X_t = \{a \in X : \mathrm{VB}(t,a)\}.

For an input structure SS on a finite set AA, the coefficient of an edge atom y∈Yy \in Y at a configuration atom a∈Xa \in X is the element of 𝔽3\mathbb{F}_3 C(y,a)=∑x∈YI(a,x)∑δ∈𝔽3Zδ(y,x)δ.C(y,a) = \sum_{\substack{x \in Y \\ \mathrm{I}(a,x)}} \; \sum_{\substack{\delta \in \mathbb{F}_3 \\ \mathrm{Z}_\delta(y,x)}} \delta .(6)✦

A configuration atom t∈Xt \in X is incident to an edge atom y∈Yy \in Y if I(a,x) and EB(y,x)for some a∈Xt and some x∈Y.\mathrm{I}(a,x) \text{ and } \mathrm{EB}(y,x) \qquad \text{for some } a \in X_t \text{ and some } x \in Y .(7)✦

A weighting λ:X→𝔽3\lambda \colon X \to \mathbb{F}_3 of the configuration atoms is normalized if ∑a∈Xtλa=1for every t∈X.\sum_{a \in X_t} \lambda_a = 1 \qquad \text{for every } t \in X .(8)✦ A pair (λ,μ)(\lambda, \mu) of weightings λ:X→𝔽3\lambda \colon X \to \mathbb{F}_3 and μ:Y→𝔽3\mu \colon Y \to \mathbb{F}_3 is consistent if μy=∑a∈XtλaC(y,a)whenever t∈X is incident to y∈Y.\mu_y = \sum_{a \in X_t} \lambda_a \, C(y,a) \qquad \text{whenever } t \in X \text{ is incident to } y \in Y .(9)✦

The Definition

Definition 1. Let SS be an input structure on a finite set, with configuration atoms XX and edge atoms YY. The separating query QQ is the property of SS given by S⊨Q⇔some normalized λ:X→𝔽3 and some μ:Y→𝔽3 form a consistent pair.S \models Q \iff \text{some normalized } \lambda \colon X \to \mathbb{F}_3 \text{ and some } \mu \colon Y \to \mathbb{F}_3 \text{ form a consistent pair}.(10)✦

What Is Checked

The definition (10) is stated over input structures (2) on a finite set for the vocabulary τ\tau of (1), through their edge atoms (4), configuration atoms (5), coefficients (6) and incidence (7), and over the conditions (8) and (9) on weightings with values in 𝔽3\mathbb{F}_3.