Irregular primes to two billion

Hart, William; Harvey, David; Ong, Wilson

doi:10.1090/mcom/3211

Irregular primes to two billion
HTML articles powered by AMS MathViewer

by William Hart, David Harvey and Wilson Ong PDF

Math. Comp. 86 (2017), 3031-3049

Abstract:

We compute all irregular primes less than $2^{31} = 2 147 483 648$. We verify the Kummer–Vandiver conjecture for each of these primes, and we check that the $p$-part of the class group of $\mathbf {Q}(\zeta _p)$ has the simplest possible structure consistent with the index of irregularity of $p$. Our method for computing the irregular indices saves a constant factor in time relative to previous methods, by adapting Rader’s algorithm for evaluating discrete Fourier transforms.

References

L. Bluestein, A linear filtering approach to the computation of discrete Fourier transform, Audio and Electroacoustics, IEEE Transactions on 18 (1970), no. 4, 451–455.
J. Buhler, R. Crandall, R. Ernvall, and T. Metsänkylä, Irregular primes and cyclotomic invariants to four million, Math. Comp. 61 (1993), no. 203, 151–153. MR 1197511, DOI 10.1090/S0025-5718-1993-1197511-5
Joe Buhler, Richard Crandall, Reijo Ernvall, Tauno Metsänkylä, and M. Amin Shokrollahi, Irregular primes and cyclotomic invariants to 12 million, J. Symbolic Comput. 31 (2001), no. 1-2, 89–96. Computational algebra and number theory (Milwaukee, WI, 1996). MR 1806208, DOI 10.1006/jsco.1999.1011
J. P. Buhler, R. E. Crandall, and R. W. Sompolski, Irregular primes to one million, Math. Comp. 59 (1992), no. 200, 717–722. MR 1134717, DOI 10.1090/S0025-5718-1992-1134717-4
J. P. Buhler and D. Harvey, Irregular primes to 163 million, Math. Comp. 80 (2011), no. 276, 2435–2444. MR 2813369, DOI 10.1090/S0025-5718-2011-02461-0
Mustapha Chellali, Accélération de calcul de nombres de Bernoulli, J. Number Theory 28 (1988), no. 3, 347–362 (French). MR 932380, DOI 10.1016/0022-314X(88)90047-9
R. Ernvall and T. Metsänkylä, Cyclotomic invariants for primes between $125\,000$ and $150\,000$, Math. Comp. 56 (1991), no. 194, 851–858. MR 1068819, DOI 10.1090/S0025-5718-1991-1068819-7
I. J. Good, The interaction algorithm and practical Fourier analysis, J. Roy. Statist. Soc. Ser. B 20 (1958), 361–372. MR 102888
David Harvey, A cache-friendly truncated FFT, Theoret. Comput. Sci. 410 (2009), no. 27-29, 2649–2658. MR 2531107, DOI 10.1016/j.tcs.2009.03.014
David Harvey, A multimodular algorithm for computing Bernoulli numbers, Math. Comp. 79 (2010), no. 272, 2361–2370. MR 2684369, DOI 10.1090/S0025-5718-2010-02367-1
David Harvey, Faster arithmetic for number-theoretic transforms, J. Symbolic Comput. 60 (2014), 113–119. MR 3131382, DOI 10.1016/j.jsc.2013.09.002
Wells Johnson, On the vanishing of the Iwasawa invariant $\mu _{p}$ for $p<8000$, Math. Comp. 27 (1973), 387–396. MR 384748, DOI 10.1090/S0025-5718-1973-0384748-5
Wells Johnson, Irregular primes and cyclotomic invariants, Math. Comp. 29 (1975), 113–120. MR 376606, DOI 10.1090/S0025-5718-1975-0376606-9
V. V. Kobelev, A proof of Fermat’s theorem for all prime ewponents less that $5500$. , Dokl. Akad. Nauk SSSR 190 (1970), 767–768 (Russian). MR 0258717
E. E. Kummer, Allgemeiner Beweis des Fermatschen Satzes, daßdie Gleichung $x^\lambda +y^\lambda =z^\lambda$ durch ganze Zahlen unlösbar ist, für alle diejenigen Potenz-Exponenten $\lambda$ welche ungerade Primzahlen sind und in den Zählern der ersten $1/2(\lambda )$ Bernoullischen zahlen als Factoren nicht vorkommen, J. Reine Angew. Math. 40 (1850), 130–138 (German). MR 1578681, DOI 10.1515/crll.1850.40.130
E. E. Kummer, Mémoire sur la théorie des nombres complexes composés de racines de l’unité et de nombres entiers, J. Math. Pure Appl 16 (1851), 377–498.
E. E. Kummer, Über diejenigen Primzahlen $\lambda$, für welche die Klassenzahl der aus $\lambda ^{\text {ten}}$ Einheitswurzeln gebildeten complexen Zahlen durch $\lambda$ teilbar ist., Berl. Monatsber. (1874), 239–248 (German).
H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341–348. MR 351045, DOI 10.1007/BF01436917
Serge Lang, Cyclotomic fields I and II, 2nd ed., Graduate Texts in Mathematics, vol. 121, Springer-Verlag, New York, 1990. With an appendix by Karl Rubin. MR 1029028, DOI 10.1007/978-1-4612-0987-4
D. H. Lehmer, Automation and pure mathematics, Applications of Digital Computers (W. F. Freiberger and W. Prager, eds.), Ginn, Boston, Mass, 1963.
D. H. Lehmer, Emma Lehmer, and H. S. Vandiver, An application of high-speed computing to Fermat’s last theorem, Proc. Nat. Acad. Sci. U.S.A. 40 (1954), 25–33. MR 61128, DOI 10.1073/pnas.40.1.25
C. M. Rader, Discrete Fourier transforms when the number of data samples is prime, Proc. IEEE 56 (1968), no. 6, 1107–1108.
J. L. Selfridge, C. A. Nicol, and H. S. Vandiver, Proof of Fermat’s last theorem for all prime exponents less than $4002$, Proc. Nat. Acad. Sci. U.S.A. 41 (1955), 970–973. MR 72892, DOI 10.1073/pnas.41.11.970
M. A. Shokrollahi, Computation of irregular primes up to eight million (preliminary report), Tech. Report TR-96-002, International Computer Science Institute, Berkeley, 1996.
R. W. Sompolski, The second case of Fermat’s last theorem for fixed irregular prime exponents, Ph.D. thesis, University of Illinois at Chicago, 1991.
E. T. Stafford and H. S. Vandiver, Determination of some properly irregular cyclotomic fields, Proceedings of the National Academy of Sciences 16 (1930), no. 2, 139–150.
Jonathan W. Tanner and Samuel S. Wagstaff Jr., New congruences for the Bernoulli numbers, Math. Comp. 48 (1987), no. 177, 341–350. MR 866120, DOI 10.1090/S0025-5718-1987-0866120-4
The Condor team, Condor software package, http://research.cs.wisc.edu/htcondor/.
L. H. Thomas, Using a computer to solve problems in physics, Applications of Digital Computers (1963), 44–45.
Joris van der Hoeven, The truncated Fourier transform and applications, ISSAC 2004, ACM, New York, 2004, pp. 290–296. MR 2126956, DOI 10.1145/1005285.1005327
H. S. Vandiver, On Bernoulli’s numbers and Fermat’s last theorem, Duke Math. J. 3 (1937), no. 4, 569–584. MR 1546011, DOI 10.1215/S0012-7094-37-00345-4
H. S. Vandiver, Examination of methods of attack on the second case of Fermat’s last theorem, Proc. Nat. Acad. Sci. U.S.A. 40 (1954), 732–735. MR 62758, DOI 10.1073/pnas.40.8.732
Samuel S. Wagstaff Jr., The irregular primes to $125000$, Math. Comp. 32 (1978), no. 142, 583–591. MR 491465, DOI 10.1090/S0025-5718-1978-0491465-4
Lawrence C. Washington, Introduction to cyclotomic fields, 2nd ed., Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1997. MR 1421575, DOI 10.1007/978-1-4612-1934-7