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 - A, 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]

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
[2]

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
[3]

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
[4]

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
[5]

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
[6]

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

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

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
[9]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[10]

Guirong Jiang, Qishao Lu. The dynamics of a Prey-Predator model with impulsive state feedback control. Discrete & Continuous Dynamical Systems - B, 2006, 6 (6) : 1301-1320. doi: 10.3934/dcdsb.2006.6.1301
[11]

Mingxin Wang, Qianying Zhang. Dynamics for the diffusive Leslie-Gower model with double free boundaries. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2591-2607. doi: 10.3934/dcds.2018109
[12]

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

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[14]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[15]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[16]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[17]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1757-1778. doi: 10.3934/dcdss.2020453
[18]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis of a thermal frictional contact problem with long memory. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021031
[19]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269
[20]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027

2019 Impact Factor: 1.338

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences