Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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! alt text

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.

share|improve this question
Gil, fascinating question. If $|S|$ is very large (say $S = [n]$) then this is basically the work of Mauduit and Rivat, who show that primes are equally likely to have odd or even digit sum in base 2. On the other hand if $|S|$ is very small (e.g. $|S| = 1$) then you've got to sum $\mu$ over a set that looks like a GAP, $P$, of small dimension; this should be possible decomposing $1_P$ into exponentials. Question is what happens in the middle! I'll think about it... –  Ben Green Mar 6 '11 at 17:42
P.S. could you edit your post a bit? I think there are some $n^A$s that should be $n^{-A}$, etc. –  Ben Green Mar 6 '11 at 17:45
Thats very interesting Ben, for question (2) we need to worry only about S of size polylog (n) –  Gil Kalai Mar 6 '11 at 20:05
Dear Ben, I do not see why the result of Mauduit and Rivat that you mentioned implies the statement about [n]. (The [n] case is a nice statement about Morse sequence being "orthogonal" to the Mobius function.) –  Gil Kalai Mar 8 '11 at 22:57
add comment

2 Answers

up vote 29 down vote accepted

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.


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.

share|improve this answer
Very nice! I said "(This does not seem to follow from bounds we can expect unconditionally on individual coefficients.)" But I was wrong, it does seem to follow if you extend the bound for the empty coefficients to all other small coefficients. (Also I am a bit confused: what is the best known bound for SUM_{k=1}^N \mu(k)?) –  Gil Kalai Mar 10 '11 at 20:20
Gil, Well it's a bit more complicated than that. I'll try and write some proper notes on the whole thing. If it works out I'm not sure it's really publishable in the sense that it's the crudest possible joining of two things already in the literature. But then again, those are two quite different literatures, so perhaps the link should be properly noted. I think there are some more general observations I can extract from the Harman-Katai paper and I shall do so in due course. Best wishes Ben –  Ben Green Mar 10 '11 at 20:24
Regarding proving it for all Fourier coefficients. It is sort of interesting on its own and it will imply Mobius randomness for functions of the binary digits that we understand their Walsh expansions. If you can prove (say under GRH) that the Fourier coefficients hat \mu(S) is below X^{-1/4 +epsilon} for every S, |S|<= n^{1/2+epsilon} then it will show that the "monotone PNT" namely that every function expressed by a monotone Boolean function (regardless of its computational complexity) of the binary digits is orthogonal to the Mobius function. –  Gil Kalai Mar 10 '11 at 20:27
Dear Ben, also maybe the results in the paper in the "Some background" already contain part (or all, although I did not find it) of what is needed. –  Gil Kalai Mar 10 '11 at 20:40
One obvious motivation for understanding the general case of Walsh functions is that we can believe that the AC^0 result extend to Boolean circuits which allow also addition mod 2 gates. This is the net step beyonf AC^o where still a lot in known and a PNT will be very welcome. If we can combine some facts from analytic number theory with the Rasborov-Smolensky methods for this type of functions this will be very nice. –  Gil Kalai Mar 11 '11 at 13:39
show 1 more comment

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.

share|improve this answer
Gil, Regarding the "normal" Fourier coefficients of $\mu$. It basically has to do with the fact that the error term in the plain prime number theorem is $e^{-C\sqrt{\log X}}$. But in the prime number theorem in $a \mod{q}$, there is an additional term coming from a so-called ``Siegel zero''; a zero of a Dirichlet $L$-function $L(s,\chi)$ anomalously close to $1$. But these only exist for a very few values of $q$, and the observation that Harman-Katai make is that if $q$ ranges over powers of $2$ then you get to ignore them (to simplify rather dramatically). –  Ben Green Mar 12 '11 at 22:17
Sorry, when I say "exist" I mean "not known not to exist". Of course GRH implies there are no such zeros. –  Ben Green Mar 12 '11 at 22:18
@Gil 'promes'? Made me laugh. –  David Roberts Dec 8 '11 at 22:43
More seriously, the link to Bourgain's September paper (pdf from arxiv.de) was broken, so I gave a link to the paper's abstract page on the home arXiv site. And I've added the link to the December paper. –  David Roberts Dec 8 '11 at 22:53
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.