Walsh Fourier Transform of the Möbius function - MathOverflow

Walsh Fourier Transform of the Möbius function

2011-03-06T06:38:17Z

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

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)

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.

Answer by Ben Green for Walsh Fourier Transform of the Möbius function

2011-03-10T15:34:20Z

An update to my earlier answer. I've written a proof of this "AC0 prime number conjecture" as a short paper, which can be found here.

http://www.dpmms.cam.ac.uk/~bjg23/papers/primes-boolean.pdf

I thought a bit about establishing a nontrivial bound on the Fourier-Walsh coefficients $\hat{\mu}(S)$ for all sets $S$. My paper does this when $|S| < cn^{1/2}/\log n$ (here $S \subseteq {1,\dots,n}$). On the GRH it works for $|S| = O(n/\log n)$. I remarked before that the extreme case $S = {1,\dots,n}$ follows from work of Mauduit and Rivat.

I still believe that there is hope of proving such a bound in general, but this does seem to be pretty tough. At the very least one has to combine the work of Mauduit and Rivat with the material in my note above, and neither of these (especially the former) is that easy.

Answer by Gil Kalai for Walsh Fourier Transform of the Möbius function

2011-03-12T19:35:40Z

Rather than updating the question, let me devote a separate answer to discuss the emerging knowledge. (Please corrent me if I make any mistake.) I will update this answer when necessary.

First, the Prime Number Theorem in its stronger known form asserts that

$$|\sum_{k=1}^X \mu(k)| \le e^{\sqrt \log X}. $$

And the RH asserts that $$|\sum_{k=1}^X \mu(k)| \le X^{1/2+\epsilon}.$$

Let $X=2^n$, the Prime number theorem deals with the Walsh coefficient $\hat \mu(\emptyset)$.

(Remark: I am still a little confused about the situation, since the upper bound for the ordinary discrete Fourier coefficients in this answer by Matt Young are not as strong as the statement for the 0th coefficient given by the PNT. This is now clarified by Ben's remark below.)

The second question and the $AC^0$-prime number conjecture (resolved by Ben Green, March 12).

Ben wrote a paper showing that $$\hat \mu (S) \le e^{\sqrt \log X}, $$ whenever $|S| \le n^{1/2-\epsilon}$ using the Herman Katai's method. This is more than enough to imply a positive answer to question 2.

Ben's positive answer to question 2 implies the $AC^0$- Prime Number Conjecture (a.k.a Sarnak-Kalai conjecture)! In my opinion, this is a very nice result.

Ben's number theoretic argument is rather delicate from it the implication is rather direct. Hastad Switching lemma implies that the total influence (a.k.a. average sensitivity) of an $AC^0$ Boolean function is polynomial in (log n) and this implies that most of the Fourier-Walsh coefficients are below the polylog level which together with an affarmative answer to question 2 gives the $AC^0$ PNC. The connection of $AC^0$ circuits and Walsh expansion was first explored by Linial, Mansour and Nisan and their full result (which was later improved a little by Hastad) asserts that the Fourier-Walsh coefficients decay exponentially above their expected value. The exponential decay does not play a role here, but it will imply stronger orthogonality consequence with better upper bounds on the Walsh coefficients of the Mobius functions.

The first question (Update April 12, resolved by Jean Bourgain)

The first question was if $\hat \mu(S)$ tends to zero uniformly with X and at what rate.

A special case of interest was the correlation between the Mobius function and the Morse function (which is \hat \mu ([n])$. Ben Green noted that the method by Mauduit and Rivat gives directly that

$$\hat \mu ([n]) \le X^{-c}, $$ for some positive constant $c$.

Also according to Ben the results and methods of Harman and Kátai will give that $\hat \mu (S)$ uniformly tends to zero whenever $|S| \le n^{1/2-\epsilon}$ (in fact they give a stronger result mentioned below).

According to Ben, the technique of Mauduit-Rivat are likely to work unless S∩[n/3] is very ``thin'', and with more effort combining Mauduit-Rivat and Herman-Katai.

Update (April 12): Jean Bourgain proved (private communication) that for every Walsh function $W_S$ we have

$\sum_{m=1}^{X}\mu(m) W_S(m) \le X \cdot e^{-(\log X)^{1/10}}.$

In other words, $\hat \mu(S) \le e^{-(\log X)^{1/10}}.$

Jean also showed that under GRH

$\sum_{m=1}^X\mu(m)W_S(m) \le X^{1-(c/(\log\log X)^2)}.$

In other words, $\hat \mu(S) \le X^{-(c/\log \log X)^2}.$

This result suffices to show under the GRH the "monotone prime number conjecture."

Update Sept 14: Bourgain's paper is now arxived.

The relation with known CS literature?

In the question there are links to several papers which deals with related question of the inability of $AC^0$ functions to compute certain number theoretic questions. These papers rely heavily on Fourier expansion of $AC^0$ circuits, Linial-Mansour-Nisan, Hastad etc.

It seems that the paper by Anna Bernasconi and Igor Shparlinski and some papers cited there are most relevant. It looks that there is a proof there that much weight of the Fourier coefficients of a function expressing square-freeness (which is close to Mobius but seems easier).

Follow up questions

1) Give an affarmative answer to question (1)

2) Extend the PNT when you consider functions expressed ACC[p] circuits, namely by Boolean depth circuits with mod p gates. Note that question (1) is a very special case of ACC2, It would be nice to "merge" the Rasborov-Smolensky method to deal with ACC[p] functions with some ANT. Now that Ben settled the PNC for $AC^0$ functions this will be a natural next step. I will ellaborate on this question below.

