ALGORITHM FOR LANG’S THEOREM

ARJEH M. COHEN AND SCOTT H. MURRAY

Abstract. We give an efficient algorithm for Lang’s Theorem in split connected reductive groups defined over finite fields of characteristic greater than 3. This algorithm can be used to construct many important structures in finite groups of Lie type. We use an algorithm for computing a Chevalley basis for a split reductive Lie algebra, which is of independent interest.

1. Introduction

A finite group of Lie type can be described as the rational points of a connected reductive algebraic group over a finite field. Given a structure in the algebraic group, such as a conjugacy class or a maximal torus, we want to find the corresponding structures in the finite group of Lie type. This can often be achieved with Lang’s Theorem. We provide a computationally efficient algorithm for Lang’s Theorem in split connected reductive groups. Our algorithm is randomised but guaranteed to return a correct answer, ie, it is Las Vegas in the sense of [Bab97]. Glasby and Howlett [GH97] have already solved this problem in a special case; our algorithm is inspired by their work and the proof of Lang’s Theorem given in [Mül03].

Throughout this paper k is a finite field of size q and characteristic p, and k_{r} is the unique degree r extension of k in the algebraic closure k̄. The affine space of dimension N can be identified with k̄^{N}. An affine variety X is a subset of k̄^{N} that consists of the zeroes of a collection of polynomials. The variety is defined over k if it is closed under the action of the map F : k̄^{N} → k̄^{N} that takes the qth power of each component. The restriction of F to X is called the (standard) Frobenius endomorphism of X. The set of rational points of X over k_{r}, denoted by X(k_{r}), consists of those elements of X fixed by F^{r}. A nonstandard Frobenius endomorphism is a morphism F′ : X → X such that (F′)^{s} = F^{s} for some positive integer s. The elements of X fixed by F′ are the rational points of a k-form of X. In this paper, Frobenius endomorphisms are standard unless otherwise stated.

A linear algebraic group is an affine variety with group multiplication and inversion given by rational functions. See, for example, [Spr98] for more details including the definitions of reductive and connected groups. Every linear algebraic group contains a maximal connected subgroup G^{∘}, the component of the identity. This subgroup is normal and G/G^{∘} is finite, so for many purposes it suffices to study connected groups. An important result on linear algebraic groups over finite fields is:

Date: June 3, 2005.

The authors would like to thank Sergei Haller, Anthony Henderson, William M. Kantor, Gus Lehrer, T. A. Springer, and D. E. Taylor for useful discussions on this topic. The authors also thank the Magma project at the University of Sydney, where some of the work was carried out.

Theorem 1.1 (Lang’s Theorem). If G is a connected linear algebraic group defined over the finite field k with Frobenius map F, then the map

G → G, a ↦ a^{−F} a

is onto.

This is equivalent to the statement that the first Galois cohomology of G is trivial.

In this paper, we give an algorithm for Lang’s Theorem in k-split connected reductive groups described by the Steinberg presentation as in [CMT04]. In particular, the root datum, and hence the Cartan type, of G is known. Reductive groups are likely to be the critical case, since the problem for an arbitrary connected linear algebraic group could be solved by working down a composition series (see Section 3) and all simple connected groups are reductive. Our main result is:

Theorem 1.2. Let k be a finite field of characteristic greater than 3. Let G be a k-split connected reductive linear algebraic group. Let c be in G(k_{r}), and suppose we are given s, the order of c^{F^{r−1}} ⋯ c^{F} c. Then we can find a ∈ G(k_{rs}) such that c = a^{−F} a in Las Vegas time O(n^{9}r^{2}s^{2} log^{2}(n) log^{2}(q)) where n is the reductive rank of G.

We can improve significantly on this result for the classical groups:

Theorem 1.3. Let G be a k-split simple connected classical group defined over k. Let c be in G(k_{r}) and suppose we are given s, the order of c^{F^{r−1}} ⋯ c^{F} c. Then we can find a ∈ G(k_{rs}) such that c = a^{−F} a in Las Vegas time O(n^{5}r^{2}s^{2} log^{2}(q)) where n is the reductive rank of G.

The parameter s measures the size of the field extension required, as explained in Section 2. In Section 3, we use the concept of F -eigenvectors to reduce to a problem involving forms of G-modules. A solution to this problem and a proof of Theorem 1.3 is given in Section 4. This solution uses the algorithm for computing a standard Chevalley basis in the Lie algebra of G described in Section 5. The running time of this algorithm is analysed in Section 6, leading to a proof of Theorem 1.2.

2. Minimum field degree

Computation in large finite fields is a challenging problem (see, for example, [LN97]). So we start with an easy result giving the size of the field extension needed for Lang’s Theorem. We define the minimum field degree of g ∈ G as the smallest r such that g^{F^{r}} = g. Note that g has minimum field degree r if, and only if, k_{r} is the smallest extension of k such that g is in G(k_{r}).

Proposition 2.1. Let G be a connected linear algebraic group defined over k. Let c be an element of G with minimum field degree r and let s be the order of c^{F^{r−1}} ⋯ c^{F} c. If c = a^{−F} a for some a in G, then the minimum field degree of a is rs.

Proof. Let m be the minimum field degree of a. Clearly k_{r} is a subfield of k_{m}, so r is a divisor of m, say ru = m. Since c^{F^{r}} = c, we have

(c^{F^{r−1}} ⋯ c^{F} c)^{u} = c^{F^{m−1}} ⋯ c^{F} c = a^{−F^{m}}a^{F^{m−1}} ⋯ a^{−F^{2}}a^{F} a^{−F} a = a^{−F^{m}}a.

Hence a^{F^{m}} = a if, and only if, u is a multiple of s. □

The most important consequence of this proposition is that the minimum field degree is independent of the particular choice of a and can be computed beforehand. In all our timings we consider s, the order of c^{F^{r−1}} ⋯ c^{F} c, to be an input of our algorithm. While it is straightforward to compute s, no polynomial time algorithm is known. The best known method for computing s is to convert from the Steinberg presentation of G to a faithful representation [CMT04] and then compute the order of the corresponding matrix using the algorithm of [CLG97]. If the representation has degree d, this takes Las Vegas time O(d^{3} log(q) log log(q^{d})) plus the time required to factor a collection of integers of the form q^{d_{i}} − 1 with ∑_{i} d_{i} ≤ d.

Suppose now that G is a k-split reductive group with reductive rank n and semisimple rank ℓ. The element c, which is the input to our algorithm, has size O((n + ℓ^{2})r log(q)); while the element a, which is the output, has size O((n + ℓ^{2})rs log(q)). Since s need not be bounded by a polynomial in n, ℓ, r, and log(q), there is no algorithm for Lang’s Theorem that is polynomial in the size of the input. The best we can hope for is an algorithm which is polynomial in the size of the output.

3. Twisted eigenvectors

We can now give an outline of our main algorithm. Let G = G\binom{}{k̄} be a connected linear algebraic group defined over k. Suppose that V is a G-module of dimension d defined over k, so that F acts on V = k̄^{d} by taking the qth power of each component. We say that v ∈ V is an F -eigenvector of c if v^{F} c = v (note that the “F -eigenvalue” is always one). The set E(k) of all F -eigenvectors in V is a k-space of dimension d. By Lang’s theorem, the k_{rs}-span of E(k) must be equal to V (k_{rs}). There is a variety E defined over k such that E(k_{t}) is the k_{t}-span of E(k) for every positive integer t. Such a variety is called a k-form of V [Spr98, Section 11.1].

The following easy lemma is the key to our recursive approach.

Lemma 3.1. Let G be a connected linear algebraic group defined over k and let V be a G-module defined over k with kernel K ≤ G. Let c be an element of G. Suppose that E(k) is the set of F -eigenvectors of c in V. Then a ∈ G satisfies c ∈ a^{−F} Ka if, and only if, V (k)a = E(k).

Proof. If a^{−F} za = c for z ∈ K, then, for all v ∈ V (k), va = vza = va^{F} c = (va)^{F} c and so va ∈ E(k). Conversely, if V (k)a = E(k), then, for all v ∈ V (k), va = (va)^{F} c = va^{F} c and so a^{F} ca^{−1} ∈ K. □

We call an element a ∈ G(k_{rs}) such that V (k)a = E(k) a transformer in G for the k-form E. Our approach to solving Lang’s Theorem is outlined in Algorithm 1. Note that s is taken to be the order of c^{F^{r−1}} ⋯ c^{F} c in the top-level function call. It is not necessary to recompute s for the recursive calls since a multiple of the element order works just as well.

Suppose that G is split reductive and let T_{0} be a k-split maximal torus of G. Using the methods of [CMT04], we can construct a module V which is projectively faithful, that is, the kernel K is contained in the centre of G. We can now take H = T_{0} in Algorithm 1, since Z(G) is contained in every maximal torus of G. Since a split torus has an easily constructed faithful module, there is at most one recursive call for reductive groups. The same algorithm could, in principle, be used for a nonreductive connected group G: construct a simple quotient G/N, take V to be the G-module induced by a projectively faithful module for G/N, and take H to Lang := function(G, c, s) [c ∈ G(k_{r}), s a multiple of the order of c^{F^{r−1}} ⋯ c^{F} c]

construct a module V for G

let E(k) = F -Eigenspace(c, V, s)

find a transformer a ∈ G(k_{rs}) for E

if V is faithful then

return a else

construct a proper connected subgroup H of G containing the kernel of V let b = Lang(H, a^{F} ca^{−1}, s) return ba

end if end function

algorithm 1. Algorithm outline for Lang’s Theorem

F -eigenspace := function(c, V, s) [c ∈ G(k_{r}), s the order of c^{F^{r−1}} ⋯ c^{F} c] let S be the k-matrix of F acting of k_{rs} let C be the k-matrix of c acting on V (k_{rs}) = k_{rs}^{d} return the fixed point space of S^{⊕d}C

end function

algorithm 2. Deterministic method for computing F -eigenvalues

F -eigenspace := function(c, V, s) [c ∈ G(k_{r}), s the order of c^{F^{r−1}} ⋯ c^{F} c]

repeat let x be a random d × d matrix over k_{rs} let a = x + x^{F} c + x^{F^{2}}c^{F} c + ⋯ + x^{F^{rs−1}}c^{F^{rs−2}} ⋯ c^{F} c

until a is invertible

return V (k)a^{−1} end function

algorithm 3. Las Vegas method for computing F -eigenvalues

be the preimage in G of the maximal torus in G/N. However, finding the normal subgroup N and constructing the quotient G/N are nontrivial problems which lie beyond the scope of this paper.

Algorithms for finding transformers are discussed in the next section. We now give two algorithms for computing the F -eigenspace. The most straightforward method is given in Algorithm 2. The key is to consider k_{rs} as a k-space of dimension rs and to consider V (k_{rs}) = k_{rs}^{d} as a k-space of dimension drs. The solution is then found by linear algebra over k. Computing S takes time O(r^{2}s^{2} log^{2}(q)), where the second factor of log(q) is for computing qth powers. Finding C and the fixed space takes time O(d^{3}r^{3}s^{3} log(q)). So the overall time is O(d^{3}r^{3}s^{3} log^{2}(q)).

An alternative method, due to Glasby and Howlett [GH97], is given in Algorithm 3. It takes time O(d^{2}r^{2}s^{2} log^{2}(q)) to apply F to a d × d matrix over k_{rs}, so computing a takes time O(d^{3}r^{2}s^{2} log^{2}(q)). Each randomly chosen x has a probability of at least 1/4 of yielding an invertible element a. Since this probability is bounded away from zero as q, r, s, and d become large, the algorithm is Las Vegas. Note that we have an algorithm for Lang’s theorem in GL(V) if the function returns a instead of V (k)a^{−1}.

