# existence of arithmetic progression of nonzero density

This is a stronger version to Szemerédi's theorem.

Let $C : \mathbb{N}\rightarrow 2^{\mathbb{N}}$ be a choice function such that $C(n)$ is a subset of $\{1,...,n\}$ with size at least $\frac{n}{M}$ for some nonzero constant $M$ that only depends on $C$. Can we guarantee an arithmetic progression in $C(n)$ of length at least $\frac{n}{M'}$ where $M'$ only depends on $M$?

If not, what is a counter example? and how big arithmetic progression (order in terms of $n$) we can guarantee in $C(n)$.

-

This is far too ambitious. Recall that the van der Waerden number W(k,c) is the smallest $N$ such that if we color $[N]$ with $c$ colors we are guaranteed to have a $k$ term arithmetic progression. Gasarch and Haeupler have given a lower bound of $W(k,c) \gg \frac{c^{k-1}}{ek}$. Thus we can color $[N]$ with $M$ colors such that there is no monochromatic arithmetic progression of length $\gg_{M} \log(N)$. Clearly one of these colors will have size $\geq N/M$, which gives a counterexample to your question.