The analytic complexity of zeta and $L$-functions after Bombieri: zero-density inputs for the counting-zero method, the $\mathrm{GL}(n)$ ($n\ge 3$) extension, and the exact two-piece Dirichlet polynomial approximation constant

Bombieri's 1997 chapter 'Remarks on the Analytic Complexity of Zeta Functions', building on Bombieri–Friedlander (1995), studies the operational complexity of computing $\zeta(\sigma+it)$ to fixed accuracy through the lengths of Dirichlet polynomials and sums of two such polynomials that can approximate zeta and $L$-functions, and leaves several explicit directions open. One of them — the proposal that a single evaluation of $\zeta(1/2+it)$ fundamentally requires $\gg_\varepsilon t^{1/2-o(1)}$ operations — is excluded here: Hiary's 2011 Annals algorithm computes $\zeta(1/2+it)$ to $\pm t^{-\lambda}$ in $t^{4/13+o(1)}$ operations. The surviving open core, stated here as one problem with a common objective, is: (i) prove the weak zero-density hypothesis $N(1/2+\delta,T;L)=o(T\log T)$ for further natural families of $L$-functions, such as Dedekind zeta functions of arbitrary number fields, which is what the counting-zero lower-bound method needs to apply unconditionally there; (ii) extend the approximate-functional-equation complexity results to $L$-functions on $\mathrm{GL}(n)$ for $n\ge 3$, including two-piece or analogous formulas and matching lower bounds on the required lengths, open even under the appropriate Riemann hypothesis; and (iii) sharpen the two-piece lower bound $xy\gg T^{1-o(1)}$ to the asymptotically exact $xy\ge(1+o(1))T/(2\pi)$, determining the optimal constant and secondary terms.

Background

The Riemann zeta function is defined for $\Re(s)>1$ by $\zeta(s)=\sum_{n\ge 1}n^{-s}$ and continues meromorphically to the whole plane; the vertical strip $0\le\Re(s)\le 1$ is the critical strip and the line $\Re(s)=1/2$ the critical line, where the deepest arithmetic information (the distribution of prime numbers, via the zeros of $\zeta$) concentrates. An $L$-function is a Dirichlet series $L(s)=\sum a_n n^{-s}$ with an Euler product and a functional equation relating $s$ to $1-s$; the main families are Dirichlet $L$-functions, Dedekind zeta functions $\zeta_K$ (the zeta function of a number field $K$, whose logarithmic derivative encodes the distribution of prime ideals of $K$), automorphic $L$-functions $L(s,\pi)$ attached to automorphic representations $\pi$ of $\mathrm{GL}(n)$ (ranked by degree $n$ in the Langlands hierarchy of the general linear group), and the Selberg class, an axiomatic class of $L$-functions satisfying analyticity, Euler product, functional-equation and Ramanujan-type axioms.

A Dirichlet polynomial is a finite sum $\sum_{n\le N}a_n n^{-s}$; its length $N$ measures its computational cost. The classical approximate functional equation (AFE) for zeta — the Riemann–Siegel formula — expresses $\zeta(1/2+it)$ as a main sum of about $t^{1/2}$ terms plus a conjugate copy and a small remainder, so a single evaluation costs $t^{1/2+o(1)}$ arithmetic operations. On the algorithmic side this exponent was lowered over decades: Schönhage's Fast-Fourier-Transform-based method achieved $t^{3/8+o(1)}$, Heath-Brown's method $t^{1/3+o(1)}$, and Hiary's 2011 algorithm, based on fast evaluation of quadratic and cubic exponential sums (sums $\sum e^{if(n)}$ with $f$ a quadratic or cubic polynomial), achieved $t^{4/13+o(1)}$ operations on numbers of $O((\log t)^2)$ bits; Odlyzko–Schönhage had earlier given fast methods for many evaluations along an arithmetic progression.

