Dealing with natural numbers, the following question can be raised: how close a square and a cube can be? The difference x3- y2 can be exactly zero when x is a perfect square, but in other cases, it seems difficult to achieve low absolute values. Marshall Hall [1] conjectured that the order of the non zero difference in absolute value can not be less than x1/2 . More preciselly, the conjecture may be formulated as follows: "For any exponent e < 1/2 , a constant Ke > 0 exists such that | x3 - y2 | > Kexe ". As much as , at present, this conjecture is neither proved nor disproved, it is interesting to enumerate the known cases when k = | x3 - y2 | < x1/2 , what we may address as good examples of Hall's conjecture borrowing notation used for the related and more general ABC conjecture . A detailed theoretical and computational account on this subject can be found in a Noam D. Elkies paper [2] , besides an abstract posted in his web page where he presents a table with 25 good examples of Hall's conjecture. L.V. Danilov [3] reported a infinite family with k < 217 sqrt(2) x^{1/2}. N.D. Elkies improved the Danilov method presenting a infinite family of examples with k ~= 0.966 x^{1/2}. Simplifying, we can attribute the first 13 items of the table to J. Gebel, A. Pethö and H.G. Zimmer [4]. They developed an algorithm to search for all integer points in the elliptic curves y2 = x3 + k for |k| < 100 000. The other 11 items where found by N.D. Elkies using base reduction algorithms.
German Sáez and Javier Herranz of the "Universitat Politecnica de Catalunya" and I have developed a new algorithm based in methods related to those used in [5] that have raised to 38 the items of the good examples of Hall's conjecture table. Very briefly, the method starts from the fact that for x=t2 and t integer, k is zero. If we consider rational values of t instead, and the integer values near x0=round(t2 ), we find that the points (x,k) correspond to the integer points of a set of cubic polynomials (see figure for t=222272/15). Knowing the polynomials, we can select those which may contain a integer point with a small k. The algorithm is probabilistic in the sense that it seeks for good examples of Hall's conjecture where they can be found with higher probability. Nevertheless, the algorithm has found all the items known till now plus 10 new items which are displayed in the table bellow. One of them, the item #16, omited in the Elkies table due to a transcription error , was found using the new algorithm. The table contains the parameter r = sqrt(x)/k for each x value. The values of y and k are not listed because they can be easily computed from x , taking y as the nearest integer to x3/2 .
The algorithm was programmed as a PARI script that was translated to C and compiled with the utility GP2C . The executable was run in a Pentium III at 1000 Mhz during about 30 days. I am gratefull aknowledged to the LABORATORIO DE ASTRONOMIA Y FÍSICA FUNDAMENTAL of the "Instituto Nacional de Técnica Aeroespacial" at Villafranca del Castillo, Madrid (Spain) to allow me to use their computing facilities. You can download the PARI script .
Table: Good examples of Hall's conjecture
==================================
# x
r
==================================
1 2
1.41
2 5234
4.26 GPZ
3 8158
3.76 GPZ
4 93844
1.03 GPZ
5 367806
2.93 GPZ
6 421351
1.05 GPZ
7 720114
3.77 GPZ
8 939787
3.16 GPZ
9 28187351
4.38 GPZ
10 110781386
1.23 GPZ
11 154319269
1.08 GPZ
12 384242766
1.34 GPZ
13 390620082
1.33 GPZ
14 3790689201
2.20 GPZ
15 65589428378
2.19 E
16 952764389446
1.15 E
17 12438517260105
1.27 E
18 35495694227489
1.15 E
19 53197086958290
1.66 E
20 5853886516781223
46.60 E
21 12813608766102806
1.30 E
22 23415546067124892
1.46 E
23 38115991067861271
6.50 E
24 322001299796379844
1.04 E
25 471477085999389882
1.38 E
26 810574762403977064
4.66 E
27 9870884617163518770
1.90 JHS
28 42532374580189966073
3.47 JHS
29 51698891432429706382
1.75 JHS
30 44648329463517920535
1.79 JHS
31 231411667627225650649
3.71 JHS
32 601724682280310364065
1.88 JHS
33 4996798823245299750533
2.17 JHS
34 14038790674256691230847 1.27
JHS
35 77148032713960680268604 10.18 J.B. (JHS)
36 180179004295105849668818 5.65 J.B. (JHS)
37 372193377967238474960883 1.33 JHS
38 2028871373185892500636155 1.14 J.B. (JHS)
GPZ - J. Gebel, A. Pethö and H.G.Zimmer.
E - Noam D. Elkies
JHS - I. Jiménez, J. Herranz and G. Sáez.
J.B. - Johan Bosman (using the software of JHS)
[1] Hall, M.: The Diophantine equation x3 - y2 = k . Pages 173-198 in Computers in Number Theory (A. Atkin, B. Birch, eds.; Academic Press, 1971).
[2] Elkies, N.D.: Rational points near curves and small nonzero | x3 - y2 | via lattice reduction.
[3] Danilov, L.V.: The Diophantine equation x3 - y2 = k and Hall's conjecture, Math. Notes Acad. Sci. USSR 32 (1982), 617-618.
[4] Gebel, J., Pethö, A., and Zimmer, H.G.: On Mordell's equation, Compositio Math. 110 (1998), 335-367.
[5] Jiménez Calvo, I. and Sáez Moreno, G.: Approximate Power
roots in Zm. Pages 310-323 in Information Security
(Proccedings of ISC 2001; G.I. Davida and Y. Frankel, eds.; Berlin:
Springer, 2001; LNCS 2200).
Homepage of Ismael Jiménez Calvo