Search

Significance A Diophantine equation is a polynomial equation to which one seeks solutions in integers. There is a notable disparity between the difficulty of stating Diophantine equations and that of solving them. This feature was formalized in the 20th century by Matiyasevich’s negative answer to Hilbert’s tenth problem: It is impossible to tell whether some Diophantine equations have solutions or not. One need not look very far to find examples whose status is unknown. A striking example was noted by Mordell in 1953: The equation x3+y3+z3=3 has the solutions (1,1,1) and (4,4,−5) (and permutations); are there any others? This paper concludes a 65-y search with an affirmative answer to Mordell’s question and strongly supports a related conjecture of Heath-Brown., We make several improvements to methods for finding integer solutions to x3+y3+z3=k for small values of k. We implemented these improvements on Charity Engine’s global compute grid of 500,000 volunteer PCs and found new representations for several values of k, including 3 and 42. This completes the search begun by Miller and Woollett in 1954 and resolves a challenge posed by Mordell in 1953.

Matiyasevich's theorem states that there is no algorithm to decide whether or not a given Diophantine equation has a solution in non-negative integers. Smorynski's theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable. We prove: (1) Smorynski's theorem easily follows from Matiyasevich's theorem, (2 ) Hilbert's Tenth Problem for Q has a negative solution if and only if the set of all Diophantine equations with a finite number of rational solutions is not recursively enumerable.

We prove: (1) the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable, (2) the set of all Diophantine equations which have at most finitely many solutions in positive integers is not recursively enumerable, (3) the set of all Diophantine equations which have at most finitely many integer solutions is not recursively enumerable, (4) analogous theorems hold for Diophantine equations D(x1, …, xp) = 0, where p ∈ N\{0} and for every i ∈ {1, …, p} the polynomial D(x1, …, xp) involves a monomial M with a non-zero coefficient such that xi divides M, (5) the set of all Diophantine equations which have at most k variables (where k≥ 9) and at most finitely many solutions in non-negative integers is not recursively enumerable.

We show that several problems concerning probabilistic finite automata of a fixed dimension and a fixed number of letters for bounded cut-point and strict cut-point languages are algorithmically undecidable by a reduction of Hilbert's tenth problem. We then consider the set of so called “F-Problems” emptiness, infiniteness, containment, disjointness, universe and equivalence and show that they are also undecidable for bounded non-strict cut-point languages on probabilistic finite automata. For a finite set of matrices $\{M_1, M_2, \ldots,M_k\} \subseteq \mathbb{Q}^{t \times t}$, we then consider the decidability of computing the maximal spectral radius of any matrix in the set $X = \{M^{j_1}_1 M^{j_2}_2 \cdot M^{j_k}_k \vert j_1, j_2,\ldots, j_k \geq 0\}$, which we call a bounded matrix language. Using an encoding of a probabilistic finite automaton shown in the paper, we prove the surprising result that determining if the maximal spectral radius of a bounded matrix language is less than or equal to one is undecidable, but determining whether it is strictly less than one is in fact decidable which is similar to a result recently shown for quantum automata.

Let K be a number field such that there exists an elliptic curve E of rank one over K. For a set [Formula: see text] of primes of K, let [Formula: see text]. Let P ∈ E(K) be a generator of E(K) modulo the torsion subgroup. Let (xn(P), yn(P)) be the affine coordinates of [n]P with respect to a fixed Weierstrass equation of E. We show that there exists a set [Formula: see text] of primes of K of natural density one such that in [Formula: see text] multiplication of indices (with respect to some fixed multiple of P) is existentially definable and therefore these indices can be used to construct a Diophantine model of ℤ. We also show that ℤ is definable over [Formula: see text] using just one universal quantifier. Both the construction of a Diophantine model using the indices and the first-order definition of ℤ can be lifted to the integral closure of [Formula: see text] in any infinite extension K∞ of K as long as E(K∞) is finitely generated and of rank one.

Let K be a p-adic field (a finite extension of some Q p ) and let K ( t ) be the field of rational functions over K . We define a kind of quadratic reciprocity symbol for polynomials over K and apply it to prove isotropy for a certain class of quadratic forms over K ( t ) . Using this result, we give an existential definition for the predicate “ v t ( x ) ⩾ 0 ” in K ( t ) . This implies undecidability of diophantine equations over K ( t ) .

