Invertible substitutions on a three-letter alphabet

Tan, Bo; Wen, Zhi-Xiong; Zhang, Yiping

Comptes Rendus. Mathématique, Tome 336 (2003) no. 2, pp. 111-116.

Nous étudions la structure des substitutions inversibles sur un alphabet à trois lettres. Nous prouvons qu'il existe un ensemble fini $𝕊$ de substitutions inversibles tel que toute substitution inversible puisse être écrite comme I_w∘σ₁∘σ₂∘⋯∘σ_k, où I_w est l'automorphisme intérieur associé à w et où ${\sigma }_j\in 𝕊$ pour 1⩽j⩽k. Comme conséquence, M est la matrice d'une substitution inversible si et seulement si elle est un produit fini de matrices élémentaires non-négatives.

We study the structure of invertible substitutions on a three-letter alphabet. We show that there exists a finite set $𝕊$ of invertible substitutions such that any invertible substitution can be written as I_w∘σ₁∘σ₂∘⋯∘σ_k, where I_w is the inner automorphism associated with w, and ${\sigma }_j\in 𝕊$ for 1⩽j⩽k. As a consequence, M is the matrix of an invertible substitution if and only if it is a finite product of non-negative elementary matrices.

[1] P. Arnoux et al., Introduction to finite automata and substitution dynamical systems, in: Lecture Notes in Math., Springer-Verlag, to appear

[2] Arnoux, P.; Ito, S. Pisot substitutions and Rauzy fractals, Journées Montoises d'Informatique Théorique (Marne-la-Vallée, 2000) (Bull. Belgian Math. Soc. Simon Stevin), Volume 8 (2001) no. 2, pp. 181-207

[3] Berstel, J. Recent results in Sturmian words, Developments in Language Theory, II (Magdeburg, 1995), World Sci. Publishing, River Edge, NJ, 1996, pp. 13-24

[4] Cobham, A. Uniform tag sequences, Math. System Theory, Volume 6 (1972), pp. 164-192

[5] Ei, H.; Ito, S. Decomposition theorem for invertible substitution, Osaka J. Math., Volume 34 (1998), pp. 821-834

[6] M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, 2002, to appear. Available at http://www-igm.univ-mlv.fr/~berstel/Lothaire

[7] Lyndon, R.C.; Schupp, P.E. Combinatorial Group Theory, Spring-Verlag, Berlin, 1977

[8] Magnus, W.; Karrass, A.; Solitar, D. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations, Dover, 1976

[9] Nielsen, J. Die Isomorphismen der freien Gruppen, Math. Ann., Volume 91 (1924), pp. 169-209

[10] Peyrière, J.; Wen, Z.-X.; Wen, Z.-Y. Polynomês associées aux endomorphismes de groupes libres, Enseign. Math., Volume 39 (1993), pp. 153-175

[11] Séébold, P. Fibonacci morphisms and Sturmian words, Theoret. Comput. Sci., Volume 88 (1991), pp. 365-384

[12] Wen, Z.-X.; Wen, Z.-Y. Local isomorphism of the invertible substitutions, C. R. Acad. Sci. Paris Sér. I Math., Volume 318 (1994), pp. 299-304

[13] Wen, Z.-X.; Wen, Z.-Y. Some properties of the singular words of the Fibonacci word, European J. Combin., Volume 15 (1994), pp. 587-598

[14] Wen, Z.-X.; Wen, Z.-Y.; Wu, J. Invertible substitutions and local isomorphisms, C. R. Acad. Sci. Paris Sér. I Math., Volume 334 (2002), pp. 629-634

[15] Wen, Z.X.; Zhang, Y. Some remarks on invertible substitutions on three letter alphabet, Chinese Sci. Bull., Volume 44 (1999) no. 19, pp. 1755-1760