---
abstract: 'In this paper we study the distribution of the non-trivial zeros of the zeta-function $\zeta(s)$ (and other L-functions) under Montgomery’s pair correlation approach. We use semidefinite programming to improve the asymptotic bounds for $N^*(T)$, $N_d(T)$ and $N({\lambda},T)$.'
address:
- 'IMPA - Instituto Nacional de Matemática Pura e Aplicada - Estrada Dona Castorina, 110, Rio de Janeiro, RJ, Brazil 22460-320'
- 'Hausdorff Center for Mathematics, Universität Bonn, Endenicher Allee 60, 53115 Bonn, Germany'
- 'Massachusetts Institute of Technology, Department of Mathematics, 77 Massachusetts Avenue, Simons building (Building 2), Room 2-241'
author:
- 'Andrés Chirre, Felipe Gonçalves and David de Laat'
title: 'Pair Correlation Estimates for the Zeros of the Zeta-Function via Semidefinite Programming'
---

Introduction
============

In this paper we give improved asymptotic bounds for several quantities related to the zeros of the zeta-function (and other functions) under Montgomery’s pair correlation approach [@M]. The key idea is to replace the usual bandlimited auxiliary functions by the class of functions used in the linear programming bounds developed by Cohn and Elkies [@CE] for the sphere packing problem. The advantage of this framework is that it reduces the problems to convex optimization problems that can be solved numerically via semidefinite programming. For all problems we considered this produces better bounds than any bandlimited construction.

Background
----------

Let $\zeta(s)$ be Riemann’s zeta-function. It is well-known that all non-trivial zeros of $\zeta(s)$ are located in the critical strip $0<{{\rm Re}\,}s<1$, and the Riemann Hypothesis (RH) is the statement that all these zeros are aligned in the line ${{\rm Re}\,}s=1/2$. Let $N(T)$ count the number of zeros $\rho = \beta + i \gamma$ of $\zeta(s)$, repeated according the multiplicity, such that $0<\beta<1$ and $0 <\gamma \leq T$. The Riemann-von Mangoldt formula (in its weaker form) states that $$\begin{aligned}
\label{RvMformula}
N(T) =  (1+o(1)) \frac{T}{2\pi} \log T.\end{aligned}$$ Let $$N^{*}(T):=\displaystyle\sum_{0<\gamma\leq T}m_{\rho},$$ where the sum is over the non-trivial zeros of $\zeta(s)$ counting multiplicities[^1] and $m_\rho$ is the multiplicity of $\rho$. In addition to RH, it is also conjectured that all zeros of $\zeta(s)$ are simple, and therefore it is [*conjectured*]{} that $$\begin{aligned}
 \label{NstarNconjecure}
N^{*}(T) \sim N(T).\end{aligned}$$ To study the distribution of the zeros of zeta, Montgomery defined the pair correlation function $$\label{paircorrelfunction}
N(x,T):=\sum_{\substack{0< {\gamma},{\gamma}'\leq T \\ 0<{\gamma}'-{\gamma}\leq \frac{2\pi x}{\log T}}} 1$$ and [*conjectured*]{} that $$N(x,T) \sim N(T)\int_0^x \bigg(1-\frac{\sin^2(\pi y)}{(\pi y)^2}\bigg){\,\text{\rm d}}y.$$ Note that by the average gap between zeros is $\frac{2\pi}{\log T}$, hence $N(x,T)$ is counting zeros not greater than $x$ times the average gap.

One line of research to understand and give evidence for the conjectures above is to produce bounds of the form $$\label{prob1}
N^*(T) \leq (1+c) N(T),$$ and $$\label{prob2}
N(x,T) \gg N(T),$$ with $c,x>0$ as small as possible, as $T\to\infty$. These two problems have been widely studied with several improvements being made over the years. One of the approaches is to use some suitable explicit formula (relating sums with integrals) with an auxiliary function $f$ in some class ${\mathcal{A}}$ and produce an inequality relating the quantity we are interested to bound with some functional ${\mathcal{Q}}(f)$ over ${\mathcal{A}}$. Minimizing (or maximizing) the functional over the class ${\mathcal{A}}$ would then produce the best bound one can possibly get with that specific approach. Nowadays, this idea is a standard technique in analytic number theory (introduced first by Beurling and Selberg) and the following are some references (clearly not a complete list) where the main approach is exactly that: Large sieve inequalities [@GV; @HV]; Erdös-Turán inequalities [@CV2; @Va]; Hilbert-type inequalities [@CL3; @CLV; @CV2; @GMK; @GV; @Va]; Tauberian theorems [@GV]; Bounds in the theory of the Riemann zeta-function and $L$-functions [@CC; @CChi; @CChiM; @CCLM; @CCM; @CCM2; @CF; @CS; @Chi; @Ga; @GG]; Prime gaps [@CMS].

From our point of view, our main contribution connects here. So far the only class ${\mathcal{A}}$ used for problems and was some Paley-Wiener space of bandlimited functions. We relax the bandlimited condition by requiring only certain sign conditions on the auxiliary function that match exactly with the very same conditions required by the linear programming bounds for the packing problem (see Section \[prelims\] for a detailed explanation). This relation is what ultimately inspired and allowed us to perform numerical computations to find good test functions for the functionals we derive in Section \[prelims\]. Furthermore, as far as we know, it is the first time this method is used in the zeta-function theory.

Main Results
============

\[thmNstar\] Assuming RH we have $$\begin{aligned}
    N^*(T)\leq ({1.3208}+o(1))N(T).
    \end{aligned}$$ Assuming GRH we have $$\begin{aligned}
    N^*(T)\leq ({1.3155}+o(1))N(T).
    \end{aligned}$$

Montgomery [@M] was the first to show the constant $1.3333...$. This result was later improved to $1.3275$ by Cheer and Goldston [@CG]. Assuming the generalized Riemann Hypothesis (GRH), Goldston, Gonek, Özlük and Snyder [@GGOS] improved it to $1.3262$. To the best of our knowledge, our bounds are the current best.

Theorem \[thmNstar\] has an important application to estimating the quantity of simple zeros of $\zeta(s)$. Let $$N_s(T):=\displaystyle\sum_{\substack{0<\gamma\leq T\\ m_\rho=1}}1.$$ Using the fact that $${N_s(T)\geq \displaystyle\sum_{0<{\gamma}\leq T}(2-m_\rho)}=2N(T)-N^{*}(T).$$ we obtain the following corollary.

Assuming RH we have $${N_s(T)}\geq ({0.6792} + o(1)){N(T)}.$$ Assuming GRH we have $${N_s(T)}\geq ({0.6845} + o(1)){N(T)}. $$

Under the pair correlation approach the previous best result known is due by Cheer and Goldston [@CG] showing that $67.27\%$ of the zeros are simple. Assuming GRH, Goldston, Gonek, Özlük and Snyder [@GGOS] showed that $67.38\%$ are simple. In this way, we improved all these bounds. However, by a different technique, still assuming RH, Bui and Heath-Brown [@BHB] improved the result to $70.37\%$, which currently is the best.

Combining the above result of Bui and Heath-Brown with Theorem \[thmNstar\] and an argument of Ghosh, we can bound the proportion of distinct zeros of zeta. Let $$N_d(T) := \sum_{0<\gamma\leq T} \frac{1}{m_\rho},$$ be the number of distinct zeros of $\zeta(s)$ with $0<{\gamma}\leq T$. Using the inequality $$2N_s(T)\leq \displaystyle\sum_{0<\gamma\leq T}\dfrac{(m_\rho-2)(m_\rho-3)}{m_\rho}=N^{*}(T)-5N(T)+6N_d(T).$$ in conjunction with the estimate $$N_s(T) \geq (0.7037+o(1))N(T)$$ and Theorem \[thmNstar\], we deduce the following corollary.

Assuming RH we have $${N_d(T)}\geq ({0.8477} + o(1)){N(T)}.$$ Assuming GRH we have $${N_d(T)}\geq ({0.8486} + o(1)){N(T)}. $$

Using the pair correlation approach, the best previous result known is due to Farmer, Gonek and Lee [@FGL] with constant $0.8051$. By a different technique, assuming RH, Bui and Heath-Brown [@BHB] improved the constant to $0.8466$. To the best of our knowledge, our new bounds are the current best.

We also obtain improved results for Montgomery’s pair correlation function.

\[thmpaircorreltation\] Assuming RH and we have $$N({0.6039},T)\gg N(T).$$ Assuming GRH and we have $$N(0.5769,T)\gg N(T).$$

Montgomery [@M] showed that $N(0.68..., T)\gg N(T)$, and in [@GGOS] it is pointed out that it is not difficult to modify Montgomery’s argument to derive the sharper constant $0.6695$. This result was improved by Goldston, Gonek, Özlük and Snyder [@GGOS] with constant $0.6072$. Later, Carneiro, Chandee, Littmann and Milinovich [@CCLM] improved the constant to $0.6068...$. Assuming GRH and , Goldston, Gonek, Özlük and Snyder showed the constant $0.5781...$. To the best of our knowledge, our new bounds are the current best.

Results for zeros of Dirichlet L-functions
------------------------------------------

To obtain averaged bounds for the percentage of simple zeros of primitive Dirichlet L-functions we use the framework established by Chandee, Lee, Liu and Radziwiłł [@CLLR]. Let $\Phi$ be a real-valued smooth function supported in the interval $[a,b]$ with $0<a<b<\infty$. Define its Mellin transform by $$\mathcal{M}\Phi(s)=\int_{0}^{\infty}\Phi(x)x^{s-1}{\,\text{\rm d}}x.$$ For a character $\chi$ mod $q$, let $L(s,\chi)$ be its associated Dirichlet L-function. Under GRH, all non-trivial zeros of $L(s,\chi)$ lie on the critical line ${{\rm Re}\,}s = 1/2$. Let $$N_{\Phi}(Q):=\displaystyle\sum_{Q\leq q\leq 2Q}\dfrac{W(q/Q)}{\varphi(q)}\displaystyle\sum_{\substack{\chi  \ (\mathrm{mod} \ q) \\ \text{primitive}}} \displaystyle\;\sum_{\gamma_\chi}\big|\mathcal{M}\Phi(i\gamma_\chi)\big|^2,$$ where $W$ is a non-negative smooth function supported in $(1,2)$, and where the last sum is over all non-trivial zeros ${\tfrac12}+i\gamma_\chi$ of the Dirichlet $L$-function $L(s,\chi)$. In [@CLLR Lemma 2.1] it is shown that $$N_{\Phi}(Q)\sim\dfrac{A}{2\pi}Q\log Q \int_{-\infty}^{\infty}\big|\mathcal{M}\Phi(ix)\big|^2{\,\text{\rm d}}x,$$ where $$A={\mathcal{M}}W(1)\displaystyle\prod_{p\ \text{prime}}\bigg(1-\dfrac{1}{p^2}-\dfrac{1}{p^3}\bigg).$$ Let $$N_{\Phi,s}(Q)=\displaystyle\sum_{Q\leq q\leq 2Q}\dfrac{W(q/Q)}{\varphi(q)}\displaystyle\sum_{\substack{\chi  \ (\mathrm{mod} \ q) \\ \text{primitive}}} \displaystyle\;\sum_{\substack{\gamma_\chi \\ \text{simple}}}\big|\mathcal{M}\Phi(i\gamma_\chi)\big|^2.$$ The quantity $$\liminf_{Q\to\infty}\frac{N_{\Phi,s}(Q)}{N_{\Phi}(Q)}$$ then measures (in average) the proportion of simple zeros among all primitive Dirichlet L-functions.

In addition, for the following theorem, we require that $\Phi(x)$ and ${\mathcal{M}}\Phi(ix)$ are non-negative functions. We note that we can also further relax the conditions on $\Phi$ so to include the function given by ${\mathcal{M}}\Phi(ix) = (\sin x/x)^2$, as was established in [@CLLR] and [@S].

\[thmsimplezerosofdir\] Assuming GRH we have $$N_{\Phi,s}(Q)\geq (0.9350+o(1))N_{\Phi}(Q).$$

Using the pair correlation approach, the best previous result known is due to Sono [@S], showing that $93.22\%$ of the zeros are simple. To the best of our knowledge, our bound is the current best.

Results for zeros of $\xi'(s)$
------------------------------

We can extend our analysis to the zeros of $\xi'(s)$, where $$\begin{aligned}
\xi(s)=\frac{1}{2}s(s-1)\pi^{-\frac{s}{2}}\Gamma\bigg(\frac{s}{2}\bigg)\zeta(s).\end{aligned}$$ It is known that $\xi'(s)$ has only zeros in the critical strip $0<{{\rm Re}\,}s<1$ and that RH implies that all its zeros satisfy ${{\rm Re}\,}s=1/2$. Let $N_1(T)$ count the number of zeros $\rho_1=\beta_1+i\gamma_1$ of $\xi'(s)$ (with multiplicity) such that $0< \gamma_1 \leq T$. It is also known that $$\begin{aligned}
N_1(T) =  (1+o(1)) \frac{T}{2\pi} \log T.\end{aligned}$$ We can then similarly define the function $$N_{1}^{*}(T):=\displaystyle\sum_{0<\gamma_1\leq T}m_{\rho_1},$$ where $m_{\rho_1}$ is the multiplicity of the zero $\rho_1$.

\[thmn1star\] Assuming RH we have $$\begin{aligned}
    N_1^*(T)\leq (1.1175+o(1))N_1(T).
    \end{aligned}$$

To the best of our knowledge, this bound is the current best.

Defining the functions $N_{1,s}(T)$ and $N_{1,d}(T)$ (quantity of simple and distinct zeros respectively) for $\xi'(s)$ and using the inequalities $${N_{1,s}(T) \geq 2 N_1(T) - N_1^*(T)}$$ and $${N_{1,d}(T) \geq \frac{3}{2}N_1(T)-\frac{1}{2}N_1^*(T)},$$ that can be derived the same way as for $\zeta(s)$, we obtain the following corollary.

Assuming RH we have $$N_{1,s}(T)\geq (0.8825+o(1))N_1(T). $$ and $$N_{1,d}(T)\geq (0.9412+o(1))N_1(T). $$

The best previous result is due to Farmer, Gonek and Lee [@FGL], showing that more than $85.83\% $ of the zeros of $\xi'(s)$ are simple. To the best of our knowledge, our new bounds are the current best.

