# A possible error in Elliot's book “Probabilistic Number Theory”

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*}

Since

$$\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.

SIDE QUESTION:

In the book, there are many inequalities given for the sum $$\sum_{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 feels much more natural to study, and $$\sum_{p feels like a logarithmically weighted version. Does anyone know of any inequalities for $$\sum_{p?

• Can you give the page number in Elliot's book, and a reference to the cited paper? – Nate Eldredge Sep 2 '20 at 23:21
• 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. – Nate Eldredge Sep 2 '20 at 23:28
• In Roth's paper one has the condition $Q \ge \frac {\sqrt N}{\sqrt {\log N}}$, otherwise the inequality is more complicated – Conrad Sep 2 '20 at 23:40
• @GHfromMO I already did, a few minutes ago. – Milo Moses Sep 2 '20 at 23:54
• 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 – Conrad Sep 2 '20 at 23:59

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.
• Is there a similar inequality to this one but with $p^2$, i.e $\sum_{p\leq Q}p^2V(p)$? – Milo Moses Sep 2 '20 at 23:53
• @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. – GH from MO Sep 2 '20 at 23:57
• 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. – Milo Moses Sep 3 '20 at 0:05
• 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$. – GH from MO Sep 3 '20 at 0:21
• 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$. – Milo Moses Sep 3 '20 at 0:25