On equations in free groups with commutant restrictions on solutions

A. I. Zetkina

Prikladnaâ diskretnaâ matematika, no. 4 (2024), pp. 5-13.

Résumé

A polynomial algorithm has been constructed that allows, given an arbitrary equation of the form $w(x_{1},\ldots,x_{n})=[a,b]$, resolved with respect to unknowns, where $w(x_{1},\ldots,x_{n})$ is a group word in the alphabet of unknowns and $[a,b]$ is the commutator of free generators $a$ and $b$ of the free group $F_2$, to determine whether there is a solution to this equation that satisfies the condition $x_{1}\ldots, x_{n}\in F_{2}^{(1)}$, where $F_2^{(1)}$ is the commutator of group $F_2$. The existence of a polynomial algorithm has been established that allows, given an arbitrary equation of the form $ w (x_{1}, \ldots, x_{n}) = g (a, b) $, where $ g (a, b) $ is an element of length less than $4$ of the free group $ F_{2} $, to determine whether a solution to this equation exists, that satisfies the condition $x_{1},\ldots, x_{t}\in F_{2}^{(1)}$, where $t$ is an arbitrary fixed number between 1 and $n$. The algorithmic solvability of a similar problem has been proven for the equations $w(x_{1},a,b)=1$ with one variable $x_1$.

Détail

Keywords: free group, equation in a free group.

Bibliographie

[1] Tarski A., Mostowski A., and Robinson R. M., Undecidable Theories, North-Holland Publ. Company, Amsterdam, 1953, xi+98 pp. | MR | Zbl

[2] Kharlampovich O. and Myasnikov A., “Elementary theory of free non-abelian groups”, J. Algebra, 302 (2006), 451–552 | DOI | MR | Zbl

[3] Lyndon R. C., “Equations in free groups”, Trans. Amer. Math. Soc., 96 (1960), 445–457 | DOI | MR | Zbl

[4] Lorents A. A., “On the representation of solution sets of systems of equations with one unknown in free groups”, Dokl. AN SSSR, 178:2 (1968), 290–292 (in Russian) | Zbl

[5] Appel K. I., “One-variable equations in free groups”, Proc. Amer. Math. Soc., 19 (1968), 912–918 ; 36:1 (1972), 110–179 | DOI | MR | Zbl

[6] Khmelevskiy Yu. I., “Systems of equations in a free group. I, II”, Math. USSR-Izv., 5:6 (1971), 1245–1276 ; 6:1 (1972), 109–180 | DOI | DOI | MR | MR

[7] Makanin G. S., “Equations in a free group”, Math. USSR-Izv., 21:3 (1983), 483–546 | DOI | MR | Zbl | Zbl

[8] Makanin G. S., “Decidability of the universal and positive theories of a free group”, Math. USSR-Izv., 25:1 (1985), 75–88 | DOI | MR | Zbl

[9] Merzlyakov Yu. I., “Positive formulas on free groups”, Algebra i Logika, 5:4 (1966), 25–42 (in Russian) | Zbl

[10] Razborov A. A., “On systems of equations in a free group”, Math. USSR-Izv., 25:1 (1985), 115–162 | DOI | MR | Zbl

[11] Gassner B. J., “On braid groups”, Abh. Math. Sem. Univ. Hamburg, 25 (1961), 10–22 | DOI | MR | Zbl

[12] Birman J. S., Braids, Links and Mapping Class Groups, AM, 82, Princeton University Press, Princeton, 1974 | MR

[13] Kurovskaya Notebook: Unsolved Questions in Group Theory, 11th ed., IM SB RAS, Novosibirsk, 1990 (in Russian)

[14] Malkhasyan A. Sh., “On the solvability in subgroups of equations in a free group”, Prikladnaya Matematika, 1986, no. 2, 42–47 (in Russian) | MR | Zbl

[15] Diekert V., Makanin's Algorithm for Solving Word Equations with Regular Constraints, Technical Report No 1998/02, University of Stuttgart, Faculty of Computer Science, 1998, 43 pp.

[16] Maltsev A. I., “About the equation $zxyx^{-1}y^{-1}z^{-1} = aba^{-1}b^{-1}$ in a free group”, Algebra i Logika, 1:5 (1962), 45–50 (in Russian) | Zbl

[17] Schupp P. E., “On the substitution problem for free groups”, Proc. Amer. Math. Soc., 23 (1969), 421–423 | DOI | MR | Zbl

[18] Edmunds C. C., “On the endomorphisms problem for free group”, Com. Algebra, 1975, no. 3, 7–20 | MR

[19] Durnev V. G., “On the solvability problem for equations with a single coefficient”, Math. Notes, 59:6 (1996), 601–610 | DOI | DOI | MR | MR | Zbl

[20] Magnus W., Karrass A., and Solitar D., Combinatorial Group Theory, Interscience Publ., N.Y., 1966 | MR | Zbl

[21] Bormotov D., Gilman R., and Myasnikov A., “Solving one-variable equation in free groups”, J. Group Theory, 12:2 (2009), 317–330 | DOI | MR | Zbl