Derivation of the optimization problems {#prelims}
=======================================

Let ${\mathcal{A}}_{LP}$ be the class of even continuous functions $f\in L^1({\mathbb{R}})$ satisfying the following conditions:

1.  ${\widehat}f(0)=f(0)=1$;

2.  ${\widehat}f\geq 0$;

3.  $f$ is eventually non-positive.

By eventually non-positive we mean that $f(x)\leq 0$ for all sufficiently large $|x|$. We then define the last sign change of $f$ by $$r(f)=\inf \big\{r>0: f(x)\leq 0 \text{ for } |x|\geq r\big\}.$$ It is easy to show that if $f\in A_{LP}$, then ${\widehat}f \in L^1({\mathbb{R}})$.

A remarkable breakthrough in the sphere problem was achieved by Cohn and Elkies in [@CE], where they showed that if $\Delta({\mathbb{R}}^d)$ is the highest sphere packing density in ${\mathbb{R}}^d$ then $$\Delta({\mathbb{R}}^d) \leq {\mathcal{Q}}(f)$$ for any $f\in  {\mathcal{A}}_{LP}({\mathbb{R}}^d)$ (this is the analogous class in higher dimensions defined for radial functions $f$), where $${\mathcal{Q}}(f) = \frac{\pi^{d/2}}{(d/2)!2^{d}}r(f)^d.$$ With this approach they generated numerical upper bounds, called linear programming bounds, for the packing density for dimensions up to $36$ (nowadays it goes much higher) that improved every single upper bound known at the time and still are the current best. These upper bounds in dimensions $8$ and $24$ revealed to be extremely close to the lower bounds given by the $E_8$ root lattice and the $\Lambda_{24}$ Leech lattice, revealing that in these special dimensions the linear programming approach could exactly act as the dual problem. This is what inspired Viazovska [@V; @CKMRV] to follow their program and solve the sphere packing problem in dimensions $8$ and $24$. What is interesting and surprising to us is that the same space ${\mathcal{A}}_{LP}$ can be used (but with a functional different than ${\mathcal{Q}}(f)$) to produce numerical bounds in analytic number theory.

The general strategy to study problems and is based on Montgomery’s function $$\begin{aligned}
F(x,T)=\frac{1}{N(T)}\sum_{0<\gamma, \gamma'\leq T}T^{ix(\gamma-\gamma')}w(\gamma-\gamma'),\end{aligned}$$ where the sum is over pairs of ordinates of zeros (with multiplicity) of $\zeta(s)$ and $w(u)=\frac{4}{4+u^2}$. The first step is to use Fourier inversion to obtain $$\label{explicit_formula}
\displaystyle\sum_{0<\gamma, \gamma'\leq T}g\bigg((\gamma-\gamma')\dfrac{\log T}{2\pi}\bigg)w(\gamma-\gamma')=N(T)\int_{-\infty}^{\infty}\widehat{g}(x)F(x,T){\,\text{\rm d}}x,$$ for suitable functions $g$, and use some known asymptotic estimate for $F(x,T)$ as $T\to\infty$ (which is proven only under RH or GRH). Secondly, after a series of inequalities, we produce a minimization problem over ${\mathcal{A}}_{LP}$ for some functional ${\mathcal{Z}}$. We then approach the problem numerically, using the class of functions used for the sphere packing problem in [@CE] and sum-of-squares/semidefinite programming techniques to optimize over these functions. The same basic strategy can be, in principle, carried out for other functions where we have a pair correlation approach. Indeed, we will also derive functionals related to the zeros of $\xi'(s)$ and a certain average of primitive Dirichlet L-functions.

Bounding $N^*(T)$ and $N(x,T)$
------------------------------

Ultimately, the functionals we need to define depend on the asymptotic behavior of $F(x,T)$. To analyze the function $N^{*}(T)$ we define the functionals $${\mathcal{Z}}(f)  =r(f) + \frac{2}{r(f)}\int_0^{r(f)}f(x)x{\,\text{\rm d}}x$$ and $${\widetilde}{\mathcal{Z}}(f)=r(f) + \frac{2}{r(f)}\int_0^{r(f)}f(x)x{\,\text{\rm d}}x + 3\int_{r(f)}^{\frac{3}{2}r(f)}f(x){\,\text{\rm d}}x -  \frac{2}{r(f)}\int_{r(f)}^{\frac{3}{2}r(f)}f(x)x{\,\text{\rm d}}x.$$

\[thmsimplezerosofxi\] Let $f\in {\mathcal{A}}_{LP}$. Assuming RH we have $$N^*(T)\leq ({\mathcal{Z}}(f)+o(1))N(T).$$ Assuming GRH, for every fixed small $\delta>0$ we have $$N^*(T)\leq ({\widetilde}{\mathcal{Z}}(f) + O(\delta) + o(1))N(T).$$

We start assuming only RH. Refining the original work of Montgomery [@M], Goldston and Montgomery [@GM Lemma 8] stated that $$\label{Fasymptotics}
F(x,T) = \big(T^{-2|x|}\log T+|x|\big)(1+o(1)),$$ uniformly for $|x|\leq 1$. Let $f\in {\mathcal{A}}_{LP}$ and let $g(x)={\widehat}f(x/r(f))/r(f)$. We can then use the explicit formula in conjunction with the asymptotic formula above to obtain $$\begin{aligned}
\sum_{0<\gamma, \gamma'\leq T}  g\bigg((\gamma-\gamma')\dfrac{\log T}{2\pi}\bigg)w(\gamma-\gamma')  = N(T)\left[\widehat{g}(0) +\int_{-1}^{1}{{\widehat}g}(x)|x|{\,\text{\rm d}}x + \int_{|x|>1}{{\widehat}g}(x)F(x,T){\,\text{\rm d}}x + o(1)
\right],\end{aligned}$$ where the $o(1)$ above is justified since ${\widehat}g$ is continuous and $T^{-2|x|}\log T\to{{\boldsymbol}\delta}_0(x)$ as $T\to\infty$ (in the distributional sense). Moreover, since $F(x,T)$ is non-negative and ${\widehat}g(x)\leq 0$ for $|x|\geq 1$ we deduce that $$\begin{aligned}
 \sum_{0<\gamma, \gamma'\leq T}g\bigg((\gamma-\gamma')\dfrac{\log T}{2\pi}\bigg)w(\gamma-\gamma') &  \leq N(T)\left[ {\widehat}g(0)+2\int_{0}^{1}{{\widehat}g}(x)x{\,\text{\rm d}}x + o(1)\right]  = N(T)\left[\frac{{\mathcal{Z}}(f)}{r(f)} + o(1)\right].\end{aligned}$$ On the other hand, clearly we have $$\begin{aligned}
\sum_{0<\gamma, \gamma'\leq T} g\bigg((\gamma-\gamma')\dfrac{\log T}{2\pi}\bigg)w(\gamma-\gamma') \geq g(0)\sum_{0<\gamma\leq T} m_\rho = \frac{N^*(T)}{r(f)}.\end{aligned}$$ Combining these results we show the first inequality in the theorem.

Assume now GRH. It is then shown in [@GGOS] that for any fixed and sufficiently small $\delta >0$ we have $$\label{Fasymptoticmore}
F(x,T) \geq \frac{3}{2}-|x| - o(1),$$ uniformly for $1\leq |x|\leq \frac{3}{2}-\delta$ as $T\to \infty$. Using this estimate and the fact that ${\widehat}g(x)\leq 0$ for $|x|\geq 1$ we obtain $$\begin{aligned}
\sum_{ 0<\gamma, \gamma'\leq T}{\widehat}g\bigg((\gamma-\gamma')\dfrac{\log T}{2\pi}\bigg)w(\gamma-\gamma')& \leq N(T)\left[{{\widehat}g}(0) + 2\int_{1}^{\frac{3}{2}-\delta}{{\widehat}g}(x)\left(\frac{3}{2}-x\right){\,\text{\rm d}}x + o(1)
\right] \\
& = N(T)\left[\frac{{\widetilde}{\mathcal{Z}}(f)}{r(f)}+o(1) +O(\delta)\right].\end{aligned}$$ Arguing as before we finish the proof.

