Dedicated to Yuri Matiyasevich, a modern day Diophantus.

First Posted: March 25, 2024; This version: May 1, 2024.

[To appear in the American Mathematical Monthly]

In 1971, 23-year-old Yuri Matiyasevich shattered    Hilbert's dream to find a universal algorithm that would input an arbitrary polynomial equation of several variables with integer coefficients and output `yes' or `no' according to whether it does, or does not, have integer solutions. It used, in a very clever way, sequences that satisfy second-order linear recurrences with integer coefficients. Ironically, as an unexpected bonus, he constructed infinite families of Diophantine equations for which the existence of solutions is decidable, the so-called Pell equations.

This was extended to higher-order (third and fourth) recurrences in a deep study by Matiyasevich's disciple, Maxim Vsemirnov, using sophisticated algebraic number theory. In the present, mostly expository, article, we revisit some of Vsemirnov's results from a different, more elementary, viewpoint, and supplement it with a Maple implementation that would enable anyone to actually construct many families of decidable diophantine equations, and find all its solutions, and prove that these are the only ones. Our method can also construct such diophantine equations for which one can prove that no solutions exist.

Maple packages

• Cfinite.txt, a new version of the classic Maple package to explore so-called C-finite sequences, with a new section that is accesed via ezraDio()

• Hilbert10.txt, a Maple package to experiment with Hilbert's tenth problem

Sample Input and Output for Hilbert10.txt

• If you want to see lots of diophantine equations with infinitey many solutions, and some with no solutions inspored by third-order recurrences
  the input file yields the output file

• If you want to see the diophantine equations satisfied by consecutive tuples of C-finite sequences of the form [b₁, ...,b_k-1,-1] if k is even and [b₁, ...,b_k-1,1] if k is odd with initial conditions [0^k-1,1]
  the input file yields the output file

• If you want to see which 3rd-order recurrences are "good"
  the input file yields the output file

• If you want to see numerous Diophantine equations with explicit infinite families of solutions (that come from consecutive pairs of triples) of solutions of second and third-order linear recurrences with constant coefficients,
  the input file yields the output file

Sample Input and Output for the new procedures of Cfinite.txt

• If you want to see many Pell-type equations with already-known-solutions
  the input file yields the output file

Doron Zeilberger's Home Page

Robert Dougherty-Bliss 's Home Page