Erdős Sumset conjecture

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 ${C}$ of this partition contains an IP-set, i.e., there exists an infinite set ${I\subset{\mathbb N}}$ such that for any finite subset ${F\subset I}$ the sum ${\sum_{x\in F}x\in C}$.

This result is a partition result with no obvious density counterpart. Indeed it is easy to see that the set ${2{\mathbb N}-1}$ of odd numbers (which has density ${1/2}$) can not have an IP-set, since for any ${x,y\in{\mathbb N}}$, either ${x}$, ${y}$ or ${x+y}$ 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 ${A}$ there is a shift ${A-k}$ which contains a triple of the form ${\{x,y,x+y\}}$, 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 ${2}$ elements, as shown by Kriz’s theorem).

Nevertheless, E. Straus constructed an example of a set ${A}$ with density

$\displaystyle d(A):=\lim_{N\rightarrow\infty}\frac{|A\cap\{1,\dots,N\}|}N$

arbitrarily close to ${1}$ and such that no shift ${A-k}$ with ${k\in{\mathbb N}}$ 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 ${I}$ into two infinite pieces ${B,C}$, it follows that any IP-set contains the sum ${B+C:=\{b+c:b\in B,c\in C\}}$ for infinite sets ${B}$ and ${C}$. Therefore the following fact can be seen as a weakening of Hindman’s theorem:

Proposition 1 For any finite partition ${{\mathbb N}=C_1\cup\dots\cup C_r}$ of the natural numbers there exists a color ${A\in\{C_1,\dots,C_r\}}$ and infinite sets ${B,C\subset{\mathbb N}}$ such that ${A\supset B+C}$.

Unlike IP-sets, the configuration ${B+C}$ 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 ${A\subset{\mathbb N}}$ and assume that the Banach density

$\displaystyle d^*(A):=\lim_{N\rightarrow\infty}\max_{M\in{\mathbb N}}\frac{|A\cap\{M+1,M+2,\dots,M+N\}|}N$

is positive. Then there exist infinite sets ${B,C\subset{\mathbb N}}$ such that ${A\supset B+C}$.

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 ${A\subset{\mathbb N}}$ which contain a sum ${B+C}$ for infinite sets ${B}$ and ${C}$ 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 ${p}$ of subsets of ${{\mathbb N}}$ closed under intersections and supersets) such that for every ${A\subset{\mathbb N}}$, either ${A\in p}$ or ${{\mathbb N}\setminus A\in p}$. The set of all ultrafilters is denoted by ${\beta{\mathbb N}}$. Given ${A\subset{\mathbb N}}$ we denote by ${\bar A}$ the family of ultrafilters ${\bar A:=\{p\in\beta{\mathbb N}:A\in p\}}$. We identify each ${n\in{\mathbb N}}$ with the ultrafilter ${p_n}$ defined by ${A\in p_n\iff n\in A\}}$. Ultrafilters of this kind are called principal, and all others are called non-principal.

Given two ultrafilters ${p,q}$ we define their sum as

$\displaystyle p+q:=\{A:\{n:A-n\in q\}\in p\}$

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 3 Let ${A\subset{\mathbb N}}$. There exist non-principal ultrafilters ${p,q\in\beta{\mathbb N}}$ such that ${A\in p+q}$ and ${A\in q+p}$ if and only if there exist infinite sets ${B,C\subset{\mathbb N}}$ such that ${B+C\subset A}$.

Proof: If ${B+C\subset A}$, let ${p\in\bar B\setminus{\mathbb N}}$ and ${q\in\bar C\setminus{\mathbb N}}$ be arbitrary. For every ${n\in B}$ we have ${C\subset A-n}$, so ${\{n:A-n\in q\}\supset B}$ and hence ${A\in p+q}$. By symmetry, also ${A\in q+p}$.

If ${A\in p+q}$ and ${A\in q+p}$ for some non-principal ultrafilters ${p}$ and ${q}$, construct, recursively, two sequences ${(x_n)}$ and ${(y_n)}$ as follows. Take ${x_1\in{\mathbb N}}$ such that ${A-x_1\in p}$. For each ${n\in{\mathbb N}}$, assume ${x_1,\dots,x_n}$ have been chosen so that ${A-x_i\in p}$ for every ${i=1,\dots,n}$ and choose

$\displaystyle y_n\in(A-x_1)\cap\cdots\cap(A-x_n)\cap\{y\in{\mathbb N}:A-y\in q\}$

