Sequences without long arithmetic progressions

Question

First, a bit of notation. If we have an arithmetic progression $a, a+k, a+2k, \ldots, a+(n-1)k$ we will call $k$ the distance, and $n$ the length.

While trying to find an example for a paper I'm writing in ring theory, I was led to ask the question: Is there a sequence of 0's and 1's for which if there is an arithmetic progression in the sequence which is constantly 0 (or 1), is there a bound for the length in terms of the distance?

I found that the answer is yes, and the Thue-Morse sequence works. Modifying the ideas of Corollary 2 in "Thue-Morse at multiples of an integer" (available here), we see that the length of a constant arithmetic progression on the Thue-Morse sequence of distance $k$ is bounded by $32k^3$.

So, here are my questions for you experts.

(1) Is there an easier sequence where one can prove this is true (possibly with citation in the literature)?

(2) If not, is there a straightforward citation for this fact for the Thue-Morse sequence? (The reference I gave above works for arithmetic progressions which start near the front of the sequence. But to get an arbitrary arithmetic progression, you need to increase the bound given in the paper a little, and also give a supplementary argument.)

Answer 1

How about this? Fix your favourite irrational number $\phi$. I like the golden mean. Let $x_s=[ s\phi ] - [(s-1)\phi]$ ($[t]$ means the integer part of $t$). These sequences are called Sturmian sequences.

Of course $x_s$ is 1 if and only if $s\phi \bmod 1$ lies in $[0,\phi)$.

Now for any $a$ and $k$, you're asking whether $(a+jk)\phi\bmod 1$ lies in $[0,\phi)$ for all $0\le j < n$ or lies in $[\phi,1)$ for all $0\le j < n$.

Provided $S_{k,n}:=\lbrace jk\phi\bmod 1\colon 0\le j < n\rbrace$ is $\delta$-dense in the circle, where $\delta=\min(\phi,1-\phi)$ this cannot happen.

This means you can "compute" the maximum length as a function of $k$, namely $L_{max}(k)=\max\lbrace n\colon S_{k,n}$ is not $\delta$-dense$\rbrace$. In the case of golden mean, $L_{max}(k)$ grows linearly in $k$, but I can't write down the proof of that here (the margin is too small).

---

Some more stuff as requested by OP

Claim: If $d(k\phi,\mathbb Z/6)=\epsilon$ then $L_{max}(k)<1/\epsilon$.

Proof: Let $k\phi=a/6+\epsilon$, where $|\epsilon|<1/12$. Notice that $\delta<1/3$. If $a=0$, then $1/\epsilon$ steps produces an $\epsilon$-dense subset of the circle. If $a=1$ or 5, then 12 steps produces a $\delta$-dense subset of the circle. If $a=3$, then $1/\epsilon$ steps produces a $2\epsilon$-dense subset of the circle [because $2k\phi$ is $2\epsilon$-close to $\mathbb Z$] and if $a=2$ or 4, then $1/\epsilon$ steps produces a $3\epsilon$-dense subset of the circle.

Next notice $d(k\phi,\mathbb Z/6)\le d(6k\phi,\mathbb Z)$. From Hardy and Wright (5th ed, Theorem 194) plus a simple argument you get $d(k\phi,\mathbb Z)\le 1/(Ak)$ for a suitable $A$.

Combining these ingredients gives the linear growth of $L_{max}$.