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.
Actes de conférences
V. Berthé and H. Goulet-Ouellet. On substitutions preserving their return sets. Dans: Combinatorics on words, Words 2023. Éd. par 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.
Prépublications
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.
Thèse
H. Goulet-Ouellet. Schützenberger groups of minimal shift spaces. University of Coimbra, PhD thesis (2022).
Cette thèse vise à faire la lumière sur la structure des sous-groupes maximaux des monoïdes profinis libres qui correspondent aux systèmes dynamiques symboliques minimaux. Ces groupes, maintenant appelés groupes de Schützenberger dans la littérature, furent d'abord étudiés par Almeida au début des années 2000. Ils révèlent une fructueuse connection entre la théorie des semi-groupes et la dynamique symbolique. Mais malgré plusieurs progrès importants au cours des deux dernières décennies, notre compréhension de ces groupes demeure incomplète. Cette thèse propose une série de contributions sur différents aspects du sujet, organisées en trois parties.
La première partie porte sur la question de la liberté: sous quelles conditions ces groupes sont-ils libres, soit dans la catégorie des groupes profinis, ou relativement à une certaine pseudo-variété de groupes finis? On s'y concentre en particulier sur les sous-groupes maximaux correspondant aux substitutions primitives. L'un des principaux résultats est un critère pour la liberté absolue utilisant un type de présentations profinies introduit par Almeida et Costa, que l'on appelle ω-présentations. Ce critère permet de mettre en évidence un exemple de substitution primitive inversible dont le groupe de Schützenberger est non-libre, réfutant un résultat proposé par Almeida. Quelques résultats préliminaires sur la liberté relative sont aussi présentés.
La deuxième partie de la thèse examine les quotients pronilpotents des groupes de Schützenberger des substitutions primitives. Le résultat principal est une description des quotients pronilpotents maximaux des groupes ω-présentés, dont les groupes de Schützenberger des substitutions primitives font partie. On y démontre que toute l'information sur les quotients pronilpotents d'un groupe ω-présenté peut être prélevée à même le polynôme caractéristique d'une certaine matrice. On peut utiliser ceci pour démontrer, par exemple, que les groupes ω-présentés ne sont jamais pro-p (ce qui répond en partie à une question de Zalesskii), et qu'ils sont parfaits seulement sous des conditions strictes qui excluent les groupes de Schützenberger des substitutions primitives. Ces résultats mènent aussi à un certain nombre de conditions nécessaires à la liberté, absolue et relative, des groupes ω-présentés. On en déduit que les groupes de Schützenberger des substitutions primitives apériodiques de longueur uniforme ne sont jamais absolument libres.
La dernière partie de la thèse est dédiée à l'étude des sous-groupes engendrés par les mots de retour dans les systèmes dynamiques symboliques minimaux. En 2016, Almeida et Costa démontrent que le comportement collectif de ces sous-groupes permet de mieux comprendre le groupe de Schützenberger. Leurs résultats sont motivés en partie par une série d'articles publiés à partir de 2015 par Berthé et al., développant des idées centrées autour de la notion de graphes d'extensions. Sous certaines conditions, les résultats de Berthé et al.~permettent d'obtenir une connaissance complète des sous-groupes engendrés par les mots de retour. Notre principale contribution sur ce sujet est une nouvelle condition, la connectivité par suffixes, permettant de généraliser certains de ces résultats. Plusieurs applications de la connectivité par suffixes pour l'étude des groupes de Schützenberger sont aussi soulignées.