MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X$ be a one-dimensional one-step irreducible shift of finite type and let $\pi$ be a one-block factor code from $X$ to a sofic $Y$. Suppose $y$ is a right transitive point of $Y$ and $\pi(u)=y$ for some $u\in X$. Given $u_0=a$ and a block $B$ of $X$, is there a point $x\in\pi^{-1}(y)$ such that $x_0=a$ and $B$ occurs in $x_{[0,\infty)}$? (Note that the stronger statement is true when $\pi$ is a finite-to-one code: a point is transitive if and only if it's image under $\pi$ is transitive, so $B$ actually occurs infinitely often in the right of $x$.) Thanks to the helpers.

share|cite|improve this question
up vote 3 down vote accepted

Sorry that this is slightly technical... It's uses some concepts that Mahsa showed me in answering a more simple question that I asked her.

Using results from, we may assume that there exists a 'magic symbol' $k\in Y$ satsisfying that for any word $y_m\cdots y_n\in Y$ with $y_m=y_n=k$, we have that any word $x_m\cdots x_n\in X$ with $\pi(x_m\cdots x_n)=(y_m\cdots y_n)$ can be extended to a sequence $x\in X$ with $\pi(x)=y$. This is not actually the definition of magic symbol but a theorem about them, see the above paper for a definition.

We assume that the desired word $B$ in $X$ starts and finishes with elements of $\pi^{-1}(k)$, if not we just extend the word $B$ a little bit. We let $B=b_1\cdots b_m$ and $C=\pi(B)$.

Let $A=\{a^1,\cdots,a^j\}$ be the set of possible values of $x_1$ for words $x_1\cdots x_m$ with $\pi(x_1\cdots x_m)=C$. Clearly $b_1\in A$, we let $a^1=b_1$.

We begin with the following lemma:

\begin{lemma} There exists a word $W=w_1\cdots w_n$ in $Y$ with $w_1=w_n=k$ such that for each $a\in A$ there exists a word $V=v_1\cdots v_n\in X$ with $\pi(V)=W$, $V$ contains $B$ and $v_1=a$. \end{lemma}

To prove the lemma we define $W=w_1\cdots w_{i_j}$ in chunks which deal with the possible values of $v_1\in A$.

We let $w_1\cdots w_{i_1}$ be the word $C$. Then for $v_1=a^1$ we are done, since $B$ is a preimage of $C$ which starts with $a^1$. Since $B$ starts and finishes with elements of $\pi^{-1}(k)$ it can be extended to a sequence $x$ projecting to $y$.

Now we deal with $a^2$. By the definition of $A$, there exists a preimage of $C$ starting with $a^2$. By the transitivity of $X$, this preimage, which is a finite word in $X$, can be extended to be another finite word in $x_1\cdots x_{i_2}\in X$ which finishes with word $B$. We let $w_1\cdots w_{i_2}=\pi(x_1\cdots x_{i_2})$, noting that $i_2>i_1$ and $\pi(x_1\cdots x_{i_1})=w_1\cdots w_{i_1}$, so there is no conflict with the values of $W$ which we already defined.

Now we do the same trick for $a^3$. There is a preimage of $w_1\cdots w_{i_1}$ $(=c_1\cdots c_m)$ starting with $a^3$, and hence there must be a preimage of $w_1\cdots w_{i_2}$ starting with $a^3$, because $w_1, w_{i_1}$ and $w_{i_2}$ are all equal to the magic symbol $k$. Let $x_1\cdots x_{i_2}$ be this word, and because $X$ is transitive we can extend it to a finite word $x_1\cdots x_{i_3}$ in $X$ finishing with block $B$. Let $w_1\cdots w_{i_3}=\pi(x_1\cdots x_{i_3})$.

We continue this process until we have a word $W=w_1\cdots w_{i_j}$, this word $W$ satisfies the conditions of the lemma, so the lemma is proved.

Now let $y\in Y$ be a transitive sequence. Then $y$ contains the word $W$, say $y_l\cdots y_{l+i_j}=W$. For our desired starting symbol $u$ there exists a word $x_1\cdots x_l$ with $x_1=u$ and $\pi(x_1\cdots x_l)=y_1\cdots y_l$, since there exists a preimage of $y$ starting with $u$. $x_l$ will be some member of $A$, and then using the lemma we can extend $x_1\cdots x_l$ to a sequence which contains $B$ and projects to $y$ as required.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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