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

  • 1
    $\begingroup$ 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. :-) $\endgroup$ – Johannes Hahn Jul 15 '14 at 18:47
  • $\begingroup$ Thanks, I changed the title and I removed my extra words. $\endgroup$ – user39115 Jul 15 '14 at 18:49
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Jul 15 '14 at 20:01
  • $\begingroup$ 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 $\endgroup$ – 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$.

| cite | improve this answer | |

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.