A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

arXiv:1706.05697v1 [math.GR] 18 Jun 2017

JOHN N. BRAY AND HENRIK BÄÄRNHIELM
Abstract. We present a new algorithm for constructive recognition of the
Suzuki groups in their natural representations. The algorithm runs in Las
Vegas polynomial time given a discrete logarithm oracle. An implementation
is available in the Magma computer algebra system.

1. Introduction
In [1] and [2], algorithms for constructive recognition of the Suzuki groups in the
natural representation are presented. They depend on a technical conjecture, which
is still open, although supported by substantial experimental evidence.
Here we present a new algorithm for this problem, which does not depend on
any such conjectures, and which is also more efficient.
We shall use the notation of [2], but for completeness we state the important
points here. The ground finite field is Fq where q = 22m+1 for some m > 0, and we
2
define t = 2m+1 so that xt = x2 for every x ∈ Fq . For a, b ∈ Fq and λ ∈ F×
q , define
the following matrices.


1
0 0 0

a
1 0 0
,
(1)
U (a, b) = 
 at+1 + b
at 1 0 
at+2 + ab + bt b a 1

 t+1
λ
0
0
0
 0
λ
0
0 
,
(2)
M ′ (λ) = 
−1
 0
0 λ
0 
−t−1
0
0
0
λ


0 0 0 1
0 0 1 0

(3)
T =
 0 1 0 0 .
1 0 0 0
If ω ∈ Fq is a primitive element, then Sz(q) = hU (1, 0), M ′ (ω), T i. This is our
standard copy of Sz(q), denoted Σ. This group acts on the Suzuki ovoid, which is

(4)
O = {(1 : 0 : 0 : 0)} ∪ (at+2 + ab + bt : b : a : 1) | a, b ∈ Fq .
 ′
×
Let F = { U (a, b) | a, b ∈ Fq } and H = M (λ) | λ ∈ Fq . Then F H = HF is
the stabiliser of (1 : 0 : 0 : 0) ∈ O, a maximal subgroup of Sz(q) and F H =
hU (1, 0), M ′ (ω)i ∼
= Fq .Fq .F×
q . The group Sz(q) is partitioned into two sets as
Sz(q) = F H ∪ F HT F = HF ∪ HF T F .
c

(5)

If G is a conjugate of Sz(q), so that G = Sz(q) for some c ∈ GL(4, q), we say
that the ordered triple of elements α, h, γ ∈ G are rewriting generators for G with
respect to c if
• αc ∈ F , hc ∈ F H, γ c = T ,
• α has order 4 and h has odd order not dividing r − 1 for any r such that q
is a non-trivial power of r.
1

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

2

Note that these conditions imply that G = hα, h, γi.
The main results are Theorem 8 and 9. The following result is a consequence:
Theorem 1. Given a random element oracle for subgroups of GL(4, q) and an
oracle for the discrete logarithm problem in Fq :
• There exists a Las Vegas algorithm that, given a conjugate G = hXi of Σ,
g
constructs g ∈ GL(4, q) such that hXi = Σ and also constructs rewriting
generators for G with respect to g as SLPs in X. The algorithm has expected
time complexity O log(q) log log(q) field operations.
• Let h ∈ GL(4, F ). Then:

(1) We can determine whether h ∈ G in time O 1 field operations.
(2) Given some preprocessing that is independent of h, and given that
h ∈ G, we can construct h as an SLP in X in time O log(q) field
operations. The preprocessing, which only has to be done
 once per constructive recognition of G, has complexity O (log(q))2 .
2. Overview
The group G = Sz(q) acts doubly transitively on O. In [2, Corollary 4.8], an
algorithm for constructing a generating set of a stabiliser of a given point P ∈ O is
described. The generators are constructed as SLPs in a given generating set X for
Sz(q).
This is then used in [2, Theorem 5.2] to obtain generating sets for the stabilisers
of the two points P∞ = (1 : 0 : 0 : 0) and P0 = (0 : 0 : 0 : 1), which consist
of lower and upper triangular matrices, respectively. These stabilisers are used in
constructive membership testing to convert any given g ∈ Sz(q) to an SLP in X,
given as [2, Algorithm 2].
In the natural representation, the constructive recognition problem reduces to
the construction of a conjugating matrix, and [2, Theorem 5.2] is also used.
The new algorithm presented here replaces the central task of constructing a
point stabiliser with a new method. A difference compared to the old method is
that the stabilised point of O is not part of the input, instead a random point
stabiliser is constructed. We therefore obtain two random point stabilisers of the
input group, but it turns out that we can construct a matrix that conjugates the
input group to G and also the two point stabilisers to GP∞ and GP0 . This is done
using a simplified version of [2, Lemma 7.4]. After that we perform constructive
membership testing with a method similar to [2, Theorem 5.2], but here we present
a deterministic algorithm instead of a probabilistic one.
3. Constructing a point stabiliser
The algorithm consists of two parts. The second part is an adaptation of [7,
Theorem 17] for the natural representation. This is given as Theorem 7.
The first part is the algorithm that constructs an element of order 4, to be used
as input to the algorithm in Theorem 7. This is presented as Algorithm 1. We use
Matn (F ) to denote the algebra of n by n matrices over the field F . To calculate the
pseudo-order of a matrix, we use [9] (see also [10, Section 2.2]). Note that we do not
need to compute precise orders, hence large integer factorisation can be avoided.
On the other hand, it turns out that one can use integer factorisation to avoid some
potential discrete logarithm calculations.
We make use of a discrete logarithm oracle DiscreteLog(λ, a), which returns
k > 0 such that λk = a, or −1 if no such number exists, that is if a ∈
/ hλi 6 F×
q . We
also make use of a random element oracle Random(G) that returns independent
random elements of a group G = hXi as SLPs in X. This is polynomial time by [4];

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

3

