Recently Gil Kalai and Dick Lipton both wrote a nice article on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and Riemann Hypothesis.
Conjecture. Let $\mu(k)$ be the Möbius function. Suppose $f: \mathbb{N} \to \{-1,1\}$ is an $\mathsf{AC}^0$ function with input $k$ in the form of binary representation of $k$, then $$ \sum_{k \leq n} \mu(k) \cdot f(k) = o(n) \text.$$
Note that if $f(k) = 1$ then we have an equivalent form of the Prime number theorem.
UPDATE: Ben Green on MathOverflow provide a short paper which claims to prove the conjecture. Take a look at the paper.
On the other hand, we know that by setting $f(k) = \mu(k)$ (with slightly modification so the range is in $\\{-1,1\\}$), the resulting sum has the estimation $$ \sum_{k \leq n} \mu(k)^2 = \Omega(n) \text.$$ There is an upper bound that $\mu(k)$ can be computed in $\mathsf{UP} \cap \mathsf{coUP} \subseteq \mathsf{NP} \cap \mathsf{coNP}$, so the constrain proposed on $f(k)$ in the conjecture cannot be relaxed to an $\mathsf{NP}$ function. My question is:
What is the lowest complexity class $\mathsf{C}$ we currently know, such that a function $f(k)$ in $\mathsf{C}$ satisfies the estimation $$ \sum_{k \leq n} \mu(k) \cdot f(k) = \Omega(n) \text{?}$$ In particular, since some of the theorists believed that computing $\mu(k)$ is not in $\mathsf{P}$, can we provide other $\mathsf{P}$ functions $f(k)$ which implies a linear growth in the summation? Can even better bounds be obtained?