Dealing  with natural numbers, the following question can be raised: how close a square and a cube can be? The difference x³- y²  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 x^1/2 . More precisely, the conjecture may be formulated as follows: "For any exponent e < 1/2 , a constant  K_e > 0 exists such that | x³ - y² | > K_ex^e ".  As much as , at present, this conjecture is neither proved nor disproved, it is interesting to enumerate the known cases when k = | x³ - y² |   <  x^1/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²  = x³ + 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=t² and t integer, k is zero. If we consider rational values of t instead, and the integer values near x₀=round(t² ), 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 x^3/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

   A search for values of x for which the values of k is less than 16x^1/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   x³ - y²  = 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 | x³ - y² | via lattice reduction.

[3] Danilov, L.V.: The Diophantine equation   x³ - 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 Z_m. 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