# Examples of the large sieve inequality where a constant larger than 1 is needed

Let $S(x) = \sum_{n=0}^{N-1} a_n e^{2 \pi i n x}$ be a trigonometric polynomial of length $N$. The analytic/harmonic large sieve inequality in its sharpest form states that

$$\sum_{r=1}^R |S(x_r)|^2 \leq (N + \delta^{-1}-1) \int_{0}^{1} |S(x)|^2 dx$$

where $x_1,x_2,\ldots,x_R$ are $\delta$ separated points. This can be thought of as a discretization of Parseval's identity on the circle.

In many of the applications of this inequality to number theory one takes $\delta = 1/N$ in which case the right hand side of the inequality has a factor $2N$.

The factor of $2$ here leads to some very unfortunate inefficiencies in sieve theoretic applications, such as the $2$ in the Brun-Titchmarsh inequality. It seems that improving the factor of $2$ in these applications is related to both the parity problem in sieve theory and the Siegel zero problem. See, for instance, this paper of Maynard.

However it is easy to see in some cases, such as when $x_1,x_2, \ldots, x_R$ are equally spaced (using Fourier analysis on the group of residues mod $N$), that the inequality indeed holds with a constant $1$ in place of the constant $2$.

Are there examples of trigonometric polynomials and $\delta = 1/N$ separated points known where the constant in the analytic large sieve inequality is required to be greater than $1$?

• You want $x_1,x_2,\dots,x_N$ to be $\delta$-separated on the circle with $\delta=1/N$. This means that $x_1,x_2,\dots,x_N$ are equally spaced, so it seems that the sentence before your question answers the question. Commented Jul 10, 2017 at 22:28
• I think you meant Parseval and not Parsavel. I don't have edit privileges so I won't change it but it might be useful to the interested reader. Commented Jul 10, 2017 at 22:32
• @SylvainJULIEN: I fixed this, thanks for pointing it out. Commented Jul 10, 2017 at 22:36
• @GH, the question should be posed with $m$ points which is permitted to be less than $N$ which eliminates the issue you identified. I have reworded the question. It seems Selberg's examples require $\delta^{-1} | N-1$ so one has no hope of getting a constant greater than $3/2$ from these. What's particularly interesting to me is that question of if the constant $2$ can be reduced is a purely analytic issue which, if true, would seems to have very deep arithmetic consequences. Commented Jul 11, 2017 at 0:06
• Ack. That's what I was looking for. Thanks. Commented Jul 11, 2017 at 5:15

1) Montgomery's survey paper https://projecteuclid.org/euclid.bams/1183540922

page 559, Theorem 3 and equation (19). It essentially says that Selberg gave an example, with the comment that this is the only situation where this is sharp.

See also page 563 for lower bounds on $\Delta$, and also upper bounds, when one is sieving modulo some subset of the integers $q\leq Q$.

This paper gives links to the rich literature of that time.

2) Similarly, also some comments after Theorem 4.7 of Tenenbaum's Introduction to analytic and probabilistic number theory, (3rd edition).

Two more recent items, maybe not so well known:

3) Vandermonde Matrices with Nodes in the Unit Disk and the Large Sieve, C\'eline Aubel and Helmut Bölcskei https://arxiv.org/abs/1701.02538

4) Refinements of Selberg's sieve, Sara Elizabeth Blight, PhD Thesis, Rutgers, 2010.

Especially chapter 4 https://rucore.libraries.rutgers.edu/rutgers-lib/27420/

• I don't think that Selberg's example answers the question. In Montgomery's notation, the example requires $R\mid N-1$ sample points, i.e. less than $N$ sample points. The OP wants $N$ sample points with $\delta=1/N$. So the OP's sample points are necessarily equidistributed at which point I am getting confused myself, so I will ask him in a remark. Note also that Montgomery has a typo: in the display below (19), $\frac{N-1}{R}R+1$ should be $\frac{N-1}{R}+1$. Commented Jul 10, 2017 at 22:20
• Inequality of Bombieri (11) from Montgomery's survey: is not it just a particular case of Schur test? I start suspecting that there is a lack of communication between number. theory and harm. analysis. Commented Jul 11, 2017 at 18:15