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

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

Published electronically:
June 30, 1999

MathSciNet review:
1696825

Full-text PDF

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]**J. Ashley, Resolving factor maps for shifts of finite type with equal entropy,*Ergod. Th. and Dynam. Sys.***11**(1991), 219-240. MR**92d:58056****[AMT]**J. Ashley, B. Marcus and S. Tuncel, The classification of one-sided Markov chains,*Ergod. Th. and Dynam. Sys.***17**(1997), 269-295. MR**98k:28021****[BMT]**M. Boyle, B. Marcus and P. Trow, Resolving maps and the dimension group for shifts of finite type,*Mem. Amer. Math. Soc.***377**(1987). MR**89c:28019****[BT]**M. Boyle and S. Tuncel, Regular isomorphism of Markov chains is almost topological,*Ergod. Th. and Dynam. Sys.***10**(1990), 89-100. MR**92i:28021****[H]**D. Handelman, Positive polynomials and product type actions of compact groups,*Mem. Amer. Math. Soc.***320**(1985). MR**86h:46091****[LM]**D. Lind and B. Marcus,*An Introduction to Symbolic Dynamics and Coding*, Cambridge Univ. Press, Cambridge, 1995. MR**97a:58050****[M]**B. Marcus, Factors and extensions of full shifts,*Monatshefte Math.***88**(1979), 239-247. MR**81g:28023****[MT1]**B. Marcus and S. Tuncel, The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains,*Ergod.Th. and Dynam. Sys.***11**(1991), 129-180. MR**92g:28038****[MT2]**B. Marcus and S. Tuncel, Entropy at a weight-per-symbol and embeddings of Markov chains,*Invent. Math.***102**(1990), 235-266. MR**91k:28023****[MT3]**B. Marcus and S. Tuncel, Matrices of polynomials, positivity, and finite equivalence of Markov chains,*J. Amer.Math. Soc.***6**(1993), 131-147. MR**93e:28022****[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]**D. Ornstein,*Ergodic Theory, Randomness and Dynamical Systems*, Yale Univ. Press, New Haven, 1974. MR**56:5836****[PS]**W. Parry and K. Schmidt, Natural coefficients and invariants for Markov shifts,*Invent. Math.***76**(1984), 15-32. MR**86b:28022a****[PT]**W. Parry and S. Tuncel, On the stochastic and topological structure of Markov chains,*Bull. London Math. Soc.***14**(1982), 16-27. MR**84i:28024****[T]**S. Tuncel, Faces of Markov chains and matrices of polynomials,*Contemp. Math.*, Vol. 135, Amer. Math. Soc., Providence, 1992, pp. 391-422. MR**94m:28034**

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:
https://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