COMPUTING IN UNIPOTENT AND REDUCTIVE ALGEBRAIC GROUPS

ARJEH M. COHEN, SERGEI HALLER, AND SCOTT H. MURRAY

Abstract. The unipotent groups are an important class of algebraic groups. We show that techniques used to compute with finitely generated nilpotent groups carry over to unipotent groups. We concentrate particularly on the maximal unipotent subgroup of a split reductive group and show how this improves computation in the reductive group itself.

1. Introduction

A linear algebraic group is unipotent if its elements are unipotent (ie, the elements only have eigenvalue one in every representation). Unipotent groups play a prominent role in the theory of algebraic groups. In this paper, we present algorithms for efficient element operations in unipotent groups. Since unipotent groups are nilpotent, we adapt methods used for computing in finitely generated nilpotent groups. A PC group provides a unique computer representation for the elements of nilpotent groups (see, for example, [HEO05]). Collection gives efficient algorithms for multiplication and inversion of group elements. We modify these concepts to work with a large class of unipotent groups defined over a field. This class contains all unipotent groups if the field has characteristic zero. It also contains the full unipotent subgroup of every split reductive group.

Algorithms for element operations in split reductive algebraic groups are given in [CMT04]. Computations in the unipotent subgroup make the largest single contribution to the time taken by these algorithms. This was the main impetus for the current paper, in which we prove:

Theorem 1.1. Let 𝔽 be a field with effective algorithms for the basic element operations. Let G be a split reductive algebraic group over 𝔽 with rank n. Then there is a normal form for elements of G(𝔽). The word problem for elements in normal form requires O(n^{2}) field operations, and multiplying or inverting them requires O(n^{3}) field operations.

This theorem is a great improvement over the analysis of [CMT04], where we proved that the operations are polynomial time, but did not compute the exponent. This result is optimal in the sense that the timings are asymptotically the same as the straightforward methods for matrices.

In Section 2, we construct FC group schemes, which give normal forms for elements of unipotent groups. We adapt two basic collection strategies in Section 3.

Date: November 1, 2006.

This paper was written during a stay of the second author at the Magma group at University of Sydney. The authors would like to thank Björn Assmann, John Cannon, Michael Harrison, Anthony Henderson, Bill Kantor, Allan Steel, and Donald E. Taylor for useful suggestions and discussions.

We have developed two new algorithms for the full unipotent subgroup of a split reductive algebraic group: The first is a new collection strategy called collection from the outside (Section 4). The second is a direct method for computing products and inverses in classical groups using standard representations (Section 5). Section 6 gives the asymptotic analysis and the proof of Theorem 1.1. Section 7 compares practical timings for the various methods considered and describes the default method used in Magma [BCP97] from version 2.13.

2. Unipotent groups and presentations

Throughout this paper, 𝔽 is a field and 𝔼 is a commutative unital algebra over 𝔽. We assume that we have effective algorithms for the basic element operations in 𝔽 and 𝔼. We find it convenient to use the scheme-theoretic definition of algebraic groups. So an algebraic group defined over 𝔽 is a functor from the category of all commutative unital algebras over 𝔽 to the category of groups, satisfying the appropriate additional conditions [DG70, Wat79]. If G is an algebraic group, then G(𝔼) is an abstract group, called the rational point group of G over 𝔼. For example, the additive group 𝔾_{a} has rational point group 𝔾_{a}(𝔼) = 𝔼^{+}.

We define an 𝔽-unipotent group to be an algebraic group defined over 𝔽 with a normal series in which every quotient is isomorphic to 𝔾_{a}. This is analogous to the definition of an 𝔽-soluble algebraic group in [DG70].

Proposition 2.1. Over a perfect field 𝔽, every connected unipotent group is 𝔽unipotent. Over a field 𝔽 of characteristic zero, every unipotent group is 𝔽-unipotent.

Proof. The first statement follows from [Ros57, Proposition 5, Corollary 2]. The second follows from the first using the standard fact that all unipotent groups are connected in characteristic zero. □

The group α_{p}, defined in [Wat79] over fields of characteristic p > 0, is unipotent but not 𝔽-unipotent.

Let U be an 𝔽-unipotent group. Fix a central series

U = U_{1} > U_{2} > ⋯ > U_{N+1} = 1,

such that each U_{r}/U_{r+1} is 𝔽-isomorphic to 𝔾_{a}. The projection U_{r} → U_{r}/U_{r+1} ≅ 𝔾_{a} splits as an 𝔽-morphism of schemes by [Spr98, Theorem 16.2.6]. Fix splitting maps x_{r} : 𝔾_{a} → U_{r}. Clearly U is parametrised by N-dimensional affine space:

𝔸^{N} → U, (a_{1}, …, a_{N}) ↦ x_{1}(a_{1}) ⋯ x_{N}(a_{N}).

Multiplication and inversion in U(𝔼) are given by polynomials. To be precise

(1)  ∏_{r=1}^{N} x_{r}(a_{r}) ∏_{r=1}^{N} x_{r}(b_{r}) = ∏_{r=1}^{N} x_{r}(F_{r}(a_{1}, …, a_{N}, b_{1}, …, b_{N})),

(2)  (∏_{r=1}^{N} x_{r}(a_{r}))^{−1} = ∏_{r=1}^{N} x_{r}(G_{r}(a_{1}, …, a_{N})),

where all products are written in ascending order, each F_{r} is a polynomial in 2N indeterminates, and each G_{r} is a polynomial in N indeterminates. The F_{r} and G_{r} are called Hall polynomials [Hal69]. These polynomials have coefficients in 𝔽, but tend to be very large and unwieldy. In order to do practical computations in U, we need a more concise description.

We now construct a presentation for the rational point group U(𝔼). Since the series U(𝔼) = U_{1}(𝔼) > U_{2}(𝔼) > ⋯ > U_{N}(𝔼) > U_{N+1}(𝔼) = 1 is central, we have

\begin{aligned}x_{r}(a)x_{r}(b) & ∈ & x_{r}(a + b)U_{r+1}(𝔼), \\ x_{r}(a)^{−1} & ∈ & x_{r}(−a)U_{r+1}(𝔼), \\ x_{s}(b)x_{r}(a) & ∈ & x_{r}(a)x_{s}(b)U_{s+1}(𝔼), \end{aligned}

for a, b ∈ 𝔼 and 1 ≤ r < s ≤ N. Hence we have relations

(3)  x_{r}(a)x_{r}(b) = x_{r}(a + b) ∏_{t=r+1}^{N} x_{t}(f_{rt}(a, b)),

(4)  x_{r}(a)^{−1} = x_{r}(−a) ∏_{t=r+1}^{N} x_{t}(g_{rt}(a)),

(5)  x_{s}(b)x_{r}(a) = x_{r}(a)x_{s}(b) ∏_{t=s+1}^{N} x_{t}(h_{rst}(a, b)),

where f_{rt}, g_{rt}, and h_{rst} are polynomials defined over 𝔽. We note that many of these relations are redundant (including (4) for all r), but the extra relations are useful for computation.

Theorem 2.2. Let U be an 𝔽-unipotent group and let 𝔼 be a commutative 𝔽algebra. Let Ũ(𝔼) be the group with generators x_{r}(a), for a ∈ 𝔼, r = 1, …, N, and relations (3), (4), and (5), for a, b ∈ 𝔼, 1 ≤ r < s ≤ N. Then the natural map Ũ(𝔼) → U(𝔼) is an isomorphism of abstract groups.

Proof. Since the given relations hold in U(𝔼), the map is well defined. The map is onto because U(𝔼) is generated by the images of the generators of Ũ(𝔼). Every element of Ũ(𝔼) is a word with terms of the form x_{r}(a) or x_{r}(a)^{−1}. This word can be collected into a product ∏_{r=1}^{N} x_{r}(a_{r}). This is achieved by first eliminating all inverses using (4), then putting the terms in order by the subscripts using (5) and removing multiple terms with the same subscript using (3). If the words ∏_{r=1}^{N} x_{r}(a_{r}) and ∏_{r=1}^{N} x_{r}(b_{r}) are equal in U(𝔼), then a_{r} = b_{r} for all r, and so these words are also equal in Ũ(𝔼). Hence the map is injective and we are done. □

We say that the group scheme U is presented by Ũ.

Now suppose we are given an arbitrary system of 𝔽-polynomials f_{rt}(a, b) and g_{rt}(a, b), for 1 ≤ r < t ≤ N; and h_{rst}(a), for 1 ≤ r < s < t ≤ N. Define the group functor Ũ by taking Ũ(𝔼) to be the abstract group given by generators x_{r}(a), for a ∈ 𝔼, r = 1, …, N, and relations (3), (4), and (5). We call Ũ an FC group functor over 𝔽. FC stands for field-commutator, since the relations involve field operations and commutators, just as the PC presentation of a nilpotent group involves powers and commutators. We call Ũ consistent if the map

