Date: Fri, 13 Dec 2002 10:57:06 -0500 Sender: Number Theory List <NMBRTHRY@LISTSERV.NODAK.EDU> From: Noam Elkies <elkies@math.harvard.edu> Subject: Re: Ten new "good examples of Hall's conjecture" Ismael Jimenez Calvo <ltqij04@pinar2.csic.es> writes:
Good Examples of Hall's Conjecture ======================================== # x r [=sqrt(x)/|x^3-y^2|] ======================================== 1 2 1.41 2 5234 4.26 GPZ 3 8158 3.76 GPZ 4 93844 1.03 GPZ [...] 13 390620082 1.33 GPZ 14 3790689201 2.20 GPZ 15 65589428378 2.19 E 16 952764389446 1.15 JHS 17 12438517260105 1.27 E 18 35495694227489 1.15 E 19 53197086958290 1.66 E 20 5853886516781223 46.60 E 21 12813608766102806 1.30 E
#16 was puzzling: how could I have missed it? In fact it turns out that this was in my files from six years ago: % ls -la h6.op -rw-r--r-- 1 elkies snr_fac 128167 Jun 10 1996 h6.op % grep e+00 h6.op -849, -687, -417: 3.773e+00 969, 826, 528: 3.156e+00 5309, 1870, 494: -4.871e+00 10525, 5761, 2365: -1.228e+00 19764, 4386, 730: -1.330e+00 19602, 4362, 728: -1.336e+00 -12423, -11660, -8208: 1.081e+00 -61569, -52560, -33652: 2.197e+00 256104, 169562, 84198: -2.188e+00
-976097, -963963, -713985: -1.145e+00 <<< 3526828, 1518521, 490364: 1.274e+00 5957826, 3581213, 1614484: 1.148e+00 %
The marked line yields x = 976097^2 - 963963 = 952764389446. I don't know how this xample got lost on the way to my tables at <http://www.math.harvard.edu/~elkies/hall.html>; at any rate, thank you for alerting me to the omission.
22 23415546067124892 1.46 E 23 38115991067861271 6.50 E 24 322001299796379844 1.04 E 25 471477085999389882 1.38 E 26 810574762403977064 4.66 E 27 9870884617163518770 1.90 JHS 28 42532374580189966073 3.47 JHS 29 51698891432429706382 1.75 JHS 30 44648329463517920535 1.79 JHS 31 231411667627225650649 3.71 JHS 32 601724682280310364065 1.88 JHS 33 4996798823245299750533 2.17 JHS 34 14038790674256691230847 1.27 JHS 35 372193377967238474960883 1.33 JHS
That's impressive. How does the running time of your approach grow with the upper bound on x? For my algorithm it's sqrt(x)*log^A(x), which means that raising the bound from 10^18 to 10^24 would multiply the time by about 10^3. The hardware and software improvements over my computation, indicated by
The algorithm was programmed as a PARI script that was translated to C and compiled with the utility GP2C. The executable was run in a Pentium III at 1000 Mhz during 30 days.
, are significant, but surely don't amount to three orders of magnitude. It is true that the new computation is not claimed to be exhaustive:
The algorithm is probabilistic in the sense that it seeks for "good examples of Hall's conjecture" where they can be found with higher probability. Nevertheless, the algorithm has found all the items known and 10 more which are displayed in the table
But these observations suggest that the algorithm in fact does catch all the "good examples" in its range, and perhaps it's possible to prove this. Unfortunately, the webpage <http://www.terra.es/personal9/ismaeljc/hall.html>, offered "for more information", does not include details on the algorithm beyond what's in the NMBRTHRY announcement; and the paper
[JS] Jimenez Calvo, I. and Saez Moreno, G.: Approximate Power roots in Z_m. pages 310-323 in ISC 2001; G.I. Davida and Y. Frankel, eds.; Berlin: Springer, 2001; LNCS 2200.
(which may or may not contain enough information to figure out the Jimenez-Herranz-Saez method) is not easy to find. Can you please post/e-mail/URL further details and/or that GP program? One correction:
A detailed theoretical and computational account on this subject can be found in [Elkies] where he published a table with the 25 items known.
Actually (as explained in that paper) infinitely many examples are known, since Danilov exhibited an infinite family of solutions of 0 < sqrt(x) < |x^3-y^2|. The next example in his family has x = 10^30 approximately, well beyond even the range of the [JHS] computation. --Noam D. Elkies