[GAP Forum] Retrieving group name (fwd)

[Markus Pueschel]

Hello,

I want to add to this discussion that Sebastian Egner and myself wrote a 
program a while ago (1997, GAP3) that decomposes a group into semidirect and 
direct product of "basic" groups (cyclic, dihedral, and some others) and 
constructs accordingly a name. I give an example below.
I am happy to send this program if somebody wants it.

best regards,
  Markus Pueschel

gap> AllSmallGroups(32);
[ 32_1, 32_2, 32_3, 32_4, 32_5, 32_6, 32_7, 32_8, 32_9, 32_10, 32_11, 32_12,
  32_13, 32_14, 32_15, 32_16, 32_17, 32_18, 32_19, 32_20, 32_21, 32_22,
  32_23, 32_24, 32_25, 32_26, 32_27, 32_28, 32_29, 32_30, 32_31, 32_32,
  32_33, 32_34, 32_35, 32_36, 32_37, 32_38, 32_39, 32_40, 32_41, 32_42,
  32_43, 32_44, 32_45, 32_46, 32_47, 32_48, 32_49, 32_50, 32_51 ]
gap> List(last, OneIsomorphismTypeGroup);
[ Z32, (Z4 : (Z2 x Z4)), (Z4 x Z8), (Z4 : Z8), (Z2 : (Z2 x Z8)),
  (Z2 : (Z2 : (Z2 x Z4))), (Z2 : (Z2 : Z8)), NonSplit(32), (Z2 : (Z2 x Z8)),
  (Z4 : Q8), (Z2 : (Z4 x Z4)), (Z8 : Z4), (Z4 : Z8), (Z4 : Z8), NonSplit(32),
  (Z2 x Z16), (Z2 : Z16), D32, QD32, Q32, (Z2 x Z4 x Z4),
  (Z2 x (Z2 : (Z2 x Z4))), (Z2 x (Z4 : Z4)), (Z2 : (Z4 x Z4)), (Z4 x D8),
  (Z4 x Q8), (Z2 : (Z2 x Z2 x Z2 x Z2)), (Z2 : (Z2 x Z2 x Z4)),
  (Z2 : (Z2 x Q8)), (Z2 : (Z2 x Z2 x Z4)), (Z2 : (Z4 x Z4)), NonSplit(32),
  (Z2 : (Z4 x Z4)), (Z2 : (Z4 x Z4)), (Q8 : Z4), (Z2 x Z2 x Z8),
  (Z2 x (Z2 : Z8)), (Z2 : (Z2 x Z8)), (Z2 x D16), (Z2 x QD16), (Z2 x Q16),
  (Z2 : (Z2 x Z8)), (Z2 : (Z2 x D8)), (Z2 : (Z2 x Q8)), (Z2 x Z2 x Z2 x Z4),
  (Z2 x Z2 x D8), (Z2 x Z2 x Q8), (Z2 x (Z2 : (Z2 x Z4))), (Z2 : (Z2 x D8)),
  (Z2 : (Z2 x Q8)), (Z2 x Z2 x Z2 x Z2 x Z2) ]



