<p>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 <a href="https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function">https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function</a> as well as this one <a href="https://mathoverflow.net/questions/97261/mobius-randomness-of-the-rudin-shapiro-sequence">https://mathoverflow.net/questions/97261/mobius-randomness-of-the-rudin-shapiro-sequence</a> . In addition, Jean Bourgain proved Mobius randomness for every monotone function $f$ (in terms of the binary-digit expansion).</p>

CC BY-SA 3.0
2013-12-29T19:19:04.393Z
2013-12-29T19:19:04.393Z
2017-04-13T12:57:54.777Z
Gil Kalai
<p>Recently, <a href="https://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/" rel="nofollow noreferrer">Gil Kalai</a> and <a href="https://rjlipton.com/2011/02/23/the-depth-of-the-mobius-function/" rel="nofollow noreferrer">Dick Lipton</a> both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis.</p>
<blockquote>
<p><strong>Conjecture.</strong> Let <span class="math-container">$\mu(k)$</span> be the <a href="https://en.wikipedia.org/wiki/M%C3%B6bius_function" rel="nofollow noreferrer">Möbius function</a>. Suppose <span class="math-container">$f: \mathbb{N} \to \{-1,1\}$</span> is an <span class="math-container">$\mathsf{AC}^0$</span> function with input <span class="math-container">$k$</span> in the form of binary representation of <span class="math-container">$k$</span>, then
<span class="math-container">$$ \sum_{k \leq n} \mu(k) \cdot f(k) = o(n) \text.$$</span></p>
</blockquote>
<p>Note that if <span class="math-container">$f(k) = 1$</span> then we have an equivalent form of the <a href="https://en.wikipedia.org/wiki/Prime_number_theorem" rel="nofollow noreferrer">Prime number theorem</a>.</p>
<p><strong>UPDATE</strong>: Ben Green on MathOverflow <a href="https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function/58081#58081">provided a short paper</a> which claims to prove the conjecture. <a href="https://arxiv.org/abs/1103.4991" rel="nofollow noreferrer" title="Ben Green: On (not) computing the Mobius function using bounded depth circuits">Take a look at the paper</a>.</p>
<p>On the other hand, we know that by setting <span class="math-container">$f(k) = \mu(k)$</span> (with slight modification so the range is in <span class="math-container">$\\{-1,1\\}$</span>), the resulting sum has the estimation
<span class="math-container">$$ \sum_{k \leq n} \mu(k)^2 = \Omega(n) \text.$$</span>
There is an upper bound that <span class="math-container">$\mu(k)$</span> can be computed in <span class="math-container">$\mathsf{UP} \cap \mathsf{coUP} \subseteq \mathsf{NP} \cap \mathsf{coNP}$</span>, so the constraint proposed on <span class="math-container">$f(k)$</span> in the conjecture cannot be relaxed to an <span class="math-container">$\mathsf{NP}$</span> function.
My question is:</p>
<blockquote>
<p>What is the lowest complexity class <span class="math-container">$\mathsf{C}$</span> we currently know, such that a function <span class="math-container">$f(k)$</span> in <span class="math-container">$\mathsf{C}$</span> satisfies the estimation
<span class="math-container">$$ \sum_{k \leq n} \mu(k) \cdot f(k) = \Omega(n) \text{?}$$</span>
In particular, since some of the theorists believe that computing <span class="math-container">$\mu(k)$</span> is not in <span class="math-container">$\mathsf{P}$</span>, can we provide other <span class="math-container">$\mathsf{P}$</span> functions <span class="math-container">$f(k)$</span> which implies a linear growth in the summation? Can even better bounds be obtained?</p>
</blockquote>

CC BY-SA 2.5
2011-02-23T21:31:09.263Z
Some quantum class like P^{BQNC} should also work, since factoring lies in that class.
Robin Kothari
CC BY-SA 2.5
2011-02-23T23:21:36.540Z
Is this even known if $f(k) = k_i$ for a fixed $i$?
Manu
CC BY-SA 2.5
2011-02-24T00:15:37.450Z
@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
CC BY-SA 2.5
2011-02-24T06:34:26.790Z
And is it known for $f \in NC^0$?
domotorp
CC BY-SA 2.5
2011-03-01T09:12:55.020Z
Do you want a function $f$ with the range $\{-1,0,1\}$ or $\{-1,1\}$ or something else?
Jukka Suomela
CC BY-SA 2.5
2011-03-01T09:29:10.850Z
@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 張顯之
CC BY-SA 2.5
2011-03-01T09:37:07.200Z
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 張顯之
CC BY-SA 2.5
2011-03-01T09:45:51.173Z
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 張顯之
<cc.complexity-theory><randomness><open-problem><nt.number-theory>
Efficiently computable function as a counter-example to Sarnak's Mobius conjecture
Hsien-Chih Chang 張顯之
# Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

(Asked by: username_0 on 2011-02-23)

Recently, [username_6](https://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/) and [Dick Lipton](https://rjlipton.com/2011/02/23/the-depth-of-the-mobius-function/) 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](https://en.wikipedia.org/wiki/M%C3%B6bius_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](https://en.wikipedia.org/wiki/Prime_number_theorem).

**UPDATE**: Ben Green on MathOverflow [provided a short paper](https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function/58081#58081) which claims to prove the conjecture. [Take a look at the paper](https://arxiv.org/abs/1103.4991 "Ben Green: On (not) computing the Mobius function using bounded depth circuits").

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?

**Tags:** cc.complexity-theory, randomness, open-problem, nt.number-theory

> **Comments:**
> **username_1**: Some quantum class like P^{BQNC} should also work, since factoring lies in that class.  
> **username_2**: Is this even known if $f(k) = k_i$ for a fixed $i$?  
> **username_3**: @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  
> **username_4**: And is it known for $f \in NC^0$?  
> **username_5**: Do you want a function $f$ with the range $\{-1,0,1\}$ or $\{-1,1\}$ or something else?  
> **username_0**: @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.)  
> **username_0**: 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.  
> **username_0**: 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?  

---

## 1 answers

### Answer by username_6 on 2013-12-29. Score: 6

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


---