𝔼^{N} → Ũ(𝔼), (a_{1}, …, a_{N}) ↦ x_{1}(a_{1}) ⋯ x_{N}(a_{N})

is injective for every commutative 𝔽-algebra 𝔼. Theorem 2.2 implies that every 𝔽-unipotent group is presented by a consistent FC group functor. We now prove the converse:

Theorem 2.3. Every consistent FC group functor defined over 𝔽 is an 𝔽-unipotent group.

Proof. Let Ũ be the consistent FC group functor. Ignoring the multiplication, we can consider Ũ to be the N-dimensional affine scheme. Using collection, as in the proof of Theorem 2.2, we can find polynomials F_{r} and G_{r} such that equations (1) and (2) are satisfied in Ũ(𝔼). So Ũ is an 𝔽-algebraic group scheme, since F_{r} and G_{r} are clearly defined over 𝔽. Finally define algebraic subgroups U_{r} = ∏_{k=r}^{N} im(x_{r}). These give a normal series for U in which every quotient is isomorphic to 𝔾_{a}, and so Ũ is an 𝔽-unipotent group. □

Let U be an 𝔽-unipotent group. Suppose the projection U_{r} → 𝔾_{a} splits as a homomorphism of 𝔽-group schemes, not just as a morphism of 𝔽-schemes. Then we can take x_{r} : 𝔾_{a} → U_{r} to be a homomorphism, and so replace (3) and (4) by

(6)  x_{r}(a)x_{r}(b) = x_{r}(a + b).

It follows immediately that

(7)  x_{r}(a)^{−1} = x_{r}(−a),

and so all the polynomials f_{rt} and g_{rt} are zero. If x_{r} is a homomorphism for r = 1, …, N, we call the corresponding FC group functor split.

Theorem 2.4. If 𝔽 is a field of characteristic zero, then every unipotent group defined over 𝔽 is presented by a split FC group functor over 𝔽.

Proof. Since 𝔽 has characteristic zero, every unipotent group U defined over 𝔽 is 𝔽-unipotent by Proposition 2.1. By induction, we can assume that U/U_{N} is presented by a split FC group functor. Fix maps y_{r} : 𝔾_{a} → U/U_{N}, for r = 1, …, N − 1, defining this functor. By [Ser88, Proposition VII.8], Ext(𝔾_{a}, 𝔾_{a}) = 0. Hence Ext(U/U_{N}, 𝔾_{a}) = 0, by repeated application of the long exact sequence for Hom(∘, 𝔾_{a}). So there exists a homomorphism y : U/U_{N} → U splitting the projection U → U/U_{N}. Define x_{r} = y ∘ y_{r} for r = 1, …, N − 1. Take x_{N} to be the 𝔽-injection 𝔾_{a} ≅ U_{N} → U. These maps clearly define a split FC group functor presenting U. □

If 𝔽 has positive characteristic, then the Witt-vector groups [Ser88] provide examples of 𝔽-unipotent groups which cannot be presented by split FC group functors. The full unipotent subgroup of a split reductive group is always presented by a split FC group functor, as we show in Proposition 4.1 below.

3. Collection and symbolic collection

We now extend some of the standard collection strategies for PC groups to FC group functors. The precise order in which the relations are applied has a huge impact on the speed of collection. Many strategies have been suggested, and we have not attempted to extend them all to FC group functors. We have implemented two fundamental techniques: collection from the left [LGS90, VL90]; and a slightly improved version of collection to the left [HJ76] (we collect the rightmost rather than the leftmost occurrence of the least uncollected letter).

Let U be an FC group functor over 𝔽, and let 𝔼 be a commutative 𝔽-algebra. The algorithms in this section operate on a word w ∈ U(𝔼). This word is always equal to ∏_{i=1}^{M} x_{r_{i}}(a_{i})^{ε_{i}}, ie, the parameters M ∈ ℕ, a_{i} ∈ 𝔼, ε_{i} = ±1, and r_{i} ∈ {1, …, N} are automatically modified when w is. Algorithm 1 describes the basic step of collection. When we say “apply a certain relation to a subword”, we mean match the subword with the left hand side of the relation, and replace it by the right hand side. CollectSubword looks at the term at position j in the word w, and either removes an inverse (if ε_{j} = −1) or ensures that r_{j−1} < r_{j}. In addition to the modified word w, it returns indices j_{1} and j_{2}. Collection to the left (Algorithm 2)

CollectSubword := function(U, w = ∏_{i=1}^{M} x_{r_{i}}(a_{i})^{ε_{i}}, j)

if ε_{j} = −1 then apply (4) to the subword x_{r_{j}}(a_{j})^{−1}

j_{1} := j, j_{2} := j

else if j > 1 and r_{j−1} = r_{j} then apply (3) to the subword x_{r_{j}}(a_{j−1})x_{r_{j}}(a_{j})

j_{1} := j − 1, j_{2} := j_{1} + #{t : f_{r_{j}t}(a_{j−1}, a_{j}) ≠ 0}

else if j > 1 and r_{j−1} > r_{j} then apply (5) to the subword x_{r_{j−1}}(a_{j−1})x_{r_{j}}(a_{j}) j_{1} := j − 1 if j_{1} > 1 and r_{j_{1}−1} < r_{j_{1}} then

j_{2} := j_{1}

else

j_{2} := j_{1} + 1 + #{t : h_{r_{j}r_{j−1}t}(a_{j−1}, a_{j}) ≠ 0}

end if else

j_{1} := j, j_{2} := j_{1} + 1

end if

return w, j_{1}, j_{2}

Algorithm 1: Collect subword

works by collecting all terms x_{1}(a), followed by all terms x_{2}(a), and so on. This uses the index j_{1}, which gives the new largest j such that r_{j} = r. Collection from

Input: An FC group functor U and a word w = ∏_{i=1}^{M} x_{r_{i}}(a_{i})^{ε_{i}}. Output: A product ∏_{r=1}^{N} x_{r}(b_{r}) that is equal to w as an element of U(𝔼).

for r := 1 to N do let j be the largest i such that r_{i} = r while j ≥ r do

w, j_{1}, j_{2} := CollectSubword(U, w, j), j := j_{1} end while

end for

return w

Algorithm 2: Collection to the left

the left (Algorithm 3) goes through the word from left to right, correcting each term that is out of position. This uses the index j_{2}, which gives the next term which is potentially out of position.

Symbolic collection is a standard method for improving the efficiency of element multiplication in a PC group. This depends on the observation that we can collect a generic product, and then substitute into polynomials for subsequent collections. This is particularly easy in the case of FC group functors: simply take Input: An FC group functor U and a word w = ∏_{i=1}^{M} x_{r_{i}}(a_{i})^{ε_{i}}. Output: A product ∏_{r=1}^{N} x_{r}(b_{r}) that is equal to w as an element of U(𝔼).

j := 1

while j ≤ M do

w, j_{1}, j_{2} := CollectSubword(U, w, j), j := j_{2} end while return w

Algorithm 3: Collection from the left

𝔼 = 𝔽[a_{1}, a_{2}, …, a_{N}, b] and do N collections in U(𝔼) to get relations

(8)  ( ∏_{s=r+1}^{N} x_{s}(a_{s}))x_{r}(b) = x_{r}(b)( ∏_{s=r+1}^{N} x_{s}(c_{rs}))

where c_{rs} is a polynomial in b and a_{r+1}, …, a_{N}. Now, taking arbitrary 𝔼 again, we can multiply two collected words ∏_{i=1}^{N} x_{i}(a_{i}) and ∏_{i=1}^{N} x_{i}(b_{i}) by substituting values from 𝔼 into the (N −1)N/2 polynomials c_{rs} in the obvious manner. A similar method can be used to compute inverses.

The advantage of symbolic collection is that each operation is faster. The disadvantage is that more preprocessing time and memory are required. In order to save memory, we represent our polynomials as straight-line programs (see [LG01] for a description of straight-line programs for group elements; the implementation for polynomials is due to Allan Steel). This means that the polynomials are basically just the collection preserved in amber, so the collection method used is still important. We note that there is another common symbolic collection algorithm, called Deep Thought [LGS98, Mer97], but we have not implemented it for unipotent groups.

4. Collection in the full unipotent subgroup

We now describe a new collection strategy for the full unipotent subgroup of a reductive group. Let G be an 𝔽-split reductive algebraic group [Spr98]. Fix a split maximal torus T in G, and a Borel subgroup B containing T. Let U be the unipotent radical of B. Since U is unique up to G-conjugacy, we refer to U as the full unipotent subgroup of G. Let Φ be the root system of G with respect to T, and let Φ^{+} ⊆ Φ be the positive roots with respect to B.