It is shown that the emptiness problemfor two-pebble automata languages is undecidable and that two-pebble automata are weaker than three-pebble automata.

We prove a strong form of the "n Squares Problem" over polynomial rings with characteristic zero constant field. In particular we prove: for all r ≥ 2 there exists an integer M = M(r) depending only on r such that, if z 1 , z 2 , ..., z M are M distinct elements of F and we have polynomials f,g,x 1 ,x 2 ,...,x M ∈ F[t], with some x i non-constant, satisfiying the equations x r i = (z i + f) r + g for each i, then g is the zero polynomial.

We show that elliptic curves whose Mordell–Weil groups are finitely generated over some infinite extensions of $${\mathbb {Q}}$$ , can be used to show the Diophantine undecidability of the rings of integers and bigger rings contained in some infinite extensions of rational numbers.

For a ring R, Hilbert’s Tenth Problem HTP(R) is the set of polynomial equations over R, in several variables, with solutions in R. We consider computability of this set for subrings R of the rationals. Applying Baire category theory to these subrings, which naturally form a topological space, relates their sets HTP(R) to the set HTP\((\mathbb {Q})\), whose decidability remains an open question. The main result is that, for an arbitrary set C, HTP\((\mathbb {Q})\) computes C if and only if the subrings R for which HTP(R) computes C form a nonmeager class. Similar results hold for 1-reducibility, for admitting a Diophantine model of \(\mathbb {Z}\), and for existential definability of \(\mathbb {Z}\).

The paper presents the history of the negative solution of Hilbert’s tenth problem , the role played in it by Martin Davis, consequent modifications of the original proof of DPRM-theorem, its improvements and applications, and a new (2010) conjecture of Martin Davis .

This chapter surveys some of the developments in the area of Mathematics that grew out of the solution of Hilbert’s Tenth Problem by Martin Davis, Hilary Putnam, Julia Robinson and Yuri Matiyasevich.

Let k be a subfield of a p-adic field of odd residue characteristic, and let L be the function field of a variety of dimension n >= 1 over k. Then Hilbert's Tenth Problem for L is undecidable. In particular, Hilbert's Tenth Problem for function fields of varieties over number fields of dimension >= 1 is undecidable., 19 pages; to appear in Journal of Algebra

We prove that a relation over F q [ Z ] is recursively enumerable if and only if it is Diophantine over F q [ W , Z ] . We do this by first constructing a model of N in F q [ Z ] , where n is represented by Z n . In a second step, we show that it suffices to eliminate a bounded universal quantifier. Then finally, the hardest part of the proof is to show that we can eliminate this quantifier.

Classical results of additive number theory lead to the undecidability of the existence of solutions for diophantine equations in given special sets of integers. Those sets which are images of polynomials are covered by a more general result in the second section. In contrast, restricting diophantine equations to images of exponential functions with natural bases leads to decidable problems, as proved in the third section. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

Let k be a global field and \pp any nonarchimedean prime of k. We give a new and uniform proof of the well known fact that the set of all elements of k which are integral at \pp is diophantine over k. Let k^{perf} be the perfect closure of a global field of characteristic p>2. We also prove that the set of all elements of k^{perf} which are integral at some prime \qq of k^{perf} is diophantine over k^{perf}, and this is the first such result for a field which is not finitely generated over its constant field. This is related to Hilbert's Tenth Problem because for global fields k of positive characteristic, giving a diophantine definition of the set of elements that are integral at a prime is one of two steps needed to prove that Hilbert's Tenth Problem for k is undecidable., Comment: 10 pages; minor revisions made

This is a short survey of known results about elimination of quantifiers over natural numbers, and some implications of these results on the power of computer algebra systems.

The paper establishes lower bounds on the provability of 𝒟=NP and the MRDP theorem in weak fragments of arithmetic. The theory I 5 E 1 is shown to be unable to prove 𝒟=NP. This non-provability result is used to show that I 5 E 1 cannot prove the MRDP theorem. On the other hand it is shown that I 1 E 1 proves 𝒟 contains all predicates of the form (∀i≤|b|)P(i,x)^Q(i,x) where ^ is =

