On the minimal components of substitution subshifts

Raphaël Henry · 2025

Read On the minimal components of substitution subshifts by Raphaël Henry (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-2501-19326.txt.

Introduction

Raphaël Henry studies the smallest repeating parts inside pattern systems built by substitution rules, in a math paper from 2025. A substitution replaces each symbol with a fixed block, and endless iteration creates rich sequences. Such systems split into minimal parts where the motion returns everywhere, and counting them was open.

Henry gives an exact characterization of those minimal parts for substitutions on a finite alphabet. He also proves a sharp bound on how many such parts can occur. The dynamics inside each part are described as well. Because the results are fully explicit, they yield an algorithm that lists and counts the parts for any given system.

Catalog record

CREATORRaphaël Henry
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE126 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-19326

Browse the full library · About the Tower of Babel

Full text

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

On the minimal components of substitution subshifts Raphaël Henry Abstract In this paper we study substitutions on A ℤ A^{\mathbb{Z}} where A A is a finite alphabet. We precisely characterize the minimal components of substitution subshifts, give an optimal bound for their number and describe their dynamics. The explicitness of these results provides a method to algorithmically compute and count the minimal components of a given substitution subshift. Introduction In symbolic dynamics, substitutions on a finite alphabet A are a rich way to generate infinite words, for a general background see [ 1 ] or the upcoming book [ 2 ] . In particular, substitution subshifts on A^{\mathbb{Z}} have been extensively studied, for a general overview see [ 17 ] and for various computability results see [ 4 ] . A very natural property of subshifts is minimality , meaning that the orbit of every point is dense. Many results were proven in the framework of minimal subshifts, for instance, Damanik and Lenz [ 9 ] proved that a substitution subshift is minimal if and only if it is linearly repetitive. As a simple way to construct minimal subshifts, it is well-known that primitive substitutions generate minimal subshifts (see for example [ 17 ] ), like the Fibonacci substitution \sigma_{F}:0\mapsto 01,1\mapsto 0 . Some non-primitive substitutions also generate minimal subshifts, like the Chacon substitution \sigma_{C}:0\mapsto 0010,1\mapsto 1 , which is even non-growing because the letter 1 is bounded . Acknowledging that it is crucial to distinguish growing and bounded letters, Shimomura [ 19 ] introduced a weaker version of primitivity, called l-primitivity , that means being primitive when removing the bounded letters. Moreover, in a recent interest towards non-minimal substitution subshifts, Maloney and Rust [ 15 ] identified that tameness , a combinatorial property of the substitution, is essential for minimality (this tame vocabulary must not be confused with a property of general dynamical systems related to semigroups, which is not related to our topic). The idea is that a wild (i.e., not tame) substitution will generate an infinite periodic word, which might prevent minimality. In his same article, Shimomura showed that these two properties characterize the minimal substitution subshifts: a substitution subshift X_{\sigma} is minimal if and only if there exists a tame and l-primitive substitution \sigma^{\prime} such that X_{\sigma}=X_{\sigma^{\prime}} . Now that minimal substitution subshifts are well-understood, the next step is to describe the structure of non-minimal substitution subshifts. In this direction, Béal, Perrin and Restivo [ 4 ] showed that any substitution subshift is quasi-minimal , meaning that it has a finite number of subshifts; and Bezuglyi, Kwiatowski and Medynets [ 6 ] showed that any growing substitution subshift on d letters has at most d minimal components. The number of subshifts - or the number of minimal components - can then be seen as a measure of the complexity of the subshift, and this paper is dedicated to the study of the minimal components of substitution subshifts. For growing substitutions, we have encouraging results. The upper bound of their number in [ 6 ] is already important, but it does not describe the minimal components themselves. On that note, one known family of minimal components is given by what Durand called main sub-substitutions : they are primitive substitutions obtained by restricting a suitable power of the original substitution to a suitable subalphabet. Each of them generates a minimal component, and they are thought to generate all the minimal components. To support this idea, the analog of main sub-substitutions was introduced by Cortez and Solomyak [ 8 ] in the framework of tiling substitutions on \mathbb{R}^{d} , and they show that the minimal components are exactly the subshifts generated by these sub-substitutions. In particular, it is remarkable that every minimal component is itself a substitution system. For non-growing substitutions, another family of minimal components arises from wildness. The idea, mentionned earlier, originates from the closely related framework of D0L-systems, where Ehrenfeucht and Rozenberg [ 12 ] begin the investigation of infinite repetitions in their language and Klouda and Starosta [ 14 ] provide effective results. More precisely, if a substitution is wild, then there exists a growing letter that generates a periodic word over bounded letters to its left or to its right. Notably, this was already used by Pansiot [ 16 ] to characterize purely morphic words with factor complexity \Theta(n^{2}) . With the work of Maloney and Rust [ 15 ] and Shimomura [ 19 ] , this transposes to the framework of substitution subshifts where, in particular, each such periodic word provides a minimal component. The main contribution of this paper is the characterization of the minimal components of any substitution subshift. In a first time, we generalize main sub-substitutions to be tame and l-primitive substitutions obtained by restricting a suitable power of the original substitution to a subalphabet. Our definition, however, is more effective than the one of Durand as it relies on finding the suitable subalphabets by constructing a specific oriented graph. Thanks to Shimomura’s result, the main sub-substitutions provide minimal components containing growing letters. We then use the fact that the substitution induces a permutation on the subshifts to show that these components are exactly all the minimal components containing growing letters, which we call tame minimal components . In a second time, we build on results of [ 14 ] and [ 4 ] to define precisely and effectively the periodic words over bounded letters produced by a wild substitution. In parallel, we adapt the notion of 1-blocks introduced in [ 10 ] to obtain a decomposition of the words over bounded letters. This shows that these single periodic orbits are exactly all the minimal components over bounded letters, which we call wild minimal components . To complete the structure of the minimal components, we also describe how the substitution acts on them: we show that the substitution induces a permutation on the minimal components that can be read from the directed graphs introduced in our proof. In our effort to make the characterization as effective as possible, we obtain that the number of minimal components of a given substitution subshift is computable. This is paired with a Python implementation of the computation of minimal components at https://codeberg.org/RaphaelHENRY/MinimalComponents.git . We are also able to bound the number of minimal components as a function of the alphabet size, generalizing the previously known bound to the non-growing case. Finally, as a way to apply our results to various examples, we compute the minimal components for all substitutions on two letters. We conclude this paper by opening the study to what we call irreducible components and briefly discussing potential generalizations of our results to other types of subshifts. 1 Preliminaries 1.1 Notations Words Given a finite alphabet A , A^{*} denotes the set of all words on A , in particular \varepsilon is the empty word and we define A^{+}:=A^{*}\backslash\{\varepsilon\} . For u=a_{0}a_{1}...a_{n-1}\in A^{*} , we write \lvert u\rvert:=n the length of u . To simplify some expressions, we will use the following notation: if (u_{i})_{0\leq i\leq n-1}\in(A^{*})^{n} , we write the concatenation from left to right as \displaystyle\displaystyle\bigsqcup_{i=0}^{n-1}u_{i}:=u_{0}u_{1}...u_{n-2}u_{n-1}\penalty\ \penalty\ \penalty\ \penalty\ \penalty\ \penalty\ \penalty\ \penalty\ \displaystyle\textrm{with the convention that }\displaystyle\bigsqcup_{i=0}^{-1}u_{i}:=\varepsilon. (1) If

Read the complete text