Universal Diophantine equation

The equation is built up from ones whose solutions are set up to be integers that satisfy particular relations. So for example the equation a² + b²  0 has solutions that are exactly those integers that satisfy the relation a  0 ∧ b  0. Similarly, assuming as in the rest of this note that all variables are non-negative, b  a + c + 1 has solutions that are exactly those integers that satisfy a < b, with c having some allowed value. From various number-theoretical results many relations can readily be encoded as integer equations:

(a  0 ∨ b  0) ↔ a b  0

(a  0 ∧ b  0) ↔ a + b  0

a < b ↔ b  a + c + 1

a  Mod[b, c] ↔ (b  a + c d ∧ a < c)

a  Quotient[b, c] ↔ (b  a c + d ∧ d < c)

a  Binomial[b, c] ↔ With[{n = 2^b + 1}, (n + 1)^b  n^c(a + d n) + e ∧ e < n^c ∧ a < n]

a  b! ↔ a  Quotient[c^b, Binomial[c, b]]

a  GCD[b, c] ↔ (b c > 0 ∧ a d  b ∧ a e  c ∧ a + c f  b g)

a  Floor[b/c] ↔ (a c + d  b ∧ d < c)

PrimeQ[a] ↔ (GCD[(a - 1)!, a]  1 ∧ a > 1)

a  BitAnd[c, d] ∧ b  BitOr[c, d] ↔ (σ[c, a] ∧ σ[d, a] ∧ σ[b, c] ∧ σ[b, d] ∧ a + b  c + d)/. σ[x_, y_]  Mod[Binomial[x, y], 2]  1

where the last encoding uses the result on page 608. (Note that any variable a can be forced to be non-negative by including an equation a  w² + x² + y² + z², as on page 910.)

Given an integer a for which IntegerDigits[a, 2] gives the cell values for a cellular automaton, a single step of evolution according say to rule 30 is given by

BitXor[a, 2 BitOr[a, 2a]]

where (see page 871)

BitXor[x, y]  BitOr[x, y] - BitAnd[x, y]

and a is assumed to be padded with 0's at each end. The corresponding form for rule 110 is

BitXor[BitAnd[a, 2a, 4a], BitOr[2a, 4a]]

The final equation is then obtained from

{1 + x₄ + x₁₂  2^{(1 + x₃) (x₁ + 2 x₃)}, x₂ + x₁₃  2^x₁, 1 + x₅ + x₁₄  2^x₁, 2^x₃ x₅ + 2^{x₁ + 2 x₃} x₆ + 2^{x₁ + x₃} x₁₅ + x₁₆  x₄, 1 + x₁₅ + x₁₇  2^x₃, 1 + x₁₆ + x₁₈  2^x₃, 2^{1 + x₃ (1 + x₁ + 2 x₃)} (-1 + x₂) - x₁₀ + x₁₁  2 x₄, x₇  BitAnd[x₆, 2 x₆] ∧ x₈  BitOr[x₆, 2 x₆], x₉  BitAnd[x₆, 2 x₇] ∧ x₁₉  BitOr[x₆, 2 x₇], x₁₀  BitAnd[x₉, 2 x₈] ∧ x₁₁  BitOr[x₉, 2 x₈]}

where x₁ through x₄ have the meanings indicated in the main text, and satisfy x_i ≥ 0. Non-overlapping subsidiary variables are introduced for BitOr and BitAnd, yielding a total of 79 variables.

Note that it is potentially somewhat easier to construct Diophantine equations to emulate register machines—or arithmetic systems from page 673—than to emulate cellular automata, but exactly the same basic methods can be used.

In the universal equation in the main text variables appear in exponents. One can reduce such an exponential equation to a pure polynomial equation by encoding powers using integer equations. The simplest known way of doing this (see note below) involves a degree 8 equation with 60 variables:

a  b^c ↔ α[d, 4 + b e, 1 + z] ∧ α[f, e, 1 + z] ∧ a  Quotient[d, f] ∧ α[g, 4 + b, 1 + z] ∧ e  16 g(1 + z)

λ[a_, b_, c_] := Module[{x}, 2 a + x₁ c∧ (Mod[b - a, c]  0 ∨ Mod[b + a, c]  0)]

α[a_, b_, c_] := Module[{x}, x₁² - b x₁ x₂ + x₂²  1 ∧ x₃² - b x₃ x₄ + x₄²  1 ∧ 1 + x₄ + x₅  x₃ ∧ Mod[x₃, x₁²]  0 ∧ 2x₄ + x₇ b x₃ ∧ Mod[-b + x₈, x₇]  0 ∧ Mod[-2 + x₈, x₁]  0 ∧ x₈ - x₁₁  3 ∧ x₁₂² - x₈ x₁₂ x₁₃ + x₁₃²  1 ∧ 1 + 2 a + x₁₄  x₁ ∧ λ[a, x₁₂, x₇] ∧ λ[c, x₁₂, x₁]]

(This roughly uses the idea that solutions to Pell equations grow exponentially, so that for example x²  2y² + 1 has solutions With[{u = 3 + 2 √2}, (uⁿ + u^-n)/2].) From this representation of Power the universal equation can be converted to a purely polynomial equation with 2154 variables—which when expanded has 1683150 terms, total degree 16 (average per term 6.8), maximum coefficient 17827424 and LeafCount 16540206.

Note that the existence of universal Diophantine equations implies that any problem of mathematics—even, say, the Riemann Hypothesis—can in principle be formulated as a question about the existence of solutions to a Diophantine equation. It also means that given any specific enumeration of polynomials, there must be some universal polynomial u which if fed the enumeration number of a polynomial p, together with an encoding of the values of its variables, will yield the corresponding value of p as a solution to u  0.