This question is related to this previous question where I asked about ordinary Fourier coefficients.

##Special case: is Möbius nearly Orthogonal to Morse

alt text http://gilkalai.files.wordpress.com/2011/02/mob.jpg! alt text http://upload.wikimedia.org/wikipedia/commons/7/78/Marston_Morse.jpg

Harold Calvin Marston Morse (24 March 1892 – 22 June 1977), August Ferdinand Möbius (November 17, 1790 – September 26, 1868)

Consider the sequence of values of the Möbius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

Start with the Möbius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Now, for a n-digit positive number $m$ regard the Mobius function as a Boolean function $\mu(x_1,x_2,\dots,x_n)$ where $x_1,x_2,\dots,x_n$ are the binary digits of $m$.

For example $\mu (0,1,0,1)=\mu(2+8)=\mu(10)=1$. We write $\Omega_n$ as the set of 0-1 vectors $x=(x_1,x_2,x_m)$ of length $n$. We also write $[n]=\{1,2,\dots,n\}$, and $N=2^n$.

Next consider for some natural number $n$ the Walsh-Fourier transform

$$\hat \mu (S)= \frac{1}{2^n} \sum _{x\in \Omega_n} \mu(x_1,x_2,\dots,x_n)(-1)^{\sum\{x_i:i\in S\}}.$$

So $\sum_{S \subset [n]}|\hat \mu (S)|^2$ is roughly $6/\pi ^2$; and the Prime Number Theorem asserts that $\hat \mu(\emptyset)=o(1)$; In fact the known strong form of the Prime Number Theorem asserts that

$$|\hat \mu (\emptyset )| \lt n^{-A} =(\log N)^{-A},$$

for every $A>0$. (Note that $|\hat \mu (\emptyset)=\sum_{k=0}^{N-1}\mu(k)$.)

My questions are:

1. Is it true that the individual coefficients tend to 0? Is it known even that $|\hat \mu (S)| \le n^{-A}$ for every $A>0$.

Solved in the positive by Jean Bourgain (April 12, 2011): Moebius-Walsh correlation bounds and an estimate of Mauduit and Rivat; (Dec, 2011) For even stronger results see Bourgain's paper On the Fourier-Walsh Spectrum on the Moebius Function.

2. Is it the case that

$$(*) \sum \{ \hat \mu ^2(S)~:~|S|<(\log n)^A \} =o(1), $$ for every $A>0$.

(This does not seem to follow from bounds we can expect unconditionally on individual coefficients.) Solved in the positive by Ben Green (March 12, 2011): On (not) computing the Mobius function using bounded depth circuits. (See Green's answer below.)

3. The Riemann Hypothesis asserts that $$|\hat \mu (\emptyset )| < N^{-1/2+\epsilon}.$$

Does it follows from the GRH that for some $c>0$, $$| \hat \mu (S)| < N^{-c},$$ for every $S$?

An upper bound of $(\log N)^{-{\log \log N}^A}$ suffices to get the desired application.

##The Motivation

The motivation for these questions from a certain computational complexity extension of the prime number theorem. It asserts that every function on the positive integers that can be represented by bounded depth Boolean circuit in terms of the binary expansion has diminishing correlation with the Mobius function. This conjecture that we can refer to as the $AC^0$- prime number conjecture is discussed here, on my blog and here, on Dick Lipton's blog. The conjecture follows from formula (***) by a result of Linial Mansour and Nisan on Walsh-Fourier coefficients of $AC^0$ functions.

Question 3 suggestes that perhaps we can deduce the $AC^0$ prime number conjecture from the GRH which would be of interest. Of course, it will be best to prove it unconditionally. (Ben Green proved it unconditionally).

For polynomial size formulas, namely for functions expressible by depth-2 polynomial size circuits we may need even less. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, a conjecture of Mansour (which also follows from a more general conjecture called the Influence/Entropy conjecture, see this blog post for a description of both conjectures) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

Let me mention that the question follows to a large extent a line of research associating $AC^0$ formulas with number theoretic questions. See the papers by Anna Bernasconi and Igor Shparlinski and the paper by Eric Allender Mike Saks Igor Shparlinski, and the paper COMPLEXITY OF SOME ARITHMETIC PROBLEMS FOR BINARY POLYNOMIALS by Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks, and Igor Shparlinski.