[proofplan] We use the ergodic-theoretic proof of Szemerédi's theorem. The [Furstenberg correspondence principle](/theorems/4615) converts the positive upper density assumption on $A$ into a measurable set $B$ of positive measure in a measure-preserving system, with finite intersections of shifts of $B$ controlled by upper densities of corresponding finite intersections of shifts of $A$. Furstenberg's multiple recurrence theorem then supplies a positive-measure intersection $B \cap T^{-r}B \cap \cdots \cap T^{-(k-1)r}B$ for some $r \geq 1$. Returning through the correspondence principle gives a positive-density set of starting points $n$ for arithmetic progressions $n,n+r,\dots,n+(k-1)r$ inside $A$. [/proofplan] [step:Handle the length one case directly] If $k = 1$, then $\overline d(A) > 0$ implies $A \neq \varnothing$. Choose $n \in A$ and set $r := 1$. Then the one-term progression $n$ is contained in $A$. For the rest of the proof, fix $k \in \mathbb{N}$ with $k \geq 2$. [/step] [step:Pass from positive density to a measure-preserving system] For each $m \in \mathbb{N}_0 := \mathbb{N} \cup \{0\}$, define the shifted set \begin{align*} A - m := \{n \in \mathbb{N} : n+m \in A\}. \end{align*} By the Furstenberg correspondence principle (citing a result not yet in the wiki: Furstenberg correspondence principle), there exist a probability space $(X,\mathcal{B},\mu)$, a measurable map $T:X \to X$ preserving $\mu$, and a set $B \in \mathcal{B}$ such that $\mu(B) = \overline d(A) > 0$ and, for every finite set $F \subset \mathbb{N}_0$, \begin{align*} \mu\left(\bigcap_{m \in F} T^{-m}B\right) \leq \overline d\left(\bigcap_{m \in F} (A-m)\right). \end{align*} Here $T^{-m}B := \{x \in X : T^m(x) \in B\}$ for $m \in \mathbb{N}_0$, with $T^0$ the identity map on $X$. [guided] We want to translate a combinatorial statement about subsets of $\mathbb{N}$ into a recurrence statement in dynamics. For each $m \in \mathbb{N}_0$, define \begin{align*} A - m := \{n \in \mathbb{N} : n+m \in A\}. \end{align*} Thus $n \in A-m$ exactly when the shifted integer $n+m$ lies in $A$. We now apply the Furstenberg correspondence principle (citing a result not yet in the wiki: Furstenberg correspondence principle). Its hypotheses require a subset of $\mathbb{N}$ with positive upper asymptotic density. This is exactly the hypothesis on $A$, since \begin{align*} \overline d(A) := \limsup_{N \to \infty} \frac{|A \cap \{1,\dots,N\}|}{N} > 0. \end{align*} The correspondence principle produces a probability space $(X,\mathcal{B},\mu)$, a measure-preserving measurable map $T:X \to X$, and a measurable set $B \in \mathcal{B}$ with positive measure. More precisely, it gives \begin{align*} \mu(B) = \overline d(A) > 0 \end{align*} and, for every finite set $F \subset \mathbb{N}_0$, \begin{align*} \mu\left(\bigcap_{m \in F} T^{-m}B\right) \leq \overline d\left(\bigcap_{m \in F} (A-m)\right). \end{align*} Here $T^{-m}B$ denotes the preimage of $B$ under $T^m$, namely \begin{align*} T^{-m}B := \{x \in X : T^m(x) \in B\}. \end{align*} This inequality is the bridge we need: any positive-measure multiple recurrence for $B$ will force positive upper density for the corresponding multiple shifted intersection of $A$. [/guided] [/step] [step:Use multiple recurrence to obtain a positive-measure simultaneous return] Apply Furstenberg's multiple recurrence theorem (citing a result not yet in the wiki: [Furstenberg multiple recurrence theorem](/theorems/4616)) to the measure-preserving system $(X,\mathcal{B},\mu,T)$, the measurable set $B$, and the integer $k \geq 2$. Since $\mu(B)>0$, there exists $r \in \mathbb{N}$ such that \begin{align*} \mu\left(B \cap T^{-r}B \cap T^{-2r}B \cap \cdots \cap T^{-(k-1)r}B\right) > 0. \end{align*} [guided] The set $B$ has positive measure, so it must return to itself in a structured way. We apply Furstenberg's multiple recurrence theorem (citing a result not yet in the wiki: Furstenberg multiple recurrence theorem). The theorem requires a probability measure-preserving system, a measurable set of positive measure, and a length $k$. We have these: $(X,\mathcal{B},\mu,T)$ is measure-preserving by the correspondence principle, $B \in \mathcal{B}$, $\mu(B)>0$, and $k \geq 2$ is fixed. The conclusion is that there exists an integer $r \in \mathbb{N}$ such that the simultaneous return set has positive measure: \begin{align*} \mu\left(B \cap T^{-r}B \cap T^{-2r}B \cap \cdots \cap T^{-(k-1)r}B\right) > 0. \end{align*} The point is that the same return time $r$ works for all the shifts $0,r,2r,\dots,(k-1)r$. This common spacing is what will become the common difference of the arithmetic progression in $A$. [/guided] [/step] [step:Transfer the positive recurrence back to a positive-density set of starting points] Define the finite set of shifts \begin{align*} F_r := \{0,r,2r,\dots,(k-1)r\} \subset \mathbb{N}_0. \end{align*} Applying the correspondence inequality to $F_r$ gives \begin{align*} 0 &< \mu\left(\bigcap_{j=0}^{k-1} T^{-jr}B\right) \\ &\leq \overline d\left(\bigcap_{j=0}^{k-1} (A-jr)\right). \end{align*} Therefore \begin{align*} \overline d\left(A \cap (A-r) \cap (A-2r) \cap \cdots \cap (A-(k-1)r)\right) > 0. \end{align*} [guided] Now we feed the recurrence information back into the correspondence principle. Define \begin{align*} F_r := \{0,r,2r,\dots,(k-1)r\} \subset \mathbb{N}_0. \end{align*} This is a finite set, so the correspondence inequality applies to $F_r$. Since the recurrence step gave \begin{align*} \mu\left(\bigcap_{j=0}^{k-1} T^{-jr}B\right) > 0, \end{align*} we obtain \begin{align*} 0 &< \mu\left(\bigcap_{j=0}^{k-1} T^{-jr}B\right) \\ &\leq \overline d\left(\bigcap_{j=0}^{k-1} (A-jr)\right). \end{align*} Hence the shifted intersection \begin{align*} A \cap (A-r) \cap (A-2r) \cap \cdots \cap (A-(k-1)r) \end{align*} has positive upper asymptotic density. In particular, it cannot be empty, because the empty set has upper asymptotic density $0$. [/guided] [/step] [step:Choose a starting point and read off the arithmetic progression] Since \begin{align*} \overline d\left(\bigcap_{j=0}^{k-1} (A-jr)\right) > 0, \end{align*} the intersection $\bigcap_{j=0}^{k-1}(A-jr)$ is nonempty. Choose \begin{align*} n \in \bigcap_{j=0}^{k-1}(A-jr). \end{align*} For each $j \in \{0,1,\dots,k-1\}$, the membership $n \in A-jr$ means $n+jr \in A$. Therefore \begin{align*} n,\ n+r,\ n+2r,\ \dots,\ n+(k-1)r \in A. \end{align*} Since $r \in \mathbb{N}$, we have $r \geq 1$, so for $k \geq 2$ this arithmetic progression is non-constant. Together with the direct verification for $k=1$, this proves the theorem. [/step]