in practice we use the product replacement algorithm [8], which is also polynomial
time by [11].
We construct an element of order 4 by constructing elements of trace 0. In G,
the elements of trace 0 have orders 1, 2 or 4.
Algorithm 1: Order4Elt(G)
Input: Group G = hXi where X ⊆ GL(4, q) such that G ∼
= Sz(q).
Output: Element f ∈ G as SLP in X, such that |f | = 4.
1 g := Random(G)
2 if |g| | q − 1 and g 6= 1 then
3
u, c, λ := Diagonalise(g)
4
✄ Now u = g c where u = diag(λt+1 , λ, λ−1 , λ−t−1 ) ∈ G and c ∈ GL(4, q)
5
h := Random(G)
6
B := hc
7
if uB 6= u−1 then
8
A := diag(xy, x, x−1 , x−1 y −1 ) ∈ Mat4 (Fq (x, y))
9
eqns := {Tr(AB) = 0, Tr(AB)t = 0}
10
✄ eqns determines 2 polynomial equations in x and y (with y used for xt )
11
if eqns has a root (r, rt ) for (x, y) where r ∈ F×
q then
12
fˆ := diag(rt+1 , r, r−1 , r−t−1 )B
13
if fˆ = 4 then
14
15
16
17
18
19
20

i := DiscreteLog(λ, r)
✄ This will return −1 if r ∈
/ hλi
if i > 0 then
✄ Now λi = r
f := g i h
✄ Now f is an SLP in X and fˆ = f c
return f
end
end
end

end
end
21 return fail
Lemma 2. With u and B as in Algorithm 1, there is a diagonal matrix δ ∈ GL(4, q)
such that uδ = u and B δ lie in Σ.
Proof. Let ∆ be the subgroup of diagonal matrices of GL(4, q).
We observe that λt+1 , λ, λ−1 , λ−t−1 are distinct elements of F×
q , since λ 6= 1
(enforced by g 6= 1). For example, if λt+1 = λ−1 , we obtain λt+2 = 1, and raising
to the power of 1 − (t/2) gives us λ = 1. Thus CGL(4,q) (u) = ∆.
The normaliser of hui in GL(4, q) must permute the eigenspaces of u, and thus
any element therein must raise u to one of the powers ±1, ±(t+ 1). We observe that
2
T inverts u, while u±(t+1) has eigenvalues λ±(t+1) , λ±(t+1) . Therefore, if u±(t+1)
2
is conjugate in GL(4, q) to u or u−1 , then λ(t+1) = λ or λ−1 . But (t + 1)2 =
2q + 2t+ 1 ≡ 2t+ 3 mod q − 1, and so we get λ2t+3 = λ or λ−1 . Now 2t+ 2 and 2t+ 4
are invertible powers when applied to F×
q , and so λ = 1. This contradiction implies
that u is not conjugate in GL(4, q) to u±(t+1) . Thus NGL(4,q) (hui) = ∆ hT i = hT i ∆.
Now it is well-known that all copies of Sz(q) in GL(4, q) are conjugate therein. Notice also that (u, B) = (g, h)c . Thus hu, Biγ1 6 Σ for some γ1 ∈ GL(4, q). Moreover,
there is γ2 ∈ Σ such that (uγ1 )γ2 is a diagonal matrix diag(µt+1 , µ, µ−1 , µ−(t+1) ).
Naturally, the eigenvalues of this diagonal matrix coincide with the eigenvalues of

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

4

u, and the argument of the previous paragraph now shows that µ = λ±1 . Therefore uγ1 γ2 = u±1 . So γ1 γ2 normalises hui, and so γ1 γ2 = δζ, where δ ∈ ∆ and
δ
γ
ζ = ζ −1 = T j for some j ∈ {0, 1}. Thus hu, Bi = (hu, Bi 1 )γ2 ζ 6 Σγ2 ζ = Σ, since
γ2 , ζ ∈ Σ, and this establishes our claim.

The next theorem asserts that the equations we have to solve in Algorithm 1
have few solutions (with one exception) and also provides a way of reducing the
problem of their solution to finding roots of a univariate polynomial of degree at
most 4 over Fq . To summarise the next theorem, let the diagonal entries of B be
a, b, c, d. Line 11 is then done as follows:
• Line 7 excludes the case a = b = c = d = 0.
• If exactly three of a, b, c, d are 0, then the equations at line 9 have no
solutions of the required type.
• If a = b = 0 and c, d 6= 0 then y = d/c.
• If c = d = 0 and a, b 6= 0 then y = b/a.
• In all other cases, equation (8) is a non-degenerate univariate polynomial
equation in y, and we consider all non-zero roots of this. The roots can be
found using [13, Algorithm 14.10].
For each value of y obtained above, we set x = y t/2 and check if equation (6) holds.
This provides the values r at line 11. (There is no need to check equation (7) since
it will automatically hold if (6) does.)
Theorem 3. The equations at line 11 in Algorithm 1 determine at most four
solutions for x, except when B is an involution that inverts u.
Proof. In the general case, we establish that y is the root of a non-zero univariate
polynomial of degree at most 4. Exceptional cases are dealt with explicitly.
The analysis of one of the cases becomes simpler if B is in our standard copy Σ.
By Lemma 2, there is a diagonal matrix δ such that B δ is in Σ. Note that Aδ = A,
and so Tr(AB δ ) = Tr(Aδ B δ ) = Tr((AB)δ ) = Tr(AB). In fact, B and B δ have the
same diagonal entries. The upshot is that Tr(AB ′ ) = Tr(AB ′ )t = 0 gives the same
equations for both B ′ = B and B ′ = B δ . From now on, we presume that B (the
old value of B δ ) has been standardised to lie in Σ.
We have Tr(AB) = axy + bx + cx−1 + dx−1 y −1 , where a = B11 , b = B22 , c = B33
and d = B44 . Multiplying through by xy and also considering Tr(AB)t gives us:
ax2 y 2 + bx2 y + cy + d = 0,
t 4 2

