Factorizable embeddings and the period of an irreducible sofic shift

Brian Marcus, Tom Meyerovitch, Klaus Thomsen, Chengyu Wu · 2025

Read Factorizable embeddings and the period of an irreducible sofic shift by Brian Marcus, Tom Meyerovitch, Klaus Thomsen, Chengyu Wu (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-2508-02554.txt.

Introduction

Brian Marcus, Tom Meyerovitch, Klaus Thomsen, and Chengyu Wu tackle a pure math question about when one pattern system can sit inside another, in a 2025 paper. The systems, called shifts, are sets of endless symbol strings that obey set rules. A key trait they study is the period, a number that captures how a system cycles.

The authors give exact tests for when a system can be placed inside a well-behaved target system through set maps. They cover maps that must cover the target, maps that must not merge points, and maps with no such limits. The results sharpen tools that classify these systems and settle cases left open by earlier work.

Catalog record

CREATORBrian Marcus, Tom Meyerovitch, Klaus Thomsen, Chengyu Wu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-02554

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Factorizable embeddings and the period of an irreducible sofic shift Brian Marcus, Tom Meyerovitch, Klaus Thomsen, Chengyu Wu Abstract . Generalizing a result of MacDonald we give necessary and sufficient conditions for an arbitrary subshift to embed into an irreducible sofic shift factoring through a given cover by an irreducible subshift of finite type (SFT). We obtain also necessary and sufficient conditions for an arbitrary subshift to embed into an irreducible sofic shift factoring through some sliding block code out of an irreducible SFT. We do that when the code is required to be surjective, and hence a factor code, and when it is required to be injective or is allowed to be arbitrary. These results require concepts of the period of an irreducible sofic shift as well as a concept of a p p -periodic subshift. Several equivalent formulations of the period are developed. 1. Introduction A celebrated theorem of Wolfgang Krieger, [ Kr1 ] , gives necessary and sufficient conditions for a subshift to embed into a given mixing SFT of larger entropy. To formulate it, let Q_{n}(X) denote the set of periodic points of least period n in a subshift X and let q_{n}(X):=\#Q_{n}(X) be the number of elements in Q_{n}(X) . Then Krieger’s theorem reads as follows: Theorem 1.1 . (W. Krieger) Let Z be a subshift and Y a mixing SFT such that h(Z)<h(Y) . Then Z embeds into Y if and only if q_{n}(Z)\leq q_{n}(Y) for all n\in\mathbb{N} . Since a proper subshift of an irreducible SFT must have strictly smaller entropy, Krieger’s theorem gives in fact both necessary and sufficient conditions for a subshift to embed into a mixing SFT. It is striking that the rather obvious necessary condition on the periodic points is also sufficient when h(Z)<h(Y) . Despite much effort and several partial results, no one has been able to give necessary and sufficient conditions for a subshift to embed into an arbitrary given sofic shift, be it irreducible or mixing. The lesson seems to be that although sofic shifts may appear to be only slight generalizations of SFTs, they contain a much more rigid internal structure; a structure which is still not fully understood. Nonetheless, a stronger version of embedding can be considered: Definition 1.2 . Let X,Y and Z be subshifts and \pi:X\to Y a sliding block code. Let \phi:Z\to Y be an embedding. We say that \phi factors through \pi if there is a sliding block code \psi:Z\to X making the following diagram commute: \textstyle{X\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{\pi} \textstyle{Z\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces} \scriptstyle{\psi} \scriptstyle{\phi} \textstyle{Y} (1.1) Note that \psi is automatically an embedding. When \pi is surjective, X is an irreducible SFT and Y is, consequently, an irreducible sofic shift, we refer to \pi:X\to Y as a cover of Y . In her thesis Sophie MacDonald considered the following problem: Given a cover \pi:X\to Y of Y , where X , and hence also Y , is mixing, when can a subshift Z with h(Z)<h(Y) be embedded into Y in such a way that the embedding factors through \pi ? Given the difficulty others have encountered when trying to embed into an arbitrary sofic shift, and despite that the problem she considered seems to be more complicated because it is asking for a specific type of embedding, MacDonald was able to give the following simple answer: Let r_{n}(\pi):=\#Q_{n}(Y)\cap\pi(Q_{n}(X)) . Then the desired embedding exists if and only if q_{n}(Z)\leq r_{n}(\pi) for all n\in\mathbb{N} . Theorem 1.3 . (MacDonald’s Theorem [ M ] ) Let \pi:X\to Y be a factor code from a mixing SFT X to a sofic shift Y . Let Z be a subshift such that h(Z)<h(Y) . Then, there is an embedding from Z into Y which factors through \pi if and only if q_{n}(Z)\leq r_{n}(\pi) for all n\in\mathbb{N} . As with Krieger’s theorem, an obvious necessary condition concerning periodic points turns out to be sufficient for the embedding in Theorem 1.3 . The condition is closely related to a condition involving the concept of a receptive periodic point (see Definition 4.4 ), which Boyle [ B ] used as a sufficient condition for an ordinary embedding of a subshift into a mixing sofic shift. In effect, MacDonald’s result gives a related necessary and sufficient condition for a stronger notion of embedding, i.e., an embedding which factors through a given factor code on a mixing SFT X . The first objective of the present paper is to extend MacDonald’s Theorem to the case where X is merely an irreducible SFT and to give both necessary and sufficient conditions also in that case. This is achieved in Theorem 3.9 , along with a second version, Theorem 3.11 where there is no assumption on the entropies. The proofs of these results are similar in spirit, but somewhat simpler, than MacDonald’s proof. One virtue of our approach, besides its greater generality, is that it allows us to use the statement of Krieger’s theorem rather than modifying its proof. Along the way, in Proposition 3.7 , we generalize also Krieger’s original theorem to the case where the target shift space is an irreducible, but not necessarily mixing, SFT. For this the notion of p -period for a general subshift is introduced as a necessary part of the assumptions. See Definition 3.6 . MacDonald’s Theorem was, in part, motivated by the following setup. In information theory, a communication channel is modeled using a set of transition probabilities, with the input and output described by stationary probability measures. The channel’s noise arises from the randomness of its transition probabilities. When there is no noise, the channel is referred to as a distortion channel, which, from the perspective of symbolic dynamics, can, in an abstract way be interpreted as a factor code from a subshift of channel inputs to a subshift of channel outputs. We can then view the problem of encoding messages through the channel as the problem of embedding a subshift of messages into the domain of the factor code such that the restriction of the factor code to the range of the embedding is one-to-one. The second aim of the paper is to find necessary and sufficient conditions for an arbitrary subshift Z to embed into an irreducible sofic shift Y in such a way that the embedding factors through some sliding block code \pi:X\to Y out of an irreducible SFT X . We obtain such a characterization in Theorem 4.18 and Theorem 4.20 , when there are no conditions on \pi , when it is required to be injective and finally also when it is required to be surjective. A crucial ingredient in Theorem 4.18 and Theorem 4.20 is a new notion of period for an irreducible sofic shift. In Section 5 , we consider several additional notions of a period for an irreducible sofic shift and show that these are all equivalent. We also consider the concept of a p -periodic subshift, as mentioned above, which applies to general subshifts. We show that p -periodicity is rather different from the notion of period in the case where the subshift is irreducible sofic. We recently became aware of a related paper by Wolfgang Krieger [ Kr2 ] . 2. Notation, terminology, and background

Read the complete text