From: elkies@abel.math.harvard.edu (Noam Elkies) Newsgroups: sci.math.numberthy Subject: small nonzero |x^3-y^2| findings Date: 17 Aug 98 10:50:55 GMT Announcement: experimental results on Hall's conjecture re |x^3 - y^2| 5853886516781223^3 - 447884928428402042307918^2 = 1641843 Recall that Hall's conjecture [H] asserts that if x and y are positive integers such that k := x^3 - y^2 is nonzero then |k| >> x^(1/2-epsilon), as usual with the implied constant depending on epsilon. It is equivalent to the conjecture that an elliptic curve over Q in its standard minimal model has discriminant >> |a_4|^(1/2-epsilon). Hall's conjecture is now recognized as part of the Masser-Oesterle ABC conjecture [O] (see also [L]). As such, its analogue over function fields is known to be true by Mason's theorem [M]; it follows as in [E1] that the conjecture cannot be *dis*proved by a polynomial parametrization. The conjecture is also supported by more naive/down-to-earth heuristics; for instance, if we let x, y range over [N/2,N] and [1,N^(3/2)] respectively, we get c N^(5/2) values of k in [-N^3,N^3]; except for the pairs (x,y)=(u^2,u^3) for which k=0, we expect these k to be about randomly distributed, so the smallest in absolute value should be of the order of sqrt(N) or so. Known theoretical results in the direction of Hall's conjecture are far from satisfactory. Because for each nonzero k the elliptic curve E_k: y^2 = x^3 - k has only finitely many integral points, |k| must grow with x; but even the best explicit upper bounds available on the heights of integral points do not yield |k| >> x^delta for any positive delta. In the other direction it is only known that |k| can be as small as (c+o(1)) sqrt(x) for infinitely many (x,y), where c = 5^(-5/2) * 54 = .96598..., using an infinite family parametrized by solutions of a "Pell equation"; this is due to Danilov [D] (see also [S, p.268]). This family was related with the cover of modular curves X_0(5)/X(1) in [E2, section 4], where it is also noted as an amusing consequence that in every known infinite family of elliptic curves with discriminant << sqrt(|a_4|) each curve admits a rational 5-isogeny. The conjecture has also been subjected to some experimental work, i.e. searches for (x,y) with small k. Of course it is enough to specify x because only one y value is feasible, namely the integer nearest to x^(3/2), and indeed k is essentially 2 x^(3/2) times the difference between y and x^(3/2). Our expectation that (unless x=u^2) the fractional parts of x^(3/2) should be equidistributed in [0,1] again corroborates the conjecture that k can be as small as x^(1/2) but not much smaller. [Standard techniques of analytic number theory can in fact prove that these fractional parts are asymptotically equidisitributed, but do not say enough about how quickly the distribution becomes uniform to shed much light on Hall's Conjecture; in fact we shall note that our new experimental approach also yields new theoretical results about this equidistribution.] We thus measure the quality of an example of x^3 - y^2 = k with small nonzero k by the size of the ratio r := sqrt(x) / |k|. Clearly one can, in time N^(1+epsilon), try all x in [1,N], as Hall did originally. More recently Gebel, Petho, and Zimmer [GPZ] investigated the arithmetic of the elliptic curves E_k for |k| <= 10^5, and in particular determined all integer points on these curves. They were thus able to list all solutions of x^3 - y^2 = k with 0 < |k| <= 10^5 and |k| < sqrt(x) [i.e. r>1]. They found 13 such solutions (listed below); the largest r's that occur are r = 4.255670- for (x,y,k)=(5234,378661,-17), and r = 4.87080+ for (x,y,k) = (28187351,149651610621,-1090). It is unfortunately not clear even heuristically how much computation this method requires to try all k in [-K,K]; the time is probably K^(c+o(1)) for some c strictly exceeding 1, and thus (if we believe Hall's Conjecture) takes time N^(c'+o(1)) to try all x <= N where c' = c/2 exceeds 1/2, though may be smaller than 1. During the past year I found a new algorithm that provably finds all solutions of |x^3-y^2| << x with x in [1,N] in time only N^(1/2+epsilon). I programmed this algorithm in 64-bit C and ran it for about three weeks on a Sparc Ultra-1 to reach N = 10^18. [A direct exhaustive search over x would only reach to about 10^12 in the same time.] I found 11 new cases of r>1 in that range, including one with r = 46.6, almost 10 times the old record. A further example with r = 6.5 is now the second largest known. Assuming no programming bugs etc., the following 24 examples constitute the full list of solutions of 0<|x^3-y^2|1 list.] The analysis of the algorithm also yields the result that the number of solutions of |x^3-y^2| << x with x in [1,N] is O(sqrt(N)log(N)); equivalently, that the number of x in that interval with x^(3/2) within O(1/sqrt(N)) of an integer is O(sqrt(N)log(N)); more generally, that for each positive rational number c and any interval I in R/Z of length |I| >> 1/sqrt(N), the number of integers x in [1,N] such that (sqrt(c x^3) mod 1) is in I is O( |I| N log(N)), the implied constant depending effectively on c. With a little more work I also show that this number is >> |I| N - O(sqrt(N)). This seems to considerably improve on results available using standard analytic tools. The algorithms readily parallelizes, so extending the search to 10^22 or even 10^24 would be feasible given enough available computer time. Details of the algorithm and analytic results will appear elsewhere. --Noam D. Elkies (elkies@math.harvard.edu) Dept. of Mathematics, Harvard University [D] Danilov, L.V.: The Diophantine equation x^3 - y^2 = k and Hall's conjecture, _Math. Notes Acad. Sci. USSR_ #32 (1982), 617-618. [E1] Elkies, N.D.: ABC implies Mordell, _International Math. Research Notices_ 1991 #7, 99-109. [E2] Elkies, N.D.: Elliptic and modular curves over finite fields and related computational issues. Pages 21-76 in _Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A.O.L. Atkin_ (D.A. Buell and J.T. Teitelbaum, eds.; AMS/International Press, 1998). [GPZ] Gebel, J., Peth\"o, A., and Zimmer, H.G.: On Mordell's equation, _Compositio Math._ #110 (1998), 335--367. [H] Hall, M.: The Diophantine equation x^3 - y^2 = k. In _Computers in Number Theory_ (A.Atkin, B.Birch, eds.; Academic Press, 1971). [M] Mason, R.C.: _Diophantine Equations over Function Fields_, London Math. Soc. Lecture Notes Series #96, Cambridge Univ. Press, 1984. See also pages 149-157 in Springer LNM #1068 (1984) [=proceedings of Journ\'ees Arithm\'etiques 1983, Noordwijkerhout]. [L] Lang, S.: Old and new conjectured diophantine inequalities, _Bull. AMS_ #23 (1990), 37-75. [O] Oesterl\'e, J.: Nouvelles approches du ``theoreme'' de Fermat, _Sem. Bourbaki_ 2/88, expose' #694. [S] Silverman, J.: _ The Arithmetic of Elliptic Curves_. New York: Springer, 1985 (GTM 106).