We now have:

Theorem 3.2. Let G be a connected linear algebraic group defined over k and let V be a G-module defined over k with dimension d. Let c be an element of G with minimum field degree r and let s be the order of c^{F^{r−1}} ⋯ c^{F} c. Then we can compute a basis for the k-space E(k) of F -eigenvectors of c in deterministic time O(d^{3}r^{3}s^{3} log^{2}(q)) or Las Vegas time O(d^{3}r^{2}s^{2} log^{2}(q)).

4. Finding transformers

Let G be a k-split connected reductive linear algebraic group defined over k, let c be in G(k_{r}), and let s be the order of c^{F^{r−1}} ⋯ c^{F} c. Let T_{0} be the standard k-split maximal torus of G determined by the Steinberg presentation. Let V be a projectively faithful G-module and compute E, the k-form of F -eigenvectors of c. In this section, we show how to find a transformer a ∈ G(k_{rs}) such that E(k)a = V (k). First we consider two special cases: split tori and classical groups. Then we give an algorithm for an arbitrary k-split connected reductive group. The key is to consider k-bases with some additional structure that ensures that G is transitive on all such bases (or G_{ad} is transitive in Subsection 4.3).

4.1. Split tori and isogeny. A k-split torus T of dimension n is just the direct product of n copies of k̄^{×} with the Frobenius endomorphism taking the qth power of each component. The standard module V is just k̄^{n} with the componentwise action. Suppose c = (c_{1}, …, c_{n}) ∈ T (k_{r}) and E is the variety of F -eigenvectors of c in V. Splitting T into n copies of k̄^{×} and using Theorem 3.2, we can compute E in Las Vegas time O(nr^{2}s^{2} log^{2}(q)). Now E has a basis of the form a_{1}e_{1}, …, a_{n}e_{n} where each a_{i} ∈ k_{rs}^{×} and e_{i} is the ith standard basis vector in V. Now (a_{1}, …, a_{n}) ∈ T (k_{rs}) is a transformer for E. Hence we have proved:

Proposition 4.1. Let T be a k-split torus of dimension n. Let c be in T (k_{r}), and suppose we are given s, the order of c^{F^{r−1}} ⋯ c^{F} c. Then we can find an element a in T (k_{rs}) such that c = a^{−F} a in Las Vegas time O(nr^{2}s^{2} log^{2}(q)).

Consider two connected linear algebraic groups G and H defined over k. Let ι be a homomorphism G → H defined over k which is onto with finite kernel K. Such a map is called an isogeny. Now suppose G and H are reductive and described by a Steinberg presentation with unipotent, Weyl, and toral generators as in [CMT04]. If there is an isogeny ι : G → H, then both groups have the same Cartan type. Furthermore, we can assume (after composing with an automorphism) that ι leaves unipotent and Weyl generators unchanged, and acts by a change of basis on the toral generators. We denote the standard tori generated by the toral generators of G (resp. H) by T_{0} (resp. U_{0}). Note that K ≤ Z(G) ≤ T_{0}. An important invariant of ι is the exponent of the finite group K, which we denote by m.

For g ∈ T_{0}(k_{r}), we have ι(g)^{F^{r}} = ι(g^{F^{r}}) = ι(g), so ι(g) ∈ U_{0}(k_{r}). This image can be computed in time O(n^{3}r log(q)) by linear algebra in T_{0}(k_{r}).

For h ∈ U_{0}(k_{r}), we can find g ∈ T_{0} such that ι(g) = h. Then ι(g^{−F^{r}}g) = h^{−F^{r}}h = 1, ie, g^{−F^{r}}g ∈ K. Hence (g^{−F^{r}}g)^{m} = 1 and so g^{m} ∈ T_{0}(k_{r}). Using the fact that T_{0} is a direct sum of copies of k̄^{×}, such a g must be in T_{0}(k_{rm}). This preimage can be computed in time O(n^{3}rm log(q)) by linear algebra in T_{0}(k_{rm}).

Proposition 4.2. Let G and H be k-split connected reductive linear algebraic groups defined over k with reductive rank n. Suppose we have an isogeny ι : G → H defined over k and that m is the exponent of the kernel of ι. For c in G or H, let s(c) denote the order of c^{F^{r−1}} ⋯ c^{F} c, where r is the minimal field degree of c.

(1) Lang’s theorem can be solved for c ∈ G(k_{r}) in time O(n^{3}r^{2}s(c)^{2}m^{2} log^{2}(q)) plus the time needed to solve it for some c′ ∈ H(k_{r}) with s(c′) ≤ s(c).

(2) Lang’s theorem can be solved for c ∈ H(k_{r}) in time O(n^{3}rs(c)m^{2} log(q)) plus the time needed to solve it for some c′ ∈ G(k_{rm}) with s(c′) ≤ ms(c).

Proof. If c ∈ G(k_{r}), then c′ = ι(c) can be found in time O(n^{3}r log(q)). Clearly s(c′) ≤ s(c). Now we can find a′ ∈ H_{rs(c)} such that a^{′−F} a′ = c′. Let a ∈ G_{rsm} be a preimage of a′ computed in time O(n^{3}rm log(q)). Consider a^{F} ca^{−1} ∈ K(k_{rs(c)m}) ≤ T_{0}(k_{rs(c)m}). Now

(a^{F} ca^{−1})^{F^{rs(c)m−1}} ⋯ (a^{F} ca^{−1})^{F} (a^{F} ca^{−1}) = a^{F^{rs(c)m}}(c^{F^{rs(c)m−1}} ⋯ c^{F} c)a^{−1} = 1,

So by Proposition 4.1, we can find b ∈ T_{0}(k_{rs(c)m}) such that a^{F} ca^{−1} = b^{−F} b in Las Vegas time O(nr^{2}s(c)^{2}m^{2} log^{2}(q)). Now (ab)^{−F} ab = c and Part (1) follows.

If c ∈ H(k_{r}), we can find an element c′ ∈ G(k_{rm}) such that ι(c′) = c in time O(n^{3}rm log(q)). Since (c^{′F^{r−1}} ⋯ c^{′F} c′)^{s(c)} ∈ K, we get s(c′) ≤ ms(c). We can now find a′ ∈ H(k_{rs(c)m^{2}}) such that c′ = a^{′−F} a′. Then a = ι(a′) can be computed in time O(n^{3}rs(c)m^{2} log(q)) and a^{−F} a = c and Part (2) is proved. □

4.2. Classical groups. We now show how to find transformers for the classical groups, using the standard representations. Throughout this subsection we take V = k̄^{d} and B_{0} to be the standard basis e_{1}, …, e_{d} of V (k).

The simplest case is G = GL_{d}\binom{}{k̄}. Let B be a k-basis of E(k). Let a be the matrix whose rows are the elements of B. Then B_{0}a = B, and so a is a transformer for E.

Now suppose G = SL_{d}\binom{}{k̄}. Given a basis B of V, define its volume, denoted vol(B), to be the determinant of the matrix whose rows are the elements of B. Then B_{0} has volume one and G is transitive on all bases of volume one. Now suppose B is a basis of E(k), the set of F -eigenvectors of c ∈ G. Then B^{F} c = B, and so

vol(B)^{F} = vol(B^{F}) = vol(Bc^{−1}) = vol(B) det(c)^{−1} = vol(B),

and vol(B) ∈ k. We can now construct a basis B′ of E(k) with volume one by dividing the first element of B by the scalar vol(B). So the matrix that takes B_{0} to B′ is a transformer in G.

Now suppose that q is odd and M is a nondegenerate orthogonal or symplectic form on V written (u, v) for u, v ∈ V. Further suppose that M is defined over k. Then the invariant group

G = {x ∈ GL_{d}(k̄) | (ux, vx) = (u, v)}

is a reductive linear algebraic group defined over k. Note that G is not necessarily split or connected however. Define the m × m matrix

A_{m} = (\begin{matrix}0 & & & 1 \\ & . & . & . \\ 1 & & & 0 \end{matrix})

and let δ be a fixed nonsquare in k. Then the form M has precisely one of the following Gram matrices M_{B} with respect to some basis B:

• If M is orthogonal and d = 2ℓ + 1, then

M_{B} = A_{d} or (\begin{matrix}& & A_{ℓ} \\ & δ \\ A_{ℓ} \end{matrix}) .

• If M is orthogonal and d = 2ℓ, then

M_{B} = A_{d} or (\begin{matrix}& & & A_{ℓ−1} \\ & 1 \\ & & −δ \\ A_{ℓ−1} \end{matrix}) .

• If M is symplectic, then d = 2ℓ and

M_{B} = (\begin{matrix}& A_{ℓ} \\ −A_{ℓ} \end{matrix}) .

A normal basis for M is a basis of V such that M_{B} is one of these matrices.

Given a nondegenerate symplectic or orthogonal form M on the k-space U, Algorithm 4 constructs a normal basis for U. The quadratic equations involved always have solutions by the standard classification theory of bilinear forms over finite fields (see [Gro02] for more details). Each of these equations can be solved by standard techniques in time log^{2}(q). Note that this construction is rational (that is, it does not use extensions of k) and takes time O(d^{3} log(q) + d log^{2}(q)).

If the form M is symplectic, we are done: our transformer is simply the matrix taking a normal basis of V (k) to a normal basis of E(k).

If M is orthogonal, the two normal bases may have different Gram matrices, in which case the equation in Lang’s Theorem has no solution. This is to be expected, since G is not connected in this case. If we take G = SO(V, M), then this problem can be avoided. Without loss of generality, the standard basis B_{0} is normal. Suppose that B is a normal basis of E(k). As with the special linear group, vol(B) is in k. Also

det(M_{B}) = det(BM_{B_{0}}B^{T}) = vol(B)^{2} det(M_{B_{0}}).

But the two choices given above for the Gram matrix have determinants in different cosets of k^{×2}, hence M_{B_{0}} = M_{B}. It now remains to ensure that vol(B) is one. Now vol(B)^{2} = det(M_{B_{0}})/ det(M_{B}) = 1, so suppose vol(B) = −1. If M_{B} = A_{d}, then exchanging the first and last vectors in B results in a new normal basis with volume one. Otherwise, negating the (ℓ + 1)st vector in B has the same effect.

Similar methods work for quadratic forms in characteristic two.

NormalBasis := function(U)

let u be a nonzero element of U

if dim(U) = 1 then find a ∈ k such that a^{2} = (u, u) or a^{2}δ = (u, u) return u/a

end if

let v be a nonzero element of u^{⊥} \ ku

if dim(U) = 2 then

if (u, u) ∈ −δ(v, v)k^{×2} then [U anisotropic] find a, b ∈ k such that (u, u)a^{2} + (v, v)b^{2} = 1 find c ∈ k such that ((u, u)a^{2} − (v, v)b^{2})c^{2} = −δ return au + bv, c(au − bv)

else [U isotropic] find a, b ∈ k such that (u, u)a^{2} + (v, v)b^{2} = 0 let w be a nonzero element of (au + bv)^{⊥} return au + bv, w

end if end if let w be a nonzero vector in (ku + kv)^{⊥} \ (ku + kv) find a, b, c ∈ k such that (u, u)a^{2} + (v, v)b^{2} + (w, w)c^{2} = 0 let x be a nonzero element of (au + bv + cw)^{⊥} return au + bv + cw, NormalBasis({u, v}^{⊥}), x

end function

algorithm 4. Finding a normal basis for a space with a bilinear form

Now suppose we have a split simple classical group G of (reductive and semisimple) rank n. Then G is isogenous to one of the groups considered above, with d = O(n).

If G has type A_{n}, then there is an isogeny map ι : SL_{n}\binom{}{k̄} → G with m ≤ n + 1. By Proposition 4.2(2), we can solve Lang’s Theorem in G in Las Vegas time O(n^{5}r^{2}s^{2} log^{2}(q)).

