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?

  • $\begingroup$ 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. $\endgroup$
    – dhy
    Nov 3, 2020 at 23:19
  • $\begingroup$ 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. $\endgroup$ Nov 3, 2020 at 23:25
  • $\begingroup$ 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... $\endgroup$
    – dhy
    Nov 3, 2020 at 23:35

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.