Let K be an algebraic function field of characteristic 2 with constant field C K . Let C be the algebraic closure of a finite field in K. Assume that C has an extension of degree 2. Assume that there are elements u, x of K with u transcendental over C K and x algebraic over C(u) and such that K = C K (u,x). Then Hilbert's Tenth Problem over K is undecidable. Together with Shlapentokh's result for odd characteristic this implies that Hilbert's Tenth Problem for any such field K of finite characteristic is undecidable. In particular, Hilbert's Tenth Problem for any algebraic function field with finite constant field is undecidable.

Let F be a function field of characteristic p > 2, finitely generated over a field C algebraic over a finite field Cp and such that it has an extension of degree p. Then Hilbert's Tenth Problem is not decidable over F.

Let L be a recursive algebraic extension of ℚ. Assume that, given α ∈ L, we can compute the roots in L of its minimal polynomial over ℚ and we can determine which roots are Aut(L)-conjugate to α. We prove that there exists a pair of polynomials that characterizes the Aut(L)-conjugates of α, and that these polynomials can be effectively computed. Assume furthermore that L can be embedded in ℝ, or in a finite extension of ℚp (with p an odd prime). Then we show that subsets of L[X]k that are recursively enumerable for every recursive presentation of L[X], are diophantine over L[X].

M. Davis proved in the early 1950s that every recursively enumerable set has an arithmetic representation with a unique bounded universal quantifier, known today as the Davis normal form. Davis, H. Putnam, and J. Robinson showed in 1961 how the Davis normal form can be transformed into a purely existential exponential Diophantine representation which uses not only addition and multiplication, but also exponentiation. The present author eliminated the exponentiation in 1970 and thus obtained the unsolvability of Hilbert's tenth problem. The paper presents a new method for transforming the Davis normal form into the exponential Diophantine representation. Bibliography: 12 titles.

Davis, Matijasevic, and Robinson, in their admirable survey article [D-M-R], interpret the negative solution of Hilbert's Tenth Problem as a resounding positive statement about the versatility of Diophantine equations (that any listable set can be coded as the set of parameter values for which a suitable polynomial possesses integral solutions).One can also view the Matijasevic result as implying that there are families of Diophantine equations parametrized by a variable t, which have integral solutions for some integral values t = a > 0, and yet there is no computable function of t which provides an upper bound for the smallest integral solution for these values a. The smallest integral solutions of the Diophantine equation for these values are, at least sporadically, too large to be bounded by any computable function. This is somewhat difficult to visualize, since there is quite an array of computable functions. But let us take an explicit example. Consider the functionMatijasevic's result guarantees the existence of parametrized families of Diophantine equations such that even this function fails to yield an upper bound for its smallest integral solutions (for all values of the parameter t for which there are integral solutions).Families of Diophantine equations in a parameter t, whose integral solutions for t = 1, 2, 3,… exhibit a certain arythmia in terms of their size, have fascinated mathematicians for centuries, and this phenomenon (the size of smallest integral solution varying wildly with the parameter-value) is surprising, even when the equations are perfectly “decidable”.

Hilbert's tenth problem for a theory T asks if there is an algorithm which decides for a given polynomial p(x) from Z [x] whether p(x) has a root in some model of T. We examine some of the model-theoretic consequences that an affirmative answer would have in cases such as T = Open Induction and others, and apply these methods by providing a negative answer in the cases when T is some particular finite fragment of the weak theories IE1 (bounded existential induction) or IU-1 (parameter-free bounded universal induction).

In this paper we extend "up to powers" Hilbert’s Theorem 90 to arbitrary finite Galois extensions. In the case of algebraic number fields with class number equal to 1 1 , we completely determine the kernel and image of the norm map.

We show that the problem of finding integer solutions to a polynomial equation over the integers has unification type zero, i.e. there exist polynomial equations which have unifiers, but which have no minimal and complete set of unifiers: In particular, it is shown that the equation uv=w+z has no minimal and complete set of solutions.

Let ∃n denote the set of all formulas ∃x1…∃xn[P(x1, …,xn) = 0], where P is a polynomial with integer coefficients. We prove a new relation-combining theorem from which it follows that if ∃n is undecidable over N, then ∃2n+2 is undecidable over Z.

