New York Journal of Mathematics
Volume 23 (2017) 1417-1425


Laurent Bartholdi

Cellular automata, duality and sofic groups

view    print

Published: October 13, 2017
Keywords: Linear cellular automata, preinjective and postsurjective endomorphisms, Garden of Eden theorem
Subject: 68Q80 (primary: Cellular automata), 43A07 (Amenable groups)

We produce for arbitrary nonamenable group G and field K a nonpreinjective, surjective linear cellular automaton. This answers positively Open Problem (OP-14) in Ceccherini-Silberstein and Coornaert's monograph "Cellular Automata and Groups''.

We also reprove in a direct manner, for linear cellular automata, the result by Capobianco, Kari and Taati that cellular automata over sofic groups are injective if and only if they are postsurjective.

These results come from considerations related to matrices over group rings: we prove that a matrix's kernel and the image of its adjoint are mutual orthogonals of each other. This gives rise to a notion of "dual cellular automaton'', which is preinjective if and only if the original cellular automaton is surjective, and is injective if and only if the original cellular automaton is postsurjective.


This work is supported by the "@raction'' grant ANR-14-ACHN-0018-01

Author information

Département de Mathématiques et Applications, École Normale Supérieure, Paris and Mathematisches Institut, Georg-August Universität zu Göttingen