On Thursday 01 July 2004 11:55, Robert Eckert wrote:
> ---------- Forwarded message ----------
> Date: Thu, 1 Jul 2004 01:25:40 -0400 (EDT)
> From: Robert Eckert <eckert at turing.math.wayne.edu>
> To: Stefan Kohl <kohl at mathematik.uni-stuttgart.de>
> Cc: GAP Support <support at gap-system.org>
> Subject: Re: [GAP Forum] Retrieving group name
>
> On Wed, 30 Jun 2004, Stefan Kohl wrote:
> > Robert Eckert wrote:
> > > This is probably more than you want to know, but...
> > >  For some time I have worked on what a "canonical" naming scheme for a
> > >  Classification of Finite *non*Simple Groups would have to look like.
> >
> > [ ... ]
> >
> > This looks like a larger project --
> >
> > Some questions however (maybe the answers are somewhere hidden in your
> > text):
> >
> > 1. Is there a bijection between your names and the isomorphism types
> >    of finite groups?
>
> That's the plan, at least:  a symbol-string should stand for either an
> impossibility (there exists Z_3 X| Z_2 = D_6 = S_3 but no Z_2 X| Z_3) or a
> group determined up to isomorphism; and each group (finite at least:
> infinites have "self-similar" decompositions like Z = Z * Z_2 or "free
> product" decompositions and maybe phenomena for which this whole language
> is not suitable) should have a unique "canonical" symbol-string naming.
> Problems divide into "ambiguities" (same symbol string for non-isomorphic
> groups, from two series of refinements of the same Type at each step down
> to the same atomics but with alpha/gamma choices that cause different
> effects) and the much less serious "ambivalencies" (as between
>  Z_6 = Z_2 + Z_3, Z_6 = Z_3 + Z_2,
> who really cares?  any arbitrary tie-breaker rule will do).  Ambiguities
> about the choice of gamma I know how to deal with; ambiguous semidirect
> products are more confusing and this remains work in progress.
>
> > 2. If not: for which types of groups or orders of groups are your names
> >    unique, or which invariants do they determine?
>
> "All groups of finite order" is the desired answer.  With certain
> "honorary atomics" like Z, Q, R we can also deal with infinites that are
> "solvable over the finites" (has a subnormal series of inclusions of
> subgroups, i.e. each normal in the next if not necessarily in the whole,
> where each quotient is abelian OR finite).
>
> > 3. Is it algorithmically feasible to determine the name of a given group
> >    according to your naming scheme? If so, for how large / complicate
> > groups?
>
> Very much work in progress.  First approx:  determine whether the group
> has a center by taking commutator-derivation until it goes trivial or
> stops shrinking; if so, try to pull out the center as a direct or ordinary
> left factor:  if ordinary, keep decomposing and note whether carry is
> revealed to be incompletely ordinary at some stage-- there are systematic
> moves that can be made to rectify the decomposition if this happens.  But
> if there is no center, use the first commutator-derived (not the terminal
> stage) as your attempted H to get a semidirect by a cyclic action, or by an
> abelian group of non-interacting actions, and keep decomposing to see if
> one of the actions "does something funny"-- here is where I am groping even
> to pin down what exactly I mean, let alone what to do about it.  The
> actions should fall into inner/central-fixing cases rectifiable to direct
> or ordinary, and wreath/non-wreath actions, plus only a handful of
> exceptionals that need to be tagged "reverse".  The conjecture is that the
> exceptionals only happen with a few "smallish" groups like A_6:  that might
> prove false, but I doubt it because it is those exceptionals and the
> anomalies surrounding them that allow the sporadic simples to arise; so if
> there was a large counterexample, there ought to be a whole new family of
> large sporadics also, and while the Simple Classification Theorem is now
> scattered among hundreds of papers that I doubt any one person has read all
> through, the community seems satisfied that it is correct.  A more likely
> kind of failure for my scheme:  what I think is non-exceptional, the
> wreath/non-wreath, conceals a kind of ambiguity (more than one "wreathlike"
> or more than one "non") that I haven't considered.
>
> To show a small example, the wreath
>   (Z_3 + Z_3) S Z_2
> would proceed algorithmically through the "ordinary" fork; writing the
> elements 0/1/2, 0/1/2, blank/S, the action of S fixes the central {00, 11,
> 22} so I would try that as H and find the quotient is a D_6 = Z_3 X| Z_2
> with, say, {00, 01, 02} as the Z_3 (no carry), and either 01S, which
> carries by
>   01S 01S = 01 10 S^2 = 11
> or 00S, which does not carry but induces carry, as the non-trivial in Z_2.
> This is incompletely ordinary, so it would be kicked over to the
> semidirect fork of the algorithm:  the rectification is to combine the old
> H with the part of T that failed to carry at all to make our new H, the
> elementary-9, and treat the part of T that either carried or induced carry
> as the subgroup acting on it.  Discover "carry-up" and tag it "wreath".
>
>  For cases with a center or a smaller commutator-derived, having chosen a
> tentative H, the T-elements are chosen preferring *independent* elements
> (no power except id falling into H or into the cosets of H using those
> T-elements already chosen) of maximal order, or else the *maximally
> independent* (largest power before it falls in), and if t is chosen,
> also incorporate into T the powers of t as far as independent; this
> trivializes gamma so far as possible.  But for other cases, simple or
> near-simple groups where commutator-derivation does not shrink the group
> at all, take a maximal H: start with an element of maximal order and keep
> appending elements of maximal independence that do not generate the full G
> until you cannot anymore; the T that is appropriate here is constructed by
> different principles, preferring involutions where possible and
> incorporating conjugates rather than powers; if the group is not actually
> simple, decompose as if it were the simple group anyway, and the extra
> factor will have to be detected.
>
> > Depending on the answers to these questions I think it might be *very*
> > desirable to have these names and a corresponding group identification
> > routine available in GAP, and I would recommend that you discuss this
> > with the author of the small groups library, Bettina Eick.
>
> That might be premature at this time; on the other hand, maybe working on
> an implementation would clarify my mind about what the "rules" really need
> to be.
>
> > Another question: How do you suppose the `Affine Monster' to look like,
>
> Like a warthog who can't get a date even from female warthogs.
>
> > and with which kind of methods do you try to establish its existence,
> > i.e. do you use a constructive approach (construct a permutation
> > representation, matrix representation, finite presentation, ...) or a
> > non-constructive one?
>
> Gross framework of the "big lemma":  work in permutation-representation
> terms.  Given an arbitrary finite simple G, choose a maximal subgroup H
> and action on H-cosets is permutational of least possible degree-- unless
> there happens to be a different maximal subgroup of smaller index
> reachable by a different route?  H is a one-point stabilizer: label the
> point standing for H-itself as "point infinity".  Pick a "point 0" and an
> involution t_0 in that coset; now find a "wholly regular" element of H,
> meaning one that has no power short of id that fixes any point but
> "infinity" (no mixing of different lengths in the disjoint-cycle
> structure), and build up to the largest possible wholly-regular subgroup
> (at least containing that cyclic, but as much as you can add and have no
> non-trivial element acting less than freely on the points other than
> infinity)-- unless there isn't even one regular in H that doesn't mix
> cycle lengths?  Start the rectified T as t_0 (moves "infinity" to "0")
> plus its conjugates by the big wholly-regular subgroup (each moving
> "infinity" to a different point); if that reaches all the points we are
> done (as in PSL(2,q) but not in general); else find an independent wholly
> regular element of H moving "0" to one of the points not reached by the
> orbit of the earlier subgroup-- unless that doesn't exist?  Else continue
> adding blocs of conjugates to the transversal until complete.  Regardless
> of what the simple group, you should be able to rectify thus far.
> If, instead of an arbitrary simple group we are given one equipped with a
> canonical decomposition, the rightmost pseudo-group factor will be
> defining S, the "simple core"-- unless all H is solvable?  The
> factors right of that pseudo-group will contain some multi-point
> stabilizing stuff (the "multiplicatives") and what we want to be
> the initial big wholly-regular subgroup (the "additives")-- unless it just
> isn't there?  (For example, in PSL(n,q) the H we have in mind is the
> subgroup of matrices with the bottom row all zeroes except the rightmost
> entry; this breaks down as PSL(n-1,q) which is our S, one new
> multiplicative group, and a column of new additive groups which t_0 is to
> be conjugated by to get us started off).  Then the further regular
> subgroups that suffice to fill out T should be precisely the same ones
> which sufficed to build the pseudogroup for S.  If everything goes
> through, we get diagrammatic relationships and can show how to figure out
> which diagram it is.
>
> The question marks are the places where things could fail, and that should
> mean G isn't really simple, or H really isn't maximal, or S wasn't
> diagrammatic either, or it can mean a different H should be chosen-- but
> you can get two H's pointing their fingers at each other saying "use that
> one instead"; this comes up in the "set-product" case.  I think I can get
> to "if everything was diagrammatic and typical before, it will be again".
> The problem is that I also seem to be finding indications of the converse,
> "if the simple core is weird, there is going to be a weird way of carrying
> it on."  In the alternating groups, this is true:  every one is a base for
> building the next one.  I don't want to prove that for every sporadic
> group there exists a next-larger one, because it doesn't seem to be true,
> and I find it embarrassing to prove falsehoods.  Given a simple core, if
> you are then going to append some intervening factors and a capping
> pseudo-group that closes up as a new simple group, the nature of the
> pseudo-group defining the simple core puts constraints on what this
> continuation has to be; the diagrammatic case imposes some complicated
> constraints (intervening additive and multiplicative factors that tie
> back just so); the alternating groups are certainly unlike most sporadics
> in demanding a very simple constraint, no intervening factors period, old
> simple core maximal in the next simple group; but each sporadic wants
> thus-and-so, blah-blah-blah, lah-di-da, and it is hard to see why the
> constraints would boil down to a contradiction, just "can't be done",
> especially hard to see why this would happen in one case only.
>
> This is not what happens in the "terminal" diagrammatic cases, the E_8,
> F_4, and G_2 exceptionals:  if you add a node you get affine diagrams, and
> what that means for the E_9, F_5, and G_3 groups is that the constraints
> will demand intervening factors which need some more which need some more
> which need...  Let us look at some easier groups to get the picture.  I
> decompose Z as ... * Z_2 * Z_2 * Z_2 (or you can use all Z_10 if you like
> decimal digits better), each bit carrying to the next higher-order,
> indexed 0 to infinity:  but with the restriction that an element of
> Z has all bits 0 past some N, or else all bits 1 (the negatives: in
> base-10, negative 1 would be written all 9's).  This I would write
> asterisk-with-a-bar-over-it Z_2, the bar for "ceiling", as opposed to
> asterisk-hat, for "metric completion", an infinite ordinary product of
> Z_2's indexed 0 to infinity, but without the restriction:  that
> construction makes the p-adics, and it is not isomorphic when you change
> base anymore.  Asterisk-underlined is product of Z_2's indexed minus
> infinity to 0:  this is the lesser Pru"fer group (he called it
> "quasi-cyclic") of fractions whose denominators are all powers of two (not
> isomorphic if you use a different prime), modulo one (no carry out of the
> topmost bit, it just overflows); putting a wedge (upside-down hat) instead
> of bar underneath means no restriction that you get down to a sea of
> zeroes eventually, and this is R/Z, the reals from 0 to 1 (and isomorphic
> if the base is changed); bar over and wedge under is R.
>
>   Similarly you can make various infinite iterations of direct products,
> like the infinite elementary-2; additive Q is a direct product of the
> greater-Pru"fers (bar over and under an asterisk:  fractions, whether
> greater or less than one, whose denominators are powers of p) for each
> prime p; multiplicative positive Q a direct product of an infinite number
> of copies of Z ("logarithms" for the p-factor at each prime p); both with
> the all-but-a-finite-number-trivial restriction.  Semidirect products
> would not seem to admit this kind of iteration, but what the "Affine
> Chevalley" groups ought to look like is some infinite tuple of groups
> joined by operators like we find in the move up from PSL(n,q) to
> PSL(n+1,q), where a column of additive groups acts each on the previous
> until a multiplicative group acts on them all and a pseudo-group wraps it
> up-- except that there is "column" after "column" after "column" in some
> rhythmic pattern, an infinite number of times "before" the pseudogroup.
> It still should be possible to construct a systematic description of what
> kind of infinite tuple constitutes an element of an Affine Chevalley, and
> what the product of two elements is defined as-- not that I feel like
> sitting down and writing out such a description right now!
>
> So, the Monster shouldn't lead to "no continuation possible" but to "no
> continuation can close in a finite number of steps", at least that is my
> hunch.  Besides the Dynkin diagrams there are the H diagrams, using braid
> numbers 5 and 5/2 with Dynkin edge-number D(B) = 4 cos^2 pi(1 - 1/B)
> working out to phi^2 = 2.618... and 2-phi = .382... (for sound reasons
> stemming from the non-integral Dynkin numbers, they support no Lie-algebra
> structures and thus aren't heard of as much); these describe the fivefold
> symmetric polytopes, like my "good friend" H_3 who lives in the
> icosahedron.  You approach H_3 groups which act on a minimum of 12 points
> through the one-point stabilizers with their peculiar actions on 11:  this
> is so strongly reminiscent of the Mathieu groups that there must be a
> connection, although I am damned if I can tell you what it is.  There is
> an affine ~H_4, forked with a central node connected to three others by 1
> (braid-number 3), .382 (5/2), and 2.618 (5) edges:  the affine nature
> indicates the linear dependency between the vectors defining the
> icosahedron and those of Kepler's stella minor figure (12 pentagrams
> joined 5 at a vertex, using the same vertices as the icosahedron, but a
> set of three which would be a triangle in the icosahedron have no edge
> connections here at all).  To make these reflections act independently,
> you have to change the figure into a multi-sheeted Riemann cover,
> festooned with branch points so that a series of moves which ought to
> bring you back home instead leaves you at the analogous place one sheet
> up; this structure is maddeningly confusing, governed by some kind of
> "Affine Mathieu" group that I need to get a grip on.  Then there is an
> affine ~H_5, an unforked chain with 2.618, 1, 1, .382 edges, describing a
> linear dependency among the 10 stellated polytopes that can be inscribed
> in the large 4-dimensional hypericosahedron/hyperdodecahedron polytopes;
> again there is, or should be if I could figure it out, a way of turning
> this into a Riemann cover where paths that should be loops do not bring
> you home.  Inside THIS labyrinth is where the "Minotaur" (my pet name for
> the "Affine Monster") ought to live.  I feel that if I could just write
> down the reiterative description of what the Minotaur is, it would be
> immediately "obvious" not only that it has to be infinite, but that it is
> the Monster's only son.
>
> > Best wishes,
>
>   Bob X
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum

-- 
Markus Pueschel
Research Faculty
Dept. of Electrical and Computer Engineering
Carnegie Mellon University
http://www.ece.cmu.edu/~pueschel