# A problem in symbolic dynamics

I got a fun problem.

Define the alphabet $\mathcal{A}=\{0,1,2\}$ and the set $\mathcal{A}^{\leq n}=\{ x_1x_2\ldots x_n: x_i\in \mathcal{A}\}$ of words of length $n,$ for each $n\in\mathbb{N}.$

Suppose that for each $n\in \mathbb{N}$ somebody selects a set $X_n$ of $2^n$ points of $\mathcal{A}^{\leq n}.$

Is it true that there exist a function of linear growth $f:\mathbb{N}\to \mathbb{N},$ a set $\{y^{n}\}_{n\in K} \subset \mathcal{A}^{\mathbb{N}}$ of infinite cardinality with $K\subset \mathbb{N}$ and for each $n\in K$ a set $Y_n\subset X_n$ with cardinality $|Y_n|\leq f(n)$ such that any sub word of $y^n$ with length $n$ belongs to $Y_n?$

(My unique intuition is that it is false. And that it should be possible to create by hand the bad sets $X_n,$ however the proof does not seem clear to me yet. I also think that it could be true a.s., my only guess is to try to use a kind of Borel-Cantelli lemma.)

• The title (and tagging) of the question bothers me. Either tell us what that application in ergodic theory is or don't, but don't tease us. :-) – Johannes Hahn Jul 15 '14 at 18:47
• Thanks, I changed the title and I removed my extra words. – user39115 Jul 15 '14 at 18:49
• If y is a fixed word of length k, and you are only looking at subwords of length n of y^n, you will have at most k distinct subwords. Thus, for large n, the challenge will not be finding a linear growth function. It will be finding a y that "threads" through all the sets X_n. If I am careful, I think I can find m such that no mth power will be a substring of any member of any X_n. Gerhard "Guesses The Answer Is 'No'" Paseman, 2014.07.15 – Gerhard Paseman Jul 15 '14 at 20:01
• To be clear, I think there are sets X_n for which your desired condition will not hold because the sets X_n will avoid mth powers for sufficiently large m. However, the obvious thing to try (take jth character to avoid symbol a[j]) does not make it clear that one can avoid mth powers. Gerhard "Ask Me About Powerful Strings" Paseman, 2014.07.15 – Gerhard Paseman Jul 15 '14 at 20:07

An easy procedure to obtain a somewhat stronger result is the following: Consider those words of length $n$ that have exactly one $2$, and this $2$ is not in position $1$. There are $(n-1)2^{n-1}$ such words, which is already more than we need to form $X_n$. Make an arbitrary selection of $2^n$ such words to define $X_n$.
Then any $y^n$ that could be considered as a candidate to have subwords from $Y_n=X_n$ only (we don't have to make $X_n$ smaller) has $2$'s in it and thus has subwords with a $2$ in position $1$, which are not in $X_n$.