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 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:
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):
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.)
— 1. Fourier reduction —
We will prove Theorem 3 by contradiction, assuming that there is a function with bounded discrepancy and then concluding a violation of the Elliott conjecture.
The function need not have any multiplicativity properties, but by using an argument from Polymath5 we can extract a random completely multiplicative function which also has good discrepancy properties (albeit in an probabilistic sense only):
Then there exists a random completely multiplicative function of magnitude such that
uniformly for all natural numbers (we allow implied constants to depend on ).
Proof: For the readers convenience, we reproduce the Polymath5 argument.
The space of completely multiplicative functions of magnitude can be identified with the infinite product since is determined by its values at the primes. In particular, this space is compact metrisable in the product topology. The functions are continuous in this topology for all . By vague compactness of probability measures on compact metrisable spaces (Prokhorov’s theorem), it thus suffices to construct, for each , a random completely multiplicative function of magnitude such that
for all , where the implied constant is uniform in and .
for all (the implied constant can depend on but is otherwise absolute). Let , and let be the primes up to . Let be a natural number that we assume to be sufficiently large depending on . Define a function by the formula
for . We also define the function by setting whenever is in (this is well defined for ). Applying (4) for and of the form with , we conclude that
for all and all but of the elements of . For the exceptional elements, we have the trivial bound
By Fourier expansion, we can write
where , , and
A little Fourier-analytic calculation then allows us to write the left-hand side of (5) as
On the other hand, from the Plancherel identity we have
and so we can interpret as the probability distribution of a random frequency . The estimate (5) now takes the form
for all . If we then define the completely multiplicative function by setting for , and for all other primes, we obtain
for all , as desired.
Remark 5 A similar reduction applies if the original function took values in the unit sphere of a complex Hilbert space, rather than in . Conversely, the random constructed above can be viewed as an element of a unit sphere of a suitable Hilbert space, so the conclusion of Proposition 4 is in fact logically equivalent to failure of the Hilbert space version of the Erdös discrepancy conjecture.
Remark 6 From linearity of expectation, we see from Proposition 4 that for any natural number , we have
and hence for each we conclude that there exists a deterministic completely multiplicative function of unit magnitude such that
This was the original formulation of the Fourier reduction in Polymath5, however the fact that varied with made this formulation inconvenient for our argument.
— 2. Applying the Elliott conjecture —
Suppose for contradiction that Conjecture 1 holds but that there exists a function of bounded discrepancy in the sense of (3). By Proposition 4, we may thus find a random completely multiplicative function of magnitude such that
for all .
We now use Elliott’s conjecture as a sort of “inverse theorem” (in the spirit of the inverse sumset theorem of Frieman, and the inverse theorems for the Gowers uniformity norms) to force to pretend to behave like a modulated character quite often.
Proposition 7 Let the hypotheses and notation be as above. Let , and suppose that is sufficiently large depending on . Then with probability , one can find a Dirichlet character of period and a real number such that
Proof: We use the van der Corput trick. Let be a moderately large natural number depending on to be chosen later, and suppose that is sufficiently large depending on . From (6) and the triangle inequality we have
so from Markov’s inequality we see with probability that
Let us condition to this event. Shifting by we conclude (for large enough) that
and hence by the triangle inequality
which we rewrite as
We can square the left-hand side out as
The diagonal term contributes to this expression. Thus, for sufficiently large depending on , we can apply the triangle inequality and pigeonhole principle to find distinct such that
By symmetry we can take . Setting , we conclude (for large enough) that
Applying Conjecture 1 in the contrapositive, we obtain the claim.
The conclusion (8) asserts that in some sense, “pretends” to be like the function ; as it has magnitude one, it should resemble the function discussed in the introduction. The remaining task is to find some generalisation of the argument that shows that had (logarithmically) large discrepancy to show that likewise fails to obey (6).
— 3. Ruling out correlation with modulated characters —
- A sufficiently small quantity .
- A natural number that is sufficiently large depending on .
- A quantity that is sufficiently small depending on .
- A natural number that is sufficiently large depending on .
- A real number that is sufficiently large depending on .
By Proposition 7, we see with probability that there exists a Dirichlet character of period and a real number such that
By reducing if necessary we may assume that is primitive.
It will be convenient to cut down the size of .
Proof: By Proposition 7 with replaced by , we see that with probability , one can find a Dirichlet character of period and a real number such that
We may assume that , since we are done otherwise. Applying the pretentious triangle inequality (see Lemma 3.1 of this paper of Granville and Soundararajan), we conclude that
However, from the Vinogradov-Korobov zero-free region for (see this previous blog post) it is not difficult to show that
if is sufficiently large depending on , a contradiction. The claim follows.
The bound (8) asserts that “pretends” to be like the completely multiplicative function . We can formalise this by making the factorisation
where is the completely multiplicative function of magnitude defined by setting for and for , and is the completely multiplicative function of magnitude defined by setting for , and for . The function should be compared with the function of the same name studied in the introduction.
The bound (8) then becomes
We now perform some manipulations to remove the and factors from and isolate the factor, which is more tractable to compute with; then we will perform more computations to arrive at an expression just involving which we will be able to evaluate fairly easily.
From (6) and the triangle inequality we have
for all (even after conditioning to the event). The averaging will not be used until much later in the argument, and the reader may wish to ignore it for now.
By (10), the above estimate can be written as
For we can use (9) to conclude that . The contribution of the error term is negligible, thus
for all . We can factor out the to obtain
For we can crudely bound the left-hand side by . If is sufficiently small, we can then sum weighted by and conclude that
(The zeta function type weight of will be convenient later in the argument when one has to perform some multiplicative number theory, as the relevant sums can be computed quite directly and easily using Euler products.) Thus, with probability , one has
We condition to this event. We have successfully eliminated the role of ; we now work to eliminate . Call a residue class bad if is divisible by for some and . and good otherwise. We restrict to good residue classes, thus
By Cauchy-Schwarz, we conclude that
Now we claim that for a in a good residue class , the quantity does not depend on . Indeed, by hypothesis, is not divisible by for any and is thus a factor of , and is coprime to . We then factor
where in the last line we use the periodicity of . Thus we have , and so
Shifting by we see that
Now, we perform some multiplicative number theory to understand the innermost sum. From taking Euler products we have
for ; from (11) and Mertens’ theorem one can easily verify that
More generally, for any Dirichlet character we have
which after using (11), Cauchy-Schwarz (using and Mertens theorem gives
for any non-principal character of period dividing ; for a principal character of period dividing we have
since and hence for all , where we have also used (13). By expansion into Dirichlet characters we conclude that
for all and primitive residue classes . For non-primitive residue classes , we write and . The previous arguments then give
which since gives (again using (13))
for all (not necessarily primitive). Inserting this back into (12) we see that
and thus by (13) we conclude (for large enough) that
We have now eliminated both and . The remaining task is to establish some lower bound on the discrepancy of that will contradict (14). As mentioned above, this will be a more complicated variant of the Borwein-Choi-Coons analysis in the introduction. The square in (14) will be helpful in dealing with the fact that we don’t have good control on the for (as we shall see, the squaring introduces two terms of this type that end up cancelling each other).
We expand (14) to obtain
Write and , thus and for we have
We thus have
For or , the inner sum is , which by the divisor bound gives a negligible contribution. Thus we may restrict to . Note that as is already restricted to numbers coprime to , and divide , we may replace the constraints with for .
We consider the contribution of an off-diagonal term for a fixed choice of . To handle these terms we expand the non-principal character as a linear combination of for with Fourier coefficients . Thus we can expand out
as a linear combination of expressions of the form
with and coefficients of size .
The constraints are either inconsistent, or constrain to a single residue class . Writing , we have
for some phase that can depend on but is independent of . If , then at least one of the two quantities and is divisible by a prime that does not divide the other quantity. Therefore cannot be divisible by , and thus by . We can then sum the geometric series in (or ) and conclude that
and so by the divisor bound the off-diagonal terms contribute at most to (15). For large, this is negligible, and thus we only need to consider the diagonal contribution . Here the terms helpfully cancel, and we obtain
We have now eliminated , leaving only the Dirichlet character which is much easier to work with. We gather terms and write the left-hand side as
The summand in is now non-negative. We can thus throw away all the except of the form with , to conclude that
It is now that we finally take advantage of the averaging to simplify the summation. Observe from the triangle inequality that for any and one has
summing over we conclude that
In particular, by the pigeonhole principle there exists such that
Shifting by and discarding some terms, we conclude that
Observe that for a fixed there is exactly one in the inner sum, and . Thus we have
Making the change of variables , we thus have
But is periodic of period with mean , thus
which leads to a contradiction for large enough (note the logarithmic growth in here, matching the logarithmic growth in the Borwein-Choi-Coons analysis). The claim follows.