# Relative irreducibility

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.

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 http://arxiv.org/abs/1001.5323v1, 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.