# Prove or disprove that $\sup_{n\in\mathbb{N}}\left|\sum_{\substack{d|n \\d<Q}}\mu(d)\right|\sim\pi(Q)$

To begin, let us set

$$A_Q(n):=\sum_{d|n \\ 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

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

$$\sup_{n\in\mathbb{N}}|A_Q(n)|\sim_{Q\to\infty}\pi(Q)$$

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.

• $A_Q(\prod_{p\in (Q^{1/2},Q)} p) = 1-(\pi(Q-1)-\pi(Q^{1/2}))$ – reuns Jan 10 at 1:35
• 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... – fedja Jan 10 at 2:43
• @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... – Milo Moses Jan 10 at 6:07
• @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? – fedja Jan 10 at 9:49
• @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. – Milo Moses Jan 10 at 16:17

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).
• 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. – reuns Mar 31 at 7:42