×

Presentations of Schützenberger groups of minimal subshifts. (English) Zbl 1293.20054

Profinite semigroups may be described shortly as projective limits of finite semigroups. A class of finite semigroups is called a pseudovariety if it closed under taking homomorphic images, subsemigroups and finite direct products. For a pseudovariety \(\mathbf V\), a profinite semigroup \(S\) is ‘pro-\(\mathbf V\)’ if it is a projective limit of members of \(\mathbf V\).
Recall construction of free objects for a pseudovariety \(\mathbf V\). For a generating set \(A\), let \(\mathbf V_0\) be a set containing a representative from each isomorphism class of \(A\)-generated members of \(\mathbf V\). The set \(\mathbf V_0\) determines a projective system by taking the unique connecting homomorphisms with respect to the choice of generators. The projective limit of this system is denoted \(\overline\Omega_A\mathbf V\) and is called the ‘free pro-\(\mathbf V\) semigroup on \(A\)’. A profinite semigroup is said to be ‘relatively free’ if it is of the form \(\overline\Omega_A\mathbf V\) for some set \(A\) and some pseudovariety \(\mathbf V\). If \(\mathbf V\) is the pseudovariety of all finite semigroups the free pro-\(\mathbf V\) semigroups are called ‘free profinite semigroups’.
Let \(A\) be a finite alphabet. The additive group \(\mathbb Z\) of integers acts naturally on the set \(A^{\mathbb Z}\) of functions \(f\colon\mathbb Z\to A\) by translating the argument: \((n\cdot f)(m)=f(m+n)\). The elements of \(A^{\mathbb Z}\) may be viewed as bi-infinite words on the alphabet \(A\). Recall that a symbolic dynamical system (or subshift) over \(A\) is a non-empty subset \(X\subseteq A^{\mathbb Z}\) which is topologically closed and stable under the natural action of \(\mathbb Z\) in the sense that it is a union of orbits.
In two previous works [Fundam. Prikl. Mat. 11, No. 3, 13-48 (2005); translation in J. Math. Sci., New York 144, No. 2, 3881-3903 (2007; Zbl 1110.20022); NATO Science Series II: Mathematics, Physics and Chemistry 207, 1-45 (2005; Zbl 1109.20050)], the first author established a natural bijection between minimal subshifts and maximal regular \(\mathcal J\)-classes of free profinite semigroups. In the reviewed paper, the Schützenberger groups of such \(\mathcal J\)-classes are investigated, in particular in respect to a conjecture proposed by the first author concerning their profinite presentation. The conjecture is established for all non-periodic minimal subshifts associated with substitutions. It entails that it is decidable whether a finite group is a quotient of such a profinite group. As a further application, the Schützenberger group of the \(\mathcal J\)-class corresponding to the Prouhet-Thue-Morse subshift is shown to admit a somewhat simpler presentation, from which it follows that it has rank three, and that it is non-free relative to any pseudovariety of groups.

MSC:

20M05 Free semigroups, generators and relations, word problems
20M07 Varieties and pseudovarieties of semigroups
37B10 Symbolic dynamics
20E18 Limits, profinite groups
22A15 Structure of topological semigroups

Software:

