Preprints

  1. Realizability of Subgroups by Subshifts of Finite Type
    arXiv Preprint [arXiv]
    2. We study the problem of realizing families of subgroups as the set of stabilizers of configurations from a subshift of finite type (SFT). This problem generalizes both the existence of strongly and weakly aperiodic SFTs. We show that a finitely generated normal subgroup is realizable if and only if the quotient by the subgroup admits a strongly aperiodic SFT. We also show that if a subgroup is realizable, its subgroup membership problem must be decidable. The article also contains the introduction of periodically rigid groups, which are groups for which every weakly aperiodic subshift of finite type is strongly aperiodic. We conjecture that the only finitely generated periodically rigid groups are virtually \(\mathbb{Z}\) groups and torsion-free virtually \(\mathbb{Z}^2\) groups. Finally, we show virtually nilpotent and polycyclic groups satisfy the conjecture.

  2. Computability of Domino Snake Problems on Finitely Generated Groups
    with Nathalie Aubrun
    Journal Version of a conference article. [PDF]
    3. We study the computability of domino snake problems on finitely generated groups. We provide general properties of these problems and introduce new tools for their study. The first is the use of symbolic dynamics to understand the set of all possible snakes. Using this approach we solve many variations of the infinite snake problem including the geodesic snake problem. Next, we introduce a notion of embedding that allows us to reduce the decidability of snake problems between groups. This notion enables us to establish the undecidability of the infinite snake and ouroboros problems on nilpotent groups for any generating set, given that we add a well-chosen element. Finally, we make use of monadic second order logic to prove that domino snake problems are decidable on virtually free groups for all generating sets.

Journals

  1. Self-Avoiding Walks on Cayley Graphs Through the Lens of Symbolic Dynamics
    with Nathalie Aubrun
    The Electronic Journal of Combinatorics 31(4), 2024 [arXiv][Journal]
    2. We study dynamical and computational properties of the set of bi-infinite self-avoiding walks on Cayley graphs, as well as ways to compute, approximate and bound their connective constant. To do this, we introduce the skeleton \(X_{G,S}\) of a finitely generated group \(G\) relative to a generating set \(S\), which is a one-dimensional subshift made of configurations on \(S\) that avoid all words that reduce to the identity. We provide a characterization of groups which have SFT skeletons and sofic skeletons: first, there exists a finite generating set \(S\) such that \(X_{G,S}\) is a subshift of finite type if and only if \(G\) is a plain group; second, there exists \(S\) such that \(X_{G,S}\) is sofic if and only if \(G\) is a plain group, \(\mathbb{Z}\times\mathbb{Z}/2\mathbb{Z}\) or \(\mathcal{D}_{\infty}\times\mathbb{Z}/2\mathbb{Z}\). We also characterize finitely generated torsion groups as groups whose skeletons are aperiodic. For connective constants, using graph height functions and bridges, we show that Cayley graphs of finitely generated torsion groups do not admit graph height functions, and that for groups that admit transitive graph height functions, the connective constant is equal to the growth rate of periodic points of the skeleton. Using a counting argument due to Rosenfeld, we give bounds on the connective constant of infinite free Burnside groups. Finally, we take a brief look at the set of bi-infinite geodesics and introduce an analog of the connective constant for the geodesic growth.

  2. Strongly Aperiodic SFTs on Generalized Baumslag-Solitar groups
    with Nathalie Aubrun and Sacha Huriot-Tattegrain
    Ergodic Theory and Dynamical Systems, 44.5: 1209-1238, 2024. [arXiv][Journal]
    3. We look at constructions of aperiodic SFTs on fundamental groups of graph of groups. In particular we prove that all generalized Baumslag-Solitar groups (GBS) admit a strongly aperiodic SFT. Our proof is based on a structural theorem by Whyte and on two constructions of strongly aperiodic SFTs on \(\mathbb{F}_n\times\mathbb{Z}\) and \(BS(m,n)\) of our own. Our two constructions rely on a path-folding technique that lifts an SFT on \(\mathbb{Z}^2\) inside an SFT on \(\mathbb{F}_n\times\mathbb{Z}\) or an SFT on the hyperbolic plane inside an SFT on \(BS(m,n)\). In the case of \(\mathbb{F}_n\times\mathbb{Z}\) the path folding technique also preserves minimality, so that we get minimal strongly aperiodic SFTs on unimodular GBS groups.

  3. Computational Complexity of Biased Diffusion Limited Aggregation
    with Eric Goles and Pedro Montealegre
    SIAM Journal on Discrete Mathematics 36(1):823-866, 2022 [PDF][Journal]
    4. Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by \(k\)-DLA the model where the particles move only in \(k\) possible directions. We study the biased DLA model from the perspective of Computational Complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid \(c\) and a sequence \(S\) of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site \(c\) when sequence \(S\) is realized. The second problem is Realization, where the input is a set of positions of the grid, \(P\). The question is whether there exists a sequence \(S\) that realizes \(P\), i.e. all particles of \(S\) exactly occupy the positions in \(P\). Our aim is to classify the Prediction and Realization problems for the different versions of DLA. We first show that Prediction is \(P\)-Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case the problem is \(NL\)-Complete. With respect to Realiaztion, we show that restricted to 2-DLA the problem is in \(P\), while in the 1-DLA case, the problem is in \(L\).

