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)$.



existence of arithmetic progression of nonzero density
This is far too ambitious. Recall that the [van der Waerden number](http://en.wikipedia.org/wiki/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](http://arxiv.org/abs/1005.3749) 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.


