# Analogue to Szemerédi's theorem for non-monotone sequences

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?

• A quick observation: You can use Szemerédi's theorem to reduce to the case where (for some fixed large n) $a_0,\cdots, a_n$ is a permutation of $0,\cdots n$. I don't immediately see how to do this case though. – dhy Nov 3 '20 at 23:19
• It is possible for $0,...,n$ to be permuted in a way that there are no $3$-term arithmetic progressions, so I'm not sure where to go from here either. – Marcel K. Goh Nov 3 '20 at 23:25
• Ah, I see what you are saying: the finitary version of this (where we have a finite sequence $a_0,\cdots,a_n$ with large density in some interval) is false: Take $n$ to be one less than a power of $2$, convert each $i$ to a $n$-digit binary string, and reverse the digits to get $a_i$. But since you have an infinite sequence maybe your statement still holds. Tricky... – dhy Nov 3 '20 at 23:35

## 1 Answer

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