Expansion, divisibility and parity

Abstract

Let $\mathbf{P}\subset [H_0,H]$ be a set of primes, where $\log H_0\ge (\log H{)}^{2/3+\epsilon }$. Let $\mathcal{L}={\sum }_{p\in \mathbf{P}}1/p$. Let $N$ be such that $\log H\le (\log N{)}^{1/2-\epsilon }$. We show there exists a subset $\mathcal{X}\subset (N,2N]$ of density close to $1$ such that all the eigenvalues of the linear operator $$(A_{|\mathcal{X}}f)(n)=\sum _{\begin{array}{c}p\in \mathbf{P}:p|n\\ n,n\pm p\in \mathcal{X}\end{array}}f(n\pm p)-\sum _{\begin{array}{c}p\in \mathbf{P}\\ n,n\pm p\in \mathcal{X}\end{array}}\frac{f(n\pm p)}{p}$$ are $O(\sqrt{\mathcal{L}})$. This bound is optimal up to a constant factor. In other words, we prove that a graph describing divisibility by primes is a strong local expander almost everywhere, and indeed within a constant factor of being "locally Ramanujan" (a.e.). Specializing to $f(n)=\lambda (n)$ with $\lambda (n)$ the Liouville function, and using an estimate by Matomäki, Radziwiłł and Tao on the average of $\lambda (n)$ in short intervals, we derive that \[\frac{1}{\log x} \sum_{n\leq x} \frac{λ(n) λ(n+1)}{n} = O\Big(\frac{1}{\sqrt{\log \log x}}\Big),\] improving on a result of Tao's. We also prove that ${\sum }_{N<n\le 2N}\lambda (n)\lambda (n+1)=o(N)$ at almost all scales with a similar error term, improving on a result by Tao and Teräväinen. (Tao and Tao-Teräväinen followed a different approach, based on entropy, not expansion; significantly, we can take a much larger value of $H$, and thus consider many more primes.) We can also prove sharper results with ease. For instance: let $S_{N,k}$ the set of all $N<n\le 2N$ such that $\Omega (n)=k$. Then, for any fixed value of $k$ with $k=\log \log N+O(\sqrt{\log \log N})$ (that is, any "popular" value of $k$) the average of $\lambda (n+1)$ over $S_{N,k}$ is $o(1)$ at almost all scales.

Second version: 101 pages, 3 figures. Last section much expanded. Minor corrections