V. Berthé, H. Goulet-Ouellet. Obstructions to return preservation for episturmian morphisms. Theory of Computing Systems (2024). arxiv:2404.08072
This paper studies obstructions to preservation of return sets by episturmian morphisms. We show, by way of an explicit construction, that infinitely many obstructions exist. This generalizes and improves an earlier result about Sturmian morphisms.
J. Almeida, H. Goulet-Ouellet. What makes a Stone topological algebra profinite. Algebra Universalis, vol. 84, no. 1 (2023). arXiv:2109.07286
This paper is a contribution to understanding what properties should a topological algebra on a Stone space satisfy to be profinite. We reformulate and simplify proofs for some known properties using syntactic congruences. We also clarify the role of various alternative ways of describing syntactic congruences, namely by finite sets of terms and by compact sets of continuous self mappings of the algebra.
H. Goulet-Ouellet. Suffix-connected languages. Theoretical Computer Science, vol 923, pp. 126-143 (2022). arXiv:2106.00452
Inspired by a series of papers initiated in 2015 by Berthé et al., we introduce a new condition called suffix-connectedness. We show that the groups generated by the return sets of a uniformly recurrent suffix-connected language lie in a single conjugacy class of subgroups of the free group. Moreover, the rank of the subgroups in this conjugacy class only depends on the number of connected components in the extension graph of the empty word. We also show how to explicitly compute a representative of this conjugacy class using the first order Rauzy graph. Finally, we provide an example of suffix-connected, uniformly recurrent language that contains infinitely many disconnected words.
H. Goulet-Ouellet. Pronilpotent quotients associated with primitive substitutions. Journal of Algebra, vol. 606, pp. 1101-1123 (2022). arXiv:2204.05706
We describe the pronilpotent quotients of a class of projective profinite groups, that we call ω-presented groups, defined using a special type of presentations. The pronilpotent quotients of an ω-presented group are completely determined by a single polynomial, closely related with the characteristic polynomial of a matrix. We deduce that ω-presented groups are either perfect or admit the p-adic integers as quotients for cofinitely many primes. We also find necessary conditions for absolute and relative freeness of ω-presented groups. Our main motivation comes from semigroup theory: the maximal subgroups of free profinite monoids corresponding to primitive substitutions are ω-presented (a theorem due to Almeida and Costa). We are able to show that the composition matrix of a primitive substitution carries partial information on the pronilpotent quotients of the corresponding maximal subgroup. We apply this to deduce that the maximal subgroups corresponding to primitive aperiodic substitutions of constant length are not absolutely free.
H. Goulet-Ouellet. Freeness of Schützenberger groups of primitive substitutions. International Journal of Algebra and Computations, vol. 32, no. 6, pp. 1101–1123 (2022). arXiv:2109.11957
Our main goal is to study the freeness of Schützenberger groups defined by primitive substitutions. Our findings include a simple freeness test for these groups, which is applied to exhibit a primitive invertible substitution with corresponding non-free Schützenberger group. This constitutes a counterexample to a result of Almeida dating back to 2005. We also give some early results concerning relative freeness of Schützenberger groups, a question which remains largely unexplored.
Conference proceedings
V. Berthé and H. Goulet-Ouellet. On substitutions preserving their return sets. In: Combinatorics on words, Words 2023. Ed. by A. Frid and R. Mercas. Lecture notes in Computer Science, vol. 13899 (2023). hal-04311379
We consider the question of whether or not a given primitive substitution preserves its sets of return words—or return sets for short. More precisely, we study the property asking that the image of the return set to a word equals the return set to the image of that word. We show that, for bifix encodings (where images of letters form a bifix code), this property holds for all but finitely many words. On the other hand, we also show that every conjugacy class of Sturmian substitutions contains a member for which the property fails infinitely often. Various applications and examples of these results are presented, including a description of the subgroups generated by the return sets in the shift of the Thue–Morse substitution. Up to conjugacy, these subgroups can be sorted into strictly decreasing chains of isomorphic subgroups weaving together a simple pattern. This is in stark contrast with the Sturmian case, and more generally with the dendric case (including in particular the Arnoux–Rauzy case), where it is known that all return sets generate the free group over the underlying alphabet.
Preprints
F. Gheeraert, H. Goulet-Ouellet, J. Leroy, P. Stas. Stability properties for subgroups generated by return words (2024). arxiv:2410.12534
Return words are a classical tool for studying shift spaces with low factor complexity. In recent years, their projection inside groups have attracted some attention, for instance in the context of dendric shift spaces, of generation of pseudorandom numbers (through the welldoc property), and of profinite invariants of shift spaces. Aiming at unifying disparate works, we introduce a notion of stability for subgroups generated by return words. Within this framework, we revisit several existing results and generalize some of them. We also study general aspects of stability, such as decidability or closure under certain operations.
F. Gheeraert, H. Goulet-Ouellet, J. Leroy, P. Stas. Algebraic characterization of dendricity (2024). arxiv:2406.15075
Dendric shift spaces simultaneously generalize codings of regular interval exchanges and episturmian shift spaces, themselves both generalizations of Sturmian words. One of the key properties enforced by dendricity is the Return Theorem. In this paper, we prove its converse, providing the following natural algebraic perspective on dendricity: A minimal shift space is dendric if and only if every set of return words is a basis of the free group over the alphabet.
V. Berthé, H. Goulet-Ouellet, C.-F. Nyberg Brodda, D. Perrin and K. Petersen. Density of group languages in shift spaces (2024). arxiv:2403.17892
We study the density of group languages (i.e. rational languages recognized by morphisms onto finite groups) inside shift spaces. The density of a rational language can be understood as the frequency of some "pattern" in the shift space, for example a pattern like "words with an even number of a given letter." In this paper, we handle density of group languages via ergodicity of skew products between the shift space and the recognizing group. We consider both the cases of shifts of finite type (with a suitable notion of irreducibility), and of minimal shifts. In the latter case, our main result is a closed formula for the density which holds whenever the skew product has minimal closed invariant subsets which are ergodic under the product of the original measure and the uniform probability measure on the group. The formula is derived in part from a characterization of minimal closed invariant subsets for skew products relying on notions of cocycles and coboundaries. In the case where the whole skew product itself is ergodic under the product measure, then the density is completely determined by the cardinality of the image of the language inside the recognizing group. We provide sufficient conditions for the skew product to have minimal closed invariant subsets that are ergodic under the product measure. Finally, we investigate the link between minimal closed invariant subsets, return words and bifix codes.
Thesis
H. Goulet-Ouellet. Schützenberger groups of minimal shift spaces. University of Coimbra, PhD thesis (2022).
This thesis aims to shed some light on the structure of maximal subgroups of free profinite monoids corresponding to minimal shift spaces. These groups, which came to be known as Schützenberger groups in the literature, were first studied by Almeida in the early 2000s. They provide a fruitful connection between semigroup theory and symbolic dynamics. But despite many significant advances taking place in the last two decades, our understanding of these groups remains sparse. This thesis proposes a number of contributions on different aspects of this topic, organized in three parts.
The first part is concerned with the freeness question: when are these groups free, be it in the category of profinite groups, or relative to some pseudovariety of finite groups? This part of the thesis focuses in particular on the maximal subgroups corresponding to primitive substitutions. One of the main results is a criterion for absolute freeness which uses a special kind of profinite presentations introduced by Almeida and Costa, which we call ω-presentations. The criterion is used to exhibit a primitive invertible substitution with a non-free Schützenberger group, disproving a result proposed by Almeida. Some early results are also obtained on the topic of relative freeness.
The second part of the thesis examines the pronilpotent quotients of Schützenberger groups of primitive substitutions. The main result is a description of the maximal pronilpotent quotients of ω-presented groups, of which Schützenberger groups of primitive substitutions are special cases. We show that all the information about the pronilpotent quotients of a given ω-presented group can be extracted from the characteristic polynomial of a certain matrix. This can be used, for instance, to show that ω-presented groups are never pro-p groups (partially answering a question of Zalesskii), and that they are perfect only under strict conditions which exclude Schützenberger groups of primitive substitutions. These results also lead to a number of necessary conditions for absolute and relative freeness of ω-presented groups. We deduce that Schützenberger groups of primitive aperiodic substitutions of constant length are never absolutely free.
The last part of the thesis is devoted to a study of the subgroups generated by return words in minimal shift spaces. In 2016, Almeida and Costa showed that the collective behaviour of these subgroups can be used to gather information about the Schützenberger group. Their results were motivated in part by a series of papers initiated in 2015 by Berthé et al., which developed a number of ideas centred around the notion of extension graphs. Under certain assumptions, Berthé et al.'s results allowed for a complete understanding of the subgroups generated by return words. Our main contribution on this topic is a new condition called suffix-connectedness, which allows to generalize some of these results. Various applications of suffix-connectedness to the study of Schützenberger groups are also highlighted.