
-
Previous Article
Li-Yorke Chaos for ultragraph shift spaces
- DCDS Home
- This Issue
-
Next Article
Dynamical obstruction to the existence of continuous sub-actions for interval maps with regularly varying property
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 |
We consider a set of necessary conditions which are efficient heuristics for deciding when a set of Wang tiles cannot tile a group.
Piantadosi [
We consider two other conditions: the first, also given by Piantadosi [
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 [
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. 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. |
[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. 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.![]() ![]() |
[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. 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. |
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. |
[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. 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. |
[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. 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.![]() ![]() |
[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. 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. |

[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
Other articles
by authors
[Back to Top]