Observe that one can always choose such ${y_n}$ because the set described above is in ${p}$ and therefore it is infinite. To choose ${x_{n+1}}$, assume that also ${y_1,\dots,y_n}$ have been chosen so that ${A-y_i\in q}$ for every ${i=1,\dots,n}$. Then choose

$\displaystyle x_{n+1}\in(A-y_1)\cap\cdots\cap(A-y_n)\cap\{x\in{\mathbb N}:A-x\in p\}$

Once again the set from which we are choosing ${x_{n+1}}$ belongs to ${q}$ and hence is infinite Finally we conclude that the infinite sets ${B=\{x_n:n\in{\mathbb N}\}}$ and ${C:=\{y_n:n\in{\mathbb N}\}}$ satisfy ${B+C\subset A}$. $\Box$

The same proof shows that ${A\in p+q}$ for non-principal ultrafilters ${p}$ and ${q}$ if and only if there are increasing sequences ${(b_n)}$ and ${(c_n)}$ of natural numbers such that ${b_n+c_m\in A}$ whenever ${n\leq m}$.

— 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 4 Let ${(X,\mu)}$ be a probability space and let ${(A_n)_{n\in{\mathbb N}}}$ be a sequence of measurable sets in ${X}$ satisfying ${a:=\inf_{n\in{\mathbb N}}\mu(A_n)>0}$. Then there exists a set ${L\subset{\mathbb N}}$ with ${\bar d(L):=\limsup_{N\rightarrow\infty}\frac{|L\cap\{1,\dots,N\}|}N\geq a}$ and such that for every finite set ${F\subset L}$

$\displaystyle \mu\left(\bigcap_{\ell\in F}A_\ell\right)>0$

Proof: For each ${x\in X}$, let ${L(x):=\{n\in{\mathbb N}:x\in A_n\}}$. For each ${N\in{\mathbb N}}$ let

$\displaystyle f_N(x):=\frac1N\sum_{n=1}^N1_{A_n}(x)$

and observe that ${\limsup_{N\rightarrow\infty}f_N(x)=\bar d\big(L(x)\big)}$. On the other hand ${\int_Xf_Nd\mu=\frac1N\sum_{n=1}^N\mu(A_n)\geq a}$. In view of Fatou’s lemma we deduce that

$\displaystyle \int_X\bar d\big(L(x)\big)d\mu\geq a\ \ \ \ \ (1)$

Now comes the trick: Let ${{\mathcal F}}$ denote the collection of all finite subsets ${F\subset{\mathbb N}}$ for which ${\mu(\bigcap_{n\in F}A_n)=0}$. Observe that ${{\mathcal F}}$ is countable and hence

$\displaystyle X_0:=\bigcup_{F\in{\mathcal F}}\left(\bigcap_{n\in F}A_n\right)$

still has ${0}$ measure.

In view of (1) one can now find ${x\in X\setminus X_0}$ such that ${\bar d(L(x))\geq a}$. Choosing ${L:=L(x)}$ we obtain the desired conclusion. $\Box$

Note that we have a lot of flexibility in defining the functions ${f_N}$ to which we apply Fatou’s lemma. In fact one can ask that ${L}$ 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 5 An invariant mean on ${{\mathbb N}}$ is a linear functional ${\lambda:\ell^\infty({\mathbb N})\rightarrow{\mathbb R}}$ which is positive (i.e. assigns a non-negative number to any sequence of non-negative numbers), invariant (i.e., ${\lambda\big((x_n)_{n\in{\mathbb N}}\big)=\lambda\big((x_{n+1})_{n\in{\mathbb N}}\big)}$ for every ${(x_n)_{n\in{\mathbb N}}\in\ell^\infty({\mathbb N})}$) and satisfies ${\lambda(1)=1}$.

Given an invariant mean ${\lambda}$ and a set ${A\subset{\mathbb N}}$ with indicator function ${1_A}$, we often write ${\lambda(A)}$ instead of ${\lambda(1_A)}$. Here is a variant of Bergelson’s lemma which is more useful for this post.

Lemma 6 Let ${\lambda}$ be an invariant mean and let ${A_1,A_2,\dots}$ be a sequence of subsets of ${{\mathbb N}}$ with ${\lambda(A_n)\geq a>0}$. Then there exists ${L\subset{\mathbb N}}$ with ${\lambda(L)\geq a}$ and such that for every finite set ${F\subset L}$

$\displaystyle \lambda\left(\bigcap_{n\in F}A_n\right)>0$

Proof: Applying a suitable version of the Furstenberg correspondence principle we can find a probability space ${(X,\mu)}$ and sets ${B_1,B_2,\dots}$ in ${X}$ with ${\mu(B_n)=\lambda(A_n)}$ and such that for every finite set ${F\subset{\mathbb N}}$

$\displaystyle \mu\left(\bigcap_{n\in F}B_n\right)=\lambda\left(\bigcap_{n\in F}A_n\right).$

As in the proof of Lemma 4, we can assume that for every finite set ${F\subset{\mathbb N}}$ the intersection ${\bigcap_{n\in F}B_n}$ is either empty or has positive measure.

Consider the family of sequences defined, for every ${x\in X}$ and ${n\in{\mathbb N}}$, by ${L(x,n)=1}$ if ${x\in B_n}$ and ${L(x,n)=0}$ if ${x\notin B_n}$. For each ${n\in{\mathbb N}}$ we have ${\int_XL(x,n)d\mu(x)=\mu(B_n)=\lambda(A_n)\geq a}$. This implies that

$\displaystyle \lambda\left(\int_XL(x,n)d\mu(x)\right)\geq a$

Observe that the sequence ${\int_XL(x,n)d\mu(x)}$ belongs to the convex hull of the sequences ${L(x,n)}$ with ${x\in{\mathbb N}}$. Since ${\lambda}$ is linear, it follows that there must be a point ${x\in X}$ for which ${\lambda(L(x,n))\geq a}$. Letting ${L:=L(x,n)}$, the conclusion follows from the correspondence principle and the fact that each intersection ${\bigcap_{n\in F}B_n}$, where ${F\subset L}$, contains ${x}$ and hence has positive measure. $\Box$

When ${A_n=A-n}$ for some fixed set ${A\subset{\mathbb N}}$, the previous lemma implies:

Corollary 7 Let ${A\subset{\mathbb N}}$ and ${\lambda}$ an invariant mean. Assume that ${\lambda(A)>0}$. Then there exists ${L\subset{\mathbb N}}$ with ${\lambda(L)\geq\lambda(A)}$ and such that for every finite subset ${F\subset L}$ we have

$\displaystyle \lambda\left(\bigcap_{\ell\in F}A-\ell\right)=\lambda\big(\{n\in{\mathbb N}:n+F\subset A\}\big)>0.$

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}$ (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 8 Let ${A\subset{\mathbb N}}$ and ${p\in\beta{\mathbb N}}$. Define ${A-p:=\{n\in{\mathbb N}:A-n\in p\}}$.

Observe that ${A-p=\{q\in\beta{\mathbb N}:p+q\in \bar A\}\cap{\mathbb N}}$. An ultrafilter ${p\in\beta{\mathbb N}}$ is called essential if every member ${A\in p}$ has positive upper Banach density. Given an invariant mean ${\lambda}$, we say that an ultrafilter ${p\in\beta{\mathbb N}}$ is ${\lambda}$-essential if every ${A\in p}$ satisfies ${\lambda(A)>0}$.

With this terminology, Corollary 7 can be written as: for every ${A\in{\mathbb N}}$ there exists a ${\lambda}$-essential ${p\in\beta{\mathbb N}}$ such that ${\lambda(A-p)\geq\lambda(A)}$.

— 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 ${A\subset{\mathbb N}}$ with ${d^*(A)>0}$. Then there exists ${k\in{\mathbb N}}$ such that ${A\cup(A-k)}$ contains a sum ${B+C}$ for infinite sets ${B}$ and ${C}$.

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 ${A\subset{\mathbb N}}$ with ${d^*(A)>1/2}$. Then ${A}$ contain a sum ${B+C}$ for infinite sets ${B}$ and ${C}$.

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

Proposition 11 Let ${A\subset{\mathbb N}}$ have ${d^*(A)>0}$. Then there for every ${\epsilon>0}$ there exists ${n\in{\mathbb N}}$ such that ${d^*\big(A\cup(A-1)\cup\cdots\cup(A-n)\big)>1-\epsilon}$.

Proof: Choose an invariant mean ${\lambda}$ for which ${\lambda(A)>0}$ and ${\lambda}$ is an extreme point of the (convex) space of all invariant means. Applying Furstenberg’s correspondence principle with this choice of ${\lambda}$ one gets an ergodic system ${(X,\mu,T)}$ and a set ${B\subset X}$ with ${\mu(B)>0}$. But by ergodicity, for every ${\epsilon>0}$ there exists ${n\in{\mathbb N}}$ such that ${\mu\big(B\cup T^{-1}B\cup\cdots\cup T^{-n}B\big)>1-\epsilon}$. $\Box$

We can now prove Theorem 9.

Proof: using Theorem 10} Let ${A\subset{\mathbb N}}$ with ${d^*(A)>0}$. In view of Proposition 11 and Theorem 10 there exists ${n\in{\mathbb N}}$ and infinite sets ${B_1,C_1}$ such that