3) Give an affermative answer to question 3. It will imply that under GRH the AC^0 PNT extends "almost" all the way to log-depth. (Update: The new result of Bourgain comes very close to that.)

Showing that $\hat \mu (S) \le X^{-1/3}$ will imply "The prime number conjecture for monotone Boolean functions" namely that the Mobius function is asymptotically orthogonal to every function described by a monotone Boolean function of the digits. (No complexity assumptions.) (Update: The new result of Bourgain appears to implies this under GRH.)

(This probably implies statement like: if you consider a randon sequance of integers $0=X_1,...,X_n$ so that $X_{i+1}$ is obtained from $X_i$ by switching a digit from 0 to 1 then the Mobius function will change sign many times on the sequence.)

4) It would be interesting to see if appropriate low level complexity classes (Also allowing random inputs to the circuits) account for other known results about "Mobius randomness". Interesting examples: Standard L functions, the Green-Tao bracketed polynomials; non deterministic sequences in the sense of Peter Sarnak,

5) There is no special reason to state the AC^0 Prime number theorem just based on the binary digit expressions. Can it be extended to expansions w.r.t. other p's?

Low degree polynomials over Z/2Z

The "Walsh-Fourier" functions considered in the question are high degree monomials over the real but they can be considered as linear functions over Z/2Z. For that, replace the values {-1,+1} by {0,1} both in the domain and range of our Boolean functions? What about low degree polynomials instead of linear polynomials?

If we can extend the results to polynomials over Z/2Z of degree at most polylog (n) this will imply by a result of Razborov Mobius randomness for AC02 circuits. (This is interesting also under GRH).

Update (12 April) While this question is still open. Jean Bourgain was able to prove Mobius randomness for AC0(2) circuits of certain sublinear size. Jean also noted that to show that the Mobius function itself is non-approximable by a AC0[2) circuit (namely you cannot reach correlation say of 0.99) can easily be derived from Razborov Smolensky theorem, since an easy computation shows that $\mu(3x)^2$ has correlation >0.8 with the 0(mod 3) function.

Moreover (As explained by Avi Wigderson), if we can show that certain functions have very low correlations with all low degree polynomials over Z/2Z this will already be ground breaking result in computational complexity. (Say, correlation which is smaller than 1/n.) This will be interesting even under GRH.

Let me just say what low degree polynomials are. You have a bunch of sets of variables; all the sets are small (smaller than $log n^t$), and your function is the parity of the number of sets for which all variables has value '1'. (If the sets are singletones we are back to the Walsh functions.)

More updates, more questions (December 2011)

Update: Jean Bourgain has now proved that every monotone Boolean function is asymptotically orthogonal to the Mobius function, unconditionally.

Questions: In addition to questions mentioned above it will be interesting

1) To relate these results with other recent results on Mobius randomness.

2) To see if the results about Mobius randomness translate to result about primes. Namely, are results of the form

(*) A $\pm$1 function f is asymptotically orthogonal to the Mobius function

can be "transformmed into a result of the form:

(**) There are infinitely many ~~promes~~ primes such that f(p)=1

Of course, we will probably need also to assume that the density of ${n:f(n)=1}$ is not too small. See also this MO question.