Let $w=x\_0 x\_1 x\_2 \ldots$ be an infinite word, where each $x\_i\in \{0,1\}$. For each positive integer $k$ (thought of as the jump size of an arithmetic progression) and each residue $0\leq a \leq k-1$ we can form the new "arithmetic progression" word $w\_{a\ {\rm mod}\ k}=x\_a x\_{a+k} x\_{a+2k}\ldots$.


**Question 1:** Does there exist a word $w$, as above, so that each of the derived words $w\_{a\ {\rm mod}\ k}$ has no arbitrarily long constant subwords?


I tried finding the answer, but failed. I did find in the literature that for non-binary languages it is possible to do this (and more) without any repetitions at all!


I believe that the answer to Question 1 is probably well-known to experts, and it is positive. If so, I'm interested in the following extension.


**Question 2:** Can the upper bound on the length of the constant subwords of $w\_{a\ {\rm mod}\ k}$ be made *independent* of $a$ and $k$? (If so, what is the smallest such bound?)



Binary words that are nonconstant on long arithmetic progressions
Any Sturmian word will work for Question 1. Before I prove this, I can't resist giving the standard example: the Fibonacci word. The Fibonacci word is defined as the fixed point of the iterative procedure which replaces every $0$ with the string $01$, and replaces every $1$ with the string $0$:


$0100101001001010010100100101...$


In general, a Sturmian word $w$ is characterized by a pair of real numbers $0 \le \alpha, \beta < 1$ such that $\alpha$ is irrational. The $i$ letter of the Sturmian word corresponding to the pair $\alpha, \beta$ is given by


$x\_i = \lfloor\alpha (i+1) + \beta \rfloor - \lfloor\alpha i + \beta \rfloor$.


To see that any Sturmian word will work, note that for any $k \in \mathbb{N}^+$ there is some $\ell \in \mathbb{N}^+$ such that the fractional part $\{\alpha k \ell \}$ of $\alpha k \ell$ is less than $\min(\alpha, 1-\alpha)$. If $m \in \mathbb{N}^+$ is large enough that $m\{\alpha k \ell\} > 1$, then no subword of $w\_{a \text{ mod } k\ell}$ of length $m$ can be constant (for any $a$), so no subword of $w\_{a \text{ mod } k}$ of length $\ell m$ can be constant.


Question: does the Thue-Morse word also work for Question 1? (The Thue-Morse word isn't a Sturmian word, but it has a similar flavor.)


