1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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
    Commented Jul 15, 2014 at 18:47
  • $\begingroup$ Thanks, I changed the title and I removed my extra words. $\endgroup$
    – user39115
    Commented Jul 15, 2014 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
    Commented Jul 15, 2014 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
    Commented Jul 15, 2014 at 20:07

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

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