a x y + bt x2 y 2 + ct x2 + dt = 0.

(6)
(7)

We now try to solve these equations. Note that x and y determine each other via
y = xt and x = y t/2 . We now let
p1 = (aat y 3 + at by 2 )x2 + abt y 3 + bbt y 2 + at cy 2 + act y + at dy + bct
and p2 = a2 y 3 + b2 y. Evaluating p1 × (6) + p2 × (7) gives us

abt cy 4 + (a2 dt + abt d + at c2 + bbt c)y 3 + (acct + bbt d)y 2
+(act d + at d2 + b2 dt + bcct )y + bct d = 0.

(8)

(The values of p1 and p2 may be obtained using polynomial division to divide
Tr(AB)t xt y t by Tr(AB)xy, treating x2 as the variable and everything else as a
constant.)
Clearly, (8) reduces to the trivial equation 0 = 0 whenever a = b = 0 or c = d = 0.
We now show that it is non-trivial in all other cases, in which case y is a root of a
non-trivial polynomial equation of degree at most 4 (over Fq ), and thus can have at
most four values. (Note that a solution to (8) does not necessarily yield a solution
to the original equations (6) and (7).) By inspecting the coefficients of y 4 and 1 in

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

5

(8), we see that this equation can only be trivial if abt c = bct d = 0, putting us in
one of the three cases a = d = 0, b = 0 or c = 0, which we now analyse separately
below.
M-I. If a = d = 0, (8) reduces to bbt cy 3 + bcct y = 0 (so bbt cy 2 + bcct = 0). If
b = 0 or c = 0, then we are in one of the excluded cases a = b = 0 or c = d = 0,
and if b, c 6= 0 we get bt y 2 + ct = 0, with unique solution y = (c/b)t/2 .
M-II. If b = 0, (8) reduces to y(a2 dt y 2 +at c2 y 2 +acct y +act d+at d2 ) = 0. Because
of the excluded case a = b = 0, we may assume that a 6= 0. So for this equation to
be identically zero, c must be 0 (coefficient of y 2 ), giving us y(a2 dt y 2 + at d2 ) = 0,
and thus forcing a2 dt = at d2 = 0. Since a 6= 0 this forces d2 = 0, whence d = 0.
But c = d = 0 is also an excluded case.
M-III. If c = 0, (8) reduces to y(a2 dt y 2 + abt dy 2 + bbt dy + at d2 + b2 dt ) = 0. We
have d 6= 0, since we are excluding c = d = 0, so for a degenerate equation we need
b = 0 (from the coefficient of y 2 ). This also implies that we need a2 dt = at d2 = 0.
So a = 0 (as d 6= 0), putting us in another excluded case, namely a = b = 0.
We now deal with the cases when (8) is identically zero, namely a = b = 0 and
c = d = 0. With the exception of the case a = b = c = d = 0, the original equations
(6) and (7) are not identically zero.
S-I. a = b = 0, c, d 6= 0. In this case y = d/c, from (6).
S-II. c = d = 0, a, b 6= 0. In this case y = b/a, from (6), as x2 y 6= 0.
S-III. Exactly three of a, b, c, d are 0. Now (6) reduces to one of ax2 y 2 = 0,
2
bx y = 0, cy = 0 or d = 0, which have no solutions, since we want x, y 6= 0.
S-IV. a = b = c = d = 0. This does occur. The subspace generated by the first
row of B is a point of O, so it is P∞ or (e2 et + ef + f t : f : e : 1) for some e, f ∈ Fq .
The requirement that B11 = 0 obviously rules out the P∞ case, and imposes the
requirement that e2 et +ef +f t = 0 in the other case. This actually forces e = f = 0.
So B = M ′ (k)U (e1 , f1 )T for some k, e1 , f1 ∈ Fq (with k 6= 0). This element has
B11 = B22 = 0, B33 = et1 /k and B44 = (e21 et1 + e1 f1 + f1t )/(kk t ), which imposes
the relations e1 = f1 = 0. So B = M ′ (k)T is an element of order 2 in the copy of
D2(q−1) that normalises the Cq−1 containing u.
(We solve e2 et + ef + f t = 0 as follows. Taking t-th powers gives us e2 e2t + et f t +
2
f = 0; take away et times the original equation to leave us with f 2 + eet f = 0.
This gives us f = 0 or f = eet , and substituting these into the original equation
gives us e2 et = 0 (so e = 0) in the case f = 0 or e2 et +eeet +(eet )t = 0 (so et e2 = 0)
in the case when f = eet . In either case, the only solution is e = f = 0. Note that
2
(z t+1 )t−1 = z t −1 = z 2−1 = z and z t+2 = (z t+1 )t for all z ∈ Fq , so that t + 1 and
t + 2 are both invertible powers when applied to Fq .)

Using the algorithms of [3], we can usually construct a copy of Sz(q) as a subgroup
of GL(4, q). However, the above algorithm, lemma, theorem and proofs hold with
obvious minor modifications even when G is a group isomorphic to Sz(q) embedded
in GL(4, F ) for any field F (including infinite ones) containing Fq . Furthermore,
the diagonal entries of the semi-standardised matrix B must lie in Fq , even though
the off-diagonal entries need not do so.
Corollary 4. Let G ∼
= Sz(q), where q = 22m+1 for some m > 0, and let g ∈ G have
order q − 1. At least 7/32 of the cosets of hgi have at least one element of order 4.
Proof. In total in G, there are q(q − 1)(q 2 + 1) elements of order 4, and q 2 (q 2 + 1)
cosets of hgi. By Theorem 3 there are at most four elements of order 4 in each coset.
Hence there are at least q(q − 1)(q 2 + 1)/4 cosets containing an element of order 4,
and the proportion of such cosets is 1/4 − 1/(4q) > 7/32, since q > 8.


A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

6

Theorem 5. Algorithm 1 is a Las Vegas algorithm, with success probability at least
7/(384 log log(q)) − O 1/q . When the algorithm succeeds it returns an element as
an SLP in X.
Proof. It is clear that g and h are constructed as SLPs, hence f will have an SLP
as well.
There are (q − 2)q 2 (q 2 + 1)/2 non-trivial elements of order dividing q − 1, hence
the test at line 2 succeeds with probability (q/2 − 1)/(q − 1), which is at least 3/7.
From now on, we can (and shall) assume that g is uniformly distributed among
the non-trivial elements of G having order dividing q − 1. Since CG (G) ∼
= Cq−1 , any
two distinct subgroups of G isomorphic to Cq−1 have trivial intersection. So we can,
for the purpose of this proof, choose g by randomly picking a copy of Cq−1 , and let g
be a random non-trivial element therein, in both cases using a uniform distribution.
We define C := CG (g) ∼
= Cq−1 , and D := NG (hgi) = NG (C) ∼
= D2(q−1) . The
(right-)cosets of C in G partition G into sets all of the same size. So we can choose
h by first choosing a random coset S (of C), and letting h be a random element of
S, again with all distributions uniform.
There are just q − 1 elements that invert g, namely those elements that lie in
the coset D \ C of C, and all
 of them are involutions, so the test at line 7 succeeds
with probability 1 − O 1/q . (Note that the pairs (u, B) and (g, h) are conjugate
in GL(4, q).) So now we can assume that S is uniformly distributed among the
cosets of C other than D \ C. We use Theorem 3 to reduce the equations on
line 11 to a univariate polynomial, and we can then compute its roots using [13,
Algorithm 14.10]. Using 3 log2 (q) applications
of [13, Algorithm 14.8] in the latter,

the probability of success is 1 − O 1/q . The solutions of these equations are in
one-to-one correspondence with the elements h1 , . . . , hs of S having order lying in
{1, 2, 4}. By Corollary 4, these equations have a solution with probability at least
7/32, and Algorithm 1 produces an element f = cfˆc−1 which is one of h1 , . . . , hs .
Unfortunately, given g, the elements f produced are not uniformly distributed
among the elements of orders 1, 2, 4 not lying in D \ C. For if h1 , . . . , hs do occur
with the same probability, then f has a probability of [s(q 4 − q + 1)]−1 , and s can
vary, depending on the coset S. But G has just (q 2 + 1)(q − 1) involutions, and 1
identity, while Corollary 4 implies that at least 7(q 4 + q 2 − 1)/32 cosets S(6= D \ C)
will have an
 element of order 4. Thus h1 , . . . , hs will all have order 4 with probability

1 − O 1/q , and so the test at line 13 succeeds with probability 1 − O 1/q .
If |g| = q − 1 then the test at line 16 always succeeds, and by [2, Lemma 2.5]
this happens with probability at least 1/(12 log log(q)).
(Note that in general, if we choose a solution at line 11 uniformly at random,
then f will be a random element of h1 , . . . , hs , chosen uniformly, depending only
on the coset S, and independent of h. Then the discrete log test at line 16 succeeds
if and only if h ∈ hgi f , which happens with probability |hgi f | / |S| = |g| /(q − 1).)
We see that the success probabilities
of lines 2, 7, 11, 13 and 16 combine to at

least 7/(384 log log(q)) − O 1/q .

We remark that successful runs of Algorithm 1 produce elements of order 4 in
G uniformly at random, provided that the solutions found at line 11 are chosen
uniformly at random; the fact that g is random smooths out the outputs obtained
when g is fixed.
Theorem 6. Given an oracle for the discrete logarithm problem inFq and a random
element oracle, Algorithm 1 has expected time complexity O log(q) field operations.

Proof. All matrix arithmetic can be done
 in O 1 field operations, except exponentiation which can be done in O log(q) field operations, for example by [10, Lemma

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

7


10.1]. Computation of characteristic polynomial and eigenspaces also requires O 1
field operations.

By [9], line 2 has expected time complexity O log(q) field operations.
At lines 3 and 11 we find the roots of a polynomial
over Fq of degree at most

4. The expected time complexity is O log(q) field operations, by [13, Corollary
14.11].

In practice, when implementing Algorithm 1, in order to avoid unnecessary work,
and excessive calls to Random(G), on rerunning the algorithm we only execute
those steps that are necessary.
Thus if Algorithm 1 fails because g has the wrong order or DiscreteLog does
not succeed, we should rerun the algorithm with a new value of g (we can retain h if
we choose). In other cases of failure, we should retain g and use a new value of h. If
the algorithm reaches the DiscreteLog stage, it will succeed there with probability |g| /(q − 1). Taking account of this small probability of success is awkward, and
suppressed analysis shows that the success probability for this stage does not exceed
1.03φ(q − 1)/(q − 2). This means that the expected number of executions of DiscreteLog before a successful run of Algorithm 1 isat least 0.97(q − 2)/φ(q − 1).
Formally, this quantity has magnitude O log log(q) . In practice, while it is the
case that n/φ(n) > log log(n) for infinitely many values of n, we do not know the
behaviour when n is q − 1 for q = 22m+1 .
We can also modify Algorithm 1 and introduce exactly one call to integer factorisation (to factor q − 1), hence only having to call DiscreteLog exactly once.
In this case, line 2 now tests whether g has order exactly q − 1. This takes time
O log q(log t + 1) field operations by [9], where t is the number of distinct prime
factors of q − 1, and so time O log(q) log log(q) in the worst case. We now run
lines 1 and 2 an expected 2(q − 1)/φ(q − 1) times until we have produced an element g of order q − 1, and do not run this part of the algorithm again. We then
execute lines 3 and 4, and repeat the rest of the algorithm (lines 5–21) until success
occurs. The tests on lines 7, 11 and 13 succeed with the same probabilities as before, but now, when executed, the discrete log test on line 16 always succeeds (and
in this case the entire algorithm succeeds).
In this variant the success probability

