FOM: Diophantine equations

[Harvey Friedman]

Reply to Shipman 1:58PM 3/23/98.

>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 not really true. For example, the following pairs of numbers are
taken from page 163 of Hilbert's Tenth Problem by Matiyasevich, MIT Press,
1993, with the reference J.P. Jones, Universal Diophantine equation, JSL,
47(3): 549-571:

(4,58), (8,38), (12,32), (16,29), (20,28), (24,26), (28,25), (36.24),
(96,21), (2668,10), (2 x 10^5,14), (6.6 x 10^43,13), (1.3 x 10^44,12), (4.6
x 10^44,11), (8.6 x 10^24,10), (1.6 x 10^45,9). Here, say, (24,26) means
that every Diophantine set of natural numbers can be Diophantine
representable by means of a polynomial with <=26 variables and degree <=24.

But it is not only the coefficients that are uncomfortably large. Imagine
how many monomials might be involved in the case (24,26)!! And also, if I
read the book correctly, Matiyasevich may actually mean that 24 is a bound
on the degree of the polynomial with respect to each of the 26 unknowns,
which would allow much much much more monomials!!!

To address this issue to some extent, Jones is cited with the same
reference as proving that 100 operations suffices. I haven't looked at the
paper, but by this I assume one has 100 uses of addition and
multiplication, where one is building more and more complex expressions.
The actual expression not only doesn't look like a polynomial, but could be
extremely wild in form. One could quantify out by 100 or so new variables,
but the inside would be a conjunction of 100 or so equations, also a horse
of a different color.

Of course, the connection between all this and independence results is the
following. In each of these complexity classes there is a polynomial (or
arithmetic expression) where the coefficients have been chosen so that the
question of whether the resulting polynomial (or expression) has a zero in
the integers is independent of ZFC. This follows from classical 1930's
logic.

I know of no reasonable bounds on the coefficients; in fact, no bound on
the coefficients that would allow them to be written in base 10 on a page
of paper. In fact, not without using more digits than electrons in the
universe. The point is that any independence result obtained in this way by
present techniques is of a completely different character than any
Diophantine equation considered by mathematicians.

TECHNICAL PROBLEM: Develop some upper bounds on the coefficients needed for
a Diophantine problem independent of ZFC, under various constraints on the
number of variables and the degree. This would round out the theory, and I
haven't seen much about this. Have any of the fom subscribers?

>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.

This "point" certainly predates Franzen, and is not convincing even as
stated. For the purposes at hand, to fail to distinguish between 15 and 15
x 10^10^100 is really quite odd (no, it's even).