Tag Archive

You are currently browsing the tag archive for the ‘Liouville function’ tag.

Value patterns of multiplicative functions and related sequences

11 April, 2019 in math.CO, math.NT, paper | Tags: Joni Teravainen, Liouville function, sign patterns | by Terence Tao | 4 comments

Joni Teräväinen and I have just uploaded to the arXiv our paper “Value patterns of multiplicative functions and related sequences“, submitted to Forum of Mathematics, Sigma. This paper explores how to use recent technology on correlations of multiplicative (or nearly multiplicative functions), such as the “entropy decrement method”, in conjunction with techniques from additive combinatorics, to establish new results on the sign patterns of functions such as the Liouville function ${\lambda}$ . For instance, with regards to length 5 sign patterns

$\displaystyle (\lambda(n+1),\dots,\lambda(n+5)) \in \{-1,+1\}^5$

of the Liouville function, we can now show that at least ${24}$ of the ${32}$ possible sign patterns in ${\{-1,+1\}^5}$ occur with positive upper density. (Conjecturally, all of them do so, and this is known for all shorter sign patterns, but unfortunately ${24}$ seems to be the limitation of our methods.)

The Liouville function can be written as ${\lambda(n) = e^{2\pi i \Omega(n)/2}}$ , where ${\Omega(n)}$ is the number of prime factors of ${n}$ (counting multiplicity). One can also consider the variant ${\lambda_3(n) = e^{2\pi i \Omega(n)/3}}$ , which is a completely multiplicative function taking values in the cube roots of unity ${\{1, \omega, \omega^2\}}$ . Here we are able to show that all ${27}$ sign patterns in ${\{1,\omega,\omega^2\}}$ occur with positive lower density as sign patterns ${(\lambda_3(n+1), \lambda_3(n+2), \lambda_3(n+3))}$ of this function. The analogous result for ${\lambda}$ was already known (see this paper of Matomäki, Radziwiłł, and myself), and in that case it is even known that all sign patterns occur with equal logarithmic density ${1/8}$ (from this paper of myself and Teräväinen), but these techniques barely fail to handle the ${\lambda_3}$ case by itself (largely because the “parity” arguments used in the case of the Liouville function no longer control three-point correlations in the ${\lambda_3}$ case) and an additional additive combinatorial tool is needed. After applying existing technology (such as entropy decrement methods), the problem roughly speaking reduces to locating patterns ${a \in A_1, a+r \in A_2, a+2r \in A_3}$ for a certain partition ${G = A_1 \cup A_2 \cup A_3}$ of a compact abelian group ${G}$ (think for instance of the unit circle ${G={\bf R}/{\bf Z}}$ , although the general case is a bit more complicated, in particular if ${G}$ is disconnected then there is a certain “coprimality” constraint on ${r}$ , also we can allow the ${A_1,A_2,A_3}$ to be replaced by any ${A_{c_1}, A_{c_2}, A_{c_3}}$ with ${c_1+c_2+c_3}$ divisible by ${3}$ ), with each of the ${A_i}$ having measure ${1/3}$ . An inequality of Kneser just barely fails to guarantee the existence of such patterns, but by using an inverse theorem for Kneser’s inequality in this previous paper of mine we are able to identify precisely the obstruction for this method to work, and rule it out by an ad hoc method.

The same techniques turn out to also make progress on some conjectures of Erdös-Pomerance and Hildebrand regarding patterns of the largest prime factor ${P^+(n)}$ of a natural number ${n}$ . For instance, we improve results of Erdös-Pomerance and of Balog demonstrating that the inequalities

$\displaystyle P^+(n+1) < P^+(n+2) < P^+(n+3)$

and

$\displaystyle P^+(n+1) > P^+(n+2) > P^+(n+3)$

each hold for infinitely many ${n}$ , by demonstrating the stronger claims that the inequalities

$\displaystyle P^+(n+1) < P^+(n+2) < P^+(n+3) > P^+(n+4)$

and

$\displaystyle P^+(n+1) > P^+(n+2) > P^+(n+3) < P^+(n+4)$

each hold for a set of ${n}$ of positive lower density. As a variant, we also show that we can find a positive density set of ${n}$ for which

$\displaystyle P^+(n+1), P^+(n+2), P^+(n+3) > n^\gamma$

for any fixed ${\gamma < e^{-1/3} = 0.7165\dots}$ (this improves on a previous result of Hildebrand with ${e^{-1/3}}$ replaced by ${e^{-1/2} = 0.6065\dots}$ . A number of other results of this type are also obtained in this paper.

In order to obtain these sorts of results, one needs to extend the entropy decrement technology from the setting of multiplicative functions to that of what we call “weakly stable sets” – sets ${A}$ which have some multiplicative structure, in the sense that (roughly speaking) there is a set ${B}$ such that for all small primes ${p}$ , the statements ${n \in A}$ and ${pn \in B}$ are roughly equivalent to each other. For instance, if ${A}$ is a level set ${A = \{ n: \omega(n) = 0 \hbox{ mod } 3 \}}$ , one would take ${B = \{ n: \omega(n) = 1 \hbox{ mod } 3 \}}$ ; if instead ${A}$ is a set of the form ${\{ n: P^+(n) \geq n^\gamma\}}$ , then one can take ${B=A}$ . When one has such a situation, then very roughly speaking, the entropy decrement argument then allows one to estimate a one-parameter correlation such as

$\displaystyle {\bf E}_n 1_A(n+1) 1_A(n+2) 1_A(n+3)$

with a two-parameter correlation such as

$\displaystyle {\bf E}_n {\bf E}_p 1_B(n+p) 1_B(n+2p) 1_B(n+3p)$

(where we will be deliberately vague as to how we are averaging over ${n}$ and ${p}$ ), and then the use of the “linear equations in primes” technology of Ben Green, Tamar Ziegler, and myself then allows one to replace this average in turn by something like

$\displaystyle {\bf E}_n {\bf E}_r 1_B(n+r) 1_B(n+2r) 1_B(n+3r)$

where ${r}$ is constrained to be not divisible by small primes but is otherwise quite arbitrary. This latter average can then be attacked by tools from additive combinatorics, such as translation to a continuous group model (using for instance the Furstenberg correspondence principle) followed by tools such as Kneser’s inequality (or inverse theorems to that inequality).

Fourier uniformity of bounded multiplicative functions in short intervals on average

5 December, 2018 in math.NT, paper | Tags: Chowla conjecture, Kaisa Matomaki, Liouville function, Maksym Radziwill | by Terence Tao | 13 comments

Kaisa Matomäki, Maksym Radziwill, and I just uploaded to the arXiv our paper “Fourier uniformity of bounded multiplicative functions in short intervals on average“. This paper is the outcome of our attempts during the MSRI program in analytic number theory last year to attack the local Fourier uniformity conjecture for the Liouville function ${\lambda}$ . This conjecture generalises a landmark result of Matomäki and Radziwill, who show (among other things) that one has the asymptotic

$\displaystyle \int_X^{2X} |\sum_{x \leq n \leq x+H} \lambda(n)|\ dx = o(HX) \ \ \ \ \ (1)$

whenever ${X \rightarrow \infty}$ and ${H = H(X)}$ goes to infinity as ${X \rightarrow \infty}$ . Informally, this says that the Liouville function has small mean for almost all short intervals ${[x,x+H]}$ . The remarkable thing about this theorem is that there is no lower bound on how ${H}$ goes to infinity with ${X}$ ; one can take for instance ${H = \log\log\log X}$ . This lack of lower bound was crucial when I applied this result (or more precisely, a generalisation of this result to arbitrary non-pretentious bounded multiplicative functions) a few years ago to solve the Erdös discrepancy problem, as well as a logarithmically averaged two-point Chowla conjecture, for instance it implies that

$\displaystyle \sum_{n \leq X} \frac{\lambda(n) \lambda(n+1)}{n} = o(\log X).$

The local Fourier uniformity conjecture asserts the stronger asymptotic

$\displaystyle \int_X^{2X} \sup_{\alpha \in {\bf R}} |\sum_{x \leq n \leq x+H} \lambda(n) e(-\alpha n)|\ dx = o(HX) \ \ \ \ \ (2)$

under the same hypotheses on ${H}$ and ${X}$ . As I worked out in a previous paper, this conjecture would imply a logarithmically averaged three-point Chowla conjecture, implying for instance that

$\displaystyle \sum_{n \leq X} \frac{\lambda(n) \lambda(n+1) \lambda(n+2)}{n} = o(\log X).$

This particular bound also follows from some slightly different arguments of Joni Teräväinen and myself, but the implication would also work for other non-pretentious bounded multiplicative functions, whereas the arguments of Joni and myself rely more heavily on the specific properties of the Liouville function (in particular that ${\lambda(p)=-1}$ for all primes ${p}$ ).

There is also a higher order version of the local Fourier uniformity conjecture in which the linear phase ${{}e(-\alpha n)}$ is replaced with a polynomial phase such as ${e(-\alpha_d n^d - \dots - \alpha_1 n - \alpha_0)}$ , or more generally a nilsequence ${\overline{F(g(n) \Gamma)}}$ ; as shown in my previous paper, this conjecture implies (and is in fact equivalent to, after logarithmic averaging) a logarithmically averaged version of the full Chowla conjecture (not just the two-point or three-point versions), as well as a logarithmically averaged version of the Sarnak conjecture.

The main result of the current paper is to obtain some cases of the local Fourier uniformity conjecture:

Theorem 1 The asymptotic (2) is true when ${H = X^\theta}$ for a fixed ${\theta > 0}$ .

Previously this was known for ${\theta > 5/8}$ by the work of Zhan (who in fact proved the stronger pointwise assertion ${\sup_{\alpha \in {\bf R}} |\sum_{x \leq n \leq x+H} \lambda(n) e(-\alpha n)|= o(H)}$ for ${X \leq x \leq 2X}$ in this case). In a previous paper with Kaisa and Maksym, we also proved a weak version

$\displaystyle \sup_{\alpha \in {\bf R}} \int_X^{2X} |\sum_{x \leq n \leq x+H} \lambda(n) e(-\alpha n)|\ dx = o(HX) \ \ \ \ \ (3)$

of (2) for any ${H}$ growing arbitrarily slowly with ${X}$ ; this is stronger than (1) (and is in fact proven by a variant of the method) but significantly weaker than (2), because in the latter the worst-case ${\alpha}$ is permitted to depend on the ${x}$ parameter, whereas in (3) ${\alpha}$ must remain independent of ${x}$ .

Unfortunately, the restriction ${H = X^\theta}$ is not strong enough to give applications to Chowla-type conjectures (one would need something more like ${H = \log^\theta X}$ for this). However, it can still be used to control some sums that had not previously been manageable. For instance, a quick application of the circle method lets one use the above theorem to derive the asymptotic

$\displaystyle \sum_{h \leq H} \sum_{n \leq X} \lambda(n) \Lambda(n+h) \Lambda(n+2h) = o( H X )$

whenever ${H = X^\theta}$ for a fixed ${\theta > 0}$ , where ${\Lambda}$ is the von Mangoldt function. Amusingly, the seemingly simpler question of establishing the expected asymptotic for

$\displaystyle \sum_{h \leq H} \sum_{n \leq X} \Lambda(n+h) \Lambda(n+2h)$

is only known in the range ${\theta \geq 1/6}$ (from the work of Zaccagnini). Thus we have a rare example of a number theory sum that becomes easier to control when one inserts a Liouville function!

We now give an informal description of the strategy of proof of the theorem (though for numerous technical reasons, the actual proof deviates in some respects from the description given here). If (2) failed, then for many values of ${x \in [X,2X]}$ we would have the lower bound

$\displaystyle |\sum_{x \leq n \leq x+H} \lambda(n) e(-\alpha_x n)| \gg 1$

for some frequency ${\alpha_x \in{\bf R}}$ . We informally describe this correlation between ${\lambda(n)}$ and ${e(\alpha_x n)}$ by writing

$\displaystyle \lambda(n) \approx e(\alpha_x n) \ \ \ \ \ (4)$

for ${n \in [x,x+H]}$ (informally, one should view this as asserting that ${\lambda(n)}$ “behaves like” a constant multiple of ${e(\alpha_x n)}$ ). For sake of discussion, suppose we have this relationship for all ${x \in [X,2X]}$ , not just many.

As mentioned before, the main difficulty here is to understand how ${\alpha_x}$ varies with ${x}$ . As it turns out, the multiplicativity properties of the Liouville function place a significant constraint on this dependence. Indeed, if we let ${p}$ be a fairly small prime (e.g. of size ${H^\varepsilon}$ for some ${\varepsilon>0}$ ), and use the identity ${\lambda(np) = \lambda(n) \lambda(p) = - \lambda(n)}$ for the Liouville function to conclude (at least heuristically) from (4) that

$\displaystyle \lambda(n) \approx e(\alpha_x n p)$

for ${n \in [x/p, x/p + H/p]}$ . (In practice, we will have this sort of claim for many primes ${p}$ rather than all primes ${p}$ , after using tools such as the Turán-Kubilius inequality, but we ignore this distinction for this informal argument.)

Now let ${x, y \in [X,2X]}$ and ${p,q \sim P}$ be primes comparable to some fixed range ${P = H^\varepsilon}$ such that

$\displaystyle x/p = y/q + O( H/P). \ \ \ \ \ (5)$

Then we have both

$\displaystyle \lambda(n) \approx e(\alpha_x n p)$

and

$\displaystyle \lambda(n) \approx e(\alpha_y n q)$

on essentially the same range of ${n}$ (two nearby intervals of length ${\sim H/P}$ ). This suggests that the frequencies ${p \alpha_x}$ and ${q \alpha_y}$ should be close to each other modulo ${1}$ , in particular one should expect the relationship

$\displaystyle p \alpha_x = q \alpha_y + O( \frac{P}{H} ) \hbox{ mod } 1. \ \ \ \ \ (6)$

Comparing this with (5) one is led to the expectation that ${\alpha_x}$ should depend inversely on ${x}$ in some sense (for instance one can check that

$\displaystyle \alpha_x = T/x \ \ \ \ \ (7)$

would solve (6) if ${T = O( X / H^2 )}$ ; by Taylor expansion, this would correspond to a global approximation of the form ${\lambda(n) \approx n^{iT}}$ ). One now has a problem of an additive combinatorial flavour (or of a “local to global” flavour), namely to leverage the relation (6) to obtain global control on ${\alpha_x}$ that resembles (7).

A key obstacle in solving (6) efficiently is the fact that one only knows that ${p \alpha_x}$ and ${q \alpha_y}$ are close modulo ${1}$ , rather than close on the real line. One can start resolving this problem by the Chinese remainder theorem, using the fact that we have the freedom to shift (say) ${\alpha_y}$ by an arbitrary integer. After doing so, one can arrange matters so that one in fact has the relationship

$\displaystyle p \alpha_x = q \alpha_y + O( \frac{P}{H} ) \hbox{ mod } p \ \ \ \ \ (8)$

whenever ${x,y \in [X,2X]}$ and ${p,q \sim P}$ obey (5). (This may force ${\alpha_q}$ to become extremely large, on the order of ${\prod_{p \sim P} p}$ , but this will not concern us.)

Now suppose that we have ${y,y' \in [X,2X]}$ and primes ${q,q' \sim P}$ such that

$\displaystyle y/q = y'/q' + O(H/P). \ \ \ \ \ (9)$

For every prime ${p \sim P}$ , we can find an ${x}$ such that ${x/p}$ is within ${O(H/P)}$ of both ${y/q}$ and ${y'/q'}$ . Applying (8) twice we obtain

$\displaystyle p \alpha_x = q \alpha_y + O( \frac{P}{H} ) \hbox{ mod } p$

and

$\displaystyle p \alpha_x = q' \alpha_{y'} + O( \frac{P}{H} ) \hbox{ mod } p$