of lines 5–21 is at least 7/32 − O 1/q . Hence, the expected time complexity until
this variant of the algorithm
succeeds (ignoring the single call to DiscreteLog)

is O log(q)(log log(q))2 field operations, which is dominated by finding g.
Theorem 7. Given a random element oracle for subgroups of GL(4, q), there exists
a Las Vegas algorithm that, given G = hXi 6 GL(4, q) such that G ∼
= Sz(q),
and an element f ∈ G of order 4, constructs Y = {f, h} ⊆ GL(4, q) such that
O2 (GP ) < hY i 6 GP , where P is the unique point of the G-ovoid
fixed by f .

The algorithm has expected time complexity O log(q) log log(q) field operations.
(If G = Σg , where Σ is our standard Sz(q), then the G-ovoid is Og .)
Proof. The algorithm proceeds as follows:
∼ Fq .Fq . Thus we pick a
(1) Use the algorithm of [6] to construct g ∈ CG (f 2 ) =
random c ∈ G such that [f 2 , c] has odd order 2k + 1 for some k ∈ N, and we
calculate g := c[f 2 , c]k (see note (a) below about this). If [f 2 , c] has even
order then start again.
If |g| = 4 then let j := g 2 , otherwise j := g. Repeat this step until
j ∈
/ {1, f 2 }. This requires expected time O log(q) field operations, and
the element j produced is uniformly distributed among the set I of q − 2
involutions of GP \ {f 2 }. See note (b) below for further details about this
step.

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

8

(2) Construct random c ∈ G such that j c ∈
/ CG (f 2 ) (see note (c) below).
 An
equivalent requirement is that c ∈
/ GP , and so this step requires O 1 field
operations. The product of two involutions has odd order if they lie in
distinct point stabilisers, so f 2 j c = 2k + 1 for some k ∈ N. 
(3) Let h = c(f 2 j c )k (see note (a) below). This requires O log(q) field operations. Then j h = f 2 , so h must fix the point fixed by f 2 and j, and hence
hf, hi lies in a point stabiliser.
(4) Now |h| = 2 or 4 or |h| | q − 1, since hf, hi lies in a point stabiliser, and
h∈
/ CG (f 2 ) now forces |h| 6= 1, 2, 4.
For each prime divisor p of 2m + 1, set ap = 2(2m+1)/p − 1, and verify
that hap 6= 1. Each test takes time O log(q) field operations, and we
have to do at most O
 log log(q) of them, for an overall time complexity
of O log(q) log log(q) . (We have no divide-and-conquer strategy of [9] to
speed things up.) Otherwise (if hap = 1 for some p) return to Step 1.
(5) Set Y = {f, h}, and return Y . Note that hY i is the whole of the point
stabiliser GP if and only if |h| = q − 1.
Some notes on aspects of the above algorithm are given below.
(a) In order to prove that g ∈ G ∼
= Sz(q) has odd order, it suffices to show that
g = 1 or g 4 6= 1. And if g has odd order 2k + 1, but we only know an odd
multiple (2k + 1)(2l + 1) = 2(2kl + k + l) + 1 of this order, then we can still
compute g k , since g 2kl+k+l = g l(2k+1)+k = g k . In our case, (q 2 + 1)(q − 1)
is always a multiple of the order of any odd order element.

(b) The probability of success at each iteration is 1 − O 1/q . Note that [f 2 , c]
has odd order whenever c ∈
/ GP , and also when c ∈ O2 (GP ), and that the
possible g obtained this way are uniformly distributed throughout all of
CG (f 2 ) = O2 (GP ). Among the q 2 possibilities for g, precisely 2 + q of them
produce a forbidden value of j. The other q 2 − q − 2 = (q − 2)(q + 1) of
them produce a j uniformly distributed among the q − 2 elements of I.
(If [f 2 , c] has even order, necessarily 2, then we can set j := g = [f 2 , c]
(not quite in line with [6]). The element j depends solely on the coset
O2 (GP )c, always lies in I, and has uniform distribution therein.)
(c) In Step 2, letting c run through X until success occurs, as it must, may be
the best way to execute this step, especially if X is small, which will typically be the case. In theory, f is independent of X, and so the probability
of success for each choice of c ∈ X is 1 − O 1/q .
Note that restricting c to lie in X does not change the success probability
of subsequent steps, notably Step 4. This is because all elements conjugating
j to f 2 lie in the coset O2 (GP )h, they all have the same order, so the order
of h depends only on the pair (f 2 , j), which is fully constructed by the end
of Step 1. Hence it is not wise to use c ∈ X when executing Step 1, as this
determines j, and Step 4 could fail for all choices of c ∈ X.
(d) If we have used the integer factorisation oracle earlier (to factor q − 1), then
it seems neater to generate the whole of GP here, and in that case, at Step
4, we test if h has order q − 1. This test takes time O log(q) log log(q) field
operations, and succeeds with probability φ(q − 1)/(q − 2). This variant

of the algorithm has expected time complexity O log(q)(log log(q))2 field
operations.
To finish off the proof, we must calculate the probability that Step 4 succeeds, and
show that correct output is returned. But the possible elements h correspond to
non-trivial cosets of O2 (GP ) in GP (any element of O2 (GP )h conjugates j to f 2 ),
Moreover, h and O2 (GP )h have the same order, and the possible elements h are

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

9

uniformly distributed, and so the order distribution of h is the same as that for
the non-trivial elements of a Cq−1 . Each order test
 carried out in Step 4 excludes
