Let $p$ be a prime number and consider the sum $S(x)=\sum_{n\le x}\left(\frac{n}{p}\right)\mu(n)$. For how small an $x$ in terms of $p$ is it known that $S(x)=o(x)$? I am especially interested in unconditional results.

$\begingroup$ Mobius randomness have gained much attention in the last couple of years (see Peter's notes in the IAS site), but your question is essentially equivalent to Dirichlet's theorem, and hence an effective version like you've asked for should follow from probably some effective proof of the PNT (with the Lfunction twisted by the quadratic character, as done in Dirichlet's original proof). Moreover you should quantify exactly the cancellation you want, littleo is an asymptotic term. $\endgroup$– AsafCommented Jul 26, 2013 at 11:33

$\begingroup$ A quick computation showed that you will have $S(x) = o(x)$ whenever $x > \exp(C (\log p)^{10})$ with $C$ some large absolute constant. Is this the kind of result you are looking for? It seems to me that the power on the $\log p$ can be significantly improved (I have only used the simplest bounds). $\endgroup$– blablerCommented Jul 26, 2013 at 21:29

$\begingroup$ In particular are you looking for good estimates, or just any estimates? If you are interested in any estimates (like the one I mention above) then I can post the proof... $\endgroup$– blablerCommented Jul 26, 2013 at 21:32

$\begingroup$ Note that the mighty Generalized Riemann Hypothesis should give you the cancellation $o(x)$ whenever $x > C_{\varepsilon} p^{\varepsilon}$. $\endgroup$– blablerCommented Jul 26, 2013 at 21:35

