> < ^ Date: Tue, 07 Oct 1997 12:22:30 +1000
> < ^ From: Burkhard Hoefling <b.hoefling@tu-bs.de >
> < ^ Subject: Re: Code Improvement

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]