[GAP Forum] An issue with finitely presented groups

[Dr. Kashyap Rajeevsarathy]

Dear Forum,

I was trying to ascertain the membership of a word (in this case a letter
b2) in the index 2 subgroup of a finitely presented (surface) group. Please
point me to a better alternative (if possible) to the example below:


gap> f := FreeGroup("a1","b1","a2","b2");

<free group on the generators [ a1, b1, a2, b2 ]>

gap> genf := GeneratorsOfGroup(f);

[ a1, b1, a2, b2 ]

gap> G :=
f/[genf[1]*genf[2]*genf[1]^(-1)*genf[2]^(-1)*genf[3]*genf[4]*genf[3]^(-1)*genf[4]^(-1)];


<fp group of size infinity on the generators [ a1, b1, a2, b2 ]>

gap> genG := GeneratorsOfGroup(G);

[ a1, b1, a2, b2 ]

gap> H := Subgroup(G,[genG[1],genG[2],genG[3],genG[4]^2]);

Group([ a1, b1, a2, b2^2 ])

gap> genH := GeneratorsOfGroup(H);

[ a1, b1, a2, b2^2 ]

gap> genG[4] in H;

Error, the coset enumeration has defined more than 4096000 cosets

called from

TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens ) called from

CosetTableFromGensAndRels( fgens, grels, fsgens ) called from

TryCosetTableInWholeGroup( H ) called from

CosetTableInWholeGroup( U ) called from

<function "unknown">( <arguments> )

called from read-eval loop at line 8 of *stdin*

type 'return;' if you want to continue with a new limit of 8192000 cosets,

type 'quit;' if you want to quit the coset enumeration,

type 'maxlimit := 0; return;' in order to continue without a limit

brk>

Thanks,
Kashyap

[Alexander Hulpke]

Dear Forum, Dear Dr. Rajeevsarathy,

The subgroup you give cannot have index 2, as it is easy to find larger index in finite quotient images. (In fact I think the index is infinite.) Is there possibly a misprint in group or realtors, or why do you think the index should be 2?