√
at most 3 q − 2 of these, and there are O log(q) such tests. Thus Step 4 succeeds
√
with probability 1 − O 1/ q . Now h acts on O2 (GP )/Φ(O2 (GP )) ∼
= (Fq , +) in
a manner corresponding to the F2 -action of λ (or λt ) for some λ ∈ Fq \ {0, 1},
and the F2 hhi-module O2 (GP )/Φ(O2 (GP )) is irreducible if and only if λ does not
belong to a proper subfield. Our order restrictions on h rule out that case, giving an
irreducible action. Therefore O2 (GP ) 6 hf, hi, since f ∈ O2 (GP ) \ Φ(O2 (Gp )). 
4. Constructive recognition
The new constructive recognition algorithm for the natural representation is
given as the following two results. The first of these describes how to conjugate
an arbitrary copy hXi of Sz(q) to the standard copy, and the second uses the first
to provide deterministic constructive membership testing of an element of GL(4, q)
inside hXi.
Theorem 8. Given a random element oracle for subgroups of GL(4, q) and an
oracle for the discrete logarithm problem in Fq , there exists a Las Vegas algorithm
g
that, for each conjugate hXi of Σ, constructs g ∈ GL(4, q) such that hXi = Σ and
rewriting generators α1 , h1 , γ of hXi with respect to g as SLPs in X.
The algorithm has expected time complexity O log(q) log log(q) field operations.
The discrete logarithm oracle is only needed in the initial phase,
 in order to obtain
an element of order 4, where it is used, at worst, O log log(q) times.
Proof. Let G = hXi. The algorithm proceeds as follows.

(1) Use Algorithm 1 to construct an element α1 of order 4. By Theorem
 5,
the expected number of invocations of the algorithm is O log log(q)
 , so
by Theorem 6, this step requires expected time O log(q) log log(q) field
operations.
(2) Use Theorem 7 to construct a set of matrices Y1 = {α1 , h1 } such that
O2 (GP ) < hY1 i 6 GP for some P in our G-ovoid. Use α1 for this. This
requires expected time O log(q) log log(q) field operations. Theorem 7,
Step 4 forces h1 to have the required order.
(3) There are just three non-trivial proper submodules of hY1 i (and even of
hα1 i), namely V1P < V2P < V3P , where dim ViP = i for i = 1, 2, 3. For each
i, we canobtain ViP as the nullspace of (α1 − 1)i . This requires expected
time O 1 field operations.
(4) Choose random β ∈ G that does not fix P (the subspace V1P constructed
in Step 3), and let γ = (α21 )β and Q = P γ. Then Q 6= P and hence
γ
hY1 i = hY2 i 6 GQ , where Y2 = {α2 , h2 } = {αγ1 , hγ1}. Also Y2γ = Y1 , since
γ is an involution. This requires expected time O 1 field operations. (It is
probably sensible to take β ∈ X here.)
Note that G is generated by any two of its distinct Sylow 2-subgroups.
Thus G = hO2 (Gp ), O2 (GQ )i = hα1 , h1 , α2 , h2 i = hα1 , h1 , γi.
(5) Use the method of Step 3 to construct the non-trivial proper submodules
V1Q < V2Q < V3Q of hY2 i (so ViQ is the nullspace of (α2 − 1)i ).
(6) Define U1 = V1P , U2 = V2P ∩V3Q , U3 = V3P ∩V2Q , U4 = V1Q . For i = 1, 2, 3, 4,
we have dim Ui = 1, and also γ swaps U1 with U4 and U2 with U3 . We
choose nonzero u1 ∈ U1 and u2 ∈ U2 , and define u3 = u2 γ ∈ U3 and
u4 = u1 γ ∈ U4 . Let k be the inverse of the matrix whose i-th row is ui .
Then by the proof of [2, Lemma 7.4], there is a diagonal matrix d ∈ GL(4, q)
such that (Gk )d = Σ, our standard copy of Sz(q). This requires expected

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

10


time O 1 field operations. (We have corrected the definitions of U2 and U3
here.)
(7) Let J = antidiag(1, 1, 1, 1), and d = diag(d1 , d2 , d3 , d4 ), where (Gk )d = Σ.
Then Gk preserves the form dJdT = antidiag(d1 d4 , d2 d3 , d2 d3 , d1 d4 ), a
form that is unique up to scalars, since G acts absolutely irreducibly on
its natural module. Since Gk contains γ k = antidiag(1, 1, 1, 1), Σ con−1
−1
−1
tains d−1 (γ k )d = antidiag(d−1
1 d4 , d2 d3 , d3 d2 , d4 d1 ), and so this must
′
×
be M (κ)T for some κ ∈ Fq , and conjugating this by the diagonal matrix
√
M ′ ( κ) ∈ Σ gives us T (= J = γ k ).
Therefore, we may assume that d centralises γ k , and this forces d =
diag(d1 , d2 , d2 , d1 ). But conjugating by scalars has no effect, and so we can
take d1 = 1. Therefore d = diag(1, d2 , d2 , 1) for some d2 , and the form
preserved by Gk is K := antidiag(1, d22 , d22 , 1). The equations hKhT = K
for h ∈ αk1 , hk1 give us many linear equations for d22 , at least some of
which are non-trivial. (Note that γ k automatically preserves the form K.)
This requires O log q field operations (to square-root d22 ).
Note that using γ to partially standardise Gk simplifies this step compared to [2, Lemma 7.3].
(8) Let g = kd, where k is as constructed in Step 6 and d is as constructed
in Step 7. Then Gg = Σ, the standard copy of Sz(q). It is clear from the
proof of [2, Lemmas 7.3 & 7.4] that P g = P∞ = (1 : 0 : 0 : 0) and
g
g
Qg = P0 = (0 : 0 : 0 : 1), hence ΣP ∞ > hY1 i and ΣP0 > hY2 i .

Most of the output criteria and complexity issues have been dealt with as we went
along. To finish off, we note that γ g = (γ k )d = T d = T .