If G is not of type A_{ℓ}, then there is a series of at most 2 isogeny maps connecting G with one of the groups considered above. For each of these maps, m is at most 4. By Proposition 4.2, we can solve Lang’s Theorem in Las Vegas time O(n^{3}r^{2}s^{2} log^{2}(q)).

We have now proved Theorem 1.3. For groups of Cartan type G_{2} and F_{4}, a similar result can probably be obtained by exploiting the structure of composition and Jordan algebras, respectively [SV00].

4.3. Adjoint representation. Now consider an arbitrary k-split connected reductive linear algebraic group G, with reductive rank n and semisimple rank ℓ. Then G has a root datum (X, Φ, Y, Φ^{⋆}) with respect to a k-split maximal torus T_{0}. Here X and Y are free ℤ-modules of dimension n with a bilinear pairing ⟨∘, ∘⟩ : X × Y → ℤ putting them in duality. We fix dual bases e_{1}, …, e_{n} for X and f_{1}, …, f_{n} for Y. The roots Φ are a finite subset of X and the coroots Φ^{⋆} are a finite subset of Y. There is a one-to-one correspondence ⋆ : Φ → Φ^{⋆} such that ⟨α, α^{⋆}⟩ = 2 for every α ∈ Φ . For more details see [CMT04].

The Lie algebra L = L(G) is a G-module defined over k. This is called the adjoint representation of G and it is projectively faithful. Now L(k) has basis elements e_{α} for α ∈ Φ and h_{i} ∈ L(T_{0}) for i = 1, …, n with structure constants:

(1)  [h_{i}, h_{j}] = 0,
(2)  [e_{α}, h_{i}] = ⟨α, f_{i}⟩ e_{α},
(3)  [e_{−α}, e_{α}] = ∑_{i=1}^{n}⟨e_{i}, α^{⋆}⟩h_{i},

(4)  [e_{α}, e_{β}] = \begin{cases}N_{αβ} e_{α+β} & for α + β ∈ Φ, \\ 0 & for α + β ∉ Φ, β ≠ −α, \end{cases}

where the integral constants N_{αβ} are defined in [Car72]. Such a basis is called a Chevalley basis.

Choose simple roots α_{1}, …, α_{ℓ}, and fix a linear ordering < on Φ^{+} which is compatible with height, ie, ht(α) < ht(β) implies that α < β. Given a nonsimple positive root ξ, take the positive roots α, β such that ξ = α + β and α is as small as possible with respect to the ordering on Φ^{+}. We call (α, β) the extraspecial pair of ξ. We can choose a Chevalley basis of L so that the integers N_{αβ} are positive on extraspecial pairs by [Car72]. We call such a basis a standard Chevalley basis. Note that, as with the normal bases in Subsection 4.2, the problem of finding a standard Chevalley basis is rational over k.

The linear map a taking the standard Chevalley basis of L(k) to a standard Chevalley basis of E(k) must be an automorphism of L(k_{rs}). We now need to find a transformer in G. Let G_{ad} be the adjoint group with the same Cartan type as G and let Γ be the automorphism group of the Dynkin diagram of G. For each element of Γ, fix a graph automorphism normalising T_{0} and the Borel subgroup determined by Φ^{+}, as in [Car72]. Take Z to be a complement to Z(L) ∩ [L, L] in Z(L); by construction, our graph automorphisms fix Z pointwise. If the characteristic of k is greater than 3, then it follows from [Hog82] that

Aut(L) = Aut(Z) × (Γ ⋉ G_{ad}).

We can compute a decomposition a = zγb with z ∈ Aut(Z), γ a graph automorphism, and b ∈ G_{ad}(k_{rs}) in time O(d^{3}rs log(q)) using a slight modification of Algorithm 6 of [CMT04]. Since L(k)zγ = L(k), the element b is a transformer in G_{ad}. It is easily checked on a case-by-case basis that the number of roots of G is O(ℓ^{2}) and so the dimension of L is O(n + ℓ^{2}). Hence Lang’s Theorem can be solved for c ∈ G_{ad}(k_{r}) in time O((n+ℓ^{2})^{3}r^{2}s^{2} log^{2}(q)), once we have a standard Chevalley basis for E(k).

Suppose now that G is simple, so that ℓ = n. Then there is an isogeny map G → G_{ad} with m at most n + 1. We can now apply Proposition 4.2(2) and obtain:

Proposition 4.3. Suppose that k has characteristic greater than 3. Let G be a ksplit connected simple linear algebraic group and let L be the Lie algebra of G. Let c be an element of G(k_{r}) and suppose we are given s, the order of c^{F^{r−1}} ⋯ c^{F} c. Let E be the variety of F -eigenvectors of c in L. We can find a ∈ G(k_{rs}) in Las Vegas time O(n^{8}r^{2}s^{2} log^{2}(q)) plus the time needed to find a standard Chevalley basis of E(k).

We give an algorithm for finding a standard Chevalley basis in the next section. The timing of this algorithm is analysed in Section 6, leading to a proof of Theorem 1.2.

5. Computing a standard Chevalley basis

We now give an algorithm for constructing a Chevalley basis of the Lie algebra L of a k-split connected reductive group G. Recall that L is a p-Lie algebra [Jac62, Section V.7]. The first and hardest step is finding a k-split maximal toral p-subalgebra. This is similar to the algorithm of [dGIR96] for finding a Cartan subalgebra, but ensuring that the subalgebra is k-split makes things considerably more complex. Once we have a split maximal toral p-subalgebra, a Chevalley basis can be constructed using [Car72, Section 4.2].

Our algorithm only works for fields of characteristic p > 3. Whenever possible we state results for characteristics 2 and 3, in the hope that the gaps in our argument for small p can be filled later.

We assume that L is given as a structure constant algebra, but we frequently compute in the adjoint representation. Throughout this section n denotes the reductive rank of G, ℓ denotes the semisimple rank of G, and d denotes the dimension of the Lie algebra L. Recall that our Steinberg presentation of G determines a ksplit maximal torus T_{0}.

5.1. Toral subalgebras. A Lie algebra L over a field of characteristic p is called a p-Lie algebra if it is equipped with a map p : L → L satisfying the axioms

(5)  (x + y)^{p} = x^{p} + y^{p} + ∑_{i=1}^{p−1} s_{i}(x, y),
(6)  (ax)^{p} = a^{p}x^{p},
(7)  [xy^{p}] = x(ad y)^{p}

where x, y ∈ L, a ∈ k̄, s_{i} is defined in [Jac62, Section V.7], and a^{p} and (ad y)^{p} are the usual pth powers.

Given values of the p-map on a basis of L, we can compute the values on an arbitrary element using Equations (5) and (6). But s_{p−1} involves Lie products of length p, so the time taken for this computation is not polynomial in log(p). Given x ∈ L, we can use (7) to compute the coset x^{p} + Z(L) in time O(ℓ^{6} log(q) log(p)), since dim(L/Z(L)) is O(ℓ^{2}). We also define the q-map by applying the p-map e times, where q = p^{e}; values of this map modulo Z(L) can be computed in time O(ℓ^{6} log^{2}(q)).

We say that x ∈ L is semisimple if it is contained in the p-subalgebra generated by x^{p}. A toral subalgebra of L is a subalgebra defined over k consisting entirely of semisimple elements. Note that a toral subalgebra need not be a p-subalgebra. However every subalgebra H of L is contained in a minimal p-subalgebra called the p-closure of H in L. The p-closure of a toral subalgebra is toral, and so a maximal toral subalgebra is automatically a p-subalgebra. An n-dimensional toral p-subalgebra H is k-split if H(k) is isomorphic, as a p-Lie algebra, to the vector space k^{n} with trivial Lie product and the p-map acting componentwise.

If L is the Lie algebra of a k-split connected reductive group G, then the values of the p-map on a Chevalley basis are

h_{i}^{p} = h_{i} and e_{α}^{p} = 0,

provided that p > 3. Clearly H_{0} := L(T_{0}) = ⟨h_{1}, …, h_{n}⟩ is a k-split toral subalgebra.

We say that the Lie algebra L is k-split if it contains a maximal toral subalgebra which is k-split. The following theorem collects together the properties of toral subalgebras which we need.

Theorem 5.1. Let L be the p-Lie algebra of a k-split connected reductive group G. (1) L is k-split with split maximal toral subalgebra H_{0}.

(2) The centre of L is a k-split toral subalgebra when p > 2.

(3) Every toral subalgebra of L is abelian.

(4) Every (k-split) maximal toral subalgebra of L is the Lie algebra of a (k-split) maximal torus of G (when p > 2).

(5) The maximal toral subalgebras of L are G-conjugate.

(6) The k-split maximal toral subalgebras of L are G(k)-conjugate when p > 2.

Proof. In Part (1) it only remains to prove maximality, which follows from [Hum67, Proposition 13.2]. Part (3) is given in [Hum78, Lemma 8.1] for characteristic zero, but the same proof works for positive characteristic. Part (5) is Corollary 13.5 of [Hum67].

We now prove Part (2). Let {e_{α}, h_{i}} be a Chevalley basis with respect to H_{0}. Suppose that z ∈ Z(L) and write

z = ∑_{i=1}^{n} t_{i}h_{i} + ∑_{α∈Φ} a_{α}e_{α}.

Let h_{α} = ∑_{i=1}^{n}⟨e_{i}, α^{⋆}⟩h_{i}, then the coefficient of e_{α} in [z, h_{α}] is 2a_{α}. Since [z, h_{α}] = 0 and p > 2, we get a_{α} = 0. Hence z is in H_{0} = ⟨h_{1}, …, h_{n}⟩. Since H_{0} is a split toral subalgebra, Z(L) is also. (The idea for this proof is from [Hog82, Lemma 6.10].)

Every maximal toral subalgebra of L is the Lie algebra of a maximal torus of G by [Hum67, Proposition 13.2]. For p > 2, split tori correspond to split toral subalgebras by [Sel67, Theorem 9]. Hence Part (4) is proved.

From now on we assume p > 2. By [Hum67, Proposition 13.6], T ↦ L(T) gives a one-to-one correspondence between maximal tori of G and maximal toral subalgebras of L. Once again, split tori correspond to split toral p-algebras. Part (6) now follows from the corresponding result for tori. □

Corollary 5.2. Given a subalgebra H of L defined over k, we can determine if H is k-split maximal toral in time O(ℓ^{7} log^{2}(q)).

Proof. First check that H is abelian of dimension n, and compute H/Z. Note that H/Z has dimension at most ℓ. By Theorem 5.1(2), it suffices to determine if H/Z(L) is a split toral algebra. This is done by testing whether b^{q}+Z(L) = b+Z(L) where b + Z(L) runs over a basis of L/Z(L). As we argued at the beginning of this section, this takes time O(ℓ^{6} log^{2}(q)) for each basis element. □

Since semisimple elements are common in L(k) (see Section 6) and the centraliser of such an element is reductive of rank n, we can find a maximal toral subalgebra by Algorithm 5.

MaximalToralSubalgebra := function(L)

repeat take x random in L until x is semisimple let M = C_{L}(x) if M is abelian then

return M else

return MaximalToralSubalgebra(M) end if

end function

algorithm 5. Finding a maximal toral subalgebra in L

The basic idea of our algorithm is to randomly select a series of increasingly split maximal toral subalgebras. We now assign a conjugacy class of W to every maximal toral subalgebra H, which measures how split H is. See [Leh92] for a more detailed version of this construction. There exists g ∈ G\binom{}{k̄} such that H = H_{0}^{g}, by Theorem 5.1(5). Note that H_{0}^{F} = H_{0} and H^{F} = H, since both are defined over k. Now