$\begingroup$ Thank you for your comments. Unfortunately it seems that for the application I had in mind any power of the logarithm bigger than $1+o(1)$ would be too big, but it is nevertheless interesting what is the smallest power one can obtain (unconditionally of course). $\endgroup$– AlexCommented Jul 27, 2013 at 14:08
2 Answers
In general, we can take $x>\exp\{c_\epsilon p^\epsilon\}$ by the Prime Number Theorem for arithmetic progressions. More generally, one can use $L$functions methods to relate $x$ to zerofree regions. In doing so it is hard to avoiding `losing logarithms'. The following elementary argument though, essentially due to Granville, does the job in an easier way.
Let $f$ be a completely multiplicative such that $f(n)\le1$ for all $n$ (so one can think that $f$ is a Dirichlet character), and assume that we know that $$ \left\sum_{n\le x} \Lambda(n)f(n) \right \le Cx\cdot \frac{\log Q}{\log x} \tag{*} $$ for all $x>Q$ (the size of $Q$ will depend on the available zerofree regions). Then we claim that $(*)$ holds for $\mu(n) f(n)$ too (with a different constant). Note that if suffices to show the result for $g(n)=\prod_{p^e\n}(f(p))^e$ (then one can use a convolution argument to pass to $f$). In order to show that $(*)$ holds with $g$ in place of $f\Lambda$, possibly with another constant $C'$ in place of $C$, we use induction, with the induction hypothesis being that $$ \left\sum_{n\le x} g(n) \right \le C' x\cdot \frac{\log Q}{\log x} \tag{**} $$ for all $x\le 2^m$. If $2^m\le Q$, this holds trivially (choosing $C'$ appropriately). Next, assume that $2^m>Q$ (and that $Q$ is large). Suppose also that that $(**)$ holds for $x\le 2^m$, and consider $x\in(2^m,2^{m+1}]$.Then $$ \sum_{n\le x} g(n) \log n = \sum_{n\le x} g(n) \sum_{dn} \Lambda(d) = \sum_{dm\le x} \Lambda(d) g(d)g(m) . $$ We apply Dirichlet's hyperbola method: \begin{align*} \sum_{n\le x} g(n) \log n &= \sum_{m\le x^{1\epsilon}} g(m) \sum_{d\le x/m} g(d)\Lambda(d) + \sum_{1<d\le x^{\epsilon}} \Lambda(d) g(d) \sum_{x^{1\epsilon}<m\le x/d} g(m) \\ &\ll \sum_{m\le x^{1\epsilon}} \frac{Cx}{m}\cdot \frac{\log Q}{\epsilon \log x} + \sum_{d\le x^{\epsilon}} \Lambda(d) \frac{C'x}{d} \cdot \frac{\log Q}{\log x} \\ &\ll \left( \frac{C}{\epsilon} + \epsilon C'\right) x\log Q \end{align*} Then applying partial summation and choosing $\epsilon$ and $C'$ appropriately completes the inductive step and thus the proof of $(**)$.
In the special case that $f(n)=(n/p)$, we know that $$ \sum_{n\le x}\Lambda(n) \left(\frac{n}{p}\right) = \sum_{\substack{\rho=\beta+i\gamma\\L(\rho,(\cdot/p))=0,\,\gamma\le p}} \frac{x^{\rho}}{\rho} + O\left(xe^{c\sqrt{\log x}}\right), $$ (see e.g. eq (13), p. 120 in Davenport's book "Multiplicative Number Theory"). There is a $c>0$ such that the first sum has at most one summand with $\beta\ge1c/\log p$, for which one then necessarily has that $\gamma=0$ (i.e. $\rho=\beta$ is a Siegel zero). The sum over the zeroes with $\beta\le 1c/\log p$ can be shown to be $\ll x^{1c'/\log q}$ for some absolute constant $c'>0$, using zerodensity estimates (see e.g. equation (18.9) in p. 428 of the book "Analytic Number Theory" by Iwaniec and Kowalski). We conclude that $$ \sum_{n\le x}\Lambda(n) \left(\frac{n}{p}\right) = \frac{x^{\beta}}{\beta} + O\left( x^{1c'/\log p} + xe^{c\sqrt{\log x}}\right) . $$ So $(*)$ holds with $Q=1/(1\beta)$ if $\beta$ exists and with $Q=p$ otherwise.

$\begingroup$ Thank you for your answer. Do you know what the known zero free regions imply for (*)? $\endgroup$– AlexCommented Jul 27, 2013 at 14:15

$\begingroup$ @Alex: I added more explanations in the end to answer your question in more detail (and corrected some typos). $\endgroup$ Commented Jul 29, 2013 at 14:29
Wirsing's Theorem tells us that if $f$ is multiplicative and each $f(p)=1,0 $ or $ 1$ then $\sum_{n\leq x} f(n) = o(x)$ as $\sum_{p\leq x} (1f(p))/p \to \infty$ (and one cannot do much better). Moreover one can get an explicit upper bound: $ \sum_{n\leq x} f(n) \ll x \exp( .32\sum_{p\leq x} (1f(p))/p)$. In your case $f(n)=\mu(n)(n/p)$ so that $\sum_{p\leq x} (1f(p))/p = 1/p+ 2\sum_{q\leq x, (q/p)=1} 1/q $. Therefore to get the bound $o(x)$ you need that a significant number of the $q\leq x$ satisfy $(q/p)=1$. So your question becomes: For what $x$ can we guarantee this? Or, in other words, is it possible that $(q/p)=1$ for "most" of the primes $\leq x$ (as may well be the case of one has a Siegel zero)?
If we use quadratic reciprocity, then $(q/p)=1$ is equivalent to demanding $(p/q)=$ something fixed, and we can find such $p$ for which this holds for all but one prime $q\ll \log p$, by Dirichlet's Theorem. But then, by smooth number estimates, one knows that for almost all such $p$ one has $\sum_{n\leq x} \mu(n)(n/p) \gg \rho(A)x$ for $x=(\log p)^A$ (for each $A$).
So we have "proved" that for any fixed $A>0$, the estimate $\sum_{n\leq x} \mu(n)(n/p) = o(x)$ does not hold uniformly for $x=(\log p)^A$.
The same ideas give, assuming GRH, that $\sum_{n\leq x} \mu(n)(n/p) = o(x)$ does hold uniformly provided $\log x/\log\log p \to \infty$ as $p\to \infty$.
These ideas can be found in my paper "Large Character Sums" with Soundararajan, though there we looked at character sums $\sum_{n\leq x} \chi(n)$; it should not take much to modify those ideas for this situation.