As a by-product of the negative solution of Hilbert's 10th problem, various prime-generating polynomials were found. The best known upper bound for the number of variables in such a polynomial, to wit 10, was found by Yuri V. Matiyasevich in 1977. We show that this bound could be lowered to 8 if the converse of Wolstenholme's theorem (1862) holds, as conjectured by James P. Jones. This potential improvement is achieved through a Diophantine representation of the set of all integers p > 5 that satisfy the congruence 2pp 2 mod p3. Our speci cation, in its turn, relies upon a terse polynomial representation of exponentiation due to Matiyasevich and Julia Robinson (1975), as further manipulated by Maxim Vsemirnov (1997). We brie y address the issue of also determining a lower bound for the number of variables in a prime-representing polynomial, and discuss the autonomous signi cance of our result about Wostenholme's pseudoprimality, independently of Jones's conjecture.
At the beginning of the 1960's, one decade after Martin Davis had set forth the `daring hypothesis that every semidecidable set is Diophantine' [Mat93, p. 99], it became clear that nding a proof of that conjecture would have entailed the possibility to construct a polynomial with integer coe cients whose positive values, as the variables run through all nonnegative integers, form the set of prime numbers.3 The existence of such a prime-generating polynomial seemed, at the time, rather unlikely; in fact, Davis's conjecture was received with understandable skepticism. ? Work partially supported by the project FRA-UniTS (2014) \Learning speci cations and robustness in signal analysis (with a case study related to health care)." 3 Cf. [DMR76, Sec. 1]: \This corollary was deduced by Putnam in 1960 from the then conjectured Main Theorem and it was considered by some to be an argument against its plausibility."
With [Mat70], Yuri V. Matiyasevich positively settled Davis's conjecture and so provided a negative answer to Hilbert's 10th problem [Hil00, p. 276]. Soon afterward, the same scholar obtained two polynomials representing primes and only primes, one in 24 and one in 21 variables [Mat71]; in [MR75], Matiyasevich and Julia Robinson brought the number of variables down to 14; then other researchers succeeded in bringing it further down, to 12 (cf. [JSWW76]). The record number, 10 as of today, was achieved by Matiyasevich in 1977: in fact, [Mat81] produces a prime-generating polynomial in 10 variables, of degree 15905 (reducible to 13201 (13983?) or to 11281 [Mat81, p. 44], or even to 10001 [Vse97, p. 3204]).
Although methods have signi cantly evolved over time, the rigmarole for getting prime-representing polynomials usually results from the combination of ideas already present in [Rob52] (see Fig. 1) with a Diophantine polynomial speci cation of exponentiation, such as the masterpiece proposed in [MR75] (see Fig. 2), which Maxim A. Vsemirnov re ned somewhat in [Vse97]. a = r j
$ j! =
a = $ rj % r j (u + 1)r uj
% u & u = 2r + 1 for any r > (2 j)j+1 : 9 x ; y p = (x + 2) (y + 2) _ p = 0 _ p = 1 $ 9 q ; u ; v p = q + 2 & p u (q + 1)! v = 1
Ameliorations along this pipeline are possible: e.g., Wilson's theorem enables one to state that p is a prime number through the formula 9 q ; u p = q + 2 & p u (q + 1)! = 1 ; and an improved exponential Diophantine representation of the binomial coe cient can be obtained through the theorem r j = (u + 1)r uj
% u for r > 0 ; j > 0 ; and u > rj ; as remarked in [MR75, pp. 544{545]. However, a more decisive enhancement in the formulation of a prime-generating polynomial would ensue if one could remove factorial from the pipeline and could avoid exploiting the binomial coefcient in its full strength.
Joseph Wolstenholme proved the congruence 2pp 11 1 mod p3 for all prime numbers p > 3 in 1862 [Wol62]; and it was conjectured by James P. Jones (cf. [Rib04, p. 23] and [McI95, p. 381]) that, conversely, every integer p > 3 satisfying the said congruence is prime. If true, this conjecture would ease our Q = $Def
Q = h2 for some h 2 N ; X j Y $Def Y =
h X for some h 2 N : A1 D F I = , F j H A2 D (A2 1) C2 + 1 A3 E 2 (i + 1) C2 D A4 F (A2 1) E2 + 1 A5 G (F A) F + A A6 H B + 2 j C A7 I (G2 1) H2 + 1
C , B 6 C E1 (M 2
E2 L2 E3 M E4 L E5 A E6 B E7 C
1) L2 + 1 = 4 (C L y)2 x y n > 0 4 n (y + 1) + x + 2 n + 1 + ` (M 1) M x n + 1 k + B present task, enabling us to express primality without factorial and in terms of the central binomial coe cient 2pp .
After recalling, in Sec. 1 the basic de nitions and techniques we need, in Sec. 2 we produce a Diophantine polynomial generator in 8 variables for the numbers meeting the just mentioned `Wolstenholme's pseudoprimality' criterion. In Sec. 3, we give clues about the proof that the proposed polynomial operates properly. In the conclusions, we brie y discuss the autonomous signi cance of our speci cation independently of Jones's conjecture, and address the issue of determining a lower bound for the number of variables in a polynomial representation of primality. 1
Main de nitions and presupposed notions Let us recall here the notion of Diophantine representation of a relation R, which historically played an essential role in the study of Hilbert's 10th problem: De nition 1. A relation R among n natural numbers is said to be Diophantine if one can precisely characterize which are the n-tuples ha1; : : : ; ani constituting R through a bi-implication of the form
R(a1; : : : ; an) $ 9 x1 9 xm
variables D(za1; : : : ; an };|x1; : : : ; xm{ ) = 0 |para{mzeters} | unk{nzowns } which musto be true under the replacement a1 7! a1 ; : : : ; an 7! an, where D is a polynomial with coe cients in Z whose variables are seen as ranging over N. In the common case when n = 1 one calls such an R a Diophantine set, and one readily gets from the de ning D the polynomial (x0 +1) 1 D2(x0; : : : ; xm) 1, whose non-negative values (under replacement of the variables x0; : : : ; xm by natural numbers x0; : : : ; xm) are precisely the elements of R.
For example, classical results on the so-called Pell equation tell us that the equation x2 d (y + 1)2 1 = 0 in the parameter d and in the unknowns x; y makes a Diophantine representation of the set
R = f 0 g [ f d 2 N j d is not a perfect square g ; therefore the non-negative values of the polynomial of pairs whose rst and second components constitute the respective increasing progressions a(0); a(1), a(2); : : : and a(0); a(1); : : : shown in Fig. 3 (the latter was formerly introduced in the caption of Fig. 2). Figures 4, 5 recapitulate important properties enjoyed by these sequences. To be better aligned with [Vse97], let us now agree that the variables appearing in our Diophantine constraints must range over positive (instead of non-negative) integers. A re ned polynomial speci cation of the components which occupy odd positions b in the progression a(b) = c discussed above is shown in Fig. 6 (right) and in Fig. 7 (left); in Fig. 7 (right) we extend it into an alike speci cation, to be discussed next, of Wolstenholme's pseudoprimality. In addition to the 6 unknowns z; w; s; h; i; j which appear explicitly in this system of Diophantine constraints, additional unknowns enter into play due to the presence of the constructs ` ', `>', `j', and of a congruence. Eliminating such abbreviations seems, at rst glance, to call for ve extra variables; a single, 7-th unknown su ces, though, thanks to the following proposition: Theorem 1 (Relation-combining theorem, [MR75, pp. 525{527]). To each q in N there corresponds a polynomial Mq with coe cients in Z such that, for all integers X1; : : : ; Xq; J; R; V with J 6= 0, the conditions F I are all met if and only if the equation Mq(X1; : : : ; Xq; J; R; V; m) = 0 admits solutions for some value m in N of the variable m. a
This theorem is exploitable in the case at hand, with q = 2, once the two divisibility conditions (one of which is hidden inside the congruence 3 w C 2 (w2 1) mod Q) are combined together by resorting to the double implication d1 j z1 ^ d2 j z2 $ d1 d2 j z1d2 + z2d1 which holds when d1; d2; z1; z2 are positive integers and d1; d2 are co-prime. All in all, we will be able to fold our constraints into a single Diophantine polynomial equation W(k; x1; : : : ; x7) = 0 over N whose degree is 5488 (as will be assessed at the end of Sec. 3) and which admits solutions in the 7 unknowns precisely for those integer values of k which exceed 4 and which also satisfy Wolstenholme's congruence 2kk 2 mod k3.
In order to get rid of the precondition k > 5 (Fig. 7, right), it su ces to strenghten the inequality K2 4 (C K Y )2 > 0 into (k 1) (k 2) (k 3) (k 4) K2 4 (C K Y )2 > 0 before resorting to Thm. 1. Accordingly, denoting by W(k; x1; : : : ; x7) the polynomial equation that results after this preparatory retouch, our conjectured prime-generating polynomial is:
x0 1 (x0 2)2 (x0 3)2 W2(x0; x1; : : : ; x7) : 3
Correctness of our representation of Wolstenholme's pseudoprimality The speci cation of Wolstenholme's pseudoprimality which we are proposing stems from ad hoc modi cations to [Jon82, Lemma 2.25, pp. 556{557]; hence, by bringing into our present discourse the main ingredients entering the proof thereof, we will easily get our main claim, which is:
Theorem 2. Let W(k; z; w; s; h; i; j; m) = 0 be the Diophantine polynomial equation resulting from the system in Fig. 7, right, via Thm. 1. Then the integer values k > 5 for which the congruence 2kk 2 mod k3 holds are precisely the ones for which the equation W(k; z; w; s; h; i; j; m) = 0|where k has superseded the variable k|can be solved relative to the unknowns z; w; s; h; i; j; m. a
First, we need an economical|as for the number of variables involved| representation of the triadic relation A(B) = C. We resort to a slight variant of the one which [Vse97, Lemma 8] proposed for an even number B, because an odd B better ts our present aims.
Lemma 1. Let A; B; C; Q be integers with A > 1, B > 1, C > 1, B odd, and Q > 0. The relationship A(B) = C holds if and only if there exist i; j such that 8DF I = > <
F j H >:B 6 C
C (P2) (P1) (P3)
D E F G H I
2 i C2 D Q
(A + 1) F B + 2 j C
A (P4) (P5) (P6) (P7) (P8) (P9) 2. Y 3 < A , 3. S3B < A , Proof: Minor modi cations to the proof of [Vse97, Lemma 8, pp. 3203{3204] (see also Remark 2 therein) yield the claim of this lemma. In its turn, that proof mimicked the proof of [MR75, Theorem 4, pp. 532{533]. tu
Second, we need a Diophantine representation of exponentiation: Lemma 2. The relationship SB = Y holds for integers S; B; Y with S > 0 if and only if there exist integers A; C such that 1. S < A , 4. A(B) = C , 5. (S2 1) Y C
S (Y 2 1) mod (2 A S
S2
Proof: See [Jon79, Lemma 2.8, pp. 213{214], where this result is credited to Julia Robinson. A key congruence in Jones's proof just cited is which follows easily from Fig. 5 (0), in light of the fact that x = a(n), y = a(n) solves the equation x2 = (a2 1) y2 + 1. Making use of the easy implication
If 0 < ` < a, y3 < a, and z3 < a then, taken together, the congruences substantial changes. Some variables of the cited lemma must be replaced by ours according to the rewritings: B0 B, z, W w, R k, and N k (notice that we are thus enforcing the equality R = N ). Moreover, one should: remove condition (B11) W = b w of the cited lemma; replace its conditions (B9) U = N 2 w and (B10) Y = N 2 s by ours, namely U = k3 w and Y = k3 s + 2; add our condition Q = 4 A 5.
Degree of the polynomial through which we have represented Wolstenholme's pseudoprimality To end, let us calculate the degree of the polynomial W(k; z; w; s; h; i; j; m) discussed above. To more easily get the degrees of the polynomials involved in the right-hand speci cation of Fig. 7, we add a few more abbreviations to it: H B + 2 j C, E 2 i C2 D Q, and G (A + 1) F A; then we get the degree map:
B=1; U=4; Y =4; C=1; M=5; H=2; A=9; P=14;
D=20; Q=9; K=15; E=32; F=82; G=91; I=186:
To complete the assessment of the degree of W, we need to make the polynomial Mq of Thm. 1 rather explicit: according to [MR75],
Mq( X1 ; : : : ; Xq ; J ; R ; V ; m ) =Def
Q 2f0;1gf1;:::;qg J 2 m+ R2
J 2 ( 2 V 1 ) R2 + W q + Pq j=1 ( 1) (j)pXj W j 1 ; where
In the case at hand,
W
1 + Piq=1 Xi2 :
W(k; z; w; s; h; i; j; m) =Def M2( X1 ; X2 ; J ; R ; V ; m); where X1 DF I and X2 Pell(P ; K); hence q = 2 and W 1 + (D F I)2 + (P 2 1) K2 + 1 2. The polynomial V which we using in a statement V > 0 is V K2 4(C K Y )2. The polynomials J; R of which we are stating that J j R, result from combination of the two conditions F j H C and 3 w C 2 (w2 1) mod Q: hence J F Q and R (H C) Q + 2 (w2 1) 3 w C F . The polynomials just introduced have degrees:
W=576; V =38; J=91; R=84 and, consequently, W has the degree deg M2 = 4 deg J 2 ( 2 V
After explaining what it means for a relation %(x1; : : : ; xn) to be Diophantine in a set S, Julia Robinson proved in [Rob69] that every recursively enumerable set is Diophantine in any in nite set of primes. We do not know whether Jones's conjectured converse of Wolstenholme's theorem will be proved, hence we cannot refer Robinson's result just recalled to the set W of all integers k > 5 such that 2kk 2 mod k3, and we feel that it would add to the autonomous signi cance of our polynomial representation of W if we succeeded in showing that every recursively enumerable set is Diophantine in W.
Albeit subject to Jones's conjecture, the result presented in this paper suggests a new estimate for the rank (= least possible number of unknowns in a Diophantine representation) of the set of primes, shifting it down from 9 to 7. Although this was to be expected (cf. [Mat93, p. 56]), we could not nd this result published anywhere.
We would also like to determine a non-trivial lower bound for the rank of primality. Pietro Corvaja gave us clues that the lower bound 2 can be obtained through direct application of Siegel's theorem on integral points (see [Sie29]4).
It is a bit deceiving that we could not bene t from the celebrated [AKS04] for the aims of this paper; an explanation might be that the complexity of primenumber recognition has to do with bounds that one can place on the sizes of the unknowns in a Diophantine representation of primality rather than on the number of those unknowns.
As hinted at above, we had pleasant and pro table exchanges of ideas with prof. Pietro Corvaja (University of Udine). N.B.
AKS04.
CZ02.
Dav58.
Dav73.
Yuri V. Matiyasevich's name was transliterated variously in his publications in English; in this bibliography, the authors have preferred conformity with the spellings found in the originals to uniformity of writing. DMR76. Martin Davis, Yuri Matijasevic, and Julia Robinson. Hilbert's tenth problem. Diophantine equations: positive aspects of a negative solution. In Mathematical Developments Arising From Hilbert Problems, volume 28 of Proceedings of Symposia in Pure Mathematics, pages 323{378, Providence, RI, 1976. American Mathematical Society. Reprinted in [Rob96].
Hil00. David Hilbert. Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker-Kongre zu Paris 1900. Nachrichten von der Konigliche Gesellschaft der Wissenschaften zu Gottingen, pages 253{297, 1900.
Jon79. James P. Jones. Diophantine representation of Mersenne and Fermat primes. Acta Arithmetica, XXXV(3):209{221, 1979.
Jon82. James P. Jones. Universal Diophantine equation. The Journal of Symbolic
Logic, 47(3):549{571, 1982.
JSWW76. James P. Jones, Daihachiro Sato, Hideo Wada, and Douglas Wiens. Diophantine representation of the set of prime numbers. American Mathematical Monthly, 83(6):449{464, 1976.
Mat70. Ju. V. Matijasevic. Diofantovost' perechislimykh mnozhestv. Doklady Akademii Nauk SSSR, 191(2):279{282, 1970. (Russian). (Translated as Ju. V. Matijasevic. Enumerable sets are Diophantine. Soviet Mathematics. Doklady, 11(2):354-358, 1970.).
Mat71. Ju. V. Matijasevic. Diophantine representation of the set of prime numbers.
Soviet Mathematics. Doklady, 12(1):249{254, 1971.
Mat81. Yu. V. Matijasevic. Primes are nonnegative values of a polynomial in 10 variables. Journal of Soviet Mathematics, 15(1):33{44, 1981.
Mat93. Yuri Vladimirovich Matiyasevich. Hilbert's tenth problem. The MIT Press,
Cambridge (MA) and London, 1993.
McI95. Richard J. McIntosh. On the converse of Wolstenholme's theorem. Acta
Arithmetica, LXXI(4):381{389, 1995.
MR75. Yuri Matijasevic and Julia Robinson. Reduction of an arbitrary diophantine equation to one in 13 unknowns. Acta Arithmetica, XXVII:521{553, 1975. Rib04. Paulo Ribenboim. The little book of bigger primes. Springer, 2nd edition, 2004.
Rob52. Julia Robinson. Existential de nability in arithmetic. Transactions of the
American Mathematical Society, 72(3):437{449, 1952.
Rob69. Julia Robinson. Unsolvable Diophantine problems. Proc. Amer. Math. Soc., 22(2):534{538, 1969.
Rob96. Julia Robinson. The collected works of Julia Robinson. Number 6 in Collected Works. American Mathematical Society, Providence, RI, 1996. ISBN 0-8218-0575-4. With an introduction by Constance Reid. Edited and with a foreword by Solomon Feferman. xliv+338 pp.
Sie29. Karl Ludwig Siegel. Uber einige Anwendungen diophantischer Approximationen. Abhandlungen der Preussischer Akademie der Wissenschaften, 1. 1929. An English translation by Clemens Fuchs is available in [Zan14]. Vse97. Maxim Aleksandrovich Vsemirnov. In nite sets of primes, admitting Diophantine representations in eight variables. Journal of Mathematical Sciences, 87(1):3200{3208, 1997.
Wol62. Joseph Wolstenholme. On certain properties of prime numbers. The Quarterly Journal of Pure and Applied Mathematics, 5:35{39, 1862.
Zan14. Umberto Zannier, editor. On some applications of Diophantine approximations. Edizioni della Normale. Scuola Normale Superiore, 2014.