[seqfan] Re: Martin Davis on Diophantine Definitions

[Neil Sloane]

Brad, Thanks for reminding the list of the connection between the OEIS
and the solution of Diophantine equations.  I've added a reference to
the Jones-Sato-et al. paper to the entry for the primes, A000040,
as well as a reference to the Davis article, which is:
Martin Davis, "Algorithms, Equations, and Logic", pp. 4-15 of S. Barry
Cooper and Andrew Hodges, Eds., "The Once and Future Turing: Computing
the World", Cambridge 2016.
Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com



On Sun, Aug 14, 2016 at 4:48 PM, Brad Klee <bradklee at gmail.com> wrote:
> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/