Write Φ^{+} = {α_{1}, α_{2}, …, α_{N}} with the roots in an order compatible with height, ie, ht(α_{r}) < ht(α_{s}) implies r < s. For each α ∈ Φ^{+}, there is a subgroup X_{α} of U isomorphic to 𝔾_{a}. Write x_{r} for the isomorphism 𝔾_{a} → X_{α_{r}}. Then U_{r} = ∏_{s=r}^{N} X_{α_{s}}, for r = 1, …, N + 1, defines a central series for U. The corresponding FC group functor has relations (6) and

(9)  x_{s}(b)x_{r}(a) = x_{r}(a)x_{s}(b) ∏_{\begin{matrix}α_{t}=iα_{r}+jα_{s}, \\ i,j>0 \end{matrix}} x_{t}(C_{ijα_{r}α_{s}}a^{i}b^{j}),

where the constants C_{ijα_{r}α_{s}} are defined as in [Car72]. Recall that these constants depend on the combinatorics of Φ, and on the choice of a sign for each nonsimple positive root. In [CMT04], a method for computing these constants is given which is efficient for small rank groups. For large ranks, we outline a new method in Section 5. We now have:

Proposition 4.1. The full unipotent subgroup of a split reductive group is presented by a split FC group functor.

Note that most of the polynomials h_{rst} from (5) of Section 2 are zero in this case. This gives us much greater flexibility in how we collect words. The ordering of the roots is of vital importance in this section. We specify an ordering in terms of subscripts: α_{1}, …, α_{N}. The subscripts on the injections x_{r} : 𝔾_{a} → U are always kept in agreement with the root ordering under discussion.

Words in U need not be collected into an order compatible with height. In fact, the algorithms of the previous section work for all orderings α_{1}, α_{2}, …, α_{N} of Φ^{+} with the property that α_{r} + α_{s} = α_{t} implies t > r and t > s. We call such an ordering left-additive.

An ordering α_{1}, α_{2}, …, α_{N} of Φ^{+} is called additive if α_{r} + α_{s} = α_{t} implies t lies between r and s (ie, r < t < s or s < t < r). Additive orderings reflect more of the combinatorial structure of the root system than left-additive orderings do. The existence and construction of additive orderings is considered in [Pap94] (see Section 6 below for more details).

In order to collect a word into the additive ordering, we replace relation (9) with

(10)  x_{s}(b)x_{r}(a) = x_{r}(a)( ∏_{\begin{matrix}α_{t}=iα_{r}+jα_{s}, \\ i,j>0 \end{matrix}} x_{t}(C_{jiα_{s}α_{r}}a^{i}(−b)^{j})) x_{s}(b),

which can be proved by applying (9) to x_{r}(a)x_{s}(−b). We then use collection from the outside (Algorithm 4), which is a modified version of collection from the left. The basic idea is to run collection from both sides simultaneously, until we meet in the middle. The two collections could easily be run in parallel, but we alternate between them. The subroutine CollectSubword from Algorithm 3 is slightly modified for both collections (CollectSubwordL and CollectSubwordR). The returned value L is the increase in the word length and k is the index of the next term potentially out of position.

Finally we note that symbolic collection works with collection from the outside, with the obvious minor modifications.

5. The full unipotent subgroup of a classical group

In this section, we present an alternative to collection which is much more efficient when G has large semisimple rank. We derive formulas for the defining polynomials of the full unipotent subgroup U of a split classical group G. This allows us to write code that implicitly applies the defining polynomials of U without having to store them explicitly in memory. We do not consider exceptional groups here, because their semisimple rank is at most 8.

The rough outline of our method is as follows: We index the roots by pairs of integers. We then construct a minimal degree matrix representation of G. We take the basis for the representation consisting of weight vectors, ordered according to the dominance ordering on the corresponding weights [Hum78]. We then order the roots by going down each column of this matrix representation, and seeing where the parameters corresponding to each root appear. We call this the representation CollectSubwordL := function(U, w = ∏_{i=1}^{M} x_{r_{i}}(a_{i})^{ε_{i}}, j)

if ε_{j} = −1 then apply (7) to the subword x_{r_{j}}(a_{j})^{−1} k := j, L := 0

else if j > 0 and r_{j−1} = r_{j} then apply (6) to the subword x_{r_{j}}(a_{j−1})x_{r_{j}}(a_{j}) k := j − 1, L := −1

else if j > 0 and r_{j−1} > r_{j} then apply (10) to the subword x_{r_{j−1}}(a_{j−1})x_{r_{j}}(a_{j}) k := j − 1, L := #{t : α_{t} = kα_{r_{j}} + lα_{r_{j−1}} for k, l > 0}

else

k := j + 1, L := 0 end if return w, k, L

CollectSubwordR := function(U, w = ∏_{i=1}^{M} x_{r_{i}}(a_{i})^{ε_{i}}, j)

if ε_{j} = −1 then apply (7) to the subword x_{r_{j}}(a_{j})^{−1} k := j, L := 0

else if j < M and r_{j} = r_{j+1} then apply (6) to the subword x_{r_{j}}(a_{j})x_{r_{j}}(a_{j+1}) k := j, L := −1

else if j < M and r_{j} > r_{j+1} then apply (10) to the subword x_{r_{j}}(a_{j})x_{r_{j+1}}(a_{j+1}) L := #{t : α_{t} = kα_{r_{j+1}} + lα_{r_{j}} for k, l > 0}, k := j + 1 + L

else

k := j − 1, L := 0 end if return w, k, L

Input: An FC group functor U and a word w = ∏_{i=1}^{M} x_{r_{i}}(a_{i})^{ε_{i}}. Output: A product ∏_{r=1}^{m} x_{r}(b_{r}) that is equal to the input as an element of U(𝔼).

i := 1, j := M while i < j do

w, k, L := CollectSubwordL(U, w, i), i := k, M := M + L, j := j + L if i < j then

w, k, L := CollectSubwordR(U, w, j), j := k, M := M + L end if

end while return w

Algorithm 4: Collection from the outside ordering. Note that the representation ordering is also an additive ordering, except in Cartan type C_{ℓ}, where it gives an additive ordering on the coroots.

The representation of roots by pairs of integers can also be used to compute the constants C_{ijα_{r}β_{r}}. For large classical groups, this is much more efficient than the method given in [CMT04]. We omit the details since this is a technical but straightforward application of formulas in [Car72].

We consider each classical type in Subsections 5.1 to 5.4. In each subsection, we fix a particular isogeny type and particular extraspecial signs [Spr98]. The choice of isogeny class is irrelevant, since the structure of the unipotent subgroup is independent of isogeny. We can easily transform between different choices of extraspecial signs using Theorem 29 of [Ste68].

5.1. Cartan type A_{ℓ}: Linear of degree ℓ + 1. Let G = SL_{l+1} and let U be the algebraic subgroup of all lower unitriangular matrices. The root system of G has Cartan type A_{ℓ}. Let V = ℝ^{ℓ+1} with basis e_{1}, …, e_{ℓ+1}. Then the roots are

α_{ij} = e_{i} − e_{j}

for i, j = 1, …, ℓ + 1 with i ≠ j. The simple roots are α_{i,i+1} for i = 1, …, ℓ. A root α_{ij} is positive if, and only if, i < j. Roots add by the formulas α_{ij} + α_{jm} = α_{im}, and α_{ij} + α_{km} = 0 unless j = k or i = m.

Define the map x_{ij} : 𝔾_{a} → G by x_{ij}(a) = I + aE_{ji}. The representation order on the roots is simply the lexicographic order on the corresponding pairs of integers. We label the coordinates of 𝔸^{(ℓ+1)ℓ/2} by the root pairs in this order, ie, a ∈ 𝔸^{(ℓ+1)ℓ/2}(𝔼) has the form

a = (a_{12}, a_{13}, …, a_{1,ℓ+1}, a_{23}, …, a_{2,ℓ+1}, …, a_{ℓ,ℓ+1}).

We can now define a parametrisation φ : 𝔸^{(ℓ+1)ℓ/2} → U by

φ(a) := ∏_{i=1}^{ℓ+1} ∏_{j=i+1}^{ℓ+1} x_{ij}(a_{ij}) = ( \begin{matrix}1 \\ a_{12} & 1 \\ a_{13} & a_{23} & 1 \\ ⋮ & ⋮ & ... & ... \\ a_{1,ℓ+1} & a_{2,ℓ+1} & … & a_{ℓ,ℓ+1} & 1 \end{matrix} ) .

We now get φ(a)φ(b) = φ(c) where

c_{ij} = a_{ij} + ∑_{i<k<j} b_{ik}a_{kj} + b_{ij}.

Also φ(a)^{−1} = φ(d) where

d_{ij} = −a_{ij} − ∑_{i<k<j} d_{ik}a_{kj}

The formulas for inversion are defined recursively and are computed in reverse representation order. We note that it is easy to derive a direct formula for d_{ij}, but the recursive version can be evaluated with fewer operations.

