Computational and Combinatorial aspects of Symbolic Dynamics on Groups. – CoCoGro

Given one or more geometric shapes (tiles), it seems natural to wonder whether they can tile the plane or not - with no overlap or gap. More precisely and in ascending order of complexity, we may wonder if the set of tiles can tile the whole plane; if it can do so in a periodic way; and how many different tilings exist. These three problems, formulated for a combinatoric version of tilings, tilings by Wang tiles, have proven to be highly difficult. This kind of tilings - also called subshifts of finite type (SFT) - are sets of colourings of the infinite grid that respect a finite number of local constraints. They can fruitfully be seen as a computational model since they can be used to encode Turing machine computations, as well as a discrete model for dynamical systems, which is the point of view of symbolic dynamics. This model has been adapted to the hyperbolic plane and to trees, but we can go further and generalize it: the infinite grid is seen as the group Z², and this group is replaced by any finitely generated group. This new point of view has two advantages: first, it unifies previous examples and will lead to results not specific to one group. Second, it defines a worthwhile computational model, relatively unexplored until now: subshifts on groups. For computer scientists, mathematical notions based on group theory provide a new and deeper understanding of subshifts as computational model. On the other hand, this computer science approach offers an innovative point of view on groups that will interest mathematicians, for instance by providing new invariants. All this perfectly illustrates how mathematics and theoretical computer science can benefit from each other.

This project focuses on the three aforementioned challenges, and explores which dynamical, combinatorial or geometric properties of the group control the computational and combinatorial properties of the subshifts it defines. First, it is noteworthy that the question of the existence of a colouring - emptiness problem - for SFTs is decidable on Z, whereas it becomes undecidable on Z². But can we characterize groups having a decidable emptiness problem? The second question concerns aperiodic subshifts - subshifts in which no colouring is left invariant by a translation. On Z, SFTs are too simple objects to produce only aperiodic configurations, while Z² does admit aperiodic SFTs. But for which groups can SFTs force aperiodicity? The third question concerns entropy, i.e. the growth rate of patterns of size n that appear in the subshift. Computing this entropy is easy for SFTs on Z, but entropy function is uncomputable for SFTs on Z². Even if we override the uncomputability of the function and focus on particular examples of SFTs, computing the entropy remains a difficult task. Indeed, a closed formula for entropy is known only for a few simple SFTs on Z². Can we compute the exact value of entropy of other 2D SFTs, and give sharp approximations on the entropy of SFTs on Z²?

In the last ten years, the introduction of tools from computability theory, and more precisely the use of subshifts as computational models, has proven highly efficient by providing a solution to long-standing problems in symbolic dynamics. Even more recently, the international community of symbolic dynamicists, who traditionally focused on the cases of Z and Z² - and to a much lesser extent on the hyperbolic plane and on trees - has started to get interested in the case of finitely generated groups, as a way of unifying the previous examples. The writing of this project follows several new results, in which the members of the project have actively participated. Three of these members are specialized in symbolic dynamics - Nathalie Aubrun, Michael Rao and Jarkko Kari - and are internationally recognized for their expertise on computability issues, combinatorics on words and computer-aided proofs. The requested funding will help bolster their leading position at an international level.