Permutation properties and the Fibonacci semigroup. (English) Zbl 0663.20063

A semigroup S is said to have the weak permutation property is there exists \(n\geq 2\) such that for any elements \(x_ 1,...x_ n\in S\) there exist two permutations \(\sigma\), \(\tau\) of the set \(\{\) 1,...,n\(\}\) such that \(\sigma\neq \tau\) and \(x_{\sigma (1)}...x_{\sigma (n)}=x_{\tau (1)}...x_{\tau (n)}\). Groups of this type were described by R. D. Blyth [J. Algebra 116, 506-521 (1988; Zbl 0647.20033)], who also showed that for groups the above property is equivalent to the permutation property: there exists \(n\geq 2\) such that for any \(x_ 1,...,x_ n\in S\) there is a permutation \(\sigma\neq 1\) such that \(x_{\sigma (1)}...x_{\sigma (n)}=x_ 1...x_ n\). An example of a semigroup S with the weak permutation property which is finitely generated, periodic but infinite is given. (It is the Rees factor of the free semigroup \(<a,b>\) by the ideal consisting of all non-factors of the infinite Fibonacci word in a,b.) This is in contrast to the result of A. Restivo and C. Reutenauer [J. Algebra 89, 102-104 (1984; Zbl 0545.20051)] asserting that every periodic semigroup with the permutation property must be locally finite.
Reviewer: J.Okniński


20M05 Free semigroups, generators and relations, word problems
20M10 General structure theory for semigroups
Full Text: DOI EuDML


[1] Berstel, J., Mots de Fibonacci, Seminaire d’Informatique Théorique, L.I.T.P. Université Paris VI et VII, Année 1980/81, 57–78.
[2] Blyth, R. D., Rewriting products of groups elements, PH.D. Thesis (1987) University of Illinois at Urbana-Champain.
[3] Curzio, M., P. Longobardi, M. Maj, Su di un problema combinatorio in teoria dei gruppi, Atti Acc. Lincei Rend. fis. VIII, 74 (1983) 136–142. · Zbl 0528.20031
[4] Curzio, M., P. Longobardi, M. Maj, D.J.S. Robinson, A permutational property of groups, Arch. Math. 44 (1985) 385–389. · Zbl 0544.20036
[5] Karhumaki, J., On cube-free {\(\omega\)}-words generated by binary morphism, Discr. Appl. Math. 5 (1983) 279–297. · Zbl 0505.03022
[6] Lallement, G., Semigroups and combinatorial applications, John Wiley (1979). · Zbl 0421.20025
[7] Lothaire, M., Combinatorics on words, Addison Wesley, Reading (1983) · Zbl 0514.20045
[8] Pirillo, G., On permutation properties for finitely generated semigroups, in ”Combinatorics” (1986) Proc.s Conference at Passo della Mendola (Italy). · Zbl 0654.20068
[9] Restivo, A., C. Reutenauer, On the Burnside problem for semigroups, Journal of Algebra, 89 (1984) 102–104. · Zbl 0545.20051
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.