A Formal Proof of Complexity Bounds on Diophantine Equations
Jonas Bayer, Marco David · 2025
Read A Formal Proof of Complexity Bounds on Diophantine Equations by Jonas Bayer, Marco David (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16963.txt.
Introduction
Jonas Bayer and Marco David formally verify, inside the Isabelle/HOL proof assistant, a construction showing that simple Diophantine equations can already be undecidable, in a paper published in two thousand twenty-five. Hilbert's tenth problem asked for an algorithm to decide whether such equations have solutions, and Matiyasevich proved none exists in general.
The question stays open for equations of bounded complexity, measured by the number of variables and the degree. A pair of bounds is called universal if every Diophantine set can be represented by equations within them, which forces undecidability for that class. In earlier work the authors found the first nontrivial universal pair for integer unknowns. This paper machine-checks the main construction behind that result. Formal proof matters here because the construction is intricate and error-prone. The verified version puts the undecidability threshold on solid ground.
Catalog record
| CREATOR | Jonas Bayer, Marco David |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-16963
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Formal Proof of Complexity Bounds on Diophantine Equations Jonas Bayer, Marco David Abstract We present a universal construction of Diophantine equations with bounded complexity in Isabelle/HOL. This is a formalization of our own work in number theory [ 1 ] . Hilbert’s Tenth Problem was answered negatively by Yuri Matiyasevich, who showed that there is no general algorithm to decide whether an arbitrary Diophantine equation has a solution. However, the problem remains open when generalized to the field of rational numbers, or contrarily, when restricted to Diophantine equations with bounded complexity, characterized by the number of variables ν \nu and the degree δ \delta . If every Diophantine set can be represented within the bounds ( ν , δ ) (\nu,\delta) , we say that this pair is universal , and it follows that the corresponding class of equations is undecidable. In a separate mathematics article, we have determined the first non-trivial universal pair for the case of integer unknowns. In this paper, we contribute a formal verification of the main construction required to establish said universal pair. In doing so, we markedly extend the Isabelle AFP entry on multivariate polynomials [ 17 ] , formalize parts of a number theory textbook [ 15 ] , and develop classical theory on Diophantine equations [ 14 ] in Isabelle. Additionally, our work includes metaprogramming infrastructure designed to efficiently handle complex definitions of multivariate polynomials. Our mathematical draft has been formalized while the mathematical research was ongoing, and benefitted largely from the help of the theorem prover. We reflect how the close collaboration between mathematician and computer is an uncommon but promising modus operandi. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, [email protected]://orcid.org/0009-0006-2500-3146 Department of Physics, University of California, Berkeley, [email protected]://orcid.org/0000-0001-5673-5389 This project would not exist without Yuri Matiyasevich who proposed the formalization of Hilbert’s Tenth Problem and encouraged our exploration of Universal Pairs. We are deeply grateful to Dierk Schleicher for his unwavering support throughout, both on a personal level and through his mathematical insight. We thank Malte Haßler, Thomas Serafini and Simon Dubischar for their mathematical contributions to the project. We are indebted to the group of students who contributed at various stages of the formalization. In particular, we thank Timothé Ringeard and Xavier Pigé for leading the formal proof of the Bridge Theorem; Anton Danilkin for his work on poly_extract and further developments in multivariate polynomial theory; Mathis Bouverot-Dupuis, Paul Wang, Quentin Vermande, and Theo André for their formalization of coding theory; Loïc Chevalier, Charlotte Dorneich, and Eva Brenner for the formalization of Matiyasevich’s polynomial and relation combining; and Chris Ye and Kevin Lee for their contributions to formal degree calculations. The above highlights their primary contributions, though many have supported other aspects of this work whenever they were able. We also thank all other members of the student work group for their involvement in the project. We gratefully acknowledge support from the Département de mathémathiques et applications at École Normale Supérieure de Paris. \lstdefinelanguage isabellekeywords=[1]type_synonym,datatype,fun,abbreviation,definition,proof,lemma,theorem,corollary,by,have,from,with,using,lift_definition,locale,consts, keywordstyle=[1] , keywords=[2]fixes,defines,where,assumes,shows,and,is, keywordstyle=[2] , keywords=[3]if,then,else,case,of,SOME,let,in,O, keywordstyle=[3] , commentstyle= , morecomment=[l](* \lstset language=isabelle, escapeinside=, columns=fixed, extendedchars, basewidth=0.5em,0.45em, basicstyle= , mathescape, ccs Theory of computation \rightarrow Logic and verification keywords Diophantine Equations, Hilbert’s Tenth Problem, Isabelle/HOL † † runningauthor: J. Bayer and M. David † † copyright: Jonas Bayer and Marco David † † supplement: The formal proof is available online. † † supplement: Formal Proof Development: https://gitlab.com/hilbert-10/universal-pairs † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction 1.1 Hilbert’s Tenth Problem The tenth problem on David Hilbert’s 1900 list of twenty-three mathematical problems asks for an algorithm to decide the solvability of any arbitrary Diophantine equation [ 7 ] . Like many problems on his list, Hilbert’s Tenth Problem has provided inspiration for much mathematical research in the last century, and still does so until today. While the original problem was solved over fifty years ago [ 10 ] , this paper presents the formal verification of results related to a new quantitative theorem, stronger than the original solution. A Diophantine equation is a multivariate polynomial equation over the integers. There are countably infinitely many such equations, and they form a very general language: many difficult problems across number theory and related fields can be equivalently expressed as a single Diophantine equation [ 13 ] . One often considers parametric equations of the type P(a,z_{1},\ldots,z_{\nu})=0 where a is called the parameter and z_{1},\ldots,z_{\nu} are called unknowns. A Diophantine set A\subset{\mathbb{N}} is then defined to be any set of parameters such that a\in A if and only if there are unknowns z_{1},\ldots,z_{\nu}\in{\mathbb{Z}} with P(a,z_{1},\ldots,z_{\nu})=0 . The Davis-Putnam-Robinson-Matiyasevich theorem (1970) [ 12 , Chapter 1] states that every recursively enumerable set is Diophantine; this is a deep relation between number theory and computability theory. An enumeration argument shows that, conversely, every Diophantine set is recursively enumerable. The resulting equivalence implies that there are Diophantine sets which are not decidable, and hence proves that Hilbert’s Tenth Problem is undecidable. 1.2 Universal Diophantine Equations and Pairs Because the set of all recursively enumerable (r.e.) sets is itself recursively enumerable, there must exist a corresponding Diophantine equation for this set, representing all r.e. sets, i.e. all Diophantine sets at once. An equation with this property is known as a universal Diophantine equation , and an explicit example can be found in an article by Jones [ 8 ] . It is now natural to ask about the minimal complexity required for such universal equations. A popular measure of complexity is the number of unknowns \nu required and the total degree \delta of the polynomial. If all Diophantine sets can be represented by a polynomial in at most \nu unknowns and in degree at most \delta , we call (\nu,\delta) a universal pair . There is a trade-off between the two measures: one may reduce the degree by introducing auxiliary unknowns, and vice versa eliminate unknowns at the cost of increasing the degree. There is a subtle but interesting distinction between allowing the unknowns z_{1},\ldots,z_{\nu} of P to take values in the natural numbers, including zero, versus in the integers. Universal pairs can be defined for both cases, and we shall write (\nu,\delta)_{\mathbb{N}} and (\nu,\delta)_{\mathbb{Z}} to make the distinction explicit. Previous work has primarily focused on universal pairs over the natural numbers. In this case, it was Matiyasevich [ 11 ] who first announced the smallest currently known number of unknowns \nu=9 . Jones [ 8 ] later published a complete proof that (9,1.64\cdot 10^{45})_{\mathbb{N}} is universal, together with the lowest currently known degree \delta=4 . More precisely, the pair (58,4)_{\mathbb{N}} is universal, too. Our work contributes the first derivation of a non-trivial universal pair over the integers. Note that any universal pair over {\mathbb{N}} induces a pair over {\mathbb{Z}} . Every n\in{\mathbb{N}} can be written as x^{2}+y^{2}+z^{2}+w^{2} for integers x,y,z,w\in{\mathbb{Z}} using Lagrange’s four square theorem. Thus, a Diophantine equation with unknowns in {\mathbb{N}} can be transformed into an