GAP express word as product of conjugates of relators

Question

GAP can tell you if a word on a finite alphabet is expressible as a product of conjugates of a given list of words. In the example below, it tells us that the word $x^3yx^3y$ is expressible as a product of conjugates of the words $x^4$, $y^2$, $xyxy$:

gap> H := FreeGroup("x", "y");
<free group on the generators [ x, y ]>
gap> x := H.1;
x
gap> y := H.2;
y
gap> G := H / [ y^2, x^4, x*y*x*y ];
<fp group on the generators [ x, y ]>
gap> x := G.1;
x
gap> y := G.2;
y
gap> x^3*y*x^3*y = x^0;
true

However, telling us that such a product exists does not tell us what it is. For instance, in the example above, we have:

$x^3yx^3y = (x^3 \color{red}{y^2} x^{-3}) \cdot \color{red}{x^4} \cdot (y(\color{red}{xyxy})^{-1}y^{-1}) \cdot (y\color{red}{x^4}y^{-1}) \cdot \color{red}{y^2}$

Is there any way we can ask GAP (or any other computer algebra package) to actually compute such a product rather than merely telling us that it exists?

Answer 1

As long as the quotient group $G$ is small (the reason for small is related to Derek Holt's observatiuon that this is a hard problem), you could form suitable generators of the kernel (as conjugates of relators) and use the general rewriting mechanism to express elements (that is their UnderlyingElement in the free group) as word in the conjugate relators. In your example:

gap> rels:=Union(List(RelatorsOfFpGroup(G),r->List(Elements(G),
> e->r^UnderlyingElement(e))));
[ y^2, x^-1*y^2*x, x^4, (x*y)^2, (y*x)^2, x^-2*y^2*x^2, x^-1*(y*x)^2*x,
  y^-1*x^-1*y^2*x*y, y^-1*x^4*y, y^-1*(x*y)^2*y, x^-3*y^2*x^3,
  x^-2*(y*x)^2*x^2, y^-1*x^-2*y^2*x^2*y, y^-1*x^-1*(y*x)^2*x*y,
  y^-1*x^-3*y^2*x^3*y, y^-1*x^-2*(y*x)^2*x^2*y ]
gap> sub:=Subgroup(H,rels);
Group(<16 generators>)
gap> Index(H,sub);
8
gap> iso:=IsomorphismFpGroupByGenerators(sub,rels);
[ y^2, x^-1*y^2*x, x^4, (x*y)^2, (y*x)^2, x^-2*y^2*x^2, x^-1*(y*x)^2*x,
  y^-1*x^-1*y^2*x*y, y^-1*x^4*y, y^-1*(x*y)^2*y, x^-3*y^2*x^3,
  x^-2*(y*x)^2*x^2, y^-1*x^-2*y^2*x^2*y, y^-1*x^-1*(y*x)^2*x*y,
  y^-1*x^-3*y^2*x^3*y, y^-1*x^-2*(y*x)^2*x^2*y ] ->
[ F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11, F12, F13, F14, F15, F16 ]
gap> elm:=x^3*y*x^3*y;;
gap> IsOne(elm);
true
gap> ImagesRepresentative(iso,UnderlyingElement(elm));
F3*F2*F5^-1*F1*F9

so the expression is $(x^4)\cdot (y^2)^x /(xyxy)\cdot (y^2)\cdot (x^4)^y$, by looking at the rels of indices 3,2,5,1,9.