Hindman’s finite sums theorem is one of the most famous and useful theorems in Ramsey theory. It states that for any finite partition of the natural numbers, one of the cells of this partition contains an IP-set, i.e., there exists an infinite set such that for any finite subset the sum .

This result is a partition result with no obvious density counterpart. Indeed it is easy to see that the set of odd numbers (which has density ) can not have an IP-set, since for any , either , or must be even. One could still hope that any set with positive density can be shifted in order to contain an IP-set. Indeed, for any set of positive Banach density there is a shift which contains a triple of the form , and often configurations which are partition regular are also in some shift of any set with positive density (however this is not always true, even for configurations with elements, as shown by Kriz’s theorem).

Nevertheless, E. Straus constructed an example of a set with density

arbitrarily close to and such that no shift with contains an IP-set. (Straus never published this result, see Theorem 11.6 in this chapter by Hindman or ) or Theorem 2.20 in this more recent paper.

Observe that by splitting an infinite set into two infinite pieces , it follows that any IP-set contains the sum for infinite sets and . Therefore the following fact can be seen as a weakening of Hindman’s theorem:

Proposition 1For any finite partition of the natural numbers there exists a color and infinite sets such that .

Unlike IP-sets, the configuration is invariant under shifts, so it makes sense to ask whether any set with positive density contains such configuration.

Conjecture 2 (Erdős sumset conjecture)Let and assume that the Banach densityis positive. Then there exist infinite sets such that .

This past week I was at AIM in San Jose for a workshop on Nonstandard methods in combinatorial number theory and there was some interesting discussion surrounding this conjecture. A few years ago there was some significant progress in this direction, in a paper by Di Nasso, Golbring, Jin, Leth, Lupini and Mahlburg using nonstandard analysis, and perhaps because all the authors were present at this workshop there was some hope of extending the ideas developed in the paper to address the general case. In this post I present a standard rendering of the proof from the DGJLLM paper as well as some of the observations made during the workshop.

** — 1. Ultrafilter interpretation — **

The family of sets which contain a sum for infinite sets and can be characterized using ultrafilters. While this characterization is barely used below (and could be avoided entirely) it gives a new perspective on the conjecture.

Recall that an ultrafilter is a filter (i.e. a non-empty collection of subsets of closed under intersections and supersets) such that for every , either or . The set of all ultrafilters is denoted by . Given we denote by the family of ultrafilters . We identify each with the ultrafilter defined by . Ultrafilters of this kind are called principal, and all others are called non-principal.

Given two ultrafilters we define their sum as

A crucial fact about this operation is that (despite being denoted with the sign) it is not commutative!

The reader unfamiliar with ultrafilters will find a more complete exposition in this previous post.

Lemma 3Let . There exist non-principal ultrafilters such that and if and only if there exist infinite sets such that .

*Proof:* If , let and be arbitrary. For every we have , so and hence . By symmetry, also .

If and for some non-principal ultrafilters and , construct, recursively, two sequences and as follows. Take such that . For each , assume have been chosen so that for every and choose

Observe that one can always choose such because the set described above is in and therefore it is infinite. To choose , assume that also have been chosen so that for every . Then choose

Once again the set from which we are choosing belongs to and hence is infinite Finally we conclude that the infinite sets and satisfy .

The same proof shows that for non-principal ultrafilters and if and only if there are increasing sequences and of natural numbers such that whenever .

** — 2. Variations on a lemma of Bergelson — **

A crucial tool in what follows is a nice lemma of Bergelson (and some of its variations). The original statement in Bergelson’s paper is the following:

Lemma 4Let be a probability space and let be a sequence of measurable sets in satisfying . Then there exists a set with and such that for every finite set

*Proof:* For each , let . For each let

and observe that . On the other hand . In view of Fatou’s lemma we deduce that

Now comes the trick: Let denote the collection of all finite subsets for which . Observe that is countable and hence

still has measure.

