In Elliot's book "Probabilistic Number Theory", there seems to be an inaccuracy. The author defines, for any sequence $a_n$, the quantity

$$V(p)=\sum_{r=0}^{p-1}\left|\sum_{\substack{n=1 \\n \equiv r\mathrm{mod}(p)}}^N a_n-p^{-1}\sum_{n=1}^N a_n \right|^2$$

He then asserts that, if $a_n$ assumes only the values 0,1, then

$$\sum_{p\leq Q}pV(p)\leq c_1 Q^2 \log(Q)\sum_{n=1}^N|a_n|^2$$

where $c_1$ is some absolute constant. The issue is, this would imply that

$$\limsup_{N\to\infty}\sum_{p\leq Q}p\frac{V(p)}{N^2}\leq c_1 Q^2 \log(Q)\limsup_{N\to\infty}\frac{1}{N^2}\sum_{n=1}^N|a_n|^2=0$$

which isn't always true. An easy counter-example is $a_n$ defined as $0$ when $n$ is even and $1$ when $n$ is odd, and $Q=2$. Namely, we have that

\begin{align*} \sum_{p\leq Q}p\frac{V(p)}{N^2} &= 2\frac{V(2)}{N^2}\\ &=\frac{2}{N^2}\sum_{r=0}^{1}\left|\sum_{\substack{n=1 \\n \equiv r\mathrm{mod}(2)}}^N a_n-\frac{1}{2}\sum_{n=1}^N a_n \right|^2\\ &=2\sum_{r=0}^{1}\left|\frac{1}{N}\sum_{\substack{n=1 \\n \equiv r\mathrm{mod}(2)}}^N a_n-\frac{1}{2N}\sum_{n=1}^N a_n\right|^2\\ &=2\left|\frac{1}{N}\sum_{\substack{n=1 \\n \equiv 0\mathrm{mod}(2)}}^N a_n-\frac{1}{2N}\sum_{n=1}^N a_n\right|^2+2\left|\frac{1}{N}\sum_{\substack{n=1 \\n \equiv 1\mathrm{mod}(2)}}^N a_n-\frac{1}{2N}\sum_{n=1}^N a_n \right|^2\\ \end{align*}


$$\lim_{N\to\infty}\frac{1}{2N}\sum_{n=1}^Na_n=\frac{1}{4}$$ $$\lim_{N\to\infty}\frac{1}{N}\sum_{\substack{n=1 \\n \equiv 1\mathrm{mod}(2)}}^N a_n=\frac{1}{2}$$ $$\lim_{N\to\infty}\frac{1}{N}\sum_{\substack{n=1 \\n \equiv 0\mathrm{mod}(2)}}^N a_n=0$$

We see that

$$\lim_{N\to\infty}\sum_{p\leq Q}\frac{V(p)}{N^2}=2\left(\frac{1}{4}\right)^2+2\left(\frac{1}{4}\right)^2=\frac{1}{8}$$

Numerical computations show that $\frac{1}{8} \neq 0$ and thus this is a contradiction. The paper cited for this result is locked behind a paywall so I cannot access it and see what the true theorem is. Does anyone know what the actual result should have been? Where is the typo?

The paper cited with the result is

Roth, Klaus F., On the large sieves of Linnik and Renyi, Mathematika, Lond. 12, 1-9 (1965). ZBL0137.25904.