and thus by the triangle inequality we have

$\displaystyle q \alpha_y = q' \alpha_{y'} + O( \frac{P}{H} ) \hbox{ mod } p$

for all ${p \sim P}$ ; hence by the Chinese remainder theorem

$\displaystyle q \alpha_y = q' \alpha_{y'} + O( \frac{P}{H} ) \hbox{ mod } \prod_{p \sim P} p.$

In practice, in the regime ${H = X^\theta}$ that we are considering, the modulus ${\prod_{p \sim P} p}$ is so huge we can effectively ignore it (in the spirit of the Lefschetz principle); so let us pretend that we in fact have

$\displaystyle q \alpha_y = q' \alpha_{y'} + O( \frac{P}{H} ) \ \ \ \ \ (10)$

whenever ${y,y' \in [X,2X]}$ and ${q,q' \sim P}$ obey (9).

Now let ${k}$ be an integer to be chosen later, and suppose we have primes ${p_1,\dots,p_k,q_1,\dots,q_k \sim P}$ such that the difference

$\displaystyle q = |p_1 \dots p_k - q_1 \dots q_k|$

is small but non-zero. If ${k}$ is chosen so that

$\displaystyle P^k \approx \frac{X}{H}$

(where one is somewhat loose about what ${\approx}$ means) then one can then find real numbers ${x_1,\dots,x_k \sim X}$ such that

$\displaystyle \frac{x_j}{p_j} = \frac{x_{j+1}}{q_j} + O( \frac{H}{P} )$

for ${j=1,\dots,k}$ , with the convention that ${x_{k+1} = x_1}$ . We then have

$\displaystyle p_j \alpha_{x_j} = q_j \alpha_{x_{j+1}} + O( \frac{P}{H} )$

which telescopes to

$\displaystyle p_1 \dots p_k \alpha_{x_1} = q_1 \dots q_k \alpha_{x_1} + O( \frac{P^k}{H} )$

and thus

$\displaystyle q \alpha_{x_1} = O( \frac{P^k}{H} )$

and hence

$\displaystyle \alpha_{x_1} = O( \frac{P^k}{H} ) \approx O( \frac{X}{H^2} ).$

In particular, for each ${x \sim X}$ , we expect to be able to write

$\displaystyle \alpha_x = \frac{T_x}{x} + O( \frac{1}{H} )$

for some ${T_x = O( \frac{X^2}{H^2} )}$ . This quantity ${T_x}$ can vary with ${x}$ ; but from (10) and a short calculation we see that

$\displaystyle T_y = T_{y'} + O( \frac{X}{H} )$

whenever ${y, y' \in [X,2X]}$ obey (9) for some ${q,q' \sim P}$ .

Now imagine a “graph” in which the vertices are elements ${y}$ of ${[X,2X]}$ , and two elements ${y,y'}$ are joined by an edge if (9) holds for some ${q,q' \sim P}$ . Because of exponential sum estimates on ${\sum_{q \sim P} q^{it}}$ , this graph turns out to essentially be an “expander” in the sense that any two vertices ${y,y' \in [X,2X]}$ can be connected (in multiple ways) by fairly short paths in this graph (if one allows one to modify one of ${y}$ or ${y'}$ by ${O(H)}$ ). As a consequence, we can assume that this quantity ${T_y}$ is essentially constant in ${y}$ (cf. the application of the ergodic theorem in this previous blog post), thus we now have

$\displaystyle \alpha_x = \frac{T}{x} + O(\frac{1}{H} )$

for most ${x \in [X,2X]}$ and some ${T = O(X^2/H^2)}$ . By Taylor expansion, this implies that

$\displaystyle \lambda(n) \approx n^{iT}$

on ${[x,x+H]}$ for most ${x}$ , thus

$\displaystyle \int_X^{2X} |\sum_{x \leq n \leq x+H} \lambda(n) n^{-iT}|\ dx \gg HX.$

But this can be shown to contradict the Matomäki-Radziwill theorem (because the multiplicative function ${n \mapsto \lambda(n) n^{-iT}}$ is known to be non-pretentious).

The structure of logarithmically averaged correlations of multiplicative functions, with applications to the Chowla and Elliott conjectures

9 August, 2017 in math.DS, math.NT, paper | Tags: Chowla conjecture, correspondence principle, Elliott conjecture, Joni Teravainen, Liouville function, multiplicative functions | by Terence Tao | 7 comments

Joni Teräväinen and I have just uploaded to the arXiv our paper “The structure of logarithmically averaged correlations of multiplicative functions, with applications to the Chowla and Elliott conjectures“, submitted to Duke Mathematical Journal. This paper builds upon my previous paper in which I introduced an “entropy decrement method” to prove the two-point (logarithmically averaged) cases of the Chowla and Elliott conjectures. A bit more specifically, I showed that

$\displaystyle \lim_{m \rightarrow \infty} \frac{1}{\log \omega_m} \sum_{x_m/\omega_m \leq n \leq x_m} \frac{g_0(n+h_0) g_1(n+h_1)}{n} = 0$

whenever ${1 \leq \omega_m \leq x_m}$ were sequences going to infinity, ${h_0,h_1}$ were distinct integers, and ${g_0,g_1: {\bf N} \rightarrow {\bf C}}$ were ${1}$ -bounded multiplicative functions which were non-pretentious in the sense that

$\displaystyle \liminf_{X \rightarrow \infty} \inf_{|t_j| \leq X} \sum_{p \leq X} \frac{1-\mathrm{Re}( g_j(p) \overline{\chi_j}(p) p^{it_j})}{p} = \infty \ \ \ \ \ (1)$

for all Dirichlet characters ${\chi_j}$ and for ${j=0,1}$ . Thus, for instance, one had the logarithmically averaged two-point Chowla conjecture

$\displaystyle \sum_{n \leq x} \frac{\lambda(n) \lambda(n+h)}{n} = o(\log x)$

for fixed any non-zero ${h}$ , where ${\lambda}$ was the Liouville function.

One would certainly like to extend these results to higher order correlations than the two-point correlations. This looks to be difficult (though perhaps not completely impossible if one allows for logarithmic averaging): in a previous paper I showed that achieving this in the context of the Liouville function would be equivalent to resolving the logarithmically averaged Sarnak conjecture, as well as establishing logarithmically averaged local Gowers uniformity of the Liouville function. However, in this paper we are able to avoid having to resolve these difficult conjectures to obtain partial results towards the (logarithmically averaged) Chowla and Elliott conjecture. For the Chowla conjecture, we can obtain all odd order correlations, in that

$\displaystyle \sum_{n \leq x} \frac{\lambda(n+h_1) \dots \lambda(n+h_k)}{n} = o(\log x) \ \ \ \ \ (2)$