In view of (1) one can now find such that . Choosing we obtain the desired conclusion.

Note that we have a lot of flexibility in defining the functions to which we apply Fatou’s lemma. In fact one can ask that has positive upper density relatively to any Folner sequence.

One can combine this lemma with Furstenberg’s correspondence principle. In order to use the correspondence principle for more than one set, it is important to restrict to a family of sets which achieve positive upper density along the same Folner sequence. In order to make things cleaner to present we will use instead invariant means.

Definition 5Aninvariant meanon is a linear functional which is positive (i.e. assigns a non-negative number to any sequence of non-negative numbers), invariant (i.e., for every ) and satisfies .

Given an invariant mean and a set with indicator function , we often write instead of . Here is a variant of Bergelson’s lemma which is more useful for this post.

Lemma 6Let be an invariant mean and let be a sequence of subsets of with . Then there exists with and such that for every finite set

*Proof:* Applying a suitable version of the Furstenberg correspondence principle we can find a probability space and sets in with and such that for every finite set

As in the proof of Lemma 4, we can assume that for every finite set the intersection is either empty or has positive measure.

Consider the family of sequences defined, for every and , by if and if . For each we have . This implies that

Observe that the sequence belongs to the convex hull of the sequences with . Since is linear, it follows that there must be a point for which . Letting , the conclusion follows from the correspondence principle and the fact that each intersection , where , contains and hence has positive measure.

When for some fixed set , the previous lemma implies:

Corollary 7Let and an invariant mean. Assume that . Then there exists with and such that for every finite subset we have

In particular we have the first nontrivial progress towards Conjecture 2: if has positive upper Banach density, then for every there exists a set with and a set with positive upper Banach density, such that (a more general version of this fact was obtained by Nathanson in this paper by elementary methods).

One can rewrite this last corollary in a succinct way using the following notation involving ultrafilters introduced by Beiglbock (see this post for some discussion on this notion.)

Definition 8Let and . Define .

Observe that . An ultrafilter is called *essential* if every member has positive upper Banach density. Given an invariant mean , we say that an ultrafilter is -essential if every satisfies .

With this terminology, Corollary 7 can be written as: for every there exists a -essential such that .

** — 3. The DGJLLM argument — **

In the DGJLLM paper mentioned above the following weaker version of the Erdős conjecture is established.

Theorem 9 (DGJLLM)Let with . Then there exists such that contains a sum for infinite sets and .

This result is obtained as a corollary of the fact that the Erdős conjecture holds for sets with large enough Banach density.

Theorem 10 (DGJLLM)Let with . Then contain a sum for infinite sets and .

To derive Theorem 9 from Theorem 10 one needs the following result of Hindman:

Proposition 11Let have . Then there for every there exists such that .

*Proof:* Choose an invariant mean for which and is an extreme point of the (convex) space of all invariant means. Applying Furstenberg’s correspondence principle with this choice of one gets an ergodic system and a set with . But by ergodicity, for every there exists such that .

We can now prove Theorem 9.

*Proof:* using Theorem 10} Let with . In view of Proposition 11 and Theorem 10 there exists and infinite sets such that

To finish the proof one can argue using Ramsey’s theorem (this is the method used in DGJLLM), but a quicker way is to resort to Lemma 3.

Indeed Lemma 3 implies that there exist non-principal ultrafilters and such that and . From the basic properties of ultrafilters, if follows that some shift belongs to and some (potentially different) shift belongs to . Therefore the union belongs to both and and invoking Lemma 3 once again we deduce that contains for infinite sets and . Since this property is shift invariant, also contains a sum for .

The following proposition encapsulates the main idea from the DGJLLM paper.

Proposition 12Let . If there exist an invariant mean , a set and such that for every finite subsetthen there exist infinite sets such that .

*Proof:* Enumerate . Let and, for each , let . Apply Lemma 6 to the family of sets

to find an increasing sequence such that for every ,

