As of today, the question remains open as to whether the quaternary quartic equation
7 (*) which M. Davis put forward in 1968, has only nitely many solutions in integers. If the answer were a rmative then|as noted by M. Davis, Yu. V. Matiyasevich, and J. Robinson in 1976|every r.e. set would turn out to admit a single-fold polynomial Diophantine representation. New candidate `rule-them-all' equations, constructed by the same recipe which led to (*), are proposed in this paper.
As was anticipated in [
This result, known as the Davis-Putnam-Robinson (or `DPR') theorem, was
later improved by Yu. Matiyasevich in two respects: in [
FRA-UniTS 2016.
use of exponentiation, altogether, from (y); in [
9 !x '( !a ; !x ) of R in the above form (y) is said to be single-fold if
'( !a ; !x ) & '( !a ; !y) =) !x = !y (i.e., the constraint '( a1; : : : ; an ; x1; : : : ; xm ) never has multiple solutions). The de nition of nite-fold -ness is akin: The overall number of solutions (in the x's) that correspond to each n-tuple ha1; : : : ; ani of actual parameters must be nite.
In [
One way out of this di culty was indicated in [
Skepticism concerning the nitude of the set of solutions to Davis's equation
began to circulate among number theorists after D. Shanks and S. S. Wagsta
[
Four candidate rule-them-all equations
As of today, there are four competitors for the role of `rule-them-all' equation'
over N (one was originally proposed in [
R(a1; : : : ; an) () 9 x0 9 x1 9 xm P (a1; : : : ; an; x1; : : : ; xm) = 4x0 + x0 ; where P is a polynomial with coe cients in Z. -11: 11 r2 (four sign combinations).
Each one of these equations stems from a square-free rational integer d > 1 such that the integers of the imaginary quadratic eld Q(p d) form a uniquefactorization domain. The numbers in question are known to be 1, 2, 3, 7, 11, 19, 43, 67, 163, and no others. Consider, for each such d except d = 1, also the equation d y2 + 1 = (meaning: `d y2 + 1 is a perfect square'). As is well known, this is a Pell equation endowed with in nitely many solutions in N. The equations we have listed are associated|in the manner discussed below| with the discriminants 2; 3; 7; 11 of the corresponding Pell equations; in principle we could have associated a rule-them-all equation also with each one of 19; 43; 67; 163.
Trivial solutions: A solution in N, for each of the four rule-them-all equations shown above, is:
r = u = 1 ; s = v = 0 :
The trivial solutions, in Z, of 11 r2 + r s + 3 s2 2 v2 + v u + 3 u2 2 = 2 are: s = 0, r 2 f 1; 1g and either v = 0, u 2 f 1; 1g or u = 1, v = 1.
Non-trivial solutions (in N): As mentioned in the Introduction, at least 50 solutions were found for the rule-them-all equation with discriminant 7.
Two non-trivial solutions for the discriminant 3 were detected, and kindly communicated to us, by Boris Z. Moroz (Rheinische Friedrich-Wilhelms-Universitat Bonn) and Carsten Roschinski:2 2 Independently, also Alessandro Logar (Univ. of Trieste) found the same solutions. 3 In the case of 7, this claim must be restrained to the odd representable positive integers.
Let us also point out, for the respective discriminants, the poison primes : prime numbers p such that p prime numbers p such that p prime numbers p such that p prime numbers p such that p 5; 7 (mod 8) ; 2 (mod 3) ; 3; 5; 6 (mod 7) ; 2; 6; 7; 8; 10 (mod 11) .
Quick discussion referring to the discriminant -11 Since we cannot a ord discussing at length each of the four candidate rule-themall equations, we will o er a bird's-eye view of how to construct, directly from the unproven assertion that the quaternary quartic equation 11 has only nitely many integer solutions, a nite-fold polynomial Diophantine representation of a relation of exponential growth.
Take into account the increasing sequence hyiii2N = h0; 3; 60; 1197; : : :i of all solutions to the Pell equation 11 y2 + 1 = : Also consider the relations: OD(a; b) ,Def 9 x (2 x + 1) a = b ;
J ( u ; w ) ,Def w 2 fy22 `+1 : ` > 2g & OD( u ; w ) : It can easily be shown that J is of exponential growth in Julia Robinson's sense, namely that: { {
J (u; v) implies v < uu ; for each `, there are u and v such that J (u; v) & u` < v .
Does the predicate w 2 fy22 `+1 : ` > 2g|and, consequently, J |admit a polynomial Diophantine representation? It turns out that the following are necessary and su cient conditions in order for w 2 fy22 `+1 : ` > 2g to hold: (i) w > 3 ; (ii) 11 w2 + 1 = ; (iii) 9 v 9 u w = v2 v u + 3 u2 ; (iv) [(r2 + r s + 3 s2) (v2 + vu + 3 u2)] - w, for any non-trivial integer solution to 11 r2 + r s + 3 s2 2 2 + u + 3 u2 2 = 2 : This results in a Diophantine speci cation if the number of solutions to the novel quaternary quartic (z) is nite ! An issue that must be left open here.
Notice that the only potential source of multiple solutions to the above representation of J is condition (iii), which, anyhow, is nite-fold.
The issue as to whether (z) has only nitely many solutions over N can be recast as the analogous problem concerning the system
The existence of nite-fold Diophantine representations for all r.e. sets thus reduces to the nitude of the set of integer points lying on a speci c surface.
Discussions with Pietro Corvaja were very fruitful for the matters of this paper.
Addendum referring to the discriminant -11 Here we provide clues on how to associate a quaternary quartic, candidate rulethem-all, equation with the number -11.
Along with the above-considered sequence hyiii2N of all solutions to the Pell equation 11 y2 + 1 = ; take also into account the associated sequence hxiii2N = h1; 10; 199; 3970; : : : i with xi = p11 yi2 + 1. Then we have: { for every h > 0, y2h is representable in the form
since y2h = 2h+1 15 Q0<i<h x2i ; { if y2` (2 h+1) is representable (in that form), so are z3 xh + 11 yh }a|nd xh + 3 yh{; { if yn is representable for some n > 0 not a power of 2, then the system coprime numbers 8 X2 11 Y 2 = 1 ; < 3 X + 11 Y = 2 + u + 3 u2 ; : X + 3 Y = r2 + r s + 3 s2 has an integer solution for which Y 6= 0 ; consequently, the equation 11 (z) has a non-trivial integer solution hr; s; v; ui, a solution being dubbed trivial when it satis es both of r2 + r s + 3 s2 = 1 and 2 + u + 3 u2 = 3. Such a solution hr; s; v; ui will also satisfy r2 + r s + 3 s2 2 + u + 3 u2 j yn.
Let H stand for the assertion (whose truth, as of today, must be left open): k The equation (z) has no solutions in integers except the trivial ones. Moreover, let H0 stand for the weaker|and also open|assertion: k The equation (z) admits at most nitely many solutions in integers.
Then the above-listed facts yield that: Theorem 1. H implies that yn is representable for n > 1 if and only if n is an odd power of 2.
Corollary 1. H implies that f y22 `+1 : ` = 0; 1; 2; : : : g is a Diophantine set. Lemma 1. H0 implies that f y22 `+1 : ` = 0; 1; 2; : : : g is a Diophantine set.