FOM: Diophantine polynomials--reply to Tennant
JOE SHIPMAN, BLOOMBERG/ SKILLMAN
jshipman at bloomberg.net
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