DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 00, 19xx

Constructive Recognition of a Black Box Group Isomorphic to GL(n, 2)

Gene Cooperman, Larry Finkelstein, and Steve Linton

Abstract. A Monte Carlo algorithm is presented for constructing the natural representation of a group G that is known to be isomorphic to GL(n, 2). The complexity parameters are the natural dimension n and the storage space required to represent an element of G. What is surprising about this result is that both the data structure used to compute the isomorphism and each invocation of the isomorphism require polynomial time complexity. The ultimate goal is to eventually extend this result to the larger question of constructing the natural representation of classical groups. Extensions of the methods developed in this paper are discussed as well as open questions.

1. Introduction

The principal objective of this paper is a demonstration of the feasibility of obtaining the natural (projective) matrix representation for a classical group initially presented as a black box group. In this model, group elements are encoded by binary strings of uniform length N, and group operations are performed by an oracle (the black box). The oracle can compute the product of elements, the inverse and recognize the identity element in time polynomial in N. The most important examples of black box groups are matrix groups and permutation groups. This effort was initially motivated by recent efforts to identify the structure of matrix groups defined over finite fields (see [3] [7] and [9] in this volume). However, an important advantage of working in a black box setting is that the techniques rely only on the structure of the group and not on the representation.

Our major result is the following.

Theorem 1.1. Let G be a black box group specified by a generating set G which is known to be isomorphic to GL(n, 2) for some n. Let M be a known upper bound on n, let μ be the time required to perform a group operation in G, let ρ be the time required to compute a (nearly) uniform random element of G, and let ϵ be the time for a field operation in GF (2). Then a Monte Carlo algorithm exists which in time O((M log^{2} M + n^{2})μ + Mρ + n^{3}ϵ) can determine the value of n and produce a data

\begin{matrix}c \\ ◯ \end{matrix}0000 American Mathematical Society 1052-1798/00 $1.00 + $.25 per page

1991 Mathematics Subject Classification. Primary 20G40, 20-04; Secondary 20C40.

The first two authors were partially supported by NSF Grant CCR-9509783.

structure which can then be used to compute an isomorphism Θ : G ⟶ GL(n, 2). Each invocation Θ(x), x ∈ G, takes time O(n^{2}μ).

In the case where elements of G are given by binary strings of length N, 2^{(n−1)^{2}} ≤ 2^{n(n−1)/2} ∏_{i=1}^{i}(2^{n} − 1) = |GL(n, 2)| ≤ 2^{N}. Hence we can choose M = 1 + \sqrt{N}. If G is specified as a subgroup of GL(m, q), then M = m + 1 suffices by Lemma 4.5.

In this paper, we will need to make use of a function Rand(G) which has as input the generating set G for G and returns a randomly chosen element of G. Ideally, one would like to have an efficient implementation of Rand() which produces elements which are uniformly distributed. In the case where G is black box group, Babai [1] achieves this goal. Simply put, he shows how to construct from G, a set of O(log |G|) elements, at a cost of O(log^{5} |G|) group multiplications, from which nearly uniform distributed random elements of G can be obtained at a cost of O(log^{4} |G|) group multiplications per random element. Although this result is of significant theoretical interest, it does not appear suitable for practical implementations at this point. In this situation, heuristic methods for generating nearly uniformly distributed group random elements are used. A novel heuristic for such random elements is described in [4] and has been used by several authors (see [9] in this volume).

It is also required that we know the prime factorization for each divisor of |G| of the form 2^{i} −1, 1 ≤ i ≤ n. This allows us to use the Bounded Order Algorithm of Celler and Leedham-Green [5] for computing the order of an element x of G when it is known in advance that |x| divides 2^{i} − 1, 1 ≤ i ≤ n.

Our approach is to determine elements of G which can easily be found in a black box setting and which relate naturally to the action of G on an n-dimensional vector space V defined over GF (2). An obvious choice is the set of transvections of G and an associated block system of imprimitivity formed from the action of G on the set of transvections.

The conjugation action of G on this block system (there actually are two of them, but they are conjugate in Aut(GL(n, 2))) is permutation equivalent to the action of G on the non-zero vectors of V. The difficulty lies in describing this action explicitly. What is surprising about our result is not the initial approach, which in its own right has been used extensively by other authors, but that the data structures for computing Θ can be determined without having to enumerate the elements of the block system which would then require time exponential in n.

Theorem 1.1 is a preliminary result. The choice of GL(n, 2) was made to remove certain technical issues which occur with arbitrary finite fields but of sufficient complexity to reveal the difficulties in obtaining a more general result. The only component procedure of our algorithm which is Monte Carlo and not Las Vegas is the determination of n. Removing this obstruction within the required time bound is of considerable interest. This issue along with possible generalizations are discussed in the the last section.

2. Overview of the Algorithm

Transvections play a key role both in determining the value of n and in creating the data structures required to compute the isomorphism Θ : G ⟶ GL(n, 2). Each transvection τ_{v,f} of GL(n, 2) can be identified with a unique vector v ∈ V and a linear functional f ∈ V^{∗} such that f(v) = 0 and τ_{v,f} acts on V according to the following rule:

wτ_{v,f} = w + f(w)v, w ∈ V.

We refer to v as the center of the transvection τ_{v,f}.

The construction of Θ depends on three critical properties of transvections.

(1): Given two transvections τ_{v,f} and τ_{u,g} of GL(n, 2), one can determine certain relations between u, v, f, and g from computing the order of their product. For example, if |τ_{v,f}τ_{u,g}| = 4, then (τ_{v,f}τ_{u,g})^{2} is a transvection and either f(u) = 0, g(v) = 1 and (τ_{v,f}τ_{u,g})^{2} = τ_{u,f} or f(v) = 1, g(v) = 0 and (τ_{v,f}τ_{u,g})^{2} = τ_{v,g} (Lemma 5.2).

(2): The permutation representation of GL(n, 2) on the set of all transvections is imprimitive with precisely two maximal systems of imprimitivity. The representatives of these block systems which contain τ_{v,f} can be described as the sets Γ(f) = {τ_{x,f} : x ∈ V, f(x) = 0, v ≠ 0} and β(v) = {τ_{v,h} : x ∈ V, h(v) = 0, h ≠ 0}.

(3): If τ_{v,f} is a transvection and α is an arbitrary element of GL(n, 2), then

τ_{v,f}^{α} = τ_{vα,fα^{∗}}

where α^{∗} ∈ GL(V^{∗}) is defined by (fα^{∗})(w) = f(wα^{−1}), for w ∈ V.

The first step in the algorithm is to determine the value of n and identify an element t ∈ G that will map under Θ to a transvection of GL(n, 2). This is rather straightforward and is discussed in section 4. Under the assumption that Θ is an isomorphism, we may set Θ(t) = τ_{v,f} for some v ∈ V and f ∈ V^{∗} with f(v) = 0. Note that since transvections form a single conjugacy class in GL(n, 2), the choice of v and f is arbitrary subject only to f(v) = 0.

