You are currently browsing the tag archive for the ‘Vinogradov’s method’ tag.

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

 Various Items | Not… on IMU Graduate Breakout Fellowsh… Anonymous on Open question: scarring for th… louigiaddario on IMU Graduate Breakout Fellowsh… gninrepoli on P=NP, relativisation, and mult… Wolfgang Arendt on A quick application of the clo… Terence Tao on Ultrafilters, nonstandard anal… sagar on Ultrafilters, nonstandard anal… Anonymous on On time management Terence Tao on An elementary non-commutative… Anonymous on An elementary non-commutative… Nathan on 254A, Notes 1: Concentration o… Terence Tao on Distinguished Lecture Series I… Terence Tao on 254A, Notes 1: Concentration o… Anonymous on Distinguished Lecture Series I… Nathan on 254A, Notes 1: Concentration o…