Preprints
- Self-Avoiding Walks on Cayley Graphs Through the Lens of Symbolic Dynamics
with Nathalie Aubrun
arXiv Preprint [arXiv] - Computability of Domino Snake Problems on Finitely Generated Groups
with Nathalie Aubrun
Journal Version of a conference article. [PDF]
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.
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
- Strongly Aperiodic SFTs on Generalized Baumslag-Solitar groups
with Nathalie Aubrun and Sacha Huriot-Tattegrain
Ergodic Theory and Dynamical Systems, First View, pp.1-30, 2023 [arXiv][Journal] - 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]
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.
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
- Contributions to the Domino Problem: Seeding, Recurrence and Satisfiability
41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) [arXiv][Proceedings] - Domino Snake Problems on Groups
with Nathalie Aubrun
Proceedings of Fundamentals of Computation Theory (FCT 2023), 2023. pg.46-59. [arXiv][Proceedings]
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.
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
- 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]
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.