## A proof of the Erdős sumset conjecture

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.

Theorem 1 Let ${A\subset{\mathbb N}}$ have positive upper density. Then it contains a sumset ${B+C=\{b+c:b\in B, c\in C\}}$ for infinite sets ${B}$ and ${C}$.

As usual, the upper density of a set ${A\subset{\mathbb N}}$ is the quantity

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

More generally, given a sequence ${\Phi:N\mapsto\Phi_N=\{a_N,a_N+1,\dots,b_N\}}$ of intervals of integers with lengths ${|\Phi_N|}$ tending to infinity (or even more generally, given any Følner sequence ${\Phi:N\mapsto\Phi_N}$ in ${{\mathbb N}}$), we define the upper density with respect to ${\Phi}$ as

$\displaystyle \bar d_\Phi(A):=\limsup_{N\rightarrow\infty}\frac{\big|A\cap\Phi_N\big|}{|\Phi_N|}.$

When the limit exists we say that the density of ${A}$ with respect to ${\Phi}$ exists and denote it by ${d(A)}$ (and whenever we write ${d(A)}$ 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.

Theorem 2 If ${A\subset{\mathbb N}}$ has positive upper density, then there exist a sequence ${\Phi}$ of intervals, a set ${L\subset{\mathbb N}}$ and ${\epsilon>0}$ such that for every finite subset ${F\subset L}$, the intersection

$\displaystyle \bigcap_{\ell\in F}(A-\ell)\cap\big\{m\in{\mathbb N}:d_\Phi(A-m\cap L)>0\big\} \ \ \ \ \ (1)$

is infinite.

In my previous post I described how Theorem 2 can then be easily checked for weak mixing sets and for Bohr sets, whose definitions we now recall.

Definition 3 A set ${A\subset{\mathbb N}}$ is:

• a Bohr set if there exist ${d\in{\mathbb N}}$, a vector ${\alpha\in{\mathbb T}^d}$ and an open set ${U\subset{\mathbb T}^d}$ such that ${A\supset\{n\in{\mathbb N}:n\alpha\in U\}\neq\emptyset}$.
• a weak mixing set with respect to the sequence of intervals ${\Phi}$ if the set ${\big\{n:\big|d_\Phi((A-n)\cap A)-d_\Phi(A)^2\big|<\epsilon\big\}}$ has density ${1}$.

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. Continue reading

## Single and multiple recurrence along non-polynomial sequences

Vitaly Bergelson, Florian Richter and I have recently uploaded to the arXiv our new paper “Single and multiple recurrence along non-polynomial sequences”. In this paper we address the question of what combinatorial structure is present in the set of return times of a non-polynomial sequence, i.e., sets of the form

$\displaystyle R=\big\{n\in{\mathbb N}:\mu(A\cap T^{-f(n)}A)>\mu^2(A)-\epsilon\big\} \ \ \ \ \ (1)$

where ${(X,\mu,T)}$ is a measure preserving system, ${A\subset X}$, ${\epsilon>0}$ and ${f:{\mathbb N}\rightarrow{\mathbb N}}$ is some non-polynomial function.

The departure point for this paper was the observation that when ${f(n)}$ is a polynomial with integer coefficients and ${f(0)=0}$, set ${R}$ in (1) is syndetic, i.e. has bounded gaps (for the special case ${f(n)=n}$ this is the content of Khintchine’s theorem, and the general case was obtained by Furstenberg, see a proof in my earlier post), but the same is no longer true in general for non-polynomial sequences ${f(n)}$.

For instance when ${f(n)=\lfloor n^a\rfloor}$ for some positive ${a\in{\mathbb R}\setminus{\mathbb Z}}$ (where ${\lfloor \cdot\rfloor}$ denotes the floor function) it is known that the set ${R}$ from (1) is nonempty, and in fact has positive density but is not (in general) syndetic.

Our first theorem shows that nevertheless, the set ${R}$ has an interesting (and a-priori surprising) combinatorial property, it is thick, i.e., contains arbitrarily long intervals of integers. One reason why this is surprising is that the notions of thick and syndetic sets are dual in the sense that a set is thick if and only if its complement is not syndetic and vice-versa. See my previous post for some discussion of the basic properties of thick and syndetic sets.

Theorem 1 Let ${(X,\mu,T)}$ be a measure preserving system, let ${A\subset X}$, and ${a,\epsilon>0}$, ${a\notin{\mathbb N}}$. Then the set ${R}$ defined in (1) for ${f(n)=\lfloor n^a\rfloor}$ is thick.

Theorem 1 implies in particular that for every ${k\in{\mathbb N}}$ there exists some ${n\in{\mathbb N}}$ such that each of the sets ${T^{-f(n)}A}$, ${T^{-f(n+1)}A}$, … , ${T^{-f(n+k)}A}$ have a large intersection with ${A}$. Our second theorem proves that in fact all of these sets intersect together.

Theorem 2 Let ${(X,\mu,T)}$ be a measure preserving system, let ${A\subset X}$, and ${a,\epsilon>0}$, ${a\notin{\mathbb N}}$. Then for every ${k\in{\mathbb N}}$ there exist (many) ${n\in{\mathbb N}}$ such that

$\displaystyle \mu\Big(A\cap T^{-f(n)}A\cap T^{-f(n+1)}A\cap\cdots\cap T^{-f(n+k)}A\Big)>0$

where ${f(n)=\lfloor n^a\rfloor}$.

Note that both Theorems 1 and 2 fail when ${f(n)}$ is a polynomial.

In the paper we deal with a considerably more general class of non-polynomial functions (see Definition 4 below) but for now I will restrict attention to the example ${f(n)=\lfloor n^a\rfloor}$. Continue reading

## 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. Continue reading

Posted in Combinatorics, Number Theory, State of the art | | 3 Comments

## An arithmetic van der Corput trick and the polynomial van der Waerden theorem

The van der Corput difference theorem (or trick) was develop (unsurprisingly) by van der Corput, and deals with uniform distribution of sequences in the torus.

Theorem 1 (van der Corput trick) Let ${(x_n)_{n\in{\mathbb N}}}$ be a sequence in a torus ${{\mathbb T}^d:={\mathbb R}^d/{\mathbb Z}^d}$. If for every ${h\in{\mathbb N}}$ the sequence ${(x_{n+h}-x_n)_{n\in{\mathbb N}}}$ is uniformly distributed on ${{\mathbb T}^d}$, then so is ${(x_n)_{n\in{\mathbb N}}}$.

In 1987, Bergelson observed that a similar trick works in Hilbert spaces and it is this version which turned out to be amazingly useful in ergodic theory (unfortunately for Bergelson, following his own example, everyone keeps calling it the van der Corput trick). Here is a consequence of the “Hilbertian” van der Corput trick of Bergelson:

Theorem 2 Let ${(X,mu,T)}$ be a measure preserving system, let ${k\in{\mathbb N}}$ and let ${p_1,\dots,p_k:{\mathbb N}\rightarrow{\mathbb Z}}$. If

$\displaystyle \lim_{N\rightarrow\infty}\frac1N\sum_{n=1}^N\int_Xf_0\cdot\prod_{p\in{\mathcal P}}T^{p(n)}f_pd\mu=0\qquad \text{ for any }f_p\in L^\infty(X) \ \ \ \ \ (1)$

holds with ${{\mathcal P}=\Big\{p_\ell(n+h)-p_1(n):\ell\in[k]\Big\}\cup\Big\{p_\ell(n)-p_1(n):\ell\in[k]\Big\}}$ for every ${h\in{\mathbb N}}$, then (1) holds with ${{\mathcal P}=\{p_1,\dots,p_k\}}$.

Then in 1996, Bergelson and Leibman adapted the same ideology to topological dynamics. Unfortunately, they didn’t explicitly state an analogue of the difference theorem in topological dynamics (such an explicit statement is Lemma 8.5 in this paper). While it is quite a stretch to call such an analogue as a van der Corput trick (so far from uniform distribution it is) it still expresses the same idea of exploiting the “derivatives” in order to obtain a result about the “original function”.

Here I take this analogy one step further, and using the connection between topological dynamics and arithmetic Ramsey theory powered by piecewise syndetic sets, I will present an arithmetic analogue of the van der Corput trick in ${{\mathbb N}}$. First it will be convenient to have the following definition:

Definition 3 Let ${k\in{\mathbb N}}$ and ${p_1,\dots,p_k:{\mathbb N}\rightarrow{\mathbb Z}}$. We say that the family ${\{p_1,\dots,p_k\}}$ is a family of multiple recurrence if for any finite coloring (i.e. partition) of the natural numbers there exists ${a,n\in{\mathbb N}}$ such that the set

$\displaystyle \big\{a,a+p_1(n),\dots,a+p_k(n)\big\}$

is monochromatic.

Theorem 4 (Arithmetic van der Corput trick) Let ${k\in{\mathbb N}}$ and ${p_1,\dots,p_k:{\mathbb N}\rightarrow{\mathbb Z}}$ be such that ${p_i(0)=0}$. Assume that for any finite set ${F\subset{\mathbb N}\cup\{0\}}$ the family

$\displaystyle \Big\{x\mapsto p_i(x+h)-p_1(x)-p_i(h)\mid h\in F,i\in\{1,\dots k\}\Big\}$

is a family of multiple recurrence. Then the family ${\{p_1,\dots,p_k\}}$ is a family of multiple recurrence as well.

In this post I will give a proof of Theorem 4 and then I will illustrate its power by deriving from it a short proof of the polynomial van der Waerden theorem of Bergelson and Leibman. Continue reading

## Piecewise syndetic sets, topological dynamics and ultrafilters

In this post I explore the notion of piecewise syndeticity and its relation to topological dynamical systems and the Stone-Čech compactification. I restrict attention to the additive semigroup ${({\mathbb N},+)}$ but most results presented are true in much bigger generality (and I tried to present the proofs in a way that does’t depend crucially on the fact that the semigroup is ${({\mathbb N},+)}$). These results and observations are collected from several sources, and are scattered in the literature so I thought it would be nice to collect them all in one place. Probably the union of Furstenberg’s book with the book by Hindman and Strauss contains most (if not all) of the things in here; these surveys of Bergelson are also a good source.

— 1. Introduction —

There are several notions of largeness for subsets of ${{\mathbb N}}$, each notion with its advantages and disadvantages. One such notion is that of syndetic set, i.e., a set ${S\subset{\mathbb N}}$ with bounded gaps. More precisely, ${S}$ is syndetic if there exists a finite set ${F}$ such that any natural number can be written as ${a-b}$ with ${a\in S}$ and ${b\in F}$.

Example 1 The following are syndetic sets:

• The set ${{\mathbb N}}$ of all natural numbers,
• Any co-finite subset ${S\subset{\mathbb N}}$,
• The set ${2{\mathbb N}}$ of even numbers,
• Any infinite progression of the form ${a{\mathbb N}+b}$,
• The set ${\{n\in{\mathbb N}:d(n\alpha,{\mathbb N})<\epsilon\}}$ for any ${\alpha,\epsilon>0}$, where ${d(x,{\mathbb N})}$ is the distance between the positive real number ${x}$ and the lattice of natural numbers.
• The set ${\{n\in{\mathbb N}:d(f(n),{\mathbb N})<\epsilon\}}$ for any ${\epsilon>0}$ and any ${f\in{\mathbb R}[x]}$ with an irrational coefficient (other than the constant term).

One problem with syndeticity is that this notion is not partition regular, i.e. if ${S}$ is a syndetic set and we decompose ${S=A\cup B}$, it may happen that neither ${A}$ nor ${B}$ are syndetic (take ${S={\mathbb N}}$ and ${A}$ and ${B}$ consisting of increasingly long alternating sequences of intervals). One way to fix this is to consider its dual family and then its intersection family (spoiler alert: we end up with piecewise syndetic sets).

## Measure preserving actions of affine semigroups and {x+y,xy} patterns

Vitaly Bergelson and I have recently submitted to the arXiv our paper entitled `Measure preserving actions of affine semigroups and ${\{x+y,xy\}}$ patterns’. The main purpose of this paper is to extend the results of our previous paper, establishing some partial progress towards the following (still open) conjecture:

Conjecture 1 Let ${{\mathbb N}=C_1\cup\cdots\cup C_r}$ be an arbitrary finite partition of the natural numbers. Then there exists ${i\in\{1,\dots,r\}}$ and infinitely many ${x,y\in{\mathbb N}}$ such that

$\displaystyle \{x+y,xy\}\subset C_i$

This conjecture is the simplest unknown case of a much stronger conjecture pertaining various monochromatic polynomial configurations, which is itself only a piece in the wide open problem of classifying which polynomial configurations are partition regular over ${{\mathbb N}}$; see this post for another recent result in this direction.

## Szemerédi Theorem Part VI – Dichotomy between weak mixing and compact extension

This is the sixth and final post in a series about Szemerédi’s theorem. In this post I complete the proof of the Multiple Recurrence Theorem, which I showed in a previous post of this series to be equivalent to Szemerédi’s theorem. The last step missing (cf. third point of Theorem 7 in my previous post) is the following:

Proposition 1 Let ${(X,{\cal B},\mu,T)}$ be a measure preserving system and let ${{\mathcal A}\subset{\mathcal B}}$ be factor. If the extension ${{\cal A}\subset{\cal B}}$ is not weak mixing, then there exists a non-trivial extension ${{\cal A}\subset{\cal D}\subset{\cal B}}$ of which is compact.

The definitions are all precisely given in this earlier post from this series. Most of this post is adapted from the Chapter 7.8 of the book by Einsiedler and Ward. Continue reading