To analyze $N(x,T)$ we define the [function]{} $${\mathcal{P}}(f) = \inf \big\{{\lambda}>0: p_f({\lambda}) > 0 \big\},$$ where $$p_f({\lambda})=-1+\frac{{\lambda}}{r(f)}+ \frac{2r(f)}{{\lambda}}\int_0^{\frac{{\lambda}}{r(f)}}{\widehat}f(x)x{\,\text{\rm d}}x,$$ and the [function]{} $${\widetilde}{\mathcal{P}}(f) = \inf\big\{{\lambda}>0: {\widetilde}p_f({\lambda}) > 0 \big\},$$ where $${\widetilde}p_f({\lambda})=-1+\frac{{\lambda}}{r(f)}+ \frac{2r(f)}{{\lambda}}\int_0^{\frac{{\lambda}}{r(f)}}{\widehat}f(x)x{\,\text{\rm d}}x +3\int_{\frac{{\lambda}}{r(f)}}^{\frac{3{\lambda}}{2r(f)}}{\widehat}f(x){\,\text{\rm d}}x -  \frac{2r(f)}{{\lambda}}\int_{\frac{{\lambda}}{r(f)}}^{\frac{3{\lambda}}{2r(f)}}{\widehat}f(x)x{\,\text{\rm d}}x.$$ Note that these functions are well defined since $p_f$ and ${\widetilde}p_f$ are $C^1$ functions that assume $-1$ at ${\lambda}=0$, and using the fact that $\widehat{f}\in L^1(\mathbb{R})$ one can show $$\lim_{{\lambda}\to\infty} \frac{p_f({\lambda})}{{\lambda}} = \lim_{{\lambda}\to\infty} \frac{{\widetilde}p_f({\lambda})}{{\lambda}} =\frac{1}{r(f)} > 0.$$

\[thmsmallgapszerosofxi\] Let $f\in {\mathcal{A}}_{LP}$ and ${\varepsilon}>0$. Assuming RH and we have $$N({\mathcal{P}}(f)+\varepsilon,T)\gg N(T).$$ Assuming GRH we have $$N({\widetilde}{\mathcal{P}}(f)+\varepsilon,T)\gg N(T).$$

In the following we only exhibit the proof assuming RH since under GRH the proof is very similar, and the only extra information needed is in . Let $f\in{\mathcal{A}}_{LP}$ and $\lambda>0$. Applying the explicit formula for $g(x)= f(r(f)x/{\lambda})$ in conjunction with we obtain $$\begin{aligned}
\sum_{0<\gamma, \gamma'\leq T}g\bigg((\gamma-\gamma')\dfrac{\log T}{2\pi}\bigg)w(\gamma-\gamma') = N(T)\int_{-\infty}^{\infty}\widehat{g}(x)F(x,T){\,\text{\rm d}}x
& \geq N(T)\left[{\widehat}g(0)+2\int_{0}^{1}{\widehat}g(x)x{\,\text{\rm d}}x+o(1)\right]
\\ & = N(T)\left[1+p_f({\lambda})+o(1)\right].\end{aligned}$$ Since ${\widehat}f\geq 0$, we have $\|f\|_{\infty}=f(0)=1$. Recall now the pair correlation function $N(x,T)$ defined in . We have $$\begin{aligned}
\sum_{0<\gamma, \gamma'\leq T}g\bigg((\gamma-\gamma')\dfrac{\log T}{2\pi}\bigg)w(\gamma-\gamma') & = N^*(T) +2\sum_{\substack{0<\gamma, \gamma'\leq T\\ 0<\gamma-\gamma'}}f\bigg((\gamma-\gamma')\dfrac{r(f)\log T}{2\pi{\lambda}}\bigg)w(\gamma-\gamma')  \\
& \leq N^*(T) +2\sum_{\substack{0<\gamma, \gamma'\leq T\\ 0<\gamma-\gamma' \leq \frac{2\pi {\lambda}}{\log T}}}f\bigg((\gamma-\gamma')\dfrac{r(f)\log T}{2\pi{\lambda}}\bigg)w(\gamma-\gamma') \\
& \leq N^*(T)+2N({\lambda},T) \\ & = (1+o(1))N(T) + 2N({\lambda},T),\end{aligned}$$ where in the last step we have used . Then, we obtain $$\begin{aligned}
 \frac{N({\lambda},T)}{N(T)}\geq \frac{p_f({\lambda})}{2}+o(1).\end{aligned}$$ Noting that $N({\lambda},T)$ increases with ${\lambda}$, we can then choose ${\lambda}$ arbitrarily close to ${\mathcal{P}}(f)$ and obtain the desired result.

Bounding $N_{\Phi,s}(Q)$
------------------------

Define the following functional over ${\mathcal{A}}_{LP}$: $${\mathcal{L}}(f) = \frac{r(f)}{2} + \dfrac{4}{r(f)}\int_{0}^{\frac{r(f)}{2}}x f(x){\,\text{\rm d}}x+2\int_{\frac{r(f)}{2}}^{r(f)}f( x){\,\text{\rm d}}x.$$ We have the following theorem.

\[thmnphi\] Let $f\in{\mathcal{A}}_{LP}$. Assuming GRH, for every fixed small $\delta>0$ we have $$N_{\Phi,s}(Q) \geq (2- {\mathcal{L}}(f) + O(\delta) + o(1))N_{\Phi}(Q).$$

For $Q>1$ and $x\in{\mathbb{R}}$, we define the pair correlation function $F_\Phi$ by $$\begin{aligned}
F_\Phi(Q^{x},W)=\dfrac{1}{N_{\Phi}(Q)}\displaystyle\sum_{Q\leq q\leq 2Q}\dfrac{W(q/Q)}{\varphi(q)}\displaystyle\sum_{\substack{\chi \ (\mathrm{mod} \ q)\\ \mathrm{primitive}}}\bigg|\displaystyle\sum_{\gamma_\chi}\mathcal{M}\Phi(i\gamma_\chi)Q^{i\gamma_\chi{x}}\bigg|^2.\end{aligned}$$ Using the asymptotic large sieve, Chandee, Lee, Liu and Radziwiłł[@CLLR] showed the following asymptotic formula under GRH $$\begin{aligned}
\label{FPhiasymp}
& F_{\Phi}(Q^{{x}},W)  \\ & = (1+o(1))\bigg[1-(1-|x|)_++\Phi\big(Q^{-|{x}|}\big)^2\log Q \bigg(\dfrac{1}{2\pi}\int_{-\infty}^{\infty}\big|\mathcal{M}\Phi(it)\big|^2{\,\text{\rm d}}t\bigg)^{-1}\bigg] + O\Big(\Phi(Q^{-|{x}|})\log^{1/2} Q\Big)\nonumber,\end{aligned}$$ which holds uniformly for $|{x}|\leq 2-\delta$ as $Q\to\infty$, for any fixed and sufficiently small $\delta>0$. Let $$N^*_{\Phi}(Q):=\displaystyle\sum_{Q\leq q\leq 2Q}\dfrac{W(q/Q)}{\varphi(q)}\displaystyle\sum_{\substack{\chi \ (\mathrm{mod} \ q) \\ \text{primitive}}}\displaystyle\sum_{\gamma_\chi}m_{\rho_\chi}\big|\mathcal{M}\Phi(i\gamma_\chi)\big|^2,$$ where $m_{\rho_\chi}$ denote the multiplicity of the nontrivial zero $\rho_\chi={\tfrac12}+i\gamma_\chi$ of $L(s,\chi)$. Since $$\displaystyle\sum_{\substack{\gamma_\chi\\\text{simple}}}\big|\mathcal{M}\Phi(i\gamma_\chi)\big|^2\geq \displaystyle\sum_{\gamma_\chi}(2-m_{\rho_\chi})\big|\mathcal{M}\Phi(i\gamma_\chi)\big|^2$$ we obtain $$\begin{aligned}
 \label{ineqNstarwithN}
N_{\Phi,s}(Q)\geq 2N_{\Phi}(Q)-N^{*}_{\Phi}(Q).\end{aligned}$$ For any $g\in L^1({\mathbb{R}})$ with ${\widehat}g\in L^1({\mathbb{R}})$ we have the following explicit formula (Fourier inversion) $$\begin{aligned}
\sum_{Q\leq q\leq 2Q} \dfrac{W(q/Q)}{\varphi(q)}\displaystyle\sum_{\substack{\chi \ (\mathrm{mod} \ q) \\ \text{primitive}}}\displaystyle\;\sum_{\gamma_\chi, \gamma'_\chi}\mathcal{M}\Phi(i\gamma_\chi)\mathcal{M}\Phi(i\gamma'_\chi)\,\widehat{g}\bigg(\dfrac{(\gamma_\chi-\gamma'_\chi)\log Q}{2\pi}\bigg)
     =N_{\Phi}(Q)\int_{-\infty}^{\infty}g(x)F_{\Phi}(Q^x,W){\,\text{\rm d}}x .\end{aligned}$$ Letting $f\in\mathcal{A}_{LP}$ and $g(x)=f(r(f)x/(2-\delta))$, for any primitive character $\chi  \ (\mathrm{mod} \ q)$ we obtain $$\begin{aligned}
&\sum_{\gamma_\chi, \gamma'_\chi}\mathcal{M}\Phi(i\gamma_\chi)\mathcal{M}\Phi(i\gamma'_\chi)\,\widehat{g}\bigg(\dfrac{(\gamma_\chi-\gamma'_\chi)\log Q}{2\pi}\bigg) \\ & = \displaystyle\sum_{\gamma_\chi}m_{\rho_\chi}\big|\mathcal{M}\Phi(i\gamma_\chi)\big|^2\,\widehat{g}(0) \nonumber + \displaystyle\sum_{\gamma_\chi\neq \gamma'_\chi}\mathcal{M}\Phi(i\gamma_\chi)\mathcal{M}\Phi(i\gamma'_\chi)\,\widehat{g}\bigg(\dfrac{(\gamma_\chi-\gamma'_\chi)\log Q}{2\pi}\bigg) \nonumber \\
        & \geq \dfrac{2-\delta}{r(f)}\,\displaystyle\sum_{\gamma_\chi}m_{\rho_\chi}\big|\mathcal{M}\Phi(i\gamma_\chi)\big|^2. 
        \end{aligned}$$ This implies that $$\begin{aligned}
& \sum_{Q\leq q\leq 2Q} \dfrac{W(q/Q)}{\varphi(q)}\displaystyle\sum_{\substack{\chi \ (\mathrm{mod} \ q) \\ \text{primitive}}}\displaystyle\;\sum_{\gamma_\chi, \gamma'_\chi}\mathcal{M}\Phi(i\gamma_\chi)\mathcal{M}\Phi(i\gamma'_\chi)g\bigg(\dfrac{(\gamma_\chi-\gamma'_\chi)\log Q}{2\pi}\bigg)  \geq \dfrac{2-\delta}{r(f)}N^*_{\Phi}(Q).\end{aligned}$$ On the other hand, observing that $$\Phi\big(Q^{-|{x}|}\big)^2\log Q \bigg(\dfrac{1}{2\pi}\int_{-\infty}^{\infty}\big|\mathcal{M}\Phi(it)\big|^2{\,\text{\rm d}}t\Big)\to {{\boldsymbol}\delta}(x),$$ as $Q\to \infty$ (in the distributional sense) and that $$\log^{1/2} Q \int_{-(2-\delta)}^{2-\delta} g(x) \Phi(Q^{-|x|}){\,\text{\rm d}}x \leq 2\log^{-1/2} Q \int_{Q^{-({2-\delta})}}^1 \Phi(t)\frac{{\,\text{\rm d}}t}{t} = O(\log^{-1/2} Q),$$ we can use the asymptotic estimate to obtain $$\begin{aligned}
\int_{-\infty}^{\infty}g({x})F_{\Phi}(Q^{x},W){\,\text{\rm d}}{x}
  & \leq \int_{-(2-\delta)}^{2-\delta}g({x})F_{\Phi}(Q^{x},W){\,\text{\rm d}}{x} \\ & =  g(0)+ \int_{-(2-\delta)}^{2-\delta}g({x})(1-(1-|x|)_+){\,\text{\rm d}}x + O(\log^{-1/2} Q) + o(1)
\\ & =\frac{2 {\mathcal{L}}(f)}{r(f)} + O(\delta) + o(1).\end{aligned}$$ We then conclude that $$N^*_{\Phi}(Q) \leq N_{\Phi}(Q) \left({\mathcal{L}}(f) + O(\delta) + o(1) \right).$$ Using we finish the proof.

Bounding $N_1^*(T)$
-------------------

Similarly to the case of the Riemann zeta-function, the functionals that we need to define depend on the asymptotic behavior of the function $F_1(x,T)$ defined by $$\begin{aligned}
 \label{5_9_18:57pm}
F_1(x,T)=N_1(T)^{-1}\displaystyle\sum_{0<\gamma_1, \gamma'_1 \leq T}T^{i\alpha(\gamma_1-\gamma'_1)}w(\gamma_1-\gamma'_1),\end{aligned}$$ where $x\in\mathbb{R}$, $T>0$ and the sum is over pairs of ordinates of zeros (with multiplicity) of $\xi'(s)$. To analyze $N_1^{*}(T)$ we define the following functional $$\begin{aligned}
{\mathcal{Z}}_{1}(f) =r(f)+\dfrac{2}{r(f)}\int_{0}^{r(f)}x\, f(x){\,\text{\rm d}}x-\dfrac{8}{r(f)^2}\int_{0}^{r(f)}x^2\, f(x){\,\text{\rm d}}x  +\displaystyle\sum_{k=1}^{\infty}\dfrac{2c_k}{r(f)^{2k+1}}\int_{0}^{r(f)}x^{2k+1}\, f(x){\,\text{\rm d}}x,\end{aligned}$$ where $c_k=2^{2k+1}\frac{(k-1)!}{(2k)!}$.

\[thmsimplezerosofxiprime\] Let $f\in {\mathcal{A}}_{LP}$. Assuming RH, for every fixed small $\delta >0$ we have $$N_1^*(T)\leq ({\mathcal{Z}}_1(f) + O(\delta) + o(1))N_1(T).$$

A result similar to for the function $F_1(x,T)$ defined in is also known (see [@FGL Theorem 1.1]), which is the following: for any fixed small $\delta>0$ we have $$F_1(x,T)=T^{-2|x|}\log T+|x| - 4|x|^2+\displaystyle\sum_{k=1}^{\infty}c_k |x|^{2k+1}+ o(1)(1+T^{-2|x|}\log T),$$ uniformly for $|x|\leq 1-\delta$ as $T\to\infty$, where $c_k=2^{2k+1}\frac{(k-1)!}{(2k)!}$. The proof then follows the same strategy as the proof for $\zeta(s)$ and we leave the details to the reader.

Numerically optimizing the bounds
=================================

Going back to the sphere packing problem, since we obviously have $\Delta({\mathbb{R}}^1)=1$, this shows $r(f)\geq 1$ for all $f\in {\mathcal{A}}_{LP}$. The last sign change equals $1$ for two (suspiciously) well-known functions: the hat function $$H(x)=(1-|x|)_+,$$ whose Fourier transform is ${\widehat}H(x)=\frac{\sin^2(\pi x)}{(\pi x)^2}$, and Selberg’s function $$S(x)=\frac{\sin^2(\pi x)}{(\pi x)^2(1-x^2)},$$ whose Fourier transform is supported in $[-1,1]$ and given by ${\widehat}S(x)=1-|x|+\frac{\sin(2\pi x)}{2\pi}$ for $|x|<1$. In particular, we can use these two functions to evaluate the functionals derived in Section \[prelims\] to obtain bounds, but this does not result in the best possible bounds. To obtain better bounds we use the class of functions used in the linear programming bounds by Cohn and Elkies [@CE] for sphere packing. That is, we consider the subspace $\mathcal A_{LP}(d)$ consisting of the functions $f \in \mathcal A_{LP}$ of the form $$\label{eq:subspace} 
f(x) = p(x) e^{-\pi x^2},$$ where $p$ is an even polynomial of degree $2d$.

In [@CE], optimization over a closely related class of functions is done by specifying the functions by their real roots and optimizing the root locations. For the sphere packing problem this works very well, where in ${\mathbb{R}}^{24}$ it leads to a density upper bound that is sharp to within a factor $1 + 10^{-51}$ of the optimal configuration [@CM]. We have also tried this approach for the optimization problems in this paper, but this did not work very well because the optimal functions seem to have very few real roots, which produces a strange effect in the numerical computations, where the last forced root tends to diverge when you increase the degree of the polynomial[^2]. Instead we use sum-of-squares characterizations and semidefinite programming, as was done in [@dLOV] for the binary sphere packing problem.

*Semidefinite programming* is the optimization of a linear functional over the intersection of a cone of positive semidefinite matrices (real symmetric matrices with nonnegative eigenvalues) and an affine space. A semidefinite program is often given in block form, which can be written as $$\begin{aligned}
\text{minimize} \; \sum_{i=1}^I \mathrm{tr}(X_iC_i) : \; & \sum_{i=1}^I \mathrm{tr}(X_iA_{i,j}) = b_j \text{ for } j \in [m],\\
& \,X_1,\ldots,X_I \in \mathbb R^{n \times n} \text{ positive semidefinite},\end{aligned}$$ where $I\in {\mathbb{N}}$ gives the number of blocks, $\{C_i\} \subseteq {\mathbb{R}}^{n \times n}$ is the objective, and $\{A_{i,j}\} \subseteq {\mathbb{R}}^{n \times n}$, $b \in {\mathbb{R}}^m$ give the linear constraints (for notational simplicity we take all blocks to have the same size). Semidefinite programming is a broad generalization of linear programming (which we recover by setting $n=1$ in the above formulation), and, as for linear programming, there exist efficient algorithms for solving them. The reason semidefinite programming comes into play here, is that we can model polynomial inequality constraints as sum-of-squares constraints, which in turn can be written as semidefinite constraints; see, e.g., [@Bl].

Proof of Theorems \[thmNstar\], \[thmsimplezerosofdir\], and \[thmn1star\]
--------------------------------------------------------------------------

To obtain the first part of Theorem \[thmNstar\] from Theorem \[thmsimplezerosofxi\] we need to minimize the functional ${\mathcal{Z}}$ over the space $\mathcal A_{LP}(d)$. We can see this as a bilevel optimization problem, where we optimize over scalars $R \geq 1$ in the outer problem, and over functions $f \in \mathcal A_{LP}(d)$ satisfying $r(f) = R$ in the inner problem. The outer problem is a simple one dimensional optimization problem for which we use Brent’s method [@Br]. The inner problem can be written as a semidefinite program as we discuss below. The numerical results suggest that the optimal $R$ goes to $1$ as $d \to \infty$ (which is itself intriguing and so far we have no explanation), but for fixed $d$ we need to optimize $R$ to obtain a good bound.

A polynomial $p$ that is nonnegative on $[R,\infty)$ can be written as $s_1(x) + (x-R) s_2(x)$, where $s_1$ and $s_2$ are sum-of-squares polynomials with $\mathrm{deg}(s_1),\mathrm{deg}(s_2(x))+1 \leq \deg(p)$; see, e.g., [@PS]. This shows that functions of the form that are non-positive on $[R,\infty)$ can be written as $$f(x) = -\big(s_1(x^2) + (x^2-R^2) s_2(x^2)\big) e^{-\pi x^2}.$$

Let $v(x)$ be a vector whose entries form a basis of the univariate polynomials of degree at most $d$. The polynomials $s_1$ and $s_2$ are sum-of-squares if and only if they can be written as $s_i(x) = v(x)^{\sf T} X_i v(x)$ for some positive semidefinite matrices $X_i$ of size $d+1$. That is, we can parameterize functions of the form that are non-positive on $[R,\infty)$ by two positive semidefinite matrices $X_1$ and $X_2$ of size $d+1$.

The space of functions of the form is invariant under the Fourier transform. Since a polynomial of degree $2d$ that is nonnegative on $[0,\infty)$ can be written as $s_3(x) + x s_4(x)$, where $s_i(x) = v(x)^{\sf T} X_i v(x)$ for $i=3,4$ are sum-of-squares polynomials of degree $2d$, we have that $\hat f$ is of the form $${\widehat}{f}(x) = \big(s_3(x^2) + x^2 s_4(x^2)\big)  e^{-\pi x^2}.$$

Let $\mathcal T$ be the operator that maps $x^{2k}$ to the function $\frac{k!}{\pi^k} L_k^{-1/2}(\pi x^2)$, where $L_k$ is the Laguerre polynomial of degree $k$ with parameter $-1/2$. Then, for $p$ an even polynomial, we have that $(\mathcal Tp)(x) e^{-\pi x^2}$ is the Fourier transform of $p(x) e^{-\pi x^2}$. We can now describe the functions of the form that are non-positive on $[R,\infty)$ and have nonnegative Fourier transform by positive semidefinite matrices $X_1,\ldots,X_4$ of size $d+1$ whose entries satisfy the linear relations coming from the identity $I(X_1,\ldots,X_4) = 0$, where $$I(X_1,\ldots,X_4) = \mathcal T\big(-s_1(x^2) - (x^2-R^2) s_2(x^2)\big) - \big(s_3(x^2) + x^2 s_4(x^2)\big).$$ Here $\mathcal T(-s_1(x^2) - (x^2-R^2) s_2(x^2))$ is a polynomial whose coefficients are linear combinations in the entries of $X_1$ and $X_2$, and the same for $s_3(x^2) + x^2 s_4(x^2)$ with $X_3$ and $X_4$. The linear constraints on the entries of $X_1,\ldots,X_4$ are then obtained by expressing $I(X_1,\ldots,X_4)$ in some polynomial basis and setting the coefficients to zero.

The conditions $f(0) = 1$ and $f(R) = 0$ are linear in the entries of $X_1$ and $X_2$, and the condition ${\widehat}f(0)=1$ is a linear condition on the entries of $X_3$ and $X_4$. Finally, the objective ${\mathcal{Z}}(f)$ is a linear combination in the entries of $X_1$ and $X_2$, which can be implemented by using the identity $$\int x^m e^{-\pi x^2} {\,\text{\rm d}}x = -\frac{1}{2\pi^{m/2+1/2}} \Gamma\Big(\frac{m+1}{2}, \pi x^2\Big),$$ where $\Gamma$ is the upper incomplete gamma function. Hence, the problem of minimizing ${\mathcal{Z}}(f)$ over functions $f \in \mathcal A_{LP}(d)$ that satisfy $r(f) = R$ is a semidefinite program.

To obtain the second part of Theorem \[thmNstar\] from Theorem \[thmsimplezerosofxi\] and to obtain Theorem \[thmsimplezerosofdir\] from \[thmnphi\] we use the same approach with a different functional. To obtain Theorem \[thmn1star\] from Theorem \[thmsimplezerosofxiprime\] we also do the same as above, but now truncate the series in the functional ${\mathcal{Z}}_{1}$ at $k=15$ and add the easy to compute upper bound $10^{-10}$ on the remainder of the terms.

### Implementation and numerical issues {#sec:rig}

In implementing the above as a semidefinite program we have to make two choices for the polynomial basis that we use: the basis defining the vector $v(x)$, and the basis to enforce the identity $I(X_1,\ldots,X_4) = 0$. This choice of bases is important for the numerical conditioning of the resulting semidefinite program. Following [@dLOV] we choose the Laguerre basis $\{L_n^{-1/2}(2\pi x^2)\}$, as this seems natural and performs well in practice (it multiplied by $e^{-\pi x^2}$ is the complete set of even eigenfunctions of the Fourier transform). We solve the semidefinite programs using sdpa-gmp [@Nakata], which is a primal-dual interior point solver using high precision floating point arithmetic. For the code to generate the semidefinite programs and to perform the post processing we use Julia [@BEKV], Nemo [@FHHJ], and Arb [@J] (where we use Arb for the ball arithmetic used in the verification procedure). For all computations we use $d=40$. In solving the systems we observe that $X_1$ can be set to zero everywhere without affecting the bounds, so that $r(f) = R$ holds exactly for the function $f(x) = (R^2 - x^2) v(x^2)^{\sf T} X_2 v(x^2) e^{-\pi x^2}$ defined by $X_2$.

The above optimization approach uses floating point arithmetic and a numerical interior point solver. This means the identity $I(0, X_2, X_3, X_4) = 0$ will not be satisfied exactly, and, moreover, because the solver can take infeasible steps the matrices $X_2$, $X_3$, and $X_4$ typically have some eigenvalues that are slightly negative. In practice this leads to incorrect upper bounds if the floating point precision is not high enough in relation to the degree $d$. Here we explain the procedure we use to obtain bounds that are guaranteed to be correct. This is an adaptation of the method from [@Lo] and [@dLOV].

We first solve the above optimization problem numerically to find $R$ and $f$ for which we have a good objective value $v = {\mathcal{L}}(f)$. Then we solve the semidefinite program again for the same value of $R$, but now we solve it as a feasibility problem with the additional constraint ${\mathcal{L}}(f) \leq v + 10^{-6}$. The interior point solver will try to give the analytical center of the semidefinite program, so that typically the matrices are all positive definite; that is, the eigenvalues are all strictly positive. Then we use interval arithmetic to check rigorously that $X_2$, $X_3$, and $X_4$ are positive definite, and we compute a rigorous lower bound $b$ on the smallest eigenvalues of $X_3$ and $X_4$.

Using interval arithmetic we compute an upper bound $B$ on the largest coefficient of $I(0, X_2, X_3,X_4)$ in the basis given by the $2d+1$ entries on the diagonal and upper diagonal of the matrix $(R^2 - x^2) v(x^2) v(x^2)^{\sf T}$. If $b \geq (1+2d)B$, then it follows that it is possible to modify the corresponding entries in $X_3$ and $X_4$ such that these matrices stay positive definite and such that $I(0,X_2,X_3,X_4) = 0$ holds exactly [@Lo]. This shows that the Fourier transform of the function $f(x) = (R^2 - x^2) v(x^2)^{\sf T} X_2 v(x^2)e^{-\pi x^2}$ is nonnegative.

We use interval arithmetic to compute $f(0) = R^2 s_2(0)$, $\mathcal T((R^2-x^2) s_2(x^2))(0)$, and ${\mathcal{Z}}(f)$, $\tilde {\mathcal{Z}}(f)$, ${\mathcal{Z}}_1(f)$, or ${\mathcal{L}}(f)$. We can then compute rigorous bounds by observing that, for example, the first part of Theorem \[thmNstar\] can be written as follows: Suppose $f$ is a continuous $L^1({\mathbb{R}})$ function with $f(x) \leq 0$ for $|x| \geq R$ and with nonnegative Fourier transform, then $$N^*(T) \leq \left(\frac{f(0)}{\hat f(0)} {\mathcal{Z}}(f) + o(1)\right) N(T).$$

In the arXiv version of this paper we attach the files ‘Z-$40$.txt’, ‘tildeZ-$40$.txt’, ‘L-$40$.txt’, and ‘Z1-$40$.txt’ that contain the value of $R$ on the first line and the matrices $X_2, X_3$ and $X_4$ on the next $3$ lines (all in $100$ decimal floating point values). For convenience it also contains the coefficients of $f$ in the monomial basis on the last line (but these are not used in the verification procedure). We include a script to perform the above verification and compute the bounds rigorously, as well as the code for setting up the semidefinite programs, using a custom semidefinite programming specification library.

Proof of Theorem \[thmpaircorreltation\]
----------------------------------------

To obtain the first part of Theorem \[thmpaircorreltation\] from Theorem \[thmsmallgapszerosofxi\] we need to minimize the function ${\mathcal{P}}$ over the space $\mathcal A_{LP}$. We can formulate this as a bilevel optimization problem in which we optimize over $R \geq 1$ in the outer problem. In the inner problem we perform a binary search over $\Lambda$ to find the smallest $\Lambda$ for which there exists a function $f \in \mathcal A_{LP}(d)$ that satisfies $f(R) = 0$, $f(x) \leq 0$ for $|x| \geq R$, and $p_f(\Lambda) \geq 0$.

To get a bound whose correctness we can verify rigorously we replace the constraints $f(0)=1$, ${\widehat}f(0) = 1$, and $p_f(\Lambda) \geq 0$ by $f(0) = 1-10^{-10}$, ${\widehat}f(0) = 1+10^{-10}$, and $p_f(\Lambda) \geq 10^{-10}$. We then use the above optimization approach to find good values for $R$ and $\Lambda$. We then add $10^{-6}$ to $\Lambda$ and solve the feasibility problem again to get the strictly feasible matrices $X_2,X_3$, and $X_4$. By performing the same procedure as in \[sec:rig\] we can verify that the Fourier transform of the function $f$ defined by $X_2$ is nonnegative everywhere, and using interval arithmetic we can check that the inequalities $f(0) \leq 1$, ${\widehat}f(0) \geq 1$, and $p_f(\Lambda) > 0$ all hold. Note that this verification procedure does not actually check that $\Lambda$ is equal to or even close to ${\mathcal{P}}(f)$, but the proof of Theorem \[thmsmallgapszerosofxi\] also works if we replace ${\mathcal{P}}(f)$ by any $\Lambda$ for which $p_f(\Lambda)$ is strictly positive. To obtain the second part of the theorem, we do the same except that we replace $p_f$ by ${\widetilde}p_f$.

In the arXiv version of this paper we attach the files ‘P-$40$.txt’, ‘tildeP-$40$.txt’, that have the same layout as the files mentioned in \[sec:rig\], with an additional line containing the value of $\Lambda$. We again include the code to perform the verification and to produce the files.

Acknowledgments {#acknowledgments .unnumbered}
===============

We are very thankful to Emanuel Carneiro and Micah Milinovich for the helpful discussions, suggestions and references.

[100]{}

J. Bezanson, A. Edelman, S. Karpinski and V.B. Shah, , SIAM Rev. 59 (2017), 65–98.

G. Blekherman, P. Parrilo, R. Thomas, ,

R. P. Brent, Algorithms for Minimization Without Derivatives, Englewood Cliffs, NJ: Prentice-Hall, 1973. Ch. 3-4.

H. M. Bui and D. R. Heath-Brown, , Bull. Lond. Math. Soc. 45 (2013), no. 5, 953–961.

E. Carneiro and V. Chandee, Bounding $\zeta(s)$ in the critical strip, J. Number Theory 131 (2011), no. 3, 363–384.

E. Carneiro and A. Chirre, Bounding $S_n(t)$ on the Riemann hypothesis, Math. Proc. Cambridge Philos. Soc. 164 (2018), no. 2, 259–283.

E. Carneiro, A. Chirre and M. B. Milinovich, Bandlimited approximations and estimates for the Riemann zeta-function, Publ. Mat., to appear.

E. Carneiro, V. Chandee, F. Littmann and M. B. Milinovich, Hilbert spaces and the pair correlation of zeros of the Riemann zeta-function, J. Reine Angew. Math. 725 (2017), 143–182.

E. Carneiro, V. Chandee and M. B. Milinovich, Bounding $S(t)$ and $S_1(t)$ on the Riemann Hypothesis, Math. Ann. 356 (2013), no. 3, 939–968.

E. Carneiro, V. Chandee and M. Milinovich, A note on the zeros of zeta and $L$-functions, Math. Z. 281 (2015), no. 1-2, 315–332.

E. Carneiro and R. Finder, On the argument of $L$-functions, Bull. Braz. Math. Soc. (N.S.) 46 (2015), no. 4, 601–-620.

E. Carneiro and F. Littmann, Extremal functions in de Branges and Euclidean spaces, Adv. Math. 260 (2014), 281–349.

E. Carneiro, F. Littmann, and J. D. Vaaler, Gaussian subordination for the Beurling-Selberg extremal problem, Trans. Amer. Math. Soc. 365 (2013), no. 7, 3493–3534.

E. Carneiro, M.B. Milinovich, K. Soundararajan, [ Fourier optimization and prime gaps]{}, Comment. Math. Helv., to appear.

E. Carneiro and J. D. Vaaler, Some extremal functions in Fourier analysis II, Trans. Amer. Math. Soc. 362 (2010), no. 11, 5803–5843.

V. Chandee, Y. Lee, S.-C. Liu and M. Radziwiłł, Simple zeros of primitive Dirichlet $L$-functions and the asymptotic large sieve, Q. J. Math 65 (2014), no. 1, 63–87.

V. Chandee and K. Soundararajan, Bounding $|\zeta(1/2+it)|$ on the Riemann hypothesis, Bull. London Math. Soc. 43 (2011), no. 2, 243–250.

A. Y. Cheer and D. A. Goldston, Simple zeros of the Riemann zeta-function, Proc. Amer. Math. Soc. 118 (1993), no. 2, 365–372.

A. Chirre, A note on Entire $L$-functions, Bull. Braz. Math. Soc., to appear.

H. Cohn and N. Elkies, , Ann. of Math. (2) 157 (2003), no. 2, 689–714.

H. Cohn and F. Gonçalves, An optimal uncertainty principle in twelve dimensions via modular forms, arXiv:1712.04438 \[math.CA\].

H. Cohn and S. D. Miller, , .

H. Cohn, A. Kumar, S. D. Miller, D. Radchenko, and M. Viazovska, The sphere packing problem in dimension $24$, Ann. of Math. (2) [185]{} (2017), no. 3, 1017–1033.

D. Farmer, S. Gonek and Y. Lee, Pair correlation of the zeros of the derivative of the Riemann $\xi$-function, J. Lond. Math. Soc.(2) 90 (2014), no. 1, 241–269.

C. Fieker, W. Hart, T. Hofmann and F. Johansson, ,

P. X. Gallagher, Pair correlation of zeros of the zeta function, J. Reine Angew. Math. 362 (1985), 72–86.

D. A. Goldston and S. M. Gonek, A note on S(t) and the zeros of the Riemann zeta-function, Bull. Lond. Math. Soc. 39 (2007), no. 3, 482–486.

D. A. Goldston, S. M. Gonek, A. E. Özlük and C. Snyder, On the pair correlation of zeros of the Riemann zeta-function, Proc. London Math. Soc. (3) 80 (2000), no. 1, 31–49.

D. A. Goldston and H. L. Montgomery, Pair correlation of zeros and primes in short intervals, in [*Analytic number theory and Diophantine problems*]{} (ed. A. C. Adolphson, J. B. Conrey, A. Ghosh and R. I. Yager), Birkhaüser, Boston (1987), 183–203.

F. Gonçalves, M. Kelly and J. Madrid, One-sided band-limited approximations of some radial functions, Bull. Braz. Math. Soc. (N.S.) 46 (2015), no. 4, 563–599.

S. W. Graham and J. D. Vaaler, A class of extremal functions for the Fourier transform, Trans. Amer. Math. Soc. 265 (1981), no. 1, 283–302.

J. Holt and J. D. Vaaler, The Beurling-Selberg extremal functions for a ball in the Euclidean space, Duke Math. J. 83 (1996), no. 1, 202–248.

F. Johansson, Arb: efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Transactions on Computers, 66 (2017), no. 8, 1281–1292.

D. de Laat, F. Oliveira, F. Vallentin, Upper bounds for packings of spheres of several radii, Forum Math. Sigma 2 (2014), e23, 42 pp.

J. Löfberg, Pre- and post-processing sums-of-squares programs in practice IEEE Trans. Automat. Control 54 (2009), 1007–1011.

H. L. Montgomery, The pair correlation of zeros of the zeta function, Proc. Symp. Pure Math. 24, Providence (1973), 181–193.

M. Nakata, A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite programming solver: SDPA-GMP,-QD and-DD, In Computer-Aided Control System Design (CACSD), 2010 IEEE International Symposium on, pages 29–34. IEEE, 2010.

G. Pólya, G. Szegö, Problems and theorems in analysis. II, Classics in Mathematics, Springer-Verlag, 1998; Translated from German by C. E. Billigheimer; Reprint of the 1976 English translation.

K. Sono, A note on simple zeros of primitive Dirichlet L-functions, Bull. Aust. Math. Soc. 93 (2016), no. 1, 19–30.

J. D. Vaaler, Some extremal functions in Fourier analysis, Bull. Amer. Math. Soc. (N.S.) 12 (1985), no. 2, 183–216.

M. S. Viazovska, The sphere packing problem in dimension $8$, Ann. of Math. (2) [185]{} (2017), no. 3, 991–1015.

[^1]: For every sum over zeros in this article the involved quantities should be repeated according to the multiplicity of the zero.

[^2]: It is worth mentioning that, in a related uncertainty problem, Cohn and Gonçalves [@CGo] discovered the same kind of instability in low dimensions.