$\displaystyle B_1+C_1\subset A_n:=A\cup(A-1)\cup\cdots\cup(A-n)$

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 ${p}$ and ${q}$ such that ${A_n\in p+q}$ and ${A_n\in q+p}$. From the basic properties of ultrafilters, if follows that some shift ${A-i}$ belongs to ${p+q}$ and some (potentially different) shift ${A-j}$ belongs to ${q+p}$. Therefore the union ${\tilde A=(A-i)\cup(A-j)}$ belongs to both ${p+q}$ and ${q+p}$ and invoking Lemma 3 once again we deduce that ${\tilde A}$ contains ${B+C}$ for infinite sets ${B}$ and ${C}$. Since this property is shift invariant, also ${A\cup(A-k)}$ contains a sum ${B+C}$ for ${k=i-j}$. $\Box$

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

Proposition 12 Let ${A\subset{\mathbb N}}$. If there exist an invariant mean ${\lambda}$, a set ${L\subset{\mathbb N}}$ and ${\epsilon>0}$ such that for every finite subset ${F\subset L}$

$\displaystyle \bigcap_{\ell\in F}(A-\ell)\ \cap\ \Big\{m\in{\mathbb N}:\lambda\big((A-m)\cap L\big)>\epsilon\Big\}\text{ is infinite}$

then there exist infinite sets ${B,C}$ such that ${A\supset B+C}$.

Proof: Enumerate ${L=\{\ell_1,\ell_2,\dots\}}$. Let ${R:=\Big\{m\in{\mathbb N}:\lambda\big((A-m)\cap L\big)>\epsilon\Big\}}$ and, for each ${n\in{\mathbb N}}$, let ${d_n\in \bigcap_{i=1}^n(A-\ell_i)\cap R}$. Apply Lemma 6 to the family of sets

$\displaystyle \Big\{(A-d_n)\cap L:n\in{\mathbb N}\Big\}$

to find an increasing sequence ${(n_k)}$ such that for every ${N\in{\mathbb N}}$,

$\displaystyle \bigcap_{k=1}^N(A-d_{n_k})\cap L\neq\emptyset.$

Let ${D=\{d_{n_k}:k\in{\mathbb N}\}}$. Now let ${b_1:=\ell_1\in L}$ and let ${c_1:=d_{n_1}\in (A-b_1)\cap D}$. For each ${n=2,3,\dots}$, let ${b_n\in L\cap(A-c_1)\cap\cdots\cap(A-c_{n-1})}$ and let ${c_n\in D\cap(A-b_1)\cap\cdots\cap(A-b_n)}$. Observe that from the construction, the intersections used to define ${b_n}$ and ${c_n}$ are always non-empty.

Letting ${B=\{b_n:n\in{\mathbb N}\}}$ and ${C=\{c_n:n\in{\mathbb N}\}}$ we get two infinite sets satisfying ${B+C\subset A}$ as desired. $\Box$

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

Corollary 13 Let ${A\subset{\mathbb N}}$. If there exist an invariant mean ${\lambda}$ and a non-principal ultrafilter ${p\in\beta{\mathbb N}}$ such that

$\displaystyle p\text{-}\lim\ \lambda\big((A-m)\cap(A-p)\big)>0$

then ${A\supset B+C}$ for infinite sets ${B}$ and ${C}$.

Proof: Let ${L=A-p}$, notice that ${A-\ell\in p}$ for every ${\ell\in L}$ and apply the above proposition. $\Box$