5.2. Cartan type B_{ℓ}: Orthogonal of degree 2ℓ + 1. Let F_{m} be the m × m matrix over 𝔽 of the form

(\begin{matrix}0 & … & 0 & 1 \\ 0 & … & 1 & 0 \\ ⋮ & ... & ⋮ & ⋮ \\ 1 & … & 0 & 0 \end{matrix}) .

We assume, for this subsection only, that 𝔽 has odd characteristic. Since the group of type B_{ℓ} is isomorphic to the group of type C_{ℓ} in characteristic 2, this restriction is not critical. Let G = SO_{2ℓ+1} be the special orthogonal group of the orthogonal form with matrix

(\begin{matrix}0 & 0 & F_{ℓ} \\ 0 & 2 & 0 \\ F_{ℓ} & 0 & 0 \end{matrix}) .

Let U be the group of all lower unitriangular matrices in G. The root system of G has Cartan type B_{ℓ}. Let V = ℝ^{ℓ} with basis e_{1}, …, e_{ℓ}. The roots are

α_{si,tj} = se_{i} − te_{j} and α_{si,0} = se_{i},

for i, j = 1, …, ℓ with i ≠ j and s, t = ±1. For the sake of readability, we write ī instead of −i in subscripts, eg, α_{2,−3} is denoted α_{2¯3}. Note that α_{ij} = αj̄ ī for all i, j = ±1, …, ±ℓ. The simple roots are α_{i,i+1}, for i = 1, …, ℓ − 1, and α_{n0}. A root α_{i,tj} for i, j > 0 is positive if, and only if, i < j; a root α_{si,0} is positive if, and only if, s = +1.

Define the root maps by

x_{ij}(a) = I + a(E_{ji} − E_{2ℓ−i+2,2ℓ−j+2}),
x_{ij̄}(a) = I + a(E_{2ℓ−j+2,i} − E_{2ℓ−i+2,j}),
x_{i0}(a) = I + a(2E_{ℓ+1,i} − E_{i,ℓ+1}) − a^{2}E_{2ℓ−i+2,i}, and
x_{ī0}(a) = I + a(E_{2ℓ−i+2,ℓ+1} − 2E_{ℓ+1,2ℓ−i+2}) − a^{2}E_{i,2ℓ−i+2}.

Let J_{i} be the sequence of integers [i+1, i+2, …, ℓ, 0, −ℓ, …, −(i+2), −(i+1)]. Let J′_{i} := J_{i} \ {0}. The representation order on the positive roots is the lexicographic order on pairs, with the integers ordered as in J_{0}. Label the coordinates of 𝔸^{ℓ^{2}} by the root pairs in this order. Now define a parametrisation φ : 𝔸^{ℓ^{2}} → U by

φ(a) := ∏_{i=1}^{ℓ} ∏_{j∈J_{i}} x_{ij}(a_{ij})

= ( \begin{matrix}1 \\ a_{12} & 1 \\ ⋮ & ... & ... \\ a_{1ℓ} & … & a_{ℓ−1,ℓ} & 1 \\ 2a_{10} & … & 2a_{ℓ−1,0} & 2a_{ℓ0} & 1 \\ a_{1ℓ̄} & … & a_{ℓ−1,ℓ̄} & a′′_{ℓ} & a′_{ℓ0} & 1 \\ ⋮ & ... & ... & a′_{ℓ−1,ℓ̄} & a′_{ℓ−1,0} & a_{ℓ−1,ℓ} & ... \\ a_{1¯2} & a′′_{2} & ... & ⋮ & ⋮ & ⋮ & ... & 1 \\ a′′_{1} & a′_{1¯2} & … & a′_{1ℓ̄} & a′_{10} & a′_{1ℓ} & … & a′_{12} & 1 \end{matrix} ) .

where

a′′_{i} = −2a_{i0}^{2} − ∑_{i<k≤ℓ} a_{ik}a_{ik̄},  a′_{i0} = −a_{i0} − ∑_{i<k≤ℓ} a_{ik}a′_{k0},
a′_{ij} = −a_{ij} − ∑_{i<k<j} a_{ik}a′_{kj},
a′_{ij̄} = −a_{ij̄} − ∑_{i<k<j} a_{ik}a′_{kj̄} − a_{ij}a′′_{j} − 2a_{i0}a_{j0} − ∑_{k∈J′_{j}} a_{ik}a_{jk̄}.

Now φ(a)φ(b) = φ(c) where

c_{i0} = a_{i0} + b_{i0} + ∑_{i<k≤ℓ} b_{ik}a_{k0},  c_{ij} = a_{ij} + b_{ij} + ∑_{i<k<j} b_{ik}a_{kj},
c_{ij̄} = a_{ij̄} + b_{ij̄} + ∑_{i<k<j} b_{ik}a_{kj̄} + a′′_{j}b_{ij} + 2b_{i0}a′_{j0} + ∑_{k∈J′_{j}} b_{ik}a′_{jk̄}.

And φ(a)^{−1} = φ(d) where

d_{i0} = −a_{i0} − ∑_{i<k≤ℓ} d_{ik}a_{k0},  d_{ij} = −a_{ij} − ∑_{i<k<j} d_{ik}a_{kj},
d_{ij̄} = −a_{ij̄} − ∑_{i<k<j} d_{ik}a_{kj̄} − a′′_{j}d_{ij} − 2d_{i0}a′_{j0} − ∑_{k∈J′_{j}} d_{ik}a′_{jk̄}.

All of these equations are recursive and are computed in reverse representation order.

5.3. Cartan type C: Symplectic. Let G = Sp_{2ℓ} be the symplectic group of the symplectic form with matrix

(\begin{matrix}0 & F_{ℓ} \\ −F_{ℓ} & 0 \end{matrix})

Let U be the group of all lower unitriangular matrices in G. The root system of G has Cartan type C_{ℓ}. Let V = ℝ^{ℓ} with basis e_{1}, …, e_{ℓ}. The roots are

α_{si,tj} = se_{i} − te_{j},

for i, j = 1, …, ℓ with i ≠ j, and s, t = ±1. Once again α_{ij} = αj̄ ī for all i, j = 0, ±1, …, ±ℓ. The simple roots are α_{i,i+1} for i = 1, …, ℓ − 1, and α_{ℓℓ̄}. A root α_{i,tj} is positive if, and only if, i < j.

Define the root maps by

x_{ij}(a) = I + a(E_{ji} − E_{2ℓ−i+1,2ℓ−j+1}),
x_{ij̄}(a) = I + a(E_{2ℓ−j+1,i} + E_{2ℓ−i+1,j}), and
x_{iī}(a) = I + aE_{2ℓ−i+1,i}.

The representation order on the positive roots is the lexicographic order on pairs, with the integers ordered as in J′_{0}. Label the coordinates of 𝔸^{ℓ^{2}} by the root pairs in this order. Now define a parametrisation φ : 𝔸^{ℓ^{2}} → U by

φ(a) := ∏_{i=1}^{ℓ+1} ∏_{j∈J′_{i}} x_{ij}(a_{ij})

= ( \begin{matrix}1 \\ a_{12} & 1 \\ ⋮ & ... & ... \\ a_{1ℓ} & … & a_{ℓ−1,ℓ} & 1 \\ a_{1ℓ̄} & … & a_{ℓ−1,ℓ̄} & a′′_{ℓ} & 1 \\ ⋮ & ... & ... & a′_{ℓ−1,ℓ̄} & a′_{ℓ−1,ℓ} & ... \\ a_{1¯2} & a′′_{2} & ... & ⋮ & ⋮ & ... & 1 \\ a′′_{1} & a′_{1¯2} & … & a′_{1ℓ̄} & a′_{1ℓ} & … & a′_{12} & 1 \end{matrix} ) ,

where

a′′_{i} = a_{iī} − ∑_{i<j≤ℓ} a_{ij}a_{ij̄},  a′_{ij} = a_{ij} − ∑_{i<k<j} a_{ik}a′_{kj},
a′_{ij̄} = a_{ij̄} − ∑_{i<k<j} a_{ik}a′_{kj̄} − a_{ij}a′′_{j} − ∑_{k∈J′_{j}} sign(k)a_{ik}a_{jk̄}.

Now φ(a)φ(b) = φ(c) where

c_{ij} = a_{ij} + b_{ij} + ∑_{i<k<j} b_{ik}a_{kj},  c_{iī} = a′′_{i} + b′′_{i} + ∑_{i<k≤ℓ} c_{ik}c_{ik̄} + ∑_{k∈J′_{i}} b_{ik}a′_{ik̄},

c_{ij̄} = a_{ij̄} + b_{ij̄} + ∑_{i<k<j} b_{ik}a_{kj̄} + a′′_{j}b_{ij} + ∑_{k∈J′_{j}} b_{ik}a′_{jk̄}.

