Return to list of publications of J.P. Jones.

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

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

** 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: **

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 *5 ^{60}*.

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:

*
*

The last pair *(9, 1.6*10 ^{45})* 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

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

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(x _{1}, x_{2},..., x_{9})*
is large,

Return to list of publications of J.P. Jones.