Printer Friendly

Polynomial-time normalizers.

1 Introduction

While algebraic methods are surely of core interest in computational complexity, a particular attraction of group-theoretic computation is its central role in the problem of testing graph isomorphism (ISO). Though rarely difficult in practice, ISO is not known to be solvable in polynomial time. Arguably, the most productive approaches to ISO have exploited its relation to a class of permutation-group problems usually represented by the following.

Problem 1

Given: a permutation group G [less than or equal to] Sym([OMEGA]) and a subset [DELTA] [subset or equal to] [OMEGA].

Find: the set stabilizer [Stab.sub.G]([DELTA]) = {g [member of] G | [[DELTA].sup.g] = [DELTA]}.

Problem 2

Given: permutation groups G, H [less than or equal to] Sym([OMEGA]).

Find: the intersection G [intersection] H.

Problem 3

Given: permutation groups G,H [less than or equal to] Sym([OMEGA]).

Find: the centralizer [C.sub.G](H) = {g [member of] G | [h.sup.g] = h for all h [member of] H}.

Problem 4

Given: permutation groups G,H [less than or equal to] Sym([OMEGA]).

Find: the normalizer [N.sub.G](H) = {g [member of] G | [H.sup.g] = H}.

As customary, we assume that a permutation group is input or output via a generating set S of permutations on a set . The input length is thus [absolute value of S][absolute value of [OMEGA]]. In fact, Sims's classical method [50] can be used to reduce the sizes of generating sets to O([absolute value of [OMEGA]]) (see, e.g., Jerrum [23], Knuth [28]). Hence, polynomial time for permutation groups is generally phrased as time polynomial in [absolute value of [OMEGA]].

Up to polynomial time, Problems 1-3 are equivalent, each is reducible to Problem 4, and ISO is reducible to any of the four problems. So, it is not surprising that, despite continued improvements in practical implementations (notably, in the computer algebra systems GAP [18] and MAGMA [9]), none of these problems is known to be solvable in polynomial time. On the other hand, the compelling evidence that ISO is unlikely to be NP-complete (see: Goldreich, Micali, and Wigderson [20, [section]2]; Schoning [48]) has been extended to decision versions of Problems 1-4 by Babai and Moran [8, [section]5]. This has motivated extensive investigation into polynomial-time computability for permutation-group problems in general but especially for Problems 1-4 (see [25], [35] for surveys).

Aside from the overall reducibility between these four problems, solutions geared to special classes of groups have facilitated polynomial-time algorithms for significant instances of ISO. For example, the solution to Problem 1 just for 2-groups yielded the first (and still the only known) polynomial-time approach to testing isomorphism of trivalent graphs (see [32, [section]2]). Subsequently, a polynomial-time set-stabilizer algorithm for the class of finite groups all of whose nonabelian composition factors are bounded (called the class [[GAMMA].sub.d] as defined below) yielded ISO in polynomial time for graphs of bounded valence (see Luks [32]) or bounded genus (see Miller [41]).

The polynomial-time solution to Problem 1 for G [member of] [[GAMMA].sub.d] led immediately to similar success with Problems 2, 3 for G [member of] [[GAMMA].sub.d]. However, the normalizer question for G [member of] [[GAMMA].sub.d] has remained open (see [35, Question 19]). The main result of this paper is its resolution.

The problem of finding normalizers is, of course, of both practical and theoretical interest. In practice, most implementations include backtrack search at some level and thereby have some potential to cause exponential worst-case running time (see [9], [18], [30], [53]). In fact, this exponential behavior has been observed even for instances of nilpotent groups (see [38], [39]).

Nevertheless, it was observed by Kantor and Luks [25, [section]10] that normalizers in nilpotent groups can be computed in polynomial time. Subsequently, a redesigned method of Luks, Rakoczi, and Wright [38] for nilpotent groups improved the polynomial timing to O([[absolute value of [OMEGA]].sup.4]).

In this paper, we consider the following class.

Definition For an integer d > 0, let [[GAMMA].sub.d] denote the class of finite groups all of whose nonabelian composition factors are isomorphic to subgroups of [S.sub.d].

Manifestly, [[GAMMA].sub.d] includes all solvable groups. As indicated, the class arises naturally in significant instances of ISO. It has also become an important subject of investigation in asymptotic group theory in its own right (see, e.g., [6], [45], [46]).

The key property that resolved Problems 1-3 for [[GAMMA].sub.d] groups was the following important result due to Babai, Cameron and Palfy: there is a function f(d) such that, if a subgroup G of [S.sub.n] is primitive with G [member of] [[GAMMA].sub.d], then [absolute value of G] = O([n.sup.f(d)]) (see [6, Theorem 1.1]). (In fact, [6] deals with a more general class of groups; for more on this, see the remark following Theorem 3.8.) This enabled a polynomial-time divide-and-conquer method that exploits orbits and blocks. As it was the convention used in [32] and other previous studies on computation involving [[GAMMA].sub.d] groups [7], [25], [35], [43], throughout this paper, we regard d as a fixed constant and thus complexity of the form O([[absolute value of [OMEGA]].sup.g(d)]), where g(d) is a function depending only on d, as polynomial time.

The aforementioned results of [32] concerning Problems 2, 3 assert that, given G,H [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], with no restriction on H, one can find G [intersection] H and [C.sub.G](H) in polynomial time. The gap in the theory has been the question of whether, given such G,H [less than or equal to] Sym([OMEGA]) with G [member of] [[GAMMA].sub.d], one can find [N.sub.G](H) in polynomial time. As a partial answer to this question, the authors announced in [36] that one can find [N.sub.G](H) in polynomial time if H [less than or equal to] G. We now completely resolve this question to fill the gap. The principal result of this paper is

Theorem 1.1 Given permutation groups G,H [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], one can find the normalizer [N.sub.G](H) in polynomial time.

Given Theorem 1.1, via a standard reduction, we also derive a polynomial-time solution to the equivalent decision problem.

Theorem 1.2 Given permutation groups G,[H.sub.1],[H.sub.2] [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], in polynomial time one can determine whether there is an element g [member of] G such that [H.sup.g.sub.1] = [H.sub.2] and, if so, exhibit such g.

In [25], Kantor and Luks hypothesized, in a quotient-group thesis, namely, that problems that are in polynomial time for permutation groups remain in polynomial time when applied to quotients of permutation groups.(i) In the spirit of this thesis, we extend these results to quotient groups via a method inspired by the Frattini argument (see [25, [section]7]).

Theorem 1.3 Given permutation groups G,K [less than or equal to] Sym([OMEGA]) such that K is a normal subgroup of G, and G/K [member of] [[GAMMA].sub.d], in polynomial time one can solve the following problems.

(i) Given a permutation group H [less than or equal to] Sym([OMEGA]) such that K is a normal subgroup of H, find the normalizer [N.sub.G](H).

(ii) Given permutation groups [H.sub.1],[H.sub.2] [less than or equal to] Sym([OMEGA]) such that K is a normal subgroup of both [H.sub.1] and [H.sub.2], determine whether there is an element g [member of] G such that [H.sup.g.sub.1] = [H.sub.2] and, if so, exhibit such g.

The overall algorithm for Theorem 1.1 utilizes the G-chief series of ([H.sup.G]) and, though reorganized here for clarity of our concerns, is thereby in the spirit of earlier normalizer computations (see, e.g., [14], [19], [39]). Thus, we reduce to the case where, for each chief factor L/K, H covers (HL = HK) or avoids (H [intersection] L = H [intersection] K). We focus then on instances M > L > K in the chief series such that H covers M/L but avoids L/K and seek the normalizer of (H [intersection] M)K/K in the action of G on M/K. For both these phases, we appeal, for polynomial time, to special properties of [[GAMMA].sub.d]. We utilize algorithms for each of Problems 1-3, but extensions of these are required as well.

We recall that the divide-and-conquer method that resolved Problems 1-3 exploits orbits and, in the transitive case, uses the primitive action on a block system to break the group into a 'small' number of cosets of the intransitive stabilizer of the blocks. This method is routinely used in our normalizer algorithm as well. But we further develop an analogue of this divide-and-conquer paradigm for matrix-group computation, since the normalizer problem even for permutation groups naturally leads to instances of finding stabilizers of subspaces in certain matrix groups. Whereas the permutation-group divide-and-conquer paradigm utilized orbits and imprimitivity blocks, the matrix-group analog, first introduced in [34, [section]6], makes use of invariant subspaces and systems of imprimitivity (cf. the computational matrix group project [29] that uses Aschbacher's classification [1]).

Using this matrix-group divide-and-conquer paradigm, we prove in particular the following result, which is required in our proof of Theorem 1.1 but may also be of independent interest (cf. [35, [section]10]).

Let V be an n-dimensional vector space over a finite field k of order [q.sup.e] for some prime q.

Theorem 1.4 Given a permutation group G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d] and a representation [phi] : G [right arrow] GL(V), one can solve the following problems in time polynomial in [absolute value of [OMEGA]], n, q and e.

(i) Given a vector v [member of] V , find the vector stabilizer [C.sub.G](v).

(ii) Given a subspace W [less than or equal to] V, find the subspace stabilizer [N.sub.G](W).

In this theorem, the characteristic q of the underlying field k is involved in the running time. This parametrization enables us to call Ronyai's deterministic algorithm for finding invariant subspaces from [47, [section]5] (while, if we appeal to his Las Vegas version instead, we can accomplish the same task in Las Vegas polynomial time in [absolute value of [OMEGA]], n, log q and e, replacing q by log q). For our applications to the problem of finding normalizers in permutation groups, all of the parameters n, q and e of V will be polynomially bounded in [absolute value of [OMEGA]].

We remark that, more generally, Theorem 1.4 and its underlying divide-and-conquer machinery, which will be presented in [section]5, also apply to manageable groups, i.e., [[GAMMA].sub.d] groups with polynomial-time procedures for constructive membership-testing (see Luks [34] and Miyazaki [43]). Indeed, [section]5 fills necessary details on the divide-and-conquer machinery for solvable matrix groups that were only outlined in [34, [section]6] (in particular, [section]5.2 clarifies an important reduction in [34, [section]6.2] and [43, [section]IV.2]). While we will often reference and employ other basic results proven in [34] in the present paper, such references will be limited to those in the earlier sections, namely, [34, [subsection]1-4].

In a future paper [37], the authors hope to elaborate on some analogues of the results herein for matrix groups in [[GAMMA].sub.d].

Finally, we emphasize that our goal is a clear resolution of the polynomial-time issue. With this in mind, in several places, we have striven to simplify the exposition at the expense of both low-level complexity and practical efficiency. We specifically reserve the latter concern for future investigation wherein it will be coupled with more general techniques for implementing polynomial-time centralizers and normalizers in classes of matrix groups (see [37], [43]).

We will appeal to the Classification of the Finite Simple Groups (CFSG) through several subroutines to prove Theorems 1.1-1.4. We will mark key results that depend on CFSG by "(CFSG)".

Organization of the paper In [section]2, we will review basic definitions and notation. In [section]3, we will recall elements of the known polynomial-time library for permutation groups, and we will further expand the library to include several subroutines needed for the normalizer algorithm. In [section]4, we will describe the overall architecture of the main algorithm and prove Theorems 1.1-1.3. Then, in [section]5, we will describe in detail the key subroutine for finding stabilizers of vectors and subspaces to prove Theorem 1.4.

The development requires statements of a large number of problems; with the exception of Problems 1-4 for general groups, all of these are shown to be in polynomial time. To facilitate searches for cited subroutines, we have numbered the problems and, where necessary, followed the problem statements with propositions (or lemmas or corollaries) that establish polynomial-time complexity.

2 Preliminaries

For the reader's convenience, we first review some basic definitions and notation of permutation and linear representations. We also summarize some standard conventions for computing with groups. Our general reference on finite group theory is [2].

2.1 Permutation representations

We denote by Sym([OMEGA]) the symmetric group of all permutations on an n-element set or by [S.sub.n] if the underlying set does not require explication. Throughout this subsection, let a group G act on such a set [OMEGA] via a homomorphism [pi] : G [right arrow] Sym([OMEGA]). We call n the degree of [pi]; if G [less than or equal to] Sym([OMEGA]), where [pi] is regarded as the natural injection, then we call n the degree of G.

For g [member of] G, we denote the images of [alpha] [member of] [OMEGA] and [DELTA] [subset or equal to] [OMEGA] under [pi](g) by [[alpha].sup.g] and [[DELTA].sup.g], respectively. The orbit of [alpha] [member of] [OMEGA] under G is [[alpha].sup.G] := {[[alpha].sup.g] | g [member of] G}. If itself forms a single orbit, then we call G (as well as [pi]) transitive.