And φ(a)^{−1} = φ(d) where

d_{ij} = −a_{ij} − ∑_{i<k<j} d_{ik}a_{kj},  d_{iī} = −a′′_{i} + ∑_{i<k≤ℓ} d_{ik}d_{ik̄} − ∑_{k∈J′_{i}} d_{ik}a′_{ik̄},

d_{ij̄} = −a_{ij̄} − ∑_{i<k<j} d_{ik}a_{kj̄} − a′′_{j}d_{ij} − ∑_{k∈J′_{j}} d_{ik}a′_{jk̄}.

5.4. Cartan type D: Even-degree orthogonal. Let G = SO_{2ℓ} be the orthogonal group of the orthogonal form with matrix F_{2ℓ}. Let U be the group of all lower unitriangular matrices in G. The root system of G has Cartan type D_{ℓ}. Let V = ℝ^{ℓ} with basis e_{1}, …, e_{ℓ}. The roots are

α_{si,tj} = se_{i} − te_{j},

for i, j = 1, …, ℓ with i ≠ j and s, t = ±1. The simple roots are α_{i,i+1}, for i = 1, …, ℓ − 1, and α_{n−1,ℓ̄}. A root α_{i,tj} for i, j > 0 is positive if, and only if, i < j.

Define the root maps by

x_{ij}(a) = I + a(E_{ji} − E_{2ℓ−i+1,2ℓ−j+1}) and
x_{ij̄}(a) = I + a(E_{2ℓ−j+1,i} − E_{2ℓ−i+1,j}).

The representation order on the positive roots is the lexicographic order on pairs, with the integers ordered as in J′_{0}. Label the coordinates of 𝔸^{ℓ(ℓ−1)/2} by the root pairs in this order. Now define a parametrisation φ : 𝔸^{ℓ(ℓ−1)/2} → U by

φ(a) := ∏_{i=1}^{ℓ} ∏_{j∈J′′_{i}} x_{ij}(a_{ij})

= ( \begin{matrix}1 \\ a_{12} & 1 \\ ⋮ & ... & ... \\ a_{1ℓ} & … & a_{ℓ−1,ℓ} & 1 \\ a_{1ℓ̄} & … & a_{ℓ−1,ℓ̄} & a′′_{ℓ} & 1 \\ ⋮ & ... & ... & a′_{ℓ−1,ℓ̄} & a′_{ℓ−1,ℓ} & ... \\ a_{1¯2} & a′′_{2} & ... & ⋮ & ⋮ & ... & 1 \\ a′′_{1} & a′_{1¯2} & … & a′_{1ℓ̄} & a′_{1ℓ} & … & a′_{12} & 1 \end{matrix} ) .

where

a′′_{i} = ∑_{i<j≤ℓ} a_{ij}a_{ij̄},  a′_{ij} = −a_{ij} − ∑_{i<k<j} a_{ik}a′_{kj},
a′_{ij̄} = −a_{ij̄} − ∑_{i<k<j} a_{ik}a′_{kj̄} − a′′_{j}a_{ij} − ∑_{k∈J′_{j}} a_{ik}a_{jk̄}.

Now φ(a)φ(b) = φ(c) where

c_{ij} = a_{ij} + b_{ij} + ∑_{i<k<j} b_{ik}a_{kj},
c_{ij̄} = a_{ij̄} + b_{ij̄} + ∑_{i<k<j} b_{ik}a_{kj̄} + a′′_{j}b_{ij} + ∑_{k∈J′_{j}} b_{ik}a′_{jk̄}.

And φ(a)^{−1} = φ(d) where

d_{ij} = −a_{ij} − ∑_{i<k<j} d_{ik}a_{kj},
d_{ij̄} = −a_{ij̄} − ∑_{i<k<j} d_{ik}a_{kj̄} − a′′_{j}d_{ij} − ∑_{k∈J′_{j}} d_{ik}a′_{jk̄}.

6. Analysis and reductive groups

We can now give precise asymptotic timings for operations in reductive groups and their full unipotent subgroups. We give our analysis in terms of the number of basic operations in the algebra 𝔼: addition, negation, multiplication, and testing equality. Once again let G be an 𝔽-split reductive algebraic group, with split maximal torus T, and Borel subgroup B containing T. Let U be the unipotent radical of B. Let W = N_{G}(T)/T be the Weyl group and let Φ be the root system. The reflection in W corresponding to the root α is denoted s_{α}. Let Φ^{+} be the positive roots with respect to B.

First we give an analysis for element operations in U(𝔼).

Theorem 6.1. Let 𝔽 be a field and let 𝔼 be a commutative unital 𝔽-algebra. Let U be the full unipotent subgroup of a split reductive linear algebraic group G over 𝔽. Let ℓ be the semisimple rank of G. Then there is a normal form for elements of U(𝔼). The word problem for elements in normal form requires O(ℓ^{2}) algebra operations, and multiplying or inverting them requires O(ℓ^{3}) algebra operations.

Proof. The normal form is a collected word, so the timing for the word problem follows from the fact that N = |Φ^{+}| is O(ℓ^{2}). We can assume that G is simple, since U is a direct sum of the full unipotent subgroups of the simple components of G.

If G is classical, the formulas of Section 5 require O(ℓ^{3}) field operations.

If G is exceptional, then ℓ is bounded. In this case we use symbolic collection. The Hall polynomials of the full unipotent subgroup of a split reductive group are independent of the algebra 𝔼, since split reductive groups can be constructed as ℤ-schemes. So the number of algebra operations required for inversion or multiplication is independent of the choice of 𝔼. □

In the rest of this section, we take 𝔼 to be an extension field of 𝔽 and we add inversion to the list of basic operations in 𝔼. We are primarily interested in computing in U(𝔼) because it allows us to compute in G(𝔼) with the algorithms of [CMT04, Section 5]. Recall that G(𝔼) has a Steinberg presentation with generators x_{α}(a), for α ∈ Φ and a ∈ 𝔼; n_{α}, for α ∈ Φ; and t ∈ T (𝔼). Note that the generator x_{r}(a) of Section 4 can be identified with the generator x_{α_{r}}(a) of the Steinberg presentation. Every element g ∈ G(𝔼) can be written uniquely in Bruhat form:

g = utẇu′,

for • u ∈ U(𝔼) stored as a collected word;

• t ∈ T (𝔼) stored as in [CMT04];

• ẇ = n_{α_{1}} ⋯ n_{α_{m}}, where s_{α_{1}} ⋯ s_{α_{m}} is a reduced expression for w ∈ W; and • u′ ∈ U_{w}(𝔼) as a collected word, where U_{w} is the subgroup of U generated

by the terms x_{α}(a), for α in Φ_{w} := {α ∈ Φ^{+} | αw^{−1} ∉ Φ^{+}}. Given two elements in Bruhat form, we need to find the Bruhat form of their product. The usual element operations in U(𝔼) are not sufficient for this purpose. There are two difficult steps, each of which requires a new operation in U. We now describe these operations and show how to carry them out with the methods of the previous sections.

6.1. Single-term separation. One difficult step is multiplying g = utẇu′ by n_{α} for some α ∈ Φ. This is achieved with Algorithm 3 of [CMT04], which uses the following operation: write u′ = ∏_{β∈Φ_{w}} x_{β}(a_{β}) in the form x_{α}(a_{α})v where v = ∏_{β∈Φ_{w}\{α}} x_{β}(b_{β}). We call this operation single-term separation.

This is easily done by collection: simply collect the term x_{α}(a_{α}) to the front of the product as in collection to the left, then put v in the required form with collection from the outside. No extra terms of the form x_{α}(b) can appear in v because only terms corresponding to roots higher than α are created. We can also do single term separation symbolically as in Section 3.

Alternatively, for classical groups, we can compute v as the product x_{α}(−a_{α})u′ using the formulas of Section 5. If α = α_{ij}, then the only possible nonzero constants in φ(a) are a_{ij}, a′_{ij}, and a′′_{i}. Hence at most O(ℓ) of the formulas for c_{ij} are nontrivial. Each such formula has at most a constant number of nonzero terms. We now have:

Proposition 6.2. Single-term separation in U(𝔼) requires O(ℓ) field operations.

Proof. Use formulas for classical components and symbolic collection for exceptional components. □

Note that, when both of the elements being multiplied are in Bruhat form, Algorithm 3 of [CMT04] only uses single-term separation for α simple. We have considered nonsimple roots as well, because they will be useful in the next subsection.

6.2. Weyl separation. The other difficult step for multiplication in G is computing the product of g ∈ G and v ∈ U. Write g in Bruhat form utẇu′. Then multiply u′ and v, and decompose the product into the form v′′v′ where

v′′ = ∏_{α∈Φ^{+}\Φ_{w}} x_{α}(b_{α}) and v′ = ∏_{α∈Φ_{w}} x_{α}(b_{α}).

