From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Groups of order (p^2)q
Date: 2 Nov 1998 00:14:01 GMT
As a suggestion for proving groups non-isomorphic, I wrote
>You must typically find some invariant of the two which is not the same
>in the two cases: if their automorphism groups are distinct, for example,
>or their character tables, group rings, homology groups, ... are not the
>same, then the groups are not isomorphic.
QSCGZ followed up with questions:
>Is this an ordered list ?
>What invariants would you test first for best efficiancy ?
I don't know what I would reach for first; it depends on what's easiest
to compute about the groups. For general finite groups I might expect
the character tables to show distinctness quickly, but probably for
solvable groups and certainly for p-groups I would look for characteristic
subgroups and how they are glued together.
>Suppose the very general case , that some groups of order 65536 are chosen
>randomly and their multiplication-tables are put into the RAM of a comuter ,
>occupying 8GB each.
Ugh! I cannot think of a _worse_ way to represent these groups! (By the
way, you would need tables with 2^32 entries, but each entry would have to
be a minimum of 16 bits, so the tables are probably 16GB each).
Probably I would immediately convert the group data to something more
manageable. These being 2-groups, I would look for a maximal central
series {1} < H1 < H2 < ... < H16 = G with H_{i+1}/H_i in the center
of G/H_i and generated by a single element g_i H_i. Then the elements
of G are precisely the words g_0^e_0 g_1^e_1 ... g_15^e_15 in the g_i,
with exponents e_i in {0,1}. The group structure is determined by the
squares (g_i)^2 and commutators [g_i, g_j]=(g_i)^(-1) (g_j)^(-1) g_i g_j.
The first will be in the subgroup H_i and the latter in H_k
where k=min(i,j). So the group is determined by a table with only 16+C(16,2)
i.e. 136 entries (272 bytes) at worst. I would call that a modest
improvement in storage...
On the other hand, you'd want to write a subroutine to perform the
multiplication of two general elements in the group, since it would be
rather convoluted, requiring many levels of recursion. Rather a lot of
elementary group theory would be used to speed things up; e.g. an
element is in the center iff it commutes with each g_i; this requires
we check 16 pairs of products, not 65536.
>Now you have to determine, whether they are isomorphic.
>What invariants can be tested fastest ?
I don't know about "fastest", exactly, but I would probably compute
the invariants of the finite abelian groups in the ascending central
series, say. For if G1 is isomorphic to G2, we certainly require
Z(G1) = Z(G2), which would be fairly easy to check. Moreover, we
would need G1/Z(G1) = G2/Z(G2), which I might be willing to assume
is testable by induction on the order of the group (that is, I would
write a program to test for isomorphism of _general_ 2-groups, rather
than groups of order 2^16.) If G1 and G2 are at least this
similar, we would then test for isomorphism by seeing whether or not
the groups are obtained by the same cocycle in H^2(G/Z,Z); this is a little
tricky since we must partition the cocycles into orbits under conjugacy
by both Aut(G/Z) and Aut(Z). (In my admittedly limited experience this
seems to be easier when we place Z by its elements of order 2 in this
discussion; then Aut(Z) = GL(n,2) for some n.)
>I would expect numbers (invariants) such as
> # elements of order k (k small) [others deleted]
>to be much faster to calculate in general than
>the obligatory invariants from your list.
Maybe; I am somewhat dubious about what's really faster. The method I
have proposed has the advantage that, at the end of it, we have a
definitive answer as to whether or not the groups are isomorphism.
IIRC this was the method used in "The Groups of Order 2^n (n \le 6)",
Marshall Hall Jr. and James K. Senior. (Perfect bedtime reading!)
As with almost every question which begins "How would you...", the
answer is really, "That depends". You seem to be assuming that a group
is most naturally presented by is multiplication table; I would
disagree, and the nature of the presentation might affect how I
answer the question. Indeed, the group-theory software I have seen
(e.g. GAP and MAGMA (=Cayley) ) usually manage several data types
which are all really groups but which are stored differently and call
for different algorithsm.
dave
Group Theory:
http://www.math.niu.edu/~rusin/known-math/index/20-XX.html
==============================================================================
From: mareg@lily.csv.warwick.ac.uk (Dr D F Holt)
Newsgroups: sci.math
Subject: Re: Groups of order (p^2)q
Date: 10 Nov 1998 18:20:28 GMT
In article <19981108063021.12671.00000950@ng14.aol.com>,
qscgz@aol.com (QSCGZ) writes:
>As a suggestion for proving groups non-isomorphic,
>rusin@vesuvius.math.niu.edu (Dave Rusin) wrote :
>
[Discussion about testing for isomorphism between groups omitted.]
> >As with almost every question which begins "How would you...", the
> >answer is really, "That depends". You seem to be assuming that a group
> >is most naturally presented by is multiplication table; I would
> >disagree, and the nature of the presentation might affect how I
> >answer the question. Indeed, the group-theory software I have seen
> >(e.g. GAP and MAGMA (=Cayley) ) usually manage several data types
> >which are all really groups but which are stored differently and call
> >for different algorithsm.
>
>I think , you mean relations of the generators.
>But I can't imagine , that they calculate such invariants without
>generating the multiplication-table .
>
They most certainly do! No efficient computation with finite groups
involves using full multiplication tables. For general groups, a
permutation representation is likely to be the best bet - and then
only generators of the group are actually stored. You would then
measure complexity of operations in terms of the degree of the
permutations rather than the order of the group.
For solvable groups, which include groups of prime power order, there
is a better data structure known as a power-conjugate presentation.
In the case of 65536 = 2^16, this would be a presentation on 16
generators and 17*16/2 = 136 relators each of length at most 18.
Calculation of invariants such as center, derived group and so on
would be almost instantaneous, and orders and sizes of conjugacy
classes would not take long. Again, when you compute a subgroup,
you never list its elements - there is no need - you just compute
a set that generates it.
However, having made light of all that, I have to concede that you
have picked a difficult example. There are certainly pairs of
nonisomorphic groups of order 2^16 in which all conceivable
invariants are the same, and deciding whether or not they are
isomorphic would have to be done by a much more extensive search,
which might well be impractical with current programs. I believe
that isomorphism testing programs for p-groups in general are
practical only when the groups have up to about 4 or 5 generators,
and with 2^16, you could get difficult pairs with, say, 12 generators.
Derek Holt.
==============================================================================
From: Dave Rusin
Date: Tue, 10 Nov 1998 13:36:46 -0600 (CST)
To: mareg@lily.csv.warwick.ac.uk
Subject: Re: Groups of order (p^2)q
Newsgroups: sci.math
In article <72a05c$q8t$1@holly.csv.warwick.ac.uk> you write:
>However, having made light of all that, I have to concede that you
>have picked a difficult example. There are certainly pairs of
>nonisomorphic groups of order 2^16 in which all conceivable
>invariants are the same, and deciding whether or not they are
>isomorphic would have to be done by a much more extensive search,
>which might well be impractical with current programs. I believe
>that isomorphism testing programs for p-groups in general are
>practical only when the groups have up to about 4 or 5 generators,
>and with 2^16, you could get difficult pairs with, say, 12 generators.
You're right about the potential difficulties, of course; I didn't have
Hall and Senior to hand when I last posted but I didn't think they claimed
to have devised a complete algorithm for testing isomorphism of 2-groups.
On the other hand, if G/Phi(G) is Z_2 ^ 12 and |G| = 2^16, it would
seem there can't be _too_ much wiggle room for G to be interesting, is
there? Indeed, it seems a=|G : Phi(G) Z(G)| ought to be bounded in some way
by b=|Phi(G): Phi(Phi(G))| -- perhaps a < b^2 (as for G = Quat(8)^n ) ?
Seems to me that in this way we'd find some Abelian direct factors for
a group of order 2^16 requiring 12 generators, and moreover those factors
would have to be of moderate rank unless G is really close to an
extension Z_2 ^ m -> G -> Z_2 ^ n.
Not that I'd want to tackle this myself, mind you.
Looks kind of Marshall Hall-ian.
dave
==============================================================================
Date: Wed, 11 Nov 1998 12:30:51 GMT
From: Dr D F Holt
To: rusin@math.niu.edu
Subject: Re: Groups of order (p^2)q
> On the other hand, if G/Phi(G) is Z_2 ^ 12 and |G| = 2^16, it would
> seem there can't be _too_ much wiggle room for G to be interesting, is
> there? Indeed, it seems a=|G : Phi(G) Z(G)| ought to be bounded in some way
> by b=|Phi(G): Phi(Phi(G))| -- perhaps a < b^2 (as for G = Quat(8)^n ) ?
> Seems to me that in this way we'd find some Abelian direct factors for
> a group of order 2^16 requiring 12 generators, and moreover those factors
> would have to be of moderate rank unless G is really close to an
> extension Z_2 ^ m -> G -> Z_2 ^ n.
>
> Not that I'd want to tackle this myself, mind you.
>
Yes, I think the most difficult examples are those of type
Z_2 ^ m -> G -> Z_2 ^ n.
I picked on the n=12 case a bit at random. It could be that something like
m=6, n=10 is hardest. But a search for an isomorphism in a difficult case
can reduce to a search through GL(n,2), which is hopeless for any n > 6, say.
Derek Holt.