Hostname: page-component-848d4c4894-hfldf Total loading time: 0 Render date: 2024-06-01T23:29:57.167Z Has data issue: false hasContentIssue false
  • English
  • Français

A Garden of Eden theorem for linear subshifts

Published online by Cambridge University Press:  13 June 2011

TULLIO CECCHERINI-SILBERSTEIN  and
MICHEL COORNAERT
TULLIO CECCHERINI-SILBERSTEIN
Affiliation:
Dipartimento di Ingegneria, Università del Sannio, Corso Garibaldi 107, 82100 Benevento, Italy (email: tceccher@mat.uniroma1.it)
MICHEL COORNAERT
Affiliation:
Institut de Recherche Mathématique Avancée, Université de Strasbourg et CRNS, 7 rue René-Descartes, 67000 Strasbourg, France (email: coornaert@math.unistra.fr)
Get access Rights & Permissions [Opens in a new window]

Abstract

Let G be an amenable group and let V be a finite-dimensional vector space over an arbitrary field 𝕂. We prove that if X⊂VG is a strongly irreducible linear subshift of finite type and τ:X→X is a linear cellular automaton, then τ is surjective if and only if it is pre-injective. We also prove that if G is countable and X⊂VG is a strongly irreducible linear subshift, then every injective linear cellular automaton τ:X→X is surjective.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 32 , Issue 1 , February 2012 , pp. 81 - 102
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bourbaki, N.. Éléments de Mathématique: Topologie Générale. Hermann, Paris, 1971, Chapitres 1–4.Google Scholar
[2]Ceccherini-Silberstein, T. and Coornaert, M.. The Garden of Eden theorem for linear cellular automata. Ergod. Th. & Dynam. Sys. 26 (2006), 53–68.CrossRefGoogle Scholar
[3]Ceccherini-Silberstein, T. and Coornaert, M.. Injective linear cellular automata and sofic groups. Israel J. Math. 161 (2007), 1–15.CrossRefGoogle Scholar
[4]Ceccherini-Silberstein, T. and Coornaert, M.. Amenability and linear cellular automata over semisimple modules of finite length. Comm. Algebra 36 (2008), 1320–1335.CrossRefGoogle Scholar
[5]Ceccherini-Silberstein, T. and Coornaert, M.. Induction and restriction of cellular automata. Ergod. Th. & Dynam. Sys. 29 (2009), 371–380.CrossRefGoogle Scholar
[6]Ceccherini-Silberstein, T. and Coornaert, M.. Cellular Automata and Groups (Springer Monographs in Mathematics). Springer, Berlin, 2010.CrossRefGoogle Scholar
[7]Ceccherini-Silberstein, T. and Coornaert, M.. On the reversibility and the closed image property of linear cellular automata. Theoret. Comput. Sci. 412 (2011), 300–306.CrossRefGoogle Scholar
[8]Ceccherini-Silberstein, T., Machì, A. and Scarabotti, F.. Amenable groups and cellular automata. Ann. Inst. Fourier (Grenoble) 49 (1999), 673–685.CrossRefGoogle Scholar
[9]Elek, G.. The rank of finitely generated modules over group algebras. Proc. Amer. Math. Soc. 131 (2003), 3477–3485 (electronic).CrossRefGoogle Scholar
[10]Elek, G. and Szabó, E.. Sofic groups and direct finiteness. J. Algebra 280 (2004), 426–434.CrossRefGoogle Scholar
[11]Fiorenzi, F.. The Garden of Eden theorem for sofic shifts. Pure Math. Appl. 11 (2000), 471–484.Google Scholar
[12]Fiorenzi, F.. Cellular automata and strongly irreducible shifts of finite type. Theoret. Comput. Sci. 299 (2003), 477–493.CrossRefGoogle Scholar
[13]Følner, E.. On groups with full Banach mean value. Math. Scand. 3 (1955), 243–254.CrossRefGoogle Scholar
[14]Gottschalk, W.. Some general dynamical notions. Recent Advances in Topological Dynamics (Proc. Conf. on Topological Dynamics, Yale University, New Haven, CT, 1972; in honor of Gustav Arnold Hedlund) (Lecture Notes in Mathematics, 318). Springer, Berlin, 1973, pp. 120–125.Google Scholar
[15]Greenleaf, F. P.. Invariant Means on Topological Groups and their Applications (Van Nostrand Mathematical Studies, 16). Van Nostrand Reinhold, New York, 1969.Google Scholar
[16]Gromov, M.. Endomorphisms of symbolic algebraic varieties. J. Eur. Math. Soc. 1 (1999), 109–197.CrossRefGoogle Scholar
[17]Gromov, M.. Topological invariants of dynamical systems and spaces of holomorphic maps. I. Math. Phys. Anal. Geom. 2 (1999), 323–415.CrossRefGoogle Scholar
[18]Grothendieck, A.. Éléments de géométrie algébrique. III. Étude cohomologique des faisceaux cohérents. I. Publ. Math. Inst. Hautes Études Sci. 11 (1961), 167pp.Google Scholar
[19]Hedlund, G. A.. Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory 3 (1969), 320–375.CrossRefGoogle Scholar
[20]Krieger, F.. Le lemme d’Ornstein–Weiss d’après Gromov. Dynamics, Ergodic Theory, and Geometry (Mathematical Sciences Research Institute Publications, 54). Cambridge University Press, Cambridge, 2007, pp. 99–111.CrossRefGoogle Scholar
[21]Ornstein, D. S. and Weiss, B.. Entropy and isomorphism theorems for actions of amenable groups. J. Anal. Math. 48 (1987), 1–141.CrossRefGoogle Scholar
[22]Paterson, A. L. T.. Amenability (Mathematical Surveys and Monographs, 29). American Mathematical Society, Providence, RI, 1988.CrossRefGoogle Scholar
[23]Weiss, B.. Sofic groups and dynamical systems. Sankhyā Ser. A 62 (2000), 350–359  (Ergodic Theory and Harmonic Analysis, Mumbai, 1999).Google Scholar