[proofplan] We prove the finite statement by contradiction, using the ergodic route. If the theorem failed, then arbitrarily long intervals would contain subsets of density at least $\delta$ with no $k$-term arithmetic progression. The [Furstenberg correspondence principle](/theorems/4615) converts this sequence of finite counterexamples into a measure-preserving system containing a measurable set of measure at least $\delta$ whose simultaneous recurrent intersections all have measure zero. Furstenberg's multiple recurrence theorem gives a positive-measure recurrent intersection, producing the required contradiction. [/proofplan] [step:Dispose of the one-term case] If $k = 1$, take $N_0(1,\delta) := 1$. For every integer $N \geq 1$, every subset $A \subset \{1,\dots,N\}$ with $|A| \geq \delta N > 0$ is nonempty, and any element $a \in A$ is an arithmetic progression of length $1$. Hence it remains to prove the result for integers $k \geq 2$. [/step] [step:Assume arbitrarily large dense finite sets avoid $k$-term progressions] Fix an integer $k \geq 2$ and a real number $\delta > 0$. Suppose, toward a contradiction, that the theorem is false for this pair $(k,\delta)$. Then for every integer $M \geq 1$ there exist an integer $N \geq M$ and a set $A \subset \{1,\dots,N\}$ such that $|A| \geq \delta N$ and $A$ contains no arithmetic progression of length $k$. Equivalently, there are sequences of integers and sets \begin{align*} N_j &\to \infty, & A_j &\subset \{1,\dots,N_j\}, & |A_j| &\geq \delta N_j, \end{align*} such that no $A_j$ contains a set of the form \begin{align*} \{a, a+r, a+2r, \dots, a+(k-1)r\} \end{align*} with $a \in \mathbb{Z}$ and $r \in \mathbb{N}$. [guided] We fix $k \geq 2$ and $\delta > 0$ and argue by contradiction. The negation of the theorem says that no matter how large a lower threshold $M$ is chosen, there is some $N \geq M$ and some dense set $A \subset \{1,\dots,N\}$ with $|A| \geq \delta N$ but with no $k$-term arithmetic progression. Choosing such a counterexample for each threshold $M=j$ gives sequences \begin{align*} N_j &\to \infty, & A_j &\subset \{1,\dots,N_j\}, & |A_j| &\geq \delta N_j. \end{align*} The condition that $A_j$ has no $k$-term arithmetic progression means precisely that there are no $a \in \mathbb{Z}$ and $r \in \mathbb{N}$ for which \begin{align*} \{a, a+r, a+2r, \dots, a+(k-1)r\} \subset A_j. \end{align*} The positive difference condition $r \in \mathbb{N}$ is important: it rules out the degenerate repetition obtained from $r=0$. [/guided] [/step] [step:Transfer the finite counterexamples to a measure-preserving system] We apply the [Furstenberg Correspondence Principle](/theorems/???) to the sequence $(A_j)_{j=1}^{\infty}$ with ambient intervals $\{1,\dots,N_j\}$. The hypotheses are satisfied because $N_j \to \infty$ and \begin{align*} \limsup_{j \to \infty} \frac{|A_j|}{N_j} \geq \delta. \end{align*} Therefore there exist a probability space $(X,\mathcal{B},\mu)$, a measure-preserving map \begin{align*} T: X &\to X, \end{align*} and a measurable set $E \in \mathcal{B}$ such that $\mu(E) \geq \delta$ and, for every integer $r \geq 1$, \begin{align*} \mu\left(E \cap T^{-r}E \cap T^{-2r}E \cap \cdots \cap T^{-(k-1)r}E\right) = 0. \end{align*} Indeed, if this measure were positive for some $r \geq 1$, the correspondence principle would give, for all sufficiently large $j$, a positive number of points $a \in \{1,\dots,N_j\}$ with \begin{align*} a, a+r, a+2r, \dots, a+(k-1)r \in A_j, \end{align*} contradicting the defining property of $A_j$. [guided] The purpose of the correspondence principle is to convert the sequence of dense finite sets into an infinite dynamical object where recurrence theorems can be applied. We apply the [Furstenberg Correspondence Principle](/theorems/???) to the sets $A_j \subset \{1,\dots,N_j\}$. Its required hypotheses are exactly the two facts already established: the interval lengths satisfy $N_j \to \infty$, and the densities have positive limsup because \begin{align*} \limsup_{j \to \infty} \frac{|A_j|}{N_j} \geq \delta. \end{align*} The conclusion supplies a probability space $(X,\mathcal{B},\mu)$, a measure-preserving map \begin{align*} T: X &\to X, \end{align*} and a measurable set $E \in \mathcal{B}$ with $\mu(E) \geq \delta$. The set $E$ represents the limiting dense set. For each integer $r \geq 1$, the measurable intersection \begin{align*} E \cap T^{-r}E \cap T^{-2r}E \cap \cdots \cap T^{-(k-1)r}E \end{align*} represents points whose orbit visits $E$ at the times $0,r,2r,\dots,(k-1)r$. If this intersection had positive measure for some $r$, the correspondence principle would transfer that positive recurrent pattern back to the finite sets and would imply that, for all sufficiently large $j$, there exists an integer $a$ such that \begin{align*} a, a+r, a+2r, \dots, a+(k-1)r \in A_j. \end{align*} That is a $k$-term arithmetic progression in $A_j$, contradicting the construction of the counterexamples. Hence every such recurrent intersection must have measure zero: \begin{align*} \mu\left(E \cap T^{-r}E \cap T^{-2r}E \cap \cdots \cap T^{-(k-1)r}E\right) = 0 \end{align*} for all $r \geq 1$. [/guided] [/step] [step:Apply multiple recurrence to obtain a positive recurrent intersection] Since $(X,\mathcal{B},\mu)$ is a probability space, $T: X \to X$ is measure-preserving, $k \geq 2$, and $E \in \mathcal{B}$ satisfies $\mu(E) \geq \delta > 0$, the hypotheses of the [Furstenberg Multiple Recurrence Theorem](/theorems/???) are satisfied. Therefore there exists an integer $r \geq 1$ such that \begin{align*} \mu\left(E \cap T^{-r}E \cap T^{-2r}E \cap \cdots \cap T^{-(k-1)r}E\right) > 0. \end{align*} This contradicts the zero-measure conclusion obtained from the correspondence principle. [guided] Now we use the dynamical theorem that supplies the missing recurrence. The [Furstenberg Multiple Recurrence Theorem](/theorems/???) applies to a probability space equipped with a measure-preserving transformation and to a measurable set of positive measure. We verify these hypotheses: $(X,\mathcal{B},\mu)$ is a probability space by the correspondence principle, the map \begin{align*} T: X &\to X \end{align*} is measure-preserving by construction, and $E \in \mathcal{B}$ has positive measure because $\mu(E) \geq \delta > 0$. The theorem therefore gives an integer $r \geq 1$ for which \begin{align*} \mu\left(E \cap T^{-r}E \cap T^{-2r}E \cap \cdots \cap T^{-(k-1)r}E\right) > 0. \end{align*} This is exactly the kind of recurrent intersection that the finite counterexamples forced to have measure zero for every $r \geq 1$. The contradiction is not merely formal: the same intersection has been shown to have measure $0$ by absence of arithmetic progressions and positive measure by multiple recurrence. [/guided] [/step] [step:Conclude the finite theorem] The contradiction shows that the assumed failure for the fixed pair $(k,\delta)$ is impossible. Hence for every integer $k \geq 2$ and every $\delta > 0$ there exists $N_0(k,\delta)$ such that every $N \geq N_0(k,\delta)$ and every $A \subset \{1,\dots,N\}$ with $|A| \geq \delta N$ contains an arithmetic progression of length $k$. Together with the previously proved case $k=1$, this proves the theorem for all integers $k \geq 1$. [/step]