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

(1)

between the Möbius function and any Lipschitz nilsequence f(n), by which we mean a sequence of the form for some orbit in a nilmanifold , and some Lipschitz function 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. for some irrational ) was established by Davenport, using the method of Vinogradov. The case when f was a 2-step nilsequence (such as the quadratic phase ; bracket quadratic phases such as 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 , fractional part , 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 .)

Now suppose you play the following game with an opponent.

- The opponent specifies a large integer d.
- You get to enter in O(1) real constants of your choice into your calculator. These can be absolute constants such as and , or they can depend on d (e.g. you can enter in ).
- The opponent randomly selects an d-digit integer n, and enters n into one of the registers of your calculator.
- You are allowed to perform O(1) operations on your calculator and record what is displayed on the calculator’s viewscreen.
- 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 .)
- 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 , provided of course that you entered the constants and in advance. You can also work out the leading digits of n by storing in advance, and computing the first few digits of .

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 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 against the additive structure (in this case, equidistribution) of the nilsequence . More precisely, we express as a divisor sum, for instance using the identity

to rewrite sums such as in the form

(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 and are complicated and should be eliminated whenever possible (for instance, using the Cauchy-Schwarz inequality), whereas the dynamic term 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

and Type II sums of the form

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 is equidistributed then the dilates 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.]

## 9 comments

Comments feed for this article

3 August, 2008 at 12:27 am

Mats GranvikDear Professor Terence Tao,

I have found that the n:th term of the möbius function can be calculated as a determinant of a modified nxn Redheffer Matrix where Redheffer Matrix(n,n) = 0. That is, the lower right corner is put to 0 in each nxn Redheffer Matrix.

References:

The On-Line Encyclopedia of Integer Sequences:

http://www.research.att.com/~njas/sequences/A143104

30 November, 2008 at 10:14 am

Marker lectures II, “Linear equations in primes” « What’s new[...] enough for our purposes, and we had to develop a quantitative analogue of this theory; see these blog posts for more discussion. Anyway, it all works, and gives asymptotics for progressions of length [...]

22 January, 2009 at 3:31 am

Mats GranvikIt appears that if you move the element in the lower right corner of a triangular matrix to a position somewhere in the same column, then the determinant is the value at a corresponding position in the transposed matrix inverse of the number triangle.

22 January, 2009 at 4:03 am

Mats GranvikDoes not hold for all triangular matrices. The diagonal must probably consist of ones.

8 March, 2011 at 7:59 am

Mats GranvikDear readers of Terence Taos blog,

I made an attempt to write an expression in terms of Lambert series for the power series of the Mobius function. This is what I arrived at:

I am unsure about the 5:th term.

http://mobiusfunction.wordpress.com/2011/03/08/the-ordinary-generating-function-for-the-mobius-function/

Mobius function generating function

11 March, 2011 at 10:22 am

The ordinary generating function for the Mobius function | The Mobius function Blog[...] I also posted it here: Terence Taos blog [...]

21 November, 2011 at 11:12 pm

The Bourgain-Sarnak-Ziegler orthogonality criterion « What’s new[...] also apply this criterion to nilsequences (obtaining a quick proof of a qualitative version of a result of Ben Green and myself) and to horocycle flows (for which no Möbius orthogonality result was previously [...]

1 March, 2012 at 5:25 pm

254B, Notes 7: Sieving and expanders « What’s new[...] theorem handles infinite arithmetic progressions , and a somewhat complicated result of Green, Tao, and Ziegler handles “non-degenerate” affine lattices in of rank two or more (such as [...]

14 October, 2012 at 5:43 pm

The Chowla conjecture and the Sarnak conjecture « What’s new[...] For nilsequences, this is a result of Ben Green and myself. [...]