I've been reading about Szemerédi's theorem recently and I'm stuck at its equivalent formulations, namely the ones called finitistic.
There are in fact two versions of it that I have seen and I'm not sure why one of them is equivalent to Szemerédi's theorem (or to another one). I might be missing something trivial, but here it is:
On this page for instance: https://joelmoreira.wordpress.com/2014/02/04/szemeredis-theorem-part-i-equivalent-formulations/ we can see the version whose equivalence with Szemerédi's theorem I can understand. It states the following:
Let $\delta>$ and $k\in\mathbb{N}$. Then there exists a number $N=N(\delta,k)$ such that for every $n\geq N$ and every $A\subset[n]$ with $|A|>\delta n$ there exists a $k$-term arithmetic progression in $A$.
The version given on Wikipedia page (https://en.m.wikipedia.org/wiki/Szemer%C3%A9di%27s_theorem) about Szemerédi's theorem differs slightly, however:
Let $\delta>$ and $k\in\mathbb{N}$. Then there exists a number $N=N(\delta,k)$ such that for every $A\subset[N]$ with $|A|>\delta N$ there exists a $k$-term arithmetic progression in $A$.
It's obvious that the first one implys the the second one. On the contrary, I fail to understand the opposite implication. How could we use the second statement to prove that there is sufficiently large $N$ such that $k$-term arithmetic progression exists when we surpass it? Why wouldn't there be a "gap" between the first and the second $N$ where the arithmetic progression doesn't exist for every subset.
A proof that the second version implies the first:
Fix $\delta>0$ and $k\geq 1$, and $N=N(\delta,k)$ such that for every $A\subseteq [N]$ if $\lvert A\rvert >\frac{\delta}{2}N$ then there is a $k$-AP in $A$.
Let $n$ be large (we'll check how large later) and $A\subset [n]$ with $\lvert A\rvert > \delta n$. Partition $[n]$ into $\lfloor n/N\rfloor$ blocks of consecutive integers of length $N$ and some block of length $<N$. In the worst case there are $N-1$ elements of $A$ in this final tail block.
By averaging there exists some block of $N$ consecutive integers which contains at least
$$ \frac{\lvert A\rvert-(N-1)}{\lfloor n/N\rfloor}>\frac{\delta n-N}{\frac{n}{N}-1}$$
many integers. A little bit of algebra shows that the right-hand side is at least $\frac{\delta}{2}N$ provided $n\geq 2\delta^{-1}N$, say.
Now shift that block of $N$ consecutive integers down to $[N]$ (and shift the part of $A$ down with it) - by the assumed result this contains a $k$-AP, and translating that $k$-AP back up finds a $k$-AP in $A$ as required.