# Connection between Möbius and 𝜔 function

How can we from $$\sum_{n\leqslant x}\mu (n)=o(x)$$ deduce $$\sum_{n\leqslant x}(-1)^{\omega(n)}=o(x)$$, where $$\omega(n)$$ is the number of different primes dividing $$n$$ and $$\mu (n)$$ is the Möbius function? Heuristic: Up to x there must be roughly the same portion of numbers with odd and even number of prime divisors. First equality ( equivalent to prime number theorem ) prooves that for square free numbers, and there is no reason why should it not be valid for all numbers

• What makes you believe one can make such a deduction?
– YCor
Sep 24 at 15:07
• Heuristic: Up to x there must be roughly the same portion of numbers with odd and even number of prime divisors. First equality ( equivalent to prime number theorem ) prooves that for square free numbers, and there is no reason why should it not be valid for all numbers . Sep 24 at 15:34
• @AndrejLeško It might be good to include that heuristic in the question itself. Sep 24 at 21:05
• O.k. "heuristic" is included in the question. Sep 25 at 10:52

Yes, that deduction is possible, but somewhat indirectly.

The estimate $$\sum_{n \leq x} \mu(n) = o(x)$$ is equivalent to the nonvanishing of $$\zeta(s)$$ on $${\rm Re}(s) = 1$$ since both conditions are known to be equivalent to the prime number theorem. (Maybe one can directly deduce the estimate and the nonvanishing from each other without going through the prime number theorem, but that's a side issue here.) The function $$\zeta(s)$$ is known by elementary techniques to be meromorphic on $${\rm Re}(s) = 1$$ with a simple pole at $$s = 1$$, so the nonvanishing of $$\zeta(s)$$ on that line is equivalent to the function $$1/\zeta(s)$$ being analytic on $${\rm Re}(s) = 1$$. I will show $$\sum_{n \leq x} (-1)^{\omega(n)} = o(x)$$ follows from analyticity of $$1/\zeta(s)$$ on $${\rm Re}(s) = 1$$, so in a rather indirect way $$\sum_{n \leq x} (-1)^{\omega(n)} = o(x)$$ follows from the estimate $$\sum_{n \leq x} \mu(n) = o(x)$$.

Set $$F(s) := \sum_{n \geq 1} (-1)^{\omega(n)}/n^s$$ for $${\rm Re}(s) > 1$$. As David Speyer observed in his answer, for $${\rm Re}(s) > 1$$ we have $$F(s) = \prod_p \frac{1-2/p^s}{1-1/p^s} = \frac{1}{\zeta(s)}\prod_p \frac{1-2/p^s}{(1-1/p^s)^2}$$ and the $$p$$-th term on the right for $${\rm Re}(s) \geq 1$$ is $$1 + O(1/p^{2s})$$ with $$O$$-constant $$4$$ since $$|1/p^{s}| \leq 1/2^{{\rm Re}(s)} \leq 1/2$$ and $$(1-2z)/(1-z)^2 = 1 + O(z^2)$$ for $$|z| \leq 1/2$$ with $$O$$-constant $$4$$: $$(1-2z)/(1-z)^2 - 1 = -z^2/(1-z)^2$$ and $$|1/(1-z)^2| \leq 4$$. So the infinite product over $$p$$ on the right, which David calls $$B(s)$$, is holomorphic for $${\rm Re}(s) \geq 1$$ (in fact, $$B(s)$$ converges and is holomorphic for $${\rm Re}(s) > 1/2$$ since $$\sum 1/p^{2s}$$ converges for $${\rm Re}(s) > 1/2$$). Since $$\zeta(s)$$ is meromorphic on $${\rm Re}(s) \geq 1$$, $$F(s)$$ has a meromorphic continuation to $${\rm Re}(s) \geq 1$$.

From $$1/\zeta(s)$$ being analytic on $${\rm Re}(s) \geq 1$$, $$F(s)$$ has an analytic continuation to $${\rm Re}(s) \geq 1$$. Now we will apply the following theorem, which is a consequence of Newman's Tauberian theorem (one of the approaches to proving the prime number theorem).

Theorem. If the Dirichlet series $$\sum_{n \geq 1} b_n/n^s$$ converges for $${\rm Re}(s) > 1$$, $$|b_n| \leq 1$$, and the series has an analytic continuation to $${\rm Re}(s) \geq 1$$ then $$(1/x)\sum_{n \leq x} b_n \to 0$$ as $$x \to \infty$$.

In this theorem use $$b_n = (-1)^{\omega(n)}$$ to see that analyticity of $$1/\zeta(s)$$ on $${\rm Re}(s) = 1$$ implies $$(1/x)\sum_{n \leq x}(-1)^{\omega(n)} \to 0$$ as $$x \to \infty$$.

What about a converse: does $$(1/x)\sum_{n \leq x}(-1)^{\omega(n)} \to 0$$ as $$x \to \infty$$ imply $$1/\zeta(s)$$ is analytic on $${\rm Re}(s) =1$$ (and thus imply $$\sum_{n \leq x} \mu(n) = o(x)$$)? Set $$A(x) = \sum_{n \leq x} (-1)^{\omega(n)}$$, so trivially $$|A(x)/x|$$ is bounded and we are assuming that in fact $$A(x)/x \to 0$$ as $$x \to \infty$$.

We already pointed out that the Dirichlet series $$F(s) = \sum (-1)^{\omega(n)}/n^s$$ has a meromorphic continuation to $${\rm Re}(s) \geq 1$$ without using any information about possible zeros of $$\zeta(s)$$ on the line $${\rm Re}(s) = 1$$.

Theorem. Assume a Dirichlet series $$G(s) := \sum_{n \geq 1} a_n/n^s$$ converges for $${\rm Re}(s) > 1$$ and $$G(s)$$ has a meromorphic continuation to $${\rm Re}(s) \geq 1$$. If $$(1/x)\sum_{n \leq x} a_n \to 0$$ as $$x \to \infty$$ then $$G(s)$$ is holomorphic on the line $${\rm Re}(s) = 1$$.

Use this theorem with $$a_n = (-1)^{\omega(n)}$$ to see that if $$A(x)/x \to 0$$ as $$x \to \infty$$, then $$F(s)$$ is holomorphic on $${\rm Re}(s) = 1$$. What does analyticity of $$F(s)$$ on $${\rm Re}(s) = 1$$ tell us about analyticity of $$1/\zeta(s)$$ on that line? In the formula for $$F(s)$$ as an infinite product over primes when $${\rm Re}(s) > 1$$, let's extract the $$p = 2$$ term: $$F(s) = \prod_p \frac{1-2/p^s}{1-1/p^s} = \frac{1}{\zeta(s)}\frac{1-2/2^s}{(1-1/2^s)^2}\prod_{p \geq 3} \frac{1-2/p^s}{(1-1/p^s)^2}.$$ To reciprocate the product on the right over $$p \geq 3$$, let's see how quickly the reciprocals of the factors tend to $$1$$. For $$|z| \leq 1/3$$ we have $$(1-z)^2/(1-2z) = 1 + z^2/(1-2z)$$ and $$|1/(1-2z)| \leq 3$$, so $$(1-z)^2/(1-2z) = 1 + O(z^2)$$ with $$O$$-constant $$3$$. Therefore $$(1-1/p^s)^2/(1-2/p^s) = 1 + O(1/p^{2s})$$ for $${\rm Re}(s) \geq 1$$ and $$p \geq 3$$ with $$O$$-constant 3, so $$\frac{1}{\zeta(s)}\frac{1-2/2^s}{(1-1/2^s)^2} = F(s)\cdot\prod_{p \geq 3} \frac{(1-1/p^s)^2}{1-2/p^s}$$ where the product on the right converges and is analytic for $${\rm Re}(s) \geq 1$$ (and in fact for $${\rm Re}(s) > 1/2$$). Therefore analyticity of $$F(s)$$ on the line $${\rm Re}(s) = 1$$ implies the expression on the left side of the displayed equation just above is analytic on $${\rm Re}(s) = 1$$. The factor $$1-1/2^s$$ is nonvanishing on $${\rm Re}(s) > 0$$, so $$(1-2/2^s)/\zeta(s)$$ is analytic on $${\rm Re}(s) = 1$$. Since $$1-2/2^s$$ is analytic on $${\rm Re}(s) = 1$$ with zeros only at the points $$s_k = 1 + 2\pi ik/\log 2$$ where $$k \in \mathbf Z$$, the meromorphic function $$1/\zeta(s)$$ is analytic on the line $${\rm Re}(s) = 1$$ except for possible poles at the points $$s_k$$.

All that remains to be done to get the desired converse result is show $$1/\zeta(s)$$ has no pole at each $$s_k$$, or equivalently that $$\zeta(s)$$ is nonvanishing at each $$s_k$$. I don't see right now how to do that in the context of this problem. (While we know $$\zeta(s) \not= 0$$ on the whole line $${\rm Re}(s) = 1$$ from methods used to prove the prime number theorem, it's not fair to use such arguments here.) I am reminded here of the trick of comparing the products $$(1-2/2^s)\zeta(s)$$ and $$(1-3/3^s)\zeta(s)$$ in one of the proofs that $$\zeta(s)$$ is analytic on $${\rm Re}(s) > 0$$ except for a simple pole at $$s = 1$$, but I don't see how to modify that. If someone has a useful suggestion to finish this argument, please put it in the comments.