H_{0}^{g^{F} g^{−1}} = ((H_{0}^{g})^{F})^{g^{−1}} = (H^{F})^{g^{−1}} = H^{g^{−1}} = H_{0},

so g^{F} g^{−1} is in N_{G}(H_{0}) = N_{G}(T_{0}). Let w be the image of g^{F} g^{−1} under projection onto the Weyl group W = N_{G}(T_{0})/T_{0}. The element w is uniquely determined by H up to conjugacy in W.

5.2. Root decompositions of L. The root decomposition of L with respect to H_{0} is

L = H_{0} ⊕ ⨁_{α∈Φ} L_{α}

where the root space L_{α} = {b ∈ L | [b, h] = α(h)b for all h ∈ H_{0}} and each root α ∈ Φ is a linear functional H_{0} → k̄ defined over k. This decomposition is defined over k by [Sel67, Theorem 6]. If the characteristic of k is greater than 3, every root space has dimension one.

Let H be a maximal toral subalgebra of L, fix g ∈ G\binom{}{k̄} such that H = H_{0}^{g} and let w be the image of g^{F} g^{−1} in W. For α ∈ Φ, define α^{g} : H → k̄ by α^{g}(h) = α(h^{g^{−1}}). Then the root decomposition with respect to H is

L = H ⊕ ⨁_{α∈Φ} L_{α^{g}},

where L_{α^{g}} = {b ∈ L | [b, h] = α^{g}(h)b for all h ∈ H} = L_{α}^{g}. This decomposition is not defined over k in general.

Fix a basis h_{1}, …, h_{n} of H and let f = (f_{1}, …, f_{n}) be a sequence of irreducible polynomials in k[X] with f_{i}(X) ≠ X for at least one i. Define

L_{f} = {y ∈ L | yf_{i}(ad(h_{i})) = 0 for i = 1, …, ℓ}.

If L_{f} ≠ 0, we call f a generalised root and L_{f} a generalised root space. The generalised root decomposition of L with respect to H is

L = H ⊕ ⨁_{f∈ℱ} L_{f},

GeneralisedRoots := function(L, H)

let h_{1}, …, h_{n} be a basis of H

let ℱ = {()} and define L_{()} = L

for i = 1, …, n do let ℱ′ = ∅ for f ∈ ℱ do

compute g, the characteristic polynomial of h_{i} on L_{f} for f_{i} an irreducible factor of g do

add (f_{1}, …, f_{i−1}, f_{i}) to ℱ′ where f = (f_{1}, …, f_{i−1}) define L_{(f_{1},...,f_{i})} = {x ∈ L_{f} | xf_{i}(ad(h_{i})) = 0}

end for end for let ℱ = ℱ′

end for

remove (X, …, X) from ℱ [since L_{(X,...,X)} = H] return ℱ

end function

algorithm 6. Generalised roots

where ℱ = ℱ(L, H) is the set of generalised roots of L with respect to H. This decomposition is defined over k. The generalised roots are computed by Algorithm 6. Complete factorisation of a polynomial of degree d over k takes time at most O(d^{3}(log(d) + log(q)) log(q)), as shown in [vzGG03]. Factoring the characteristic polynomials g is the dominant contribution to the running time of this algorithm. Since each g has degree at most d, and the sum of the degrees of all the gs is at most nd, the algorithm takes time O(nd^{3}(log(d) + log(q)) log(q)).

In fact, we do not apply this algorithm directly to L, since we want our time to depend on ℓ but not on n (this is necessary for analysing the recursion in Algorithm 8). By Theorem 5.1(2), the centre Z(L) is contained in H. So we can construct a basis h_{1}, …, h_{n} for H(k) with ⟨h_{1}, …, h_{m}⟩ = Z(L) central for some m ≤ n. Extend this to a basis B of L(k). Let ϕ be the pullback map L/Z(L) → L which takes b + Z to b for all b ∈ B. Note that ϕ is a linear map, but need not be a Lie algebra map. We compute in L/Z(L), since it has dimension O(ℓ^{2}) independent of n, and the results are then transfered into L via ϕ. However, L/Z(L) need not be the Lie algebra of a group of Lie type, so most of our theoretical results do not apply to this quotient.

Let ℱ be the set of generalised roots of L/Z(L) with respect to H/Z(L). Given f = (f_{1}, …, f_{m}) ∈ ℱ define the sequence f′ = (f_{1}, …, f_{m}, X, …, X) of length n. It is now easy to see that ϕ((L/Z(L))_{f}) = L_{f′}. Hence the generalised root decomposition of L with respect to H follows immediately once we have the decomposition of L/Z(L) with respect to H/Z. Since the dimension of L/Z(L) is O(ℓ^{2}), the decomposition of L/Z(L) can be computed in time O(ℓ^{7}(log(ℓ) + log(q)) log(q)).

Given a generalised root f ∈ ℱ(L, H), the subspace L_{f} is a direct sum of components L_{α^{g}} of the root decomposition with respect to H. So we can partition Φ into subsets Φ_{f} such that L_{f} = ⨁_{α∈Φ_{f}} L_{α^{g}}. Define the degree of f to be the lowest common multiple of the degrees of the f_{i}. Given a generalised root f, we define

f_{−} = ((−1)^{deg(f_{1})}f(−X), …, (−1)^{deg(f_{n})}f(−X)).

Clearly Φ_{f_{−}} = −Φ_{f}. Note that we can have f = f_{−} when the degree of f is greater than one.

We now prove some properties of the sets Φ_{f}.

Lemma 5.3. Let f be a generalised root of L = L(G) with respect to H. (1) The action of F on {L_{α^{g}} | α ∈ Φ_{f}} is equivalent to the action of w on Φ_{f}.

(2) Φ_{f} is a union of orbits of w on Φ.

(3) If deg(f) = 1, then w acts trivially of Φ_{f}. If in addition q > 3, then Φ_{f} contains a single root.

(4) If deg(f) = 2 and f = f_{−}, then w acts on Φ_{f} by negation.

Proof. Write g^{F} g^{−1} = tẇ for some t ∈ T_{0}. Now

L_{α^{g}}^{F} = L_{α}^{gF} = L_{α}^{F^{−1}gF} = L_{α}^{g^{F}} = L_{α}^{tẇg} = L_{αw}^{g} = L_{(αw)^{g}},

and so Part (1) is proved. Part (2) follows since L_{f}^{F} = L_{f}.

Part (3) holds because L_{f} is a root space when deg(f) = 1.

Suppose deg(f) = 2 and f = f_{−}. Let α ∈ Φ_{f}. Then L_{α^{g}}^{F} = L_{(αw)^{g}} and so (αw)^{g}(h_{i}) and α^{g}(h_{i}) are conjugate roots of f_{i}. But if deg(f_{i}) = 2, then f = f_{−} implies that the conjugate roots are negatives of each other. And if deg(f_{i}) = 1, then f = f_{−} implies that the only root of f_{i} is zero. In either case (αw)^{g}(h_{i}) = −α^{g}(h_{i}) and so w acts by negation. □

5.3. Fundamental subalgebras. Now that we have the generalised root decomposition of L with respect to H, we consider the subalgebra M_{f} generated by a generalised root space L_{f}. Such subalgebras often turn out to be fundamental: We define a (split) fundamental subgroup of G as a connected reductive subgroup normalised by a (split) maximal torus. A subalgebra M of L is (split) fundamental if it is the Lie algebra of a (split) fundamental group. This subgroup is denoted G_{M}. Fundamental subalgebras clearly normalise a maximal toral subalgebra.

The most important properties of such algebras for our purposes are:

Theorem 5.4. Suppose that k has characteristic greater than 3. Let M be a fundamental subalgebra of L normalised by the maximal toral subalgebra H.

(1) M ∩ H is a maximal toral subalgebra of M.

(2) If H is a split maximal toral subalgebra, then M is split fundamental.

Proof. We have H ≤ C_{M+H}(H) ≤ C_{L}(H) = H, so M + H has root decomposition

(8)  M + H = H ⊕ ⨁_{β} M_{β},

where β runs over Φ(M + H, H), the set of roots of M + H with respect to H. Suppose m + h ∈ M_{β} where m ∈ M and h ∈ H. Then, for all h′ ∈ H, [m, h′] = [m + h, h′] = α(h′)(m + h). But [m, h′] ∈ M, and so h ∈ M and M_{β} ≤ M. By intersecting (8) with M, using the fact that each M_{β} has dimension one, we obtain the root decomposition

M = (H ∩ M) ⊕ ⨁_{β} M_{β},

and so H ∩ M is a maximal toral subalgebra of M.

Finally if M normalises H and H is split, then, by Theorem 5.1(4), H = L(T) for some split maximal torus T of G. Then G_{M} normalises T and Part (2) is proved. □

Recall that the closure \overline{Ψ} of Ψ ⊆ Φ is just the set of all roots that can be written as a sum of elements of Ψ. Note that if \overline{Ψ} is also closed under negation, it is a subsystem. If \overline{Ψ} is a subsystem, we say w ∈ W is inner on \overline{Ψ} if the action of w on \overline{Ψ} is induced by an element of W (\overline{Ψ}).

Lemma 5.5. Suppose that k has odd characteristic. Let M be the subalgebra generated by ∑_{α∈Ψ} L_{α^{g}}, where Ψ is an orbit in Φ under the action of w ∈ W.

(1) M is fundamental or soluble.

(2) If M is fundamental, then G_{M} is semisimple.

(3) M is fundamental if, and only if, \overline{Ψ} is a subsystem.

(4) If \overline{Ψ} is a subsystem and w is inner on \overline{Ψ}, then M is split fundamental.

Proof. Since [∑_{α∈Ψ} L_{α^{g}}, H] ≤ ∑_{α∈Ψ} L_{α^{g}}, we have [M, H] ≤ M and so M normalises H. Since [L_{α}, L_{β}] ≤ L_{α+β} (recalling that L_{0} = H), we have

M = (H ∩ M) ⊕ ⨁_{α∈\overline{Ψ}} L_{α^{g}}.

Let Ψ = Ψ_{1} ∪ ⋯ ∪ Ψ_{m} be the finest decomposition of Ψ into pairwise orthogonal subsets. Then \overline{Ψ} = \overline{Ψ}_{1} ∪ ⋯ ∪ \overline{Ψ}_{m} is also an orthogonal decomposition. Clearly w permutes the sets Ψ_{i} and, since w is transitive on Ψ, it must be transitive on them. Since −\overline{Ψ}_{1} is never orthogonal to \overline{Ψ}_{1}, we either have −\overline{Ψ}_{1} = \overline{Ψ}_{1} or −\overline{Ψ}_{1} is disjoint from \overline{Ψ}_{1}. By the transitivity of w, whichever of these cases holds for −\overline{Ψ}_{1}, also holds for all −\overline{Ψ}_{i}. In particular, \overline{Ψ} is closed under negation iff \overline{Ψ}_{1} is. Let ψ be the sum of all the elements of \overline{Ψ}_{1}. Now \overline{Ψ}_{1} is closed under negation iff ψ = 0 (since ψ = 0 implies −α = ∑_{β∈\overline{Ψ}_{1},β≠α} β ∈ \overline{Ψ}_{1} for all α ∈ \overline{Ψ}_{1}, and the converse is trivial). We define M_{i} = H_{i} ⊕ ⨁_{α∈\overline{Ψ}_{i}} L_{α^{g}}, where H_{i} is the subalgebra of H generated by [L_{α^{g}}, L_{−α^{g}}] for all α ∈ \overline{Ψ}_{i}. Note that M = ⨁_{i} M_{i}.

