Invertible substitutions on a three-letter alphabet.
A substitution is defined as a non-erasing morphism of the free monoid; a substitution is called invertible if it extends to an automorphism of the free group. The structure of the monoid of invertible substitutions over a two-letter alphabet is perfectly known [\textit{Z. Wen} and \textit{Z. Wen}, C. R. Acad. Sci., Paris, Sér. I 318, 299--304 (1994; Zbl 0812.11018)]; moreover it coincides with the monoid of Sturmian substitutions, that is, the substitutions which fix Sturmian words [\textit{F. Mignosi} and \textit{P Séébold}, J. Théor. Nombres Bordx. 5, 221--233 (1993; Zbl 0797.11029)]. The aim of this note is to extend this result to three-letter alphabets. The situation is a priori more involved since the monoid of invertible substitutions over a three-letter alphabet is known to be of infinite type [\textit{Z. Wen} and \textit{Y. Zhang}, Chin. Sci. Bull. 44, 1755--1760 (1999; Zbl 1040.20504)]. Nevertheless it is proved in the note under review that there exists a finite set S of elementary substitutions such that any invertible substitution can be decomposed as a finite composition of these susbtitutions, up to an inner automorphism; more precisely, if \(\sigma\) is an invertible substitution over a three-letter alphabet, then there exist \(W\), \(k\) such that \(\sigma= I_W\circ\sigma_i\circ \cdots\circ \sigma_k\), where for all \(i\), \(\sigma_i\in S\) and \(I_W\) is the morphism of the free group defined by \(I_W: U\mapsto WUW^{-1}\) (it is not a substitution in general). This immediately implies that an integer square matrix of size 3 with non-negative entries is the incidence matrix of an invertible substitution if and only if it is a finite product of nonnegative elementary matrices.
scientific article; zbMATH DE number 1907779