Recall that a syndetic subset of the integers is any $S\subseteq \mathbb{Z}$ with bounded gaps, i.e. there is some $k< \omega$ so that consecutive members of $S$ have distance at most $k$. One way to state Van der Waerden's theorem is that every syndetic set contains arbitrarily long arithmetic progressions (which I will call APs).

Call an AP of the form $\{a, a+d,...,a+(\ell-1)d\}$ a $d$-AP of length $\ell$. Now fix a syndetic $S\subseteq \mathbb{Z}$. For each $\ell < \omega$, let $d_\ell$ denote the least $d$ so that $S$ contains a $d$-AP of length $\ell$. My question is about the function $\ell\to d_\ell$. Is there a syndetic $S\subseteq \mathbb{Z}$ where $d_\ell\to \infty$?


1 Answer 1


The answer is yes, in fact the sequence $S\subset \mathbb{N}$ indexed by Thue-Morse sequence works, see this MO question. Note that this sequence is syndetic because it contains one of $\{2n, 2n+1\}$ for every $n$. You can extend to the negatives by reflecting and trivially only lose a factor of two on $\ell$.

  • $\begingroup$ Thanks! The link you gave suggests the following idea which is quite intuitive. If $x\in [0,1]$ is irrational, let $S = \{n\in \mathbb{Z}: xn-\lfloor xn \rfloor\in [0, 1/2]\}$. Then this clearly has the property I want. How fast can one make the function $\ell\to d_\ell$ grow? $\endgroup$
    – Andy
    Commented Apr 27, 2017 at 3:38
  • $\begingroup$ Not too much to add to that answer - essentially what it shows is such a set $S_x$ will have long arithmetic progressions of common difference $d$ iff $xd$ is very close to an integer, and the length will be inversely proportional to how close this is. In particular the example $x=\phi$ should be best possible up to constants with $\{xd\} \ge d^{-1}$ by standard Diophantine approximation results, and so $d_{\ell}$ growing linearly in $\ell$ is best possible using this construction. $\endgroup$
    – Xiaoyu He
    Commented Apr 27, 2017 at 7:17

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.