Diophantine equation

Diophantine equations are equations, typically polynomial, where the valid solutions are integers. Polynomial equations are in the form P(X) = P(Y), where P(V) denotes a polynomial which is defined using a given vector of variables. For the equation $x^{3}-2x=0$, $x=0$ is a Diophantine solution, but $x=\pm {\sqrt {2}}$ is not since it is not an integer, and $5x=2$ has no valid solutions.

Examples

Some common Diophantine equations include:

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

As a model of computation

Diophantine equations can be parameterized. Parameterization splits variables into two categories, parameters and unknowns. Viewed from this angle, Diophantine equations are partial functions where parameters are used as arguments, with unknowns encoding at least part of the result. Note that they are partial functions, since the equations can have no solutions. Diophantine equations can be thought to model sets, with a set being Diophantine if there exists a Diophantine equation modeling it.

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