×

Necessary conditions for tiling finitely generated amenable groups. (English) Zbl 1440.37027

Let \(G =\langle S|R\rangle\) be a finitely generated group and \(\mathcal{C}\) a finite set of colours. A Wang tile on \(\mathcal{C}\) and \(S\) is a map \(S\cup S^{-1} \rightarrow C\). Let \(T\) be a set of Wang tiles and \(X_T\) be the corresponding \(G\)-Wang subshift. S. T. Piantadosi [Discrete Contin. Dyn. Syst. 20, No. 3, 725–738 (2008; Zbl 1140.37006)] obtained a subalphabet such that every letter admits a valid neighbor in the subalphabet for every generator and provided the Condition \((\star\star)\) (explained in the paper). Then, J.-R. Chazottes et al. [Geom. Dedicata 173, 129–142 (2014; Zbl 1316.52028)] defined the asymptotic Thurston semi-norm and provided a necessary condition to decide if a set of Wang tiles gives a tiling of \(\mathbb{Z}^{2}\) (Condition \((\star\star)'\) in the paper).
In this paper the authors study Piantadosi’s and Chazottes-Gambaudo-Gautero’s conditions, \((\star\star)\) and \((\star\star)'\), respectively. The authors prove that two conditions are equivalent. The following theorem is proved:
Theorem. Let \(T\) be a set of Wang tiles over the set of colours \(\mathcal{C}\) and the set of generators \(\mathcal{S}\). \(T\) satisfies condition \((\star\star)'\) if, and only if, the associated graphs satisfy condition \((\star\star)\).
Then the authors show that conditions \((\star\star)\) and condition \((\star\star)'\) form a necessary condition for a subshift of finite type to admit a valid tiling on any finitely generated amenable group. Lastly, the authors give for any non-free finitely generated group a counterexample that satisfies all conditions but does not provide a valid tiling.

MSC:

37B52 Tiling dynamics
37B10 Symbolic dynamics
05B45 Combinatorial aspects of tessellation and tiling problems
52C22 Tilings in \(n\) dimensions (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI arXiv

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. · Zbl 07561690
[2] N. Aubrun; J. Kari, Tiling problems on Baumslag-Solitar groups, Computations and Universality 2013, Electron. Proc. Theor. Comput. Sci. (EPTCS), EPTCS, 128, 35-46 (2013) · Zbl 1469.20028 · doi:10.4204/EPTCS.128.12
[3] A. Ballier; M. Stein, The domino problem on groups of polynomial growth, Groups, Geometry, and Dynamics, 12, 93-105 (2018) · Zbl 1386.37017 · 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. · Zbl 1432.37037
[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; M. Sablik, A generalization of the simulation theorem for semidirect products, Ergodic Theory and Dynamical Systems, 39, 3185-3206 (2019) · Zbl 1433.37013 · doi:10.1017/etds.2018.21
[7] R. Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society, (1966), 72 pp. · Zbl 0199.30802
[8] D. Carroll; A. Penland, Periodic points on shifts of finite type and commensurability invariants of groups, New York Journal of Mathematics, 21, 811-822 (2015) · Zbl 1360.37037
[9] J.-R. Chazottes; J.-M. Gambaudo; F. Gautero, Tilings of the plane and Thurston semi-norm, Geometriae Dedicata, 173, 129-142 (2014) · Zbl 1316.52028 · doi:10.1007/s10711-013-9932-4
[10] D. B. Cohen; C. Goodman-Strauss, Strongly aperiodic subshifts on surface groups, Groups, Geometry, and Dynamics, 11, 1041-1059 (2017) · Zbl 1377.37028 · 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. · Zbl 1506.37023
[12] H. Maturana Cornejo and M. Schraudner, Weakly aperiodic \(\begin{document} \mathbb{F}_d \end{document} \)-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. · Zbl 1478.05020
[16] E. Jeandel and P. Vanier, The Undecidability of the Domino Problem, Unpublished Book Chapter. · Zbl 1336.37015
[17] S. Mozes, Aperiodic tilings, Inventiones Mathematicae, 128, 603-611 (1997) · Zbl 0879.52011 · doi:10.1007/s002220050153
[18] S. Mozes, Aperiodic tilings, Inventiones Mathematicae, 128, 603-611 (1997) · Zbl 1140.37006 · doi:10.1007/s002220050153
[19] S. T. Piantadosi, Symbolic dynamics on free groups, Discrete and Continuous Dynamical Systems, 20, 725-738 (2008) · Zbl 1140.37006 · 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. · doi:10.1007/978-94-009-2356-0_9
[21] H. Wang, Proving theorems by pattern recognition. Ⅱ, Bell System Technical Journal, 40, 1-41 (1961) · doi:10.1007/978-94-009-2356-0_9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.