Research

2024

1. 

   Effective dynamical systems beyond dimension zero and factors of SFTs

   Sebastián Barbieri, Nicanor Carrasco-Vargas, and Cristóbal Rojas

   2024

   Abs arXiv Bib

   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.

   @misc{barbieri2024effective,
     title = {Effective dynamical systems beyond dimension zero and factors of SFTs},
     author = {Barbieri, Sebastián and Carrasco-Vargas, Nicanor and Rojas, Cristóbal},
     year = {2024},
     eprint = {2401.07973},
     archiveprefix = {arXiv},
     primaryclass = {math.DS}
   }

2. 

   Undecidability of dynamical properties of SFTs and sofic subshifts on $\mathbb{Z}^2$ and other groups

   Nicanor Carrasco-Vargas

   2024

   Abs arXiv Bib PDF Poster

   We study the algorithmic undecidability of abstract dynamical properties for sofic $\mathbb{Z}^2$-subshifts and subshifts of finite type (SFTs) on $\mathbb{Z}^2$. Within the class of sofic $\mathbb{Z}^2$-subshifts, we prove the undecidability of every nontrivial dynamical property. We show that although this is not the case for $\mathbb{Z}^2$-SFTs, it is still possible to establish the undecidability of a large class of dynamical properties. This result is analogous to the Adian-Rabin undecidability theorem for group properties. Besides dynamical properties, we consider dynamical invariants of $\mathbb{Z}^2$-SFTs taking values in partially ordered sets. It is well known that the topological entropy of a $\mathbb{Z}^2$-SFT can not be effectively computed from an SFT presentation. We prove a generalization of this result to \emph{every} dynamical invariant which is nonincreasing by factor maps, and satisfies a mild additional technical condition. Our results are also valid for $\mathbb{Z}^{d}$, d≥2, and more generally for any group where determining whether a subshift of finite type is empty is undecidable.

   @misc{carrascovargas2024undecidability,
     title = {Undecidability of dynamical properties of SFTs and sofic subshifts on $\mathbb{Z}^2$ and other groups},
     author = {Carrasco-Vargas, Nicanor},
     year = {2024},
     archiveprefix = {arXiv},
     primaryclass = {math.DS}
   }

2023

1. 

   The geometric subgroup membership problem

   Nicanor Carrasco-Vargas

   2023

   Accepted in Groups, Geometry, and Dynamics.

   Abs arXiv Bib PDF

   We show that every infinite graph which is locally finite and connected admits a translation-like action by $\mathbb{Z}$ such that the distance between a vertex $v$ and $v∗1$ is uniformly bounded by 3. This action can be taken to be transitive if and only if the graph has one or two ends. This strengthens a theorem by Brandon Seward. Our proof is constructive, and thus it can be made computable. More precisely, we show that a finitely generated group with decidable word problem admits a translation-like action by $\mathbb{Z}$ which is computable, and satisfies an extra condition which we call decidable orbit membership problem. As an application we show that on any finitely generated infinite group with decidable word problem, effective subshifts attain all effectively closed Medvedev degrees. This extends a classification proved by Joseph Miller for $\mathbb{Z}^{d}, d≥1$.

   @misc{carrascovargas2023geometric,
     title = {The geometric subgroup membership problem},
     author = {Carrasco-Vargas, Nicanor},
     year = {2023},
     archiveprefix = {arXiv},
     primaryclass = {math.DS},
     url = {https://arxiv.org/abs/2303.14820},
     note = {Accepted in <a href="https://ems.press/journals/ggd">Groups, Geometry, and Dynamics</a>.}
   }

2. 

   Infinite Eulerian trails are computable on graphs with vertices of infinite degree

   Nicanor Carrasco-Vargas

   2023

   Accepted in Computability.

   Abs arXiv Bib PDF

   The Erdős, Grünwald and Weiszfeld theorem provides a characterization of infinite graphs which are Eulerian. That is, infinite graphs which admit infinite Eulerian trails. In this article we complement this theorem with a characterization of those finite trails that can be extended to infinite Eulerian trails. This allows us to prove an effective version of the Erdős, Grünwald and Weiszfeld theorem for a class of graphs that includes non locally finite ones, generalizing a theorem of D.Bean.

   @misc{carrascovargas2023characterization,
     title = {Infinite Eulerian trails are computable on graphs with vertices of infinite degree},
     author = {Carrasco-Vargas, Nicanor},
     year = {2023},
     archiveprefix = {arXiv},
     primaryclass = {math.CO},
     url = {https://arxiv.org/abs/2303.14820},
     note = {Accepted in <a href="https://www.iospress.com/catalog/journals/computability">Computability</a>.}
   }