2019, 15: 427-435. doi: 10.3934/jmd.2019026

The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics (Brin Prize article)

Department of Mathematics, University of Maryland, College Park, MD 20742-4015, USA

Received  October 24, 2018 Published  December 2019

Fund Project: This article is based on the talk I gave on the occasion of Mike Hochman's being awarded the Brin Prize. I am grateful to Nishant Chandgotia, Emmanuel Jeandel, Doug Lind, and Anush Tserunyan for very helpful feedback.

We review the impact of Mike Hochman's work on mutlidimensional symbolic dynamics and Borel dynamics.

Citation: Mike Boyle. The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics. Journal of Modern Dynamics, 2019, 15: 427-435. doi: 10.3934/jmd.2019026
References:
[1]

R. L. Adler and B. Marcus, Topological entropy and equivalence of dynamical systems, Mem. Amer. Math. Soc., 20 (1979). doi: 10.1090/memo/0219.

[2]

N. AubrunS. Barbieri and M. Sablik, A notion of effectiveness for subshifts on finitely generated groups, Theoret. Comput. Sci., 661 (2017), 35-55.  doi: 10.1016/j.tcs.2016.11.033.

[3]

N. Aubrun and M. Sablik, Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl. Math., 126 (2013), 35-63.  doi: 10.1007/s10440-013-9808-5.

[4]

R. J. Baxter, Exactly solved models in statistical mechanics, Academic Press, Inc., London, 1989.

[5]

R. Bowen, Topological entropy for noncompact sets, Trans. Amer. Math. Soc., 184 (1973), 125-136.  doi: 10.1090/S0002-9947-1973-0338317-X.

[6]

M. Boyle and J. Buzzi, The almost Borel structure of surface diffeomorphisms, Markov shifts and their factors, J. Eur. Math. Soc. (JEMS), 19 (2017), 2739-2782.  doi: 10.4171/JEMS/727.

[7]

M. BoyleJ. Buzzi and R. Gómez, Almost isomorphism for countable state Markov shifts, J. Reine Angew. Math., 592 (2006), 23-47.  doi: 10.1515/CRELLE.2006.021.

[8]

D. Burguet, Topological and almost Borel universality for systems with the weak specification property, Ergodic Theory Dynam. Systems, (first published online February 2019). doi: 10.1017/etds.2019.7.

[9]

D. Burguet, Topological and almost Borel universality for systems with the weak specification property, preprint, arXiv: 1901.00666.

[10]

J. Buzzi, Intrinsic ergodicity of smooth interval maps, Israel J. Math., 100 (1997), 125-161.  doi: 10.1007/BF02773637.

[11]

N. Chandgotia and T. Meyerovitch, Borel subsystems and ergodic universality for compact $\mathbb Z^d$-systems via specification and beyond, preprint, arXiv: 1903.05716.

[12]

C. T. ConleyA. S. Kechris and B. D. Miller, Stationary probability measures and topological realizations, Israel J. Math., 198 (2013), 333-345.  doi: 10.1007/s11856-013-0025-8.

[13]

M. Delacourt and B. Hellouin de Menibus, Characterisation of limit measures of higher-dimensional cellular automata, Theory Comput. Syst., 61 (2017), 1178-1213.  doi: 10.1007/s00224-017-9753-1.

[14]

R. DoughertyS. Jackson and A. S. Kechris, The structure of hyperfinite Borel equivalence relations, Trans. Amer. Math. Soc., 341 (1994), 193-225.  doi: 10.1090/S0002-9947-1994-1149121-0.

[15]

B. Durand and A. Romashchenko, On the expressive power of quasiperiodic SFT, 42nd International Symposium on Mathematical Foundations of Computer Science, 2017.

[16]

B. Durand, A. Romashchenko and A. Shen, Effective closed subshifts in 1D can be implemented in 2D, in Fields of Logic and Computation, Lecture Notes in Computer Science, 6300, Springer, Berlin, 2010,208–226. doi: 10.1007/978-3-642-15025-8_12.

[17]

P. Guillon and C. Zinoviadis, Densities and entropies in cellular automata, in How the World Computes, Lecture Notes in Computer Science, 7318, Springer, Heidelberg, 2012,253–263. doi: 10.1007/978-3-642-30870-3_26.

[18]

B. Hellouin de Menibus and M. Sablik, Characterization of sets of limit measures of a cellular automaton iterated on a random configuration, Ergodic Theory Dynam. Systems, 38 (2018), 601-650.  doi: 10.1017/etds.2016.46.

[19]

M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167.  doi: 10.1007/s00222-008-0161-7.

[20]

