To begin, let us set

$$A_Q(n):=\sum_{d|n \\ d<Q}\mu(d)$$

If we fix $Q$ and let $n$ vary, we get a very surprising amount of cancellation. For instance, the trivial bound

\begin{align*} \mathbb{E}_{n\in\mathbb{N}}\left[|A_Q(n)|\right]&\leq\mathbb{E}_{n\in\mathbb{N}}\left[\sum_{\substack{d|n \\ d<Q}}1\right]\\ &=\sum_{d=1}^{Q-1}\frac{1}{d}\sim\log(Q) \end{align*}

can be reduced to the (astonishing) $\mathbb{E}_{n\in\mathbb{N}}[|A_Q(n)|]=O(1)$, and even more strongly $\mathbb{E}_{n\in\mathbb{N}}[|A_Q(n)|^2]=O(1)$. The question now turns the exact nature of the distribution of $A_Q(n)$ over $\mathbb{N}$ as $Q$ varies.

On the "maximum" side of things, the only trivial bound is using Sperner's Lemma which yields the inequality

$$\sup_{n\in\mathbb{N}}|A_Q(n)|\leq {\pi(Q)\choose \pi(Q)/2}\leq \frac{2^{\pi(Q)}}{\sqrt{\pi(Q)}}$$

Stronger results require finer knowledge of the distribution of primes, and more specifically getting a large value $A_Q(n)$ means that the prime factors of $n$ are tightly packed and so large values of $A_Q(n)$ are morally equivalent to repeated small prime gaps (i.e a reltively small interval $M$ in which many primes appear). While proving any results seem difficult, numerical evidence suggests the following miraculous asymptotic relationship


There are other seemingly miraculous properties of $A_Q(n)$, like the fact that the probabilities $\Pr_{n\in\mathbb{N}}[A_Q(n)=j]$ seem to converge as $Q\to\infty$ for any $j$, but that is a different can of worms entirely.

If somebody could give any insights about how someone would even try to go about proving $\sup_{n\in\mathbb{N}}|A_Q(n)|\sim_{Q\to\infty}\pi(Q)$ I would be extremely grateful, since currently all of my approaches seem to only result in weak upper bounds.

  • 3
    $\begingroup$ $A_Q(\prod_{p\in (Q^{1/2},Q)} p) = 1-(\pi(Q-1)-\pi(Q^{1/2}))$ $\endgroup$
    – reuns
    Commented Jan 10, 2021 at 1:35
  • $\begingroup$ the only trivial bound is using Sperner's Lemma... I would say "the most trivial bound is $Q$: at most $Q$ terms each of which is at most $1$". The bound $\pi(Q)$ is, of course not so immediate... $\endgroup$
    – fedja
    Commented Jan 10, 2021 at 2:43
  • $\begingroup$ @fedja are you sure about that? The $\pi(Q)$ comes from the fact that the sum $\sum_{\substack{d|n \\ d<Q}}\mu(d)$ is a sum over $2^{\pi(Q)}$ points, for quite immediate reasons... $\endgroup$
    – Milo Moses
    Commented Jan 10, 2021 at 6:07
  • $\begingroup$ @MiloMoses Then I just don't understand your notation: I thought that $d<Q$ means $d\in[1,2,\dots,Q]$ and $\pi(Q)$ is the usual prime counting function, but, apparently, you mean something else. What is it then? $\endgroup$
    – fedja
    Commented Jan 10, 2021 at 9:49
  • $\begingroup$ @fedja The notation you assumed I am using is correct. The bound $Q$ is immediate, I agree, but the bound $\frac{2^{\pi(Q)}}{\sqrt{\pi(Q)}}$ was used instead to illustrate a bound which uses properties of the Mobius function, even if it is less sharp. By "The bound $\pi(Q)$ is, of course not so immediate" I thought you were referring to the bound $\frac{2^{\pi(Q)}}{\sqrt{\pi(Q)}}$ as the "bound based on $\pi(Q)$", but I see now that that was a misunderstanding. $\endgroup$
    – Milo Moses
    Commented Jan 10, 2021 at 16:17

1 Answer 1


This is not true. In fact $$ x(\log x)^{-1+1/\pi} \gg \sup_n \Big| \sum_{\substack{ d|n \\ d\le x}} \mu(d) \Big| \gg x (\log x)^{-1+1/\pi}. $$ The upper bound is due to Montgomery and Vaughan (see Theorem 5 there) and the lower bound is due to Hall and Tenenbaum (see the references in Montgomery and Vaughan).

  • 3
    $\begingroup$ Thank you SO MUCH for this reference!!!!!!! $\endgroup$
    – Milo Moses
    Commented Jan 10, 2021 at 6:08
  • $\begingroup$ Hi, do you know if this is well-known, that $f(x)-\sum_{\Im(\rho)>0} e^{i\rho x}$ is analytic at $0$ for some "elementary" function $f$, it should give non-obvious information on the distributions of non-trivial zeros. Also the expression seems to be continuous in $\epsilon$ when replacing $\zeta(s)$ by $\zeta(s)+\epsilon L(s,\chi)$, which is surprising. $\endgroup$
    – reuns
    Commented Mar 31, 2021 at 7:42

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.