We call this operation Weyl separation. We now get the Bruhat form

gv = [u(v′′)^{˙w^{−1}t^{−1}}]tẇv′

where (v′′)^{˙w^{−1}t^{−1}} is in U since α ∈ Φ^{+} \ Φ_{w} implies αw^{−1} is positive.

If we take the elements of Φ^{+} \ Φ_{w} in an order compatible with height, followed by the elements of Φ_{w} in an order compatible with height, we get a left-additive ordering on Φ^{+}. So the algorithms of Section 3 can also be used for separation. But note that (v′′)^{˙w^{−1}t^{−1}} will need to be collected again, since the image of the left additive ordering on Φ^{+} \ Φ_{w} under w^{−1} need not be left additive.

We can also use collection from the outside for Weyl separation. We need the following classification of additive orderings from [Pap94]:

Theorem 6.3. Let w be an element of the Weyl group W. Let s_{β_{1}} ⋯ s_{β_{m}} be a reduced expression for w. Then

β_{1}s_{β_{2}} ⋯ s_{β_{N}} , …, β_{N−2}s_{β_{N−1}}s_{β_{N}} , β_{N−1}s_{β_{N}} , β_{N}

is an additive ordering on Φ_{w}. All additive orderings on Φ_{w} arise from reduced expressions in this manner.

Now let w_{0} be the longest word in W and fix a reduced expression s_{α_{1}} ⋯ s_{α_{N}} for w_{0} (in practice, we use the lexicographically least reduced expression, but this is not necessary). We use the additive ordering on Φ^{+} corresponding to this reduced expression as the fixed order for collection. Now let w be a Weyl group element. If we restrict the fixed ordering to Φ_{w} we get an additive ordering, with corresponding reduced expression s_{β_{1}} … s_{β_{m}} = w. Similarly we restrict to get an ordering on Φ_{w_{0}w^{−1}} = (Φ^{+} \ Φ_{w})w^{−1} and a corresponding reduced expression s_{γ_{1}} … s_{γ_{N−m}} = w_{0}w^{−1}. Now w_{0} = s_{γ_{1}} … s_{γ_{N−m}}s_{β_{1}} … s_{β_{m}} is reduced. The corresponding ordering is: our fixed ordering restricted to Φ^{+} \ Φ_{w} and transformed by w, followed by our fixed ordering restricted to Φ_{w}. This is precisely the ordering we need for separation.

Finally we analyse Weyl separation:

Proposition 6.4. Weyl separation in U requires O(ℓ^{3}) field operations.

Proof. For classical components, we apply single-term separation for each root in Φ_{w}. By Proposition 6.2, this takes O(Nℓ) = O(ℓ^{3}) operations. For exceptional components use symbolic collection. □

In the exceptional case, this proposition assumes we have a system of symboliccollection polynomials for every Weyl element. Although this is polynomial time, the memory required to store all these polynomials is prohibitive. In practice, it is much faster to use collection from the outside for Weyl separation in exceptional groups.

6.3. Operations in reductive groups. We now prove the following result on computation in G:

Theorem 6.5. Let 𝔽 be a field and let 𝔼 be an extension of 𝔽. Let G be a split reductive linear algebraic group over the field 𝔽. Let ℓ be the semisimple rank of G and let n be the reductive rank. Then there is a normal form for elements of G(𝔼). The word problem for elements in normal form requires O(n + ℓ^{2}) field operations, and multiplying or inverting them requires O(nℓ^{2}) field operations.

Proof. We use the Bruhat decomposition to store g ∈ G in the normal form g = uhẇu′. Here u, u′, and ẇ are words of length at most N, while h has length n. Once again the timing for the word problem is clear. Now G is a central product of simple algebraic groups and a central torus of dimension at most n. Multiplying a toral element by an element in a simple component is done as in Subsection 5.5 of [CMT04], and takes time O(nℓ^{2}). So it suffices to show that multiplication and inversion in a simple group G requires O(ℓ^{3}) operations. The algorithms for multiplication and inversion given in [CMT04] require a constant number of multiplications or inversions in U(𝔼), together with a constant number of Weyl separations and at most O(ℓ^{2}) single-term separations. The theorem now follows from Theorem 6.1, Proposition 6.2, and Proposition 6.4. □

Theorem 1.1 is an immediate consequence of this result and the fact that ℓ ≤ n.

7. Implementation and timings

A number of heuristic improvements are built into our implementations of the algorithms described. Most of them are either obvious or were suggested by our profiling of the code. We restrict ourselves here to a brief description of the basic data types used. Representations of elements of the field 𝔽 or algebra 𝔼 are taken care of by the Magma computer algebra system [BCP97]. Most of our code is written in traditional C [KR88] and incorporated into the Magma core. Less timecritical code is written in the Magma language itself.

A collected product ∏_{r=1}^{N} x_{r}(a_{r}) is stored as a sequence [a_{1}, …, a_{N}]. While doing the collection, we represent a term x_{r}(a) as a pair (r, a) of an integer and an element of 𝔼. Note that pairs (r, 0) are trivial – they are always eliminated as soon as they occur. A word ∏_{i=1}^{M} x_{r_{i}}(a_{i})^{ε_{i}} is represented as a doubly linked chain. That is, every root element in the chain contains a reference to its predecessor and successor, which is a null-reference if the element is the first (resp. last) in the chain:

← ∘ ⇆ ∘ ⇆ ⋯ ⇆ ∘ →

We use this data structure because inserting and deleting terms in the word when applying relations (3)–(5) can be done in constant time. For sequences, insertion and deletion would be more expensive, since the tail of the sequence has to be copied in memory. The chain is doubly linked, since we need both the predecessor and the successor of a term in the word for the CollectSubword functions.

In our tables we use the following abbreviations for collection algorithms:

CTL: Collection to the left, Section 3.
CFL: Collection from the left, Section 3.
CFO: Collection from the outside, Section 4.
SCFL: Symbolic collection from the left, Section 3.
SCFO: Symbolic collection from the outside, Section 4.

We have two different implementations of the method of Section 5:

D: Modified matrix multiplication. For given a, b, we use formulas of Section 5 to compute φ(a) and the significant part of φ(b) (we do not use b′_{ij} and, except in types B (even characteristic) and C, we do not use b′′_{i}). Then the product of the two matrices is computed using algorithms implemented in the Magma computer algebra system [BCP97]. The resulting matrix agrees with φ(c) in the entries c_{ij} and in the entries c′′_{i} (where they are needed). Thus we can recover the product c = ab from the resulting matrix by formulas of Section 5.

SD: Compute the polynomials of (8) in Section 3, using the formulas instead of collection.

Method D outperforms SD in most cases, since asymptotically fast algorithms are used for matrix multiplication. But SD is faster for fields with very rapid blow-up of terms, such as multivariate rational function fields. All timings were run on an AMD Opteron 150 Processor with 2393 MHz.

Table 1 gives times and memory consumption for creating the reductive groups and precomputing all constants. For symbolic algorithms, this also includes time taken to compute the polynomials. Note that all constants and polynomials are independent of the field, and are computed on a per-root-datum basis. This means that preprocessing time is nearly zero if a group with the same root datum has already been created in the same Magma session. We used a workspace of 4 gigabytes – when this is insufficient we do not give a time and write > 4GB in the memory column. In columns D and SD, the constants are computed as they are needed and not stored in memory.

Table 2 gives average times for multiplying and inverting random elements of full unipotent groups over the field with 17 elements. The average is taken over 100 multiplications. The same random elements are used for different algorithms. If a single multiplication required more than 2 gigabytes of memory, we write > 2GB instead of a time. We did not attempt those cases where the preprocessing took more than 4 gigabytes of memory.

Table 3 gives similar times for multiplying and inverting random elements of the reductive group itself. Each such operation involves a number of collections. Computing random elements in a reductive group can be time consuming, but this is not included in our timings.

Table 4 gives average times for multiplying and inverting random elements of full unipotent groups of reductive groups over different fields. Over the field of rational numbers, the random field elements are chosen by taking a random numerator and a random denominator of size up to the given number of bits and a random sign.

18 ARJEH M. COHEN, SERGEI HALLER, AND SCOTT H. MURRAY

