You are currently browsing the monthly archive for September 2015.
Starting this week, I will be teaching an introductory graduate course (Math 275A) on probability theory here at UCLA. While I find myself using probabilistic methods routinely nowadays in my research (for instance, the probabilistic concept of Shannon entropy played a crucial role in my recent paper on the Chowla and Elliott conjectures, and random multiplicative functions similarly played a central role in the paper on the Erdos discrepancy problem), this will actually be the first time I will be teaching a course on probability itself (although I did give a course on random matrix theory some years ago that presumed familiarity with graduate-level probability theory). As such, I will be relying primarily on an existing textbook, in this case Durrett’s Probability: Theory and Examples. I still need to prepare lecture notes, though, and so I thought I would continue my practice of putting my notes online, although in this particular case they will be less detailed or complete than with other courses, as they will mostly be focusing on those topics that are not already comprehensively covered in the text of Durrett. Below the fold are my first such set of notes, concerning the classical measure-theoretic foundations of probability. (I wrote on these foundations also in this previous blog post, but in that post I already assumed that the reader was familiar with measure theory and basic probability, whereas in this course not every student will have a strong background in these areas.)
Note: as this set of notes is primarily concerned with foundational issues, it will contain a large number of pedantic (and nearly trivial) formalities and philosophical points. We dwell on these technicalities in this set of notes primarily so that they are out of the way in later notes, when we work with the actual mathematics of probability, rather than on the supporting foundations of that mathematics. In particular, the excessively formal and philosophical language in this set of notes will not be replicated in later notes.
Let and
be two random variables taking values in the same (discrete) range
, and let
be some subset of
, which we think of as the set of “bad” outcomes for either
or
. If
and
have the same probability distribution, then clearly
In particular, if it is rare for to lie in
, then it is also rare for
to lie in
.
If and
do not have exactly the same probability distribution, but their probability distributions are close to each other in some sense, then we can expect to have an approximate version of the above statement. For instance, from the definition of the total variation distance
between two random variables (or more precisely, the total variation distance between the probability distributions of two random variables), we see that
for any . In particular, if it is rare for
to lie in
, and
are close in total variation, then it is also rare for
to lie in
.
A basic inequality in information theory is Pinsker’s inequality
where the Kullback-Leibler divergence is defined by the formula
(See this previous blog post for a proof of this inequality.) A standard application of Jensen’s inequality reveals that is non-negative (Gibbs’ inequality), and vanishes if and only if
,
have the same distribution; thus one can think of
as a measure of how close the distributions of
and
are to each other, although one should caution that this is not a symmetric notion of distance, as
in general. Inserting Pinsker’s inequality into (1), we see for instance that
Thus, if is close to
in the Kullback-Leibler sense, and it is rare for
to lie in
, then it is rare for
to lie in
as well.
We can specialise this inequality to the case when a uniform random variable
on a finite range
of some cardinality
, in which case the Kullback-Leibler divergence
simplifies to
where
is the Shannon entropy of . Again, a routine application of Jensen’s inequality shows that
, with equality if and only if
is uniformly distributed on
. The above inequality then becomes
Thus, if is a small fraction of
(so that it is rare for
to lie in
), and the entropy of
is very close to the maximum possible value of
, then it is rare for
to lie in
also.
The inequality (2) is only useful when the entropy is close to
in the sense that
, otherwise the bound is worse than the trivial bound of
. In my recent paper on the Chowla and Elliott conjectures, I ended up using a variant of (2) which was still non-trivial when the entropy
was allowed to be smaller than
. More precisely, I used the following simple inequality, which is implicit in the arguments of that paper but which I would like to make more explicit in this post:
Lemma 1 (Pinsker-type inequality) Let
be a random variable taking values in a finite range
of cardinality
, let
be a uniformly distributed random variable in
, and let
be a subset of
. Then
Proof: Consider the conditional entropy . On the one hand, we have
by Jensen’s inequality. On the other hand, one has
where we have again used Jensen’s inequality. Putting the two inequalities together, we obtain the claim.
Remark 2 As noted in comments, this inequality can be viewed as a special case of the more general inequality
for arbitrary random variables
taking values in the same discrete range
, which follows from the data processing inequality
for arbitrary functions
, applied to the indicator function
. Indeed one has
where
is the entropy function.
Thus, for instance, if one has
and
for some much larger than
(so that
), then
More informally: if the entropy of is somewhat close to the maximum possible value of
, and it is exponentially rare for a uniform variable to lie in
, then it is still somewhat rare for
to lie in
. The estimate given is close to sharp in this regime, as can be seen by calculating the entropy of a random variable
which is uniformly distributed inside a small set
with some probability
and uniformly distributed outside of
with probability
, for some parameter
.
It turns out that the above lemma combines well with concentration of measure estimates; in my paper, I used one of the simplest such estimates, namely Hoeffding’s inequality, but there are of course many other estimates of this type (see e.g. this previous blog post for some others). Roughly speaking, concentration of measure inequalities allow one to make approximations such as
with exponentially high probability, where is a uniform distribution and
is some reasonable function of
. Combining this with the above lemma, we can then obtain approximations of the form
with somewhat high probability, if the entropy of is somewhat close to maximum. This observation, combined with an “entropy decrement argument” that allowed one to arrive at a situation in which the relevant random variable
did have a near-maximum entropy, is the key new idea in my recent paper; for instance, one can use the approximation (3) to obtain an approximation of the form
for “most” choices of and a suitable choice of
(with the latter being provided by the entropy decrement argument). The left-hand side is tied to Chowla-type sums such as
through the multiplicativity of
, while the right-hand side, being a linear correlation involving two parameters
rather than just one, has “finite complexity” and can be treated by existing techniques such as the Hardy-Littlewood circle method. One could hope that one could similarly use approximations such as (3) in other problems in analytic number theory or combinatorics.
I’ve just uploaded two related papers to the arXiv:
- The logarithmically averaged Chowla and Elliott conjectures for two-point correlations, submitted to Forum of Mathematics, Pi; and
- The Erdos discrepancy problem, submitted to the new arXiv overlay journal, Discrete Analysis (see this recent announcement on Tim Gowers’ blog).
This pair of papers is an outgrowth of these two recent blog posts and the ensuing discussion. In the first paper, we establish the following logarithmically averaged version of the Chowla conjecture (in the case of two-point correlations (or “pair correlations”)):
Theorem 1 (Logarithmically averaged Chowla conjecture) Let
be natural numbers, and let
be integers such that
. Let
be a quantity depending on
that goes to infinity as
. Let
denote the Liouville function. Then one has
as
.
For comparison, the non-averaged Chowla conjecture would imply that
which is a strictly stronger estimate than (2), and remains open.
The arguments also extend to other completely multiplicative functions than the Liouville function. In particular, one obtains a slightly averaged version of the non-asymptotic Elliott conjecture that was shown in the previous blog post to imply a positive solution to the Erdos discrepancy problem. The averaged version of the conjecture established in this paper is slightly weaker than the one assumed in the previous blog post, but it turns out that the arguments there can be modified without much difficulty to accept this averaged Elliott conjecture as input. In particular, we obtain an unconditional solution to the Erdos discrepancy problem as a consequence; this is detailed in the second paper listed above. In fact we can also handle the vector-valued version of the Erdos discrepancy problem, in which the sequence takes values in the unit sphere of an arbitrary Hilbert space, rather than in
.
Estimates such as (2) or (3) are known to be subject to the “parity problem” (discussed numerous times previously on this blog), which roughly speaking means that they cannot be proven solely using “linear” estimates on functions such as the von Mangoldt function. However, it is known that the parity problem can be circumvented using “bilinear” estimates, and this is basically what is done here.
We now describe in informal terms the proof of Theorem 1, focusing on the model case (2) for simplicity. Suppose for contradiction that the left-hand side of (2) was large and (say) positive. Using the multiplicativity , we conclude that
is also large and positive for all primes that are not too large; note here how the logarithmic averaging allows us to leave the constraint
unchanged. Summing in
, we conclude that
is large and positive for any given set of medium-sized primes. By a standard averaging argument, this implies that
is large for many choices of , where
is a medium-sized parameter at our disposal to choose, and we take
to be some set of primes that are somewhat smaller than
. (A similar approach was taken in this recent paper of Matomaki, Radziwill, and myself to study sign patterns of the Möbius function.) To obtain the required contradiction, one thus wants to demonstrate significant cancellation in the expression (4). As in that paper, we view
as a random variable, in which case (4) is essentially a bilinear sum of the random sequence
along a random graph
on
, in which two vertices
are connected if they differ by a prime
in
that divides
. A key difficulty in controlling this sum is that for randomly chosen
, the sequence
and the graph
need not be independent. To get around this obstacle we introduce a new argument which we call the “entropy decrement argument” (in analogy with the “density increment argument” and “energy increment argument” that appear in the literature surrounding Szemerédi’s theorem on arithmetic progressions, and also reminiscent of the “entropy compression argument” of Moser and Tardos, discussed in this previous post). This argument, which is a simple consequence of the Shannon entropy inequalities, can be viewed as a quantitative version of the standard subadditivity argument that establishes the existence of Kolmogorov-Sinai entropy in topological dynamical systems; it allows one to select a scale parameter
(in some suitable range
) for which the sequence
and the graph
exhibit some weak independence properties (or more precisely, the mutual information between the two random variables is small).
Informally, the entropy decrement argument goes like this: if the sequence has significant mutual information with
, then the entropy of the sequence
for
will grow a little slower than linearly, due to the fact that the graph
has zero entropy (knowledge of
more or less completely determines the shifts
of the graph); this can be formalised using the classical Shannon inequalities for entropy (and specifically, the non-negativity of conditional mutual information). But the entropy cannot drop below zero, so by increasing
as necessary, at some point one must reach a metastable region (cf. the finite convergence principle discussed in this previous blog post), within which very little mutual information can be shared between the sequence
and the graph
. Curiously, for the application it is not enough to have a purely quantitative version of this argument; one needs a quantitative bound (which gains a factor of a bit more than
on the trivial bound for mutual information), and this is surprisingly delicate (it ultimately comes down to the fact that the series
diverges, which is only barely true).
Once one locates a scale with the low mutual information property, one can use standard concentration of measure results such as the Hoeffding inequality to approximate (4) by the significantly simpler expression
The important thing here is that Hoeffding’s inequality gives exponentially strong bounds on the failure probability, which is needed to counteract the logarithms that are inevitably present whenever trying to use entropy inequalities. The expression (5) can then be controlled in turn by an application of the Hardy-Littlewood circle method and a non-trivial estimate
for averaged short sums of a modulated Liouville function established in another recent paper by Matomäki, Radziwill and myself.
When one uses this method to study more general sums such as
one ends up having to consider expressions such as
where is the coefficient
. When attacking this sum with the circle method, one soon finds oneself in the situation of wanting to locate the large Fourier coefficients of the exponential sum
In many cases (such as in the application to the Erdös discrepancy problem), the coefficient is identically
, and one can understand this sum satisfactorily using the classical results of Vinogradov: basically,
is large when
lies in a “major arc” and is small when it lies in a “minor arc”. For more general functions
, the coefficients
are more or less arbitrary; the large values of
are no longer confined to the major arc case. Fortunately, even in this general situation one can use a restriction theorem for the primes established some time ago by Ben Green and myself to show that there are still only a bounded number of possible locations
(up to the uncertainty mandated by the Heisenberg uncertainty principle) where
is large, and we can still conclude by using (6). (Actually, as recently pointed out to me by Ben, one does not need the full strength of our result; one only needs the
restriction theorem for the primes, which can be proven fairly directly using Plancherel’s theorem and some sieve theory.)
It is tempting to also use the method to attack higher order cases of the (logarithmically) averaged Chowla conjecture, for instance one could try to prove the estimate
The above arguments reduce matters to obtaining some non-trivial cancellation for sums of the form
A little bit of “higher order Fourier analysis” (as was done for very similar sums in the ergodic theory context by Frantzikinakis-Host-Kra and Wooley-Ziegler) lets one control this sort of sum if one can establish a bound of the form
where goes to infinity and
is a very slowly growing function of
. This looks very similar to (6), but the fact that the supremum is now inside the integral makes the problem much more difficult. However it looks worth attacking (7) further, as this estimate looks like it should have many nice applications (beyond just the
case of the logarithmically averaged Chowla or Elliott conjectures, which is already interesting).
For higher than
, the same line of analysis requires one to replace the linear phase
by more complicated phases, such as quadratic phases
or even
-step nilsequences. Given that (7) is already beyond the reach of current literature, these even more complicated expressions are also unavailable at present, but one can imagine that they will eventually become tractable, in which case we would obtain an averaged form of the Chowla conjecture for all
, which would have a number of consequences (such as a logarithmically averaged version of Sarnak’s conjecture, as per this blog post).
It would of course be very nice to remove the logarithmic averaging, and be able to establish bounds such as (3). I did attempt to do so, but I do not see a way to use the entropy decrement argument in a manner that does not require some sort of averaging of logarithmic type, as it requires one to pick a scale that one cannot specify in advance, which is not a problem for logarithmic averages (which are quite stable with respect to dilations) but is problematic for ordinary averages. But perhaps the problem can be circumvented by some clever modification of the argument. One possible approach would be to start exploiting multiplicativity at products of primes, and not just individual primes, to try to keep the scale fixed, but this makes the concentration of measure part of the argument much more complicated as one loses some independence properties (coming from the Chinese remainder theorem) which allowed one to conclude just from the Hoeffding inequality.
The Chowla conjecture asserts that all non-trivial correlations of the Liouville function are asymptotically negligible; for instance, it asserts that
as for any fixed natural number
. This conjecture remains open, though there are a number of partial results (e.g. these two previous results of Matomaki, Radziwill, and myself).
A natural generalisation of Chowla’s conjecture was proposed by Elliott. For simplicity we will only consider Elliott’s conjecture for the pair correlations
For such correlations, the conjecture was that one had
as for any natural number
, as long as
was a completely multiplicative function with magnitude bounded by
, and such that
for any Dirichlet character and any real number
. In the language of “pretentious number theory”, as developed by Granville and Soundararajan, the hypothesis (2) asserts that the completely multiplicative function
does not “pretend” to be like the completely multiplicative function
for any character
and real number
. A condition of this form is necessary; for instance, if
is precisely equal to
and
has period
, then
is equal to
as
and (1) clearly fails. The prime number theorem in arithmetic progressions implies that the Liouville function obeys (2), and so the Elliott conjecture contains the Chowla conjecture as a special case.
As it turns out, Elliott’s conjecture is false as stated, with the counterexample having the property that
“pretends” locally to be the function
for
in various intervals
, where
and
go to infinity in a certain prescribed sense. See this paper of Matomaki, Radziwill, and myself for details. However, we view this as a technicality, and continue to believe that certain “repaired” versions of Elliott’s conjecture still hold. For instance, our counterexample does not apply when
is restricted to be real-valued rather than complex, and we believe that Elliott’s conjecture is valid in this setting. Returning to the complex-valued case, we still expect the asymptotic (1) provided that the condition (2) is replaced by the stronger condition
as for all fixed Dirichlet characters
. In our paper we supported this claim by establishing a certain “averaged” version of this conjecture; see that paper for further details. (See also this recent paper of Frantzikinakis and Host which establishes a different averaged version of this conjecture.)
One can make a stronger “non-asymptotic” version of this corrected Elliott conjecture, in which the parameter does not go to infinity, or equivalently that the function
is permitted to depend on
:
Conjecture 1 (Non-asymptotic Elliott conjecture) Let
, let
be sufficiently large depending on
, and let
be sufficiently large depending on
. Suppose that
is a completely multiplicative function with magnitude bounded by
, such that
for all Dirichlet characters
of period at most
. Then one has
for all natural numbers
.
The -dependent factor
in the constraint
is necessary, as can be seen by considering the completely multiplicative function
(for instance). Again, the results in my previous paper with Matomaki and Radziwill can be viewed as establishing an averaged version of this conjecture.
Meanwhile, we have the following conjecture that is the focus of the Polymath5 project:
Conjecture 2 (Erdös discrepancy conjecture) For any function
, the discrepancy
is infinite.
It is instructive to compute some near-counterexamples to Conjecture 2 that illustrate the difficulty of the Erdös discrepancy problem. The first near-counterexample is that of a non-principal Dirichlet character that takes values in
rather than
. For this function, one has from the complete multiplicativity of
that
If denotes the period of
, then
has mean zero on every interval of length
, and thus
Thus has bounded discrepancy.
Of course, this is not a true counterexample to Conjecture 2 because can take the value
. Let us now consider the following variant example, which is the simplest member of a family of examples studied by Borwein, Choi, and Coons. Let
be the non-principal Dirichlet character of period
(thus
equals
when
,
when
, and
when
), and define the completely multiplicative function
by setting
when
and
. This is about the simplest modification one can make to the previous near-counterexample to eliminate the zeroes. Now consider the sum
with for some large
. Writing
with
coprime to
and
at most
, we can write this sum as
Now observe that . The function
has mean zero on every interval of length three, and
is equal to
mod
, and thus
for every , and thus
Thus also has unbounded discrepancy, but only barely so (it grows logarithmically in
). These examples suggest that the main “enemy” to proving Conjecture 2 comes from completely multiplicative functions
that somehow “pretend” to be like a Dirichlet character but do not vanish at the zeroes of that character. (Indeed, the special case of Conjecture 2 when
is completely multiplicative is already open, appears to be an important subcase.)
All of these conjectures remain open. However, I would like to record in this blog post the following striking connection, illustrating the power of the Elliott conjecture (particularly in its nonasymptotic formulation):
Theorem 3 (Elliott conjecture implies unbounded discrepancy) Conjecture 1 implies Conjecture 2.
The argument relies heavily on two observations that were previously made in connection with the Polymath5 project. The first is a Fourier-analytic reduction that replaces the Erdos Discrepancy Problem with an averaged version for completely multiplicative functions . An application of Cauchy-Schwarz then shows that any counterexample to that version will violate the conclusion of Conjecture 1, so if one assumes that conjecture then
must pretend to be like a function of the form
. One then uses (a generalisation) of a second argument from Polymath5 to rule out this case, basically by reducing matters to a more complicated version of the Borwein-Choi-Coons analysis. Details are provided below the fold.
There is some hope that the Chowla and Elliott conjectures can be attacked, as the parity barrier which is so impervious to attack for the twin prime conjecture seems to be more permeable in this setting. (For instance, in my previous post I raised a possible approach, based on establishing expander properties of a certain random graph, which seems to get around the parity problem, in principle at least.)
(Update, Sep 25: fixed some treatment of error terms, following a suggestion of Andrew Granville.)
Kaisa Matomäki, Maksym Radziwiłł, and I have just uploaded to the arXiv our paper “Sign patterns of the Liouville and Möbius functions“. This paper is somewhat similar to our previous paper in that it is using the recent breakthrough of Matomäki and Radziwiłł on mean values of multiplicative functions to obtain partial results towards the Chowla conjecture. This conjecture can be phrased, roughly speaking, as follows: if is a fixed natural number and
is selected at random from a large interval
, then the sign pattern
becomes asymptotically equidistributed in
in the limit
. This remains open for
. In fact even the significantly weaker statement that each of the sign patterns in
is attained infinitely often is open for
. However, in 1986, Hildebrand showed that for
all sign patterns are indeed attained infinitely often. Our first result is a strengthening of Hildebrand’s, moving a little bit closer to Chowla’s conjecture:
Theorem 1 Let
. Then each of the sign patterns in
is attained by the Liouville function for a set of natural numbers
of positive lower density.
Thus for instance one has for a set of
of positive lower density. The
case of this theorem already appears in the original paper of Matomäki and Radziwiłł (and the significantly simpler case of the sign patterns
and
was treated previously by Harman, Pintz, and Wolke).
The basic strategy in all of these arguments is to assume for sake of contradiction that a certain sign pattern occurs extremely rarely, and then exploit the complete multiplicativity of (which implies in particular that
,
, and
for all
) together with some combinatorial arguments (vaguely analogous to solving a Sudoku puzzle!) to establish more complex sign patterns for the Liouville function, that are either inconsistent with each other, or with results such as the Matomäki-Radziwiłł result. To illustrate this, let us give some
examples, arguing a little informally to emphasise the combinatorial aspects of the argument. First suppose that the sign pattern
almost never occurs. The prime number theorem tells us that
and
are each equal to
about half of the time, which by inclusion-exclusion implies that the sign pattern
almost never occurs. In other words, we have
for almost all
. But from the multiplicativity property
this implies that one should have
and
for almost all . But the above three statements are contradictory, and the claim follows.
Similarly, if we assume that the sign pattern almost never occurs, then a similar argument to the above shows that for any fixed
, one has
for almost all
. But this means that the mean
is abnormally large for most
, which (for
large enough) contradicts the results of Matomäki and Radziwiłł. Here we see that the “enemy” to defeat is the scenario in which
only changes sign very rarely, in which case one rarely sees the pattern
.
It turns out that similar (but more combinatorially intricate) arguments work for sign patterns of length three (but are unlikely to work for most sign patterns of length four or greater). We give here one fragment of such an argument (due to Hildebrand) which hopefully conveys the Sudoku-type flavour of the combinatorics. Suppose for instance that the sign pattern almost never occurs. Now suppose
is a typical number with
. Since we almost never have the sign pattern
, we must (almost always) then have
. By multiplicativity this implies that
We claim that this (almost always) forces . For if
, then by the lack of the sign pattern
, this (almost always) forces
, which by multiplicativity forces
, which by lack of
(almost always) forces
, which by multiplicativity contradicts
. Thus we have
; a similar argument gives
almost always, which by multiplicativity gives
, a contradiction. Thus we almost never have
, which by the inclusion-exclusion argument mentioned previously shows that
for almost all
.
One can continue these Sudoku-type arguments and conclude eventually that for almost all
. To put it another way, if
denotes the non-principal Dirichlet character of modulus
, then
is almost always constant away from the multiples of
. (Conversely, if
changed sign very rarely outside of the multiples of three, then the sign pattern
would never occur.) Fortunately, the main result of Matomäki and Radziwiłł shows that this scenario cannot occur, which establishes that the sign pattern
must occur rather frequently. The other sign patterns are handled by variants of these arguments.
Excluding a sign pattern of length three leads to useful implications like “if , then
” which turn out are just barely strong enough to quite rigidly constrain the Liouville function using Sudoku-like arguments. In contrast, excluding a sign pattern of length four only gives rise to implications like “`if
, then
“, and these seem to be much weaker for this purpose (the hypothesis in these implications just isn’t satisfied nearly often enough). So a different idea seems to be needed if one wishes to extend the above theorem to larger values of
.
Our second theorem gives an analogous result for the Möbius function (which takes values in
rather than
), but the analysis turns out to be remarkably difficult and we are only able to get up to
:
Theorem 2 Let
. Then each of the sign patterns in
is attained by the Möbius function for a set
of positive lower density.
It turns out that the prime number theorem and elementary sieve theory can be used to handle the case and all the
cases that involve at least one
, leaving only the four sign patterns
to handle. It is here that the zeroes of the Möbius function cause a significant new obstacle. Suppose for instance that the sign pattern
almost never occurs for the Möbius function. The same arguments that were used in the Liouville case then show that
will be almost always equal to
, provided that
are both square-free. One can try to chain this together as before to create a long string
where the Möbius function is constant, but this cannot work for any
larger than three, because the Möbius function vanishes at every multiple of four.
The constraints we assume on the Möbius function can be depicted using a graph on the squarefree natural numbers, in which any two adjacent squarefree natural numbers are connected by an edge. The main difficulty is then that this graph is highly disconnected due to the multiples of four not being squarefree.
To get around this, we need to enlarge the graph. Note from multiplicativity that if is almost always equal to
when
are squarefree, then
is almost always equal to
when
are squarefree and
is divisible by
. We can then form a graph on the squarefree natural numbers by connecting
to
whenever
are squarefree and
is divisible by
. If this graph is “locally connected” in some sense, then
will be constant on almost all of the squarefree numbers in a large interval, which turns out to be incompatible with the results of Matomäki and Radziwiłł. Because of this, matters are reduced to establishing the connectedness of a certain graph. More precisely, it turns out to be sufficient to establish the following claim:
Theorem 3 For each prime
, let
be a residue class chosen uniformly at random. Let
be the random graph whose vertices
consist of those integers
not equal to
for any
, and whose edges consist of pairs
in
with
. Then with probability
, the graph
is connected.
We were able to show the connectedness of this graph, though it turned out to be remarkably tricky to do so. Roughly speaking (and suppressing a number of technicalities), the main steps in the argument were as follows.
- (Early stage) Pick a large number
(in our paper we take
to be odd, but I’ll ignore this technicality here). Using a moment method to explore neighbourhoods of a single point in
, one can show that a vertex
in
is almost always connected to at least
numbers in
, using relatively short paths of short diameter. (This is the most computationally intensive portion of the argument.)
- (Middle stage) Let
be a typical number in
, and let
be a scale somewhere between
and
. By using paths
involving three primes, and using a variant of Vinogradov’s theorem and some routine second moment computations, one can show that with quite high probability, any “good” vertex in
is connected to a “good” vertex in
by paths of length three, where the definition of “good” is somewhat technical but encompasses almost all of the vertices in
.
- (Late stage) Combining the two previous results together, we can show that most vertices
will be connected to a vertex in
for any
in
. In particular,
will be connected to a set of
vertices in
. By tracking everything carefully, one can control the length and diameter of the paths used to connect
to this set, and one can also control the parity of the elements in this set.
- (Final stage) Now if we have two vertices
at a distance
apart. By the previous item, one can connect
to a large set
of vertices in
, and one can similarly connect
to a large set
of vertices in
. Now, by using a Vinogradov-type theorem and second moment calculations again (and ensuring that the elements of
and
have opposite parity), one can connect many of the vertices in
to many of the vertices
by paths of length three, which then connects
to
, and gives the claim.
It seems of interest to understand random graphs like further. In particular, the graph
on the integers formed by connecting
to
for all
in a randomly selected residue class mod
for each prime
is particularly interesting (it is to the Liouville function as
is to the Möbius function); if one could show some “local expander” properties of this graph
, then one would have a chance of modifying the above methods to attack the first unsolved case of the Chowla conjecture, namely that
has asymptotic density zero (perhaps working with logarithmic density instead of natural density to avoids some technicalities).
Recent Comments