GROUP DECOMPOSITIONS, JORDAN ALGEBRAS, AND ALGORITHMS FOR P-GROUPS by JAMES B. WILSON A DISSERTATION Presented to the Department of Mathematics and the Graduate School of the University of Oregon in partial fulfillment of the requirements for the degree of Doctor of Philosophy June 2008 11 University of Oregon Graduate School Confirmation of Approval and Acceptance of Dissertation prepared by: James Wilson Title: "Group Decompositions, Jordan Algebras, and Algorithms for p-groups" This dissertation has been accepted and approved in partial fulfillment of the requirements for the degree in the Department of Mathematics by: William Kantor, Chairperson, Mathematics Peter Gilkey, Member, Mathematics Charles Wright, Member, Mathematics Jonathan Brundan, Member, Mathematics Eugene Luks, Outside Member, Computer & Information Science and Richard Linton, Vice President for Research and Graduate StudieslDean of the Graduate School for the University of Oregon. June 14,2008 Original approval signatures are on file with the Graduate School and the University of Oregon Libraries. @2008, James B. Wilson. iii iv An Abstract of the Dissertation of James B. Wilson for the degree of Doctor of Philosophy in the Department of Mathematics to be taken June 2008 Title: GROUP DECOMPOSITIONS, JORDAN ALGEBRAS, AND ALGORITHMS FOR P-GROUPS Approved: _ Dr. William M. Kantor Finite p-groups are studied using bilinear methods which lead to using nonassociative rings. There are three main results, two which apply only to p-groups and the third which applies to all groups. First, for finite p-groups P of class 2 and exponent p the following are invariants of fully refined central decompositions of P: the number of members in the decomposition, the multiset of orders of the members, and the multiset of orders of their centers. Unlike for direct product decompositions, Aut P is not always transitive on the set of fully refined central decompositions, and the number of orbits can in fact be any positive integer. The proofs use the standard semi- simple and radical structure of Jordan algebras. These algebras also produce useful criteria for a p-group to be centrally indecomposable. In the second result, an algorithm is given to find a fully refined central decomposition of a finite p-group of class 2. The number of algebraic operations used by the algorithm is bounded by a polynomial in the log of the size of the group. The algorithm uses a Las Vegas probabilistic algorithm to compute the structure of a finite ring and the Las Vegas MeatAxe is also used. However, when pis small, the probabilistic methods can be replaced by deterministic polynomial- time algorithms. The final result is a polynomial time algorithm which, given a group of permutations, matrices, or a polycyclic presentation; returns a Remak decomposition of the group: a fully refined direct decomposition. The method uses group varieties to reduce to the case of p-groups of class 2. Bilinear and ring theory methods are employed there to complete the process. CURRICULUM VITAE NAME OF AUTHOR: James B. Wilson PLACE OF BIRTH: Brisbane, Queensland, Australia DATE OF BIRTH: July 8, 1980 GRADUATE AND UNDERGRADUATE SCHOOLS ATTENDED: University of Oregon, Eugene, Oregon Portland State University, Portland, Oregon DEGREES AWARDED: Doctor of Philosophy, University of Oregon, 2008 Master of Science, University of Oregon, 2004 Bachelor of Science, Portland State University, 2002 AREAS OF SPECIAL INTEREST: Groups, Nonassociative Algebras, Bilinear Maps, Algorithms for Groups and Algebras PROFESSIONAL EXPERIENCE: Graduate Teaching Fellow, University of Oregon, 2002-2008 PUBLICATIONS: J. B. Wilson, Decomposing p-groups via Jordan algebras (submitted), http://arxiv.org/abs/0711.0201. J. B. Wilson, Finding central decompositions of p-groups (submitted), http://arxiv.org/abs/0801.3434. v vi ACKNOWLEDGMENTS I am very grateful to my advisor W. M. Kantor for the liberty and encouragement to work on these problems, the extensive patience to listen to their early (often mistaken) proofs, and the copious notes on previous drafts. In particular, thank you for suggesting the Jordan product for Sym(b). I am also grateful to E. M. Luks and C. R. B. Wright for their extraordinary attention to the ideas contained here. Thanks to all the members of my committee for improving the exposition of this dissertation through your questions and comments. Thanks also to E. I. Zel'manov and H. P. Petersson for advice on Jordan algebras; and to L. Ronyai for discussing the current state of algorithms for associative algebras. This research was supported in part by NSF Grant DMS 0242983. In pursuing this degree God has blessed me with the support of a wonderful wife Karie, and strong friendships with Mark Walsh, Dawn Archey, Laura Hammond, and many others. I thank God and them for their support. I also salute my parents Richard and Laura Wilson, my uncle William Crawford Jr., and my family. They know their roles in this - as do 1. DEDICATION To my wife Karie. vii --------- TABLE OF CONTENTS Chapter viii Page L INTRODUCTION 1 II. DECOMPOSING p-GROUPS VIA JORDAN ALGEBRAS ILl Introduction......... II.2 Background . IL3 Bilinear Maps and p-groups . IIA Adjoint and Self-adjoint Operators. It5 Isometry Orbits of ...L.-decompositions IL6 Semi-refinements and Proof of Theorem II.1.1.(i) . II.7 Unbounded Numbers of Orbits of Central Decompositions II.8 Closing Remarks . III. FINDING CENTRAL DECOMPOSITIONS OF p-GROUPS 2 2 5 12 17 32 40 45 55 57 III,1 III.2 I1I.3 IlIA IIL5 I1I.6 III.7 Introduction . . . . . . . . . . . . . . . . . . . . . . . Background . Reducing Central Decompositions to Orthogonal Decompositions The *-ring of Adjoints of a Bilinear Map Algorithms for *-rings . . Proof of Theorem IIL1.1 Closing Remarks. . ... 57 58 61 65 67 74 75 IV. FINDING DIRECT PRODUCT DECOMPOSITIONS. 78 IV.1 IV.2 IV.3 IVA IV.5 IV.6 Introduction . . . . . . Background . Direct Decompositions Pulling Back Direct Decompositions of Quotient Groups The Remak Decomposition Algorithms Closing Remarks. 78 81 90 95 111 118 BIBLIOGRAPHY . 121 1CHAPTER I INTRODUCTION I present three theorems in three chapters. The central theme of each is the use of bilinear maps and algebras to answer questions about p-groups. This would be unremarkable if stated for bilinear forms and, simple groups or simple algebras. For instance, the work of E. Artin, C. Chevalley, T. A. Springer, and J. Tits uses nondegenerate bilinear forms to explain many of the structures of classical and non-classical groups. On the algebra side the same was done by 1. N. Herstein, 1. L. Kantor, M. Koecher, and N. Jacobson to understand the structure of simple Lie and Jordan algebras. In this work I apply precisely the opposite philosophy. Unlike bilinear forms, bilinear maps have a rich and complicated structure owing partly to the enormous number of non-isometric bilinear maps of any fixed dimensions. There is no hope to classify or broadly study individual isometry types of bilinear maps. My approach uses groups and algebras to study bilinearity, in contrast to the goals of earlier works. Starting with a bilinear map, associate to it a natural associative *-algebra, a Jordan algebra, and a Lie algebra. Also define the group of isometries and conformal maps, just as is done with bilinear forms. Only now the perspective is to use the structure theorems of these algebras and groups to inform us about the structure of bilinear maps. With these tools I will show that bilinear maps have an unexplored "radical and semisimple structure" - where radical here is not the usual radical of a bilinear map. By recognizing this structure and its translation to p-groups it is possible to discover new theorems and algorithms for these groups and other groups. The use of bilinear maps to studying p-groups I believe began with Baer [6], and my use is similar. These methods have lost favor due to the stronger connections between p-groups and nilpotent Lie algebras. However, sometimes it is best to trade a hard problem for p-groups for an easier problem for bilinear maps, rather than an equivalently hard problem for nilpotent Lie algebras. Indeed, the results in this dissertation can be applied also to nilpotent Lie algebras. 2CHAPTER II DECOMPOSING p-GROUPS VIA JORDAN ALGEBRAS ILl Introduction For finite p-groups P of class 2 and exponent p the following are invariants of fully refined central decompositions of P: the number of members in the decomposition, the multiset of orders of the members, and the multiset of orders of their centers. Unlike for direct product decompositions, Aut P is not always transitive on the set of fully refined central decompositions, and the number of orbits can in fact be any positive integer. The proofs use the standard semi-simple and radical structure of Jordan algebras. These algebras also produce useful criteria for a p-group to be centrally indecomposable. A central decomposition of a group G is a set 1t of subgroups in which distinct members commute, and G is generated by 1i but by no proper subset. A group is centrally indecomposable if its only central decomposition consists of the group itself. A central decomposition is fully refined I if it consists of centrally indecomposable subgroups. We prove: Theorem 11.1.1. For p-groups P of class 2 and exponent p, (i) the following are invariants of fully refined central decompositions of P: the number of mem- bers, the multiset of orders of the members, and the multiset of orders of the centers of the members; and (ii) the number of Aut P-orbits acting on the set of fully refined central decompositions can be any positive integer. Central decompositions arise from, and give rise to, central products (cf. Section II.2.1), and hence Theorem II.l.1.(i) is a theorem of Krull-Remak-Schmidt type (cf. [49, (3.3.8)]). That 3theorem states that the multiset of isomorphism types of fully refined direct decompositions (Remak-decompositions) is uniquely determined by the group, and the automorphism group is transitive on the set of Remak-decompositions. Theorem n.1.1.(ii) points out how unrelated the proof of Theorem 11.1.1.(i) is to that of the classical Krull-Remak-Schmidt theorem. Moreover, inductive proofs do not work for central decompositions. For example, a quotient by a member in a central decomposition generally removes the subtle intersections of other factors and so is of little use. Similarly, automorphisms of a member in a central decomposition usually do not extend to automorphisms of the entire group. We conjecture that under the hypotheses of Theorem n.1.l, even the multiset of isomor- phism types of a fully refined central decomposition of P is uniquely determined by P. For details see Section 11.8.1. While the literature on direct decompositions is vast, little appears to have been done for central decompositions. For p-groups, results similar to Theorem n.1.l have concentrated on central decompositions with centrally indecomposable subgroups of rank 2 and 3, with various constraints on their centers [1, 2, 55, 56]. Using entirely different techniques, our setting applies to groups of arbitrary rank at the cost of assuming exponent p. The methods used in this paper involve bilinear maps and non-associative algebras, but not the nilpotent Lie algebras usually associated with p-groups. We introduce a *-algebra and a Jordan algebra in order to study central decompositions. The approach leads to a great many other results for p-groups and introduces a surprising interplay between p-groups, symmetric bilinear forms, and various algebras. Most of these ideas will be developed in subsequent works. As the algebras we use are easily computed, in [60] we provide algorithms for finding fully refined central decompositions and related decompositions - even for p-groups of general class and exponent (including 2-groups). In [63] we prove there are pZn3 /27+Cn2 centrally indecomposable groups of order pn, which is of the same form as the Higman-Sims bound on the total number of groups of order pn [18, 53]. In [63] we also prove that a randomly presented group of order pn is centrally indecomposable, and we characterize various minimal centrally indecomposable p-groups by means of locally finite p-groups, including those p-groups with pI ~ Z~. Finally, in [62] we address central decompositions of 2- groups, p-groups of arbitrary exponent, and p-groups of arbitrary class, by means of an equivalence on p-groups related to the isoclinism of P. Hall [16]. 4II. 1.1 Outline of the Proof Section II.2 contains background and notation for central decompositions of groups and orthogonal decompositions of bilinear maps. Section I1.3 translates p-groups P of class 2 and exponent p into alternating bilinear maps on PIP' induced by commutation. This approach is well-known and appears as early as Baer's work [6] and refined in [28J and [58J; however, such techniques have been upstaged by appealing to various associated Lie algebras of Kaloujnine, Lazard, Mal'cev and others [32J. By contrast, the bilinear approach translates unwieldy central decompositions into natural-looking orthogonal decompositions, and automorphisms into pseudo-isometries (Theorem II.3.6). In Section II.4 we introduce two algebraic invariants of bilinear maps: the associative *- algebra of adjoi~t operators, and the Jordan algebra of self-adjoint operators. The first of these encodes isometries, while the second encodes orthogonal decompositions via sets of pairwise or- thogonal idempotents (Theorem II.4.29). We use these algebras to give criteria for indecomposable bilinear maps and centrally indecomposable p-groups (Corollary I1.4.35 and Theorem I1.4.36). We also prove the first part of Theorem II.l.l.(i) .. In Section II.5 we prove that a certain subgroup of isometries acts on suitable sets of idempotents of our Jordan algebra with the same orbits as the full isometry group. Using the radical theory of Jordan algebras and the classification of finite dimensional simple Jordan algebras we identify the orbits of the isometry group acting on the set of fully refined orthogonal decompositions (and therefore the orbits of CAut p(P') on the set of fully refined central decompositions of P) (Cor- ollary I1.5.16). In Section II.6, semi-refined central decompositions are introduced. These are derived from properties of symmetric bilinear forms and then interpreted in the setting of p-groups, leading to the proof of Theorem I1.l.l.(i). Section I1.7 proves Theorem II.1.1.(ii). We also build families of centrally indecompos- able groups of the types in Theorem II.4.36. These examples are only a sample of the known constructions of this sort and the proofs provided are self-contained versions of broader results in [63J. Section II.8 has concluding remarks. 511.2 Background Unless stated otherwise, all groups, algebras, and vector spaces will be finite and p will be an odd prime. We begin with brief introductions to central products and central decompositions of groups, followed by orthogonal decompositions of bilinear maps. II.2.1 Central Decompositions and Products Let H be a central decomposition of a group G (d. Section ILl). The condition [H, K] = 1 for distinct H, K E H shows that H n (H - {H}) ::; Z(G) for all H E H. Whence, the members of H are normal subgroups of G. Central decompositions can be realized by means of central products. Fix a set H of groups and a subgroup N of ii := I1HE'H H such that N n H = 1 for all H E H. The central product of 1{ with respect to N is ii/N. If H is a central decomposition of a group G, then define 1f: ii....-4 G by (XH)HE'HI-+ fIHE'HXH. Then G 9'! ii/ker1f. These two treatments are equivalent [5, (11.1)]. In an arbitrary central decomposition H of a group G, in general H n K and H n J are distinct, for distinct elements H, K, J E H. Definition 11.2.1. Given a subgroup M ::; G and a central decomposition H ofG, we callH an M -central decomposition if M = H n K for all distinct H, K E H. The associated central product is an M-central product. Every central decomposition induces a Z(G)-central decomposition HZ(G) := {HZ(G) : H E H}. Some authors write HI * ... *H s or HI 0'" 0 H s for a Z(G)-central product. These notations still depend on the given N ::; HI X ... X H s . We require a precise meaning in the following specific case: n n ~~ H 0···0 H = H x '" x H /N . j where N := ((1, ... , X, 1, ... , x-I, 1, ... )11 ::; i < j ::; n, x E Z(H)). (ILl) 611.2.2 Central Decompositions of p-groups of Class 2 and Exponent p Using standard group theory, we show that central decompositions of a finite p-group P of class 2 and exponent p reduce to central decompositions of a subgroup Q where P' = Q' = Z(Q) and P = QZ(P). Furthermore, we show that for our purposes we may consider only Z(Q)-central decompositions (d. Corollary II.2.9). Definition II.2.2. An automorphism

