It is well known that some statements about partial sums of multiplicative functions are extremely hard. For example, the Riemann hypothesis is equivalent to the assertion that $\mu(1)+\mu(2)+\dots+\mu(n)$ is bounded above by $n^{1/2+\epsilon}$ for all $\epsilon > 0$. However, I want to know about lower bounds for such partial sums, valid for infinitely many n. For instance, is it known that the sums of the Möbius function must infinitely often be somewhere near $n^{1/2}$ in magnitude? Can one at least prove that they are unbounded? And what about the Liouville function $\lambda$? Are its partial sums unbounded? If so, can anyone give me a good reference or quick proof? And how about general completely multiplicative functions that take values of modulus 1? Is anything known about those?

1$\begingroup$ I heard from Andrew Granville that the following is (roughly) true: Let $f(n)$ be a completely multiplicative function, with f(n) = 1, such that the mean value of $f(p)$ is equal to $\alpha \neq 0, 1$. Then under some technical conditions, $\sum_{n < x} f(n)$ is asymptotic to a constant times $(\log x)^{\alpha  1}$. Apparently this is due to Tenenbaum, based on ideas of Selberg. Unfortunately I'm not familiar with the proof, nor do I know a reference. $\endgroup$ – Frank Thorne Jun 29 '11 at 3:34

$\begingroup$ Frank, you must mean a constant times $x (\log x)^{a1}$. One reference is my paper with Finch and Sebah (Google knows it), although the best use of that hint is to find more primary references from my paper's bibliography. $\endgroup$ – Greg Martin Aug 30 '11 at 4:52

$\begingroup$ Greg  indeed, that's what I meant, thank you! $\endgroup$ – Frank Thorne Aug 6 '12 at 21:52