It will be convenient to denote the preimage of a transvection τ_{u,g} under Θ by t_{u,g} and refer to elements of this conjugacy class of G as transvections as well. Furthermore, we will often denote an arbitrary element of this conjugacy class of G in the form t_{w,h}. This is legitimate as long as we don’t make any assumptions on the values of w and h that can’t be properly inferred from Θ. For example, if t_{w,h} = t_{u_{1},g}t_{u_{2},g} and we have already extended Θ to t_{u_{1},g} and t_{u_{2},g}, then Θ(t_{w,h}) = Θ(t_{u_{1},g})Θ(t_{u_{2},g}) = τ(u_{1}, g)τ(u_{2}, g) = τ(u_{1} + u_{2}, g). Thus w = u_{1} + u_{2} and h = g.

Given a transvection t_{v,f} of G, we may successively use properties (1) and (2) to construct subsets B_{Γ} and B_{β} of G which we will refer to as a dual block pair and which satisfies the following properties:

• Θ(B_{Γ}) = {τ_{v_{1},f}, τ_{v_{2},f}, …, τ_{v_{n−1},f}} where {v_{1}, …, v_{n−1}} is a basis for Γ(f).

• Θ(B_{β}) = {τ_{v_{n},g_{1}}, …, τ_{v_{n},g_{n−1}}} where f(v_{n}) = 1 and {g_{1}, …, g_{n−1}} is a

basis for β(v_{n}).

• g_{i}(v_{j}) = δ_{ij}, 1 ≤ i, j ≤ n − 1, where δ_{ij} is interpreted as an element of

GF (2).

The construction of B_{Γ} and B_{β} is presented in section 6. Here t_{v,f} = t_{v_{1},f}. We set B_{Γ} = {t_{v_{1},f}, …, t_{v_{n−1},f}} and B_{β} = {t_{v_{n},g_{1}}, …, t_{v_{n},g_{n−1}}}.

Since f(v_{n}) = 1, the set {v_{1}, v_{2}, …, v_{n}} is a basis of V. Assuming we know the restriction of Θ to B_{Γ} ∪ B_{β}, the image Θ(x), for an arbitrary x ∈ G, is then determined by computing the coefficients of v_{i}Θ(x) relative to {v_{1}, v_{2}, …, v_{n}} for 1 ≤ i ≤ n. To do this, we make use of (3) above. Thus, for 1 ≤ i ≤ n − 1,

τ_{v_{i},f}^{Θ(x)} = τ_{v_{i}Θ(x),fΘ(x)^{∗}} = τ_{w_{i},h_{i}},

and

τ_{v_{n},g_{n−1}}^{Θ(x)} = τ_{v_{n}Θ(x),g_{n−1}Θ(x)^{∗}} = τ_{w_{n},h_{n}}.

Thus the problem of expressing v_{i}Θ(x) as a linear combination of {v_{1}, v_{2}, …, v_{n}} reduces to the following problem. Given the transvection τ_{w_{i},h_{i}}, express w_{i} as a linear combination of {v_{1}, v_{2}, …, v_{n}}, 1 ≤ i ≤ n. Since we do not have any explicit way of constructing w_{i}, this does not appear to be all that useful. However, for 1 ≤ i ≤ n − 1, τ_{w_{i},h_{i}} = Θ(t_{v_{i},f}^{x}) and so the preimage of τ_{w_{i},h_{i}} under Θ is precisely t_{v_{i},f}^{x} = t_{w_{i},h_{i}} which can be computed in G.

More generally, assume we are given a transvection t_{w,h} of G and we want to express w = ∑_{i=1}^{n} a_{i}v_{i}. Initially, we have no information on the values of w and h. The solution of this problem occurs in two stages and is presented in section 7. In the first stage, we reduce to the case where h = f and simultaneously determine the coefficient a_{n}. This reduction is fairly straightforward and makes use of properties of transvections developed in section 5. In the second stage, we know that t_{w,f} ∈ ⟨B_{Γ}⟩ and want to express t_{w,f} in terms of the basis B_{Γ} for ⟨B_{Γ}⟩. This means, finding coefficients {a_{1}, …, a_{n−1}} such that

t_{w,f} = t_{v_{1},f}^{a_{1}} ⋯ t_{v_{n−1},f}^{a_{n−1}}.

In the black box setting, we do not have an explicit value for w and so the usual linear algebra methods do not work. Instead, we use the existence of our dual block pair (B_{Γ}, B_{β}) which allows us to easily find explicit values for {a_{1}, …, a_{n−1}}. The details are presented in section 7.

3. The Top Level Procedures

The procedure Construct-Data-Structures is used to set up the data structures required for each call to Θ. The input is the generating set G. We will not be concerned with precise probability estimates. Rather, each of the procedures that is called will be responsible for returning the correct answer with constant probability, i.e. with probability at least c for some fixed c, 0 < c < 1. Each procedure will return false if it can detect that the returned value is incorrect. In general, each procedure can achieve higher reliability in the standard way by sampling more random chosen elements. We initialize M to be an upper bound on the dimension n of G. As noted in the introduction, if G is a black box group specified by binary strings of length N, then M may be set to 1 + \sqrt{N}.

Procedure Construct-Data-Structures(G)

Input: A generating set G for G.

Output: The dimension n of G, a transvection t = t_{v,f} ∈ G, an element σ ∈ G which commutes with t and whose order contains a primitive prime divisor of 2^{n−2} − 1 and a dual block pair (B_{Γ}, B_{β}). (If n − 2 = 6, then we require that |σ| = 63.) Reliability: 1/128 Complexity: O((M log^{2} M + n^{2})μ + Mρ + n^{3}ϵ) where μ, ρ, ϵ are as defined in

Theorem 1.1. If G ⊆ GL(m, q)

Set M ← m + 1

[See Lemma 4.5.]

Else If G is a Black Box group Let N be the binary string length for specifying elements of G

Set M ← ⌊1 + \sqrt{N}⌋

Set (ℓ, t, σ) ← Find-Element-in-C_{2}(G, M)

[See section 4] If ℓ = 0

      Return(false)

Set n = ℓ + 2

Set B_{Γ} ← Construct-Block-Basis(n, t, σ, G)

[See section 6]

If B_{Γ} = false
      Return(false)
Set B_{β} ← Construct-Dual-Block-Pair (n, t, σ, B_{Γ}, G)

[See section 6]

If B_{β} = false
      Return(false)

Construct-Data-Structures is Monte Carlo with constant reliability. The procedure Find-Element-in-C_{2} has constant reliability that the returned values (ℓ, t, σ) are correct, hence may return the wrong answer without it being detected. It should be noted, that if n = ℓ + 2 is correct, then it is certain that t is a transvection of G and σ is a ppd(n, 2, n−2) element of G. The two other procedures

Construct-Block-Basis and Construct-Dual-Block-Pair are both Las Vegas

given that n has been correctly determined.

We can now specify the isomorphism Θ: G ⟶ GL(n, 2). Elements of G will be represented as n × n matrices over GF (2) relative to the basis for V = {v_{1}, …, v_{n}} determined by the dual block pair (B_{Γ}, B_{β}), where B_{Γ} = {t_{v_{1},f}, …, t_{v_{n−1},f}}, with t_{v,f} = t_{v_{1},f}, and B_{β} = {t_{v_{n},g_{1}}, …, t_{v_{n},g_{n−1}}}.

