> < ^ From:

> < ^ Subject:

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.

> < [top]