# Balancing act for infinite walks

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?

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

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

• 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? Apr 24 at 21:48
• 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.
– 1001
Apr 24 at 21:54
• On second thought, yes you are right. Any unbounded positive sequence will do.
– 1001
Apr 24 at 22:03