$\begingroup$ I had an idea that it might be worth a) defining exhaustively the algebra of functions which are multiplicative on the domain of positive integers and b) the modular form of the same algebra based on any two elements being considered equivalent if they yield the same Euler product, which although an ambitious enterprise should surely yield some new insight into this area. math.stackexchange.com/questions/2436382 $\endgroup$ – user334732 Sep 20 '17 at 11:59
This reference contains the best result of this kind currently known for $\mu(n)$:
Tadej Kotnik and Herman te Riele The Mertens Conjecture revisited. Algorithmic number theory, 156167, Lecture Notes in Comput. Sci., 4076, Springer, Berlin, 2006.
They prove that $\limsup_{x \rightarrow +\infty}M(x)/\sqrt{x} \geq 1.218$ and that $\liminf_{x \rightarrow +\infty}M(x)/\sqrt{x} \leq 1.229$. Here
$ M(x) = \sum_{n \leq x}\mu(n) $
is the conventional notation for the summatory function of the Möbius function. Their proof is a mixture of analytic number theory and large scale computations. They also have a survey of what is known and what is conjectured about the size of $M(x)$.
Now on to the Liouville function $\lambda(n)$ and its summatory function $L(x)$. The latter is very closely connected with $M(x)$, for
$ \sum_{n \leq \sqrt{x}}\mu(n)L\left(\frac{x}{n^2}\right) = \sum_{n \leq \sqrt{x}}\mu(n)\sum_{m \leq x/n^2}\lambda(m) = \sum_{N \leq x}\sum_{mn^2 = N}\mu(n)\lambda(m) = \sum_{N \leq x}\mu(N) = M(x). $
Thus
$ M(x) \leq \sum_{n \leq \sqrt{x}}L\left(\frac{x}{n^2}\right) $
and so the assumption
$ L(x) = o\left(\frac{\sqrt{x}}{\log^{1 + \epsilon}(x)}\right) $
for example, leads to a contradiction with the Kotnikte Riele result (or earlier results) for any $\epsilon > 0$.
My guess is that if one looks up the old (precomputer) results on $M(x)$ from below, one might prove that $\limsup_{x \rightarrow +\infty}L(x)/\sqrt{x} > 0$. This may even be in the literature somewhere.
Alternatively
$ \sum_{n = 1}^{\infty}\lambda(n)n^{s} = \prod_{p}\sum_{k=0}^{\infty}\lambda(p^k)p^{ks} = \prod_{p}\sum_{k=0}^{\infty}(1)^kp^{ks} = \prod_{p}(1 + p^{s})^{1} = \frac{\zeta(2s)}{\zeta(s)} $
by the Euler product formula, and from here on it is more elementary than it was with $M(x)$ in the argument that David Speyer gave, because we don't need the zeros on the critical line. For $\zeta(2s)$ has a pole at $s = 1/2$ which is not canceled by a pole of $\zeta(s)$ at the same point. Thus $L(x) = O(x^{\alpha})$ is impossible with $\alpha < 1/2$ by partial summation.
For multiplicative functions of modulus $1$, the situation is much less clear. For simplicity, assume that $f(n)$ is a totally multiplicative function (multiplicative and $f(p^k) = f(p)^k$) with $c_p = 1$ where $c_p = f(p)$. The Liouville function is the case $c_p \equiv 1$. Then
$ \sum_{n = 1}^{\infty}f(n)n^{s} = \prod_{p}\frac{1}{1  c_pp^{s}}{\quad},{\quad}A(x) = \sum_{n \leq x}f(n) $
by the Euler product formula. The basic principle is that if $A(x) = O(x^{\alpha})$, then the Dirichlet series on the left hand side is convergent in the half plane $\sigma > \alpha$, so the sum is holomorphic in that half plane. If we can find a singularity $s_0$ of the product on the right hand side with $\mathrm{Re}(s_0) = \sigma_0$, that tells us that $A(x) = O(x^{\alpha})$ with $\alpha < \sigma_0$ is impossible. The bad thing now is that the product may diverge at a point without having a singularity there, because the product may diverge to zero, and a holomorphic function may be zero at a point without being singular there.
But it is straightforward to show that if $\mathrm{Re}(c_p) \geq \delta > 0$ for all $p$, then $A(x) = O(x^{\alpha})$ is impossible for any $\alpha < 1$, by showing that the series $ \sum_{p}c_pp^{\sigma} $ goes to infinity as $\sigma \rightarrow 1^{+}$.
You probably know this, but: Set $s(n) = \mu(1) + \cdots + \mu(n)$. Suppose, for the sake of contradiction, that $s(n) = O(n^{1/2  \epsilon})$. Then $$\sum s(n) \left( n^{s}  (n+1)^{s} \right)$$ would converge for $Re(s) > 1/2\epsilon$. This would give an analytic extension of $1/\zeta(s)$ to this half plane, contradicting that $\zeta$ has zeroes on the critical line.
So we know that the partial sums of $\mu$ are NOT $O(n^{1/2  \epsilon})$. I don't know if this can be pushed to show that they are not $o(n^{1/2})$.

$\begingroup$ I was fairly sure that partial sums of mu were not better than the square root of n, but I didn't in fact know this argument, so thanks for giving it. I'll think about whether it can be adapted to work for the Liouville function. $\endgroup$ – gowers Jan 7 '10 at 23:56

