A geometric obstruction to self-simulation for groups

Basic Information

• Paper ID: 2510.10291
• Title: A geometric obstruction to self-simulation for groups
• Authors: Sebastián Barbieri, Kanéda Blot, Mathieu Sablik, Ville Salo
• Classification: math.GR (Group Theory), math.DS (Dynamical Systems)
• Publication Date: October 11, 2025
• Paper Link: https://arxiv.org/abs/2510.10291

Abstract

This paper introduces a new quasi-isometric invariant for finitely generated groups and proves that every group with this property admits a subshift that is pattern-effectively closed but cannot be realized as a topological factor of any finite-type subshift. The paper provides examples of multiple groups with this property, including amenable groups, groups with multiple ends, generalized Baumslag-Solitar groups, surface fundamental groups, and compact Fuchsian groups.

Research Background and Motivation

1. Core Problem: Investigating which finitely generated groups admit effective subshifts that are not sofic subshifts. This is a fundamental question at the intersection of symbolic dynamics and group theory.
2. Problem Significance:
   • Understanding how geometric properties of groups influence the realizability of dynamical systems on them
   • Exploring the expressive boundaries of finite-type subshifts (SFT)
   • Connecting quasi-isometric invariants in group theory with dynamical systems theory
3. Limitations of Existing Approaches:
   • It was previously known that amenable groups and groups with multiple ends are not self-simulating, but a unified geometric characterization was lacking
   • Mirror shift arguments primarily relied on amenability of groups, with limited applicability
   • Absence of general geometric criteria to identify non-self-simulating groups
4. Research Motivation: Seeking a quasi-isometrically invariant geometric property that can uniformly explain all known examples of non-self-simulating groups and discover new examples.

Core Contributions

1. Introduction of the "extraterrestrial" property: A new quasi-isometric invariant for finitely generated groups, based on the existence of UFO structures in the Cayley graph of the group
2. Establishment of a geometric obstruction theorem: Proving that extraterrestrial groups are not strongly self-simulating (Theorem B)
3. Proof of quasi-isometric invariance: Demonstrating that the extraterrestrial property is preserved under quasi-isometries (Theorem A)
4. Provision of rich examples: Including amenable groups, groups with multiple ends, generalized Baumslag-Solitar groups, surface fundamental groups, etc.
5. Construction of generalized mirror shifts: A pattern-effectively closed but non-sofic subshift construction

Methodology Details

Task Definition

Studying subshifts on finitely generated groups G, specifically:

• Input: Finitely generated group G and its generating set S
• Output: Determining whether G is extraterrestrial and constructing the corresponding non-sofic effective subshift
• Constraints: Preserving quasi-isometric invariance

Core Concepts: UFO and Extraterrestrial Groups

UFO Definition

For a graph G=(V,E) and non-negative integers m, k, r, an (m,k,r)-UFO is a triple of vertices (U,F,O) satisfying:

1. |U| ≥ m|F| (the size of U is at least m times the size of F)
2. There exists a complete matching of length at most k between U and O
3. Any path from U to O avoiding F has length at least r

Extraterrestrial Groups

A group G is extraterrestrial if for all m∈ℕ, there exists k∈ℕ such that for all r∈ℕ, Cay(G,S) admits an (m,k,r)-UFO.

Technical Innovations

1. Geometric Unification: The UFO concept unifies the geometric essence of amenability and multiple-endedness
2. Quasi-isometric Invariance: Proven through refined metric analysis that this property is geometrically invariant
3. Constructive Proof: Explicit construction of generalized mirror shifts proves the obstruction property

Generalized Mirror Shift Construction

Using alphabet Λ = Σ × {0,1}, where Σ = {⋆,u,o} × {-,+}:

1. Coherence Rules: Utilizing configurations ξ∈{0,1}^G from Lemma 4.1 to encode the word problem of the group
2. Matching Rules: Constructing matchings M(p) based on lexicographic order, requiring matched elements to be identical in the ± component
3. Effectiveness: The entire construction process is algorithmically realizable

Experimental Setup

Theoretical Verification Framework

This paper is primarily theoretical work, verified through:

1. Quasi-isometric Invariance Proof: Through concrete constant estimates and path analysis
2. Concrete Example Verification: Constructing explicit UFOs for each class of groups
3. Non-soficity Proof: Through proof by contradiction and combinatorial arguments

Evaluation Metrics

