On the Garden of Eden theorem for endomorphisms of symbolic algebraic varieties

algebraic cellular automaton algebraic mean dimension amenable group complete algebraic variety Garden of Eden theorem Krull dimension preinjectivity projective algebraic variety

Mathematics Subject Classification ID

Varieties and morphisms (14A10) Schemes and morphisms (14A15) Symbolic dynamics (37B10) Dynamical aspects of cellular automata (37B15) Means on groups, semigroups, etc.; amenable groups (43A07)

Abstract: Let

G

be an amenable group and let

X

be an irreducible complete algebraic variety over an algebraically closed field

K

. Let

A

denote the set of

K

-points of

X

and let

a u c o l o n A^{G} o A^{G}

be an algebraic cellular automaton over

(G, X, K)

, that is, a cellular automaton over the group

G

and the alphabet

A

whose local defining map is induced by a morphism of

K

-algebraic varieties. We introduce a weak notion of pre-injectivity for algebraic cellular automata, namely

(*)

-pre-injectivity, and prove that

a u

is surjective if and only if it is

(*)

-pre-injective. In particular,

a u

has the Myhill property, i.e., is surjective whenever it is pre-injective. Our result gives a positive answer to a question raised by Gromov in~cite{gromov-esav} and yields an analogue of the classical Moore-Myhill Garden of Eden theorem.

Review text

One of the fundamental properties of finite sets is: ``a self-map is injective if and only if it is surjective. The famous Ax's theorem (``any injective regular selfmapping of a complex algebraic variety is surjective) was deeply investigated by \textit{M. Gromov} [J. Eur. Math. Soc. (JEMS) 1, No. 2, 109--197 (1999; Zbl 0998.14001)], who extended it to the proalgebraic setting (inverse limits of algebraic varieties). In this manner, it connects to the theory of cellular automata, which are none but continuous equivariant self-maps on a space \(A^G\) for \(A\) a finite set and \(G\) a group (typically \(\mathbb Z^2\)). Indeed \(A^G\) is the inverse limit of \(A^X\) where \(X\) runs over finite subsets of \(G\). The classical results in the universe of cellular automata are variations on this theme: due to \textit{E. F. Moore} [in: Proc. Sympos. Appl. Math. 14, 17--33 (1962; Zbl 0126.32408)] and \textit{J. Myhill} [Proc. Am. Math. Soc. 14, 685--686 (1963; Zbl 0126.32501)], they come under the name of ``Garden of Eden theorem: for \(G=\mathbb Z^n\), a cellular automaton is surjective if and only if it is \emph{pre-injective}, namely it distinguishes configurations which differ in finitely many coordinates. A pioneering work by the first author [\textit{T. G. Ceccherini-Silberstein} et al., Ann. Inst. Fourier 49, No. 2, 673--685 (1999; Zbl 0920.43001)] proved that this holds whenever \(G\) is \emph{amenable}. A common setting encompassing both these results is hinted at in Gromov's article cited above, who asks ``Does the Garden of Eden theorem generalize to the proalgebraic category? First, one asks if preinjectivity implies surjectivity, while the reverse implication needs further modification of definitions. This question is answered in the present article when the proalgebraic variety is of the form \(A^G\) for \(A\) being an irreducible, complete algebraic variety over an algebraically closed field. The endomorphism \(\tau\colon A^G\to A^G\) is defined by a morphism \(A^X\to A\) for a finite subset \(X\) of \(G\) (the ``local rule), and extended by \(G\)-equivariance. The authors need to redefine pre-injectivity of \(\tau\) appropriately: it is the \emph{inexistence} of a finite subset \(Y\subset G\) and a proper, Zariski-closed subset \(H\subset A^Y\) such that \(\tau(A^Y\times\{p\})=\tau(H\times\{p\})\) for all \(p\in A^{G\setminus Y}\). In the case of \(A\) finite, this definition coincides with the old one (i.e., if \(p,q\in A^G\) differ on \(Y\subset G\) finite and have same image under \(\tau\), consider \(H=A^Y\setminus\{p\restriction Y\}\); if \(\tau(A^Y\times\{p\})=\tau(H\times\{p\})\), extend \(p\) to \(G\) in two manners, within and without \(H\)). Once the proper definition is set up, the proof proceeds along the usual strategy of relating both pre-injectivity and surjectivity to preservation of the ``mean dimension, a limiting, scaled dimension taken along restrictions to a Følner sequence. The article ends with an interesting collection of counterexamples showing that the hypotheses of their main result cannot be easily weakened.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: On the Garden of Eden theorem for endomorphisms of symbolic algebraic varieties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189528)