Szemerédi's theorem states that a strictly increasing sequence of positive integers $a\_0, a\_1, \ldots$ whose range has positive density contains arbitrarily long arithmetic progressions (as subsequences). I was wondering if the statement still holds when the sequence is not required to be strictly increasing (for any $k$, there is an $n$ such that an arithmetic
progression can be found in $a\_0,\ldots, a\_n$). Perhaps there is some example where, even though the range is of positive density, the elements are shuffled in such a way that, for large enough $k$, no arithmetic progression of length $k$ can appear.


I tried to reduce the problem to the original theorem by waiting long enough in the sequence until a dense subset of $[-N,N]$ appears and then applying Erdős-Szekeres, but this does not seem to work because the length of the monotone subsequence will scale like $\delta \sqrt N$.


This seems like a problem that has been studied before, so would anyone be able to point me towards a reference?



Analogue to Szemerédi's theorem for non-monotone sequences
It appears the statement is false. The paper "On permutations containing no long arithmetic progressions," by Davis, Entringer, Graham, and Simmons [*Acta Arithmetica* **34** (1977)] exhibits a permutation of the positive integers that has no arithmetic progressions of length $5$. The range of this sequence has density $1/2$.