For [alpha] [member of] , the point stabilizer of [alpha] in G is the subgroup [G.sub.[alpha]] := {g [member of] G | [[alpha].sup.g] = [alpha]}. For [DELTA] [subset or equal to] [OMEGA], the pointwise stabilizer of [DELTA] in G is the subgroup [G.sub.[DELTA]] := {g [member of] G | [[delta].sup.g] = [delta] for all [delta] [member of] [DELTA]}, whereas the set stabilizer of [DELTA] in G is the subgroup [Stab.sub.G]([DELTA]) := {g [member of] G | [[DELTA].sup.g] = [DELTA]}. If [OMEGA] possesses a group structure with G acting as automorphisms, then we often write [C.sub.G]([alpha]), [C.sub.G]([DELTA]) and [N.sub.G]([DELTA]) to denote [G.sub.[alpha]], [G.sub.[DELTA]] and [Stab.sub.G]([DELTA]), respectively. For x [member of] Sym([OMEGA]), the support of x is supp(x) := {[alpha] [member of] [OMEGA] | [[alpha].sup.x] [not equal to] [alp whereas the fixed points of x is fix(x) := {[alpha] [member of] [OMEGA] | [[alpha].sup.x] = [alpha]}. We also write fix(G) := {[alpha] [member of] [OMEGA] | [[alpha].sup.g] = [alpha] for all g [member of] G}; again, if [OMEGA] possesses a group structure with G acting as automorphisms, then we often write C(G) := fix(G).

For G-invariant [DELTA] [subset or equal to] [OMEGA] (that is, [[DELTA].sup.g] = [DELTA] for all g [member of] G), we call the restriction of [pi] to [DELTA], denoted by [pi]|[DELTA] : G [right arrow] Sym([DELTA]), the constituent of [pi] on [DELTA] and its image [G.sup.[DELTA]] := [pi]|[DELTA](G) the constituent of G on [DELTA], if [DELTA] is an orbit, then we call both [pi]|[DELTA] and [G.sup.[DELTA]] transitive constituents.

Assume that G is transitive on [OMEGA]. A subset [DELTA] [subset or equal to] [OMEGA] is a block if, for each g [member of] G, either [[DELTA].sup.g] = [DELTA] or [[DELTA].sup.g] [intersection] [DELTA] = [empty set]. We call the set of all images of a block, forming a G-invariant partition of [OMEGA], a system of blocks. If G has no system of blocks other than the partition into singletons and the partition with [OMEGA] itself, then we call G (as well as [pi]) primitive.

2.2 Linear representations

Let k be a field and V be an n-dimensional vector space over k. We denote by [End.sub.k](V ) the algebra of k-linear endomorphisms of V and by GL(V ) = GL(V, k) the general linear group of all units of [End.sub.k](V). Throughout this subsection, let a group G act on V via a homomorphism [phi] : G [right arrow] GL(V). We say V is a kG-module. We call n the degree of [phi] over k; if G [less than or equal to] GL(V), where [phi] is regarded as the natural injection, then we call n the degree of G over k. Since GL(V) [less than or equal to] Sym(V), the notation of permutation representations applies to G.

A subspace W of V is a kG-submodule if [W.sup.g] = W for all g [member of] G. If the only kG-submodules are 0 and V , then we call V (as well as G and [phi]) irreducible. If V is a direct sum of irreducible kG-submodules, then we call V (as well as G and [phi]) completely reducible.

Suppose that V is completely reducible. For an irreducible kG-submodule W of V , the kG-homogeneous component of V determined by W is the kG-submodule generated by all irreducible kG-submodules of V that are kG-isomorphic to W (here, for kG-modules X, Y , a kG-homomorphism is a k-linear map [psi] : X [right arrow] Y commuting with the actions of G in the sense that [psi]([x.sup.g]) = [psi][(x).sup.g] for all x [member of] X and g [member of] G). The (canonical) isotypic decomposition of V is the direct sum of its kG-homogeneous components. If V itself forms one kG-homogeneous component, then we call V (as well as G and [phi]) kG-homogeneous.

If V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m], m [greater than or equal to] 2, and G permutes [V.sub.1],..., [V.sub.m] as a transitive permutation group of degree m under [phi], then we call V := {[V.sub.1],..., [V.sub.m]} a system of imprimitivity. If the induced permutation representation of G on V is primitive, then we call V a minimal system of imprimitivity. If V is an irreducible kG-module but has no system of imprimitivity, then we call V (as well as G and [phi]) primitive.

Let f : G [right arrow] V be a function. If f(gh) = f[(g).sup.h] + f(h) for all g, h [member of] G, then we call f a 1-cocycle. This also means that f is a 1-cocycle if and only if the extension of [phi] to [[phi].sub.f] : G [right arrow] GL(V [direct sum]k) defined by

(v, a)[[phi].sub.f] (g) := ([v.sup.g] + af(g), a)

for v [member of] V, a [member of] k and g [member of] G is a homomorphism. The set of all 1-cocycles from G to V, denoted by [Z.sub.1](G, V), forms a kG-module via (f + f')(g) := f(g) + f'(g), (af)(g) := a(f(g)) and [f.sup.h](g) := f[([g.sup.h-1]).sup.h] for f, f' [member of] [Z.sub.1](G, V), g, h [member of] G and a [member of] k.

An element e of [End.sub.k](V) is unipotent if all characteristic values of e are equal to 1 [member of] k. A subgroup G of GL(V) is unipotent if all elements of G are unipotent; if char k = p, then G is unipotent if and only if G is a p-group.

2.3 Computational conventions

We summarize some standard computational conventions in the generality of abstract finite groups equipped with polynomial-time procedures to compute products and inverses of elements (for the related abstract notion of black-box groups, see, e.g., [49, Chapter 2]).

We again emphasize that, for both input and output, groups ares specified by generators, unless stated otherwise. In this subsection, assume that we are given a group G = <S>.

All algorithms identifying group elements are constructive and computed via the following notion of a straight-line program: For g [member of] G, a straight-line program to reach g from S is a sequence ([g.sub.1],..., [g.sub.l]) such that [g.sub.l] = g and, for i = 1,..., l - 1, one of the following holds:

[g.sub.i] [member of] S, [g.sub.i] = [g.sup.-1.sub.j] for some j < i, or [g.sub.i] = [g.sub.j][g.sub.k] for some j, k < i.

Consider a homomorphism [pi] : G [right arrow] M. In computational situations, [pi] is specified by the image [pi](s) of each s [member of] S, and the image [pi](g) of g [member of] G is computed via a straight-line program to reach g from S. For a representation [phi] : G [right arrow] GL(V), where V is a finite dimensional vector space over a field k, a 1-cocycle f : G [right arrow] V is specified by the image f(s) of each s [member of] S. The image f(g) of g [member of] G is then computed via

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] is evaluated using a straight-line program to reach g from S.

Consider a coset Gx. In computational situations, Gx is specified by a pair consisting of generators for G and any coset representative. A subcoset of Gx is a subset of Gx that is either empty or a coset of a subgroup of G. Certain subcosets are defined by predicates that can be easily evaluated (for example, consider, for G [less than or equal to] Sym([OMEGA]) and [[DELTA].sub.1],[[DELTA].sub.2] [subset or equal to] [OMEGA], the subset transporter [Trans.sub.G]([[DELTA].sub.1],[[DELTA].sub.2]) := {g [member of] G | [[DELTA].sup.g.sub.1] = [[DELTA].sub.2]}). In general, for a subcoset Hy [subset or equal to] Gx (using the notation Hy even if it may be empty), when generators for H and a coset representative are not necessarily available at hand, if we are given a polynomial-time procedure to determine, for any given z [member of] Gx, whether z [member of] Hy, then we say Hy is (polynomial-time) recognizable.

The length of a subgroup series is often essential to polynomial running time of algorithms. In [S.sub.n], by Lagrange's theorem, a series of subgroups has length at most log n! = O(n log n), and this bound will be sufficient for our purposes (though, for optimum O(n) bounds, see [5], [12]).

3 Polynomial-time library

In [subsection]3.1-3.4, we will review relevant portions of the known polynomial-time library for permutation groups. In [subsection]3.5-3.7, we will introduce some new additional tools. For further details on [subsection]3.1-3.4, we refer to [25], [35].

3.1 Basic tools

We first summarize some of the most fundamental results (see [17], [24], [33], [35], [49], [50]).

Theorem 3.1 Given G = <S> [less than or equal to] Sym([OMEGA]), in polynomial time one can solve the following problems.

(i) Given [alpha] [member of] [OMEGA], list the orbit [[alpha].sup.G] and test the transitivity of G.

(ii) Test whether G is primitive and, if not, find a non-trivial block system.

(iii) Given a recognizable subgroup H of G such that [absolute value of G : H] = O([[absolute value of [OMEGA]].sup.c]) for a constant c > 0 (specified by a polynomial-time procedure to test, for given g [member of] G, whether g [member of] H), find generators for H and a complete set of coset representatives for H in G.

(iv) Find [absolute value of G].

(v) Given x [member of] Sym([OMEGA]), test whether x [member of] G and, if so, exhibit a straight-line program to reach x from S.

(vi) Given a homomorphism [pi] : G [right arrow] Sym([OMEGA]') (defined on generators),

(a) find Ker [pi],

(b) for given M [less than or equal to] [pi](G), find [[pi].sup.-1](M) = {g [member of] G | [pi](g) [member of]M}.

(vii) Find the derived series of G and test the solvability of G.

(viii) Given N [less than or equal to] Sym([OMEGA]) such that N is normalized by G,

(a) find [C.sub.G](N) (including, in particular, Z(G)),

(b) find G [intersection] N,

(c) for given x [member of] GN, find g [member of] G and n [member of] N such that x = gn.

(ix) Find a composition series of G.

(x) Find a chief series of G.

(xi) (CFSG) Given a prime p dividing [absolute value of G], find a Sylow p-subgroup of G; furthermore, given such subgroups [P.sub.1] and [P.sub.2] of G, find g [member of] G such that [P.sup.g.sub.1] = [P.sub.2]. [there does not exist]

It is well-known that Problems (i), (ii) can be solved easily by elementary combinatorial methods (see, e.g., [35, 3.1, 3.2]). Problems (iii)-(v) were first shown to be in polynomial time in [17] using a variant of Sims's method [50].

For Problem (vi)(a), under the induced action [phi] : G [right arrow] Sym([OMEGA] [union] [OMEGA]'), it suffices to find the pointwise stabilizer of [OMEGA]' in [phi](G) via Problem (iii) (see also [33, Lemma 1.1(8)]). For Problem (vi)(b), given M = <X>, it is sufficient to find a small set Y [subset or equal to] G such that [pi](Y) = X from straight-line programs to reach x [member of] X from [pi](S) via Problem (v), for [[pi].sup.-1](M) = <Y [union] Ker [pi]>.

Problem (vii) is an easy extension of Problem (v) (see, e.g., [35, 3.12]), and Problem (viii)(b) is an extension of Problem (iii) (see, e.g., [35, Proposition 7.1]). To solve Problem (viii)(c), given N = <T>, it suffices to form a straight-line program P to reach x from S [union] T, for a factor g of x may be obtained by substituting in P each occurrence of t [member of] T by 1 [member of] Sym([OMEGA]).

Problem (ix) was first shown in to be in polynomial time in [33]. A polynomial-time algorithm for Problem (viii)(a) was also given originally in [33, [section]3] as one of the key subroutines for Problem (ix) (cf. [35, Proposition 7.3]). It is an application of [33], [47] that Problem (x) is in polynomial time (see, e.g., [25, [section]4]).

Polynomial-time solutions to Problem (xi) are due to the seminal work of Kantor [24] and extensively use CFSG.

3.2 The quotient-group thesis

As suggested in the quotient-group thesis in [25], all known problems that are in polynomial time for permutation groups remain in polynomial time when applied to quotients of permutation groups. For our purposes, we essentially require the ability to solve in quotient groups only the most fundamental Problems (iv)-(viii) of Theorem 3.1.

Polynomial-time solutions to the quotient-group versions of Problems (iv)-(vii), (viii)(b), (c) are immediate from Theorem 3.1(iv)-(vii), (viii)(b), (c), respectively.(ii) However, for Problem (viii)(a), despite the elementary nature of the method for Theorem 3.1(viii)(a), as far as we know, the justification of the thesis is not routine. The next lemma from [25, [section]6] involves construction of Sylow subgroups via Theorem 3.1(xi) and thus must appeal to CFSG (cf. [35, [section]8]).

Throughout this paper, a quotient group G := G/K, where K [??] G [less than or equal to] Sym([OMEGA]), is specified by a pair consisting of generating sets for G and K, and an element g [member of] G is specified by a coset representative g [member of] G such that g = Kg.

Lemma 3.2 (Kantor-Luks)(CFSG) For G = G/K, where K [??] G [less than or equal to] Sym([OMEGA]), given H,N [less than or equal to] G such that H normalizes N, one can find [C.sub.H](N) (including, in particular, Z(H)) in polynomial time. [there does not exist]

3.3 Centralizers and normalizers in Sym([OMEGA])

In the following, we discuss some polynomial-time tools for finding centralizers and special instances of normalizers in Sym([OMEGA]).

We begin with

Problem 5

Given: G [less than or equal to] Sym([OMEGA]).

Find: [C.sub.Sym([OMEGA])](G).

The following is a well-known fact (see, e.g., [49, [section]6.1.2]).

Lemma 3.3 Problem 5 is in polynomial time. 2

Next, we consider

Problem 6

Given: E [less than or equal to] Sym([OMEGA]) such that E is elementary abelian and isomorphic to a direct product of its transitive constituents.

Find: [N.sub.Sym([OMEGA])](E).

Lemma 3.4 Problem 6 is in polynomial time.

Proof: Let [[DELTA].sub.i], i = 1,..., l, be the orbits of E so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (i.e., for each i, the action of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] on [[DELTA].sub.i] is regular).

For i = 1,..., l, let [N.sub.i] := {x [member of] [N.sub.Sym([OMEGA])](E) | supp(x) [subset or equal to] [DELTA].sub.i]} and [C.sub.i] := [C.sub.Sym([OMEGA])](E) [intersection] [N.sub.i]. Notice now that, if we regard each [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] as a vector space, then each [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. With this correspondence in hand, we construct, for i = 1,..., l, a small set (e.g., of size 2) [T.sub.i] for which [N.sub.i] = <[T.sub.i], [C.sub.i]> (here, we construct [T.sub.i] only, though [C.sub.i] and thus [N.sub.i] are computable in polynomial time).

It now remains to find, for each pair of orbits [[DELTA].sub.i] and [[DELTA].sub.j] of the same length, a transposition [x.sub.ij] [member of] [N.sub.Sym([OMEGA])](E) that switches [[DELTA].sub.i] and [[DELTA].sub.j], leaving the remaining points of [OMEGA] fixed. Indeed, [C.sub.Sym([OMEGA])](E) includes such transpositions since, for each such pair [[DELTA].sub.i] and [[DELTA].sub.j], the regular E-action on [[DELTA].sub.i] is equivalent to that on [[DELTA].sub.j]. Thus, we return <[T.sub.1],..., [T.sub.l], [C.sub.Sym([OMEGA])](E)> = [N.sub.Sym([OMEGA])](E). [there does not exist]

Remark Problem 6 is not known to be in polynomial time if we remove the assumption that G is isomorphic to a direct product of its transitive constituents. In fact, without such an assumption, ISO is reducible to this problem (see [35, [section]10]).

Via Problem 5, the following two additional problems are also in polynomial time.

Problem 7

Instance: G,H [less than or equal to] Sym([OMEGA]) and an isomorphism [pi] : G [??] H (defined on generators of G).

Question: Is there x [member of] Sym([OMEGA]) such that [pi](g) = [g.sup.x] for all g [member of] G? If so, exhibit such x.

Lemma 3.5 Problem 7 is in polynomial time.

Proof: Consider an action [phi] : G [right arrow] Sym([OMEGA] x {1, 2}) defined by [([alpha], 1).sup.[phi](g)] := ([[alpha].sup.g], 1) and [([alpha], 2).sup.[phi](g)] := ([[alpha].sup.[pi]](g), 2) for [alpha] [member of] [OMEGA] and g [member of] G. Via Problem 5, we find C := [C.sub.Sym([OMEGA]x{1,2})]([phi](G)); here, C acts on the set of the orbits of [phi](G), say, D := {[[DELTA].sub.1],..., [[DELTA].sub.m]} via [psi] : C [right arrow] Sym(D). Then there is an appropriate element x [member of] Sym([OMEGA]) if and only if, for each orbit [[DELTA].sub.i], exactly half of the sets in [[DELTA].sup.[psi](C).sub.i] lie in [OMEGA] x {1} (see, e.g., [49, [section]6.1.2]). If this holds, it is easy to find y [member of] C such that [([OMEGA] x {1}).sup.y] = [OMEGA] x {2} (in fact, for each orbit [[DELTA].sub.i], C induces the symmetric group on [[DELTA].sup.[psi](C).sub.i]). The desired element x is then defined by [([alpha], 1).sup.y] = ([[alpha].sup.x], 2). [there does not exist]

Remark In general, for G = <S> [less than or equal to] Sym([OMEGA]) and M [less than or equal to] Sym([OMEGA]'), it is easy to determine whether a given function [pi] : S [member of] M is extendible to a homomorphism (resp. isomorphism) G [right arrow] M (cf. [25, [section]4]). To see this, let D := <(s, [pi](s)) | s [member of] S> [less than or equal to] Sym([OMEGA]) x Sym([OMEGA]'). Then [pi] extends to a homomorphism (resp. isomorphism) if and only if [absolute value of D] = [absolute value of G] (resp. [absolute value of D] = [absolute value of G] = [absolute value of M]).

Problem 8

Instance: G [less than or equal to] Sym([OMEGA]) and [sigma] [member of] Aut(G) (defined on generators).

Question: Is [sigma] [member of] Inn(G)? If so, exhibit [alpha] [member of] G such that [g.sup.a] = [g.sup.[sigma]] for all g [member of] G.

Lemma 3.6 Problem 8 is in polynomial time.

Proof: We first find, via Problem 7, x [member of] Sym([OMEGA]) such that [g.sup.x] = [g.sup.[sigma]] for all g [member of] G. We then test whether x [member of] [G.sub.Sym([OMEGA])](G), and if so, using Theorem 3.1(viii)(c), find [alpha] [member of] G and c [member of] [C.sub.Sym([OMEGA])](G) such that x = ac. It suffices to return a. [there does not exist]

Remark Lemma 3.6 answers an open question of Kantor and Luks posed in [25, [section]13].

3.4 Tools for [[GAMMA].sub.d]

In the class [[GAMMA].sub.d], there are polynomial-time solutions to a number of permutation-group problems that resemble ISO. The following results from [32] concerning Problems 1-3 are particularly well-known (cf. [35, Corollary 6.4]).

Theorem 3.7 (Luks) Given G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], in polynomial time one can solve the following problems.

(i) Given [DELTA] [subset or equal to] [OMEGA], find [Stab.sub.G]([DELTA]).

(ii) Given H [less than or equal to] Sym([OMEGA]), find G [intersection] H.

(iii) Given H [less than or equal to] Sym([OMEGA]), find [C.sub.G](H).

In fact, Theorem 3.7 was first proved in [32] under the stronger assumption that all composition factors, both abelian and nonabelian, were in [S.sub.d]. With a view toward extending the applicability of the methods, Babai, Cameron and Palfy subsequently derived the following important result in [6, Theorem 1.1].

Theorem 3.8 (Babai-Cameron-Palfy) There is a function f(d) satisfying the following: if G is a primitive permutation group of degree n such that G [member of] [[GAMMA].sub.d], then [absolute value of G] = O([n.sup.f(d)]). [there does not exist]

Remark (i) An earlier version of Theorem 3.8 was also proved in [32] under the assumption that all composition factors were in [S.sub.d], and this sufficed for the graph-isomorphism application. In fact, [6] weakened the restriction on composition factors even further than our assumption in Theorem 3.8; specifically, [6] deals with [A.sub.d]-free groups, in which no section (i.e., quotient of any subgroup) is isomorphic to [A.sub.d] (cf. [46]). However, we require the present definition of [[GAMMA].sub.d] to derive another crucial polynomial bound in linear groups in Proposition 5.7. Our definition of [[GAMMA].sub.d] is also the same as that of [35].

(ii) The function f(d) has been investigated further (see [7]). By [45], it was improved from O(d log d) to O(d) for [A.sub.d]-free groups (cf. [31]). Divide and conquer using orbits and blocks. The divide-and-conquer paradigm that motivated Theorem 3.8 applies to problems that ask for construction of a recognizable subcoset of a given coset Gx in X [less than or equal to] Sym([OMEGA]), where G [member of] [[GAMMA].sub.d], equipped with a representation X [right arrow] Sym([SIGMA]) and a G-invariant subset [PHI] [subset or equal to] [SIGMA] such that the following hold:

(1) Recursive property. Given proper G-invariant subsets [[PHI].sub.1], [[PHI].sub.2] [subset] [PHI] such that [PHI] = [[PHI].sub.1] [??] [[PHI].sub.2], the problem is recursively reducible to induced problems on [[PHI].sub.1] and [[PHI].sub.2] in time polynomial in [absolute value of [OMEGA]] and [absolute value of [SIGMA]].

(2) Base property. If [PHI] is a singleton, then the problem is solvable in time polynomial in [absolute value of [OMEGA]] and [absolute value of [SIGMA]].

We illustrate this paradigm by recalling the proof of Theorem 3.7. The essential steps are concentrated in the method for

Problem 9

Given: G,H [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d] and x [member of] Sym([OMEGA]).

Find: Gx [intersection] H.

Proposition 3.9 Problem 9 is in polynomial time.

Proof: Consider the coordinatewise action of Gx x H on [OMEGA] x [OMEGA] and [DELTA] := Diag([OMEGA] x [OMEGA]). To solve Problem 9, it then suffices to find [Stab.sub.Gx x H]([DELTA]) = {(y, y) | y [member of] Gx [intersection] Hg. To accommodate recursion, we consider, more generally, the following subcoset problem.

Let [p.sub.1] denote the first-coordinate projection map of Sym([OMEGA]) x Sym([OMEGA]). For [GAMMA] [subset or equal to] [OMEGA], we write Diag([GAMMA], [OMEGA]) := {([alpha], [alpha]) | [alpha] [member of] [GAMMA]}.

Given: G [less than or equal to] Sym([OMEGA]) x Sym([OMEGA]) such that [p.sub.1](G) [member of] [[GAMMA].sub.d], x [member of] Sym([OMEGA]) x Sym([OMEGA]) and [p.sub.1](G)-invariant [PHI] [subset or equal to] [OMEGA].

Find: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

If not empty, C(Gx, [PHI]) is a coset of [Stab.sub.G](Diag([PHI], [OMEGA])). We now solve this problem under the divide-and-conquer paradigm. We perform two levels of divide-and-conquer maneuvers under the G-action on [PHI] via [p.sub.1], involving the decomposition of [direct sum] into orbits and, in the transitive case, the decompositions of [direct sum] into blocks and G into cosets. In particular, we consider the following three (two recursive and one base) cases.

Intransitive case If G acts intransitively on [direct sum], then we first find proper G-invariant subsets [[PHI].sub.1], [[PHI].sub.2] [subset] [PHI] such that [PHI] = [[PHI].sub.1] [??] [[PHI].sub.2]. Since C(Gx, [PHI]) = C(C(Gx, [[PHI].sub.1]), [[PHI].sub.2]), it is sufficient to solve recursively for, if not empty, Hy := C(Gx, [[PHI].sub.1]) and then C(Hy, [[PHI].sub.2]).

Transitive case If G acts transitively on [PHI], where [absolute value of [PHI]] > 1, then we find a minimal block system [PHI] := {[[PHI].sub.1],..., [[PHI].sub.m]} of [PHI] and decompose G into cosets of the kernel K of the G-action on [PHI], say, G = K [y.sub.1] [??] xxx [??] K [y.sub.l] for some [y.sub.1],..., [y.sub.l] [member of] G. Since K acts intransitively on [PHI], the problem is reduced to l instances of the intransitive case of finding C(K [y.sub.1]x, [PHI]),..., C(K [y.sub.]x, [PHI]). Of l solutions to these instances, nonempty ones are cosets [Lz.sub.1],..., [Lz.sub.k] of the same subgroup L := [Stab.sub.K](Diag([PHI], [OMEGA])). These cosets may easily be pasted together to form a single coset of [Stab.sub.G](Diag([PHI], [OMEGA])), for [Lz.sub.1] [??] xxx [??] [Lz.sub.k] = <L, [{[z.sub.i][z.sup.-1.sub.1]}.sub.i=2,..., k]>[z.sub.1].

Base case The above recursion bottoms out when G acts primitively on [PHI] (i.e., when [[PHI].sub.1],..., [[PHI].sub.m] become singletons). If [PHI] = {[alpha]} and x = ([x.sub.1], [x.sub.2]), we return either [empty set] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Timing analysis In the intransitive case, we solve sequentially on [[PHI].sub.1] and [[PHI].sub.2], where [[absolute value of [[PHI].sub.1]] + [[absolute value of [[PHI].sub.2]] = [absolute value of [PHI]]. In the transitive case, notice that, by Theorem 3.8, the kernel of the G-action on a minimal block system has polynomial index in G, that is, l = O([m.sup.c]) for a constant c > 0. Therefore, the original problem on [direct sum] is reduced to O([m.sup.c+1]) problems on subsets of size [absolute value of [PHI]]/m. By the results of x3.1, these reductions are in polynomial time. Hence, this algorithm runs in polynomial time. [there does not exist]

Via Problem 9, we can now solve Problem 1 in [[GAMMA].sub.d]. In fact, we can also solve

Problem 10

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d] and [[DELTA].sub.1], [[DELTA].sub.2] [subset or equal to] [OMEGA].

Find: [Trans.sub.G]([[DELTA].sub.1], [[DELTA].sub.2]) = {g [member of] G | [[DELTA].sup.g.sub.1] = [[DELTA].sub.2]}.

Corollary 3.10 Problem 10 is in polynomial time.

Proof: If [absolute value of [[DELTA].sub.1]] = [absolute value of [[DELTA].sub.2]], then we find x [member of] Sym([OMEGA]) such that [[DELTA].sup.x.sub.1] = [[DELTA].sub.2] and, via Problem 9, [Gx.sup.-1] [intersection] [Stab.sub.Sym([OMEGA])]([[DELTA].sub.1]). [there does not exist]

We now complete

Proof of Theorem 3.7: The assertions concerning Problems (i), (ii) are immediate from Proposition 3.9 and Corollary 3.10, so it remains to solve Problem (iii). For this, note that [C.sub.G](H) = G [intersection] [C.sub.Sym([OMEGA])](H); that is, via Problems 5, 9, we have a polynomial-time solution to Problem (iii). [there does not exist]

Remark See [32, [section]3] for an illustration of the paradigm directly applied to Theorem 3.7(i).

Let X = ([OMEGA], E) denote a hypergraph consisting of a set and a collection [OMEGA] [subset or equal to] [2.sup.[OMEGA]]; here, we regard elements of [OMEGA] vertices and members of E hyperedges. For G [less than or equal to] Sym([OMEGA]), under the induced action of G on [2.sup.[OMEGA]], we consider the problem of finding the automorphism group of X in G.

Problem 11

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d] and a hypergraph X = ([OMEGA], E).

Find: [Aut.sub.G](X) = {g [member of] G | [E.sup.g] = E}.

The following result is due to the work of Miller [42]. We include a proof in our notation as an additional illustration of the divide-and-conquer paradigm.

Lemma 3.11 (Miller) Problem 11 is in polynomial time.

Proof: For [PHI] [subset or equal to] [OMEGA], we define [E.sub.[PHI]] := {[PHI] [intersection] [DELTA] | [DELTA] [member of] E}. To accommodate recursion, we consider the following generalization.

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], x [member of] Sym([OMEGA]), G-invariant [PHI] [subset or equal to] and E [subset or equal to] [2.sup.[PHI]].

Find: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

We note that, if not empty, C(Gx, [PHI], E) is a coset of [Stab.sub.G]([E.sub.[PHI]]).

To solve this problem, we apply the divide-and-conquer paradigm using the action of G on [PHI], but the intransitive case requires some additional work: First, given proper G-invariant subsets [[PHI].sub.1], [[PHI].sub.2] [subset] [PHI] such that [PHI] = [[PHI].sub.1] [??] [[PHI].sub.2], we find, via recursion, C(C(Gx, [[PHI].sub.1], E), [[PHI].sub.2], E). If not empty, the result of this recursion is a coset Hy, where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Here, observe that, for each [DELTA] [member of] E, each element of Hy need not map [[PHI].sub.1] [intersection] [DELTA] and [[PHI].sub.2] [intersection] [DELTA] into the same member of E. Thus, we perform the following to find C(Gx, [direct sum], E). We form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Under the induced action of H on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], we now find [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] via Problem 10.

