FOM: OpenMindedComparison

[Lou van den Dries]

Okay, here are three short statements:

1. There is no fool proof algorithm to tell whether a given polynomial
equation p(x_1,...,x_n) = 0 with integer coefficients has a solution
in integers.

2. There is a fool proof algorithm to tell whether a given polynomial
equation p(x,y) = 0 with integer coefficients has infinitely many
solutions in integers (and to compute a bound on the number of
solutions if there are only finitely many).

3. There is a fool proof algorithm to tell whether a given polynomial
equation p(x,y) = 0 with rational coefficients has infinitely many
solutions in rationals.

1. is a consequence of Matyasevich, 2. is a consequence of Siegel's
theorem, and Falting's theorem is a big step towards 3. There is no
doubt that number theorists are strongly motivated by the hope of
ultimately settling simple questions like that. (By the way, in 2.
one actually knows the algorithm, and in 3. an algorithm is available
if
a certain number theoretic conjecture holds.)

Now, for 2. and 3. one does not need to have available a general
definition of algorithm (unlike for 1.), so in that sense 1. has a
special status, which you may call foundational if you like. And
certainly, number theorists should be aware of limitations of this kind.
(And they are.) But there is also something like the art of asking
the right questions: in 2. and 3. this means concentrating on the
question of infinitely many solutions (since that property is
invariant under a much bigger group) rather than having one (integer
or rational) solution, which is more delicate. (Of course, one
ultimately wants to solve that too.)

By the way, I fully recognize statistics and complexity theory as
(very interesting) mathematical areas. And complexity theory uses
nowadays a fair amount of number theory. -Lou van den Dries-