Marshall Hall's conjecture.

Dealing  with natural numbers, the following question can be raised: how close a square and a cube can be? The difference x3- ycan 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 precisely, 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 y = 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,  omitted 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 gratefully acknowledged 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
12 1.41
25234 4.26 GPZ
38158 3.76 GPZ
493844 1.03 GPZ
5367806 2.93 GPZ
6421351 1.05 GPZ
7720114 3.77 GPZ
8939787 3.16 GPZ
928187351 4.87 GPZ
10110781386 1.23 GPZ
11154319269 1.08 GPZ
12384242766 1.34 GPZ
13390620082 1.33 GPZ
143790689201 2.20 GPZ
1565589428378 2.19 E
16952764389446 1.15 E
1712438517260105 1.27 E
1835495694227489 1.15 E
1953197086958290 1.66 E
205853886516781223 46.60 E
2112813608766102806 1.30 E
2223415546067124892 1.46 E
2338115991067861271 6.50 E
24322001299796379844 1.04 E
25471477085999389882 1.38 E
26810574762403977064 4.66 E
279870884617163518770 1.90 JHS
2842532374580189966073 3.47 JHS
2951698891432429706382 1.75 JHS
3044648329463517920535 1.79 JHS
31231411667627225650649 3.71 JHS
32601724682280310364065 1.88 JHS
334996798823245299750533 2.17 JHS
345592930378182848874404 1.38 JHS
3514038790674256691230847 1.27 JHS
3677148032713960680268604 10.18 J.B. (JHS)
37180179004295105849668818 5.65 J.B. (JHS)
38372193377967238474960883 1.33 JHS
39664947779818324205678136 16.53 JHS
402028871373185892500636155 1.14 J.B. (JHS)
4110747835083471081268825856 1.35 JHS
42372239000787342151819465871.38 JHS
433690445383173227306376634720 1.51 JHS
446078673043126084065007902175846955 1.03 JHS

A search for values of x for which the values of k is less than 16x1/2 in absolute value was done. The data can be found here, in a format readable by PARI, in the form of 704 couples of values (x,k). The distribution of the values of k is very close to an uniform distribution as is shown in the plot below.

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 - y = k . Pages 173-198 in Computers in Number Theory (A. Atkin, B. Birch, eds.; Academic Press, 1971).

[3] Danilov, L.V.: The Diophantine equation   x3 - y  = 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).

Last updated: May 9, 2006