``Hall's conjecture'' asserts that if x and y are positive integers such that k := x3-y2 is nonzero then |k| > x1/2-o(1). [M. Hall raised the question of how small k can be in his paper ``The Diophantine equation x3-y2=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| >> x1/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| << x1/2 (or indeed of |k| << x) with x < N in time O(N1/2+o(1)). I implemented the algorithm in 64-bit C for N=1018, and ran it for almost a month. [The direct algorithm of trying all x up to N and comparing x3 with the square of the integer nearest x3/2 would only reach to about 1012 in that time, finding but one new solution.] I found 10 new cases of 0 < |k| < x1/2 in that range, including two that improved on the previous record for x1/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| < x1/2 with x < 1018. For each solution we list x, k, and r, the latter two being defined by k=x3-y2 and r=x1/2 / |k|. We do not bother to list y, which is always the integer closest to x3/2. For instance, the top row of our table implies y = 447884928428402042307918, so
|x = (t / 9) (t9 + 6t6 + 15 t3 + 12),|
|y = t15 / 27 + (t12 + 4t9 + 8t6) / 3 +(5t3+1) / 12,|
|k = -(3t6 + 14t3 + 27) / 108;|