Szemerédi’s Theorem – Does It Hold for Sets with Positive Upper Banach Density?

additive-combinatoricsarithmetic-progressionmeasure-theorynt.number-theory

We say that a set of natural numbers $A\subseteq \omega$ has positive upper density if $$\lim\sup_{n\to\infty}\frac{|A\cap n|}{n+1} > 0.$$
Szeméredi's theorem states that every $A\subseteq \omega$ having positive upper density contains arithmetic sequences of arbitrary (finite) length.

For $y\in \omega$ we set $A – y:= \{|a\setminus y|:a\in A\}.$ Note that $|a\setminus y|$ equals the difference of $a$ and $y$ if $a\geq y$, and $0$ otherwise. The upper Banach density is defined by $$d_{uB}(A) = \lim_{n\to\infty}\big(\sup
\{\frac{|(A-y)\cap n|}{n+1}: y\in\omega\}\big).$$

It is easy to see that $d_{uB}(A) \geq d_{u}(A)$ for all $A\subseteq \omega$.

Question. If $A\subseteq \omega$ has the property that $d_{uB}(A)>0$, does $A$ contain arithmetic sequences of arbitrary finite length?

Best Answer

Yes. As Martin says, this is often how the theorem is stated. It also follows immediately from the also common finitary form:

For all $\delta>0$ and $k\geq 1$, if $N$ is large enough depending on $\delta$ and $k$, $P$ is an arithmetic progression of length $N$, and $A\subseteq P$ has size $\lvert A\rvert\geq \delta N$, then $A$ contains a non-trivial arithmetic progression of length $k$.

(This is e.g. equivalent to the finitary form stated in the Wikipedia article where $P=\{1,\ldots,N\}$, since the property of containing an arithmetic progression is invariant under dilations and translations.)