Time  Memory (MB)
CTL  CFL  CFO  SCFL  SCFO  D  SD  CTL  CFL  CFO  SCFL  SCFO  D  SD
A_{10}(17)  0.790  0.790  0.780  0.780  0.820 0.180 0.200  4.469  4.469  4.469  4.674  4.659 3.726  3.800
A_{20}(17)  8.950  8.870  8.990  9.000  9.310 0.180 0.190  12.853 12.853 12.853 15.488 13.821 3.708  4.227
A_{30}(17)  44.110 44.330 44.150 46.670 45.580 0.200 0.240  53.915 53.915 53.915 79.217 58.180 3.781  5.416
A_{100}(17)  –  –  –  –  – 0.640 2.250 > 4GB > 4GB > 4GB > 4GB > 4GB 8.139 52.477
B_{10}(17)  4.490  4.320  4.480  4.390  4.580 0.180 0.180  4.731  4.731  4.731  6.219  6.377 3.693  3.992
B_{20}(17)  68.700 68.870 68.570 72.270 69.750 0.190 0.250  39.072 39.072 39.072 83.714 45.900 3.710  7.951
B_{30}(17)  357.170 357.060 355.760 437.320 365.790 0.200 0.430 177.452 177.452 177.452 613.679 426.778 3.790 14.250
B_{100}(17)  –  –  –  –  – 0.620 14.380 > 4GB > 4GB > 4GB > 4GB > 4GB 8.160 445.203
C_{10}(17)  4.460  4.400  4.560  4.380  4.530 0.180 0.200  4.730  4.730  4.730  6.218  5.549 3.693  3.992
C_{20}(17)  68.730 68.680 68.800 72.720 69.870 0.190 0.250  39.078 39.078 39.078 83.721 65.053 3.710  7.951
C_{30}(17)  354.660 357.230 354.970 436.860 363.670 0.190 0.440 177.449 177.449 177.449 613.676 285.094 3.790 14.250
C_{100}(17)  –  –  –  –  – 0.620 16.490 > 4GB > 4GB > 4GB > 4GB > 4GB 8.160 445.205
D_{10}(17)  1.820  1.820  1.710  1.820  1.870 0.190 0.160  4.344  4.344  4.344  5.198  4.895 3.692  3.986
D_{20}(17)  28.540 28.400 28.400 31.640 29.910 0.190 0.270  34.589 34.589 34.589 79.227 54.305 3.708  7.911
D_{30}(17) 153.440 153.080 152.900 220.920 159.850 0.200 0.400 167.857 167.857 167.857 604.077 249.470 3.785 14.242
D_{100}(17)  –  –  –  –  – 0.640 14.180 > 4GB > 4GB > 4GB > 4GB > 4GB 8.158 445.176
G_{2}(17)  0.210  0.190  0.190  0.190  0.200  –  –  3.580  3.580  3.580  3.580  3.580  –  –
F_{4}(17)  0.410  0.440  0.400  0.400  0.430  –  –  3.764  3.764  3.764  3.859  3.764  –  –
E_{6}(17)  0.440  0.450  0.430  0.440  0.460  –  –  4.532  4.532  4.532  4.532  4.532  –  –
E_{7}(17)  0.990  1.000  0.980  1.010  0.980  –  –  4.726  4.726  4.726  4.305  3.870  –  –
E_{8}(17)  3.130  3.110  3.100  3.180  3.230  –  –  6.088  6.088  6.088 14.175  7.376  –  –

Table 1. Time and memory consumption for preprocessing

COMPUTING IN UNIPOTENT GROUPS 19

Group  Multiply  Invert
CTL  CFL CFO  SCFL SCFO  D  SD  CTL  CFL CFO  SCFL SCFO  D  SD
A_{10}(17)  0.009 0.006 0.006  0.007 0.006 0.006  0.006  0.003 0.002 0.002  0.003 0.002 0.001  0.002
A_{20}(17)  1.511 0.058 0.030  0.174 0.031 0.020  0.032  1.051 0.042 0.012  0.157 0.019 0.003  0.017
A_{30}(17) 114.543 0.768 0.111  3.069 0.334 0.046  0.182  84.299 0.734 0.063  3.052 0.326 0.007  0.148
A_{100}(17)  –  –  –  –  – 0.854  51.744  –  –  –  –  – 0.071  52.425
B_{10}(17)  0.101 0.016 0.013  0.045 0.038 0.012  0.014  0.069 0.009 0.005  0.039 0.032 0.004  0.007
B_{20}(17)  280.288 1.144 0.180  5.134 0.614 0.050  0.321 209.010 1.105 0.136  5.474 0.622 0.017  0.305
B_{30}(17)  > 2GB 25.472 1.412 107.734 49.190 0.122  2.015 > 2GB 25.419 1.240 115.646 49.338 0.045  2.024
B_{100}(17)  –  –  –  –  – 2.728 1025.957  –  –  –  –  – 1.115 1048.822
C_{10}(17)  0.093 0.016 0.013  0.044 0.016 0.013  0.014  0.065 0.009 0.005  0.038 0.009 0.004  0.007
C_{20}(17)  266.161 1.133 0.178  4.999 2.306 0.050  0.319 194.365 1.106 0.119  5.411 2.316 0.017  0.300
C_{30}(17)  > 2GB 27.562 1.443 113.089 21.446 0.125  2.099 > 2GB 27.656 1.097 123.097 21.609 0.047  2.098
C_{100}(17)  –  –  –  –  – 2.760 1046.944  –  –  –  –  – 1.161 1054.659
D_{10}(17)  0.062 0.014 0.011  0.020 0.012 0.011  0.012  0.040 0.007 0.004  0.014 0.006 0.004  0.006
D_{20}(17) 195.012 0.887 0.144  4.470 1.621 0.046  0.293 141.648 0.874 0.096  4.713 1.619 0.016  0.275
D_{30}(17)  > 2GB 22.057 1.181 102.313 15.470 0.121  1.963 > 2GB 22.229 0.931 108.976 15.613 0.045  1.969
D_{100}(17)  –  –  –  –  – 2.631 1038.942  –  –  –  –  – 1.093 1044.249
G_{2}(17)  0.001 0.001 0.001  0.001 0.001  –  –  0.000 0.000 0.000  0.000 0.000  –  –
F_{4}(17)  0.004 0.003 0.003  0.003 0.003  –  –  0.001 0.001 0.001  0.001 0.001  –  –
E_{6}(17)  0.006 0.004 0.004  0.005 0.004  –  –  0.002 0.001 0.001  0.002 0.001  –  –
E_{7}(17)  0.042 0.009 0.007  0.014 0.008  –  –  0.029 0.004 0.002  0.009 0.004  –  –
E_{8}(17)  4.924 0.053 0.016  0.309 0.032  –  –  3.966 0.044 0.008  0.292 0.027  –  –

Table 2. Average time to multiply random elements of the full unipotent group

20 ARJEH M. COHEN, SERGEI HALLER, AND SCOTT H. MURRAY

Group  Multiply  Invert
CTL  CFL  CFO  SCFL  SCFO  D  SD  CTL  CFL  CFO  SCFL  SCFO  D  SD
A_{10}(17)  0.123  0.119 0.118  0.121  0.117  0.288  0.295  0.163 0.160 0.162  0.163  0.160  0.222  0.220
A_{20}(17)  1.359  0.729 0.662  1.293  0.695  2.063  2.129  2.268 1.147 1.080  1.546  1.112  1.982  2.031
A_{30}(17) 120.524 10.798 7.887 21.833  8.936 29.141 29.752 104.102 13.639 12.655 21.838 13.484 21.959 22.627
A_{100}(17)  –  –  –  –  –  –  –  –  –  –
B_{10}(17)  0.423  0.325 0.304  0.453  0.414  1.353  1.359  0.561 0.495 0.486  0.592  0.570  0.860  0.867
B_{20}(17)  342.015  9.964 5.184 28.542  7.234 27.707 29.383 237.331 10.345 8.721 24.834 10.331 18.471 19.728
B_{30}(17)  > 2GB 170.359 34.042 560.664 228.163 190.445 198.912 > 2GB 92.252 51.170 397.654 197.548 140.195 146.980
B_{100}(17)  –  –  –  –  –  –  –  –  –  –
C_{10}(17)  0.430  0.329 0.314  0.455  0.334  1.420  1.426  0.556 0.488 0.483  0.588  0.502  0.893  0.905
C_{20}(17)  347.298 10.341 5.380 28.422 14.166 27.950 29.116 225.542 10.033 8.517 24.409 15.189 18.399 19.387
C_{30}(17)  > 2GB 174.191 33.764 580.168 116.204 181.660 190.782 > 2GB 99.784 54.166 414.583 115.765 138.295 145.607
C_{100}(17)  –  –  –  –  –  –  –  –  –  –
D_{10}(17)  0.344  0.280 0.268  0.317  0.278  1.170  1.184  0.454 0.412 0.409  0.441  0.416  0.727  0.734
D_{20}(17) 225.229  8.183 4.606 24.562 10.825 23.712 24.692 166.790 8.538 7.340 21.308 12.015 15.674 16.571
D_{30}(17)  > 2GB 147.254 31.131 521.051 90.824 174.995 185.490 > 2GB 82.122 47.233 373.211 94.738 135.237 142.438
D_{100}(17)  –  –  –  –  –  –  –  –  –  –
G_{2}(17)  0.008  0.008 0.006  0.008  0.008  –  –  0.006 0.006 0.006  0.006  0.006  –  –
F_{4}(17)  0.080  0.076 0.075  0.077  0.074  –  –  0.060 0.060 0.059  0.059  0.060  –  –
E_{6}(17)  0.172  0.166 0.158  0.165  0.158  –  –  0.128 0.129 0.124  0.127  0.126  –  –
E_{7}(17)  0.774  0.508 0.451  0.518  0.455  –  –  0.419 0.369 0.363  0.381  0.366  –  –
E_{8}(17)  52.481  3.098 1.566  3.815  1.624  –  –  8.781 1.396 1.288  1.974  1.353  –  –

