Theoretical Backgrounds of Applied Discrete Mathematics
On equations in free groups with commutant restrictions on solutions
A. I. Zetkina Yaroslavl State University, Yaroslavl, Russia
Abstract:
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$.
Keywords:
free group, equation in a free group.
UDC:
512+512.5+
512.54+
512.54.03
DOI:
10.17223/20710410/66/1