As the title of the question susggests, I would like to show that

The "trivial bound is that"

\begin{align*} \lim_{Q\to\infty}\lim_{N\to\infty}\frac{1}{N\pi(Q)}\sum_{n<N}\left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right|&\leq \lim_{Q\to\infty}\lim_{N\to\infty}\frac{1}{N\pi(Q)}\sum_{n<N}\left(\sum_{\substack{p<Q\\p|n}}p+\pi(Q)\right)\\ &=2 \end{align*}

where the equality is obtained by noting that $\frac{1}{p}$ numbers are multiplies of $p$, so the expected value of $\sum_{\substack{p<q \\ p|n}}p$ is exactly $\sum_{p<Q}1=\pi(Q)$. Thus, we are looking only for a "$o(\cdot)$" improvement. The first thought of mine would be to note that since $\sum_{\substack{p<q \\p|n}}p$ is an additive function and so by the Turan-Kubilius inequality

$$\sum_{n<N}\left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right|^2\leq 4N\sum_{p<Q}p$$

The issue is, this inequality is worse than the trivial one since apply Cauchy-Shwartz we get that this inequality yields

\begin{align*} \frac{1}{N\pi(Q)}\sum_{n<N}\left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right|&\leq \frac{1}{\pi(Q)}\sqrt{\frac{1}{N}\sum_{n<N}\left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right|^2}\\ &\leq \frac{2}{\pi(Q)}\sqrt{\sum_{p<Q}p}\\ \end{align*}

where by the PNT this last term is on the order of $\sqrt{\frac{Q^2}{\log(Q)}}=\frac{Q}{\sqrt{\log(Q)}}$. This inequality would indicate to us that the sum would $\mathit{diverge}$, namely


I have proved that the sum can't go to zero too fast, and specifically that


for any $\epsilon>0$. It does, however, feel natural that this sum should be at least $o(1)$.

  • $\begingroup$ I think the third equation should read: $\cdots \leq \frac{1}{\sqrt{N}\pi(Q)} \sqrt{\frac{1}{N}\cdots}$ which implies that the limit as $N$ tends to infinity is $0$. $\endgroup$ – David Tweedle Oct 28 '20 at 2:21
  • 1
    $\begingroup$ @DavidTweedle Are you sure that you accounted for the extra factor of $N$ that appears in the square root when you apply Cauchy-Shwartz? $\endgroup$ – Milo Moses Oct 28 '20 at 2:28
  • 2
    $\begingroup$ The inner limit, $\lim_{N\to\infty}\frac 1{N\pi(Q)}\sum_{n<N}\left|\sum_{p<Q,\,p|n} p-\pi(Q)\right|$ is exactly $\frac1{M\pi(Q)}\sum_{n<M}\left|\sum_{p<Q,\,p|n} p-\pi(Q)\right|$, where $M$ is the product of all primes less than $Q$ since the summand in absolute values is $M$-periodic in $n$. $\endgroup$ – Anthony Quas Oct 28 '20 at 7:37
  • 1
    $\begingroup$ If $n$ is uniformly distributed on the set $\{1,\ldots,M\}$, then the events $p|n$ are mutually independent for all $p<Q$. This means you can rewrite the inner limit as $\frac 1{\pi(Q)}\mathbb E\left|\sum_{p<Q} X_p-\pi(Q)\right|$, where the $X_p$'s are independent random variables taking the value $p$ with probability $\frac 1p$ and 0 otherwise. $\endgroup$ – Anthony Quas Oct 28 '20 at 7:49
  • $\begingroup$ @MiloMoses Yes, I made a mistake. Sorry about that! $\endgroup$ – David Tweedle Nov 10 '20 at 13:19

It seems that the conjecture is false, if I did not miss some asymptotc issue The essence of what follows is that I show that the interior limit exceeds any function of $Q$ tending to $0$.

For any $t\geq 1$, denote by $p_t(Q)$ the density of those $n$ divisible by at least one $p$ with $t\pi(Q)<p<Q$. We have \begin{align*} p_t(Q)&=1-\prod_{t\pi(Q)<p<Q}\left(1-\frac1p\right) \sim 1-\exp\left(\sum_{t\pi(Q)<p<Q}\frac1p\right) \sim 1-\frac{\log Q}{\log (t\pi(Q))}\\ &\sim 1-\frac{\log Q}{\log Q+\log t-\log\log Q} =\frac{\log\log Q-\log t}{\log Q+\log t-\log\log Q}\\ &\sim \frac{\log\log Q-\log t}{\log Q}, \end{align*} where the estimates work in the regime $t\leq o(Q/\pi(Q))=o(\log Q)$. (More precisely, in any such regime this equivalence is uniform over $t\leq o(\log Q)$, as $q\to\infty$.)

Assume now that your conjecture is true, i.e., that $$ f(Q):=\lim_{N\to\infty}\frac{1}{N\pi(Q)}\sum_{n<N}\left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right| \to 0, \qquad Q\to\infty. $$ Take $N$ to be a multiple of $Q!$. Notice that at least $p_t(Q)N$ of the summands are larger than $(t-1)\pi(Q)$. Put $q=\log Q$. Summing up over $t=2,3,\dots,qf(Q)=o(q)$, we obtain \begin{align*} \frac1{N\pi(Q)}\sum_{n<N}\left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right| &\buildrel(*)\over\ge \sum_{t=2}^{qf(Q)} p_t(Q) \sim \sum_{t=2}^{qf(Q)} \frac{\log q-\log t}{q} =\frac1q\log\frac{q^{qf(Q)}}{(qf(Q))!}\\ &\sim \frac1q\log\left(\frac{qe}{qf(Q)}\right)^{qf(Q)} \sim f(Q)(-\log f(Q)). \end{align*} Since $f(Q)=o(1)$, the limit of the above expression as $N\to\infty$ cannot equal $f(Q)$.

Remark. The inequality $(*)$ holds, because if a number $n$ is accounted for $x$ times in the right sum, then its large prime divisor $p$ is larger than $(x+1)\pi(Q)$, so that $$ \left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right|>x\pi(Q). $$

  • $\begingroup$ Are you sure that there are no issues with counting numbers multiple times in the sum $\sum_{t=2}^{qf(Q)}p_t(Q)$? If it is the density of primes where at least on prime divides in that in those intervals, numbers which appear in the tightest interval will also appear in every other term. $\endgroup$ – Milo Moses Oct 28 '20 at 15:50
  • $\begingroup$ It seems that I am; notice that there is no $\sim$ sign there. I've added a clarification in the Remark at the end. If you are unsure about some other steps --- feel free to ask, this is really sketchy; sorry for that. $\endgroup$ – Ilya Bogdanov Oct 28 '20 at 16:24
  • $\begingroup$ Could you expand the last step in the first line of math where you claim that $1-\frac{\log(Q)}{\log(t\pi(Q))}$ is asymptotic to a much simpler expression (and at a uniform rate) $\endgroup$ – Milo Moses Oct 28 '20 at 16:37
  • $\begingroup$ I've inserted a line into the equation. Is it really the place you got troubls, or perhaps you meany a different one? $\endgroup$ – Ilya Bogdanov Oct 29 '20 at 6:03
  • $\begingroup$ Though it pains me to say it, I can't find any more questionable steps in your proof. Thank you very much for your help. $\endgroup$ – Milo Moses Oct 29 '20 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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