A short proof of a conjecture of Erdős proved by Moreira, Richter and Robertson

A short proof of a conjecture of Erdős proved by Moreira, Richter and Robertson, Discrete Analysis 2019:19, 10 pp.

The following question, sometimes known as the Erdős sumset conjecture, was asked by Erdős several decades ago. (The exact age of the problem is hard to determine, but he included it in a list of open problems in 1980, referring to it as an old problem even then.) Let $A$ be a dense subset of the positive integers. Must there be infinite sets $B$ and $C$ such that $B+C\subset A$?

To make this question precise, one needs of course to decide what “dense” means: the definition adopted is that the density $d^*(A)$ of $A$ is

$$\limsup_{n\to\infty}\sup_m \frac{|A\cap\{m+1,\dots,m+n\}|}{n}.$$

Thus, $A$ has positive density if for some $\delta>0$ one can find arbitrarily long intervals of integers inside which $A$ has density at least $\delta$.

Given this hypothesis, it is straightforward to prove that for every $k$ we can find an infinite set $B$ and a set $C$ of size $k$ such that $B+C\subset A$. Indeed, if we choose an integer $r\geq 2\delta^{-1}k$ and a long interval inside which $A$ has density at least $\delta$, then the average density of $A$ inside a subinterval $I$ of length $r$ is at least $\delta/2$, which implies that the average cardinality of $A\cap I$ is at least $k$. We can therefore find inside $A$ an infinite sequence of disjoint subsets, each of which has size $k$ and diameter at most $r$. By the pigeonhole principle, we can find an infinite subsequence of such sets that are translates of one another, and that gives us the desired sets $B$ and $C$.

However, if we want $C$ to be infinite, this argument breaks down completely, since it is no longer possible for each of the sets $b+C$ to live in separate intervals.

The problem was finally resolved in 2018, by Joel Moreira, Florian Richter and Donald Robertson [1], using ultrafilters and ideas from ergodic theory. Much of their proof did not use ergodic theory methods directly in the way that, for example, Furstenberg used them directly to prove Szemerédi’s theorem. Instead, they used arguments that were inspired by ergodic theory methods but translated into formulations that were more combinatorial and concerned sets of integers rather than associated dynamical systems. These translations were not straightforward, so the resulting proof was quite long.

The author of this paper has found a way of formulating the problem dynamically so that the translations are no longer needed and ergodic methods can be used directly. The consequence is an argument that is significantly shorter than that of Moreira, Richter and Robertson.

[1] Joel Moreira, Florian Richter and Donald Robertson, A proof of a sumset conjecture of Erdős, Annals of Mathematics 189 (2019), pp. 605-652; preprint at arxiv:1803.00498