Sous-décalages de type fini sur des groupes : problèmes du vide et d'apériodicité
Nicolás Bitar · HAL (Le Centre pour la Communication Scientifique Directe) · 2024
A subshift of finite type is a set of tilings of a group subject to a finite number of local constraints, where the group acts by translation. In recent years, much progress has been made in understanding their dynamical and computational properties. The goal of this thesis is to continue the study of how the algebraic and geometric properties of the underlying group influence the properties of subshifts of finite type defined on the group. The results are divided into three broad categories: decidability, aperiodicity, and substitutions. For the first part, we study the Domino Problem, its variants, and the consequences of its undecidability on many finitely generated groups. We classify the computability of the Seeded Domino Problem, the Recurring Domino Problem, the k-SAT Problem, and Domino Snake Problems for many well-known classes of groups. In particular, they are all decidable for virtually free groups. This classification is obtained through reductions involving SFT constructions, automata theory, and Monadic Second Order Logic. At the end of the first part, we go on a tangent to study the set of bi-infinite self-avoiding walks on Cayley graphs. This set appears naturally in the study of the Infinite Snake Problem and is a ℤ-subshift. We classify for which groups this subshift is aperiodic, of finite type, and sofic. We also study its entropy and its relation to the connective constant of the Cayley graph. The second part tackles the existence of strongly and weakly aperiodic subshifts of finite type. We begin with a survey on the state of the art of these problems and explore parallels with problems from probability and combinatorics. We then look at which subgroups of a group can be realized as the stabilizers of subshifts of finite type, establishing both algebraic and computational conditions for this to happen. Within this same framework, we introduce the class of periodically rigid groups, i.e. groups where every weakly aperiodic subshift of finite type is strongly aperiodic. We end this part by building upon the work of Aubrun and Kari to construct the first examples of strongly aperiodic subshifts of finite type on non-solvable Baumslag-Solitar groups and on Fₙ x ℤ. By theorems of Whyte and Cohen, we obtain the existence of such subshifts for non-cyclic generalized Baumslag-Solitar groups. The final part of the thesis introduces new notions of substitutions, S-adic systems, and their corresponding subshifts for countable groups. We identify three classes groups. First, we define S-decomposable groups. These groups have the appropriate hierarchical structure for defining general S-adic systems. Second, we study ccc groups introduced by Gao, Jackson, and Seward, as they allow the definition of constant-shape S-adic systems. Third, we introduce monoform groups. These groups allow for the definition of constant-shape substitutions. We provide examples for all three classes and examples for their corresponding S-adic systems. We finish studying the dynamical properties of the subshifts defined by these systems. We show that, in general, they are minimal under primitivity conditions, and that for some amenable ccc groups, they have zero entropy and are uniquely ergodic.