Suppose first that ψ ≠ 0. Then the root subsystem generated by Ψ_{1} is just \overline{Ψ}_{1} ∪ −\overline{Ψ}_{1}. Since this root subsystem is irreducible, ψ induces an ordering on it which makes \overline{Ψ_{1}} the set of positive roots. Hence M_{1} is just the Borel subalgebra of the Lie algebra of a simple group, and so must be soluble. The transitivity of w on the sets \overline{Ψ}_{i} implies that M_{i} is soluble for every i, and so M = ⨁_{i} M_{i} is soluble.

If ψ = 0, then \overline{Ψ}_{1} is an irreducible root subsystem and so M_{1} is fundamental with G_{M_{1}} a simple group. Hence M = ⨁_{i} M_{i} is fundamental with G_{M} a semisimple group. Parts (1), (2) and (3) are now proved.

Now suppose that \overline{Ψ} is closed under negation and w is inner on \overline{Ψ}. By Lang’s theorem in G_{M}, we can find h ∈ G_{M} such that h^{F} h^{−1} = ẇ. On the other hand, g satisfies g^{F} g^{−1} = tẇ for some t ∈ T_{0}. Now the map ẇF is a nonstandard Frobenius endomorphism since ẇ^{F} = ẇ and so (ẇF)^{m} = F^{m}, where m is the order of ẇ. Furthermore T_{0}^{ẇF} = T_{0}. So, by Lang’s theorem in T_{0}, there is a u ∈ T_{0} such that t = u^{ẇF} u^{−1}. Set g̃ = u^{−ẇ}g, so that

g̃^{F} g̃^{−1} = u^{−ẇF} g^{F} g^{−1}uẇ = u^{−ẇF} tuẇ = ẇ

and H_{0}g̃ = H_{0}^{˙w^{−1}u^{−1}ẇg} = H_{0}^{g} = H. Hence h^{F} h^{−1} = g̃^{F} g̃^{−1}, that is g̃h^{−1} is defined over k and so H^{h^{−1}} = H_{0}^{g̃h^{−1}} is split. So

[M, H^{h^{−1}}] = [M^{h}, H]^{h^{−1}} = [M, H]^{h^{−1}} ≤ M^{h^{−1}} = M

and M is split fundamental by Theorem 5.4(2). □

Components := function(L)

let H := MaximalToralSubalgebra(L)

let ℱ = GeneralisedRoots(L, H)

for each f ∈ ℱ let M_{f} be the subalgebra generated by L_{f} construct the graph with vertices ℱ

and an edge (f, g) whenever M_{f} ∩ M_{g} is not contained in H let C = ∅ for each graph component c do

add the subalgebra ⟨M_{f} | f ∈ c⟩ to C end for return C

end function

algorithm 7. Direct sum components

An immediate application is Algorithm 7 for computing the direct sum decomposition of a the Lie algebra L. Although more that one w-orbit of Φ can have the same generalised root, this clearly is not possible for orbits in different components of Φ. The components returned are fundamental subalgebras.

5.4. Finding a split maximal toral subalgebra. Suppose now that we have found a nontrivial split fundamental subalgebra M. The following proposition shows that we can use recursion to find a split maximal toral subalgebra of L.

Proposition 5.6. Suppose that the characteristic of k is greater than 3. Let M be a split fundamental subalgebra of L. Let K be a split maximal toral subalgebra of M. Then C_{L}(K) is a split fundamental subalgebra of L with full rank n. Hence a split maximal toral subalgebra of C_{L}(K) is also a split maximal toral subalgebra of L.

Proof. Let G_{M} be the split fundamental subgroup of G such that L(G_{M}) = M. Let T be a split maximal torus of G which normalises G_{M} and let H = L(T). Then U = G_{M} ∩ T is a split maximal torus of G_{M}. By Theorem 5.1(6), we can assume without loss of generality that K = L(U).

Let C = C_{G}(U). Clearly C is normalised by T and it is reductive by [Hum75, Corollary 26.2A], hence it is split fundamental.

Let Ψ be the subset of Φ = Φ(G, T) consisting of roots of G_{M}, or equivalently of M. Let Ψ′ be the elements of Φ which are orthogonal to all elements of Ψ. Then Ψ′ is the root system of C and

L(C) = H ⊕ ⨁_{α∈Ψ′} L_{α}.

Clearly L(C) ≤ C_{L}(K).

Conversely, suppose x ∈ C_{L}(K). Let {e_{α}, h_{i}} be a Chevalley basis of L with respect to H and write

x = ∑_{i=1}^{n} t_{i}h_{i} + ∑_{α∈Φ} a_{α}e_{α}.

If α ∉ Ψ′ then there exists β ∈ Ψ such that ⟨α, β^{⋆}⟩ ≠ 0. By the basic properties of root data |⟨α, β^{⋆}⟩| ≤ 3, so ⟨α, β^{⋆}⟩ is still nonzero considered as an element of k.

SplitMaximalToralSubalgebra := function(L, Z) [Z ≤ Z(L)]

repeat let H/Z = MaximalToralSubalgebra(L/Z) if H is split then return H let ℱ = GeneralisedRoots(L/Z, H/Z) for each f ∈ ℱ compute M_{f} = ϕ(⟨(L/Z)_{f}⟩)

until we find A ⊆ ℱ such that M_{A} = ⟨∑_{f∈A} M_{f}⟩ < L is split fundamental let H_{A} = SplitMaximalToralSubalgebra(M_{A}, ϕ(Z(M_{A}/Z))) let C_{A} = ϕ(C_{L/Z}(H_{A})) and Z = ϕ(Z(C_{A}/Z)) let K = Z for M in Components(C_{A}, Z) do

let K = K + SplitMaximalToralSubalgebra(M, Z) end for return K

end function

algorithm 8. Finding a split maximal toral subalgebra

Now h_{β} = [e_{−β}, e_{β}] is in K, and so [x, h_{β}] = 0. But the coefficient of e_{α} in [x, h_{β}] is a_{α}⟨α, β^{⋆}⟩ by (2). Hence a_{α} = 0 for all α ∉ Ψ′ and so x ∈ L(C).

The second conclusion is an immediate consequence of the first. □

We now have a method for finding split maximal toral subalgebras of L: Find a maximal toral subalgebra H, and compute its generalised roots. For each generalised root f, construct the subalgebra M_{f} generated by L_{f}. Now, assuming that we can find A ⊆ ℱ for which M_{A} = ⟨∑_{f∈A} M_{f}⟩ is known to be split fundamental and strictly contained in L, find a split maximal toral subalgebra H_{A} of M_{A}. By Proposition 5.6, a split maximal toral subalgebra of C_{L}(H_{A}) is a split maximal toral subalgebra of L. Since M_{A} and C_{L}(H_{A}) are split fundamental subalgebras of L, Theorem 5.4(2) ensures that they are also the Lie algebras of k-split connected reductive algebraic groups and so this recursion is valid. Algorithm 8 gives the precise method we use. Note that the second argument Z passed to this function is intended to indicate that we have a basis of L(k) extending a basis of Z(k), and the pullback map ϕ : L/Z → L. We take Z = Z(L) initially. In Section 6, we give a method for ensuring that M_{A} is known to be split fundamental.

5.5. Finding a Chevalley basis. We start by giving a recognition theorem for a standard Chevalley basis.

Theorem 5.7. Suppose the finite field k has characteristicgreater than 3. Let G be a k-split connected reductive linear algebraic group defined over k and let L be the Lie algebra of G. Let H be a k-split maximal toral subalgebra of L and let L = H ⨁_{α} L_{α} be the root decomposition of L. Suppose we have a basis of L consisting of h_{i} ∈ H for i = 1, …, n and e_{α} ∈ L_{α} for α ∈ Φ. Further suppose this basis satisfies the equation

[e_{−α}, e_{α}] = ∑_{i=1}^{n}⟨e_{i}, α^{⋆}⟩h_{i}

StandardChevalleyBasis := function(L)

let H = SplitMaximalToralSubalgebra(L)

compute the root system Φ and root spaces L_{α} for α ∈ Φ

find simple roots α_{1}, …, α_{ℓ} for Φ

for i = 1, …, ℓ do let α = α_{i} choose nonzero e_{α} ∈ L_{α} and f_{α} ∈ L_{−α} find a ∈ k such that [e_{α}, [f_{α}, e_{α}]] = 2ae_{α} let e_{−α} = f_{α}/a, h_{α} = [e_{−α}, e_{α}]

end for

compute a basis {h_{i}} for H(k) with h_{α} = ∑_{i}⟨e_{i}, α^{⋆}⟩h_{i} for simple roots α for γ a nonsimple root do

let (α, β) be the extraspecial pair of γ

let e_{γ} = [e_{α}, e_{β}]/N_{αβ}, e_{−β} = [e_{−α}, e_{−β}]/N_{−α,−β} end for return {e_{α}, h_{i}}

end function

algorithm 9. Finding a standard Chevalley basis

for every simple root α and the equations

[e_{α}, e_{β}] = N_{αβ}e_{α+β} and [e_{−α}, e_{−β}] = N_{−α,−β}e_{−α−β}

for every extraspecial pair (α, β). Then this is a standard Chevalley basis.

Proof. We need to prove that this basis satisfies the defining equations given in Subsection 4.3. Equation (1) follow from the fact that a toral subalgebra is abelian, Equation (1) is given, and the Equation (4) follows from [Car72, Theorem 4.2.1]. It remains to prove Equation (2).

For y ∈ Y, define h_{y} = ∑_{i=1}^{n}⟨e_{i}, y⟩h_{i} ∈ H(k). It suffices to prove that

[e_{α}, h_{y}] = ⟨α, y⟩ e_{α}, (9)

for some collection of elements y generating Y.

Now (9) is true for all y ∈ Φ^{⋆} by [Car72, Theorem 4.2.1]. If ⟨α, y⟩ = 0 for all α ∈ Φ, then h_{y} is central and so (9) is trivially true. Together, these two kinds of element generate Y and so we are done. □

A consequence of this theorem is Algorithm 9 for finding a Chevalley basis of L. Note that for an extraspecial pair (α, β), we have 0 < N_{αβ} ≤ 3, so division by N_{αβ} is not a problem. The basis {h_{i}} can be computed by elementary linear algebra. Note that in the second for-loop, the roots are taken in the linear order < of Subsection 4.3, thus ensuring that e_{α} and e_{β} are already known when we compute e_{γ}.

6. Time analysis

Let L be the Lie algebra of the k-split connected reductive linear algebraic group G. We now find bounds on the probability of finding a maximal toral subalgebra H ≤ L and a set A of generalised roots such that M_{A} is known to be split fundamental. To simplify our analysis, we just bound the probability that Algorithm 5 finds a maximal toral subalgebra in a single step, or equivalently that the random element chosen is regular semisimple. Subsection 6.1 gives bounds on the frequencies of regular semisimple elements corresponding to Weyl group elements. In Section 6.2, we bound the proportion of suitable Weyl group elements. We give the proof of Theorem 1.2 in Section 6.3.

Throughout this section, n is the reductive rank of G, ℓ is the semisimple rank of G, d is the dimension of L, and d_{1}, …, d_{ℓ} are the invariant degrees of G as defined in [Car72, Section 9.3].

6.1. Regular semisimple elements. An element of L is regular semisimple if its centraliser is a maximal toral subalgebra. For any subvariety S of L, let S_{rss} be the variety of regular semisimple elements in S. Recall from Subsection 5.1 that the maximal toral subalgebras of L are classified up to G(k)-conjugacy by the conjugacy classes of W. Fix w in W and let L_{rss,w} be the set of elements x ∈ L which are regular semisimple and such that there exists g ∈ G with C_{L}(x) = H_{0}^{g} and g^{F} g^{−1} ∈ T_{0}ẇ. Although we give direct proofs, many results in this section also follow from Gus Lehrer’s analysis of hyperplane complements [Leh92, Leh98].