GAP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Almeida, Finite Semigroups and Universal Algebra, World Scientific, Singapore, 1995, English translation. · Zbl 0757.08001
[2] J. Almeida, Dynamics of implicit operations and tameness of pseudovarieties of groups, Transactions of the American Mathematical Society 354 (2002), 387–411. · Zbl 0988.20014 · doi:10.1090/S0002-9947-01-02857-4
[3] J. Almeida, Profinite groups associated with weakly primitive substitutions, Fundamentalnaya i Prikladnaya Matematika (Fundamental and Applied Mathematics) 11 (2005), 13–48, In Russian. English version in Journal of Mathematical Sciences 144 (2007), 3881–3903. · Zbl 1110.20022
[4] J. Almeida, Profinite semigroups and applications, in Structural Theory of Automata, Semigroups, and Universal Algebra (New York) (V. B. Kudryavtsev and I. G. Rosenberg, eds.), NATO Science Series II: Mathematics, Physics and Chemistry, Vol. 207, Springer, Berlin, 2005, Proceedings of the NATO Advanced Study Institute on Structural Theory of Automata, Semigroups and Universal Algebra, Montréal, Québec, Canada, 7–18 July, 2003, pp. 1–45.
[5] J. Almeida and A. Costa, Infinite-vertex free profinite semigroupoids and symbolic dynamics, Journal of Pure and Applied Algebra 213 (2009), 605–631. · Zbl 1179.20050 · doi:10.1016/j.jpaa.2008.08.009
[6] J. Almeida and M. V. Volkov, Subword complexity of profinite words and subgroups of free profinite semigroups, International Journal of Algebra and Computation 16 (2006), 221–258. · Zbl 1186.20040 · doi:10.1142/S0218196706002883
[7] L. Balková, E. Pelantová and W. Steiner, Sequences with constant number of return words, Monatshefte für Mathematik 155 (2008), 251–263. · Zbl 1185.68503 · doi:10.1007/s00605-008-0001-2
[8] A. Costa, Conjugacy invariants of subshifts: an approach from profinite semigroup theory, International Journal of Algebra and Computation 16 (2006), 629–655. · Zbl 1121.37013 · doi:10.1142/S0218196706003232
[9] A. Costa and B. Steinberg, Profinite groups associated to sofic shifts are free, Proceedings of the London Mathematical Society 102 (2011), 341–369. · Zbl 1257.20054 · doi:10.1112/plms/pdq024
[10] F. Durand, A characterization of substitutive sequences using return words, Discrete Mathematics 179 (1998), 89–101. · Zbl 0895.68087 · doi:10.1016/S0012-365X(97)00029-0
[11] F. Durand, Linearly recurrent subshifts have a finite number of non-periodic subshift factors, Ergodic Theory and Dynamical Systems 20 (2000), 1061–1078. · Zbl 0965.37013 · doi:10.1017/S0143385700000584
[12] F. Durand, B. Host and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups, Ergodic Theory and Dynamical Systems 19 (1999), 953–993. · Zbl 1044.46543 · doi:10.1017/S0143385799133947
[13] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, Lecture Notes in Mathematicsrlin, 2002. · Zbl 1014.11015
[14] The GAP Group, GAP-Groups, Algorithms, and Programming, Version 4.4, 2006 ( http://www.gap-system.org ).
[15] K. W. Gruenberg, Projective profinite groups, Journal of the London Mathematical Society 42 (1967), 155–165. · Zbl 0178.02703 · doi:10.1112/jlms/s1-42.1.155
[16] T. Harju and M. Linna, On the periodicity of morphisms on free monoids, RAIRO Informatique Théorique et Applications 20 (1986), 47–54. · Zbl 0608.68065
[17] R. P. Hunter, Some remarks on subgroups defined by the Bohr compactification, Semigroup Forum 26 (1983), 125–137. · Zbl 0503.22001 · doi:10.1007/BF02572826
[18] D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1996. · Zbl 1106.37301
[19] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, 2002. · Zbl 1001.68093
[20] A. Lubotzky, Pro-finite presentations, Journal of Algebra 242 (2001), 672–690. · Zbl 0985.20017 · doi:10.1006/jabr.2001.8805
[21] S. Margolis, M. Sapir and P. Weil, Irreducibility of certain pseudovarieties, Communications in Algebra 26 (1998), 779–792. · Zbl 0904.20042 · doi:10.1080/00927879808826163
[22] B. Mossé, Puissances de mots et reconnaissabilité des points fixes d’une substitution, Theoretical Computer Science 99 (1992), 327–334. · Zbl 0763.68049 · doi:10.1016/0304-3975(92)90357-L
[23] B. Mossé, Reconnaissabilité des substitutions et complexité des suites automatiques, Bulletin de la Société Mathématique de France 124 (1996), 329–346.
[24] J.-J. Pansiot, Decidability of periodicity for infinite words, RAIRO Informatique Théorique et Applications 20 (1986), 43–46. · Zbl 0617.68063
[25] J. Rhodes and B. Steinberg, Closed subgroups of free profinite monoids are projective profinite groups, The Bulletin of the London Mathematical Society 40 (2008), 375–383. · Zbl 1153.20029 · doi:10.1112/blms/bdn017
[26] J. Rhodes and B. Steinberg, The q-theory of Finite Semigroups, Springer Monographs in Mathematics, Springer, Berlin, 2009. · Zbl 1186.20043
[27] L. Ribes and P. A. Zalesskiĭ, Profinite groups, Ergebenisse der Mathematik und ihrer Grenzgebiete, Vol. 40, Springer, Berlin, 2000. · Zbl 0949.20017
[28] B. Steinberg, Maximal subgroups of the minimal ideal of a free profinite monoid are free, Israel Journal of Mathematics 176 (2010), 139–155. · Zbl 1220.20045 · doi:10.1007/s11856-010-0023-z
[29] J. Wilson, Profinite Groups, London Mathematical Society Monographs, New Series, Vol. 19, Clarendon, Oxford, 1998. · Zbl 0909.20001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.