Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow with N. But how fast? For instance, are there arbitrarily large N admitting a subset of [1..N] with no three-term AP and no gap longer than $N^\epsilon$? Does the subset constructed by Behrend have this property, or might it have unexpectedly long gaps?



Subsets of [1..N] with no three-term arithmetic progressions and no large gaps
For the sake of having a reference, Ron Graham shows in ["On the growth of a van der Waerden-like function"](http://www.emis.ams.org/journals/INTEGERS/papers/g29/g29.pdf) that for a fixed $k$, there exists a 3AP-free subset of $\{1,2,\dots,N\}$ with gaps bounded by $k$ and $N\geq k^{c\log k}$, where $c$ is some absolute constant that doesn't depend on $k$. Therefore you can get gaps to be even bounded by $\exp(c\sqrt{\log N})$.


