Skip to main content
SpringerLink
Log in

Growth-type invariants for ℤd subshifts of finite type and arithmetical classes of real numbers

  • Published:
Inventiones mathematicae Aims and scope

Abstract

We discuss some numerical invariants of multidimensional shifts of finite type (SFTs) which are associated with the growth rates of the number of admissible finite configurations. Extending an unpublished example of Tsirelson (A strange two-dimensional symbolic system, 1992), we show that growth complexities of the form exp (n α+o(1)) are possible for non-integer α’s. In terminology of de Carvalho (Port. Math. 54(1):19–40, 1997), such subshifts have entropy dimension α. The class of possible α’s are identified in terms of arithmetical classes of real numbers of Weihrauch and Zheng (Math. Log. Q. 47(1):51–65, 2001).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahn, Y.-H., Dou, D., Park, K.K.: Entropy dimensions and variational principle. Trends Math. 10(2), 163–165 (2008)

    Google Scholar 

  2. Blume, F.: Possible rates of entropy convergence. Ergod. Theory Dyn. Syst. 17(1), 45–70 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  3. de Carvalho, M.: Entropy dimension of dynamical systems. Port. Math. 54(1), 19–40 (1997)

    MATH  Google Scholar 

  4. Einsiedler, M., Lind, D., Miles, R., Ward, T.: Expansive subdynamics for algebraic \({\Bbb{Z}}\sp d\)-actions. Ergod. Theory Dyn. Syst. 21(6), 1695–1729 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  5. Ferenczi, S., Park, K.K.: Entropy dimensions and a class of constructive examples. Discrete Contin. Dyn. Syst. 17(1), 133–141 (2007)

    MathSciNet  MATH  Google Scholar 

  6. Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176(1), 131–167 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. (2) 171(3), 2010–2038 (2010)

    Article  MathSciNet  Google Scholar 

  8. Katok, A., Thouvenot, J.-P.: Slow entropy type invariants and smooth realization of commuting measure-preserving transformations. Ann. Inst. Henri Poincaré Probab. Stat. 33(3), 323–338 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  9. Kim, K.H., Ormes, N.S., Roush, F.W.: The spectra of nonnegative integer matrices via formal power series. J. Am. Math. Soc. 13(4), 773–806 (2000) (electronic)

    Article  MathSciNet  MATH  Google Scholar 

  10. Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995)

    Book  MATH  Google Scholar 

  11. Lind, D.A.: The entropies of topological Markov shifts and a related class of algebraic integers. Ergod. Theory Dyn. Syst. 4(2), 283–300 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  12. Meyerovitch, T.: Finite entropy for multidimensional cellular automata. Ergod. Theory Dyn. Syst. 28(1), 61–83 (2008)

    MathSciNet  Google Scholar 

  13. Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12, 177–209 (1971)

    Article  MathSciNet  Google Scholar 

  14. Simpson, S.G.: Medvedev degrees of 2-dimensional subshifts of finite type (2007)

  15. Tsirelson, B.: A strange two-dimensional symbolic system. Unpublished notes from Tel Aviv University Math Colloquim (1992)

  16. Zheng, X., Weihrauch, K.: The arithmetical hierarchy of real numbers. Math. Log. Q. 47(1), 51–65 (2001)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Pacific Institute for the Mathematical Science, 107-1933 West Mall, Vancouver, British Columbia, V6T 1Z2, Canada

    Tom Meyerovitch

Authors
  1. Tom Meyerovitch
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tom Meyerovitch.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Meyerovitch, T. Growth-type invariants for ℤd subshifts of finite type and arithmetical classes of real numbers. Invent. math. 184, 567–589 (2011). https://doi.org/10.1007/s00222-010-0296-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00222-010-0296-1

Mathematics Subject Classification (2000)

Search

Navigation