In the base case in which [PHI] is a singleton, we simply compare [E.sub.[PHI]] against [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and return either Gx or [empty set]. [there does not exist]

We need the following extension of Problem 11.

Problem 12

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Find: [Stab.sub.G]([epsilon]).

Lemma 3.12 Problem 12 is in polynomial time.

Proof: To solve this problem, we first form E' := [[??].sub.E[member of][epsilon]] E [subset or equal to] [2.sup.[OMEGA]] and then, via Problem 11, find H := [Stab.sub.G](E'). Here, notice that [epsilon] [member of] [2.sup.E']. Under the induced action of H on E', we return, via Problem 11, [Stab.sub.H]([epsilon]). [there does not exist]

3.5 Tools for linear representations

In this subsection, we consider several fundamental problems whose inputs are permutation groups equipped with linear representations. Throughout this subsection, we assume that V is an n-dimensional vector space over a finite field k of order [q.sup.e] for some prime q.

We first begin with

Problem 13

Instance: G [less than or equal to] Sym([OMEGA]) and a representation [phi] : G [right arrow] GL(V).

Question: Is [phi] irreducible? If not, exhibit a proper kG-submodule W < V.

In [47], Ronyai considered problems in associative algebras and proved, as a byproduct of his main result,

Theorem 3.13 (Ronyai) Problem 13 is solvable in time polynomial in [absolute value of [OMEGA]], n, q and e [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. [there does not exist]

Remark This theorem is used in finding a chief series of G [less than or equal to] Sym([OMEGA]) in polynomial time (see, e.g., [25, [section]4]; see also Theorem 3.1(x)). As in the chief-series application, for any vector space V arising in the present work, all of the parameters n, q and e of V are polynomially bounded in [absolute value of [OMEGA]]. It is thus sufficient to achieve running time of linear-representation problems such as Problem 13 in time polynomial in [absolute value of [OMEGA]], n, q and e (see also the remark following Theorem 5.1). Note, however, that log q suffices in the timings for Problems 14, 16, and we expect that these problems will have other applications.

Another fundamental problem is

Problem 14

Instance: G [less than or equal to] Sym([OMEGA]), a representation [phi] : G [right arrow] GL(V) and kG-submodules [W.sub.1], [W.sub.2] [less than or equal to] V.

Question: Is there a kG-isomorphism [psi]: [W.sub.1] [??] [W.sub.2]? If so, exhibit such [psi].

In general, Brooksbank and Luks [10] have shown that testing isomorphism of modules over an arbitrary field requires only a polynomial number of field operations (see also Chistov, Ivanyos and Karpinski [15], which suffices for our application over finite fields); in particular, we have

Lemma 3.14 Problem 14 is solvable in time polynomial in [absolute value of [OMEGA]], n, log q and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. [there does not exist]

With Theorem 3.13 and Lemma 3.14 at hand, we next consider

Problem 15

Given: G [less than or equal to] Sym([OMEGA]), an irreducible representation [phi] : G [right arrow] GL(V) and N [??] G.

Find: a direct sum of the kN-homogeneous components V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m] whose summands form a system of imprimitivity for G or a report that V is kN-homogeneous.

Lemma 3.15 Problem 15 is solvable in time polynomial in [absolute value of [OMEGA]], n, q and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Proof: We apply the standard argument in the proof of Clifford's theorem (see, e.g., [2, 12.13]).

We first use Theorem 3.13 to find an irreducible kN-submodule W [less than or equal to] V . Next, we find 1 = [g.sub.1],..., [g.sub.r] [member of] G such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

We now appeal to Lemma 3.14 to partition V into isomorphism classes, say, [V.sub.1],..., [V.sub.m]; that is, we put [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] into the same class if they are kN-isomorphic. Unless m = 1, for each class Vi, we add all its members to form a kN-homogeneous component [V.sub.i]; hence, V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m], and G permutes the summands as a system of imprimitivity. If there is only one isomorphism class, then we report that V is kN-homogeneous. [there does not exist]

Now, we consider

Problem 16

Given: G [less than or equal to] Sym([OMEGA]) and a representation [phi] : G [right arrow] GL(V).

Find: Ker [phi].

As far as we know, this problem cannot be solved efficiently via a sequential stabilization of a basis of V (for comparison, we note that Problem 18 hypothesizes that G [member of] [[GAMMA].sub.d]). Nevertheless, in [25, [section]4], with the help of Kantor's Sylow machinery and thus CFSG (Theorem 3.1(xi)), the problem was asserted to be in polynomial time; since the proof was omitted in [25] due to space limitations, we include it here.

Lemma 3.16 (CFSG) Problem 16 is solvable in time polynomial in [absolute value of [OMEGA]], n, log q and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Proof: We reduce a given instance to a p-group case. For each prime p dividing [absolute value of G], we appeal to Theorem 3.1(xi) to find a single P [member of] [Syl.sub.p](G) and collect them in a common set P. Since the kernel of [phi] is generated by the kernels of [phi]|P for all P [member of] P, it suffices to solve the problem for each P [member of] P.

The remainder of the proof is in [34, [section]4.6], which in fact resolves, more generally, the problem for a solvable linear group G assuming the primes in [absolute value of G] are polynomially bounded. [there does not exist]

Remark (i) If we hypothesize that G [member of] [[GAMMA].sub.d] in Problem 16, then the problem can be solved without invoking CFSG by using the method of Kantor and Taylor from [26], in place of Theorem 3.1(xi), to find Sylow subgroups.

(ii) We also note that, in general, if G and H are manageable groups (in the sense of [34]), i.e., groups with polynomial-time procedures for constructive membership-testing, for any homomorphism [pi] : G [right arrow] H, finding Ker [pi] and [[pi].sup.-1](M) for given M [less than or equal to] [pi](G) is in polynomial time: To find Ker [pi], we form a presentation <X|R> of [pi](G) and pull back <[R.sup.F(X)]>. To find [[pi].sup.-1](M) for given M = <T>, it suffices to find U [subset or equal to] G such that [pi](U) = T and return <U [union] Ker [pi]> = [[pi].sup.-1](M). For more on this, see [34, [section]4] (cf. Theorem 3.1(vi)).

Now, in general, for N [??] G [less than or equal to] GL(V), notice that g [member of] G centralizes N if and only if g fixes all elements of the linear span k[N] in [End.sub.k](V). So, Problem 16 is used to solve

Problem 17

Given: G [less than or equal to] Sym([OMEGA]), N E G and a representation [phi] : G [right arrow] GL(V).

Find: C [??] G such that [phi](C) = [C.sub.[phi](G)]([phi](N)).

