Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings

This paper is a slightly extended version of the lecture given by the first author at the “5th International Algebraic Conference in Ukraine” held on July 20–27 2005 at the Odessa I.I. Mechnikov National University.

Збережено в:

Бібліографічні деталі
Дата:	2006
Автори:	Ceccherini-Silberstein, T., Coornaert, M.
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут прикладної математики і механіки НАН України 2006
Назва видання:	Algebra and Discrete Mathematics
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/157384
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings / T. Ceccherini-Silberstein, M. Coornaert // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 2. — С. 22–35. — Бібліогр.: 31 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-157384
record_format	dspace
spelling	irk-123456789-1573842019-06-21T01:27:35Z Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings Ceccherini-Silberstein, T. Coornaert, M. This paper is a slightly extended version of the lecture given by the first author at the “5th International Algebraic Conference in Ukraine” held on July 20–27 2005 at the Odessa I.I. Mechnikov National University. 2006 Article Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings / T. Ceccherini-Silberstein, M. Coornaert // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 2. — С. 22–35. — Бібліогр.: 31 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 37B15, 68Q80, 43A07, 20F65, 16S34, 16S50. http://dspace.nbuv.gov.ua/handle/123456789/157384 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	This paper is a slightly extended version of the lecture given by the first author at the “5th International Algebraic Conference in Ukraine” held on July 20–27 2005 at the Odessa I.I. Mechnikov National University.
format	Article
author	Ceccherini-Silberstein, T. Coornaert, M.
spellingShingle	Ceccherini-Silberstein, T. Coornaert, M. Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings Algebra and Discrete Mathematics
author_facet	Ceccherini-Silberstein, T. Coornaert, M.
author_sort	Ceccherini-Silberstein, T.
title	Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings
title_short	Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings
title_full	Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings
title_fullStr	Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings
title_full_unstemmed	Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings
title_sort	linear cellular automata: garden of eden theorem, l-surjunctivity and group rings
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2006
url	http://dspace.nbuv.gov.ua/handle/123456789/157384
citation_txt	Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings / T. Ceccherini-Silberstein, M. Coornaert // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 2. — С. 22–35. — Бібліогр.: 31 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT ceccherinisilbersteint linearcellularautomatagardenofedentheoremlsurjunctivityandgrouprings AT coornaertm linearcellularautomatagardenofedentheoremlsurjunctivityandgrouprings
first_indexed	2025-07-14T09:49:20Z
last_indexed	2025-07-14T09:49:20Z
_version_	1837615348104298496
fulltext	Algebra and Discrete Mathematics RESEARCH ARTICLE Number 2. (2006). pp. 22 – 35 c© Journal “Algebra and Discrete Mathematics” Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings Tullio Ceccherini-Silberstein, Michel Coornaert Communicated by V. V. Kirichenko Dedicated to the memory of V. M. Usenko Abstract. This paper is a slightly extended version of the lecture given by the first author at the “5th International Algebraic Conference in Ukraine” held on July 20–27 2005 at the Odessa I.I. Mechnikov National University. 1. Cellular automata 1.1. Finitely generated groups Let G be a finitely generated group. Fix a finite generating system S which is symmetric (i.e. s ∈ S ⇒ s−1 ∈ S). Then the Cayley graph of G w.r. to S is the graph Cay(G, S) with vertex set G and edges {g, gs}, g ∈ G and s ∈ S. The S-length ℓS(g) of a group element g ∈ G is defined by ℓS(1G) = 0 (where 1G denotes the unit element in G) and, for g 6= 1G, ℓS(g) = min{n ∈ N : g = s1s2 · · · sn, si ∈ S}. The finitely generated group G can then be endowed with a metric space structure by introducing the distance function dS : G × G → R+ defined by setting, for all g, h ∈ G, dS(g, h) = ℓS(g−1h). 2000 Mathematics Subject Classification: 37B15, 68Q80, 43A07, 20F65, 16S34, 16S50. Key words and phrases: Linear cellular automaton, Garden of Eden theorem, amenable group, sofic group, surjunctivity, group ring, zero-divisor problem. T. Ceccherini-Silberstein, M. Coornaert 23 Note that, denoting by dCay(G,S) the geodesic distance in the Cayley graph G of G w.r. to S and identifying a group element in G with the corre- sponding vertex in Cay(G, S), one has dS(g, h) = dCay(G,S)(g, h) for all g, h ∈ G. For g ∈ G and r ∈ N we denote by B(g; r) = {h ∈ G : dS(g, h) ≤ r} the ball of radius r centered at g. In the classical case G is the lattice Z 2 of integer points of Eu- clidean plane. In von Neumann’s terminology [vN2] the generating sys- tem for Z 2 is SvN = {(1, 0), (−1, 0), (0, 1), (0,−1)} while in Moore’s [Moo], SM = SvN ∪ {(1, 1), (1,−1), (−1, 1), (−1,−1)}. Note that the corre- sponding Cayley graphs induce a tessellation of the Euclidean plane into squares; in the classical framework one considers these squares, called cells, rather than the vertices of these squares (i.e. the vertices of the graphs): this point of view is clearly equivalent as these graphs are iso- morphic to their dual graphs (that is the graphs whose vertices are the cells, and two cells are neighbour if they share a common edge). 1G g4 g2 g1 g3 1G g7 g3 g1g8 g2 g5g6 g4 (von Neumann’s) (Moore’s) Figure 1. The ball B(1G; 1) of radius one in Z 2. 1.2. Cellular automata The notion of a cellular automaton goes back to J. von Neumann [vN2] and S. Ulam [U]. Let G be a finitely generated group, called the universe, and let A be a set, called the alphabet or the set of states. A configuration is a map x : G → A. The space AG of all configurations is equipped with the right action of G defined by G×AG ∋ (g, x) 7→ xg ∈ AG, where xg(g′) = x(gg′) for all g′ ∈ G. 24 Linear cellular automata One defines a distance function d : AG × AG → R+ by setting for x, y ∈ AG d(x, y) = { 0 if x = y 1 n where n = max{r ∈ N : x\|B(1G;r) ≡ y\|B(1G;r)}. When A is finite, the configuration space AG becomes a compact totally disconnected metric space. A cellular automaton over G on the alphabet A is a map τ : AG → AG satisfying the following condition: there exists a finite subset M ⊂ G and a map µ : AM → A such that τ(x)(g) = µ (x(g1g), x(g2g), . . . , x(gtg)) ≡ µ(xg\|M ) (1.1) for all x ∈ AG, g ∈ G, where xg\|M denotes the restriction of xg to M and {g1, g2, . . . , gt} = M . Such a set M is called a memory set and µ is called a local defining map for τ . Note that, when G is finitely generated, say by a finite symmetric generating system S, it is not restrictive to choose as a memory set for τ , a ball B(1G; r) of radius r ∈ N centered at 1G w.r. to the distance dS induced by S. Let us note that every cellular automaton τ : AG → AG is G−equiva- riant, i.e., it satisfies τ(xg) = τ(x)g for all g ∈ G and x ∈ AG. The following fact characterizes the “locality” of cellular automata from a topological point of view. Theorem 1.1 (Hedlund). Suppose that A is finite. A map τ : AG → AG is a cellular automaton if and only if τ is (uniformly) continuous and G−equivariant. 1.3. An example: Conway’s game of life In order to give the reader an explicit example of a cellular automaton we present here the Game of life of John H. Conway. T. Ceccherini-Silberstein, M. Coornaert 25 y= 0 = absence of life, i= 1 = presence of life. Figure 2. The local rule for Conway’s Game of life −→ −→ −→ −→ Survival Death Death Birth iy y yy y ii i y � � � i y y yy i y � � � yy y i y � � �y i � � � i y � � � y i y � � � ii y i � � � y i � � �i i y i y � � � y i � � � y yy y yy y ii i i The set of states is A = {0, 1}; state 0 corresponds to absence of life while state 1 indicates life; therefore passing from 0 to 1 can be interpreted as birth, while passing from 1 to 0 corresponds to death. The universe is Z 2 with Moore’s system of generators (cfr. Figure 1), so that the ball B((0, 0); 1) consists of the 9 points (x1, x2) ∈ Z 2 with \|x1\| ≤ 1 and \|x2\| ≤ 1. 26 Linear cellular automata The local map is defined as follows: f(a(0,0), a(1,0), . . . , a(−1,−1)) =    1 if { either ∑ s∈S as = 3 or ∑ s∈S as = 2 and a(0,0) = 1 0 otherwise. In other words [BCG, Chapter 25] for the transition map one has: - Birth: a cell that is dead at time t becomes live at time t+1 if and only if three of its neighbours are live at time t. - Survival: a cell that is live at time t will remain live at t + 1 if and only if it has just two or three live neighbours at time t. - Death by overcrowding: a cell that is live at time t and has four or more of its neighbours live at time t will be dead at time t + 1: food will not suffice. - Death by isolation: a cell that has at most one live neighbour at time t becomes depressed and will be dead at time t + 1. 1.4. Amenability and entropy Let G be a countable group (e.g. a finitely generated group) and let P(G) denote the set of all subsets of G. The group G is said to be amenable if there exists a right-invariant mean that is a map µ : P(G) → [0, 1] satisfying the following conditions: (1) µ(G) = 1 (normalization); (2) µ(A ∪ B) = µ(A) + µ(B) for all A, B ∈ P(G) such that A ∩ B = ∅ (finite additivity); (3) µ(Ag) = µ(A) for all g ∈ G and A ∈ P(G) (right-invariance). We mention that if G is amenable, namely such a right-invariant mean exists, then also left-invariant and in fact even bi-invariant means do exist. The class of amenable groups includes, in particular, finite groups, solvable groups and finitely–generated groups of subexponential growth. It is closed under the operations of taking subgroups, taking factors, taking extensions and taking directed unions. The free group F2 on two generators and therefore all groups containing non-abelian free subgroups are non-amenable. We mention that there exist periodic (and thus with no free subgroups) non amenable groups: the first examples are due to Ol’shanski [Ol]; later Adyan [Ady] showed that also the free Burnside groups B(m, n) = 〈s1, s2, . . . , sm : wn〉 of rank m ≥ 2 and odd exponent n ≥ 665 are non-amenable. We mention that in both cases the non- amenability is detected by applying Grigorchuk’s cogrowth criterion for T. Ceccherini-Silberstein, M. Coornaert 27 amenability.Recently Olshanskii and Sapir [OlS] found examples of non- amenable groups with no free subgroups in the class of finitely presented groups. It follows from a result of Følner [Føl] that a countable group G is amenable if and only if it admits a Følner sequence, i.e., a sequence (Ωn)n∈N of non-empty finite subsets of G such that lim n→∞ \|∂E(Ωn)\| \|Ωn\| = 0 for all finite subsets E ⊂ G, (1.2) where ∂E(Ω) = Ω△EΩ is the symmetric difference of Ω and EΩ = {eω : e ∈ E, ω ∈ Ω}. For instance, for G = Z 2 one can take as Følner sets the squares Ωn = [−n, n] × [−n, n]. Suppose that G is amenable and fix a Følner sequence (Ωn)n∈N. For a subset X ⊂ AG of configurations, in order to measure its “size” inside AG, one introduces an asymptotic density, called entropy, as follows: ent(Ωn)(X) = lim sup n→∞ log\|A\| \|XΩn \| \|Ωn\| (1.3) where, for any subset Ω ⊂ G XΩ = {x\|Ω : x ∈ X} denotes the set of restrictions to Ω of all configurations in X. Note that if X is G−invariant, then the above liminf in (1.3) is in fact a limit and does not depend on the particular Følner sequence (Ωn)n∈N; this follows from a well known result of Ornstein and Weiss in [OrW]. One clearly has ent(AG) = 1 and ent(X) ≤ ent(Y ) if X ⊂ Y . 1.5. Pre-injectivity, Gardens of Eden and entropy Let Y be a set. Following a terminology introduced by Gromov [Gro1], one says that a map f : AG → Y is pre-injective if the equality f(x) = f(x′) implies x = x′ for all x, x′ ∈ AG such that {g ∈ G : x(g) 6= x′(g)} is finite. Clearly, every injective map AG → Y is pre-injective but the converse is not true in general. Given a cellular automaton τ : AG → AG, one often speaks of τ as being time: if x ∈ AG is the configuration of the universe at time t, then τ [x] is the configuration of the universe at time t + 1. An initial configuration is a configuration at time t = 0. A configuration x not in the image of τ , namely x ∈ AG \ τ [AG], is called a Garden of Eden configuration, briefly a GOE configuration, this biblical terminology being 28 Linear cellular automata motivated by the fact that GOE configurations may only appear as initial configurations. The following theorem is called the Garden of Eden Theorem be- cause it gives a necessary and sufficient condition for the surjectivity of certain cellular automata. It was first proved by Moore and My- hill for G = Z 2. Then it was extended to groups of sub-exponential growth by Mach̀ı and Mignosi [MaMi] and to general amenable groups by Ceccherini-Silberstein, Mach̀ı and Scarabotti [CMS]. Theorem 1.2. Let G be a countable amenable group and let A be a finite set. Let τ : AG → AG be a cellular automaton. The following are equivalent: - τ is surjective (i.e. there are no GOE configurations); - τ is pre-injective; - τ preserves the entropy: ent(τ [AG]) = 1. As Conway’s game of life is concerned, we have that this cellular automaton is clearly not preinjective (the constant dead configuration and the configuration with only one live cell have the same image) and by the previous theorem it is not surjective either. In the non-amenable setting the above theorem fails to hold in general. Let G be any group containing the free group F2. In [CMS] it is presented the construction of two cellular automata over G such that: the first one is pre-injective not surjective, the second one is surjective not pre-injective. It is not known whether the GOE theorem only holds for amenable groups or not: clearly, if this is the case, a new characterization of amenability would derive. 2. Surjunctivity and sofic groups 2.1. Surjunctivity A group G is surjunctive (a terminology due to Gottschalk [Got]) if, given any finite alphabet A, any injective cellular automaton τ : AG → AG is surjective. In other words, uniqueness implies existence for solutions of the equation y = τ(x). This property is reminiscent of several other classes of mathematical objects for which injective endomorphisms are always surjective (finite sets, finite-dimensional vector spaces, algebraic varieties, co-Hopfian groups, etc.). Recall that a group G is said to be residually finite if for every element g 6= 1G in G there exist a finite group F and a homomorphism h : G → F such that h(g) 6= 1F . This amounts to saying that the intersection of all subgroups of finite index of G is reduced to the identity element. The T. Ceccherini-Silberstein, M. Coornaert 29 class of residually finite groups is quite large. For instance, every finitely generated subgroup of GLn(C) is residually finite. However, there are finitely generated amenable groups, and even finitely generated solvable groups, which are not residually finite. Lawton proved that residually finite groups are surjunctive. From Theorem 1.2 one immediately deduces that amenable groups are surjunctive. 2.2. Sofic groups Let S be a set. A S-labeled graph is a triple (Q, E, λ), where Q is a set, E is a symmetric subset of Q×Q and λ is a map from E to S. We shall view every subgraph of a labeled graph as a labeled graph in the obvious way. Let (Q, E, λ) and (Q′, E′, λ′) be S-labeled graphs. Two vertices q ∈ Q and q′ ∈ Q′ are said to be r-equivalent and we write q ∼r q′ if the balls B(q, r) and B(q′, r) are isomorphic as labeled graphs (i.e. there is a bijection ϕ : B(q, r) → B(q′, r) sending q to q′ such that (q1, q2) ∈ E ∩ (B(q, r)×B(q, r)) if and only if (ϕ(q1), ϕ(q2)) ∈ E′ ∩ (B(q′, r)×B(q′, r)) and λ(q1, q2) = λ′(ϕ(q1), ϕ(q2)). Let G be a finitely generated group and let S be a finite symmetric generating subset of G. The group G is said to be sofic if for all ε > 0 and r ∈ N there exists a finite S-labeled graph (Q, E, λ) such that the set Q(r) ⊂ Q defined by Q(r) = {q ∈ Q : q ∼r 1G} (here 1G is considered as a vertex in the Cayley graph Cay(G, S)) satisfies \|Q(r)\| ≥ (1 − ε)\|Q\| (2.1) where \| · \| denotes cardinality. It can be shown (see [Wei]) that this definition does not depend on the choice of S and that it can be extended as follows. A (not necessarily finitely generated) group G is said to be sofic if all of its finitely generated subgroups are sofic. Sofic groups were introduced by M. Gromov in [Gro1] under the name of initially amenable groups. The sofic terminology is due to B. Weiss [Wei] The class of sofic groups contains, in particular, all residually amenable groups and it is closed under direct products, free products, taking subgroups and extensions by amenable groups [ES2]. Theorem 2.1 ([Wei]). Sofic groups are surjunctive. In other words, given a finite set A and a sofic group G, any injective cellular automaton τ : AG → AG is automatically surjective. We end this section by mentioning that there is no known example of a non-surjunctive group nor even of a non-sofic group up to now. 30 Linear cellular automata 3. Linear cellular automata 3.1. Linear cellular automata and linear subshifts A linear cellular automaton is a cellular automaton τ : V G → V G, where the alphabet V is a vector space over some field K and τ is linear. As an example, let G be a group, S a non-empty finite (not neces- sarily symmetric) subset of G and V a vector space over a field K whose characteristic is not equal to the cardinality of S. The Laplace operator associated with S is the linear cellular automa- ton LS : V G → V G defined by LS(x)(g) = x(g) − 1 \|S\| ∑ s∈S x(gs) for all x ∈ V G and g ∈ G. Note that LS is never injective for V 6= 0 since all constant functions G → V are in the kernel of LS . Note that V G (equipped with the Tychonov product topology where V is endowed with the discrete topology) is no longer a compact space so that many topological arguments based on compactness need to be obtained with an alternative method. As an example, the following facts, which are almost trivial in the classical (finite alphabet case) framework, need an appropriate proof. Lemma 3.1 ([CeC1]). Let G be a countable group and let V be a finite- dimensional vector space over a field K. Let τ : V G → V G be a linear cellular automaton. Then τ(V G) is a closed subspace of V G. A subset X ⊂ V G is called a linear subshift if it is a closed G−invariant vector subspace of V G. We extend our definition of a linear cellular automaton to linear sub- shifts in the following way. Let X, Y ⊂ V G be linear subshifts. A map τ : X → Y is called a linear cellular automaton if it is the restriction τ = τ \|X of a linear cellular automaton τ : V G → V G. Theorem 3.2 ([CeC2]). Let G be a countable group and let V be a finite-dimensional vector space over a field K. Let X, Y ⊂ V G be linear subshifts and suppose that τ : X → Y is a bijective cellular automaton. Then the inverse map τ−1 : Y → X is also a linear cellular automaton. T. Ceccherini-Silberstein, M. Coornaert 31 3.2. Mean dimension For linear cellular automata the following notion of mean dimension plays the role of entropy used in the classical framework, namely, for cellular automata with a finite alphabet. Let G be a countable amenable group and V a finite-dimensional vector space over a field K. Fix a Følner sequence (Ωn)n∈N for G. Given a vector subspace X of V G and a subset Ω ⊂ G, we denote by XΩ{x\|Ω : x ∈ X} the projection of X on V Ω, where, as above, x\|Ω denotes the restriction of x to Ω. The mean dimension of X (with respect to the Følner sequence (Ωn)n∈N) is the non–negative number mdim(X) = lim inf n→∞ dim(XΩn ) \|Ωn\| . (3.1) Note that it immediately follows from this definition that mdim(V G) = dim(V ) and that mdim(X) ≤ dim(V ) for every vec- tor subspace X of V G. More generally, one has mdim(X) ≤ mdim(Y ) if X and Y are vector subspaces of V G such that X ⊂ Y . Again, if X is G−invariant, the result of Ornstein and Weiss [OrW] implies that in (3.1) we have a limit and that it does not depend on the particular choice of the Følner sequence (Ωn)n∈N for G. 3.3. GOE theorem and L-surjunctivity for linear cellular au- tomata The linear analogue of the Garden of Eden Theorem for linear cellular automata states as follows. Theorem 3.3 ([CeC1]). Let V be a finite-dimensional vector space over a field K and let G be a countable amenable group. Let τ : V G → V G be a linear cellular automaton. Then the following are equivalent. - τ is surjective (i.e. there are no GOE configurations); - τ is pre-injective; - τ preserves the mean dimension: mdim(τ [V G]) = dim(V ). Also, say that a group G is L−surjunctive if for any field K and finite dimensional vector space V over K, any injective linear cellular automaton τ : V G → V G is automatically surjective. Theorem 3.4 ([CeC2]). Sofic groups are L−surjunctive. 32 Linear cellular automata 4. Applications to ring theory Let G be a group and K a field. We denote by K[G] the group ring of G with coefficients in K, that is, the vector space over K with basis the ele- ments of G, endowed with the bilinear product induced by multiplication in G. 4.1. Zero-divisors in group rings Recall that, given a ring R, an element a ∈ R is a (proper)zero-divisor if a 6= 0 and there exists b ∈ R such that either ab = 0 or ba = 0. If a group G has torsion, that is it contains an element g0 6= 1G of finite order, say gn 0 = 1G, then (1G−g0)(1G+g0+g2 0+· · ·+gn−1 0 ) = (1G+g0+g2 0+· · ·+gn−1 0 )(1G−g0) = 0, thus showing that K[G] has proper zero-divisors. A famous long standing open problem in the theory of group rings is Kaplansky zero-divisor problem [Kap1] which asks whether K[G] has no proper zero-divisors whenever G is torsion-free. The zero-divisor problem is known to have an affirmative answer for the class of unique-product (briefly u-p) groups (a group G is u-p, [Pas1], if given two non-empty finite subsets A, B ⊂ G there exists an element g = g(A, B) ∈ G which can be uniquely expressed as a product g = ab with a ∈ A and b ∈ B); indeed if α = ∑ a∈A λaa and β = ∑ b∈B λ′ bb ∈ K[G] with non-empty finite supports A and B ⊂ G, respectively, then their product αβ does not vanish at g(A, B). The class of u-p groups contains the class of ordered groups (a group G is ordered, [Pas1], if it admits a total order ≤ such that g1 ≤ g2 implies gg1 ≤ gg2 for all g, g1, g2 ∈ G); indeed we can take g(A, B) = minAbm where bm = minB. In the class of ordered groups one finds the free groups, the free abelian groups, the fundamental groups of surfaces and the braid groups. In the setting of linear cellular automata we have the following result which is a reformulation of Kaplansky zero-divisor problem. Theorem 4.1 ([CeC1]). A group ring K[G] has no zero-divisors if and only if every linear cellular automaton τ : K G → K G is pre-injective. 4.2. Direct finiteness of group rings Recall that a ring R with identity element 1R is said to be directly finite if one-sided inverses in R are also two-sided inverses, i.e., ab = 1R implies ba = 1R for a, b ∈ R. The ring R is said to be stably finite if the ring T. Ceccherini-Silberstein, M. Coornaert 33 Md(R) of d × d matrices with coefficients in R is directly finite for all integer d ≥ 1. Commutative rings and finite rings are obviously directly finite. Also observe that if elements a and b of a ring R satisfy ab = 1R then (ba)2 = ba, that is, ba is an idempotent. Therefore if the only idempotents of R are 0R and 1R (e.g. if R has no proper zero-divisors) then R is directly finite. The class of directly finite rings is closed under taking subrings, direct products, and direct limits. The ring of endomorphisms of an infinite-dimensional vector space yields an example of a ring which is not directly finite. Kaplansky [Kap2] observed that, for any group G and any field K of characteristic 0, the group ring K[G] is stably finite (see [Mon] and [Pas2] for detailed proofs in the case K = C) and asked whether this property remains true for fields of characteristic p > 0. We have that this holds for L-surjunctive groups. Theorem 4.2 ([CeC2]). A group G is L-surjunctive if and only if the group ring K[G] is stably finite for any field K. As an immediate consequence of Theorems 3.4 and 4.2, we deduce the following result which has been previously established by G. Elek and A. Szabó [ES1] using different methods (their proof involves embeddings of the group rings into continuous von Neumann regular rings). Corollary 4.3 ([ES1]). Let G be a sofic group and K any field. Then the group ring K[G] is stably finite. In particular, K[G] is directly finite. References [Ady] S.I. Adyan, Random walks on free periodic groups, Math. USSR Izvestiya, 21 (1983), 425–434. [BCG] E.R. Berlekamp, J.H. Conway and R.K. Guy, Winning Ways for your mathe- matical plays, vol 2, Chapter 25, Academic Press 1982. [CeC1] T. Ceccherini-Silberstein, M. Coornaert, The Garden of Eden theorem for linear cellular automata, Ergodic Theory Dynam. Systems (to appear). [CeC2] T. Ceccherini-Silberstein and M. Coornaert, Injective linear cellular automata and sofic groups, preprint 2005. [CGH] T. Ceccherini-Silberstein, R.I. Grigorchuk and P. de la Harpe, Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces, Proc. Steklov Inst. Math., 224 (1999), 57-97. [CMS] T.G. Ceccherini-Silberstein, A. Mach̀ı and F. Scarabotti, Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble), 49 (1999), 673–685. [ES1] G. Elek, A. Szabó, Sofic groups and direct finiteness, J. Algebra 280 (2004) 426-434. [ES2] G. Elek, A. Szabó, On sofic groups, J. Group Theory (to appear). 34 Linear cellular automata [Føl] E. Følner, On groups with full Banach mean value, Math. Scand. 3 (1955), 245– 254. [Got] W. Gottschalk, Some general dynamical systems, Recent advances in topological dynamics, pp. 120–125, Lecture Notes in Math. 318, Springer, Berlin, 1973. [Gre] F.P. Greenleaf, Invariant means on topological groups and their applications, Van Nostrand, 1969. [Gro1] M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS) 1 (1999), 109–197. [Gro2] M. Gromov, Topological invariants of dynamical systems and spaces of holo- morphic maps, Part I, Math. Phys. Anal. Geom. 2 (1999), 323–415. [Kap1] I. Kaplansky, Problems in the theory of rings. Report of a conference on linear algebras, June, 1956, pp. 1-3. National Academy of Sciences-National Research Council, Washington, Publ. 502, 1957. [Kap2] I. Kaplansky, Fields and Rings, Chicago Lectures in Math. Univ. of Chicago Press, Chicago, 1969. [LiM] D. Lind, B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cam- bridge University Press, Cambridge, 1995. [LiW] E. Lindenstrauss and B. Weiss, Mean topological dimension, Israel J. Math. 115 (2000), 1–24. [MaMi] A. Mach̀ı and F. Mignosi, Garden of Eden configurations for cellular automata on Cayley graphs of groups, SIAM J. Disc. Math. 6 (1993), 44–56. [Mon] M.S. Montgomery, Left and right inverses in group algebras, Bull. Amer. Math. Soc. 75 (1969), 539–540. [Moo] E.F. Moore, Machine Models of Self-Reproduction, Proc. Symp. Appl. Math., AMS Providence R.I. 14 (1963), 17-34. [Myh] J. Myhill, The converse of Moore’s Garden of Eden Theorem, Proc. Amer. Math. Soc. 14 (1963), 685–686. [vN1] J. von Neumann, Zur allgemeinen Theorie des Masses, Fund. Math. 13 (1930), 73–116. [vN2] J. von Neumann, The Theory of Self-Reproducing Automata (A. Burks ed.), University of Illinois Press, Urbana and London, 1966. [Ol] A.Yu. Ol’shanskii, On the question of the existence of an invariant mean on a group Uspekhi Mat. Nauk 35 (1980), no. 4 (214), 199–200. [OlS] A.Yu. Ol’shanskii and M. Sapir, Non-amenable finitely presented torsion-by- cyclic groups, Publ. Math. Inst. Hautes Études Sci. No. 96 (2002), 43–169 (2003). [OrW] D.S. Ornstein and B. Weiss, Entropy and isomorphism theorems for actions of amenable groups, J. Analyse Math. 48 (1987), 1–141. [Pas1] D.S. Passman, The algebraic structure of group rings. Reprint of the 1977 original. Robert E. Krieger Publishing Co., Inc., Melbourne, FL, 1985. [Pas2] D.S. Passman, Idempotents in group rings, Proc. Amer. Math. Soc. 28 (1971), 371–374. [Pat] A. Paterson, Amenability, AMS Mathematical Surveys and Monographs, 29, American Mathematical Society, 1988. [U] S. Ulam, Processes and Transformations, in: Proc. Int. Cong. Mathem. 2 (1952), 264-275. T. Ceccherini-Silberstein, M. Coornaert 35 [Wei] B. Weiss, Sofic groups and dynamical systems, (Ergodic theory and harmonic analysis, Mumbai, 1999) Sankhya Ser. A. 62 (2000), 350–359. Contact information Tullio Ceccherini- Silberstein Dipartimento di Ingegneria, Università del Sannio, C.so Garibaldi 107, 82100 Ben- evento, Italy E-Mail: tceccher@mat.uniroma1.it Michel Coornaert Institut de Recherche Mathématique Avancée, Université Louis Pasteur et CNRS, 7 rue René-Descartes, 67084 Strasbourg Cedex, France E-Mail: coornaert@math.u-strasbg.fr Received by the editors: 26.11.2005 and in final form 30.06.2006.

Linear cellular automata: Garden of Eden Theorem, L-surjunctivity and group rings

Репозитарії

Схожі ресурси