Procedure Θ

Input: An arbitrary matrix x ∈ G, B_{Γ} and B_{β}. Output: A matrix (a_{i,j}) for 1 ≤ i ≤ n, 1 ≤ j ≤ n. Complexity:: O(n^{2}μ), where μ is as defined in Theorem 1.1.

For i ← 1 to n − 1

Set (a_{i,1}, …, a_{i,n−1}) ← Compute-Transvection-Center(t_{v_{i},f}^{x}, B_{Γ}, B_{β}) Set (a_{n,1}, …, a_{n,n−1}) ← Compute-Transvection-Center(t_{v_{n},g_{1}}^{x}, B_{Γ}, B_{β}))

[See section 7] Return((a_{i,j}))

4. Finding a Transvection

In this section, we derive a method for finding transvections of GL(n, 2) that does not depend on having the natural representation of GL(n, 2) in hand. This can then be used as the conceptual basis for the procedure Find-Element-in-C_{2}. This procedure is Monte Carlo with constant reliability and may return an incorrect answer without it being detected. However, if we are willing to spend sufficient time, then the probability of error can be reduced below any given threshold.

An element of G = GL(n, 2) is irreducible if its characteristic polynomial is irreducible over GF (2), or equivalently if it acts irreducibly on V. A Singer cycle is a cyclic subgroup of order 2^{n} − 1 which acts transitively on the non-zero vectors of V. It is well known that all Singer cycles are conjugate and that each irreducible element of GL(n, 2) is conjugate to an element of a Singer cycle. A Singer cycle can be constructed through the embedding of GL(1, 2^{n}) = GF (2^{n})^{∗} into GL(n, 2). Furthermore, one can also embed GF (2^{n})^{∗} extended by Aut(GF (2^{n})) into GL(n, 2), where Aut(GF (2^{n})) is a cyclic group of order n induced by the Frobenius automorphism. It then follows that each irreducible element contained in a Singer Cycle is conjugate to n of its powers.

Definition 4.1. A prime p is said to be a primitive prime divisor of 2^{n} − 1 if p | (2^{n} − 1) but p |̸(2^{j} − 1), j < n. An element σ of GL(n, 2) is said to be a ppd(n, 2, e) element, n/2 < e ≤ n, if σ satisfies two conditions. First, it should fix an n − e dimensional subspace of the underlying vector space. Second, |σ| = 63 when e = 6 and |σ| contains a primitive prime divisor of 2^{e} − 1 when e ≠ 6. A ppd(n, 2, n) element is said to be primitive.

Remark 4.2. It follows from a result of Zsigmondy that for e ≠ 6, 2^{e} − 1 always has a primitive prime divisor. Thus a ppd(n, 2, e) element exists for all values of n and e. We employ a slightly more restrictive definition than that given by Niemeyer and Praeger in these proceedings.

We now define a class of elements of GL(n, 2) that occur with high frequency and which allow us to identify transvections in a black box setting.

Definition 4.3. Let τ be a fixed transvection and ν a ppd(n, 2, n − 2) element of order 2^{n−2} − 1. Denote by I_{2}, the set of all elements of the form τσ, where σ ∈ ⟨ν⟩, and σ is a ppd(n, 2, n − 2) element. Set C_{2} = I_{2}^{GL(n,2)}.

Lemma 4.4. |C_{2}|/|GL(n, 2)| ≥ 1/(4(n − 1)).

Proof. Let V = U_{1} ⊕ U_{2} where U_{1} = C_{V} (ν) and U_{2} = [V, ν]. Then τ centralizes U_{2} and stabilizes U_{1}. Hence, C = C_{GL(n,2)}(τν) = C_{GL(U_{1})}(τ|U_{1}) × ⟨ν⟩ ≅ Z_{2} × Z_{2^{n−2}−1}. Furthermore, C = C_{GL(n,2)}(τσ) for each τσ ∈ I_{2}. If N = N_{GL(n,2)}(⟨τν⟩), then N/ ⟨τν⟩ is cyclic of order n − 2. Also, two elements of I are conjugate in G if and only if they are conjugate in N. This follows from the structure of C_{GL(n,2)}(τ) = 2^{2n−3}GL(n − 2, 2). In particular, each conjugacy class contained in C_{2} contains precisely n − 2 elements of I_{2}. Thus

|C_{2}| = {|G|/(2(2^{n−2} − 1))}|I_{2}|/(n − 2)
= {|G|/(2)}|I_{2}|/((2^{n−2} − 1)(n − 2)).

If n ≠ 8, then |I_{2}|/(2^{n−2} − 1) is the proportion of primitive elements in a Singer cycle of GL(n−2, 2), and if n−2 = 6, then it is the proportion of generating elements. However, it is shown in [8, Lemmas 2.3 and 2.4] that this number is at least n−2/(n−1), except when n−2 = 6 in which case it is at least n−2/(2(n−1)). Thus

|C_{2}|/|GL(n, 2)| ≥ 1/4(n − 1)

as required.

The next result will be useful in the case where the generating matrices S for G are given as m × m matrices over GF (q).

Lemma 4.5. If GL(n, 2) is a subgroup of GL(m, q), then n ≤ m + 1.

Proof. Let ζ be a Singer cycle of GL(n, 2). If (q, 2^{n} − 1) = 1, then in some extension field GF (q^{r}), ζ is diagonalizable and has n distinct conjugates. This implies that ζ has at least n distinct eigenvalues as an element of GL(m, q^{r}). Hence n ≤ m. If (q, 2^{n} − 1) ≠ 1, then q is a power of a prime distinct from 2 and so (q, 2^{n−1} − 1) = 1 (since (2^{n} − 1) − (2^{n−1} − 1) = 2^{n−1}). The same argument using an element of order 2^{n−1} − 1 which generates a Singer cycle of GL(n − 1, 2) then yields n − 1 ≤ m.

In our context, G is a black box group isomorphic to GL(n, 2) for some unknown value of n. We need a method for characterizing elements of C_{2} of G which does not depend on any of the usual linear algebra properties.

Lemma 4.6. Let G be a black box group which is isomorphic to GL(n, 2). A necessary condition for g ∈ G to be a ppd(n, 2, e) element for some value of e, is that

• |g| | 2^{e} − 1, and

• |g| contains a primitive prime divisor of 2^{e} − 1.

Lemma 4.6 leads to the following method for identifying elements of C_{2} of G.

Lemma 4.7. Let S be a sequence of elements of G and suppose it is known that S contains an element of C_{2}. Let S′ be the subset of S consisting of those elements g with the property that |g| = 2k_{g} with k_{g} odd. For each g ∈ S′ define t_{g} = g^{k_{g}} and σ_{g} = g^{2}. (Thus, ⟨g⟩ = ⟨t_{g}⟩ × ⟨σ_{g}⟩.) For g ∈ S′, let ℓ_{g} be a non-negative integer set according to the following rule. If k_{g} = 63, set ℓ_{g} = 6. If k_{g} divides 2^{e} − 1 and contains a primitive prime divisor of 2^{e} − 1, set ℓ_{g} = e. Otherwise, set ℓ_{g} = 0. Let ℓ = max{ℓ_{g} : g ∈ S′}. Then ℓ = n − 2. Further, for those g ∈ S′ satisfying ℓ_{g} = ℓ, t_{g} is a transvection and σ_{g} is a ppd(n, 2, n − 2) element.

Proof. Recall from Definition 4.3 that if g ∈ S is an element of C_{2}, then t_{g} is a transvection and σ_{g} is a ppd(n, 2, n − 2) element. Hence ℓ = ℓ_{g} = n − 2.

We claim that any element h with ℓ_{h} = ℓ will be an element of C_{2}. To see this, let V be an n dimensional GF (2)–module for G. Since σ_{h} commutes with the involution t_{h}, σ_{h} stabilizes C_{V} (t_{h}). Furthermore, since dim(C_{V} (t_{h})) ≥ n/2, it follows that either dim(C_{V} (t_{h})) = n − 2 or dim(C_{V} (t_{h})) = n − 1. The case dim(C_{V} (t_{h})) = n − 2 is impossible since in this case, C_{G}(t_{h}) is isomorphic to an extension of a 2-group of order 2^{4n−12} by GL(2, 2) × GL(n − 4, 2) and this is incompatible with the conditions on k_{h}. Thus t_{h} is a transvection.

The following procedure Find-Element-Of-C_{2}-In-Set is based on Lemma 4.7. The input is a set S of elements of G and an upper bound M on the dimension of G. For example, if G is specified by m × m matrices over GF (q), then we can choose M = m + 1 by Lemma 4.5. If it is known in advance that S contains an element g ∈ C_{2}, then Find-Element-Of-C_{2}-In-Set returns (ℓ_{g}, t_{g}, σ_{g}). If it is not known for certain that S contains an element of C_{2}, then the procedure will find an element g ∈ S which appears most likely to be an element of C_{2} and returns (ℓ_{g}, t_{g}, σ_{g}). Otherwise, the procedure concludes that S does not contain an element of C_{2} and returns a triple (ℓ, t, s) with ℓ = 0.

The procedure makes use of the functions Order-Test and Bounded-Order. Order-Test has input an element x ∈ G and the bound M on the dimension of G. It returns either the smallest positive integer i ≤ M such that |x| | 2^{i} −1 or else 0 if no such i exists. Using the standard doubling algorithm together with the observation that |x| | 2^{i} − 1 if and only if x^{2^{i}} = x, it is easy to see that Order-Test requires at most O(log M) multiplications. The function Bounded-Order has as input an element x, an integer i such that |x| | 2^{i} −1 and returns |x|. An implementation can be based on the algorithm described in [5] and requires O(log^{2} M) multiplications. We assume that this function has access to the prime factorization of 2^{i} −1, i ≤ M, and do not consider this in the complexity. Similarly, for each i ≤ M, we assume that we can test if a divisor of 2^{i} − 1 is primitive.

Procedure Find-Element-Of-C_{2}-In-Set

Input: (S, M) where S is a set of elements of G and M is an upper bound on

the dimension of G. Output: A triple (ℓ, t, σ). If the procedure can verify that S does not contain an element of C_{2}, then ℓ is set to 0. Otherwise, ℓ is assigned a value believed to be n − 2, an involution t and an element σ which commutes with t such that g = tσ ∈ S, and g is believed to be an element of C_{2}. Complexity: O(|S| log^{2} Mμ) where μ is as defined in Theorem 1.1

Set (ℓ, t, σ) ← (0, nil, nil) For non-trivial g ∈ S do

Set σ_{g} = g^{2}

      Set ℓ_{g} ← Order-Test(σ_{g}, M)

[ℓ_{g} ← min{i: i ≤ M, |σ_{g}| | 2^{i} − 1} or ℓ_{g} ← 0]
If ℓ_{g} > 0
If g^{2^{ℓg}} ≠ g
[In this case, |g| = 2|σ_{g}|. Otherwise, ⟨g⟩ = ⟨σ_{g}⟩.]

                 Set k_{g} ← Bounded-Order(σ_{g}, ℓ_{g})

[k_{g} ← |σ_{g}|]
If (ℓ_{g} = 6 and k_{g} = 63)

Or k_{g} contains a primitive prime divisor of 2^{ℓ_{g}} − 1 If ℓ_{g} > ℓ

Set (ℓ, t, σ) ← (ℓ_{g}, g^{k_{g}}, σ_{g})

Return(ℓ, t, σ)

The value of ℓ is a lower bound on n − 2 because it arises through the existence of an element whose order divides |GL(ℓ, 2)| but not |GL(i, 2)| for 1 ≤ i < ℓ. If S does contain an element of C_{2}, then Find-Element-Of-C_{2}-In-Set will find it.

We are now able to describe the procedure Find-Element-in-C_{2}. The input to Find-Element-in-C_{2} is a generating set G of G and an upper bound M on the dimension n of G. A single call is made to Find-Element-Of-C_{2}-In-Set with argument a set S of 4M randomly chosen element of G. This will ensure that S contains an element of C_{2} with constant probability.

Procedure Find-Element-in-C_{2}

Input: A generating set G and a bound M on the dimension of G.

Output: A triple (ℓ, t, σ), where ℓ = n − 2, t is a transvection and s commutes

with t such that ts ∈ C_{2}. Reliability: 1 − 1/e. Complexity: O(M log^{2} Mμ + Mρ), where μ, ρ are as defined in Theorem 1.1.

Let S be a set of 4M randomly chosen elements of G

Set (ℓ, t, σ) ← Find-Element-in-C_{2}(S, M)

If ℓ ≠ 0 Return(ℓ, t, σ)

5. Preliminary Results on Transvections

There is a transvection τ_{v,f} of GL(n, 2) for any non-zero vector v ∈ V and linear form f ∈ V^{∗}, such that f(v) = 0. The action of τ_{v,f} on V is given by the formula

wτ_{v,f} = w + f(w)v.

When the field is not GF (2) there is a scale question. Replacing v by λv and f by λ^{−1}f does not change τ_{v,f}.

Lemma 5.1. Two transvections τ_{v,f} and τ_{u,g}:

(i) are the same,

(ii) commute and their product is τ_{u+v,f} when f = g, u ≠ v, (iii) commute and their product, τ_{v,f+g} when f ≠ g, u = v, (iv) commute and their product is not a transvection, when f(u) = g(v) = 0,

f ≠ g, u ≠ v,

(v) have product of order 3 when f(u) = g(v) = 1; note that here, τ_{v,f}^{τ_{u,g}} = τ_{u+v,f+g},

(vi) have product of order 4 with square τ_{v,g} when f(u) = 1 and g(v) = 0, or (vii) have product of order 4 with square τ_{u,f} when f(u) = 0 and g(v) = 1.

Given a fixed transvection τ_{v,f}, we are interested in finding a transvection τ_{u,g} such that τ_{v,f}τ_{u,g} has a specified property.

Lemma 5.2. Let τ_{u,g} be randomly chosen. Then for sufficiently large n, each of the following events has probability approaching 1/4 for large n.

(i) τ_{v,f} commutes with τ_{u,g} but τ_{v,f}τ_{u,g} is not a transvection.

(ii) |τ_{v,f}τ_{u,g}| = 3.

(iii) |τ_{v,f}τ_{u,g}| = 4, with (τ_{v,f}τ_{u,g})^{2} = τ_{v,g}.

(iv) |τ_{v,f}τ_{u,g}| = 4, with (τ_{v,f}τ_{u,g})^{2} = τ_{u,f}.

Proof. The structure of C_{GL(n,2)}(τ_{v,f}) is a split extension of an extra-special 2-group of order 2^{2n−3} by GL(n − 2, 2). Thus the number of transvections is [GL(n, 2) : C_{GL(n,2)}(τ_{v,f})] = (2^{n} − 1)(2^{n−1} − 1). Given a fixed transvection τ_{v,f}, it follows from Lemma 5.1(iv), that the number of transvections τ_{u,g} which satisfy (i) is (2^{n−1} − 2)(2^{n−2} − 2). Hence, the proportion of transvections which have this property is then (2^{n−1} − 2)(2^{n−2} − 2)/(2^{n} − 1)(2^{n−1} − 1). This approaches 1/4 asymptotically and establishes (i). The proofs of (ii), (iii) and (iv) follow in a similar manner.

Remark 5.3. It follows from Lemma 5.2(iii),(iv), that for a given transvection τ_{v,f} with probability 1/2, a randomly chosen transvection τ_{u,g} has the property that τ = (τ_{v,f}τ_{u,g})^{2} is a transvection. In fact, τ = τ_{v,g} or τ_{u,f} and so both ττ_{v,f} and ττ_{u,g} are both transvections. Note that it would be difficult to find a transvection such as τ directly.

Remark 5.4. In the course of constructing Θ, we will often use Lemma 5.1 in the following way. Suppose that t is a transvection of G and Θ(t) = τ_{v,f} so that t is labeled by t = t_{v,f}. Let t′ be an arbitrary transvection of G which we label by t′ = t_{u,g} to indicate that Θ(t) = τ_{u,g}, and suppose there is no a priori relationship between v, f and u, g. If |t_{v,f}t_{u,g}| = 4, then Θ((t_{v,f}t_{u,g})^{2}) = (τ_{v,f}τ_{u,g})^{2}, and so by Lemma 5.1(v),(vi), either (τ_{v,f}τ_{u,g})^{2} = τ_{u,f} or (τ_{v,f}τ_{u,g})^{2} = τ_{v,g} . Hence, the same holds in G, namely (t_{v,f}t_{u,g})^{2} = t_{u,f} or (t_{v,f}t_{u,g})^{2} = t_{v,g}.

6. Building a Dual Block Pair

In this section, we construct the dual block pair (B_{Γ}, B_{β}) required for the construction of the isomorphism Θ. The input to Construct-Block-Basis is the dimension n of G, a transvection t of G, which we denote by t_{v,f} to indicate that Θ(t_{v,f}) = τ_{v,f} ∈ GL(n, 2), an element σ which commutes with t_{v,f} such that Θ(σ) is a ppd(n, 2, n − 2) element of GL(n, 2), and a generating set G for G.

This construction is Las Vegas, in that if the inputs are correct (if G ≃ GL(n, 2), t is a transvection, etc.), then either the answer false is returned or else the correct answer is returned. Thus, one does not need to verify correctness of the answer. Further, there is some constant such that the correct answer is returned with at least that probability. Thus, repeated application of the procedure can assure that if the inputs are correct, then the probability of returning false on all iterations can be made arbitrarily small.

There are two maximal block systems of GL(n, 2) in the conjugation action on the conjugacy class of transvections. The two blocks which contain τ_{v,f} are Γ(f) = {τ_{x,f} : x ∈ V, f(x) = 0, v ≠ 0} and β(v) = {τ_{v,h} : x ∈ V, h(v) = 0, h ≠ 0}. It is clear from Lemma 5.1 that Γ(f) ∪ β(v) contains all transvections which commute with τ_{v,f} and whose product with τ_{v,f} is also a transvection. In our construction, Θ(B_{Γ}) is a basis for ⟨Γ(f)⟩. Note that Γ(f) and β(v) are conjugate in Aut(GL(n, 2)), so the choice that our block maps onto Γ(f) is purely arbitrary.

The first step in applying these ideas to the black box group G is to find another transvection in the same block as t_{v,f}. By Lemma 5.2, the probability is approximately 1/2 that a random transvection t_{u,g} satisfies |t_{v,f}t_{u,g}| = 4. But then (t_{v,f}t_{u,g})^{2} = t_{v,g} or t_{u,f} as in Remark 5.4. Without loss of generality, we may assume that (t_{v,f}t_{u,g})^{2} = t_{u,f}, for some u ≠ v, and hence t_{v,f} and t_{u,f} belong to ⟨B_{Γ}⟩.

Since σ centralizes t_{v,f}, σ normalizes ⟨B_{Γ}⟩. From the structure of C_{G}(t_{v,f}) ≅ 2^{2n−3}GL(n − 2, 2), σ acts irreducibly on a hyperplane of ⟨B_{Γ}⟩. In particular, ⟨B_{Γ}⟩ = ⟨t_{v,f}⟩ ⊕ [⟨B_{Γ}⟩ , ⟨σ⟩] where ⟨t_{v,f}⟩ and [⟨B_{Γ}⟩ , ⟨σ⟩] are, of necessity, the only proper σ invariant subspaces of ⟨B_{Γ}⟩. Since σ does not centralize t_{u,f}, t_{v_{2},f} = [t_{u,f}, σ] ∈ [⟨B_{Γ}⟩ , ⟨σ⟩]. Hence t_{v_{2},f}, t_{v_{2},f}^{σ}, …, t_{v_{2},f}^{σ^{n−2}} is a basis for [⟨Γ(f)⟩ , ⟨σ⟩] and adding t_{v,f} yields a basis for ⟨B_{Γ}⟩. This leads to:

Procedure Construct-Block-Basis

Input: (n, t, σ, G) where n is the dimension of G, t = t_{v,f} is a transvection of G, σ is an element which commutes with t such that σ is a ppd(n, 2, n − 2) element, and G is a generating set for G. Output: A basis B_{Γ} = {t_{v_{1},f}, …, t_{v_{n−1},f}} for ⟨B_{Γ}⟩ Complexity: O(nμ + ρ), where μ, ρ are as defined in Theorem 1.1. Reliability: 1/2

Set t_{v_{1},f} ← t_{v,f} Set x ← Rand(G) and t_{u,g} ← t_{v,f}^{x} If |t_{u,g}t_{v,f}| ≠ 4

      Return (false)

Set t_{u,f} ← (t_{v,f}t_{u,g})^{2} Set t_{v_{2},f} ← [t_{u,f}, σ] For i ← 3 to n − 1

Set t_{v_{i},f} ← t_{v_{i−1},f}^{σ} Set B_{Γ} ← {t_{v_{1},f}, …, t_{v_{n−1},f}}

Return(B_{Γ})

We now focus on finding a suitable vector v_{n} such that {v_{1}, …, v_{n}} is a basis for V and then computing a set B_{β} such that Θ(B_{β}) is basis for ⟨β(v_{n})⟩. We begin by observing from Lemma 5.1 that the probability is 1/4 that a randomly chosen transvection t_{v_{n},g′_{n−1}} satisfies |t_{v,f}t_{v_{n},g′_{n−1}}| = 3, and for such a transvection, f(v_{n}) = 1. Assuming that t_{v_{n},g′_{n−1}} satisfies this property, it follows that v_{1}, …, v_{n−1} together with v_{n} forms a basis for V. We will first construct a basis B′_{β} = {t_{v_{n},g′_{1}}, …, t_{v_{n},g′_{n−1}}} such that Θ(B′_{β}) is a basis for β(v_{n}) and then transform this to a basis B_{β} = {t_{v_{n},g_{1}}, …, t_{v_{n},g_{n−1}}} with the desired property that g_{i}(v_{j}) = δ_{ij}, 1 ≤ i, j ≤ n − 1.

If t_{v_{n},g′_{n−1}} = t_{v,f}^{x}, then conjugating B_{Γ} by x will give a basis for Θ^{−1}(⟨Γ(g′_{n−1})⟩). A randomly chosen transvection t_{u,g′} has probability 1/2 of satisfying the equation |t_{u,g′}t_{v_{n},g′_{n−1}}| = 4. In this case, either (i) g′_{n−1}(u) = 0, g′(v_{n}) = 1 or (ii) g′_{n−1}(u) = 1, g′(v_{n}) = 0. In case (i), |t_{u,g′}t′| | 4 for all t_{w,g′_{n−1}} ∈ Θ^{−1}(⟨Γ(g′_{n−1})⟩). Note that t_{u,g′} has equal likelihood of being in case (i) or case (ii). Assuming we can confirm that t_{u,g′} is in case (ii), it then follows that (t_{u,g′}t_{v_{n},g′_{n−1}})^{2} = t_{v_{n},g′} ∈ Θ^{−1}(β(v_{n})). We may then construct the basis B′_{β} = {t_{v_{n},g′_{1}}, …, t_{v_{n},g′_{n−1}}} for Θ^{−1}(β(v_{n})) by setting t_{v_{n},g′_{1}} = t_{v_{n},g′} and t_{v_{n},g′_{i+1}} = t_{v_{n},g′_{i}}^{σ^{x}}, 1 ≤ i ≤ n − 2.

It remains for us to verify that t_{u,g′} is in case (ii). We first observe that case (ii) can be distinguished from case (i) since |t_{u,g′}t_{w′,g′_{n−1}}| = 3 for approximately 1/2 of the elements t_{w′,g′_{n−1}} ∈ Θ^{−1}(Γ(g′_{n−1})). To see that this happens in case (ii), note that g′_{n−1}(u) = 1 implies that |t_{u,g′}t_{w,g′_{n−1}}| = 4 if g′(w) = 0 and |t_{u,g′}t_{w,g′_{n−1}}| = 3 if g′(w) = 1. Since, g′(v_{n}) = 1 and v_{n} ∈ ker(g_{n−1}), g′ is not trivial on ker(g′_{n−1}). Hence, g′(w) = 1 on 1/2 of the vectors w ∈ ker(g′_{n−1}) which proves the assertion.

Thus our test for finding a transvection t_{u,g′} in case (ii) consists of the following. First generate a random transvection t_{u,g′} and test if |t_{u,g′}t_{v_{n},g_{n−1}}| = 4. If so, then generate a random element t_{w,g′_{n−1}} ∈ Θ^{−1}(Γ(g′_{n−1})) and check if |t_{w,g′_{n−1}}t_{u,g′}| = 3. Thus the overall probability of generating a random transvection which can then be confirmed to be in case (ii) is at least 1/8.

We now describe how to transform B′_{β} to B_{β}. We want to find an (n−1)×(n−1) matrix X = (x_{ij}) such that if

t_{v_{n},g_{i}} = ∏_{j=1}^{n−1} t_{v_{n},g′_{j}}^{x_{ij}}

then g_{i}(v_{j}) = δ_{ij}, 1 ≤ i, j ≤ n − 1. Note that this is equivalent to finding (x_{ij}) such that

g_{i} = ∑_{j=1}^{n−1} x_{ij}g′_{j}

subject to g_{i}(v_{j}) = δ_{ij}, 1 ≤ i, j ≤ n − 1. Let Y = (y_{ij}) be the (n − 1) × (n − 1) matrix with y_{ij} = g′_{i}(v_{j}), 1 ≤ i, j ≤ n − 1. It is easy to see that Y is nonsingular since {g′_{1}, …, g′_{n−1}} is a basis for the annihilator of ⟨v_{n}⟩ in V^{∗} and hence remains independent when viewed as a subset of ⟨v_{1}, …, v_{n−1}⟩^{∗}. It then follows by direct computation that X = Y^{−1}. This reduces the problem of determining X to computing Y. Now although we don’t have an explicit representation of the functionals {g′_{1}, …, g′_{n−1}} or the vectors {v_{1}, …, v_{n−1}}, we can still compute y_{ij} = g′_{i}(v_{j}). Since f(v_{n}) = 1, it follows from Lemma 5.1 that g′_{i}(v_{j}) = 0 if |t_{v_{n},g′_{i}}t_{v_{j},f}| = 4 and g′_{i}(v_{j}) = 1 if |t_{v_{n},g′_{i}}t_{v_{j},f}| = 3.

Procedure Construct-Dual-Block-Pair

Input: (n, t, σ, B_{Γ}, G) where n, t, σ, G are as before and B_{Γ} is the basis for

Θ^{−1}(⟨Γ(f)⟩) constructed in Construct-Block-Basis. Output: A basis B_{β} = {t_{v_{n},g_{1}}, …, t_{v_{n},g_{n−1}}} for Θ^{−1}(⟨β(v_{n})⟩) where f(v_{n}) = 1

and g_{i}(v_{j}) = δ_{ij}, 1 ≤ i, j ≤ n − 1. Complexity: O(n^{2}μ + ρ + n^{3}ϵ), where μ, ρ, ϵ are as defined in Theorem 1.1. Reliability: 1/32

Set x ← Rand(G) Set t_{v_{n},g′_{n−1}} ← t_{v,f}^{x} If |t_{v_{n},g′_{n−1}}t_{v,f}| ≠ 3

      Return(false)

[Thus f(v_{n}) = 1, g′_{n−1} ≠ f, and {v_{1}, …, v_{n}} is a basis for V.] Set t_{w,g′_{n−1}} ← t_{v_{2},f}^{x}

[v_{2} ≠ v implies that w ≠ u] Set x′ ← Rand(G) and t_{u,g′} ← t_{v,f}^{x′} If (|t_{u,g′}t_{v_{n},g′_{n−1}}| ≠ 4 or |t_{w,g′_{n−1}}t_{u,g′}| ≠ 3)

      Return(false)

[This ensures that t_{u,g′} satisfies case (ii) in the previous discussion] Set t_{v_{n},g′_{1}} ← (t_{u,g′}t_{v_{n},g′_{n−1}})^{2}

[t_{v_{n},g′_{1}} is an additional element of Θ^{−1}(β(v_{n}))] For i ← 1 to n − 2

Set t_{v_{n},g′_{i+1}} ← t_{v_{n},g′_{i}}^{σ^{x}} Set B′_{β} ← {t_{v_{n},g′_{1}}, …, t_{v_{n},g′_{n−1}}}

[Construct B_{β}] For i ← 1 to n − 1

For j ← 1 to n − 1

If |t_{v_{n},g′_{i}}t_{v_{j},f}| = 4
Set y_{ij} ← 0

           Else Set y_{ij} ← 1

[In this case, |t_{v_{n},g′_{i}}t_{v_{i},f}| = 3]

Set (x_{ij}) ← (y_{ij})^{−1}

[Viewing (x_{ij}) and (y_{ij}) as matrices] For i ← 1 to n − 1

Set t_{v_{n},g_{i}} = ∏_{j=1}^{n−1} t_{v_{n},g′_{j}}^{x_{ij}}

Return(B_{β})

7. Computing the Center of a Transvection

We will assume the existence of the dual block pair (B_{Γ}, B_{β}) constructed in the previous section. Given an unknown transvection, t_{w,h} ∈ G, we wish to express the vector w ∈ V as a linear combination w = ∑_{i=1}^{n} a_{i}v_{i}. This is accomplished by the procedure Compute-Transvection-Center. Similarly, we can also write h as a linear combination of the basis {f, g_{1}, …, g_{n−1}} for V^{∗}, but this is not required.

Compute-Transvection-Center has two component procedures. The first procedure, denoted by Reduce-Transvection-Center, has input t_{w,h}, B_{Γ} and B_{β}, and returns a pair (t_{w′,f}, a_{n}) where w′ ∈ ⟨v_{1}, …, v_{n−1}⟩ and w = w′ + a_{n}v_{n}. We include the possibility that w′ = 0 in which case t_{w′,f} = 1. The second procedure Sift has as input t_{w′,f}, B_{Γ} and B_{β}, and returns coefficients (a_{1}, …, a_{n−1}) such that w′ = ∑_{i=1}^{n−1} a_{i}v_{i}.

Procedure Compute-Transvection-Center

Input: An unknown transvection t_{w,h}, B_{Γ} and B_{β}.

Output: Coefficients (a_{1}, …, a_{n}) such that w = ∑_{i=1}^{n} a_{i}v_{i}. Complexity: O(nμ), where μ is as defined in Theorem 1.1.

Set (t_{w′,f}, a_{n}) ← Reduce-Transvection-Center(t_{w,h}, B_{Γ}, B_{β})

If t_{w′,f} = 1 Return (0, …, 0, a_{n}) Else Set (a_{1}, …, a_{n−1}) ← Sift(t_{w′,f}, B_{Γ}, B_{β}) Return (a_{1}, …, a_{n})

7.1. The Procedure Reduce-Transvection-Center. We will first present a conceptual development of the procedure, including a proof of correctness and then present the pseudocode. Starting with an arbitrary transvection t_{w,h}, the goal is to find a transvection t_{w′,f} where w′ = w + a_{n}v_{n} ∈ ⟨v_{1}, …, v_{n−1}⟩. This is accomplished through the following sequence of cases.

Case 1 w = v_{n}, hence w′ = 0.

This case can be determined by testing if |t_{w,h}t_{v_{n},g_{i}}| = 2 for all i, 1 ≤ n − 1. If this happens, then g_{i}(v) = 0, 1 ≤ i ≤ n − 1, in which case β(w) = β(v_{n}). Hence w = v_{n}. The procedure will then return (t_{0,h}, 1).

Case 2 f(w) = 0.

We first show that f(w) = 0 if and only if |t_{w,h}t_{v_{i},f}| | 4 for all i, 1 ≤ i ≤ n − 1. This provides a simple test for this case. First note that this condition is true if and only if f(w) = 0. To see this, note that by Lemma 5.1, f(w) = 0 implies |t_{w,h}, t_{v_{i},f}| ∈ {2, 4} for all i. Conversely, assume that |t_{w,h}t_{v_{i},f}| ∈ {2, 4} for all i and f(w) = 1. Then h(v_{i}) = 0 for all i by Lemma 5.1 and so h ∈ ⋂_{i=1}^{n−1} v_{i}^{∘} = ⟨f⟩. But then h = f contradicting h(w) = 0. In this case, a_{n} = 0 and so w′ = w. Further reduction of t_{w′,h} to t_{w′,f} is performed in case 4.

Case 3 f(w) = 1.

Since f(v_{n}) = 1 by our choice of v_{n}, and f(w) = 1 by assumption, w involves v_{n} and a_{n} = 1. Suppose first that |t_{w,h}, t_{v_{n},g_{i}}| = 3 for some i, 1 ≤ i ≤ n − 1. Then t_{w′,h′} is set to t_{w,h}^{t_{vn,g_{i}}} = t_{w+v_{n},h+g_{i}}. In the remaining case, |t_{w,h}, t_{v_{n},g_{i}}| | 4, 1 ≤ i ≤ n − 1. We claim that h(v_{n}) = 0. Otherwise, h(v_{n}) = 1 which implies that g_{i}(w) = 0, 1 ≤ i ≤ n − 1. But then, w = v_{n}, which contradicts h(w) = 0. We may further assume that since f(w) = 1, g_{i}(w) = 1 for some i, 1 ≤ i ≤ n − 1 and hence |t_{w,h}, t_{v_{n},g_{i}}| = 4. In this case, t_{w′,h′} is set to t_{w,h}(t_{w,h}t_{v_{n},g_{i}})^{2} = t_{w+v_{n},h}. This reduces to the case where f(w′) = 0 and is addressed next.

Case 4 f(w′) = 0.

We have reduced to the case of analyzing t_{w′,h′} where f(w′) = 0. Note that the case w′ = 0 has already been discussed in case 1. We know at this point that w′ = w + a_{n}v_{n} for our original transvection t_{w,h}.

Recall from case 2 that |t_{w′,h′}t_{v_{i},f}| | 4 for all i, 1 ≤ i ≤ n − 1. If there is an i such that |t_{w′,h′}t_{v_{i},f}| = 4, then (t_{w′,h′}t_{v_{i},f})^{2} = t_{w′,f} and we return (t_{w′,h′}t_{v_{i},f})^{2}, a_{n}). Otherwise, |t_{w′,h′}t_{v_{i},f}| = 2 for all i, 1 ≤ i ≤ n − 1 which implies that h′ = f and we return (t_{w′,h′}, a_{n}).

Procedure Reduce-Transvection-Center

Input: An unknown transvection t_{w,h}, B_{Γ} and B_{β}.

Output: (t_{w′,f}, a_{n}) where a_{n} = f(w) and w = w′ + a_{n}v_{n}. (Recall that B_{Γ} uniquely determines f.) [Note that we also allow w′ = 0, in which case t_{w′,f} = 1.]

Complexity: O(n^{2}μ), where μ is as defined in Theorem 1.1.

If |t_{w,h}t_{v_{n},g_{i}}| = 2 for all i, 1 ≤ n − 1 [w = v_{n}]

Return (t_{0,h}, 1) If |t_{w,h}t_{v_{i},f}| | 4 for all i, 1 ≤ i ≤ n − 1 [f(w) = 0]

Set t_{w′,h′} ← t_{w,h}

Set a_{n} ← 0

Else [f(w) = 1] Set a_{n} ← 1

If |t_{w,h}t_{v_{n},g_{i}}| = 3 for some i, 1 ≤ n − 1 [h(v_{n}) = 1]
Set t_{w′,h′} ← t_{w,h}^{t_{vn,g_{j}}} [w′ = w + v_{n}]
Else Choose j, 1 ≤ j ≤ n − 1 such that |t_{w,h}t_{v_{n},g_{j}}| = 4
Set t_{v_{n},h} = (t_{w,h}t_{v_{n},g_{j}})^{2}
Set t_{w′,h′} ← t_{w,h}t_{v_{n},h}

For i ← 1 to n − 1 [Now, f(w′) = 0]

If |t_{w′,h′}t_{v_{i},f}| = 4

Return ((t_{w′,h′}t_{v_{i},f})^{2}, a_{n}) [(t_{w′,h′}t_{v_{i},f})^{2} = t_{w′,f}]

Return (t_{w′,h′}, a_{n}) [h′(v_{i}) = 0 for all i, hence h′ = f.]

7.2. The Procedure Sift. The key to the procedure Sift is the choice of basis B_{β} = {t_{v_{n},g_{1}}, …, t_{v_{n},g_{n−1}}} for Θ^{−1}(⟨β(v_{n})⟩) with the property that g_{i}(v_{j}) = δ_{ij}, 1 ≤ i, j ≤ n−1. In this case, if w = ∑_{j=1}^{n−1} a_{j}v_{j}, then g_{i}(w) = a_{i}. Since f(v_{n}) = 1, |t_{w,f}t_{v_{n},g_{i}}| = 3 or 4 depending on whether a_{i} = g_{i}(w) = 1 or 0 respectively.

Procedure Sift

Input: A transvection t_{w,f} ∈ Θ^{−1}(Γ(f)), B_{Γ} and B_{β}.

Output: A sequence (a_{1}, …, a_{n−1}) with each a_{i} ∈ GF (2) such that w =

∑_{i=1}^{n−1} a_{i}v_{i} (or equivalently, such that t_{w,f} = t_{v_{1},f}^{a_{1}} ⋯ t_{v_{n−1},f}^{a_{n−1}}). Complexity: O(nμ), where μ is as defined in Theorem 1.1.

For i ← 1 to n − 1 If |t_{w,f}t_{v_{n},g_{i}}| = 3

Set a_{i} ← 1

      Else Set a_{i} ← 0

[In this case |t_{w,f}t_{v_{n},g_{i}}| = 4]

Return((a_{1}, …, a_{n−1}))

8. Open Questions

We enumerate questions which emerge from this work and which will be the subject of future research efforts on our part.

Question 8.1. The most interesting question concerns the extension of Theorem 1.1 to groups defined over prime fields for odd primes p. There are two possible such extensions.

• Construct the natural representation into GL(n, p) for a black box group G satisfying SL(n, p) ⊆ G ⊆ GL(n, p).

• Construct the natural projective representation into GL(n, p) for a black box group G satisfying P SL(n, p) ⊆ G ⊆ P GL(n, p) (for the case when SL(n, p) is not simple).

It appears that the machinery set up in this paper should settle the two issues raised in Question 8.1, at least for the special linear groups. Such an extension is almost complete.

Question 8.2. Does Theorem 1.1 extend to the other classical groups?

Question 8.3. Can the algorithm used to prove Theorem 1.1 be made Las Vegas?

As indicated in the introduction, proving the correctness of Θ relies solely on verifying the value of n determined by the algorithm. We sketch a two-part approach that verifies n together with the underlying hypothesis that G ≃ GL(n, 2).

(1): Construct a subgroup G_{0} of G with G_{0} ≃ GL(n, 2).

(2): Prove that G = G_{0}

A standard approach to solving (1) is to first find a presentation P = ⟨S|R⟩ for GL(n, 2) and a set S of elements satisfying the presentation P, i.e. there exists a 1-1 map ϕ : S ⟶ S so that each relation of R is satisfied in G if elements of S in the relation are replaced by their respective images under ϕ. This approach works as long as n > 2, since GL(n, 2) is then simple. Given the machinery that has already been developed, it should be possible to construct a set S of transvections in G satisfying P.

In order to answer (2), it suffices to show that each generator g ∈ G of G is an element of G_{0}. A recent result of Celler and Leedham-Green [6] seems to apply directly to this problem. We first compute Θ(g) and then apply [6] to express Θ(g) as word in Θ(S). By shadowing the computation in G, we can then produce an element g_{0} ∈ G_{0} such that Θ(g_{0}) = Θ(g). We then test if g_{0} = g to certify that g ∈ G_{0}.

References

[1] L. Babai, “Local expansion of vertex-transitive graphs and random generation in finite groups”, Proc. 23rd ACM STOC, pp. 164–174.

[2] L. Babai, and R. Beals, (1993). “Las Vegas Algorithms for Matrix Groups,”, Proc. 24th IEEE FOCS, pp. 427–436.

[3] R. Beals, “Towards polynomial time algorithms for matrix groups”, in: Groups and Computation II (L. Finkelstein, W. M. Kantor, eds.), DIMACS Workshop on Groups and Computation (June 1995), A. M. S., to appear.

[4] F. Celler, C. R. Leedham-Green, S .H. Murray, A C. Niemeyer, and E. A. O’Brien, “ Generating random elements of a matrix group”, Comm. Algebra, 23, 1995, 4931–4948.

[5] F. Celler and C. R. Leedham-Green, “Calculating the Order of an Invertible Matrix”, in: Groups and Computation II (L. Finkelstein, W. M. Kantor, eds.), DIMACS Workshop on Groups and Computation (June 1995), A. M. S., to appear.

[6] F. Celler and C. R. Leedham-Green, “A Constructive Recognition Algorithm for the Special Linear Group”, preprint.

[7] F. Celler and C. R. Leedham-Green, “A Non-Constructive Recognition Algorithm for the Special Linear and Other Classical Groups”, in: Groups and Computation II (L. Finkelstein, W. M. Kantor, eds.), DIMACS Workshop on Groups and Computation (June 1995), A. M. S., to appear.

[8] P.M. Neumann and C. Praeger, “A recognition algorithm for special linear groups”, Proc. London Math, Soc. 65 (1992), 555-603.

[9] A.C. Niemeyer and Cheryl Praeger, “Implementing a Recognition Algorithm for Classical Groups”, in: Groups and Computation II (L. Finkelstein, W. M. Kantor, eds.), DIMACS Workshop on Groups and Computation (June 1995), A. M. S., to appear.

College of Computer Science, Northeastern University, Boston, MA 02115,

E-mail address: gene@ccs.neu.edu

College of Computer Science, Northeastern University, Boston, MA 02115,

E-mail address: laf@ccs.neu.edu

Department of Computer Science, St. Andrews University, St. Andrews, Scotland,

E-mail address: sal@cs.st-andrews.ac.uk