Think of a one-dimensional infinite walk as a map $$w\colon \mathbb{N}\to \{-1,1\}.$$ (If it is more convenient, you can think of a walk as a subset of $\mathbb{N}$, or as a binary word, or as any other convenient model.) Similarly, a finite walk, say of $n$-steps (for some integer $n\geq 1$), is a map $$v\colon [0,n-1]\cap \mathbb{N}\to\{-1,1\}.$$

Given a finite walk $v$, with exactly $n$ steps, let us say that is is nondecreasing if $\sum_{i=0}^{n-1}v(i)\geq 0$. Define nonincreasing finite walks dually, using $\leq$.

Given an infinite walk $w$, and a finite (nonempty) set $S$ of finite walks, let us say that $w$ avoids using $S$ too often, if there is some positive integer $N$ (depending on $w$ and $S$) so that if we concatenate any $N$ elements of $S$ (allowing repetitions), then such a concatenated finite walk does not appear as a (consecutive) subwalk in $w$.

For example, if $S=\{v_0\}$ where $v_0$ is the $1$ step walk where $v_0(0)=1$, and if $w$ is the walk where $w(i)=(-1)^{i}$, then we can take $N=2$, and we see that $w$ avoids using $S$ too often. Or in in terms of binary words, the infinite binary word $01010101\ldots$ does not have arbitrarily long strings of consecutive $1$s.

Of course, there exists an infinite walk that avoids using too often any finite set of nondecreasing finite walks. Just take $w$ to be the strictly decreasing walk where $w(i)=-1$.

My question is whether the following balancing act is possible.

Does there exist an infinite walk $w$, such that for every finite set $S$ of nondecreasing finite walks, as well as for every finite set $S$ of nonincreasing finite walks, $w$ avoids using $S$ too often?

  • $\begingroup$ Doesn't $010011000111\dots$ work? $\endgroup$ Apr 24 at 18:01
  • $\begingroup$ @CommandMaster No, because if we take $S=\{1\}$, then $N$-fold concatenations of $S$ occur for every positive integer $N$. $\endgroup$ Apr 24 at 18:06
  • $\begingroup$ Right. The Thue-Morse sequence is cube free, so it should work with $N=3$. $\endgroup$ Apr 24 at 18:58
  • $\begingroup$ Oh, nevermind, it only works for $|S|=1$, it fails for $10,01$. $\endgroup$ Apr 24 at 19:14
  • $\begingroup$ @CommandMaster Right, this is a sort of generalization of cube-free-ness, which gets tricky for sets of words. $\endgroup$ Apr 24 at 20:21

1 Answer 1


The limit of the following sequences probably works:

  • $A_0 = \varepsilon$
  • $A_i = (A_{i-1}0)^{2^{(i^2)}}A_{i-1}(1A_{i-1})^{2^{(i^2)}}$

Intuition: For every $S$, there exists some $A_i$ which is not a factor of a word in $S^*$, because it has parts that are increasing/decreasing too much. However note that $A_n \in (A_i(0|1))^*A_i$ for all $n \geq i$. Thus we can pick $N = 2|A_i|$.

  • 2
    $\begingroup$ This is a beautiful answer! (I think you can remove the word "probably", and change "Intuition" to "Proof".) Also, am I right in thinking that $2^{(i^2)}$ can be replaced by any unbounded positive sequence? $\endgroup$ Apr 24 at 21:48
  • $\begingroup$ Maybe it is not necessary. However, the words in $S$ can have different sizes, so I would like the fluctuation within $A_i$ to be more than any constant factor greater than the fluctuation in $A_{i-1}$ just to be safe. Something like $2^{\omega(i)}$ should be sufficient. $\endgroup$
    – 1001
    Apr 24 at 21:54
  • 2
    $\begingroup$ On second thought, yes you are right. Any unbounded positive sequence will do. $\endgroup$
    – 1001
    Apr 24 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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