• Constructibility of UFO parameters
• Parameter transformation under quasi-isometric mappings
• Effectiveness and non-soficity of subshifts

Experimental Results

Main Results

Theorem A: The extraterrestrial property is a quasi-isometric invariant for bounded-degree graphs.

Theorem B: If G is a finitely generated extraterrestrial group, then there exists a G-subshift that is pattern-effectively closed but is not a topological factor of any G-SFT.

Theorem C: The following classes of finitely generated groups are all extraterrestrial:

• Infinite amenable groups
• Groups with multiple ends
• Amalgamated free products over amenable subgroups
• HNN extensions over amenable subgroups
• Generalized Baumslag-Solitar groups
• Compact Fuchsian groups
• Surface fundamental groups

Concrete Construction Examples

1. UFO for Z^d: For standard generating sets, explicit (m,3d^{-1}m+1,2r+4)-UFOs are constructed
2. Pentagon Model: Proving that groups quasi-isometric to the hyperbolic plane are extraterrestrial
3. Explicit Amenable Cuts for Surface Groups: Providing explicit amenable cuts for genus-2 surface groups

Key Technical Results

Lemma 4.1: There exists a universal constant A≥1 such that for every infinite finitely generated group G and generating set S, there exists a configuration ξ∈{0,1}^G that can locally distinguish elements at distance k.

Related Work

Main Research Directions

1. Self-simulating Group Theory: Concept introduced by Barbieri et al., studying which groups have the property that all effective subshifts are sofic
2. Symbolic Dynamics: Hochman's pioneering work on multidimensional shifts
3. Geometric Properties of Groups: Classical invariants such as amenability and number of ends

Position of This Work

• Unifies previous results on non-self-simulation of amenable groups and groups with multiple ends
• Answers the open question of whether 1-ended hyperbolic groups are self-simulating (negatively)
• Provides new geometric perspective for understanding dynamical systems on groups

Conclusions and Discussion

Main Conclusions

1. The extraterrestrial property provides a geometric characterization of non-self-simulation for groups
2. This property is quasi-isometrically invariant, hence an intrinsic geometric property of groups
3. A large number of important group classes, including surface groups, possess this property

Limitations

1. It remains unclear whether all non-self-simulating groups are extraterrestrial
2. Unknown whether there exist extraterrestrial groups that do not admit amenable multi-ended Schreier graphs
3. While the constructed subshifts are non-sofic, their complexity analysis is not sufficiently deep

Future Directions

The paper poses two important open problems:

1. Do there exist groups that are neither strongly self-simulating nor extraterrestrial?
2. Do there exist extraterrestrial groups that do not admit multi-ended Schreier graphs over amenable subgroups?

In-Depth Evaluation

Strengths

1. Conceptual Innovation: The UFO concept cleverly captures the geometric structure of groups with intuitive geometric meaning
2. Theoretical Depth: Proof techniques are refined, particularly the proof of quasi-isometric invariance involving complex metric estimates
3. Rich Examples: Covering multiple important categories in group theory, demonstrating broad applicability of the theory
4. Unification: Provides unified geometric explanation for previously scattered results

Weaknesses

1. Open Problems: Two core questions remain unresolved, and the completeness of the theory awaits further development
2. Computational Complexity: The algorithmic complexity of determining whether a group is extraterrestrial is not discussed
3. Limited Applications: Primarily theoretical results with limited practical application value

Impact

1. Theoretical Contribution: Provides new tools for cross-disciplinary research between group theory and dynamical systems
2. Methodological Value: The UFO method may be applicable to other geometric-algebraic problems
3. Subsequent Research: Expected to inspire further research on relationships between geometric properties of groups and dynamical systems

Applicable Scenarios

• Study of geometric properties in group theory
• Classification problems of subshifts in symbolic dynamics
• Decidability problems in computational group theory
• Theory of topological dynamical systems

References

The paper cites 31 important references, covering:

• Foundational theory of symbolic dynamics (Ceccherini-Silberstein & Coornaert)
• Self-simulating group theory (prior work by Barbieri, Sablik, Salo)
• Geometric theory of groups (Bridson & Haefliger)
• Computational theory foundations (Cooper)
• Theory of group actions on trees (Serre)

This paper makes important contributions at the intersection of group theory and dynamical systems. The proposed extraterrestrial concept provides a new perspective for understanding the relationship between geometric properties of groups and dynamical systems on them. Although open problems remain, its theoretical framework and rich examples provide a solid foundation for future research.