Remark 1 The formulation of this corollary suggests the following tantalizingly simple (but wrong!) proof of the Erdős conjecture: given a set ${A\subset{\mathbb N}}$, find ${\lambda}$ so that ${\lambda(A)>0}$ and, using Corollary 7, a non-principal ${p}$ so that ${\lambda(A-p)>0}$. Then the set ${U:=\{q\in\beta{\mathbb N} :\lambda(A-q\cap A-p)>\lambda(A)/2\}}$ contains ${p}$, so, restricting to ${{\mathbb N}}$ we obtain a set ${U\cap{\mathbb N}}$ which belongs to ${p}$ and hence ${p\text{-}\lim\ \lambda\big((A-m)\cap(A-p)\big)\geq\lambda(A)/2}$.

The problem with this “proof” is of course that ${U}$ is not necessarily open (because ${\beta{\mathbb N}}$ is only semi-topological!) and therefore ${U}$ containing ${p}$ is not enough to conclude that ${U\cap{\mathbb N}\in p}$, or even that ${U\cap p}$ is non-empty.

Theorem 10 follows directly from Proposition 12.

Proof of Theorem 10: Let ${A\subset{\mathbb N}}$ and find an invariant mean ${\lambda}$ so that ${\lambda(A)>1/2}$. Let ${L}$ be the set given by Lemma 6 and let $\epsilon=2\lambda(A)-1$. Notice that for every $m\in\mathbb{N}$ we have ${\lambda\big((A-m)\cap L\big)>\epsilon}$. The conclusion now follows from Proposition 12. $\Box$

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

Definition 14 Let ${f\in\ell^\infty({\mathbb N})}$ and let ${\lambda}$ be an invariant mean. Let ${\Delta f\in\ell^\infty({\mathbb N})}$ be the sequence defined by ${(\Delta f)(n):=\lambda\Big(\big(f(x+n)f(x)\big)_{x\in{\mathbb N}}\Big)}$.

We say that ${f}$ is weak-mixing with respect to ${\lambda}$ if ${\lambda(|\Delta f|)=0}$. We say that a set ${A\subset{\mathbb N}}$ is pseudo-random if there exists an invariant mean ${\lambda}$ such that ${\lambda(A)>0}$ and ${1_A-\lambda(A)}$ is weakly mixing with respect to ${\lambda}$.

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 15 Let ${f\in\ell^\infty({\mathbb N})}$ and let ${\lambda}$ be an invariant mean. Assume that ${f}$ is weakly mixing with respect to ${\lambda}$. Then for every ${g\in\ell^\infty({\mathbb N})}$,

$\displaystyle \lambda\bigg(\Big|\lambda\big(f(x+n)g(x)\big)_{x\in{\mathbb N}}\Big|\bigg)_{n\in{\mathbb N}}=0$

Theorem 16 (DGJLLM) Let ${A\subset{\mathbb N}}$ be pseudo-random. Then ${A}$ contains ${B+C}$ for infinite sets ${B}$ and ${C}$.

Proof: Let ${\lambda}$ be an invariant mean which witnesses the pseudo-randomness of ${A}$ and let ${L}$ be give by Lemma 6. Proposition 15 implies that the set

$\displaystyle R:=\{m\in{\mathbb N}:\lambda\big((A-m)\cap L\big)>\lambda(A)\lambda(L)/2\}$

satisfies ${\lambda(R)=1}$. Therefore for any finite set ${F\subset{\mathbb N}}$,

$\displaystyle \lambda\left(\bigcap_{\ell\in F}(A-\ell)\cap R\right)=\lambda\left(\bigcap_{\ell\in F}(A-\ell)\right)>0$

and the conclusion now follows directly from Proposition 12. $\Box$

— 4. An attempt to extend the DGJLLM argument —

It is natural to ask whether any set ${A\subset{\mathbb N}}$ with ${d^*(A)>0}$ satisfies the condition of Proposition 12.

In general, one can not hope that ${R:=\{m\in{\mathbb N}:\lambda\big((A-m)\cap L\big)>\epsilon\}}$ has full density for every ${L}$ which comes out of Bergelson’s lemma. For instance, if ${A}$ is an infinite progression ${A=a{\mathbb N}+b}$, then the set ${L}$ given by Lemma 6 is a shift ${a{\mathbb N}+c}$ of ${A}$, and hence ${R=a{\mathbb N}+(b-c)}$ has density ${1/a}$. However in this case it is easy to check that the intersection ${\bigcap_{\ell\in L}(A-\ell)}$ is precisely ${R}$. This idea generalized to piecewise Bohr sets.

Definition 17

