Strong shift equivalence theory and

the shift equivalence problem

Author:
J. B. Wagoner

Journal:
Bull. Amer. Math. Soc. **36** (1999), 271-296

MSC (1991):
Primary 19C99, 19D55, 58F99, 81R99

DOI:
https://doi.org/10.1090/S0273-0979-99-00798-3

Published electronically:
June 24, 1999

MathSciNet review:
1688990

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper discusses strong shift equivalence and counterexamples to the long standing Shift Equivalence Problem in symbolic dynamics. We also discuss how strong shift equivalence theory is closely related to areas of mathematics outside dynamics such as algebraic K-theory, cyclic homology, and topological quantum field theory.

**[A]**R.L. Adler,*The torus and the disk*, IBM Journal of Research and Development, Vol. 31, No.2, March 1987, 224-234 CMP**19:14****[AKM]**R.L. Adler, A. Konheim, and M. McAndrew,*Topological entropy*, TAMS 114, 1965, 309-319 MR**30:5291****[B]**K. Baker,*Strong shift equivalence of matrices of non-negative integers*, ETDS, 1983, 3, 501-508 MR**86g:28021****[Bl]**S. Bloch,*Algebraic K-theory and crystalline cohomology*, Pub. Math. IHES 47, 1977, 197-238 MR**81j:14011****[Bo]**M. Boyle,*The stochastic shift equivalence conjecture is false*, Contemporary Mathematics, Vol. 135, 1992, 107-110 MR**93i:28013****[Bow]**R. Bowen,*Markov partitions for Axiom A diffeomorphisms*, Amer. Jour. Math. 92, 1970, 725-747 MR**43:2740****[BF]**M. Boyle and U.Fiebig,*The action of inert finite order automorphisms on finite subsystems*, ETDS 11, 1991, 413-425 MR**92g:58029****[BH1]**M. Boyle and D. Handelman,*Algebraic shift equivalence and primitive matrices*, Trans. AMS 336, No. 1, 1993, 121-149. MR**93e:58050****[BH2]**- ,*The spectra of nonnegative matrices via symbolic dynamics*, Annals of Mathematics, 133, 1991, 249-316 MR**92d:58057****[BK1]**M. Boyle and W. Krieger,*Periodic points and automorphisms of the shift*, Trans. AMS 302, 1987, 125-149 MR**88g:54065****[BK2]**- ,*Automorphisms and subsystems of the shift*, Jour. Reine Angew. Math. 437, 1993, 13-28 MR**95b:54051****[BLR]**M. Boyle, D. Lind, and D. Rudolph,*The automorphism group of a shift of finite type*, Trans. AMS 306, 1988, 71-114 MR**89m:54051****[BMT]**M. Boyle, B. Marcus, and P. Trow,*Resolving maps and the dimension group for shifts of finite type*, Mem. Amer. Math. Soc. vol. 70 (1987), Number 377, Providence, R.I. MR**89c:28019****[BW]**M. Boyle and J.B. Wagoner,*Nonnegative algebraic K-theory and subshifts of finite type*, in preparation**[BaW]**L. Badoian and J.B. Wagoner,*Simple connectivity of the Markov partition space*, preprint, UC Berkeley, 1998, to appear in Pac. Jour. Math.**[C]**J. Cerf,*La stratification naturelle des espaces de fonctions diffrentiables relles et le theoreme de la pseudo-isotopie*, Publ. Math. IHES, No. 39, 1970, 5-173 MR**45:1176****[CK1]**J. Cuntz and W. Krieger,*Topological Markov chains and dicyclic dimension groups*, J. Reine Angew. Math. 320, 1980, 44-51 MR**81m:54074****[CK2]**- ,*A class of C*-Algebras and topological Markov chains*, Inventiones Math. 56, 1980, 251-268 MR**82f:46073a****[E]**E.G. Effros,*Dimensions and Algebras*, CBMS No. 46, AMS, 1981 MR**84k:46042****[F]**U. Fiebig,*Gyration numbers for involutions of subshifts of finite type I*, Forum Math. 4, 1992, 77-108; and II, Forum Math.4, 1992, 183-211 MR**93g:58041**; MR**93g:58042****[Fr]**J. Franks,*Homology and dynamical systems*, CBMS No. 49, AMS, 1982 MR**84f:58067****[G1]**P.M. Gilmer,*Invariants for one-dimensional cohomology classes arising from TQFT*, Topology and its Applications 75, 1997, 217-259 MR**97k:57018****[G2]**-,*Topological quantum field theory and strong shift equivalence*, preprint from Louisiana State University, 1997, to appear in Bulletin of the Canadian Mathematical Society**[GR]**S. Geller and L. Roberts,*of some truncated polynomial rings*, Ring Theory Waterloo, Springer-Verlag LNM 734, 1979, 249-278 MR**80k:13005****[H]**G. Hedlund,*Endomorphisms and automorphisms of shift dynamical systems*, Math. Systems Theory**3**, 1969, 320-375 MR**41:4510****[HW]**A. Hatcher and J.B. Wagoner,*Pseudo Isotopies of Compact Manifolds*, Astrisque No. 6, Socit Mathmatique de France, 1973 MR**50:5821****[K]**B. Kitchens,*Symbolic dynamics, one-sided, two-sided and countable state Markov shifts*, Springer-Verlag, 1998 MR**98k:58079****[Ke]**F. Keune,*The relativization of*, Journal of Algebra, 1978, 159-177 MR**80a:18013****[Kol]**A.N. Kolomogorov,*New metric invariants of transitive dynamical systems and automorphisms of Lebesgue spaces*, Dokl. Akad. Nauk. SSSR, 119, 1958, 861-864**[Kr]**W. Krieger,*On dimension functions and topological Markov chains*, Invent. Math. 56, 1980, 239-250 MR**81m:28018****[KOR]**K.H. Kim, N. Ormes, and F.W. Roush,*The spectra of nonnegative integer matrices via formal power series*, preprint, University of Texas at Austin, 1998**[KR1]**K.H. Kim and F.W. Roush,*Some results on decidability of shift equivalence*, J. Comb. Inform. System Sci. 4, 1979, 123-146. MR**81m:58064****[KR2]**- ,*Decidability of shift equivalence*, in J. W. Alexander, ed., Dynamical Systems, Lecture Notes in Mathematics, vol. 1342, Springer-Verlag, Heidelberg, 1988 MR**90g:54033****[KR3]**- ,*On the structure of inert automorphisms of subshifts*, Pure Mathematics and Applications 2, 1991, 3-22 MR**94c:58056****[KR4]**- ,*Williams's conjecture is false for reducible subshifts*, Jour. AMS 5, 1992, 213-215 MR**92j:54055****[KR5]**- ,*Williams's conjecture is false for irreducible subshifts*, ERA AMS 3, 1997, 105-109 MR**98i:58081****[KR6]**- ,*Williams's conjecture is false for irreducible subshifts*, preprint from Alabama State University, 1997, to appear in Annals of Mathematics**[KR7]**- ,*Path components of matrices and strong shift equivalence over*, Linear Algebra and Applications 145, 1991, 177-186 MR**92c:58027****[KR8]**- ,*Strong shift equivalence of Boolean and positive rational matrices*, Linear Algebra and Applications 161, 1992, 153-164 MR**93h:15012****[KRW1]**K.H. Kim, F.W. Roush, and J. Wagoner,*Automorphisms of the dimension group and gyration numbers*, Jour. AMS 5, 1992, 191-212. MR**93h:54026****[KRW2]**- ,*Characterization of inert actions on periodic points, Part I and Part II*, preprint, UC Berkeley, 1997, to appear in Forum Mathematicum**[KRW3]**- ,*Inert Actions on Periodic Points*, ERA AMS 3, 1997, 55-62 MR**98i:54021****[Li]**W.B.R. Lickorish*An Introduction to Knot Theory*, GTM 175, Springer-Verlag, 1997 MR**98f:57015****[Lo]**J.- L. Loday,*Cyclic Homology*, Springer-Verlag, Second Edition, 1998 MR**98h:16014****[LM]**D. Lind and B. Marcus,*An introduction to symbolic dynamics and coding*, Cambridge University Press, 1995 MR**97a:58050****[M]**B. Marcus,*Symbolic dynamics and connections to coding theory, automata theory and system theory*, AMS Proc. Symp. Applied Math. 50, 1995, 95-108. MR**97a:58052****[Mi]**J. Milnor,*Introduction to Algebraic K-Theory*, Annals of Mathematics Studies Number 72, Princeton University Press, 1971 MR**50:2304****[MB]**S. MacLane and G. Birkhoff,*Algebra*, Macmillan Company, Second Edition, 1979 MR**80d:00002****[MH]**M. Morse and G.A. Hedlund,*Symbolic Dynamics*, Amer. Jour. Math. 60 (1938), 815-866.**[MS]**H. Maazen and J. Stienstra,*A presentation for of split radical pairs*, Journal of Pure and Applied Algebra 10, 1977, 271-294 MR**57:12485****[MT1]**B. Marcus and S. Tuncel,*Entropy at a weight-per-symbol and an imbedding theorem for Markov chains*, Inventiones Mathematicae 102, 1990, 235-266. MR**91k:28023****[MT2]**-,*The weight-per-symbol polytope and scaffolds of invariants associated with Markov chains*, Ergodic Theory and Dynamical Systems 11, 1991, 129-180. MR**92g:28038****[MT3]**-,*Matrices of polynomials, positivity, and finite equivalence of Markov chains*, AMS Journal 6, 1993, 131-147 MR**93e:28022****[N]**M. Nasu,*Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological Markov shifts*, Springer Lecture Notes in Math 1342, 1988 MR**89j:54045****[PT]**W. Parry and S. Tuncel,*Classification problems in ergodic theory*, LMS Lecture Notes 67, Cambridge University Press, 1982 MR**84g:28024****[PW]**W. Parry and R.F. Williams,*Block coding and a zeta function for Markov chains*, Proc. LMS 35, 1977, 483-495 MR**57:6368****[Q]**F. Quinn,*Lectures on axiomatic topological quantum field theory*, Geometry and Quantum Field Theory (edited by D. Freed and K. Uhlenbeck), IAS/Park City Mathematics Series, Vol. 1, AMS, 1995, 325-453 MR**96e:57021****[R]**J. Rosenberg,*Algebraic K-Theory and Its Applications*, GTM 147, Springer-Verlag, 1994 MR**95e:19001****[S]**S. Smale,*Differential Dynamical Systems*, BAMS, Vol. 73, No. 6, 1967, 747-847 MR**37:3598****[Sh]**C. Shannon,*A mathematical theory of communication*, Bell Sys. Tech Jour. 27, 1948, 379-423, 623-656 MR**10:133e****[St]**J. Stienstra,*On and of truncated polynomial rings*, LNM 854, Springer, 1981 MR**82k:13016****[SW1]**D. Silver and S. Williams,*Augmented group systems and shifts of finite type*, Israel Journal of Mathematics 95, 1996, 231-251 MR**98b:20045****[SW2]**- ,*Knot invariants from symbolic dynamical systems*, to appear in Trans. AMS 351, No. 8, 1999, 3243-3265 CMP**97:17****[T]**S. Tuncel,*Faces of Markov chains and matrices of polynomials*, Contemporary Mathematics, Vol. 135, AMS, 1992, 391-422 MR**94m:28034****[vdK]**W. van der Kallen,*Le des nombres duaux*, C.R. Acad. Sc. Paris, Srie A, t. 273 , 20 dcembre 1971, 1204-1207 MR**45:252****[W1]**J.B. Wagoner,*Markov partitions and*, Publ. Math. IHES, No. 65, 1987, 91-129 MR**90d:28022****[W2]**- ,*Triangle identities and symmetries of a subshift of finite type*, Pacific Jour. Math. 144, 1990, 181-205 MR**91h:28017****[W3]**- ,*Higher dimensional shift equivalence is the same as strong shift equivalence over the integers*, Proc. AMS 109, 1990, 527-536 MR**90i:54088****[W4]**- ,*Eventual finite order generation for the kernel of the dimension group representation*, Trans. AMS 317, 1990, 331-350 MR**91a:54055****[W5]**- ,*Classification of subshifts of finite type revisited*, Contemporary Mathematics, Vol. 135, AMS, 1992, 423-436 MR**93m:20004****[W6]**- ,*Markov chains, -algebras, and*, Advances of Mathematics, Vol. 71, No. 2, 1988, 133-185 MR**90j:46059****[W7]**- ,*Strong shift equivalence and of the dual numbers*, preprint from UC Berkeley, 1998, to appear in Jour. Reine Angew. Math.**[Wi1]**R.F. Williams,*Classification of subshifts of finite type*, Annals of Math.(2) 98, 1973, 120-153; Errata ibid. 99, 1974, 380-381. MR**48:9769****[Wi2]**- ,*Shift equivalence of matrices in GL(2,)*, Cont. Math., Vol. 135, AMS, 1992, 445-451 MR**93k:58183****[Wi3]**- ,*Classification of 1-dimensional attractors*, Global Analysis, Proceedings of the Symposium on Pure Mathematics 14, AMS, 1970, 341-361 MR**42:1134****[Wi4]**- ,*Addendum to ``Classification of 1-dimensional attractors"*, preprint from University of Texas, Austin, 1998

Retrieve articles in *Bulletin of the American Mathematical Society*
with MSC (1991):
19C99,
19D55,
58F99,
81R99

Retrieve articles in all journals with MSC (1991): 19C99, 19D55, 58F99, 81R99

Additional Information

**J. B. Wagoner**

Affiliation:
Mathematics, University of California, Berkeley, CA 94720

Email:
wagoner@math.berkeley.edu

DOI:
https://doi.org/10.1090/S0273-0979-99-00798-3

Keywords:
Strong shift equivalence,
the shift equivalence problem,
positivity

Received by editor(s):
April 29, 1999

Received by editor(s) in revised form:
May 27, 1999

Published electronically:
June 24, 1999

Additional Notes:
The author was supported in part by NSF Grant DMS 9322498.

Article copyright:
© Copyright 1999
American Mathematical Society