We next consider problems that resemble ISO in linear representations. As before, we restrict inputs to the class [[GAMMA].sub.d] to seek polynomial-time solutions. The following two problems are of our primary interest.

Problem 18

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], a representation [phi] : G [right arrow] GL(V) and v [member of] V.

Find: [C.sub.G](v) = {g [member of] G | [v.sup.g] = v}.

Problem 19

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], a representation [phi] : G [right arrow] GL(V) and W [less than or equal to] V.

Find: [N.sub.G](W) = {g [member of] G | [W.sup.g] = W}.

To accommodate recursion, we first reformulate Problems 18, 19 to seek subcosets rather than subgroups. An equivalent subcoset-version of Problem 18 is naturally

Problem 20

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], a representation [phi] : G [right arrow] GL(V) and v, w [member of] V.

Find: [Trans.sub.G](v, w) = {g [member of] G | [v.sup.g] = w}.

In fact, Problem 20 is also equivalent to

Problem 21

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], a representation [phi] : G [right arrow] GL(V), f [member of] [Z.sub.1](G, V) and v [member of] V.

Find: [f.sup.-1](v) = {g [member of] G | f(g) = v}.

If not empty, [f.sup.-1](v) is a coset of Ker f = [f.sup.-1](0). For given v [member of] V , let f(x) := [v.sup.x] - v. Then Ker f = [C.sub.G](v). Also, for another given w [member of] V, note that [f.sup.-1](w - v) is the solution to Problem 20.

Conversely, to reduce Problem 21 to Problem 20, for given f [member of] [Z.sub.1](G, V), we consider the extension of [phi] to [[phi].sub.f] : G [right arrow] GL(V [direct sum] k) defined by [(v, a).sup.g] := ([v.sup.g] + af(g), a) for v [member of] V, a [member of] k and g [member of] G. With such [[phi].sub.f], we have f(g) = v if and only if [(v, 1).sup.g] = ([v.sup.g] + v, 1) for v [member of] V, 1 [member of] k and g [member of] G.

For Problem 19, we consider the following reformulation.

Problem 22

Given: G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], a representation [phi] : G [right arrow] GL(V) and [W.sub.1], [W.sub.2] [less than or equal to] V.

Find: [Trans.sub.G]([W.sub.1], [W.sub.2]) = {g [member of] G | [W.sup.g.sub.1] = [W.sub.2]}.

We will devote [section]5 to the proof of

Proposition 3.17 Problems 18-22 are solvable in time polynomial in [absolute value of [OMEGA]], n, q and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

To prove Proposition 3.17, we will first solve Problem 21 since it lends itself easily to a divide-andconquer paradigm. As a corollary, we will immediately obtain solutions to Problems 18, 20. We will then solve Problems 19, 22 via Problem 20.

3.6 Automorphisms of characteristically simple groups

In this subsection, we will develop polynomial-time tools for constructing representations of the automorphism groups of direct products of isomorphic nonabelian simple groups.

We first recall some basic facts concerning permutation representations of group extensions. Suppose that a group H is an extension of a normal subgroup N by a group K. If N acts faithfully on a set [OMEGA], then it induces a faithful action of H on x K in the following way: Consider the canonical homomorphism * : H [right arrow] K whose kernel is N and fix a lifting of *, say, [lambda] : K [right arrow] H (i.e., [lambda][(k).sup.*] = k for k [member of] K). For each h [member of] H, we define a function [f.sup.h] : K [right arrow] N by [f.sup.h](k) := [lambda](k)h[lambda][([kh.sup.*]).sup.-1] for k [member of] K. Then, for h [member of] H and ([alpha], k) [member of] [OMEGA] x K, we define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

We now consider the following general problem.

Problem 23

Given: G [less than or equal to] Sym([OMEGA]) such that Z(G) = 1 and [SIGMA] [subset or equal to] Aut(G) such that <Inn(G) [union] [SIGMA]> = Aut(G).

Find: a faithful representation [pi] : Aut(G) [right arrow] Sym([OMEGA]') (where [absolute value of [OMEGA]'] is polynomially bounded).

More specifically, for G = <S>, we assume that [sigma] [member of] [SIGMA] is defined on each s [member of] S and that [pi] performs the following: given [sigma] [member of] Aut(G) defined on each s [member of] S, determine [pi]([sigma]) in Sym([OMEGA]').

Proposition 3.18 Problem 23 is solvable in time polynomial in [absolute value of [OMEGA]], [absolute value of [SIGMA]] and [absolute value of Out(G)].

Proof: We construct a faithful action of Aut(G) on [OMEGA] x Out(G) by applying the preceding method for general group extensions to 'H' = Aut(G), 'N' = Inn(G) and 'K' = Out(G). For this, it suffices to describe how to construct (i) a faithful action of Inn(G) on [OMEGA] and (ii) a multiplication table of Out(G), the canonical homomorphism * : Aut(G) [right arrow] Out(G) and a lifting [lambda] : Out(G) [right arrow] Aut(G) in the desired time.

We recall that, for G = <S>, given [sigma], [tau] [member of] Aut(G) and s [member of] S, we can evaluate [s.sup.[sigma][tau]] = [([s.sup.[sigma]]).sup.[tau]] by means of a straightline program from S to [s.sup.[sigma]] (cf. [section]2.3). We also recall that Problem 8, the problem of determining, for any given [sigma] [member of] Aut(G), whether [sigma] [member of] Inn(G), is in polynomial time.

For a faithful action of Inn(G) on [OMEGA], since Z(G) = 1, it suffices to construct an isomorphism [phi] : Inn(G) [??] G. For this, given [sigma] [member of] Inn(G), we use Problem 8 to determine [alpha] [member of] G such that [g.sup.a] = [g.sup.[sigma]] for all g [member of] G and set [phi]([sigma]) := a.

For (ii), from [SIGMA], again via Problem 8, we generate a complete set of coset representatives R for Inn(G) in Aut(G) and then construct a multiplication table for Out(G) indexed by elements [a.sub.[rho]], [rho] [member of] R. To construct * : Aut(G) [right arrow] Out(G), for each [sigma] [member of] [SIGMA], we find [rho] [member of] R such that [sigma][[rho].sup.-1] [member of] Inn(G) and define [[sigma].sup.*] := [a.sub.[rho]]. To construct a lifting of *, we set [lambda]([a.sub.[rho]]) := [rho] for [a.sub.[rho]] [member of] Out(G). [there does not exist]

The preceding technique will be used when dealing with nonabelian simple groups. For this, we appeal to the following fact from CFSG: For every nonabelian simple group T, we have [absolute value of Out(T)] = O(log [absolute value of T]) (see, e.g., [27]). Furthermore, if T is given as a permutation group, then, by [24], in polynomial time, one can find the "natural" representation of T, in which form the elements of Out(T) are easily listed: For the alternating groups An with n [greater than or equal to] 5, except for n = 6, it is an elementary fact that Aut([A.sub.n]) = [S.sub.n] and thus [absolute value of Out([A.sub.n])] = 2 (see, e.g., [52, I, 3.2.17]). For the simple groups of Lie type, the automorphisms adhere to a neatly-formulated pattern (more specifically, every automorphism is the product of an inner, a "diagonal", a "graph" and a "field" automorphism) (see, e.g., [13, Chapter 12], [21, [section]2].5]).

Consequently, for any nonabelian simple T [less than or equal to] Sym([OMEGA]), [absolute value of Out(T)] is polynomially bounded, and small [SIGMA] [subset or equal to] Aut(T) such that <Inn(T) [union] [SIGMA]> = Aut(T) is computable in polynomial time. With this in mind, we consider

Problem 24

Given: T [less than or equal to] Sym([OMEGA]) such that T is nonabelian simple.

Find: a faithful representation [pi] : Aut(T) [right arrow] Sym([OMEGA]') (where [absolute value of [OMEGA]'] is polynomially bounded).

By Proposition 3.18, we have

Corollary 3.19 (CFSG) Problem 24 is in polynomial time. 2

Remark It is also not difficult to directly solve Problem 24 using the well-known structures of the automorphisms of the simple groups. As indicated in Problem 23, the preceding approach offers a general method and applicable to any centerless groups whose outer automorphism groups are small.

Recall that, if N [congruent to] [T.sup.l] for a nonabelian simple group T, then Aut(N) [congruent to] Aut(T)[??][S.sub.l]. This isomorphism is used in the solution of

Problem 25

Given: N [less than or equal to] Sym([OMEGA]), [T.sub.1],..., [T.sub.l] [??] N such that N [congruent to] [T.sub.1] x xxx x [T.sub.l] [congruent to] [T.sub.l] for a nonabelian simple group

T, and isomorphisms [[tau].sub.i] : [T.sub.1] [??] [T.sub.i] (defined on generators) for i = 2,..., l.

Find: a faithful representation [pi] : Aut(N) [right arrow] Sym([OMEGA]') (where [absolute value of [OMEGA]'] is polynomially bounded).

Lemma 3.20 (CFSG) Problem 25 is in polynomial time.

Proof: We first construct an isomorphism [phi] : Aut(N) [??] Aut(T) [??] [S.sub.l]. For this, given [sigma] [member of] Aut(N), we perform the following: Let [a.sub.[sigma]] [member of] [S.sub.l] induced by the action of [sigma] on {[T.sub.1],..., [T.sub.l]} via the bijection [T.sub.i] [??] i for i = 1,..., l. We now form [[alpha].sub.[sigma]] [member of] Aut(N) that permutes via [a.sub.[sigma]] the corresponding elements of [T.sub.1],..., [T.sub.l] according to [[tau].sub.2],..., [[tau].sub.l]; that is, if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for [t.sub.i] [member of] [T.sub.i]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] stabilizes each of [T.sub.1],..., [T.sub.l]; thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for some [[sigma].sub.i] [member of] Aut([T.sub.i]) for i = 1,..., l. Regarding T = [T.sub.1] = xxx = [T.sub.l], we define [phi]([sigma]) := ([[sigma].sub.1],..., [[sigma].sub.l])[a.sub.[sigma]] [member of] Aut(T) [??] [S.sub.l].

Via Problem 24, we next form a faithful representation [psi]: Aut(T) [right arrow] Sym([OMEGA] x Out(T)). We paste together [phi] and [psi] to form a faithful representation [pi] : Aut(N) [right arrow] Sym([OMEGA] x Out(T) x {1,..., l}). [there does not exist]

We now apply the methods for Problems 24, 25 to solve

Problem 26

Given: N = N/K for K [??] N [less than or equal to] Sym([OMEGA]), [T.sub.1],..., [T.sub.l] [??] N such that N [congruent to] [T.sub.1] x xxx x [T.sub.l] [congruent to] [T.sub.l] for a nonabelian simple group T, and isomorphisms [[tau].sub.i] : [T.sub.1] [??] [T.sub.i] (defined on generators) for i = 2,..., l.

Find: a faithful representation [pi] : Aut(N) [right arrow] Sym([OMEGA]') (where [absolute value of [OMEGA]'] is polynomially bounded).

Lemma 3.21 (CFSG) Problem 26 is in polynomial time.

Proof: As demonstrated above, since Aut(N) [congruent to] Aut(T) [??] [S.sub.l], we may assume that N is nonabelian simple. Here, we call a procedure from [33, [section]6] for constructing permutation representations of composition factors of permutation groups, to form, on a small set [??], a faithful representation [phi] : N [right arrow] Sym([??]). Then, via [phi], we apply the method for Problem 24. [there does not exist]

3.7 Normalizers of characteristically simple groups

In this subsection, we will develop polynomial-time tools for finding normalizers of direct products of isomorphic simple groups.

First, we consider normalizing elementary abelian groups.

Problem 27

Given: G, E [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], and E is elementary abelian.

Find: [N.sub.G](E).

Lemma 3.22 Problem 27 is in polynomial time.

Proof: First, we find the orbits of E, say [[DELTA].sub.i], i = 1,..., l, and form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Here, we note that [N.sub.G](E) [less than or equal to] [N.sub.G]([E.sub.0]). Next, via Problems 6, 9, we find [G.sub.0] := [N.sub.G]([E.sub.0]) = G [intersection] [N.sub.Sym([OMEGA])]([E.sub.0]). Under the linear representation induced by the conjugation action of [G.sub.0] on [E.sub.0], we then find, via Problem 19, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. [there does not exist]

We next consider the following general problem (cf. Problem 23).

Problem 28

Given: G [less than or equal to] Sym([OMEGA]) and [SIGMA] [subset or equal to] Aut(G) (defined on generators) such that <Inn(G) [union] [SIGMA]> = Aut(G).

Find: [N.sub.Sym([OMEGA])](G).

Proposition 3.23 Problem 28 is solvable in time polynomial in [absolute value of [OMEGA]], [absolute value of [SIGMA]] and [absolute value of Out(G)].

Proof: We first form, via Problem 8, a complete set of right coset representatives R := {[[rho].sub.1],..., [[rho].sub.l]} for Inn(G) in Aut(G). Then, for each [[rho].sub.i] [member of] R, we test, via Problem 7, if there is [x.sub.i] [member of] Sym([OMEGA]) such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for all g [member of] G, and if so, collect such [x.sub.i] in a set X. Next, via Problem 5, we find [C.sub.Sym([OMEGA])](G) and then return <X>[G.sub.Sym([OMEGA])](G) = [N.sub.Sym([OMEGA])](G). [there does not exist]

We will now consider several normalizer problems involving nonabelian simple groups. As in Problems 24-26, we will appeal to the aforementioned facts about the outer automorphism groups of nonabelian simple groups.

Problem 29

Given: T [less than or equal to] Sym([OMEGA]) such that T is nonabelian simple.

Find: [N.sub.Sym([OMEGA])](T).

Since the structure of Out(T) is known, where [absolute value of Out(T)] is polynomially bounded, we have, by Proposition 3.23,

Corollary 3.24 (CFSG) Problem 29 is in polynomial time. 2

For G, T [less than or equal to] Sym([OMEGA]), note that [N.sub.G](T) = G [intersection] [N.sub.Sym([OMEGA])](T). Problems 9 and 29 now provide a solution to

Problem 30

Given: G, T [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], and T is nonabelian simple.

Find: [N.sub.G](T).

Corollary 3.25 (CFSG) Problem 30 is in polynomial time. 2

We use a similar technique to solve

Problem 31

Given: G, [T.sub.1], [T.sub.2] [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], and [T.sub.1], [T.sub.2] are nonabelian simple.

Find: [Trans.sub.G]([T.sub.1], [T.sub.2]) = {g [member of] G | [T.sup.g.sub.1] = [T.sub.2]}.

Lemma 3.26 (CFSG) Problem 31 is in polynomial time.