• All is clear. I have one question: can we from 1. $\sum_{n\leqslant x}(-1)^{\omega(n)}=o(x)$ deduce the Prime number theorem or 1. is weaker than PNT? Sep 25 at 9:45
• @AndrejLeško I added a second part to my solution that almost (but not quite) answers the question in your comment affirmatively, but at the very end I got stuck. Sep 25 at 16:09

Let $$f(n)$$ be the multiplicative function with $$f(p^k) = 1-k$$. Then $$(-1)^{\omega(n)} = \sum_{d|n} f(d) \mu(n/d).$$ (Proof: Both sides are multiplicative, so we just need to check prime powers, which is easy.)

Then $$\sum_{n \leq x} (-1)^{\omega(n)} = \sum_{d \leq x} f(d) \sum_{m \leq x/d} \mu(m).$$ If the absolute value of the inner sum is bounded by $$C (x/d)$$, then we have bounded the LHS by $$\sum_{d\leq x} |f(d)| \cdot C (x/d).$$ We win if we can show that $$\sum_{d=1}^{\infty} |f(d)|/d$$ is convergent.

To see that this is plausible, note that $$f(d)=0$$ if there is any prime factor of $$d$$ whose square does not divide $$d$$. To actually prove this, since it is a sum of positive terms, we may rearrange to an Euler product, and our goal is to show that $$\prod_p (1+1/p^2 + 2/p^3 + 3/p^4+ \cdots) = \prod_p \left( 1+\tfrac{1}{p^2 (1-1/p)^2} \right)= \prod_p \left( 1+\tfrac{1}{(p-1)^2} \right)$$ is convergent.

