Simulations and the lamplighter group

DOI10.4171/GGD/692MaRDI QIDQ2694797zbMATH OpenFDO

Authors Yanyan Li

Publication date 4 April 2023

Published in Groups, Geometry, and Dynamics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.14299

zbMATH Keywords

decision problems in group theoryDiestel-Leader graphsdomino problemlamplighter grouptiling problemwreath products

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extensions, wreath products, and other compositions of groups (20E22) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Geometric group theory (20F65) Symbolic dynamics (37B10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Review text

Summary: We introduce a notion of ``simulation for labelled graphs, in which edges of the simulated graph are realized by regular expressions in the simulating graph, and we prove that the tiling problem (a.k.a. the ``domino problem) for the simulating graph is at least as difficult as that for the simulated graph. We apply this to the Cayley graph of the ``lamplighter group \(L = \mathbb{Z}/2 \wr \mathbb{Z}\), and more generally to ``Diestel-Leader graphs. We prove that these graphs simulate the plane, and thus deduce that the seeded tiling problem is unsolvable on the group \(L\). We note that \(L\) does not contain any plane in its Cayley graph, so our undecidability criterion by simulation covers cases not addressed by Jeandel's criterion based on translation-like action of a product of finitely generated infinite groups. Our approach to tiling problems is strongly based on categorical constructions in graph theory.

Recommendations

• Simulations between cellular automata on Cayley graphs
• On the domino problem of the Baumslag-Solitar groups
• Tiling problems on Baumslag-Solitar groups.
• Tilings and submonoids of metabelian groups.
• Groups and tilings

Cites work

• A conjecture concerning a limit of non-Cayley graphs
• About the domino problem for subshifts on groups
• Amenability, bi-Lipschitz equivalence, and the von Neumann conjecture
• Burnside's problem, spanning trees and tilings.
• Combinatorial group theory.
• Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• Horocyclic products of trees
• Lamplighters admit weakly aperiodic SFTs
• Lamplighters, Diestel–Leader Graphs, Random Walks, and Harmonic Functions
• Symbolic dynamics and relatively hyperbolic groups.
• The domino problem on groups of polynomial growth
• The large scale geometry of strongly aperiodic subshifts of finite type
• The undecidability of the domino problem
• Tiling problems on Baumslag-Solitar groups.
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(6)

• Monadic second-order logic and the domino problem on self-similar graphs
• Simulations and the Lamplighter group
• FO logic on cellular automata orbits equals MSO logic
• Invariant sets and nilpotency of endomorphisms of algebraic sofic shifts
• SFT covers for actions of the first Grigorchuk group
• A general framework for quasi-isometries in symbolic dynamics beyond groups

This page was built for publication: Simulations and the lamplighter group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2694797)