Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the 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 provided 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 slight 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 constraint 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 believe 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?

  • 3
    $\begingroup$ Some quantum class like P^{BQNC} should also work, since factoring lies in that class. $\endgroup$ Commented Feb 23, 2011 at 21:31
  • 5
    $\begingroup$ Is this even known if $f(k) = k_i$ for a fixed $i$? $\endgroup$
    – Manu
    Commented Feb 23, 2011 at 23:21
  • 2
    $\begingroup$ @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 $\endgroup$ Commented Feb 24, 2011 at 0:15
  • 1
    $\begingroup$ And is it known for $f \in NC^0$? $\endgroup$
    – domotorp
    Commented Feb 24, 2011 at 6:34
  • $\begingroup$ Do you want a function $f$ with the range $\{-1,0,1\}$ or $\{-1,1\}$ or something else? $\endgroup$ Commented Mar 1, 2011 at 9:12

1 Answer 1


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.