Ben Green and I have just uploaded to the arXiv our paper, “The Möbius function is asymptotically orthogonal to nilsequences“, which is a sequel to our earlier paper “The quantitative behaviour of polynomial orbits on nilmanifolds“, which I talked about in this post.  In this paper, we apply our previous results on quantitative equidistribution polynomial orbits in nilmanifolds to settle the Möbius and nilsequences conjecture from our earlier paper, as part of our program to detect and count solutions to linear equations in primes.  (The other major plank of that program, namely the inverse conjecture for the Gowers norm, remains partially unresolved at present.)  Roughly speaking, this conjecture asserts the asymptotic orthogonality

\displaystyle |\frac{1}{N} \sum_{n=1}^N \mu(n) f(n)| \ll_A \log^{-A} N (1)

between the Möbius function \mu(n) and any Lipschitz nilsequence f(n), by which we mean a sequence of the form f(n) = F(g^n x) for some orbit g^n x in a nilmanifold G/\Gamma, and some Lipschitz function F: G/\Gamma \to {\Bbb C} on that nilmanifold.  (The implied constant can depend on the nilmanifold and on the Lipschitz constant of F, but it is important that it be independent of the generator g of the orbit or the base point x.)  The case when f is constant is essentially the prime number theorem; the case when f is periodic is essentially the prime number theorem in arithmetic progressions.  The case when f is almost periodic (e.g. f(n) = e^{2\pi i \alpha n} for some irrational \alpha) was established by Davenport, using the method of Vinogradov.  The case when f was a 2-step nilsequence (such as the quadratic phase f(n) = e^{2\pi i \alpha n^2}; bracket quadratic phases such as f(n) = e^{2\pi \lfloor \alpha n \rfloor \beta n} can also be covered by an approximation argument, though the logarithmic decay in (1) is weakened as a consequence) was done by Ben and myself a few years ago, by a rather ad hoc adaptation of Vinogradov’s method.  By using the equidistribution theory of nilmanifolds, we were able to apply Vinogradov’s method more systematically, and in fact the proof is relatively short (20 pages), although it relies on the 64-page predecessor paper on equidistribution.  I’ll talk a little bit more about the proof after the fold.

There is an amusing way to interpret the conjecture (using the close relationship between nilsequences and bracket polynomials) as an assertion of the pseudorandomness of the Liouville function from a computational complexity perspective.    Suppose you possess a calculator with the wonderful property of being infinite precision: it can accept arbitrarily large real numbers as input, manipulate them precisely, and also store them in memory.  However, this calculator has two limitations.  Firstly, the only operations available are addition, subtraction, multiplication, integer part x \mapsto [x], fractional part x \mapsto \{x\}, memory store (into one of O(1) registers), and memory recall (from one of these O(1) registers).  In particular, there is no ability to perform division.  Secondly, the calculator only has a finite display screen, and when it shows a real number, it only shows O(1) digits before and after the decimal point.  (Thus, for instance, the real number 1234.56789 might be displayed only as \ldots 34.56\ldots.)

Now suppose you play the following game with an opponent.

  1. The opponent specifies a large integer d.
  2. You get to enter in O(1) real constants of your choice into your calculator.  These can be absolute constants such as \sqrt{2} and \pi, or they can depend on d (e.g. you can enter in 10^{-d}).
  3. The opponent randomly selects an d-digit integer n, and enters n into one of the registers of your calculator.
  4. You are allowed to perform O(1) operations on your calculator and record what is displayed on the calculator’s viewscreen.
  5. After this, you have to guess whether the opponent’s number n had an odd or even number of prime factors (i.e. you guess \lambda(n).)
  6. If you guess correctly, you win $1; otherwise, you lose $1.

For instance, using your calculator you can work out the first few digits of \{ \sqrt{2}n \lfloor \sqrt{3} n \rfloor \}, provided of course that you entered the constants \sqrt{2} and \sqrt{3} in advance.  You can also work out the leading digits of n by storing 10^{-d} in advance, and computing the first few digits of 10^{-d} n.

Our theorem is equivalent to the assertion that as d goes to infinity (keeping the O(1) constants fixed), your probability of winning this game converges to 1/2; in other words, your calculator becomes asymptotically useless to you for the purposes of guessing whether n has an odd or even number of prime factors, and you may as well just guess randomly.

[I should mention a recent result in a similar spirit by Mauduit and Rivat; in this language, their result asserts that knowing the last few digits of the digit-sum of n does not increase your odds of guessing \lambda(n) correctly.]

Now let me sketch the method of proof, which basically follows the Vinogradov (and Hardy-Littlewood) approach.  First, we use a factorisation theorem in our equidistribution paper to prepare the nilsequence f(n) into what is basically one of two forms: either a periodic sequence (or something very close to a periodic sequence) or a totally equidistributed sequence.  (Actually, it is possible to also be a hybrid of the two, in which the sequence foliates along dense arithmetic progressions into subsequences, each of which is totally equidistributed in its own nilmanifold, but let us ignore this technicality for simplicity.)

In the “major arc” case when the sequence f(n) is basically periodic, we can appeal to the prime number theorem in arithmetic progressions (or more precisely, the Siegel-Walfisz theorem, in order to get the right decay rate).

In the “minor arc” case when f(n) is equidistributed, we use the method of Type I and Type II sums.  The basic idea here is to play off the multiplicative structure of the Möbius function \mu(n) against the additive structure (in this case, equidistribution) of the nilsequence f(n).  More precisely, we express \mu(n) as a divisor sum, for instance using the identity

\displaystyle \mu(n) = \sum_{b,c: bc|n} \mu(b) \mu(c)

to rewrite sums such as \sum_n \mu(n) f(n) in the form

\displaystyle \sum_b \sum_c \sum_d \mu(b) \mu(c) f(bcd)

(here we suppress the ranges of the variables n,b,c,d for sake of discussion).  The philosophy here is that the arithmetic terms such as \mu(b) and \mu(c) are complicated and should be eliminated whenever possible (for instance, using the Cauchy-Schwarz inequality), whereas the dynamic term f(bcd) is much easier to understand thanks to its equidistribution.  Indeed, after performing various truncation tricks and Cauchy-Schwarz tricks, one can eliminate the number-theoretic terms from the above expressions, and upper bound their magnitude by a combination of Type I sums of the form

\displaystyle \sum_n |\sum_m f(nm)|

and Type II sums of the form

\displaystyle \sum_n \sum_{n'} |\sum_m f(nm) f(n'm)|

where we again suppress the (important) technical details about what ranges the variables n, n’, m will be varying over.  These sums can then be handled by the equidistribution assumption on f, the key lemma being (roughly speaking) that if a nilsequence n \mapsto f(n) is equidistributed then the dilates n \mapsto f(mn) will also be equidistributed for most m.  (This is a quantitative and generalised variant of the obvious fact that if a number is irrational, then most integer multiples of that number will also be irrational.)

[Update, July 20: Title of paper changed.]