The following result bounds our chances of finding a regular semisimple element in L(k) whose centraliser corresponds to the W -class of a given w.

Proposition 6.1. Let L be the Lie algebra of a k-split connected reductive group G with root datum (X, Φ, Y, Φ^{⋆}). Let w be an element of the Weyl group W. Define

Q_{w}(X) = \frac{∏_{i=1}^{ℓ}(1 − X^{d_{i}})}{det_{Y} (1 − wX)}.

Then

(1 − ∑_{i=1}^{ℓ} \frac{c_{i}}{q^{i}} ) Q_{w}(1/q)\frac{|w^{W} |}{|W |} ≤ \frac{|L_{rss,w}(k)|}{|L(k)|} ≤ Q_{w}(1/q)\frac{|w^{W} |}{|W |}.

where c_{i} = c_{i}(w) is the number of w-orbits in Φ consisting of roots α with the property that i is the largest integer for which α, αw, …, αw^{i−1} are k̄-linearly independent.

Proof. Fix some g ∈ G such that g^{F} g^{−1} = ẇ and define H_{w} = H_{0}^{g}. Let T_{w} = T_{0}^{g} so that L(T_{w}) = H_{w}. Then

L_{rss,w}(k) = {x ∈ L_{rss}(k) | x ∈ H_{w}(k)^{h} for some h ∈ G(k)},

which is in one-to-one correspondence with

{(x, H) ∈ L_{rss}(k) × H_{w}(k)^{G(k)} | x ∈ H}.

Since N_{G(k)}(H_{w}(k))/T_{w}(k) ≅ C_{W} (w), we have |H_{w}(k)^{G(k)}| = \frac{|G(k)|}{|T_{w}(k)||C_{W} (w)|}. Hence

\frac{|L_{rss,w}(k)|}{|L(k)|} = |(H_{w})_{rss}(k)|\frac{|G(k)|}{|L(k)||T_{w}(k)|} \frac{|w^{W} |}{|W |}.

Given a root α ∈ Φ, define

H_{α} = {h ∈ H_{w} | α^{g}(h) = 0}.

Then H_{α} is a hyperplane in H_{w} and (H_{w})_{rss} = H_{w} − ⋃_{α∈Φ} H_{α}. Now H_{α}^{F} = H_{αw},

so H_{α}(k) = (⋂_{j} H_{αw^{j}}) (k). This space has codimension i, the largest integer such that α, αw, …, αw^{i−1} are linearly independent. So, for each i = 1, …, ℓ, we are removing c_{i} subspaces of codimension i from a k-space of dimension n. Hence

q^{n} (1 − ∑_{i=1}^{ℓ} \frac{c_{i}}{q^{i}} ) ≤ |(H_{w})_{rss}(k)| ≤ q^{n}.

Using Theorem 9.4.10 of [Car72] and the fact that our group is untwisted, we get

|G(k)| = q^{d} ∏_{i=1}^{ℓ} (1 − \frac{1}{q^{d_{i}}} ) .

Using Proposition 3.3.5 of [Car93] and the fact that F is the standard Frobenius, we find that T_{w}(k) has order det_{Y} (qI − w). Hence

\frac{|G(k)|}{|L(k)||T_{w}(k)|} = \frac{q^{d} ∏_{i}(1 − 1/q^{d_{i}})}{q^{d} det_{Y} (qI − w)} = \frac{Q_{w}(1/q)}{q^{n}}.

□

The following useful lemma can be proved by elementary calculus.

Lemma 6.2. Let a_{1}, …, a_{m} be a sequence of nonnegative integers and suppose that no integer appears more than a times in this sequence. Then

∏_{i} (1 − \frac{1}{q^{a_{i}}} ) ≥ (1 − \frac{1}{q})^{2a} .

6.2. Reflection derangements. Recall from Subsection 5.2 that there is a relationship between between the generalised roots f with respect to a toral subalgebra and the orbits of the corresponding Weyl group element w on Φ. This relationship need not be a one-to-one correspondence. As we saw in Lemma 5.3(3) and (4), this relationship is almost a one-to-one correspondence when the degree of f is one, or the degree is two and f = f_{−}. This happens when there is a root α such that αw = ±α. In other words, when a reflection s_{α} is fixed under conjugation by w.

In this section, we count the number of Weyl group elements of this kind. Given a permutation representation of a group, an element of the group is called a derangement with respect to the representation if it fixes no points at all. The proportion of derangements of the symmetric group Sym_{m} acting on m letters is known to approach 1/e as m → ∞. We give similar results for a Weyl group acting on its reflections by conjugation. We refer to these elements as reflection derangements. We are grateful to Anthony Henderson for helping us with the proof of this proposition.

Proposition 6.3. If W is an irreducible Coxeter group of classical type A_{ℓ}, B_{ℓ} / C_{ℓ}, or D_{ℓ}, then the proportion of its reflection derangements approaches 2e^{−3/2}, e^{−5/4}, 2e^{−5/4} + (4e)^{−1}, respectively, as ℓ → ∞. For exceptional types, the proportions are as listed below:

\begin{matrix}G_{2} & F_{4} & E_{6} & E_{7} & E_{8} \\ 1/3 & 1/4 & 1409/2592 & 1646/2835 & 3385549/6220800 \end{matrix}

Proof. Denote by f the number of reflection derangements of W. We wish to determine f/|W |.

Type A_{ℓ}: The Weyl group W (A_{ℓ}) can be identified with the symmetric group Sym_{ℓ+1} on ℓ + 1 letters. Write m = ℓ + 1 and write d_{m} for the proportion of permutations in Sym_{m} without fixed points in {1, …, m}. Denote by R_{m} the set of all permutations in Sym_{m} with at most one fixed point in {1, …, m}.

An element of Sym_{m} does not fix a reflection if, and only if, it belongs to R_{m} and does not contain a transposition (i, j) in its cycle decomposition. So

f = |R_{m} − ⋃_{1≤i<j≤m} R_{m}^{i,j}|

where

R_{m}^{ij} = {w ∈ R_{m} | w contains (i, j)}.

We compute f by inclusion/exclusion. As R_{m}^{ij} and R_{m}^{ij′} intersect trivially for j ≠ j′ we can find f as an alternating sum over h-tuples of commuting transpositions:

∑_{h=0}^{⌊m/2⌋}(−1)^{h}\binom{m}{2h}\frac{(2h)!}{2^{h}h!}|R_{m−2h}|.

Since, clearly, |R_{m}| = d_{m} + md_{m−1}/m,

f = m! ∑_{h=0}^{⌊m/2⌋} (−\frac{1}{2})^{h} \frac{1}{h!} (d_{m−2h} + d_{m−2h−1}) .

As lim_{m→∞} d_{m} = 1/e, the required proportion tends to

lim_{m→∞} \frac{f}{m!} = ∑_{h=0}^{∞} (−\frac{1}{2})^{h} \frac{1}{h!} \frac{2}{e} = e^{− \frac{1}{2}} \frac{2}{e} = 2e^{− \frac{3}{2}} .

Types B_{ℓ} and C_{ℓ}: The Weyl group W = W (B_{ℓ}) = W (C_{ℓ}) can be identified with the group of all permutations w of {±1, …, ±ℓ} such that (−i)w = −(iw). Define the homomorphism ϕ : W → Sym_{ℓ} by iw^{ϕ} = |iw|. Then w ∈ W fixes no reflections if, and only if, w^{ϕ} is a derangement of Sym_{ℓ} and, for every transposition (i, j) contained in the cycle decomposition of w^{ϕ}, either (i, j, −i, −j) or (j, i, −j, −i) is contained in the cycle decomposition of w.

Writing S_{ℓ} for elements of W such that w^{ϕ} is a derangement and

S_{ℓ}^{ij} = {w ∈ S_{ℓ} | w contains (i, j)(−i, −j) or (i, −j)(−i, j)},

we find that

f = |S_{ℓ} − ⋃_{1≤i<j≤ℓ} S_{ℓ}^{ij}| .

Again, we can count f by taking alternating sums over h-tuples of commuting transpositions in W^{ϕ}. As each transposition in the decomposition of an element of w^{ϕ} corresponds to two 4-cycles as indicated above, we find an extra factor 2^{h} compared to the A_{ℓ} case:

∑_{h≥0,2h≤ℓ}(−1)^{h}\binom{ℓ}{2h}\frac{(2h)!}{2^{h}h!}2^{h}|S_{ℓ−2h}|.

As |S_{ℓ}| = 2^{ℓ} ℓ! d_{ℓ},

f = ∑_{h≥0,2h≤ℓ} (−1)^{h} \frac{ℓ!}{h!}2^{ℓ−2h}d_{ℓ−2h}.

As lim_{m→∞} d_{m} = 1/e and |W (B_{ℓ})| = 2^{ℓ}ℓ!, the required proportion tends to

lim_{m→∞} \frac{f}{2^{ℓ}ℓ!} = ∑_{h=0}^{∞} (−\frac{1}{4})^{h} \frac{1}{h!} \frac{1}{e} = e^{− \frac{1}{4}} e^{−1} = e^{− \frac{5}{4}} .

Type D_{ℓ}: The Weyl group W (D_{ℓ}) is the subgroup of W (B_{ℓ}) consisting of all elements w such that ∏_{i=1}^{ℓ} iw is positive. In cycle notation, this means that w has an even number of negative cycles (that is, cycles in which both positive and negative numbers occur).

Define ϕ : W → Sym_{ℓ} as the restriction of the map for type B_{ℓ}. Then w ∈ W does not commute with any reflection if, and only if,

(i) w^{ϕ} fixes at most one element of {1, …, ℓ} and, for every transposition (i, j) contained in the cycle decomposition of ϕ(w), the cycle occurring in w is (i, j, −i, −j) or (j, i, −j, −i); or

(ii) w^{ϕ} has exactly two fixed points, say i and j, and the cycle decomposition of

w contains (i, −i)(j)(−j) or (i)(−i)(j, −j). The number of elements of the type (ii) is clearly \binom{ℓ}{2}d_{ℓ−2}2^{ℓ−2}(ℓ − 2)!, contributing

lim_{ℓ→∞} \frac{\binom{ℓ}{2}2^{ℓ−2}d_{ℓ−2}(ℓ − 2)!}{|W (D_{ℓ})|} = lim_{ℓ→∞} 2^{−2}d_{ℓ−2} = \frac{1}{4e}

to the required asymptotic proportion.

Writing T_{ℓ} for elements of W such that w^{ϕ} fixes at most two elements and

T_{ℓ}^{i,j} = {w ∈ T_{ℓ} | w contains (i, j)(−i, −j) or (i, −j)(j, −i)},

we find that the set of elements of type (i) is

T_{ℓ} − ⋃_{1≤i<j≤ℓ} T_{ℓ}^{i,j}.

Again, we take alternating sums over h-tuples of commuting transpositions in ϕ(W). As each transposition in the decomposition of an element of ϕ(w) corresponds to two 4-cycles as indicated above, we find the same factor 2^{h} as for the B_{ℓ} case:

∑_{h=0}^{⌊ℓ/2⌋}(−1)^{h}\binom{ℓ}{2h}\frac{(2h)!}{2^{h}h!}2^{h}|T_{ℓ−2h}|.

As |T_{ℓ}| = 2^{ℓ−1} ℓ! (d_{ℓ} + d_{ℓ−1}), the result is

∑_{h=0}^{⌊ℓ/2⌋} (−\frac{1}{4})^{h} (d_{ℓ−2h} + d_{ℓ−2h−1}) ,

which contributes