Bombieri's chapter approaches the opposite, lower-bound side in the same operational model (arithmetic operations on numbers of $O((\log t)^2)$ bits): how short can a Dirichlet polynomial — or a sum of two Dirichlet polynomials of lengths $x$ and $y$, a two-piece approximation — be and still approximate $\zeta(1/2+it)$ (or a general $L$-function) to fixed accuracy throughout $0<t\le T$? Throughout, a two-piece approximation means a sum $P(s)=\sum_{n\le x}a_n n^{-s}+\chi(s)\sum_{n\le y}b_n n^{-1+s}$ (for an $L$-function, with its own functional-equation factor), where $\chi$ is the factor in $\zeta(s)=\chi(s)\zeta(1-s)$, the coefficients satisfy $a_n,b_n=O(n^{o(1)})$, and the lengths are functions $x=x(T)$, $y=y(T)$ of $T$; approximating to fixed accuracy throughout $0<t\le T$ means $\sup_{0<t\le T}|\zeta(1/2+it)-P(1/2+it)|\le\varepsilon$ for a fixed $\varepsilon>0$, of which the sharper tolerance $\pm t^{-\lambda}$ (fixed $\lambda>0$) used by the algorithms above is a special case. Building on Bombieri–Friedlander (1995), which bounded the lengths of the shortest Dirichlet polynomials approximating general $L$-functions satisfying certain conditions, the chapter proves upper bounds on the complexity of exponential type in fixed strips and, conditionally and unconditionally in special cases, lower bounds by the counting-zero method: a short approximate polynomial cannot reproduce the roughly $T\log T$ sign changes of $\zeta(1/2+it)$ in $0<t\le T$, so its length must grow with the zero count. Writing $N(\sigma,T;L)$ for the number of zeros $\rho=\beta+i\gamma$ of $L$ with $\beta\ge\sigma$ and $0<\gamma\le T$, the unconditional application of this method to a family of $L$-functions requires the weak zero-density hypothesis the chapter calls H3: $N(1/2+\delta,T;L)=o(T\log T)$ for every $\delta>0$. The chapter proves a two-piece lower bound of the shape $xy\gg T^{1-o(1)}$ and notes that a refinement is expected to yield the exact relation $xy\ge(1+o(1))T/(2\pi)$, the constant $1/(2\pi)$ being the same as in the Riemann–Siegel balance between the two pieces. GRH below denotes the generalized Riemann hypothesis for the relevant $L$-functions, i.e. that all their nontrivial zeros lie on the critical line.

Problem Statement

Pin down the analytic (operational) complexity of zeta and $L$-functions via Dirichlet-polynomial approximation, resolving the three linked components that Bombieri's chapter leaves open (the chapter's fourth direction, the proposal that $\zeta(1/2+it)$ requires $\gg_\varepsilon t^{1/2-o(1)}$ operations, is excluded because Hiary's $t^{4/13+o(1)}$-operation algorithm refuted it):

(i) Weak zero-density inputs for the counting-zero method. Prove or disprove, for further natural families of $L$-functions beyond $\zeta$ and Dirichlet $L$-functions — the required family being the Dedekind zeta functions $\zeta_K$ of arbitrary number fields $K$, with other natural families welcome but not required — the weak zero-density hypothesis H3: for every $\delta>0$, $N(1/2+\delta,T;\zeta_K)=o(T\log T)$ as $T\to\infty$, where $N(\sigma,T;L)$ counts zeros $\rho=\beta+i\gamma$ of $L$ with $\beta\ge\sigma$ and $0<\gamma\le T$, with the field $K$ fixed (the implied constant may depend on $K$ and $\delta$); this is the input needed to make the counting-zero complexity lower bounds unconditional for those families.

(ii) The $\mathrm{GL}(n)$ extension. Extend the approximate-functional-equation complexity results to the $L$-functions $L(s,\pi)$ attached to automorphic representations $\pi$ of $\mathrm{GL}(n)$, $n\ge 3$: derive suitable approximate functional equations (two-piece or analogous formulas) for $L(s,\pi)$ and prove matching lower bounds on the lengths required for fixed-accuracy approximation, where matching means that the lower bound matches the length required by the derived approximate functional equation up to $T^{o(1)}$ factors, the class covered — the base field and the normalization of $L(s,\pi)$ — being fixed. The extension is open even under strong hypotheses such as the appropriate Riemann hypothesis for those $L$-functions.

(iii) The sharp two-piece constant. Sharpen the two-piece lower bound — for a sum of two Dirichlet polynomials of lengths $x$ and $y$ approximating $\zeta(1/2+it)$ to fixed accuracy throughout $0<t\le T$ — from $xy\gg T^{1-o(1)}$ to the asymptotically exact relation $xy\ge(1+o(1))T/(2\pi)$, determining the precise optimal constant and the exact form of the secondary terms, the relation being attained by a matching two-piece construction.

These three components share one scientific objective: making the operational complexity of $L$-functions rigorous, unconditional and sharp through the Dirichlet-polynomial approximation framework. They are scientifically linked — all three turn on the same counting-zero method, applied to the family of $L$-functions at issue — so they constitute one problem.

References