Let . Now let and let . For each , let and let . Observe that from the construction, the intersections used to define and are always non-empty.

Letting and we get two infinite sets satisfying as desired.

We can use ultrafilters to rewrite the proposition in a more succinct and suggestive way:

Corollary 13Let . If there exist an invariant mean and a non-principal ultrafilter such thatthen for infinite sets and .

*Proof:* Let , notice that for every and apply the above proposition.

Remark 1The formulation of this corollary suggests the following tantalizingly simple (but wrong!) proof of the Erdős conjecture: given a set , find so that and, using Corollary 7, a non-principal so that . Then the set contains , so, restricting to we obtain a set which belongs to and hence .The problem with this “proof” is of course that is not necessarily open (because is only semi-topological!) and therefore containing is not enough to conclude that , or even that is non-empty.

Theorem 10 follows directly from Proposition 12.

*Proof of Theorem 10:* Let and find an invariant mean so that . Let be the set given by Lemma 6 and let . Notice that for every we have . The conclusion now follows from Proposition 12.

Proposition 12 can also be used to give another result obtained in the BGJLLM paper.

Definition 14Let and let be an invariant mean. Let be the sequence defined by .We say that is

weak-mixing with respect toif . We say that a set ispseudo-randomif there exists an invariant mean such that and is weakly mixing with respect to .

The next proposition is well known in the realm of ergodic theory (see this lemma from my previous post), and can be proved in the current setting by an application of the Furstenberg correspondence principle or directly with the van der Corput trick.

Proposition 15Let and let be an invariant mean. Assume that is weakly mixing with respect to . Then for every ,

Theorem 16 (DGJLLM)Let be pseudo-random. Then contains for infinite sets and .

*Proof:* Let be an invariant mean which witnesses the pseudo-randomness of and let be give by Lemma 6. Proposition 15 implies that the set

satisfies . Therefore for any finite set ,

and the conclusion now follows directly from Proposition 12.

** — 4. An attempt to extend the DGJLLM argument — **

It is natural to ask whether any set with satisfies the condition of Proposition 12.

In general, one can not hope that has full density for every which comes out of Bergelson’s lemma. For instance, if is an infinite progression , then the set given by Lemma 6 is a shift of , and hence has density . However in this case it is easy to check that the intersection is precisely . This idea generalized to piecewise Bohr sets.

Definition 17

- A nonempty set is called a
Bohr setif there exists a homomorphism where is a compact group and an open set such that .- A set is said to be
thickif it contains arbitrarily long intervals or equivalently, if .- A set is called piecewise Bohr if it is the intersection of a Bohr set and a thick set.

Observe that every piecewise Bohr set is in particular piecewise syndetic, and hence contains a shift of an IP-set and in particular . However, it is not so clear that it satisfies the condition of Proposition 12.

Proposition 18Let be piecewise Bohr. Then it satisfies the condition of Proposition 12.

*Proof:* Let be a Bohr set and be a thick set such that . Let be an invariant mean such that . Then .

Let be a compact abelian group and be a homomorphism such that for some open subset . Without loss of generality, assume that is dense in . One can find non-empty open sets such that . Let and . Clearly and thus for every finite set we have

where satisfies .

On the other hand, for every , we have , so , and hence . Putting everything together we conclude that

Given a measure preserving system , every function can be decomposed as where is weakly mixing and is almost periodic (in the sense that the -algebra it generates yields a system isomorphic to a compact group rotation). This is the Koopman-von Neumann decomposition and similar results apply for sequences, including the so-called arithmetic regularity lemmas. In other words, every set can be in some sense decomposed into a pseudo-random set and a Bohr almost periodic set. Unfortunately, the methods used above to establish the assumptions in Proposition 12 for pseudo-random and piecewise Bohr sets do not seem to be robust enough to extend to sets obtained by combining both kinds.

A more concrete problem, which is still open is the following:

Problem 19Let and assume that for every there exists a Bohr set such that the symmetric difference is pseudo-random and has . Show that contains for some infinite sets and .

