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
Additional Information
- William Hart
- Affiliation: Technische Universität Kaiserslautern, Fachbereich Mathematik, Postfach 3049, 67653 Kaiserslautern, Germany
- MR Author ID: 777249
- Email: goodwillhart@googlemail.com
- David Harvey
- Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, New South Wales 2052, Australia
- MR Author ID: 734771
- ORCID: 0000-0002-4933-658X
- Email: d.harvey@unsw.edu.au
- Wilson Ong
- Affiliation: University of Cambridge, Department of Engineering, Information Engineering Division, Trumpington Street, Cambridge, CB2 1PZ, United Kingdom
- MR Author ID: 1001021
- Email: wo218@cam.ac.uk
- Received by editor(s): May 29, 2016
- Published electronically: March 3, 2017
- © Copyright 2017 by the authors
- Journal: Math. Comp. 86 (2017), 3031-3049
- MSC (2010): Primary 11R18, 11Y40
- DOI: https://doi.org/10.1090/mcom/3211
- MathSciNet review: 3667037