Strong shift equivalence theory and the shift equivalence problem

Wagoner, J.

doi:10.1090/S0273-0979-99-00798-3

Strong shift equivalence theory and the shift equivalence problem
HTML articles powered by AMS MathViewer

by J. B. Wagoner PDF

Bull. Amer. Math. Soc. 36 (1999), 271-296 Request permission

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.

References

R.L. Adler, The torus and the disk, IBM Journal of Research and Development, Vol. 31, No.2, March 1987, 224-234
R. L. Adler, A. G. Konheim, and M. H. McAndrew, Topological entropy, Trans. Amer. Math. Soc. 114 (1965), 309–319. MR 175106, DOI 10.1090/S0002-9947-1965-0175106-9
Kirby A. Baker, Strong shift equivalence of $2\times 2$ matrices of nonnegative integers, Ergodic Theory Dynam. Systems 3 (1983), no. 4, 501–508. MR 753918, DOI 10.1017/S0143385700002091
Spencer Bloch, Algebraic $K$-theory and crystalline cohomology, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 187–268 (1978). MR 488288
Mike Boyle, The stochastic shift equivalence conjecture is false, Symbolic dynamics and its applications (New Haven, CT, 1991) Contemp. Math., vol. 135, Amer. Math. Soc., Providence, RI, 1992, pp. 107–110. MR 1185083, DOI 10.1090/conm/135/1185083
Rufus Bowen, Markov partitions for Axiom $\textrm {A}$ diffeomorphisms, Amer. J. Math. 92 (1970), 725–747. MR 277003, DOI 10.2307/2373370
Mike Boyle and Ulf-Rainer Fiebig, The action of inert finite-order automorphisms on finite subsystems of the shift, Ergodic Theory Dynam. Systems 11 (1991), no. 3, 413–425. MR 1125880, DOI 10.1017/S0143385700006246
Mike Boyle and David Handelman, Algebraic shift equivalence and primitive matrices, Trans. Amer. Math. Soc. 336 (1993), no. 1, 121–149. MR 1102219, DOI 10.1090/S0002-9947-1993-1102219-4
Mike Boyle and David Handelman, The spectra of nonnegative matrices via symbolic dynamics, Ann. of Math. (2) 133 (1991), no. 2, 249–316. MR 1097240, DOI 10.2307/2944339
Mike Boyle and Wolfgang Krieger, Periodic points and automorphisms of the shift, Trans. Amer. Math. Soc. 302 (1987), no. 1, 125–149. MR 887501, DOI 10.1090/S0002-9947-1987-0887501-5
Mike Boyle and Wolfgang Krieger, Automorphisms and subsystems of the shift, J. Reine Angew. Math. 437 (1993), 13–28. MR 1212251, DOI 10.1515/crll.1993.437.13
Mike Boyle, Douglas Lind, and Daniel Rudolph, The automorphism group of a shift of finite type, Trans. Amer. Math. Soc. 306 (1988), no. 1, 71–114. MR 927684, DOI 10.1090/S0002-9947-1988-0927684-2
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, DOI 10.1090/memo/0377
M. Boyle and J.B. Wagoner, Nonnegative algebraic K-theory and subshifts of finite type, in preparation
L. Badoian and J.B. Wagoner, Simple connectivity of the Markov partition space, preprint, UC Berkeley, 1998, to appear in Pac. Jour. Math.
Jean Cerf, La stratification naturelle des espaces de fonctions différentiables réelles et le théorème de la pseudo-isotopie, Inst. Hautes Études Sci. Publ. Math. 39 (1970), 5–173 (French). MR 292089
Joachim Cuntz and Wolfgang Krieger, Topological Markov chains with dicyclic dimension groups, J. Reine Angew. Math. 320 (1980), 44–51. MR 592141, DOI 10.1515/crll.1980.320.44
Joachim Cuntz and Wolfgang Krieger, A class of $C^{\ast }$-algebras and topological Markov chains, Invent. Math. 56 (1980), no. 3, 251–268. MR 561974, DOI 10.1007/BF01390048
Edward G. Effros, Dimensions and $C^{\ast }$-algebras, CBMS Regional Conference Series in Mathematics, vol. 46, Conference Board of the Mathematical Sciences, Washington, D.C., 1981. MR 623762, DOI 10.1090/cbms/046
Ulf-Rainer Fiebig, Gyration numbers for involutions of subshifts of finite type. I, Forum Math. 4 (1992), no. 1, 77–108. MR 1142474, DOI 10.1515/form.1992.4.77
John M. Franks, Homology and dynamical systems, CBMS Regional Conference Series in Mathematics, vol. 49, Published for the Conference Board of the Mathematical Sciences, Washington, D.C. by the American Mathematical Society, Providence, R.I., 1982. MR 669378, DOI 10.1090/cbms/049
Patrick M. Gilmer, Invariants for one-dimensional cohomology classes arising from TQFT, Topology Appl. 75 (1997), no. 3, 217–259. MR 1430088, DOI 10.1016/S0166-8641(96)00090-9
—, Topological quantum field theory and strong shift equivalence, preprint from Louisiana State University, 1997, to appear in Bulletin of the Canadian Mathematical Society
Leslie G. Roberts, $K_{2}$ of some truncated polynomial rings, Ring theory (Proc. Conf., Univ. Waterloo, Waterloo, 1978) Lecture Notes in Math., vol. 734, Springer, Berlin, 1979, pp. 249–278. With a section written jointly with S. Geller. MR 548133
G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320–375. MR 259881, DOI 10.1007/BF01691062
Allen Hatcher and John Wagoner, Pseudo-isotopies of compact manifolds, Astérisque, No. 6, Société Mathématique de France, Paris, 1973. With English and French prefaces. MR 0353337
Bruce P. Kitchens, Symbolic dynamics, Universitext, Springer-Verlag, Berlin, 1998. One-sided, two-sided and countable state Markov shifts. MR 1484730, DOI 10.1007/978-3-642-58822-8
Frans Keune, The relativization of $K_{2}$, J. Algebra 54 (1978), no. 1, 159–177. MR 511460, DOI 10.1016/0021-8693(78)90024-8
A.N. Kolomogorov, New metric invariants of transitive dynamical systems and automorphisms of Lebesgue spaces, Dokl. Akad. Nauk. SSSR, 119, 1958, 861-864
Wolfgang Krieger, On dimension functions and topological Markov chains, Invent. Math. 56 (1980), no. 3, 239–250. MR 561973, DOI 10.1007/BF01390047
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
K. H. Kim and F. W. Roush, Some results on decidability of shift equivalence, J. Combin. Inform. System Sci. 4 (1979), no. 2, 123–146. MR 564188
Ki Hang Kim and Fred W. Roush, Decidability of shift equivalence, Dynamical systems (College Park, MD, 1986–87) Lecture Notes in Math., vol. 1342, Springer, Berlin, 1988, pp. 374–424. MR 970567, DOI 10.1007/BFb0082843
K. H. Kim and F. W. Roush, On the structure of inert automorphisms of subshifts, Pure Math. Appl. Ser. B 2 (1991), no. 1, 3–22. MR 1139751
K. H. Kim and F. W. Roush, Williams’s conjecture is false for reducible subshifts, J. Amer. Math. Soc. 5 (1992), no. 1, 213–215. MR 1130528, DOI 10.1090/S0894-0347-1992-1130528-4
K. H. Kim and F. W. Roush, The Williams conjecture is false for irreducible subshifts, Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 105–109. MR 1472090, DOI 10.1090/S1079-6762-97-00032-2
—, Williams’s conjecture is false for irreducible subshifts, preprint from Alabama State University, 1997, to appear in Annals of Mathematics
K. H. Kim and F. W. Roush, Path components of matrices and strong shift equivalence over $\textbf {Q}^+$, Linear Algebra Appl. 145 (1991), 177–186. MR 1080683, DOI 10.1016/0024-3795(91)90294-7
K. H. Kim and F. W. Roush, Strong shift equivalence of Boolean and positive rational matrices, Linear Algebra Appl. 161 (1992), 153–164. MR 1142735, DOI 10.1016/0024-3795(92)90010-8
K. H. Kim, F. W. Roush, and J. B. Wagoner, Automorphisms of the dimension group and gyration numbers, J. Amer. Math. Soc. 5 (1992), no. 1, 191–212. MR 1124983, DOI 10.1090/S0894-0347-1992-1124983-3
—, Characterization of inert actions on periodic points, Part I and Part II, preprint, UC Berkeley, 1997, to appear in Forum Mathematicum
K. H. Kim, F. W. Roush, and J. B. Wagoner, Inert actions on periodic points, Electron. Res. Announc. Amer. Math. Soc. 3 (1997), 55–62. MR 1464576, DOI 10.1090/S1079-6762-97-00024-3
W. B. Raymond Lickorish, An introduction to knot theory, Graduate Texts in Mathematics, vol. 175, Springer-Verlag, New York, 1997. MR 1472978, DOI 10.1007/978-1-4612-0691-0
Jean-Louis Loday, Cyclic homology, 2nd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 301, Springer-Verlag, Berlin, 1998. Appendix E by María O. Ronco; Chapter 13 by the author in collaboration with Teimuraz Pirashvili. MR 1600246, DOI 10.1007/978-3-662-11389-9
Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092, DOI 10.1017/CBO9780511626302
Brian Marcus, Symbolic dynamics and connections to coding theory, automata theory and system theory, Different aspects of coding theory (San Francisco, CA, 1995) Proc. Sympos. Appl. Math., vol. 50, Amer. Math. Soc., Providence, RI, 1995, pp. 95–108. MR 1368637, DOI 10.1090/psapm/050/1368637
John Milnor, Introduction to algebraic $K$-theory, Annals of Mathematics Studies, No. 72, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. MR 0349811
Saunders Mac Lane and Garrett Birkhoff, Algebra, 2nd ed., Macmillan, Inc., New York; Collier Macmillan Publishers, London, 1979. MR 524398
M. Morse and G.A. Hedlund, Symbolic Dynamics, Amer. Jour. Math. 60 (1938), 815-866.
Hendrik Maazen and Jan Stienstra, A presentation for $K_{2}$ of split radical pairs, J. Pure Appl. Algebra 10 (1977/78), no. 3, 271–294. MR 472795, DOI 10.1016/0022-4049(77)90007-X
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, DOI 10.1007/BF01233428
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, DOI 10.1017/S0143385700006052
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, DOI 10.1090/S0894-0347-1993-1168959-X
Masakazu Nasu, Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological Markov shifts, Dynamical systems (College Park, MD, 1986–87) Lecture Notes in Math., vol. 1342, Springer, Berlin, 1988, pp. 564–607. MR 970572, DOI 10.1007/BFb0082848
William Parry and Selim Tuncel, Classification problems in ergodic theory, Statistics: Textbooks and Monographs, vol. 41, Cambridge University Press, Cambridge-New York, 1982. MR 666871, DOI 10.1017/CBO9780511629389
William Parry and R. F. Williams, Block coding and a zeta function for finite Markov chains, Proc. London Math. Soc. (3) 35 (1977), no. 3, 483–495. MR 466490, DOI 10.1112/plms/s3-35.3.483
Frank Quinn, Lectures on axiomatic topological quantum field theory, Geometry and quantum field theory (Park City, UT, 1991) IAS/Park City Math. Ser., vol. 1, Amer. Math. Soc., Providence, RI, 1995, pp. 323–453. MR 1338394, DOI 10.1090/pcms/001/05
Jonathan Rosenberg, Algebraic $K$-theory and its applications, Graduate Texts in Mathematics, vol. 147, Springer-Verlag, New York, 1994. MR 1282290, DOI 10.1007/978-1-4612-4314-4
S. Smale, Differentiable dynamical systems, Bull. Amer. Math. Soc. 73 (1967), 747–817. MR 228014, DOI 10.1090/S0002-9904-1967-11798-1
Morgan Ward, Ring homomorphisms which are also lattice homomorphisms, Amer. J. Math. 61 (1939), 783–787. MR 10, DOI 10.2307/2371336
Jan Stienstra, On $K_{2}$ and $K_{3}$ of truncated polynomial rings, Algebraic $K$-theory, Evanston 1980 (Proc. Conf., Northwestern Univ., Evanston, Ill., 1980) Lecture Notes in Math., vol. 854, Springer, Berlin, 1981, pp. 409–455. MR 618315, DOI 10.1007/BFb0089532
Daniel S. Silver and Susan G. Williams, Augmented group systems and shifts of finite type, Israel J. Math. 95 (1996), 231–251. MR 1418295, DOI 10.1007/BF02761041
—, Knot invariants from symbolic dynamical systems, to appear in Trans. AMS 351, No. 8, 1999, 3243-3265
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, DOI 10.1090/conm/135/1185106
Wilberd van der Kallen, Le $K_{2}$ des nombres duaux, C. R. Acad. Sci. Paris Sér. A-B 273 (1971), A1204–A1207 (French). MR 291158
J. B. Wagoner, Markov partitions and $K_2$, Inst. Hautes Études Sci. Publ. Math. 65 (1987), 91–129. MR 908217, DOI 10.1007/BF02698936
J. B. Wagoner, Triangle identities and symmetries of a subshift of finite type, Pacific J. Math. 144 (1990), no. 1, 181–205. MR 1056673, DOI 10.2140/pjm.1990.144.181
J. B. Wagoner, Higher-dimensional shift equivalence and strong shift equivalence are the same over the integers, Proc. Amer. Math. Soc. 109 (1990), no. 2, 527–536. MR 1012941, DOI 10.1090/S0002-9939-1990-1012941-9
J. B. Wagoner, Eventual finite order generation for the kernel of the dimension group representation, Trans. Amer. Math. Soc. 317 (1990), no. 1, 331–350. MR 1027363, DOI 10.1090/S0002-9947-1990-1027363-9
J. B. Wagoner, Classification of subshifts of finite type revisited, Symbolic dynamics and its applications (New Haven, CT, 1991) Contemp. Math., vol. 135, Amer. Math. Soc., Providence, RI, 1992, pp. 423–444. MR 1185107, DOI 10.1090/conm/135/1185107
J. B. Wagoner, Topological Markov chains, $C^*$-algebras, and $K_2$, Adv. in Math. 71 (1988), no. 2, 133–185. MR 963485, DOI 10.1016/0001-8708(88)90075-8
—, Strong shift equivalence and $K_2$ of the dual numbers, preprint from UC Berkeley, 1998, to appear in Jour. Reine Angew. Math.
R. F. Williams, Classification of subshifts of finite type, Ann. of Math. (2) 98 (1973), 120–153; errata, ibid. (2) 99 (1974), 380–381. MR 331436, DOI 10.2307/1970908
R. F. Williams, Strong shift equivalence of matrices in $\textrm {GL}(2,\textbf {Z})$, Symbolic dynamics and its applications (New Haven, CT, 1991) Contemp. Math., vol. 135, Amer. Math. Soc., Providence, RI, 1992, pp. 445–451. MR 1185108, DOI 10.1090/conm/135/1185108
R. F. Williams, Classification of one dimensional attractors, Global Analysis (Proc. Sympos. Pure Math., Vol. XIV, Berkeley, Calif., 1968) Amer. Math. Soc., Providence, R.I., 1970, pp. 341–361. MR 0266227
—, Addendum to “Classification of 1-dimensional attractors", preprint from University of Texas, Austin, 1998