Abstract
The Riemann zeta function on the critical line can be computed using a straightforward application of the Riemann-Siegel formula, Schönhage’s method, or Heath-Brown’s method. The complexities of these methods have exponents 1/2, 3/8, and 1/3 respectively. In this article, three new fast and potentially practical methods to compute zeta are presented. One method is very simple. Its complexity has exponent 2/5. A second method relies on this author’s algorithm to compute quadratic exponential sums. Its complexity has exponent 1/3. The third method, which is our main result, employs an algorithm developed here to compute cubic exponential sums with a small cubic coefficient. Its complexity has exponent 4/13 (approximately, 0.307).
-
[BK]
M. V. Berry and J. P. Keating, "A new asymptotic representation for $\zeta(\frac12+it)$ and quantum spectral determinants," Proc. Roy. Soc. London Ser. A, vol. 437, iss. 1899, pp. 151-173, 1992.@article {BK, MRKEY = {1177749},
AUTHOR = {Berry, M. V. and Keating, J. P.},
TITLE = {A new asymptotic representation for {$\zeta(\frac12+it)$} and quantum spectral determinants},
JOURNAL = {Proc. Roy. Soc. London Ser. A},
FJOURNAL = {Proceedings of the Royal Society. London. Series A. Mathematical, Physical and Engineering Sciences},
VOLUME = {437},
YEAR = {1992},
NUMBER = {1899},
PAGES = {151--173},
ISSN = {0962-8444},
CODEN = {PRLAAZ},
MRCLASS = {11M06 (11M41 11Z50 58F20 81Q50)},
MRNUMBER = {1177749},
MRREVIEWER = {Jack Quine},
DOI = {10.1098/rspa.1992.0053},
ZBLNUMBER = {0776.11048},
} -
[BF] E. Bombieri and J. B. Friedlander, "Dirichlet polynomial approximations to zeta functions," Ann. Scuola Norm. Sup. Pisa Cl. Sci., vol. 22, iss. 3, pp. 517-544, 1995.
@article {BF, MRKEY = {1360548},
AUTHOR = {Bombieri, E. and Friedlander, J. B.},
TITLE = {Dirichlet polynomial approximations to zeta functions},
JOURNAL = {Ann. Scuola Norm. Sup. Pisa Cl. Sci.},
FJOURNAL = {Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie IV},
VOLUME = {22},
YEAR = {1995},
NUMBER = {3},
PAGES = {517--544},
ISSN = {0391-173X},
CODEN = {PSNAAI},
MRCLASS = {11M06 (11M41)},
MRNUMBER = {1360548},
MRREVIEWER = {Kohji Matsumoto},
URL = {http://www.numdam.org/item?id=ASNSP_1995_4_22_3_517_0},
ZBLNUMBER = {0837.11051},
} -
[Da] H. Davenport, Multiplicative Number Theory, Third ed., New York: Springer-Verlag, 2000, vol. 74.
@book {Da, MRKEY = {1790423},
AUTHOR = {Davenport, Harold},
TITLE = {Multiplicative Number Theory},
SERIES = {Grad. Texts in Math.},
VOLUME = {74},
EDITION = {Third},
NOTE = {revised and with a preface by Hugh L. Montgomery},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {2000},
PAGES = {xiv+177},
ISBN = {0-387-95097-4},
MRCLASS = {11-02 (11-01 11Mxx 11Nxx)},
MRNUMBER = {1790423},
ZBLNUMBER = {1002.11001},
} -
[Ed] H. M. Edwards, Riemann’s Zeta Function, Mineola, NY: Dover Publications, 2001.
@book {Ed, MRKEY = {1854455},
AUTHOR = {Edwards, H. M.},
TITLE = {Riemann's Zeta Function},
NOTE = {reprint of the 1974 original [Academic Press, New York; MR0466039]},
PUBLISHER = {Dover Publications},
ADDRESS = {Mineola, NY},
YEAR = {2001},
PAGES = {xiv+315},
ISBN = {0-486-41740-9},
MRCLASS = {11M06 (11M26)},
MRNUMBER = {1854455},
ZBLNUMBER = {1113.11303},
} -
[HB] D. R. Heath-Brown, Private communication to A.M. Odlyzko.
@misc{HB,
author={Heath-Brown, D. R.},
TITLE={Private communication to {A.M. O}dlyzko},
} -
[Hi] G. A. Hiary, "A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals," Ann. of Math., vol. 174, pp. 859-989, 2011.
@article{Hi,
author={Hiary, G. A.},
TITLE={A nearly-optimal method to compute the truncated theta function, its derivatives, and integrals},
journal = {Ann. of Math.},
volume = {174},
year = {2011},
pages = {859--989},
doi = {10.4007/annals.2011.174.2.3},
} -
[Ga] W. Gabcke, Neue Herleitung und explicite Restabschätzung der Riemann-Siegel-Formel, 1979.
@misc{Ga,
author={Gabcke, W.},
TITLE={Neue {H}erleitung und explicite {R}estabschätzung der {R}iemann-{S}iegel-{F}ormel},
NOTE={Ph.D. dissertation, Göttingen},
YEAR={1979},
} -
[GK] S. W. Graham and G. Kolesnik, Van der Corput’s Method of Exponential Sums, Cambridge: Cambridge Univ. Press, 1991, vol. 126.
@book {GK, MRKEY = {1145488},
AUTHOR = {Graham, S. W. and Kolesnik, G.},
TITLE = {van der {C}orput's Method of Exponential Sums},
SERIES = {London Math. Soc. Lecture Note Ser.},
VOLUME = {126},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {1991},
PAGES = {vi+120},
ISBN = {0-521-33927-8},
MRCLASS = {11L07},
MRNUMBER = {1145488},
MRREVIEWER = {Zun Shan},
DOI = {10.1017/CBO9780511661976},
ZBLNUMBER = {0713.11001},
} -
[Od] A. M. Odlyzko, The $10^{20}$-th zero of the Riemann zeta function and 175 million of its neighbors.
@misc{Od,
author = {Odlyzko, A. M.},
TITLE={The $10^{20}$-th zero of the {R}iemann zeta function and 175 million of its neighbors},
URL={www.dtc.umn.edu/~odlyzko},
} -
[OS] A. M. Odlyzko and A. Schönhage, "Fast algorithms for multiple evaluations of the Riemann zeta function," Trans. Amer. Math. Soc., vol. 309, iss. 2, pp. 797-809, 1988.
@article {OS, MRKEY = {0961614},
AUTHOR = {Odlyzko, A. M. and Sch{ö}nhage, A.},
TITLE = {Fast algorithms for multiple evaluations of the {R}iemann zeta function},
JOURNAL = {Trans. Amer. Math. Soc.},
FJOURNAL = {Transactions of the American Mathematical Society},
VOLUME = {309},
YEAR = {1988},
NUMBER = {2},
PAGES = {797--809},
ISSN = {0002-9947},
CODEN = {TAMTAM},
MRCLASS = {11M06 (11M26 11Y35 65E05 68Q25)},
MRNUMBER = {0961614},
MRREVIEWER = {H. J. Godwin},
DOI = {10.2307/2000939},
ZBLNUMBER = {0706.11047},
} -
[Ru] M. Rubinstein, "Computational methods and experiments in analytic number theory," in Recent Rerspectives in Random Matrix Theory and Number Theory, Cambridge: Cambridge Univ. Press, 2005, vol. 322, pp. 425-506.
@incollection {Ru, MRKEY = {2166470},
AUTHOR = {Rubinstein, Michael},
TITLE = {Computational methods and experiments in analytic number theory},
BOOKTITLE = {Recent Rerspectives in Random Matrix Theory and Number Theory},
SERIES = {London Math. Soc. Lecture Note Ser.},
VOLUME = {322},
PAGES = {425--506},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {2005},
MRCLASS = {11Y35 (11M41)},
MRNUMBER = {2166470},
MRREVIEWER = {Robert Juricevic},
DOI = {10.1017/CBO9780511550492.015},
ZBLNUMBER = {1168.11329},
} -
[Sc] A. Schönhage, "Numerik analytischer Funktionen und Komplexität," Jahresber. Deutsch. Math.-Verein., vol. 92, iss. 1, pp. 1-20, 1990.
@article {Sc, MRKEY = {1037441},
AUTHOR = {Sch{ö}nhage, A.},
TITLE = {Numerik analytischer {F}unktionen und {K}omplexität},
JOURNAL = {Jahresber. Deutsch. Math.-Verein.},
FJOURNAL = {Jahresbericht der Deutschen Mathematiker-Vereinigung},
VOLUME = {92},
YEAR = {1990},
NUMBER = {1},
PAGES = {1--20},
ISSN = {0012-0456},
CODEN = {JDMVA7},
MRCLASS = {68Q40 (65E05 68Q25)},
MRNUMBER = {1037441},
MRREVIEWER = {Helmut Alt},
zblnumber = {0797.68090},
} -
[Ti] E. C. Titchmarsh, The Theory of the Riemann Zeta-Function, Second ed., New York: The Clarendon Press Oxford University Press, 1986.
@book {Ti, MRKEY = {0882550},
AUTHOR = {Titchmarsh, E. C.},
TITLE = {The Theory of the {R}iemann Zeta-Function},
EDITION = {Second},
NOTE = {edited and with a preface by D. R. Heath-Brown},
PUBLISHER = {The Clarendon Press Oxford University Press},
ADDRESS = {New York},
YEAR = {1986},
PAGES = {x+412},
ISBN = {0-19-853369-1},
MRCLASS = {11M06},
MRNUMBER = {0882550},
MRREVIEWER = {Matti Jutila},
ZBLNUMBER = {0601.10026},
} -
[Tu] A. M. Turing, "Some calculations of the Riemann zeta-function," Proc. London Math. Soc., vol. 3, pp. 99-117, 1953.
@article {Tu, MRKEY = {0055785},
AUTHOR = {Turing, A. M.},
TITLE = {Some calculations of the {R}iemann zeta-function},
JOURNAL = {Proc. London Math. Soc.},
FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},
VOLUME = {3},
YEAR = {1953},
PAGES = {99--117},
ISSN = {0024-6115},
MRCLASS = {65.0X},
MRNUMBER = {0055785},
MRREVIEWER = {D. H. Lehmer},
DOI = {10.1112/plms/s3-3.1.99},
ZBLNUMBER = {0050.08101},
}
Full Article