On the subsystems of certain almost Markov shifts
Wolfgang Krieger · 2025
Read On the subsystems of certain almost Markov shifts by Wolfgang Krieger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-02717.txt.
Introduction
Wolfgang Krieger wrote a short note in 2025 on subsystems of certain sofic shifts, under a head title that differs from the catalog's Markov shift title. A past theorem of his, from 1982, gives a condition on periodic points for embedding one shift system into another. That condition is both needed and enough when the target is a shift of finite type and the source has lower entropy. The note shows the theorem extends to certain sofic shifts as targets, widening its use.
Catalog record
| CREATOR | Wolfgang Krieger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 12 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-02717
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the subsystems of certain almost Markov shifts Wolfgang Krieger Abstract . For an aperiodic subshift of finite type Y Y and for a subshift X X with topological entropy less than the topological entropy of Y Y , it was proved in Krieger: On the subsystems of topological Markov chains, Ergodic Theory & dynamical systems 1982 𝟚 \mathbb{2} , 195-202, that the necessary condition on the periodic points of X X and Y Y for the existence of an embedding of X X into Y Y is also sufficient for the existence of an embedding of X X into Y Y . In this note we extend this theorem to a certain class of almost Markov shifts as target shifts. Let \Sigma be a finite alphabet, and let S_{\Sigma} denote the left shift on \Sigma^{\mathbb{Z}} Given an S_{\Sigma} -invariant subset X of \Sigma^{\mathbb{Z}} the restriction S_{\Sigma} of S_{\Sigma} to X is called a subshift. For basic notions of the theory of subshifts we refer to [ Ki ] or [ LM ] . Denote the set of periodic points of period n of a subshift X by P_{n}(X) and denote the topological entropy of X by h(X) . Use {{\operatorname{card}}} as notation for the cardinality of a set. In [ Kr1 ] the following theorem was proved. Theorem 1 . Let Y be an aperiodic subshift of finite type and let X be a subshift such that h(X)<h(Y) . Then there exists an embedding of X into Y if and only if {{\operatorname{card}}}(P_{n}(X))\leq{{\operatorname{card}}}(P_{n}(Y)),\quad\quad\quad n\in\mathbb{N}. In [ B ] there is an example that shows that Theorem 1 does not extend to all mixing sofic shifts as target shifts. In this paper we prove a theorem that extends Theorem 1 to a certain class of almost Markov shifts (AFT-shifts, see [ M ] ) as target shifts. Before we state this Theorem 2 we introduce more notation and terminology for subshifts and we recall the notion of an almost Markov shift Given a subshift X\subset\Sigma^{\mathbb{Z}} , and I^{-},I^{+}\in\mathbb{Z},I^{-}\leq I^{+} we call (\sigma_{i})_{I^{-}\leq i\leq I^{+}}\in\Sigma^{[I^{-},I^{+}]} a block and we use the notation x_{[I^{-},I^{+}]}=(x_{i})_{I^{-}\leq i\leq I^{+}},\quad\quad\quad x\in X, and the notation X_{[I^{-},I^{+}]}=\{x_{[I^{-},I^{+}]}:x\in A\}. We use similar notations in the case that indices range in left infinite or right infinite intervals. We use the same notation for a block in X_{[I^{-},I^{+}]} and for the word that the block carries. The language of admissible words of a subshift X we denote by \mathcal{L}(X) . We set \Gamma^{+}(a)=\{x^{-}\in X_{(j,\infty)}:ax^{-}\in X_{[i,\infty)}\},\quad a\in x_{[i,j]},\quad i,j\in\mathbb{Z},i\leq j. The notation \Gamma^{-} has the symmetric meaning. A word c\in\mathcal{L}(X) is synchronizing if one has for u^{-}\in\Gamma^{-}(C) and u^{-}\in\Gamma^{-}(C) that u^{-}cu^{-}+\in X . We introduce notation and terminology for labelled directed graphs. We denote a finite directed graph with vertex set {\mathfrak{V}} and edge set {\mathcal{E}} by G(\mathfrak{V},\mathcal{E}) . As notation for the source vertex and target vertex of an edge or path in a directed graph we use {{\operatorname{src}}} and {{\operatorname{trg}}} . A \Sigma -labelled directed graph is called 1-right resolving if for every vertex V and every label \sigma\in\Sigma there is at most one edge that leaves V and that carrries the label \sigma . The edge shift of the 1-right resolving \Sigma -labelled directed graph G(\mathfrak{V},\mathcal{E}) is the set of bi-infinite directed paths in the graph that is equipped with the left shift. We recall a construction of the Fischer cover [ F ] . For a sofic system Y\subset\Theta^{\mathbb{Z}} the (right) Fischer cover of Y is given by a 1-right resolving \Theta -labelled directed graph G(\mathfrak{V}(Y),\mathcal{E}(Y)) that has as its vertex set \mathfrak{V}(Y) the set \Gamma^{+}(c),c a synchronizing words of Y . A vertex V\in\mathfrak{V}(Y) accepts the symbol \vartheta\in\Theta as input precisely if there is a right-infinite sequence in V that starts with \vartheta , and the target vertex of the edge in \mathcal{E}(Y)) that leaves V and that carries the label \vartheta is the set of right-infinite sequences (\vartheta_{k})_{k>1} that are obtained from a right-infinite sequence (\vartheta_{k})_{k\in\mathbb{N}} such that \vartheta_{1}=\vartheta by removing its initial symbol \vartheta §. We denote by C_{Y} the edge shift of the graph G(\mathfrak{V}(Y),\mathcal{E}(Y)) and we denote by \varphi_{Y} the projection of C_{Y} onto Y that assigns to a bi-infinite path in C_{Y} its label sequence. The extension of Y that is given by \varphi_{Y} is the Fischer cover of Y . This extension is canonical [ Kr2 ] . The sofic system Y is said to be almost Markov [ BK ] if the graph G(\mathfrak{V}(Y),\mathcal{E}(Y)) is left resolving. Concerning the canonicity of the Fischer cover of almost Markov shifts see also [ BKM ] . We state Theorem 2. Theorem 2 . Let Y be an aperiodic almost Markov subshift such that every periodic point p of Y has an inverse image under \varphi_{Y} of the same period as p . Let X be a subshift such that h(X)<h(Y) . Then there exists an embedding of X into Y if and only if {{\operatorname{card}}}(P_{n}(X))\leq{{\operatorname{card}}}(P_{n}(Y)),\quad\quad\quad n\in\mathbb{N}. The hypothesis of Theorem 2 on the periodic points of the sofic system Y is part of the periodic data [ BK ] of the Fischer cover of Y and is therefore invariant under topological conjugacy. The following graph1 is an example of an almost Markov system that satisfies the hypothesis: graph1 U_{1} U_{2} V_{1} V_{2} \beta \alpha 1 0 0 0 1 With very minor modifications the proof of Theorem 1 as given in [ Kr1 ] yields also a proof of Theorem 2. For completeness we describe a proof of Theorem 2 that is a modified version of the proof in [ Kr1 ] . Let there be given a mixing almost Markov shift Y that satisfies the hypothesis of Theorem 2. We consider the set of paths in the graph G(\mathfrak{V}(Y),\mathcal{E}(Y)) . We construct a path a such that no proper prefix of a is a suffix of a , and such that the label sequence o a is a resolving word. If there is a path \beta\alpha\alpha with distinct edges \alpha and \beta , then let b be a path with initial edge \beta and suffix \beta\alpha and a label sequence that is a resolvent word of Y . Denote the length of b by \mu(b) and set a=b\alpha^{\mu(b)}. Otherwise let \alpha be an edge that can be followed by distinct edges \beta and \gamma that are distinct from \alpha . Choose paths \alpha b\alpha and \alpha c\alpha of shortest length such that the initial edge of the path b is \beta and the initial edge of the path c is \gamma . Let d be a path with the prefix \alpha c and the suffix \alpha c\alpha b and a label sequence that is a resolving word of Y . Denote the length of d by \nu(d) and set a=(\alpha b)^{\nu(d)} . For some K\in\mathbb{N} , choose for vertices U,W\in\mathfrak{V}(Y) a path c(U,W) from U to W . Denote by \mathcal{D}_{n}(a) the set of paths of length n that do not traverse the path a . Denote by L the length of a . By means of the Perron-Frobenius Theorem one derives that \lim_{l\to\infty}\frac{{{\operatorname{card}}}(\mathcal{L}_{l-2(L+K)}(C_{Y}))-{{\operatorname{card}}}(\mathcal{D}_{l-2(L+K)}(a))}{{{\operatorname{card}}}(\mathcal{L}_{l}(X))}=\infty. This means that we can choose an \ell>2(L+K) such that \mathcal{L}_{l}(X)\subset\mathcal{L}_{l-2(L+K)}(C_{Y})\smallsetminus\mathcal{D}_{l-2(L+K)}(a),\quad\quad\quad l\geq\ell. For \ell\leq l\leq 4\ell