Florian Richter, Donald Robertson and I have uploaded to the arXiv our paper entitled A proof of the Erdős sumset conjecture. The main goal of the paper is to prove the following theorem, which verifies a conjecture of Erdős discussed in this previous post.
As usual, the upper density of a set is the quantity
More generally, given a sequence of intervals of integers with lengths tending to infinity (or even more generally, given any Følner sequence in ), we define the upper density with respect to as
When the limit exists we say that the density of with respect to exists and denote it by (and whenever we write we are implicitly stating that the limit exists).
As explained in my earlier post mentioned above (see Proposition 12), one can adapt an argument of Di Nasso, Goldbring, Jin, Leth, Lupini and Mahlburg to reduce Theorem 1 to the following statement.
Definition 3 A set is:
- a Bohr set if there exist , a vector and an open set such that .
- a weak mixing set with respect to the sequence of intervals if the set has density .
It is well known in the realm of ergodic theory that weak mixing and almost periodicity are extreme points of a dichotomy (see for instance, this post) and so it was natural to try to patch these two observations into a proof of Theorem 2 in general. While this is ultimately how we prove Theorem 2, there were several problems with implementing this idea. Below the fold I explain the problems that arise and (briefly) sketch how we address them.
— 1. Generalizing from sets to functions —
The first problem is that one can not decompose an arbitrary set into a Bohr set and a weak mixing set; instead one can only hope to decompose the indicator function of an arbitrary set with positive density as the sum of an almost periodic and a weak mixing components. However, it is not obvious how to interpret (1) if has been replaced with a function.
To overcome this issue we make use of the notion of ultrafilters. An ultrafilter is a collection of subsets of which is closed under finite intersections and has the properties that if and , then ; and if , then . One should think of ultrafilters in this context as elements of the Stone-Čech compactification of , so that is a discrete but dense subset of . Given a set and an ultrafilter , we denote by the set . One can interpret as a generalized shift of , which has some, but not all, properties of “principal” shifts with . For more background on ultrafilters, see also this previous post.
Here, as usual, the expression denotes the number with the property that for every the set belongs to . It can be shown that such exists and is unique whenever is bounded.
where and for every , and . To make the notation even more suggestive of the functional analytic intuition we want to use, let’s define, for every and sequence of intervals ,
whenever the limit exists, and
With this notation we can briefly formulate a functional version of Theorem 4.
It is not hard to show that Theorem 5 holds for weak mixing and for almost periodic functions.
Definition 6 Let be a function and let be a sequence of intervals.
- is Bohr almost periodic if for every there exists a trigonometric polynomial , where , and , such that
- is Besicovitch almost periodic along if for every there exists a trigonometric polynomial , where , and , such that
- is weak mixing along if for every , the set
has full density.
To establish Theorem 5 for a Bohr almost periodic function one needs to fix a small (say ), then take any ultrafilter containing the infinite set . It follows that and that for all , whence (3) follows. Observe that the same argument does not quite work for a Besicovitch almost periodic function, although it can be combined with an application of the ergodic theorem to work in this case.
Strictly speaking, Theorem 5 is vacuous for weak mixing functions, since a function is weak mixing along if and only if ; but it is also not too hard to establish Theorem 5 when is weak mixing for some constant (this is the case when and is a weak mixing set). Indeed, one can take any ultrafilter which contains the (full density) set , where , and satisfies . That such an ultrafilter exists can be established by modifying the proof of the intersectivity lemma of Bergelson.
— 2. The decompositions —
Next we face the second problem: it is not true that every function can be decomposed into the sum of a Besicovitch almost periodic function and a weak mixing function. Instead we need to resort to two decompositions of an arbitrary function into a pseudo-random and an almost periodic components.
These decompositions are on their own a nice outcome of the proof, and explain to some extent how to decompose a function on in a way which mimics dynamical intuition. It is crucial for us to be able to pass to a subsequence of our initial sequence of intervals, as there are examples which can not be decomposed into reasonable pieces otherwise.
The next definition is heavily influenced by the corresponding notion in ergodic theory (see, for instance Definition 1 in this previous post)
Definition 7 Let be a sequence of intervals. A function is compact with respect to if for every there exists such that
Observe that every Besicovitch almost periodic function along is compact with respect to ; however the converse does not hold. One can show that is compact if it has a Furstenberg system where it is represented by a compact function. Similarly, a function is Besicovitch almost periodic if it has a Furstenberg system where it is represented by a function in the closure of the space spanned by the continuous eigenfunctions.
Our first decomposition is the analog of the Jacobs-de Leeuw-Glicksberg decomposition in .
such that is compact with respect to and is weak mixing with respect to .
The proof of Theorem 8 consists of applying Furstenberg’s correspondence principle to , then using the usual Jacobs-de Leeuw-Glicksberg decomposition and then bringing back the two components from the measure preserving system into functions over . There is a subtle issue regarding the fact that the two components will not be continuous functions (as the decomposition is only a measurable gadget) and to bring the functions back to requires some effort.
Unfortunately, it is not clear how to prove Theorem 5 for a compact function, so we need to also use a second decomposition.
Theorem 9 Let be bounded and let be a sequence of intervals. Then there exists a subsequence of and a decomposition
such that is Besicovitch almost periodic with respect to and for every trigonometric polynomial .
The first term of (4) is very small for a full density set of (in view of the fact that is a weak mixing function) and so for “most” ultrafilters (most here means with respect to a probability measure on which is related with the sequence ).
The middle term of (4) can be easily managed when is Bohr almost periodic: just find a Bohr set with (for some small ) for every , and for every . The second condition implies that whenever is an ultrafilter with we have , and then it is not hard to show that which is positive when is small enough. It is not so easy to deal with the second term when is a general Besicovitch almost periodic function but one can use the approximation of Besicovitch almost periodic functions by trigonometric polynomials, together with the pointwise ergodic theorem to obtain a similar result.
However, it is not clear how to deal with the third term of (4). Observe that this is the term we know the least about, in the sense that is compact but it may not be Besicovitch almost periodic (which would be a stronger condition) and is orthogonal to trigonometric polynomials but it is not necessarily weak mixing (which again would be a stronger condition).
— 3. The final step —
At the end of last section we sketched the argument showing that for almost every ultrafilter containing a certain Bohr set , the sum of the first two terms in (4) is non-negative. The last step is to show that for “many” ultrafilter containing , the last term of (4) is not too negative as . Recall that contained only numbers for which , so we can essentially replace with . Thus we need to show:
Theorem 10 Let be a sequence of intervals in , let be bounded, let satisfy for every trigonometric polynomial , let be a Bohr set and let . Then there is a subsequence of and an ultrafilter containing such that
Our proof of Theorem 10 is inspired by an argument of Beiglböck described in my previous post. One can rephrase the statement of Beiglböck’s result as stating that for any sets one can find an ultrafilter such that . In fact its proof is not hard to modify in order to show that for any functions there exists an ultrafilter such that
However, our condition that must contain the set is crucial and makes the argument more complicated. In particular, we need crucially that is orthogonal to every trigonometric polynomial, and hence also orthogonal to the indicator function of the Bohr set .