lim_{m→∞} \frac{f}{2^{ℓ}ℓ!} = ∑_{h=0}^{∞} (−\frac{1}{4})^{h} \frac{1}{h!} \frac{2}{e} = 2e^{− \frac{1}{4}} e^{−1} = 2e^{− \frac{5}{4}}

to the required proportion. Hence, the asymptotic proportion is (4e)^{−1} + 2e^{−5/4}.

The exceptional types: These were computed by machine. □

Corollary 6.4. The proportion of reflection derangements in a Weyl group is less than \frac{2}{3}.

Proof. Recall that if a_{n} > 0 converges monotonically to zero, then ∑_{i=0}^{∞}(−1)^{i}a_{i} is called an alternating series. The maximum value of the partial sums s_{n} = ∑_{i=0}^{n}(−1)^{i}a_{i} of such a series is one of the first two partial sums. Since the series in the previous proposition are sums of alternating sequences, it is always possible to find a constant M such that the maximum value of the partial sums is one of s_{1}, …, s_{M}. It is now easy to show on a case-by-case basis that the proportion of reflection derangements in an irreducible Weyl group is at most \frac{2}{3}.

If W is a direct product decomposition into s irreducible Weyl groups, then an element of W is a reflection derangement if and only if each component of w is a reflection arrangement, and so their proportion is at most (\frac{2}{3})^{s} ≤ \frac{2}{3}. □

Together with Proposition 6.1, this shows that the chance of finding a regular semisimple element of L corresponding to a reflection nonderangement in the Weyl group is at least one third, provided q is large enough. To complete the analysis, we need a more precise bound on the probability of finding certain regular semisimple elements.

6.3. Time analysis. We start by looking at the Coxeter class in the Weyl group. The Coxeter element is actually a reflection derangement, but this proof is the model for our next result.

Proposition 6.5. Suppose that W is an irreducible Weyl group. If w_{c} is a Coxeter element of W, then

\frac{|L_{rss,w_{c}}(k)|}{|L(k)|} ≥ (1 − \frac{ℓ}{q^{ℓ/2}} ) (1 − \frac{1}{q})^{4} \frac{1}{h}

where h is the order of w_{c}.

Proof. Suppose α is a root and αw_{c}^{m} is a linear combination of α, αw_{c}, …, αw_{c}^{m−1}. We prove that m ≥ ℓ/2 on a case-by-case basis:

Type A_{ℓ}: Identify W with Sym_{ℓ+1} and consider Φ to consist of roots e_{i} − e_{j} with i ≠ j. We can take w_{c} = (1, 2, …, ℓ + 1) and α = e_{i} − e_{j}. So αw_{c}^{m} = e_{i+m} − e_{j+m} with the subscripts taken modulo ℓ + 1. Hence αw_{c}^{m} is a linear combination of α, …, αw_{c}^{m} iff i + m and j + m are both in [i, i + m − 1] ∪ [j, j + m − 1] modulo ℓ + 1. By the pigeon hole principle, this can only happen if m ≥ (ℓ + 1)/2.

Type C_{ℓ}: Identify W with the set of permutations w of {±1, …, ±ℓ} such that (−i)w = −(iw) for i = 1, …, ℓ. Consider Φ = Φ(C_{ℓ}) to consist of roots εe_{i} − δe_{j} with ε, δ ∈ {±1}, i, j = 1, …, ℓ and εi ≠ δj. We can take

w_{c} = (1, 2, …, ℓ, −1, −2, …, −ℓ)

and α = εe_{i} − δe_{j}. The same argument used in type A_{ℓ} now shows that m ≥ ℓ/2.

Type B_{ℓ}: The permutation action of W (B_{ℓ}) on its roots is isomorphic to the action of W (C_{ℓ}) on its roots, so the same argument works.

Types D_{ℓ}: Identify W with the elements of W (C_{ℓ}) such that ∏_{i=1}^{ℓ}(iw) > 0 and consider Φ to consist of the roots εe_{i} − δe_{j} with ε, δ ∈ {±1}, i, j = 1, …, ℓ and i ≠ j. We can take w_{c} = (1, 2, …, ℓ−1, −1, −2, …, −ℓ+1)(ℓ, −ℓ) and α = εe_{i}−δe_{j}. Once again m ≥ ℓ/2 if i, j ≠ ℓ. If i = ℓ, j ≠ ℓ, then αw_{c}^{m} = (−1)^{m}εe_{ℓ} − δe_{j+m} with the second subscript taken modulo ℓ − 1, and so m ≥ ℓ − 1.

Exceptional types: These are easily checked by computer.

A_{ℓ}  ∏_{i=1}^{ℓ}(1 − X^{i})
B_{ℓ}, C_{ℓ} (1 − X^{ℓ}) ∏_{i=1}^{ℓ−1}(1 − X^{2i})
D_{ℓ}  ∏_{i∈{1,ℓ−1,ℓ}}(1 − X^{i}) ∏_{i=2}^{ℓ−2}(1 − X^{2i})
G_{2}  (1 − X^{2})(1 − X^{3})(1 + X)
F_{4}  (1 − X^{6}) ∏_{i∈{4,6,8}}(1 − X^{i})
E_{6}  (1 − X^{6}) ∏_{i∈{1,4,5,6,8}}(1 − X^{i})(1 + X^{3} + X^{6})
E_{7}  (1 − X^{6}) ∏_{i∈{1,6,8,10,12,14}}(1 − X^{i})(1 + X^{3} + X^{6})
E_{8}  ∏_{i∈{1,8,10,12,14,18,20,24}}(1 − X^{i})(1 + X^{3})(1 + X^{5} + X^{10})

Table 1. The functions Q_{w}(X) for a Coxeter element w

It is well known that every orbit of w_{c} on Φ has size h, so ∑_{i} c_{i}(w_{c}) = 2N/h = ℓ. We have shown that c_{i}(w_{c}) = 0 for i < ℓ/2, so

1 − ∑_{i=1}^{ℓ} \frac{c_{i}(w_{c})}{q^{i}} ≥ 1 − \frac{ℓ}{q^{ℓ/2}} .

The functions Q_{w_{c}}(X) are straightforward to compute and are given in Table 1. The terms in which every coefficient is positive can be ignored, since they are bounded below by 1 when we set X = 1/q. Since no term 1 − X^{a} appears more than twice in these polynomials and q ≥ 3, it follows by Lemma 6.2 that Q_{w_{c}}(1/q) ≥ (1 − 1/q)^{4}.

The required inequality now follows from the first inequality of Proposition 6.1 and the fact that the centraliser of w_{c} has order h. □

We now consider reflection nonderangements that are, in some sense, close to being Coxeter elements.

Proposition 6.6. Suppose that W is an irreducible Weyl group of rank greater than one. If W is classical with rank at least 7 then there is a reflection nonderangement w such that

\frac{|L_{rss,w}(k)|}{|L(k)|} ≥ (1 − \frac{3}{q} − \frac{4}{q^{2}} − \frac{ℓ + 5}{q^{(ℓ−2)/2}} ) (1 − \frac{1}{q})^{6} \frac{1}{4ℓ}.

For other Cartan types there is a reflection nonderangement w such that

\frac{|L_{rss,w}(k)|}{|L(k)|} ≥ (1 − ∑_{i=1} \frac{c_{i}}{q^{i}} ) (1 − \frac{1}{q})^{6} \frac{1}{c}.

with the constants c and c_{i} listed in Table 2.

Proof. Fix a root β. Assume β is short (resp. long) for Cartan type B_{ℓ} (resp. C_{ℓ}). Let Φ_{β} = {γ ∈ Φ | ⟨γ, β^{⋆}⟩ = 0}. Then Φ_{β} is a subsystem of W and, except in type D_{4}, it has at most two irreducible components. Let Φ′_{β} be the irreducible summand of Φ_{β} of maximal rank. Let s_{β} be the reflection in β and let w_{β} be the Coxeter element of W (Φ′_{β}). We take w = s_{β}w_{β}, except for type A_{1} where we use w = 1, type G_{2} where we use w = s_{β}, and type D_{4} where we use s_{1}s_{2}s_{1}s_{3}s_{2}s_{1}s_{4}s_{2}s_{1}s_{3}s_{2}. (Here s_{i} is the ith simple reflection, with the numbering given in [Bou75].) These elements are all reflection nonderangements.

ALGORITHM FOR LANG’S THEOREM 25

Type c  c_{1} c_{2} c_{3} c_{4} c_{5} c_{6} c_{7} c_{8}
A_{1}  2  1
A_{2}  2  1 2
B_{2}  8  4 0
G_{2}  4  3 4
A_{3}  8  2 4 0
B_{3}  8  1 2 2
A_{4}  6  1 2 0 2
B_{4}  12 1 1 4 0
D_{4}  16 5 8 0 0
F_{4}  36 3 1 6 0
A_{5} 8 1 1 2 4 0
B_{5}  16 1 0 0 4 2
D_{5}  16 3 5 2 4 0
A_{6}  10 1 0 0 4 0 2
B_{6}  20 1 0 0 2 5 0
D_{6}  24 3 5 3 4 0 0
E_{6}  36 3 0 3 2 6 0
E_{7}  60 3 0 0 2 10 0 0
E_{8}  108 3 0 0 0 0 4 9 0

Table 2. The constants c and c_{i} for small rank and exceptionals

First we prove that

∑_{i=1} \frac{c_{i}}{q^{i}} ≤ \frac{3}{q} + \frac{4}{q^{2}} + \frac{ℓ + 5}{q^{(ℓ−2)/2}}

for the classical types of rank at least 7. Type A_{ℓ}: Assume β = e_{1} − e_{2}. Then Φ_{β} has type A_{ℓ−2}, and so orbits within Φ_{β} contribute at most \frac{ℓ−2}{q^{(ℓ−2)/2}} to the sum, as in the previous proof. If α ∉ Φ_{β}, then α = ±(e_{i} − e_{j}) where i = 1 or 2 and j > 2. These roots form one orbit of size 2 and either two orbits of size ℓ − 1 or one orbit of size 2(ℓ − 1). So these orbits contribute at most 1/q + 2/q^{ℓ}. Type B_{ℓ} with β short: Assume β = e_{1} − e_{2}. Then Φ_{β} has type B_{ℓ−1}, and so the orbits within Φ_{β} contribute at most \frac{ℓ−1}{q^{(ℓ−1)/2}} . If α ∉ Φ_{β}, then α = εe_{i} − δe_{j} where i = 1 or 2 and j > 2. These roots form four orbits of size two with m = 1 and four orbits with m = ℓ − 2. Type C_{ℓ} with β long: This is similar to type B_{ℓ}, with the short roots and long roots exchanged. Type D_{ℓ}: Assume β = e_{1}−e_{2}. Then Φ_{β} has type D_{ℓ−2} A_{1} and Φ′_{β} is the subsystem of type D_{ℓ−2}. So the orbits within Φ′_{β} contribute at most \frac{ℓ−2}{q^{(ℓ−1)/2}} to the sum. If α ∉ Φ′_{β}, then α = εe_{i} − δe_{j} where i = 1 or 2 and j > 2. These roots form at most four orbits with m = ℓ − 2.

The values of the constants in Table 2 are easily computed in Magma. The constant c is just |C_{W} (w)|. The functions Q_{w}(X) are given in Table 3. Applying

