The Setting
Binary containment is the relation on that holds between and when, at every place , the binary digit of is at most the binary digit of : (1)✦ For example, , while . This is the masking relation of the Jones-Matiyasevich arithmetization of register machines.
The question is whether , as a relation on , 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 , and seven auxiliary unknowns, built on the binomial coefficient .
Single-fold Representations
A single-fold representation of a relation on tuples of natural numbers is a polynomial with integer coefficients in the input variables and finitely many auxiliary variables , such that (2)✦ and such that, for each input tuple , any two auxiliary tuples and with are equal. A relation is single-fold when it has a single-fold representation.✦
The Binary Containment System
The binary containment system of is the following system of conditions on a tuple : (3)✦
The Claim
Theorem 1 (Proposition 6.1). The relation of binary containment, (4)✦ is single-fold. So is the relation on 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 . For natural numbers and a natural number , is a digit of in base : (6)✦ For all natural numbers and , the parity of is given by Lucas’s theorem for the prime : (7)✦