Proof: We consider, for the transposition t on {1, 2}, the natural action of [??] := G [??] <t> on [OMEGA] x {1, 2} via [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for ([alpha], i) [member of] [OMEGA] x {1, 2} and [g.sub.i] [member of] G for i = 1, 2. Also, consider [??] := [T.sub.1] x [T.sub.2] for which [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for ([alpha], i) [member of] [OMEGA] x {1, 2} and [t.sub.i] [member of] [T.sub.i] for i = 1, 2. Since the structure of Out([??]) is known, where [absolute value of Out([??])] is polynomially bounded, we proceed to find, via Problem 28, [??] := [N.sub.[??]]([??]) in polynomial time. If [??] stabilizes x {1}, then we return [Trans.sub.G]([T.sub.1], [T.sub.2]) = [empty set]. Otherwise, we find a generator [??] of [??] such that [([OMEGA] x {1}).sup.[??]] = [OMEGA] x {2} and then determine g [member of] G such that [([alpha], 1).sup.[??]] = ([[alpha].sup.g], 2) for all [alpha] [member of] [OMEGA]. Now, via Problem 30, we find [N.sub.G]([T.sub.1]) and return [N.sub.G]([T.sub.1])g = [Trans.sub.G]([T.sub.1], [T.sub.2]). [there does not exist]

For finding normalizers of direct products of isomorphic nonabelian simple groups, we first consider the following technical problem.

Problem 32

Given: G, [T.sub.1],..., [T.sub.l] [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], and [T.sub.1],..., [T.sub.l] are nonabelian simple, and an action of G on I = {1,..., l}.

Find: [Stab.sub.G](f(t, i) | i [member of] I and t [member of] [T.sub.i]}) in the action of G on Sym([OMEGA]) x I.

Lemma 3.27 (CFSG) Problem 32 is in polynomial time.

Proof: To accommodate recursion, we write T := {(t, i) | i [member of] I and t [member of] [T.sub.i]} and consider the following generalization.

Given: H [less than or equal to] G, g [member of] G and H-invariant J [subset or equal to] I.

Find: [{x [member of] Hg | (T [intersection] (Sym([OMEGA]) x J)).sup.x] = T [intersection] (Sym([OMEGA]) x [J.sup.g])}.

For this, we apply the divide-and-conquer paradigm of [section]3.4 to the action of H on J (cf. Proposition 3.9). In the base case in which J = {j}, we return, via Problem 31, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. [there does not exist]

Problem 33

Given: G,H [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], and H is a direct product of isomorphic nonabelian simple groups.

Find: [N.sub.G](H).

Lemma 3.28 (CFSG) Problem 33 is in polynomial time.

Proof: Suppose that H = [T.sub.1] xxx [T.sub.l] [congruent to] [T.sub.1] x xxx x [T.sub.l] in which all [T.sub.i] are isomorphic nonabelian simple groups. Since Problem 30 is in polynomial time, we may assume that l [greater than or equal to] 2. We will utilize the fact that x [member of] Sym([OMEGA]) normalizes H if and only if x stabilizes {[T.sub.1],..., [T.sub.l]}.

Suppose that two distinct [T.sub.i] have a common nontrivial orbit. Then the orders of these two and therefore all [T.sub.i] are equal to the size of such an orbit. For each [T.sub.i], we form [A.sub.i] := {([alpha], [[alpha].sup.t]) | [alpha] [member of] [OMEGA] and t [member of] [T.sub.i]}.

Now, notice that x [member of] Sym([OMEGA]) stabilizes {[T.sub.1],..., [T.sub.l]} if and only if x stabilizes {[A.sub.1],..., [A.sub.l]} under the natural action of Sym([OMEGA]) on [OMEGA] x [OMEGA]. We thus find, via Problem 11, [Stab.sub.G]({[A.sub.1],..., [A.sub.l]}).

Next, suppose instead that no two [T.sub.i] have a common orbit. For this, for each [T.sub.i], we form the set [B.sub.i] of all orbits of [T.sub.i]. Under the natural action of G on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], via Problem 12, we then find [G.sub.0] := [Stab.sub.G]({[B.sub.1],..., [B.sub.l]}). Let [G.sub.0] act on I := {1,..., l} induced by the action of [G.sub.0] on {[B.sub.1],..., [B.sub.l]} via the bijection [B.sub.i] [??] i for i = 1,..., l. It now suffices to find, via Problem 32, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. [there does not exist]

4 Main algorithm to find [N.sub.G](H)

In this section, we will first describe the main steps of our normalizer algorithm and then prove Theorems 1.1, 1.2, 1.3.

For simplicity, it is convenient to focus on a procedure that is aimed only at getting a step closer to the normalizer; in particular, we consider

Problem 34

Given: G,H [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d] and [N.sub.G](H) < G.

Find: [G.sub.0] such that [N.sub.G](H) [less than or equal to] [G.sub.0] < G.

In the next two subsections, we will describe our procedure to prove

Proposition 4.1 (CFSG) Problem 34 is in polynomial time.

Here, we first recall the notions of covering and avoidance: Let G be a group, A, B [less than or equal to] G, and C [??] B. We say A covers B/C if BA = CA. We say A avoids B/C if B [intersection] A = C [intersection] A.

In [section]4.1, we will first reduce the given instance to the case in which H either covers or avoids each G-chief factor of ([H.sup.G]). Then, in [section]4.2, we will focus on a segment M > L > K in the chief series such that H covers M/L but avoids L/K.

4.1 Reducing to H that covers or avoids each factor

Using Theorem 3.1(x), we first construct a G-chief series for X := ([H.sup.G]) as follows.

X = [X.sub.1] [??] [X.sub.2] [??] xxx [??] [X.sub.r] = 1:

If there is a chief factor L/K of X such that L > (H [intersection] L)K > K (i.e., H neither covers nor avoids L/K), we then perform the following according to the structure of L/K. Here, we note that G does not normalize (H [intersection] L)K.

Case 1 L/K is abelian. Under the natural action of G on L/K, find [G.sub.0] := [N.sub.G]((H [intersection] L)K/K) via Problem 19. Return [G.sub.0] and exit.

