A Krieger Embedding Theorem for Near Markov Sofic Shifts
Brian Marcus, Tom Meyerovitch, Chengyu Wu · 2026
Read A Krieger Embedding Theorem for Near Markov Sofic Shifts by Brian Marcus, Tom Meyerovitch, Chengyu Wu (2026) 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-2606-25475.txt.
Introduction
Symbolic dynamics studies infinite symbol streams cut by rules, and a classic theorem of Krieger says exactly when one rule system can be embedded inside a mixing shift of finite type. Brian Marcus, Tom Meyerovitch, and Chengyu Wu extend that result in 2026 to a broader target class, near Markov sofic shifts. Sofic shifts are the labelled projections of finite type systems, and the plain theorem fails for them, as a simple even shift example shows. Near Markov shifts form a special, well behaved subclass defined without reference to any presentation.
Generalised Krieger conditions, comparing entropy and periodic point counts, become necessary and sufficient for embedding into such targets. When the system being embedded is itself irreducible and sofic, the conditions can be checked by a finite procedure. The work is dedicated to Benjamin Weiss, who discovered sofic shifts, on his eighty fifth birthday.
Catalog record
| CREATOR | Brian Marcus, Tom Meyerovitch, Chengyu Wu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25475
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Krieger Embedding Theorem for Near Markov Sofic Shifts Brian Marcus, Tom Meyerovitch, Chengyu Wu Abstract . Krieger’s classical embedding theorem gives necessary and sufficient conditions for embedding a subshift into a mixing shift of finite type (SFT) as a proper subshift. The same result does not hold if one replaces mixing SFT by a mixing sofic shift. In this paper, we generalize Krieger’s conditions to give necessary and sufficient conditions for embedding a subshift into a mixing (in fact irreducible) near Markov sofic shift (a special conjugacy-invariant class of sofic shifts). We also show that if the subshift to be embedded is irreducible sofic, then the conditions are finitely decidable. Dedicated to Benjamin Weiss on the occasion of his 85th birthday. We are forever grateful for his discovery of sofic shifts. 1. Introduction For a subshift X , let h(X) be the topological entropy of X and q_{n}(X) denote the number of periodic points of least period n in X . Krieger’s celebrated embedding theorem, characterizes the subshifts that can be embedded as a proper subshift of a mixing shift of finite type (SFT). Theorem 1 . (W. Krieger [ Kr1 ] ) 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} . This indeed gives a characterization of proper embeddings of subshifts into mixing SFTs because an embedding from a subshift Z into a mixing SFT Y is proper iff h(Z)<h(Y) . Krieger’s embedding theorem is one of the most central and important results in symbolic dynamics, with a wide range of applications. The necessity of the periodic point condition is trivial, as is the entropy inequality. It is the sufficiency of the conditions that is the heart of the theorem, namely the construction of an embedding. Roughly speaking, the periodic point condition enables a “local” embedding on a “periodic part” of Z and the entropy condition enables a “local” embedding on the “non-periodic part” of Z ; a globally synchronizing property, using that Y is a mixing SFT, enables the “gluing together” of the local embeddings. Terminology used in Theorem 1 above and terminology below will be defined in Section 2 . It is not hard to see that Krieger’s embedding theorem does not hold in general when the target is mixing sofic instead of being a mixing SFT. Indeed, let Y be the even shift, i.e., the subshift over the alphabet \{0,1\} such that 10^{k}1 is allowed iff k is even. Let Z be an irreducible SFT containing exactly two fixed points and q_{n}(Z)\leq q_{n}(Y) for all n and h(Z)<h(Y) . If Z embeds into Y , then Z is conjugate to an irreducible sub-SFT U contained in Y , and U contains both 0^{\infty} and 1^{\infty} . Let k be an integer greater than the memory of U as an SFT. Then, by the irreducibility of U , for all k , 10^{k} and 0^{k}1 are both in the language of U . But this implies that 10^{k}1 is allowed in U , contradicting the definition of Y as the even shift. Thus, to see that Krieger’s embedding theorem does not hold for Y as the target shift, it suffices to find a subshift Z satisfying the requirements above. The existence of such a Z is fairly clear. An explicit such Z is given by the edge shift defined by the finite directed graph in Figure 1 below. Here, we have h(Z)\approx\log 1.46557 , which is less than h(Y)=\log\frac{\sqrt{5}+1}{2} . By the estimates in [ LM , Page 351] one obtains that q_{n}(Y)\leq q_{n}(W) for all n\geq 14 , where W is the golden mean shift. Since q_{n}(W)=q_{n}(Y) for all n\geq 2 , we have q_{n}(Z)\leq q_{n}(Y) for all n\geq 14 . By direct computation, one can verify that q_{n}(Z)\leq q_{n}(Y) for all 1\leq n<14 (note that this holds trivially for 1\leq n\leq 5 since q_{1}(Z)=2=q_{1}(Y) and for 2\leq n\leq 5 , q_{n}(Z)=0 ). Thus, by the argument above, Z does not embed into Y . Figure 1. The edge shift Z This phenomenon has been known since the time of Krieger’s embedding theorem; indeed, see [ B , Example 3.1] for a more elaborate example Y . Recently, Krieger [ Kr3 ] showed that for some special classes of (non-SFT) sofic shifts Y his original necessary conditions are sufficient for proper embedding. The main results of our paper, Theorem 7 (characterization of embeddings) and Theorem 24 (decidability of characterization), give a complete and finitely decidable characterization of existence of proper embeddings of irreducible sofic shifts into a given target sofic shift Y in a conjugacy-invariant class. This is the class of near Markov shifts, which are defined as those that can be presented as a factor of an irreducible SFT which is one-to-one off of a finite set. These are, in some sense, the sofic shifts that are as close to being SFTs, without actually being SFTs. This class includes the even shift and other irreducible sofic shifts defined by forbidding words in the union of a finite list of words and a finite list of congruence conditions. Our conditions are necessarily stronger than Krieger’s original necessary conditions when the target shift is a near Markov shift that is not of finite type. In the case when the target shift Y is the even shift, our main result, Theorem 7 , reduces to the proposition below, which is proven at the end of Section 3 . Proposition 2 . Let Z be a subshift. Then Z embeds into the even shift Y if and only if one of the following conditions hold: (1) Z is conjugate to Y . (2) h(Z)<h(Y) , Z has at most 1 fixed point, and q_{n}(Z)\leq q_{n}(Y) for all n\geq 2 . (3) h(Z)<h(Y) , Z has exactly 2 fixed points, q_{n}(Z)\leq q_{n}(Y) for all n\geq 2 , and Z admits a 2 -blowup at one of the fixed points of Z ; that is, there exist a subshift \hat{Z} and a factor code \pi:\hat{Z}\to Z such that for all z\in Z , |\pi^{-1}(z)|=1 if z is not that fixed point, and \pi^{-1}{(z)} is an orbit of length 2 if z is that fixed point. We remark here that [ T , Theorem 8.6] gave necessary and sufficient conditions for embedding a mixing sofic shift X that satisfies certain special conditions into a general sofic shift Y . In particular these additional conditions hold when X is a mixing SFT. We also remark that Krieger [ Kr2 ] gave necessary and sufficient conditions for the factor problem, analogous to the embedding problem, of given mixing sofic shifts Y and Z , with h(Z)>h(Y) , factoring Z onto Y . The remainder of the paper is organized as follows. In Section 2 , we review basic concepts and important results from symbolic dynamics. In Section 3 , we state and prove our main result, Theorem 7 , which characterizes when a subshift can be embedded into a near Markov shift. The condition involves the existence of a so-called blowup of a subshift, whose properties are investigated in Section 4 . Finally,