You are currently browsing the tag archive for the ‘second moment method’ tag.
Let be the Liouville function, thus
is defined to equal
when
is the product of an even number of primes, and
when
is the product of an odd number of primes. The Chowla conjecture asserts that
has the statistics of a random sign pattern, in the sense that
for all and all distinct natural numbers
, where we use the averaging notation
For , this conjecture is equivalent to the prime number theorem (as discussed in this previous blog post), but the conjecture remains open for any
.
In recent years, it has been realised that one can make more progress on this conjecture if one works instead with the logarithmically averaged version
of the conjecture, where we use the logarithmic averaging notation
Using the summation by parts (or telescoping series) identity
it is not difficult to show that the Chowla conjecture (1) for a given implies the logarithmically averaged conjecture (2). However, the converse implication is not at all clear. For instance, for
, we have already mentioned that the Chowla conjecture
is equivalent to the prime number theorem; but the logarithmically averaged analogue
is significantly easier to show (a proof with the Liouville function replaced by the closely related Möbius function
is given in this previous blog post). And indeed, significantly more is now known for the logarithmically averaged Chowla conjecture; in this paper of mine I had proven (2) for
, and in this recent paper with Joni Teravainen, we proved the conjecture for all odd
(with a different proof also given here).
In view of this emerging consensus that the logarithmically averaged Chowla conjecture was easier than the ordinary Chowla conjecture, it was thus somewhat of a surprise for me to read a recent paper of Gomilko, Kwietniak, and Lemanczyk who (among other things) established the following statement:
Theorem 1 Assume that the logarithmically averaged Chowla conjecture (2) is true for all
. Then there exists a sequence
going to infinity such that the Chowla conjecture (1) is true for all
along that sequence, that is to say
for all
and all distinct
.
This implication does not use any special properties of the Liouville function (other than that they are bounded), and in fact proceeds by ergodic theoretic methods, focusing in particular on the ergodic decomposition of invariant measures of a shift into ergodic measures. Ergodic methods have proven remarkably fruitful in understanding these sorts of number theoretic and combinatorial problems, as could already be seen by the ergodic theoretic proof of Szemerédi’s theorem by Furstenberg, and more recently by the work of Frantzikinakis and Host on Sarnak’s conjecture. (My first paper with Teravainen also uses ergodic theory tools.) Indeed, many other results in the subject were first discovered using ergodic theory methods.
On the other hand, many results in this subject that were first proven ergodic theoretically have since been reproven by more combinatorial means; my second paper with Teravainen is an instance of this. As it turns out, one can also prove Theorem 1 by a standard combinatorial (or probabilistic) technique known as the second moment method. In fact, one can prove slightly more:
Theorem 2 Let
be a natural number. Assume that the logarithmically averaged Chowla conjecture (2) is true for
. Then there exists a set
of natural numbers of logarithmic density
(that is,
) such that
for any distinct
.
It is not difficult to deduce Theorem 1 from Theorem 2 using a diagonalisation argument. Unfortunately, the known cases of the logarithmically averaged Chowla conjecture ( and odd
) are currently insufficient to use Theorem 2 for any purpose other than to reprove what is already known to be true from the prime number theorem. (Indeed, the even cases of Chowla, in either logarithmically averaged or non-logarithmically averaged forms, seem to be far more powerful than the odd cases; see Remark 1.7 of this paper of myself and Teravainen for a related observation in this direction.)
We now sketch the proof of Theorem 2. For any distinct , we take a large number
and consider the limiting the second moment
We can expand this as
If all the are distinct, the hypothesis (2) tells us that the inner averages goes to zero as
. The remaining averages are
, and there are
of these averages. We conclude that
By Markov’s inequality (and (3)), we conclude that for any fixed , there exists a set
of upper logarithmic density at least
, thus
such that
By deleting at most finitely many elements, we may assume that consists only of elements of size at least
(say).
For any , if we let
be the union of
for
, then
has logarithmic density
. By a diagonalisation argument (using the fact that the set of tuples
is countable), we can then find a set
of natural numbers of logarithmic density
, such that for every
, every sufficiently large element of
lies in
. Thus for every sufficiently large
in
, one has
for some with
. By Cauchy-Schwarz, this implies that
interchanging the sums and using and
, this implies that
We conclude on taking to infinity that
as required.
Van Vu and I have just uploaded to the arXiv our survey paper “From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices“, submitted to Bull. Amer. Math. Soc.. This survey recaps (avoiding most of the technical details) the recent work of ourselves and others that exploits the inverse theory for the Littlewood-Offord problem (which, roughly speaking, amounts to figuring out what types of random walks exhibit concentration at any given point), and how this leads to bounds on condition numbers, least singular values, and resolvents of random matrices; and then how the latter then leads to universality of the empirical spectral distributions (ESDs) of random matrices, and in particular to the circular law for the ESDs for iid random matrices with zero mean and unit variance (see my previous blog post on this topic, or my Lewis lectures). We conclude by mentioning a few open problems in the subject.
While this subject does unfortunately contain a large amount of technical theory and detail, every so often we find a very elementary observation that simplifies the work required significantly. One such observation is an identity which we call the negative second moment identity, which I would like to discuss here. Let A be an matrix; for simplicity we assume that the entries are real-valued. Denote the n rows of A by
, which we view as vectors in
. Let
be the singular values of A. In our applications, the vectors
are easily described (e.g. they might be randomly distributed on the discrete cube
), but the distribution of the singular values
is much more mysterious, and understanding this distribution is a key objective in this entire theory.
Recent Comments