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: 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.