M. Hochman, Isomorphism and embedding of Borel systems on full sets, Acta Appl. Math., 126 (2013), 187-201.  doi: 10.1007/s10440-013-9813-8.

[21]

M. Hochman, Every Borel automorphism without finite invariant measures admits a two-set generator, J. Eur. Math. Soc. (JEMS), 21 (2019), 271-317.  doi: 10.4171/JEMS/836.

[22]

M. Hochman, Multidimensional shifts of finite type and sofic shifts, in Combinatorics, Words and Symbolic Dynamics, Encyclopedia Math. Appl., 159, Cambridge Univ. Press, Cambridge, 2016, 296–358.

[23]

M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math. (2), 171 (2010), 2011–2038. doi: 10.4007/annals.2010.171.2011.

[24]

S. JacksonA. S. Kechris and A. Louveau, Countable Borel equivalence relations, J. Math. Log., 2 (2002), 1-80.  doi: 10.1142/S0219061302000138.

[25]

E. Jeandel, Computability in symbolic dynamics, in Pursuit of the Universal, Lecture Notes in Computer Science, 9709, Springer, 2016,124–131. doi: 10.1007/978-3-319-40189-8_13.

[26]

E. Jeandel and P. Vanier, Characterizations of periods of multi-dimensional shifts, Ergodic Theory Dynam. Systems, 35 (2015), 431-460.  doi: 10.1017/etds.2013.60.

[27]

J. Kari, Rice's theorem for the limit sets of cellular automata, Theoret. Comput. Sci., 127 (1994), 229-254.  doi: 10.1016/0304-3975(94)90041-8.

[28]

J. Kari, Cellular automata, tilings and (un)computability, in Combinatorics, Words and Symbolic Dynamics, Encyclopedia Math. Appl., 159, Cambridge Univ. Press, Cambridge, 2016, 241–295.

[29]

P. W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice, Physica, 27 (1961), 1209-1225.  doi: 10.1016/0031-8914(61)90063-5.

[30]

W. Krieger, On entropy and generators of measure-preserving transformations, Trans. Amer. Math. Soc., 149 (1970), 453-464.  doi: 10.1090/S0002-9947-1970-0259068-3.

[31]

E. H. Lieb, Residual entropy of square ice, Phys. Rev., 162, 1967. doi: 10.1103/PhysRev.162.162.

[32]

D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dynam. Systems, 4 (1984), 283-300.  doi: 10.1017/S0143385700002443.

[33]

D. Lind, Multi-dimensional symbolic dynamics, in Symbolic Dynamics and Its Applications, Proc. Sympos. Appl. Math., 60, Amer. Math. Soc., Providence, RI, 2004, 61–79. doi: 10.1090/psapm/060/2078846.

[34]

K. McGoff and R. Pavlov, Random $\Bbb{Z}^d$-shifts of finite type, J. Mod. Dyn., 10 (2016), 287-330.  doi: 10.3934/jmd.2016.10.287.

[35]

T. Meyerovitch, Growth-type invariants for $\Bbb Z^d$ subshifts of finite type and arithmetical classes of real numbers, Invent. Math., 184 (2011), 567-589.  doi: 10.1007/s00222-010-0296-1.

[36]

S. Mozes, Tilings, substitution systems and dynamical systems generated by them, J. Analyse Math., 53 (1989), 139-186.  doi: 10.1007/BF02793412.

[37]

R. Pavlov and M. Schraudner, Entropies realizable by block gluing $\Bbb{Z}^d$ shifts of finite type, J. Anal. Math., 126 (2015), 113-174.  doi: 10.1007/s11854-015-0014-4.

[38]

A. Quas and T. Soo, Ergodic universality of some topological dynamical systems, Trans. Amer. Math. Soc., 368 (2016), 4137–4170. doi: 10.1090/tran/6489.

[39]

R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.  doi: 10.1007/BF01418780.

[40]

S. Shelah and B. Weiss, Measurable recurrence and quasi-invariant measures, Israel J. Math., 43 (1982), 154-160.  doi: 10.1007/BF02761726.

[41]

S. G. Simpson, Medvedev degrees of two-dimensional subshifts of finite type, Ergodic Theory Dynam. Systems, 34 (2014), 679-688.  doi: 10.1017/etds.2012.152.

[42]

A. Tserunyan, Finite generators for countable group actions in the Borel and Baire category settings, Adv. Math., 269 (2015), 585-646.  doi: 10.1016/j.aim.2014.10.013.

[43]

B. Weiss, Measurable dynamics, in Conference in Modern Analysis and Probability, Contemp. Math., 26, Amer. Math. Soc., Providence, RI, 1984,395–421. doi: 10.1090/conm/026/737417.

