FOM: Diophantine polynomials--reply to Tennant

[Martin Davis]

>Neil--For what it's worth, not only the number of variables but also the
>exponents can be bounded by small integers so ALL the complication can be coded
>into the  coefficients.  This is a significant point which justifies Franzen to
>some degree -- if you regard all natural numbers as having the same logical
>complexity then the diophantine polynomials are really not very complex at all.
>If Davis's conjecture about singlefold representations is true (equivalent to a
>certain extremely simple polynomial in 2 variables having only finitely many
>solutions) then the simple diophantine representation faithfully reflects the
>complexity of the original problem in a strong sense.  It is still true that it
>would take a 100-page book to actually write down all the coefficients (Martin,
>can you confirm this?), so Harvey's finite combinatorial result is simpler
>information-theoretically but *not* logically.--Joe Shipman
>
I believe none of this is right:

One can get the degree down to 4 (almost trivially) and the number of
unknowns down to 9 (not at all trivially) BUT NOT SIMULTANEOUSLY. Getting
one to be small makes the other enormous in any work I've seen.

On the other hand, James Jones has a universal system of equations that can
be written in 1/4 page. The catch is an exponent of 5^60. Going to a single
equation is naturally no big deal (sum the squares). But of course to turn
this into an undecidable sentence in ZF will, as indicated, require
substituting some enormous integers (to code provability in ZF as well as an
index of a non-computable set) into the equation.

Martin

References:
HILBERT'S TENTH PROBLEM by Yuri Matiyasevich, MIT Press 1993, p.70.
UNIVERSAL DIOPHANTINE EQUATIONS by James Jones, JSL, 47(1982), pp. 549-571.