• A nonempty set ${B\subset{\mathbb Z}}$ is called a Bohr set if there exists a homomorphism ${\phi:{\mathbb Z}\rightarrow K}$ where ${K}$ is a compact group and an open set ${U\subset K}$ such that ${B=\phi^{-1}(U)}$.
• A set ${T\subset{\mathbb N}}$ is said to be thick if it contains arbitrarily long intervals or equivalently, if ${d^*(T)=1}$.
• A set ${A\subset{\mathbb N}}$ 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 ${B+C}$. However, it is not so clear that it satisfies the condition of Proposition 12.

Proposition 18 Let ${A\subset{\mathbb N}}$ be piecewise Bohr. Then it satisfies the condition of Proposition 12.

Proof: Let ${B}$ be a Bohr set and ${T}$ be a thick set such that ${A=B\cap T}$. Let ${\lambda}$ be an invariant mean such that ${\lambda(T)=1}$. Then ${\lambda(A)=\lambda(B)>0}$.

Let ${K}$ be a compact abelian group and ${\phi:{\mathbb Z}\rightarrow K}$ be a homomorphism such that ${B=\phi^{-1}(U)}$ for some open subset ${U\subset K}$. Without loss of generality, assume that ${\phi({\mathbb Z})}$ is dense in ${K}$. One can find non-empty open sets ${V_1,V_2\subset K}$ such that ${V_1+V_2\subset U}$. Let ${L=\phi^{-1}(V_1)}$ and ${S=\phi^{-1}(V_2)}$. Clearly ${L+S\subset B}$ and thus for every finite set ${F\subset L}$ we have

$\displaystyle \bigcap_{\ell\in F}(A-\ell)=\bigcap_{\ell\in F}(B-\ell)\cap \bigcap_{\ell\in F}(T-\ell)\supset S\cap T_F$

where ${T_F:=\bigcap_{\ell\in F}(T-\ell)}$ satisfies ${\lambda(T_F)=1}$.

On the other hand, for every ${s\in S}$, we have ${B-s\supset L}$, so ${(A-s)\cap L=(B-s)\cap(T-s)\cap L\supset (T-s)\cap L}$, and hence ${\lambda((A-s)\cap L)\geq\lambda(L)}$. Putting everything together we conclude that

$\displaystyle \lambda\left(\bigcap_{\ell\in F}(A-\ell)\cap\Big\{m\in{\mathbb N}:\lambda\big((A-m)\cap L\big)>\lambda(L)/2\Big\}\right)\geq\lambda(S)>0.$

$\Box$

