> < ^ From:

< ^ Subject:

Dear Gap-Forum,

let me add some comments to the previous discussion.

Avital Oliver wrote:

> The main problem is the memory that ConjugacyClassesSubgroups takes.

> Even with a group of relativaly small size for my application (2000

> elements), it takes up approximately 200-300mg of memory. Although I am far

The memory requirements will depend very much on the group. If your

calculation requires that much memory, I'd expect that the group contains a

large elementary abelian subgroup.

from an expert on the internals of GAP, I would think there should be a way

to generate each subgroup at a time, without wasting the memory needed for

Not in the general context: All known algorithms create the groups from

``smaller'' groups, and often it is necessary to keep found groups in memory

to eliminate conjugates.

What one can do for your specific case, however is to use the subdirect

product construction mentioned by Laci Kovacs and write a dedicated routine

to find subdirect products. The constituents are all there, essentially one

has to create all normal subgroups and then all possible isomorphisms of the

factor groups.

To describe the subgroups K of a direct product G x H, one needs

to know not only the subgroups U of G and the subgroups X of H

(so one can form all possible K = U x X ), but also all

isomorphisms f : U/V -> X/Y between (nontrivial) sections of G

Extra work is needed to eliminate conjugates. It is easy to see that f only

has to be defined up to inner automorphisms, in fact one can show that one

has to consider normal subgroups up to conjugacy by the normalizers of U and

X, and then consider isomorphisms up to automorphisms induced by the

normalizers of V and Y.

(If you can read German: a proof is given in theorem (32) on page 33

of my PhD thesis, which can be found at:

http://www.math.colostate.edu/~hulpke/paper/prom.ps.gz )

Continuing, Laci Kovacs describes self-normalizing subgroups:

> How can one tell whether the K so defined is self-normalizing? If

> K = U x X, the test is simply that U and X are to be

> self-normalizing (in G and H, respectively). When K is formed

> from an f, the answer is more difficult. Part of it is that U/V

> should have trivial centralizer (I mean, if an element g of G is

> such that all commutators [u,g] lie in V then g must lie in V:

> in particular, U/V must have trivial centre), and of course the

(I think also U=V is possible, even if the normalizer is larger ?)

Such a test (or parts of it) can be easily incorporated.

> same must hold for X/Y. The other part is much harder to check: f

> must not be the restriction of any isomorphism

> f*: U*/V -> X*/Y such that U is a proper normal subgroup of U*.

> The necessity of these conditions is obvious, and it is not hard to

> show that together they are also sufficient, but I have not seen them

> stated anywhere in the literature.

This test seems to be much harder. In fact computing normalizers is

reasonably fast that I'd guess it might be cheaper to construct the

subdirect product and just test for self-normalizing.

I append a simple-minded routine which does all this. It does *not* do the full

conjugacy test, but only uses inner automorphisms induced by U/V. You will

therefore have to test the resulting representatives up to conjugacy.

I don't know what groups you have in mind -- I've only tried subgroups of

S_3 xS_4, but for these the performance is reasonable.

I hope this routine is of help (it also is easily adapted to other

situations of subdirect products),

Alexander Hulpke

-- Colorado State University, Department of Mathematics,

Weber Building, Fort Collins, CO 80523, USA

email: hulpke@math.colostate.edu, Phone: ++1-970-4914288

http://www.math.colostate.edu/~hulpke

HasTrivialFactorCentralizer:=function(G,U,V)

local n, nhom, c;

# this is not the complete test: We check that N_{N_G(U)}(V)/V has a

# trivial centralizer for U.

n:=Normalizer(G,U);

n:=Normalizer(n,V);

nhom:=NaturalHomomorphismByNormalSubgroup(n,V);

c:=Centralizer(Image(nhom),Image(nhom,U));

return Size(c)=1 or Size(U)=Size(V);

if Size(c)<>1 and Size(Centre(Image(nhom,U)))=1 then

Error("x");

fi;

return Size(Centre(Image(nhom,U)))=1;

end;

# assume: Both G and H are permutation groups or pc groups, otherwise the

# code is likely to be very slow

CreateSubdirectProducts:=function(G,H)

local all, d, e1, e2, ug, uh, vs, uhom, q, a, inn, areps, ys, vhom, eygens, r, f, gens, s, u, v, x, y, rep;

all:=[];

d:=DirectProduct(G,H);

e1:=Embedding(d,1);

e2:=Embedding(d,2);

ug:=List(ConjugacyClassesSubgroups(G),Representative);

uh:=List(ConjugacyClassesSubgroups(H),Representative);

for u in ug do

vs:=NormalSubgroups(u);

# test: trivial centralizer

vs:=Filtered(vs,i->HasTrivialFactorCentralizer(G,u,i));

Print("U=",u,", ",Length(vs)," normals\n");

for v in vs do

uhom:=NaturalHomomorphismByNormalSubgroup(u,v);

q:=Image(uhom);

a:=AutomorphismGroup(q);

inn:=InnerAutomorphismsAutomorphismGroup(a);

areps:=RightTransversal(a,inn);

# still to do: conjugacy by normalizer of Ufor x in uh do

ys:=NormalSubgroups(x);

# right index

ys:=Filtered(ys,i->Index(x,i)=Size(q));# test: trivial centralizer

ys:=Filtered(ys,i->HasTrivialFactorCentralizer(G,x,i));Print("X=",x,", ",Length(ys)," normals\n");

for y in ys do

vhom:=NaturalHomomorphismByNormalSubgroup(x,y);

eygens:=List(GeneratorsOfGroup(y),i->Image(e2,i));

r:=Image(vhom);

f:=IsomorphismGroups(q,r);

if f<>fail then

# still to do: conjugacy by normalizer of X

for rep in areps do

# build the semidirect product for u,v and rep*f

# first generators of u, glued together properly with v

gens:=List(GeneratorsOfGroup(u),i->

Image(e1,i)*

Image(e2, PreImagesRepresentative(vhom,

Image(f,Image(rep,Image(uhom,i))))));

# then generators of y

Append(gens,eygens);

s:=Subgroup(d,gens);# now test for self-normalizing if Index(Normalizer(d,s),s)=1 then Add(all,s); fi; od; fi; od;

od; od; od; return all; end;

> < [top]