Case 2 L/K is nonabelian. On some set [OMEGA]', construct a faithful representation [pi] : [Aut.sub.GL/K](L/K) [right arrow] Sym([OMEGA]') via Problem 26. Now, use Lemma 3.2 to find a homogeneous component J/K in the socle of (H [intersection] L)K/K (cf. [7, [section]5], [25, [section]9]). Here, J/K char (H [intersection] L)K/K, so [N.sub.G]((H [intersection] L)K/K) [less than or equal to] [N.sub.G](J/K); furthermore, since L/K is a chief factor, [N.sub.G](J/K) < G. Now, working with the image of G in Sym([OMEGA]') via [pi], find [G.sub.0] := [N.sub.G](J/K) via Problem 33. Return [G.sub.0] and exit.

4.2 M > L > K where H covers M/L but avoids L/K

We may assume now that H either covers or avoids each factor. For such a series, if applicable, we first move covered factors towards the tail of the series as follows: While there is a segment M > L > K in the series, where H covers M/L but avoids L/K, and G normalizes (H [intersection] M)K, replace L by (H [intersection] M)K.

Since G does not normalize H, we then have a segment M > L > K such that H covers M/L but avoids L/K, and G does not normalize ( H [intersection] M) K. For such a segment, we perform the following according to the structure of L/K. Let M := M/K, L := L/K, and H := (H [intersection] M)K/K (here, M = HL, H [intersection] L = 1, and H [congruent to] M/L).

Case 1 L is abelian. Form the natural homomorphism * : H [right arrow] HL/L (actually, * is an isomorphism since H [intersection] L = 1) and its inverse [lambda] : [H.sup.*] [right arrow] H such that [lambda]([h.sup.*]) = h for all h [member of] H. Notice that, if g [member of] G, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Forma 1-cocycle f [member of] [Z.sup.1](G, [Z.sup.1]([H.sup.*], L)) defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

for g [member of] G (here, [H.sup.*] acts on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and h [member of] H, and G acts on [Z.sup.1]([H.sup.*], L) via [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for [alpha] [member of] [Z.sup.1]([H.sup.*], L), h [member of] H and g [member of] G). Working with the representation of G on [Z.sup.1] ([H.sup.*], L) (whose dimension is at most rank L * log |H|), find [G.sub.0] := Ker f = [N.sub.G](H) via Problem 21. Return [G.sub.0] and exit.

Case 2 L is nonabelian. For G := GK/K, on some set [OMEGA]', construct a faithful representation [pi]: [Auto.sub.GM](L) [right arrow] Sym([OMEGA]') via Problem 26 (here, since M embeds in AutoM(L), H embeds in Sym([OMEGA]') via [pi]). Working with the image of G in Sym([OMEGA]') via [pi], find [G.sub.0] := [N.sub.G](H) via Problem 27 or 33. Return [G.sub.0] and exit.

4.3 Proofs of Theorems 1.1-1.3

Proof of Theorem 1.1: With the help of the above procedure for Problem 34, we describe how to find [N.sub.G](H).

First, let [G.sub.1] := G. While [G.sub.1] does not normalize H, repeat the following: find [G.sub.0] such that N[G.sub.1] (H) [less than or equal to] [G.sub.0] < [G.sub.1] via Problem 34 and let [G.sub.1] := [G.sub.0]. Finally, return [G.sub.1] = [N.sub.G](H).

Proof of Theorem 1.2: We mimic a standard reduction from the problem of testing conjugacy of two elements to the problem of finding the centralizer of an element given in [25, [section]11] (cf. Lemma 3.26).

We consider, for the transposition t on {1,2}, the natural action of G := GI (t) on [OMEGA] x {1, 2} such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. We also form H := [H.sub.1] x [H.sub.2] for which [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and [h.sub.i] [member of] [H.sub.i] for i = 1, 2. Using Theorem 1.1, we find [??] := [N.sub.G] ([??]). Then there is g [member of] G such that [H.sup.9.sub.1] = [H.sub.2] if and only if there is a generator s of N such that [([OMEGA] x {1}).sup.[??]] = [OMEGA] x {2}. In particular, if such [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Proof of Theorem 1.3: The following proof involves a computational use of the Frattini method with Kantor's Sylow machinery (Theorem 3.1(xi)) as in [25, [section]5].

We may assume that K is not nilpotent (because, if K is nilpotent, then G [member of] [[LAMBDA].sub.d]). Suppose that G = (S) and H = (T). Since K is not nilpotent, for some prime p dividing |K |, there is P [member of] [Syl.sub.p](K) such that P is not normal in K. To begin, we appeal to Theorem 3.1(xi) to find such P. Now, we form [S.sub.0] := {s [member of] S | [P.sup.s] = P}. Then, for each s [member of] S such that P [not equal to] [P.sup.s], with the help of Theorem 3.1(xi) again, we find k [member of] K such that [P.sup.k] = [P.sup.s] and add [ks.sup.-1] to [S.sub.0]. We repeat the same for T to form a set To [sunset or equal to] [N.sub.H](P).

Next, form X := (S, T) and Y := ([S.sub.0],[T.sub.0]). We remark here that, by the Frattini argument, X = NX(P)K = YK. We then form an isomorphism [phi] : X/K [??] Y/(Y [intersection] K). For this, we recall that, by Theorem 3.1(viii)(c), for any given x [member of] X, we can find yx [member of] Y and [k.sub.x] [member of] K such that x = [y.sub.x][k.sub.x]; so, using any such [y.sub.x], we define [phi](Kx) := (Y [intersection] K)[y.sub.x]. Under this isomorphism, we recursively find [N.sub.[phi]](G/K)([phi](H/K)) in Y/(Y [intersection] K) and then pull back the result in G/K; here, to find the pullback, we appeal to the quotient-group version of Theorem 3.1(vi)(b) (see [section]3.2).

5 Finding vector and subspace stabilizers

Throughout this section, we assume that V is an n-dimensional vector space over a finite field k of order [q.sup.e] for some prime q.

The main purpose of this section is to prove Proposition 3.17 and thus Theorem 1.4. In particular, we will solve Problems 18-22 in time polynomial in |[OMEGA]|, n, q and e. Our solutions are based on a divide-and-conquer paradigm resulting from the following.

Theorem 5.1 Given G [less than or equal to] Sym([OMEGA]) such that G [member of] [[LAMBDA].sub.d] and an irreducible representation : G [right arrow] GL(V), one can find one of the following, in time polynomial in |[OMEGA]|, n, q and [member of] (where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]).

(i) H [less than or equal to] G and a direct sum V = [V.sub.1] [direct sum] ... [direct sum] [V.sub.m], where m [greater than or equal to] 2, such that

(a) each [dim.sub.k] [V.sub.i] = n/m, |G : H| = O([m.sup.c]) for a constant c > 0, and

(b) H acts on V = {[V.sub.1],..., [V.sub.m]} as a permutation group of degree m.

(ii) A [??] G such that A is abelian and |G : A| = O(|[OMEGA]| + n).

Remark (i) As indicated in [section] 1, in Theorem 5.1, the characteristic q of the field k is involved in the running time. Indeed, this parametrization enables us to call the deterministic version of Ronyai's method to test irreducibility (e.g., in Propositions 5.8, 5.11, where we have to make use of his method). (If, however, we appeal to his Las Vegas version instead, we can accomplish the same task in Las Vegas polynomial time in |[OMEGA]|, n, log q and e, replacing q by log q.) For our applications to the problem of finding normalizers in permutation groups, n, q and [member of] are all polynomially bounded in |[OMEGA]|.

(ii) We do not assert in Theorem 5.1(i) that V is a system of imprimitivity for H because the action of H on V will not necessarily be transitive. In fact, although the decomposition arises in various ways through the results leading up to the proof of Theorem 5.1, it will be seen that this action always turns out to be either transitive or trivial. However, the critical item for our divide-and-conquer paradigm is just that the summands in the decomposition of V have equal dimension n/m.

With the help of Roonyai's method to test irreducibility from [47, [section]5] (see also Theorem 3.13), Theorem 5.1 facilitates the extension to representations of [[LAMBDA].sub.d] groups of the divide-and-conquer paradigm for solvable linear groups (see [34, [section]6]). As in [section]3.4, it is indeed rd that enables us to find subgroups of polynomial index that preserve suitable direct-sum decompositions.

In [section]5.1, we will first present this divide-and-conquer paradigm resulting from Theorem 5.1. In [section]5.2, as promised in [section]3.5, we will prove that the paradigm is applicable to Problems 18-22 (cf. [34, [subsection]6.2, 6.3]). The remainder of this section is devoted to proving Theorem 5.1. In [section]5.3, we will begin with some preliminaries on linear groups. In [subsection] 5.4, 5.5, we will next describe the two key subroutines that will be used in our main algorithm for Theorem 5.1. In [section]5.6, we will then present the main algorithm.

5.1 Divide and conquer using invariant subspaces and imprimitivity systems

In general, as in permutation groups, this divide-and-conquer paradigm for linear groups applies to problems (such as Problems 18-22) that ask for construction of a recognizable subcoset of a given coset Gx in X [less than or equal to] Sym([OMEGA]), where G [member of] [[LAMBDA].sub.d], equipped with a representation X [right arrow] GL(V) such that the following hold:

(1) Recursive property. Given a proper kG-submodule W < V, the problem is recursively reducible to induced problems on W and V/W in time polynomial in |[OMEGA]|, n, q and e.

(2) Base property. If the G-action on V is irreducible and cyclic, then the problem is solvable in time polynomial in |[OMEGA]|, n, q and e.

The paradigm works in the following way. With the help of Theorems 3.13, 5.1, the paradigm performs two levels of divide-and-conquer maneuvers involving proper kG-submodules of V and, in the irreducible case, direct-sum decompositions of V on which subgroups of G of polynomial index act. In particular, we consider the following three cases (two recursive and one base).

Reducible case As required by (1) above, if there is a proper kG-submodule W < V, then we recursively solve the induced problems on W and V/W.

Irreducible case We first appeal to Theorem 5.1 and perform the following according to which of the outputs we obtain.

In case (i), we consider the output: H [less than or equal to] G and V = [V.sub.1] [direct sum] ... [direct sum] [V.sub.m], where m [greater than or equal to] 2. For this, we first decompose G into cosets of H, say, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for some [y.sub.1],..., [y.sub.l] [member of] G, where l = O([m.sup.c]). Thus, the problem for G on V reduces to t problems for cosets of H on V. Each of these t problems considers the orbit/imprimitivity structure of H in V, following the standard permutation-group divide-and-conquer paradigm (illustrated previously for Theorem 3.7): in each orbit, consider the action on a minimal system of imprimitivity, and decompose the group into cosets of the kernel of that action. The process continues until we are faced with a single element of V and a group fixing that element.

(For simplicity of presentation and timing, the algorithm keeps to the submodules generated by elements of V until it is faced with a single [V.sub.i]. In practice, finer decomposition may be observed and used, especially as the group at hand decreases.)

In case (ii), we consider the output: A [??] G such that the A-action on V is abelian. As before, we decompose G into cosets of A and reduce the problem to instances involving these cosets. The problem for A exploits the recursive property, ultimately reducing to [less than or equal to] n instances of the following base case Base case The above recursion bottoms out when the abelian G-action on V becomes irreducible (and thus cyclic by Schur's lemma, see, e.g., [2, 12.4]). In this base case, the problem is solvable in the desired time as required by (2) above.

Timing analysis In the reducible case, we solve sequentially on W and V/W, where [dim.sub.k] W + [dim.sub.k] V/W = n.

In case (i), divide-and-conquer is applied to the action on V with respect to orbits and then minimal systems of imprimitivity using stabilizers of such systems (cf. [section]3.4). Having exhausted the action on V, we end up with a problem on one of the Vj's. Using the bound on primitive rd groups (from Theorem 3.8) for the index of the kernels of the minimal-system actions, we conclude that the problem for each coset of H is reduced to O([m.sup.f(d)+1]) instances on submodules of dimension n/m. Thus, since |G : H| = O([m.sup.c]) for a constant c > 0, the original problem for G on V is reduced to O(mc+f instances on submodules of dimension n/m.

In case (ii), where A [??] G such that the A-action on V is abelian, the original problem is reduced to O(n(|[??]| + n)) instances of the base case.

5.2 Applying the divide-and-conquer paradigm

We will solve Problems 18-22 to prove Proposition 3.17 via the divide-and-conquer paradigm described above. (In the following solution to Problem 35, the proof of the base property (2) corrects a corresponding reduction in [34, [section]6.2] and the proof of Theorem 4.1.2(i), Case 1, in [43, [section]IV.2].)

Proof of Proposition 3.17: As indicated in [section]3.5, it suffices to solve Problems 21,22 in the desired running time.

Solution to Problem 21: To accommodate the above paradigm, we consider the following generalization. Problem 35

Given: X [less than or equal to] Sym([OMEGA]), a representation- : X [right arrow] GL(V), G [less than or equal to] X such that G [member of] [[lambda].sub.d], x [member of] X,

f [member of] [Z.sup.1] (X,V) and v [member of] V.

Find: C(Gx, V, f, v) := {y [member of] Gx | f (y) = v}.

If not empty, C (Gx, V, f, v) is a coset of Ker f|G = [(f|G).sup.-1](0).

As indicated in [section]5.1, to complete the proof, it suffices to prove that this problem has these properties: (1) given a proper kG-submodule W < V, the problem is recursively reducible to induced problems on W and V/W, and (2) if the G-action on V is irreducible and cyclic, then the problem is solvable in the desired time.

Proof of the recursive property (1) for Problem 35: To begin, we suppose that a proper kG-submodule W < V is given. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Since C(Gx, V, f, v) = C(G, V, f, u)x, it suffices to find C (G,V,f,u).

We first solve the problem on V/W. In particular, under the induced representation G [right arrow] GL(V/W), with [??] [member of] [Z.sup.1](G, V/W) defined by [??] (g) := W + f (g) for g [member of] G, we solve recursively for C(G, V/W, f, W + u), which is, if not empty, a coset K [alpha] [subset or equal to] G.

We next solve the problem on W. For this, we first note that [??] (g) = W if and only if f (g) [member of] W for g [member of] G; so, f (K) [subset or equal to] W. Under the restriction K [right arrow] GL(W), regarding f [member of] [Z.sup.1](K, W), we find [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] recursively. If not empty, the result is a coset Hb [subset or equal to] K. So, C (G, V, f, u) = Hba and C(Gx, V, f, v) = Hbax.

Proof of the base property (2) for Problem 35: We now suppose that the G-action on V is irreducible and cyclic. It is also convenient to assume that the ground field k is a prime field [F.sub.q]. (If k is of order [q.sup.e] for e > 1, then we regard V [congruent to] [F.sup.en.sub.q] and consider the induced [F.sub.q]X-representation of degree en.) As before, let u := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. To solve for C(Gx, V, f, v), it suffices to find C(G, V, f, u). If f (G) = 0, we simply return 0 if u [not equal to] 0 or G if u = 0. So, we suppose that f (G) [not equal to] 0.

To begin, via Problem 16, we find N := [C.sub.G](V), the kernel of the G-action on V. Clearly, f|N : N [right arrow] V is a homomorphism. By the cocycle property, f ([g.sup.-1] ng) = f [(n).sup.g] for n [member of] N and g [member of] G. Thus, f (N) is G-invariant as an abelian group and therefore a ZG-module. That is, since k is a prime field, f (N) is a kG-submodule of V. Since [bar.G] is irreducible, f (N) = 0 or V.

We first assume that f (N) = V. We recall here that, for f|N : N [right arrow] V and any w [member of] V, finding the preimage [(f|N).sup.-1](w) = {n G [member of] | f (n) = w} is in polynomial time (see Remark (ii) following Lemma 3.16). Suppose that G = <S>. Now, for each s [member of] S, we find [n.sub.s] [member of] N such that f ([n.sub.s]) = -f (s) (and hence f ([sn.sub.s]) = 0). Let H := <[sn.sub.s] | s [member of] S). Then G = HN, where, for h [member of] H and n [member of] N, we have f (hn) = u if and only if f (n) = u. Thus, we return H[(f|N).sup.-1](u) = C(G, V, f, u).

Now, we assume that f (N) = 0. We first find a [member of] G such that G/N = <Na> so that G = <a>N and C(G, V, f, u) = C(<a>, V, f, u)N. Thus, it suffices to find the integers r such that f ([a.sup.r]) = u. Let t := f (a) and [alpha] := [bar.a]. Clearly, K := k[[alpha]] is a field. Since [bar.G] is irreducible, V = Kt; in particular, u = [beta]t for some [beta] [member of] K. The cocycle property implies that [[alpha].sup.r] t = ([alpha] - 1)f ([a.sup.r]) +1; hence, it suffices to solve for r in [[alpha].sup.r] = ([alpha] - 1) [beta] + 1. This discrete-log problem in <[alpha]> is in polynomial time since the primes in the order of [alpha] are polynomially bounded.

Solution to Problem 22: For this, we consider the following generalization.

Problem 36

Given: X [less than or equal to] Sym([OMEGA]), a representation : X [right arrow] GL(V), G [less than or equal to] X such that G [member of] [[GAMMA].sub.d], x [member of] X and [W.sub.1], [W.sub.2] [less than or equal to] V.

Find: C(Gx, V, [W.sub.1], [W.sub.2]) := {y [member of] Gx | [W.sup.y.sub.1] = [W.sub.2]}.

If not empty, C (Gx, V, [W.sub.1], [W.sub.2]) is a coset of [N.sub.G] ([W.sub.1]).

As before, it suffices to prove that this problem has the aforementioned properties (1), (2). As indi- cated in [section]3.5, our methods eventually reduce the above problem to Problem 20, which is equivalent to Problem 21.

Proof of the recursive property (1) for Problem 36: As before, we suppose that a proper kG-submodule W < V is given. Here, let [W.sub.3] := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Since C(Gx, V, [W.sub.1], [W.sub.2]) = C(G, V, [W.sub.1], [W.sub.3])x, it suffices to find C (G, V, [W.sub.1], [W.sub.3]).

We first solve an induced problem on W. In particular, under the restriction G [right arrow] GL(W), we solve recursively for C (G, W, [W.sub.1] [intersection] W, [W.sub.3] [intersection] W), which is, if not empty, a coset K a [subset or equalt o] G.

We next solve a residual problem on V/W. For this, under the representation K [right arrow] GL(V/W), we find C(K, V/W, (W + [W.sub.1])/W, (W + [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.])/W) recursively. If not empty, the result is a coset Nb [subset or equal to] K.

We still have some additional work to do to complete our solution. Let [W.sub.4] := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] . Since C(G, V, [W.sub.1], [W.sub.3]) = C(N, V, [W.sub.1], [W.sub.4]) ba, we now seek C(N, V, [W.sub.1], [W.sub.4]). For this, form kN-submodules A := W + [W.sub.1] = W + [W.sub.4] and B := W [intersection] [W.sub.1] = W [intersection] [W.sub.4]. As A/B = W/B [direct sum] [W.sub.1] /B = W/B [direct sum] [W.sub.4]/B, we next find e, f [member of] [End.sub.k] (A/B) such that e and f are the projections onto [W.sub.1]/B and [W.sub.4]/B, respectively. Under the induced action of N on [End.sub.k] (A/B), it now suffices to find [Trans.sub.N](e, f), which is computable via Problem 20.

Proof of the base property (2) for Problem 36: We suppose that the G-action on V is irreducible and abelian. We may also assume that [W.sub.1] [not equal to] 0. Let [W.sub.3] := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Our goal is to find C(G, V, [W.sub.1], [W.sub.3]). Here, we note that, since G is abelian, C(G, V, W, U) = C(G, V, [W.sup.g], [U.sup.g]) for all W, U [less than or equal to] V and g [member of] G.

Let A := [W.sub.1], B := [W.sub.3], A' := 0 and B' := 0. We perform the following:
while A + A' [not equal to] V do
  begin
    find g [member of] G such that [A.sup.g] [??] < A + A';
    (* Here, such g [member of] G exists by the irreducibility of G. *)
    if [A.sup.g] [intersection] (A + A') [not equal to] 0 then
      begin
        A := A [intersection] [MATHEMATICAL EXPRESSION NOT
        REPRODUCIBLE IN ASCII.];
        B := B [intersection] ; [MATHEMATICAL EXPRESSION
        NOT REPRODUCIBLE IN ASCII.]

        end

    else

        begin

          A' := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]
          B' := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

        end

end


This loop maintains the following invariant:

A [not equal to] 0, A [intersection] A' = 0 and C (G, V, [W.sub.1], [W.sub.3]) [subset or equal to] C(G, V, A, B) [intersection] C(G, V, A', B').

Once the loop terminates, we have V = A [direct sum] A'. Let A" = A' [intersection] [W.sub.1] so that [W.sub.1] = A [direct sum] A". Let B" = B' [intersection] [W.sub.3]. If either V [not equal to] B [direct sum] B' or [W.sub.3] [not equal to] B [direct sum] B", then we return 0. Otherwise, by the above loop invariant and the fact that [W.sub.1] = A [direct sum] A', we observe that

C(G,V,[W.sub.1],[W.sub.3]) [subset or equal to] C(G, V, A, B) [intersection] C(G, V, A',B') [intersection] C(G,V,[W.sub.1],[W.sub.3]) [subset or equal to] C(G, V, A, B) [intersection] C(G, V, A', B') [intersection] C(G, V, A", B") [subset or equal to] C(G, V, [W.sub.1], [W.sub.3]) [intersection] C(G, V, A', B') [subset or equal to] C( G, V, [W.sub.1], [W.sub.3]).

That is,

C(G, V, [W.sub.1], [W.sub.3]) = C(G, V, A, B) [intersection] C(G, V, A', B') [intersection] C(G, V, A", B").

We first solve recursively for C(G, V, A", B"), which is, if not empty, a coset Ka [subset or equal to] G. It then remains to find C(K, V, A, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]) [intersection] C(K, V, A', [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]). For this, we form e, f [member of] [End.sub.k](V) such that e and f are projections from V onto A and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] with respect to V = A [direct sum] A' and V = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] [direct sum] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], respectively. It turns out that C(K, V, A, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]) [intersection] C(K, V, A', [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]) = {k [member of] K | [e.sup.k] = f}, which is computable via Problem 20.

5.3 Preliminaries on linear groups

In this subsection, we will study some structural properties of linear groups. There are two key propositions. Lemma 5.2 is a general fact that will be used in the main result of 5.5. Proposition 5.7 is the most important result of this subsection. Along with Theorem 3.8, this result on irreducible [[GAMMA].sub.d] groups enables us to find subgroups of polynomial index that preserve direct-sum decompositions for Theorem 5.1(i) when V is homogeneous (see [section] 5.4).

We begin with the following well-known fact. We include a proof for the reader's convenience. Recall that n = [dim.sub.k] V.

Lemma 5.2 If G is an irreducible subgroup of GL(V), and A is a cyclic normal subgroup of G, then [absolute value of (G :[C.sub.g](A)| [less than or equal to] n.

Proof: Suppose that A = <a>. Let [bar.k] be the algebraic closure of k and write [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Regard G [less than or equal to] GL([V.sup.k, [bar.k]) so that a is diagonalizable.

Let U be an eigenspace for a and [G.sub.1] := [N.sub.G](U) = {g [member of] G | [U.sup.g] = U}. Since G normalizes A, it permutes the eigenspaces of a. Hence, [absolute value of G : [G.sub.1], which measures the number of images of U under G, is [less than or equal to] n. Thus, it suffices to prove that [G.sub.1] [less than or equal to] [C.sub.G](A).

Let g [member of] [G.sub.1]. Since G normalizes A, it follows that [g, a] = [a.sup.m] [member of] A for some integer m > 0. Now, a acts on U as a scalar, so [g, a] fixes every u [member of] U and therefore has nonzero fixed points even over k. Since [C.sub.V]([A.sup.m]) is a kG-submodule, the irreducibility of G implies that [g, a] = 1 and thus g [member of] [C.sub.G](A).

To prepare for the proof of Proposition 5.7, we state four lemmas. The following lemma is borrowed from [6].

Lemma 5.3 If G is an irreducible subgroup of GL(V) such that G/Z(G) is a direct product of t non-abelian simple groups, then n [greater than or equal to] [2.sup.l].

Proof: Let [G.sub.1]/Z(G) be a simple factor of G/Z(G). Then [6, Proposition 2.7] asserts that n [greater than or equal to] [2.sup.l-1][n.sub.1], where [n.sub.1] is the dimension of an irreducible k[G.sub.1]-submodule of V.

Recall that, in general, an automorphism [sigma] of a group G is central if [sigma] is in the kernel of the induced action of Aut(G) on G/Z(G). Since the central automorphisms of G leave every element of G' fixed, we have

Lemma 5.4 If G is a group such that G = G', Aut(G) is isomorphic to a subgroup of Aut(G/Z(G)).

A classical theorem of Wielandt [54, Theorem 8.7], Praeger and Saxl [44] asserts that, if a subgroup G of [S.sub.n] is primitive with [A.sub.n] [??] G, then [absolute value of G] [less than or equal to] [4.sup.n] (in fact, via CFSG, [absolute value of G] [??] [11]; see also [3], [4], [40]). In turn, this leads to the following fact (see, e.g., [6, Lemma 2.2]).

Lemma 5.5 Let G [less than or equal to] [S.sub.n]. If no composition factor of G is isomorphic to [A.sub.m] for any m > d [greater than or equal to] 6, then [absolute value of G] < [d.sup.n-1].

For the last of our lemmas, we prove

Lemma 5.6 Let N, M [less than or equal to] GL(V) with [N, M] = 1 and NM irreducible. If W is an irreducible kN-submodule of V, U is an irreducible kM-submodule of V, and K := [End.sub.kN](W), then [dim.sub.k] V [greater than or equal to] [dim.sub.K] W * [dim.sub.k] U.

Proof: The irreducibility of NM implies that V is homogeneous both as a kN-module and as a kM- module. Let A := [Hom.sub.kG](W, V). By [2, 27.14(5)], the k-space structures on V and A are extendible to K-space structures so that V is K-isomorphic to [direct sum]. Thus, [dim.sub.k] V = [dim.sub.k] A * [dim.sub.K] W.

Now, fix 0 [not equal to] [w.sub.0] [member of] W. The kM-linear map [phi]: A [right arrow] V defined by [phi](a) := [w.sup.a.sub.o for a [member of] A is nontrivial, else {w [member of] W | [w.sup.A] = 0} would be a proper kN-submodule of W. Hence, [phi](A) is a nonzero kM-submodule of V and therefore contains an isomorphic copy of U. So, [dim.sub.k] A [greater than or equal to] [dim.sub.k] [phi](A) [greater than or equal to] [dim.sub.k] U.

The result follows.

We now come to the main result of this subsection.

Proposition 5.7 Let G be an irreducible subgroup of GL(V) such that G [member of] [[GAMMA].sub.d], and let N, A [??] G such that A is cyclic, and N/A is a nonabelian chieffactor ofG. Suppose that V is homogeneous both as a kN'-module and as a k[C.sub.G](N' )-module. If [n.sub.0] is the dimension of an irreducible k[C.sub.G](N ')-submodule of V, then [absolute value of G : [C.sub.G](N')] [less than or equal to] [(n/[n.sub.0]).sup.c] for a constant c > 0.

Proof: We first note that A = Z(N). To see this, notice that, since N/A is a minimal normal subgroup of G/A, either A = [C.sub.N] (A) or [C.sub.N] (a) = N. However, if A = [C.sub.N] (A), then N/A would embed in Aut(A), which is abelian, a contradiction. Hence, [C.sub.N](A) = N and thus A = Z(N).

Let H := N' throughout. We next note that H is semisimple; that is, H = H', and H/Z(H) is a direct product of nonabelian simple groups (see, e.g., [52, II, 6.6.5]). Further, Z( H) = H [intersection] Z( N) so that N/Z(N) [congruent to] H/Z(H).

Let W be an irreducible kH-submodule of V and K := [End.sub.kH](W). Since V is a homogeneous kH- module, H acts faithfully on W. Consider the induced representation [phi] : H [right arrow] GL(W, K) of degree t (where t [greater than or equal to] 2 since H is noncyclic). Now, let Z := Z(H), and write H/Z [congruent to] [H.sub.1]/Z x ... x [H.sub.l]/Z, where each [H.sub.i]/Z is isomorphic to a nonabelian simple group T. It follows from Lemma 5.3 that [2.sup.l] [less than or equal to] t.

Since H is semisimple, Aut(H) embeds in Aut(H/Z) by Lemma 5.4; therefore, G/[C.sub.G](H) embeds in Aut(H/Z) [congruent to] Aut(T) [??] [S.sub.l]. Let [??] denote the isomorphic image of G/[C.sub.G](H) in Aut(H/Z), and consider L [??] G that leaves each [H.sub.i]/Z invariant. Clearly, [??] embeds in [Aut(T).sup.l] so that [absolute value of [??]] [less than or equal to] [c.supl.sub.1] for some constant [c.sub.1] > 0 (by the [[GAMMA].sub.d] hypothesis). Next, write [c.sub.2] := max(d, 6). Since [??]/[??] lies in [S.sub.l], where no composition factor of [??]/[??] is isomorphic to [A.sub.m] for any m > [c.sub.2], it follows from Lemma 5.5 that |[absolute value of [??]/[??]] < [c.sup.l-1.sub.2]. Hence, if [c.sub.3] := [c.sub.1][c.sub.2], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

It suffices now to prove that n/[n.sub.0] [greater than or equal to] t. For this, let [V.sub.0] be an irreducible kHCG(H)-submodule such that W [less than or equal to] [V.sub.0] [less than or equal to] V and U0 be an irreducible kCG(H)-submodule of [V.sub.0]. By Lemma 5.6, [dim.sub.k] [V.sub.0] [greater than or equal to] [dim.sub.K] W * [dim.sub.k] [U.sub.0]. Since V is a homogeneous kCG(H)-module, [n.sub.0] = [dim.sub.k] [U.sub.0]. Consequently, n [greater than or equal to] [dim.sub.k] [V.sub.0] [greater than or equal to] [dim.sub.K] W * [dim.sub.k] [U.sub.0] = [tn.sub.0].

Remark It is in this proposition that the present definition of [[GAMMA].sub.d] (in which all nonabelian composition factors lie in [S.sub.d]) is essential (in particular, to bound the orders of the automorphism groups of nonabelian simple groups).

5.4 Divide and conquer using nonabelian chief factors

As promised earlier, in this and the next subsections, we will describe the two key subroutines that will be used in the main procedure to prove Theorem 5.1. For given G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], an irreducible representation : G [right arrow] GL(V) and a chief factor N/A of G, both of these subroutines seek a decomposition of V into a system of imprimitivity or a direct sum of equal-dimensional kH-submodules for some H < G of polynomial index, based on the structure of N/A (barring a few exceptional cases when N/A is abelian).

We first deal with nonabelian chief factors. In the following proposition, the key property of [[GAMMA].sub.d] linear groups we require is Proposition 5.7.

Proposition 5.8 Given G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], an irreducible [representation.sup.-] : G [right arrow] GL(V) and N, A [??] G such that N > 1, [bar.A] is cyclic, and N/A is a nonabelian chief factor of G, one can find one of the following, in time polynomial in [absolute value of [OMEGA]] n, q and e (where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]).

(i) A direct sum V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m], where m [greater than or equal to] 2, and the summandsform a system of imprimitivity for G.

(ii) H [??] G and a direct sum of kG-isomorphic irreducible kH-submodules V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m], where m [greater than or equal to] 2, such that [absolute value of G : H] = O([m.sup.c]) for a constant c > 0.

