The AC0 Prime Number Conjecture

Möbius randomness and computational complexity

Last spring Peter Sarnak gave a thought-provoking lecture in Jerusalem. (Here are the very interesting slides of a similar lecture at I.A.S.)

Here is a variation of the type of questions Peter has raised.

The AC_0 Prime Number Conjecture: The correlation between the Möbius function and any function f from the natural numbers to {-1,1}, so that f can be described by a bounded depth polynomial size circuit, tends to zero!

Updates: (March) The conjecture made it to major league blogs as a very interesting blog post describing the conjecture appeared on Dick Lipton’s blog, and let to some interesting discussion. I posted two related Mathoverflow problems . The first
is about the discrete Fourier coefficients of the Mobius function
and the second
is about Walsh-Fourier coefficients of the Mobius function.
 Ben Green have posted an answer to my Mathoverflow question indicating an affarmative solution for the AC^0 Prime Number Conjecture. The proof is based on combining the Linial-Mansour-Nisan theorem with Results and techniques by Glyn Harman and Imre Kátai, (From the paper Primes with preassigned digits. II. Acta Arith. 133 (2008), 171–184.)

Ben have written some rough notes on this a short paper giving the solution here.  (An  earlier note by Ben assumed GRH and the full paper contain the extra work is needed to prove it unconditionally.) This is a very nice result. Ben is also optimistic that showing that all Walsh-Fourier functions are orthogonal to Mobius (which is a more general result) is within reach by combining the above result with results by Mauduit-Rivat. 

Of course, the next logical step is the ACC[2]-Prime number conjecture.  This includes as a very special case the question if all Walsh-Fourier functions are orthogonal asymptotically to the Mobius function. The “Walsh-Fourier” functions 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 AC0[2] circuits. (This is interesting also under GRH).

(AprilJean 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  GRH the “monotone prime number conjecture.”

While the questions about polylog degree polynomials over Z/2Z and about AC0(2) circuits  are 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. So we have a simple argument showing that (for n large) an ACC(2) function (or even a polylog degree polynomial)) cannot have correlation larger than 0.99 with the Mobius function, but showing that it cannot have correlation larger than 0.01 with the Mobius function seems at present very difficult. (More update: as it turned out, this last observation can be found already in Allender-Saks-Shparlinski’s paper.) 

End of updates.

Let me state the conjecture more precisely. Continue reading

Believing that the Earth is Round When it Matters

A world map. Canada seems much bigger than Israel. Note, however, that in the map countries near the equator looks smaller than they are. Update: The round-earth hypothesis is clearer to the people of New Zealand; see the comments section.

One difficult aspect of the academic life is the requirement to fly to conferences and other academic activities all over the world. Strangely, speaking about this hardship to non- academic friends does not always elicit the sympathy we deserve.

Last month, I had to be on duty in two places outside Jerusalem. The first was  a conference in Beijing and the second was a conference and a visit in the the Los Angeles area. My solution was to make a round trip to Beijing and another round trip to LA. (I am simplifying matters since there was some interference due to additional travels, visa matters, etc..)

I discovered the following flaws I make in planning my trips:

1) I am (somewhat) biased toward round trips.

More seriously…

2) I dont take into account that the earth is round.

The book solution to this travel was to go from Jerusalem to Beijing and then from Beijing to Los Angeles and from LA to Jerusalem. I completely ignored this possibility. When I realized it, it made me wonder what this reveals about my true beliefs regarding the round earth hypothesis.

Believing that this coffee cup is a realistic model of the world suffices to prefer the Beijing-LA solution over two round-trips solution!

Continue reading