``Hall's conjecture'' asserts that if x and y are positive integers
such that k := x^{3}-y^{2} is nonzero then
|k| > x^{1/2-o(1)}. [M. Hall raised the question of how
small k can be in his paper ``The Diophantine equation
x^{3}-y^{2}=k'' In *Computers in Number Theory*
(A.Atkin, B.Birch, eds.; Academic Press, 1971), though the conjecture
he originally formulated there is the more ambitious (and almost
certainly false) |k| >> x^{1/2}.] It is now recognized as
a special case of the Masser-Oesterlé ``ABC conjecture'' (see
Oesterlé, J.: Nouvelles approches du ``théorème''
de Fermat, *Sém. Bourbaki* 2/88, exposé #694).
Known theoretical results in the direction of Hall's conjecture
are far from satisfactory, but the question has been subject to
considerable experimental work, starting with Hall's original paper.

I have found a new algorithm that finds all solutions of
|k| << x^{1/2} (or indeed of |k| << x)
with x < N in time O(N^{1/2+o(1)}).
I implemented the algorithm in 64-bit C for N=10^{18},
and ran it for almost a month. [The direct algorithm
of trying all x up to N and comparing x^{3} with
the square of the integer nearest x^{3/2} would only reach
to about 10^{12} in that time, finding but one new solution.]
I found 10 new cases of 0 < |k| < x^{1/2} in that range,
including two that improved on the previous record for
x^{1/2} / |k|, one of which breaks the old record
by a factor of nearly 10.

The following table gives the 24 solutions of
0 < |k| < x^{1/2} with x < 10^{18}.
For each solution we list x, k, and r, the latter two being
defined by k=x^{3}-y^{2} and r=x^{1/2} / |k|.
We do not bother to list y, which is always the integer
closest to x^{3/2}. For instance, the top row of our table
implies y = 447884928428402042307918, so

# | k | x | r | |

1 | 1641843 | 5853886516781223 | 46.60 | ! ! |

2 | 30032270 | 38115991067861271 | 6.50 | ! |

3 | -1090 | 28187351 | 4.87 | GPZ |

4 | -193234265 | 810574762403977064 | 4.66 | |

5 | -17 | 5234 | 4.26 | GPZ, P(-3) |

6 | -225 | 720114 | 3.77 | GPZ |

7 | -24 | 8158 | 3.76 | GPZ, P(3) |

8 | 307 | 939787 | 3.16 | GPZ |

9 | 207 | 367806 | 2.93 | GPZ |

10 | -28024 | 3790689201 | 2.20 | GPZ |

11 | -117073 | 65589428378 | 2.19 | |

12 | -4401169 | 53197086958290 | 1.66 | |

13 | 105077952 | 23415546067124892 | 1.46 | * |

14 | -1 | 2 | 1.41 | |

15 | -497218657 | 471477085999389882 | 1.38 | |

16 | -14668 | 384242766 | 1.34 | GPZ, P(-9) |

17 | -14857 | 390620082 | 1.33 | GPZ, P(9) |

18 | -87002345 | 12813608766102806 | 1.30 | |

19 | 2767769 | 12438517260105 | 1.27 | |

20 | -8569 | 110781386 | 1.23 | GPZ |

21 | 5190544 | 35495694227489 | 1.15 | |

22 | -11492 | 154319269 | 1.08 | GPZ |

23 | -618 | 421351 | 1.05 | GPZ |

24 | 548147655 | 322001299796379844 | 1.04 | D |

25 | -297 | 93844 | 1.03 | GPZ, D |

4090263 | 16544006443618 | 0.99 | so close! |

- !!: New record; even the second-best solution with r=6.5 improves on the previous record-holder with r=4.87
- GPZ: 1 < |k| < 10
^{5}, so solution found by J.Gebel, A.Pethö, and H.G.Zimmer

(``On Mordell's Equation'',*Compositio Math.*#110 (1998), 335-367). - D: Danilov's infinite family, with r approaching
5
^{5/2}/ 54=1.035+; the fact that our computation found the second Danilov solution was a welcome sanity check. See

Danilov, L.V.: ``The Diophantine equation x^{3}- y^{2}= k and Hall's conjecture'',

*Math. Notes Acad. Sci. USSR*#32 (1982), 617-618. - P(t): Polynomial family. Let t be an integer congruent
to 3 mod 6, and set
x = (t / 9) (t ^{9}+ 6t^{6}+ 15 t^{3}+ 12),y = t ^{15}/ 27 + (t^{12}+ 4t^{9}+ 8t^{6}) / 3 +(5t^{3}+1) / 12,k = -(3t ^{6}+ 14t^{3}+ 27) / 108;^{4}). Announced by S.Chowla in a letter to B.J.Birch dated 29 September 1961. See the paper by them together with M.Hall and A.Schinzel:

``On the difference x^{3}- y^{2}'',*Norske Vid. Selsk. Forh.*#38 (1965), 65-69.

[If the journal name is not familiar, the full title is ``Det Kongelige Norske Videnskabers Selskab: Forhandlinger''] - *: Obtained from our record solution by multiplying x,y,k by 4,8,64. This reduces r by a factor of 32, but r=46.6 is so large that even a solution 32 times worse still makes it to our table.