[44]

B. Weiss, Countable generators in dynamics–-universal minimal models, in Measure and Measurable Dynamics, Contemp. Math., 94, Amer. Math. Soc., Providence, RI, 1989,321–326. doi: 10.1090/conm/094/1013000.

[45]

C. Zinoviadis, Hierarchy and expansiveness in 2D subshifts of finite type, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 8977, Springer, Cham, 2015,365–377. doi: 10.1007/978-3-319-15579-1_28.

show all references

References:
[1]

R. L. Adler and B. Marcus, Topological entropy and equivalence of dynamical systems, Mem. Amer. Math. Soc., 20 (1979). doi: 10.1090/memo/0219.

[2]

N. AubrunS. Barbieri and M. Sablik, A notion of effectiveness for subshifts on finitely generated groups, Theoret. Comput. Sci., 661 (2017), 35-55.  doi: 10.1016/j.tcs.2016.11.033.

[3]

N. Aubrun and M. Sablik, Simulation of effective subshifts by two-dimensional subshifts of finite type, Acta Appl. Math., 126 (2013), 35-63.  doi: 10.1007/s10440-013-9808-5.

[4]

R. J. Baxter, Exactly solved models in statistical mechanics, Academic Press, Inc., London, 1989.

[5]

R. Bowen, Topological entropy for noncompact sets, Trans. Amer. Math. Soc., 184 (1973), 125-136.  doi: 10.1090/S0002-9947-1973-0338317-X.

[6]

M. Boyle and J. Buzzi, The almost Borel structure of surface diffeomorphisms, Markov shifts and their factors, J. Eur. Math. Soc. (JEMS), 19 (2017), 2739-2782.  doi: 10.4171/JEMS/727.

[7]

M. BoyleJ. Buzzi and R. Gómez, Almost isomorphism for countable state Markov shifts, J. Reine Angew. Math., 592 (2006), 23-47.  doi: 10.1515/CRELLE.2006.021.

[8]

D. Burguet, Topological and almost Borel universality for systems with the weak specification property, Ergodic Theory Dynam. Systems, (first published online February 2019). doi: 10.1017/etds.2019.7.

[9]

D. Burguet, Topological and almost Borel universality for systems with the weak specification property, preprint, arXiv: 1901.00666.

[10]

J. Buzzi, Intrinsic ergodicity of smooth interval maps, Israel J. Math., 100 (1997), 125-161.  doi: 10.1007/BF02773637.

[11]

N. Chandgotia and T. Meyerovitch, Borel subsystems and ergodic universality for compact $\mathbb Z^d$-systems via specification and beyond, preprint, arXiv: 1903.05716.

[12]

C. T. ConleyA. S. Kechris and B. D. Miller, Stationary probability measures and topological realizations, Israel J. Math., 198 (2013), 333-345.  doi: 10.1007/s11856-013-0025-8.

[13]

M. Delacourt and B. Hellouin de Menibus, Characterisation of limit measures of higher-dimensional cellular automata, Theory Comput. Syst., 61 (2017), 1178-1213.  doi: 10.1007/s00224-017-9753-1.

[14]

R. DoughertyS. Jackson and A. S. Kechris, The structure of hyperfinite Borel equivalence relations, Trans. Amer. Math. Soc., 341 (1994), 193-225.  doi: 10.1090/S0002-9947-1994-1149121-0.

[15]

B. Durand and A. Romashchenko, On the expressive power of quasiperiodic SFT, 42nd International Symposium on Mathematical Foundations of Computer Science, 2017.

[16]

B. Durand, A. Romashchenko and A. Shen, Effective closed subshifts in 1D can be implemented in 2D, in Fields of Logic and Computation, Lecture Notes in Computer Science, 6300, Springer, Berlin, 2010,208–226. doi: 10.1007/978-3-642-15025-8_12.

[17]

P. Guillon and C. Zinoviadis, Densities and entropies in cellular automata, in How the World Computes, Lecture Notes in Computer Science, 7318, Springer, Heidelberg, 2012,253–263. doi: 10.1007/978-3-642-30870-3_26.

[18]

B. Hellouin de Menibus and M. Sablik, Characterization of sets of limit measures of a cellular automaton iterated on a random configuration, Ergodic Theory Dynam. Systems, 38 (2018), 601-650.  doi: 10.1017/etds.2016.46.

[19]

M. Hochman, On the dynamics and recursive properties of multidimensional symbolic systems, Invent. Math., 176 (2009), 131-167.  doi: 10.1007/s00222-008-0161-7.

[20]

