Avoid common mistakes on your manuscript.
1 Correction to: Semigroup Forum https://doi.org/10.1007/s00233-021-10216-8
Not long after the publication of my survey article [16], I received some comments from Yu. V. Matiyasevich on its contents, which raised and corrected several issues made regarding the chronology and details of the history of the undecidability of few-relation monoids, which warrant the present corrigendum. A better account is given in the excellent article [15] by Matiyasevich (missing from the reference list in [16]). I detail and correct the issues below. I express my sincere gratitude to Yu. V. Matiyasevich for informing me of these chronological errors. Following this, I give a list of other errata and omissions.
First, the following is stated on p. 303:
Tseitin’s example [of a 7-relation monoid with undecidable word problem] remains the shortest, with respect to total length of the defining relations, known example.
This is incorrect; one can (see [13, 21, p. 1264]), remove one letter from one of Tseitin’s relations and retain undecidability. Hence, the shortest example, called \(\mathfrak {E}_0\), is due to Matiyasevich, where the sum of the lengths of the seven defining relations is 32.
Second, the following is stated just below on p. 303 and footnote 3 therein:
In 1966, G. S. Makanin provided an example showing that five (short!) defining relations suffice [for undecidability]; Yu. V. Matiyasevich provided an example with the same number of relations (one of which is rather long) in 1967.
[...]
Adian recalls that at the end of a 1966 seminar in Moscow given by Makanin regarding his five-relation example, A. A. Markov conjectured that the number of relations could be reduced to three, and suggested Makanin write to Matiyasevich. Apparently, Matiyasevich had already found such an example, as it was published the next year.
Here emphasis is added for clarity. These statements, both of which have their origin in [3], are inaccurate for two reasons. First: none of the relations in Matiyasevich’s five-relation monoid are long. This inaccurate claim was also made in [3, p. 559], which I was reading at the time of writing the survey; I should have consulted Matiyasevich’s original article in more detail before proliferating this error.Footnote 1 The second reason the above quote is inaccurate is that the chronology is incorrect. According to Matiyasevich, the chronology was rather as follows: first, Matiyasevich constructed a system with five relations. Soon thereafter, N. M. Nagorny (a student of Markov’s) came to Leningrad from Moscow, and said that in Moscow, Makanin had built an undecidable system with six relations. Nagorny asked Matiyasevich’s permission to pass on the five-relation system to Moscow, which he received. According to Matiyasevich, it was in this way that Makanin learned of the five-relation system, and inspired by this subsequently improved his own system to five relations.Footnote 2 However, by then, the Doklady paper [12] had already been accepted, and the five-relation example was added in a footnote in proof, in which Matiyasevich’s example is acknowledged.
In line with the above chronological issue, footnote 3 on p. 303 of my survey is dubious, chronologically speaking; it seems very likely that A. A. Markov was aware of Matiyasevich’s example by then. Indeed, as Matiyasevich recalls, Markov said (words to the effect of): “Matiyasevich proved the problem is undecidable for three relations; for one relation, the problem is decidable; and the word problem for two-relation monoids will remain open for a hundred years”.Footnote 3 My own view of the matter is not very different.
In addition to the above chronological corrigendum and addendum, I wish to point out the following errata and omissions in the article:
-
(1)
On p. 334, it is stated that Squier & Wrathall gave an elementary proof of the Freiheitssatz to one-relation monoids. This is correct, but Shneerson [20, 20] (not present in the original reference list) had already given an elementary proof some ten years earlier, using no group-theoretic methods. Indeed, a significant generalisation, called the generalised Freiheitssatz in [10], is proved therein, namely: every monoid given by a presentation with \(n+k\) generators and k defining relations contains a free submonoid freely generated by n of the generators. Taking \(k=1\), one obtains the Freiheitssatz for one-relation monoids (see also [8]).
-
(2)
On p. 335, it is stated “Adian classified all special one-relation monoids satisfying some non-trivial identity.” This is incorrect. What is correct is that Adian [1] classified all (not necessarily finitely presented) special monoids satisfying some non-trivial identity, and which are not groups. Thus, there remained work to classify the special one-relation monoids satisfying some non-trivial identity. Shneerson [18], using results by Magnus [11], showed that there is only one non-cyclic group which can be defined as a one-relation special monoid; this is the Klein bottle group \({\text {BS}}(1,-1) \cong \text {Mon} \langle a,b \mid ab^2a=1 \rangle \), which is virtually free abelian, and satisfies the identity \(x^2y^2 = y^2x^2\). This completes the classification of special one-relation monoids satisfying some non-trivial identity.
-
(3)
On p. 335, it is stated that Shneerson classified the one-relation monoids satisfying some non-trivial identities, and that Vazhenin later used this classification to classify the one-relation monoids with decidable first-order theory; the list of the monoids in this latter class is then given. The chronology in the survey is, however, unclear and somewhat misleading, and should be corrected as follows: Shneerson classified the (infinite) one-relation monoids satisfying some non-trivial identity in 1972 [18, 19]. This classification is the same as the monoids appearing on line 8, p. 335 of the survey, together with the special one-relation monoids with two generators a, b and one of the relations \(ab=1\), \(aba=1\), \(b=1\), or \(ab^2a=1\). Via personal communication in 1973, Shneerson provided the articles [18, 19] to Yu. Vazhenin. In Vazhenin’s paper [21] from 10 years later, classifying the one-relation monoids with decidable first-order theory, the article [19] is cited, and references to methods and theorems from the same are made, but it is not mentioned that the resulting classification is the same as in [19].
I express my sincere gratitude to L. M. Shneerson for informing me of (1), (2), and (3).
-
(3)
On p. 308, during the discussion of cycle-freeness, cancellativity, and group-embeddability, two important references are omitted. First, Bush [6] gave an example of a group-embeddable monoid which is not cycle-free. Second, Rumyantsev [17] (a diploma student of Shneerson’s) gave an example of a two-generator two-relator monoid which is cancellative but not group-embeddable, namely:
$$\begin{aligned} \text {Mon} \langle a,b \mid a^2b^2 = b^2 a^2, a^2 ba b^2 = b^2 aba^2 \rangle . \end{aligned}$$This shows that the one-relation case is indeed very special.
-
(4)
While it is claimed on p. 308 of the survey that Remmers extended Adian’s theorem on the embeddability of cycle-free semigroups in groups beyond the finitely presented case, in fact Adian notes in a footnote on [1, p. 45] that his proof does not use finite presentability anywhere, so this theorem was proved already in 1966.
-
(5)
On page 308, a reference is made to a theorem by Guba [9, Theorem 4]. In the English translation of that article, the theorem in question is false as stated; left and right have been transposed. The statement on p. 308 in the survey is correct.
-
(6)
The final part of Theorem 6.3 is incorrect, but fairly obviously so. The correct statement should be: “the word and left/right divisibility problems all reduce to the problem of equality with a single letter.” That is, the “(resp. left/right divisibility)” statement should simply be deleted (the obvious incorrectness of this statement stems from the fact that the right divisibility problem by a single letter is trivial in any one-relation monoid with a right cycle, but the word problem remains open).
-
(7)
On p. 318, at the beginning of §3.2, it is stated that strong compression had “rather confusingly appeared in the 1978 paper by Adian and Oganesian [4]”. This is not correct; there is another, besides weak compression, form of compression studied at the end of [4], but this is quite different from strong compression.
-
(8)
On p. 327, as part of the statement of Theorem 4.3, and elsewhere, it is stated that \(\mathfrak {A}\) may “loop” indefinitely, and that being able to detect this behaviour is equivalent to solving the word problem in all one-relation monoids. This is not the correct terminology – “loop” should everywhere be replaced with “does not terminate”.
-
(9)
An interesting theorem is omitted. Borisov [5] constructs, given any n-generator r-relation monoid with undecidable word problem, a \((2n+r+5)\)-relator group with undecidable word problem. Hence, if the word problem is decidable for all 10-relator groups, then the word problem is decidable for all one-relation monoids. As the decidability of the word problem already for 2-relator groups remains open, this seems a rather unappetising way of approaching the one-relation problem, but nevertheless reduces it to a purely group-theoretic problem.
-
(10)
Finally, at no point in the survey is the question of who first explicitly asked the question of the decidability of the word problem for one-relation monoids (implicitly, it is asked by Thue). According to Adian [2, p. 28], Novikov posed the problem in 1957, in the wake of the undecidability results for finitely presented (semi)groups. This is, to the best of my knowledge, the first explicit appearance of the problem – which, hence, celebrates its 65th anniversary this very year.
Notes
The origin of the error in [3] is quite easy to understand. In [13], a five-relation monoid \(\mathfrak {H}\) with undecidable word problem, and all relations quite short, is constructed. However, there is another five-relation monoid with undecidable word problem in Matiyasevich’s article. In this monoid, there called \(\mathfrak {M}\), one of the relations is rather long, being \(M = N\), where \(|M| = 256\) and \(|N|=512\). This monoid \(\mathfrak {M}\) is subsequently used in the process of constructing the famous undecidable three-relation monoid. It seems likely the author of [3] had in mind \(\mathfrak {M}\), rather than \(\mathfrak {H}\), when he wrote his comment.
I do not know what method Makanin used to find his own system, and no proof ever appeared in print. By contrast, Matiyasevich’s example is proved correct in [14].
Words to the same effect are also given by Collins [7, p. 233].
References
Adian, S.I.: Defining relations and algorithmic problems for groups and semigroups. Proceedings of the Steklov Institute of Mathematics, No. 85 (1966). American Mathematical Society, Providence, 1966. [Trudy Mat. Inst. Steklov 85 (1966), 3–123]
Adian, S.I.: The works of P. S. Novikov and his students on algorithmic questions of algebra. Proc. Steklov Inst. Math. 133, 21–30 (1977). Mathematical logic, theory of algorithms and theory of sets (dedicated to P. S. Novikov on the occasion of his seventieth birthday) [Trudy Mat. Inst. Steklov. 133 (1973), 23–32, 274]
Adian, S.I.: Gennadiǐ Semënovich Makanin’s investigations on algorithmic questions of group and semigroup theory. Russian Math. Surveys 73(3), 553–568 (2018). [Uspekhi Mat. Nauk 73, 3 (2018), 183–196]
Adian, S.I., Oganesian, G.U.: On problems of equality and divisibility in semigroups with a single defining relation. Math. USSR, Izv. 12, 207–212 (1978). [Izv. Akad. Nauk SSSR Ser. Mat. 42, 2 (1978), 219–225]
Borisov, V.V.: Simple examples of groups with unsolvable word problem. Math. Notes 6, 768–775 (1969). [Mat. Zametki 6 (1969), 521–532]
Bush, George C.: Note on an embedding theorem of Adyan. Proc. Amer. Math. Soc. 14, 597–599 (1963)
Collins, Donald J.: A simple presentation of a group with unsolvable word problem. Illinois J. Math. 30(2), 230–234 (1986)
Fine, B., Kreuzer, M., Rosenberger, G.: On Magnus’ Freiheitssatz and free polynomial algebras. Int. J. Group Theory 4(1), 13–19 (2015)
Guba, V.S.: Conditions for the embeddability of semigroups into groups. Math. Notes, 56(1–2), 763–769 (1994). [Mat. Zametki 56, 2 (1994), 3–14]
Kharlampovich, O.G., Sapir, M.V.: Algorithmic problems in varieties. Internat. J. Algebra Comput. 5(4–5), 379–602 (1995)
Magnus, W.: Das Identitätsproblem für Gruppen mit einer definierenden Relation. Math. Ann. 106(1), 295–307 (1932)
Makanin, G.S.: On the identity problem in finitely defined semigroups. Soviet Math. Dokl. 7, 1478–1480 (1966). [Dokl. Akad. Nauk SSSR 171, 2 (1966), 285–287]
Matiyasevich, Yu. V.: Simple examples of unsolvable associative calculi. Soviet Math. Dokl., 8, 555–557 (1967). [Dokl. Akad. Nauk SSSR 173, 6 (1967), 1264–1266]
Matiyasevich, Yu.V.: Simple examples of unsolvable canonical calculi. Trudy Mat. Inst. Steklov 93, 50–88 (1967). ((In Russian))
Matiyasevich, Yu. V.: Word problem for Thue systems with a few relations. In: Term rewriting (Font Romeux, 1993), Lecture Notes in Computer Science, vol. 909, pp. 39–53. Springer, Berlin (1995)
Nyberg-Brodda, Carl-Fredrik.: The word problem for one-relation monoids: a survey. Semigroup Forum 103(2), 297–355 (2021)
Rumyantsev, Yu.: A minimal example of a semigroup with cancellation which is not imbeddable in a group. In: Algebraic Systems, pp. 198–202. Ivanov. Gos. Univ., Ivanovo (1981). (in Russian)
Shneerson, L.M.: Identities in semigroups with one defining relation. Logic, Algebra, and Computational Mathematics, Ivanovo Pedagogical Institute 1(1–2), 139–156 (1972). (in Russian)
Shneerson, L.M.: Identities in semigroups with one defining relation. II. Logic. Algebra, and Computational Mathematics, Ivanovo Pedagogical Institute 1(3–4), 112–124 (1972). (in Russian)
Shneerson, L.M.: The free subsemigroups of finitely presented semigroups. Siberian Math. J. 15, 325–328 (1974). [Sibirsk. Mat. Zh. 15 (1974), 450–453, 463]
Vazhenin, Yu. M.: Semigroups with one defining relation whose elementary theories are decidable. Siberian Math. J. 24, 33–41 (1983). [Sibirsk. Mat. Zh. 24 (1983), 40–49]
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Mikhail Volkov.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The original article for which this is a corrigendum was written while the author was a PhD student at the University of East Anglia. The author is currently a research associate at the University of Manchester, funded by the Dame Kathleen Ollerenshaw Trust, for which the author expresses his gratitude.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Nyberg-Brodda, CF. Correction to: The word problem for one-relation monoids: a survey. Semigroup Forum 105, 834–838 (2022). https://doi.org/10.1007/s00233-022-10310-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00233-022-10310-5