Jones, J.P., Universal diophantine equation, Journal of Symbolic Logic 47 (1982), 549-571. MR 84e:10070.

Abstract

A universal diophantine equation is a polynomial equation, in several variables, which by choice of a parameter (or several parameters), can existentially define an arbitrary recursively enumerable set.

Examples of universal diophantine equations are constructed in this paper. The equations are of various degrees and numbers of unknowns. Some of the universal equations have degrees as small as 4.

An example is the system of equations given in the following theorem. Here the parameters are x, z, u and y. W(z,u,y) denotes an arbitrary r.e. set of nonnegative integers, indexed by z, u and y.

Theorem. In order that x belongs to W(z,u,y) it is necessary and sufficient that the following system of equations have a solution in nonnegative integers:

elg2 + A = (b - xy)q2, q = b560, E + q4 = 1 + Eb5, D + 2z = b5, l = u + tD, e = y + mD, n = q16,

r = [g + eq3 + lq5 + (2(e - zE)(1 + xb5 + g)4 + Eb5 + Eb5q4)q4][n2 - n] + [q3 - bl + l + DEq3 + (b5-2)q5] [n2 - 1],

p = 2ws2r2n2, p2k2 - k2 + 1 = F2, 4(c - ksn2)2 + C = k2, k = r + 1 + hp - h, a = (wn2 + 1)rsn2, c = 2r + 1 + G,

d = bw + ca - 2c + 4aB - 5B, d2 = (a2 - 1)c2 + 1, f2 = (a2 - 1)i2c4 + 1, (d + of)2 = ((a + f2(d2 - a))2 - 1) (2r + 1 + jc)2 + 1

In these equations there are 28 unknowns a,b,c,d,e,f,g,h,i,j,k,l, m,n,o,p,q,r,s,t,w,A,B,C,D,E,F,G and four parameters z,u,v,x. The degree is 560.

The degree can be reduced to 4 at the expense of the number of unknowns. The following pairs (n,d) where n is the number of unknowns and d is the degree, are sufficient for all r.e. sets:

(58, 4),   (38, 8),   (32, 12),   (29, 16),   (28, 20),   (26, 24),

(25, 28),   (24, 36),   (21, 96),   (19, 2668),   (14, 2.0*105),

(13, 6.6*1043),   (12, 1.3*1044),   (11, 4.6*1044),   (10, 8.6*1044),   (9, 1.6*1045).

The last pair (9, 1.6*1045) is the 9 unknowns theorem. This theorem, due to Matijasevich, is proved in this paper. The theorem states that the number of unknowns can be reduced to 9 at the expense of the degree d. Formally:

Theorem. Every recursively enumerable set A is diophantine definable in 9 unknowns,

A(x) <=> E x1 x2,..., x9 [P(x1, x2,..., x9) = 0].

Since every recursively enumerable set is existentially definable in 9 unknowns, every diophantine equation, in any number of unknowns, is equivalent to a diophantine equation in 9 unknowns. The degree of the polynomial P(x1,   x2,..., x9) is large, 1.6*1045.