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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\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$.

Improve this answer
$\endgroup$
2
  • $\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

You must log in to answer this question.

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