2
$\begingroup$

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

$$\lim_{N\to\infty}\frac{1}{N\pi(Q)}\sum_{n<N}\left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right|=\Omega(\sqrt{\log(Q)})$$

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

$$\lim_{N\to\infty}\frac{1}{N\pi(Q)}\sum_{n<N}\left|\sum_{\substack{p<Q\\p|n}}p-\pi(Q)\right|=\Omega(\log(Q)^{-\epsilon})$$

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

$\endgroup$
5
  • $\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$ Oct 28, 2020 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, 2020 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$ Oct 28, 2020 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$ Oct 28, 2020 at 7:49
  • $\begingroup$ @MiloMoses Yes, I made a mistake. Sorry about that! $\endgroup$ Nov 10, 2020 at 13:19

1 Answer 1

2
$\begingroup$

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

$\endgroup$
5
  • $\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, 2020 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$ Oct 28, 2020 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, 2020 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$ Oct 29, 2020 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, 2020 at 15:13

Your Answer

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

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