Necessary conditions for tiling finitely generated amenable groups

Benjamin Hellouin de Menibus; Hugo Maturana Cornejo

doi:10.3934/dcds.2020116

Article Contents

2020, Volume 40, Issue 4: 2335-2346. Doi: 10.3934/dcds.2020116

This issue Previous Article Dynamical obstruction to the existence of continuous sub-actions for interval maps with regularly varying property Next Article Li-Yorke Chaos for ultragraph shift spaces

Necessary conditions for tiling finitely generated amenable groups

Benjamin Hellouin de Menibus^1, , , and
Hugo Maturana Cornejo^2,

1.
Laboratoire de Recherche en Informatique, Université Paris-Sud - CNRS - CentraleSupélec, Université Paris-Saclay, France
2.
Departamento de Ingeniería Matemática, DIM-CMM, Universidad de Chile, Chile

^* Corresponding author: Benjamin Hellouin de Menibus
^* Corresponding author: Benjamin Hellouin de Menibus

Received: July 2019

Published online: April 2020

This article was written during stays of the first author funded by an LRI internal project. The second author was partially funded by the ECOS-SUD project C17E08, the ANR project CoCoGro (ANR-16-CE40-0005) and CONICYT doctoral fellowship 21170770.

Abstract / Introduction Full Text(HTML) Figure(1) Related Papers Cited by

Abstract

We consider a set of necessary conditions which are efficient heuristics for deciding when a set of Wang tiles cannot tile a group.

Piantadosi [19] gave a necessary and sufficient condition for the existence of a valid tiling of any free group. This condition is actually necessary for the existence of a valid tiling for an arbitrary finitely generated group.

We consider two other conditions: the first, also given by Piantadosi [19], 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 Chazottes et. al. [9], is a necessary condition to decide if a set of Wang tiles gives a tiling of $ \mathbb Z^2 $.

We show that these last two conditions are equivalent. Joining and generalising approaches from both sides, we prove that they are necessary for having a valid tiling of any finitely generated amenable group, confirming a remark of Jeandel [14].

Keywords:

Mathematics Subject Classification: Primary: 37B50; Secondary: 37B10, 05B45.

Citation:

Full Text(HTML)

Figure 1. Examples of Wang tiles with colours $ \mathcal{C} = \left\{ {a,b,c,d} \right\}$ on one and two generators, respectively, with their corresponding maps

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	N. Aubrun, S. Barbieri and É. Moutot, The domino problem is undecidable on surface groups, 44th International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 138 (2019), Art. 46, 14 pp.
[2]	N. Aubrun and J. Kari, Tiling problems on Baumslag-Solitar groups, Computations and Universality 2013, Electron. Proc. Theor. Comput. Sci. (EPTCS), EPTCS, 128 (2013), 35-46. doi: 10.4204/EPTCS.128.12.
[3]	A. Ballier and M. Stein, The domino problem on groups of polynomial growth, Groups, Geometry, and Dynamics, 12 (2018), 93-105. doi: 10.4171/GGD/439.
[4]	S. Barbieri, A geometric simulation theorem on direct products of finitely generated groups, Discrete Analysis, (2019), Paper No. 9, 25 pp.
[5]	S. Barbieri, Shift Spaces on Groups: Computability and Dynamics, Ph.D thesis, Université de Lyon, 2017, https://tel.archives-ouvertes.fr/tel-01563302.
[6]	S. Barbieri and M. Sablik, A generalization of the simulation theorem for semidirect products, Ergodic Theory and Dynamical Systems, 39 (2019), 3185-3206. doi: 10.1017/etds.2018.21.
[7]	R. Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society, (1966), 72 pp.
[8]	D. Carroll and A. Penland, Periodic points on shifts of finite type and commensurability invariants of groups, New York Journal of Mathematics, 21 (2015), 811-822.
[9]	J.-R. Chazottes, J.-M. Gambaudo and F. Gautero, Tilings of the plane and Thurston semi-norm, Geometriae Dedicata, 173 (2014), 129-142. doi: 10.1007/s10711-013-9932-4.
[10]	D. B. Cohen and C. Goodman-Strauss, Strongly aperiodic subshifts on surface groups, Groups, Geometry, and Dynamics, 11 (2017), 1041-1059. doi: 10.4171/GGD/421.
[11]	D. B. Cohen, C. Goodman-Strauss and Y. Rieck, Strongly aperiodic subshifts of finite type on hyperbolic groups, arXiv: 1706.01387.
[12]	H. Maturana Cornejo and M. Schraudner, Weakly aperiodic $\mathbb{F}_{d}$-Wang subshift with minimal alphabet size and its complexity function, Unpublished preprint, (2018).
[13]	E. Jeandel, Aperiodic subshifts on polycyclic groups, arXiv: 1510.02360.
[14]	E. Jeandel, Translation-like actions and aperiodic subshifts on groups, arXiv: 1508.06419.
[15]	E. Jeandel and M. Rao, An aperiodic set of 11 Wang tiles, arXiv: 1506.06492.
[16]	E. Jeandel and P. Vanier, The Undecidability of the Domino Problem, Unpublished Book Chapter.
[17]	D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995. doi: 10.1017/CBO9780511626302.
[18]	S. Mozes, Aperiodic tilings, Inventiones Mathematicae, 128 (1997), 603-611. doi: 10.1007/s002220050153.
[19]	S. T. Piantadosi, Symbolic dynamics on free groups, Discrete and Continuous Dynamical Systems, 20 (2008), 725-738. doi: 10.3934/dcds.2008.20.725.
[20]	A. Sahin, M. Schraudner and I. Ugarcovic, A strongly aperiodic shift of finite type for the discrete Heisenberg group, preprint, (2014), announced at: http://www.dim.uchile.cl/ mschraudner/SyDyGr/Talks/sahin_cmmdec2014.pdf.
[21]	H. Wang, Proving theorems by pattern recognition. Ⅱ, Bell System Technical Journal, 40 (1961), 1-41. doi: 10.1007/978-94-009-2356-0_9.