# Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

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?

• Some quantum class like P^{BQNC} should also work, since factoring lies in that class. – Robin Kothari Feb 23 '11 at 21:31
• Is this even known if $f(k) = k_i$ for a fixed $i$? – Manu Feb 23 '11 at 23:21
• @Emanuele, good question. The indicator function of the i-th bit in the binary representation of k is a linear "bracket polynomial", but it has very high coefficients, so it might not follow from the Green-Tao theorem on the correlation of the Mobius function with bounded-step nilsequences. Bounded-step nilsequences have bounded-degree bracket polynomials as special cases, but their result might have some restrictions on the magnitudes of the coefficients – Luca Trevisan Feb 24 '11 at 0:15
• And is it known for $f \in NC^0$? – domotorp Feb 24 '11 at 6:34
• Do you want a function $f$ with the range $\{-1,0,1\}$ or $\{-1,1\}$ or something else? – Jukka Suomela Mar 1 '11 at 9:12

There have been interesting developments on this problem, however Replacing $AC^0$ with ACC(2) (Namely allowing mod 2 gates as well) is still well out-of-reach. Some progress beyond Ben Green's theorem can be found in this MO question https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function as well as this one https://mathoverflow.net/questions/97261/mobius-randomness-of-the-rudin-shapiro-sequence . In addition, Jean Bourgain proved Mobius randomness for every monotone function $f$ (in terms of the binary-digit expansion).