Creating Decidable Diophantine Equations

By Robert Dougherty-Bliss, Charles Kenney, and Doron Zeilberger


Dedicated to Yuri Matiyasevich, a modern day Diophantus.

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

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

Sample Input and Output for Hilbert10.txt

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

Articles of Doron Zeilberger

Doron Zeilberger's Home Page

Robert Dougherty-Bliss 's Home Page