We show that if R is a nonconstant regular (semi-)local subring of a rational function field over an algebraically closed field of characteristic zero, Hilbert's Tenth Problem for this ring R has a negative answer; that is, there is no algorithm to decide whether an arbitrary Diophantine equation over R has solutions over R or not. This result can be seen as evidence for the fact that the corresponding problem for the full rational field is also unsolvable.

Hilbert’s tenth problem asked for an algorithm to determine whether any given polynomial Diophantine equation has a solution in integers. After important preliminary work by Martin Davis, Hilary Putnam (the philosopher) and Julia Robinson, Yuri Matiyasevic showed that no such algorithm exists. The proof is long and we shall give only a few of the highlights here. For a complete treatment, the reader may wish to consult Davis [1973].

Let R be a recursive subring of a number field. We show that recursively enumerable sets are diophantine for the polynomial ring R[Z]., Comment: Previous version had a mistake in Proposition 18. This problem is avoided by working only with number fields instead of finitely generated fields of characteristic zero

The purpose of the present paper is to give a new, simple proof of the theorem of M. Davis, H. Putnam and J. Robinson [1961], which states that every recursively enumerable relation A(a1, …, an) is exponential diophantine, i.e. can be represented in the formwhere a1 …, an, x1, …, xm range over natural numbers and R and S are functions built up from these variables and natural number constants by the operations of addition, A + B, multiplication, AB, and exponentiation, AB. We refer to the variables a1,…,an as parameters and the variables x1 …, xm as unknowns.Historically, the Davis, Putnam and Robinson theorem was one of the important steps in the eventual solution of Hilbert's tenth problem by the second author [1970], who proved that the exponential relation, a = bc, is diophantine, and hence that the right side of (1) can be replaced by a polynomial equation. But this part will not be reproved here. Readers wishing to read about the proof of that are directed to the papers of Y. Matijasevič [1971a], M. Davis [1973], Y. Matijasevič and J. Robinson [1975] or C. Smoryński [1972]. We concern ourselves here for the most part only with exponential diophantine equations until §5 where we mention a few consequences for the class NP of sets computable in nondeterministic polynomial time.

Let $\mathbb{C}$ be the set of all straight-line programs with one input variable, x, using the following instruction set: $y \leftarrow 0$, $y \leftarrow 1$, $y \leftarrow y + w$, $y \leftarrow y - w$, $y \leftarrow y * w$, and $y \leftarrow \lfloor y/w \rfloor $. We show that two programs in $\mathbb{C}$ are equivalent over integer inputs if and only if they are equivalent on all inputs x such that $|x| \leqq 2^{2^{\lambda r^2 } } $ ($\lambda $ is a fixed positive constant and r is the maximum of the lengths of the programs). In contrast, we prove that the zero-equivalence problem (deciding whether a program outputs 0 for all inputs) is undecidable for programs with two input variables. An interesting corollary is the following: Let $\mathbb{N}$ be the set of natural numbers and f be any total one-to-one function from $\mathbb{N}$ onto $\mathbb{N} \times \mathbb{N}$ (f is called a pair generator. Such functions are useful in recursive function theory and computability theory.) Then f cannot be computed ...

A new proof is given for the well-known theorem of Putnam, Davis, and Robinson on exponential diophantine representation of recursively enumerable sets. Starting from the usual definition of r.e. sets via Turing machines, a new method of arithmetization is given. This new method leads directly to a purely existential exponential formula. The new proof may be more suitable for a course on the theory of algorithms because it requires less knowledge of number theory.

We prove that the diophantine problem for a ring of polynomials over an integral domain of characteristic zero or for a field of rational functions over a formally real field is unsolvable.

Let k be an algebraic number field of finite degree. We denote the absolute class field of k by and the absolute ideal class group of k by Cl(k).

Hilbert's tenth problem is to find an algorithm for determining whether or not a diophantine equation possesses solutions. A diophantine predicate (of positive integers) is defined to be one of the formwhere P is a polynomial with integral coefficients (positive, negative, or zero). Previous work has considered the variables as ranging over nonnegative integers; but we shall find it more useful here to restrict the range to positive integers, no essential change being thereby introduced. It is clear that the recursive unsolvability of Hilbert's tenth problem would follow if one could show that some non-recursive predicate were diophantine. In particular, it would suffice to show that every recursively enumerable predicate is diophantine. Actually, it would suffice to prove far less.

