Wang subshifts on finitely generated groups

Abstract

En este trabajo de tesis se estudia la dinámica simbólica en grupos finitamente generados. La motivación inicial de esta investigación fueron los resultados obtenidos por S. Piantadosi [42] en dinámica simbólica de grupos libres Fk, desarrollando la teoría de subshifts de tipo finito, y el trabajo realizado por E. Jeandel y M. Rao [27], donde los autores obtuvieron que la cantidad mínima de Z 2 -Wang tiles que generan un Z 2 -Wang subshift aperiódico no vacío es 11 (definición de Wang tile y Wang subshifts en 3.1). En una de las líneas de trabajo nos enfocamos en determinar la cantidad mínima de Fk-Wang tiles necesarias para conseguir un Fk-Wang subshift aperiódico no vacío. En otra de las líneas de trabajo el foco de la investigación es exponer la relación que existe entre condiciones necesarias para obtener un teselamiento válido en Z 2 , resultado dado por J. Chazottes y coautores en [13], y las condiciones determinadas por S. Piantadosi para Fk, obteniendo que ambas son equivalentes, y que resultan ser condiciones necesarias para obtener un teselamiento válido en grupos promediables finitamente generados. La teoría de Wang subshifts, desarrollada por H. Wang [46], tuvo relevancia para estudiar el problema del dominó: dado un conjunto de restricciones (por ejemplo, un conjunto de Wang tiles), ¿existe un algoritmo que decide si es posible obtener un teselamiento de Z 2 , respetando dichas restricciones? El problema resultó ser indecidible, obteniéndose un teselamiento aperiódico no vacío que usó 20.426 Z 2 -Wang tiles, dado por R. Berger [6]. A lo largo de los años, el número de Z 2 -Wang tiles fue disminuyendo, hasta llegar a la cantidad mínima el año 2015, que resultó ser 11. Motivados por este resultado y el desarrollo de la dinámica simbólica en grupos libres por S. Piantadosi, extendimos la teoría de Wang subshifts a grupos libres para determinar el número mínimo de Fk-Wang tiles que determinan un Fk-Wang subshift aperiódico no vacío, resultando en el teorema prinicipal de esta línea de trabajo, el que nos dice que dicha cantidad es 3. En la segunda línea de trabajo, consideramos un conjunto de condiciones necesarias que son heurísticas eficientes para decidir cuándo un conjunto de Wang tiles no puede teselar un grupo. Para esto consideramos dos condiciones: la primera dada por S. Piantadosi [42] que resulta ser una condición necesaria y suficiente para decidir si un conjunto de Fk-Wang tiles entrega un teselamiento fuertemente periódico en el grupo libre; la segunda, dada por R. Chazottes et. al [13], es una condición necesaria para decidir si un conjunto de Wang tiles consigue un teselamiento válido en Z 2 . Demostramos que ambas condiciones son equivalentes, uniendo y generalizando ambos mundos (Fk y Z 2 ), probando que estas resultan ser condiciones necesarias para tener un teselamiento válido en cualquier grupo promediable finitamente generado.

In this thesis work we study symbolic dynamics in finitely generated groups. The initial motivation of this research comes from the results obtained by S. Piantadosi in symbolic dynamics on free groups Fk, developing the theory of subshifts of finite type and the work developed by E. Jeandel and M. Rao. [27], where the authors obtained that the minimum number of Z 2 -Wang tiles generating an aperiodic nonempty Z 2 -Wang subshift is 11 (definition of Wang tiles and Wang subshifts in 3.1). In one of the work lines we focus on determining the minimum number of Fk-Wang tiles needed to achieve a nonempty aperiodic Fk-Wang subshift, in another direction the focus of the investigation is to expose the relationship between necessary conditions to obtain a valid tiling in Z 2 , result given by Chazottes et. al. [13], and the conditions determined by S. Piantadosi for Fk, obtaining that both are equivalent and moreover that they are necessary conditions to obtain a valid tiling in finitely generated amenable groups. Wang subshifts theory, developed by H. Wang [46], was relevant in the study of the domino problem: given a set of restrictions (e.g., a set of Wang tiles), is there an algorithm to decide whether it is possible to obtain a tiling of Z 2 , respecting those restrictions?. The problem turned out to be undecidable, obtaining a nonempty aperiodic tiling using 20, 426 Z 2 -Wang tiles, given by R. Berger. Over the years, the number of Z 2 -Wang tiles decreased, until the proof that the minimal amount of Wang tiles that can produce an aperiodic SFT is 11, which was done by E. Jeandel and M. Rao in 2015 [27]. Motivated by this result and the development of symbolic dynamics in free groups by S. Piantadosi, we developed the theory of Wang subshifts on free groups to determine the minimum number of Fk-Wang tiles that generate a nonempty aperiodic Fk-Wang subshift, resulting in the main theorem of this work line, where we obtain that such quantity is 3. In a second direction, we study a set of necessary conditions which are an efficient heuristic to decide when a set of Wang tiles cannot tessellate a group. For this, we consider two conditions: the first given by S. Piantadosi [42] is a necessary and sufficient condition to decide if a set of Wang tiles gives a strongly periodic tiling of the free group; the second, given by R. Chazottes et. al. [13] is a necessary condition to decide if a set of Wang tiles gives a tiling of Z 2 . We show that both conditions are equivalent, joining and generalizing two different settings (Fk and Z 2 ), and we prove that they are necessary for having a valid tiling of any finitely generated amenable group.