My research aims to study the rich interplay between the dynamics of group actions and computability to further understand both phenomena from a unified perspective.
A more detailed exposition can be found by clicking on my self portrait on the right.
Preprints
Cellular automata, percolation and dynamical dichotomies. With Felipe García-Ramos and Siamak Taati.
We establish a connection between percolation on the Cayley graphs of a group and the dy-
namical diversity of cellular automata on that group. Specifically, we demonstrate that Gilman’s
dichotomy between equicontinuity and sensitivity with respect to Bernoulli measures holds on a
finitely generated group if and only if the group has a trivial percolation threshold. Consequently,
we show that a countable group satisfies Gilman’s dichotomy if and only if it is locally virtually
cyclic.
Bibtex:
@misc{barbieri-garciaramos-taati-2024-gilmandychotomy,
title={Cellular automata, percolation and dynamical dichotomies},
author={Sebasti\'{a}n Barbieri and Felipe Garc\'{i}a-Ramos and Siamak Taati},
year={2024},
eprint={2410.23770},
archivePrefix={arXiv},
}
Medvedev degrees of subshifts on groups. With Nicanor Carrasco-Vargas.
The Medvedev degree of a subshift is a dynamical invariant of computable origin that can
be used to compare the complexity of subshifts that contain only uncomputable configurations.
We develop theory to describe how these degrees can be transferred from one group to another
through algebraic and geometric relations, such as quotients, subgroups, translation-like actions
and quasi-isometries.
We use the aforementioned tools to study the possible values taken by this invariant on subshifts
of finite type on some finitely generated groups. We obtain a full classification for some classes,
such as virtually polycyclic groups and branch groups with decidable word problem. We also
show that all groups which are quasi-isometric to the hyperbolic plane admit SFTs with nonzero
Medvedev degree. Furthermore, we provide a classification of the degrees of sofic subshifts for
several classes of groups.
Bibtex:
@misc{barbieri2024medvedev,
title={Medvedev degrees of subshifts on groups},
author={Sebastián Barbieri and Nicanor Carrasco-Vargas},
year={2024},
eprint={2406.12777},
archivePrefix={arXiv},
}
The group of reversible Turing machines: subgroups, generators and computability. With Jarkko Kari and Ville Salo.
We study an abstract group of reversible Turing machines. In our model, each machine is interpreted as a homeomorphism over a space which represents a tape filled with symbols and a head carrying a state. These homeomorphisms can only modify the tape at a bounded distance around the head, change the state and move the head in a bounded way. We study three natural subgroups arising in this model: the group of finite-state automata, which generalizes the topological full groups studied in topological dynamics and the theory of orbit-equivalence; the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates; and the group of elementary Turing machines, which are the machines which are obtained by composing finite-state automata and oblivious Turing machines.
We show that both the group of oblivious Turing machines and that of elementary Turing machines are finitely generated, while the group of finite-state automata and the group of reversible Turing machines are not. We show that the group of elementary Turing machines has undecidable torsion problem. From this, we also obtain that the group of cellular automata (more generally, the automorphism group of any uncountable one-dimensional sofic subshift) contains a finitely-generated subgroup with undecidable torsion problem. We also show that the torsion problem is undecidable for the topological full group of a full $\mathbb{Z}^d$-shift on a non-trivial alphabet if and only if $d \geq 2$.
Bibtex:
@misc{Barbieri_Kari_Salo_2023,
Author = {Sebasti{\'{a}}n Barbieri and Jarkko Kari and Ville Salo},
Title = {he group of reversible Turing machines: subgroups, generators and computability},
Year = {2023},
Eprint = {arXiv:2303.17270},
}
Groups with self-simulable zero-dimensional dynamics. With Mathieu Sablik and Ville Salo.
We say that a finitely generated group $\Gamma$ is (dynamically) self-simulable if every effectively closed action of $\Gamma$ on a closed subset of $\{\mathtt{0},\mathtt{1}\}^{\mathbb{N}}$ is the topological factor of a $\Gamma$-subshift of finite type. We show that self-simulable groups exist, that any direct product of non-amenable finitely generated groups is self-simulable, that under technical conditions self-simulability is inherited from subgroups, and that the subclass of self-simulable groups is stable under commensurability and quasi-isometries of finitely presented groups.
Some notable examples of self-simulable groups obtained are the direct product $F_k \times F_k$ of two free groups of rank $k \geq 2$, non-amenable finitely generated branch groups, the simple groups of Burger and Mozes, Thompson's $V$, the groups $\operatorname{GL}_n(\mathbb{Z})$, $\operatorname{SL}_n(\mathbb{Z})$, $\operatorname{Aut}(F_n)$ and $\operatorname{Out}(F_n)$ for $n \geq 5$; The Braid groups $B_m$ for $m \geq 7$, and certain classes of RAAGs. We also show that Thompson's $F$ is self-simulable if and only if $F$ is non-amenable, thus giving a computability characterization of this well-known open problem. We also exhibit a few applications of self-simulability on the dynamics of these groups, notably, that every self-simulable group with decidable word problem admits a nonempty strongly aperiodic subshift of finite type.
Bibtex:
@misc{Barbieri_Sablik_Salo_2021,
Author = {Sebasti{\'{a}}n Barbieri and Mathieu Sablik and Ville Salo},
Title = {Groups with self-simulable zero-dimensional dynamics},
Year = {2021},
Eprint = {arXiv:2104.05141},
}
Journals
Soficity of free extensions of effective subshifts. With Mathieu Sablik and Ville Salo. Discrete and Continuous Dynamical Systems, in early access.
Let $G$ be a group and $H\leqslant G$ a subgroup. The free extension of an $H$-subshift $X$ to $G$ is the $G$-subshift $\widetilde{X}$ whose configurations are those for which the restriction to every coset of $H$ is a configuration from $X$. We study the case of $G = H \times K$ for finitely generated groups $H$ and $K$: on the one hand we show that if $K$ is nonamenable and $H$ has decidable word problem, then the free extension to $G$ of any $H$-subshift which is effectively closed is a sofic $G$-subshift. On the other hand we prove that if both $H$ and $K$ are amenable, there are always $H$-subshifts which are effectively closed by patterns whose free extension to $G$ is non-sofic. We also present a few applications in the form of a new simulation theorem and a new class of groups which admit strongly aperiodic
SFTs.
Bibtex:
@articleInfo{BSS_2024_soficity_free,
title = {Soficity of free extensions of effective subshifts},
journal = {Discrete and Continuous Dynamical Systems},
pages = {}
year = {2024},
issn = {1078-0947},
doi = {10.3934/dcds.2024125},
url = {https://www.aimsciences.org/article/id/66f10c972bcf34161cd931e6},
author = {Sebastián Barbieri and Mathieu Sablik and Ville Salo},
keywords = {Symbolic dynamics, effectively closed action, free extension, simulation, non-amenable group, subshift of finite type}
}
Effective dynamical systems beyond dimension zero and factors of SFTs. With Nicanor Carrasco-Vargas and Cristóbal Rojas. Ergodic Theory and Dynamical Systems, published in first view.
Using tools from computable analysis we develop a notion of effectiveness for general dynamical systems as those group actions on arbitrary spaces that contain a computable representative in their topological conjugacy class. Most natural systems one can think of are effective in this sense, including some group rotations, affine actions on the torus and finitely presented algebraic actions. We show that for finitely generated and recursively presented groups, every effective dynamical system is the topological factor of a computable action on an effectively closed subset of the Cantor space. We then apply this result to extend the simulation results available in the literature beyond zero-dimensional spaces. In particular, we show that for a large class of groups, many of these natural actions are topological factors of subshifts of finite type.
Bibtex:
@misc{BCR_2024_arxiv,
doi = {10.48550/ARXIV.2401.07973},
url = {https://arxiv.org/abs/2401.07973},
author = {Barbieri, Sebasti\'an and Carrasco-Vargas, Nicanor and Rojas, Crist\'obal},
title = {Effective dynamical systems beyond dimension zero and factors of {SFT}s},
publisher = {arXiv},
year = {2024},
}
Indistinguishable asymptotic pairs and multidimensional Sturmian configurations. With Sébastien Labbé. Ergodic Theory and Dynamical Systems, published in first view.
Two asymptotic configurations on a full $\mathbb{Z}^d$-shift are indistinguishable if for every finite pattern the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of $\mathbb{Z}^d$. We prove that indistinguishable asymptotic pairs satisfying a "flip condition" are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together the two results provide a generalization to $\mathbb{Z}^d$ of the characterization of Sturmian sequences by their factor complexity $n+1$. Many open questions are raised by the current work and are listed in the introduction.
Bibtex:
@journal{Barbieri_Labbe_ETDS_2024,
Author = {Sebasti{\'{a}}n Barbieri and S{\'e}bastien Labb{\'e}},
Title = {Indistinguishable asymptotic pairs and multidimensional Sturmian configurations},
DOI={10.1017/etds.2024.39},
Year = {2024},
pages={1–59},
Journal = {Ergodic Theory and Dynamical Systems},
}
Zero-Temperature Chaos in Bidimensional Models with Finite-Range Potentials. With Rodrigo Bissacot, Gregório Dalle Vedove and Philippe Thieullen. Advances in Mathematics, 457(109906):1–51, 2024.
We construct a finite-range potential on a bidimensional full shift on a finite alphabet that exhibits a zero-temperature chaotic behavior as introduced by van Enter and Ruszel. This is the phenomenon where there exists a sequence of temperatures that converges to zero for which the whole set of equilibrium measures at these given temperatures oscillates between two sets of ground states. Br\'emont's work shows that the phenomenon of non-convergence does not exist for finite-range potentials in dimension one for finite alphabets; Leplaideur obtained a different proof for the same fact. Chazottes and Hochman provided the first example of non-convergence in higher dimensions $d\geq3$; we extend their result for $d=2$ and highlight the importance of two estimates of recursive nature that are crucial for this proof: the relative complexity and the reconstruction function of an extension.
We note that a different proof of this result was found by Chazottes and Shinoda, at around the same time that this article was initially submitted and that a strong generalization has been found by Gayral, Sablik and Taati.
Bibtex:
@article{BARBIERI2024109906,
title = {Zero-temperature chaos in bidimensional models with finite-range potentials},
journal = {Advances in Mathematics},
volume = {457},
pages = {109906},
year = {2024},
issn = {0001-8708},
doi = {https://doi.org/10.1016/j.aim.2024.109906},
url = {https://www.sciencedirect.com/science/article/pii/S0001870824004213},
author = {Sebastián Barbieri and Rodrigo Bissacot and Gregório {Dalle Vedove} and Philippe Thieullen},
keywords = {Chaos at zero temperature, Ground states, Equilibrium measures, Turing machines, Computability},
abstract = {We construct a finite-range potential on a bidimensional full shift on a finite alphabet that exhibits a zero-temperature chaotic behavior as introduced by van Enter and Ruszel. This is the phenomenon where there exists a sequence of temperatures that converges to zero for which the whole set of equilibrium measures at these given temperatures oscillates between two sets of ground states. Brémont's work shows that the phenomenon of non-convergence does not exist for finite-range potentials in dimension one for finite alphabets; Leplaideur obtained a different proof for the same fact. Chazottes and Hochman provided the first example of non-convergence in higher dimensions d≥3; we extend their result for d=2 and highlight the importance of two estimates of recursive nature that are crucial for this proof: the relative complexity and the reconstruction function of an extension. We note that a different proof of this result was found by Chazottes and Shinoda, at around the same time that this article was initially submitted and that a strong generalization has been found by Gayral, Sablik and Taati.}
}
Aperiodic subshifts of finite type on groups which are not finitely generated. Proceedings of the American Mathematical Society, 151:3839-3843, 2023
We provide an example of a non-finitely generated group which admits a nonempty strongly aperiodic subshift of finite type. Furthermore, we completely characterize the groups with this property in terms of their finitely generated subgroups and the roots of their conjugacy classes.
Bibtex:
@article{Barbieri2023,
doi = {10.1090/proc/16379},
url = {https://doi.org/10.1090/proc/16379},
year = {2023},
month = jun,
publisher = {American Mathematical Society ({AMS})},
author = {Sebasti{\'{a}}n Barbieri},
title = {Aperiodic subshifts of finite type on groups which are not finitely generated},
journal = {Proceedings of the American Mathematical Society}
}
The Lanford–Ruelle theorem for actions of sofic groups. With Tom Meyerovitch. Transactions of the American Mathematical Society, 376(2):1299-9947, 2023.
Let $\Gamma$ be a sofic group, $\Sigma$ be a sofic approximation sequence of
$\Gamma$ and $X$ be a $\Gamma$-subshift with nonnegative sofic topological
entropy with respect to $\Sigma$. Further assume that $X$ is a shift of finite
type, or more generally, that $X$ satisfies the topological Markov property. We
show that for any sufficiently regular potential $f \colon X \to \mathbb{R}$,
any translation-invariant Borel probability measure on $X$ which maximizes the
measure-theoretical sofic pressure of $f$ with respect to $\Sigma$, is a Gibbs
state with respect to $f$. This extends a classical theorem of Lanford and
Ruelle, as well as previous generalizations of Moulin Ollagnier, Pinchon, Tempelman and others, to the case where the group is sofic.
As applications of our main result we present a criterion for uniqueness of
an equilibrium measure, as well as sufficient conditions for having that the
equilibrium states do not depend upon the chosen sofic approximation sequence.
We also prove that for any group-shift over a sofic group, the Haar measure is
the unique measure of maximal sofic entropy for every sofic approximation
sequence, as long as the homoclinic group is dense.
On the expository side, we present a short proof of Chung's variational
principle for sofic topological pressure.
Bibtex:
@article {MR4531676,
AUTHOR = {Barbieri, Sebasti\'{a}n and Meyerovitch, Tom},
TITLE = {The {L}anford-{R}uelle theorem for actions of sofic groups},
JOURNAL = {Trans. Amer. Math. Soc.},
FJOURNAL = {Transactions of the American Mathematical Society},
VOLUME = {376},
YEAR = {2023},
NUMBER = {2},
PAGES = {1299--1342},
ISSN = {0002-9947},
MRCLASS = {37B10 (37D35 82B20)},
MRNUMBER = {4531676},
DOI = {10.1090/tran/8810},
URL = {https://doi.org/10.1090/tran/8810},
}
Markovian properties of continuous group actions: algebraic actions, entropy and the homoclinic group. With Felipe García Ramos and Hanfeng Li. Advances in Mathematics, 397(108196):1–52, 2022.
We provide a unifying approach which links results on algebraic actions by Lind and Schmidt, Chung and Li, and a topological result by Meyerovitch that relates entropy to the set of asymptotic pairs. In order to do this we introduce a series of Markovian properties and, under the assumption that they are satisfied, we prove several results that relate topological entropy and asymptotic pairs (the homoclinic group in the algebraic case). As new applications of our method, we give a characterization of the homoclinic group of any finitely presented expansive algebraic action of (1) any elementary amenable group with an upper bound on the orders of finite subgroups or (2) any left orderable amenable group, using the language of independence entropy pairs.
Bibtex:
@article{Barbieri_Ramos_Li_2022,
doi = {10.1016/j.aim.2022.108196},
url = {https://doi.org/10.1016/j.aim.2022.108196},
year = {2022},
month = mar,
publisher = {Elsevier {BV}},
volume = {397},
pages = {108196},
author = {Sebasti{\'{a}}n Barbieri and Felipe Garc{\'{\i}}a-Ramos and Hanfeng Li},
title = {Markovian properties of continuous group actions: Algebraic actions, entropy and the homoclinic group},
journal = {Advances in Mathematics}
}
On the entropies of subshifts of finite type on countable amenable groups. Groups, Geometry and Dynamics, 15(2):607–638, 2021. There is a mistake in the proof of Thm 4.7, this will be updated soon.
Let $G,H$ be two countable amenable groups. We introduce the notion of group charts, which gives us a tool to embed an arbitrary $H$-subshift into a $G$-subshift. Using an entropy addition formula derived from this formalism we prove that whenever $H$ is finitely presented and admits a subshift of finite type (SFT) on which $H$ acts freely, then the set of real numbers attained as topological entropies of $H$-SFTs is contained in the set of topological entropies of $G$-SFTs modulo an arbitrarily small additive constant for any finitely generated group $G$ which admits a translation-like action of $H$. In particular, we show that the set of topological entropies of $G$-SFTs on any such group which has decidable word problem and admits a translation-like action of $\mathbb{Z}^2$ coincides with the set of non-negative upper semi-computable real numbers. We use this result to give a complete characterization of the entropies of SFTs in several classes of groups.
Bibtex:
@article{Barbieri_2021,
doi = {10.4171/ggd/608},
url = {https://doi.org/10.4171/ggd/608},
year = {2021},
month = jul,
volume = {15},
number = {2},
pages = {607--638},
publisher = {European Mathematical Society - {EMS} - Publishing House {GmbH}},
author = {Sebasti{\'{a}}n Barbieri},
title = {On the entropies of subshifts of finite type on countable amenable groups},
journal = {Groups, Geometry, and Dynamics}
}
A hierarchy of topological systems with completely positive entropy. With Felipe García-Ramos. Journal d'Analyse Mathématique, 143(2):639-680, 2021.
We define a hierarchy of systems with topological completely positive entropy in the context of countable amenable continuous group actions on compact metric spaces. For each countable ordinal we construct a dynamical system on the corresponding level of the aforementioned hierarchy and provide subshifts of finite type for the first three levels. We give necessary and sufficient conditions for entropy pairs by means of the asymptotic relation on systems with the pseudo-orbit tracing property, and thus create a bridge between a result by Pavlov and a result by Meyerovitch. As a corollary, we answer negatively an open question by Pavlov regarding necessary conditions for completely positive entropy.
Bibtex:
@article{Barbieri_GarciaRamos_2021,
Author = {Sebasti{\'{a}}n Barbieri and Felipe Garc{\'{i}}a-Ramos},
doi = {10.1007/s11854-021-0167-2},
volume = {143},
number = {2},
pages = {639--680},
journal = {Journal d{\textquotesingle}Analyse Math{\'{e}}matique}
title = {A hierarchy of topological systems with completely positive entropy},
publisher = {Springer Science and Business Media {LLC}},
url = {https://doi.org/10.1007/s11854-021-0167-2},
year = {2021},
month = jun
}
A characterization of Sturmian sequences by indistinguishable asymptotic pairs With Sébastien Labbé and Štěpán Starosta. European Journal of Combinatorics, 95(103318):1-22, 2021.
We give a new characterization of Sturmian configurations in terms of indistinguishable asymptotic pairs. Two asymptotic configurations on a full $\mathbb{Z}$-shift are indistinguishable if the sets of occurrences of every pattern in each configuration coincide up to a finitely supported permutation. This characterization can be seen as an extension to biinfinite sequences of Pirillo’s theorem which characterizes Christoffel words. Furthermore, we provide a full characterization of indistinguishable asymptotic pairs on arbitrary alphabets using substitutions and characteristic Sturmian sequences. The proof is based on the well-known notion of derived sequences.
Bibtex:
@article{BarLabSta_2021,
title = {A characterization of Sturmian sequences by indistinguishable asymptotic pairs},
journal = {European Journal of Combinatorics},
volume = {95},
pages = {103318},
year = {2021},
issn = {0195-6698},
doi = {https://doi.org/10.1016/j.ejc.2021.103318},
url = {https://www.sciencedirect.com/science/article/pii/S019566982100010X},
author = {Sebastián Barbieri and Sébastien Labbé and Štěpán Starosta},
abstract = {We give a new characterization of biinfinite Sturmian sequences in terms of indistinguishable asymptotic pairs. Two asymptotic sequences on a full Z-shift are indistinguishable if the sets of occurrences of every pattern in each sequence coincide up to a finitely supported permutation. This characterization can be seen as an extension to biinfinite sequences of Pirillo’s theorem which characterizes Christoffel words. Furthermore, we provide a full characterization of indistinguishable asymptotic pairs on arbitrary alphabets using substitutions and biinfinite characteristic Sturmian sequences. The proof is based on the well-known notion of derived sequences.}
}
Gibbsian representations of continuous specifications: the theorems of Kozlov and Sullivan revisited. With Ricardo Gómez, Brian Marcus, Tom Meyerovitch and Siamak Taati. Communications in Mathematical Physics, 382(2):1111–1164, 2021.
The theorems of Kozlov and Sullivan characterize Gibbs measures as measures with positive continuous specifications. More precisely, Kozlov showed that every positive continuous specification on symbolic configurations of the lattice is generated by a norm-summable interaction. Sullivan showed that every shift-invariant positive continuous specification is generated by a shift-invariant interaction satisfying the weaker condition of variation-summability. These results were proven in the 1970s. An open question since that time is whether Kozlov’s theorem holds in the shift-invariant setting, equivalently whether Sullivan’s conclusion can be improved from variation-summability to norm-summability. We show that the answer is no: there exist shift-invariant positive continuous specifications that are not generated by any shift-invariant norm-summable interaction. On the other hand, we give a complete proof of an extension, suggested by Kozlov, of Kozlov’s theorem to a characterization of positive continuous specifications on configuration spaces with arbitrary hard constraints. We also present an extended version of Sullivan’s theorem. Aside from simplifying some of the arguments in the original proof, our new version of Sullivan’s theorem applies in various settings not covered by the original proof. In particular, it applies when the support of the specification is the hard-core shift or the two-dimensional $q$-coloring shift for $q \geq 6$.
Bibtex:
@article{Barbieri_Gomez_Marcus_Meyerovitch_Taati_2020,
doi = {10.1007/s00220-021-03979-2},
url = {https://doi.org/10.1007/s00220-021-03979-2},
year = {2021},
month = feb,
publisher = {Springer Science and Business Media {LLC}},
volume = {382},
number = {2},
pages = {1111--1164},
author = {Sebasti{\'{a}}n Barbieri and Ricardo G{\'{o}}mez and Brian Marcus and Tom Meyerovitch and Siamak Taati},
title = {{G}ibbsian Representations of Continuous Specifications: The Theorems of {K}ozlov and {S}ullivan Revisited},
journal = {Communications in Mathematical Physics}
}
Equivalence of relative Gibbs and relative equilibrium measures for
actions of countable amenable groups. With Ricardo Gómez, Brian Marcus and Siamak Taati. Nonlinearity, 33(5):2409–2454, 2020.
We formulate and prove a very general relative version of the Dobrushin-Lanford-Ruelle theorem which gives conditions on constraints of configuration spaces over a finite alphabet such that for every absolutely
summable relative interaction, every translation-invariant relative Gibbs
measure is a relative equilibrium measure and vice versa. Neither implication
is true without some assumption on the space of configurations. We note that
the usual finite type condition can be relaxed to a much more general class of
constraints. By "relative" we mean that both the interaction and the set of
allowed configurations are determined by a random environment. The result
includes many special cases that are well known. We give several applications
including (1) Gibbsian properties of measures that maximize pressure among all
those that project to a given measure via a topological factor map from one
symbolic system to another; (2) Gibbsian properties of equilibrium measures for
group shifts defined on arbitrary countable amenable groups; (3) A Gibbsian
characterization of equilibrium measures in terms of equilibrium condition on
lattice slices rather than on finite sets; (4) A relative extension of a
theorem of Meyerovitch, who proved a version of the Lanford--Ruelle theorem
which shows that every equilibrium measure on an arbitrary subshift satisfies a
Gibbsian property on interchangeable patterns.
Bibtex:
@article{Barbieri_2020,
doi = {10.1088/1361-6544/ab6a75},
year = 2020,
month = {mar},
publisher = {{IOP} Publishing},
volume = {33},
number = {5},
pages = {2409--2454},
author = {Sebasti{\'{a}}n Barbieri and Ricardo G{\'{o}}mez and Brian Marcus and Siamak Taati},
title = {Equivalence of relative {G}ibbs and relative equilibrium measures for actions of countable amenable groups},
journal = {Nonlinearity}
}
A geometric simulation theorem on direct products of finitely generated groups. Discrete Analysis, 9:25, 2019.
We show that every effectively closed action of a finitely generated group $G$ on a closed subset of $\{0,1\}^{\mathbb{N}}$ can be obtained as a topological factor of the $G$-subaction of a $(G \times H_1 \times H_2)$-subshift of finite type (SFT) for any choice of infinite and finitely generated groups $H_1,H_2$. As a consequence, we obtain that every group of the form $G_1 \times G_2 \times G_3$ admits a non-empty strongly aperiodic SFT subject to the condition that each $G_i$ is finitely generated and has decidable word problem. As a corollary of this last result we prove the existence of non-empty strongly aperiodic SFT in a large class of branch groups, notably including the Grigorchuk group.
Bibtex:
@article{Barbieri_2019_DA,
title={A geometric simulation theorem on direct products of finitely generated groups},
doi = {10.19086/da.8820},
journal={Discrete Analysis},
author={Sebasti{\'a}n Barbieri},
number={9},
year={2019},
month = jun,
}
A generalization of the simulation theorem for semidirect products. With Mathieu Sablik. Ergodic Theory and Dynamical Systems, 39(12):3185–3206, 2019.
We generalize a result of Hochman in two simultaneous directions: instead of realizing an arbitrary effectively closed $\mathbb{Z}^d$ action as a factor of a subaction of a $\mathbb{Z}^{d+2}$-SFT we realize an action of a finitely generated group analogously in any semidirect product of the group with $\mathbb{Z}^2$. Let $H$ be a finitely generated group and $G = \mathbb{Z}^2 \rtimes_{\varphi} H$ a semidirect product. We show that for any effectively closed $H$-dynamical system $(Y,T)$ where $Y \subset \{0,1\}^{\mathbb{N}}$, there exists a $G$-subshift of finite type $(X,\sigma)$ such that the $H$-subaction of $(X,\sigma)$ is an extension of $(Y,T)$. In the case where $T$ is an expansive action, a subshift conjugated to $(Y,T)$ can be obtained as the $H$-projective subdynamics of a sofic $G$-subshift. As a corollary, we obtain that $G$ admits a non-empty strongly aperiodic subshift of finite type whenever the word problem of $H$ is decidable.
Bibtex:
@article{Barbieri_Sablik_2019,
title={A generalization of the simulation theorem for semidirect products},
volume={39},
DOI={10.1017/etds.2018.21},
number={12},
journal={Ergodic Theory and Dynamical Systems},
publisher={Cambridge University Press},
author={Barbieri, Sebasti{\'{a}}n and Sablik, Mathieu},
year={2019},
pages={3185--3206}
}
Realization of aperiodic subshifts and uniform densities in groups. With Nathalie Aubrun and Stéphan Thomassé. Groups, Geometry, and Dynamics, 13(1):107–129, 2019.
A theorem of Gao, Jackson and Seward, originally conjectured to be false by Glasner and Uspenskij, asserts that every countable group admits a 2-coloring. A direct consequence of this result is that every countable group has a strongly aperiodic subshift on the alphabet $\{0,1\}$. In this article, we use Lovász local lemma to first give a new simple proof of said theorem, and second to prove the existence of a $G$-effectively closed strongly aperiodic subshift for any finitely generated group $G$. We also study the problem of constructing subshifts which generalize a property of Sturmian sequences to finitely generated groups. More precisely, a subshift over the alphabet $\{0,1\}$ has uniform density $\alpha \in [0,1]$ if for every configuration the density of 1's in any increasing sequence of balls converges to $\alpha$. We show a slightly more general result which implies that these subshifts always exist in the case of groups of subexponential growth.
Bibtex:
@article{Aubrun_Barbieri_Thomasse_2019,
doi = {10.4171/ggd/487},
url = {https://doi.org/10.4171/ggd/487},
year = {2019},
publisher = {European Mathematical Publishing House},
volume = {13},
number = {1},
pages = {107--129},
author = {Nathalie Aubrun and Sebasti{\'{a}}n Barbieri and St{\'{e}}phan Thomass{\'{e}}},
title = {Realization of aperiodic subshifts and uniform densities in groups},
journal = {Groups, Geometry, and Dynamics}
}
A notion of effectiveness for subshifts on finitely
generated groups. With Nathalie Aubrun and Mathieu Sablik. In Theoretical Computer Science, 661:35–55, 2017.
We generalize the classical definition of effectively closed subshift to finitely generated groups. We study classical stability properties of this class and then extend this notion by allowing the usage of an oracle to the word problem of a group. This new class of subshifts forms a conjugacy class that contains all sofic subshifts. Motivated by the question of whether there exists a group where the class of sofic subshifts coincides with that of effective subshifts, we show that the inclusion is strict for several groups, including recursively presented groups with undecidable word problem, amenable groups and groups with more than two ends. We also provide an extended model of Turing machine which uses the group itself as a tape and characterizes our extended notion of effectiveness. As applications of these machines we prove that the origin constrained domino problem is undecidable for any group of the form $G\times \mathbb{Z}$ subject to a technical condition on G and we present a simulation theorem which is valid in any finitely generated group.
Bibtex:
@article{Aubrun_Barbieri_Sablik_2017,
title = "A notion of effectiveness for subshifts on finitely generated groups",
journal = "Theoretical Computer Science",
volume = "661",
pages = "35 - 55",
year = "2017",
issn = "0304-3975",
doi = "https://doi.org/10.1016/j.tcs.2016.11.033",
url = "http://www.sciencedirect.com/science/article/pii/S0304397516306983",
author = "Nathalie Aubrun and Sebasti{\'a}n Barbieri and Mathieu Sablik",
keywords = "Symbolic dynamics, Turing machines, Word problems, Models of computation"
}
Conference Proceedings
The domino problem is undecidable on surface groups. With Nathalie Aubrun and Etienne Moutot. 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), pages 1–14, 2019.
We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove that the domino problem is undecidable for the fundamental group of any closed orientable surface of genus at least 2.
Bibtex:
@InProceedings{Aubrun_Barbieri_Moutot_2018,
author = {Nathalie Aubrun and Sebasti{\'a}n Barbieri and Etienne Moutot},
title = {{The Domino Problem is Undecidable on Surface Groups}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {46:1--46:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-117-7},
ISSN = {1868-8969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10990},
URN = {urn:nbn:de:0030-drops-109900},
doi = {10.4230/LIPIcs.MFCS.2019.46},
annote = {Keywords: tilings, substitutions, SFTs, decidability, domino problem}
}
The domino problem for self-similar structures. With Mathieu Sablik. Pursuit of the Universal (CIE 2016), pages 205–214, 2016.
We define the domino problem for tilings over self-similar structures of $\mathbb{Z}^d$ given by forbidden patterns. In this setting we exhibit non-trivial families of subsets with decidable and undecidable domino problem.
Bibtex:
@InProceedings{Barbieri_Sablik_2016,
author="Barbieri, Sebasti{\'a}n
and Sablik, Mathieu",
editor="Beckmann, Arnold
and Bienvenu, Laurent
and Jonoska, Nata{\v{s}}a",
title="The Domino Problem for Self-similar Structures",
booktitle="Pursuit of the Universal",
year="2016",
publisher="Springer International Publishing",
address="Cham",
pages="205--214",
isbn="978-3-319-40189-8"
}
The group of reversible Turing machines. With Jarkko Kari and Ville Salo. Cellular Automata and Discrete Complex Systems (AUTOMATA 2016), pages 49–62, 2016.
We consider Turing machines as actions over configurations in $\Sigma^{\mathbb{Z}^d}$ which only change them locally around a marked position that can move and carry a particular state. In this setting we study the monoid of Turing machines and the group of reversible Turing machines. We also study two natural subgroups, namely the group of finite-state automata, which generalizes the topological full groups studied in the theory of orbit-equivalence, and the group of oblivious Turing machines whose movement is independent of tape contents, which generalizes lamplighter groups and has connections to the study of universal reversible logical gates. Our main results are that the group of Turing machines in one dimension is neither amenable nor residually finite, but is locally embeddable in finite groups, and that the torsion problem is decidable for finite-state automata in dimension one, but not in dimension two.
Bibtex:
@InProceedings{Barbieri_Kari_Salo_2016,
author="Barbieri, Sebasti{\'a}n
and Kari, Jarkko
and Salo, Ville",
editor="Cook, Matthew
and Neary, Turlough",
title="The Group of Reversible Turing Machines",
booktitle="Cellular Automata and Discrete Complex Systems",
year="2016",
publisher="Springer International Publishing",
address="Cham",
pages="49--62",
isbn="978-3-319-39300-1"
}
Book chapters
About the Domino Problem for Subshifts on Groups. With Nathalie Aubrun and Emmanuel Jeandel. Sequences, Groups, and Number Theory, pages 331–389. Springer
International Publishing, 2018.
From a classical point of view, the domino problem is the question of the existence of an algorithm which can decide whether a finite set of square tiles with colored edges can tile the plane, subject to the restriction that adjacent tiles share the same color along their adjacent edges. This question has already been settled in the negative
by Berger in 1966, however, these tilings can be reinterpreted in dynamical terms using the formalism of subshifts of finite type, and hence the same question can be formulated for arbitrary finitely generated groups. In this chapter we present the state of the art concerning the domino problem in this extended framework. We also discuss different notions of effectiveness in subshifts defined over groups, that is, the ways in which these dynamical objects can be described through Turing machines.
Bibtex:
@incollection{Aubrun_Barbieri_Jeandel_2018,
address = {Cham},
series = {Trends in {Mathematics}},
title = {About the {Domino} {Problem} for {Subshifts} on {Groups}},
isbn = {978-3-319-69152-7},
language = {en},
urldate = {2019-05-25},
booktitle = {Sequences, {Groups}, and {Number} {Theory}},
publisher = {Springer International Publishing},
author = {Aubrun, Nathalie and Barbieri, Sebasti{\'{a}}n and Jeandel, Emmanuel},
editor = {Berth{\'{e}}, Val{\'{e}}rie and Rigo, Michel},
year = {2018},
doi = {10.1007/978-3-319-69152-7_9},
pages = {331--389},
}
Thesis and Memoires
Shift spaces on groups: computability and dynamics. Theses, Université
de Lyon (ENS de Lyon), June 2017.
Shift spaces are sets of colorings of a group which avoid a set of forbidden patterns and are endowed with a shift action. These spaces appear naturally as discrete versions of dynamical systems: they are obtained by partitioning the phase space and mapping each element into the sequence of partitions visited by its orbit.
Several breakthroughs in this domain have pointed out the intricate relationship between dynamics of shift spaces and their computability properties. One remarkable example is the classification of the entropies of multidimensional subshifts of finite type as the set of right recursively enumerable numbers. This work explores shift spaces with a dual approach: on the one hand we are interested in their dynamical properties and on the other hand we study these objects as computational models.
Four salient results have been obtained as a result of this approach: (1) a combinatorial condition ensuring non-emptiness of subshifts on arbitrary countable groups; (2) a simulation theorem which realizes effective actions of finitely generated groups as factors of a subaction of a subshift of finite type; (3) a characterization of effectiveness with oracles using generalized Turing machines and (4) the undecidability of the torsion problem for two group invariants of shift spaces.
As byproducts of these results we obtain a simple proof of the existence of strongly aperiodic subshifts in countable groups. Furthermore, we realize them as subshifts of finite type in the case of a semidirect product of a $d$-dimensional integer lattice with a finitely generated group with decidable word problem whenever $d>1$.
Bibtex:
@phdthesis{barbierilemp:tel-01563302,
TITLE = {{Shift spaces on groups : computability and dynamics}},
AUTHOR = {Barbieri, Sebasti{\'{a}}n},
URL = {https://tel.archives-ouvertes.fr/tel-01563302},
NUMBER = {2017LYSEN021},
SCHOOL = {{Universit{\'e} de Lyon}},
YEAR = {2017},
MONTH = Jun,
KEYWORDS = {Conjugacy invariants ; Group theory ; Simulation theorems ; Symbolic dynamics ; Dynamical systems ; Shift spaces ; Aperiodicity ; Computability ; Dynamique symbolique ; Syst{\`e}mes dynamiques ; Sous-d{\'e}calages ; Aperiodicit{\'e} ; Calculabilit{\'e} ; Th{\'e}or{\`e}mes de simulation ; Th{\'e}orie des groupes ; Invariants de conjugaison},
TYPE = {Theses},
HAL_ID = {tel-01563302},
HAL_VERSION = {v1},
}
Tilings on different structures: exploration
towards two problems. Mémoire Master 2, 2014.
We study the problem of tiling structures which are different from the usual group $\mathbb{Z}^d$. In the first part we show a class of finitely generated groups for which the $G$-subshift $X_{\leq 1}$, which consists on the functions from $G$ to $\{0,1\}$ so that at most one $g \in G$ can map to 1, is not of sofic type. In the second part we study tilings over structures which are not groups and are generated by a special type of substitution. We define the emptiness problem and the possibility to simulate more complex substitutions in these structures and we show results in that direction for two specific examples. We end that section by constructing a partial order which under the assumption of a property preserves decidability of the emptiness problem monotonically.
Subshifts generados por sustituciones multidimensionales. Memoria ingeniería Universidad de Chile, 2014.
Sebastián Barbieri Lemp 
