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: