Let $S(\alpha) = \sum_{n\leq N}f(n) e^{2\pi i \alpha n}$ for some arithmetic function $f$. Suppose $\alpha_1, \ldots, \alpha_R$ are real numbers that are $\delta$-spaced modulo $1$, for some $0 < \delta < 1/2$. The large sieve inequality then gives
$$
\sum_{r=1}^R \left| S\left(\alpha_r \right)\right|^2 \ll (N + \delta^{-1}) \sum_{n\leq N}|f(n)|^2.
$$
The $N$ term is satisfactory when the support of $f$ is dense enough in $[1,N]$. However it becomes worse the sparser the support of $f$ is.
Are there any methods or inequalities or examples known in literature to tackle the case when the support of $f$ is sparse, say when $\#(\text{supp}(f) \cap [1,N]) \asymp \sqrt{N}$. Even in this extreme of $\sqrt{N}$ the large sieve can give non-trivial cancellation, but can one do better?
Best Answer
If $f$ is $M$-sparse, then from Cauchy-Schwarz one has $|S(\alpha)|^2 \leq M \sum_{n \leq N} |f(n)|^2$ which gives the bound $$ \sum_{r=1}^R |S(\alpha_r)|^2 \leq R M \sum_{n \leq N} |f(n)|^2$$ which is superior in the regime $RM \leq N$ (i.e., below the range of the Heisenberg uncertainty principle). For $RM \geq N$ one is now consistent with the uncertainty principle and one cannot hope to do better than the large sieve in general. Indeed, if $M$ divides $N$ and $f$ is the indicator function of the multiples $\{ mN/M: m=1,\dots,M\}$ of $N/M$, then $S(\alpha)=M$ for $\alpha$ a multiple of $M/N$, so if one chooses $\alpha_1,\dots,\alpha_R$ to contain the $N/M$ different multiples of $M/N$ mod $1$ (and sets $\delta$ to be anything less than or equal to $M/N$) then equality in the large sieve is essentially attained.
Note that in this example $f$ had a lot of additive structure (in particular the support was basically closed under addition). If $f$ is additively unstructured (e.g., if it is supported on a dissociated set) then one can do better by taking higher moments. For instance by applying the large sieve to $f*f$ rather than to $f$ one has $$ \sum_{r=1}^R |S(\alpha_r)|^4 \ll (N + \delta^{-1}) \sum_{n \leq 2N} |f*f(n)|^2$$ and hence by Cauchy-Schwarz $$ \sum_{r=1}^R |S(\alpha_r)|^2 \ll R^{1/2} (N + \delta^{-1})^{1/2} (\sum_{n \leq 2N} |f*f(n)|^2)^{1/2}.$$ If $f$ is not very additively structured, then $f*f$ will be quite spread out and this can be a superior bound to the previously mentioned bounds. Similarly if one plays with higher convolutions such as $f*f*f$. Basically one is convolving one's way out of sparsity in order to make more efficient use of the large sieve. (A similar technique is frequently employed to study large values of Dirichlet polynomials, taking advantage of the fact that the logarithms $\log n$ of the natural numbers only have a very limited amount of additive structure, thanks to the divisor bound.)
As a variant of the above strategy, if $f$ is supported in some set $E$ on which good bounds are known on exponential sums $\sum_{n \in E} e(\alpha n)$ (or weighted versions of such sums) - which is a measure of lack of additive structure in $E$ - then one can sometimes get good bounds from a duality argument (sometimes known as a "large values" argument, particularly in the context of controlling the large values of Dirichlet polynomials). See for instance
Green, Ben; Tao, Terence, Restriction theory of the Selberg sieve, with applications, J. Théor. Nombres Bordx. 18, No. 1, 147-182 (2006). ZBL1135.11049.
for an example of this (where the function $f$ is supported on something like the set of primes).