The exact query cost of a prepared equality interface

4 October 2026. Research note. Written proof with independent review.

Can equality and disequality constraints store a Boolean matrix so that later pins activate a vector and one short query tests any row? This would make a familiar matrix lower-bound argument available for native equality recognition. Under a broad, explicit formula interface, the answer has an exact minimum: a row needs one query equation for each distinct selected column pattern.

Preparation may use arbitrarily many auxiliary variables and arbitrarily much work. The bound concerns the query that remains necessary after that preparation. It is a statement about this formula interface, rather than about every possible scaffolding representation.

The interface

Fix a Boolean matrix $M\in\{0,1\}^{m\times n}$ and distinct input variables $X_1,\ldots,X_n$. Prepare any satisfiable 2-affine formula $F_M$: a conjunction of unary pins $x=c$ and binary equations $x\oplus y=c$, with $c\in\{0,1\}$. Arbitrary auxiliary variables are permitted.

An arriving vector $v$ activates exactly its 1-coordinates:

$$A_v=\bigwedge_{j:v_j=1}T(X_j).$$

Require $F_M\land A_v$ to be satisfiable for every $v$. A query $Q_i$, chosen from $M$ and row $i$ but independently of $v$, may contain arbitrary further unary/binary equations and fresh variables. Correctness means

$$F_M\land A_v\land Q_i\text{ is inconsistent} \quad\Longleftrightarrow\quad \bigvee_j(M_{ij}\land v_j)=1$$

for every vector $v$.

Let

$$\kappa_i=\left|\{M_{*,j}:M_{ij}=1\}\right|,$$

the number of distinct full column vectors having a 1 in row $i$. Query atoms are counted as individual unary pins or binary parity equations. One higher-arity relation record that abbreviates several equations would be a different unit of cost.

Minimum-query theorem. Every valid interface has at least $\kappa_i$ atoms in $Q_i$. One equality-only preparation attains that bound simultaneously for every row.

Why preparation cannot merge different column patterns

A satisfiable 2-affine formula consists of signed connected components: inside a component every variable equals a chosen representative or its complement, and a component may also be pinned to a constant.

Since the all-ones activation must extend, any two input variables in the same old component have the same sign. No input is forced false. An input already forced true can only have an all-zero matrix column, since activating it would never change satisfiability.

Set $v=0$. Correctness says $F_M\land Q_i$ is satisfiable. Then the singleton activation $v=e_j$ gives

$$M_{ij}=1\quad\Longleftrightarrow\quad (F_M\land Q_i)\models X_j=0.$$

Input variables in the same old component have the same sign and are forced false together by every query. They must therefore have identical columns of $M$. Every distinct column counted by $\kappa_i$ supplies a different old component that is initially unforced and must become anchored to zero after $Q_i$.

This conclusion holds regardless of how many other variables or aliases were placed in those components during preparation.

Anchoring the components costs at least one atom each

Contract each connected component of $F_M$ to one vertex. Include one constant vertex and contract already pinned components into it, retaining the appropriate signs. Fresh query variables are additional vertices. A binary query equation contributes at most one edge between vertices, and a unary query pin contributes one edge to the constant vertex.

The all-zero activation guarantees that $F_M\land Q_i$ stays consistent. Thus a target old component becomes forced precisely by connection to the constant vertex. A connected graph joining $k$ previously unforced target vertices to an anchor needs at least $k$ edges. Consequently

$$|Q_i|\ge\kappa_i.$$

Connecting targets together first does not circumvent the bound: joining $k$ separate targets takes at least $k-1$ edges, and reaching an anchor needs another. Fresh variables can subdivide or join these routes but cannot reduce that minimum. Redundant equations and inconsistent cycles supply no shortcut, since the zero activation must be accepted.

A matching construction

Partition the input indices by identical column vectors of $M$. During preparation, equate all $X_j$ in each block, with no pins. This accepts every activation. For a row $i$, choose one representative $Z_c$ from each column class with $c_i=1$ and use

$$Q_i=\bigwedge_{c:c_i=1}F(Z_c).$$

There are exactly $\kappa_i$ atoms. The query is inconsistent exactly when some activated coordinate lies in one of those blocks, which is the required Boolean row product.

This construction uses at most $n-1$ preparation equations and no fresh query variables. For fixed-width names of $d=\lceil\log_2(n+1)\rceil$ symbols, preparation has $O(n\log(n+2))$ encoded length and the row query has exactly $\kappa_i(d+4)$ characters. The case $\kappa_i=0$ uses the empty query.

Literal names impose a representation-independent encoding cost within this interface

Every target old component must be incident to a query edge. Hence $Q_i$ must mention at least one old variable from each of $\kappa_i$ distinct components. Those mentions use distinct literal binary names. There are only $2^{r+1}-2$ nonempty binary names of length at most $r$, so the sum of the lengths of $\kappa$ distinct names is $\Omega(\kappa\log(\kappa+2))$. Therefore

$$N(Q_i)=\Omega\!\left(\kappa_i\log(\kappa_i+2)\right).$$

Arbitrarily many prepared aliases cannot give all those separate components constant-length names. With a common $d$-bit naming convention the bound is also $\Omega(\kappa_i d)$. This is unavoidable input length after preparation; it is not an extra lower bound on processing an already supplied query.

For example, let $M$ have an all-ones row followed by the $n$ identity rows. All its columns are distinct. The first row query requires at least $n$ atoms and $\Omega(n\log n)$ symbols, whatever the preparation size. This prevents the $O(\log n)$ row-query budget needed by the previous serialized matrix reductions.

As a smaller consequence, one final unary pin can represent a family of nonempty row supports exactly when those supports are pairwise identical or disjoint. Crossing supports such as $\{1,2\}$ and $\{2,3\}$ cannot both be isolated that way. The matching construction equates variables within each disjoint block.

What this resolves, and what it leaves open

The theorem retires the entire prepare/positive-activate/short-query formula architecture, including arbitrary signed auxiliaries, aliases and query joins. It does not show that native equality recognition is impossible. A different representation, activation contract or obstruction mechanism could behave differently.

Snapshots do not remove this bottleneck. Saving an already processed prefix and extending it is different from cheaply conjoining two independently prepared formulas. A row-star formula and a vector-pin formula could answer a row query if such a cheap join were available; native prefix snapshots do not supply that join.

Likewise, the lower bound in Henzinger–Wu’s fully retroactive graph work, §3 pp8–9, changes earlier updates and uses graph deletions. Their insertion-only historical variant has a polylogarithmic algorithm in §4, Theorem 5. Neither contract becomes a native equality-language lower bound merely through immutable history.

The signed-component description is standard linear algebra. The additional result here is the exact optimum for this activation/query contract, its matching construction and its encoded-name consequence. The proof was independently audited with arbitrary auxiliary components and query connections allowed. It supports the propagation and replay investigation by identifying a precise structural limit of its matrix route. The live question is still whether a native scaffold can maintain and read the current equality component during the arrival of an ordinary variable name.