6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\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 Apr 27 '17 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 Apr 27 '17 at 7:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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