# Binary words that are nonconstant on long arithmetic progressions

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

• Van der Waerden's theorem says that the answer to question 2 is no, even for larger alphabets. – zeb Oct 29 at 23:42
• @zeb I should have seen that. Good point! – Pace Nielsen Oct 30 at 0:50

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

• I think Olga Parshina has looked at Question 1 for the Thue-Morse word here. – Narad Rampersad Oct 30 at 2:15
• Excellent answer. This gives a bound, $m$, in terms of a rather complicated function of $k$. Do you know if a "nicer" bound can be given for $m$ (in terms of a relatively slow growing function of $k$)? – Pace Nielsen Oct 30 at 16:06
• I haven't worked out the explicit bound in terms of $k$ - I suspect that without too much effort you may be able to get an explicit quadratic or linear bound in $k$ for the Fibonacci word (since the golden ratio has nice rational approximations). Perhaps you can do better with other words - this seems like a natural followup question to ask! – zeb Oct 31 at 14:20