Theorem 9. Let X, α1 , h1 , γ, g be as in Theorem 8. Thus G = hXi = hα1 , h1 , γi ∼
=
Sz(q) is a subgroup of GL(4, q) and Gg = Σ. Let h ∈ GL(4, F ). Then:

(1) We can determine whether h ∈ G in O 1 field operations.
(2) Given some preprocessing that is independent of h, and given
 that h ∈ G, we
can construct h as an SLP inα1 , h1 , γ in time O log(q) field operations.
The SLP has length O log(q) . Thus we also get h as an SLP in X. The
preprocessing, which only has to be done once for any (X, α1 , h1 , γ, g), has
complexity at most O (log(q))2 , the true value being dependent on the
complexity of matrix inversion.
(We are counting log2 (q) bit operations as being 1 field operation, as one field
operation over Fq must take at least log2 (q) bit operations.)
Proof. We note that h ∈ GL(4, q) belongs to G if and only if hg ∈ Gg = Σ, which
we solve as follows. We make use of the partitioning from (5).

(1) Consider the first row of hg . If it is µ(1, 0, 0, 0) for some µ 6= 0 let k1 = Id4 . If
it is c(at+2 +ab+bt , b, a, 1) for some a, b, µ with µ 6= 0 let k1 = (T U (a, b))−1 .
In any other case, hg does not preserve O, so return fail. In successful cases,
let k0 = (hg )k1−1 .
(2) Now the first row of k0 has the form µ(1, 0, 0, 0) for some µ 6= 0. So in the
case when hg ∈ Σ, we have k0 ∈ Σ, and so k0 = M ′ (λ)U (c, d) for some
c, d, λ with λ 6= 0.
Look at the (2, 2)-entry of k0 . This should be λ, so if it is 0 then return
fail. In the other cases, define k3 = M ′ (λ), and k2 = k3−1 k0 . If k2 is U (c, d)
for some c, d then we succeed, otherwise we return fail.
(3) In the cases of success, we have also written hg in the form k3 k2 k1 =
M ′ (λ)U (c, d).1 or M ′ (λ)U (c, d)T U (a, b) for some a, b, c, d, λ with λ 6= 0.

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

11


All the above clearly requires just O 1 field operations. In the successful cases, we
wish to write h as an SLP in X. First, we show how to write each of the elements
T , M ′ (λ) and U (a, b) in terms of f = αg1 , e = hg1 and z = γ g . The easy one is
that T = z. We also have M ′ (λ) = zU (0, λ1+t/2 )zU (λ−t/2 , λ−1−t/2 )zU (λt/2 , 0),
which just defers the problem. Last, but not least, we consider U (a, b). We have
f = U (a1 , b1 ) and e = M ′ (µ)U (a2 , b2 ) for some a1 , b1 , a2 , b2 , µ with a1 , µ 6= 0. Now
O2 (he, f i) = O2 (GP∞ ) has generating set
i

i

L := { f e , (f 2 )e | 0 6 i 6 2m }.
In terms of matrices
i

i