(The error message you get is indicating that coset enumeration did not succeed. One can type `return;’ to try with more memory, but of course it can never terminate if the index is infinite.)

Regards,

Alexander Hulpke

Mitto ab tabulariUM meum

Post by Dr. Kashyap Rajeevsarathy
Dear Forum,
I was trying to ascertain the membership of a word (in this case a letter
b2) in the index 2 subgroup of a finitely presented (surface) group. Please
gap> f := FreeGroup("a1","b1","a2","b2");
<free group on the generators [ a1, b1, a2, b2 ]>
gap> genf := GeneratorsOfGroup(f);
[ a1, b1, a2, b2 ]
gap> G :=
f/[genf[1]*genf[2]*genf[1]^(-1)*genf[2]^(-1)*genf[3]*genf[4]*genf[3]^(-1)*genf[4]^(-1)];
<fp group of size infinity on the generators [ a1, b1, a2, b2 ]>
gap> genG := GeneratorsOfGroup(G);
[ a1, b1, a2, b2 ]
gap> H := Subgroup(G,[genG[1],genG[2],genG[3],genG[4]^2]);
Group([ a1, b1, a2, b2^2 ])
gap> genH := GeneratorsOfGroup(H);
[ a1, b1, a2, b2^2 ]
gap> genG[4] in H;
Error, the coset enumeration has defined more than 4096000 cosets
called from
TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
TryCosetTableInWholeGroup( H ) called from
CosetTableInWholeGroup( U ) called from
<function "unknown">( <arguments> )
called from read-eval loop at line 8 of *stdin*
type 'return;' if you want to continue with a new limit of 8192000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit
brk>
Thanks,
Kashyap
--
Kashyap Rajeevsarathy
Assistant Professor,
Indian Institute of Science Education and Research (IISER) Bhopal,
Indore By-pass Road,
Bhauri, Bhopal - 462066,
Madhya Pradesh, India.
Phone: [phone]
Website: https://home.iiserb.ac.in/~kashyap
_______________________________________________
Forum mailing list
https://mail.gap-system.org/mailman/listinfo/forum

[Derek Holt]

Dear Forum, Dear Dr. Rajeevsarathy,

As Alexander conjectured, the index of the subgroup H in G is infinite in this
example. There seem to be very few known methods for computing with subgroups of
infinite index in finitely presented groups. One such method is to use the
theory of automatic coset systems, and there is an implementation of this in
the KBMAG GAP package. If you can compute an automatic coset system for
a subgroup of sn FP-group, then you can compute the index of the subgroup,
and also reduce arbitrary words (in the underlying free group) to a normal
form coset representative of the subgroup. This enables you to test membership
of the subgroup.

Of course this only word if the group in question happens to be automatic with
respect to the subgroup, but fortunately that is the case in your example.

gap> f := FreeGroup("a1","b1","a2","b2");;
gap> genf := GeneratorsOfGroup(f);;
gap> G := f/[genf[1]*genf[2]*genf[1]^(-1)*genf[2]^(-1)*genf[3]*genf[4]*

genf[3]^(-1)*genf[4]^(-1)];;

gap> genG := GeneratorsOfGroup(G);;
gap> H := Subgroup(G,[genG[1],genG[2],genG[3],genG[4]^2]);;
gap>
gap> LoadPackage("kbmag");
true
gap> R := KBMAGRewritingSystem(G);;
gap> HR := SubgroupOfKBMAGRewritingSystem(R,H);;
gap> A := AutomaticStructureOnCosets(R,HR);
true
gap> Index(R,HR);
infinity
gap> ReducedCosetRepresentative(R,HR,genf[4]);
b2
gap> ReducedCosetRepresentative(R,HR,genf[4]^2);
<identity ...>
gap> ReducedCosetRepresentative(R,HR,genf[4]^3);
b2

Best wishes,
Derek Holt

Dear Forum, Dear Dr. Rajeevsarathy,
The subgroup you give cannot have index 2, as it is easy to find larger index in finite quotient images. (In fact I think the index is infinite.) Is there possibly a misprint in group or realtors, or why do you think the index should be 2?
(The error message you get is indicating that coset enumeration did not succeed. One can type `return;’ to try with more memory, but of course it can never terminate if the index is infinite.)
Regards,
Alexander Hulpke
Mitto ab tabulariUM meum

Post by Dr. Kashyap Rajeevsarathy
Dear Forum,
I was trying to ascertain the membership of a word (in this case a letter
b2) in the index 2 subgroup of a finitely presented (surface) group. Please
gap> f := FreeGroup("a1","b1","a2","b2");
<free group on the generators [ a1, b1, a2, b2 ]>
gap> genf := GeneratorsOfGroup(f);
[ a1, b1, a2, b2 ]
gap> G :=
f/[genf[1]*genf[2]*genf[1]^(-1)*genf[2]^(-1)*genf[3]*genf[4]*genf[3]^(-1)*genf[4]^(-1)];
<fp group of size infinity on the generators [ a1, b1, a2, b2 ]>
gap> genG := GeneratorsOfGroup(G);
[ a1, b1, a2, b2 ]
gap> H := Subgroup(G,[genG[1],genG[2],genG[3],genG[4]^2]);
Group([ a1, b1, a2, b2^2 ])
gap> genH := GeneratorsOfGroup(H);
[ a1, b1, a2, b2^2 ]
gap> genG[4] in H;
Error, the coset enumeration has defined more than 4096000 cosets
called from
TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
TryCosetTableInWholeGroup( H ) called from
CosetTableInWholeGroup( U ) called from
<function "unknown">( <arguments> )
called from read-eval loop at line 8 of *stdin*
type 'return;' if you want to continue with a new limit of 8192000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit
brk>
Thanks,
Kashyap
--
Kashyap Rajeevsarathy
Assistant Professor,
Indian Institute of Science Education and Research (IISER) Bhopal,
Indore By-pass Road,
Bhauri, Bhopal - 462066,
Madhya Pradesh, India.
Phone: [phone]
Website: https://home.iiserb.ac.in/~kashyap
_______________________________________________
Forum mailing list
https://mail.gap-system.org/mailman/listinfo/forum

_______________________________________________
Forum mailing list
https://mail.gap-system.org/mailman/listinfo/forum