Diophantine equation

A Diophantine equation is an equation of the form D(V) = 0, where D is a polynomial with integer coefficients and V is a tuple of variables.

Examples

Solutions to Diophantine equations must be integers. For the equation $x^{3}-2x=0$, $x=0$ is a Diophantine solution, but $x=\pm {\sqrt {2}}$ are not since they are not integers. In contrast, $5x-2=0$ has no integer solutions.

Some common Diophantine equations include:

• $a^{2}+b^{2}-c^{2}=0$ Pythagorean theorem (when considering triples)
• $a^{n}+b^{n}-c^{n}=0$ Fermat's last theorem
• $x^{2}-ay^{2}-1=0$ Pell's equation (constant $a$)

Diophantine sets

We can imagine splitting the variables of a Diophantine equation D into two rows, the parameters and the unknowns. The idea is to treat a Diophantine equation as a system that can be queried; when we assign some values to the parameters, what values can the unknowns have? Each solution of the equation corresponds to a tuple of unknowns.

Let D be a Diophantine equation split into parameters and unknowns. A set of tuples S is a Diophantine set when for every element s in S there exists a tuple of unknowns u such that s and u are a solution for D.

Any split is legal. Suppose D(V) is the polynomial of a Diophantine equation and V has three variables x, y, and z. Then there are eight legal splits corresponding to the eight subsets of V: the empty set, x, y, z, x and y, x and z, y and z, and the full row of all three variables.

We can imagine Diophantine equations as multi-valued partial functions where the parameters are inputs and the unknowns are outputs. If the corresponding Diophantine set is empty then the resulting partial function is not defined at any input.

As a model of computation

To use a parameterized Diophantine equation as a partial function, replace all occurrences of the parameterized variables with the arguments (turning them into constants). Then, enumerate every single combination of integers (or naturals) for the unknowns, trying all possible combinations. The following is a Python program which uses the Diophantine equation $(x+2)(y+2)-a=0$ to semidecide if the parameter is a composite number, and what a pair of its factors are if it is. Note that this semidecides the compositeness of the input, it halts for composites, and loops infinitely for primes.

def factorize(a):
    eq = lambda x, y: (x + 2) * (y + 2) - a
    x = 0
    y = 0
    while eq(x, y) != 0:
        if x == y:
            y += 1
            x = -1
        x += 1
    return x + 2, y + 2

It was shown by Matiyasevich, Robinson, Davis, and Putnam (MRDP) that parameterized Diophantine equations can model any recursively enumerable set. Since Turing machines and other Turing complete models of computation also model the recursively enumerable sets (and nothing more), parameterized Diophantine equations are Turing complete. This means that a generalized version of the program above, where an equation is run against an enumeration of every permutation of unknowns (even for just the natural numbers) is Turing complete.

Computational systems which can model recursively enumerable sets are able to model themselves or other Turing complete systems by creating a universal machine. A universal Diophantine equation was given by Jones. This equation has several reflected forms, meaning there are universal Diophantine equations based on this equation which trade number of degree and unknowns. Jones also provides a universal equation with 100 multiplication and addition operations.

Universal Diophantine equations due to Jones

Degree	Unknowns
4	58
8	38
12	32
20	28
24	26
28	25
96	21
2668	19
2.0×105	14
1.3×1044	12
4.6×1044	11
8.6×1044	10

Diophantine equations are generally solvable for degrees one (linear) and two (quadratic), as well as for one variable. Skolem showed that any Diophantine polynomial can be expressed as a quartic (albeit often with more variables), which also proves degree 4 undecidable. It is impossible to produce a general algorithmic solution for any of the cases where there exists a universal Diophantine equation, since a general solution would have to solve for the universal equation's outputs, and since Turing machines can be encoded into them, such a solution would solve the halting problem. This proves that there is no general algorithm for Hilbert's Tenth problem, which asks if any and all arbitrary Diophantine equations can be solved mechanistically.

The exact bounds for undecidability are unknown. Related problems for the decidability of polynomials on other rings are variously decidable (e.g. reals) or undecidable (e.g. single variable real valued functions^{[verification needed]}).

Languages and problems

The following languages/problems can be viewed as particular cases of Diophantine equations.

• Quadratic sync problem

Further reading

• Gregory J. Chaitin, Algorithmic Information Theory (Cambridge University Press 1987) (ISBN: 9780511608858, 9780521343060, 9780521616041, online) presents a translation from LISP, to register machines, to Diophantine equations