M. Hochman, Isomorphism and embedding of Borel systems on full sets, Acta Appl. Math., 126 (2013), 187-201.  doi: 10.1007/s10440-013-9813-8.

[21]

M. Hochman, Every Borel automorphism without finite invariant measures admits a two-set generator, J. Eur. Math. Soc. (JEMS), 21 (2019), 271-317.  doi: 10.4171/JEMS/836.

[22]

M. Hochman, Multidimensional shifts of finite type and sofic shifts, in Combinatorics, Words and Symbolic Dynamics, Encyclopedia Math. Appl., 159, Cambridge Univ. Press, Cambridge, 2016, 296–358.

[23]

M. Hochman and T. Meyerovitch, A characterization of the entropies of multidimensional shifts of finite type, Ann. of Math. (2), 171 (2010), 2011–2038. doi: 10.4007/annals.2010.171.2011.

[24]

S. JacksonA. S. Kechris and A. Louveau, Countable Borel equivalence relations, J. Math. Log., 2 (2002), 1-80.  doi: 10.1142/S0219061302000138.

[25]

E. Jeandel, Computability in symbolic dynamics, in Pursuit of the Universal, Lecture Notes in Computer Science, 9709, Springer, 2016,124–131. doi: 10.1007/978-3-319-40189-8_13.

[26]

E. Jeandel and P. Vanier, Characterizations of periods of multi-dimensional shifts, Ergodic Theory Dynam. Systems, 35 (2015), 431-460.  doi: 10.1017/etds.2013.60.

[27]

J. Kari, Rice's theorem for the limit sets of cellular automata, Theoret. Comput. Sci., 127 (1994), 229-254.  doi: 10.1016/0304-3975(94)90041-8.

[28]

J. Kari, Cellular automata, tilings and (un)computability, in Combinatorics, Words and Symbolic Dynamics, Encyclopedia Math. Appl., 159, Cambridge Univ. Press, Cambridge, 2016, 241–295.

[29]

P. W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice, Physica, 27 (1961), 1209-1225.  doi: 10.1016/0031-8914(61)90063-5.

[30]

W. Krieger, On entropy and generators of measure-preserving transformations, Trans. Amer. Math. Soc., 149 (1970), 453-464.  doi: 10.1090/S0002-9947-1970-0259068-3.

[31]

E. H. Lieb, Residual entropy of square ice, Phys. Rev., 162, 1967. doi: 10.1103/PhysRev.162.162.

[32]

D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dynam. Systems, 4 (1984), 283-300.  doi: 10.1017/S0143385700002443.

[33]

D. Lind, Multi-dimensional symbolic dynamics, in Symbolic Dynamics and Its Applications, Proc. Sympos. Appl. Math., 60, Amer. Math. Soc., Providence, RI, 2004, 61–79. doi: 10.1090/psapm/060/2078846.

[34]

K. McGoff and R. Pavlov, Random $\Bbb{Z}^d$-shifts of finite type, J. Mod. Dyn., 10 (2016), 287-330.  doi: 10.3934/jmd.2016.10.287.

[35]

T. Meyerovitch, Growth-type invariants for $\Bbb Z^d$ subshifts of finite type and arithmetical classes of real numbers, Invent. Math., 184 (2011), 567-589.  doi: 10.1007/s00222-010-0296-1.

[36]

S. Mozes, Tilings, substitution systems and dynamical systems generated by them, J. Analyse Math., 53 (1989), 139-186.  doi: 10.1007/BF02793412.

[37]

R. Pavlov and M. Schraudner, Entropies realizable by block gluing $\Bbb{Z}^d$ shifts of finite type, J. Anal. Math., 126 (2015), 113-174.  doi: 10.1007/s11854-015-0014-4.

[38]

A. Quas and T. Soo, Ergodic universality of some topological dynamical systems, Trans. Amer. Math. Soc., 368 (2016), 4137–4170. doi: 10.1090/tran/6489.

[39]

R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12 (1971), 177-209.  doi: 10.1007/BF01418780.

[40]

S. Shelah and B. Weiss, Measurable recurrence and quasi-invariant measures, Israel J. Math., 43 (1982), 154-160.  doi: 10.1007/BF02761726.

[41]

S. G. Simpson, Medvedev degrees of two-dimensional subshifts of finite type, Ergodic Theory Dynam. Systems, 34 (2014), 679-688.  doi: 10.1017/etds.2012.152.

[42]

A. Tserunyan, Finite generators for countable group actions in the Borel and Baire category settings, Adv. Math., 269 (2015), 585-646.  doi: 10.1016/j.aim.2014.10.013.

[43]

