Embedding of shifts of finite type into the Dyck shift (Q2486419)

From the text: Periodic points data of the Dyck shift are precisely investigated. A necessary and sufficient condition for an irreducible shift of finite type to be embedded into the Dyck shift are be shown. In [Ergodic Theory Dyn. Syst. 20, No. 2, 501--516 (2000; Zbl 0992.37010)] and [Bull. Lond. Math. Soc. 38, No. 4, 617--624 (2006; Zbl 1097.37006)], \textit{W. Krieger} introduced and investigated a certain class of subshifts enjoying some algebraic property; they are called property A subshifts. The Dyck shift is one of these shift spaces, and is a typical and fundamental shift space in this class. Any property A subshift comprises a lot of SFTs (shifts of finite type) in the shift space, which are essential for the algebraic property. So it is natural to ask how an SFT sits in this shift space. This should be done in terms of the notion of embedding. In [(*) Ergodic Theory Dyn. Syst. 2, 195--202 (1982; Zbl 0508.54032)], Krieger showed under what condition an irreducible SFT is properly embedded into another irreducible SFT. Here, proper embedding means a one-to-one, into but not onto conjugacy of shift spaces. The necessary and sufficient condition for proper embedding is known and given by entropy condition and embedding periodic condition [(*)]. This result was improved by \textit{M. Boyle} [Ergodic Theory Dyn. Syst. 3, 541--557 (1983; Zbl 0529.28014)] for proper embedding of an SFT into an irreducible sofic shift, although it is a sufficient condition. In this paper we investigate proper embedding of an irreducible SFT into the Dyck shifts \(D_M\). The Dyck shift \(D=D_2\), which comes from language theory, is defined to be a shift space over the alphabet \(\Sigma\) consisting of four symbols, two negative symbols \((\) and \([\), and the other two positive symbols \()\) and \(]\). For an \(x\) in the shift space \(\Sigma^Z\), \(x\) is in \(D\) if and only if every finite block appearing in \(x\) has a nonzero reduced form. Therefore, the constraint for \(x\) cannot be bounded. Our question is under what condition an irreducible SFT can be conjugate with a subshift inside \(D\). Since \(D\) has a lot of SFTs in it, one could expect that Krieger's embedding theorem is also true for the Dyck shift, which is quite different from any SFT. However, as shown in Section 7, in our case his condition is not enough for embedding. The necessary and sufficient condition for embedding of an irreducible SFT into the Dyck shift \(D\) is established in terms of certain restricted embedding periodic condition and entropy condition (Theorem 5.3). The restricted embedding periodic condition is computable (as seen in Section 4). The computation is done by counting the number of periodic defining blocks in terms of colorable paths of the one-dimensional symmetric random walk on \(\mathbb Z\) (Proposition 2.4). Also for the Dyck shifts \(D_M\), \(M\geq 3\), the necessary and sufficient condition for embedding of an irreducible SFT into \(D_M\) is obtained (Theorem 6.3). More generally, in a forthcoming paper we intend to extend the main theorem from the Dyck shift to a class of property A subshifts [J. Reine Angew. Math. 632, 37--61 (2009; Zbl 1177.37019)]. Besides regarding entropy for irreducible SFTs of the Dyck shift, it will be observed that any irreducible SFT of the Dyck shift can always be properly enlarged to another irreducible SFT of the Dyck shift (Proposition 3.1). This will lead us to see why the case (E2) in Theorem 4.4 occurs. We believe that this result might be of independent interest.