Tilings of the hyperbolic plane of substitutive origin as subshifts of finite type on Baumslag–Solitar groups $\mathit{BS}(1,n)$

Aubrun, Nathalie; Schraudner, Michael

Comptes Rendus. Mathématique, Tome 362 (2024) no. G5, pp. 553-580

We present a technique to lift some tilings of the discrete hyperbolic plane –tilings defined by a 1D substitution– into a zero entropy subshift of finite type (SFT) on non-abelian amenable groups $\mathit{BS}(1,n)$ for $n\ge 2$. For well chosen hyperbolic tilings, this SFT is also aperiodic and minimal. As an application we construct a strongly aperiodic SFT on $\mathit{BS}(1,n)$ with a hierarchical structure, which is an analogue of Robinson’s construction on ${\mathbb{Z}}^2$ or Goodman–Strauss’s on ${ℍ}^2$.

Nous présentons une technique pour relever certains pavages du plan hyperbolique discret, ceux définis par une substitution 1D, au sein d’un sous-décalage de type fini (SFT) d’entropie nulle sur les groupes de Baumslag–Solitar moyennables et non abéliens $\mathit{BS}(1,n)$ avec $n\ge 2$. Lorsque ces pavages hyperboliques sont bien choisis, on montre que ce SFT est également apériodique et minimal. En guise d’application nous construisons un SFT fortement apériodique sur $\mathit{BS}(1,n)$ avec une structure hiérarchique, qui est l’analogue de la construction de Robinson sur ${\mathbb{Z}}^2$ ou de celle de Goodman–Strauss sur ${ℍ}^2$.

Classification : 37B10, 20F99

[1] Aubrun, N.; Bitar, N.; Huriot-Tattegrain, S. Strongly aperiodic SFTs on generalized Baumslag–Solitar groups, Ergodic Theory Dyn. Syst. (2023) | DOI

[2] Aubrun, N.; Barbieri, S.; Moutot, E. The Domino Problem is Undecidable on Surface Groups, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Volume 138 (2019), 46 | Zbl | DOI | MR

[3] Aubrun, N.; Barbieri, S.; Thomassé, S. Realization of aperiodic subshifts and uniform densities in groups, Groups Geom. Dyn., Volume 13 (2018) no. 1, pp. 107-129 | DOI | MR | Zbl

[4] Aubrun, N.; Kari, J. Tiling Problems on Baumslag-Solitar groups, Proceedings of the conference on machines, computations and universality 2013, MCU 2013 (Neary, Turlough et al., eds.) (Electronic Proceedings in Theoretical Computer Science), Volume 128, Open Publishing Association (2013), pp. 35-46 | Zbl | MR

[5] Aubrun, N.; Kari, J. On the domino problem of the Baumslag-Solitar groups, Theor. Comput. Sci., Volume 894 (2021), pp. 12-22 (Building Bridges – Honoring Nataša Jonoska on the Occasion of Her 60th Birthday) | DOI | Zbl | MR

[6] Barbieri, S. On the entropies of subshifts of finite type on countable amenable groups, Groups Geom. Dyn., Volume 15 (2021) no. 2, pp. 607-638 | DOI | Zbl | MR

[7] Barbieri, S.; Sablik, M. A generalization of the simulation theorem for semidirect products, Ergodic Theory Dyn. Syst., Volume 39 (2019) no. 12, pp. 3185-3206 | DOI | Zbl | MR

[8] Cohen, D. B.; Goodman-Strauss, C. Strongly aperiodic subshifts on surface groups, Groups Geom. Dyn., Volume 11 (2017) no. 3, pp. 1041-1059 | DOI | Zbl | MR

[9] Cohen, D. B.; Goodman-Strauss, C.; Rieck, Y. Strongly aperiodic subshifts of finite type on hyperbolic groups, Ergodic Theory Dyn. Syst., Volume 42 (2021) no. 9, pp. 2740-2783 | DOI | Zbl | MR

[10] Culik, K.; Kari, J. An aperiodic set of Wang cubes, J. UCS The Journal of Universal Computer Science: Annual Print and CD-ROM Archive Edition Volume 1 • 1995 (Maurer, H.; Calude, C.; Salomaa, A., eds.), Springer, 1996, pp. 675-686 | DOI | Zbl

[11] Esnay, S. J.; Moutot, E. Aperiodic SFTs on Baumslag-Solitar groups, Theor. Comput. Sci., Volume 917 (2022), pp. 31-50 | DOI | Zbl | MR

[12] Farb, B.; Mosher, L. A rigidity theorem for the solvable Baumslag-Solitar groups, Invent. Math., Volume 131 (1998), pp. 419-451 | DOI | Zbl | MR

[13] Gao, S.; Jackson, S.; Seward, B. A coloring property for countable groups, Math. Proc. Camb. Philos. Soc., Volume 147 (2009), pp. 579-592 | DOI | Zbl | MR

[14] Goodman-Strauss, C. A strongly aperiodic set of tiles in the hyperbolic plane, Invent. Math., Volume 159 (2004) no. 1, pp. 119-132 | DOI | Zbl | MR

[15] Goodman-Strauss, C. A hierarchical strongly aperiodic set of tiles in the hyperbolic plane, Theor. Comput. Sci., Volume 411 (2010) no. 7, pp. 1085-1093 | DOI | Zbl | MR

[16] Jeandel, E. Aperiodic Subshifts of Finite Type on Groups (2015) | arXiv

[17] Kari, J. A small aperiodic set of Wang tiles, Discrete Math., Volume 160 (1996) no. 1, pp. 259-264 | DOI | Zbl | MR

[18] Lyndon, R. C.; Schupp, P. E. Combinatorial Group Theory, Classics in Mathematics, Springer, 2001 | DOI | Zbl

[19] Muller, D. E.; Schupp, P. E. The theory of ends, pushdown automata, and second-order logic, Theor. Comput. Sci., Volume 37 (1985), pp. 51-75 | DOI | Zbl | MR

[20] Ornstein, D. S.; Weiss, B. Entropy and isomorphism theorems for actions of amenable groups, J. Anal. Math., Volume 48 (1987) no. 1, pp. 1-141 | DOI | Zbl | MR

[21] Robinson, R. Undecidability and nonperiodicity for tilings of the plane, Invent. Math., Volume 12 (1971), pp. 177-209 | Zbl | MR | DOI

[22] Whyte, K. The large scale geometry of the higher Baumslag-Solitar groups, Geom. Funct. Anal., Volume 11 (2001), pp. 1327-1343 | DOI | Zbl | MR

[23] Şahin, A. A.; Schraudner, M.; Ugarcovici, I. A strongly aperiodic shift of finite type on the discrete Heisenberg group using Robinson tilings, Ill. J. Math., Volume 65 (2021) no. 3, pp. 655-686 | DOI | Zbl | MR