Discrete Fourier Transform of the Möbius Function

Question

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 and here. 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, 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!

Answer 1

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)$.

Answer 2

The high level of abstraction that number theorists sustain is a continual source of amazement to me ... doesn't anyone want to see what $\hat\mu(k,n)$ concretely looks like?

So let's do it! Mainly for fun (and as a gesture of respect for Gil), here is a density plot of $n^{1/2} \hat\mu(k,n)$ for all values $(n,k) \in 1,1024$ (note that a normalizing factor $n^{1/2}$ is included; this scaling yields near-uniform luminance in the plot):

(canonical Moebius plot) http://faculty.washington.edu/sidles/Moebius/Moebius__1024_canonical.png

As usual, the argument (phase) of $\hat\mu(k,n)$ is encoded as hue, and the magnitude as saturation and value. For details, see the Mathematica code that produced the above plot (for many people, the most interesting aspect of the code will be the idiom for exporting Mathematica graphics to png files; certainly this is by far the longest part of the code, and the toughest to debug).

Such codes code encourages us to do numerical experiments ...

What happens if we randomize the sign of the Möbius function?

(canonical Moebius plot) http://faculty.washington.edu/sidles/Moebius/Moebius__1024_randomized.png

Hmmm ... when we randomize the sign of the Möbius function, $\hat\mu(k,n)$ doesn't look much different, does it?

On the other hand, we know (from other numerical experiments) that when we compute a pseudo-Riemann function $\zeta^\prime(s) = (\sum_{r=1}^\infty \mu(r)/r^s)^{-1}$ using a randomized-sign Möbius function, then the resulting $\zeta^\prime(s)$ has a distribution of zeros that is grossly different from the distribution of zeros in $\zeta(s)$ (to see this, just try it).

In summary, the special properties of the distribution of primes (relative to randomized distributions) that are so plainly evident when we "look" at the zeros of $\zeta(s)$, are not immediately evident when we "look" at the magnitude and phase of $\hat\mu(k,n)$.

As for what this observation means (if anything at all) ... well ... that is for the number theorists to comment upon, not me! :)

Answer 3

Expanding on Matt's answer, it is possible to show without too much difficulty (see here, Exercise 3 of section 18.2.1) that if $(a,q) = 1$, then $$\sum_{n \leq x}{\mu(n) e^{2\pi i an/q}} = \sum_{d \mid q} \frac{\mu(d)}{\varphi(q/d)} \sum_{\chi \pmod{q/d}} \tau(\overline{\chi}) \chi(a) M\left(\frac{x}{d}; \chi \chi_{0(d)}\right),$$ where the inner sum is over all Dirichlet characters modulo $q/d$, $\tau(\overline{\chi})$ is the Gauss sum of $\overline{\chi}$, $\chi_{0(d)}$ is the principal character modulo $d$, and $$M(x ; \chi) = \sum_{n \leq x}{\mu(n) \chi(n)}.$$ A pretty simple calculation (using Euler products and the fact that $\mu(n) \chi(n)$ is multiplicative) shows that for $\Re(s) > 1$, $$\frac{1}{L(s,\chi)} = s \int_{1}^{\infty} \frac{M(x ; \chi)}{x^s} \: \frac{dx}{x}.$$ So one can then use Perron's formula to invert this relationship, and then apply the classic method of pushing the integral to the left of the line $\Re(s) > 1$ and use estimates on $1/L(s,\chi)$ in the zero-free region to obtain the desired bound on $$\sum_{n \leq x}\mu(n) e^{2\pi i an/q}.$$ Though this doesn't seem to give a uniform bound, Montgomery and Vaughan's notes outline (Q1-Q5 of the same section) how to obtain uniform bounds in $\alpha$.

Note also that it is quite easy to show that for every $\varepsilon > 0$, $$\sum_{n \leq x}{\mu(n) e^{2\pi i n \alpha}} = O(x^{1/2 + \varepsilon})$$ for almost every $\alpha \in \mathbb{R}$; this is just a simple application of Carleson's theorem on the pointwise almost-everywhere convergence of an $L^2$-periodic function to its Fourier series. Unfortunately, this is not quantitative; we cannot say that this applies to rational $\alpha$ (otherwise we would be able to prove GRH).