OctoInformBeta

OpenAI preprint, September 2026 · §6. Testing containment of binary digits

Proposition 6.1: The relation x≼yx \preceq y and the binary containment system, which reads (yx)\binom{y}{x} as a digit of (B+1)y(B+1)^y in base BB, are both single-fold

Containment of binary digits is a single-fold relation.

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

Binary containment is the relation ≼\preceq on ℕ\mathbb{N} that holds between xx and yy when, at every place i∈ℕi \in \mathbb{N}, the binary digit of xx is at most the binary digit of yy: x≼y⇔⌊x2i⌋mod⁡2≤⌊y2i⌋mod⁡2for every i∈ℕ.x \preceq y \iff \Bigl\lfloor \frac{x}{2^i} \Bigr\rfloor \bmod 2 \le \Bigl\lfloor \frac{y}{2^i} \Bigr\rfloor \bmod 2 \quad \text{for every } i \in \mathbb{N}.(1)✦ For example, 5=1012≼1112=75 = 101_2 \preceq 111_2 = 7, while 2=102⋠1012=52 = 10_2 \not\preceq 101_2 = 5. This is the masking relation of the Jones-Matiyasevich arithmetization of register machines.

The question is whether ≼\preceq, as a relation on ℕ2\mathbb{N}^2, is single-fold, that is, whether it has a Diophantine representation whose auxiliary unknowns are unique whenever they exist. Proposition 6.1 answers it with a system of exponential conditions on xx, yy and seven auxiliary unknowns, built on the binomial coefficient (yx)\binom{y}{x}.

Single-fold Representations

A single-fold representation of a relation RR on tuples of natural numbers is a polynomial P(a,w)P(a, w) with integer coefficients in the input variables aa and finitely many auxiliary variables ww, such that a∈R⇔P(a,w)=0 for some tuple w of natural numbers,a \in R \iff P(a, w) = 0 \text{ for some tuple } w \text{ of natural numbers},(2)✦ and such that, for each input tuple aa, any two auxiliary tuples ww and w′w' with P(a,w)=P(a,w′)=0P(a, w) = P(a, w') = 0 are equal. A relation is single-fold when it has a single-fold representation.✦

The Binary Containment System

The binary containment system of x,y∈ℕx, y \in \mathbb{N} is the following system of conditions on a tuple w=(B,H,N,s,d,r,t)∈ℕ7w = (B, H, N, s, d, r, t) \in \mathbb{N}^7: x≤y,B=2y+1,H=Bx,N=(B+1)y,N=sBH+dH+r,d<B,r<H,d=2t+1.\begin{gathered} x \le y, \qquad B = 2^{y+1}, \qquad H = B^x, \qquad N = (B+1)^y, \\ N = sBH + dH + r, \qquad d < B, \qquad r < H, \qquad d = 2t + 1. \end{gathered}(3)✦

The Claim

Theorem 1 (Proposition 6.1). The relation of binary containment, {(x,y)∈ℕ2:x≼y},\{(x, y) \in \mathbb{N}^2 : x \preceq y\},(4)✦ is single-fold. So is the relation on ℕ9\mathbb{N}^9 formed by the solutions of the binary containment system, $$\{(x, y, B, H, N, s, d, r, t) \in \mathbb{N}^9 : \eqref{eq:system} \text{ holds}\}.$$(5)✦

What Is Checked

The claim is stated over binary containment (1), the binary containment system (3) and single-fold representations (2).

The library also states two facts about the binomial coefficient (yx)\binom{y}{x}. For natural numbers x≤yx \le y and a natural number B>2yB > 2^y, (yx)\binom{y}{x} is a digit of (B+1)y(B+1)^y in base BB: ⌊(B+1)yBx⌋mod⁡B=(yx).\Bigl\lfloor \frac{(B+1)^y}{B^x} \Bigr\rfloor \bmod B = \binom{y}{x}.(6)✦ For all natural numbers xx and yy, the parity of (yx)\binom{y}{x} is given by Lucas’s theorem for the prime 22: (yx)≡1(mod⁡2)⇔x≼y.\binom{y}{x} \equiv 1 \pmod{2} \iff x \preceq y.(7)✦