Return to Question

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

!

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

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.

Special case: is Möbius nearly orthogonal to Morse

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

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 $$\tag{$*$} \sum \{ \hat \mu ^2(S)~:~|S|<(\log n)^A \} =o(1), \label{*}$$ 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 \eqref{*} by a result of Linial Mansour and Nisan on Walsh-Fourier coefficients of $AC^0$ functions.

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.

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.

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

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.

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

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.

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

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.

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

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.