Consider 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.) Next consider for some natural number $n$ the discrete Fourier transform


$$\hat \mu (k)= \frac1n \sum \_{r=0}^{n-1} \mu(r)e^{2 \pi i rk/n}.$$


So $\sum \_{k=0}^{n-1} |\hat{\mu} (k)|^2$ is roughly $6/\pi ^2$; and the Prime Number Theorem asserts that $\hat \mu(0)=o(1)$; 


My questions are: 


1) Is it true (or even obvious based on PNT?) that the individual coefficients tend to 0? 


2) Is it known that $\sum\_{k=0}^{s}|\hat \mu (k)|^2=o(1)$, where say $s=\log n^A$? or perhaps for some other specific $s$ Fourier coefficients? (Here $A$ is suppose to be a large real even as large as some large power of $\log \log n$ but it can also be a small real.)


3) Is it perhaps known that the sum of squares of the largest (in absolute value) $s$ Fourier coefficients is $o(1)$? When $s=$ some power of $\log n$ as above? 


4) What is expected to be the correct value of $s$ so that the sum of squares of absolute value of the highest $s$ Fourier coefficients are already not $o(1)$? 


**UPDATE and AND A FOLLOW-UP QUESTION:**


The answers below give a very good picture regarding what is known for the individual Fourier coefficients unconditionally and under GRH. I am still curious if there are some cases that a bound on the contribution of a bunch of Fourier coefficients can be given which is better than what you obtain from individual coefficients. So here is a question:


5) Let $n$ be a positive integer. Let $\cal P$ be its prime factors and let $Q(n,r)$ be all divisors of $n$ that involve at most $r$ primes in ${\cal P}$. 


Consider $$\sum \_{k \in Q(n,r)} |\hat{\mu} (k)|^2.$$ 


We now from the result on individual coefficients that this sum is o(1) for every $n$ if $r$ is bounded. Is it possible to prove that the sum is o(1) even when $r$ is a specific very slow growing function of n, where the bound of individual coefficients is not good enough? (We can ask a similar question about improving over the individual coeffient bound for $P(n,r)$ the set of all divisors of $n$ which are the product of at most $r$ primes in ${\cal P}$.) This example is geared towards the specific extension for the Walsh-Fourier coefficients. But there it seems that the knowledge regarding individual coefficients uconditionally and under GRH is weaker. **END of UPDATE**




---


The motivation came from a certain computational complexity extension of the prime number theorem which is discussed [here](http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/) and [here](http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/). For the conjecture we will need Walsh expansions rather than Fourier expansion and we will need (3) for Walsh coefficients corresponding to sets of size $(\log n)^{(\log \log n)^t}$.




---


Here is a follow-up MO question about Walsh-Fourier transform][3](https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-mobius-functions), which has direct applications to the computational complexity question. "Transforming" the answers given here from the Fourier transform to the Walsh-Fourier transform will already have interesting consequences!



Discrete Fourier Transform of the Möbius Function
Here is an answer to 1. It is known that for any $A > 0$ that $\sum\_{m \leq x} \mu(m) e(\alpha m) = O\_A(x (\log{x})^{-A})$ uniformly in $\alpha$. For instance, consult Theorem 13.10 of Iwaniec and Kowalski's book, Analytic Number Theory. This uniform bound comes from combining the zero free region of Dirichlet L-functions with Vinogradov's method. This bound shows that $|\hat{\mu}(k)| \leq C\_A (\log{n})^{-A}$. 


This gives 2) for $A$ fixed. Edit 1: It gives 3) also.


Edit 2: I would guess the truth is $|\hat{\mu}(k)| \leq C(\varepsilon) n^{-1/2 + \varepsilon}$ so $s$ would have to be almost as large as $n$ to get anything not $o(1)$.


