This question is related to this [previous question][1] where I asked about ordinary Fourier coefficients. Start with the Mobius 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 )|<n^{-A}$ (=($\log N)^A$) for every A>0. (Note that $|\hat \mu (\emptyset)=\sum_{k=0}^{N-1-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$. 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.) 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}$? (An upper bound of $(\log N)^{{\log \log N}^A}$ suffices to get the desired application.) _____________________ 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][2] and [here, on Dick Lipton's blog][3]. 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. For polynomial size *formulas*, namely for functions expressible by depth-2 polynomial size circuits we need even less. By a result of Mansour the inequality $|\hat \mu (S)| \le n^(\log \log n)^A$ for every $A>0$, would suffice. Moreover based on a conjecture of Mansour (which also follows from a more general conjecture called the Influence/Entropy conjecture, see [this blog post][4] for a description of both conjectures) it will be enough to prove that $|\hat \mu (S)| \le n^A$ for every $A>0$, to deduce the PNT for formulas. __________________ 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][5] and the paper by Eric Allender Mike Saks Igor Shparlinski, and [the paper COMPLEXITY OF SOME ARITHMETIC PROBLEMS FOR BINARY POLYNOMIALS][6] by Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks, and Igor Shparlinski. [1]: http://mathoverflow.net/questions/57230/discrete-fourier-transform-of-the-mobius-function [2]: http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/ [3]: http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/ [4]: http://terrytao.wordpress.com/2007/08/16/gil-kalai-the-entropyinfluence-conjecture/ [5]: http://web.science.mq.edu.au/~igor/SF_ACo-STACS.ps [6]: http://www.springerlink.com/content/npg9c7nra24dhw0x/fulltext.pdf