4
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think Olga Parshina has looked at Question 1 for the Thue-Morse word here. $\endgroup$ – Narad Rampersad Oct 30 at 2:15
  • $\begingroup$ 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$)? $\endgroup$ – Pace Nielsen Oct 30 at 16:06
  • $\begingroup$ 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! $\endgroup$ – zeb Oct 31 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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