### List of integers x,y with x<1018, 0 < |x3-y2| < x1/2

``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

58538865167812233 - 4478849284284020423079182 = 1641843.

 # 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!
Notations:

• !!: New record; even the second-best solution with r=6.5 improves on the previous record-holder with r=4.87
• GPZ: 1 < |k| < 105, 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 55/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 x3 - y2 = 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) (t9 + 6t6 + 15 t3 + 12), y = t15 / 27 + (t12 + 4t9 + 8t6) / 3 +(5t3+1) / 12, k = -(3t6 + 14t3 + 27) / 108;
then r = 12/t + O(1/t4). 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 x3 - y2'', 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.