Evènement pour le groupe Graphes et Logique

Date 2012-03-27  11:00-12:00
TitreSchützenberger groups of primitive substitutions are decidable 
Résumé(joint work with Alfredo Costa) It is well known that the words that appear as factors in the iteration on the letters of a primitive endomorphism (substitution) f of the free semigroup on a finite alphabet A is the language of blocks of a minimal symbolic dynamical system (subshift) X_f, consisting of biinfinite words over the alphabet A whose blocks are those factors. I proved in 2005 that, associating to a minimal subshift X over the alphabet A the closure J(X) of its language of blocks in the profinite semigroup freely generated by A, one obtains a bijection between minimal subshifts and J-maximal regular J-classes. My co-author showed in his thesis that, viewed as an abstract group G(X), the maximal subgroups of J(X) constitute a conjugacy invariant. I also showed that, if f induces an automorphism of the free group on A, then G(X_f) is a free profinite group, while there are examples for which G(X_f), which is always finitely generated, is not a free profinite group. Rhodes and Steinberg proved that the closed subgroups of a free profinite semigroup are projective as profinite groups. Hence, as observed by Lubotzky, if finitely generated, such groups admit finite presentations, as profinite groups, in which the relations simply state that each generator is a fixed point of a retraction of the free profinite group. I conjectured in 2005 that, under special conditions on the primitive substitution f, the group G(X_f) admits such a presentation in which the retraction is obtained as a (profinite) idempotent iterate of a positive finite continuous endomorphism f' of the free profinite group, where f' can be effectively computed from f. The interest in such presentations stems from the fact that the relations can be effectively checked in a given finite group, so that the group with such a retract presentation has decidable finite quotients. It turns out that the conjecture holds for every primitive substitution f. It is therefore decidable whether a finite group is a quotient of G(X_f). The proof of the conjecture in such a wide setting depends on a synchronization result of Mossé for (biinfinite) fixed points of primitive substitutions. As an application, we show that the group associated with the classical Prouhet-Thue-Morse substitution (a -> ab, b -> ba) is not free. 
Lieusalle 76 
OrateurJorge Almeida 
UrlUniversity of Porto 

Aucun document lié à cet événement.

Retour à l'index