(t+2)i t+1
f e = U (µit a1 , ∗) and (f 2 )e = U (0, µ(t+1)it at+1
a1 ),
1 ) = U (0, µ

where we have not calculated the starred entry. By construction of h1 , µ does
not lie in a subfield of Fq , and hence the elements µit a1 and µ(t+2)i at+1
form
1
vector space bases for Fq over F2 . Now solve a linear system over F2 and calculate
n0 , . . . , n2m ∈ {0, 1} such that a = a1 (n0 + n1 µt + · · · + n2m µ2mt ). We set
j1 =

2m
Y

i

(f e )ni = f n0 e−1 f n1 e−1 . . . e−1 f n2m e2m ,

i=0

and note that its matrix has form U (a, ∗). We have U (a, b) = j1 U (0, β) for some β,
t+2
and solve another linear system to obtain β = at+1
+ · · ·+ p2m µ2m(t+2) )
1 (p0 + p1 µ
for some p0 , . . . , p2m ∈ {0, 1}. This gives us
j2 =

2m
Y

((f 2 )ei )pi = f 2p0 e−1 f 2p1 e−1 . . . e−1 f 2p2m e2m = U (0, β),

i=0


and so U (a, b) = j1 j2 writes U (a, b) as a word or SLP of length O log(q) in {e, f }.
Note that the matrices, and their inverses, used in the linear system solving do
not depend on h, and hence we precompute them. (This leads to Θ(log(q)) space
complexity of the algorithm, which may be unavoidable in any case.) We then obtain
ni and pi by multiplication with these
inverse matrices, which requires O (log(q))2

bit operations, and thus O log(q) field (Fq ) operations. Therefore, writing U (a, b)
as an SLP in e and f also requires O log(q) field operations. The precomputation
requires us to invert two degree
log2 (q) matrices over F2 , for which
the classical


algorithm uses O (log(q))3 bit operations and thus O (log(q))2 field operations.
(It is known that asymptotically faster matrix inversion algorithms exist. It is not
known whether it is possible for Gaussian elimination to be asymptotically faster
than matrix inversion.)
Having shown how to write each of the elements T , M ′ (λ) and U (a, b) as SLPs
in αg1 , hg1 , γ g , we can now easily obtain hg as an SLP in αg1 , hg1 , γ g since we have
already noted that hg = M ′ (λ)U (c, d) or M ′ (λ)U (c, d)T U (a, b) for some a, b, c, d, λ.
The same SLP gives h in terms of α1 , h1 , γ, and since these three elements have
known SLPs in terms of X, so now does h.
As we have seen, writing h as an SLP in {α1 , h1 , γ} requires at most 5 invocations
of the above method that writes an element
of F as an SLP in {e, f }. Therefore

this requires time complexity
O
log(q)
field
operations,
and produces an SLP for

h having length O log(q) in {α1 , h1 , γ}.


A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

12

5. Elements of order 4
Following Corollary 4, we conjecture that the actual proportion of cosets of hgi
possessing an element of order 4 is
5q 3 − 3q 2 + 14q − 16
,
8q(q 2 + 1)
a value we have checked for q = 2, 8, 32, 128, 512. We associate the vector (v1 , v2 , v4 )
to a coset of hgi, where vi is the number of elements of order i in that coset. We have
proved that there are just nine possibilities for this vector. (Theorem 3 restricts the
possible vectors, but some other arguments are needed too.) The possible vectors,
and the number of cosets (of hgi) in Sz(q) that we conjecture have this vector, are
tabulated below.
vector #cosets
vector #cosets
1
3
2
(0, 1, 0) 12 (q − 1)q(q + 2)
(0, 0, 0) 8 (q − 1)(3q + 2q − 8q + 16)
(0, 0, 1)

(0, 0, 2)
(0, 0, 3)
(0, 0, 4)

1
2
6 (q − 1)q(2q + q + 20)
1
2
4 (q − 1)q (q − 2)
1
2 (q − 1)q(q − 2)
1
24 (q − 1)q(q − 2)(q − 8)

(0, 1, 2)

1
2 (q

(0, q − 1, 0) 1

− 1)q(q − 2)

(1, 0, 0) 1

Again, we have checked these values for q = 2, 8, 32, 128, 512. For the case q = 2 and
vector (0, 1, 0) one should sum the values listed for the cases (0, 1, 0) and (0, q−1, 0).

6. Implementation and performance
An implementation of the algorithms described here is available in Magma [5], as
part of the CompositionTree package [3]. The implementation uses the existing
Magma implementations of the algorithms described in [8], [9] and [13, Corollary
14.10].
A benchmark of the algorithm in Theorem 8, for field sizes q = 22m+1 , with
m = 1, . . . , 100, is given in Figure 1. For each field size, 100 random conjugates of
Sz(q) were recognised, and the average running time for each call, as well as the
average time spent in discrete logarithm calculations, is displayed. As expected, the
running time is completely dominated by the time to compute discrete logarithms,
and the two plots in Figure 1 are almost indistinguishable.
The timings jump up and down due to the cost of discrete logarithms and due
to the way that Magma handles finite field computations: it uses Zech logarithms
for finite fields up to a certain size, and for larger fields it tries to find a subfield
smaller than this size. Hence field arithmetic speed depends on the prime divisors
of 2m + 1.
We have also benchmarked the algorithm in Theorem 9 in a similar way. For each
field size, SLPs of 100 random elements were calculated and the average running
time for each call is displayed in Figure 2. The time to precomputate the matrices
used in the linear system solving is not included in the running time.
In all benchmarks, we used a generating set of size 2. We can always switch to
a generating set of this size by choosing random elements of the input group. The
probability that 2 uniformly random elements generate the group is high, and we
can detect this using [2, Theorem 6.2].
The benchmark was carried out using Magma V2.22-7, Intel64 CUDA 5.5 flavour,
on a PC with an Intel Core i5-4690 CPU running at 3.5 GHz. We used the software
package R [12] to produce the figure.

13

Time
Discrete log time

0.0 0.8 1.6 2.4 3.2 4.0 4.8 5.6 6.4 7.2 8.0 8.8 9.6

Time [sec]

10.6

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

5 10

20

30

40

50

60

70

80

90

100

m, q = 2^(2m + 1)

Figure 1. Benchmark of recognition
References
1. Henrik Bäärnhielm, Algorithmic problems in twisted groups of Lie type, Ph.D. thesis, Queen
Mary, University of London, 2007.
2. Henrik Bäärnhielm, Recognising the Suzuki groups in their natural representations, J. Algebra
300 (2006), no. 1, 171–198.
3. Henrik Bäärnhielm, Derek Holt, C.R. Leedham-Green, and E.A. O’Brien, A practical model
for computation with matrix groups, J. Symbolic Comput. 68 (2015), 27–60.
4. László Babai, Local expansion of vertex-transitive graphs and random generation in finite
groups, STOC ’91: Proceedings of the twenty-third annual ACM symposium on Theory of
computing (New York, NY, USA), ACM Press, 1991, pp. 164–174.
5. 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
6. John N. Bray, An improved method for generating the centralizer of an involution, Arch.
Math. (Basel) 74 (2000), no. 4, 241–245.
7. John N. Bray and Henrik Bäärnhielm, Standard generators for the Suzuki groups, preprint
(2015).
8. Frank Celler, Charles R. Leedham-Green, Scott H. Murray, Alice C. Niemeyer, and E.A.
O’Brien, Generating random elements of a finite group, Comm. Algebra 23 (1995), no. 13,
4931–4948.

14

0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0

Time [msec]

10.5

12.0

A NEW METHOD FOR RECOGNISING SUZUKI GROUPS

5 10

20

30

40

50

60

70

80

90

100

m, q = 2^(2m + 1)

Figure 2. Benchmark of membership testing
9. 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.
10. C.R. Leedham-Green and E.A. O’Brien, Constructive recognition of classical groups in odd
characteristic, J. Algebra 322 (2009), no. 3, 833–881.
11. Igor Pak, The product replacement algorithm is polynomial, FOCS ’00: Proceedings of the
41st Annual Symposium on Foundations of Computer Science (Washington, DC, USA), IEEE
Computer Society, 2000, pp. 476–485.
12. R Development Core Team, R: A language and environment for statistical computing, R
Foundation for Statistical Computing, Vienna, Austria, 2005, 3-900051-07-0.
13. Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, second ed., Cambridge University Press, Cambridge, 2003.
E-mail address: j.n.bray@qmul.ac.uk
School of Mathematical Sciences, Queen Mary, University of London, Mile End
Road, London E1 4NS, United Kingdom
E-mail address: henrik@math.auckland.ac.nz
Department of Mathematics, University of Auckland, Private Bag 92019, Auckland,
New Zealand