In the book, there are many inequalities given for the sum $\sum_{p<Q}pV(p)$, but if you think about $V(p)$ as being on the order of $\frac{N^2}{p^2}$ for large $N,p$ (which is the worst-case scenario), then the sum $\sum_{p<Q}p^2V(p)$ feels much more natural to study, and $\sum_{p<Q}pV(p)$ feels like a logarithmically weighted version. Does anyone know of any inequalities for $\sum_{p<Q}p^2V(p)$?

  • $\begingroup$ Can you give the page number in Elliot's book, and a reference to the cited paper? $\endgroup$ Sep 2, 2020 at 23:21
  • 1
    $\begingroup$ There's an "Insert Citation" button when you edit that will let you insert the full citation (title, authors, journal reference, DOI), pulled from Zbmath. Anyway it's better to have this info in the question instead of a comment which is not meant to be permanent. $\endgroup$ Sep 2, 2020 at 23:28
  • 1
    $\begingroup$ In Roth's paper one has the condition $Q \ge \frac {\sqrt N}{\sqrt {\log N}}$, otherwise the inequality is more complicated $\endgroup$
    – Conrad
    Sep 2, 2020 at 23:40
  • 1
    $\begingroup$ @GHfromMO I already did, a few minutes ago. $\endgroup$
    – Milo Moses
    Sep 2, 2020 at 23:54
  • 1
    $\begingroup$ The result in Roth is as folows (actually he allows the sum to be on a subset of the primes less than $Q$, using the appropriate cardinality instead of $P(Q)$) but ignoring that and taking the full sum one gets: $\sum_{p\leq Q}pV(p)\leq c(ZN+ZQ^2\log(R)+Z^2P(Q)R^{-2}), c$ absolute constant, where $Z$ is the cardinality of the set $n \le N, a_n=1$ (so $\sum a_n=\sum a_n^2$ etc in this special case), $R \ge 2$ parameter, $P(Q)$ the number of primes $\le Q$; choosing $R=Q \ge \frac{\sqrt N}{\sqrt {\log N}}$ gives $\sum_{p\leq Q}pV(p)\leq c_1ZQ^2\log Q$ which is what Elliott quotes $\endgroup$
    – Conrad
    Sep 2, 2020 at 23:59

1 Answer 1


You are right that the second display is false in general (Elliott might impose some conditions). The following version is well-known, and a consequence of Selberg's optimized large sieve inequality: $$\sum_{p\leq Q}pV(p)\leq (N+Q^2-1)\sum_{n=1}^N|a_n|^2.$$ This holds for any complex numbers $a_n$. See (23) in Montgomery: The analytic principle of the large sieve. Well, Montgomery has $N+Q^2$ instead of $N+Q^2-1$, but the latter is also valid in the light of Theorem 3 in Montgomery's survey.

  • $\begingroup$ Is there a similar inequality to this one but with $p^2$, i.e $\sum_{p\leq Q}p^2V(p)$? $\endgroup$
    – Milo Moses
    Sep 2, 2020 at 23:53
  • $\begingroup$ @MiloMoses: I don't know. On the other hand, $\sum_{p\leq Q}p^2V(p)$ is at most $Q$ times $\sum_{p\leq Q}pV(p)$, and this is practically optimal. Indeed, in practice one would localize $p$ between $Q/2$ and $Q$, and then the new sum is essentially $Q$ times the old sum. $\endgroup$
    – GH from MO
    Sep 2, 2020 at 23:57
  • $\begingroup$ I don't think that this is entirely correct. If $\lim_{N\to\infty}\frac{p^2V(p)}{N^2}=V'(p)$ exists for every prime $p$, which is true for many bounded sequences $a_n$, then one can relatively easily get that $\frac{1}{\pi(Q)} \sum_{p\leq Q}p^2V(p)\to0$, whereas the "practically optimal" bound would only imply boundedness. My main question is whether or not this implied rate of convergence to $0$ is global or if there are some sequences for which the convergence to $0$ is arbitrarily slow. $\endgroup$
    – Milo Moses
    Sep 3, 2020 at 0:05
  • $\begingroup$ You seem to think of $V(p)$ as a function of $N$, with a fixed sequence $(a_n)$. That is fine, but then I don't know what you mean by $\frac{1}{\pi(Q)} \sum_{p\leq Q}p^2V(p)\to0$. Under what condition? There are two variables going to infinity in your setup: $N$ and $Q$. $\endgroup$
    – GH from MO
    Sep 3, 2020 at 0:21
  • $\begingroup$ Sorry, that was a typo. I meant to say that $\frac{1}{\pi(Q)}\sum_{p\leq Q}p^2V'(p)\to 0$, since $V'$ is purely a function of $p$. $\endgroup$
    – Milo Moses
    Sep 3, 2020 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.