FOM: Diophantine polynomials--reply to Tennant

Mon Mar 23 13:50:51 EST 1998

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

More information about the FOM mailing list