37

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?

auspicious99
  • 111
  • 1
  • 8
Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
  • 3
    Some quantum class like P^{BQNC} should also work, since factoring lies in that class. – Robin Kothari Feb 23 '11 at 21:31
  • 5
    Is this even known if $f(k) = k_i$ for a fixed $i$? – Manu Feb 23 '11 at 23:21
  • 2
    @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 00:15
  • 1
    And is it known for $f \in NC^0$? – domotorp Feb 24 '11 at 06:34
  • Do you want a function $f$ with the range ${-1,0,1}$ or ${-1,1}$ or something else? – Jukka Suomela Mar 01 '11 at 09:12
  • @Jukka: A function $f$ with range ${1,-1}$ computable in some small class $\mathsf{C}$ with linear growth on the convolution with the Möbius function would be nice. I am curious most in whether the conjecture holds if we only put a polynomial-time computable restriction on $f$. But weaker results are fine, since this may be an open problem. (cont.) – Hsien-Chih Chang 張顯之 Mar 01 '11 at 09:29
  • Here a function is computable in $\mathsf{C}$ in the following sense: Given a binary representation of $k$ as input, there is a $\mathsf{C}$-machine (uniformly or not) such that $f(k) = 1$ if the machine accepts $k$; otherwise $f(k) = -1$. This definition corresponds to the power of the machine to simulate randomness, which is the central idea of the conjecture. – Hsien-Chih Chang 張顯之 Mar 01 '11 at 09:37
  • I'm not sure how much we can relax the range of $f$. I guess a constant range ${-K,\ldots,K}$ would be fine, and for ${-n,\ldots,n}$ the function $f$ exists trivially. Any ideas if $f$ has a sub-linear range? – Hsien-Chih Chang 張顯之 Mar 01 '11 at 09:45

1 Answers1

5

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

Community
  • 1
Gil Kalai
  • 6,033
  • 35
  • 73