Given a measure preserving system ${(X,\mu,T)}$, every function ${f\in L^2}$ can be decomposed as ${f=f_{wm}+f_c}$ where ${f_{wm}}$ is weakly mixing and ${f_c}$ is almost periodic (in the sense that the ${\sigma}$-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 ${A\subset{\mathbb N}}$ 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 19 Let ${A\subset{\mathbb N}}$ and assume that for every ${\epsilon>0}$ there exists a Bohr set ${D\subset A}$ such that the symmetric difference ${E:=A\triangle D}$ is pseudo-random and has ${d^*(E)<\epsilon}$. Show that ${A}$ contains ${B+C}$ for some infinite sets ${B}$ and ${C}$.

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

Corollary 20 Assume ${A\subset{\mathbb N}}$ has relative density ${d^*(A\cap P)/d^*(P)}$ bigger than ${1/2}$ in some infinite progression ${P=a{\mathbb N}+b}$. Then ${A\supset B+C}$ for infinite sets ${B}$ and ${C}$.

Proof: Let ${\tilde A:=\{n:an+b\in A\}}$ and observe that ${d^*(\tilde A)>1/2}$. Therefore ${\tilde A\supset\tilde B+\tilde C}$, and hence ${A\supset B+C}$ where ${B=a\tilde B+b}$ and ${C=a\tilde C}$. $\Box$

This observation implies that if ${A}$ does not contain ${B+C}$ then it must have some weak form of regularity. One can also find a progression ${P=a{\mathbb N}+b}$ where the relative density of ${A}$ is almost as large as possible and, replacing ${A}$ with ${\{n:an+b\in A\}}$, assume that the relative density of ${A}$ in any progression is close to the density of ${A}$, 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 21 Assume that ${A\subset{\mathbb N}}$ has the property that for some invariant mean ${\lambda(A\cap P)/\lambda(P)=\lambda(A)>0}$ for every infinite arithmetic progression ${P}$. Show that ${A}$ contains ${B+C}$.

On the other hand, if ${\lambda(A\cap B)/\lambda(B)=\lambda(A)>0}$ for every Bohr set ${B}$, then ${A}$ is pseudo-random and therefore must contain a sum ${\tilde B+C}$ for infinite sets ${\tilde B}$ and ${C}$. Unfortunately, the short argument given in the proof of Corollary 20 does not apply to sets which have relative density bigger than ${1/2}$ 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 ${(G,\cdot)}$ be a countable amenable semigroup and let ${A\subset G}$ have positive upper Banach density. Is it true that ${A\supset B\cdot C:=\{b\cdot c:b\in B,c\in C\}}$ for some infinite sets ${B,C\subset G}$?

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 ${B\cdot C}$, since an IP-set in a noncommutative semigroup is defined as a set ${A}$ containing ${x_{n_1}\cdot x_{n_2}\cdots x_{n_k}}$ for every ${n_1, where ${(x_n)_{n\in{\mathbb N}}}$ is an injective sequence in the semigroup.

In particular, the following seems to still be open.

Question 23 Let ${(G,\cdot)}$ be a non-commutative semigroup and let ${S\subset G}$ be a syndetic set. Is it true that ${S\supset B\cdot C}$ for infinite subsets ${B,C\subset G}$?

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 24 Let ${(G,\cdot)}$ be a countable semigroup and let ${A\subset G}$. Then ${A}$ contains ${B\cdot C}$ for infinite sets ${B}$ and ${C}$ if and only if there exist non-principle ultrafilters ${p}$ and ${q}$ such that

$\displaystyle A\in p+_Lq=\{E\subset G:\{g\in G:g^{-1}E\in q\}\in p\}$

and

$\displaystyle A\in q+_Rp=\{E\subset G:\{g\in G:Eg^{-1}\in p\}\in q\}$

Proof: If ${B\cdot C\subset A}$, let ${p,q\in\beta G}$ be arbitrary non-principal ultrafilters such that ${B\in p}$ and ${C\in q}$. For every ${b\in B}$ we have ${C\subset g^{-1}A}$, so ${\{g:g^{-1}A\in q\}\supset B}$ and hence ${A\in p+_Lq}$. Similarly, also ${A\in q+_Rp}$.

If ${A\in p+_Lq}$ and ${A\in q+_Rp}$ for some non-principal ultrafilters ${p}$ and ${q}$, construct, recursively, two sequences ${(x_n)}$ and ${(y_n)}$ as follows. Take ${x_1\in G}$ such that ${Ax_1^{-1}\in p}$. For each ${n\in{\mathbb N}}$, assume ${x_1,\dots,x_n}$ have been chosen so that ${Ax_i^{-1}\in p}$ for every ${i=1,\dots,n}$ and choose

$\displaystyle y_n\in(Ax_1^{-1})\cap\cdots\cap(Ax_n^{-1})\cap\{y\in G:y^{-1}A\in q\}$

Observe that one can always choose such ${y_n}$ because the set described above is in ${p}$ and therefore it is infinite. To choose ${x_{n+1}}$, assume that also ${y_1,\dots,y_n}$ have been chosen so that ${y_i^{-1}A\in q}$ for every ${i=1,\dots,n}$. Then choose

$\displaystyle x_{n+1}\in(y_1^{-1}A)\cap\cdots\cap(y_n^{-1}A)\cap\{x\in{\mathbb N}:Ax^{-1}\in p\}$

Once again the set from which we are choosing ${x_n}$ belongs to ${q}$ and hence is infinite Finally we conclude that the infinite sets ${B=\{x_n:n\in{\mathbb N}\}}$ and ${C:=\{y_n:n\in{\mathbb N}\}}$ satisfy ${B\cdot C\subset A}$. $\Box$

This argument also shows that if ${A}$ belongs to all the ultrafilters ${p+_Lq}$, ${p+_R q}$, ${q+_L p}$ and ${q+_R p}$, then there exist infinite sets ${B,C\subset G}$ such that ${B\cdot C\subset A}$ and ${C\cdot B\subset A}$.

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

Advertisements
This entry was posted in Combinatorics, Number Theory, State of the art and tagged , , , , , , , . Bookmark the permalink.

4 Responses to Erdős Sumset conjecture

1. Mel Nathanson says:

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.

• Joel Moreira says:

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