It is an immediate consequence of results of Church and Gödel that there exist arithmetical recursively unsolvable problems, that is, recursively unsolvable problems of the form [M](P = Q) where P and Q are polynomials and [M] is some finite sequence of existential and universal quantifiers. A question which is immediately raised by this result is whether there exist unsolvable problems of this form where [M] is some finite sequence of existential quantifiers only. As a matter of fact this question is easily seen to be closely related to the tenth problem in the famous list proposed by Hilbert in 1900.In this paper, we prove the existence of recursively unsolvable problems of the formwhere P and Q are polynomials with non-negative integral coefficients. As a matter of fact we show that every recursively enumerable predicate is of the form (1), and conversely that every predicate of the form (1) is recursively enumerable. While our result does not yield the recursive unsolvability of Hilbert's tenth problem, it is easily seen that any considerable improvement of our result would yield this unsolvability.The author wishes to take this opportunity to express his gratitude to Professors Alonzo Church and E. L. Post with whom he has had the privilege of discussing some of the questions involved in this paper. He also wishes to thank his friends Melvin Hausner and Jacob Schwartz who have made valuable suggestions.

It is proved that closed finite-dimensional subsets of Q and 12 are Z-sets iff their complement is 1-ULC. As a corollary, closed finite-dimensional sets of deficiency 1 are shown to be Z-sets. 0. Introduction. J. L. Bryant and C. L. Seebeck have proved a homeomorphism extension theorem for k-dimensional compacta in Rn with 1-ULC complements, where 2k+2_n (see [3], [4]). Their results have been considerably generalized by M. A. Stan'ko. Stan'ko gives in [8] several definitions of "dimension-of-embedding" for closed subsets of Rn and proves, besides equivalence of these definitions, the following result: THEOREM (STAN'KO). If K is a closed subset of Rn and dim(K)= k n-2, then the dimension-ofembedding coincides with ordinary dimension. If the dimension gap between K and Rn is sufficiently large, then equality of both dimensions can be considered as a definition of tame embeddings. This apparatus cannot distinguish between tame and wild arcs in R3, because the dimension gap is too small. Professor R. D. Anderson suggested to me that some generalization to the infinite-dimensional case might be possible. An intuitive rephrasing of Stan'ko's result is: If Rn\K is 1-ULC then Rn\K is locally and globally homotopically trivial up to as high a dimension as is compatible with the dimension of K. Stated this way, the obvious generalization to the cases X=12 and X= Q becomes: if K is a finite-dimensional closed subset of X, then K is a Z-set in X iff X\K is 1-ULC. This is the main theorem of this paper. The proof is a straightforward generalization of Stan'ko's proof of Proposition 5 in [8], applied to the infinite-dimensional case. However, no knowledge of infinite-dimensional topology is needed to follow the

An example is given of a diophantine relation which has exponential growth. This, together with the well-known results of Martin Davis, Hilary Putnam, and Julia Robinson, yields a proof that every enumerable predicate is diophantine. This theorem implies that Hilbert's tenth problem is algorithmically unsolvable.

We investigate Diophantine definability and decidability over some subrings of algebraic numbers contained in quadratic extensions of totally real algebraic extensions of Q. Among other results we prove the following. The “big” subring definability and undecidability results previously shown by the author to hold over totally complex extensions of degree 2 of totally real number fields, are shown to hold for all extensions of degree 2 of totally real number fields. The definability and undecidability results for integral closures of “small” and “big” subrings of number fields in the infinite algebraic extensions of Q, previously shown by the author to hold for totally real fields, are extended to a large class of extensions of degree 2 of totally real fields. This class includes infinite cyclotomics and abelian extensions with finitely many ramified rational primes.

For any nontrivial set of cardinal numbers _bt, it is shown that there is no algorithm for testing whether or not the number of positive integer solutions of a given polynomial Diophantine equation belongs to the set. We consider decision problems concerning the number of distinct solutions in positive integers of polynomial Diophantine equations. For any polynomial P(xl, * *, xm) with integer coefficients (not identically zero) we let #(P) be the number of distinct positive integer solutions of P(x1,.*.*, X.) = 0. Thus, O