Tight bounds on the partial Möbius sum $\sum_{\substack{d|n\\dAn important area of study in Analytic Number Theory is the behavior of the Möbius function $\mu(n)$. I was trying to prove a different theorem when I came about a very interesting behavior. If you look at the partial sums of the sum of the Möbius function over the divisors of $n$, namely
$$A_Q(n)=\sum_{\substack{d|n\\d<Q}}\mu(d)$$
We see extraordinary cancelling. If we take $Q$ to larger than the maximum divisor than $n$ then of course this sum will be $0$ for $n>1$, but I would still have expected large partial sums. If we define
$$\omega_Q(n)=\sum_{\substack{p|n\\p<Q}}1$$
to be the number of distinct prime factors of $n$ less than $Q$, then my conjecture is that there exists an integer $k$ such that
$$\left| A_Q(n)\right|=O\left(\omega_Q(n)^k\right)$$
There is strong numerical evidence to back this up. I have experimentally seen that, for a given count $j$ of prime factors less than $Q$, $\left| A_Q(n)\right|$ finds its largest values when $n=p_1p_2\cdots p_j$ is the product of the first $j$ primes. I then used Desmos to create the best-fit cubic which has an $r^2$ value of $.999$: It is essentially a perfect fit. This means that is highly probable that
$$A_Q(n)=O\left(\omega_Q(n)^3\right)$$
but even proving that it is polynomial in $\omega_Q(n)$ is difficult. Does anyone have any ideas or know of any papers that discuss this topic?
 A: It turns out that there is no polynomial bound in terms of $\omega_Q(n)$. Namely, this happens if one chooses all of the primes to be "equal". This isn't possible but in practice one can choose groups of primes that are arbitrarily tightly packed with respect to their size, see [here][1], which gets us the same results.
If all of the primes are equal then we can choose $Q$ such that any group of $j$ primes is less than $Q$ but any group of $j+1$ primes is greater than $Q$, and thus by counting the number of divisors of $n$ with any given number of prime factors less than $j$ signed according to the Mobius function we see that
$$A_Q(n)=\sum_{k=0}^{j}{ {\omega_Q(n)}\choose{k}}(-1)^{k}$$
For large values of $j$ this sum will be dominated by it's last term, namely
$$A_Q(n)=(1-o(1)){ {\omega_Q(n)}\choose{j}}(-1)^j$$
where the $o(1)$ is with respect to $j$. We can thus get the sharp bound (in terms of $\omega_Q(n)$) that
\begin{equation}
|A_Q(n)|<{ {\omega_Q(n)}\choose{\omega_Q(n)/2}}\tag{1}
\end{equation}
since $j=\omega_Q(n)/2$ maximizes ${ {\omega_Q(n)}\choose{j}}$. Using more complex methods one can rigorously show that this is indeed the best bound, and that (1) always holds. Using stirling's approximation on (1) we get that
\begin{equation}
|A_Q(n)|<\frac{2^{\omega_Q(n)}}{\sqrt{\omega_Q(n)}}
\end{equation}
which is a much more useful bound. Namely, it can get us results about the quantity $\mathbf{E}_{n\in\mathbb{N}}\left[|A_Q(n)|\right]$. The trivial bound by counting terms gives us that
$$\mathbf{E}_{n\in\mathbb{N}}\left[|A_Q(n)|\right]<\frac{6}{\pi^2}\log(Q)$$
but using this new bound we can improve this to
$$\mathbf{E}_{n\in\mathbb{N}}\left[|A_Q(n)|\right]<C\frac{\log(Q)}{\sqrt{\log(\log(Q))}}$$
EDIT: It turns out that the true bound (the proof is too long to include here) is that
$$\mathbf{E}_{n\in\mathbb{N}}\left[|A_Q(n)|\right]<c_0$$
for some absolute constant $c_0$
[1]: https://annals.math.princeton.edu/wp-content/uploads/Maynard.pdf
