Given a list of conjugacy classes of subgroups genlist of the symmetric group $S_n$. I want to compute the reduced table of marks of $S_n$ with the conjugacy classes of subgroups genlist. That means that I want to obtain a Size(genlist) $\times$ Size(genlist) matrix mred that only contains the rows and columns of the table of marks of $S_n$, for which the underlying group is conjugated to a group in genlist. It turns out that this is not easy, so for the moment I wrote a function GetRedTomWithTom that computes the reduced table of marks from the complete table of marks of $S_n$:
DeclareGlobalFunction("GetRedTomWithTom");
InstallGlobalFunction( GetRedTomWithTom, [IsInt, IsTableOfMarks, IsList ],
function( n, tom, genlist )
local i, j, k, subs, indexlist, fulltom, tomred;
subs := GeneratorsSubgroupsTom( tom );
indexlist := [ [ ], [ ] ];
fulltom := MatTom( tom );
tomred := [ ];
if( genlist[ 1 ] = [ ( ) ] ) then
Add( indexlist[ 1 ], 1 );
Add( indexlist[ 2 ], [ () ] );
for i in [ 2 .. Size( subs[ 1 ] ) ] do
for j in [ 2 .. Size( genlist ) ] do
if( IsConjugate( SymmetricGroup( n ), Group( genlist[ j ] ), Group( subs[ 1 ]{ subs[ 2 ][ i ] } ) ) ) then
Add( indexlist[ 1 ], i );
Add( indexlist[ 2 ], subs[ 1 ]{ subs[ 2 ][ i ] } );
break;
fi;
od;
od;
else
for i in [ 2 .. Size( subs[ 1 ] ) ] do
for j in [ 1 .. Size( genlist ) ] do
if( IsConjugate( SymmetricGroup( n ), Group( genlist[ j ] ), Group( subs[ 1 ]{ subs[ 2 ][ i ] } ) ) ) then
Add( indexlist[ 1 ], i );
Add( indexlist[ 2 ], subs[ 1 ]{ subs[ 2 ][ i ] } );
break;
fi;
od;
od;
fi;
for i in [ 1 .. Size( indexlist[ 1 ] ) ] do
Add( tomred, [ ] );
for k in indexlist[ 1 ] do
Add( tomred[ i ], fulltom[ indexlist[ 1 ][ i ] ][ k ] );
od;
od;
return [ tomred, indexlist[ 2 ] ] ;
end
);
If I call this function with the parameters 8, TableOfMarksFromLibrary("S8"), genlist, where
genlist := [ [ () ], [ (1,2) ], [ (2,3)(4,5)(7,8) ], [ (1,6)(2,5)(3,7)(4,8) ], [ (1,2)(7,8) ], [ (4,5), (1,3)(7,8) ],
[ (4,5), (7,8) ], [ (1,6)(2,3)(4,7)(5,8), (2,3)(4,5)(7,8) ], [ (1,2)(3,4)(5,6)(7,8), (1,6)(2,5)(3,7)(4,8) ],
[ (2,5)(3,4), (2,3)(4,5)(6,7) ], [ (2,5), (1,6)(2,5)(3,7)(4,8) ],
[ (1,4)(2,6)(3,7)(5,8), (1,5)(2,6)(3,7)(4,8) ], [ (1,2)(3,4)(5,6)(7,8), (1,2)(3,4) ], [ (6,7), (7,8) ],
[ (1,7)(2,8), (1,3)(2,4) ], [ (4,5), (6,7), (3,8) ], [ (1,6)(2,4,8,5)(3,7), (2,8) ],
[ (4,5), (6,7), (1,2)(3,8) ], [ (2,7,6,8), (7,8) ], [ (1,2)(3,4), (1,5,2,6)(3,7,4,8) ],
[ (1,4)(2,6)(3,7)(5,8), (1,5)(2,6)(3,7)(4,8), (2,6) ], [ (1,8)(2,3)(6,7), (1,4,8,5)(2,3,7,6) ],
[ (3,4)(5,6,7,8), (6,8) ], [ (1,2)(3,4)(5,6)(7,8), (1,5)(2,6)(3,7)(4,8), (1,6)(2,5)(3,7)(4,8) ],
[ (1,8)(6,7), (1,3)(7,8) ], [ (4,5), (3,4), (1,8)(6,7) ], [ (2,5)(3,4), (2,4,6,3,5,7) ],
[ (4,5), (1,2)(6,8), (1,3)(7,8) ], [ (4,5), (6,7,8), (7,8) ], [ (1,6)(2,4,8,5,3,7), (1,6)(2,5)(3,7)(4,8) ],
[ (2,8)(3,4)(6,7), (2,3)(4,5)(7,8) ], [ (1,4)(2,6)(3,7)(5,8), (1,5,8,4,2,7,3,6) ],
[ (2,6), (1,6)(2,5)(3,7)(4,8), (1,5)(2,6)(3,7)(4,8) ], [ (1,5)(2,6)(3,7,4,8), (1,6)(2,5)(3,7,4,8), (7,8) ],
[ (2,7,6,8), (7,8), (3,4) ], [ (2,5), (1,6)(2,5)(3,7,4,8), (3,4) ], [ (1,2)(4,5), (1,2), (1,2)(6,7), (3,8) ],
[ (4,5), (1,3)(7,8), (1,8)(6,7) ], [ (1,3)(7,8), (1,4)(2,6)(3,7)(5,8), (2,6) ], [ (3,8), (6,8), (3,4) ],
[ (1,7,5)(4,8,6), (1,2,5,7)(3,4,6,8) ], [ (4,5), (2,3), (2,6), (7,8) ],
[ (1,4)(2,6)(3,7)(5,8), (1,2), (1,2)(7,8) ], [ (1,6), (1,6)(2,5)(3,7,4,8), (2,5), (3,4) ],
[ (4,5), (6,7,8), (3,4), (7,8) ], [ (3,5,7)(4,6,8), (1,3,5,7)(2,4,6,8), (1,8,5,4)(2,7,6,3) ],
[ (1,2,4,5), (1,2,3,4,5,6) ], [ (4,5), (3,4), (3,8), (6,7) ], [ (4,5), (3,4), (3,8), (1,2)(6,7) ],
[ (2,5), (2,3,5,7)(4,6,8), (6,8) ], [ (1,3)(2,4), (1,2,5,4,3), (6,7,8), (7,8) ],
[ (1,8,7,3)(2,6,5,4), (1,7), (1,3)(7,8), (2,5) ], [ (6,8), (3,4,5,6,7,8) ],
[ (1,2)(4,5), (1,3), (6,8,7), (1,2)(6,7) ], [ (6,8), (1,2)(3,4,5,6,7,8) ],
[ (1,6)(2,4,8,5,3,7), (1,6)(2,5)(3,7,4,8), (1,6) ], [ (1,2)(4,5), (1,3), (1,2,6), (1,3)(7,8) ],
[ (1,2,7), (1,3), (1,2,4) ], [ (1,3)(2,4), (1,6)(2,5)(3,7,4,8), (1,2) ], [ (2,5), (2,4,3), (6,7,8), (7,8) ],
[ (2,6), (1,3,7,4,8,5)(2,6), (1,8) ], [ (1,4)(2,6)(3,7)(5,8), (1,2,4), (7,8), (1,2) ],
[ (6,8), (1,2,4,3), (1,2,7), (1,2) ], [ (3,4,5,6), (1,2,3,4)(5,6,7,8) ],
[ (1,2)(3,4), (1,5,7)(3,4,6,8), (1,5,7,2)(3,4,6,8) ], [ (2,5), (1,2,3), (2,6,7) ],
[ (1,8)(2,3,4)(5,6,7), (3,4)(6,7,8) ], [ (1,5)(2,6,3,7,4,8), (1,2) ], [ (1,2)(6,7,8), (2,8)(3,4)(5,6) ],
[ (2,3), (2,3,4,5,6,7,8) ], [ (1,2), (2,3,4,5,6,7,8) ] ];
GAP throws a no method found error:
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `IsPrime' on 2 arguments called from
IsPrime( DefaultRing( [ r ] ), r ) called from
IsPrime( Length( dom ) / Length( b ) ) called from
DoBlocks( t ) called from
DoBlocks( subo[1] ) called from
AllBlocks( h ) called from
... at line 59 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
Can anybody tell me where that might come from? For example it does not occur for the list
genlist := [ [ (2,3)(4,5) ], [ (4,5) ], [ (4,5), (2,3) ], [ (3,4,5), (4,5) ],
[ (4,5), (2,3), (2,4)(3,5) ], [ (1,2,3,4,5), (2,5)(3,4) ],
[ (4,5), (1,2,3), (2,3) ], [ (2,3)(4,5), (2,4)(3,5), (3,4,5), (4,5) ],
[ (1,2,3,4,5), (1,2) ] ];
Thanks for reading!
The problem is a bug in the conjugacy test in $S_n$. When trying to conjugate a transitive group to an intransitive one, the code does not test for transitivity of the second group, but simply tries to compute block systems. The error then is a side-effect of block size not dividing domain size. (If this error would not arise, the code would return `fail' for non-matching block systems.)
This will be fixed in the 4.8 release. An easy workaround would be to simply test for equal transitivity (or better: same orbit sizes) before calling the conjugacy test. E.g. if U and V are the subgroups, test
On a slightly related note: In your code, you call `SymmetricGroup(n)' in every conjugacy test. This will create a new group each time and require rebuilding some data structures. You might see a small performance improvement by initially creating $S_n$ once.
Also, if you want to test for conjugacy representatives amongst a duplicate free list of subgroups, tree is a utility function:
that produces representatives and tries to avoid redundant tests, thus being faster. (Due to the bug you should separate transitive and intransitive groups first.)