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 U

for 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;