A_{1}  1 − X
A_{2}  1 − X^{3}
A_{3}  (1 − X)(1 − X^{3})(1 + X^{2})
A_{ℓ} (ℓ > 3)  ∏_{i∈{1,...,ℓ+1}\{2,ℓ−1}}(1 − X^{i})
B_{2}, C_{2}  (1 − X)^{2}(1 + X^{2})
B_{3}, C_{3}  (1 − X)(1 − X^{2})(1 − X^{6})
B_{4}, C_{4}  (1 − X)(1 − X^{3})(1 − X^{4})(1 − X^{8})
B_{ℓ}, C_{ℓ} (ℓ > 4) (1 − X)(1 − X^{ℓ−2})^{(3−(−1)^{ℓ})/2} ∏_{i∈{2,...,ℓ}\{ℓ−1}}(1 − X^{2i})
D_{4}  (1 − X)^{2}(1 + X^{6})(1 + X^{2})^{2}
D_{5}  (1 − X)^{3}(1 − X^{5})(1 − X^{6})(1 + X^{2})(1 + X^{4})
D_{6}  (1 − X)^{3}(1 − X^{3})(1 − X^{6})(1 − X^{10})(1 + X^{2})^{2}(1 + X^{4})
D_{ℓ} (ℓ > 6)  (1 − X)^{3} ∏_{i∈{ℓ−3,ℓ}}(1 − X^{i}) ∏_{i∈{4,...,ℓ−1}\{ℓ−3}}(1 − X^{2i})×

(1 + X^{2})(1 + X^{2} + X^{4})

G_{2}  1 − X^{6}
F_{4}  ∏_{i∈{1,3,8,12}}(1 − X^{i})
E_{6}  (1 − X)^{2} ∏_{i∈{5,8,9,12}}(1 − X^{i})
E_{7}  (1 − X)^{2} ∏_{i∈{5,6,12,14,18}}(1 − X^{i})(1 + X^{2})(1 + X^{4})
E_{8}  (1 − X)^{2} ∏_{i∈{6,12,14,20,24,30}}(1 − X^{i})×

(1 + X^{2})(1 + X^{4})(1 + X^{3} + X^{6})

Table 3. The functions Q_{w}(X)

Lemma 6.2, we get Q_{w}(1/q) ≥ (1 − 1/q)^{6}.

For groups not covered in Table 2, let h_{β} be the Coxeter number of Φ′_{β}. Then the centraliser of w_{β} in W (Φ′_{β}) has order h_{β}, and the centraliser of w in W has order 2h_{β} ≤ 4ℓ. The required result now follows from the first inequality of Proposition 6.1. □

Finally we are in a position to give an analysis of our algorithm. We refer to Algorithm 10, a version of Algorithm 8 which searches for maximal toral subalgebras corresponding to reflection nonderangements. As discussed in Subsection 6.2, finding f with deg(f) = 1, or deg(f) = 2 and f = f_{−} is equivalent to the corresponding Weyl group element being a reflection nonderangement. When deg(f) = 2 and f = f_{−}, we have always found in practice that M/Z is of type A_{1}, and so has dimension 3. We do not have a proof of this however, so it is necessary to check and then decompose over the field extension k_{2} in the unlikely event that we get a larger subalgebra.

Theorem 6.7. Suppose that the characteristic of k is greater than 3. Let G be a k-split connected reductive group and let L be the Lie algebra of G. We can find a split maximal toral subalgebra of L in Las Vegas time O(n^{3}ℓ^{6} log^{2}(ℓ) log^{2}(q)).

Proof. Before calling Algorithm 10, we compute the centre of L, which takes time O((n+ℓ^{2})^{3} log(q)). Using Algorithm 7, we can assume G is simple. As indicated in Algorithm 10, the computations within the main loop take time O(ℓ^{7} log(ℓ) log^{2}(q)).

SplitMaximalToralSubalgebra := function(L, Z)

repeat let H/Z = MaximalToralSubalgebra(L/Z) O(ℓ^{6} log(q)) if H is split then return H O(ℓ^{7} log(q)) let ℱ = GeneralisedRoots(L/Z, H/Z) O(ℓ^{7} log(ℓ) log^{2}(q)) if there exists f ∈ ℱ with deg(f) = 1 then

let M/Z := ⟨ϕ((L/Z)_{f} + (L/Z)_{f_{−}})⟩ O(ℓ^{6} log(q)) elif there exists f ∈ ℱ with deg(f) = 2 and f = f_{−} then

let M/Z := ⟨ϕ((L/Z)_{f}⟩ O(ℓ^{6} log(q))

if dim(M/Z) ≠ 3 then find α in Φ_{f} over k_{2} O(ℓ log^{2}(q)) let M/Z = ⟨ϕ((L/Z)_{α} + (L/Z)_{−α})⟩ O(ℓ^{6} log(q))

end if until M is defined O(ℓ log(ℓ)) times let H = SplitMaximalToralSubalgebra(M, ϕ(Z(M/Z))) let C = ϕ(C_{L/Z}(H)) and Z = ϕ(Z(C/Z)) let K = Z for M in Components(C, H) do

let K = K + SplitMaximalToralSubalgebra(M, Z) end for return K

end function

algorithm 10. Finding a split maximal toral subalgebra

By Proposition 6.6, if G is classical with rank at least 7, we obtain a split toral subalgebra M with probability at least

(1 − \frac{1}{q})^{6} (1 − \frac{3}{q} − \frac{4}{q^{2}} − \frac{ℓ + 5}{q^{(ℓ−2)/2}} ) \frac{1}{4ℓ}.

For q ≥ 5 and ℓ ≥ 7, this is at least

(\frac{4}{5})^{6} (1 − \frac{3}{5} − \frac{4}{25} − \frac{12}{5^{5/2}} ) \frac{1}{4ℓ} > 0.

Similarly for the Cartan types in Table 2, except for D_{4},

(1 − ∑_{i=1} \frac{c_{i}}{q^{i}} ) (1 − \frac{1}{q})^{6} \frac{1}{c} ≥ (1 − ∑_{i=1} \frac{c_{i}}{5^{i}} ) (1 − \frac{1}{5})^{6} \frac{1}{c} > 0.

For type D_{4}, the bound is negative for q = 5, but positive for q ≥ 7. So it remains to consider the Lie algebra D_{4}(5). But for any fixed Lie algebra, it is easily seen that there is a nonzero chance of the algorithm working, since there is a chance that the toral subalgebra found by Algorithm 5 is already split. We have now shown that there is a constant C > 0 such that the probability of success after one iteration of the main loop is at least C/ℓ.

Since

lim_{ℓ→∞} (1 − \frac{C}{ℓ} )^{aℓ} = e^{−aC},

we can choose a such that

(1 − \frac{C}{ℓ} )^{aℓ} ≤ \frac{1}{e^{4}}

for all ℓ. Hence the probability of failure after aℓ log(ℓ) repetitions of the loop is at most

(1 − \frac{C}{ℓ} )^{aℓ log(ℓ)} ≤ (\frac{1}{e^{4}} )^{log(ℓ)} = \frac{1}{ℓ^{4}} .

Clearly the depth of recursion is at most ℓ, which contributes a further factor of ℓ to our timing. The ranks of all the subalgebras in all the calls at a particular depth sum to at most ℓ, so the total number of recursive calls is at most ℓ^{2}. Hence the overall probability of success is at least

(1 − \frac{1}{ℓ^{4}} )^{ℓ^{2}} ≥ (1 − \frac{1}{2ℓ^{2}} )^{ℓ^{2}} ≥ \frac{1}{2}.

Hence Algorithm 10 takes Las Vegas time O(ℓ^{9} log^{2}(ℓ) log^{2}(q)). Combining this with the preprocessing time of O((n + ℓ^{2})^{3} log(q)), and using the fact that n ≥ ℓ we get the desired result. □

Corollary 6.8. Suppose that the characteristic of k is greater than 3. Let G be a k-split connected reductive group and let L be the Lie algebra of G. We can find a Chevalley basis of L in Las Vegas time O(n^{3}ℓ^{6} log^{2}(ℓ) log^{2}(q)).

Proof. The time taken to find a split maximal toral subalgebra clearly dominates the time for Algorithm 9. □

We can easily decompose G into simple subgroups, since we know its root datum. Hence, combining this corollary with Proposition 4.3, we see that the algorithm for Lang’s Theorem takes Las Vegas time

O(n^{3}ℓ^{6} log^{2}(ℓ) log^{2}(q) + n^{8}r^{2}s^{2} log^{2}(q)),

which is easily simplified to the expression in Theorem 1.2.

References

[Bab97] László Babai, Randomization in group algorithms: conceptual questions, Groups and computation, II (New Brunswick, NJ, 1995), Amer. Math. Soc., Providence, RI, 1997, pp. 1–17.

[Bou75] N. Bourbaki, Éléments de mathématique, Hermann, Paris, 1975, Fasc. XXXVIII: Groupes et algèbres de Lie. Chapitre VII: Sous-algèbres de Cartan, éléments réguliers. Chapitre VIII: Algèbres de Lie semi-simples déployées, Actualités Scientifiques et Industrielles, No. 1364.

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

[Car93] , Finite groups of Lie type, John Wiley & Sons Ltd., Chichester, 1993, Conjugacy classes and complex characters, Reprint of the 1985 original, A Wiley-Interscience Publication.

[CLG97] Frank Celler and C. R. Leedham-Green, Calculating the order of an invertible matrix, Groups and computation, II (New Brunswick, NJ, 1995), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 28, Amer. Math. Soc., Providence, RI, 1997, pp. 55–60. MR MR1444130 (98g:20001)

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

[dGIR96] Willem de Graaf, Gábor Ivanyos, and Lajos Rónyai, Computing Cartan subalgebras of Lie algebras, Appl. Algebra Engrg. Comm. Comput. 7 (1996), no. 5, 339–349. MR 98m:17001

[GH97] S. P. Glasby and R. B. Howlett, Writing representations over minimal fields, Comm. Algebra 25 (1997), no. 6, 1703–1711. MR 98c:20019

[Gro02] Larry C. Grove, Classical groups and geometric algebra, Graduate Studies in Mathematics, vol. 39, American Mathematical Society, Providence, RI, 2002. MR MR1859189 (2002m:20071)

[Hog82] G. M. D. Hogeweij, Almost-classical Lie algebras. I, II, Nederl. Akad. Wetensch. Indag. Math. 44 (1982), no. 4, 441–452, 453–460. MR MR683531 (84f:17007)

[Hum67] James E. Humphreys, Algebraic groups and modular Lie algebras, Memoirs of the American Mathematical Society, No. 71, American Mathematical Society, Providence, R.I., 1967. MR 36 #169

[Hum75] , Linear algebraic groups, Springer-Verlag, New York, 1975, Graduate Texts in Mathematics, No. 21.

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

[Jac62] Nathan Jacobson, Lie algebras, Interscience Publishers (a division of John Wiley & Sons), New York-London, 1962, Interscience Tracts in Pure and Applied Mathematics, No. 10.

[Leh92] G. I. Lehrer, Rational tori, semisimple orbits and the topology of hyperplane complements, Comment. Math. Helv. 67 (1992), no. 2, 226–251. MR 93e:20065

[Leh98] , The cohomology of the regular semisimple variety, J. Algebra 199 (1998), no. 2, 666–689. MR MR1489931 (98k:20080)

[LN97] Rudolf Lidl and Harald Niederreiter, Finite fields, second ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997, With a foreword by P. M. Cohn. MR 97i:11115

[Mül03] Peter Müller, Algebraic groups over finite fields, a quick proof of Lang’s theorem, Proc.

Amer. Math. Soc. 131 (2003), no. 2, 369–370 (electronic). MR 2003i:20088

[Sel67] George B. Seligman, Some results on Lie p-algebras, Bull. Amer. Math. Soc. 73 (1967), 528–530. MR MR0219585 (36 #2664)

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

[SV00] Tonny A. Springer and Ferdinand D. Veldkamp, Octonions, Jordan algebras and exceptional groups, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2000. MR MR1763974 (2001f:17006)

[vzGG03] Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, second ed., Cambridge University Press, Cambridge, 2003. MR MR2001757 (2004g:68202)