Dear Forum members,
on Fri 3 Oct, Bruce W. Colletti asked how the following can be done efficiently with GAP. >----------------- > >PROBLEM STATEMENT > > - Let S(n) be the symmetric group on n letters (n is even) > > - Let H = <(1,2),(3,4),(5,6),...,(n-1,n)> > > - Let B := <(1,3)(2,4),(3,5)(4,6),(5,7)(6,8),...>, where i'th generator >is (2i-1,2i+1)(2i,2(i+1)) > > - Show HB is a subgroup and H intersect B is {identity}. > >To show the >former, I use HB = BH iff HB is a group. I loop through n = 14, 16, 18, 20. > >-----------------
For the last step, Bruce chooses to compute the double cosets HB and BH via
D1 := DoubleCoset(H,(),B); D2 := DoubleCoset(B,(),H);
where B and H are subgroups of the full symmetric group. Comparing these
two double cosets involves computing and comparing the sets of all elements
of D1 and D2, which have roughly half a million elements each in the case n
= 14. This might explain why that approach proves not to be feasible.
In the above case, I would suggest the following instead: HB is a subgroup
of G if and only if the size of the (finite) coset HB equals that of the
sugroup generated by H and B, and that |HB| = |H| |B| / |H intersection B|.
Thus, the following piece of code:
# HB = BH?J := Subgroup (G, Union (H.generators, B.generators));
I := Intersection(H,B);Print("\nn=",n," group(HB)? ",Size (J)*Size (I) = Size (H)*Size (B), " |H intsect B| = ", Size(I));
could be used to do the test. For n = 14, 16, 18, 20, this is now a matter
of seconds; even values of n in the thousands take less than a minute (on
my 120 MHz Mac).
Hope this helps,
Burkhard.