Expansion in a prime divisibility graph

Joint with M. Radziwill

Let ${\bf N} = {\Bbb Z}\cap (N, 2N ]$ and ${\bf P} \subset [1, H]$ a set of primes with $H \leq \exp(\sqrt{ \log N /2})$. Given any subset ${\cal X} \subset {\bf N}$, define the linear operator $$(A_{\cal |X} f )(n) =\sum_{p\in{\bf P}:p|n; n,n\pm p\in{\cal X}}f (n \pm p) − \sum_{p\in{\bf P}; n,n\pm p\in{\cal X}}{f (n \pm p)\over n}$$ on functions $f : {\bf N}\to{\Bbb C}$. Let $L = \sum_{p\in{\bf P}}{1\over p}$ .

We prove that, for any $C \gt 0$, there exists a subset ${\cal X}\subset{\bf N}$ of density $1 − O(e^{−C{\cal L}} )$ in $\bf N$ such that $A_{\cal |X}$ has a strong expander property: every eigenvalue of $A_{\cal |X}$ is $O(\sqrt{\cal L})$. It follows immediately that, for any bounded $f, g : {\bf N}\to {\Bbb C}$, $${1\over N{\cal L}}\left| \sum_{n\in{\bf N}; p\in{\bf P}:p|n} f(n)\overline{g(n\pm p)}- \sum_{n\in{\bf N}; p\in{\bf P}}{f(n)\overline{g(n\pm p)}\over p}\right| =O\left(1\over\sqrt{\cal L}\right)\tag{1}$$

This bound is sharp up to constant factors.

Specializing the above bound to $f(n) = g(n) = \lambda(n)$ with $\lambda(n)$ the Liouville function, and using a result in (Matomäki-Radziwiłł-Tao, 2015), we obtain $${1\over\log x}\sum_{n\leq x}{\lambda(n)\lambda(n+1)\over n}=O\left({1\over\sqrt{\log\log x}}\right),\tag{2}$$ improving on a result of Tao’s. Tao’s result relied on a different approach (entropy decrement), requiring $H \leq (\log N )^{ o(1)}$ and leading to weaker bounds.

We also prove the stronger statement that Chowla’s conjecture is true at almost all scales with an error term as in (2), improving on a result by Tao and Teraväinen.

Harald Helfgott