for all odd ${k}$ and all integers ${h_1,\dots,h_k}$ (which, in the odd order case, are no longer required to be distinct). (Superficially, this looks like we have resolved “half of the cases” of the logarithmically averaged Chowla conjecture; but it seems the odd order correlations are significantly easier than the even order ones. For instance, because of the Katai-Bourgain-Sarnak-Ziegler criterion, one can basically deduce the odd order cases of (2) from the even order cases (after allowing for some dilations in the argument ${n}$ ).

For the more general Elliott conjecture, we can show that

$\displaystyle \lim_{m \rightarrow \infty} \frac{1}{\log \omega_m} \sum_{x_m/\omega_m \leq n \leq x_m} \frac{g_1(n+h_1) \dots g_k(n+h_k)}{n} = 0$

for any ${k}$ , any integers ${h_1,\dots,h_k}$ and any bounded multiplicative functions ${g_1,\dots,g_k}$ , unless the product ${g_1 \dots g_k}$ weakly pretends to be a Dirichlet character ${\chi}$ in the sense that

$\displaystyle \sum_{p \leq X} \frac{1 - \hbox{Re}( g_1 \dots g_k(p) \overline{\chi}(p)}{p} = o(\log\log X).$

This can be seen to imply (2) as a special case. Even when ${g_1,\dots,g_k}$ does pretend to be a Dirichlet character ${\chi}$ , we can still say something: if the limits

$\displaystyle f(a) := \lim_{m \rightarrow \infty} \frac{1}{\log \omega_m} \sum_{x_m/\omega_m \leq n \leq x_m} \frac{g_1(n+ah_1) \dots g_k(n+ah_k)}{n}$

exist for each ${a \in {\bf Z}}$ (which can be guaranteed if we pass to a suitable subsequence), then ${f}$ is the uniform limit of periodic functions ${f_i}$ , each of which is ${\chi}$ –isotypic in the sense that ${f_i(ab) = f_i(a) \chi(b)}$ whenever ${a,b}$ are integers with ${b}$ coprime to the periods of ${\chi}$ and ${f_i}$ . This does not pin down the value of any single correlation ${f(a)}$ , but does put significant constraints on how these correlations may vary with ${a}$ .

Among other things, this allows us to show that all ${16}$ possible length four sign patterns ${(\lambda(n+1),\dots,\lambda(n+4)) \in \{-1,+1\}^4}$ of the Liouville function occur with positive density, and all ${65}$ possible length four sign patterns ${(\mu(n+1),\dots,\mu(n+4)) \in \{-1,0,+1\}^4 \backslash \{-1,+1\}^4}$ occur with the conjectured logarithmic density. (In a previous paper with Matomaki and Radziwill, we obtained comparable results for length three patterns of Liouville and length two patterns of Möbius.)

To describe the argument, let us focus for simplicity on the case of the Liouville correlations

$\displaystyle f(a) := \lim_{X \rightarrow \infty} \frac{1}{\log X} \sum_{n \leq X} \frac{\lambda(n) \lambda(n+a) \dots \lambda(n+(k-1)a)}{n}, \ \ \ \ \ (3)$

assuming for sake of discussion that all limits exist. (In the paper, we instead use the device of generalised limits, as discussed in this previous post.) The idea is to combine together two rather different ways to control this function ${f}$ . The first proceeds by the entropy decrement method mentioned earlier, which roughly speaking works as follows. Firstly, we pick a prime ${p}$ and observe that ${\lambda(pn)=-\lambda(n)}$ for any ${n}$ , which allows us to rewrite (3) as

$\displaystyle (-1)^k f(a) = \lim_{X \rightarrow \infty} \frac{1}{\log X}$

$\displaystyle \sum_{n \leq X} \frac{\lambda(pn) \lambda(pn+ap) \dots \lambda(pn+(k-1)ap)}{n}.$

Making the change of variables ${n' = pn}$ , we obtain

$\displaystyle (-1)^k f(a) = \lim_{X \rightarrow \infty} \frac{1}{\log X}$

$\displaystyle \sum_{n' \leq pX} \frac{\lambda(n') \lambda(n'+ap) \dots \lambda(n'+(k-1)ap)}{n'} p 1_{p|n'}.$

The difference between ${n' \leq pX}$ and ${n' \leq X}$ is negligible in the limit (here is where we crucially rely on the log-averaging), hence

$\displaystyle (-1)^k f(a) = \lim_{X \rightarrow \infty} \frac{1}{\log X} \sum_{n \leq X} \frac{\lambda(n) \lambda(n+ap) \dots \lambda(n+(k-1)ap)}{n} p 1_{p|n}$

and thus by (3) we have

$\displaystyle (-1)^k f(a) = f(ap) + \lim_{X \rightarrow \infty} \frac{1}{\log X}$

$\displaystyle \sum_{n \leq X} \frac{\lambda(n) \lambda(n+ap) \dots \lambda(n+(k-1)ap)}{n} (p 1_{p|n}-1).$

The entropy decrement argument can be used to show that the latter limit is small for most ${p}$ (roughly speaking, this is because the factors ${p 1_{p|n}-1}$ behave like independent random variables as ${p}$ varies, so that concentration of measure results such as Hoeffding’s inequality can apply, after using entropy inequalities to decouple somewhat these random variables from the ${\lambda}$ factors). We thus obtain the approximate isotopy property

$\displaystyle (-1)^k f(a) \approx f(ap) \ \ \ \ \ (4)$

for most ${a}$ and ${p}$ .

On the other hand, by the Furstenberg correspondence principle (as discussed in these previous posts), it is possible to express ${f(a)}$ as a multiple correlation

$\displaystyle f(a) = \int_X g(x) g(T^a x) \dots g(T^{(k-1)a} x)\ d\mu(x)$

for some probability space ${(X,\mu)}$ equipped with a measure-preserving invertible map ${T: X \rightarrow X}$ . Using results of Bergelson-Host-Kra, Leibman, and Le, this allows us to obtain a decomposition of the form

$\displaystyle f(a) = f_1(a) + f_2(a) \ \ \ \ \ (5)$

where ${f_1}$ is a nilsequence, and ${f_2}$ goes to zero in density (even along the primes, or constant multiples of the primes). The original work of Bergelson-Host-Kra required ergodicity on ${X}$ , which is very definitely a hypothesis that is not available here; however, the later work of Leibman removed this hypothesis, and the work of Le refined the control on ${f_1}$ so that one still has good control when restricting to primes, or constant multiples of primes.

Ignoring the small error ${f_2(a)}$ , we can now combine (5) to conclude that

$\displaystyle f(a) \approx (-1)^k f_1(ap).$

Using the equidistribution theory of nilsequences (as developed in this previous paper of Ben Green and myself), one can break up ${f_1}$ further into a periodic piece ${f_0}$ and an “irrational” or “minor arc” piece ${f_3}$ . The contribution of the minor arc piece ${f_3}$ can be shown to mostly cancel itself out after dilating by primes ${p}$ and averaging, thanks to Vinogradov-type bilinear sum estimates (transferred to the primes). So we end up with

$\displaystyle f(a) \approx (-1)^k f_0(ap),$

which already shows (heuristically, at least) the claim that ${f}$ can be approximated by periodic functions ${f_0}$ which are isotopic in the sense that

$\displaystyle f_0(a) \approx (-1)^k f_0(ap).$

But if ${k}$ is odd, one can use Dirichlet’s theorem on primes in arithmetic progressions to restrict to primes ${p}$ that are ${1}$ modulo the period of ${f_0}$ , and conclude now that ${f_0}$ vanishes identically, which (heuristically, at least) gives (2).

The same sort of argument works to give the more general bounds on correlations of bounded multiplicative functions. But for the specific task of proving (2), we initially used a slightly different argument that avoids using the ergodic theory machinery of Bergelson-Host-Kra, Leibman, and Le, but replaces it instead with the Gowers uniformity norm theory used to count linear equations in primes. Basically, by averaging (4) in ${p}$ using the “ ${W}$ -trick”, as well as known facts about the Gowers uniformity of the von Mangoldt function, one can obtain an approximation of the form

$\displaystyle (-1)^k f(a) \approx {\bf E}_{b: (b,W)=1} f(ab)$

where ${b}$ ranges over a large range of integers coprime to some primorial ${W = \prod_{p \leq w} p}$ . On the other hand, by iterating (4) we have

$\displaystyle f(a) \approx f(apq)$

for most semiprimes ${pq}$ , and by again averaging over semiprimes one can obtain an approximation of the form

$\displaystyle f(a) \approx {\bf E}_{b: (b,W)=1} f(ab).$

For ${k}$ odd, one can combine the two approximations to conclude that ${f(a)=0}$ . (This argument is not given in the current paper, but we plan to detail it in a subsequent one.)

Furstenberg limits of the Liouville function

5 March, 2017 in expository, math.NT | Tags: Chowla conjecture, correspondence principle, Liouville function, randomness | by Terence Tao | 11 comments

Given a function ${f: {\bf N} \rightarrow \{-1,+1\}}$ on the natural numbers taking values in ${+1, -1}$ , one can invoke the Furstenberg correspondence principle to locate a measure preserving system ${T \circlearrowright (X, \mu)}$ – a probability space ${(X,\mu)}$ together with a measure-preserving shift ${T: X \rightarrow X}$ (or equivalently, a measure-preserving ${{\bf Z}}$ -action on ${(X,\mu)}$ ) – together with a measurable function (or “observable”) ${F: X \rightarrow \{-1,+1\}}$ that has essentially the same statistics as ${f}$ in the sense that

$\displaystyle \lim \inf_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N f(n+h_1) \dots f(n+h_k)$

$\displaystyle \leq \int_X F(T^{h_1} x) \dots F(T^{h_k} x)\ d\mu(x)$

$\displaystyle \leq \lim \sup_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N f(n+h_1) \dots f(n+h_k)$

for any integers ${h_1,\dots,h_k}$ . In particular, one has

$\displaystyle \int_X F(T^{h_1} x) \dots F(T^{h_k} x)\ d\mu(x) = \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N f(n+h_1) \dots f(n+h_k) \ \ \ \ \ (1)$

whenever the limit on the right-hand side exists. We will refer to the system ${T \circlearrowright (X,\mu)}$ together with the designated function ${F}$ as a Furstenberg limit ot the sequence ${f}$ . These Furstenberg limits capture some, but not all, of the asymptotic behaviour of ${f}$ ; roughly speaking, they control the typical “local” behaviour of ${f}$ , involving correlations such as ${\frac{1}{N} \sum_{n=1}^N f(n+h_1) \dots f(n+h_k)}$ in the regime where ${h_1,\dots,h_k}$ are much smaller than ${N}$ . However, the control on error terms here is usually only qualitative at best, and one usually does not obtain non-trivial control on correlations in which the ${h_1,\dots,h_k}$ are allowed to grow at some significant rate with ${N}$ (e.g. like some power ${N^\theta}$ of ${N}$ ).

The correspondence principle is discussed in these previous blog posts. One way to establish the principle is by introducing a Banach limit ${p\!-\!\lim: \ell^\infty({\bf N}) \rightarrow {\bf R}}$ that extends the usual limit functional on the subspace of ${\ell^\infty({\bf N})}$ consisting of convergent sequences while still having operator norm one. Such functionals cannot be constructed explicitly, but can be proven to exist (non-constructively and non-uniquely) using the Hahn-Banach theorem; one can also use a non-principal ultrafilter here if desired. One can then seek to construct a system ${T \circlearrowright (X,\mu)}$ and a measurable function ${F: X \rightarrow \{-1,+1\}}$ for which one has the statistics

$\displaystyle \int_X F(T^{h_1} x) \dots F(T^{h_k} x)\ d\mu(x) = p\!-\!\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N f(n+h_1) \dots f(n+h_k) \ \ \ \ \ (2)$

for all ${h_1,\dots,h_k}$ . One can explicitly construct such a system as follows. One can take ${X}$ to be the Cantor space ${\{-1,+1\}^{\bf Z}}$ with the product ${\sigma}$ -algebra and the shift

$\displaystyle T ( (x_n)_{n \in {\bf Z}} ) := (x_{n+1})_{n \in {\bf Z}}$

with the function ${F: X \rightarrow \{-1,+1\}}$ being the coordinate function at zero:

$\displaystyle F( (x_n)_{n \in {\bf Z}} ) := x_0$

(so in particular ${F( T^h (x_n)_{n \in {\bf Z}} ) = x_h}$ for any ${h \in {\bf Z}}$ ). The only thing remaining is to construct the invariant measure ${\mu}$ . In order to be consistent with (2), one must have

$\displaystyle \mu( \{ (x_n)_{n \in {\bf Z}}: x_{h_j} = \epsilon_j \forall 1 \leq j \leq k \} )$

$\displaystyle = p\!-\!\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N 1_{f(n+h_1)=\epsilon_1} \dots 1_{f(n+h_k)=\epsilon_k}$

for any distinct integers ${h_1,\dots,h_k}$ and signs ${\epsilon_1,\dots,\epsilon_k}$ . One can check that this defines a premeasure on the Boolean algebra of ${\{-1,+1\}^{\bf Z}}$ defined by cylinder sets, and the existence of ${\mu}$ then follows from the Hahn-Kolmogorov extension theorem (or the closely related Kolmogorov extension theorem). One can then check that the correspondence (2) holds, and that ${\mu}$ is translation-invariant; the latter comes from the translation invariance of the (Banach-)Césaro averaging operation ${f \mapsto p\!-\!\lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N f(n)}$ . A variant of this construction shows that the Furstenberg limit is unique up to equivalence if and only if all the limits appearing in (1) actually exist.

One can obtain a slightly tighter correspondence by using a smoother average than the Césaro average. For instance, one can use the logarithmic Césaro averages ${\lim_{N \rightarrow \infty} \frac{1}{\log N}\sum_{n=1}^N \frac{f(n)}{n}}$ in place of the Césaro average ${\sum_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N f(n)}$ , thus one replaces (2) by

$\displaystyle \int_X F(T^{h_1} x) \dots F(T^{h_k} x)\ d\mu(x)$

$\displaystyle = p\!-\!\lim_{N \rightarrow \infty} \frac{1}{\log N} \sum_{n=1}^N \frac{f(n+h_1) \dots f(n+h_k)}{n}.$

Whenever the Césaro average of a bounded sequence ${f: {\bf N} \rightarrow {\bf R}}$ exists, then the logarithmic Césaro average exists and is equal to the Césaro average. Thus, a Furstenberg limit constructed using logarithmic Banach-Césaro averaging still obeys (1) for all ${h_1,\dots,h_k}$ when the right-hand side limit exists, but also obeys the more general assertion

$\displaystyle \int_X F(T^{h_1} x) \dots F(T^{h_k} x)\ d\mu(x)$

$\displaystyle = \lim_{N \rightarrow \infty} \frac{1}{\log N} \sum_{n=1}^N \frac{f(n+h_1) \dots f(n+h_k)}{n}$

whenever the limit of the right-hand side exists.

In a recent paper of Frantizinakis, the Furstenberg limits of the Liouville function ${\lambda}$ (with logarithmic averaging) were studied. Some (but not all) of the known facts and conjectures about the Liouville function can be interpreted in the Furstenberg limit. For instance, in a recent breakthrough result of Matomaki and Radziwill (discussed previously here), it was shown that the Liouville function exhibited cancellation on short intervals in the sense that

$\displaystyle \lim_{H \rightarrow \infty} \limsup_{X \rightarrow \infty} \frac{1}{X} \int_X^{2X} \frac{1}{H} |\sum_{x \leq n \leq x+H} \lambda(n)|\ dx = 0.$

In terms of Furstenberg limits of the Liouville function, this assertion is equivalent to the assertion that

$\displaystyle \lim_{H \rightarrow \infty} \int_X |\frac{1}{H} \sum_{h=1}^H F(T^h x)|\ d\mu(x) = 0$

for all Furstenberg limits ${T \circlearrowright (X,\mu), F}$ of Liouville (including those without logarithmic averaging). Invoking the mean ergodic theorem (discussed in this previous post), this assertion is in turn equivalent to the observable ${F}$ that corresponds to the Liouville function being orthogonal to the invariant factor ${L^\infty(X,\mu)^{\bf Z} = \{ g \in L^\infty(X,\mu): g \circ T = g \}}$ of ${X}$ ; equivalently, the first Gowers-Host-Kra seminorm ${\|F\|_{U^1(X)}}$ of ${F}$ (as defined for instance in this previous post) vanishes. The Chowla conjecture, which asserts that

$\displaystyle \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N \lambda(n+h_1) \dots \lambda(n+h_k) = 0$

for all distinct integers ${h_1,\dots,h_k}$ , is equivalent to the assertion that all the Furstenberg limits of Liouville are equivalent to the Bernoulli system ( ${\{-1,+1\}^{\bf Z}}$ with the product measure arising from the uniform distribution on ${\{-1,+1\}}$ , with the shift ${T}$ and observable ${F}$ as before). Similarly, the logarithmically averaged Chowla conjecture

$\displaystyle \lim_{N \rightarrow \infty} \frac{1}{\log N} \sum_{n=1}^N \frac{\lambda(n+h_1) \dots \lambda(n+h_k)}{n} = 0$

is equivalent to the assertion that all the Furstenberg limits of Liouville with logarithmic averaging are equivalent to the Bernoulli system. Recently, I was able to prove the two-point version

$\displaystyle \lim_{N \rightarrow \infty} \frac{1}{\log N} \sum_{n=1}^N \frac{\lambda(n) \lambda(n+h)}{n} = 0 \ \ \ \ \ (3)$

of the logarithmically averaged Chowla conjecture, for any non-zero integer ${h}$ ; this is equivalent to the perfect strong mixing property

$\displaystyle \int_X F(x) F(T^h x)\ d\mu(x) = 0$

for any Furstenberg limit of Liouville with logarithmic averaging, and any ${h \neq 0}$ .

The situation is more delicate with regards to the Sarnak conjecture, which is equivalent to the assertion that

$\displaystyle \lim_{N \rightarrow \infty} \frac{1}{N} \sum_{n=1}^N \lambda(n) f(n) = 0$

for any zero-entropy sequence ${f: {\bf N} \rightarrow {\bf R}}$ (see this previous blog post for more discussion). Morally speaking, this conjecture should be equivalent to the assertion that any Furstenberg limit of Liouville is disjoint from any zero entropy system, but I was not able to formally establish an implication in either direction due to some technical issues regarding the fact that the Furstenberg limit does not directly control long-range correlations, only short-range ones. (There are however ergodic theoretic interpretations of the Sarnak conjecture that involve the notion of generic points; see this paper of El Abdalaoui, Lemancyk, and de la Rue.) But the situation is currently better with the logarithmically averaged Sarnak conjecture

$\displaystyle \lim_{N \rightarrow \infty} \frac{1}{\log N} \sum_{n=1}^N \frac{\lambda(n) f(n)}{n} = 0,$

as I was able to show that this conjecture was equivalent to the logarithmically averaged Chowla conjecture, and hence to all Furstenberg limits of Liouville with logarithmic averaging being Bernoulli; I also showed the conjecture was equivalent to local Gowers uniformity of the Liouville function, which is in turn equivalent to the function ${F}$ having all Gowers-Host-Kra seminorms vanishing in every Furstenberg limit with logarithmic averaging. In this recent paper of Frantzikinakis, this analysis was taken further, showing that the logarithmically averaged Chowla and Sarnak conjectures were in fact equivalent to the much milder seeming assertion that all Furstenberg limits with logarithmic averaging were ergodic.

Actually, the logarithmically averaged Furstenberg limits have more structure than just a ${{\bf Z}}$ -action on a measure preserving system ${(X,\mu)}$ with a single observable ${F}$ . Let ${Aff_+({\bf Z})}$ denote the semigroup of affine maps ${n \mapsto an+b}$ on the integers with ${a,b \in {\bf Z}}$ and ${a}$ positive. Also, let ${\hat {\bf Z}}$ denote the profinite integers (the inverse limit of the cyclic groups ${{\bf Z}/q{\bf Z}}$ ). Observe that ${Aff_+({\bf Z})}$ acts on ${\hat {\bf Z}}$ by taking the inverse limit of the obvious actions of ${Aff_+({\bf Z})}$ on ${{\bf Z}/q{\bf Z}}$ .

Proposition 1 (Enriched logarithmically averaged Furstenberg limit of Liouville) Let ${p\!-\!\lim}$ be a Banach limit. Then there exists a probability space ${(X,\mu)}$ with an action ${\phi \mapsto T^\phi}$ of the affine semigroup ${Aff_+({\bf Z})}$ , as well as measurable functions ${F: X \rightarrow \{-1,+1\}}$ and ${M: X \rightarrow \hat {\bf Z}}$ , with the following properties:

(i) (Affine Furstenberg limit) For any ${\phi_1,\dots,\phi_k \in Aff_+({\bf Z})}$ , and any congruence class ${a\ (q)}$ , one has
$\displaystyle p\!-\!\lim_{N \rightarrow \infty} \frac{1}{\log N} \sum_{n=1}^N \frac{\lambda(\phi_1(n)) \dots \lambda(\phi_k(n)) 1_{n = a\ (q)}}{n}$

$\displaystyle = \int_X F( T^{\phi_1}(x) ) \dots F( T^{\phi_k}(x) ) 1_{M(x) = a\ (q)}\ d\mu(x).$

(ii) (Equivariance of ${M}$ ) For any ${\phi \in Aff_+({\bf Z})}$ , one has
$\displaystyle M( T^\phi(x) ) = \phi( M(x) )$

for ${\mu}$ -almost every ${x \in X}$ .

(iii) (Multiplicativity at fixed primes) For any prime ${p}$ , one has
$\displaystyle F( T^{p\cdot} x ) = - F(x)$

for ${\mu}$ -almost every ${x \in X}$ , where ${p \cdot \in Aff_+({\bf Z})}$ is the dilation map ${n \mapsto pn}$ .

(iv) (Measure pushforward) If ${\phi \in Aff_+({\bf Z})}$ is of the form ${\phi(n) = an+b}$ and ${S_\phi \subset X}$ is the set ${S_\phi = \{ x \in X: M(x) \in \phi(\hat {\bf Z}) \}}$ , then the pushforward ${T^\phi_* \mu}$ of ${\mu}$ by ${\phi}$ is equal to ${a \mu\downharpoonright_{S_\phi}}$ , that is to say one has
$\displaystyle \mu( (T^\phi)^{-1}(E) ) = a \mu( E \cap S_\phi )$

for every measurable ${E \subset X}$ .

Note that ${{\bf Z}}$ can be viewed as the subgroup of ${Aff_+({\bf Z})}$ consisting of the translations ${n \mapsto n + b}$ . If one only keeps the ${{\bf Z}}$ -portion of the ${Aff_+({\bf Z})}$ action and forgets the rest (as well as the function ${M}$ ) then the action becomes measure-preserving, and we recover an ordinary Furstenberg limit with logarithmic averaging. However, the additional structure here can be quite useful; for instance, one can transfer the proof of (3) to this setting, which we sketch below the fold, after proving the proposition.

The observable ${M}$ , roughly speaking, means that points ${x}$ in the Furstenberg limit ${X}$ constructed by this proposition are still “virtual integers” in the sense that one can meaningfully compute the residue class of ${x}$ modulo any natural number modulus ${q}$ , by first applying ${M}$ and then reducing mod ${q}$ . The action of ${Aff_+({\bf Z})}$ means that one can also meaningfully multiply ${x}$ by any natural number, and translate it by any integer. As with other applications of the correspondence principle, the main advantage of moving to this more “virtual” setting is that one now acquires a probability measure ${\mu}$ , so that the tools of ergodic theory can be readily applied.

Read the rest of this entry »

Special cases of Shannon entropy

1 March, 2017 in expository, math.IT, math.NT | Tags: Liouville function, randomness, Shannon entropy | by Terence Tao | 24 comments

Given a random variable ${X}$ that takes on only finitely many values, we can define its Shannon entropy by the formula

$\displaystyle H(X) := \sum_x \mathbf{P}(X=x) \log \frac{1}{\mathbf{P}(X=x)}$

with the convention that ${0 \log \frac{1}{0} = 0}$ . (In some texts, one uses the logarithm to base ${2}$ rather than the natural logarithm, but the choice of base will not be relevant for this discussion.) This is clearly a nonnegative quantity. Given two random variables ${X,Y}$ taking on finitely many values, the joint variable ${(X,Y)}$ is also a random variable taking on finitely many values, and also has an entropy ${H(X,Y)}$ . It obeys the Shannon inequalities

$\displaystyle H(X), H(Y) \leq H(X,Y) \leq H(X) + H(Y)$

so we can define some further nonnegative quantities, the mutual information

$\displaystyle I(X:Y) := H(X) + H(Y) - H(X,Y)$

and the conditional entropies

$\displaystyle H(X|Y) := H(X,Y) - H(Y); \quad H(Y|X) := H(X,Y) - H(X).$

More generally, given three random variables ${X,Y,Z}$ , one can define the conditional mutual information

$\displaystyle I(X:Y|Z) := H(X|Z) + H(Y|Z) - H(X,Y|Z)$

and the final of the Shannon entropy inequalities asserts that this quantity is also non-negative.

The mutual information ${I(X:Y)}$ is a measure of the extent to which ${X}$ and ${Y}$ fail to be independent; indeed, it is not difficult to show that ${I(X:Y)}$ vanishes if and only if ${X}$ and ${Y}$ are independent. Similarly, ${I(X:Y|Z)}$ vanishes if and only if ${X}$ and ${Y}$ are conditionally independent relative to ${Z}$ . At the other extreme, ${H(X|Y)}$ is a measure of the extent to which ${X}$ fails to depend on ${Y}$ ; indeed, it is not difficult to show that ${H(X|Y)=0}$ if and only if ${X}$ is determined by ${Y}$ in the sense that there is a deterministic function ${f}$ such that ${X = f(Y)}$ . In a related vein, if ${X}$ and ${X'}$ are equivalent in the sense that there are deterministic functional relationships ${X = f(X')}$ , ${X' = g(X)}$ between the two variables, then ${X}$ is interchangeable with ${X'}$ for the purposes of computing the above quantities, thus for instance ${H(X) = H(X')}$ , ${H(X,Y) = H(X',Y)}$ , ${I(X:Y) = I(X':Y)}$ , ${I(X:Y|Z) = I(X':Y|Z)}$ , etc..

One can get some initial intuition for these information-theoretic quantities by specialising to a simple situation in which all the random variables ${X}$ being considered come from restricting a single random (and uniformly distributed) boolean function ${F: \Omega \rightarrow \{0,1\}}$ on a given finite domain ${\Omega}$ to some subset ${A}$ of ${\Omega}$ :

$\displaystyle X = F \downharpoonright_A.$

In this case, ${X}$ has the law of a random uniformly distributed boolean function from ${A}$ to ${\{0,1\}}$ , and the entropy here can be easily computed to be ${|A| \log 2}$ , where ${|A|}$ denotes the cardinality of ${A}$ . If ${X}$ is the restriction of ${F}$ to ${A}$ , and ${Y}$ is the restriction of ${F}$ to ${B}$ , then the joint variable ${(X,Y)}$ is equivalent to the restriction of ${F}$ to ${A \cup B}$ . If one discards the normalisation factor ${\log 2}$ , one then obtains the following dictionary between entropy and the combinatorics of finite sets:

Random variables ${X,Y,Z}$	Finite sets ${A,B,C}$
Entropy ${H(X)}$	Cardinality ${\|A\|}$
Joint variable ${(X,Y)}$	Union ${A \cup B}$
Mutual information ${I(X:Y)}$	Intersection cardinality ${\|A \cap B\|}$
Conditional entropy ${H(X\|Y)}$	Set difference cardinality ${\|A \backslash B\|}$
Conditional mutual information ${I(X:Y\|Z)}$	${\|(A \cap B) \backslash C\|}$
${X, Y}$ independent	${A, B}$ disjoint
${X}$ determined by ${Y}$	${A}$ a subset of ${B}$
${X,Y}$ conditionally independent relative to ${Z}$	${A \cap B \subset C}$

Every (linear) inequality or identity about entropy (and related quantities, such as mutual information) then specialises to a combinatorial inequality or identity about finite sets that is easily verified. For instance, the Shannon inequality ${H(X,Y) \leq H(X)+H(Y)}$ becomes the union bound ${|A \cup B| \leq |A| + |B|}$ , and the definition of mutual information becomes the inclusion-exclusion formula

$\displaystyle |A \cap B| = |A| + |B| - |A \cup B|.$

For a more advanced example, consider the data processing inequality that asserts that if ${X, Z}$ are conditionally independent relative to ${Y}$ , then ${I(X:Z) \leq I(X:Y)}$ . Specialising to sets, this now says that if ${A, C}$ are disjoint outside of ${B}$ , then ${|A \cap C| \leq |A \cap B|}$ ; this can be made apparent by considering the corresponding Venn diagram. This dictionary also suggests how to prove the data processing inequality using the existing Shannon inequalities. Firstly, if ${A}$ and ${C}$ are not necessarily disjoint outside of ${B}$ , then a consideration of Venn diagrams gives the more general inequality

$\displaystyle |A \cap C| \leq |A \cap B| + |(A \cap C) \backslash B|$

and a further inspection of the diagram then reveals the more precise identity

$\displaystyle |A \cap C| + |(A \cap B) \backslash C| = |A \cap B| + |(A \cap C) \backslash B|.$

Using the dictionary in the reverse direction, one is then led to conjecture the identity

$\displaystyle I( X : Z ) + I( X : Y | Z ) = I( X : Y ) + I( X : Z | Y )$

which (together with non-negativity of conditional mutual information) implies the data processing inequality, and this identity is in turn easily established from the definition of mutual information.

On the other hand, not every assertion about cardinalities of sets generalises to entropies of random variables that are not arising from restricting random boolean functions to sets. For instance, a basic property of sets is that disjointness from a given set ${C}$ is preserved by unions:

$\displaystyle A \cap C = B \cap C = \emptyset \implies (A \cup B) \cap C = \emptyset.$

Indeed, one has the union bound

$\displaystyle |(A \cup B) \cap C| \leq |A \cap C| + |B \cap C|. \ \ \ \ \ (1)$

Applying the dictionary in the reverse direction, one might now conjecture that if ${X}$ was independent of ${Z}$ and ${Y}$ was independent of ${Z}$ , then ${(X,Y)}$ should also be independent of ${Z}$ , and furthermore that

$\displaystyle I(X,Y:Z) \leq I(X:Z) + I(Y:Z)$

but these statements are well known to be false (for reasons related to pairwise independence of random variables being strictly weaker than joint independence). For a concrete counterexample, one can take ${X, Y \in {\bf F}_2}$ to be independent, uniformly distributed random elements of the finite field ${{\bf F}_2}$ of two elements, and take ${Z := X+Y}$ to be the sum of these two field elements. One can easily check that each of ${X}$ and ${Y}$ is separately independent of ${Z}$ , but the joint variable ${(X,Y)}$ determines ${Z}$ and thus is not independent of ${Z}$ .

From the inclusion-exclusion identities

$\displaystyle |A \cap C| = |A| + |C| - |A \cup C|$

$\displaystyle |B \cap C| = |B| + |C| - |B \cup C|$

$\displaystyle |(A \cup B) \cap C| = |A \cup B| + |C| - |A \cup B \cup C|$

$\displaystyle |A \cap B \cap C| = |A| + |B| + |C| - |A \cup B| - |B \cup C| - |A \cup C|$

$\displaystyle + |A \cup B \cup C|$

one can check that (1) is equivalent to the trivial lower bound ${|A \cap B \cap C| \geq 0}$ . The basic issue here is that in the dictionary between entropy and combinatorics, there is no satisfactory entropy analogue of the notion of a triple intersection ${A \cap B \cap C}$ . (Even the double intersection ${A \cap B}$ only exists information theoretically in a “virtual” sense; the mutual information ${I(X:Y)}$ allows one to “compute the entropy” of this “intersection”, but does not actually describe this intersection itself as a random variable.)

However, this issue only arises with three or more variables; it is not too difficult to show that the only linear equalities and inequalities that are necessarily obeyed by the information-theoretic quantities ${H(X), H(Y), H(X,Y), I(X:Y), H(X|Y), H(Y|X)}$ associated to just two variables ${X,Y}$ are those that are also necessarily obeyed by their combinatorial analogues ${|A|, |B|, |A \cup B|, |A \cap B|, |A \backslash B|, |B \backslash A|}$ . (See for instance the Venn diagram at the Wikipedia page for mutual information for a pictorial summation of this statement.)

One can work with a larger class of special cases of Shannon entropy by working with random linear functions rather than random boolean functions. Namely, let ${S}$ be some finite-dimensional vector space over a finite field ${{\mathbf F}}$ , and let ${f: S \rightarrow {\mathbf F}}$ be a random linear functional on ${S}$ , selected uniformly among all such functions. Every subspace ${U}$ of ${S}$ then gives rise to a random variable ${X = X_U: U \rightarrow {\mathbf F}}$ formed by restricting ${f}$ to ${U}$ . This random variable is also distributed uniformly amongst all linear functions on ${U}$ , and its entropy can be easily computed to be ${\mathrm{dim}(U) \log |\mathbf{F}|}$ . Given two random variables ${X, Y}$ formed by restricting ${f}$ to ${U, V}$ respectively, the joint random variable ${(X,Y)}$ determines the random linear function ${f}$ on the union ${U \cup V}$ on the two spaces, and thus by linearity on the Minkowski sum ${U+V}$ as well; thus ${(X,Y)}$ is equivalent to the restriction of ${f}$ to ${U+V}$ . In particular, ${H(X,Y) = \mathrm{dim}(U+V) \log |\mathbf{F}|}$ . This implies that ${I(X:Y) = \mathrm{dim}(U \cap V) \log |\mathbf{F}|}$ and also ${H(X|Y) = \mathrm{dim}(\pi_V(U)) \log |\mathbf{F}|}$ , where ${\pi_V: S \rightarrow S/V}$ is the quotient map. After discarding the normalising constant ${\log |\mathbf{F}|}$ , this leads to the following dictionary between information theoretic quantities and linear algebra quantities, analogous to the previous dictionary:

Random variables ${X,Y,Z}$	Subspaces ${U,V,W}$
Entropy ${H(X)}$	Dimension ${\mathrm{dim}(U)}$
Joint variable ${(X,Y)}$	Sum ${U+V}$
Mutual information ${I(X:Y)}$	Dimension of intersection ${\mathrm{dim}(U \cap V)}$
Conditional entropy ${H(X\|Y)}$	Dimension of projection ${\mathrm{dim}(\pi_V(U))}$
Conditional mutual information ${I(X:Y\|Z)}$	${\mathrm{dim}(\pi_W(U) \cap \pi_W(V))}$
${X, Y}$ independent	${U, V}$ transverse ( ${U \cap V = \{0\}}$ )
${X}$ determined by ${Y}$	${U}$ a subspace of ${V}$
${X,Y}$ conditionally independent relative to ${Z}$	${\pi_W(U)}$ , ${\pi_W(V)}$ transverse.

The combinatorial dictionary can be regarded as a specialisation of the linear algebra dictionary, by taking ${S}$ to be the vector space ${\mathbf{F}_2^\Omega}$ over the finite field ${\mathbf{F}_2}$ of two elements, and only considering those subspaces ${U}$ that are coordinate subspaces ${U = {\bf F}_2^A}$ associated to various subsets ${A}$ of ${\Omega}$ .

As before, every linear inequality or equality that is valid for the information-theoretic quantities discussed above, is automatically valid for the linear algebra counterparts for subspaces of a vector space over a finite field by applying the above specialisation (and dividing out by the normalising factor of ${\log |\mathbf{F}|}$ ). In fact, the requirement that the field be finite can be removed by applying the compactness theorem from logic (or one of its relatives, such as Los’s theorem on ultraproducts, as done in this previous blog post).

The linear algebra model captures more of the features of Shannon entropy than the combinatorial model. For instance, in contrast to the combinatorial case, it is possible in the linear algebra setting to have subspaces ${U,V,W}$ such that ${U}$ and ${V}$ are separately transverse to ${W}$ , but their sum ${U+V}$ is not; for instance, in a two-dimensional vector space ${{\bf F}^2}$ , one can take ${U,V,W}$ to be the one-dimensional subspaces spanned by ${(0,1)}$ , ${(1,0)}$ , and ${(1,1)}$ respectively. Note that this is essentially the same counterexample from before (which took ${{\bf F}}$ to be the field of two elements). Indeed, one can show that any necessarily true linear inequality or equality involving the dimensions of three subspaces ${U,V,W}$ (as well as the various other quantities on the above table) will also be necessarily true when applied to the entropies of three discrete random variables ${X,Y,Z}$ (as well as the corresponding quantities on the above table).

However, the linear algebra model does not completely capture the subtleties of Shannon entropy once one works with four or more variables (or subspaces). This was first observed by Ingleton, who established the dimensional inequality

$\displaystyle \mathrm{dim}(U \cap V) \leq \mathrm{dim}(\pi_W(U) \cap \pi_W(V)) + \mathrm{dim}(\pi_X(U) \cap \pi_X(V)) + \mathrm{dim}(W \cap X) \ \ \ \ \ (2)$

for any subspaces ${U,V,W,X}$ . This is easiest to see when the three terms on the right-hand side vanish; then ${\pi_W(U), \pi_W(V)}$ are transverse, which implies that ${U\cap V \subset W}$ ; similarly ${U \cap V \subset X}$ . But ${W}$ and ${X}$ are transverse, and this clearly implies that ${U}$ and ${V}$ are themselves transverse. To prove the general case of Ingleton’s inequality, one can define ${Y := U \cap V}$ and use ${\mathrm{dim}(\pi_W(Y)) \leq \mathrm{dim}(\pi_W(U) \cap \pi_W(V))}$ (and similarly for ${X}$ instead of ${W}$ ) to reduce to establishing the inequality

$\displaystyle \mathrm{dim}(Y) \leq \mathrm{dim}(\pi_W(Y)) + \mathrm{dim}(\pi_X(Y)) + \mathrm{dim}(W \cap X) \ \ \ \ \ (3)$

which can be rearranged using ${\mathrm{dim}(\pi_W(Y)) = \mathrm{dim}(Y) - \mathrm{dim}(W) + \mathrm{dim}(\pi_Y(W))}$ (and similarly for ${X}$ instead of ${W}$ ) and ${\mathrm{dim}(W \cap X) = \mathrm{dim}(W) + \mathrm{dim}(X) - \mathrm{dim}(W + X)}$ as

$\displaystyle \mathrm{dim}(W + X ) \leq \mathrm{dim}(\pi_Y(W)) + \mathrm{dim}(\pi_Y(X)) + \mathrm{dim}(Y)$

but this is clear since ${\mathrm{dim}(W + X ) \leq \mathrm{dim}(\pi_Y(W) + \pi_Y(X)) + \mathrm{dim}(Y)}$ .

Returning to the entropy setting, the analogue

$\displaystyle H( V ) \leq H( V | Z ) + H(V | W ) + I(Z:W)$

of (3) is true (exercise!), but the analogue

$\displaystyle I(X:Y) \leq I(X:Y|Z) + I(X:Y|W) + I(Z:W) \ \ \ \ \ (4)$

of Ingleton’s inequality is false in general. Again, this is easiest to see when all the terms on the right-hand side vanish; then ${X,Y}$ are conditionally independent relative to ${Z}$ , and relative to ${W}$ , and ${Z}$ and ${W}$ are independent, and the claim (4) would then be asserting that ${X}$ and ${Y}$ are independent. While there is no linear counterexample to this statement, there are simple non-linear ones: for instance, one can take ${Z,W}$ to be independent uniform variables from ${\mathbf{F}_2}$ , and take ${X}$ and ${Y}$ to be (say) ${ZW}$ and ${(1-Z)(1-W)}$ respectively (thus ${X, Y}$ are the indicators of the events ${Z=W=1}$ and ${Z=W=0}$ respectively). Once one conditions on either ${Z}$ or ${W}$ , one of ${X,Y}$ has positive conditional entropy and the other has zero entropy, and so ${X, Y}$ are conditionally independent relative to either ${Z}$ or ${W}$ ; also, ${Z}$ or ${W}$ are independent of each other. But ${X}$ and ${Y}$ are not independent of each other (they cannot be simultaneously equal to ${1}$ ). Somehow, the feature of the linear algebra model that is not present in general is that in the linear algebra setting, every pair of subspaces ${U, V}$ has a well-defined intersection ${U \cap V}$ that is also a subspace, whereas for arbitrary random variables ${X, Y}$ , there does not necessarily exist the analogue of an intersection, namely a “common information” random variable ${V}$ that has the entropy of ${I(X:Y)}$ and is determined either by ${X}$ or by ${Y}$ .

I do not know if there is any simpler model of Shannon entropy that captures all the inequalities available for four variables. One significant complication is that there exist some information inequalities in this setting that are not of Shannon type, such as the Zhang-Yeung inequality

$\displaystyle I(X:Y) \leq 2 I(X:Y|Z) + I(X:Z|Y) + I(Y:Z|X)$

$\displaystyle + I(X:Y|W) + I(Z:W).$

One can however still use these simpler models of Shannon entropy to be able to guess arguments that would work for general random variables. An example of this comes from my paper on the logarithmically averaged Chowla conjecture, in which I showed among other things that

$\displaystyle |\sum_{n \leq x} \frac{\lambda(n) \lambda(n+1)}{n}| \leq \varepsilon x \ \ \ \ \ (5)$

whenever ${x}$ was sufficiently large depending on ${\varepsilon>0}$ , where ${\lambda}$ is the Liouville function. The information-theoretic part of the proof was as follows. Given some intermediate scale ${H}$ between ${1}$ and ${x}$ , one can form certain random variables ${X_H, Y_H}$ . The random variable ${X_H}$ is a sign pattern of the form ${(\lambda(n+1),\dots,\lambda(n+H))}$ where ${n}$ is a random number chosen from ${1}$ to ${x}$ (with logarithmic weighting). The random variable ${Y_H}$ was tuple ${(n \hbox{ mod } p)_{p \sim \varepsilon^2 H}}$ of reductions of ${n}$ to primes ${p}$ comparable to ${\varepsilon^2 H}$ . Roughly speaking, what was implicitly shown in the paper (after using the multiplicativity of ${\lambda}$ , the circle method, and the Matomaki-Radziwill theorem on short averages of multiplicative functions) is that if the inequality (5) fails, then there was a lower bound

$\displaystyle I( X_H : Y_H ) \gg \varepsilon^7 \frac{H}{\log H}$

on the mutual information between ${X_H}$ and ${Y_H}$ . From translation invariance, this also gives the more general lower bound

$\displaystyle I( X_{H_0,H} : Y_H ) \gg \varepsilon^7 \frac{H}{\log H} \ \ \ \ \ (6)$

for any ${H_0}$ , where ${X_{H_0,H}}$ denotes the shifted sign pattern ${(\lambda(n+H_0+1),\dots,\lambda(n+H_0+H))}$ . On the other hand, one had the entropy bounds

$\displaystyle H( X_{H_0,H} ), H(Y_H) \ll H$

and from concatenating sign patterns one could see that ${X_{H_0,H+H'}}$ is equivalent to the joint random variable ${(X_{H_0,H}, X_{H_0+H,H'})}$ for any ${H_0,H,H'}$ . Applying these facts and using an “entropy decrement” argument, I was able to obtain a contradiction once ${H}$ was allowed to become sufficiently large compared to ${\varepsilon}$ , but the bound was quite weak (coming ultimately from the unboundedness of ${\sum_{\log H_- \leq j \leq \log H_+} \frac{1}{j \log j}}$ as the interval ${[H_-,H_+]}$ of values of ${H}$ under consideration becomes large), something of the order of ${H \sim \exp\exp\exp(\varepsilon^{-7})}$ ; the quantity ${H}$ needs at various junctures to be less than a small power of ${\log x}$ , so the relationship between ${x}$ and ${\varepsilon}$ becomes essentially quadruple exponential in nature, ${x \sim \exp\exp\exp\exp(\varepsilon^{-7})}$ . The basic strategy was to observe that the lower bound (6) causes some slowdown in the growth rate ${H(X_{kH})/kH}$ of the mean entropy, in that this quantity decreased by ${\gg \frac{\varepsilon^7}{\log H}}$ as ${k}$ increased from ${1}$ to ${\log H}$ , basically by dividing ${X_{kH}}$ into ${k}$ components ${X_{jH, H}}$ , ${j=0,\dots,k-1}$ and observing from (6) each of these shares a bit of common information with the same variable ${Y_H}$ . This is relatively clear when one works in a set model, in which ${Y_H}$ is modeled by a set ${B_H}$ of size ${O(H)}$ , and ${X_{H_0,H}}$ is modeled by a set of the form

$\displaystyle X_{H_0,H} = \bigcup_{H_0 < h \leq H_0+H} A_h$

for various sets ${A_h}$ of size ${O(1)}$ (also there is some translation symmetry that maps ${A_h}$ to a shift ${A_{h+1}}$ while preserving all of the ${B_H}$ ).

However, on considering the set model recently, I realised that one can be a little more efficient by exploiting the fact (basically the Chinese remainder theorem) that the random variables ${Y_H}$ are basically jointly independent as ${H}$ ranges over dyadic values that are much smaller than ${\log x}$ , which in the set model corresponds to the ${B_H}$ all being disjoint. One can then establish a variant

$\displaystyle I( X_{H_0,H} : Y_H | (Y_{H'})_{H' < H}) \gg \varepsilon^7 \frac{H}{\log H} \ \ \ \ \ (7)$

of (6), which in the set model roughly speaking asserts that each ${B_H}$ claims a portion of the ${\bigcup_{H_0 < h \leq H_0+H} A_h}$ of cardinality ${\gg \varepsilon^7 \frac{H}{\log H}}$ that is not claimed by previous choices of ${B_H}$ . This leads to a more efficient contradiction (relying on the unboundedness of ${\sum_{\log H_- \leq j \leq \log H_+} \frac{1}{j}}$ rather than ${\sum_{\log H_- \leq j \leq \log H_+} \frac{1}{j \log j}}$ ) that looks like it removes one order of exponential growth, thus the relationship between ${x}$ and ${\varepsilon}$ is now ${x \sim \exp\exp\exp(\varepsilon^{-7})}$ . Returning to the entropy model, one can use (7) and Shannon inequalities to establish an inequality of the form

$\displaystyle \frac{1}{2H} H(X_{2H} | (Y_{H'})_{H' \leq 2H}) \leq \frac{1}{H} H(X_{H} | (Y_{H'})_{H' \leq H}) - \frac{c \varepsilon^7}{\log H}$

for a small constant ${c>0}$ , which on iterating and using the boundedness of ${\frac{1}{H} H(X_{H} | (Y_{H'})_{H' \leq H})}$ gives the claim. (A modification of this analysis, at least on the level of the back of the envelope calculation, suggests that the Matomaki-Radziwill theorem is needed only for ranges ${H}$ greater than ${\exp( (\log\log x)^{\varepsilon^{7}} )}$ or so, although at this range the theorem is not significantly simpler than the general case).

A conjectural local Fourier-uniformity of the Liouville function

2 December, 2015 in expository, math.NT, question | Tags: Chowla conjecture, Gowers uniformity norm, Liouville function | by Terence Tao | 21 comments

Let ${\lambda}$ denote the Liouville function. The prime number theorem is equivalent to the estimate

$\displaystyle \sum_{n \leq x} \lambda(n) = o(x)$

as ${x \rightarrow \infty}$ , that is to say that ${\lambda}$ exhibits cancellation on large intervals such as ${[1,x]}$ . This result can be improved to give cancellation on shorter intervals. For instance, using the known zero density estimates for the Riemann zeta function, one can establish that

$\displaystyle \int_X^{2X} |\sum_{x \leq n \leq x+H} \lambda(n)|\ dx = o( HX ) \ \ \ \ \ (1)$

as ${X \rightarrow \infty}$ if ${X^{1/6+\varepsilon} \leq H \leq X}$ for some fixed ${\varepsilon>0}$ ; I believe this result is due to Ramachandra (see also Exercise 21 of this previous blog post), and in fact one could obtain a better error term on the right-hand side that for instance gained an arbitrary power of ${\log X}$ . On the Riemann hypothesis (or the weaker density hypothesis), it was known that the ${X^{1/6+\varepsilon}}$ could be lowered to ${X^\varepsilon}$ .

Early this year, there was a major breakthrough by Matomaki and Radziwill, who (among other things) showed that the asymptotic (1) was in fact valid for any ${H = H(X)}$ with ${H \leq X}$ that went to infinity as ${X \rightarrow \infty}$ , thus yielding cancellation on extremely short intervals. This has many further applications; for instance, this estimate, or more precisely its extension to other “non-pretentious” bounded multiplicative functions, was a key ingredient in my recent solution of the Erdös discrepancy problem, as well as in obtaining logarithmically averaged cases of Chowla’s conjecture, such as

$\displaystyle \sum_{n \leq x} \frac{\lambda(n) \lambda(n+1)}{n} = o(\log x). \ \ \ \ \ (2)$

It is of interest to twist the above estimates by phases such as the linear phase ${n \mapsto e(\alpha n) := e^{2\pi i \alpha n}}$ . In 1937, Davenport showed that

$\displaystyle \sup_\alpha |\sum_{n \leq x} \lambda(n) e(\alpha n)| \ll_A x \log^{-A} x$

which of course improves the prime number theorem. Recently with Matomaki and Radziwill, we obtained a common generalisation of this estimate with (1), showing that

$\displaystyle \sup_\alpha \int_X^{2X} |\sum_{x \leq n \leq x+H} \lambda(n) e(\alpha n)|\ dx = o(HX) \ \ \ \ \ (3)$

as ${X \rightarrow \infty}$ , for any ${H = H(X) \leq X}$ that went to infinity as ${X \rightarrow \infty}$ . We were able to use this estimate to obtain an averaged form of Chowla’s conjecture.

In that paper, we asked whether one could improve this estimate further by moving the supremum inside the integral, that is to say to establish the bound

$\displaystyle \int_X^{2X} \sup_\alpha |\sum_{x \leq n \leq x+H} \lambda(n) e(\alpha n)|\ dx = o(HX) \ \ \ \ \ (4)$

as ${X \rightarrow \infty}$ , for any ${H = H(X) \leq X}$ that went to infinity as ${X \rightarrow \infty}$ . This bound is asserting that ${\lambda}$ is locally Fourier-uniform on most short intervals; it can be written equivalently in terms of the “local Gowers ${U^2}$ norm” as

$\displaystyle \int_X^{2X} \sum_{1 \leq a \leq H} |\sum_{x \leq n \leq x+H} \lambda(n) \lambda(n+a)|^2\ dx = o( H^3 X )$

from which one can see that this is another averaged form of Chowla’s conjecture (stronger than the one I was able to prove with Matomaki and Radziwill, but a consequence of the unaveraged Chowla conjecture). If one inserted such a bound into the machinery I used to solve the Erdös discrepancy problem, it should lead to further averaged cases of Chowla’s conjecture, such as

$\displaystyle \sum_{n \leq x} \frac{\lambda(n) \lambda(n+1) \lambda(n+2)}{n} = o(\log x), \ \ \ \ \ (5)$

though I have not fully checked the details of this implication. It should also have a number of new implications for sign patterns of the Liouville function, though we have not explored these in detail yet.

One can write (4) equivalently in the form

$\displaystyle \int_X^{2X} \sum_{x \leq n \leq x+H} \lambda(n) e( \alpha(x) n + \beta(x) )\ dx = o(HX) \ \ \ \ \ (6)$

uniformly for all ${x}$ -dependent phases ${\alpha(x), \beta(x)}$ . In contrast, (3) is equivalent to the subcase of (6) when the linear phase coefficient ${\alpha(x)}$ is independent of ${x}$ . This dependency of ${\alpha(x)}$ on ${x}$ seems to necessitate some highly nontrivial additive combinatorial analysis of the function ${x \mapsto \alpha(x)}$ in order to establish (4) when ${H}$ is small. To date, this analysis has proven to be elusive, but I would like to record what one can do with more classical methods like Vaughan’s identity, namely:

Proposition 1 The estimate (4) (or equivalently (6)) holds in the range ${X^{2/3+\varepsilon} \leq H \leq X}$ for any fixed ${\varepsilon>0}$ . (In fact one can improve the right-hand side by an arbitrary power of ${\log X}$ in this case.)

The values of ${H}$ in this range are far too large to yield implications such as new cases of the Chowla conjecture, but it appears that the ${2/3}$ exponent is the limit of “classical” methods (at least as far as I was able to apply them), in the sense that one does not do any combinatorial analysis on the function ${x \mapsto \alpha(x)}$ , nor does one use modern equidistribution results on “Type III sums” that require deep estimates on Kloosterman-type sums. The latter may shave a little bit off of the ${2/3}$ exponent, but I don’t see how one would ever hope to go below ${1/2}$ without doing some non-trivial combinatorics on the function ${x \mapsto \alpha(x)}$ . UPDATE: I have come across this paper of Zhan which uses mean-value theorems for L-functions to lower the ${2/3}$ exponent to ${5/8}$ .

Let me now sketch the proof of the proposition, omitting many of the technical details. We first remark that known estimates on sums of the Liouville function (or similar functions such as the von Mangoldt function) in short arithmetic progressions, based on zero-density estimates for Dirichlet ${L}$ -functions, can handle the “major arc” case of (4) (or (6)) where ${\alpha}$ is restricted to be of the form ${\alpha = \frac{a}{q} + O( X^{-1/6-\varepsilon} )}$ for ${q = O(\log^{O(1)} X)}$ (the exponent here being of the same numerology as the ${X^{1/6+\varepsilon}}$ exponent in the classical result of Ramachandra, tied to the best zero density estimates currently available); for instance a modification of the arguments in this recent paper of Koukoulopoulos would suffice. Thus we can restrict attention to “minor arc” values of ${\alpha}$ (or ${\alpha(x)}$ , using the interpretation of (6)).

Next, one breaks up ${\lambda}$ (or the closely related Möbius function) into Dirichlet convolutions using one of the standard identities (e.g. Vaughan’s identity or Heath-Brown’s identity), as discussed for instance in this previous post (which is focused more on the von Mangoldt function, but analogous identities exist for the Liouville and Möbius functions). The exact choice of identity is not terribly important, but the upshot is that ${\lambda(n)}$ can be decomposed into ${\log^{O(1)} X}$ terms, each of which is either of the “Type I” form

$\displaystyle \sum_{d \sim D; m \sim M: dm=n} a_d$

for some coefficients ${a_d}$ that are roughly of logarithmic size on the average, and scales ${D, M}$ with ${D \ll X^{2/3}}$ and ${DM \sim X}$ , or else of the “Type II” form

$\displaystyle \sum_{d \sim D; m \sim M: dm=n} a_d b_m$

for some coefficients ${a_d, b_m}$ that are roughly of logarithmic size on the average, and scales ${D,M}$ with ${X^{1/3} \ll D,M \ll X^{2/3}}$ and ${DM \sim X}$ . As discussed in the previous post, the ${2/3}$ exponent is a natural barrier in these identities if one is unwilling to also consider “Type III” type terms which are roughly of the shape of the third divisor function ${\tau_3(n) := \sum_{d_1d_2d_3=1} 1}$ .

A Type I sum makes a contribution to ${ \sum_{x \leq n \leq x+H} \lambda(n) e( \alpha(x) n + \beta(x) )}$ that can be bounded (via Cauchy-Schwarz) in terms of an expression such as

$\displaystyle \sum_{d \sim D} | \sum_{x/d \leq m \leq x/d+H/d} e(\alpha(x) dm )|^2.$

The inner sum exhibits a lot of cancellation unless ${\alpha(x) d}$ is within ${O(D/H)}$ of an integer. (Here, “a lot” should be loosely interpreted as “gaining many powers of ${\log X}$ over the trivial bound”.) Since ${H}$ is significantly larger than ${D}$ , standard Vinogradov-type manipulations (see e.g. Lemma 13 of these previous notes) show that this bad case occurs for many ${d}$ only when ${\alpha}$ is “major arc”, which is the case we have specifically excluded. This lets us dispose of the Type I contributions.

A Type II sum makes a contribution to ${ \sum_{x \leq n \leq x+H} \lambda(n) e( \alpha(x) n + \beta(x) )}$ roughly of the form

$\displaystyle \sum_{d \sim D} | \sum_{x/d \leq m \leq x/d+H/d} b_m e(\alpha(x) dm)|.$

We can break this up into a number of sums roughly of the form

$\displaystyle \sum_{d = d_0 + O( H / M )} | \sum_{x/d_0 \leq m \leq x/d_0 + H/D} b_m e(\alpha(x) dm)|$

for ${d_0 \sim D}$ ; note that the ${d}$ range is non-trivial because ${H}$ is much larger than ${M}$ . Applying the usual bilinear sum Cauchy-Schwarz methods (e.g. Theorem 14 of these notes) we conclude that there is a lot of cancellation unless one has ${\alpha(x) = a/q + O( \frac{X \log^{O(1)} X}{H^2} )}$ for some ${q = O(\log^{O(1)} X)}$ . But with ${H \geq X^{2/3+\varepsilon}}$ , ${X \log^{O(1)} X/H^2}$ is well below the threshold ${X^{-1/6-\varepsilon}}$ for the definition of major arc, so we can exclude this case and obtain the required cancellation.

A small remark on the Elliott conjecture

30 October, 2015 in expository, math.NT | Tags: Chowla conjecture, Elliott conjecture, Liouville function | by Terence Tao | 4 comments

The Chowla conjecture asserts, among other things, that one has the asymptotic

$\displaystyle \frac{1}{X} \sum_{n \leq X} \lambda(n+h_1) \dots \lambda(n+h_k) = o(1)$

as ${X \rightarrow \infty}$ for any distinct integers ${h_1,\dots,h_k}$ , where ${\lambda}$ is the Liouville function. (The usual formulation of the conjecture also allows one to consider more general linear forms ${a_i n + b_i}$ than the shifts ${n+h_i}$ , but for sake of discussion let us focus on the shift case.) This conjecture remains open for ${k \geq 2}$ , though there are now some partial results when one averages either in ${x}$ or in the ${h_1,\dots,h_k}$ , as discussed in this recent post.

A natural generalisation of the Chowla conjecture is the Elliott conjecture. Its original formulation was basically as follows: one had

$\displaystyle \frac{1}{X} \sum_{n \leq X} g_1(n+h_1) \dots g_k(n+h_k) = o(1) \ \ \ \ \ (1)$

whenever ${g_1,\dots,g_k}$ were bounded completely multiplicative functions and ${h_1,\dots,h_k}$ were distinct integers, and one of the ${g_i}$ was “non-pretentious” in the sense that

$\displaystyle \sum_p \frac{1 - \hbox{Re}( g_i(p) \overline{\chi(p)} p^{-it})}{p} = +\infty \ \ \ \ \ (2)$

for all Dirichlet characters ${\chi}$ and real numbers ${t}$ . It is easy to see that some condition like (2) is necessary; for instance if ${g(n) := \chi(n) n^{it}}$ and ${\chi}$ has period ${q}$ then ${\frac{1}{X} \sum_{n \leq X} g(n+q) \overline{g(n)}}$ can be verified to be bounded away from zero as ${X \rightarrow \infty}$ .

In a previous paper with Matomaki and Radziwill, we provided a counterexample to the original formulation of the Elliott conjecture, and proposed that (2) be replaced with the stronger condition

$\displaystyle \inf_{|t| \leq X} \sum_{p \leq X} \frac{1 - \hbox{Re}( g_i(p) \overline{\chi(p)} p^{-it})}{p} \rightarrow +\infty \ \ \ \ \ (3)$

as ${X \rightarrow \infty}$ for any Dirichlet character ${\chi}$ . To support this conjecture, we proved an averaged and non-asymptotic version of this conjecture which roughly speaking showed a bound of the form

$\displaystyle \frac{1}{H^k} \sum_{h_1,\dots,h_k \leq H} |\frac{1}{X} \sum_{n \leq X} g_1(n+h_1) \dots g_k(n+h_k)| \leq \varepsilon$

whenever ${H}$ was an arbitrarily slowly growing function of ${X}$ , ${X}$ was sufficiently large (depending on ${\varepsilon,k}$ and the rate at which ${H}$ grows), and one of the ${g_i}$ obeyed the condition

$\displaystyle \inf_{|t| \leq AX} \sum_{p \leq X} \frac{1 - \hbox{Re}( g_i(p) \overline{\chi(p)} p^{-it})}{p} \geq A \ \ \ \ \ (4)$

for some ${A}$ that was sufficiently large depending on ${k,\varepsilon}$ , and all Dirichlet characters ${\chi}$ of period at most ${A}$ . As further support of this conjecture, I recently established the bound

$\displaystyle \frac{1}{\log \omega} |\sum_{X/\omega \leq n \leq X} \frac{g_1(n+h_1) g_2(n+h_2)}{n}| \leq \varepsilon$

under the same hypotheses, where ${\omega}$ is an arbitrarily slowly growing function of ${X}$ .

In view of these results, it is tempting to conjecture that the condition (4) for one of the ${g_i}$ should be sufficient to obtain the bound

$\displaystyle |\frac{1}{X} \sum_{n \leq X} g_1(n+h_1) \dots g_k(n+h_k)| \leq \varepsilon$

when ${A}$ is large enough depending on ${k,\varepsilon}$ . This may well be the case for ${k=2}$ . However, the purpose of this blog post is to record a simple counterexample for ${k>2}$ . Let’s take ${k=3}$ for simplicity. Let ${t_0}$ be a quantity much larger than ${X}$ but much smaller than ${X^2}$ (e.g. ${t = X^{3/2}}$ ), and set

$\displaystyle g_1(n) := n^{it_0}; \quad g_2(n) := n^{-2it_0}; \quad g_3(n) := n^{it_0}.$

For ${X/2 \leq n \leq X}$ , Taylor expansion gives

$\displaystyle (n+1)^{it} = n^{it_0} \exp( i t_0 / n ) + o(1)$

and

$\displaystyle (n+2)^{it} = n^{it_0} \exp( 2 i t_0 / n ) + o(1)$

and hence

$\displaystyle g_1(n) g_2(n+1) g_3(n+2) = 1 + o(1)$

and hence

$\displaystyle |\frac{1}{X} \sum_{X/2 \leq n \leq X} g_1(n) g_2(n+1) g_3(n+2)| \gg 1.$

On the other hand one can easily verify that all of the ${g_1,g_2,g_3}$ obey (4) (the restriction ${|t| \leq AX}$ there prevents ${t}$ from getting anywhere close to ${t_0}$ ). So it seems the correct non-asymptotic version of the Elliott conjecture is the following:

Conjecture 1 (Non-asymptotic Elliott conjecture) Let ${k}$ be a natural number, and let ${h_1,\dots,h_k}$ be integers. Let ${\varepsilon > 0}$ , let ${A}$ be sufficiently large depending on ${k,\varepsilon,h_1,\dots,h_k}$ , and let ${X}$ be sufficiently large depending on ${k,\varepsilon,h_1,\dots,h_k,A}$ . Let ${g_1,\dots,g_k}$ be bounded multiplicative functions such that for some ${1 \leq i \leq k}$ , one has

$\displaystyle \inf_{|t| \leq AX^{k-1}} \sum_{p \leq X} \frac{1 - \hbox{Re}( g_i(p) \overline{\chi(p)} p^{-it})}{p} \geq A$

for all Dirichlet characters ${\chi}$ of conductor at most ${A}$ . Then

$\displaystyle |\frac{1}{X} \sum_{n \leq X} g_1(n+h_1) \dots g_k(n+h_k)| \leq \varepsilon.$

The ${k=1}$ case of this conjecture follows from the work of Halasz; in my recent paper a logarithmically averaged version of the ${k=2}$ case of this conjecture is established. The requirement to take ${t}$ to be as large as ${A X^{k-1}}$ does not emerge in the averaged Elliott conjecture in my previous paper with Matomaki and Radziwill; it thus seems that this averaging has concealed some of the subtler features of the Elliott conjecture. (However, this subtlety does not seem to affect the asymptotic version of the conjecture formulated in that paper, in which the hypothesis is of the form (3), and the conclusion is of the form (1).)

A similar subtlety arises when trying to control the maximal integral

$\displaystyle \frac{1}{X} \int_X^{2X} \sup_\alpha \frac{1}{H} |\sum_{x \leq n \leq x+H} g(n) e(\alpha n)|\ dx. \ \ \ \ \ (5)$

In my previous paper with Matomaki and Radziwill, we could show that easier expression

$\displaystyle \frac{1}{X} \sup_\alpha \int_X^{2X} \frac{1}{H} |\sum_{x \leq n \leq x+H} g(n) e(\alpha n)|\ dx. \ \ \ \ \ (6)$

was small (for ${H}$ a slowly growing function of ${X}$ ) if ${g}$ was bounded and completely multiplicative, and one had a condition of the form

$\displaystyle \inf_{|t| \leq AX} \sum_{p \leq X} \frac{1 - \hbox{Re}( g(p) \overline{\chi(p)} p^{-it})}{p} \geq A \ \ \ \ \ (7)$

for some large ${A}$ . However, to obtain an analogous bound for (5) it now appears that one needs to strengthen the above condition to

$\displaystyle \inf_{|t| \leq AX^2} \sum_{p \leq X} \frac{1 - \hbox{Re}( g(p) \overline{\chi(p)} p^{-it})}{p} \geq A$

in order to address the counterexample in which ${g(n) = n^{it_0}}$ for some ${t_0}$ between ${X}$ and ${X^2}$ . This seems to suggest that proving (5) (which is closely related to the ${k=3}$ case of the Chowla conjecture) could in fact be rather difficult; the estimation of (6) relied primarily of prior work of Matomaki and Radziwill which used the hypothesis (7), but as this hypothesis is not sufficient to conclude (5), some additional input must also be used.

An averaged form of Chowla’s conjecture

17 March, 2015 in math.NT, paper | Tags: Chowla's conjecture, Kaisa Matomaki, Liouville function, Maksym Radziwill | by Terence Tao | 29 comments

Kaisa Matomaki, Maksym Radziwill, and I have just uploaded to the arXiv our paper “An averaged form of Chowla’s conjecture“. This paper concerns a weaker variant of the famous conjecture of Chowla (discussed for instance in this previous post) that

$\displaystyle \sum_{n \leq X} \lambda(n+h_1) \dots \lambda(n+h_k) = o(X)$

as ${X \rightarrow \infty}$ for any distinct natural numbers ${h_1,\dots,h_k}$ , where ${\lambda}$ denotes the Liouville function. (One could also replace the Liouville function here by the Möbius function ${\mu}$ and obtain a morally equivalent conjecture.) This conjecture remains open for any ${k \geq 2}$ ; for instance the assertion

$\displaystyle \sum_{n \leq X} \lambda(n) \lambda(n+2) = o(X)$

is a variant of the twin prime conjecture (though possibly a tiny bit easier to prove), and is subject to the notorious parity barrier (as discussed in this previous post).

Our main result asserts, roughly speaking, that Chowla’s conjecture can be established unconditionally provided one has non-trivial averaging in the ${h_1,\dots,h_k}$ parameters. More precisely, one has

Theorem 1 (Chowla on the average) Suppose ${H = H(X) \leq X}$ is a quantity that goes to infinity as ${X \rightarrow \infty}$ (but it can go to infinity arbitrarily slowly). Then for any fixed ${k \geq 1}$ , we have

$\displaystyle \sum_{h_1,\dots,h_k \leq H} |\sum_{n \leq X} \lambda(n+h_1) \dots \lambda(n+h_k)| = o( H^k X ).$

In fact, we can remove one of the averaging parameters and obtain

$\displaystyle \sum_{h_2,\dots,h_k \leq H} |\sum_{n \leq X} \lambda(n) \lambda(n+h_2) \dots \lambda(n+h_k)| = o( H^{k-1} X ).$

Actually we can make the decay rate a bit more quantitative, gaining about ${\frac{\log\log H}{\log H}}$ over the trivial bound. The key case is ${k=2}$ ; while the unaveraged Chowla conjecture becomes more difficult as ${k}$ increases, the averaged Chowla conjecture does not increase in difficulty due to the increasing amount of averaging for larger ${k}$ , and we end up deducing the higher ${k}$ case of the conjecture from the ${k=2}$ case by an elementary argument.

The proof of the theorem proceeds as follows. By exploiting the Fourier-analytic identity

$\displaystyle \int_{{\mathbf T}} (\int_{\mathbf R} |\sum_{x \leq n \leq x+H} f(n) e(\alpha n)|^2 dx)^2\ d\alpha$

$\displaystyle = \sum_{|h| \leq H} (H-|h|)^2 |\sum_n f(n) \overline{f}(n+h)|^2$

(related to a standard Fourier-analytic identity for the Gowers ${U^2}$ norm) it turns out that the ${k=2}$ case of the above theorem can basically be derived from an estimate of the form

$\displaystyle \int_0^X |\sum_{x \leq n \leq x+H} \lambda(n) e(\alpha n)|\ dx = o( H X )$

uniformly for all ${\alpha \in {\mathbf T}}$ . For “major arc” ${\alpha}$ , close to a rational ${a/q}$ for small ${q}$ , we can establish this bound from a generalisation of a recent result of Matomaki and Radziwill (discussed in this previous post) on averages of multiplicative functions in short intervals. For “minor arc” ${\alpha}$ , we can proceed instead from an argument of Katai and Bourgain-Sarnak-Ziegler (discussed in this previous post).

The argument also extends to other bounded multiplicative functions than the Liouville function. Chowla’s conjecture was generalised by Elliott, who roughly speaking conjectured that the ${k}$ copies of ${\lambda}$ in Chowla’s conjecture could be replaced by arbitrary bounded multiplicative functions ${g_1,\dots,g_k}$ as long as these functions were far from a twisted Dirichlet character ${n \mapsto \chi(n) n^{it}}$ in the sense that

$\displaystyle \sum_p \frac{1 - \hbox{Re} g(p) \overline{\chi(p) p^{it}}}{p} = +\infty. \ \ \ \ \ (1)$

(This type of distance is incidentally now a fundamental notion in the Granville-Soundararajan “pretentious” approach to multiplicative number theory.) During our work on this project, we found that Elliott’s conjecture is not quite true as stated due to a technicality: one can cook up a bounded multiplicative function ${g}$ which behaves like ${n^{it_j}}$ on scales ${n \sim N_j}$ for some ${N_j}$ going to infinity and some slowly varying ${t_j}$ , and such a function will be far from any fixed Dirichlet character whilst still having many large correlations (e.g. the pair correlations ${\sum_{n \leq N_j} g(n+1) \overline{g(n)}}$ will be large). In our paper we propose a technical “fix” to Elliott’s conjecture (replacing (1) by a truncated variant), and show that this repaired version of Elliott’s conjecture is true on the average in much the same way that Chowla’s conjecture is. (If one restricts attention to real-valued multiplicative functions, then this technical issue does not show up, basically because one can assume without loss of generality that ${t=0}$ in this case; we discuss this fact in an appendix to the paper.)

	Terence Tao on Searching for singularities in…
	Terence Tao on 247B, Notes 2: Decoupling…
	Rex on 247B, Notes 2: Decoupling…
	Xiao-Chuan Liu on 247B, Notes 2: Decoupling…
	Brian on Searching for singularities in…
	Aniket Bhattacharya on There’s more to mathematics th…
	Alberto Ibañez on Almost all Collatz orbits atta…
	Rex on 247B, Notes 2: Decoupling…
	Terence Tao on Almost all Collatz orbits atta…
	Rex on 247B, Notes 2: Decoupling…
	Spencer on 246A, Notes 5: conformal …
	Anonymous on Almost all Collatz orbits atta…
	Alberto Ibañez on Almost all Collatz orbits atta…
	Anonymous on Analysis I
	Rex on 247B, Notes 2: Decoupling…

Tag Archive

Value patterns of multiplicative functions and related sequences

Fourier uniformity of bounded multiplicative functions in short intervals on average

The structure of logarithmically averaged correlations of multiplicative functions, with applications to the Chowla and Elliott conjectures

Furstenberg limits of the Liouville function

Special cases of Shannon entropy

A conjectural local Fourier-uniformity of the Liouville function

A small remark on the Elliott conjecture

An averaged form of Chowla’s conjecture

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

For commenters