American Institute of Mathematical Sciences

Advanced
April  2020, 40(4): 2335-2346. doi: 10.3934/dcds.2020116

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

Received  July 2019 Published  January 2020

Fund Project: 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.

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: Symbolic dynamics, tilings, groups, periodicity, amenability, domino problem.
Mathematics Subject Classification: Primary: 37B50; Secondary: 37B10, 05B45.
Citation: Benjamin Hellouin de Menibus, Hugo Maturana Cornejo. Necessary conditions for tiling finitely generated amenable groups. Discrete & Continuous Dynamical Systems, 2020, 40 (4) : 2335-2346. doi: 10.3934/dcds.2020116
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

S. Barbieri, A geometric simulation theorem on direct products of finitely generated groups, Discrete Analysis, (2019), Paper No. 9, 25 pp.  Google Scholar

[5]

S. Barbieri, Shift Spaces on Groups: Computability and Dynamics, Ph.D thesis, Université de Lyon, 2017, https://tel.archives-ouvertes.fr/tel-01563302. Google Scholar

[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.  Google Scholar

[7]

R. Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society, (1966), 72 pp.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

D. B. Cohen, C. Goodman-Strauss and Y. Rieck, Strongly aperiodic subshifts of finite type on hyperbolic groups, arXiv: 1706.01387. Google Scholar

[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). Google Scholar

[13]

E. Jeandel, Aperiodic subshifts on polycyclic groups, arXiv: 1510.02360. Google Scholar

[14]

E. Jeandel, Translation-like actions and aperiodic subshifts on groups, arXiv: 1508.06419. Google Scholar

[15]

E. Jeandel and M. Rao, An aperiodic set of 11 Wang tiles, arXiv: 1506.06492. Google Scholar

[16]

E. Jeandel and P. Vanier, The Undecidability of the Domino Problem, Unpublished Book Chapter. Google Scholar

[17] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.  doi: 10.1017/CBO9780511626302.  Google Scholar
[18]

S. Mozes, Aperiodic tilings, Inventiones Mathematicae, 128 (1997), 603-611.  doi: 10.1007/s002220050153.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[4]

S. Barbieri, A geometric simulation theorem on direct products of finitely generated groups, Discrete Analysis, (2019), Paper No. 9, 25 pp.  Google Scholar

[5]

S. Barbieri, Shift Spaces on Groups: Computability and Dynamics, Ph.D thesis, Université de Lyon, 2017, https://tel.archives-ouvertes.fr/tel-01563302. Google Scholar

[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.  Google Scholar

[7]

R. Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society, (1966), 72 pp.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

D. B. Cohen, C. Goodman-Strauss and Y. Rieck, Strongly aperiodic subshifts of finite type on hyperbolic groups, arXiv: 1706.01387. Google Scholar

[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). Google Scholar

[13]

E. Jeandel, Aperiodic subshifts on polycyclic groups, arXiv: 1510.02360. Google Scholar

[14]

E. Jeandel, Translation-like actions and aperiodic subshifts on groups, arXiv: 1508.06419. Google Scholar

[15]

E. Jeandel and M. Rao, An aperiodic set of 11 Wang tiles, arXiv: 1506.06492. Google Scholar

[16]

E. Jeandel and P. Vanier, The Undecidability of the Domino Problem, Unpublished Book Chapter. Google Scholar

[17] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.  doi: 10.1017/CBO9780511626302.  Google Scholar
[18]

S. Mozes, Aperiodic tilings, Inventiones Mathematicae, 128 (1997), 603-611.  doi: 10.1007/s002220050153.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

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
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Steven T. Piantadosi. Symbolic dynamics on free groups. Discrete & Continuous Dynamical Systems, 2008, 20 (3) : 725-738. doi: 10.3934/dcds.2008.20.725
[2]

Nicola Soave, Susanna Terracini. Symbolic dynamics for the $N$-centre problem at negative energies. Discrete & Continuous Dynamical Systems, 2012, 32 (9) : 3245-3301. doi: 10.3934/dcds.2012.32.3245
[3]

Nicola Soave, Susanna Terracini. Addendum to: Symbolic dynamics for the $N$-centre problem at negative energies. Discrete & Continuous Dynamical Systems, 2013, 33 (8) : 3825-3829. doi: 10.3934/dcds.2013.33.3825
[4]

Samuel R. Kaplan, Ernesto A. Lacomba, Jaume Llibre. Symbolic dynamics of the elliptic rectilinear restricted 3--body problem. Discrete & Continuous Dynamical Systems - S, 2008, 1 (4) : 541-555. doi: 10.3934/dcdss.2008.1.541
[5]

Jim Wiseman. Symbolic dynamics from signed matrices. Discrete & Continuous Dynamical Systems, 2004, 11 (2&3) : 621-638. doi: 10.3934/dcds.2004.11.621
[6]

George Osipenko, Stephen Campbell. Applied symbolic dynamics: attractors and filtrations. Discrete & Continuous Dynamical Systems, 1999, 5 (1) : 43-60. doi: 10.3934/dcds.1999.5.43
[7]

Michael Hochman. A note on universality in multidimensional symbolic dynamics. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 301-314. doi: 10.3934/dcdss.2009.2.301
[8]

Jose S. Cánovas, Tönu Puu, Manuel Ruiz Marín. Detecting chaos in a duopoly model via symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2010, 13 (2) : 269-278. doi: 10.3934/dcdsb.2010.13.269
[9]

Dieter Mayer, Fredrik Strömberg. Symbolic dynamics for the geodesic flow on Hecke surfaces. Journal of Modern Dynamics, 2008, 2 (4) : 581-627. doi: 10.3934/jmd.2008.2.581
[10]

Frédéric Naud. Birkhoff cones, symbolic dynamics and spectrum of transfer operators. Discrete & Continuous Dynamical Systems, 2004, 11 (2&3) : 581-598. doi: 10.3934/dcds.2004.11.581
[11]

Fryderyk Falniowski, Marcin Kulczycki, Dominik Kwietniak, Jian Li. Two results on entropy, chaos and independence in symbolic dynamics. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3487-3505. doi: 10.3934/dcdsb.2015.20.3487
[12]

David Ralston. Heaviness in symbolic dynamics: Substitution and Sturmian systems. Discrete & Continuous Dynamical Systems - S, 2009, 2 (2) : 287-300. doi: 10.3934/dcdss.2009.2.287
[13]

Mike Boyle. The work of Mike Hochman on multidimensional symbolic dynamics and Borel dynamics. Journal of Modern Dynamics, 2019, 15: 427-435. doi: 10.3934/jmd.2019026
[14]

Anke D. Pohl. Symbolic dynamics for the geodesic flow on two-dimensional hyperbolic good orbifolds. Discrete & Continuous Dynamical Systems, 2014, 34 (5) : 2173-2241. doi: 10.3934/dcds.2014.34.2173
[15]

Lorenzo Sella, Pieter Collins. Computation of symbolic dynamics for two-dimensional piecewise-affine maps. Discrete & Continuous Dynamical Systems - B, 2011, 15 (3) : 739-767. doi: 10.3934/dcdsb.2011.15.739
[16]

Snir Ben Ovadia. Symbolic dynamics for non-uniformly hyperbolic diffeomorphisms of compact smooth manifolds. Journal of Modern Dynamics, 2018, 13: 43-113. doi: 10.3934/jmd.2018013
[17]

Marian Gidea, Yitzchak Shmalo. Combinatorial approach to detection of fixed points, periodic orbits, and symbolic dynamics. Discrete & Continuous Dynamical Systems, 2018, 38 (12) : 6123-6148. doi: 10.3934/dcds.2018264
[18]

A. Yu. Ol'shanskii and M. V. Sapir. The conjugacy problem for groups, and Higman embeddings. Electronic Research Announcements, 2003, 9: 40-50.

[19]

H. M. Hastings, S. Silberger, M. T. Weiss, Y. Wu. A twisted tensor product on symbolic dynamical systems and the Ashley's problem. Discrete & Continuous Dynamical Systems, 2003, 9 (3) : 549-558. doi: 10.3934/dcds.2003.9.549
[20]

Scott Schmieding, Rodrigo Treviño. Random substitution tilings and deviation phenomena. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3869-3902. doi: 10.3934/dcds.2021020

2020 Impact Factor: 1.392

Tools

Metrics

  • PDF downloads (161)
  • HTML views (96)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences