A characterization of the entropies of multidimensional shifts of finite type

Pages 2011-2038 from Volume 171 (2010), Issue 3 by Michael Hochman, Tom Meyerovitch

Abstract

We show that the values of entropies of multidimensional shifts of finite type (SFTs) are characterized by a certain computation-theoretic property: a real number $h\geq0$ is the entropy of such an SFT if and only if it is right recursively enumerable, i.e. there is a computable sequence of rational numbers converging to $h$ from above. The same characterization holds for the entropies of sofic shifts. On the other hand, the entropy of strongly irreducible SFTs is computable.

  • [AW70] R. L. Adler and B. Weiss, Similarity of Automorphisms of the Torus, Providence, R.I.: Amer. Math. Soc., 1970, vol. 98.
    @book {AW70, MRKEY = {0257315},
      AUTHOR = {Adler, Roy L. and Weiss, Benjamin},
      TITLE = {Similarity of Automorphisms of the Torus},
      SERIES = {Mem. Amer. Math. Soc.},
      VOLUME={98},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, R.I.},
      YEAR = {1970},
      PAGES = {ii+43},
      MRCLASS = {28.70},
      MRNUMBER = {41 \#1966},
      MRREVIEWER = {D. Newton},
      ZBLNUMBER = {0195.06104},
      }
  • [B66] R. Berger, The Undecidability of the Domino Problem, Providence, RI: Amer. Math. Soc., 1966, vol. 66.
    @book {B66, MRKEY = {0216954},
      AUTHOR = {Berger, Robert},
      TITLE = {The Undecidability of the Domino Problem},
      SERIES = {Mem. Amer. Math. Soc. No.},
      FJOURNAL = {Memoirs of the American Mathematical Society},
      VOLUME = {66},
      YEAR = {1966},
      PUBLISHER={Amer. Math. Soc.},
      ADDRESS={Providence, RI},
      PAGES = {72},
      ISSN = {0065-9266},
      MRCLASS = {02.74},
      MRNUMBER = {36 \#49},
      MRREVIEWER = {J. R. B{ü}chi},
      ZBLNUMBER = {0199.30802},
      }
  • [B78] R. Bowen, On Axiom A Diffeomorphisms, Reg. Conf. Series in Math., No. 35, Providence, R.I.: Amer. Math. Soc., 1978.
    @book {B78, MRKEY = {0482842},
      AUTHOR = {Bowen, Rufus},
      TITLE = {On {A}xiom {A} Diffeomorphisms, Reg. Conf. Series in Math., {\rm No. 35}},
      PUBLISHER = {Amer. Math. Soc.},
      ADDRESS = {Providence, R.I.},
      YEAR = {1978},
      PAGES = {vii+45},
      ISBN = {0-8218-1685-3},
      MRCLASS = {58F15 (28A65)},
      MRNUMBER = {58 \#2888},
      MRREVIEWER = {L. A. Bunimovic},
      ZBLNUMBER = {0383.58010},
      }
  • [burton94] R. Burton and J. E. Steif, "Non-uniqueness of measures of maximal entropy for subshifts of finite type," Ergodic Theory Dynam. Systems, vol. 14, iss. 2, pp. 213-235, 1994.
    @article {burton94, MRKEY = {1279469},
      AUTHOR = {Burton, Robert and Steif, Jeffrey E.},
      TITLE = {Non-uniqueness of measures of maximal entropy for subshifts of finite type},
      JOURNAL = {Ergodic Theory Dynam. Systems},
      FJOURNAL = {Ergodic Theory and Dynamical Systems},
      VOLUME = {14},
      YEAR = {1994},
      NUMBER = {2},
      PAGES = {213--235},
      ISSN = {0143-3857},
      MRCLASS = {28D20 (22D40 54H20 82B20 82B26)},
      MRNUMBER = {95f:28023},
      MRREVIEWER = {Meir Smorodinsky},
      ZBLNUMBER = {0807.58023},
      }
  • [CP75] Go to document E. M. Coven and M. E. Paul, "Sofic systems," Israel J. Math., vol. 20, iss. 2, pp. 165-177, 1975.
    @article {CP75, MRKEY = {0383379},
      AUTHOR = {Coven, Ethan M. and Paul, Michael E.},
      TITLE = {Sofic systems},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {20},
      YEAR = {1975},
      NUMBER = {2},
      PAGES = {165--177},
      ISSN = {0021-2172},
      MRCLASS = {54H20},
      MRNUMBER = {52 \#4260},
      MRREVIEWER = {R. L. Adler},
      DOI = {10.1007/BF02757884},
      ZBLNUMBER = {0307.28015},
      }
  • [MCK76] M. Denker, C. Grillenberger, and K. Sigmund, Ergodic Theory on Compact Spaces, New York: Springer-Verlag, 1976, vol. 527.
    @book {MCK76, MRKEY = {0457675},
      AUTHOR = {Denker, Manfred and Grillenberger, Christian and Sigmund, Karl},
      TITLE = {Ergodic Theory on Compact Spaces},
      SERIES = {Lecture Notes in Math.},
      VOLUME={527},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1976},
      PAGES = {iv+360},
      MRCLASS = {28A65 (54H20)},
      MRNUMBER = {56 \#15879},
      MRREVIEWER = {W. Parry},
      ZBLNUMBER = {0328.28008},
      }
  • [D06] Go to document A. Desai, "Subsystem entropy for $\Bbb Z^d$ sofic shifts," Indag. Math., vol. 17, iss. 3, pp. 353-359, 2006.
    @article {D06, MRKEY = {2321105},
      AUTHOR = {Desai, Angela},
      TITLE = {Subsystem entropy for {$\Bbb Z\sp d$} sofic shifts},
      JOURNAL = {Indag. Math.},
      FJOURNAL = {Koninklijke Nederlandse Akademie van Wetenschappen. Indagationes Mathematicae. New Series},
      VOLUME = {17},
      YEAR = {2006},
      NUMBER = {3},
      PAGES = {353--359},
      ISSN = {0019-3577},
      MRCLASS = {37B10 (37B40)},
      MRNUMBER = {2321105},
      DOI = {10.1016/S0019-3577(06)80037-6},
      ZBLNUMBER = {1104.37006},
      }
  • [FJ99] Go to document S. Forchhammer and J. Justesen, "Entropy bounds for constrained two-dimensional random fields," IEEE Trans. Inform. Theory, vol. 45, iss. 1, pp. 118-127, 1999.
    @article {FJ99, MRKEY = {1677852},
      AUTHOR = {Forchhammer, Søren and Justesen, Jørn},
      TITLE = {Entropy bounds for constrained two-dimensional random fields},
      JOURNAL = {{\rm IEEE} Trans. Inform. Theory},
      FJOURNAL = {Institute of Electrical and Electronics Engineers. Transactions on Information Theory},
      VOLUME = {45},
      YEAR = {1999},
      NUMBER = {1},
      PAGES = {118--127},
      ISSN = {0018-9448},
      CODEN = {IETTAW},
      MRCLASS = {94A29 (94A17)},
      MRNUMBER = {99k:94023},
      DOI = {10.1109/18.746776},
      ZBLNUMBER = {0946.94011},
      }
  • [friedland97] Go to document S. Friedland, "On the entropy of $\Bbb Z^d$ subshifts of finite type," Linear Algebra Appl., vol. 252, pp. 199-220, 1997.
    @article {friedland97, MRKEY = {1428636},
      AUTHOR = {Friedland, Shmuel},
      TITLE = {On the entropy of {$\bold Z\sp d$} subshifts of finite type},
      JOURNAL = {Linear Algebra Appl.},
      FJOURNAL = {Linear Algebra and its Applications},
      VOLUME = {252},
      YEAR = {1997},
      PAGES = {199--220},
      ISSN = {0024-3795},
      CODEN = {LAAPAW},
      MRCLASS = {54H20 (28D99 54C70 82B05)},
      MRNUMBER = {98b:54052},
      MRREVIEWER = {Manfred Denker},
      DOI = {10.1016/0024-3795(95)00676-1},
      ZBLNUMBER = {0893.54031},
      }
  • [F05] Go to document S. Friedland and U. N. Peled, "Theory of computation of multidimensional entropy with an application to the monomer-dimer problem," Adv. in Applied Math., vol. 34, iss. 3, pp. 486-522, 2005.
    @article {F05, MRKEY = {2123547},
      AUTHOR = {Friedland, Shmuel and Peled, Uri N.},
      TITLE = {Theory of computation of multidimensional entropy with an application to the monomer-dimer problem},
      JOURNAL = {Adv. in Applied Math.},
      FJOURNAL = {Advances in Applied Mathematics},
      VOLUME = {34},
      YEAR = {2005},
      NUMBER = {3},
      PAGES = {486--522},
      ISSN = {0196-8858},
      MRCLASS = {82B20 (05B45)},
      MRNUMBER = {2005m:82020},
      MRREVIEWER = {Andr{á}s Kr{á}mli},
      DOI = {10.1016/j.aam.2004.08.005},
      ZBLNUMBER = {1076.82009},
      }
  • [GS98] Go to document C. Goodman-Strauss, "Matching rules and substitution tilings," Ann. of Math., vol. 147, iss. 1, pp. 181-223, 1998.
    @article {GS98, MRKEY = {1609510},
      AUTHOR = {Goodman-Strauss, Chaim},
      TITLE = {Matching rules and substitution tilings},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {147},
      YEAR = {1998},
      NUMBER = {1},
      PAGES = {181--223},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {52C22},
      MRNUMBER = {99m:52027},
      MRREVIEWER = {E. Hertel},
      DOI = {10.2307/120988},
      ZBLNUMBER = {0941.52018},
      }
  • [HU79] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publ. Co., Reading, MA, 1979.
    @book {HU79, MRKEY = {645539},
      AUTHOR = {Hopcroft, John E. and Ullman, Jeffrey D.},
      TITLE = {Introduction to Automata Theory, Languages, and Computation},
      SERIES = {Addison-Wesley Series in Computer Science},
      PUBLISHER = {Addison-Wesley Publ. Co., Reading, MA},
      YEAR = {1979},
      PAGES = {x+418},
      ISBN = {0-201-02988-X},
      MRCLASS = {68-01 (03-01 03Dxx 68D05 68F05)},
      MRNUMBER = {83j:68002},
      MRREVIEWER = {S. Istrail},
      ZBLNUMBER = {0426.68001},
      }
  • [Hurd92] L. P. Hurd, J. Kari, and K. Culik, "The topological entropy of cellular automata is uncomputable," Ergodic Theory Dynam. Systems, vol. 12, iss. 2, pp. 255-265, 1992.
    @article {Hurd92, MRKEY = {1176622},
      AUTHOR = {Hurd, Lyman P. and Kari, Jarkko and Culik, Karel},
      TITLE = {The topological entropy of cellular automata is uncomputable},
      JOURNAL = {Ergodic Theory Dynam. Systems},
      FJOURNAL = {Ergodic Theory and Dynamical Systems},
      VOLUME = {12},
      YEAR = {1992},
      NUMBER = {2},
      PAGES = {255--265},
      ISSN = {0143-3857},
      MRCLASS = {58F08 (68Q80)},
      MRNUMBER = {93f:58124},
      MRREVIEWER = {M. L. Blank},
      ZBLNUMBER = {0770.58017},
      }
  • [K98] B. P. Kitchens, Symbolic Dynamics, One-Sided, Two-Sided and Countable State Markov Shifts, New York: Springer-Verlag, 1998.
    @book {K98, MRKEY = {1484730},
      AUTHOR = {Kitchens, Bruce P.},
      TITLE = {Symbolic Dynamics, One-Sided, Two-Sided and Countable State Markov Shifts},
      SERIES = {Universitext},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1998},
      PAGES = {x+252},
      ISBN = {3-540-62738-3},
      MRCLASS = {58F03 (54H20)},
      MRNUMBER = {98k:58079},
      MRREVIEWER = {Doris Fiebig},
      ZBLNUMBER = {0892.58020},
      }
  • [KO91] K. Ko, Complexity Theory of Real Functions, Boston: Birkhäuser, 1991.
    @book {KO91, MRKEY = {1137517},
      AUTHOR = {Ko, Ker-I},
      TITLE = {Complexity Theory of Real Functions},
      SERIES = {Prog. Theoret. Comput. Sci.},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Boston},
      YEAR = {1991},
      PAGES = {x+309},
      ISBN = {0-8176-3586-6},
      MRCLASS = {03D15 (03-02 03F60 26E40 65Y20 68Q15)},
      MRNUMBER = {93i:03057},
      MRREVIEWER = {Douglas S. Bridges},
      ZBLNUMBER = {0791.03019},
      }
  • [lind84] D. A. Lind, "The entropies of topological Markov shifts and a related class of algebraic integers," Ergodic Theory Dynam. Systems, vol. 4, iss. 2, pp. 283-300, 1984.
    @article {lind84, MRKEY = {766106},
      AUTHOR = {Lind, D. A.},
      TITLE = {The entropies of topological {M}arkov shifts and a related class of algebraic integers},
      JOURNAL = {Ergodic Theory Dynam. Systems},
      FJOURNAL = {Ergodic Theory and Dynamical Systems},
      VOLUME = {4},
      YEAR = {1984},
      NUMBER = {2},
      PAGES = {283--300},
      ISSN = {0143-3857},
      MRCLASS = {58F11 (15A48 28D20)},
      MRNUMBER = {86c:58092},
      MRREVIEWER = {W. Krieger},
      ZBLNUMBER = {0546.58035},
      }
  • [LM95] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge: Cambridge Univ. Press, 1995.
    @book {LM95, MRKEY = {1369092},
      AUTHOR = {Lind, Douglas and Marcus, Brian},
      TITLE = {An Introduction to Symbolic Dynamics and Coding},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1995},
      PAGES = {xvi+495},
      ISBN = {0-521-55124-2; 0-521-55900-6},
      MRCLASS = {58F03 (15A48 54H20 58F20 94A24 94B60)},
      MRNUMBER = {97a:58050},
      MRREVIEWER = {Petr K{\.u}rka},
      ZBLNUMBER = {1106.37301},
      }
  • [LS90] Go to document D. Lind, K. Schmidt, and T. Ward, "Mahler measure and entropy for commuting automorphisms of compact groups," Invent. Math., vol. 101, iss. 3, pp. 593-629, 1990.
    @article {LS90, MRKEY = {1062797},
      AUTHOR = {Lind, Douglas and Schmidt, Klaus and Ward, Tom},
      TITLE = {Mahler measure and entropy for commuting automorphisms of compact groups},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {101},
      YEAR = {1990},
      NUMBER = {3},
      PAGES = {593--629},
      ISSN = {0020-9910},
      CODEN = {INVMBH},
      MRCLASS = {22D40 (28D20)},
      MRNUMBER = {92j:22013},
      MRREVIEWER = {Meir Smorodinsky},
      DOI = {10.1007/BF01231517},
      ZBLNUMBER = {0774.22002},
      }
  • [M76] M. Misiurewicz, "A short proof of the variational principle for a ${\bf Z}_{+}^{N}$ action on a compact space," in International Conference on Dynamical Systems in Mathematical Physics, Paris: Soc. Math. France, 1976, vol. 40, pp. 147-157.
    @incollection {M76, MRKEY = {0444904},
      AUTHOR = {Misiurewicz, Micha{\l}},
      TITLE = {A short proof of the variational principle for a {${\bf Z}\sb{+}\sp{N}$} action on a compact space},
      BOOKTITLE = {International {C}onference on {D}ynamical {S}ystems in {M}athematical {P}hysics},
      VENUE={{R}ennes, 1975},
      PAGES = {147--157},
      SERIES={Astérisque},
      VOLUME={40},
      PUBLISHER = {Soc. Math. France},
      ADDRESS = {Paris},
      YEAR = {1976},
      MRCLASS = {28A65 (58F99)},
      MRNUMBER = {56 \#3250},
      MRREVIEWER = {P. Walters},
      ZBLNUMBER = {0368.54013},
      }
  • [mozes89] S. Mozes, "Tilings, substitution systems and dynamical systems generated by them," J. Analyse Math., vol. 53, pp. 139-186, 1989.
    @article {mozes89, MRKEY = {1014984},
      AUTHOR = {Mozes, Shahar},
      TITLE = {Tilings, substitution systems and dynamical systems generated by them},
      JOURNAL = {J. Analyse Math.},
      FJOURNAL = {Journal d'Analyse Mathématique},
      VOLUME = {53},
      YEAR = {1989},
      PAGES = {139--186},
      ISSN = {0021-7670},
      CODEN = {JOAMAV},
      MRCLASS = {58F03 (54H20 58F11)},
      MRNUMBER = {91h:58038},
      MRREVIEWER = {Peter Walters},
      ZBLNUMBER = {0745.52013},
      }
  • [P64] Go to document W. Parry, "Intrinsic Markov chains," Trans. Amer. Math. Soc., vol. 112, pp. 55-66, 1964.
    @article {P64, MRKEY = {0161372},
      AUTHOR = {Parry, William},
      TITLE = {Intrinsic {M}arkov chains},
      JOURNAL = {Trans. Amer. Math. Soc.},
      FJOURNAL = {Transactions of the American Mathematical Society},
      VOLUME = {112},
      YEAR = {1964},
      PAGES = {55--66},
      ISSN = {0002-9947},
      MRCLASS = {60.65},
      MRNUMBER = {28 \#4579},
      MRREVIEWER = {H. P. Edmundson},
      DOI = {10.2307/1994009},
      ZBLNUMBER = {0127.35301},
      }
  • [robinson71] Go to document R. M. Robinson, "Undecidability and nonperiodicity for tilings of the plane," Invent. Math., vol. 12, pp. 177-209, 1971.
    @article {robinson71, MRKEY = {0297572},
      AUTHOR = {Robinson, Raphael M.},
      TITLE = {Undecidability and nonperiodicity for tilings of the plane},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {12},
      YEAR = {1971},
      PAGES = {177--209},
      ISSN = {0020-9910},
      MRCLASS = {02G05 (05B45 52A45 68A10)},
      MRNUMBER = {45 \#6626},
      MRREVIEWER = {D. A. Klarner},
      DOI = {10.1007/BF01418780},
      ZBLNUMBER = {0197.46801},
      }
  • [R04] D. Ruelle, Thermodynamic Formalism, The Mathematical Structures of Equilibrium Statistical Mechanics, Second ed., Cambridge: Cambridge Univ. Press, 2004.
    @book {R04, MRKEY = {2129258},
      AUTHOR = {Ruelle, David},
      TITLE = {Thermodynamic Formalism, The Mathematical Structures of Equilibrium Statistical Mechanics},
      SERIES = {Cambridge Math. Lib.},
      EDITION = {Second},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2004},
      PAGES = {xx+174},
      ISBN = {0-521-54649-4},
      MRCLASS = {82B05 (37A60 37D35 37N20 82-02)},
      MRNUMBER = {2006a:82008},
      ZBLNUMBER = {1062.82001},
      }
  • [S48] C. E. Shannon, "A mathematical theory of communication," Bell System Tech. J., vol. 27, pp. 379-423, 623, 1948.
    @article {S48, MRKEY = {0026286},
      AUTHOR = {Shannon, C. E.},
      TITLE = {A mathematical theory of communication},
      JOURNAL = {Bell System Tech. J.},
      FJOURNAL = {The Bell System Technical Journal},
      VOLUME = {27},
      YEAR = {1948},
      PAGES = {379--423, 623--656},
      ISSN = {0005-8580},
      MRCLASS = {60.0X},
      MRNUMBER = {10,133e},
      MRREVIEWER = {J. L. Doob},
      ZBLNUMBER = {1154.94303},
      }
  • [S06] J. G. Simonsen, "On the computability of the topological entropy of subshifts," Discrete Math. Theor. Comput. Sci., vol. 8, iss. 1, pp. 83-95, 2006.
    @article {S06, MRKEY = {2247517},
      AUTHOR = {Simonsen, Jakob Grue},
      TITLE = {On the computability of the topological entropy of subshifts},
      JOURNAL = {Discrete Math. Theor. Comput. Sci.},
      FJOURNAL = {Discrete Mathematics \& Theoretical Computer Science. DMTCS.},
      VOLUME = {8},
      YEAR = {2006},
      NUMBER = {1},
      PAGES = {83--95},
      ISSN = {1365-8050},
      MRCLASS = {37B40 (03B25 37B10 37B15 68Q05 68Q45)},
      MRNUMBER = {2008b:37025},
      MRREVIEWER = {Enrico Formenti},
      ZBLNUMBER = {1153.37320},
      }
  • [W94] Go to document T. Ward, "Automorphisms of $\Bbb Z^d$-subshifts of finite type," Indag. Math., vol. 5, iss. 4, pp. 495-504, 1994.
    @article {W94, MRKEY = {1307966},
      AUTHOR = {Ward, Thomas},
      TITLE = {Automorphisms of {$\bold Z\sp d$}-subshifts of finite type},
      JOURNAL = {Indag. Math.},
      FJOURNAL = {Koninklijke Nederlandse Akademie van Wetenschappen. Indagationes Mathematicae. New Series},
      VOLUME = {5},
      YEAR = {1994},
      NUMBER = {4},
      PAGES = {495--504},
      ISSN = {0019-3577},
      MRCLASS = {28D15 (54H20)},
      MRNUMBER = {97a:28014},
      DOI = {10.1016/0019-3577(94)90020-5},
      ZBLNUMBER = {0823.28007},
      }
  • [W77] Go to document B. Weiss, "Subshifts of finite type and sofic systems," Monatsh. Math., vol. 77, pp. 462-474, 1973.
    @article {W77, MRKEY = {0340556},
      AUTHOR = {Weiss, Benjamin},
      TITLE = {Subshifts of finite type and sofic systems},
      JOURNAL = {Monatsh. Math.},
      VOLUME = {77},
      YEAR = {1973},
      PAGES = {462--474},
      MRCLASS = {28A65 (54H20)},
      MRNUMBER = {49 \#5308},
      MRREVIEWER = {R. L. Adler},
      DOI = {10.1007/BF01295322},
      ZBLNUMBER = {0285.28021},
      }
  • [W73] Go to document R. F. Williams, "Classification of subshifts of finite type," Ann. of Math., vol. 98, pp. 120-153; errata, ibid. 99 (1974), 380, 1973.
    @article {W73, MRKEY = {0331436},
      AUTHOR = {Williams, R. F.},
      TITLE = {Classification of subshifts of finite type},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {98},
      YEAR = {1973},
      PAGES = {120--153; errata, {\it ibid.} 99 (1974), 380--381},
      ISSN = {0003-486X},
      MRCLASS = {58F20 (28A65)},
      MRNUMBER = {48 \#9769},
      MRREVIEWER = {C. B. Thomas},
      DOI = {10.2307/1970908},
      ZBLNUMBER = {0282.58008},
      }

Mathematical Subject Classification
Primary: , , ,
DOI
http://doi.org/10.4007/annals.2010.171.2011
MR
2680402
zbMATH
1192.37022
Milestones
Received: 8 March 2007
Accepted: 11 April 2008

Authors

Michael Hochman

Department of Mathematics
Princeton University
Fine Hall - Washington Rd.
Princeton, NJ
United States
and
School of Mathematics
Institute for Advanced Study
Einstein Dr.
Princeton, NJ 08540
United States

Tom Meyerovitch

School of Mathematical Sciences
Tel Aviv University
Ramat Aviv
Tel Aviv 69978
Israel