Table 3. Average time to multiply random elements of the reductive group

Group  Multiply  Invert
CFO SCFO  D  SD  CFO SCFO  D  SD
A_{20}(2)  0.021 0.030  0.020 0.031  0.005  0.017  0.003  0.015
A_{20}(17)  0.029 0.031  0.020 0.032  0.012  0.018  0.003  0.017
A_{20}(ℚ), 32 bits 0.045 0.038  0.024 0.038  0.051  0.109  0.213  0.135
A_{20}(ℚ), 64 bits 0.049 0.041  0.028 0.041  0.086  0.195  0.736  0.265
A_{20}(ℚ), 128 bits 0.056 0.047  0.039 0.047  0.177  0.394  2.877  0.611
A_{20}(ℚ(i)), 32 bits 0.074 0.052  0.047 0.049  0.080  0.143  0.048  0.117
A_{20}(ℚ(p)), 32 bits 0.108 0.069  0.062 0.062  0.122  0.265  0.068  0.214
A_{20}(R)  0.049 0.038  0.025 0.038  6.868  2.562  0.594  1.609
B_{20}(2)  0.056 0.589  0.047 0.303  0.023  0.590  0.015  0.282
B_{20}(17)  0.174 0.592  0.049 0.309  0.125  0.596  0.017  0.289
B_{20}(ℚ), 32 bits 0.420 0.811  0.254 1.901  0.986  2.630  2.625  5.169
B_{20}(ℚ), 64 bits 0.534 0.960  0.630 3.594  2.205  5.111 11.937 12.567
B_{20}(ℚ), 128 bits 0.798 1.269  1.865 8.058  5.575 11.475 50.818 34.318
B_{20}(ℚ(i)), 32 bits 0.680 0.972  1.078 2.124  1.270  2.654  1.344  3.874
B_{20}(ℚ(p)), 32 bits 1.092 1.362  1.410 3.864  2.276  4.542  2.053  7.212
B_{20}(R)  0.589 0.777 > 2GB 31.884 > 2GB > 2GB > 2GB > 2GB
E_{8}(2)  0.012 0.028  –  –  0.003  0.022  –  –
E_{8}(17)  0.016 0.029  –  –  0.007  0.023  –  –
E_{8}(ℚ),  32 bits 0.047 0.125  –  –  0.061  0.283  –  –
E_{8}(ℚ),  64 bits 0.075 0.206  –  –  0.118  0.526  –  –
E_{8}(ℚ), 128 bits 0.141 0.390  –  –  0.262  1.099  –  –
E_{8}(ℚ(i)), 32 bits 0.077 0.162  –  –  0.094  0.310  –  –
E_{8}(ℚ(p)), 32 bits 0.113 0.291  –  –  0.146  0.621  –  –
E_{8}(R)  0.315 0.349  –  –  0.904  1.166  –  –

Table 4. Operations for random elements of the full unipotent group over different fields

CFL  CFO
max  avg  max  lim avg
A_{ℓ}  ℓ  (ℓ + 2)/3  2  2
B_{ℓ}  2ℓ − 1  (2ℓ + \frac{3}{2} − \frac{1}{2ℓ})/3  4  4
C_{ℓ}  2ℓ − 1  (2ℓ + \frac{3}{2} − \frac{1}{2ℓ})/3  3  3
D_{ℓ}  2ℓ − 3  (2ℓ − 1)/3  3  3

Table 5. Total degrees of Hall polynomials

Similar random elements were used for the Gaussian integers ℚ(i) and for ℚ(p), which is the splitting field of a random irreducible polynomial of degree 6 with integral coefficients in the range 1 to 10. The field R is the multivariate rational function field over ℚ with 10 variables. Random field elements over R were taken to be random invariates. In B_{20}(R) the coefficient blowup is so large that over 2 gigabytes of memory was needed in some cases (see entries in the table).

Finally, in Table 5, we compare the total degrees of the polynomials used for different kinds of symbolic collection. The last column contains lim_{ℓ→∞} avg{deg(p) : p ∈ P}, where P is the set of polynomials used for symbolic collection. This goes a long way towards explaining why collection from the outside works so well. Since the polynomials are multivariate in 2N = 2|Φ^{+}| variables, we still can have large polynomials. To have a very rough idea of the size, we printed the largest of the polynomials in type B_{15} as a string and measured its size in bytes. Using collection from the outside, the size is 9226 bytes; using collection from the left, the size is about 297 megabytes.

References

[BCP97] Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265, Computational algebra and number theory (London, 1993). MR MR1484478

[Car72] Roger W. Carter, Simple groups of Lie type, John Wiley & Sons, London-New York-Sydney, 1972, Pure and Applied Mathematics, Vol. 28.

[CMT04] Arjeh M. Cohen, Scott H. Murray, and D. E. Taylor, Computing in groups of Lie type, Math. Comp. 73 (2004), 1477–1498.

[DG70] Michel Demazure and Pierre Gabriel, Groupes algébriques. Tome I: Géométrie algébrique, généralités, groupes commutatifs, Masson & Cie, Éditeur, Paris, 1970, Avec un appendice Corps de classes local par Michiel Hazewinkel.

[Hal69] Philip Hall, The Edmonton notes on nilpotent groups, Queen Mary College Mathematics Notes, Mathematics Department, Queen Mary College, London, 1969. MR MR0283083 (44 #316)

[HEO05] Derek F. Holt, Bettina Eick, and Eamonn A. O’Brien, Handbook of computational group theory, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2005. MR MR2129747

[HJ76] Marshall Hall Jr., The theory of groups, Chelsea Publishing Co., New York, 1976, Reprinting of the 1968 edition.

[Hum78] James E. Humphreys, Introduction to Lie algebras and representation theory, Springer-Verlag, New York, 1978, Second printing, revised. MR 81b:17007

[KR88] Brian W. Kernighan and Dennis M. Ritchie, The C programming language, 2nd ed., Prentice-Hall Internat. Ser. Comput. Sci., Englewood Cliffs, NJ, 1988.

[LG01] Charles R. Leedham-Green, The computational matrix group project, Groups and computation, III (Columbus, OH, 1999), Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001, pp. 229–247. MR 2002d:20084

[LGS90] C. R. Leedham-Green and L. H. Soicher, Collection from the left and other strategies, J. Symbolic Comput. 9 (1990), no. 5-6, 665–675, Computational group theory, Part 1. MR 92b:20021

[LGS98] C. R. Leedham-Green and Leonard H. Soicher, Symbolic collection using Deep Thought, LMS J. Comput. Math. 1 (1998), 9–24 (electronic). MR 99f:20002

[Mer97] Wolfgang Wilhelm Merkwitz, Symbolische multiplikation in nilpotenten gruppen mit deep thought, Master’s thesis, Rheinisch-Westfälische Technische Hochschule Aachen, 1997.

[Pap94] Paolo Papi, A characterization of a special ordering in a root system, Proc. Amer. Math. Soc. 120 (1994), no. 3, 661–665. MR 94e:20056

[Ros57] Maxwell Rosenlicht, Some rationality questions on algebraic groups, Ann. Mat. Pura Appl. (4) 43 (1957), 25–50. MR MR0090101 (19,767h)

[Ser88] Jean-Pierre Serre, Algebraic groups and class fields, Graduate Texts in Mathematics, vol. 117, Springer-Verlag, New York, 1988, Translated from the French. MR MR918564 (88i:14041)

[Spr98] T. A. Springer, Linear algebraic groups, second ed., Birkhäuser Boston Inc., Boston, MA, 1998.

[Ste68] R. Steinberg, Lectures on Chevalley groups, Tech. report, Yale University, 1968.

[VL90] M. R. Vaughan-Lee, Collection from the left, J. Symbolic Comput. 9 (1990), no. 5-6, 725–733, Computational group theory, Part 1. MR 92c:20065

[Wat79] William C. Waterhouse, Introduction to affine group schemes, Graduate Texts in Mathematics, vol. 66, Springer-Verlag, New York, 1979. MR 82e:14003

Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, Netherlands

E-mail address: A.M.Cohen@tue.nl

School of Mathematics and Statistics F07, Faculty of Science, University of Sydney, NSW 2006, Australia

E-mail address: sergei@sergei-haller.de, murray@maths.usyd.edu.au