OctoInformBeta

Single-fold Diophantine representations and undecidability under an at-most-one-solution promise

Throughout, ℕ={0,1,2,…}\mathbb{N}=\{0,1,2,\ldots\} and n≥1n\ge1. A set S⊆ℕnS\subseteq\mathbb{N}^n is recursively enumerable if a deterministic computation accepts exactly its members. A Diophantine representation of SS is a polynomial P∈ℤ[A1,…,An,W1,…,Wm]P\in\mathbb{Z}[A_1,\ldots,A_n,W_1,\ldots,W_m], for some m∈ℕm\in\mathbb{N}, such that, for every a∈ℕna\in\mathbb{N}^n, a∈Sa\in S if and only if P(a,w)=0P(a,w)=0 for some w∈ℕmw\in\mathbb{N}^m. The representation is single-fold if, for every a∈Sa\in S, exactly one w∈ℕmw\in\mathbb{N}^m satisfies P(a,w)=0P(a,w)=0. It is finite-fold if, for every a∈ℕna\in\mathbb{N}^n, only finitely many w∈ℕmw\in\mathbb{N}^m satisfy P(a,w)=0P(a,w)=0. 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 PP 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 w∈ℕmw\in\mathbb{N}^m with P(a,w)=0P(a,w)=0. In 1974 Matiyasevich proved that every recursively enumerable set has an exponential Diophantine representation in which, for each member aa, exactly one w∈ℕmw\in\mathbb{N}^m satisfies P(a,w)=0P(a,w)=0. The same paper formulates the question above. It reduces the question to a single-fold Diophantine representation of the relation c=bnc=b^n on triples (b,n,c)∈ℕ3(b,n,c)\in\mathbb{N}^3. 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 g:ℕ→ℕg\colon\mathbb{N}\to\mathbb{N} whose graph has a single-fold Diophantine representation. It further proves that the relation c=bnc=b^n, restricted to b≥2b\ge2, has a single-fold Diophantine representation. From Theorem 1.1 the preprint derives that, for some m,D≥1m,D\ge1, no algorithm decides whether a polynomial in ℤ[W1,…,Wm]\mathbb{Z}[W_1,\ldots,W_m] of total degree at most DD has a zero in ℕm\mathbb{N}^m, 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.

The Lean library: SingleFold

SingleFold is a Lean library: 17 items, in seven groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. Recursively enumerable sets and single-fold representations Single-fold Diophantine representations of recursively enumerable sets.
  2. Theorem 1.1 Every recursively enumerable set has a single-fold Diophantine representation.
§2. Polynomial constructions with unique witnesses 2 items
  1. Definition 2.1 Diophantine representations with a unique auxiliary tuple.
  2. Lemma 2.2 Intersections and disjoint unions of single-fold relations are single-fold.
§3. A rank-one curve with unique arithmetic codes 4 items
  1. Proposition 3.1 The curve y2=x3−25xy^2 = x^3 - 25x has rank one.
  2. Rational codes and point codes Coding rational numbers and points of EE by natural numbers.
  3. Lemma 3.2 Each rational number has exactly one valid code.
  4. Lemma 3.3 Sums and multiples of points of EE as single-fold relations.
§4. A uniquely represented function with intermediate growth 3 items
  1. Heights, the scalar m_* and the sequence W_j Canonical heights and a height sequence of quadratic logarithmic growth.
  2. Lemma 4.1 Representative points are unique per index and single-fold.
  3. Proposition 4.2 A function with a single-fold graph and intermediate growth.
§5. A power graph from a growth function 2 items
  1. Lemma 5.1 Pell terms grow between two geometric rates.
  2. Proposition 5.2 Exponentiation is single-fold, through a growth function.
§6. Testing containment of binary digits 1 item
  1. Proposition 6.1 Containment of binary digits is a single-fold relation.
§7. One witness for a halting computation 3 items
  1. Counter machines Counter machines, their runs and the first halting time.
  2. Lemma 7.1 Counter machines recognize every recursively enumerable relation.
  3. Proposition 7.2 The halting relation of a counter machine is single-fold.

No item matches.