Document Open Access Logo

Realizing Finitely Presented Groups as Projective Fundamental Groups of SFTs

Authors Léo Paviet Salomon, Pascal Vanier

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.75.pdf
  • Filesize: 0.87 MB
  • 15 pages

Document Identifiers

Author Details

Léo Paviet Salomon
  • Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France
Pascal Vanier
  • Normandie Univ, UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France

Funding

This research was partially funded by ANR JCJC 2019 19-CE48-0007-01.

Acknowledgements

The authors would like to thank all the anonymous referees of this paper for their remarks which helped improve the exposition.

Cite As Get BibTex

Léo Paviet Salomon and Pascal Vanier. Realizing Finitely Presented Groups as Projective Fundamental Groups of SFTs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.75

Abstract

Subshifts are sets of colourings - or tilings - of the plane, defined by local constraints. Historically introduced as discretizations of continuous dynamical systems, they are also heavily related to computability theory. In this article, we study a conjugacy invariant for subshifts, known as the projective fundamental group. It is defined via paths inside and between configurations. We show that any finitely presented group can be realized as a projective fundamental group of some SFT.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Mathematics of computing → Discrete mathematics
Keywords
  • Subshifts
  • Wang tiles
  • Dynamical Systems
  • Computability
  • Subshift of Finite Type
  • Fundamental Group

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nathalie Aubrun, Sebastián Barbieri, and Emmanuel Jeandel. About the domino problem for subshifts on groups. In Trends in Mathematics, pages 331-389. Springer International Publishing, 2018. URL: https://doi.org/10.1007/978-3-319-69152-7_9.
  2. Nathalie Aubrun, Sebastián Barbieri, and Mathieu Sablik. A notion of effectiveness for subshifts on finitely generated groups. Theoretical Computer Science, 661:35-55, January 2017. URL: https://doi.org/10.1016/j.tcs.2016.11.033.
  3. Nathalie Aubrun and Jarkko Kari. Tiling Problems on Baumslag-Solitar groups. In Machines, Computations and Universality (MCU), number 128 in Electronic Proceedings in Theoretical Computer Science, pages 35-46, 2013. URL: https://doi.org/10.4204/EPTCS.128.12.
  4. Nathalie Aubrun and Mathieu Sablik. An order on sets of tilings corresponding to an order on languages. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, pages 99-110, 2009. Google Scholar
  5. Alexis Ballier, Bruno Durand, and Emmanuel Jeandel. Tilings robust to errors. In LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, pages 480-491, 2010. URL: https://doi.org/10.1007/978-3-642-12200-2_42.
  6. Robert Berger. The Undecidability of the Domino Problem. Number 66 in Memoirs of the American Mathematical Society. The American Mathematical Society, 1966. Google Scholar
  7. William W. Boone. Certain Simple, Unsolvable Problems of Group Theory V. Indagationes Mathematicae, 60:22-27, 1957. URL: https://doi.org/10.1016/S1385-7258(57)50003-6.
  8. William W. Boone. Word problems and recursively enumerable degrees of unsolvability. a sequel on finitely presented groups. The Annals of Mathematics, 84(1):49, July 1966. URL: https://doi.org/10.2307/1970530.
  9. Mike Boyle, Ronnie Pavlov, and Michael Schraudner. Multidimensional sofic shifts without separation and their factors. Transactions of the AMS, 362(9):4617-4653, September 2010. URL: https://doi.org/10.1090/S0002-9947-10-05003-8.
  10. Nishant Chandgotia and Brian Marcus. Mixing properties for hom-shifts and the distance between walks on associated graphs. Pacific Journal of Mathematics, 294(1):41-69, January 2018. URL: https://doi.org/10.2140/pjm.2018.294.41.
  11. John H. Conway and Jeffrey C. Lagarias. Tiling with polyominoes and combinatorial group theory. J. Comb. Theory, Ser. A, 53(2):183-208, 1990. URL: https://doi.org/10.1016/0097-3165(90)90057-4.
  12. Van Cyr and Bryna Kra. The automorphism group of a shift of linear growth: beyond transitivity. Forum of Mathematics, Sigma, 3, February 2015. URL: https://doi.org/10.1017/fms.2015.3.
  13. Sebastián Donoso, Fabien Durand, Alejandro Maass, and Samuel Petite. On automorphism groups of low complexity subshifts. Ergodic Theory and Dynamical Systems, 36(1):64-95, November 2015. URL: https://doi.org/10.1017/etds.2015.70.
  14. Bruno Durand, Andrei Romashchenko, and Alexander Shen. Effective Closed Subshifts in 1D Can Be Implemented in 2D. In Fields of Logic and Computation, number 6300 in Lecture Notes in Computer Science, pages 208-226. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15025-8_12.
  15. Francesca Fiorenzi. Periodic configurations of subshifts on groups. International Journal of Algebra and Computation, 19(03):315-335, May 2009. URL: https://doi.org/10.1142/s0218196709005123.
  16. Silvere Gangloff, Benjamin Hellouin de Menibus, and Piotr Oprocha. Short-range and long-range order: a transition in block-gluing behavior in hom shifts, 2022. URL: https://doi.org/10.48550/arXiv.2211.04075.
  17. William Geller and James Propp. The projective fundamental group of a ℤ²-shift. Ergodic Theory and Dynamical Systems, 15(6):1091-1118, 1995. Google Scholar
  18. Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, and Pascal Vanier. Undecidable word problem in subshift automorphism groups. In Computer Science endash Theory and Applications, pages 180-190. Springer International Publishing, 2019. URL: https://doi.org/10.1007/978-3-030-19955-5_16.
  19. Yuri Gurevich and I Koryakov. Remarks on Berger’s paper on the domino problem. Siberian Math. Journal, pages 319-320, 1972. Google Scholar
  20. David Harel. Recurring Dominoes: Making the Highly Undecidable Highly Understandable. Annals of Discrete Mathematics, 24:51-72, 1985. Google Scholar
  21. Allen Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. Google Scholar
  22. G. A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Mathematical Systems Theory, 3(4):320-375, December 1969. URL: https://doi.org/10.1007/bf01691062.
  23. Michael Hochman. On the dynamics and recursive properties of multidimensional symbolic systems. Inventiones Mathematicae, 176(1):2009, April 2009. Google Scholar
  24. Michael Hochman. On the automorphism groups of multidimensional shifts of finite type. Ergodic Theory and Dynamical Systems, 30(3):809-840, 2010. URL: https://doi.org/10.1017/S0143385709000248.
  25. Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. Annals of Mathematics, 171(3):2011-2038, May 2010. URL: https://doi.org/10.4007/annals.2010.171.2011.
  26. Emmanuel Jeandel. Translation-like Actions and Aperiodic Subshifts on Groups. working paper or preprint, August 2015. URL: https://hal.inria.fr/hal-01187069.
  27. Emmanuel Jeandel and Pascal Vanier. A characterization of subshifts with computable language. In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 of LIPIcs, pages 40:1-40:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.40.
  28. Wilhelm Magnus, Abraham Karrass, and Donald Solitar. Combinatorial group theory: Presentations of groups in terms of generators and relations. Courier Corporation, 2004. Google Scholar
  29. Kengo Matsumoto. Dimension groups for subshifts and simplicity of the associated c^*-algebras. Journal of the Mathematical Society of Japan, 51(3), July 1999. URL: https://doi.org/10.2969/jmsj/05130679.
  30. Tom Meyerovitch. Growth-type invariants for ℤ^d subshifts of finite type and arithmetical classes of real numbers. Inventiones Mathematicae, 184(3), 2010. URL: https://doi.org/10.1007/s00222-010-0296-1.
  31. P.S. Novikov. On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov, 44:3-143, 1955. Google Scholar
  32. Ronnie Pavlov and Michael Schraudner. Entropies realizable by block gluing ℤ^d shifts of finite type. Journal dquotesingleAnalyse Mathématique, 126(1):113-174, April 2015. URL: https://doi.org/10.1007/s11854-015-0014-4.
  33. Marcus Pivato. Algebraic invariants for crystallographic defects in cellular automata. Ergodic Theory and Dynamical Systems, 27(1):199-240, 2007. Google Scholar
  34. Klaus Schmidt. The cohomology of higher-dimensional shifts of finite type. Pacific Journal of Mathematics, 170(1):237-269, 1995. Google Scholar
  35. Klaus Schmidt. Tilings, fundamental cocycles and fundamental groups of symbolic ℤ^d-actions. Ergodic Theory and Dynamical Systems, 18(6):1473-1526, 1998. Google Scholar
  36. William P Thurston. Conway’s tiling groups. The American Mathematical Monthly, 97(8):757-773, 1990. Google Scholar
  37. Marcin Wrochna. Homomorphism reconfiguration via homotopy. SIAM Journal on Discrete Mathematics, 34(1):328-350, January 2020. URL: https://doi.org/10.1137/17m1122578.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact