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

CREATORWolfgang Krieger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text