Proof: We will describe our algorithm in the following two steps. In Step 1, we first seek a system of imprimitivity for G induced by some accessible normal subgroup of G; if V has no such system, then, in Step 2, we appeal to Proposition 5.7 for a desirable pair (H,[[direct sum].sup.m.sub.i=1][V.sub.i]).

Step 1 Reduction to Problem 15. To begin, we solve Problem 15 to seek a system of imprimitivity v := {[V.sub.1],..., [V.sub.m]} for G induced by either N' or C < G such that C = [C.sub.[bar.G]]([bar.N]') (here, C is computable in polynomial time via Problem 17). Unless V is homogeneous both as a kN'-module and as a kC-module, we return [[direct sum].sup.m.sub.i=1][V.sub.i] for (i) and halt.

Step 2 V is homogeneous both as a kN'-module and as a kC-module. Since [bar.N]' centralizes [bar.C] and is nonabelian, [bar.C] is necessarily reducible. Via Problem 13, we find an irreducible kC-submodule [V.sub.1] < V, decompose V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m] such that each [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and then return a pair (H, [[direct sum].sup.m.sub.i=1][V.sub.i]) with H := C.

We note here that, since V is a homogeneous kC-module, all irreducible kC-submodules of V share the same dimension; thus, any irreducible kC-submodule [V.sub.1] may be used to decompose V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m] for which Proposition 5.7 guarantees that [absolute value of G:C] is polynomially bounded in m.

5.5 Divide and conquer using abelian chief factors

In this subsection, we will describe the second key subroutine for Theorem 5.1 that deals with abelian chief factors. We will give a top-level description of this subroutine in the proof of Proposition 5.11, which is the main result of this subsection. We will prove this proposition by way of three lemmas. Throughout this subsection, [Q.sub.8] denotes the quaternion group of order 8.

The following result is inspired by the well-known structure of extraspecial p-groups (see, e.g., [22, 13.7 Satz], [51, Theorem 19.2]).

Lemma 5.9 Given P [less than or equal to] Sym([OMEGA]), a [representation.sup.-] : P [right arrow] GL(V) such that [bar.P] is a p-group for some prime p [not equal to] q, [C.sub.V] (P') = 0, Z([bar.P]) is cyclic, and [bar.P]/Z([bar.P]) is an elementary abelian group of rank 2l > 0, one can find one of the following, in time polynomial in [absolute value of [OMEGA]] n, q and e (where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]).

(i) E [??] P such that P' < E and [bar.E] is elementary abelian, with the isotypic decomposition with respect to E, V = V [direct sum] xxx [direct sum] [V.sub.m], where m [greater than or equal to] [p.sup.l/3], and the summandsform a system of imprimitivity for P.

(ii) Q [??] P such that [bar.P] = [bar.Q]Z([bar.P]) and [bar.Q] [??] [Q.sub.8]. (This option will only turn up when p = 2 and l = 1.)

Proof: Let K be the kernel of [sup.-] : P [right arrow] GL(V). In this proof, for any x [member of] P and X [less than or equal to] P, we write x := Kx and X := XK/K.

We will describe our algorithm in the following two steps. In Step 1, we exploit the symplectic structure of P/Z(P) and factor P into a product of Z(P) and 2l cyclic groups. In Step 2, using this factorization, we construct E [??] P and a system of imprimitivity induced by E for P for (i) (except for one case in which we end up with (ii)).

Step 1 Factoring P. Consider the natural homomorphism * : P [right arrow] P/Z(P). Since P/Z(P) is elementary abelian, [absolute value of P'] = p, so that we may regard P' as a finite field of order p and P* as a vector space over P'. A function f : P* x P* [right arrow] P' defined by f (x*, y*) := [x, y] for x, y [member of] P is then a symplectic form, making (P*, f) a symplectic space.

Our goal is to decompose P with respect to a hyperbolic basis of (P*, f); that is, we seek [a.sub.1], [b.sub.1],..., [a.sub.l],[b.sub.l] [member of] P such that P = Z(P)([a.sub.l])([b.sub.l]) xxx ([a.sub.1])([b.sub.1]), where [absolute value of [a.sub.i] ] [greater than or equal to] [absolute value of [b.sub.i]] for i = 1,...,l, [[a.sub.i], [a.sub.j]] = [[a.sub.i], [b.sub.j]] = [[b.sub.i], [b.sub.j]] = 1 for all pairs i [not equal to] j, and 1 [not equal to] [[a.sub.1], [b.sub.1]] = xxx = [[a.sub.l], [b.sub.l]] = [z.sub.0] where P' = ([z.sub.0]). For this, we first fix 1 [not equal to] [z.sub.0] [member of] P' and find [a.sub.1], [b.sub.1] [member of] P such that [[a.sub.1], [b.sub.1]] = [z.sub.0] with [absolute value of [a.sub.1]] [greater than or equal to] [absolute value of [b.sub.1]]. We next find [P.sub.1] [??] P such that [P.sub.1] = [C.sub.P](([a.sub.1], [b.sub.1])). Then P = [P.sub.1]([a.sub.1])([b.sub.1]). By repeating this procedure on [P.sub.1] and so on, the desired factorization readily follows.

Step 2 Seeking a suitable E. There are three cases to consider.

Case (a) p is odd. For i = 1, ...,l, we first find an integer [e.sub.i] > 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. We then form E := ([e.sub.1],..., [e.sub.l], [z.sub.0]), where [bar.E] is indeed elementary abelian of rank l + 1. For each l-tuple [lambda] = ([[lambda].sub.1], ..., [[lambda].sub.l]) [member of] [Z.sup.l.sub.p], set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and V := {[V.sub.[lambda]] [absolute value of [lambda] [member of] [Z.sup.l.sub.p]}. Then E acts as a cyclic group on each [V.sub.[lambda]] [member of] V and, since [C.sub.V](P') = 0, each isotypic submodule for E is in V. Furthermore, since, for 1 [less than or equal to] i [less than or equal to] l,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

P acts transitively on V, which is then the complete isotypic decomposition of V with respect to E. In this case, m = [p.sup.l].

Note that the system V is computable via Problem 15 or directly from the definition of [V.sub.[lambda]].

Case (b) p = 2 and l [greater than or equal to] 2. For i = 1, ...,l, we find an integer [e.sub.i] [greater than or equal to] 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Next, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] if l is even. Now, we form E := ([e.sub.1],..., [e.sub.[l/2]], [z.sub.0]). The rest is the same as Case (a)'s argument. In this case, m = [2.sup.[l/2]] [greater than or equal to] [2.sup.l/3].

Case (c) p = 2 and l =1. Write a := [a.sub.1] and b := [b.sub.1]. As before, we find an integer e [greater than or equal to] 0 such that [a.sup.2e][b.sup.2] = 1 and let d := [a.sup.e]b (here, [absolute value of d] = 2 or 4).

Unless [absolute value of d] = [absolute value of a] = 4, we now perform one of the following: (1) if [absolute value of d] = 2, let [e.sub.1] := d; (2) if [absolute value of d] = 4 and [absolute value of a] = 2, let [e.sub.1] := a; (3) if [absolute value of d] = 4 and [absolute value of a] [greater than or equal to] 8, we find an integer r [greater than or equal to] 3 such that [absolute value of a] = [2.sup.r] and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Then, in any case, we form E := ([e.sub.1], [z.sub.0]). The rest is the same as Case (a)'s argument. In this case, m = [2.sup.l].

Finally, if [absolute value of d] = [absolute value of a] = 4, we form Q := (a, d) for (ii).

Before proving the main result, we present, with the help of Lemma 5.9, an intermediate lemma.

Lemma 5.10 Given G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], an irreducible [representation.sup.-] : G [right arrow] GL(V) and N, A [??] G such that [bar.A] is cyclic and centralized by [bar.N] > 1, and N/A is an abelian chief factor of G, one can find one of the following, in time polynomial in [absolute value of [OMEGA]], n, q and e (where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

(i) H [less than or equal to] G and a direct sum V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m], where m [greater than or equal to] 2, such that [absolute value of G : H] = O([m.sup.c]) for a constant c > 0, and the summands form a system of imprimitivity for H.

(ii) Q [??] G such that N = QA and [bar.Q] [??] [Q.sub.8].

(iii) B [??] G such that [bar.B] is abelian and A < B.

Proof: We will describe our algorithm in the following two steps. In Step 1, unless [bar.N] is abelian, to apply Lemma 5.9, we will first find P [??] N such that [bar.P] is a p-group of class 2. In Step 2, we will then appeal to the lemma with respect to this P.

Step 1 Finding a p-group of class 2. If [bar.N] is abelian, then we simply return B := N for (iii). Otherwise, [bar.N] is nilpotent of class 2, and we find P [??] N such that [bar.P] is the unique Sylow p-subgroup of [bar.N] for the prime p that divides [absolute value of N/A]; here, as [bar.G] is irreducible, p [not equal to] q and [C.sub.V](P') = 0. We also find Z [??] G such that [bar.Z] = Z([bar.P]). Since N/A is a chief factor of G, [bar.A] = Z([bar.N]); therefore, N = PA and thus P/Z [congruent to] N/A. The rank of P/Z must then be even, say, 2l > 0 (see, e.g., [22, 13.7 Satz]).

Step 2 Applying Lemma 5.9. We now appeal to Lemma 5.9 with respect to this P to either

(a) find E [??] P such that P' < E, and [bar.E] is elementary abelian, with the isotypic decomposition with respect to E, V = [V.sub.1] [direct sum] xxx [direct sum] [V.sub.m], where m [greater than or equal to] [p.sup.l/3], and the summands form a system of imprimitivity for P, or

(b) return Q [??] P such that P = QZ (which implies N = QA) and [bar.Q] [congruent to] [Q.sub.8] for (ii).

In case (a), we proceed to find the kernel H of the natural action of G on P/Z. Since H centralizes P/Z, it follows that EZ [??] H so that H acts on V := {[V.sub.1], ..., [V.sub.m]} as well. We then return the pair (H,[[direct sum].sup.m.sub.i=1] [V.sub.i]) for(i).

It now remains to prove that [absolute value of G : H] is polynomially bounded in m. Since G acts irreducibly on N/A, it also acts irreducibly on P/Z, whose rank is 2l. By the result of Babai, Cameron and Palfy on the orders of completely reducible linear groups in [[GAMMA].sub.d] [6, Corollary 3.3], there is a constant [c.sub.2] > 0 such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. By Lemma 5.9, m [greater than or equal to] [p.sup.l/3]; thus, if [c.sub.1] := 6[c.sub.2], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

We are now ready to complete the proof of the main result of this subsection. In the following proposition, we refine Lemma 5.10 by amending (i) and removing (ii) with an additional assumption that [absolute value of G : A] > 24n. Indeed, the proof of this proposition essentially consists of special routines to handle the quaternion case of Lemma 5.10(ii).

Proposition 5.11 Given G [less than or equal to] Sym(Q) such that G [member of] [[GAMMA].sub.d], an irreducible [representation.sup.-]: G [right arrow] GL(V) and N, A [??] G such that [bar.A] is cyclic and centralized by [bar.N] > 1, N/A is an abelian chief factor of G, and [absolute value of G : A] > 24n, one can find one of the following, in time polynomial in [absolute value of [OMEGA]]n, q and e (where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]).

(i) H [less than or equal to] G and a direct sum V = [V.sub.1] [cross product] xxx [cross product] [V.sub.m], where m [greater than or equal to] 2, such that [absolute value of G : H] = O([m.sup.c]) for a constant c > 0, and either

(a) {[V.sub.1], ..., [V.sub.m]} is a system of imprimitivity for H, or

(b) V is a homogeneous kH-module, where [V.sub.1], ..., [V.sub.m] are irreducible kH-submodules of V of dimension n/m.

(ii) B [??] G such that B is abelian and A < B.

Proof: We will describe our algorithms in the following two steps. In Step 1, we reduce the given input to instances to which Proposition 5.8 and/or Lemma 5.10 are applicable. In Step 2, we handle a special case involving quaternion groups to which Proposition 5.8 and Lemma 5.10 do not apply, and we seek a system of imprimitivity induced by these groups.

Step 1 Applying Proposition 5.8 and Lemma 5.10. We first apply the algorithm for Lemma 5.10 to the given input. Unless it results in the quaternion type, we immediately return the result of applying this lemma, namely, the pair (H, [[cross product].sup.m.sub.i=1] [V.sub.i]) for (i)(a) or B [??] G such that B is abelian and A < B for (ii), and halt.

We next consider the case in which the result of applying Lemma 5.10 is of the quaternion type (say, Q [??] G). For this, via Problem 17, we first find C [??] G such that C = [C.sub.[bar.G]] ([bar.N]). Here, we observe that [absolute value of G : C] [less than or equal to] 24n (to see this, notice that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] and, since [C.sub.[bar.G]]([bar.N]) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] by Lemma 5.2). Since [absolute value of G : A] > 24n, this then implies that A < C. Now, we find M [less than or equal to] C such that M/A is a chief factor of G and consider the following two cases.

