Arithmetic progression in a subset of $\mathbb N$

Question

What non-trivial sufficient and/or necessary conditions are there for existence an arithmetic progression (finite or infinite length) in an infinite subset of $\mathbb N$.

Answer 1

I assume you know all of this, but:

• Szemerédi's theorem gives a sufficient condition: It suffices that the set (call it $A$) has positive upper density, that is, $$ \limsup_n \frac{|A\cap[1,n]|}n>0. $$ This improved van der Waerden's theorem that ensures that for any $A\subseteq\mathbb N$, either it or its complement has arbitrarily large progressions.

• The Green-Tao theorem shows that Szemerédi's condition is not necessary: The primes have arbitrarily long progressions, and density zero. But their argument identifies a strengthening of Szemerédi's result. As they put it, "any subset of a sufficiently pseudorandom set of positive relative density contains progressions of arbitrary length." For the precise (somewhat technical) statement, see Theorem 3.5 in their paper The primes contain arbitrarily long arithmetic progressions.

• The Erdős conjecture would extend both results: It suffices that $$\sum_{n\in A} \frac1n=+\infty.$$ This is currently completely open: We do not even know that such an $A$ contains $3$-term progressions.

• Some results are known in term of descriptive set theory. The point is that the sets $B$ that do not contain arbitrarily large progressions form an ideal (that is, if $\mathcal I$ is the class of such sets $B$, then if $C\subseteq B\in\mathcal I$, then also $C\in\mathcal I$, and if $B,D\in\mathcal I$, then $B\cup D\in\mathcal I$). This ideal is a Borel ideal (identifying it with a subset of $2^{\mathbb N}$, endowed with the usual product topology), and therefore suitable to techniques of descriptive set theory and set theoretic topology. See for example these slides by Jana Flašková. There is in fact a sizable literature on ultrafilters and their connection to van der Waerden's theorem.