OctoInformBeta

OpenAI preprint, September 2026 · §9. Adaptive fingerprints within budget blocks · §9

Lemma 9.9 [Restoring equality test]: For x,y≤Px, y \le P and a proper register triple, a reversible update leaves the middle register unchanged exactly when x=yx = y, and four probes read this off

An equality test that restores its catalyst register.

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 catalytic small-space computation has, besides its work tape, a large register whose initial contents are arbitrary and which it must hand back unchanged. A recurring task inside such a computation is to decide whether two numbers xx and yy, each at most a fixed bound PP, are equal, when the two can be produced only one at a time.

Here the catalyst is a triple of registers, and the test updates it in four additive steps, each of which involves only one of the two numbers. The question is whether such an update can detect the equality x=yx = y and still be undone.

Registers, Steps and Probes

Fix a natural number PP, the peak. The bit length lb⁡(m)\operatorname{lb}(m) of a natural number mm is ⌊log⁡2m⌋+1\lfloor \log_2 m \rfloor + 1 when m≥1m \ge 1 and 11 when m=0m = 0.✦ The kk-th digit db(a,k)d_b(a,k) of a natural number aa in base bb is ⌊a/bk⌋mod⁡b\lfloor a/b^k \rfloor \bmod b✦, and bit ii of a natural number WW is W[i]=d2(W,i)W[i] = d_2(W,i). The peak determines the parameters B=lb⁡(P),e=lb⁡(B),n=2e,L=⌊B/e⌋+1,M=n4.B = \operatorname{lb}(P), \qquad e = \operatorname{lb}(B), \qquad n = 2^e, \qquad L = \lfloor B/e \rfloor + 1, \qquad M = n^4.(1)

A proper triple v=(R,Z,W)v = (R, Z, W) is a triple of natural numbers with R<ML,Z<M,W<2n.R < M^L, \qquad Z < M, \qquad W < 2^n.(2)✦ Its entries are the three registers of the catalyst: RR is read through its LL digits in base MM as a vector in (ℤ/M)L(\mathbb{Z}/M)^L, ZZ as a residue modulo MM with four digits in base nn, and WW as a string of nn bits.

A number xx enters through its first LL digits in base nn. The digit inner product of numbers xx and yy and the mixed inner product of a register RR with yy are ⟨x,y⟩=∑i<Ldn(x,i)dn(y,i),⟨R,y⟩M=∑i<LdM(R,i)dn(y,i).\langle x, y \rangle = \sum_{i<L} d_n(x,i)\, d_n(y,i), \qquad \langle R, y \rangle_M = \sum_{i<L} d_M(R,i)\, d_n(y,i).(3) For a sign s∈{1,−1}s \in \{1, -1\}, the shifted register R+sxR +_s x is the number below MLM^L obtained by adding ss times the digits of xx to those of RR, digit by digit modulo MM: R+sx=∑i<L((dM(R,i)+sdn(x,i))mod⁡M)Mi.R +_s x = \sum_{i<L} \bigl( (d_M(R,i) + s\, d_n(x,i)) \bmod M \bigr)\, M^i.(4)✦

For a sign ss and natural numbers xx and yy, the four steps S1,xsS^s_{1,x}, S2,ysS^s_{2,y}, S3,xsS^s_{3,x} and S4,ysS^s_{4,y} are the maps on proper triples S1,xs(R,Z,W)=(R+sx,Z+s⟨x,x⟩,W),S2,ys(R,Z,W)=(R,Z+s⟨y,y⟩−2s⟨R,y⟩M,W),S3,xs(R,Z,W)=(R+−sx,Z,W),S4,ys(R,Z,W)=(R,Z+2s⟨R,y⟩M,W),\begin{aligned} S^s_{1,x}(R,Z,W) &= \bigl(R +_s x,\ Z + s\langle x,x\rangle,\ W\bigr),\\ S^s_{2,y}(R,Z,W) &= \bigl(R,\ Z + s\langle y,y\rangle - 2s\langle R,y\rangle_M,\ W\bigr),\\ S^s_{3,x}(R,Z,W) &= \bigl(R +_{-s} x,\ Z,\ W\bigr),\\ S^s_{4,y}(R,Z,W) &= \bigl(R,\ Z + 2s\langle R,y\rangle_M,\ W\bigr), \end{aligned}(5) with the middle entry reduced modulo MM. Writing ++ and −- for the signs 11 and −1-1, the forward map Φx,y\Phi_{x,y} and the backward map Ψx,y\Psi_{x,y} of numbers xx and yy are the maps on triples Φx,y=S4,y+∘S3,x+∘S2,y+∘S1,x+,Ψx,y=S1,x−∘S2,y−∘S3,x−∘S4,y−.\Phi_{x,y} = S^{+}_{4,y} \circ S^{+}_{3,x} \circ S^{+}_{2,y} \circ S^{+}_{1,x}, \qquad \Psi_{x,y} = S^{-}_{1,x} \circ S^{-}_{2,y} \circ S^{-}_{3,x} \circ S^{-}_{4,y}.(6)

For a natural number WW and a position ii, the flipped number W(i)W^{(i)} is the number below 2n2^n whose bit kk, for each k<nk < n, is W[k]W[k] when k≠ik \ne i and 1−W[i]1 - W[i] when k=ik = i. For j<4j < 4, the probe qjq_j sends a triple to the bit of WW at the position given by digit jj of ZZ in base nn✦, and the flip φj\varphi_j is the map on triples that changes that bit: qj(R,Z,W)=W[dn(Z,j)],φj(R,Z,W)=(R,Z,W(dn(Z,j))).q_j(R,Z,W) = W\bigl[d_n(Z,j)\bigr], \qquad \varphi_j(R,Z,W) = \bigl(R,\ Z,\ W^{(d_n(Z,j))}\bigr).(7)✦

The Claim

Theorem 1 (Restoring equality test). Let PP be a natural number with the parameters nn, LL and MM of (1), let v=(R,Z,W)v = (R, Z, W) be a proper triple, and let xx and yy be natural numbers. Then Ψx,y(Φx,y(v))=v.\Psi_{x,y}\bigl(\Phi_{x,y}(v)\bigr) = v.(8)✦ If moreover x≤Px \le P and y≤Py \le P, and Z′Z' is the middle entry of Φx,y(v)\Phi_{x,y}(v), then Z′=Z⇔x=y,Z' = Z \iff x = y,(9)✦ and x=y⇔(qj(Φx,y(φj(v)))≠qj(Φx,y(v)) for every j<4).x = y \iff \Bigl( q_j\bigl(\Phi_{x,y}(\varphi_j(v))\bigr) \ne q_j\bigl(\Phi_{x,y}(v)\bigr) \text{ for every } j < 4 \Bigr).(10)✦

In the paper, the result reads: if a shared bit vector VV has arbitrary initial contents, and excursions to two deterministically specified endpoints u1u_1 and u2u_2 return the cursor, with path and result independent of VV and with nested procedures restoring VV, then a procedure adds the indicator 𝟏k(u1)=k(u2)\mathbf{1}_{k(u_1) = k(u_2)} to a local bit modulo 22, restores VV, and needs only constant local data across four endpoint excursions, where k(u1)k(u_1) and k(u2)k(u_2) are the numbers written xx and yy here.

What Is Checked

The claims (8), (9) and (10) are stated over a peak PP with the parameters (1), a proper triple (2), natural numbers xx and yy, at most PP in (9) and (10), the forward and backward maps (6) built from the four steps (5) with the inner products (3) and the shifted register (4), and the probes and flips (7).