Powers of positive polynomials and codings of Markov chains onto Bernoulli shifts

Authors:
Brian Marcus and Selim Tuncel

Journal:
Electron. Res. Announc. Amer. Math. Soc. **5** (1999), 91-101

MSC (1991):
Primary 28D20; Secondary 11C08, 05A10

Published electronically:
June 30, 1999

MathSciNet review:
1696825

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We give necessary and sufficient conditions for a Markov chain to factor onto a Bernoulli shift (i) as an eventual right-closing factor, (ii) by a right-closing factor map, (iii) by a one-to-one a.e. right-closing factor map, and (iv) by a regular isomorphism. We pass to the setting of polynomials in several variables to represent the Bernoulli shift by a nonnegative polynomial in several variables and the Markov chain by a matrix of such polynomials. The necessary and sufficient conditions for each of (i)-(iv) involve only an eigenvector of and basic invariants obtained from weights of periodic orbits. The characterizations of (ii)-(iv) are deduced from (i). We formulate (i) as a combinatorial problem, reducing it to certain state-splittings (partitions) of paths of length . In terms of positive polynomial masses associated with paths, the aim then becomes the construction of partitions so that the masses of the paths in each partition element sum to a multiple of , the multiple being prescribed by . The construction, which we sketch, relies on a description of the terms of and on estimates of the relative sizes of the coefficients of .

**[A]**Jonathan Ashley,*Resolving factor maps for shifts of finite type with equal entropy*, Ergodic Theory Dynam. Systems**11**(1991), no. 2, 219–240. MR**1116638**, 10.1017/S0143385700006118**[AMT]**Jonathan Ashley, Brian Marcus, and Selim Tuncel,*The classification of one-sided Markov chains*, Ergodic Theory Dynam. Systems**17**(1997), no. 2, 269–295. MR**1444053**, 10.1017/S0143385797069745**[BMT]**Mike Boyle, Brian Marcus, and Paul Trow,*Resolving maps and the dimension group for shifts of finite type*, Mem. Amer. Math. Soc.**70**(1987), no. 377, vi+146. MR**912638**, 10.1090/memo/0377**[BT]**Mike Boyle and Selim Tuncel,*Regular isomorphism of Markov chains is almost topological*, Ergodic Theory Dynam. Systems**10**(1990), no. 1, 89–100. MR**1053800**, 10.1017/S014338570000540X**[H]**David Handelman,*Positive polynomials and product type actions of compact groups*, Mem. Amer. Math. Soc.**54**(1985), no. 320, xi+79. MR**783217**, 10.1090/memo/0320**[LM]**Douglas Lind and Brian Marcus,*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092****[M]**Brian Marcus,*Factors and extensions of full shifts*, Monatsh. Math.**88**(1979), no. 3, 239–247. MR**553733**, 10.1007/BF01295238**[MT1]**Brian Marcus and Selim Tuncel,*The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains*, Ergodic Theory Dynam. Systems**11**(1991), no. 1, 129–180. MR**1101088**, 10.1017/S0143385700006052**[MT2]**Brian Marcus and Selim Tuncel,*Entropy at a weight-per-symbol and embeddings of Markov chains*, Invent. Math.**102**(1990), no. 2, 235–266. MR**1074475**, 10.1007/BF01233428**[MT3]**Brian Marcus and Selim Tuncel,*Matrices of polynomials, positivity, and finite equivalence of Markov chains*, J. Amer. Math. Soc.**6**(1993), no. 1, 131–147. MR**1168959**, 10.1090/S0894-0347-1993-1168959-X**[MT4]**B. Marcus and S. Tuncel, On large powers of positive polynomials in several variables, preprint.**[MT5]**B. Marcus and S. Tuncel, Resolving Markov chains onto Bernoulli shifts, preprint.**[O]**Donald S. Ornstein,*Ergodic theory, randomness, and dynamical systems*, Yale University Press, New Haven, Conn.-London, 1974. James K. Whittemore Lectures in Mathematics given at Yale University; Yale Mathematical Monographs, No. 5. MR**0447525****[PS]**William Parry and Klaus Schmidt,*Natural coefficients and invariants for Markov-shifts*, Invent. Math.**76**(1984), no. 1, 15–32. MR**739621**, 10.1007/BF01388488**[PT]**William Parry and Selim Tuncel,*On the stochastic and topological structure of Markov chains*, Bull. London Math. Soc.**14**(1982), no. 1, 16–27. MR**642417**, 10.1112/blms/14.1.16**[T]**Selim Tuncel,*Faces of Markov chains and matrices of polynomials*, Symbolic dynamics and its applications (New Haven, CT, 1991) Contemp. Math., vol. 135, Amer. Math. Soc., Providence, RI, 1992, pp. 391–422. MR**1185106**, 10.1090/conm/135/1185106

Retrieve articles in *Electronic Research Announcements of the American Mathematical Society*
with MSC (1991):
28D20,
11C08,
05A10

Retrieve articles in all journals with MSC (1991): 28D20, 11C08, 05A10

Additional Information

**Brian Marcus**

Affiliation:
IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120

Email:
marcus@almaden.ibm.com

**Selim Tuncel**

Affiliation:
Department of Mathematics, Box 354350, University of Washington, Seattle, WA 98195

Email:
tuncel@math.washington.edu

DOI:
http://dx.doi.org/10.1090/S1079-6762-99-00066-9

Received by editor(s):
January 21, 1999

Published electronically:
June 30, 1999

Additional Notes:
Partially supported by NSF Grant DMS–9622866

Communicated by:
Klaus Schmidt

Article copyright:
© Copyright 1999
American Mathematical Society