The last is clear.

Morally, why this should work:

$$\sum_n \frac{(-1)^{\omega(n)}}{n^s} = \prod_p \left( 1 - \frac{1}{p^s} - \frac{1}{p^{2s}} - \cdots \right) = \prod_p \left( 1 - \frac{1}{p^s} \right) \left( 1-O(1/p^{-2s}) \right)$$ $$=: \left( \sum_n \frac{\mu(n)}{n^s} \right) B(s)$$ where $$B(s)$$ is defined as the product of the error terms.

The product defining $$B(s)$$ converges to the right of $$Re(s)=1/2$$, so $$\sum_n \tfrac{(-1)^{\omega(n)}}{n^s}$$ and $$\sum_n \tfrac{\mu(n)}{n^s}$$ have the same zeroes and poles on the line $$Re(s)=1$$. So partial sums of $$(-1)^{\omega(n)}$$ and $$\mu(n)$$ should have similar behavior.

Actually, there is a slight error here: The $$p=2$$ term is $$(1-1/2^{2s} -2/2^{3s}-3/2^{4s}-\cdots)$$ which approaches $$1-1/4-2/8-3/16-\cdots = 0$$ as $$s \to 1$$. So $$B(s)$$ has an extra zero at $$s=1$$, with the result that $$\sum_n \tfrac{(-1)^{\omega(n)}}{n^s}$$ vanishes with order $$2$$ as $$s \to 1$$ and $$\sum_n \tfrac{\mu(n)}{n^s}$$ only vanishes to order $$1$$. Fortunately, when I tried to make the argument elementary, it worked out anyway. But this looks like it will pose a problem for reversing the argument in such an easy way.

The function $$f(n)$$ was motivated by $$B(s) = \sum_n f(n)/n^s$$. The remaining step was then to remove the complex analysis and see if a simple bound would go directly from one partial sum to the other.

• Is this rigorous proof? What does it mean that " partial sums of $(-1)^{\omega(n)}$ and $\mu(n)$ should have similar behavior" ? Sep 24 at 15:44
• @AndrejLeško The first half of the post is a rigorous proof, the second is an intuitive derivation of the argument. Sep 24 at 15:45
• Could I recommend changing the name $\phi(n)$ to something more generic, like $f(n)$? It took me a minute to realize it doesn't denote the totient function. Sep 24 at 15:51
• Okay, $\phi$ changed to $f$. Sep 24 at 15:58
• Ok, now i understand the proof,the second part is motivation, it is clear, but is it possible to proove the deduction in oposite direction in other words: are the two equalities in my question equivalent to each other? This would mean tha PNT is equivalent to $\sum_{n\leqslant x}(-1)^{\omega(n)}=o(x)$ Sep 24 at 16:09