# Mixing coded systems and period of their graph presentations

A coded system [see F. Blanchard, G. Hansel, Systèmes codés, Theoretical Computer Science, Vol. 44, 1986, pp. 17-49, http://dx.doi.org/10.1016/0304-3975(86)90108-8. (http://www.sciencedirect.com/science/article/pii/0304397586901088)] is a shift space $X$ which admits a cover (a presentation) by a countable labeled strongly connected (irreducible) directed graph $(G, g)$ where a labeling function maps the edge set of $G$ into a finite set $A$. This means that $X$ is the closure of the image of the map $L_g \colon S_G \to A^\mathbb{Z}$ induced on the countable Markov shift $S_G$ of all bi-infinite paths in G by $L_g(x)_i := g(x_i)$, $i \in \mathbb{Z}$, $x \in S_G$. In Lind and Marcus book An introduction to symbolic dynamics and coding, page 451 there are some other equivalent conditions.

A coded system is transitive by definition. A synchronized system is a transitive shift space $X$ which has a synchronizing block $v$, that is $v$ is an admissible block for $X$ and whenever $vw$ and $uv$ are admissible blocks in $X$ then $uvw$ is also admissible. Every transitive sofic shift is synchronized. A synchronized system is well-known to be coded. Moreover, any synchronized system admits a presentetion by a connected, right-resolving, follower separated labeled graph with a magic word (known as the Fisher cover).

It is relatively easy to prove that a synchronized system is topologically mixing if and only if there are two closed paths in its Fisher cover of relatively prime lengths. Does the same hold for coded systems? It is easy to see that two closed paths in $G$ with relatively prime lengths imply that the shift space presented by $G$ is mixing, but how about the converse? I mean, does every mixing coded system has a presentation with two closed paths of relatively prime lengths?

Note: The equivalence holds if $G$ is finite, but I am interested in the case, when $G$ may be infinite.

Edit There exists a presentation of a full shift such that every loop has even length. But there are presentations of the full shift with two closed paths of relatively prime lengths.

• An equivalent charcterization of coded systems says that a shift space $X$ is a coded system if there exist a countable collection of finite words (blocks) $(w_n)_{n\in\mathbb{N}}$, called generators, such that $X$ is the closure of the set of sequences obtained by freely concatenating the generators. The question above can be then restated as follows: Does every mixing coded system have a set of genertaors $(w_n)_{n\in\mathbb{N}}$ such that $\text{gcd} \{|w_n| : n\in\mathbb{N}\}=1$? ($|w|$ is the length of a word (block) $w$). – Dominik Kwietniak Feb 9 '14 at 23:27
• What does happen when you have a mixing coded system $X$ with generators $(w_n)_{n\in\mathbb{N}}$ and you add a new block w, i.e. you consider $X'$ that corresponds to the closure of the sets of sequences obtained by freely concatenating words in $(w_n)_{n\in\mathbb{N}}$ and $w$ ? Is the mixing property preserved? – user39115 Mar 27 '14 at 18:54
• Usually yes. If there are two generators with relatively prime lengths, then after adding any block the system would still be mixing. – Dominik Kwietniak Mar 31 '14 at 8:13

In general no! Let $X=\{0,\,1\}^{\mathbb{Z}}$ be the full shift generated by $\{00,\,10,\,01,\,11\}$ and set $w=12$ and let $\sigma_{X'}$ be the shift map on $X'$. Then $N(w,\,w)=\{n: {\sigma}_{X'}^nw\cap w\neq\emptyset\}=2\mathbb{N}$ and it is not a cofinite set as required for a mixing system.
If you do not sure that $(w_n)$, the generator of mixing coded, has relatively prime lengths or there is at least one $w_i\in (w_n)$ s.t. $gcd(w_i,\,w)=1$, we can not say that the new coded system which generated by $(w_n)$ and $w$ is mixing!