In a different direction, we have the following corollary of Theorem 10.

Corollary 20Assume has relative density bigger than in some infinite progression . Then for infinite sets and .

*Proof:* Let and observe that . Therefore , and hence where and .

This observation implies that if does not contain then it must have some weak form of regularity. One can also find a progression where the relative density of is almost as large as possible and, replacing with , assume that the relative density of in any progression is close to the density of , to obtain a somewhat stronger form of uniformity. It is not clear, however, that this kind of uniformity is enough to be useful. For instance, I do not even know how to solve the following problem:

Problem 21Assume that has the property that for some invariant mean for every infinite arithmetic progression . Show that contains .

On the other hand, if for every Bohr set , then is pseudo-random and therefore must contain a sum for infinite sets and . Unfortunately, the short argument given in the proof of Corollary 20 does not apply to sets which have relative density bigger than in some Bohr set. In fact, this case is much more general than the situation in Problem 19.

** — 5. Related questions — **

In this section I will collect some final thoughts on related questions to the Erdős conjecture which were brought up during the AIM workshop.

It makes sense to ask the same question in amenable groups (and in fact there are notions of Banach density even for non-amenable groups but we will not pursue this direction).

Question 22 (Erdős conjecture for amenable semigroups)Let be a countable amenable semigroup and let have positive upper Banach density. Is it true that for some infinite sets ?

Theorems 10 and 9 were proved in the DGJLLM paper also for amenable groups. However, certain things start to break down when one removes commutativity. For instance, it is no longer true that any IP-set contains a product , since an IP-set in a noncommutative semigroup is defined as a set containing for every , where is an injective sequence in the semigroup.

In particular, the following seems to still be open.

Question 23Let be a non-commutative semigroup and let be a syndetic set. Is it true that for infinite subsets ?

Since every IP-set is contained in an idempotent ultrafilter, it follows that the characterization given in Lemma 3 does not quite hold in the noncommutative setting. We can still repair the lemma to hold in general:

Proposition 24Let be a countable semigroup and let . Then contains for infinite sets and if and only if there exist non-principle ultrafilters and such thatand

*Proof:* If , let be arbitrary non-principal ultrafilters such that and . For every we have , so and hence . Similarly, also .

If and for some non-principal ultrafilters and , construct, recursively, two sequences and as follows. Take such that . For each , assume have been chosen so that for every and choose

Observe that one can always choose such because the set described above is in and therefore it is infinite. To choose , assume that also have been chosen so that for every . Then choose

Once again the set from which we are choosing belongs to and hence is infinite Finally we conclude that the infinite sets and satisfy .

This argument also shows that if belongs to all the ultrafilters , , and , then there exist infinite sets such that and .

Another natural question is to ask which other subsets of contain a sumset . A natural candidate is the set of prime numbers. The first observation is that even the fact that the primes contain a sum where is infinite and implies the famous bounded gaps theorem of Zhang. Somewhat surprisingly, the claim that the set of prime numbers contains a sum for infinite sets and was proved by Granville conditionally on the famous Hardy and Littlewood’s prime -tuplets conjecture, which is believed to be true.

You wrote, “In particular we have the first nontrivial progress towards Conjecture 2: if {A\subset{\mathbb N}} has positive upper Banach density, then for every {N\in{\mathbb N}} there exists a set {F_N\subset{\mathbb N}} with {|F_N|\geq N} and a set {L_N\subset{\mathbb N}} with positive upper Banach density, such that {F_N+L_N\subset A}.”

This is exact Theorem 6 in

M. B. Nathanson, Sumsets contained in infinite sets of integers, J. Combina. Theory, Series A, 28 (1980), 150 – 155.

Thanks for the reference, I’ve added it in the text.

Pingback: A proof of the Erdős sumset conjecture | I Can't Believe It's Not Random!

Pingback: Optimal intersectivity | I Can't Believe It's Not Random!