3$\begingroup$ By the way, it is not necessary to know that $\zeta(s)$ has any zeros on the critical line, just that it has at least one zero in the critical strip $0 \leq \sigma \leq 1$. For then it has at least two zeros in $\sigma \geq 1/2$ by the functional equation and symmetry about the real axis, and only a single zero in $\sigma \geq 1/2$ is needed. $\endgroup$ – engelbrekt Jan 8 '10 at 21:40
This paper shows that $L(n) > .061867\sqrt{n}$ for infinitely many $n$.
As for somewhat elementary methods (in the sense of avoiding the Riemann zeta function) to show that $L(n)$ is "usually" of order $\sqrt{n}$, one can use the Lambert series $$\sum_{n=1}^{\infty}{\frac{\lambda(n)q^n}{1q^n}} = \sum_{n=1}^{\infty}{q^{n^2}}.$$
As $$\frac{q^n}{1+q^n} = \frac{q^n}{1q^n}  2\frac{q^{2n}}{1q^{2n}},$$ we have $$\sum_{n=1}^{\infty}{\frac{\lambda(n)}{q^{n}+1}} = \sum_{n=1}^{\infty}{q^{n^2}}  2\sum_{n=1}^{\infty}{q^{2n^2}}$$
or equivalently, letting $q = e^{\pi/x}$ and $\psi(x) = \sum_{n=1}^{\infty}{e^{\pi xn^2}}$, where $x$ is large, $$\sum_{n=1}^{\infty}{\frac{\lambda(n)}{e^{n\pi/x}+1}} = \psi(1/x)  2\psi(2/x)$$
Now $\psi(x)$ satisfies the functional equation $$\frac{1+2\psi(x)}{1+2\psi(1/x)} = \frac{1}{\sqrt{x}},$$
and so we can rewrite this as $$\sum_{n=1}^{\infty}{\frac{\lambda(n)}{e^{n\pi/x}+1}} = \frac{1\sqrt{2}}{2}\sqrt{x} + \frac{1}{2} + (\psi(x)2\psi(x/2))\sqrt{x}.$$
For large $x$, the lefthand side "looks like" $L(x)$, whereas the righthand side is dominated by the term $\frac{1\sqrt{2}}{2}\sqrt{x}$. This also explains why $L(n)$ is predominantly negative, as $\frac{1\sqrt{2}}{2}$ is negative.
Here is a largely historical remark:
Littlewood showed that there exists $x$ so that $\pi(x)$ is greater than the logintegral $\mathrm{li}(x)$. In fact, $\pi(x)  \mathrm{li}(x)$ is (more or less) a linear combination of factors $x^{1/2+it}$, where $1/2+it$ are zeroes of $\zeta$. Form the multiplicative convolution with a suitable smooth function: you can thereby make the sum over only finitely many zeroes. Now find (by Dirichlet) some $x$ for which all the numbers $i t \log(x)$ are near multiples of $2 \pi$, etc.
This shows that $\pi(x)  \mathrm{li}(x)$ is not bounded by $C \sqrt{x}$ for any $C$; in the case of Mobius, you get some $C$ but not any $C$, because it's harder to understand the coefficients of $x^{1/2+it}$.
Finally, there are some results valid for any completely multiplicative function: See the paper by A. Granville and K. Soundararajan entitled "The spectrum of multiplicative functions."

$\begingroup$ Would you please provide reference to Littlewood's paper (or its not original explanation)? Many thanks! $\endgroup$ – Fedor Petrov May 28 '10 at 12:52
This might not be exactly what you have in mind, but it is an old result of Paley that for an infinite (but very sparse) set of real Dirichlet characters the inequality
$max_{N} \sum_{n}^{N} \chi(n) > c \sqrt{Q} \ln\ln(Q) $
holds, where Q is the modulus of the character. Montgomery and Vaughan have shown the reverse inequality (on RH) for all Dirichlet characters, that is to say,
$max_{N} \sum_{n}^{N} \chi(n) < c \sqrt{Q} \ln\ln(Q)$.
Recently Paley's theorem was improved by Granville and Soundararajan in their work on Pretentious characters (among other things, they prove the lower bound holds for a larger set of characters).
references: R.E.A.C. Paley, A theorem on characters, J. London Math. Soc 7 (1932), 2832
H.L. Montgomery and R.C. Vaughan, Exponential sums with multiplicative coefficients, Invent. Math 43 (1977), 6982.
LARGE CHARACTER SUMS: PRETENTIOUS CHARACTERS AND THE POLYAVINOGRADOV THEOREM: http://arxiv.org/abs/math.NT/0503113.

$\begingroup$ Since Dirichlet characters are periodic, their partial sums are uniformly bounded. Thus one seeks bounds for families of Dirichlet characters in terms of the modulus, which seems rather different from the situation of $\mu$ and $\lambda$. (Disclaimer: I am not an analytic number theorist. Maybe there's more of a similarity here than is immediately apparent.) $\endgroup$ – Pete L. Clark Jan 9 '10 at 12:16

1$\begingroup$ It should be $\sqrt{Q}\log \log Q$ in the above comment. The sums are trivially bounded by $Q$ and it is not too hard to show that the inequality (PolyaVinogradov) $\sum_{M\leq n \leq M+N} \chi(n) = O(\sqrt{Q} \log Q)$ holds no matter how large $N$ is. @Pete: they are quite similar from the point of view of Lfunctions. The key word here is "conductor", which puts "t" and "q" in the same footing. See the beginning of chapter 5 of the book by IwaniecKowalski for detail. $\endgroup$ – Idoneal Jan 13 '10 at 16:57