If M/A is nonabelian, then we appeal to Proposition 5.8 with respect to M/A and directly return its result for (i)(a) or (i)(b).

If M/A is abelian, then we appeal to Lemma 5.10 with respect to M/A. As before, unless it results in the quaternion type again (say, R [??] G this time), directly return the result of applying Lemma 5.10 for (i)(a) or (ii), and halt.

Step 2 Finding a system of imprimitivity induced by quaternion groups. We are now left with the case in which we have at hand both Q, R [??] G such that N = QA = RA and [bar.Q], [bar.R] [??] [Q.sub.8]. Our goal here is to construct a system of imprimitivity induced by elements of Q, R and A.

First, we find [e.sub.1] [member of] Q and [e.sub.2] [member of] R such that [[bar.e].sub.1] [member of] [bar.Q]\[bar.R] and [[bar.e].sub.2] [member of] [bar.R] \ [bar.Q]. Then, with a [member of] A such that [absolute value of [bar.a]] = 2, we form E := <[e.sub.1][e.sub.2], a>. We also find the kernel H of the natural action of G on NM/A. As in the proof of Lemma 5.9, we find the set V := {[V.sub.1], [V.sub.2]} of isotypic subspaces for E, which form a system of imprimitiviy for H. It suffices to return the pair (H, [V.sub.1] [cross product] [V.sub.2]) for (i)(a), where [absolute value of G : H] is bounded by a constant.

5.6 The main algorithm for Theorem 5.1

In this subsection, we will finally present our main algorithm to prove Theorem 5.1. We will prove the theorem by way of repeated applications of

Proposition 5.12 Given G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d], an irreducible [representation.sup.-]: G [right arrow] GL(V) and A [??] G such that [bar.A] is abelian, and [absolute value of G : A] > max([absolute value of [OMEGA]], d!/2, 24n), one canfindone of the following, in time polynomial in [absolute value of [OMEGA]]n, q and e (where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]).

(i) H [less than or equal to] G and a direct sum V = [V.sub.1] [cross product] xxx [cross product] [V.sub.m], where m [greater than or equal to] 2, such that [absolute value of G : H] = O([m.sup.c]) for a constant c > 0, and either

(a) {[V.sub.1], ..., [V.sub.m]} is a system of imprimitivity for H, or

(b) V is a homogeneous kH-module, where [V.sub.1], ..., [V.sub.m] are irreducible kH-submodules of V of dimension n/m.

(ii) B [??] G such that [bar.B] is abelian and A < B.

Proof: We will describe our algorithm in the following two steps. In Step 1, we seek a system of imprimitivity induced by A; if V has no such system, then, in Step 2, we appeal to Propositions 5.8, 5.11. We may assume that [bar.G] is nonabelian and that G/A is nonsimple.

Step 1 Reduction to Problem 15. We solve Problem 15 to find, if it exists, a system of imprimitivity V = {[V.sub.1], ..., [V.sub.m]} for G induced by A. Unless V is a homogeneous kA-module, we return the result of solving Problem 15, namely, [[cross product].sup.m.sub.i=1] [V.sub.i], for (i)(a) and halt.

Step 2 V is a homogeneous kA-module. We note that, in this step, [bar.A] must be cyclic. To begin, via Problem 17, we find C [??] G such that [bar.C] = [C.sub.[bar.G]]([bar.A]). Notice here that [absolute value of G : C] [less than or equal to] n by Lemma 5.2. Since [absolute value of G : A] > n, it then follows that A < C . We next find N [less than or equal to] C such that N/A is a chief factor of G and consider two cases.

If N/A is nonabelian, then we apply the algorithm for Proposition 5.8 and directly return its result for (i)(a)or(i)(b).

If N/A is abelian, then we apply the algorithm for Proposition 5.11 and directly return its result; that is, the pair (H, [[cross product].sup.m.sub.i] [V.sub.i]) for (i)(a) or (i)(b), or B < G such that B is abelian and A < B for (ii).

Proof of Theorem 5.1: We now describe, with the help of Proposition 5.12, the top-level algorithm for Theorem 5.1. Recall that, for given G [less than or equal to] Sym([OMEGA]) such that G [member of] [[GAMMA].sub.d] and an irreducible [representation.sup.-] : G [right arrow] GL(V), our goal is to find one of the following.

(i) H [less than or equal to] G and a direct sum V = [V.sub.1] [cross product] xxx [cross product] [V.sub.m], where m [greater than or equal to] 2, such that each [dim.sub.k] [V.sub.i] = n/m, [absolute value of G : H] = O([m.sup.c]) for a constant c > 0, and H acts on V = {[V.sub.1], ..., [V.sub.m]} as a permutation group of degree m.

(ii) A [??] G such that A is abelian and [absolute value of G : A] = O([absolute value of [OMEGA]] + n).

Note that cases (i)(a) and (i)(b) of Proposition 5.12 both fall into case (i) above.

Algorithm We first initialize A := 1. While [absolute value of G : A] > max([absolute value of [OMEGA]], d!/2, 24n), we repeat the following: (1) Apply the algorithm for Proposition 5.12; (2) if its result is B [??] G such that [bar.B] is abelian and A < B, then we now let A := B; else, we return the result and halt.

received 27th March 2011, revised 12th November 2011, accepted 17th November 2011.

References

[1] M. Aschbacher, On the maximal subgroups of the finite classical groups, Invent. Math. 76 (1984), 469-514.

[2] --, Finite group theory, 2nd ed., Cambridge Stud. Adv. Math., vol. 10, Cambridge Univ. Press, Cambridge, 2000.

[3] L. Babai, On the order of uniprimitive permutation groups, Ann. of Math. (2) 113 (1981), 553-568.

[4] --, On the order of doubly transitive permutation groups, Invent. Math. 65 (1982), 473-484.

[5] --, On the length of chains of subgroups in the symmetric group, Comm. Algebra 14 (1986), 1729-1736.

[6] L. Babai, P. J. Cameron and P. P. Palfy, On the orders of primitive groups with restricted nonabelian composition factors, J. Algebra 79 (1982), 161-168.

[7] L. Babai, W. M. Kantor and E. M. Luks, Computational complexity and the classification of finite simple groups, 24th Annual Symposium on Foundations of Computer Science, Tucson, Nov. 7-9, 1983, IEEE Comput. Soc. Press, Washington, D.C., 1983, pp. 162-171.

[8] L. Babai and S. Moran, Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes, J. Comput. System Sci. 36 (1988), 254-276.

[9] B. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), 235-265.

[10] P. A. Brooksbank and E. M. Luks, Testing isomorphism of modules, J. Algebra 320 (2008), 4020-4029.

[11] P. J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), 1-22.

[12] P. J. Cameron, R. Solomon and A. Turull, Chains of subgroups in symmetric groups, J. Algebra 127 (1989), 340-352.

[13] R. W. Carter, Simple groups of Lie type, Pure Appl. Math., vol. 28, Wiley-Intersci., New York, 1972.

[14] F. Celler, J. Neubuser and C. R. B. Wright, Some remarks on the computation of complements and normalizers in soluble groups, Acta Appl. Math. 21 (1990), 57-76.

[15] A. Chistov, G. Ivanyos and M. Karpinski, Polynomial-time algorithms for modules over finite dimensional algebras, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, Kihei, Hawai'i, July 21-23, 1997, ACM, New York, 1997, pp. 68-74.

[16] J. D. Dixon and B. Mortimer, Permutation groups, Graduate Texts in Math., vol. 163, Springer, New York, 1996.

[17] M. Furst, J. Hopcroft and E. Luks, Polynomial-time algorithms for permutation groups, 21st Annual Symposium on Foundations of Computer Science, Syracuse, N.Y., Oct. 13-15,1980, IEEE Comput. Soc. Press, Washington, D.C., 1980, pp. 36-41.

[18] The GAP Group, GAP - Groups, Algorithms, and Programming, version 4.4.12, 2008 (http://www.gap-system.org).

[19] S. P. Glasby and M. C. Slattery, Computing intersections and normalizers in soluble groups, J. Symbolic Comput. 9 (1990), 637-651.

[20] O. Goldreich, S. Micali and A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proofs, J. ACM 38 (1991), 691-729.

[21] D. Gorenstein, R. Lyons and R. Solomon, The classification of the finite simple groups. Number 3. Part I. Chapter A. Almost simple K-groups, Math. Surveys Monogr., vol. 40.3, Amer. Math. Soc., Providence, R.I., 1998.

[22] B. Huppert, Endliche Gruppen. I, Grundlehren Math. Wiss., Bd. 134, Springer, Berlin, 1967.

[23] M. Jerrum, A compact representation for permutation groups, J. Algorithms 7 (1986), 60-78.

[24] W. M. Kantor, Sylow's theorem in polynomial time, J. Comput. System Sci. 30 (1985), 359-394.

[25] W. M. Kantor and E. M. Luks, Computing in quotient groups, Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, Baltimore, May 14-16, 1990, ACM, New York, 1990, pp. 524-534.

[26] W. M. Kantor and D. E. Taylor, Polynomial-time versions of Sylow's theorem, J. Algorithms 9 (1988), 1-17.

[27] S. Kohl, A bound on the order of the outer automorphism group of a finite simple group of given order, preprint, 2003 (http://www.gap-system.org/DevelopersPages/StefanKohl/ preprints/outbound.pdf).

[28] D. E. Knuth, Efficient representation of perm groups, Combinatorica 11 (1991), 33-44.

[29] C. R. Leedham-Green, The computational matrix group project, Groups and Computation. III, Columbus, June 15-19, 1999 (W. M. Kantor and A. Seress, eds.), Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 229-247.

[30] J. S. Leon, Partitions, refinements, and permutation group computation, Groups and Computation. II, Piscataway, N.J., June 7-10, 1995 (L. Finkelstein and W. M. Kantor, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, R.I., 1997, pp. 123-158.

[31] M. W. Liebeck and A. Shalev, Simple groups, permutation groups, and probability, J. Amer. Math. Soc. 12 (1999), 497-520.

[32] E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. System Sci. 25 (1982), 42-65.

[33] --, Computing the composition factors of a permutation group in polynomial time, Combinatorica 7 (1987), 87-99.

[34] --, Computing in solvable matrix groups, 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Oct. 24-27, 1992, IEEE Computer Soc. Press, Los Alamitos, Calif., 1992, pp. 111-120.

[35] --, Permutation groups and polynomial-time computation, Groups and Computation, Piscataway, N.J., Oct. 7-10, 1991 (L. Finkelstein and W. M. Kantor, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, R.I., 1993, pp. 139-175.

[36] E. M. Luks and T. Miyazaki, Polynomial-time normalizers for permutation groups with restricted composition factors, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, Villeneuve d'Ascq, July 7-10, 2002, ACM, New York, 2002, pp. 176-183.

[37] --, in preparation.

[38] E. M. Luks, F. Rakoczi and C. R. B. Wright, Computing normalizers in permutation p-groups, Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation, Oxford, July 20-22, 1994, ACM, New York, 1994, pp. 139-146.

[39] --, Some algorithms for nilpotent permutation groups, J. Symbolic Comput. 23 (1997), 335-354.

[40] A. Maroti, On the orders of primitive groups, J. Algebra 258 (2002), 631-640.

[41] G. L. Miller, Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus, Inform. and Control 56 (1983), 1-20.

[42] --, Isomorphism of graphs which are pairwise k-separable, Inform. and Control 56 (1983), 21-33.

[43] T. Miyazaki, Polynomial-time computation in matrix groups, Ph.D. Dissertation, Tech. Rep. CIS-TR-99-11, Department of Computer and Information Science, University of Oregon, Eugene, 1999.

[44] C. E. Praeger and J. Saxl, On the orders of primitive permutation groups, Bull. London Math. Soc. 12 (1980), 303-307.

[45] L. Pyber, Asymptotic results for permutation groups, Groups and Computation, Piscataway, N.J., Oct. 7-10, 1991 (L. Finkelstein and W. M. Kantor, eds.), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, R.I., 1993, pp. 197-219.

[46] L. Pyber and A. Shalev, Asymptotic results for primitive permutation groups, J. Algebra 188 (1997), 103-124.

[47] L. Ronyai, Computing the structure of finite algebras, J. Symbolic Comput. 9 (1990), 355-373.

[48] U. Schoning, Graph isomorphism is in the low hierarchy, J. Comput. System Sci. 37 (1988), 312-323.

[49] A. Seress, Permutation group algorithms, Cambridge Tracts in Math., vol. 152, Cambridge Univ. Press, Cambridge, 2003.

[50] C. C. Sims, Computational methods in the study of permutation groups, Computational Problems in Abstract Algebra, Oxford, Aug. 29-Sept. 2, 1967 (J. Leech, ed.), Pergamon Press, Oxford, 1970, pp. 169-183.

[51] D. A. Suprunenko, Matrix groups, "Nauka", Moscow, 1972 (Russian); English transl., Transl. Math. Monographs, vol. 45, Amer. Math. Soc., Providence, R.I., 1976.

[52] M. Suzuki, Group theory. I, II, Iwanami Shoten, Tokyo, 1977, 1978 (Japanese); English transl., Grundlehren Math. Wiss., Bd. 247, 248, Springer, Berlin, 1982, 1986.

[53] H. TheiBen, Eine Methode zur Normalisatorberechnung in Permutationsgruppen mit Anwendungen in der Konstruktion primitiver Gruppen, Dissertation, Lehrstuhl D fur Mathematik, Rheinisch-Westfalische Technische Hochschule, Aachen, 1997.

[54] H. Wielandt, Permutation groups through invariant relations and invariant functions, Lecture Notes, Department of Mathematics, The Ohio State University, Columbus, 1969; Reprint, Mathematische Werke/Mathematical Works, vol. 1 (B. Huppert and H. Schneider, eds.), de Gruyter, Berlin, 1994, pp. 237296.

(i) Assuming, of course, that the problem makes sense when stated for quotients, e.g., the problem of finding set stabilizers would not seem to have a meaningful extension.

(ii) In the quotient-group version of Problem (v), we are given an element and a subgroup of a quotient group in Sym([OMEGA]). Likewise, in that of Problem (vi), we are given a homomorphism from a quotient group in Sym([OMEGA]) to a quotient group in Sym([OMEGA]').

Eugene M. Luks (1) ([dagger]) ([section]) and Takunari Miyazaki (2) ([double dagger]) ([section])

(1) Department of Computer and Information Science, University of Oregon, Eugene, USA

(2) Computer Science Department, Trinity College, Hartford, Connecticut, USA

([dagger]) E-mail: luks@cs.uoregon.edu.

([double dagger]) E-mail: takunari.miyazaki@trincoll.edu.

([section]) Supported in part by NSF Grant CCR-9820945.
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Luks, Eugene M.; Miyazaki, Takunari
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:1USA
Date:Dec 1, 2011
Words:23821
Previous Article:On the sensitivity of cyclically-invariant Boolean functions.
Next Article:Optimal computer crash performance precaution.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |