# Discrete Fourier Transform of the Möbius Function

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!

-
Should $\mu(k)$ in your first display be $\mu(r)$? Should the sum in the next line be over $k$, not $i$? – Gerry Myerson Mar 3 '11 at 10:53
Yes and yes, thanks Gerry and Scott – Gil Kalai Mar 3 '11 at 14:04
thanks, Chandru – Gil Kalai Mar 3 '11 at 15:22
If I remember correctly, this is actually equivalent to the prime number theorem, so naively at the very least, it should only be obvious from the PNT if the converse is, which I don't think is so. – Adam Hughes Mar 3 '11 at 17:33
Adam, i did not understand the comment. – Gil Kalai Mar 3 '11 at 20:01

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

-
That's great, Matt. Do you know what A stands really for? (usually when you can prove things for A arbitrary large the proof allows A to be a function of n) E.g. if A is (log log n)^B still ok? regarding edit 2 can we expect that s should be at least a constant times n? Is the guess about the truth follows from RH or some version? – Gil Kalai Mar 3 '11 at 17:18
Gil, without any extra hypotheses $A$ cannot be taken to be a slowly growing function of $n$, since the constant $C_A$ is ineffective. This comes from a well-known source of ineffectivity related to possible Siegel zeros: one can show that there cannot be two bad real characters but there might still be one. On the GRH you can certainly prove $\hat{\mu}(k) \ll n^{-c}$ pointwise. I'd have to look up the best value of $c$ currently known, due to Harman I think. From memory it's about 1/4. – Ben Green Mar 3 '11 at 18:24
Yes, I believe what I just said is correct. It's a paper of Baker and Harman with MS reference MR1111578 (92d:11087). Apparently Montgomery and Vaughan had this independently but didn't publish. – Ben Green Mar 3 '11 at 18:28
Ick, I lost the comment I had typed up. Luckily, Ben covered the A-dependence. I would just add that the issue is if $k/n$ has a good rational approximation of the form $a/q$ with $q$ corresponding to a Landau-Siegel zero. If $k=1$ or is very small then this is not going to happen so perhaps for 2) one can take $A$ larger. I didn't work it out though. I would be careful on the size of $s$ since it's reminiscent of the Mertens conjecture. As for the "truth", it comes from the heuristic that the M\"{o}bius function is not correlated with additive characters. – Matt Young Mar 3 '11 at 18:46
Many thanks Ben and Matt. Ben you wrote: "one can show that there cannot be two bad real characters but there might still be one." This is good for us since we want to show that the entire "energy is not concentrated on a few characters". What can be said about the second worse character? can we show that (log n)^({log log n}^A}) characters cannot captire a substantial amount of L_2 norm for perhaps every positive A. – Gil Kalai Mar 3 '11 at 20:00

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):

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?

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! :)

-
The two pictures look precisely the same...(I just detected a pair of bright red rays on the top one which disappear in the botton one...) – Gil Kalai Mar 8 '11 at 6:04
I can see 3 red rays that are in the top but not the bottom, but I would guess there are a number of them them that are too thin to see or the resolution is not enough to bring them out. – David Roberts Mar 8 '11 at 6:37
Both observations are correct. (1) The above pictures are only 600 pixels wide; thus the fractal-like structure of the plotted function is not spatially resolved. (2) Details of the second function (the "random-sign Moebius function") depend upon the random number seed, but for all seeds the functions are generically similar to one another and to the first function (the "canonical Moebius function"). – John Sidles Mar 8 '11 at 15:25

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

-