Throughout, and . A set is recursively enumerable if a deterministic computation accepts exactly its members. A Diophantine representation of is a polynomial , for some , such that, for every , if and only if for some . The representation is single-fold if, for every , exactly one satisfies . It is finite-fold if, for every , only finitely many satisfy . The question is whether every recursively enumerable set has a single-fold Diophantine representation.
An exponential Diophantine representation is defined in the same way, except that may be an expression built with exponentiation as well as addition and multiplication. Davis, Putnam and Robinson proved that every recursively enumerable set has an exponential Diophantine representation. Robinson had shown that suitable growth conditions yield an existential definition of exponentiation. Matiyasevich constructed in 1970 a Diophantine relation of exponential growth, which completed this route to Diophantine representations of all recursively enumerable sets. The resulting representation theorem implies the negative solution of Hilbert’s tenth problem. That representation theorem does not bound the number of with . In 1974 Matiyasevich proved that every recursively enumerable set has an exponential Diophantine representation in which, for each member , exactly one satisfies . The same paper formulates the question above. It reduces the question to a single-fold Diophantine representation of the relation on triples . The single-fold conjecture asserts that the answer to this question is affirmative. The finite-fold conjecture asserts that every recursively enumerable set has a finite-fold Diophantine representation (Matiyasevich, 2010).
The preprint proves the single-fold conjecture, as its Theorem 1.1. It also constructs a total function whose graph has a single-fold Diophantine representation. It further proves that the relation , restricted to , has a single-fold Diophantine representation. From Theorem 1.1 the preprint derives that, for some , no algorithm decides whether a polynomial in of total degree at most has a zero in , even under the promise that it has at most one; the Lean library does not contain this corollary.
The results on these pages are those of the Lean library SingleFold, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The preprint is a guide only: it gives the results their order and their names. The Lean library proves Theorem 1.1 with no added hypothesis.
SingleFold is a Lean library: 17 items, in seven groups. Each has a page written by OctoInform, listed below.
No item matches.