7
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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
    Commented 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$
    – Marcel K. Goh
    Commented 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
    Commented Nov 3, 2020 at 23:35

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .