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

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

2 Answers 2

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I think Olga Parshina has looked at Question 1 for the Thue-Morse word here. $\endgroup$
    – Narad Rampersad
    Commented Oct 30, 2020 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
    Commented Oct 30, 2020 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
    Commented Oct 31, 2020 at 14:20
  • 1
    $\begingroup$ As zeb said, for a Sturmian, the max length of a constant run of $0$ or $1$ is just $\lfloor \max \left( \frac{1}{1 - \alpha}, \frac{1}{\alpha} \right) \rfloor$. And for a Sturmian $x$ with rotation number $\alpha$, $x_{a \pmod k}$ is a Sturmian with rotation number $k\alpha$. So, your $m(k)$ function is basically just the reciprocal of the distance $[k\alpha]$ from $k\alpha$ to $\mathbb{Z}$. As zeb said, the growth of $m(k)$ is basically controlled by the continued fraction expansion of $\alpha$. For example, if $\alpha$ is quadratic irrational, then $m(k) = o(k^{2+t})$ for all $t > 0$. $\endgroup$
    – Ronnie Pavlov
    Commented Jul 28, 2021 at 18:50
2
$\begingroup$

This is maybe not a totally explicit answer, but for any nontrivial subshift $X$ (meaning $|X| > 1$) which is totally minimal, any sequence $x \in X$ should have your property. Here, totally minimal means that for any non-zero power $k$ of the shift $\sigma$, the associated topological dynamical system $(X, \sigma^k)$ is minimal (and a dynamical system is minimal if there are no nonempty proper closed subsets of $X$ invariant under the action).

To see this, just note that if $x \in X$ and there were arbitrarily long subwords of some $x_{a \pmod k}$ which were constant, then by taking limits and shifts, there would be a point $y \in X$ for which $y_{a \pmod k}$ is constant, say all $b$s. Then, define the subset $Y \subset X$ of all such sequences. $Y$ is nonempty, closed, and must be a proper subset of $X$; if all sequences in $X$ had $b$s at all indices in $a + k\mathbb{Z}$, then by invariance of $X$ under $\sigma$, the only sequence in $X$ would be all $b$s, and we assumed $|X| > 1$. So, $Y$ is a nonempty closed proper subset of $X$ invariant under $\sigma^k$, contradicting total minimality of $X$.

So, indeed all sequences in such $X$ have your property. And there are many examples of totally minimal subshifts. One is indeed the Sturmian shifts from zeb's answer. Also, any minimal topologically weak mixing system is totally minimal (this is from "The structure of weakly mixing minimal transformation groups" by Keynes), so for instance the Chacon subshift generated by the substitution $0 \mapsto 0010, 1 \mapsto 1$ (which is known to be weak mixing and minimal) should also be totally minimal. I think that all non-constant length substitutions should generate totally minimal subshifts under some weak 'nontriviality' hypotheses, but am not sure about this. I'm sure someone else might know of larger classes of/constructions for totally minimal subshifts.

Improve this answer
$\endgroup$

You must log in to answer this question.

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