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

Necessary conditions for tiling finitely generated amenable groups

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].

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. ChazottesJ.-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. ChazottesJ.-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
[1]

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

[2]

Kiyoshi Igusa, Gordana Todorov. Picture groups and maximal green sequences. Electronic Research Archive, , () : -. doi: 10.3934/era.2021025

[3]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141

[4]

Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022

[5]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

[6]

Simone Calogero, Juan Calvo, Óscar Sánchez, Juan Soler. Dispersive behavior in galactic dynamics. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 1-16. doi: 10.3934/dcdsb.2010.14.1

[7]

Patrick Henning, Anders M. N. Niklasson. Shadow Lagrangian dynamics for superfluidity. Kinetic & Related Models, 2021, 14 (2) : 303-321. doi: 10.3934/krm.2021006

[8]

Mao Okada. Local rigidity of certain actions of solvable groups on the boundaries of rank-one symmetric spaces. Journal of Modern Dynamics, 2021, 17: 111-143. doi: 10.3934/jmd.2021004

[9]

Hsin-Lun Li. Mixed Hegselmann-Krause dynamics. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021084

[10]

Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53

[11]

Yu Jin, Xiao-Qiang Zhao. The spatial dynamics of a Zebra mussel model in river environments. Discrete & Continuous Dynamical Systems - B, 2021, 26 (4) : 1991-2010. doi: 10.3934/dcdsb.2020362

[12]

Hua Shi, Xiang Zhang, Yuyan Zhang. Complex planar Hamiltonian systems: Linearization and dynamics. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3295-3317. doi: 10.3934/dcds.2020406

[13]

Mirelson M. Freitas, Anderson J. A. Ramos, Manoel J. Dos Santos, Jamille L.L. Almeida. Dynamics of piezoelectric beams with magnetic effects and delay term. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021015

[14]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[15]

Chonghu Guan, Xun Li, Rui Zhou, Wenxin Zhou. Free boundary problem for an optimal investment problem with a borrowing constraint. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021049

[16]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021

[17]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[18]

Giulio Ciraolo, Antonio Greco. An overdetermined problem associated to the Finsler Laplacian. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1025-1038. doi: 10.3934/cpaa.2021004

[19]

Yang Zhang. A free boundary problem of the cancer invasion. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021092

[20]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (123)
  • HTML views (95)
  • Cited by (0)

[Back to Top]