A remark on inverse limits of effective subshifts

Sebastián Barbieri, Leo Poirier · 2025

Read A remark on inverse limits of effective subshifts by Sebastián Barbieri, Leo Poirier (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00183.txt.

Introduction

Sebastián Barbieri and Leo Poirier show that stacking rule-bound pattern systems can escape any rule-bound system above them, for a wide class of groups, in a paper from two thousand twenty-five. These groups have solvable word choice but unsolvable tiling choice. The chain's limit is no projection of any single effective system.

Catalog record

CREATORSebastián Barbieri, Leo Poirier
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-00183

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A remark on inverse limits of effective subshifts Sebastián Barbieri, Leo Poirier Abstract We show that, for every finitely generated group with decidable word problem and undecidable domino problem, there exists a sequence of effective subshifts whose inverse limit is not the topological factor of any effective dynamical system. This follows from considerations on the universality under topological factors for this class of dynamical systems. Keywords: symbolic dynamics, effective dynamical systems, universality, topological factors. MSC2020: Primary: 37B10, Secondary: 20F10. 1 Introduction Given a finitely generated group G and a compact metrizable space X , one can consider the space of all actions of G on X by homeomorphisms. This space can be quite large, and a natural restriction is to consider only actions which are effective , in the sense that both the space and the dynamics can be described by an algorithm. Effective actions can be formally defined using computable analysis. We say that an action of a finitely generated group G\curvearrowright X is an effective dynamical system (EDS), if it is topologically conjugate to an action of G on a recursively compact subset of a computable metric space, in such a way that every generator of G acts through computable maps. This class of actions is intimately related to other natural classes of group actions, such as subshifts of finite type, see [ 8 , 3 ] . The understanding of this relationship has led to interesting results, such as the classification of the numbers that arise as topological entropies of subshifts of finite type [ 9 ] in \mathbb{Z}^{2} and the existence of chaotic behavior at zero-temperature for locally constant potentials [ 6 ] . While the class of EDS satisfies several interesting dynamical properties, in general it is not closed under topological factor maps (see the examples in [ 3 , Propositions 8.1 and 8.2] ). However, the class of topological factors of an EDS does satisfy a weak computability constraint: it must be topologically conjugate to the inverse limit of a (non-necessarily uniform) sequence of effective subshifts [ 3 , Corollary 8.8] . This led the authors of [ 3 ] to define the class of weakly effective dynamical systems (wEDS) as that of the groups actions G\curvearrowright X which are topologically conjugate to the inverse limit of a sequence of effective G -subshifts. The class of wEDS is stable under topological factor maps, and every EDS is a wEDS. The main motivation behind the name wEDS in [ 3 ] was an initial belief that they might characterize the class of topological factors of EDS ( [ 3 , Question 8.12] ). Our main result is that in fact there exists wEDS which are not the topological factor of any EDS in a large class of groups. Theorem A . For any finitely generated group with decidable word problem and undecidable domino problem, there exists a wEDS which is not the topological factor of any EDS. The domino problem of a finitely generated group G is undecidable if there is no algorithm which, given as input a finite set of forbidden patterns, can decide whether the subshift of finite type induced by those patterns is nonempty. This notion is based on the classical result by Berger [ 4 ] that states, in modern terms, that the domino problem is undecidable for G=\mathbb{Z}^{2} . We refer the reader to [ 1 ] for a survey on the domino problem for groups, and note that it has been conjectured that the only groups for which the domino problem is decidable are the virtually free groups [ 2 ] . The proof of A requires two ingredients which, from our point of view, are interesting results by themselves. These results deal with the notion of universality for topological factors. Let us fix a group G . We say that an EDS G\curvearrowright\mathfrak{U} is universal if every other EDS of the group G can be obtained as a topological factor of G\curvearrowright\mathfrak{U} . Similarly, a wEDS of G is called universal is every other wEDS of G is a topological factor of it. The first a ingredient is a characterization, initially proved for \mathbb{Z}^{d} -actions by Hochman [ 7 ] , of the groups with decidable word problem which admit a universal EDS. Theorem B . Let G be a finitely generated group with decidable word problem. There exists a universal EDS G\curvearrowright\mathfrak{U} if and only if the domino problem of G is decidable. We remark that B is just the natural extension of Theorems 1.1 and 1.2 of [ 7 ] to finitely generated groups with decidable word problem, and that this generalization does not present any additional difficulties. We provide this proof in Section 3 for the sake of completeness. The second ingredient is the existence of universal wEDS on any finitely generated group. Theorem C . For every finitely generated group G there exists a universal wEDS G\curvearrowright\mathfrak{X} . We will now show that A follows from B and C . Suppose that every wEDS on G is the topological factor of some EDS in G , it follows from C that there exists a universal EDS on G . Indeed, by our assumption the universal wEDS G\curvearrowright\mathfrak{X} admits an EDS extension G\curvearrowright\mathfrak{U} . As every wEDS (and in particular every EDS) is the topological factor of G\curvearrowright\mathfrak{X} , it follows that G\curvearrowright\mathfrak{U} is universal. In particular, if G is a finitely generated group with decidable word problem and undecidable domino problem, the conclusion from the argument above would contradict B , and thus we obtain A . In Section 2 we introduce the reader to the the necessary background material and set the notation for the rest of the article. In Section 3 we provide the proof of Propositions 3.1 and 3.2 which together prove B . In Section 4 we show the existence of a universal wEDS for any finitely generated group with decidable word problem, and then explain how this result is valid even without the assumption of decidable word problem. Finally, in Section 5 we discuss the missing case of groups with decidable domino problem and give a few pointers towards a characterization of topological factors of EDS. 2 Preliminaries We denote the set of non-negative integers by \mathbb{N} . For a finite set A we write A^{*}=\bigcup_{n\in\mathbb{N}}A^{n} for the set of all words on A . A subset L\subset A^{*} is called a language . We say L is recursively enumerable if there is an algorithm which halts on input w\in A^{*} if and only if w\in L . We say that L is decidable if both L and A^{*}\setminus L are recursively enumerable. A partial map g\colon A^{*}\to B^{*} is computable if there is an algorithm which on input (u,v)\in A^{*}\times B^{*} halts if and only if v=g(u) . Through the canonical binary coding we identify non-negative integers with words in \{0,1\}^{*} and thus extend the notions of recursive enumerable and decidable to sets of non-negative integers. A sequence of recursively enumerable languages (L_{n})_{n\in\mathbb{N}} is uniform if there is an algorithm with in input n\in\mathbb{N} and a word w halts if and only if w\in L_{n} . For a

Read the complete text