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?

  • 3
    $\begingroup$ Isn't this result actually often formulated with upper Banach density? (Maybe with the names Furstenberg and Katznelson.) Google, Google Books, Google Scholar. $\endgroup$ Dec 14, 2022 at 9:07
  • 1
    $\begingroup$ To say it explicitly, you can prove the upper Banach density version from the upper density version by showing the latter is equivalent to the finitary form in the parenthetical in Thomas's answer, which is equivalent to the other finitary form in Thomas's answer, which is equivalent to the upper Banach density version. $\endgroup$ Dec 14, 2022 at 14:51

1 Answer 1


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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.