B. Weiss, Measurable dynamics, in Conference in Modern Analysis and Probability, Contemp. Math., 26, Amer. Math. Soc., Providence, RI, 1984,395–421. doi: 10.1090/conm/026/737417.

[44]

B. Weiss, Countable generators in dynamics–-universal minimal models, in Measure and Measurable Dynamics, Contemp. Math., 94, Amer. Math. Soc., Providence, RI, 1989,321–326. doi: 10.1090/conm/094/1013000.

[45]

C. Zinoviadis, Hierarchy and expansiveness in 2D subshifts of finite type, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 8977, Springer, Cham, 2015,365–377. doi: 10.1007/978-3-319-15579-1_28.

[1]

Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete and Continuous Dynamical Systems - S, 2009, 2 (2) : 301-314. doi: 10.3934/dcdss.2009.2.301

[2]

Dmitry Dolgopyat, Bassam Fayad, Sixu Liu. Multiple Borel–Cantelli Lemma in dynamics and MultiLog Law for recurrence. Journal of Modern Dynamics, 2022, 18: 209-289. doi: 10.3934/jmd.2022009

[3]

Mikhail Lyubich. Forty years of unimodal dynamics: On the occasion of Artur Avila winning the Brin Prize. Journal of Modern Dynamics, 2012, 6 (2) : 183-203. doi: 10.3934/jmd.2012.6.183

[4]

Giovanni Forni. On the Brin Prize work of Artur Avila in Teichmüller dynamics and interval-exchange transformations. Journal of Modern Dynamics, 2012, 6 (2) : 139-182. doi: 10.3934/jmd.2012.6.139

[5]

Stefano Marmi. Some arithmetical aspects of renormalization in Teichmüller dynamics: On the occasion of Corinna Ulcigrai winning the Brin Prize. Journal of Modern Dynamics, 2022, 18: 131-147. doi: 10.3934/jmd.2022006

[6]

Viktoria Xing. Dynamical Borel–Cantelli lemmas. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1737-1754. doi: 10.3934/dcds.2020339

[7]

Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete and Continuous Dynamical Systems, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725

[8]

James Kingsbery, Alex Levin, Anatoly Preygel, Cesar E. Silva. Dynamics of the $p$-adic shift and applications. Discrete and Continuous Dynamical Systems, 2011, 30 (1) : 209-218. doi: 10.3934/dcds.2011.30.209

[9]

Jim Wiseman. Symbolic dynamics from signed matrices. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 621-638. doi: 10.3934/dcds.2004.11.621

[10]

George Osipenko, Stephen Campbell. Applied symbolic dynamics: attractors and filtrations. Discrete and Continuous Dynamical Systems, 1999, 5 (1) : 43-60. doi: 10.3934/dcds.1999.5.43

[11]

Mike Boyle, Sompong Chuysurichay. The mapping class group of a shift of finite type. Journal of Modern Dynamics, 2018, 13: 115-145. doi: 10.3934/jmd.2018014

[12]

Dong Han Kim. The dynamical Borel-Cantelli lemma for interval maps. Discrete and Continuous Dynamical Systems, 2007, 17 (4) : 891-900. doi: 10.3934/dcds.2007.17.891

[13]

Dominique Lecomte. Hurewicz-like tests for Borel subsets of the plane. Electronic Research Announcements, 2005, 11: 95-102.

[14]

Runlin Zhang. Equidistribution of translates of a homogeneous measure on the Borel–Serre compactification. Discrete and Continuous Dynamical Systems, 2022, 42 (4) : 2053-2071. doi: 10.3934/dcds.2021183

[15]

Jose S. Cánovas, Tönu Puu, Manuel Ruiz Marín. Detecting chaos in a duopoly model via symbolic dynamics. Discrete and Continuous Dynamical Systems - B, 2010, 13 (2) : 269-278. doi: 10.3934/dcdsb.2010.13.269

[16]

Nicola Soave, Susanna Terracini. Symbolic dynamics for the $N$-centre problem at negative energies. Discrete and Continuous Dynamical Systems, 2012, 32 (9) : 3245-3301. doi: 10.3934/dcds.2012.32.3245

[17]

Dieter Mayer, Fredrik Strömberg. Symbolic dynamics for the geodesic flow on Hecke surfaces. Journal of Modern Dynamics, 2008, 2 (4) : 581-627. doi: 10.3934/jmd.2008.2.581

[18]

Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 581-598. doi: 10.3934/dcds.2004.11.581

[19]

Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487

[20]

David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete and Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287

2021 Impact Factor: 0.641

Metrics

  • PDF downloads (268)
  • HTML views (389)
  • Cited by (0)

Other articles
by authors

[Back to Top]