Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

Irregular primes to two billion


Authors: William Hart, David Harvey and Wilson Ong
Journal: Math. Comp. 86 (2017), 3031-3049
MSC (2010): Primary 11R18, 11Y40
DOI: https://doi.org/10.1090/mcom/3211
Published electronically: March 3, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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.
  • [2] 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, https://doi.org/10.2307/2152942
  • [3] 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, https://doi.org/10.1006/jsco.1999.1011
  • [4] 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, https://doi.org/10.2307/2153086
  • [5] J. P. Buhler and D. Harvey, Irregular primes to 163 million, Math. Comp. 80 (2011), no. 276, 2435-2444. MR 2813369, https://doi.org/10.1090/S0025-5718-2011-02461-0
  • [6] Mustapha Chellali, Accélération de calcul de nombres de Bernoulli, J. Number Theory 28 (1988), no. 3, 347-362 (French). MR 932380, https://doi.org/10.1016/0022-314X(88)90047-9
  • [7] 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, https://doi.org/10.2307/2008413
  • [8] I. J. Good, The interaction algorithm and practical Fourier analysis, J. Roy. Statist. Soc. Ser. B 20 (1958), 361-372. MR 0102888
  • [9] David Harvey, A cache-friendly truncated FFT, Theoret. Comput. Sci. 410 (2009), no. 27-29, 2649-2658. MR 2531107, https://doi.org/10.1016/j.tcs.2009.03.014
  • [10] David Harvey, A multimodular algorithm for computing Bernoulli numbers, Math. Comp. 79 (2010), no. 272, 2361-2370. MR 2684369, https://doi.org/10.1090/S0025-5718-2010-02367-1
  • [11] David Harvey, Faster arithmetic for number-theoretic transforms, J. Symbolic Comput. 60 (2014), 113-119. MR 3131382, https://doi.org/10.1016/j.jsc.2013.09.002
  • [12] Wells Johnson, On the vanishing of the Iwasawa invariant $ \mu _{p}$ for $ p<8000$, Math. Comp. 27 (1973), 387-396. MR 0384748
  • [13] Wells Johnson, Irregular primes and cyclotomic invariants, Math. Comp. 29 (1975), 113-120. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR 0376606
  • [14] V. V. Kobelev, A proof of Fermat's theorem for all prime exponents less than $ 5500$., Dokl. Akad. Nauk SSSR 190 (1970), 767-768 (Russian). MR 0258717
  • [15] 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, https://doi.org/10.1515/crll.1850.40.130
  • [16] 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.
  • [17] 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).
  • [18] H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341-348. MR 0351045
  • [19] 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
  • [20] D. H. Lehmer, Automation and pure mathematics, Applications of Digital Computers (W. F. Freiberger and W. Prager, eds.), Ginn, Boston, Mass, 1963.
  • [21] 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 0061128
  • [22] C. M. Rader, Discrete Fourier transforms when the number of data samples is prime, Proc. IEEE 56 (1968), no. 6, 1107-1108.
  • [23] 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 0072892
  • [24] M. A. Shokrollahi, Computation of irregular primes up to eight million (preliminary report), Tech. Report TR-96-002, International Computer Science Institute, Berkeley, 1996.
  • [25] 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.
  • [26] 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.
  • [27] Jonathan W. Tanner and Samuel S. Wagstaff Jr., New congruences for the Bernoulli numbers, Math. Comp. 48 (1987), no. 177, 341-350. MR 866120, https://doi.org/10.2307/2007895
  • [28] The Condor team, Condor software package, http://research.cs.wisc.edu/htcondor/.
  • [29] L. H. Thomas, Using a computer to solve problems in physics, Applications of Digital Computers (1963), 44-45.
  • [30] Joris van der Hoeven, The truncated Fourier transform and applications, ISSAC 2004, ACM, New York, 2004, pp. 290-296. MR 2126956, https://doi.org/10.1145/1005285.1005327
  • [31] H. S. Vandiver, On Bernoulli's numbers and Fermat's last theorem, Duke Math. J. 3 (1937), no. 4, 569-584. MR 1546011, https://doi.org/10.1215/S0012-7094-37-00345-4
  • [32] 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 0062758
  • [33] Samuel S. Wagstaff Jr., The irregular primes to $ 125000$, Math. Comp. 32 (1978), no. 142, 583-591. MR 0491465
  • [34] Lawrence C. Washington, Introduction to cyclotomic fields, 2nd ed., Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1997. MR 1421575

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11R18, 11Y40

Retrieve articles in all journals with MSC (2010): 11R18, 11Y40


Additional Information

William Hart
Affiliation: Technische Universität Kaiserslautern, Fachbereich Mathematik, Postfach 3049, 67653 Kaiserslautern, Germany
Email: goodwillhart@googlemail.com

David Harvey
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, New South Wales 2052, Australia
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
Email: wo218@cam.ac.uk

DOI: https://doi.org/10.1090/mcom/3211
Received by editor(s): May 29, 2016
Published electronically: March 3, 2017
Article copyright: © Copyright 2017 by the authors

American Mathematical Society