``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
# | 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! |
x = (t / 9) (t9 + 6t6 + 15 t3 + 12), | |
y = t15 / 27 + (t12 + 4t9 + 8t6) / 3 +(5t3+1) / 12, | |
k = -(3t6 + 14t3 + 27) / 108; |