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), 91101
MSC (1991):
Primary 28D20; Secondary 11C08, 05A10
Published electronically:
June 30, 1999
MathSciNet review:
1696825
Fulltext 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 rightclosing factor, (ii) by a rightclosing factor map, (iii) by a onetoone a.e. rightclosing 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 statesplittings (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
(92d:58056), http://dx.doi.org/10.1017/S0143385700006118
 [AMT]
Jonathan
Ashley, Brian
Marcus, and Selim
Tuncel, The classification of onesided Markov chains, Ergodic
Theory Dynam. Systems 17 (1997), no. 2,
269–295. MR 1444053
(98k:28021), http://dx.doi.org/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 (89c:28019)
 [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
(92i:28021), http://dx.doi.org/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
(86h:46091)
 [LM]
Douglas
Lind and Brian
Marcus, An introduction to symbolic dynamics and coding,
Cambridge University Press, Cambridge, 1995. MR 1369092
(97a:58050)
 [M]
Brian
Marcus, Factors and extensions of full shifts, Monatsh. Math.
88 (1979), no. 3, 239–247. MR 553733
(81g:28023), http://dx.doi.org/10.1007/BF01295238
 [MT1]
Brian
Marcus and Selim
Tuncel, The weightpersymbol polytope and scaffolds of invariants
associated with Markov chains, Ergodic Theory Dynam. Systems
11 (1991), no. 1, 129–180. MR 1101088
(92g:28038), http://dx.doi.org/10.1017/S0143385700006052
 [MT2]
Brian
Marcus and Selim
Tuncel, Entropy at a weightpersymbol and embeddings of Markov
chains, Invent. Math. 102 (1990), no. 2,
235–266. MR 1074475
(91k:28023), http://dx.doi.org/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
(93e:28022), http://dx.doi.org/10.1090/S0894034719931168959X
 [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., 1974. James K.
Whittemore Lectures in Mathematics given at Yale University; Yale
Mathematical Monographs, No. 5. MR 0447525
(56 #5836)
 [PS]
William
Parry and Klaus
Schmidt, Natural coefficients and invariants for
Markovshifts, Invent. Math. 76 (1984), no. 1,
15–32. MR
739621 (86b:28022a), http://dx.doi.org/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
(84i:28024), http://dx.doi.org/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
(94m:28034), http://dx.doi.org/10.1090/conm/135/1185106
 [A]
 J. Ashley, Resolving factor maps for shifts of finite type with equal entropy, Ergod. Th. and Dynam. Sys. 11 (1991), 219240. MR 92d:58056
 [AMT]
 J. Ashley, B. Marcus and S. Tuncel, The classification of onesided Markov chains, Ergod. Th. and Dynam. Sys. 17 (1997), 269295. 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), 89100. 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), 239247. MR 81g:28023
 [MT1]
 B. Marcus and S. Tuncel, The weightpersymbol polytope and scaffolds of invariants associated with Markov chains, Ergod.Th. and Dynam. Sys. 11 (1991), 129180. MR 92g:28038
 [MT2]
 B. Marcus and S. Tuncel, Entropy at a weightpersymbol and embeddings of Markov chains, Invent. Math. 102 (1990), 235266. 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), 131147. 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), 1532. MR 86b:28022a
 [PT]
 W. Parry and S. Tuncel, On the stochastic and topological structure of Markov chains, Bull. London Math. Soc. 14 (1982), 1627. MR 84i:28024
 [T]
 S. Tuncel, Faces of Markov chains and matrices of polynomials, Contemp. Math., Vol. 135, Amer. Math. Soc., Providence, 1992, pp. 391422. MR 94m:28034
Similar Articles
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/S1079676299000669
PII:
S 10796762(99)000669
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
