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 1Let . 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 2Let . 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 3For 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).

## 18 comments

Comments feed for this article

6 September, 2015 at 7:51 pm

Philip LeePlease pardon me if this doesn’t belong here. I saw a glance of the wave equation approach to automorphic function, though not having any special skills in the area, it did remind me of the generating functions from combinatorics. There is also in my mind relationship to Newman’s proof of the prime number theorem. I am trying to read and understand it, at least to try to learn the estimation involved or the techniques that lead to it.

Generating functions as complex functions, and their singularities (by Cauchy integral theorem) give asymptotic estimates for the size of combinatorial objects. This is inspired by an Analysis of Algorithms course online. Are there any specific connections worked out connecting these and the primes as a combinatorial (set?)? There is a Fourier series for the Mobius function in connection to the post above, otherwise I hope that this post doesn’t distract the comments anyway.

6 September, 2015 at 9:18 pm

AnonymousCan theorem 1 be generalized for the sign patterns of for some fixed nonconsecutive(!) triples ?

(obviously, we may assume and ).

7 September, 2015 at 8:13 am

Terence TaoGood question! Each such triple will generate a different “Sudoku puzzle” that needs to be solved (where the Sudoku-type constraints are that avoids a certain sign pattern as ranges over small numbers and ranges over all natural numbers). We were lucky in the case that these constraints (together with some additional information on coming from the prime number theorem) were enough to limit the possible solutions to ones that could be ruled out by Matomaki-Radziwill. However for other choices of this triple, it is not clear that the solution set is as rigid, the problem may become seriously underdetermined. (One may have to work in the asymptotic regime where is allowed to be large, in contrast with our analysis which basically only needs those that are divisible by 60.

7 September, 2015 at 4:40 am

WillIs it crucial that this graph be on the integers and not some interval of the integers? I’m trying to formalize the expander graph problem at the end and I want to work with the graph on the interval where you connect one residue class mod for all . There are only possible choices of residue classes and sets the graph could fail to expand, so trying to use the probabilistic method and the union bound in the obvious way there isn't a lot of extra room.

7 September, 2015 at 10:45 am

Terence TaoIt doesn’t seem to make much difference where one restricts the integers, but one can weaken the expansion requirement by only needing to test sets that are well distributed locally. More precisely, the claim needed is the following:

* Let be large, and let be sufficiently large depending on . Form the random graph on by connecting together and for all odd primes and all in a randomly selected residue class . Then, with probability (as go to infinity), one has a bound of the form whenever has the property that for all and all residue classes with (probably one only needs this for q=2, to deal with the bipartite nature of G).

If one has this claim then one can show that , that is to say one has the first nontrivial case of Chowla’s conjecture in the logarithmic density category. One can also restrict the primes to a subset of the primes less than X, at the cost of replacing by .

As you say, a direct probabilistic argument looks unpromising. One may have to locate some other property that implies expansion (e.g. some mixing property of the random walk) which does not require one to verify an exponential number of assertions. Unfortunately one has to control the random walk for times up to almost to make a naive version of this strategy work; in our paper we were able to control the walk up to a little bit less than but the combinatorics became quite complicated beyond that point and we used a different method to propagate the graph further.

A model problem may be to replace G by a weighted Erdos-Turan model in which any pair n,n+p are connected with an independent probability of 1/p (rather than only connecting those n,n+p in a random residue class). Now there is a lot more randomness and a Pinsker type probabilistic argument of the type you propose may work.

8 September, 2015 at 1:22 pm

Terence TaoDid a quick back of the envelope calculation using Bennett’s inequality for the Erdos-Turan model mentioned above. For a fixed choice of , is the sum of about random variables of total variance about , so if I did my calculations correctly, Bennett’s inequality predicts some cancellation in this sum with probability about , which is superexponential and so one usually has the desired expansion property. Heuristically this predicts (but does not prove) that the original random graph G should also have the required expansion property.

7 September, 2015 at 11:40 am

arch16th paragraph: “a similar argument gives {\lambda(60n-5)} *= -1* almost always,…”

[Corrected, thanks – T.]9 September, 2015 at 12:06 am

Uwe StroinskiThe Sudoku-flavor arguments remind me on the EDP Polymath project, where some of us tried to prove (without computer) that completely multiplicative sequences with values in have discrepancy greater than 3. Can these recent results of Matomaki and Radziwill be used/adapted/generalized to help with this problem or is there some obstacle to make that hopeless ?

9 September, 2015 at 11:08 am

Terence TaoThere is indeed some similarity on the surface, but Matomaki-Radziwill only lets one control the sum of a -valued multiplicative functions in short intervals such as where is much smaller than , basically by using Fourier inversion (or Perron’s formula) to convert this to a question about the Dirichlet series . Roughly speaking, the relationship between the intervals and the phases is that and essentially differ only by a constant when . By using Dirichlet characters one can also control in short progressions such as for small, medium size, and very large, but I don’t see an obvious way to control the EDP type discrepancies which are more to do with progressions such as when are both large.

EDIT: Ah, using complete multiplicativity I see that the EDP for completely multiplicative functions is equivalent to

lower boundingthe sum of on intervals such as rather than upper bounding it. The Matomaki-Radziwill technology is geared towards upper bounds only. As usual we have the problem that Dirichlet characters already have bounded discrepancy, so one has to somehow use the fact that the multiplicative function doesn’t vanish…29 September, 2015 at 5:22 am

DomiIn the end this was useful: http://arxiv.org/abs/1509.05363

Congratulations!

9 September, 2015 at 2:27 pm

kodlu2nd paragraph after Theorem 1, the fragment “…which implies for in particular that…” seems to have an extra “for”.

And I’d like to second Uwe Stroinsky’s query, re: EDP for the multiplicative case.

[Corrected, thanks – T.]9 September, 2015 at 9:16 pm

Terence TaoHmm, actually there does appear to be a connection between the EDP and something we looked at in our previous paper, namely Elliott’s conjecture (a generalisation of Chowla’s conjecture to arbitrary bounded multiplicative functions). There is in fact a chance that a suitable version of this conjecture implies that all +1,-1 sequences have unbounded discrepancy. I’ll work this out in detail a subsequent blog post.

11 September, 2015 at 6:27 am

The Erdos discrepancy problem via the Elliott conjecture | What's new[…] number . This conjecture remains open, though there are a number of partial results (e.g. these two previous results of Matomaki, Radziwill, and […]

18 September, 2015 at 4:11 am

Updates and plans III. | Combinatorics and more[…] posts by Terry Tao (1), (2) (reporting also on subsequent works by Matomaki, Radzwill, and Tao) NEW (3) (4)). Update (Sept 18, 2015): Terry Tao have just uploaded a paper to the arxive where he solves […]

18 September, 2015 at 4:46 pm

The logarithmically averaged Chowla and Elliott conjectures for two-point correlations; the Erdos discrepancy problem | What's new[…] pair of papers is an outgrowth of these two recent blog posts and the ensuing discussion. In the first paper, we establish the following […]

24 September, 2015 at 8:46 am

Frogs and Lily Pads and Discrepancy | Gödel's Lost Letter and P=NP[…] famous Discrepancy Conjecture” (DC) of Paul Erdős. This emerged from discussion of his two earlier posts this month on his blog. They and his 9/18 announcement post re-create much of the […]

17 October, 2015 at 3:39 am

A Magical Answer to an 80-Year-Old Puzzle | Quorai[…] of potential applications of their method to problems in number theory. On September 6, Tao wrote a blog post about some of this work pertaining to the Liouville function, and he mentioned that the problem […]

8 November, 2015 at 4:36 pm

Problem rozbieżności Erdősa | Nowe Problemy[…] od tego tematu, chociaż związanymi z własnościami ciągów multiplikatywnych. 6 września opisał na swoim blogu stan swoich prac. 9 września Uwe Stroinski pozostawił pod tym wpisem komentarz o możliwym […]