[seqfan] Martin Davis on Diophantine Definitions

[Brad Klee]

Hi Seqfans,

You may be interested in Martin Davis' contribution "Algorithms, Equations,
and Logic", which appears first in the compendium: "The Once and Future
Turing". The main result discussed by Davis is the refutation of Hilbert's
tenth problem; though, the result is given in the positive form of the
MRDP/DPRM theorem, which states that:

"If a set [of natural numbers] is listable then it is also Diophantine"

As Davis explains in a semi-personal story, this is a huge an unexpected
result only decided after decades of research involving a team of no fewer
than four great mathematicians, including lastly Yuri Matiyasevich. The
theorem has far reaching implications, especially relevant to OEIS:

Consider any well-defined OEIS sequence, free of ordering, as an example of
a "listable set". According to MRDP/DPRM theorem, any such sequence is
associated with the solutions of a Diophantine equation. In general, the
determination of a Diophantine equation provides 1/2 of the information
necessary for the definition of an OEIS sequence. As Davis' article
discusses, from the DE it is always possible to generate an un-ordered list
by tupling positive integers and evaluating the DE. Ordering of the set
into a sequence remains, but I'm sure that this is possible in many
situations.

We can just take some examples to start. The prime numbers are discussed
explicitly in Davis' article. On Page 14 Davis gives a result from Jones,
Sato, Wada, and Wiens--a Diophantine Equation (DE) that defines the prime
numbers A000040, the same equation as is found at:

https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/JonesSatoWadaWiens.pdf

which appears not to be mentioned on the entry for A000040. It's very
interesting that such an equation exists, but, yes, it is somewhat
foreboding and people will not find it as beautiful as many of Euler's
one-line results, etc. Furthermore, since the equation involves a large
space, it's difficult to say how we could go about constructing an
algorithm for search and sequence.

It's possible that some general search algorithm subsumes all special
cases, but in ignorance of general means it may be better to consider the
examples on Page 7 for:

composite numbers (A002808):       a - (x+2)(y+2)=0
Not Powers of 2 ( A057716 ):            a - (2x+3)(y+1) =0
nonsquares ( A000037 ):                   x^2 -a*(y+1)^2 - 1 = 0

where the convention is that "a" is in the "diophantine set" if there
exists a solution of the DE in N^2 ( pairs of natural numbers including
zero ).

Quick search of pages for A002808, A057716, A000037 did not reveal any
reference to Diophantine equations, much less a computable enumeration
function that searches N^2 and outputs in the correct order. The first two
look easy to crack, the third, possibly more complicated. Out of time,
today, but excited about this new direction, which we might take up
throughout OEIS.

At least one article of "The Once and Future Turing" may be of interest to
our readership. It seems that implications of Davis' discovery have yet to
be fully implemented and explored in the context of OEIS. Send questions or
comments.

Best Regards,

Brad