1. Enrico Bombieri, "Remarks on the Analytic Complexity of Zeta Functions", in Y. Motohashi (ed.), Analytic Number Theory, London Mathematical Society Lecture Note Series 247, Cambridge University Press, 1997, pp. 21-30. DOI: 10.1017/cbo9780511666179.004, https://doi.org/10.1017/cbo9780511666179.004
2. E. Bombieri and J. B. Friedlander, "Dirichlet polynomial approximations to zeta functions", Annali della Scuola Normale Superiore di Pisa - Classe di Scienze (4) 22 (1995), no. 3, pp. 517-544. No DOI registered; full text at Numdam, item ASNSP_1995_4_22_3_517_0, https://numdam.org/item/ASNSP_1995_4_22_3_517_0
3. Ghaith A. Hiary, "Fast methods to compute the Riemann zeta function", Annals of Mathematics (2) 174 (2011), no. 2, pp. 891-946. DOI: 10.4007/annals.2011.174.2.4, arXiv:0711.5005, https://doi.org/10.4007/annals.2011.174.2.4
4. David Mark Lewis, "A computational algorthm for the Hardy function Z(t), utlising sub-sequences of generalised quadratic Gauss sums, with an overall operational complexity O(((t/epsilon)^(1/3))*(log(t))^(2+o(1)))", preprint, arXiv:1711.01928, 2017 (title reproduced as listed on arXiv), https://arxiv.org/abs/1711.01928
5. Arindam Roy and Akshaa Vatwani, "Zeros of partial sums of L-functions", Advances in Mathematics 346 (2019), pp. 467-509. DOI: 10.1016/j.aim.2019.02.009, arXiv:1807.11093, https://doi.org/10.1016/j.aim.2019.02.009
6. Habiba Kadiri and Nathan Ng, "Explicit zero density theorems for Dedekind zeta functions", Journal of Number Theory 132 (2012), no. 4, pp. 748-775. DOI: 10.1016/j.jnt.2011.09.002, arXiv:1201.3932, https://doi.org/10.1016/j.jnt.2011.09.002
7. Jesse Thorner and Asif Zaman, "A zero density estimate for Dedekind zeta functions", International Mathematics Research Notices 2023 (2023), no. 8, pp. 6739-6761. DOI: 10.1093/imrn/rnac015, arXiv:1909.01338, https://doi.org/10.1093/imrn/rnac015
8. János Pintz, "On the Density Hypothesis for the Selberg class", preprint, arXiv:2408.00617, 2024, https://arxiv.org/abs/2408.00617
9. J. Bourgain and B. S. Kashin, "On the uniform approximation of the partial sum of the Dirichlet series by a shorter sum", Mathematical Notes 87 (2010), no. 1-2, pp. 285-286. DOI: 10.1134/S0001434610010360, https://doi.org/10.1134/S0001434610010360
10. Jean Bourgain and Boris S. Kashin, "Uniform approximation of partial sums of a Dirichlet series by shorter sums and Phi-widths", Sbornik: Mathematics 203 (2012), no. 12, pp. 1736-1760. DOI: 10.1070/sm2012v203n12abeh004285, https://doi.org/10.1070/sm2012v203n12abeh004285
11. Athanasios Sourmelidis, Jörn Steuding, and Ade Irma Suriajaya, "Riemann-type functional equations: Dirichlet polynomial approximations and a weak Gram law", Acta Arithmetica 204 (2022), no. 2, pp. 97-113. DOI: 10.4064/aa210111-13-4, https://doi.org/10.4064/aa210111-13-4
12. Juan Arias de Reyna, "On the approximation of the zeta function by Dirichlet polynomials", preprint, arXiv:2406.16667, 2024, https://arxiv.org/abs/2406.16667
13. Jerzy Kaczorowski and Alberto Perelli, "On the structure of the Selberg class, VII: 1 < d < 2", Annals of Mathematics 173 (2011), no. 3, pp. 1397-1441. DOI: 10.4007/annals.2011.173.3.4, https://doi.org/10.4007/annals.2011.173.3.4
14. A. M. Odlyzko and A. Schoenhage, "Fast algorithms for multiple evaluations of the Riemann zeta function", Transactions of the American Mathematical Society 309 (1988), no. 2, pp. 797-809. DOI: 10.1090/S0002-9947-1988-0961614-2, https://doi.org/10.1090/S0002-9947-1988-0961614-2
15. Jiseong Kim, "Approximations of $SL(3,\mathbb{Z})$ Hecke-Maass $L$-functions by short Dirichlet polynomials", preprint, arXiv:2204.12612, 2022, https://arxiv.org/abs/2204.12612