W is a bilinear map, then (0:, &) ~ & is a homomorphism from Isom*(b) into GL(W) with kernel naturally identified with Isom(b). In light of Proposition II.2.10.(ii) we will view Isom(b) as a subgroup of Isom*(b) and Isom*(b)jIsom(b) as a subgroup of GL(W). 11.2.4 J..-Decompositions Definition 11.2.11. Let b: V x V ----> W be a k-bilinear map. (i) A set X of subspaces of V is a J..-decomposition of b if' (a) b(X, Y) = 0 for all distinct X, Y E X and (b) V = (Y) for Y ~ X if, and only if, Y = X. (ii) A subspace X of V is a J..-factor if there is a J..-decomposition X containing X. Furthermore, define X.L := (X - {X}). (iii) We say b is J..-indecomposable if is has only the trivial J..-decomposition {V}. (iv) A l--decomposition X of b is completely refined if bx is l--indecomposable for each X E X (cf. (II.2)). When b is Hermitian it is also reflexive in the sense that b(u, v) 0 if, and only if, b(v,u) = 0, for u,v E V. Also, X.L = {x E V: b(X,x) = O}. Let X be a J..-decomposition of b and take X E X. For each x E X n (X -:- {X}) we know b(x, (X - {X})) = 0 and b(x,X) = 0; thus, b(x, V) = O. Hence, X n (X - {X}) :s; radb. Thus a fully refined l--decomposition is also a direct decomposition of V (and more generally any J..-decomposition, if the bilinear map is non-degenerate.) 11 The pseudo-isometry group. (II.5) acts on the set of all J..-decompositions, but may not be transitive on the set of all fully refined decompositions. This fact can already be seen for symmetric bilinear forms (see Theorem II.5.5). II.2.5 Symmetric Bilinear Forms Various parts of our proofs and examples require some classical facts about symmetric bilinear forms over finite fields. Let K be a finite field and w E K a non-square. By [4, p. 144], every n-dimensional non-degenerate symmetric bilinear K-form is isometric to d : Kn x Kn ---+ K defined by (11.7) where D is In or In- 1 E9 [w]. If n is odd then these two forms are pseudo-isometric, but they are not pseudo-isometric if n is even. If A E GL(n, K) then d(uA, vA) = u(ADAt)vt . The discriminant of d is . (II.B) for any A E GL(n, K) [4, (3.7)]. The discriminant distinguishes the two isometry classes of non- degenerate symmetric bilinear forms of a fixed dimension. Lemma 11.2.12. Let d: K2 x K 2 ---+ K be defined as in (11.7). Ii) If di'cd ~ [1] then ([; ~a]'W) E [,om'Cd), wh're W ~ a' +fi' E K. Iii) If discd ~ {wi th,n ([: ~],w) E hom'Cd) Proof. In both cases ADAt = wD for the given matrix and scalar pair (A, w) and D as in (II.7). 0 Proposition 11.2.13. Let d be as in (11.7). Then (by definition) Isom(d) is the general orthogonal group GO(d). Also, (i) ifn is odd then Isom*(d) = ((a, 1), (sIn, S2) Ia E GO(d), s E KX)i hence, Isom*(d)jIsom(d) ~ (KX?i 12 (ii) if n is even then Isom*(d) = ((0:,1), (sIn' S2), ( W' (see (11.4)), then Grp(a,a) : Grp(b) ----> Grp(b ' ) is (v,w) H (va,wa). By direct computation we verify that Grp(b) is a p-group of class 2 and exponent p with center radb x Wand commutator subgroup 0 x W. Furthermore, Grp is a functor. Compare with [58, Theorem 5.14] and [6, Theorem 2.1]. If

W defined by Plx(

W be an alternating Zp-bilinear map and Pap-group of class 2 and exponent p. 15 (i) There is a natural pseudo-isometry (7,i) from b to b':= Bi(Grp(b)). (ii) Every function f : PIP' ---+ P to a transversal of PIP' in P, with Of = 1 determines an isomorphism Kj otherwise, N(K) = K2. Definition 11.4.8. Let 0 be an associative composition algebra and V be a free left O-module. We call a K -bilinear map d : V x V --> 0 a Hermitian O-form if, for u, v E V and s E 0, it follows that: (i) d(u,v) = d(v,u), and (ii) d(su,v) = sd(u,v) and d(u,sv) = d(u,v)s. The rank of d is the rank of V as a free left O-module. Note that a Hermitian O-form is also a Hermitian K -bilinear map and the usual definitions of (pseudo-)isometries apply. It is most important to note that d(x,x) = d(x,x); hence, d(x,x) E K, for all x E V. Let 0 be an associative composition algebra over K and D E Mn(O) where D = Dt. Then dD(u,v) := uDfi, for u,v E on, determines a Hermitian O-form dD : on X on --> O. Here adjoints f,1* E Adj(dD) can be represented as matrices F, F* E Mn(O) such that: uFDvt = dD(uf,v) = dD(u,v1*) = uD(F*)tvt, Yu,v Eon. Hence, FD = D(F*)t. As D is invertible, Adj(dD) *-isomorphic to Mn(O) with involution defined by F* := DFt D-1 , (II.12) Likewise, if d : V x V --> 0 is a Hermitian O-form and X is an ordered basis of V as a free left O-module, then setting Dxy := d(x, y), for all x, y E X, determines a matrix Din Mn(O), n = lXI, such that D = Dt and the Hermitian O-form given by D is isometric to d. Furthermore, d is non-degenerate if, and only if, D is invertible. So we have: 21 Corollary 11.4.9. Every simple *-algebra is *-isomorphic to Adj(d) for a non-degenerate Hermi- tian C-form d: V x V ----} C. In the cases where C has orthogonal or unitary type we have the usual symmetric and Hermitian forms, respectively. Suppose instead the C = M 2 (K) and that d : V x V ----} C is the non-degenerate Hermitian C-from d(u, v) := uvt , where V = Cn. There is a natural submodule U. of V defined by: Furthermore, d(U, U) ~ K; hence, the restrictiondu: U x U ----} K is a bilinear form. It is easily checked that du is alternating and non-degenerate. The case when C has exchange type is not usually handled as a form but for a uniform treatment we find it convenient. In particular we may state: Definition 11.4.10. Given a non-degenerate Hermitian C-form d: V x V ----} C, an element x E V is non-singular if d(v, v) i=- 0 and dim Cv = dim C. Proposition 11.4.11. Every non-degenerate Hermitian C-form d: V x V ----} C has an orthogonal C -basis X (i. e.: X is a C -basis for V and d(x, y) = 0 if x i=- y, x, Y EX). FUrthermore, every fully refined i.-decomposition of d determines an orthogonal basis and so every i.-indecomposable has rank 1. Proof First we show that there is always a non-singular vector x E V. Suppose otherwise: d(x,x) = 0 for any x E V such that dimCx= dimC. Immediately, d(v,v) = 0 for all v E V and thus -d(v,u) = d(u,v) = d(v,u) for u,v E V. For each u E V, Cd(u, V) + d(V,u)C is a bar-ideal of C. As C is a simple bar-algebra (Theorem II.4.7), Cd(u, V) + d(V,u)C = 0 or C. If Cd(u, V) + d(V,u)C = 0 then Cd(u, V) = 0 and d(V, u)C = 0; hence, u E radd = O. Thus, C = Cd(u, V) + d(V, u)C for all u E V - {O}. We divide into two cases. If C = Cd(u, V) then 1 = d(su, v) for some sEC and v E V. Then 1 = I = d(su, v) = -d(su,v) = -1, so char K = 2, which we exclude. Similarly, d(V,u)C i=- c. 22 Now suppose G =I- Gd(u, V), d(V, u)G. Then Gd(u, V) is a proper ideal of G. By Theo- rem 11.4.7 we see that G = K El1 K with the exchange involution. Without loss of generality, take Gd(u,V) = KEl10. Hence (1,0) = sd(u,v) for some s E G and v E V. Thus, (1,1) = d(su, v) + d(su, v) = d(su, v) - d(su, v) = 0, which is false. Therefore, there exists a non-singular vector x E V. As 0 =I- d(x, x) = d(x, x) it follows that d(x, x) E K X • Then d (v - ~i~::~ x, x) = d(v, x) - d(v,x) d( ) 0 J: V Th' d(v,x) l- h d(v,x) ( d(V,x») hd(x,x) x,x = , lor v E. at IS, v - d(x,x)x EX; ence, v = d(x,x)x + v - d(x,x)x sows that V = Gx + xl-. Since Gx n xl- = 0 it follows that V = Gx El1 xl-. Restrict d to xl- and induct to exhibit an orthogonal basis X for d on xl-. Thus X U {x} is an orthogonal basis of d on V. D Notice in the case of type symplectic type, if {Xl, ... , x n } is an orthogonal G-basis for d, then V = GXI ..1 .. , ..1 Gxw Translating to the associated alternating bilinear form d', the orthogonal basis becomes a hyperbolic basis:U = HI ..1 ... ..1 Hn where each Hi is a hyperbolic line (cf. [4, Definition 3.5]). In the case of exchange type, a natural orthogonal basis is given by {(x,x) : x E X} where X is a K-basis of U and V = U El1 U, U = K n • Corollary II.4.12. IfG does not have orthogonal type then d has an orthonormal G-basis (i.e.: a basis X where d(x, y) = Oxy, for all x, y EX). In particular, d is pseudo-isometric to the G-dot product d : Gn x Gn ---; G where d(u, v) := uii, for all u, v E V. Proof. From Theorem H.4.7, N(G) = K whenever G > K. Therefore if v E V such that d(v, v) =I- 0 then d(v,v) = N(s) = ss for some s E G X • Let u = S-IV so that d(u,u) = s-ld(v,v)S-1 = S-1 N(S)S-l = 1. By Proposition HAll, we have an orthogonal basis X for d. Replace each x E X with S;I X so that d(S;I X, S;I X) = 1 and {S-I X : x E X} is still an orthogonal G-basis. D Proposition 11.4.13. Let d : V x V ---; G be a non-degenerate Hermitian G-form. Then Adj(d) == End V ~ Mn (G) as an algebra, and the following hold: Orthogonal type G = K and Isom(d) = GO(d); Unitary type G = F and Isom(d) = GU(d); Exchange type G = K El1 K, Isom(d) ~ GL(U), V = U El1 U; and· Symplectic type G = M 2(K) and Isom(d) ~ Sp(U), V = U El1 U. 23 Proof. The first two cases are by definition alone. If C = KEEl K then Adjc(d) ~ End U EEl End U with (J EEl g)* = 9 EEl f· Hence, the isometry group is: Isom(d) = {f EEl 9 E GL(U) EEl GL(U) : (J EEl g)(J EEl g)* = 1 EEl I} = {f EEl r 1 : f E GL(U)} ~ GL(U). Finally, if C = M 2 (K) then Adj(d) ~ Adj(d') where d' is the non-degenerate alternating K-bilinear form on U, Remark 11.4.5. Therefore Isom(d) ~ Isom(d') as both are the set of elements defined by E. Proof. (i) Lemma II.4.24 proves the forward direction. 'For the converse, since b(E, F) = 0 it follows that b(ue,v(l- e)) = 0 = b(u(l- e),ve) for all u,v E V. Hence b(ue,v) b(ue,ve + v(l - e)) = b(ue,ve) b(ue + u(l - e),ve) b(u, ve), for all u,v E Vi thus, e E Sym(b). For (ii), note that Sym(b)Ue ~ eAdj(b)e and so Sym(b)Ue is faithfully represented in EndE by restriction. Furthermore, b(uexe,v) = b(u,vexe) for all u,v E E and x E Sym(b). Thus the restriction of Sym(b)Ue is Sym(bE). 0 :From Proposition II.4.26.(i) we see that F = E1- (d. Definition II.2.1L(ii)). Definition 11.4.27. [25, pp.117-118/ Let J be a Jordan algebra. (i) Two idempotents e, f in J are orthogonal if e. f = fUe = eU! = 0 [21, 5.1}. (ii) An idempotent is primitive if it is not the sum of two proper orthogonal idempotents. (iii) A set of idempotents is supplementary if the idempotents are pairwise orthogonal and sum to L (iv) A frame £ of J is a set of primitive pairwise orthogonal idempotents which sum to L Idempotents in special Jordan algebras are idempotents in the associative algebra as well. If e, f E Sym(b) then e and f are orthogonal idempotents in Sym(b) if, and only if, they are 29 orthogonal in Adj(b). To see this, if 0 = e. f = ~(ef + fe) andefe = fUe = 0 then ef = ef + efe = e(ef + fe) = 0 and also fe = O. If ef = 0 = fe then e. f = ~(ef + fe) = 0 (cf.[27, p. 5.4]). However, if e is a primitive idempotent in Sym(b) it need not follow that e is primitive in Adj(b) since there may be orthogonal idempotents in Adj(b) which sum to e but do not lie in Sym(b). The following definition is based on standard uses of idempotents in linear algebra. Definition 11.4.28. Let V be a vector space over k. (i) Let £(Y) be the set of supplementary idempotents parameterizing a (J}-decomposition Y of v. (ii) Let X(F) be the (J}-decomposition arising from a set of supplementary idempotents F of EndV. Theorem 11.4.29. Let X be a (J}-decomposition of V and let £ = £(X). (i) £(X) ~ Sym(b) if, and only if, X is a i.-decomposition of b. (ii) X is a fully refined i.-decomposition if, and only if, £ is a frame. (iii) Let X be a i.-decomposition. If (a, a) E Isom*(b), then Xa = x(£(a,a») and £(a,a) = £(Xa). In particular, Isom*(b) acts on the set of all frames ofSym(b). Proof. Part (i) follows from Proposition II.4.26. Part (ii) follows from observing that an idempotent e E Sym(b) is primitive if, and only if, bVe is i.-indecomposable. For part (iii), if e E £ and x E Vea, then x(e(a,a») = ((xa-1)e)a = xa-1a = x. Therefore V(e(a,a»)=Vea. 0 II.4.7 Linking Central Decompositions, i.-Decompositions, Frames, and Orthogonal Bases: ?iI, XI, £I, and Xd(I)' We use the following notation repeatedly as a means to track the changes from p-groups, to bilinear maps, to *-algebras, to Hermitian forms, and then back. As usual, we assume that P has class 2, exponent p, and pI = Z(P). Let ?i be a fully refined central decomposition of P, X a fully refined i.-decomposition of 30 b := Bi(P), E a frame of J := Sym(b) , A := Adj(b), and I E speco A. Define: Er = {e E E : e tf. I}, Xr = {X EX: e E E(X)r,X = Vel, Hr = {H E H : HP'IP' E Bi(H)r}. (11.15) (11.16) (11.17) Since AII ~ Adj(d(I)) for some non-degenerate Hermitian C-form d := d(I), (Theorem 11.4.15.(iii))), it follows that JI(I n J) ~ Sym(d). Hence, In J is a maximal ideal of J (Theorem 11.4.23.(iii)). Therefore, Er parameterizes a frame EJ/(InJ) := {(I n J) + e : e E Er} of JI(I n J). Furthermore, this gives rise to a fully refined ..i-decomposition Xd(I) := {Ue'T: e E Er} (11.18) (11.19) of d(I) where 'T: All ---+ Adj(d(I)) is a *-isomorphism. Certainly, Xd(I) depends on the choice of 'T but we consider 'T fixed. This influences the definition of address in Section 11.5.1. Proposition 11.4.30. Let H be a fully refined central decomposition of P, X := Bi(H), and E := E(X). The sets Hr, Xr, Er~ EJ/(InJ), and Xd(I) are in bijection. Proof. This follows from Theorem 11.3.6. (ii), Theorem 11.4.29. (ii), Theorem 11.4.23. (iii), and Prop- osition 11.4.11. 0 Proposition 11.4.31. For every fully refined central decomposition H of P with P' = Z(P), the set {Hr : I E speco Adj(Bi(P))} partitions H. Furthermore, IHrl depends only on P and I Especo Adj(Bi(P)). Proof. By Proposition 11.4.30 we know Hr is in bijection with Er for each maximal *-ideal of Adj(Bi(P)). As E is partitioned by Er, as I ranges over the maximal *-ideals of Adj(Bi(P)), it follows that {Hr: I E specoAdj(Bi(P))} partition H. 0 31 II.4.8 All Fully Refined Central Decompositions Have the Same Size We now prove the first part of Theorem II. 1.1. (i) - that fully refined central decompositions of a p-group P of exponent p and class 2 have the same size. Theorem 11.4.32. Let P be a finite p-group of class 2 and exponent p and'H a fully refined central decomposition. Let Q := (IC), IC := 'H - Z(H). Then'H is partitioned into Z(H) U {IC] : I E speco Adj(Bi(Q))}. (11.20) Furthermore, JZ(H)I and IICI are uniquly determined by P, and IHI is uniquely determined by P. Proof. By Lemma 11.2.3 we know P = Q ED A with A S; Z(P) and Q' = pI = Z(Q). Furthermore, JZ(H)I = IAI = [Z(P) : PI]. Therefore, Lemma II.2.5 and Proposition II.4.31 complete the ~~ 0 II.4.9 The Five Classical Indecomposable Families By Theorem II.4.29, a bilinear map b has no proper 1.-decompositions if, and only if, 0 and 1 are the only idempotents of Sym(b). But more can be said if Adj(b) is considered as well: Lemma 11.4.33 (Fitting's Lemma for bilinear maps). If b is 1.-indecomposable then, for every x E Adj(b), T(x) = x + x* is either invertible or nilpotent. In particular, every x E Sym(b) is either invertible or nilpotent. Proof. Set y = x + x* and note yr E Sym(b) for all r E N. By Fitting's lemma there is some r > 0 such that V = imyr ED keryr. By Lemma II.4.24, b(imyr,keryr) = O. So we have a 1.- decomposition of b. Since b is 1.-indecomposable, yr = 0 so that y is nilpotent, or keryr = 0 and im yr = V so that y is invertible. 0 Theorem 11.4.34. [47, Theorem 2/ If (A, *) is a *-algebra over a finite field of odd characteristic such that T(x) is either invertible or nilpotent for each x E A, then AI rad A is an associative composition algebra. Corollary 11.4.35. For a k-bilinear map b the following are equivalent: (i) b is 1.-indecomposable, 32 (ii) Sym(b) has only trivial idempotents, (iii) J / rad J is isomorphic to a field extension of k. (iv) A = Adj(b) has A/radA is isomorphic to an associative composition algebra. Theorem 11.4.36. A p-group P of class 2 and exponent p is centrally indecomposable if, and only if, one of the following holds with G:= CAutP(Z(P))/Op(CAutP(Z(P))): Abelian /PI = p, Orthogonal G S:! O(l,pe) S:! Z2 with Pi' 3, or p = 3 and CAutPoP(P')/Op(CAutPoP(P')) S:! GO±(2, 3e); Exchange IPI i' p and G S:! GL(l,pe) S:! Zpe_I, or Symplectic G S:! Sp(2,pe) ~ SL(2,pe); for some e > O. Proof. This follows from Corollary 11.4.35, Theorem II.4.17 and Theorem II.3.6. o In Section II.7 we demonstrate that with the possible exception of the unitary type, each of these types can occur. 11.5 Isometry Orbits of .i-decompositions In this section we describe the orbits of CAut p(P') in its action on the set of fully refined central decompositions. To do this, we define a computable CAutP(P')-invariant for each fully refined central decomposition called its address. Then we prove that any two fully refined central decompositions with the same address lie in the same orbit. II. 5. 1 Addresses Definition 11.5.1. Let d: V x V -> C be a non-degenerate Hermitian C-form. 33 (i) Given a non-singular x E V (cf. Definition II.4.10), the address of X := Gx is X@:= d(x,x)N(G X), as an element of KX IN(GX). (ii) X@ := {X@ : X E X} (as a multiset indexed by X) for every fully refined i.-decomposition X ofd. From Theorem II.4.7 we know N(G) = K if G > K and therefore the addresses of non-singular points of a non-symmetric non-degenerate Hermitian G-form are all equal to K X • Therefore we ignore this case. However, for non-degenerate symmetric bilinear forms, the address is a coset of (KX)2. Let d : V x V ~ K be a non-degenerate symmetric bilinear form. Fix w E K X - (K X )2. Every address of a non-singular point of V is either [1] := (K X)2 or [w] := W(KX)2. If X is an orthogonal basis of d, then for some °:::; s :::; n, n-s 8 ,-"--., ....---"'-.. X@ = {[I], ... , [1], [w], ... , [w]}, We write (n - s : s) for the address X@. The discriminant of Hermitian G-form d is discd = IT X@ XEX n = dimV. (II.21) as an element of K XIN(GX) (d. (II.8)). In particular, if d is symmetric then discd = [w B]. Otherwise we can regard the discriminant as trivial. Let P be a p-group P of class 2, exponent p, and pI = Z(P). Let 11. be a fully refined central decomposition of P, X := Bi(11.), and £ := £(X). Using the notation of Section II.4.7 and Proposition II.4.30, for each maximal *-ideal I of Adj(Bi(P)), assign the address of 11.1, XI, £1, 34 and £J/(InJ) as the address of Xd(I)' Finally, £@ := ((I,£[@) : IE speco Adj(Bi(P))}, X@:= {(I,X[@): I E specoAdj(Bi(P))}, 1{@ := {(I, 1{[@) : I E speco Adj(Bi(P))}. (II.22) (11.23) (II.24) Remark 11.5.2. Recall that Xd(I) depends on the choice of non-degenerate Hermitian O-form d := d(I) : U x U --> O. Any other choice is pseudo-isometric to d. Suppose that d' : U' X U' --> 0 is pseudo-isometric to d via (a,{3). Let u E U such that d(u,u) E KX (cf. Proposition II.4.11). Then d(u,u){3 = d(ua,ua) = d(ua,ua) = iJd(u,u). (II.25) Hence, {3 = iJi thus, (3 E KX. The affect is that Xd,@{3 = Xd@. Therefore the specific cosets in K XjN(OX) are not significant. The pseudo-isometry invariant of Xd(I)@ is the partition into equal cosets. For finite fields, the notation (n - s : s) records this partition. Proposition 11.5.3. (i) If X is a fully refinedl..-decomposition of band cp E 1som(b) then X@= Xcp@ for all X EX. (ii) If 1{ is a fully refined central decomposition of P and cp E 0 Aut P (P') then B@ = H cp@ for all HE 1{. Proof. (i). Let I E specoAdj(b) and Adj(b)jI ~ Adj(d), d:= d(I) : U x U --> O. By Proposition II.4.3.(ii), 1som(b) maps into 1som(d). Let X E X[ and Ox, x E U, the corresponding member of Xd(I)' The address of X is by definition the address of Ox. As d(x, x) = d(xcp, xcp) it follows that Oxcp@ = Ox@ and Xcp@ = X@. (ii). This follows from (i) and Theorem 11.3.6. 0 We now work towards the converse of Proposition II.5.3. II.5.2 Orbits of Fully Refined l..-decompositions of Non-degenerate Hermitian O-forms The theorems of this section are undoubtedly known, though with different terminology. Lemma 11.5.4. Let d: V x V --> 0 be a non-degenerate Hermitian O-form and X a fully refined 35 i.-decompositions of d. Then, for each cp E Isom(d) there is aTE Isom(d) which is a product of involutions and such that Xcp = XT, for X EX. Proof. If the rank of V is 1 then let T = 1. So assume the rank is greater than 1. By Proposition 11.4.13, we have the four classical groups to consider. The orthogonal groups are generated by reflections so take T := cp. In the exchange, unitary, and symplectic cases, the rank of V excludes the case GF(q)X, GU(l, q) and Sp(2, q). Therefore the relevant symplectic groups are generated by their involutions and again T := cp. In the exchange and unitary cases the involutions generate a normal subgroup N ::::: Isom(d) n SL(V). Therefore cp == J..l (mod N) where J..l is a diagonalizable. Without loss of generality, XJ..l = X, so take T := J..l-lcp E N. 0 Theorem 11.5.5. Let d : V x V -> C be a non-degenerate Hermitian C-form and X and Y fully refined i.-decompositions of d. Then there is an isometry cp of d such that Xcp = Y if, and only if, X@ = Y@. Indeed, if cjJ: ,1'-> Y is a bijection where XcjJ@ = X@ for each X E X, then cp can be taken as a product of involutions where Xcp = XcjJ, for each X EX. Proof. Suppose Xcp = Y for some cp E Isom(d). Given X E X, d(xcp,xcp) = d(x,x) for each x E X; hence, X@ equals Xcp@. Thus, the addresses of X and Y agree. For the converse, suppose we have a bijection cjJ as described above. Fix generators x and Yx for X ='Cx E X and XcjJ = CYx E Y, respectively. By assumption, there is an Sx E CX such that d(x, x) = N(sx)d(yx, Yx). Define cp : V -> V by xcp = SxYx for each X = Cx E X. It follows that d(xcp,xcp) = N(sx)d(yx, Yx) = d(x, x) for all X = Cx E X; thus, cp E Isom(d). Furthermore, Xcp = Y and Xcp = XcjJ. To convert cp into a product of involutions, invoke Lemma II.5.4. 0 We also require the following version of transitivity as well. Theorem 11.5.6. Let d : V x V -> C be a non-degenerate Hermitian C-form. If X, Y E V are non-singular points (Definition II.4.10), then Xcp = Y for some cp E Isom(d) if, and only if, X@=Y@. Proof. If X cp = Y then X@ = Y@. For the reverse direction suppose that X@ = Y@. Since X@discdx-L = discd = Y@discdy-L, it follows that discdx-L = discdyL By (II.7) for the symmetric case and Prop- osition II.4.ll for all other cases, there are orthogonal bases X' of dX-L and Y' of dy-L such 36 that X'@ = {[I], ... , [1], [discdx.L]} and X'@= {[I], ... , [1], [discdy.L]}. Set X = {X}UX' and Y := {Y} U Y'. Then X and Yare fully refined -.i-decompositions of d. Furthermore, X@ = {X@, [1], ... , [1], [discdx.L]} = {Y@,[l], ... ,[l], [discdy.L]} = Y@. Therefore, by Theorem 11.5.5, there is a ep E Isom(d) such that Xr = Y and Xep = Y. 0 II.5.3 Orbits of Frames in Jordan Algebras In this section we determine the orbits of Isom(b) acting on fully refined -.i-decompositions of b, for an arbitrary Hermitian bilinear map b : V x V -; W. To do this we use frames, radicals, and the semi-simple structure of the Jordan algebra Sym(b). We caution that we make frequent use of results from Sections 11.4.5 and II.4.6, at times without specific reference. Suppose X is a fully refined -.i-decomposition of b. By Theorem II.4.29, £ := £(,1') is a frame of Sym(b). We also know that Isom(b) acts on Sym(b) by conjugation (Theorem II.4.20) and that £'P = £(Xep) for each ep E Isom(b) (Theorem II.4.29). Therefore, it suffices to work with the orbits of frames of Sym(b) under the action of Isom(b). To make use of the Jordan algebra we also translate the action of Isom(b) into Jordan automorphisms of Sym(b) in the following way. By Proposition II.4.3.(ii), every isometry ep has the defining property epep* = 1. Hence, ep E Sym(b) n Isom(b) if, and only if, ep2 = 1. Definition 11.5.7. Define Inv(J) = (UX : x E J, x 2 = 1) ::; GL(J) for a special Jordan algebra J. We consider only those Jordan algebras J which are subalgebras or quotient algebras of a special Hermitian Jordan algebra such as Sym(b). Note that if x E J with x2 = 1 then yUx = x-lyx = yX for all y E J. Therefore each element of Inv(J) acts both as a product of U-operators and as conjugation. So Inv(J) is a group of automorphisms of J built from elements of J. Remark 11.5.8. The group Inv(Sym(b)) is not contained in Isom(b) and we are careful to dis- tinguish the action on J := Sym(b) by the two groups as follows: if ep E Isom(b) then write y'P (cf. Proposition II.4.3.(i)), and if ep E Inv(J) then use the usual function notation yep, for y E J. However, Inv(Sym(b)) embeds in Isom(b) by extending Ux f---f x, x E Sym(b), x2 = 1. By Definition II.4.25, if e E J, e2 = e then JUe = eJe is a subalgebra with identity e. 37 Proposition U.5.9. Let e be an idempotent in J. Then Inv(JUe ) embeds in Inv(J) acting as the identity on JU1- e. Proof. It suffices to extend the generators of Inv(JUe ) to J. Let v E JUe with v2 = e. Set u := (l-e)+v E J. As v = vUe = eve it follows that u2 = (1-e)2+(1-e)eve+eve(1-e)+v2 = 1, so Uu E Inv(J). Furthermore, if x E JUe, then xUu = xUeUu = ((I-e) +v)exe((l-e) +v) = xUv . Finally, if x E JU1- e , then xUu = xU1- eUu = ((1 - e) + v)(l - e)x(l - e)((l - e) + v) = x. 0 Lemma 11.5.10. (25, III. 7, Lemma 4] Let N be a nil ideal in J. If N +u E JIN with u2-1 E N, then there is a v E J such that N + u = N + v and v2 = 1. Proposition 11.5.11. (i) Ifcp E Inv(J) then (radJ)cp = radJ and cplJ/radJ E Inv(J/radJ). (ii) Suppose N ::9 J and N is nil (in particular for N S;; rad J). Then for each rj; E Inv(J IN) there is a cp E Inv (J) such that cpl J/N = rj;. Proof. (i) Inv(J) is a subgroup of the automorphism group of J and so maximal inner ideals are mapped to maximal inner ideals and the radical is preserved. Since involutions of J are sent to involutions of J/radJ, it follows that Inv(J)IJ/radJ::; Inv(J/radJ). (ii) By definition Inv(J IN) is generated by the Un for which v is an involution of J IN. For each v, by Lemma II.5.10 there is an involution v E J such that v = v + N. Thus Un = Uv +N = o Lemma U.5.12. Let e, e' E J be orthogonal idempotents. If z E J such that z2 = a and e + z is an idempotent, then there is a v E J such that (i) v2 = 1, (ii) eUv = e + z and (iii) e'Uv = e'-2e'.z+e'Uz . Proof. Let v = 1 - 2e - z. (i). Since e + z = (e + Z)2 = e + ez + ze it follows that z = ez + ze. Hence, v2 = 1 - 4e + 4e2 - 2z + 2ez + 2ze + z2 = 1. For (ii) note that a = z2= ez2 + zez so that zez = o. Thus, (1 - 2e - z)e(l - 2e - z) = ((1 - 2e - z)e)(e(l - 2e - z)) = (e + ze)(e + ez) = e + ez + ze = e + z. 38 So eUv = e + z. Finally for (iii): e'Uv = (1- 2e - z)e'(l - 2e - z) = (e' - ze')(e' - e'z) = e' - 2e'. z + e'Uz . o Lemma 11.5.13. Let N be an ideal in J such that N 2 = O. If & and F are both sets of supple- mentary idempotents of J such that & == F (mod N), then there is

O. By [25, Lemma V.2.2] there is an ideal M of J such that N 2 ~ MeN. Then &

2 then there are distinct X, X' E X with X@ = X'@. By induction on Z := X - {X, X'} we have an isometry r of d(z} which permutes Z. We also induct on S to locate an involution I-" E 1som(d(s}) such that XI-" = X'. Set p = r ffi I-" E 1som(d). Hence, p2 = 1 and permutes X. Moreover, {X EX: Xp = X} = S = {Z E Z : Zr = Z} and discd = X@X'@discd(z} = discd(z}. Therefore, each case of S is satisfied for X with p as it is satisfied for Z with r. Therefore p satisfies (i), (ii), and (iii). For (iv), let 21r - s. First assume s ~ 2. From the induction on Z there is a fully refined ..L-decomposition W of (Z) of address (n - 2 : s - 2) such that (Z, Zr) = (Y n (Z, Zp)) for each Z E Z. If X@ = [w] then set Y = W U {XiX'} to complete (iv). If X@ = [1] then use (rp, w) E 1som*(d(x,x/}) from Lemma II.2.12 and set Y := W U {Xrp, X'rp}. Finally, if s < 2 then take W to have address (n - 2 : s) and define Y := W U {Xrp,X'rp} if X@ = [w], and Y := W U {X, X'} otherwise. 0 Corollary II.6.3. The set of addresses of orthogonal bases of d is { n-c}(n- (c+2k): c+2k): 0 ~ k ~ -2-. where disc d = [wc], c = 0,1. In particular, there are 1 + ln2"cJ addresses. Proof. From Theorem 11.5.2.(iv), there is a fully refined ..L-decomposition of d for each address in the set. By Lemma II.5.1, these are the possible addresses of d. 0 Corollary II.6.4. Let d : V x V -+ K be a non-degenerate symmetric bilinear form with n = dim V and let X and Y be orthogonal bases with addresses (n - s : s) and (n - r : r), respectively. (i) If n is odd then Xrp = Y for some (rp, $) E 1som*(d) if, and only if, s = r. (ii) If n is even then Xrp = Y for some (rp, $) E 1som*(d) if, and only if, s = r or s = n - r. Proof Let Xrp = y. Then as $ E KX, $ == 1 or w (mod (KX )2). If x E X, then X = (x). 42 Thus y@ = X@ep. If ep == 1 (mod (K X)2) then s = r. If ep == w then s = n - 1', and (disc d) [wn ] = II X@ep = II Y@ = discd. XEX YEY So, 2/n. This completes the proof of (i). For the converse, by Theorem II.5.5 it remains only to consider s = n - 1', which means X@ = Y@[w], and from above also n = 2m. By Proposition 11.2.13.(ii) there is a (cp, w) E 1som*(d). Therefore Xcp@ = Y@. By Theorem 11.5.5 there is aTE 1som(d) such that XcpT = y. This completes the proof of (ii). 11.6.2 Semi-refinements o Definition 11.6.5. A bilinear map b : V x V ---* W is .i-semi-indecomposable if it is either .i- indecomposable or b has orthogonal type with a fully refined .i-decomposition {X, Y} such that X@=Y@. A .i-decomposition is semi-refined if it consists of .i-semi-indecomposables and it has no coarser .i-decomposition consisting of .i-semi-indecomposables. Remark 11.6.6. Suppose that b is a .i-semi-indecomposable bilinear map which is not .i-indecom- posable. Then, we have a fully refined .i-decomposition {X, Y} of b with X@ = Y@. By Corollary II.5.17.(ii), this is equivalent to having an isometry cp E 1som(b) in which Xcp = Y. Thus bx is isometric to by. Hence, if c := bx then b is isometric to c .i c. Theorem 11.6.7. Let b be a non-degenerate Hermitian bilinear map. (i) Given a semi-refined .i-decomposition Z and any fully refined .i-decomposition X, there is a fully refined .i-decomposition Y with X@ = Y@ and Z = y[p] := {(Y, Yp) : Y E Y}, where p E 1som(b) is an involution. In particular, IZ/ ;::: IXI/2. (ii) 1som(b) acts transitively on the set of semi-refined .i-decompositions. (iii) Every fully refined .i-decomposition of a bilinear map b determines a semi-refined .i-decomposition (as in (i)). In particular, semi-refined .i-decompositions exist. 43 Proof. (i). The idempotents associated to a semi-indecomposable bz , Z E Z, project to the same simple factor of Adj(b). By Proposition II.4.31, {ZI : I 2. Define b : V x V --- V /\ V by b(u,v) := u/\ v, for all u,v E V. Then b is alternating and Adj(b) ~ k with trivial involution, that is, b is J..-indecomposable of type 1. Proof. Take 9 E Adj(b). We show that 9 is a scalar matrix and thus Adj(b) ~ k. Hence b is J..-indecomposable of type 1 with respect to k. Let V = (el, ... ,en) so that {ei/\ej: 1:S i < j:S n} is a basis of V /\ V. Fix 1:S i,j:S n, 46 i =I- j. We have 1 S. i < j S. n. (1I,28) n n 0= eig 1\ ej - ei 1\ ejg* = Lgis(es 1\ ej) - L gjt(ei 1\ et) s=1 t=1 . n n L gis(es 1\ ej) + (gii - gjj)ei 1\ ej - L gjt(ei 1\ et). s=l,s#i t=l,t#j So we have gis = a for all s =I- i and gjt = a for all t =I- j, 1 S. s, t S. n and furthermore gii = gk As this is done for arbitrary 1 S. i, j S. n, i =I- j, we have gll = g22 = gii for all 2 < i S. n. Finally, g22 = gil = gss = gll so in fact g = gllIn and similarly g* = gllIn . As g was arbitrary, Adj(b) = k. 0 If dim V· == 2 then· V 1\ V ~ k and the k-bilinear map b is simply the non-degenerate alternating k-bilinear form of dimension 2. This is indecomposable of symplectic type (Lemma 11.7.11) and the corresponding group is the extra-special group of order pS and exponent p. Corollary II.7.2. Let V be an IF'q-vector space of dimension n > 2 and let b: V x V -> V 1\ V be defined by b(u, v) = u 1\ v for all u, v E V. Then Grp(b) is centrally indecomposable of orthogonal type (see Section II.3.2). Proof. This follows from Theorem 11.3.6. o When q = p, Grp(b) ~ (al,'" ,an I class 2, exponent p). Note that the smallest example of an orthogonal type group is (ai, a2, as I class 2, exponent p) - the free class 2 exponent p-group of rank 3 and order p6. II. 7.2 Direct Sums and Tensor Products Direct sums and tensor products are two natural ways to construct bilinear maps from others. To use these we must demonstrate that the adjoint algebras of such products are determined by the adjoints of the components. A full account is given in [63] but here we give only the cases required and supply direct computational proofs. 47 Definition II. 7 .3. Let b : V x V ---. Wand b' : V' x V' ---. W' be k-bilinear maps. Let b EEl b' : V EEl V' x V EEl V' ---. W EEl W' be the bilinear map defined by (b EEl b') (u EEl u', v EEl v') = b(u, v) EEl b' (u', v') for all u, v E V and u' ,v' E V'. Proposition II.7.4. Let band b' be two non-degenemte bilinear maps. Then Adj(bEElb') = Adj(b)EEl Adj(b'), where the *-opemtor on the right hand side is componentwise. Hence also Sym(b EEl b') = Sym(b) EEl Sym(b'). Proof Evidently Adj(b) EEl Adj(b') :::; Adj(bEElb'). For the reverse, let f E Adj(bEElb') E End(VEElV'). Given u, v E V, v' E V', take (uEElO)f = xEElx' and (vEElv')f = yEEly' for some xEElx', yEEly' E VEElV'. It follows that b(x, v) EEl b' (x', v') = (b EEl b')( (u EEl O)f, v EEl v') = (b EEl b')(u EEl 0, (v EEl v')f*) = b(u, y) EEl b'(O, y') = b(u, y) EEl O. Therefore b'(x', v') = 0 for all v' E V'. So x' E radb' = O. Thus (u EEl 0)/ E V EEl 0 for all u E V. Similarly (0 EEl v')f E 0 EEl V'. So f E (End V) EEl (End V'). Let / = 9 EEl hand f* = g* EEl h* for g, g* E End V and h, h* E End V'. It follows that b(ug, v) EEl 0 = b(ug, v) EEl b' (u', 0) = (b EEl b')( (u EEl u')f, v EEl 0) = (b EEl b')(u EEl u', (v EEl O)f*) = b(u, vg*) EEl b'(u', 0). Therefore 9 E Adj(b) and similarly h E Adj(b'). So f E Adj(b) EEl Adj(b'). o Given two bilinear maps b : V x V ---. Wand b' : V' x V' ---. W' we induce a multi-linear map (b x b') : V x V' x V X V' ---. W 0 W' defined by: (b0b')(u,u',v,v'):= b(u,v) 0b'(u',v'), Vu,v E V,u',v' E V'. (11.29) Let W denote the induced linear map V 0 V' 0 V 0 V' ---. W 0 W', With this notation we give: 48 Definition 11.7.5. Let b 0 b ' : V 0 V' X V 0 V' ---. W 0 W' be the restriction of W to V 0 V' x V 0 V', where b : V x V ---. Wand b ' : V' x V' ---. W' are bilinear maps. Evidently, b0 b ' is bilinear. Using tensor products and the following obvious result, we can convert symmetric bilinear maps to alternating bilinear maps. Proposition 11.7.6. Let b : U x U ---. Wand c : V x V ---. X be Hermitian maps over k with involutions () and r, respectively. Then b0 c is Hermitian with involution () 0 r. In particular, the tensor of two symmetric bilinear maps is symmetric, the tensor of a symmetric and an alternating bilinear map is alternating, and the tensor of two alternating bilinear maps is symmetric. Proposition 11.7.7. Let d: U x U ---. C be a non-degenerate Hermitian C-form with k = {x E C : x = x} and let b ' : V x V ---. W be a k-bilinear map. Then Adj(d 0 b) = Adj(d) 0 Adj(b) and Sym(d 0 b) = Sym(d) 0 Sym(b). Proof. Clearly Adj(d) 0 Adj(b) ~ Adj(d 0 b). For the reverse inclusion, let X be an orthogonal basis of d and £ = £(X). Take gE Adj(d 0 b). We show that 9 E Adj(d) 0 Adj(b). If x, Y E X with associated idempotents e, f E £, then (e 01)g(l 01) restricts to (x) 0 V ---. (y) 0 V, so there is a gx,y : V ---. V defined by vgx,y = Vi, where (x 0 v)(e 01)g(l 01) = y 0 Vi. Let (x,y) be the transposition interchanging x and y and identity on X - {x,y}, treated as an element of End U = Adj(d). Set ex,y = e(x, y)f. Thus, (e 01)g(l 01) = ex,y 0 gx,y. Since 9 = (2: e 01) 9 (2: f 01) eEt: fEt: it suffices to prove that gx,y E Adj(b). = 2: (e 01)g(l 01) = 2: ex,y 0 gx,y, e,fEt: x,yEA' As (e 01)g(l 01) E Adj(d 0 b) with ((e 01)g(l 01))* = (I 01)g*(e 01) it follows that: 10 b(v(d(y, y)gx,y), Vi) = d(y, y) 0 b(vgx,y, Vi) = (d 0 b)((x 0 v)(e 01)g(l 01), y 0 Vi) = (d 0 b)(x 0 v, (y 0 v')(1 01)g*(e 01)) = d(x, x) 0 b(v, Vig;,x) = 1 0 b(v, Vi (d(x, x)g;,x)). Notice we have used the fact that d(x,x),d(y,y) E k X and that the tensor product is taken over 49 k. Therefore b(vgx,y, v') = ~t~:~~b(v,v'g;,x) for all v,v' E V. Hence gx,y E Adj(b) with adjoint ~t~:~~g;,x. This completes the proof. 0 It can be shown that Adj(bI8lc) = Adj(b) I8lAdj(c) for any two bilinear maps band c [63]. II. 7.3 Proof of Theorem II.1.1.(ii) The best known examples of central products are the extra-special p-groups of exponent p n A sociated associative composition algebra e:= Adj(Bi(H))j rad Adj(Bi(H)) (d. Theorem IIA.36). n . ~ Recall that K := {x E e : x = x} is a field (d. Definition II.4.6). Set P := H 0'" 0 Hand n n b := Bi(H o· ~. 0 H}. As in Example 11.3.7, b = Bi(H) 1. .~. 1. Bi(H)' which we can express com- pactly as b = d I8lK Bi(H), where d : Kn x Kn -> K is the usual dot product d(u,v) := uvt , u,v E Kn. Hence, by Proposition 11.7.7, it follows that Adj(b) = Adj(d) I8lK Adj(Bi(H)) and thus Adj(b)jradAdj(b) ~ Adj(d) I8lK e. Yet, Adj(d) I8lK e ~ Adj(d'), where d' : en x en -> e is defined by d' (u, v) := uiJt , for u, v E en. If e > K then Corollary 11.5.16 proves that all fully refined central decompositions are conjugate under automorphisms. We now demonstrate that the same is not generally possible with orthogonal type. Lemma 11.7.8. Let H = (X) be a centrally indecomposable p-group of orthogonal type over JFq n ~ with X a minimal generating set of H. Set P := H 0'" 0 H and let 1io = {HI,"" Hn } be the canonical central decomposition given by the central product, so that Hi = (Xi: x E X) where Xi denotes x in the i-th component. Let w = a 2 + (32 E Zp be a non-square. If 0:::; m :::; nj2 then define where 50 for I ::; j ::; m. Then every member of Hm is isomorphic to Hand Hm is a fully refined central decompositions of P with address (n - 2m: 2m), for I ::; m ::; n/2. Proof As X is a minimal generating set of H, if x, y E X with Z(H)x = Z(H)y then x = y. n ~ Therefore, X x ... x X is mapped injectively into P via the homomorphism IT : ITHE1i H ~ P described in Section 11.2.1. This makes the groups Hi, K 2j- 1 , and K 2j well-defined, for each I ::; i ::; n and I ::; j ::; n/2. Furthermore, Hi 9:! H for each I ::; i ::; nand Ho is a fully refined central decomposition of P. Set Xi = Hi/HI = HiP'/P', W = P' = HI, I::; i::; n. Also set Lj := (H2j-l,H2j) = (K2j-l,K2j), I ::; j ::; n/2. Then Lj/Lj = X 2j- 1 EB X 2j and blLi/Lj is b 1.. b where b = Bi(H). Recall that Bi(P) = d0b where d: kn xkn ~ k is the dot product and X := Bi(Ho) = {Xi: I ::; i ::; n} is a fully refined 1..-decomposition of Bi(P). As Adj(Bi(P)) = Adj(d) 0 Adj(Bi(H)) 9:! Adj(d), it follows that Xd = {Yb ... , Yn } is fully refined 1..-decomposition of d. In fact, the implied isomorphism Adj(Bi(P)) to Adj(d) maps f 0 1 ~ f, so £(X) is sent to the canonical frame {Diag{l, O, ... }, ... , Diag{... , 0, I}} of Adj(d). So, Ho@ = Xd@ = (n: 0). Define ( A) ( [0:IX2i_l 1. Define the k-bilinear map b: (k EB V) x (k EB V) -7 V by Then b is alternating and b(a EB u,,B EB v) := av - ,Bu. (11.30) h ] : hE hom(k, V),a,,B E k}' ,Blv where the multiplication and the action on k EB V is interpreted as matrix multiplication and where the involution is defined by [ alk h] * ._ [,Bolk O. ,Blv -h] alv In particular, Adj(b)j rad Adj(b) 9"! k EB k with the exchange involution and the radical is Thus b is .i-indecomposable of exchange type. Proof. It is easily checked that e := lk EB Ov, f ;= Ok EB Iv E End(k EB V) are both in Adj(b) and furthermore e* = f, e2 = e, P::= f. Fix 9 E Adj(b). Then ege, egf, fge and fgf lie in Adj(b). Let u, v E V be linearly independent. Since (0 EB u)fge = A EB 0 and (0 EB v)fg*e = rEB 0 for some A, r E k, it follows that AV = b(A EB 0, 0 EB v) = b((O EB u)g, 0 EB v) = b(O EB u, (0 EB v)g*) = b(O EB u, r EB 0) = -ru. However, u and 11 are linearly independent, and hence A = 0 = r so fge = 0 = fg*e. 54 Next let (1 EB O)ege = a EB 0 and (0 EB u)fg* f = 0 EB v for some a E k and v E V. Then au = b(a EB 0, 0 EB u) = b((l EB O)ege, 0 EB u) = b(l EB 0, (0 EB u)g*) = b(l EB 0, 0 EB v) = v. Thus fg* f = 0 EB a1 V where ege = a1k EB Ov. Setting (0 EB u)fgf = 0 EB v and (1 EB O)eg*e = ,8 EB 0 we similarly find fgf = 0 EB ,81v where eg*e =,8h EB Ov. Finally, set (1 EB O)egf = 0 EB u and (1 EB O)eg* f = 0 EB v. Then -u = b(O EB u, 1 EB 0) = b( (1 EB O)egf, 1 EB 0) = b(l EB 0, (1 EB O)eg* f) = b(l EB 0, 0 EB v) = v. So egf is induced by a k-linear map h: k -> V and eg* f is induced by -h. o Corollary II.7.14. Let b: (IB'q EBIB'~) x (IB'q EBIB'~) -> IB'~ be as in (11.30) with n > 1. Then Grp(b) is centrally indecomposable of exchange type. Proof This follows from Theorem II.3.6. o If n = 1 then b is simply the non-degenerate alternating bilinear k-form of dimension 2. The smallest example of a p-group with exchange type is in fact of order p5 with rank 3. We can use this example as evidence that the radicals accounted for in Section 11.5.3 do arise for the setting of p-groups. We emphasize that instances of non-trivial radicals are known in far more general settings than .i-indecomposable bilinear maps of exchange type. The radical in of Adj(b), for b as in (II.30), intersects Sym(b) trivially. However, if we define c : (k EB V) x (k EB V) -> V by c(a EB u,,8 EB v) := av + ,8u, 'Va,,8, E k,u,v E V; (II.31) then Adj(c)jradAdj(c) ~ k EB k with the exchange involution. Here radAdj(c) :::; Sym(c). To make this example alternating we may simply tensor by the alternating bilinear map from Lemma II.7.I. To further make a .i-decomposable bilinear map we may tensor with a dot-product. By Proposition II.7.7, the result has a non-trivial radical in Sym(b). 55 H.8 Closing Remarks II. 8.1 Conjecture on Uniqueness of Fully Refined Central Decompositions It remains open whether or not the multiset of isomorphism types of fully refined central decompositions of a p-group P of class 2 and exponent p is uniquely determined. It suffices to answer the following: Let Hand K be centrally indecomposable p-groups of class 2, exponent p, and of orthogonal type. Is it true that whenever H 0 H ~ K 0 K then H ~ K? We conjecture this is true. Because such groups involve symmetric bilinear forms, it is possible that a solution will divide along the congruence of p modulo 4. Some evidence of this has been uncovered while attempting to develop counter-examples. It appears that a counter-example would have order at least 530 . II. 8.2 Further directions The condition that an endomorphism f E End V lies in Adj(b) (or Sym(b)) is determined by a system of linear equations. This is the source of polynomial time algorithms for computing central decompositions of p-groups found in [60]. In contrast, the equations to determine if f E Isom(b) or Isom*(b) (and hence to determine the automorphism group of a p-group) are quadratic and generally difficult to solve. Our theorems apply (at least over finite fields) to central decompositions of class 2 nilpotent Lie algebras. See also [3] and [9, pp. 608-609]. II. 8. 3 Other fields The use of finite fields removed the need to consider Hermitian forms over non-commutative division rings in the classification of *-simple algebras, and consequently also the related simple Jordan algebras (Theorem 11.4.15 and Theorem II.4.23); therefore, this assumption affects Section II.5.2. Furthermore, as finite fields are separable, we are able to apply Taft's *-algebra version of the Wedderburn Principal theorem (Theorem II.4.16) in proving Theorem II.4.36. Evidently our proofs apply also to bilinear maps over algebraically closed fields of characteristic not 2. 56 II. 8.4 2-gro71,pS of exponent 4 The omission of 2-groups of exponent 4 in the proof of Theorem II.3.6 can be relaxed [60]. The known obstacles for 2-groups of class 2 and exponent 4 derive from the usual complications of symmetric bilinear forms in characteristic 2. We are presently investigating whether or not these are indeed the only limitations. 57 CHAPTER III FINDING CENTRAL DECOMPOSITIONS OF p-GROUPS IIL1 Introduction An algorithm is given to find a fully refined central decomposition of a finite p-group of class 2. The number of algebraic operations used by the algorithm is bounded by a polynomial in the log of the size of the group. The algorithm uses a Las Vegas probabilistic algorithm to compute the structure of a finite ring and the Las Vegas MeatAxe is also used. However, when p is small, the probabilistic methods can be replaced by deterministic polynomial time algorithms. A set 7-{ of subgroups of a group G is a central decomposition of G if 7-{ generates G but no proper subset does, and distinct members of 7-{ commute. We say that G is centrally indecomposable if it has only the trivial central decomposition. A fully refined central decomposition of G is a central decomposition consisting of centrally indecomposable groups. Such decompositions arise from to central products in which the centers of the factors need not be the same. For computational purposes, we assume groups are input and output via generators in a useful computational representation, such as a set of permutations, a set of matrices, or a polycyclic presentation (see Section IIl.2.1). We prove: Theorem IILl.l. Assuming a discrete log oracle module p, there is a Las Vegas polynomial time· algorithm which, given a p-group P of class 2, returns a fully refined central decomposition. The algorithm uses in O(10g6[P : PI]) time. When p ::; loge IPI, for some constant c, there is also a deterministic polynomial time algorithm for the same task. The discrete log oracle in our algorithm is unavoidable (Proposition IlL7.1). Although Theorem IlL1.1 concerns groups, most of the work of the algorithm is concentrated on computing the semisimple and radical structure of certain finite rings. Our algorithm introduces methods to compute the structure of *-rings and constructive recognition of simple *-algebras. 58 At a high level, the algorithm proceeds by passing from P to a related bilinear map b; and it is shown that central decompositions of P correspond to orthogonal decompositions of b, see Proposition III.3.1 and Theorem III.3.2. To find a fully refined orthogonal decomposition of b, a ring with involution (Le. a *-'T'ing) Adj(b) is introduced and shown to parameterize orthogonal decompositions of b via sets of suitable idempotents; see Corollary III.4.3. In Section III.5 we find such sets of idempotents using the semisimple and radical structure of Adj(b). This structure can be computed efficiently by reducing to rings of characteristic p and applying the algorithms of Ronyai, Friedl, and Ivanyos for finite /Zp-algebras [51, 22, 24]. This stage uses a Las Vegas polynomial time algorithm for factoring polynomials over finite fields of characteristic p, such as the methods of Berlekamp or Cantor-Zassenhaus [57, Chapter 14]. We select [22J as the specific approach to compute the structure of the rings we encounter. This leads us to use of the Las Vegas MeatAxe [21, 23J in one stage of our algorithm, d. Theorem III.5.3. However, for a deterministic algorithm (for small p), both of these Las Vegas algorithms can be avoided (Section III.7.2). Having found a fully refined orthogonal decomposition of b we convert this to a fully refined central decomposition of P using straightforward group theory (Corollary III.3.4). The methods of Theorem III.!.1 took root in [59J where central decompositions of p-groups P of class 2 and exponent p were studied. There the *-ring Adj(b) and its associated Jordan algebra Sym(b) were used to describe the Aut P-orbits of the set of fully refined central decompositions of P. Here, the algorithms apply in all exponents and include 2-groups. A result in a different direction is the development of efficient algorithms to find direct product decomposition not only of p-groups, but general groups [61J. That work illustrates how decompositions of p-groups of arbitrary class can be reduced to the case of p-groups of class 2, where once again bilinear and ring theory methods are introduced to solve the problem. III.2 Background Throughout this work we assume p is a prime. Unless otherwise obvious, all our groups, rings, modules, and algebras (Le.: rings over a field) are finite. All our rings are associative and unital. We express all abelian groups additively and refrain from indicating this elsewhere. We use .it. U B for the disjoint union of sets A and B, and A - B for the complement of 59 AnB in A. We measure the efficiency of our algorithms by bounding the total number of algebraic operations (in a group, module, or ring) by a polynomial in the size of the iriput, roughly log IFI. The probabilistic aspects of our algorithm are of Las Vegas type, which means they return correct result but with probability c > 0 they may fail to return in the alloted number of steps. III. 2.1 Representing Groups for Computation We assume throughout that P is a finite p-group for a known prime p. We allow P to be input by various means including via a polycyclic presentation, as a permutation group, or as a matrix group [20, Section 3.:l.J. In all cases we assume that P is specified with generators; a method to multiply, invert, and test equality of elements in P; and a method to test if an element 9 E P lies in a subgroup (T), where T ~ P. That is, we may consider P to be a black-box group with a membership test oracle [20, Section 3.2J. For large primes p, membership testing already assumes an instance of the discrete log problem (d. Section III.7.1). We count each of these tasks as a single algebraic operation though we are mindful that each requires more than constant time. The assumptions on P give rise to deterministic algorithms which use a polynomial number of group operations and which: find I(T) I for any T ~ P; find generators for the normal closure (TG) of the subgroup (T), T ~ Pj find generators for the commutator subgroup pI of Pj and find generators for the center Z(P) of P [20, Section 3.3J. Remark III.2.1. (i) Though in practice most p-groups are input by polycyclic presentations, the current methods to multiply in such groups, and to test membership, have exponential complexity (even when p = 2,3) within the collection process [35, p. 670J. (ii) Permutation groups use fast multiplication and membership testing, but various p-groups have no small degree faithful permutation representations [45, Example 1.1]. (iii) For matrix p-groups, multiplication is efficient and membership testing can be done if p is small or if p is the characteristic of the ground field [38, Theorem 3.2J. III.2.2 Abelian p-groups, Bases, Effective Homomorphisms, and Solving Systems of Equations A basis of a finite abelian p-group V is a subset X of V such that V = EI1xEx (x). Every basis of V gives a natural isomorphism to Zpel E!1 ••. E!1 Zpes for el :::; ... :::; es E Z+. Operating in the latter representation is preferable to V's original representation and we assume all abelian 60 groups are handled in this way. Each endomorphism f of V can be represented by an integer matrix F = [Fij ] such that pej-e i Wij, 1 ::; i ::; j ::; s, and furthermore, every such matrix induces an endomorphism of V (with respect to X) [19, Theorem 3.3]. We have need in various places to apply homomorphisms and isomorphisms between finite abelian p-groups, rings, and algebras. We say a homomorphism is effective when it can be evaluated efficiently - for instance with the same cost as matrix multiplication - and a coset representative for the preimage of a point in the codomain can also be found efficiently. This means that effective isomorphisms are easily evaluated and inverted. Suppose we have a system of Zpe linear equations with solutions in· a Zpe.,module V. There are efficient deterministic methods to solve for a basis of the solution space of the system [39, Theorem 8.3]; however, it is essential to note that for large p, this process assumes a discrete log oracle of p and we must do the same. For simplicity, we use the usual cubic polynomial-time methods of Gaussian elimination and traditional matrix multiplication. III.2.3 Bilinear Maps, -i-decompositions, and Isometry A Zpe-bilinear map b: V x V --f W is a function of Zpe-modules V and W where b(su + u', tv + v') = stb(u, v) + sb(u, v') + tb(u', v) + b(u', v'), (III.1) for each u, u', v, v' E V and s, t E Zpe. A -i-decomposition of b is a decomposition V of V into a direct sum of submodules which are pairwise orthogonal relative to b, i.e. b(X, Y) = 0 for distinct X,YEV. Let X and Z be ordered bases of V and W respectively. We define B~V E Zpe by Set = L LsxtyB~Vz, x,YEX zEZ (III.2) B - ~B(z)xy - L...J xy z, zEZ Vx,y E X; so that B = [Bxy]x,YEX is an n x n-matrix with entries in W, where n = IXI. Writing the elements 61 of V as row vectors with entries in Zpe with respect to the basis X we can then write: b(u, v) = uBvt , 'Vu,v E V. (111.3) Take j, g E End V represented as matrices F and G with respect to the basis X above. Define FBand BGt by the usual matrix multiplication, but notice the results are matrices with entries in W. Evidently, (F + G)B = FB + GB, F(GB) = (FG)B, and similarly for the action on the right. The significance of these operations is seen by their relation to b: b(uj,v) = uFBvt and b(u,vg) = uBGtv\ for all u,v E V. (IlIA) An isometry between two bilinear maps b : V x V --. Wand b' : V' x V' --. W is an isomorphism 0: : V --. V' such that b' (uo:, vo:) = b(u, v) for all u, v E V. Evidently, isometries map -i-decompositions of b to -i-decomposition of b'. Finally, we call a bilinear map Hermitian if there is () E GL(W) of order at most 2 such that b(u,v) = b(v,u)(), 'Vu,v E V. (111.5) This meaning of Hermitian includes the usual symmetric, b(u, v) = b(v,u); and skew symmetric, b(u, v) = -bev, u) flavors of bilinear maps. If W = (b(u, v) : u, v E V) then () is uniquely determined by b and so in that case we make no effort to specify () explicitly. 111.2.4 Rings All our rings will have characteristic a power of p and so they are input with a generating set. Furthermore, each of our rings will be represented in End V for some abelian p-group V and thus multiplication is done by the usual matrix multiplication. I1L3, Reducing Central Decompositions to Orthogonal Decompositions , " i In this section we reduce the problem of finding a central decomposition of a p-group of class 2 to the related problem of finding a -i-decomposition of an associated bilinear map. 62 III.3.l Bilinear Maps and p-groups Let P be a p-group of class 2 and pi ::; M ::; Z(P). Associated to P are various bilinear maps b := Bi(P, M) defined by b : P/M x P/M -> pi where b(Mx, My) := [x, y], for each x, yEP. We will express the operations in P /M, pi, and b additively. Notice that b is alternating and skew-symmetric: b(Mx,Mx) = 0 and b(Mx,My) = -b(My,Mx) for all x,y E P. III. 3. 2 Central Decompositions from Orthogonal Decompositions We recall some ideas from [59, Section 4] involving class 2 and exponent p and modify them to p-groups P of class 2 of general exponent, including 2-groups. Let 1{ be a set of subgroups of P. Given a normal subgroup M of P we define: 'HM:= {HM: H E 'H} - {M}, 'HM/M := {HM/M : H E 'H} - {M/M}. (IlL6) (III.7) A central decomposition 'H is an M -central decomposition if H n ('H - {H}) ::; M for each H E 'H. We may assume that M ::; Z(P) as every central decomposition of P is a Z(P)-central decompo- sition. Given an M -central decomposition 'H, it follows that 'HM/ M is a direct decomposition of P/M. Suppose that V is a direct decomposition of P/M. Define 'H(V) := {H::; P: M::; H,H/M E V}. Note that V and 'H(V) are in a natural bijection.. Proposition 111.3.1. Let P be a p-group of class 2, pi::; M ::; Z(P), and b:= Bi(P, M). (i) If'H is an M -central decomposition of P then 'HM/ M is a .l-decomposition of b. (IlL8) (ii) IfV is a .l-decomposition of b then 'H(V) is an M -central decomposition of P where 'H(V)M = 'H(V) and 'H(V)/M = V. Proof. (i). If 'H is an M-centraldecomposition of P then 'HM/M is a direct decomposition of V := P/M. Furthermore, if Hand K are distinct members of 'H then [H, K] = 1, which proves that b(HM/M, KM/M) = O. Thus, 'HM/M is a .l-decomposition of b. 63 (ii). Let V be a ..i-decomposition of b and set K := H(V). By definition, K = KM and KIM = V, so that K n (K - {K}) = M for all K E K. Therefore, it remains to show that K is a central decomposition of P. As V i= 0 it follows that K i= 0. Furthermore, V = (V) so P = (K, M) = (K), as M ::; K for any K E K. Since K is in bijection with V, if:J is a proper subset of K then :JIM is a proper subset of V and as :JIM does not generate V it follows that :J does not generate P. Finally, if Hand K are distinct members of K then 0 = b(HIM,KIM) = [H,K]. Thus, K is a central decomposition of P. 0 Theorem III.3.2. If P is a p-group of class 2, then P is centrally indecomposable if, and only if, Bi(P, Z(P)) is ..i-indecomposable and Z(P) ::; iI?(P). Proof Assume that P is centrally indecomposable. Let V be a ..i-decomposition of Bi(P, Z(P)). By Proposition III.3.1.(ii), H(V) is a central decomposition of P and therefore H(V) = {Pl. Hence, V = H(V)IZ(P) = {PIZ(P)}. As V was an arbitrary ..i-decomposition of Bi(P, Z(P)), it follows that Bi(P, Z(P)) is ..i-indecomposable. Next let iI?(P) ::; Q ::; P be such that PliI?(P) = QliI?(P) EEl Z(P)iI?(P)/iI?(P) as Zp-vector spaces. Set 11. = {Q,Z(P)}. Clearly [Q,Z(P)] = 1 and P is generated by H. Therefore, 11. contains a subset which is a central decomposition of P. As P is centrally indecomposable and P i= Z(P), it follows that P = Q, and so 1 = Z(P)iI?(P)/iI?(P) , which proves that Z(P) ::; iI?(P). For the reverse direction we assume that Bi{P, Z(P)) is ..i-indecomposable and that Z(P) ::; iI?(P). Let H be a central decomposition of P. By Proposition III.3.1.(i) we know HZ(P)IZ(P) is a ..i-decomposition of Bi(P, Z(P)). Thus, HZ(P)IZ(P) = {PIZ(P)} so that HZ(P) = {Pl. Hence, for all H E H, either H ::; Z(P) or HZ(P) = P. As Z(P) ::; iI?(P) < P, it follows that at least one H E H is not contained in Z(P) and furthermore, P = HZ(P) = H as Z(P) consists of non-generators. Since no proper subset of H generates P and P E 11., it follows that 11. = {Pl. Since 11. was an arbitrary central decomposition of P it follows that P is centrally indecomposable. 0 Proposition III.3.3. Suppose Pis ap-group of class 2 such that Bi(P, Z(P)) is ..i-indecomposable. Then (i) every central decomposition of P has exactly one nonabelian member, and 64 (ii) there is deterministic algorithm using O(10g4[P : Pi]) algebraic operations which returns a nonabelian centrally indecomposable group Q such that P = Q or {Q, Z(P)} is a central decomposition of P. Proof. (i). Let H be a central decomposition of P. Since P =I- Z(P) and Bi(P, Z(P)) is 1.- indecomposable, there is a nonabelian H E 'H and HZ(P) = {P} proves that P = HZ(P). If K E H - {H} then [K,Pj = [K,HZ(P)] = [K,H] = 1, since distinct members of'H commute. Thus K :<::; Z(P), which proves that H is the only nonabelian group in H. (ii). If Z(P) :<::; (P) then the algorithm returns P. Otherwise, compute generators for a vector space complement Q/(P) to Z(P)(P)/(P) in P/(P), (P) :s; Q < P. Recurse with Q in the role of P and return the result of this recursive call. If we find that Z(P) :<::; (P) then Theorem III.3.2 proves that P is centrally indecom- posable. Otherwise, Z(P)(P)/(P) is a proper subspace of the vector space P/(P). The group Q satisfies P = QZ(P). Hence, pi = [QZ(P), QZ(P)] = Q' (so Q is nonabelian) and [Z(Q), P] = [Z(Q), QZ(P)] = 1, so that Z(Q) = Q n Z(P) ;::: P'. In particular, the isomorphism of P/Z(P) = QZ(P)/Z(P) ~ Q/Z(P) n Q = Q/Z(Q) gives an isometry between Bi(P, Z(P)) and Bi(Q,Z(Q)) which implies that Bi(Q,Z(Q)) is 1.-indecomposable. Thus we may recurse with Q. By induction, the return of a recursive call is a centrally indecomposable subgroup pi :<::; R :<::; P such that Q = RZ(Q) and so P = RZ(P), which proves that {R, Z(P)} is a central decomposition of P. For the timing we note that [Q : Qll < [P : Pi]. Thus the number of recursive calls is bounded by 10g[P : Pi]. To find a vector space complement amounts to finding a basis of Z(P)(P)/(P) and extending the basis to one for P/(P) and so it uses O(10g3[P : Pi]) algebraic operations. Hence, the algorithm uses O(log4[p : Pi]) algebraic operations. 0 Corollary 111.3.4. Let P be a p-group of class 2 and V a fully refined 1.-decomposition of Bi(P, Z(P)). There is a deterministic algorithm using O(log5[p : Pi]) algebraic operations, which returns a fully refined central decomposition H of P such that HZ(P)/Z(P) = V. Proof Algorithm. Computing H := H(V). Set fe = 0. Then, for each HE H, use the algorithm of Proposition III.3.3.(ii) to find a nonabelian centrally indecomposable subgroup K :<::; H such that H = KZ(P) and add K to fe. Next, given Z(P) = (8), set.:J:= feU {(x) : x E 8 - (fen. Using a greedy algorithm, remove the abelian members from .:J until no proper subset of.:J generates P. 65 Correctness. By Proposition IlI.3.1 we know that 1i is a central decomposition of P in which every member H has Z(H) = Z(P) and Bi(H, Z(H)) is -i-indecomposable. Thus the algorithm of Proposition IlL3.3.(ii) can be applied to H and so the set IC consists of nonabelian centrally indecomposable subgroups where distinct members pairwise commute. Furthermore, ICZ(P) = 1i. Let Q := (IC). We now have P = QZ(P). Thus, at every stage of the greedy algorithm, the set .:J generates P, distinct members pairwise commute, and every member is centrally indecomposable. Thus.:J contains a central decomposition of P (i.e.: a subset which generates P and no proper subset does). If {, c .:J and generates P, then given H E .:J - {, it follows that 1 = [H, (J:,)] = [H,P] so that H :::; Z(P). Hence, the greedy algorithm need only consider the abelian members of.:J. The algorithm halts when a central decomposition is found. Timing. There are IVI calls made to the algorithm of Proposition IlL3.3.(ii), which uses O(10g4[H : H'D algebraic operations for each H E 1i. The greedy algorithm halts after lSI steps as then it has tested each abelian member of .:J. 111.4 The *-ring of Adjoints of a Bilinear Map o We have discussed the necessary group theory and now concentrate on the ring theory required in proving Theorem IlLl.l. In this section we introduce a ring with involution (Le. a *-ring [37]) as a means to compute -i-decompositions of a Hermitian bilinear map. Throughout this section we assume that b : V x V ---+ W is a Zpe-bilinear map. 111.4.1 Adjoints The ring of adjoints of b is: Adj(b):= {(f,g) E End V EEl (End V)OP: b(uf,v) = b(u,vg), "iu,v E V}. There is a natural subset of Adj(b) of self-adjoint elements: Sym(b) := {(f, f) E End V EEl (End V)OP : b(uf, v) = b(u, vI), "iu, v E V}. (III.9) (IlUO) Remark 111.4.1. Notice that Sym(b) is not an associative subring but rather a Jordan algebra, quadratic in the case of characteristic 2, cf. [59, Section 4.5J. This is a vital observation for an- 66 swering questions surrounding .i-decompositions; however, for algorithmic purposes this perspective is not necessary. If b is Hermitian then (f, g) E Adj (b) if, and only if, (g, f) ~ Adj (b). Hence, (f, g) f-' (g, f) is an anti-isomorphism * (which uses multiplication in (End V)OP in the second variable). Indeed, * has order 1 or 2 so that Adj(b) is a *-ring. In general, for a *-ring (R,*) and additive subgroup S ~ R, we define Sj(S,*) = {s E S: s* = s} which is again a subgroup of S, as * is additive. (Sj is for Hermitian and is a notation encouraged by Jacobson.) III.4.2 Self-adjoint Idempotents Recall that an endomorphism e E End V is an idempotent if e2 = e. Hence, V = Ve EEl V(l - e). Indeed, every direct decomposition V of V is parameterized by the set of projection idempotents £ := £(V); that is, for each U E V, eu E £ where eu projects V onto U with kernel (V - {U}). It follows that distinct members e and f of £ are orthogonal (Le. ef = 0 = f e) and 1 = 2:eEt: e. Note that 1 E Sym(b). All idempotents in Sym(b) are self-adjoint and vice-versa, but to emphasize this requirement we call these self-adjoint idempotents. The significance of Sym(b) is the following: Theorem 111.4.2. A direct decomposition V of V is a .i-decomposition ofb: V x V --> W if, and only if, £(V) ~ Sym(b). Proof. See [59, Proposition 4.30, Theorem 4.33.(i)] (whose proof applies in any characteristic). 0 Aself-adjoint idempotent e E Sym(b) is self-adjoint-primitive if it is not the sum of proper (Le.: not anor 1) pairwise orthogonal self-adjoint idempotents in Sym(b). Such idempotents need not be primitive in Adj(b). A set of pairwise orthogonal self-adjoint primitive idempotents of Sym(b) which sum to 1 is called a frame of Sym(b). More generally, in a *-ring (R, *), a (self- adjoint) frame is a set of self-adjoint-primitive pairwise orthogonal idempotents which sum to 1. Corollary 111.4.3. There is a natural bijection between the set of fully refined .i-decompositions of b and the set of all frames of Sym(b). Proof. See [59, Theorem 4.33.(i(I]. III.4.3 Computing Adj(b) and Sym(b) 67 o Let V and W be finite abelian p-groups specified with bases X and Z respectively. Take b : V x V --+ W to be a Zpe-bilinear map. Assume that b is input with structure constant matrix B with respect to the bases X and Z (d. (III.3) ). If End V is expressed as matrices (see Section III.2.2) with respect to X then Adj(B) = {(X, Y) E End V EB End V: X B = Byt }. To find a basis for Adj(B) we solve for X and Y such that: (III.ll ) 0 - "'" X ,B(z) _ "'" v ,B(z) - L-J xx x'y L-J .[ yy xy" xEX yEX 'Vx,y E X,z E Z. (III.12) This amounts to solving IXI 2 1ZIlinear equations over Zpe, each in 21XI variables and can be done using O(/XI 4 IZI) operations in Zpe (d. Section III.2.2). Computing a basis of Sym(b) can be done in similar fashion. Remark 111.4.4. If b is Hermitian then the number of equations determining Adj(b) can be decreased by 2 by considering the ordering of the basis X and using only the equations (III.12) for x ::; y, x, Y E X and z E Z. 111.5 Algorithms for *-rings In this section we prove effective versions of the classical semisimple and radical structure theorems for finite *-rings. Most of the work reduces to known algorithms for the semisimple and radical structure theorems of finite algebras over Zp. III. 5. 1 A Fast Skolem-Noether Algorithm Let K be a field of characteristic p. The Skolem-Noether theorem states that every ring automorphism cp of Mn(K) has the form Xcp = D-IxoD for (D,(]') E GLn(K) ~ Gal(K/Zp), for X E Mn(K), [10, (3.62)]. Given an effective automorphism cp, there is a straightforward method 68 to find (D, a) which involves solving a system of n 2 linear equations over K and thus uses O(n6 ) field operations. We offer the following improvement by analyzing the proof of the Skolem-Noether theorem in [26, Chapter VIII]. Proposition IlL5.I. Given an effective ring automorphism cp of Mn(K), K a finite field of characteristic p, there is a deterministic algorithm using O(n4 + dimzp K) algebraic operations which finds (D,a) E GLn(K) XI Gal(K/Zp ) such that Xcp = D-1xuD, for all X E Mn(K). Proof. Define g , K" ~ Mn(K) by x ~ :] ""d r , K n ~ Mn(K) by xr ~ xg'P. Fix. bMffi :'~[:~(~~f]:nM~:~n::c~: ~~i:~:: :::":~:~:,r:h~n :e::;~,:)j $ n. Set Xi(XnT) We summarize how the steps in this algorithm perform the various stages of the proof of Skolem-Noether, given in [26, Chapter VIII]. Let I be the image of g. As I is a minimal right ideal, the image] := Icp is also a minimal right ideal. Thus, there is an 1 :s: i :s: n such that Xi] =1= O. Since Xi] is a simple right Mn(K)-module, it follows that Xi] ~ Kn. As {Xlg, ... ,xng} is a K-basis of I, {XIT, ... ,XnT} is a K-basis of ] and so {Xi(XIT), ... , Xi (XnT)} is a basis of xJ. Thus D is an invertible matrix in Mn(K). Finally, (aln)cp = (aa)In, for a E K, defines a field automorphisms of K. It follows that Xcp = D-1Xu D for each X E Mn(K). The algorithm searches over the set of all 1 :s: i,j :s: n and tests whether Xi(XjT) i= 0, a test which uses O(n2 ) field operations in K. The additional task of inducing a uses O(dimzp K) operations in Zp. D 69 III.5.2 Constructive Recognition of Simple *-algebras Let A be a finite simple *-algebra of characteristic p. There is an elementary yet highly useful observation that: every simple *-algebra is either simple as an algebra, or the sum of two simple algebras with the involution exchanging the two simple factors. (III.13) We call the second case a simple *-algebra with exchange involution, that is, (Mn (K) EB Mn (K), e) where (X, Y)· = (y t , X t ) for each (X, Y) E Mn(K) EB Mn(K). (Note, we could have treated this simple *-algebra as Adj(d) for a nondegenerate Hermitian bilinear map d: K 2n X K 2n -7 K EB K as in [59, Corollary 4.11].) When A is a simple algebra it is *-isomorphic to Adj(d) where d : Kn x X n -7 K is a nondegenerate Hermitian form (recall from Section III.2.3 that our meaning of Hermitian includes alternating and symmetric as well). The proof of this follows from [26, IX.lO-ll] and adapts well to an algorithm: Theorem III.5.2. Given a *-algebra (A, *) with an effective (easily evaluated and inverted) ring isomorphism cp : A -7 Mn(K) for some field extension KjZpJ there is a deterministic algorithm using O(n4 +dimzpK) algebraic operations which returns an effective *-isomorphism fL : (A, *) -7 Adj(d) for some nondegenerate Hermitian form d : Kn x Kn -7 K. Proof. Define the ring anti-automorphism e : X 1-+ ((Xcp-l )*)cp, and the ring automorphism T : X 1-+ (X·)t on Mn(K). Apply the algorithm of Proposition III.5.1 to T to find (D, a) E GLn(K) ) (T, *)} of *"ring epimorphisms. (i) There is exactly one, E r for each maximal *-ideal M of (R, *), and ker, = M. (ii) For each, : (R, *) ----> (T, *) E r either: (a) T = (Mm(K) EB Mm(K),.) a simple *-algebra with exchange involution, or (b) T = Adj(d) for a nondegenerate Hermitian form d: Km x Km ----> K. (iii) If x, y E (R, *) such that x, = y, then the representatives x', y' E (R, *) of the pullbacks to (R,*) of x, and Yf given by the effective, E r, satisfy x' == y' (mod pR). Proof We build r recursively. 72 Let r = 0. Using the algorithm of Theorem III.5.3, compute a representative set of ring epimorphisms n = {71" : R ---+ EndK W} corresponding to the maximal ideals of R. Take 71" E n and set M := ker7l". Test if M* = M. If so then apply Theorem III.5.2 to construct an effective isomorphism

K, there is a deterministic algorithm using O(n3 ) operations in K which finds a frame ofSym(d). (ii) If (Mn(K) EB Mn(K), e) a simple *-ring with exchange involution, then £ = {(Eii , Eii ) : 1 :::; i:::;n} is a frame ofSJ(Mn(K)EBMn(K),e). Proof. (i). By Corollary 111.4.3 we know that the set of frames of Sym(d) is in bijection with the fully refined ..i-decompositions of d. As d is a bilinear form the fully refined ..i-decomposition of d are parameterized by standard bases; Le. a bases X of d such that for each x E X there is a unique y E X such that d(x,y) i- O. Finding a standard basis ofd can be done by standard linear algebra at a cost of O(n3 ) operations in K. Given a standard basis X of d, create the fully refined ..i-decomposition V := {(x) : x E X} and compute associated projection idempotents £ := £(V). This is the return of the algorithm. (ii). This is obvious from Section III.5.2. o Theorem 111.5.8. Given a *-ring (R, *) with R :::; End V, V an abelian p-group, there is a Las Vegas algorithm using o(rank6 R) algebraic operations which finds a frame ofSJ(R, *). 74 Proof Using Corollary III.5.4 we compute a set r of *-epimorphisms onto simple *-algebras, one for each maximal *-ideal of (R,*). Given,: (R,*) ---+ (T,*) E r, use Proposition IIl.5.7 to compute a self-adjoint frame £"1 of (T,*). By Corollary III.5A.(iii), we pullback E-y to a set F-y = {e + pR ~ e2 == e (mod pR), e* == e (mod pR)} such that F maps to E via e + pR f--7 e, + pRo Next, using Lemma IlI.5.5, choose coset represen- tatives 1 E R for each e + pR E F such that 1* = f so that now: F~ = {f + pR : 12 == 1 (mod pR), j* = f} and F-y, = £"(' Apply Lemma IlI.5.6 to the members of F-y to create f = {j :1 E F-y}, which is a set of pairwise orthogonal self-adjoint primitive idempotents. Since F-y projects onto a unique *-simple factor of (R, *), and there is exactly one, E r for each maximal *-ideal of (R, *), it follows that F:= U-YEI'F-y is a self-adjoint frame of (R, *). Now we consider the number of operations. By using Corollary IlI.5A we use O(rank5 V) algebraic operations. Now fix , : (R, *) ---+ (T-y, *) E r with T-y = EndK W"(' Proposition IlI.5.7 uses O(rank3 W-y) operations. Since 2:-YEI' rank W-y is at most rank V, it follows that this stage takes at most O(rank3 V) operations. Next, the computation applies Lemma IIl.5.5 which uses O(rank3 T-y) operations. Since the bases computed in Lemma IlI.5.5 can be reused for each application with respect to a fixed " it follows that the total cost of this stage is 0 (2:-YEI' rank3 T-y) = 0 (2:-yEI' rank6 W-y) = O(rank6 V) operations. 0 111.6 Proof of Theorem 111.1.1 Given a finite p-group P of class 2, compute bases for PjZ(P) and pi and compute a structure constant representation of b := Bi(P, Z(P» (which is straightforward from the definitions in Section III.3.1 and (III.3». Next, compute a basis for Adj(b) (Section IlI.4.3). Apply Theorem III.5.8 to find a self- adjoint fra~e £ of Adj(b). Induce a fully refined .i-decomposition V = {(PjZ(P»e : e E £} of b (d. Corollary IIIA.3). 75 Apply Corollary III.3.4 to produce a fully refined central decomposition of P. Since rankAdj(b) ~ log;[p : Z(P)]2 ~ log2[P : pI], the total number of algebraic opera- tions is at most O(log6[P : PI]). 0 III.7 Closing Remarks. III. 7.1 Discrete Logs are Required The discrete log problem for Zp, is: given two elements x, y in an elementary abelian p- group, determine if y E (x) [20, Section 7.1]. That is, can we decide if (x, y) is isomorphic to Zp or Zp x Zp. This problem occurs in many fields of computational mathematics. It has no known polynomial-time solution and is generally regarded as a hard problem. A stronger version of the discrete log problem asks further for an exponent e such that x e = y and this is the version required in Section III.2.2 to use [39, Theorem 8.3] for large primes. Since the abelian centrally indecomposable p-groups are the cyclic p-groups, we cannot test if an abelian p-group is centrally indecomposable without solving the discrete log problem, i.e.: determining if (x, y) is Zp or Zp x Zp. For p-groups of general class the situation does not improve: Proposition III.7.1. The discrete log problem for Zp is polynomial-time reducible to testing if a central decomposition of finite p-group of class 2 is fully refined. Proof. Let V = (x, y) be an instance of the discrete log problem for Zp. Set P := p1+2 x V, where p1+2 is the extraspecial p-group of order p3 and exponent p, in particular, p1+2 is centrally indecomposable of class 2. Evidently P is a p-group of class 2 and H = {p1+2 X 1, 1 x V} is a central decomposition of P. Furthermore, H is fully refined if, and only if, V = (x, y) is cyclic. 0 A version of Proposition III.7.1 for p-groups P of any class c shows that there exists a centrally indecomposable p-group of any class c. 76 111.7.2 Deterministic Version Suppose that p is small, for instance bounded by loge IPj. In this case the discrete log problem can be solved by brute force. FUrthermore, by replacing the Las Vegas method of [22] with the original deterministic methods of [24] in the algorithm of Theorem IlL5.3, we can avoid all use of nondeterministic methods. III. 7.3 A Faster Las Vegas Algorithm Suppose that we are only interested in testing if a p-group P of class 2 is centrally inde- composable. By Theorem IlL3.2, the key step is to prove that Bi(P, Z(P)) is i.-indecomposable. This means that we must prove that Sym(b)j(Sym(b) n radAdj(b)) is a field. This can be done without polynomial factorization as we must only verify that various polynomials are irreducible (see the algorithm of [24, Corollary 5.2]). Testing irreducibility can be done deterministically [57, Theorem 14.37]. The use of discrete log oracles could also be avoided in this constrained setting as we use this only in our pullback algorithm Lemma IlL5.5. So it appears possible that a deter- ministic method can prove that a rgroup of class 2 is centrally indecomposable. (Note, the same is impossible for abelian p-groups by Section III.7.l.) If we can test if a p-group of class 2 is centrally indecomposable in a deterministic and efficient manner then there is an alternative approach to proving Theorem IlLl.l, with discrete logs reserved only to determine if abelian central factors are centrally indecomposable. The algo- rithm would replace Theorem IIl.5.8 by a random search for self-adjoint idempotents in Sym(b). Unfortunately, Sym(b) is a (quadratic) Jordan algebra, and there are presently no known estimates on the the number of zero-divisors in Sym(b) and therefore finding idempotents at random may not be easy. These questions are being investigated. III. 7.4 Parallel Implementation The algorithm described here is sequential. Recent investigations have revealed alternative parallel algorithms for associative algebras, and the algorithms added here can be modified to a parallel setting [64]. 77 III. 7. 5 Finding Orbits of Central Decompositions In [59J, the action of the automorphism group of a p-group P of class 2 and exponent p was studied. Though not presented in detail, it is clear that the methods here can be used to find a representative fully refined central decomposition for each CAutp(P')-orbit as described in [59, Corollary 5.23.(iii)]. The necessary step is to choose an orthogonal basis in Proposition III.5.7 with the desired address in the sense of [59, Definition 5JJ. 78 CHAPTER IV FINDING DIRECT PRODUCT DECOMPOSITIONS IV.1 Introduction A polynomial-time algorithm is provided which, given a group of permutations, matrices, or a polycyclic presentation; returns a Remak decomposition of the group: a fully refined direct decomposition. The method uses group varieties to reduce to the case of p-groups of class 2. Bilinear and ring theory methods are employed there to complete the process. One of the most elementary methods to create a group is through a direct product of other groups. This immediately suggests the problem of decomposing a group into a direct product of nontrivial subgroups or proving that no such decomposition exists. By the classical Krull-Remak- Schmidt theorem, finding one direct decomposition with maximal size is sufficient to understand all other direct decompositions, as any two maximal direct decompositions are equivalent up to an automorphism of the group. However, this does not resolve the problem of finding even one proper direct factor, should one exist. For finite groups G this is a finite problem, but surprisingly algorithms to accomplish this task use IG/IOg IGI+O(I) steps, see Section IV.6.!.1 Thus such methods . are impractical and here we present a substantial improvement as seen in the following special case of our main theorem: Theorem IV.I.L There is a polynomial-time algorithm which, given G = (T) :::; Sn, returns a direct decomposition of G into nontrivial subgroups: G = HI X ••• x He, with emaximal. As every group Gcan be represented as a permutation group of degree IGI, this leads to a polynomial-time, in IGI, algorithm to find a direct decomposition of any group. With a careful analysis we prove that in fact such an algorithm is nearly optimal: 1 In this work, all logs are with base 2. 79 Corollary IV.L2. There is a nearly linear-time, O~(N), algorithm which, given the multipli- cation table of a group G of order N, returns a direct decomposition into nontrivial subgroups G = HI X .,. X He, with l maximal. We have not pursued every notable optimization in the algorithm of Theorem IV. l.1. How- ever, much of that algorithm adapts to matrix groups and groups given by polycyclic presentations. To explain this some vocabulary is required. Groups and subgroups are given by sets of generators. To decompose a group into a direct product of nontrivial subgroups it suffices to provide a set of generating sets for the members of the direct decomposition. A group G is directly indecomposable if its only direct decomposition is {G} - owing to the fact that we do not allow 1 as a direct factor. A Remak decomposition is a direct decomposition consisting of directly indecomposable subgroups. We let Gn denote a class of groups suitable for computation, together with a list of hypothesized routines available for members of Gn which are described in Section IV.2.2. If G = (B) E Gn then G is input by O(IBjn) bits of data, and the algorithm's complexity is measured in terms of IBln + log IGI. In some domains Gn , there are no efficient deterministic algorithms for some of the hypothesized routines, but often there are Las Vegas algorithms or the inherent obstacles appear infrequently in practical settings. Section IV.2.2 expands on these issues. We can now present our main theorem: Theorem IV.L3. There is a deterministic polynomial time algorithm which, given a group G E Gn , returns a Remak decomposition ofG. IV.I.1 Outline of the Algorithm of Theorem IV.I. 3 The algorithm works recursively through the following characteristic series of the given finite group G f 1: (IV.1) where (i(G) represents the upper central series of G, i E Z+, 06(G) is the solvable radical, and S(G)/06(G) = soc(G/06 (G)) is the pullback of the socle of G/06(G). Using this series we describe the stages of the algorithm. 80 • Case: G > 0 15 (G) = 1. This case is settled in Section IV.5A, utilizing the unique Remak decomposition of the socle of G to build the unique Remak decomposition of G. • Case: G = 015(G) > 1. This case is settled in Sections IV.5.1- IV.5.3 and breaks into five subcases. - Subcase: G> (1(G) = 1. This case is settled in Theorem IV.5.4, reducing to the case of p-groups by means of a Sylow system for the group. - Subcase: G = (1 (G) > 1. This case is settled in Section IV.2.3. Here G is a direct product of cyclic groups of prime power order. To find such a decomposition is routine but in general relies on factoring and discrete logs. - Subcase: G > (2 (G) = (1 (G) > 1. This is settled in Section IV.5.3, using a recursive call to find a Remak decomposition of Gj (1 (G). Using the algorithm for abelian groups, the algorithm lifts and reduces that decomposition to a Remak decomposition of G. - Subcase: G = (2(G) > (1(G) > 1. This is settled in Sections IVA.9 and IV.5.l. This stage of the algorithm uses the bilinear map of commutation of the group G and the structure of a certain commutative ring. This translates the problem to one of factoring polynomials over finite fields. - Subcase: G > (2(G) > (1 (G) > 1. This is settled in Sections IV.5.2 and IV.5.3, using a recursive call to find a Remak decomposition of Gj (1 (G). Using the algorithm for nilpotent groups of class 2, the algorithm lifts and reduces that decomposition to a Remak decomposition of G . • Case: G > 0 15 (G) > 1. This is settled in Section IV.5.5 making a recursive call to find a Remak decomposition of Gj015(G). Then using the algorithm for solvable groups, the algorithm lifts and reduces that decomposition to a Remak decomposition of G. The recursive calls in the third and fifth subcases, and the final case, use the same frame- work. Indeed, the algorithm handles them uniformly through the use of group varieties. That is carried out in Section IV.4.l. 81 IV.2 Background IV.2.1 Notation Unless otherwise obvious, we assume all groups, rings, and modules are finite. We use A - B for the complement of A n B in A, and Au B denotes a union of disjoint sets. In general p denotes a prime. Groups, rings, and modules will be denoted by capital Roman letters, i.e.: G, H, etc. Sets of subgroups, subrings, and submodules will be denoted with calligraphy, for instance, H, X, etc. Varieties will be denoted in Gothic letters, i.e: W, 91, etc. The direct product of groups A and B is denoted by A x B, whereas the direct product of rings or modules A and B is denoted by A ED B. Given a set H of groups we let ITHEfi H denote the direct product of the members of H. Given a set H oj normal subgroups oj G, we use only the notation (H) := (H : H E H) jor the product oj the members in H and thus avoid confusion with the notation ITHEfi H. As we contend with many notions of "product" we take care to include the adjective "direct" whenever appropriate. Given a group G, our convention is that gh := h-1gh and [g, h] = g-1 g\ for g, h E G. Also, [H, K] := ([h, k] : hE H, k E K) and CH(K) := {h E H : [h, K] = I}, for H, K :S G. We make repeated implicit use of the following: given normal subgroups A, B, C of G: [A, B] :::! G, [A,B]:S AnB, [A,B] = [B,A], and [A,BC] = [A,BHA,C]. Set (I(G) := Cc(l) and inductively define (i+1(G) ;::: (i(G) so that (i+l(G)!(i(G) = (1(G!(i(G)), i E Z+; that is the usual upper central series of G. We say that G is nilpotent of class c if (c(G) = G > (c-1(G). The derived series begins with G(O) := G and recursively GCi+1) = [GCi), G(i)], i E N. We call G solvable oj derived length d if G(d-l) > G(d) = 1. The solvable radical of G, O(5(G), is the. largest solvable normal subgroup of G.. The socle of G, soc G, is the subgroup generated by all minimal normal subgroups of G. IV.2.2 Gn and its Hypothesized Routines For Gn we have in mind permutation groups, matrix groups, and groups given by polycyclic presentations. More generally, Gn is a class of groups for which: (i) given G = (8) E Gn is input using 0(18In) bits, 82 (ii) if H = (T) :::; G, G E Gn , then HE Gn , and (iii) the list of hypothesized routines (IV.2.3-IV.2.12) below, are available for members of Gn . The complexity of all algorithms is with respect to 18ln+log IGI. The additional log IGI term allows for recursion through chains of subgroups of G (which have length at most log IG/). In the examples of Gn above, this is implicit since log IGI E O~(n). Though we discuss current implementation and complexities for (IV.2.3-IV.2.12), these algorithm can be taken as oracles in that the algorithm of Theorem IV.1.3 is a deterministic polynomial-time reduction to these hypothesized routines. In the context of permutation groups, (IV.2.3-IV.2.12) has a deterministic polynomial-time solution, which leads to Theorem IV.1.1. Quotients of Permutation Groups: Gn = QPERMn' Here G E QPERMn if, and only if, G = GIM where G = (8) :::; Sym(n), Inl = n, and M = (TG ) g G. Remark IV.2.1. Theorem IV.1.1 references permutation groups but the algorithm applies also to quotients of permutation groups. In fact, it requires this generality (actually the quotients in IV. 2. 7). But a benefit of this requirement is that it allows for larger families of groups. For example, extraspecial2-groups of order 2l+2m have no faithful permutation representations of degree less than 2m . However, such groups are obvious quotients of a permutation group of degree 8m. "Proto" Matrix groups: G n = PRMAT(d, q) with n = d2 log q, and q a power of a known prime p. Here G E PRMAT(d, q) if, and only if, G = Glei (G) for some i E N or G = G10'5 (G), where G = (8) :::; GL(V), V a d dimensional vector space over IF'q. Remark IV.2.2. Working with general quotients of matrix groups would seem the appropriate context here; however, algorithms for such general settings do not exist. As they are not required, this generality suffices, and indeed, it this generality alone that is required for permutation group setting. Polycyclic groups: Gn = PC(Pl,'" ,Pd) with n = (d!l) logmax{pl,'" ,Pd}, and Pi not neces- sarily distinct primes, for 1 :::; i :::; d. Here (IV.2) 83 It follows that every g E G can be written as (IV.3) Hypothesized Routines. IV.2.3. Given x,y E G = (8) E Gn , compute xy, X-I, and test if x = y. IV.2.4. Given G= (8) E Gn , return IGI. IV.2.5. Given H = (T) ~ G = (8) E Gn and x E G, test if x E H. If x E H then also return x as a word (or straight line program) in T. The routines (IV.2.3-IV.2.5) are interrelated. For QPERMn and PRMAT(d, q) both xy and x-I can be computed efficiently by obvious means. To test x = y requires testing equality of cosets in some instances, and is thus essentially equivalent to (IV.2.4) and (IV.2.5). Deterministic polynomial-time algorithms for (IV.2.3-IV.2.5) for QPERM are in [29, PI]. For PRMAT(d, q), these problems presently require many of the methods of the ongoing matrix group project, [46]. Many of those methods are nondeterministic Monte Carlo and Las Vegas routines, and also require large integer factorization and discrete logs (see [57, Chapter 19, p. 569]) - though in practice these are reportedly of little concern. 2 Deterministic polynomial time algorithms are known for restricted classes of matrix groups including solvable groups involving only small primes [38, Theorem 3.2J and other generalizations as in [41J. For groups in PC, none of these problems have polynomial-time solutions at present. The most popular method to test equality is through (IV.3). However, the known methods to write words W(XI, . .. ,Xd) as a words of the form (IV.3) have exponential complexity, even in the average case [35]. An improvement was given for p-groups in [36], but the complexity of that algorithm is not established. However, the domain Pc has a great deal of successful uses in practice. and is often the easiest method to input solvable groups. In this case the algorithm of Theorem IV.1.3 will not be polynomial-time but rather will use a polynomial number of group multiplications. IV.2.6. Given IGI for G= (8) EGn , return the primary factorization of IGI. For G E QPERMn , the prime divisors of IGI are at most n and so the factorization is always easy. For G E PC(PI,." ,Pd), following (IV.3), IGI divides Pl'" Pd. To factor IG] is 2Thanks to C.R. Leedham-Green for communicating the state of these at Groups and Computation V. 84 straight forward as the primes {PI, ... , Pd} are known. If G E PRMAT(d, q) this routine can involve the difficult problem of factoring qi - 1 for various 1 ~ i ~ d. IV.2.7. Given G = (B) E G n and ME {(I(G), (2(G), ... , Oe;(G)}, return H = (T) E Gf(n) and an isomorphism cp : G / M ~ H, where f (n) is a polynomial in n independent of G. For the domains QPERMn , PRMAT(d, q), and PC(PI, ... ,Pd), this routine is trivial, with f(n) = n, as these classes are closed to quotients by these subgroups. If we consider simply the class of permutation groups (without quotients) then it is not even clear that quotients of this form have faithful permutation representations of degree a polynomial in n. IV.2.8. Given M = (TG) ~ G = (B) E Gn , return CG(M). Consequently, given G = (B) E Gn and i E Z +, return the i -th upper central series term (i (G) . For QPERM see [29, P7J. This presently depends upon the classification of finite simple groups. For PRMAT we have not found a treatment of this problem; however, for solvable matrix groups this is solved in [38, Theorem 3.2.(8)J under the assumption that all primes in the order of the group are small. That condition can be removed by hypothesizing routines for integer factorization and discrete logs, and it is possible that methods from the matrix group project apply for the general matrix group setting. For Pc see [20, Section 8.8.2]. IV.2.9. Given G = (B) E G n , return the solvable radical: Oe;(G). For QPERM see [29, P29J. As the groups in Pc are solvable, there G = Oe;(G) so the problem is trivial. For PRMAT this problem has long been studied as part of the matrix group project, but has not been resolved in general, though in many situations this can be computed; see [46, Section 1.3]. IV.2.10. Given G = (8) E Gn with Oe;(G) = 1, return a minimal normal subgroup ofG. Conse- quently, also find the sode of G: soc G. See [29] for QPERM and [46, Section 1.3] for PRMAT. For groups G > 1 in Pc, Oe;(G) = G > 1 so this problem is not applicable.. iV.2.11. Given a solvable group 0 = (B) E G n , return a Bylow system P = {PI, ... , Pt } of 0: Pi a Bylow subgroup ofG for 1 ~ i ~ t, G = Pt ···pt , and PiPj = PjPi for 1 ~ i,j ~ t. 85 For details on the existence and uniqueness of Sylow systems see [11, Section 1.4]. For Pc see [13], for QPERM [29, P13], and for PRMAT [31]. IV.2.12. Given H = (T) :::; G = (8) E Gn , return K:::; G such that G = H x K, or prove that no such K exists. (IV.2.12) was solved independently by E. M. Luks and C.R.B. Wright in 2004 in a back to back lectures given at the University of Oregon. Earlier Holt and Luks independently produced polynomial-time algorithms to find a complement K to H in G, though possibly not a direct complement; see for instance [30, Proposition 3.8]. Their methods are essentially the same and can be viewed as applications of I-cohomology. Coupled with the (IV.2.8), this leads to: Theorem IV.2.13 (Luks,Wright; 2004 (unpublished». Given a method to find general comple- ments and solutions to (IV.2.5) and (IV.2.8) in Gn , there is a deterministic polynomial time algorithm which solves (IV. 2. 12}. Proof Let G E Gn . Algorithm. Use (IV.2.5) to determine if H::9 G. If not, then report that H is not a direct factor of G. Otherwise, use (IV.2.8) to compute Gc(H) and Z(H). Use (IV.2.5) to test if G :::; HGc(H) and if not, report that H is not a direct factor of G. Next, find a general complement K:::; Gc(H) to Z(H), if one exists, and return K; otherwise, report that H is not a direct factor ofG. Correctness. Evidently, G = H x J, for some J :::; G, requires that H ::9 G, Gc(H) = Z(H) x J, and G = HGc(H). Therefore, a negative return is given only if H is not a direct factor. Now suppose that H is a direct factor of G. Then every direct complement of H lies in Gc(H). Furthermore, a direct complement of H is also a direct complement of Z(H) in Gc(H). As Z(H) is central in G, so also in Gc(H), a complement K :::; Gc(H) to Z(H) is a direct complement to Z(H). Furthermore, H n K :::; H n Gc(H) = Z(H), so H n K :::; Z(H) n K = 1. Also, HK ~ HZ(H)K = HGc(H) = G. Finally, [H,K] = 1 so G = H x K. Timing. The algorithm makes a bounded number of calls to assumed routines. 0 Remark IV.2.14. For clarity we point out that the only computational domains considered here which have deterministic polynomial time algorithms. for each of the hypothesized routines are quotients of permutation groups and solvable matrix groups whose orders involves small primes. 86 IV.2.3 Abelian p-groups, Bases, Effective Homomorphisms, and Solving Systems of Equations A basis of a finite abelian p-group V is a subset X of V such that V = EBxEX (x). Every basis of V gives a natural isomorphism to Zpel EB ... EB Zpes for el :S ... :S es E Z+. Operating in the latter representation is preferable to V's original representation and we assume all abelian groups are handled in this way. Each endomorphism f of V can be represented by an integer matrix F = [Fij ] such that pej-eiIFij, 1:S i :S j :::;; s, and furthermore, every such matrix induces an endomorphism of V (with respect to X) [19, Theorem 3.3]. In various places we apply homomorphisms and isomorphisms between finite abelian p- groups, rings, and algebras. We say a homomorphism is effective when it can be evaluated efficiently - for instance with the same cost as matrix multiplication - and a coset representative for the preimage of an element in the codomain can also be found efficiently. This means that effective isomorphisms are easily evaluated and inverted. Suppose we have a system of Zpe-linear equations with solutions in a Zpe-module V. There are efficient deterministic methods to find a basis of the solution space of the system [39, Theorem 8.3]; however, it is essential to note that for a large p, this process assumes a discrete log oracle mod p. However, we have elected to assume (IV.2.5) which incapsulates this problem for large p and so we do not make explicit mention of the discrete log problem below. Proposition IV.2.15. There is a deterministic polynomial time algorithm which, given an abelian group in Gn , returns a Remak decomposition of the group. Proof. Let G E Gn be abelian. Algorithm. Use (IV.2.4) and (IV.2.6) to compute and factor N := IGI. For each prime piN, let mp be the p' part of N, and set Gp := Gmp • Use [39, Theorem 8.3] to find a basis Xp for Gp • Return U{(x) : x E Xp }. piN Correctness. The subgroups Gp are the p-primary components of G and so [39, Theorem 8.3] applies. Furthermore, G = ITplN (Xp), and (X) = ITXEX (x) by the definition of a basis. Timing. The algorithm applies deterministic polynomial time methods. As log IGI :S n, the number of applications of these routines is polynomial in n. o 87 IV.2.4 Rings, Idempotents, and Frames All our rings will have characteristic a power of p and are input with a basis. Furthermore, each of our rings will be represented in End V for some abelian p-group V and thus multiplication is the usual matrix multiplication. Let R be a finite ring. An element e E R is an idempotent if e2 = e. The trivial idempotents are °and 1 and all other idempotents are called proper. Two idempotents e and f are orthogonal when ef = °= fe. Given any idempotent e, 1 - e is also an idempotent and is orthogonal to e, and if f is orthogonal to e then f(I - e) = f = (1 - e)f. A set E of pairwise orthogonal idempotents is supplementary if 1 = LeEe e. An idempotent is primitive if it is not the sum of proper pairwise orthogonal idempotents. Finally, a frame is a supplementary set of primitive pairwise orthogonal idempotents. As R is finite, it follows that R has a frame and any two frames of R are conjugate under a unit of R [10, p. 14IJ. The unique size of a frame we call the capacity of R. If R has capacity 1 then we say R is a local ring. As idempotents are not quasi-regular, they lie outside ofthe Jacobson radical J(R) of R. Thus, a frame of R induces a frame of R/J(R). We have occasion to use the following classic formula for the lifting of idempotents: Lemma IV.2.16 (Lifting idempotents). Suppose that e E R such that e2 - e E J(R). Then there is an n E N such that (e2 - e)n = 0, and setting n-l (2n -1) . .e := en L . en- 1- J(1 - e)J j=O J it follows that: (i) e2 = e, (ii)e == e (mod J(R)),and (iii) r=e = 1 - e. (iv) If E is a frame of RjJ(R) , then t := {e : e E E} is a frame of R. (IVA) Proof (i)-(iii) are verified directly, compare [10, (6.7)]. For (iv) note that J(R) consists of nilpo- tent elements as R is finite. By (i), t is a set of idempotents of R. Given e E E, we have assumed that 1 - e = LfE&-{e} f, and so by (iii) e is orthogonal to j for all fEE - {e}. Finally, by (ii), 88 if e is not primitive in R then e is not primitive in R/J(R), which contradicts our assumptions. Thus t is a frame of R. 0 Consequently, if R is a finite commutative ring, then R/J(R) is a product of fields and so there is a unique frame & of R; that is, {Re : e E &} is the unique direct decomposition of R into commutative local subrings. Let R be a finite ring and V a finite (left) R-module. If S is a subring of EndR V then every idempotent e E S decomposes V into R-modules: V = Ve EB V(l - e). In general a direct decomposition X of V determines a supplementary set &(X) of pairwise orthogonal idempotents which are the projection endomorphisms to the various components. If instead we start with a set & c EndR V of supplementary pairwise orthogonal idempotents then the associated direct decomposition is denoted X(&) := {Ve: e E &}. Notice that &(X(&)) = & and X(E(X)) = X. IV.2.5 Biadditive and Bilinear Maps Let V and W denote finite abelian groups. A map b : V x V --> W is biadditive if b(u +u/, V +VI) = b(u, v) +b(u l , v) +b(u, VI) + b(u/,VI), for all u, ulv, VI E V. Define b(X, Y) := (b(x, y) : x E X, Y E Y) for X, Y ~ V. If X::; V then define bx : X x X --> b(X,X) as the restriction of b to inputs from X. The radical of b is radb:= {v E V: b(v, V) = a= b(V, v)}. (IV.5) (IV.6) (IV.7) (IV.8) We say that b is nondegenerate if rad b = O. If R is a ring, then a biadditive map b : V x V --> W is R-bilinear if V and Ware (left) 89 R-modules such that b(ru,v) = rb(u,v) = b(u,rv), Vu, v E V, and r E R. (IV.9) We say b is faithful R-bilinear when AnnR VnAnnR W = 0, where the annihilator of an R-module V is AnnR V = {r E R: rV = O}. Every biadditive map is also Z-bilinear. More generally, if R is a subring of Sand b is S-bilinear then b is also R-bilinear. In that case rad band b(V, V) are both R- and S-modules. IV.2.6 Representing Bilinear Maps for Computations Assume that b : V x V ~ W is a Zp.-bilinear map. Let X and Z be ordered bases of V and W respectively. We define B~fJ E Zp' by Set b (I: Sx X , I: ty y) xEX yEX = I: I: sxtyB~fJZ, x,yEX zEZ (IV. 10) B - "" B(z)xy - L.... xy Z, zEZ Vx,y E X; so that B = [BXY]X,YEX is an n x n-matrix with entries in W, where n = IXI. Writing the elements of V as row vectors with entries in Zp' with respect to the basis X we can then write: b(u, v) = uBvt , Vu,v E V. (IV.ll) Take F, G E End V, represented as matrices with respect to the ordered basis X. Define F Band BG t by the usual matrix multiplication, but notice the result is a matrix with entries in W. Evidently, (F+ G)B = FB +GB, F(GB) = (FG)B, and similarly for the action on the other side of B. If H E End W then define BH by [BH]x,y := BxyH for each x,y E X. The significance of these operations is seen by their relation to b: (IV.12) for all u, v E V. 90 IV.3 Direct Decompositions In this section we develop various properties of direct decompositions. Our principal aim is to establish when direct products can be lifted from direct products of a quotient (Subsection IVA). IV.3.l Normal, Central, and Direct Decompositions A set H of normal subgroups of a group G is a (normal) decomposition of G if'H generates G but no proper subset does. Evidently, 1 rf- H. Thus, if G = 1, its the only decomposition is 0. A decomposition H is central if [H, (H - {H})] = 1 for each H E 'H, or direct if H n (H - {H}) = 1 for each H E H. Direct decompositions are also central decompositions. If H is a decomposition where [H,K] = 1 for distinct H, K E H, then [H, (H - {H})] = 1 so H is a central decomposition. A subgroup H ::; G is a direct factor of G if there is a direct decomposition H of G with H E H. Notice H =J. 1. Remark IV.3.l. Central decompositions are in the internal description of central products while direct decompositions are the internal description of direct products. Remark IV.3.2. Suppose that G = (H) = (J) for some sets of subgroups J ~ H .. (i) If [H, (H - {H})] = 1 for each H E H, then K::; Z(G) for each K E H - J. (ii) If Hn (H - {H}) = 1 for each H E H, then K = 1 for any K E 'H - J. Thus, the definition of direct decompositions given in the introduction agrees with definition just given. Proposition IV.3.3. If H is a normal, central, or direct decomposition of G and K is a subset ofH, then K is a normal, central, or direct decomposition of (K), respectively. IV.3.2 Finer and Coarser Decompositions A set H of subgroups of a group G is finer than another set K of subgroups of G if K = (H E H : H::; K), VKEK. (IV.13) 91 Note this is not the same as H ~ K. Evidently this gives a partial ordering on the decompositions of G with top element {G}. We also say that K is coarser than H, or that H refines K. Remark IV.3.4. Note that we have not required that Hand K be decompositions in the definition of refinement. This allows us to speak of refinements of induced sets as in (IV.14)-(IV.16), below. Proposition IV.3.5. Suppose that H is a finer decomposition than K. IfH is normal, central, or direct, then K is central or direct, respectively. Proof. If every member of H is normal then any group generated by a subset of H is normal; thus, the members of K are normal. Now assume H is central and fix K E K. As (K - {K}) = (H E H : H i K) it follows that [K, (K - {K})] ([H, (H E H: H i K)] : H E H,H:::; K) < ([H, (H - {H})] : H E H,H:::; K) = 1. So K is a central decomposition. Finally assume that H is a direct decomposition. Note that K n (K - {K}) = (H E H: H:::; K) n (H E H: H i K). As H is a direct decomposition, each 9 EGis expressed uniquely as 9 = I1HE'H gH, gH E H. If 9 E Kn (K - {K}) then 9 E K so gH = 1 for all H i K, H E H. Also, 9 E (K - {K}) so gH = 1 for all H:::; K, H E H. Hence, 9 = 1. 0 IV.3.3 Induced Decompositions and Generically Split Subgroups Let M be a normal subgroup of a group G and H a set of subgroups of G. The following notation is convenient (coincidences can occur, but the resulting objects are sets so coincidences are ignored): HnM .- {HnM:HEH}-{1}, HM .- {HM: H E H} - {M}, and HM/M .- {HM/M: H E H} - {M/M}. (IV.14) (IV.15) (IV.16) 92 Remark IV.3.6. IfH is a decomposition, it is generally possible to that H n M, HM, or HMIM is not a decomposition of M, G, or GIM, respectively. Proposition IV.3.7. Let G be a group with a direct decomposition H. If M::::JG and M = (HnM) then: (i) H n M is a direct decomposition of M; (ii) HM = KM for H, K E H implies H, K ::; M (so HM, HMIM, and H- {H E H : H ::; M} are in bijection); (iii) HM1M is a direct decomposition of G1M; and (iv) if N ::::J G with N = (H n N) then M n N = (H n M n N) and M N = (H n M N). Proof. (i). Suppose that M = (H n M). If H n M E H n M, then H n M::::J M. Furthermore, (H n M) n (H n M - {H n M}) ::; H n (H - {H}) = 1. By definition, 1 ¢ H n M, and so H n M is a direct decomposition of M. (ii). FixH,K E H, H -=f. K. Set J:= (H-{H,K}). By Proposition IV.3.5, G = HxKxJ and by (i), M = (H n M) x (K n M) x (J n M). Thus, HM H x (KnM) x (JnM), KM = (HnM) x K x (In M). If H M = K M then H = H n M and K = K n M. (iii). As G = (H) = (H, M) it follows that G1M is generated by HMIM and the members of HMIM are normal in GIM. Fix H E H. Clearly M ::; HM n (H - {H})M. Next we reverse the inequality. Set J := (H - {H}), so G = H x J. So HM = H x (J n M) and JM = (H n M) x J. Thus HMnJM = (HnM)x(JnM) = M. Furthermore, HM is in bijection with H-{H E H: H::; M}. So (H - {H})M = {KM: K E H,K i M,K -=f. H} = HM - {HM}. Thus, (HMIM) n (JMIM) = MIM implies (HMIM) n (HMIM - {HMIM}) = 1. As MIM ¢ HMIM (by (IV.16)) it follows that HMIM is a direct decomposition of GIM. 93 (iv). Let gEM n N. By (i), H n M is a direct decomposition of M and since gEM, it follows that g = IlHEH hH for unique hH E H n M, H E H. Similarly, H n N is a direct decomposition of N and by the uniqueness of the hH , it follows that hH E H n N, and so hH E H n M n N. Thus M n N::; (H n M n N) ::; M n N. The argument for M N = (H n M N) is equally transparent. 0 Definition IV.3.8. A subgroup M:::J G is generically split if given any direct decomposition H of G, then H n M is a direct decomposition of M. Evidently 1 and G are always generically split. Furthermore, Proposition IV.3.7.(iv) show that the set of all generically split subgroups of G form a lattice. In Section IV.4.3 we uncover a great number of generically split subgroups but for now we give some simpler examples. Example IV.3.9. (i) If G ~ Z~ then the only generically split subgroups are 1 and G. (ii) In any group, the subgroups (i(G) are generically split; see Proposition IV.4.11.(i). (iii) In any finite group, the solvable radical is generically split; see Proposition IV.4.11. (ii). Proposition IV.3.10. If M ::; N are normal subgroups of G such that M is generically split in N and N is generically split in G, then M is generically split in G. In particular, every characteristic generically split subgroup of N is generically split in G. Proof. Let H be a direct decomposition of G. As N is generically split in G, N n H is a direct decomposition of N. As M is generically split in N, also M n (N n H) = M n H is a direct decomposition of M. Thus, M is generically split in G. 0 IV. 3.4 Krull-Remak-Schmidt Redux We make crucial use of the classical theorem for direct products of groups: Theorem IV.3.11 (Krull-Remak-Schmidt). Let G be a finite group with Remak decompositions Hand K. Then for each .1 <;;;; H, there is a cp E CAutG(InnG) such that .Jcp <;;;; K and Hcp = (H - .1) u .1cp. In particular, there is a cp E CAut G (Inn G) with Hcp = K. Proof See [49, (3.3.8)]. o 94 Remark IV.3.12. Theorem IV.3.11 was proved by Remak in his 1911 thesis [48]. Over the next two years, Remak and Schmidt exchanged successive improvements in the proof concluding in Schmidt's 3 page proof [52]. Krull was 12 years old at the time of these results, but 14 years later contributed a version for modules [33], a simpler but widely used version of the theorem. Modern group theory texts synthesize both versions into one statement involving operator groups. Incomprehensibly, Remak's name is sometimes dropped from the title. Remark IV.3.13. The Krull-Remak-Schmidt theorem is a hybrid of an exchange theorem (in the sense of a matroid) and a transitivity theorem. Both of these interpretations are used in the proof of Theorem IV.l.S. We need the following consequence: Corollary IV.3.14. Let G be a finite group, H a direct decomposition of G, and R a Remak decomposition of G. Then (i) RM refines HM whenever Z(G) ::; M ~ G, and (ii) R n M refines H n M whenever M ~ G, M ::; G'. Hence, RZ(G) and R n G' are uniquely determined by G, and Aut G acts on both sets. Proof (i). Let K be a Remak decomposition which refines Ji (there always is one). By Theorem IV.3.lI, there is some

G). (IV.17) This is the subgroup generated by all evaluations of the words in W with elements from G. Given f, f' : X ----> G we form the product f f' : X ----> G pointwise. Thus, in the indexed sequence notation above we have: wff' = w(g19~, g2g~, ... ) (IV.18) forw E F[X], gi = xi! and g~ = xii', i E Z+. The counterpart to verbal subgroups are the W-mar:ginal subgroups introduced by P. Hall [17J. W*(G) := {a E G I W(91, •.. ,gi-l, agi, gi+l, ... ) = W(gl, ... ,gi-l, gi, gi+l, ... ), Vgi E G,i E Z+,w E W} However, we will prefer the definition in the following equivalent forrtiulation: Nullx-+c(W) .- {f': X ----> G Iwf'f = wI, "If: X -+ G, Vw E W}, W*(G) = U imf· !ENullx_a(W) (IV.19) (IV.20) (IV.21) Notice f': X ----> G has imf' ~ W*(G) if, and only if, f' E Nullx-+c(W). Verbal subgroups are fully-invariant (F. Levi, [17]) while marginal subgroups are in general only characteristic (P. Hall, [17]). Example IV.4.1. (i) Let [X1J := Xl and [Xl, ... , Xc+lJ := [[Xl"", Xc]' Xc+l], c E N. If We = {[Xl",' ,xc+d}, then W(G) = IC+l(G), the (c+ 1)-st term in the lower central series. Also, W;(G) = (c(G), the c-th term in the upper central series of G [49, 2.3]. (ii) Let O(Xl) := Xl and O(Xl"",X2d+1) = [O(Xl"",X2d),O(X2d+l"",X2d+1)], dEN. If Wd = {O(Xl,'" ,X2d)}, then W(d)(G) = G(d) is the d-th derived group of G. It appears that W*(G) is not generally encountered and has no associated name. However, a philo- 97 sophically appropriate title might be the d-th upper derived subgroup of G, since WJ (G) is a solvable group of derived length d. However, it is not generally true that the quotients of the series Wtl) (G) ~ W(2) (G) ~ . .. are abelian. 3 Proposition IV.4.2. Given a class m of groups, the following are equivalent: (i) there is a countable nonempty set W of words such that GEm if, and only if, W(G) = 1; (ii) (P. Hall) there is a countable nonempty set W of words such that GEm if, and only if, W*(G) = 1; (iii) (G. Birkhoff) 1 E mand m is closed to homomorphic images, subgroups, and direct products. If m satisfies any of these properties then m is called a variety of groups. Given a set of words, the associated variety is denoted m(W). Proof. See [49, 2.3]. o Remark IV.4.3. Given sets of words W, W' ~ F[X], it is be possible that m(W) = m(W') with W =I W'. Therefore, the subgroups W (G) and W* (G) are not necessarily determined by the variety m(W), but rather by set of words W. Example IV.4.4. (i) The variety 91c := m([Xl"'" XC+l]) is the class of nilpotent groups of class at most c [32, Theorem 3.9]. (ii) The variety 6d := m(5(Xl,"" X2d)) is the class of solvable groups of derived length at most d [32, Theorem 3.20]. Definition IV.4.5. Am-subgroup H of a group G is a subgroup contained in the variety m. Proposition IV.4.6. Let m:= m(W) be a group variety and G a group. If H is a m-subgroup of G then so is W*(G)H, that is: W*(G)H Em. Proof. Let f : X -> G with im f ~ W* (G)H. As each element of W* (G)H has the form ah for a E W* (G) and h E H, choose functions f', f" from X to G where im f' ~ W* (G), im f" ~ M, and f = f'f" (pointwise). By the definition of W* (G), wI = wf' f II = wf" for all w E W. As HEm, W(H) = 1 and so wf" = 1 for all wE W. Thus, wI = 1 for all wE Wand all f: X -> G with imf ~ W*(G)H; that is, W(W*(G)H) = 1 and hence, W*(G)H Em. o 3Peter Neumann informs me that for reasons such as this, marginal subgroups are not generally used except in the context of nilpotent groups. Indeed, they do not appear in [11]. 98 IV.4·2 W-cores: O'XJ(G) Following Remark IVA.3 we know that W*(G) may depend on the choice of Wand might not be uniquely determined by the variety W(W). In this section we define a characteristic subgroup O'XJ(G) of G with properties similar to W*(G) which depends only on W(W), not W. Definition IVA.7. Fix a variety Wand a group G. (i) A subgroup M :::! G is a maximal normal W-subgroup if whenever M 2: N :::! G and NEW, then M = N. (ii) The W-core, O'XJ(G), of G is the intersection of all maximal normal W-subgroups of G. As 1 E W, the set of maximal normal W-subgroups of a group G is always nonempty. It can be a singleton set, Examples .(ii)-(iii), but it need not be, Example .(i). Also note that W is closed to subgroups so O'XJ(G) E W. Example IV.4.8. (i) 01)11 (G) is the intersection of all maximal normal abelian subgroups ofG. Generally there can be any number of maximal normal abelian subgroups of G so 01)11 (G) is not a trivial intersection. (ii) Omc (G) is the intersection of all maximal normal nilpotent subgroups of G with class at most c. If c > log IG I then all nilpotent subgroups of G have class at most c and therefore Om c (G) is the Fitting subgroup of G: the unique maximal normal nilpotent subgroup of G. (iii) Similar to (ii), OSd (G), d > log IGI, is the unique maximal normal solvable subgroup of G, i. e.: the solvable radical Os (G) of G. Proposition IVA.9. Let W := W(W) be a group variety and G a group. Then (i) W* (G) ::; O'XJ(W) (G), and (ii) if M:::! G then O'XJ(G)O'XJ(M) is a normal W-subgroup of G. Proof. (i). By Proposition IVA.6, every maximal normal W-subgroup of G contains W*(G). (ii). As M :::! G and O'XJ(M) is characteristic in M, it follows that O'XJ(M) is a normal W-subgroup of G. Thus, O'XJ(M) lies in a maximal normal W-subgroup N of G. As O'XJ(G) ::; N we have O'XJ(G)O'XJ(M) 2: NEW. As W is closed to subgroups, it follows that O'XJ(G)O'XJ(M) is in W. 0 99 Remark IV.4.IO. (i) If W, W' ~ F[X] with m(W) = m(W'), then OW(W)(G) = OW(W,)(G) and (W')*(G) ::::; OW(W)(G). (ii) It is possible to have W*(G) < OW(W)(O). For instance, with SJ11 = m((Xl,XZ]) and G = 83 X Cz, the marginal subgroup is the center 1 x Cz, whereas the SJ11-core is C3 x Cz. IV.4.3 Induced Decompositions with Margins and Cores We now prove that marginal and core subgroups behave well when considering direct decompositions. Throughout we assume W ~ F[X] and m= m(W) as defined in Section IV.4.I. Proposition IVA.II. Let G be a finite group with a direct decomposition 'H. Then . (i) 'Hnw*(G) = {W*(H) : H E 'H}, this is a direct decomposition ofW*(G), and'HW*(G)jW*(G) is a direct decomposition of GjW*(G); and (ii) 'HnOw(G) = {Ow(H) : H E 'H}, this is a direct decomposition ofOw(G), and'HOw(G)jOw(G) is a direct decomposition of GjOw (G) . In particular, margins and cores are generically split subgroups for any set ofwords and any variety. Proof (i). We must show that 'H n W*(G) = {W*(H) : H E 'H} and by Proposition IV.3.7 that W*(G) = ('H n W*(G). If 'H = {G} then these are true trivially. Fix H E 'H and set K:= ('H-{H}). By induction we may assume that ('H-{H})nW*(K) = {W*(K): K E 'H-{H}} and this is a direct decomposition of W*(K). As G = H x K, every f : X -t G decomposes uniquely as f = fH X fK, where fH : X -t H, fK : X -t K. Moreover, if w E W, then w1 = WfH x WfK. Take f~ : X -t H with im f~ ~ W*(H), and fi< : X -t K with imfi< ~ W*(K), and define!, : X -t G by !' = f~ x fi<. Thus, by the definition of W*(H) and W*(K), for each wE W: w!'f = w(J~ x fi<)(fH x !Id = (wf~fH) x (wfi MN, write f = fN X fK where fN : X --> Nand fK : X --> MK. Hence, wf = WfN X fK' = WfN X WfK' However, W(N) = 1 and W(MK ) = 1 as N,MK E QJ. Thus, wJ = 1, which proves that W(MN) = 1. So MN E QJ as claimed. As M is a maximal normal QJ-subgroup of G, M = MN and N = MH. Hence, H n M = N is a maximal normal QJ-subgroup of H. So we have characterized the maximal normal QJ- subgroups of G as the direct products of maximal normal QJ-subgroups of members H E H. Thus, H n Ol)J(G) = {Ol)J(H) : H E H} and this generates Ol)J(G). By Proposition IV.3.7, H n Ol)J(G) is a direct decomposition of Ol)J(G). 0 IV.4.4 QJ-separated Direct Decompositions In this section we define QJ-separated direct decompositions. These decompositions are direct decompositions which can be partitioned into subgroups lying in QJ, together with subgroups with no direct factors in QJ. This is the key organizational device for the proof of Theorem IV.1.3, through the use of Theorem IV.4.22. Definition IV.4.12. Let QJ be a variety and G a group with a direct decomposition H. (i) QJnH:={HEH:HEQJ}. 101 (ii) H - \21 := {H E H : H rf \21} = H - (\21 n H). (iii) H is \21-separated if each H E H - !1.1 has no direct factor in !1.1 (note 1 rf H). (iv) His \21-refined if it is \21-separated and every member ofH n!1.1 is directly indecomposable. Example IV.4.13. (i) For the variety sn1 of abelian groups, an snl-separated direct decompo- sition is a decomposition in which all nonabelian members have no abelian direct factors (recalling 1 is not a direct factor). (ii) Given a group G and the variety 6d, d > log IGI, an 6d-separated direct decomposition of G is a decomposition in which the nonsolvable members have no solvable direct factors. Proposition IV.4.14. Let \21 be a variety and G a finite group. (i) Every Remak decomposition of G is \21-separated and so every direct decomposition can be refined to a \21-separated decomposition of G. (ii) If H is a \21-separated direct decomposition of G then {(H - \21), (\21 n H)} is a \21-separated direct decomposition of G. (iii) IfH and K are any two !1.1-separated direct decompositions of G then (H -!1.1) U (\21 n K) is a !1.1-separated direct decomposition of G. (iv) If!1.1 = \21(W) and H is a \21-separated decomposition of G then (\21 n H) ~ W*(G). Proof. (i). Let H be a Remak decomposition of G. As every H E H is directly indecomposable, the only direct factor of H is H. Thus, the members of H - \21 have no direct factors in \21. So H is \21-separated. (ii). Let K be a Remak decomposition of G which refines H. As \21 is closed to subgroups, J := {K E K : 3H E \21 n H with K ~ H} ~ \21 n K. (IV.24) Furthermore, every K E K - J lies in some H E H - \21 and so is a direct factor of H. As H is \21-separated it follows that K rf \21, for any K E K - \21. Thus J = \21 n K. Set L := (H - \21) = (K - \21) = (K - J) and V = (\21 n K) = (\21 n H). We claim {L, V} is \21-separated. If L has a direct factor which lies in \21 then, as \21 is closed to subgroups, it follow that L has a directly indecomposable direct factor M which lies in \21. However, K - \21 is a Remak 102 decomposition of L (Proposition IV.3.3) and so M is isomorphic to a member of K - m (Theorem IV.3.11) and ME m by assumption. This is impossible as no member of K - m lies in m. Finally, as m is closed to direct products it follows that V E m. Thus {L, V} is m-separated. (iii). Let Hand K be two m-separated decompositions. Choose Remak decompositions :J and I:. which refine Hand K, respectively. Without loss of generality, assume that 1m n:J1 ~ 1m n 1:.1 (we will see shortly these are equal). By Theorem IV.3.11 applied to m n:J ~ :J and 1:., there is W ~ I:. such that I := (:J - m) u W is a Remak decomposition of G. Thus, I is m-separated by (i). Theorem IV.3.11 provides a 'P E Aut G such that (m n :J)'P = W. As m is closed to isomorphic images, it follows that W ~ mn 1:.. As Imnl:.l :::; Imn:J1 = IWI, mnl:. = W. Thus, I = (:J -m) u (mnl:.). As shown in the proof of (ii), :J - m refines H - m, and m n I:. refines m n K. Thus, Prop- osition IV.3.5 proves that (H - m) u (m n K) is a direct decomposition of G, and it is m-separated. (iv). Let V:= (m nH) and H:= (H - m). Fix wE w, f,!': X ~ G with im!, ~ V. As G = H x V we write f = fv X fH for unique fH : X ~ Hand fv ; X ~ V. As V E m, 1 = W(V) = {wg: g: X ~ V,W E W} so that wfi;fv = 1 = wfv for each w E W. Hence, wf'f = w(fi; x 1H)(fv x fH) = wfi;fv x WfH = WfH = WfH x wfv = wf. Hence, im!, ~ W*(G) so that V:::; W*(G). o Proposition IV.4.15. Let m= m(W), G be a group, such that Z(G) :::; W*(G) :::; M:s! G where M is generically split in G. If X is a Remak decomposition of M, then then either {G} is m- separated or there is a nonempty subset W ~ X and a subgroup H :::; G, such that G = H ~ (W). Furthermore, ifH is a m-refined direct decomposition ofG, then (Hnm)Z(M) = WZ(M). Proof If GEm then G = W*(G) = M and so any X is a m-separated direct decomposition of G. Thus we assume that G 1. m. Suppose that {G} is not m-separated. Then by Proposition IV.4.14.(ii) there is a direct decomposition {H, V} of G which is m-separated and 1 ::J V E m. Since M is generically split, {H n M, V n M} is a direct decomposition of M. By Proposition IV.4.14.(iv), V:::; W*(G) :::; M so that {H n M, V} is a direct decomposition of M. Let H be a Remak decomposition of G. Set Z := {Y E H : Y :::; V}, and then extend Z to a Remak decomposition Y of M. From Theorem 103 IV.3.11, applied to M and Z ~ Y, there is W ~ X such that (Y-Z)UW is a Remak decomposition of M. As V =11, 0 < 121 = IWI. Also, G = (H, V) = (H,Y-Z, W). As, Hn (W) :::: M, it follows that H n (W) = (H nM) n (W) = (Y - Z) n (W) = 1. So G = H ~ (W). By Corollary IV.3.14.(i), YZ(M) = «Y - Z) U W)Z(M), so ZZ(M) = WZ(M). 0 Iv'4.5 Central Reduction Algorithms Definition IVA.IB. A centrally-refined direct decomposition 1{ of a group G is a direct decompo- sition in which every abelian member is cyclic of prime power order, and every nonabelian member has no abelian direct factor. Theorem IVA.17. There is a deterministic polynomial-time algorithm which, given a group in iGn , returns a centrally-refined direct decomposition of G. Proof. Let G E iGn . Algorithm. Use the algorithm for Definition IVA.I9.(i) to compute Z(G). If Z(G) = 1 then return {G}. If Z(G) > 1, use the algorithm for Definition IVA.I9.(ii), find a Remak decomposition X for Z(G). Use (IV.2.12) to build W := {W EX: 3K :::: G, G = K x W}. Use (IV.2.12) to find K :::: G such that G = K x (W). Return {K} U W. Correctness. If Z (G) = 1 then G has no abelian direct factors and so {G} is a centrally- refined direct decomposition of G. Now assume Z(G) > 1 and that X is Remak decomposition of G. By Proposition IVA.I5, W, G = H ~ (W) with H having no central direct factor. As (W) :::: Z(G) it follows that G = H x (W) and {H}UW is a centrally-refined direct decomposition ofG. Timing. The algorithm uses G(log IGI) calls to polynomial-time algorithms for iGn . 0 Theorem IVA.IB. There is a deterministic polynomial-time algorithm which, given G E iGn and a decomposition 1{ of G, returns a centrally-refined direct decomposition K of G such that if JiM refines .JM for a generically split abelian subgroup M 2 Z(G) and a direct decomposition .J of G, then KM refines .JM . Proof. Algorithm. Begin with K := 0 and J:= 1 :::: G. Now loop over each HE 1{ and perform the following steps. Set J := (J, H) and use (IV.2.12) to construct.c := {K E K : 3X :::: J, J = KxX}. Use (IV.2.12) to compute X :::: J such that J = (.c) x X. Let X be the return of the algorithm 104 for Theorem IV.4.17 applied to X, and set K := .c U X. Then continue with the next term in the loop. When the loop ends, return K. Correctness. We claim the following loop invariants: J is generated by a subset of H, K is a centrally-refined direct decomposition of (K). At the end of each loop iteration, (K) = J and so at the end of the loop, J = G and so K is a centrally-refined direct decomposition of G. The loop invariants are initially true. It is also clear that J is generated by a subset of 7-{ and the loop ends once J = G. Within the loop, .c S;; K and so .c is a centrally-refined direct decomposition of (.c). By assumption, X is also a centrally-refined direct decomposition of X. As J = (.c) xX, it follows that .c U X is a centrally-refined direct decomposition of J. Hence, K is maintained as a centrally-refined direct decomposition of (K). Now suppose that 7-{M refines .:JM for some direct decomposition .:J of G. Suppose that H E H is the current iterate. By induction we assume that K refines (K) n.:J. By assumption, there is a unique JH E .:J such that H :::; JH M. Since H is not contained in (K) it is also not contained in (.c). As JH is a direct factor of G, J n JH is a direct factor of J. Furthermore, Z(G) :::; M ::; HM ::; JM so Z(G) :::; Z(JM). Thus, H:::; (J n hf)Z(JM). Therefore H lies in YZ(JM) for some (unique) direct factor Y of J; see Corollary IV.3.14.(i). By Corollary IV.3.14.(i) applied to J = (.c) x X, and the fact that H does not lie in .cZ(JM), it follows that H S; X Z (JM). As the members of K - .c satisfy (IV.13), it follows that X Z (J) ::; (J n JH) Z (JM) (inequality is possible). Thus, the updated K := (.c U X)Z(JM) refines (J n .:J)Z(JM). At the end of the loop, G = J and so KM refines .:JM. Timing. The algorithm uses polynomial time methods with [HI::; log IGI recursive calls. o IV.4.6 Reduction Algorithms In this section we provide the algorithms to reduce a direct decomposition of G/M(G), M E {W*, Omcw)} to a direct decomposition of G, see Theorem IVA.23. Throughout this section, we assume that QJ := QJ(W) is a group variety (Section IV.4.1) and that Gn is a computational domain (Section IV.2.2). Definition IV.4.19. A computational domain Gn is W -computable if there are polynomial-time algorithms (in n) for each of the following: 105 (i) given G E Gr" return generators for M (G), where M (G) is either W* (G) or O'!T(W) (G), and (ii) given G E Gn with G E QJ(W), return a Remak decomposition of G. Example IV.4.20. Let W = [Xl, X2], so QJ := QJ(W) is the group variety of abelian groups and the marginal subgroups W*(G) are the center of groups G E Gni see Example IV.4.4.(i). Then any computational domain Gn with the hypothesized routines of Section IV.2.2 (for example: QPERM, PRMAT, and Pc) are W-computable; see (IV. 2.8) and Proposition IV.2.15. Remark IV.4.21. It is possible that for some words Wand computational domains Gn , generators can be obtained for both W* (G) and O'!T(W) (G). In such a case either subgroup can be used as M(G) for the algorithms of this section. Theorem IV.4.22. Let Gn be W-computable and V := QJ(W). Then there is a deterministic polynomial-time algorithm which: given G E Gn , returns a QJ-separated direct decomposition 1t of G in which I'H - QJI ::; 1 and each member of QJ n 'H is directly indecomposable. Proof Algorithm. Use the algorithm for Definition IVA.19.(i) to compute M(G). If M(G) = 1 then return {G}. If M(G) > 1, use the algorithm for Definition IV.4.19.(ii), find a Remak decomposition X for M(G). Use (IV.2.12) to build W:= {W EX: :JZ(G) ::; K::; G,GjZ(G) = KjZ(G) x WZ(G)jZ(G)}. (IV.25) Use (IV.2.12) to find Z(G) ::; K ::; G such that GjZ(G) = KjZ(G) x (W)Z(G)jZ(G). Now apply the algorithm for Theorem IVA.18 to {K} U Wand return the output of that algorithm. Correctness. If M(G) = 1 then either 1 = O'!T(G) :2: W*(G) (Proposition IVA.9.(i)) or 1 = W*(G); in any case, W*(G) = 1. By Proposition IV.4.14.(iv), if G has a direct factor which lies in QJ then that factor lies in W*(G) = 1. Hence, G has no direct factor which lies in QJ and so {G} is QJ-separated. Now let M(G) > 1 and X be a Remak decomposition of M(G). The set 1t := {K} U W is a normal decomposition of G where 1t = 'HZ(G). Therefore, the algorithm of Theorem IVA.18 can be applied. Furthermore, Z(M) is characteristic in M and generically split in Z(M). As M is generically split in G, it follows by Proposition IV.3.1O that Z(M) is generically split in G. Thus, Theorem IVA.18 guarantees that the return is a centrally-refined direct decomposition K of G such 106 that if 1iZ(M) refines .:JZ(G) for a direct decomposition .:J of G, then KZ(M) refines .:JZ(M). By Proposition IVA.I5, we know 1iZ(M) refines .:JZ(M) for some QJ-refined direct decomposition of G, and thus the return is indeed QJ-refined. Timing. The algorithm applies polynomial-time algorithms O(log IGI) times. 0 Theorem IV.4.23. Let Gn be a W-computable computational domain where W*(G) ~ Z(G) for each G E Gn , and QJ := QJ(W). Then, there is a deterministic polynomial-time algorithm which: given G E Gn and a normal decomposition 1i of G, returns a QJ-refined direct decomposition K of G such that if 1iN refines .:JN for M(G) :::; N :::; G with N generically split in G, and .:J a direct decomposition of G, then KN refines .:IN. Proof Algorithm. Begin with K := 0 and J := 1 :::; G. Now loop over each H E 1i and perform the following steps. Set J:= (J, H) and use (IV.2.I2) to construct £ := {K E K : ::JX ~ J, J = KxX}. Use (IV.2.I2) to compute X ~ J such that J = (£) x X. Let X be the return of the algorithm for Theorem IVA.22 applied to X, and set K:= £ U X. Then continue with the next term in the loop. When the loop ends, return K. Correctness. We claim the following loop invariants: J is generated by a subset of 1i and K is a QJ-refined direct decomposition of (K). At the end of each loop iteration, (K) = J and so at the end of the loop, J = G and so K is a QJ-refined direct decomposition of G. The loop invariants are initially true. It is also clear that J is generated by a subset of 1i and the loop ends once J = G. Within the loop, £ ~ K and so £ is a QJ-refined direct decomposition of (£). By assumption, X is also a QJ-refined direct decomposition of X. As J = (£) xX, it follows that £ U X is a QJ-refined direct decomposition of J. Hence, K is maintained as again QJ-refined. Now suppose that 1iM refines .:JM for some direct decomposition .:J of G. Suppose that H E 1i is the current iterate. By induction we assume that K refines (K) n.:J. By assumption, there is a unique JH E .:J such that H ~ JHM. Since H is not contained in (K) it is also not contained in (£). As JH is a direct factor of G, J n JH is a direct factor of J. Furthermore, Z(G) ~ M(G) :s:; N so Z(G) :s:; Z(JN). Thus, H ~ (In hf)Z(JN). Therefore H lies in YZ(JN) for some (unique) direct factor Y of J; see Corollary IV.3.I4.(i). By Corollary IV.3.I4.(i) applied to J = (£) x X, and the fact that H does not lie in £Z (JN), it follows that H :::; X Z (JN). As the members ofK - £ satisfy (IV.I3), it follows that XZ(J) :s:; (J n JH)Z(JN). Thus, the updated K := (£ U X)Z (JN) refines (J n .:J)Z(J N). At the end of the loop, G = J and so KN refines .:JN. 107 Timing. The algorithm loops over the elements of 'H and within each loop it uses polynomial-time methods on a set of size at most I'HI. Thus, the algorithm uses O(I'HI) polynomial- time methods. D IV.4.7 Enrichment In this section we define the largest ring over which a biadditive map b is faithfully bilinear. In the next section, we show how this ring parameterizes the direct decompositions of b. This technique arose in [42, 43] to study the model theory of bilinear maps. Here the definitions are different (and apply more generally) but they are ultimately equivalent. Throughout this section let b : V x V -> W be a biadditive map of abelian p-groups V and W. Definition IV.4.24. Define Rich(b) := {(f, g) E End V EB End W : b(uf, v) = b(u, v)g = b(u, vJ), \:Iu, v E V}. This is the enrichment ring of b. The title of "enrichment" is justified by the following: Theorem IV.4.25. Let b : V x V -> W be 'a biadditive map. Then the following hold: (i) Rich(b) is a subring of End V EB End W, and V and W are (right) Rich(b)-modules. (ii) If b is K-bilinear, for a commutative ring K, then K/(AnnK V n AnnK W) embeds in Rich(b)OP. Whence, Rich (b) is the largest ring over which b is "faithful" bilinear, i.e.: AnnRich(b) V n AnnRich(b) W = o. Proof. (i). Set S:= RichR(b). Evidently S is closed to sums. For composition, let (f,g), (f',g') E S. Then for all u, v E V we have b(uff' , v) = b(uf,v)g' = b(u,vJ)g'= b(u,v)gg' .b(uff' , v) = b(uf,v)g' = b(u,vJ)g' = b(u,vfJ'). Hence (ff',gg') E S. 108 (ii). Let b be K-bilinear. As V and Ware K-modules, there are p : K -; End V and p : K -; End W such that rv = p(r)v and rw = p(r)w for v E V, w E W, and r E K. As b is K-bilinear, b(ru,v) = rb(u,v) = b(u,rv) so (p(r),p(r)) E Rich(b)OP. 0 Proposition IV.4.26. Ifradb = 0 and b(V, V) = W then Rich(b) is commutative. Proof For all (f, g), (f', g') E Rich(b) and u, v E V we have b(u[f, 1'], v) = b(u, vf1') - b(u, v1' f) = b(u, vf1') - b(u, v1')g = b(u,vf1') - b(u1',v)g = b(u,vf1') - b(u1',vJ) = b(u, v f 1') - b(u, v f 1') = o. This is easily repeated in the second variable to show that v[f, 1'] E rad b = 0, for all v E V. Thus, [f, 1'] = O. Also, b(U,V)[g,g'] = b(u,v)gg' - b(U,V)g'g = b(u,vf1') - b(u,v1'f) = b(u, v[f, 1']) = O. As W is generated by b(u,v), u,v E V, and b(u,V)[g,g'] = 0, it follows that [g,g'] = O. 0 Remark IV.4.27. If radb = 0 and (f,g), (f',g) E Rich(b) then f = 1'. If W = b(V, V) and (f,g),(f,g') E Rich(b) then 9 = g'. So ifradb = 0 and W = b(V,V) then the first variable determines the second and vice-versa. In this setting we write (f, j) for elements in Rich(b). IV.4·8 Direct Products of Bilinear Maps In this section we define the direct product of bilinear maps and then use the enrichment ring to parameterize the direct decompositions of a bilinear map. Let b : V x V -; Wand b ' : V' x V' -; W' be two K-bilinear maps. Then form b ED b' : V ED V' x V ED V' -; W ED W' by (b ffi b' )(u ffi u' , v ffi v') := b(u, v) ffi b(u' , v'). (IV.26) This makes b ffi b' an K.:bilinear map. This is the product in the category of K-bilinear maps. 109 We also have a natural internal description. Suppose that b : V x V --. W is an K-bilinear map. Then a direct decomposition of b is a set B <; PG(V) x PG(W) (here PG(X) denotes the set of K-submodules of an K-module X) such that V= EB Z, CU,Z)EB W = EB Z, and b(U, U) :::; z, V(U, Z) E B. CU,Z)EB (IV.27) This makes b naturally isomorphic (in the category of bilinear maps) to EBCU,Z)EB cCU,Z), where c(U,Z) : U xU --. Z is defined by c(u, v) := b(u, v) for all U,v E U. (Note that b(U, U') :::; Z nz' = 0 for distinct (U, Z), (U', Z') E B so that U and U' are perpendicular.) By standard linear algebra, given a direct decomposition X of an R-module V there is a corresponding set of pairwise orthogonal supplementary idempotents £(X) which are the projections of the decomposition. Therefore given a direct decomposition B of an K -bilinear map b : V x V --. W, we define £(B) as the set of ordered pairs (e,e) of projection endomorphisms e E EndK V, e E EndK W resulting from the direct factors in B. Likewise, given a set £ of supplementary idempotents of EndK V x EndK W, then B(£) := {(Ve, We) : (e,e) E £}. Theorem IV.4.28. Let b be a non-degenerate bilinear map and B a direct decomposition of b. (i) £(B) is a set of pairwise orthogonal supplementary idempotents ofRich(b) and B(£(B)) = B. (ii) B(£) is a direct decomposition of band £(B(£)) = £. (iii) B is fully refined if, and only if, £(B) is a frame of Rich(b). (iv) b is directly indecomposable if, and only if, Rich b is a local ring. Proof. These are readily verified, compare [42, Section 3]. o Corollary IV.4.29. Given a biadditive map b: V x V --. W where radb = 0 and W = b(V, V), there is a unique fully refined direct decomposition of b. Proof. By Proposition IVA.26, Rich(b) is commutative. Thus it has a unique direct decomposition into a product of local commutative rings, that is, it has a unique frame. Thus, by Theorem IV.4.28.(iii), b has a unique fully refined direct decomposition. o 110 IV.4.9 Finding Direct Decompositions of Bilinear Maps In this section we give an algorithm to find a direct decomposition of a bilinear map. The general setting depends on the work of Ronyai [50] on algorithms for associative algebras. However, the setting we require for Theorem IV.1.3 requires only the work of Berlekamp to factor polynomials over finite fields [8]. Thus the method is deterministic if the characteristic is small, otherwise, the method is only Las Vegas. Let b : V x V -4 W be a Zpe-bilinear map for which bases X and Z are known for V and W. Thus b(u, v) = uBvt as in (IV.11). In this notation we have: Rich(B) = {(F, G) E End V x End W: FB = B G = BFt }. (IV.28) We recognize FB = BG = BF t is a system oflinear equations over Zpe in the variables Fx,x' and Gz,z' , for x,x' E X, and z,z' E Z. This can be solved deterministically, see Section IV.2.3. Thus we have: Proposition IV.4.30. There is is a deterministic polynomial time algorithm which, given a Zpe- bilinear map b : V x V -4 W specified by bases X for V, Z for W, and structure constants matrix B with respect to these bases, returns a basis for Rich(b) as a subring of End V x End W. Theorem IV.4.31. There is a deterministic polynomial time algorithm, assuming an omde for polynomial factorization of a field of chamcteristic p, which given a Zpe -bilinear map b as in Proposition IV.4.30, returns a fully refined direct decomposition of b. Proof. Algorithm. Use Proposition IV.4.30 to compute Rich(b). Then use the algorithm of [50, 5.1] to find a frame Eof Rich(b)j J(Rich(b)) and apply the lifting of idempotents formula, Lemma IV.2.16, to t to obtain a frame £ of Rich(b). Return {bve : Ve x Ve -4 We: (e,e) E £}. Correctness. Let R := Rich(b). As RjJ(R) is a semisimple of characteristic dividing pe, it is in fact of characteristic p and a Zp-vector space. Thus pR ~ J(R). Hence, RjpR is a Zp-algebra, so [50, Section 5.1] can be applied to find a frame of E. As R is finite, J(R) is nilpotent and so we can apply the lifting of idempotents lemma to produce a frame of R. By Theorem IV.4.28, the return is a fully refined direct decomposition of b. Timing. The algorithms of [50, 5.1] are deterministic polynomial-time, up to the factoring of polynomials over finite fields of characteristic p. 0 111 Remark IV.4.32. (i) Berlekamp [7] provided a deterministic polynomial time algorithm to fac- tor polynomials over finite fields if the characteristic is small compared to the degree. His later Las Vegas method works in all characteristics, and subsequent algorithms have improved the timing, see [57, Chapter 14]. (ii) The method of [50, 5.1] can be replaced by the nearly optimal Monte Carlo method of [12]. For Las Vegas speedup, observe that Rich(b)jpRich(b) embeds in Md(Zp) ED MJ(Zp) where d = rank V and f = rank W. Thus, [22] can be applied as well. (iii) If rad b = 0 and W = b(V, V), then by Proposition IV.4.26, Rich(b) is commutative and there is a unique fully refined direct decomposition of b, (Corollary IV.4.29). Thus, instead of [50, 5.1] we may use [14], and in fact the entire problem is naturally equivalent to factoring polynomials, that is, it does not require the reductions used in [50] using general associative algebras. IV.5 The Remak Decomposition Algorithms In this section we prove Theorem IV.1.3. This relies on five distinct stages. First, in Section IV.5.1, a proof is given for p-groups of class 2. In Section IV.5.2 the algorithm is extended to p-groups of any class. Section IV.5.3 addresses solvable groups. Section IV.5.4 deals with almost semisimple groups, and Section IV.5.5 puts these methods together to prove Theorem IV.1.3. IV. 5.1 p-groups of Class 2 In this section we prove Theorem IV.1.3 for the case of p-groups P of class 2. The algorithm depends on a bilinear map associated to P, the algorithm of Theorem IV.4.31, and the algorithm of Theorem IV.4.22 where the variety is 1)11 , the variety of abelian groups (Corollary??). Write the operations of P j Z (P) and pi additively. A result of Baer [6] associates to P a bi- additive map b := Bi(PjZ(P), Pi) defined by b : PjZ(P)xPjZ(P) -> pi where b(Z(P)x, Z(P)y) := [x, y], for each x, yEP. Note that rad b = 0 and b(PjZ(P), PjZ(P)) = [P, PJ. Also, b is naturally Zpe-bilinear where ppe = 1. Theorem IV.5.l. There is a deterministic polynomial time algorithm which, given a p-group of class 2 in 2. Thus, P/(l(P) has class c - 1 and by induction the recursive call returns a decomposition 11. of P where 11. = 11.(l(P) and 11./(l(P) is a Remak decomposition of P/(l(P), Let R be a Remak decomposition of P. By Proposition IVA.ll, R(l(P)/(l (P) is a direct decomposition of P/(l(P). Hence, 11.(l(P/(l(P))/(l(P) refines R(1 (P/(l (P))/(l (P) by Corollary IV.3.14.(i) (applied to P/(l(P)). That is, 11.(2(P) refines R(2(P), Therefore, Corollary IV.5.2 applies and returns a lJh-separated direct decomposition K of G in which K(2(P) = R(2(P) and every member of 1)12nK is directly indecomposable. We now show that K is a Remak decomposition of P. As n is a Remak decomposition of P it is 1)12-separated. By Proposition IV.4.14.(iii), it follows that J ;= (R - 1)12) u (1)12 n K) is a direct decomposition of P. As the members of J are directly indecomposable it follows that J is a Remak decomposition of P. In particular, IR n 1)121 = IK n 1)121. Next, as K(2(P) = R(2(P) and both are 1)12-separated, it follows from Proposition IV.3.7.(ii) that IK -1)121 = IR -1)121· Thus, IKI = IK -1)121 + [1)12 n KI = IR -1)121 + 11)12 n RI = IRI· Hence, K is a direct decomposition of G of size equal to the size of a Remak decomposition of P: K is a Remak decomposition of P by Theorem IV.3.11. Timing. The algorithm depends on polynomial time algorithms in a recursion of depth c-2. D IV.5.3 Solvable Groups In this section we prove Theorem IV.1.3 for solvable groups. The algorithm has two phases. First if the group has a trivial center then the algorithm uses Sylow system to reduce to the case of a p-group, where it uses Theorem IV.5.3. The second phase uses a recursion to the centerless case together with Theorem IV.4.18 and Corollary IV.5.2. Theorem IV.5.4. There is a deterministic polynomial time algorithm which: given a solvable group in Gn with trivial center, returns a Remak decomposition of the group. 114 Proof Let G be a solvable group in Gn . Algorithm. If G = 1 then return 0. Otherwise, use (IV.2.11) to find a Sylow system S of G. For each PES, use Theorem IV.5.3 to find a Remak decomposition P(P) of P. Set K := UPES P(P). Then while there are distinct X, Y E K such that [X, Y] 1= 1, set K := (K - {X, Y}) u {(X, Y)}. When this loop completes, return K. Correctness. Assume G 1= 1 and note that lSI> 1 since G is not nilpotent (Z(G) = 1). By Theorem IV.5.3 we knowP(P) is a Remak decomposition of P for each PES. Let V := U PES P(P) be the set of vertices in a graph where edges are defined between members X and Y if, and only if, [X, Y] 1= 1. If X, Y, Z E V are vertices where X and Y lie in the same connected component and Z does not, then [Z, (X, Y)] = 1. Throughout the loop, K generates G. The loop ends when the distinct members of K pairwise centralize each other; that is, the loop returns the subgroups spanned by the connected components of the graph. Therefore, [H, K] = 1 for H, K E K, H 1= K. Furthermore, G = (S) = (P(P) : PES) = (K). Thus, some .:J ~ K is a central decomposition of G. However, Z(G) = 1 and 1 ¢:. K so .:J = K. Furthermore, as H n (1i - {H}) :S Z(G) = 1 for all H E K, we conclude that K is a direct decomposition of G. Now we prove that each K E K are directly indecomposable. Recall K = (Q E V : Q :S K). Suppose that K = A x B, A,B 1= 1 and take PES. As A and B are normal in K, {P n A, P n B} is a direct decomposition of P n K. Let Q be a Remak decomposition of P n K refining {P n A, P n B}. Notice that PK(P) := {Q E P(P) : Q :S K} is a direct decomposition of P n K consisting of directly indecomposable groups, thus, also a Remak decomposition of P n K. As PK(P) and Q are conjugate under a central automorphism of P n K, we can partition PK(P) to create a coarser direct decomposition {A(P),B(P)} which is conjugate under a central automorphism to {P n A, P n B}. As this is done for arbitrary PES it can be done for all PES. Now take Q,R E {Q E V: Q:S K} such that Q:S A(PA) and R:S B(PB) for PA,PB E S. Then [Q, R] :S [A, B] = 1. Letting R range over all possibilities we see that {Q E V : Q :S K} has at least two connected components, which contradicts the assumption of how K was built. Timing. Evidently we require integer factorization to find the primes dividing IGI, but ." 115 this is handled by an oracle. The recursion has depth equal to the number of prime divisors of IGI. Finally, the loop is a transitive closure and so it terminates in polynomial time. 0 Corollary IV.5.5. There is a deterministic polynomial time algorithm which: given a solvable group in Gn , returns a Remak decomposition of the group. Proof. Let G E Gn be a solvable group. Algorithm. If G is nilpotent then find the unique Sylow system S of G and apply the algorithm of Theorem IV.5.3 on each PES to obtain a Remak decomposition P(P) for each PES. Return UPES P(P). Now G is not nilpotent. If Z(G) = 1 then use Theorem IV.5A and return the output of that algorithm. Else, if (2(G) = (l(G) then use Theorem IV.5A to find a set H = H(l(G) such that H/(l(G) is a Remak decomposition of G/(l(G). Then apply Theorem IVA.I8 to return a Remak decomposition of G. Finally, if (2(G) > (l(G), use a recursive call to find H = H(l(G) such that H/(l(G) is a Remak decomposition of G/Z(G). Then apply the algorithm of Corollary IV.5.2 to H(2(G) and return the result. Correctness. If G is nilpotent this is clear, as is the case when (1 (G) = 1. If (2 (G) = (1 (G) then there is a unique Remak decomposition of G/(l(G) and so H refines R(l(G) for any Remak decomposition R of G. Thus, Corollary IVA.I8 applies to return a Remak decomposition of G. Otherwise, G > (2(G) > (1 (G) and by induction H/(l(G) is a Remak decomposition of G/(l(G). So H(2(G) refines R(2(G) and so Corollary IV.5.2 returns a Remak decomposition of G. Timing. The algorithm makes at most log IGI recursions using polynomial time algorithms in the base cases. o IV. 5.4 Almost Semisimple Groups In this section we prove Theorem IV.1.3 for almost semisimple groups, that is groups G with no proper normal abelian subgroups, equivalently 0 6 (G) = 1. The proof given is just one of many natural approaches for this case. Though it is not explicitly necessary in the following proofs, note that a group with trivial solvable radical has trivial center; hence, by Theorem IV.3.11, the group has a unique Remak decomposition. The socle, soc(G), of G is the subgroup generated by all minimal normal subgroups. 116 Lemma IV.5.6. IfG is a finite group with Oe(G) = I, then the set of minimal normal subgroups of G is a direct decomposition of soc(G). Proof See [49, pp. 85-88]. Theorem IV.5.7. Let G be a finite group with Oe(G) = 1 and direct decomposition 1i. Then (i) H n soc(G) = soc(H) for all H E 1i, (ii) 1i n soc(G) = {soc(H) : H E 1i} is a direct decomposition of soc(G), (iii) if M is the set of minimal normal subgroups of G, then M refines 1i n soc(G); and (iv) 1i = {CG(CG(soc(H))) : H E 1i}. o Proof. Since 1i is a direct decomposition of G, if H E 1i and M is a minimal normal subgroup of H, then M is a minimal normal subgroup of G. Thus soc(H) ~ H n soc(G). Now suppose that M is a minimal normal subgroup of G. Since each H E 1i is normal in G it follows that HnM is normal in G; hence, HnM is 1 or M. Suppose that HnM = 1 for all H E 1i. Hence, [H, M] ~ H n M = 1 for all H E 1i. Thus, [G, M] = [(1i) , M] = ([H, M] : H E 1i) = 1. This proves that M ~ Z(G) = 1. This is impossible as M > 1. Thus, there exists some HM E 1i such that HM n M = M, that is, M ~ HM. Since HM n K = 1 for all K E 1i - {HM}, it follows that M is not contained in any K E 1i - {H} and so H M is uniquely determined by M. To prove (i), note that H n soc(G) is normal in G and therefore generated by minimal normal subgroups of G contained in H. Thus H n soc(G) ~ soc(H). For (ii) and (iii), 1i n soc(G) = {soc(H) : HE 1i} = {(M EM: M ~ H) : H E 1i}, and by Lemma IV.5.6, M is a direct decomposition of soc(G). As M refines 1i n soc(G), 1i n soc(G) is a direct decomposition of soc(G), by Proposition IV.3.5. For (iv), fix HE 1i. Since G = Hx (1i-{H}) it follows that CG(soc(H)) = CH(soc(H)) x (1i - {H}). As soc(H) :::lH, CH(soc(H)):::l H and thus CH(soc(H)) = 1 or CH(soc(H)). The later means that CH(soc(H)) contains a minimal normal subgroup of Hand 1 < CH(soc(H))nsoc(H) ~ Z(soc(H)) = 1, which is impossible. So CG(soc(H)) = (1i - {H}) and CG(CG(soc(H)) = H, by reapplying the argument interchanging the roles of Hand (1i - {H}). 0 Theorem IV.5.S. There is a deterministic polynomial time algorithm which: given an almost semisimple group in CGn , returns a Remak decomposition of the group. 117 Proof Let G be an almost semisimple group in Gn . Algorithm. Use (IV.2.1O)to find a minimal normal subgroup N of G. Use (IV.2.8) to compute Gc(N). If Gc(N) = 1 then return {G}. Otherwise, recurse with Gc(N) in the role of G to find a Remak decomposition K of Gc(N). Use (IV.2.12) to create the set .c := {K E K : 3X :::; G, G = K x X}. Then (IV.2.12) to find H :::; G such that G = H x (.c). Return {H} u.c. Correctness. Let R. be the Remak decomposition of G. As N is a minimal normal subgroup of G as soc(G) is semisimple, it follows that N is a directly indecomposable direct factor of soc G. As R. n socG is a direct decomposition of socG, it follows that N .$ RN for a unique RN E R.. If Gc(N) = 1 then R. = {RN}' As R. generates G it follows that G = RN, or rather that {G} is the Remak decomposition of G. So now we assume that Gc(N) > l. As N is a direct product of nonabelian simple groups it follows that N i Gc(N) and so Gc(N) is smaller than G. If M