Conference Proceedings

  1. Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability
    41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) [arXiv][Proceedings]
    2. We study the seeded domino problem, the recurring domino problem and the \(k\)-SAT problem on finitely generated groups. These problems are generalization of their original versions on \(\mathbb{Z}^2\) that were shown to be undecidable using the domino problem. We show that the seeded and recurring domino problems on a group are invariant under changes in the generating set, are many-one reduced from the respective problems on subgroups, and are positive equivalent to the problems on finite index subgroups. This leads to showing that the recurring domino problem is decidable for free groups. Coupled with the invariance properties, we conjecture that the only groups in which the seeded and recurring domino problems are decidable are virtually free groups. In the case of the \(k\)-SAT problem, we introduce a new generalization that is compatible with decision problems on finitely generated groups. We show that the subgroup membership problem many-one reduces to the \(2\)-SAT problem, that in certain cases the \(k\)-SAT problem many one reduces to the domino problem, and finally that the domino problem reduces to \(3\)-SAT for the class of scalable groups.

  2. Domino Snake Problems on Groups
    with Nathalie Aubrun
    Proceedings of Fundamentals of Computation Theory (FCT 2023), 2023. pg.46-59. [arXiv][Proceedings]
    3. In this article we study domino snake problems on finitely generated groups. We provide general properties of these problems and introduce new tools for their study. The first is the use of symbolic dynamics to understand the set of all possible snakes. Using this approach we solve many variations of the infinite snake problem including the geodesic snake problem for certain classes of groups. Next, we introduce a notion of embedding that allows us to reduce the decidability of snake problems from one group to another. This notion enable us to establish the undecidability of the infinite snake and ouroboros problems on nilpotent groups for any generating set, given that we add a well-chosen element. Finally, we make use of monadic second order logic to prove that domino snake problems are decidable on virtually free groups for all generating sets.

Book Chapters

  1. Distortion in Automorphisms of Expansive Systems
    with Sebastian Donoso and Alejandro Maass, 2022
    Automata and Complexity, Essays presented to Eric Goles on the occasion of his 70th birthday, [Link][PDF]
    2. In this work we study the role distortion plays on automorphisms groups of expansive dynamical systems. We begin by generalizing results from subshifts, linking distortion and non-expansivity, to arbitrary expansive systems, and explore the subset of symmetrically distorted automorphisms. Due to the generalization, we are able to determine that expansive automorphisms can never be distorted.