# Two-closure of rank 3 groups in polynomial time

Saveliy V. Skresanov

(Sobolev Institute of Mathematics, Novosibirsk, Russia.
E-mail<EMAIL_ADDRESS>
###### Abstract

A finite permutation group $G$ on $\Omega$ is called a rank $3$ group if it
has precisely three orbits in its induced action on $\Omega\times\Omega$. The
largest permutation group on $\Omega$ having the same orbits as $G$ on
$\Omega\times\Omega$ is called the $2$-closure of $G$. We construct a
polynomial-time algorithm which given generators of a rank 3 group computes
generators of its 2-closure.

##  1 Introduction

The graph isomorphism problem is one of the central topics in computational
complexity theory, being one of the natural candidates for a problem with an
intermediate complexity status. In its original formulation the problem asks
if it is possible to determine in polynomial time that two graphs given by
their adjacency matrices are isomorphic or not, but it is well known to be
equivalent to the problem of computing generators of the full automorphism
group of a given graph.

As the exact complexity status of graph isomorphism remains unknown, several
successful attacks on the problem have been made. Luks [23] developed a
polynomial-time algorithm for isomorphism of graphs of bounded valence, Babai
and Luks [2] presented the moderately exponential $\exp(O(\sqrt{n}\log^{2}n))$
algorithm for graphs with $n$ vertices, and finally in 2017 Babai solved graph
isomorphism in quasi-polynomial time, i.e. in time $\exp(O(\log^{c}n))$, for
some $c>1$ [1].

Owing to the immense difficulty of the general problem, several relaxations
have been developed, for instance, graph isomorphism problem for graphs in
specific classes such as planar graphs [15], graphs of bounded Hadwiger number
[27] or bounded treewidth [6]. Another approach is inspired by group theory
and is chosen in this work. Suppose we are given enough many automorphisms of
a graph, is it then possible to reconstruct its full automorphism group in
polynomial time? One way to define “enough” would be to require known
automorphisms to act transitively on vertices, arcs and non-arcs of our graph;
note that in this case the graph is strongly regular and it is called a rank
$3$ graph. More generally, if $G$ is a permutation group on $\Omega$, its
orbits on $\Omega\times\Omega$ are called $2$-orbits and the number of
2-orbits is the rank of $G$. If $G$ is a permutation group of rank 3, it has
one diagonal and two non-diagonal orbits, and in the case when the order of
$G$ is even, each non-diagonal orbit induces a rank 3 graph.

If $G$ is an arbitrary permutation group (of any rank), the largest
permutation group on $\Omega$ having the same 2-orbits as $G$ is called the
$2$-closure of $G$ and denoted by $G^{(2)}$. Clearly, the full automorphism
group of a rank 3 graph associated to a rank 3 group $G$ is precisely
$G^{(2)}$, so now our relaxation of graph isomorphism can be stated as “given
a rank 3 graph and a list of generators of an associated rank 3 group $G$,
compute $G^{(2)}$”. This is the problem we solve in this paper, in fact, we
even drop the requirement of $G$ being associated with some graph:

######  Theorem 1.1.

Let $G$ be a finite permutation group of rank $3$. Then one can compute the
$2$-closure $G^{(2)}$ in polynomial time.

Throughout this paper permutation groups will be specified by lists of
generating permutations, and “polynomial-time” means polynomial in the degree
of the groups involved.

The reader may validly point out that the measure of “enough automorphisms” we
choose in this paper is too restrictive, indeed, rank 3 groups admit a
detailed classification [5, 18, 22, 21]. Nevertheless, this approach is quite
fruitful. It turns out that the set of 2-orbits of an arbitrary permutation
group forms a coherent configuration, a combinatorial object closely related
to the original graph isomorphism problem through the Weisfeiler-Leman color
refinement algorithm [37]. Such a coherent configuration is essentially a
colored graph, and the full automorphism group of this graph is the 2-closure
of the original group. This point of view initiated by Ponomarenko in [28] led
to a series of results computing 2-closures of permutation groups from various
classes, such as, groups of odd order [13], nilpotent groups [28],
$\frac{3}{2}$-transitive groups [36] and supersolvable groups [26]. Our
contribution can be thought as a continuation of this line of research.

A common approach to the computational 2-closure problem consists in embedding
the 2-closure inside a group with restricted composition factors (for example,
an iterated wreath product of cyclic groups) and then applying the Babai-Luks
algorithm [2, Corollary 3.6] to find the 2-closure in this larger group.
Unfortunately one cannot put a sufficient restriction on the composition
factors of rank 3 groups as arbitrarily large alternating and linear groups
may occur. Therefore here we utilize a different approach, namely, in the most
of cases we constructively recognize a graph associated to the given rank 3
group. For instance, the affine polar graph
$\operatorname{VO}^{\epsilon}_{2m}(q)$ is determined by the order $q$ of the
field, dimension of the space $2m$ and a quadratic form of type
$\epsilon=\pm$, so if we have successfully identified vertices of our graph
with corresponding vectors over $\operatorname{GF}(q)$ and reconstructed the
associated quadratic form, writing down the full automorphism group becomes a
relatively easy task.

The structure of the paper is as follows. In Section 2.1 we review the
description of 2-closures of rank 3 groups and the classification of affine
rank 3 groups, while in Section 2.2 we list the fundamental polynomial-time
algorithms used in this work. Proof of the main result is split into four
parts: in Section 3.1 we deal with nonaffine rank 3 groups and in Section 3.2,
consisting of Subsections 3.2.1, 3.2.2 and 3.2.3, we cover affine groups. At
the end of each part we provide the relevant polynomial-time procedure in
terms of pseudocode (Algorithms 1–4).

##  2 Preliminaries

All groups are assumed to be finite.

Our notation is mostly standard. If $G\leq\operatorname{Sym}(\Delta)$ and
$H\leq\operatorname{Sym}(X)$ we write $G\wr
H\leq\operatorname{Sym}(\Delta\times X)$ for the imprimitive wreath product of
$G$ and $H$, and $G\uparrow H\leq\operatorname{Sym}(\Delta^{X})$ for the
primitive wreath product. The full semilinear group is denoted by
$\operatorname{\Gamma L}_{a}(q)$, and the full affine semilinear group by
$\operatorname{A\Gamma L}_{a}(q)$. For basic properties of 2-closures the
reader is referred to [38].

In the next two sections we review some information on rank 3 groups and
polynomial-time algorithms for permutation groups.

###  2.1 Rank 3 groups

Primitive rank 3 groups were completely classified. A primitive rank 3
permutation group either stabilizes a nontrivial product decomposition, is
almost simple or is an affine group. The description of rank 3 groups
stabilizing a nontrivial product decomposition follows from the classification
of 2-transitive almost simple groups, see Theorem 4.1 (ii)(a) and Section 5 in
[9]. Almost simple rank 3 groups were determined in [5] when the socle is an
alternating group, in [18] when the socle is a classical group and in [22]
when the socle is an exceptional or sporadic group. The classification of
affine rank 3 groups was completed in [21].

A description of 2-closures of rank 3 groups was given in [33], the key tool
being the aforementioned classification of rank 3 groups. Here we record the
main statement.

######  Theorem 2.1 ([33]).

Let $G$ be a rank $3$ permutation group on a set $\Omega$ and suppose that
$|\Omega|>3^{12}$. Then exactly one of the following is true.

  1. (i)

$G$ is imprimitive, i.e. it preserves a nontrivial decomposition
$\Omega\simeq\Delta\times X$. Then
$G^{(2)}=\operatorname{Sym}(\Delta)\wr\operatorname{Sym}(X)$.

  2. (ii)

$G$ is primitive and preserves a product decomposition
$\Omega\simeq\Delta^{2}$ (or in other words, the Hamming graph
$H(2,|\Delta|)$). Then
$G^{(2)}=\operatorname{Sym}(\Delta)\uparrow\operatorname{Sym}(2)$.

  3. (iii)

$G$ is primitive almost simple with socle $L$, i.e. $L\unlhd
G\leq\operatorname{Aut}(L)$. Then $G^{(2)}=N_{\operatorname{Sym}(\Omega)}(L)$,
and $G^{(2)}$ is almost simple with socle $L$.

  4. (iv)

$G$ is a primitive affine group which does not stabilize a product
decomposition. Then $G^{(2)}$ is also an affine group. More precisely, there
exist an integer $a\geq 1$ and a prime power $q$ such that
$G\leq\operatorname{A\Gamma L}_{a}(q)$, and exactly one of the following holds
(setting $F=\operatorname{GF}(q)$).

    1. (a)

$G\leq\operatorname{A\Gamma L}_{1}(q)$. Then $G^{(2)}\leq\operatorname{A\Gamma
L}_{1}(q)$.

    2. (b)

$G\leq\operatorname{A\Gamma L}_{2m}(q)$ preserves the bilinear forms graph
$H_{q}(2,m)$, $m\geq 3$. Then $G^{(2)}\leq\operatorname{A\Gamma L}_{2m}(q)$
and

$G^{(2)}=F^{2m}\rtimes((\operatorname{GL}_{2}(q)\circ\operatorname{GL}_{m}(q))\rtimes\operatorname{Aut}(F)).$

    3. (c)

$G\leq\operatorname{A\Gamma L}_{2m}(q)$ preserves the affine polar graph
$\operatorname{VO}_{2m}^{\epsilon}(q)$, $m\geq 2$, $\epsilon=\pm$. Then
$G^{(2)}\leq\operatorname{A\Gamma L}_{2m}(q)$ and

$G^{(2)}=F^{2m}\rtimes\operatorname{\Gamma O}^{\epsilon}_{2m}(q).$

    4. (d)

$G\leq\operatorname{A\Gamma L}_{10}(q)$ preserves the alternating forms graph
$A(5,q)$. Then $G^{(2)}\leq\operatorname{A\Gamma L}_{10}(q)$ and

$G^{(2)}=F^{10}\rtimes((\operatorname{\Gamma L}_{5}(q)/\\{\pm
1\\})\times(F^{\times}/(F^{\times})^{2})).$

    5. (e)

$G\leq\operatorname{A\Gamma L}_{16}(q)$ preserves the affine half spin graph
$\operatorname{VD}_{5,5}(q)$. Then $G^{(2)}\leq\operatorname{A\Gamma
L}_{16}(q)$ and

$G^{(2)}=F^{16}\rtimes((F^{\times}\circ\operatorname{Inndiag}(D_{5}(q)))\rtimes\operatorname{Aut}(F)).$

    6. (f)

$G\leq\operatorname{A\Gamma L}_{4}(q)$ preserves the Suzuki-Tits ovoid graph
$\operatorname{VSz}(q)$, $q=2^{2e+1}$, $e\geq 1$. Then
$G^{(2)}\leq\operatorname{A\Gamma L}_{4}(q)$ and

$G^{(2)}=F^{4}\rtimes((F^{\times}\times\operatorname{Sz}(q))\rtimes\operatorname{Aut}(F)).$

Construction and properties of mentioned graphs can be looked up in, for
example, [8], but in what follows we will most closely work with bilinear
forms graphs and affine polar graphs. We remind that if an affine group
$G=V\rtimes G_{0}$ from (iv) preserves the bilinear forms graph $H_{q}(2,m)$,
then the underlying vector space decomposes into a tensor product $V=U\otimes
W$ over $\operatorname{GF}(q)$, where $\dim U=2$ and $\dim W=m$, and $G_{0}$
preserves this decomposition. If $G$ preserves the affine polar graph
$\operatorname{VO}_{2m}^{\epsilon}(q)$, then
$V\simeq\operatorname{GF}(q)^{2m}$ can be endowed with a non-degenerate
quadratic form $\kappa:V\to\operatorname{GF}(q)$ of type $\epsilon$, such that
$G_{0}$ acts on $\kappa$ by semisimiliarities.

We will also require information on the structure of affine rank 3 groups.

######  Theorem 2.2 ([21]).

Let $G$ be a finite primitive affine permutation group of rank $3$ and degree
$n=p^{d}$, with socle $V\simeq\operatorname{GF}(p)^{d}$ for some prime $p$,
and let $G_{0}$ be the stabilizer of the zero vector in $V$. Then $G_{0}$
belongs to one of the following classes.

  1. (A)

Infinite classes. These are:

    1. (1)

$G_{0}\leq\operatorname{\Gamma L}_{1}(p^{d})$;

    2. (2)

$G_{0}$ is imprimitive as a linear group;

    3. (3)

$G_{0}$ stabilizes the decomposition of $V\simeq\operatorname{GF}(q)^{2m}$
into $V=V_{1}\otimes V_{2}$, where $p^{d}=q^{2m}$, $\dim V_{1}=2$ and $\dim
V_{2}=m$. Moreover, $\operatorname{SL}(V_{2})\unlhd G_{0}^{V_{2}}$ or $p=q=2$,
$d=a=8$, or $\dim V_{2}\leq 3$;

    4. (4)

$G_{0}\unrhd\operatorname{SL}_{m}(\sqrt{q})$ and $p^{d}=q^{m}$, where $2$
divides $\frac{d}{m}$;

    5. (5)

$G_{0}\unrhd\operatorname{SL}_{2}(\sqrt[3]{q})$ and $p^{d}=q^{2}$, where $3$
divides $\frac{d}{2}$;

    6. (6)

$G_{0}\unrhd\operatorname{SU}_{m}(q)$ and $p^{d}=q^{2m}$;

    7. (7)

$G_{0}\unrhd\Omega_{2m}^{\pm}(q)$ and $p^{d}=q^{2m}$;

    8. (8)

$G_{0}\unrhd\operatorname{SL}_{5}(q)$ and $p^{d}=q^{10}$;

    9. (9)

$G_{0}\unrhd B_{3}(q)$ and $p^{d}=q^{8}$;

    10. (10)

$G_{0}\unrhd D_{5}(q)$ and $p^{d}=q^{16}$;

    11. (11)

$G_{0}\unrhd\operatorname{Sz}(q)$ and $p^{d}=q^{4}$.

  2. (B)

‘Extraspecial’ classes.

  3. (C)

‘Exceptional’ classes.

Moreover, classes (B) and (C) consist of finitely many groups of degree not
exceeding $3^{12}$.

The correspondence between classes of Theorem 2.2 and rank 3 graphs, as well
as formulae for subdegrees will be given later in Tables 1 and 2.

###  2.2 Polynomial toolkit

As was mentioned earlier, both input and output permutation groups used by our
algorithms are specified by their generating sets. In fact, if $G$ is a
permutation group of degree $n$ generated by a set of elements $S$, one can in
time polynomial in $n$ and $|S|$ construct a set of generators of size at most
$n^{2}$, see [32, Exercise 4.1]. Therefore we can assume that $|S|$ is bounded
polynomially in terms of $n$, and hence an algorithm runs in polynomial time
if its running time can be bounded as a polynomial in $n$ only.

Recall that if $\Sigma$ is a collection of finite simple groups (specified by
their names), $O_{\Sigma}(G)$ is the largest normal subgroup of $G$ such that
each composition factor of $O_{\Sigma}(G)$ is isomorphic to a member of
$\Sigma$. The following fundamental algorithms will be used in the text
without further notice.

######  Proposition 2.3 ([32]).

Let $G\leq\operatorname{Sym}(\Omega)$ be a permutation group given by its
generating set. The following can be solved in polynomial time:

  1. 1.

compute the order of $G$,

  2. 2.

given $g\in\operatorname{Sym}(\Omega)$ test whether $g\in G$,

  3. 3.

compute the orbits of $G$,

  4. 4.

given $\alpha$ and $\beta$ in the same orbit, compute $g\in G$ such that
$\alpha^{g}=\beta$,

  5. 5.

given $\alpha\in\Omega$ compute the point stabilizer $G_{\alpha}$,

  6. 6.

compute a minimal block system for $G$,

  7. 7.

compute socle of $G$, center $Z(G)$ and derived subgroup $[G,G]$,

  8. 8.

compute $O_{\Sigma}(G)$ for any collection of simple groups $\Sigma$,

  9. 9.

test if $G$ is simple, and if it is, identify its isomorphism type,

  10. 10.

enumerate all elements of $G$ in time polynomial in $|G|$ and $|\Omega|$,

  11. 11.

all of the above, except items $3$–$6$, in quotient groups of $G$.

The last item is based on the work of Kantor and Luks [19]. For quotient group
algorithms we assume that we are given generators of $G$ and generators of its
normal subgroup $N$. Elements of the quotient $G/N$ are then specified by
coset representatives.

We also remark that certain permutation group constructions, such as primitive
and imprimitive wreath products, can be trivially performed in polynomial
time.

Next result will be used in the treatment of almost simple groups.

######  Lemma 2.4 ([24, Corollary 3.24]).

Let $T\leq Sym(\Omega)$ be a nonabelian simple group. Then
$N_{Sym(\Omega)}(T)$ can be found in polynomial time.

Recall that the vertex set of the Hamming graph $H(a,q)$ is the set of tuples
$(x_{1},\dots,x_{a})$ where components $x_{i}$ are taken from some finite set
of cardinality $q$, and two vertices are adjacent if they differ in exactly
one place. This labelling of vertices is called a _Hamming labelling_ , and
the next result provides a polynomial algorithm for finding such a labelling.

######  Lemma 2.5 ([16]).

Given a graph (specified by a list of vertices and a list of edges), one can
decide in polynomial time if it is a Hamming graph, and find an appropriate
Hamming labelling if that is the case.

Affine groups of rank 3 will require certain algorithms for linear groups. If
$G=V\rtimes G_{0}$ is a primitive affine group, observe that $V$ is the socle
and $G_{0}$ is point stabilizer and thus they can be computed in polynomial
time. Since $|V|=n$ we can avoid most of the theory of effective algorithms
for matrix groups, for instance, we can represent subspaces as lists of
vectors, and compute their sums and intersections by straightforward
procedures. One can easily test if $G_{0}$ acts irreducibly on $V$, indeed, it
suffices to check that for every nonzero vector $v\in V$ the orbit $v^{G_{0}}$
spans $V$, while the general procedure for matrix groups is highly nontrivial,
see [30, Corollary 5.4] and [25].

Nevertheless we will require the following two matrix groups algorithms. Note
that algorithms run in polynomial time in the size of the input, in
particular, the running time may depend on the size of the matrices involved
and the order of the field. Linear groups are given by their generating
matrices, and since all our linear groups will arise from permutation groups,
all parameters (matrix size, order of the field, number of generators, etc.)
will be under control.

######  Lemma 2.6 ([10, Theorem 2]).

Let $g_{1},\dots,g_{k}$ and $h_{1},\dots,h_{k}$ be elements of
$\operatorname{GL}_{d}(p)$, where $p$ is a prime. Then it can be checked in
polynomial time whether there exists an element $t\in\operatorname{GL}_{d}(p)$
such that $g_{i}^{t}=h_{i}$, $i=1,\dots,k$, and such an element can be
computed if it exists.

######  Lemma 2.7 ([31]).

Given $G_{0}\leq\operatorname{GL}_{d}(p)$, where $p$ is a prime, the
centralizer $C_{\operatorname{GL}_{d}(p)}(G_{0})$ can be computed in
polynomial time.

##  3 Proof of the main result

Set $n=|\Omega|$. If $n\leq 3^{12}$, we can find the 2-closure by brute-force,
so from now on we assume that $n>3^{12}$. In the following we will often leave
out the condition $n>3^{12}$ and write that “$n$ is sufficiently large”
instead.

By Theorem 2.1, rank 3 groups fall into four categories: imprimitive groups,
primitive preserving a nontrivial product decomposition, almost simple and
affine. In the next section we provide an algorithm covering the first three
cases (Algorithm 1), while affine groups are subdivided into the “small” case
(Algorithm 2, tensor product case (Algorithm 3) and quadratic form case
(Algorithm 4). The main algorithm consists of running Algorithms 1 through 4
and taking the largest output as the final result. Indeed, our group is
guaranteed to lie in one of the four cases mentioned above, and as we will
prove below, each algorithm computes the 2-closure correctly for the
respective class.

In the following sections we detail the descriptions of the mentioned classes
and provide required algorithms.

###  3.1 Nonaffine case

In this section we consider imprimitive rank 3 groups, groups preserving a
nontrivial product decomposition and almost simple groups. Notice that despite
the name of the section, some affine groups may fall in this case, for
example, affine groups stabilizing a nontrivial product decomposition (i.e.
linearly imprimitive affine groups).

######  Proposition 3.1.

It can be tested in polynomial time if $G$ is an imprimitive rank $3$ group,
and if it is, $G^{(2)}$ can be found in polynomial time.

###### Proof.

If $\Delta$ is a nontrivial block of imprimitivity of $G$, and $\Omega$ is
identified with $\Delta\times X$ for some set $X$, then
$G^{(2)}=\operatorname{Sym}(\Delta)\wr\operatorname{Sym}(X)$ by Theorem 2.1
(i). A nontrivial block system of a permutation group can be found in
polynomial time, so generators of the required wreath product can be easily
obtained. The claim is proved. ∎

######  Proposition 3.2.

It can be tested in polynomial time if $G$ is a primitive rank $3$ permutation
group preserving a nontrivial product decomposition, and if it is, $G^{(2)}$
can be found in polynomial time.

###### Proof.

Suppose that $G$ does preserve a nontrivial product decomposition, in
particular, its subdegrees are $2(\sqrt{n}-1)$ and $(\sqrt{n}-1)^{2}$ (these
are subdegrees of the Hamming graph $H(2,\sqrt{n})$). Since the degree of $G$
is large enough, we can assume that subdegrees of $G$ have different sizes.
The smallest nondiagonal 2-orbit induces a Hamming graph on $\Omega$, and
Hamming graphs can be recognized and appropriately relabeled in polynomial
time by Lemma 2.5, allowing one to reconstruct the product decomposition
$\Omega\simeq\Delta^{2}$ preserved by $G$. We have
$G^{(2)}=\operatorname{Sym}(\Delta)\uparrow\operatorname{Sym}(2)$, and we can
obtain generators of that wreath product in polynomial time. ∎

######  Proposition 3.3.

It can be tested in polynomial time if $G$ is a primitive rank $3$ permutation
group with nonabelian simple socle, and if it is, $G^{(2)}$ can be found in
polynomial time.

###### Proof.

One can compute the socle $S$ and check that it is simple in polynomial time.
By Theorem 2.1, we have $G^{(2)}=N_{\operatorname{Sym}(\Omega)}(S)$. The claim
now follows from Lemma 2.4. ∎

We summarize the algorithm for the nonaffine case in the following figure.

Input: generators of a rank 3 group $G\leq\operatorname{Sym}(\Omega)$ of
sufficiently large degree

Output: generators of $G^{(2)}$ if $G$ is imprimitive or primitive stabilizing
a nontrivial product decomposition or almost simple, and failure otherwise

if  _$G$ is imprimitive_ then

Find a nontrivial decomposition $\Omega\simeq\Delta\times X$;

return _$\operatorname{Sym}(\Delta)\wr\operatorname{Sym}(X)$_

end if

Set $\Gamma$ to be the smallest 2-orbit of $G$;

if  _$\Gamma$ is a Hamming graph_ then // Lemma 2.5

Find a decomposition $\Omega\simeq\Delta^{2}$;

return _$\operatorname{Sym}(\Delta)\uparrow\operatorname{Sym}(2)$_

end if

Compute the socle $S$ of $G$;

if  _$S$ is a nonabelian simple group_ then

return _$N_{\operatorname{Sym}(\Omega)}(S)$_ // Lemma 2.4

end if

// If the group is affine

return _failure_

Algorithm 1 Nonaffine

###  3.2 Affine case

Recall that if $G$ is an affine rank 3 group, then $G\leq\operatorname{A\Gamma
L}_{a}(q)$ and $G$ decomposes as $G=V\rtimes G_{0}$, where $V$ is an
$a$-dimensional vector space over $\operatorname{GF}(q)$, while
$G_{0}\leq\operatorname{\Gamma L}_{a}(q)$. The smallest value of $a$ such that
$G\leq\operatorname{A\Gamma L}_{a}(q)$ for some $q$ will be denoted by $a(G)$.
We continue to use our standard notation $n=|\Omega|=|V|$. Note also that
$n=p^{d}=q^{a}$, where $q$ is a power of a prime $p$ and $a$ divides $d$.

By Theorem 2.2 affine groups of rank $3$ fall into three categories (A), (B)
and (C), where the latter two encompass only a finite number of groups and are
not considered since $n>3^{12}$. Also notice that groups from class (A2)
stabilize a nontrivial product decomposition, and so they were covered in the
previous section.

Finally, structure of affine rank 3 groups, their subdegrees, graphs preserved
and values of $a(G)$ can be easily read of [33, Tables 1 and 3]. Here we
provide a summary for reader’s convenience. The meaning of the column “Class”
is explained right after the tables.

Table 1: Linearly primitive rank 3 group in class (A) | Type of $G$ | a(G) | Graph | Class
---|---|---|---|---
(A1): | $G_{0}<\Gamma L_{1}(p^{d})$ | $1$ | One-dimensional affine | (S)
(A3): | tensor product | $2m$ | $H_{q}(2,m)$ | (T)
(A4): | $G_{0}\unrhd\operatorname{SL}_{m}(\sqrt{q})$ | $m$ | $H_{\sqrt{q}}(2,m)$ | (T)
(A5): | $G_{0}\unrhd\operatorname{SL}_{2}(\sqrt[3]{q})$ | $2$ | $H_{\sqrt[3]{q}}(2,3)$ | (T)
(A6): | $G_{0}\unrhd\operatorname{SU}_{m}(q)$ | $m$ |  $\operatorname{VO}^{\epsilon}_{2m}(q)$, $\epsilon=(-1)^{m}$ | (Q)
(A7): | $G_{0}\unrhd\Omega^{\epsilon}_{2m}(q)$ | $2m$ | $\operatorname{VO}^{\epsilon}_{2m}(q)$ | (Q)
(A8): | $G_{0}\unrhd\operatorname{SL}_{5}(q)$ | $10$ | $A(5,q)$ | (S)
(A9): | $G_{0}\unrhd B_{3}(q)$ | $8$ | $\operatorname{VO}^{+}_{8}(q)$ | (S)
(A10): | $G_{0}\unrhd D_{5}(q)$ | $16$ | $\operatorname{VD}_{5,5}(q)$ | (S)
(A11): | $G_{0}\unrhd\operatorname{Sz}(q)$ | $4$ | $\operatorname{VSz}(q)$ | (S)
Table 2: Subdegrees of some groups in class (A) | $n=p^{d}$ | Subdegrees
---|---|---
(A3): | $q^{2m}$ |  $(q+1)(q^{m}-1)$, $q(q^{m}-1)(q^{m-1}-1)$
(A4): | $q^{m}$ |  $(\sqrt{q}+1)(\sqrt{q}^{m}-1)$, $\sqrt{q}(\sqrt{q}^{m}-1)(\sqrt{q}^{m-1}-1)$
(A5): | $q^{2}$ |  $(\sqrt[3]{q}+1)(q-1)$, $\sqrt[3]{q}(q-1)(\sqrt[3]{q}^{2}-1)$
(A6): | $q^{2m}$ | $\begin{cases}(q^{m}-1)(q^{m-1}+1),q^{m-1}(q-1)(q^{m}-1),\,m\text{ even}\\\ (q^{m}+1)(q^{m-1}-1),q^{m-1}(q-1)(q^{m}+1),\,m\text{ odd}\end{cases}$
(A7): | $q^{2m}$ | $\begin{cases}(q^{m}-1)(q^{m-1}+1),q^{m-1}(q-1)(q^{m}-1),\,\epsilon=+\\\ (q^{m}+1)(q^{m-1}-1),q^{m-1}(q-1)(q^{m}+1),\,\epsilon=-\end{cases}$

For the algorithmic considerations to follow it is more useful to regroup
linearly primitive affine rank 3 groups into the following three families:

  1. (S)

Small groups, that is, groups with $a(G)\leq 16$ and such that the zero
stabilizer $G_{0}$ is 4-generated.

  2. (T)

Tensor case, that is, classes (A3), (A4) and (A5). These groups stabilize a
nontrivial tensor decomposition.

  3. (Q)

Quadratic form case, that is, classes (A6) and (A7). These groups preserve a
quadratic form.

Classes (A3)–(A7) fall into cases (T) and (Q) by definition, so it is left to
sort out classes (A1) and (A8)–(A11). We need the following observation.

######  Lemma 3.4 ([12, Corollary to Theorem 1]).

Let $G$ be an almost simple group with socle $S$. Then $G/S$ and $G$ are
3-generated.

######  Proposition 3.5.

Classes (A1), (A8)–(A11) lie in (S).

###### Proof.

Obvious for (A1). If $G$ lies in (A8)–(A11), then $G_{0}/Z(G_{0})$ is almost
simple and $Z(G_{0})$ is cyclic, see [21, (1.4)] (it also follows from Table 1
and Theorem 2.1). By Lemma 3.4 the group $G_{0}/Z(G_{0})$ is 3-generated.
Since $Z(G_{0})$ is cyclic, $G_{0}$ is 4-generated, as claimed. Table 1
implies $a(G)\leq 16$ at last. ∎

As a corollary from Theorem 2.2 and Proposition 3.5 we yield

######  Proposition 3.6.

Let $G$ be a primitive affine rank $3$ permutation group on $\Omega$ which
does not preserve a nontrivial product decomposition, and assume that
$|\Omega|>3^{12}$. Then $G$ belongs to class (S), (T) or (Q).

Names of classes, corresponding to cases (A1)–(A11), are written in the last
column of Table 1. We stress that classes (S), (T) and (Q) may overlap, so a
group may belong to several classes.

####  3.2.1 Small groups case

Let $G$ lie in (S), and recall that $G=V\rtimes G_{0}$, where $V$ is an
$a$-dimensional vector space over $\operatorname{GF}(q)$ and
$G_{0}\leq\operatorname{\Gamma L}_{a}(q)$. Moreover, $a\leq 16$ and $G_{0}$ is
4-generated.

In order to compute the 2-closure we first show that $G^{(2)}$ lies in
$\operatorname{A\Gamma L}_{a}(q)$ for some $a\leq 48$ and $q$. Then we
explicitly enumerate all groups of the form $\operatorname{\Gamma L}_{a}(q)$,
$a\leq 48$, containing $G_{0}$, and find the 2-closure by brute-force, i.e. by
listing all elements of $\operatorname{A\Gamma L}_{a}(q)$ and checking which
permutations preserve the associated rank 3 graph.

######  Lemma 3.7.

Let $G$ be an affine rank $3$ group of sufficiently large degree, and suppose
that $G$ does not stabilize a nontrivial product decomposition. Then
$a(G^{(2)})\leq 3a(G)$.

###### Proof.

It follows from Theorem 2.1 that

$\begin{split}\operatorname{Aut}(H_{q}(2,m))\leq\operatorname{A\Gamma
L}_{2m}(q),\\\
\operatorname{Aut}(\operatorname{VO}^{\pm}_{2m}(q))\leq\operatorname{A\Gamma
L}_{2m}(q),\\\ \operatorname{Aut}(A(5,q))\leq\operatorname{A\Gamma
L}_{10}(q),\\\
\operatorname{Aut}(\operatorname{VD}_{5,5}(q))\leq\operatorname{A\Gamma
L}_{16}(q),\\\
\operatorname{Aut}(\operatorname{VSz}(q))\leq\operatorname{A\Gamma
L}_{4}(q).\end{split}$

Also, Theorem 2.1 (iv)(a) implies that if $G\leq\operatorname{A\Gamma
L}_{1}(q)$ then $G^{(2)}\leq\operatorname{A\Gamma L}_{1}(q)$. Table 1 lists
$a(G)$ and corresponding rank 3 graphs for affine linearly primitive rank 3
groups $G$, so the inequality $a(G^{(2)})\leq 3a(G)$ follows easily by
inspection of the table. Equality is attained in case (A5), where $a(G)=2$,
and $G^{(2)}$ is the automorphism group of the bilinear forms graph
$H_{\sqrt[3]{q}}(2,3)$, so $a(G^{(2)})=6$. ∎

######  Corollary 3.8.

If $G$ belongs to (S), then $a(G^{(2)})\leq 48$.

######  Lemma 3.9.

Let $n=q^{a}$. Then $|\operatorname{\Gamma L}_{a}(q)|\leq n^{a+1}$ and
$|\operatorname{A\Gamma L}_{a}(q)|\leq n^{a+2}$.

###### Proof.

Observe that

$|\operatorname{\Gamma
L}_{a}(q)|=|\operatorname{GL}_{a}(q)|\cdot|\operatorname{Aut}(\operatorname{GF}(q))|\leq
q^{a^{2}}\cdot q\leq n^{a+1}.$

In particular, $|\operatorname{A\Gamma
L}_{a}(q)|=q^{a}\cdot|\operatorname{\Gamma L}_{a}(q)|\leq n^{a+2}$. ∎

######  Corollary 3.10.

If $G$ belongs to (S), then $|G|\leq n^{18}$.

Above corollary justifies the name “small” for the class (S), indeed, groups
from this class have order polynomially bounded in terms of $n$.

######  Lemma 3.11.

Let $g_{1},\dots,g_{k}$ be some elements of $\operatorname{GL}_{d}(p)$, where
$k$ is a fixed constant, and let $G_{0}$ be the group generated by
$g_{1},\dots,g_{k}$. It can be checked in polynomial time whether $G_{0}$ is
conjugate to a subgroup of $\operatorname{\Gamma
L}_{a}(q)\leq\operatorname{GL}_{d}(p)$, where $a$ is a fixed constant, and if
it is conjugate, an element $t\in\operatorname{GL}_{d}(p)$ such that
$G_{0}^{t}\leq\operatorname{\Gamma L}_{a}(q)$ can be found in polynomial time.
In fact, all embeddings of $G_{0}$ into $\operatorname{\Gamma L}_{a}(q)$ can
be found in polynomial time.

###### Proof.

Try all $k$-tuples $h_{1},\dots,h_{k}$ of elements of $\operatorname{\Gamma
L}_{a}(q)$ (there are at most $n^{k(a+1)}$ of those by Lemma 3.9), and using
Lemma 2.6 check if there exists an element $t\in\operatorname{GL}_{d}(p)$ such
that $g_{i}^{t}=h_{i}$, $i=1,\dots,k$. ∎

Recall that there might be several subgroups of the form $\operatorname{\Gamma
L}_{a}(q)$ inside $\operatorname{GL}_{d}(p)$, depending on the embedding of
the multiplicative group of the field $\operatorname{GF}(q)$ in
$\operatorname{GL}_{d}(p)$. All of these subgroups are conjugate in
$\operatorname{GL}_{d}(p)$, so if $\operatorname{\Gamma
L}_{a}(q)\leq\operatorname{GL}_{d}(p)$ and $G_{0}$ lies in some
$\widetilde{\operatorname{\Gamma L}_{a}(q)}$, then
$\widetilde{\operatorname{\Gamma L}_{a}(q)}^{t}=\operatorname{\Gamma
L}_{a}(q)$ for some $t\in\operatorname{GL}_{d}(p)$, and hence
$G_{0}^{t}\leq\operatorname{\Gamma L}_{a}(q)$. We can find all such $t$ in
polynomial time in the situation of Lemma 3.11, so in fact we can find all
subgroups of the form $\operatorname{\Gamma L}_{a}(q)$ containing $G_{0}$.

######  Proposition 3.12.

It can be tested in polynomial time if $G$ belongs to (S), and if it does,
$G^{(2)}$ can be found in polynomial time.

###### Proof.

Find $|G|$ and check that $|G|\leq n^{18}$. If that is the case, list all
elements of $G_{0}$ in polynomial time, and check if any $4$-tuple of elements
generates $G_{0}$ (there are at most $n^{18\cdot 4}$ such tuples). Given a
generating set of size $4$, by Lemma 3.11 we can check in polynomial time if
$G_{0}$ is conjugate to a subgroup of $\operatorname{\Gamma L}_{a}(q)$, $a\leq
16$, hence it is possible to check if $G$ belongs to (S) in polynomial time.

By Corollary 3.8, $G^{(2)}\leq\operatorname{A\Gamma L}_{a}(q)$, $a\leq 48$, in
particular, $G_{0}\leq(G^{(2)})_{0}\leq\operatorname{\Gamma L}_{a}(q)$, $a\leq
48$. By Lemma 3.11, we can find all groups $\operatorname{\Gamma L}_{a}(q)$,
$a\leq 48$, such that $G_{0}\leq\operatorname{\Gamma L}_{a}(q)$ in polynomial
time. In particular, we can find all groups $\operatorname{A\Gamma L}_{a}(q)$,
$a\leq 48$, containing $G$, and since $|\operatorname{A\Gamma L}_{a}(q)|$ is
polynomially bounded in terms of $n$, we can find the subgroup of
$\operatorname{A\Gamma L}_{a}(q)$ preserving the 2-orbits of $G$ in polynomial
time. The largest such subgroup will give us the 2-closure of $G$, as
required. ∎

In the following figure (Algorithm 2) we give an overview of the algorithm for
class (S). When checking the condition $a(G)\leq 16$ we use an additional
variable $f$ as a flag: $f=0$ if $G_{0}$ cannot be embedded into
$\operatorname{\Gamma L}_{a}(q)$, $a\leq 16$, and $f=1$ otherwise. In the last
part of the algorithm, intersection $G^{(2)}\cap\operatorname{A\Gamma
L}_{a}(q)$ is computed by brute-force, i.e. all elements of
$\operatorname{A\Gamma L}_{a}(q)$ are listed and it is checked which elements
preserve the 2-orbits of $G$.

Input: generators of an affine rank 3 group $G$ of sufficiently large degree
$n=p^{d}$

Output: generators of $G^{(2)}$ if $G$ lies in (S), and failure otherwise

Check that $G$ is affine and construct $G_{0}$;

if  _$|G| >n^{18}$_ then

return _failure_

end if

Compute all elements of $G$;

if  _$G_{0}$ is not 4-generated_ then

return _failure_

else

Find 4 generators of $G_{0}$ by brute-force;

end if

// Check that $a(G)\leq 16$

Set $f=0$;

for  _$a=1,\dots,16$ , such that $a$ divides $d$_ do

Set $q=p^{d/a}$;

if  _$G_{0}$ embeds in $\operatorname{\Gamma L}_{a}(q)$_ then // Lemma 3.11

Set $f=1$;

end if

end for

if  _$f=0$_ then

return _failure_

end if

Set $L$ to be an empty list;

for  _$a=1,\dots,48$ , such that $a$ divides $d$_ do

Set $q=p^{d/a}$;

for  _$\operatorname{\Gamma L}_{a}(q)\leq\operatorname{GL}_{d}(p)$ such that
$G_{0}\leq\operatorname{\Gamma L}_{a}(q)$_ do // Lemma 3.11

Find $G^{(2)}\cap\operatorname{A\Gamma L}_{a}(q)$ by brute-force;

Add $G^{(2)}\cap\operatorname{A\Gamma L}_{a}(q)$ to the list $L$;

end for

end for

return _the largest member of $L$_

Algorithm 2 Small groups case

####  3.2.2 Tensor product case

Let $G$ lie in (T), and recall that $G=V\rtimes G_{0}$, where $V$ is a
$2m$-dimensional vector space over $\operatorname{GF}(q)$ and
$G_{0}\leq\operatorname{\Gamma L}_{2m}(q)$, $m\geq 2$. The space decomposes
into a tensor product $V=U\otimes W$ over $\operatorname{GF}(q)$, where $\dim
U=2$, $\dim W=m$, and one of the two orbits of $G_{0}$ on nonzero vectors
consists of simple tensors, i.e. vectors of the form $u\otimes w$, $u\in U$,
$w\in W$.

We mention that if $G_{0}$ lies in (A3), it stabilizes a tensor decomposition
by definition, while in classes (A4) and (A5) it follows from the fact that
$G_{0}$ stabilizes a certain subspace. For example, if $G_{0}$ lies in (A4),
it stabilizes a subspace $U\leq V$ of dimension $m$ over
$\operatorname{GF}(\sqrt{q})$, where $n=q^{m}$, and hence $G_{0}$ stabilizes a
nontrivial tensor decomposition $V\simeq U\otimes\operatorname{GF}(q)$, where
the tensor product is taken over $\operatorname{GF}(\sqrt{q})$. Similar
reasoning holds for (A5).

Since $G$ from class (T) stabilizes a bilinear forms graph, Theorem 2.1 and
[7, Theorem 9.5.1] imply that

$G^{(2)}=\operatorname{GF}(q)^{2m}\rtimes((\operatorname{GL}_{2}(q)\circ\operatorname{GL}_{m}(q))\rtimes\operatorname{Aut}(F)),$

when $m>2$, and

$G^{(2)}=\operatorname{GF}(q)^{4}\rtimes((\operatorname{GL}_{2}(q)\circ\operatorname{GL}_{2}(q))\rtimes\operatorname{Aut}(F))\rtimes
C_{2},$

when $m=2$, where an additional automorphism of order two flips components of
simple tensors. Notice also that the case of $m=2$ is covered by Theorem 2.1
(c), since $H_{q}(2,2)$ is isomorphic to $\operatorname{VO}_{4}^{+}(q)$.

To compute the 2-closure in polynomial time, we will first obtain an explicit
embedding of $G_{0}$ into $\operatorname{\Gamma L}_{2m}(q)$. Then we will
exhibit a basis of $V$ of the form $u_{i}\otimes w_{j}$, $i=1,2$,
$j=1,\dots,m$, where $u_{1},u_{2}$ is a basis of $U$ and $w_{1},\dots,w_{m}$
is a basis of $W$; we will call such a basis a _tensor basis_. Finally, given
a tensor basis and the action of the field $\operatorname{GF}(q)$ it is
possible to write down generators of $G^{(2)}$ explicitly.

We start with several general lemmata which will be used in this and next
sections to construct embeddings of $G_{0}$ into groups of the form
$\operatorname{\Gamma L}_{a}(q)$. Recall that the group $\operatorname{\Gamma
L}_{a}(q)$ is completely determined by the embedding of the field
$\operatorname{GF}(q)$ in $\operatorname{GL}_{d}(p)$. Indeed, if
$F=\operatorname{GF}(q)$, then $F^{\times}\leq\operatorname{\Gamma L}_{a}(q)$
and $\operatorname{\Gamma L}_{a}(q)$ is precisely the set of all
$F$-semilinear mappings of the vector space $V$. It is enough to know a
generator of $F^{\times}$ to specify the field, hence we write “the field is
given” if such a generator is given as input to an algorithm, and “the field
is known” if we computed it at some stage of an algorithm.

Notice that in what follows matrix groups $\operatorname{GL}_{d}(p)$, $G_{0}$
etc. are given by generating permutations, in particular, polynomial time
still means polynomial in $n=p^{d}$.

######  Lemma 3.13.

If $c\in\operatorname{GL}_{d}(p)$ and $a$ divides $d$, then we can check in
polynomial time whether $c$ generates a multiplicative group of a finite field
$\operatorname{GF}(p^{d/a})$. Moreover, given
$G_{0}\leq\operatorname{GL}_{d}(p)$, we can check whether
$G_{0}\leq\operatorname{\Gamma L}_{a}(p^{d/a})$, where the respective field is
generated by the element $c$.

###### Proof.

For the first claim, check that the order of $c$ equals $p^{d/a}-1$, and check
that the set of matrices $0$, $c,c^{2},\dots,c^{p^{d/a}-1}$ is closed under
addition (clearly then it satisfies all other field axioms). For the second
claim, it suffices to check that all generators $g_{1},\dots,g_{k}$ of $G_{0}$
act semilinearly on $V\simeq\Omega$ viewed as a vector space over
$\operatorname{GF}(p^{d/a})\simeq F=0\cup\langle c\rangle$. First, check that
$F$ is $G_{0}$-invariant, i.e. $c^{g}\in F$ for $g\in\\{g_{1},\dots,g_{k}\\}$.
Now, notice that for each $v\in V$, $f\in F$ and every generator
$g\in\\{g_{1},\dots,g_{k}\\}$ we have:

$(f\cdot v)^{g}=v^{fg}=v^{gf^{g}}=f^{g}\cdot v^{g},$

where $\cdot$ denotes the action of the field on the vector space and is
defined as $f\cdot v=v^{f}$ for $v\in V$ and $f\in\langle c\rangle$, and
$0\cdot v=0$. Therefore $G$ acts semilinearly if and only if for every
generator $g\in\\{g_{1},\dots,g_{k}\\}$ and every $f\in F$ we have
$f^{g}=f^{p^{i}}$ for some $i$ (depending only on $g$). All checks can be done
in polynomial time, so the claim is proved. ∎

######  Lemma 3.14.

Let $H\leq\operatorname{GL}_{d}(p)$ and suppose that $V$ decomposes into a
direct sum of $k$ irreducible $H$-modules over $\operatorname{GF}(p)$. Then
$|C_{\operatorname{GL}_{d}(p)}(H)|\leq n^{k}$ and, in particular, all elements
of $C_{\operatorname{GL}_{d}(p)}(H)$ can be enumerated in time polynomial in
$n^{k}$.

###### Proof.

Take a decomposition of $V$ into irreducible $H$-modules

$V=V_{1}\oplus\dots\oplus V_{k}$

and fix arbitrary nonzero vectors $v_{i}\in V_{i}$, $i=1,\dots,k$. Since
$V_{i}$ is an irreducible $H$-module over $\operatorname{GF}(p)$, it is
generated by $v_{i}^{H}$ as an abelian group, so $V$ is generated by all
classes $v_{i}^{H}$, $i=1,\dots,k$, as an abelian group.

Now, let $c\in C_{\operatorname{GL}_{d}(p)}(H)$, and set $u_{i}=v_{i}^{c}$,
$i=1,\dots,k$. Fix arbitrary $i\in\\{1,\dots,k\\}$. Then, for any $h\in H$ we
have

$(v_{i}^{h})^{c}=(v_{i}^{c})^{h}=u_{i}^{h},$

and hence the action of $c$ on all elements of the $H$-orbit $v_{i}^{H}$ can
be deduced from the value of $u_{i}$. Since $V$ is generated by orbits
$v_{i}^{H}$, $i=1,\dots,k$, as an abelian group, the action of $c$ on $V$ is
completely determined by values of $u_{i}$, $i=1,\dots,k$.

There are at most $n^{k}$ choices for the vectors $u_{i}$, $i=1,\dots,k$,
therefore $|C_{\operatorname{GL}_{d}(p)}(H)|\leq n^{k}$. Now one can enumerate
all elements of $C_{\operatorname{GL}_{d}(p)}(H)$ by applying Lemma 2.7. ∎

######  Corollary 3.15.

Let $G_{0}\leq\operatorname{GL}_{d}(p)$ and suppose that $V$ decomposes into
$k$ irreducible $[G_{0},G_{0}]$-modules over $\operatorname{GF}(p)$. Then for
every $a$ dividing $d$, one can find all groups of the form
$\operatorname{\Gamma L}_{a}(p^{d/a})$ containing $G_{0}$ in time polynomial
in $n^{k}$.

###### Proof.

Suppose that $G_{0}\leq\operatorname{\Gamma L}_{a}(p^{d/a})$ and let
$c\in\operatorname{GL}_{d}(p)$ be a generator of the center
$Z(\operatorname{GL}_{a}(p^{d/a}))$. Since $H=[G_{0},G_{0}]$ lies in
$\operatorname{GL}_{a}(p^{d/a})$, the element $c$ centralizes $H$. By Lemma
3.14, we can enumerate all elements of $C_{\operatorname{GL}_{d}(p)}(H)$ in
time polynomial in $n^{k}$. By Lemma 3.13, we can check in polynomial time if
$c\in C_{\operatorname{GL}_{d}(p)}(H)$ generates a finite field of order
$p^{d/a}$ and if $G_{0}\leq\operatorname{\Gamma L}_{a}(p^{d/a})$, where
$\operatorname{\Gamma L}_{a}(p^{d/a})$ corresponds to the finite field
generated by $c$. ∎

In order to apply algorithms for embeddings into $\operatorname{\Gamma
L}_{a}(q)$ in the particular case of groups from class (T), we first need a
more precise analysis of the structure of $G_{0}$ in class (T).

######  Proposition 3.16.

Let $G$ be an affine permutation group of rank $3$, such that $G_{0}$
stabilizes a tensor decomposition $V=U\otimes W$ over $\operatorname{GF}(q)$,
where $\dim U=2$ and $\dim W=m$, $m\geq 2$. Then one of the following holds.

  1. (i)

$G_{0}\leq\operatorname{\Gamma L}_{1}(q)$;

  2. (ii)

$G_{0}$ is imprimitive as a linear group;

  3. (iii)

$m=4$ and $q=2$;

  4. (iv)

$\operatorname{SL}(W)\unlhd G_{0}$;

  5. (v)

$\operatorname{SL}(U)\unlhd G_{0}$ and $m=3$.

###### Proof.

Follows directly from [4, Theorem 3.2]. In the terminology the authors use,
$G_{0}$ falls into one of the classes (R0), (I0), (T1)–(T6). Class (R0)
corresponds to (i) in our statement, class (I0) to (ii), class (T4) implies
(iii), classes (T1)–(T3) and (T5) satisfy the conclusion of (iv) and class
(T6) implies (v). ∎

Note that the main part of the proposition is (v), since the rest follows from
the description of the classes (A3)–(A5) (see Theorem 2.2). We also mention
that [4] proves a lot more about the structure of $G_{0}$, see [4, Theorems
3.1 and 3.2].

######  Lemma 3.17.

Suppose that $G$ lies in class (T). Set $H=[G_{0},G_{0}]$ and let

$V=V_{1}\oplus\dots\oplus V_{k},$

be a decomposition of $V$ into a direct sum of irreducible $H$-modules over
$\operatorname{GF}(p)$. Then $k\leq 3$.

###### Proof.

Let $V=U_{1}\otimes U_{2}$ be a tensor decomposition preserved by $G_{0}$. By
definition of the class (T), $G_{0}$ is primitive as a linear group and since
$m\geq 2$, we have $a(G)\geq 2$ (see Table 1), and consequently $G_{0}$ does
not lie in $\operatorname{\Gamma L}_{1}(q)$. By Proposition 3.16, $G_{0}$
contains a normal subgroup $S=\operatorname{SL}(U_{2})$ preserving subspaces
of the form $u\otimes U_{2}$, for $u\in U_{1}$ (in the notation of Proposition
3.16, $U_{2}=W$ in case (iv) and $U_{2}=U$ in case (v)). Moreover, $\dim
U_{1}\leq 3$. Since $n$ is large enough, we may assume that $S$ is neither
$\operatorname{SL}_{2}(2)$ nor $\operatorname{SL}_{2}(3)$. Hence $S$ is
perfect and we have $S\leq H$.

Now, $S$ acts transitively on $U_{2}$, so $u\otimes U_{2}$ is an irreducible
$S$-module of $V$ for every nonzero $u$. Hence $V$ admits the following
decomposition into irreducible $S$-modules:

$V=\sum_{i=1}^{l}u_{i}\otimes U_{2},$

where $u_{1},\dots,u_{l}$ is a basis of $U_{1}$, in particular, $l\leq 3$.
Since $S\leq H$ we immediately obtain $k\leq 3$. ∎

######  Corollary 3.18.

Suppose that $G$ lies in class (T). Then all possibilities for $a$ and
$\operatorname{\Gamma L}_{a}(p^{d/a})$ such that
$G_{0}\leq\operatorname{\Gamma L}_{a}(p^{d/a})$ can be found in polynomial
time.

###### Proof.

Follows from Corollary 3.15 and Lemma 3.17. ∎

Next we show that we can check if a given basis is a tensor basis in
polynomial time.

######  Lemma 3.19.

Suppose that the field $\operatorname{GF}(q)$ is given, and let $v_{ij}$,
$i=1,2$, $j=1,\dots,m$ be a $\operatorname{GF}(q)$-basis of $V$. Then in
polynomial time it is possible to check that $G_{0}$ preserves a tensor
decomposition $V=U\otimes W$, and that $v_{ij}=u_{i}\otimes w_{j}$, where
$u_{1},u_{2}$ is some basis of $U$ and $w_{1},\dots,w_{m}$ is some basis of
$W$.

###### Proof.

Construct a formal tensor product $V^{\prime}=U^{\prime}\otimes W^{\prime}$,
where $U^{\prime}$ has basis $u_{1},u_{2}$ and $W^{\prime}$ has basis
$w_{1},\dots,w_{m}$ over $\operatorname{GF}(q)$. Let $\phi:V\to V^{\prime}$ be
an isomorphism defined by the rule $\phi(v_{ij})=u_{i}\otimes w_{j}$, $i=1,2$,
$j=1,\dots,m$. Clearly we can define the action of $G_{0}$ on $V^{\prime}$ by
$\phi(v)^{g}=\phi(v^{g})$, where $v\in V$, $g\in G_{0}$.

To finish the proof of the claim it suffices to check that $G_{0}$ preserves a
tensor decomposition $V^{\prime}=U^{\prime}\otimes W^{\prime}$. That amounts
to checking that for all $u^{\prime}\in U^{\prime}$, $w^{\prime}\in
W^{\prime}$ and $g\in G_{0}$ we have $(u^{\prime}\otimes
w^{\prime})^{g}=u^{\prime\prime}\otimes w^{\prime\prime}$ for some
$u^{\prime\prime}\in U^{\prime}$ and $w^{\prime\prime}\in W^{\prime}$. Notice
that we only need to check that for elements $g$ taken from some generating
set of $G_{0}$. The size of that generating set can be polynomially bounded in
terms of $n$, and there are at most $n^{4}$ choices for
$u^{\prime},w^{\prime},u^{\prime\prime},w^{\prime\prime}$. Thus this check can
be performed in polynomial time and the claim follows. ∎

######  Lemma 3.20.

Let $G$ lie in class (T), and suppose that the associated field and some
tensor basis are known. Then one can compute generators of $G^{(2)}$ in
polynomial time.

###### Proof.

Let $G_{0}\leq\operatorname{\Gamma L}_{a}(q)=\operatorname{\Gamma L}(V)$,
where $V=U\otimes W$, and let $u_{i}\otimes w_{j}$, $i=1,2$, $j=1,\dots,m$, be
the given tensor basis. Let $g_{1},\dots,g_{s}$ and $h_{1},\dots,h_{r}$ be
generators of $\operatorname{GL}(U)$ and $\operatorname{GL}(W)$ respectively
(take, for example, diagonal matrices and transvections, so $s$ and $r$ are
polynomial in $n$). The following linear transformations, given by their
action on the basis, preserve the tensor product:

$\begin{split}u_{i}\otimes w_{j}\mapsto u_{i}^{g_{k}}\otimes
w_{j},\;k=1,\dots,s,\\\ u_{i}\otimes w_{j}\mapsto u_{i}\otimes
w_{j}^{h_{k}},\;k=1,\dots,r.\end{split}$

Clearly these transformations generate the central product
$\operatorname{GL}(U)\circ\operatorname{GL}(W)$.

Since the field $\operatorname{GF}(q)$ is known, we can add the following
semilinear map to our generating set:

$\sum_{i,j}c_{ij}(u_{i}\otimes w_{j})\mapsto\sum_{i,j}c_{ij}^{p}(u_{i}\otimes
w_{j}),$

where $p$ is the characteristic of the field. This element generates field
automorphisms, hence we obtained generators for the group
$(\operatorname{GL}(U)\circ\operatorname{GL}(W))\rtimes\operatorname{Aut}(\operatorname{GF}(q))$.

Finally, if $m=2$, add the following linear map, given by its action on the
tensor basis:

$u_{i}\otimes w_{j}\mapsto u_{j}\otimes w_{i}.$

This element generates the additional automorphism of order $2$. Since the
number of generators obtained is bounded polynomially in terms of $n$ and all
computations were performed in polynomial time, the claim is proved. ∎

######  Lemma 3.21.

Suppose that $G$ lies in class (T) and preserves a tensor decomposition
$V=U\otimes W$, where $\dim U=2$, $\dim W=m$ and $m\geq 4$. Suppose also that
the respective field is known. Then $\operatorname{SL}(W)\unlhd G_{0}$ and it
is possible to find that subgroup in polynomial time.

###### Proof.

The fact that $\operatorname{SL}(W)\unlhd G_{0}$ follows from Proposition 3.16
(or directly from the description of classes (A3) and (A4)). In order to find
$\operatorname{SL}(W)$ explicitly, first compute the second derived subgroup
$H$ of $G_{0}$. Set $F=\operatorname{GL}(q)$. Since
$G_{0}\leq(\operatorname{GL}(U)\circ\operatorname{GL}(W))\rtimes\operatorname{Aut}(F)$,
we have $H\leq\operatorname{SL}(U)\circ\operatorname{SL}(W)$. Now,
$\operatorname{SL}(W)$ is precisely the preimage of $O_{\Sigma}(H/(H\cap
F^{\times}))$ in $H$, where $\Sigma=\\{\operatorname{PSL}_{m}(q)\\}$. ∎

The following lemma about arbitrary (not necessarily rank 3) permutation
groups allows one to “shift” subsets of the permutation domain away from other
subsets.

######  Lemma 3.22.

Let $G$ be a permutation group on $\Omega$, and let
$\Gamma,\Delta\subseteq\Omega$. Then one can compute $g\in G$ such that
$\Gamma^{g}\not\subseteq\Delta$ in polynomial time, or determine that there is
no such $g$.

###### Proof.

Let $|\Omega|=n$ and set $\Gamma=\\{\gamma_{1},\dots,\gamma_{k}\\}$, $k\leq
n$. One can compute orbits $\gamma_{i}^{G}$, $i=1,\dots,k$, in polynomial
time. Clearly all orbits lie inside $\Delta$ if and only if
$\Gamma^{g}\subseteq\Delta$ for all $g\in G$, so we can test if the required
$g$ exists in polynomial time. Now, if there exists an orbit $\gamma_{i}^{G}$
such that $\gamma_{i}^{G}\not\subseteq\Delta$, then take
$\gamma\in\Delta\setminus\gamma_{i}^{G}$. One can now find $g\in G$ with
$\gamma=\gamma_{i}^{g}$ in polynomial time, and
$\Gamma^{g}\not\subseteq\Delta$. ∎

######  Proposition 3.23.

If $G$ belongs to (T), then we can compute $G^{(2)}$ in polynomial time.

###### Proof.

Suppose that $G_{0}$ preserves a tensor decomposition $V=U\otimes W$ over the
field $\operatorname{GF}(q)$ (notice that $q$ is not necessarily the largest
power of $p$ such that $G_{0}\leq\operatorname{\Gamma L}_{a}(q)$ for some
$a$). Without loss of generality we may assume that $\dim U=2$ and $\dim W=m$
for some $m$. We claim that in polynomial time it is possible to find the
field $\operatorname{GF}(q)$ and a $\operatorname{GF}(q)$-basis of $V$ of the
form $u_{i}\otimes w_{j}$, $i=1,2$, $j=1,\dots,m$, where the pair
$u_{1},u_{2}$ is some basis of $U$ and $w_{1},\dots,w_{m}$ is some basis of
$W$. Given such a basis we can compute $G^{(2)}$ in polynomial time by Lemma
3.20.

Set $q$ to be the largest power of $p$ dividing the second subdegree, and
notice that it is the order of the field required, see Table 2. Also let $m$
be an integer such that $n=q^{2m}$, and notice that it is equal to the
dimension of $W$ over $\operatorname{GF}(q)$. Observe that by Corollary 3.15
and Lemma 3.17, we can find all possibilities for the field
$\operatorname{GF}(q)$ in polynomial time.

Now, if $m\leq 3$, there are at most $n^{6}$ bases of $V$ over
$\operatorname{GF}(q)$. Using Lemma 3.19, we can check all such bases by brute
force in polynomial time, so we are done in this case. From now on we may
assume that $m\geq 4$.

Choose two vectors $v_{1},v_{2}\in V$ and assume they have the form
$v_{1}=u_{1}\otimes w$, $v_{2}=u_{2}\otimes w$ for some linearly independent
(over $\operatorname{GF}(q)$) vectors $u_{1},u_{2}\in U$. Then $v_{1}$ and
$v_{2}$ span the subspace $P=U\otimes w$. By Lemma 3.21, we can compute
$\operatorname{SL}(W)\leq G_{0}$ in polynomial time. If
$g\in\operatorname{SL}(W)$, then $P^{g}=U\otimes w^{g}$, therefore we have
either $P=P^{g}$ or $P\cap P^{g}=0$ depending on whether $w$ and $w^{g}$ are
linearly dependent or not. Since $\operatorname{SL}(W)$ acts transitively on
nonzero vectors of $W$, there exists $g\in\operatorname{SL}(W)$ such that
$P\cap P^{g}=0$, and we can find such $g$ by applying Lemma 3.22 with
$\Gamma=\Delta=P$. In general, if $Q=P^{g_{1}}\oplus
P^{g_{2}}\oplus\dots\oplus P^{g_{k}}$,
$g_{1},\dots,g_{k}\in\operatorname{SL}(W)$, $g_{1}=1$, is a proper subspace of
$V$, then for some $g\in\operatorname{SL}(W)$ the subspace $P^{g}$ does not
lie in $Q$ and hence $Q\cap P^{g}=0$. This allows us to add another direct
summand to $Q$ and to proceed further. After the final step we will end up
with precisely $m$ direct summands.

Now, since $V=P^{g_{1}}\oplus\dots\oplus P^{g_{m}}$, where $g_{1}=1$, the set
$v_{1}^{g_{1}},v_{2}^{g_{1}},\dots,v_{1}^{g_{m}},v_{2}^{g_{m}}$ is a basis for
$V$. Notice that $v_{i}^{g_{j}}=u_{i}\otimes w^{g_{j}}$ and that vectors
$w^{g_{1}},\dots,w^{g_{m}}$ form a basis for $W$. Setting $w_{j}=w^{g_{j}}$,
$j=1,\dots,m$, we obtain that $v_{i}^{g_{j}}=u_{i}\otimes w_{j}$ is a required
tensor basis for $V$. Since there are at most $n^{2}$ choices for vectors
$v_{1},v_{2}$ and since we can check if the basis obtained is correct using
Lemma 3.19, the claim follows. ∎

We provide a summary of the algorithm for class (T) in the following figure
(Algorithm 3). Notice that in contrast to the algorithm for class (S), this
algorithm may not output “failure” if the input group fails to lie in (T).

Input: generators of an affine rank 3 group $G$ of sufficiently large degree
$n=p^{d}$

Output: generators of $G^{(2)}$ if $G$ lies in (T)

Check that $G$ is affine and construct $G_{0}$;

Set $q$ to be the largest power of $p$ dividing the second subdegree;

Find an integer $m$ such that $n=q^{2m}$;

for  _all embeddings of $G_{0}$ into $\operatorname{\Gamma L}_{2m}(q)$_ do //
Corollary 3.18

Find the associated field $\operatorname{GF}(q)$;

if  _$m\leq 3$_ then

for  _all bases of $V$ over $\operatorname{GF}(q)$_ do

if  _it is a tensor basis_ then // Lemma 3.19

return _$G^{(2)}$_ // Lemma 3.20

end if

end for

// There is no appropriate basis

return _failure_

end if

Find the subgroup $\operatorname{SL}(W)\leq G_{0}$ ;

// Lemma 3.21

for  _all $v_{1},v_{2}\in V\setminus 0$_ do

Compute the span $P=\langle v_{1},v_{2}\rangle$;

Set $g_{1}=1$;

for  _$i=2,\dots,m$_ do

Find $g_{i}\in\operatorname{SL}(W)$ such that

$P^{g_{1}}\oplus\dots\oplus P^{g_{i-1}}\cap P^{g_{i}}=0$ ;

// Lemma 3.22

end for

if  _$v_{1}^{g_{1}},v_{2}^{g_{1}},\dots,v_{1}^{g_{m}},v_{2}^{g_{m}}$ is a
tensor basis_ then // Lemma 3.19

return _$G^{(2)}$_ // Lemma 3.20

end if

end for

end for

// No embedding gives a tensor product basis

return _failure_

Algorithm 3 Tensor product case

####  3.2.3 Quadratic form case

Let $V$ be a vector space over $\operatorname{GF}(q)$. Recall that a mapping
$\kappa:V\to\operatorname{GF}(q)$ is called a quadratic form, if
$\kappa(\lambda v)=\lambda^{2}\kappa(v)$ for all
$\lambda\in\operatorname{GF}(q)$ and $v\in V$, and the mapping $f:V\times
V\to\operatorname{GF}(q)$ defined by

$f(x,y)=\kappa(x+y)-\kappa(x)-\kappa(y)$

is a bilinear form (the bilinear form associated to $\kappa$). The quadratic
form $\kappa$ is non-degenerate if the radical $\operatorname{rad}(f)$ is
trivial, where

$\operatorname{rad}(f)=\\{x\in V\mid f(x,y)=0\text{ for all }y\in V\\}.$

There are two types of quadratic forms on vector spaces of even dimension: the
$+$ type and $-$ type; the precise definition will not be important for us, so
we refer the interested reader to [20, Section 2.5] for details.

If $G$ lies in class (Q), then $G=V\rtimes G_{0}$, where $V$ is a
$2m$-dimensional vector space over $\operatorname{GF}(q)$, and
$G_{0}\leq\operatorname{\Gamma L}_{2m}(q)$. The group $G_{0}$ acts on a non-
degenerate quadratic form $\kappa:V\to\operatorname{GF}(q)$ of type
$\epsilon=\pm$ by semisimiliarities, i.e.
$\kappa(v^{g})=\lambda\kappa(v)^{\alpha}$ for all $v\in V$, where
$\lambda\in\operatorname{GF}(q)$,
$\alpha\in\operatorname{Aut}(\operatorname{GF}(q))$ depend only on $g\in
G_{0}$. Also, $G_{0}$ contains either $\operatorname{SU}_{m}(q)$ or
$\Omega^{\epsilon}_{2m}(q)$ as a normal subgroup, depending on whether $G$
lies in (A6) or (A7).

There are exactly two orbits of $G_{0}$ on nonzero vectors, one orbit
consisting of isotropic vectors (i.e. those $v$ with $\kappa(v)=0$), and
another consisting of non-isotropic vectors. The number of non-isotropic
vectors is divisible by $q$, while the number of isotropic vectors is not
(see, for instance, [39, Section 3.6 and formula (3.27)]), in particular, one
can determine isotropic vectors in polynomial time just by taking an orbit of
appropriate size.

In order to compute the $2$-closure, we will show that either $G_{0}$ lies in
$\operatorname{\Gamma L}_{4}(q)$, and $G^{(2)}$ can be found by brute-force,
or the quadratic form $\kappa$ can be recovered, and $G^{(2)}$ can be
constructed explicitly. We start with preliminary lemmata which will allow us
to recover the field and find embeddings of $G_{0}$ into $\operatorname{\Gamma
L}_{a}(q)$.

Recall that a prime $r$ dividing $x^{k}-1$, $k\geq 1$, is called a _primitive
prime divisor_ if $r$ does not divide $x^{m}-1$ for $1\leq m<k$. We remind a
special case of Zsigmondy’s theorem.

######  Lemma 3.24 ([40]).

The number $x^{k}-1$, where $x,k\geq 2$, has a primitive prime divisor except
when $x=2$ and $k=6$, or $x+1$ is a power of two and $k=2$.

######  Lemma 3.25.

Let $G=V\rtimes G_{0}$ lie in class (Q), and let $S\unlhd G_{0}$, where
$S=\operatorname{SU}_{m}(q)$ or $\Omega_{2m}^{\pm}(q)$, $m\geq 2$, depending
on whether $G$ lies in (A6) or (A7) respectively. Suppose that $|V|>2^{12}$.
Then $V$ decomposes into a direct sum of $k$ irreducible $S$-modules over
$\operatorname{GF}(p)$, where $k\leq 2$ when $m=2$, and $k=1$ when $m>2$.

###### Proof.

Set $F=\operatorname{GF}(q^{2})$ in the case $S=\operatorname{SU}_{m}(q)$ and
$F=\operatorname{GF}(q)$ in the case $S=\Omega_{2m}^{\pm}(q)$. By [20,
Proposition 2.10.6], $S$ acts irreducibly on $V$ over $F$, in particular,
$F^{\times}S$ acts irreducibly on $V$ over $\operatorname{GF}(p)$. Since $S$
is a normal subgroup of $F^{\times}S$, the module $V$ is completely reducible
and decomposes into a direct sum of isomorphic irreducible $S$-modules over
$\operatorname{GF}(p)$:

$V=U_{1}\oplus\dots\oplus U_{k}.$

Clearly $k=\frac{\dim V}{\dim U_{1}}$, where dimension is computed over
$\operatorname{GF}(p)$. We wish to derive an upper bound on $k$.

Set $q=p^{r}$, where $p$ is a prime. Since $|F:\operatorname{GF}(p)|\leq 2r$,
we obtain $k\leq 2r$. Set $s=\dim U_{1}$. As $S$ acts faithfully on $V$, it
embeds into the following direct product

$\operatorname{GL}(U_{1})\times\dots\times\operatorname{GL}(U_{k})\simeq\operatorname{GL}_{s}(p)^{k},$

and, in particular, $|S|$ divides $|\operatorname{GL}_{s}(p)|^{k}$. Recall
that the order of $\operatorname{GL}_{s}(p)$ is equal to
$p^{s(s-1)/2}\prod_{i=1}^{s}(p^{s}-1)$.

We consider the case $S=\operatorname{SU}_{m}(q)$ first. By [20, Table 2.1.C],
the order of $S$ is divisible by $q^{m}-(-1)^{m}$ and $q^{m-1}-(-1)^{m-1}$. If
$m$ is even, then $q^{m-1}-(-1)^{m-1}=p^{(m-1)r}+1$. By Lemma 3.24, the number
$p^{2(m-1)r}-1$ has a primitive prime divisor unless $2(m-1)r=2$, or $p=2$ and
$2(m-1)r=6$, where the latter situation can be discarded since $|V|=p^{2mr}$
is large enough. Now, $2(m-1)r=2$ implies $r=1$ and $m=2$; we can use the
previously obtained bound $k\leq 2r=2$ in this case. Thus we can assume that
$p^{2(m-1)r}-1$ has a primitive prime divisor.

Notice that the primitive prime divisor of $p^{2(m-1)r}-1$ must divide
$p^{(m-1)r}+1$ and, hence, must divide $|S|$. As $|S|$ divides
$|\operatorname{GL}_{s}(p)|^{k}$, this prime divisor must divide one of the
numbers $p^{i}-1$, where $s=1,\dots s$, which implies $2(m-1)r\leq s$. Recall
that $\dim V=2mr$, and therefore $k=\frac{\dim V}{\dim
U_{1}}=\frac{2mr}{s}\leq\frac{2mr}{2(m-1)r}=\frac{m}{m-1}$. It can be readily
seen that $k\leq 2$ if $m=2$, and $k\leq 1$ if $m>2$, as required.

If $m$ is odd, then $q^{m}-(-1)^{m}=p^{mr}+1$ divides $|S|$. Again, since
$2mr>2$ (and the case $p=2$, $2mr=6$ is excluded by $|V|>2^{6}$) the number
$p^{2mr}-1$ has a primitive prime divisor dividing $p^{mr}+1$, and hence
dividing $|S|$. We obtain $2mr\leq s$, and therefore $k\leq\frac{2mr}{2mr}=1$
in this case.

We now consider the case $S=\Omega_{2m}^{\pm}(q)$. By [20, Table 2.1.C], the
order of $S$ is divisible by $q^{2m-2}-1=p^{2(m-1)r}-1$. If $r=1$, then $S$ is
defined over $\operatorname{GF}(p)$ and is already irreducible on $V$, hence
we may assume $r\geq 2$. Now $2(m-1)r>2$, and $p^{2(m-1)r}-1$ has a primitive
prime divisor. Proceeding as in the previous case we derive $2(m-1)r\leq s$.
Recall that $\dim V=2mr$, since $|F|=p^{r}$, so
$k=\frac{2mr}{s}\leq\frac{2mr}{2(m-1)r}=\frac{m}{m-1}$. Thus $k\leq 2$ if
$m=2$, and $k\leq 1$ if $m>2$, as claimed. ∎

We mention that the case $k=2$ can indeed happen, for instance,
$\operatorname{SU}_{2}(q)$ has an invariant two-dimensional
$\operatorname{GF}(q)$-subspace in its action on
$\operatorname{GF}(q^{2})^{2}$ (see an example at the beginning of Section 3.6
in [39] for more details).

######  Corollary 3.26.

Let $G$ lie in class (Q). Then all possibilities for $a$ and
$\operatorname{\Gamma L}_{a}(p^{d/a})$ such that
$G_{0}\leq\operatorname{\Gamma L}_{a}(p^{d/a})$ can be found in polynomial
time.

###### Proof.

Since $n$ is large enough, $\operatorname{SU}_{m}(q)$ and
$\Omega_{2m}^{\pm}(q)$ are perfect, see, for instance, [20, Proposition 2.9.2
and remark after Proposition 2.10.6]. The claim now follows from Lemma 3.25
and Corollary 3.15. ∎

######  Proposition 3.27.

If $G$ is a simple unitary or orthogonal permutation group, then one can
compute a pair of elements generating $G$ in polynomial time.

###### Proof.

Let $n$ be the degree of $G$. If $|G|\leq n^{8}$, one can find required
generators by brute-force. If $|G|>n^{8}$, one can compute an isomorphism from
$G$ into a classical group given in its natural matrix representation [17,
Theorem 9.3]. Now, explicit pairs of matrices generating unitary and
orthogonal groups were found in [35] and [29], and the claim follows. ∎

We note that pairs of generators for all Chevalley groups were computed by
Steinberg [34] in terms of the root structure, but we require specific
matrices to be able to lift them to generators of the original permutation
group.

######  Lemma 3.28.

Let $G$ lie in class (Q). Then either $G_{0}\leq\operatorname{\Gamma
L}_{4}(q)$ or $G_{0}$ is 6-generated and one can find such a set of generators
in polynomial time.

###### Proof.

Let $S\unlhd G_{0}$, where $S$ is $\operatorname{SU}_{m}(q)$ or
$\Omega_{2m}^{\epsilon}(q)$, depending on whether $G$ lies in (A6) or (A7). By
Lemma 3.25, either $m=2$ or $S$ acts irreducibly on the underlying vector
space. In the first case $a(G)\leq 4$, hence $G_{0}\leq\operatorname{\Gamma
L}_{4}(q)$ (see Table 1). In the second case $S$ acts irreducibly, hence the
centralizer $C=C_{\operatorname{GL}(V)}(S)$ is a multiplicative group of a
finite field, and thus cyclic.

To find six generators of $G_{0}$ in polynomial time, observe that $S$ can be
found in polynomial time by computing a sufficient term of derived series. The
centralizer $C$ can be found in polynomial time by Lemma 2.7, and hence the
associated field $F$ can be recovered. Since the size of $C$ is polynomially
bounded, we can compute $S\cap C$ in polynomial time. The simple group
$\overline{S}=S/(S\cap C)$ acts faithfully on the set of lines of the vector
space $V$ over $F$, and therefore possesses a faithful permutation
representation of degree less than $n$. One can now apply Proposition 3.27 to
find a pair of generators.

Note that $S(G_{0}\cap C)/(G_{0}\cap C)\simeq\overline{S}$. Now,

$S(G_{0}\cap C)/(G_{0}\cap C)\unlhd G_{0}/(G_{0}\cap C)\simeq
G_{0}C/C\leq\operatorname{Aut}(S)\leq\operatorname{Aut}(\overline{S}),$

where the last embedding follows since $S$ is perfect. Therefore
$G_{0}/(S(G_{0}\cap C))$ is a subgroup of the outer automorphism group of
$\overline{S}$. It is 3-generated by Lemma 3.4, and its size can be
polynomially bounded in terms of $n$ (see [11, Table 5]), hence we can find
three generators of $G_{0}/(S(G_{0}\cap C))$ in polynomial time by brute-
force. The group $G_{0}\cap C$ is cyclic so we can easily find its generator,
and we found two generators of $\overline{S}=S/(S\cap C)$ earlier, so by
taking preimages we find three generators of $S(G_{0}\cap C)$. By taking
preimages once more, we obtain six generating elements of $G_{0}$, as claimed.
∎

The following lemma will be used to derive the value of the quadratic form on
non-isotropic vectors.

######  Lemma 3.29.

Let $G_{0}$ be a subgroup of $\operatorname{\Gamma
L}_{a}(q)=\operatorname{\Gamma L}(V)$ preserving a quadratic form
$\kappa:V\to\operatorname{GF}(q)$, and suppose that the field
$\operatorname{GF}(q)$ is known. Suppose we are given generators
$g_{1},\dots,g_{6}$ of $G_{0}$, a vector $v\in V$, the value
$\kappa(v)\in\operatorname{GF}(q)$, scalars
$\lambda_{i}\in\operatorname{GF}(q)$ and automorphisms
$\alpha_{i}\in\operatorname{Aut}(\operatorname{GF}(q))$, $i=1,\dots,6$, such
that $\kappa(u^{g_{i}})=\lambda_{i}\kappa(u)^{\alpha_{i}}$ for all $u\in V$
and $i=1,\dots,6$. Then we can compute in polynomial time the value of
$\kappa(u)$ for all vectors $u$ from the orbit $v^{G_{0}}$.

###### Proof.

We will increase the number of vectors where $\kappa$ is known step by step.
Denote by $\Delta_{j}\subseteq v^{G_{0}}$ the set of vectors $u$ for which
$\kappa(u)$ is known after $j$ steps of the algorithm. Since $v\in v^{G_{0}}$
and we are given $\kappa(v)$ as input, we set $\Delta_{0}=\\{v\\}$.

Suppose we made $j$ steps of the algorithm. If
$\Delta_{j}^{g_{i}}\subseteq\Delta_{j}$ for all $i=1,\dots,6$, then
$\Delta_{j}=v^{G_{0}}$ and we are done. Otherwise, we can find some
$u\in\Delta_{j}$ and $i\in\\{1,\dots,6\\}$ such that
$u^{g_{i}}\not\in\Delta_{j}$. We can compute the value of $\kappa$ on
$u^{g_{i}}$, indeed

$\kappa(u^{g_{i}})=\lambda_{i}\kappa(u)^{\alpha_{i}},$

where the right hand side can be computed since $\kappa(u)$ is known. We set
$\Delta_{j+1}=\Delta_{j}\cup\\{u^{g_{i}}\\}$, and proceed with the algorithm.

Clearly this procedure will require at most $n$ steps to stop, and since each
step can be trivially performed in polynomial time, the claim follows. ∎

######  Lemma 3.30.

Let $G_{0}$ be a subgroup of $\operatorname{\Gamma
L}_{a}(q)=\operatorname{\Gamma L}(V)$ and suppose that the field
$\operatorname{GF}(q)$ is known. Given a function
$\kappa:V\to\operatorname{GF}(q)$ we can check in polynomial time if $\kappa$
is a non-degenerate quadratic form and if $G_{0}$ acts on $\kappa$ by
semisimiliarities. Moreover, we can find the associated bilinear form in
polynomial time.

###### Proof.

The last claim follows from the fact that
$f(u,v)=\kappa(u+v)-\kappa(u)-\kappa(v)$. It is easy to compute
$\operatorname{rad}(f)$ and check that $\kappa$ is a non-degenerate quadratic
form by straightforward algorithms. In order to check that $G_{0}$ acts on
$\kappa$ by semisimiliarities, it suffices to do that only for generators of
$G_{0}$. If $g\in G_{0}$, it is easy to test if for all $v\in V$ we have
$\kappa(v^{g})=\lambda\kappa(v)^{\alpha}$, for some
$\lambda\in\operatorname{GF}(q)$ and
$\alpha\in\operatorname{Aut}(\operatorname{GF}(q))$ depending only on $g$
(indeed, we need only to try out a polynomially bounded number of scalars
$\lambda$ and automorphisms $\alpha$). This provides the required algorithm. ∎

######  Lemma 3.31.

Let $G$ lie in class (Q), and suppose that the associated field, bilinear and
quadratic forms are known. Then one can compute generators of $G^{(2)}$ in
polynomial time.

###### Proof.

Let $F=\operatorname{GF}(q)$ be the associated field. By Theorem 2.1, we have
$G^{(2)}=F^{2m}\rtimes\operatorname{\Gamma O}_{2m}^{\epsilon}(q)$,
$\epsilon=\pm$, for appropriate $m$, so it suffices to find generators of
$\operatorname{\Gamma O}_{2m}^{\epsilon}(q)$. Since the field and forms are
known, we can construct the standard basis of the space in polynomial time;
the usual procedure can be easily adopted into a polynomial-time algorithm,
see, for example, the proof of [20, Proposition 2.5.3]. Now generators can be
written down explicitly, see [20, Sections 2.7 and 2.8]. ∎

######  Proposition 3.32.

If $G$ belongs to (Q), then we can find $G^{(2)}$ in polynomial time.

###### Proof.

By Corollary 3.26, we can find the required field and an overgroup
$\operatorname{\Gamma L}_{a}(q)$. If $a\leq 4$, then
$G^{(2)}\leq\operatorname{A\Gamma L}_{8}(q)$ (see Table 1), so we can find the
2-closure in polynomial time by brute-force. Now we can assume that $G_{0}$ is
not contained in $\operatorname{\Gamma L}_{4}(q)$, so by Lemma 3.28, $G_{0}$
is 6-generated and its generators $g_{1},\dots,g_{6}$ can be obtained in
polynomial time.

We describe the procedure for constructing the quadratic form $\kappa$. Choose
an arbitrary non-isotropic vector $v\neq 0$, and choose some value for
$\kappa(v)\in\operatorname{GF}(q)$ (there are at most $n$ such values). Now,
choose scalars $\lambda_{1},\dots,\lambda_{6}\in\operatorname{GF}(q)$ and
automorphisms
$\alpha_{1},\dots,\alpha_{6}\in\operatorname{Aut}(\operatorname{GF}(q))$;
observe that there are at most polynomial number of such choices. Assume that
$\kappa(u^{g_{i}})=\lambda_{i}\kappa(u)^{\alpha_{i}}$, $i=1,\dots,6$, for all
$u\in V$. Since all non-isotropic vectors are conjugate to $v$ by elements of
$G_{0}$, Lemma 3.29 implies that we can compute $\kappa(u)$ for all non-
isotropic $u$ and hence for all $u\in V$.

Using Lemma 3.30 we can check that $\kappa$ is a non-degenerate quadratic form
and that $G_{0}$ acts on it by semisimiliarities. If that is the case for at
least one choice of the field, $\kappa(v)$, scalars $\lambda_{i}$ and
automorphisms $\alpha_{i}$, $i=1,\dots,6$, then $G$ belongs to (Q). Clearly
the described procedure will succeed if $G$ does belong to (Q), so the first
claim is proved.

Now, in order to construct the 2-closure of $G$, we restore the bilinear form
associated with $\kappa$ and apply Lemma 3.31. ∎

We provide an overview of the algorithm in case (Q) in the following figure
(Algorithm 4). Notice that this algorithm may find the 2-closure correctly
even if the group does not belong to class (Q), for example, that is the case
with some subgroups of $\operatorname{\Gamma L}_{4}(q)$ lying in class (S).

Input: generators of an affine rank 3 group $G$ of sufficiently large degree
$n=p^{d}$

Output: generators of $G^{(2)}$ if $G$ lies in (Q)

Check that $G$ is affine and construct $G_{0}$;

// Case when $a(G)=4$

Set $L$ to be an empty list;

for  _all embeddings of $G_{0}$ into $\operatorname{\Gamma L}_{4}(q)$_ do //
Corollary 3.26

Add $G^{(2)}\cap\operatorname{A\Gamma L}_{8}(q)$ to the list $L$;

end for

if  _$L$ is not empty_ then

return _the largest member of $L$_

end if

// Case when $a(G)>4$

Find elements $g_{1},\dots,g_{6}$ generating $G_{0}$ ;

// Lemma 3.28

for  _all embeddings of $G_{0}$ into $\operatorname{\Gamma L}_{a}(q)$_ do //
Corollary 3.26

Find the associated field $\operatorname{GF}(q)$;

Choose arbitrary non-isotropic $v\in V\setminus 0$;

for  _all $\gamma,\lambda_{1},\dots,\lambda_{6}\in\operatorname{GF}(q)$_ do

for  _all automorphisms
$\alpha_{1},\dots,\alpha_{6}\in\operatorname{Aut}(\operatorname{GF}(q))$_ do

Set $\kappa(u)=0$ for all isotropic vectors $u$;

Extend the function $\kappa:V\to\operatorname{GF}(q)$ to all non-isotropic
vectors using identities $\kappa(v)=\gamma$ and
$\kappa(u^{g_{i}})=\lambda_{i}\kappa(u)^{\alpha_{i}}$, where $i=1,\dots,6$ and
$u\in V$ ;

// Lemma 3.29

_ _ if  _$\kappa$ is a non-degenerate quadratic form_

 _and_ $G_{0}$ acts on it by semisimiliarities then // Lemma 3.30

Restore the associated bilinear form;

return _$G^{(2)}$_ // Lemma 3.31

end if

end for

end for

end for

// No embedding or choice of vectors, scalars or automorphisms defines a
correct quadratic form

return _failure_

Algorithm 4 Quadratic form case

Finally, we remind the overall algorithm for computing 2-closures of rank 3
groups. If degree of the group is at most $3^{12}$, we find the 2-closure by
brute-force. Otherwise, we apply Algorithms 1–4 to our group and obtain at
most four possible answers (some algorithms may fail, but at least one of them
must succeed by our classification of rank 3 groups into nonaffine, (S), (T)
and (Q) cases). We choose the largest output as our final answer. Since all of
four candidate groups lie in the 2-closure and at least one coincides with it,
the algorithm works correctly.

##  4 Conclusion

It was shown that the 2-closure of rank 3 groups can be computed in polynomial
time. We would like to make a few comments regarding the complexity of the
algorithm, some implications of the methods involved and mention a few
directions for future research.

Since the question of exact complexity estimates was out of scope of this
paper, it is easy to notice that our algorithms are of purely theoretical
nature and their precise complexity is quite large. The bottleneck here seems
to be Algorithm 2, which requires at least $O(n^{50})$ operations in the worst
case when searching for a generating 4-tuple of elements of $G$. It seems
plausible that one can lower this bound by designing custom algorithms for
graphs from class (S), such as, for example, the Suzuki–Tits ovoid graph and
the alternating forms graph.

It should also be mentioned that in many cases we do not only construct the
2-closure, but recognize the corresponding rank 3 graph as well, with the only
exception being graphs arising from almost simple groups (i.e. Theorem 2.1
(iii)). The claim is clear for Hamming graphs, bilinear forms graphs (class
(T)) and affine polar graphs (class (Q)). For graphs arising from class (S)
one can use a slight modification of Algorithm 2. One constructs canonic
copies of “potential” rank 3 graphs ($A(5,q)$, $\operatorname{VO}_{8}^{+}(q)$,
etc.) and their automorphism groups, and then uses the embedding procedure
(Lemma 3.11) to conjugate the given rank 3 group $G$ inside the full
automorphism group of the potential graph. It is then easy to check if $G$
does indeed stabilize the graph, and since there are only polynomially many
potential graphs the whole recognition procedure runs in polynomial time.

Finally, an important open problem is the recognition of rank 3 graphs without
using the corresponding rank 3 group:

Question. Given a graph, is it possible to check if it is a rank 3 graph and
find an appropriate labelling in polynomial time?

Notice that the result of Imrich and Klavz̆ar [16] answers this question in
the case of a Hamming graph. It is interesting whether other classes of rank 3
graphs admit such an algorithm, for example, the question is open even for the
bilinear forms graph. Clearly if one could construct a polynomial algorithm
for recognizing (and labelling) all rank 3 graphs, it would supersede the
results presented in this paper, and moreover, would solve the graph
isomorphism problem for rank 3 graphs.

One promising approach to this problem is to bound the combinatorial base
number of respective graphs; combinatorial base (also called the EP-base in
[3], and just base in [14]) is a generalization of the usual notion of a base
of a permutation group. If a graph has combinatorial base number $b$ then its
full automorphism group has base number at most $b$, in particular, its order
is bounded by $n^{b}$. This implies that many classes of rank 3 graphs cannot
have bounded base since they have large automorphism groups, yet it is quite
possible that all rank 3 graphs associated with affine rank 3 groups from
class (S) may have combinatorial base number bounded by some universal
constant. In [14] it was shown than Paley graphs have combinatorial base
number at most 3, but it seems to be the only known case, the problem being
open even for other one-dimensional affine graphs such as Peisert graphs.

##  5 Acknowledgements

The author would like to express his gratitude to M.A. Grechkoseeva, M.
Muzychuk, I.N. Ponomarenko, A.V. Vasil’ev and E.P. Vdovin for helpful remarks
and comments on this paper.

The work is supported by Mathematical Center in Akademgorodok under agreement
No. 075-15-2019-1613 with the Ministry of Science and Higher Education of the
Russian Federation.

## References

  * [1] L. Babai.  Groups, graphs, algorithms: the graph isomorphism problem.  In Proceedings of the International Congress of Mathematicians (ICM 2018), volume 3, pages 3303–3320. WORLD SCIENTIFIC, 2019\.
  * [2] L. Babai and E. M. Luks.  Canonical labeling of graphs.  In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83, page 171–183, New York, NY, USA, 1983. Association for Computing Machinery.
  * [3] R. F. Bailey and P. J. Cameron.  Base size, metric dimension and other invariants of groups and graphs.  Bull. London Math. Soc., 43(2):209–242, 2011.
  * [4] J. Bamberg, A. Devillers, J. B. Fawcett, and C. E. Praeger.  Partial linear spaces with a rank 3 affine primitive group of automorphisms.  Journal Lond. Math. Soc., 104(3):1011–1084, 2021.
  * [5] E. Bannai.  Maximal subgroups of low rank of finite symmetric and alternating groups.  J. Fac. Sci. Univ. Tokyo, 18:475–486, 1972.
  * [6] H. L. Bodlaender.  Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees.  J. Algorithms, 11(4):631–643, 1990.
  * [7] A. E. Brouwer, A. M. Cohen, and A. Neumaier.  Distance-regular graphs.  Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics. Springer Berlin Heidelberg, 1989.
  * [8] A. E. Brouwer and H. Van Maldeghem.  Strongly Regular Graphs.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2022.
  * [9] P. J. Cameron.  Finite permutation groups and finite simple groups.  Bull. London Math. Soc., 13(1):1–22, 1981.
  * [10] A. Chistov, G. Ivanyos, and M Karpinski.  Polynomial time algorithms for modules over finite dimensional algebras.  In Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97, page 68–74, New York, NY, USA, 1997. Association for Computing Machinery.
  * [11] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, and R. A. Wilson.  Atlas of finite groups: maximal subgroups and ordinary characters for simple groups.  Clarendon Press, 1985.
  * [12] F. Dalla Volta and A. Lucchini.  Generation of almost simple groups.  J. Algebra, 178:194 – 223, 1995.
  * [13] S. Evdokimov and I. Ponomarenko.  Two-closure of odd permutation group in polynomial time.  Discrete Mathematics, 235(1):221 – 232, 2001.
  * [14] S. A. Evdokimov and I. N. Ponomarenko.  Characterization of cyclotomic schemes and normal schur rings over a cyclic group.  St. Petersburg Math. J., 14(2):189–221, 2003.
  * [15] J. E. Hopcroft and R. E. Tarjan.  Isomorphism of planar graphs (working paper).  In R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, editors, Complexity of Computer Computations. The IBM Research Symposia Series, pages 131–152. Springer, Boston, MA, 1972.
  * [16] W. Imrich and S. Klavžar.  Recognizing Hamming graphs in linear time and space.  Inform. Process. Lett., 63(2):91 – 95, 1997.
  * [17] W. M. Kantor.  Sylow’s theorem in polynomial time.  Journal of Computer and System Sciences, 30(3):359 – 394, 1985\.
  * [18] W. M. Kantor and R. A. Liebler.  The rank 3 permutation representations of the finite classical groups.  Trans. Amer. Math. Soc., 271:1–71, 1982.
  * [19] W. M. Kantor and E. M. Luks.  Computing in quotient groups.  In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC ’90, pages 524–534, New York, NY, USA, 1990. Association for Computing Machinery.
  * [20] P. B. Kleidman and M. W. Liebeck.  The subgroup structure of the finite classical groups.  London Mathematical Society Lecture Note Series. Cambridge University Press, 1990.
  * [21] M. W. Liebeck.  The affine permutation groups of rank three.  Proc. London Math. Soc., s3-54(3):477–516, 1987.
  * [22] M. W. Liebeck and J. Saxl.  The finite primitive permutation groups of rank three.  Bull. London Math. Soc., 18(2):165–172, 1986.
  * [23] E. M. Luks.  Isomorphism of graphs of bounded valence can be tested in polynomial time.  J. Comput. System Sci., 25(1):42–65, 1982.
  * [24] E. M. Luks and T. Miyazaki.  Polynomial-time normalizers.  Discrete Mathematics and Theoretical Computer Science, Vol. 13 no. 4(4):61–96, 2011.
  * [25] R. A. Parker.  The computer calculation of modular characters (the Meat-Axe).  In Symposium on Computational Group Theory (ed. Michael Atkinson, Academic Press, London, 1984), pages 267–274, 1984.
  * [26] I. Ponomarenko and A. Vasil’ev.  Two-closure of supersolvable permutation group in polynomial time.  Comp. Complexity, 29(5), 2020.
  * [27] I. N. Ponomarenko.  The isomorphism problem for classes of graphs closed under contraction.  J. Math. Sci., 55:1621–1643, 1991.
  * [28] I. N. Ponomarenko.  Graph isomorphism problem and 2-closed permutation groups.  AAECC, 5:9–22, 1994.
  * [29] L. J. Rylands and D. E. Taylor.  Matrix generators for the orthogonal groups.  J. Symbolic Comput., 25(3):351–360, 1998.
  * [30] L. Rónyai.  Computing the structure of finite algebras.  J. Symbolic Computation, 9(3):355–373, 1990.
  * [31] L. Rónyai.  Computing the order of centralizers in linear groups.  Inform. and Comput., 91(2):172 – 176, 1991.
  * [32] Á. Seress.  Permutation group algorithms.  Cambridge Tracts in Mathematics. Cambridge University Press, 2003.
  * [33] S. V. Skresanov.  On 2-closures of rank 3 groups.  Ars Math. Contemp., 21(1):#P1.08, 2021.
  * [34] R. Steinberg.  Generators for simple groups.  Canad. J. Math, 14:277–283, 1962.
  * [35] D. E. Taylor.  Pairs of generators for matrix groups. I.  The Cayley Bulletin, 3:76–85, 1987.
  * [36] A. V. Vasil’ev and D. V. Churikov.  The 2-closure of a $\frac{3}{2}$-transitive group in polynomial time.  Sib. Math. J., 60(2):279–290, 2019.
  * [37] B. Weisfeiler.  On Construction and Identification of Graphs.  Springer Lecture Notes, 558, 1976.
  * [38] H. W. Wielandt.  Permutation groups through invariant relations and invariant functions.  The Ohio State University, 1969.
  * [39] R. Wilson.  The finite simple groups.  Graduate Texts in Mathematics. Springer London, 2009.
  * [40] K. Zsigmondy.  Zur Theorie der Potenzreste.  Monatsh. für Math. u. Phys., 3:265–284, 1892.


Benchmarking sec:bench This section benchmarks . We first evaluate its
accuracy in reporting battery measurements. We then evaluate its performance
with respect to CPU, memory, and responsiveness of its device mirroring
mechanism. We then investigate ’s heterogeneity and the feasibility of
usability testing when coupled with power monitoring.

Accuracy sec:eval:accuracy Compared to a classic local setup for device
performance measurements, introduces some hardware (circuit relay) and
software (device mirroring) components that can impact the accuracy of the
measurements. We devised an experiment where we compare three scenarios.
First, a direct scenario consisting of the Monsoon power meter, the testing
device, and the Raspberry Pi to instrument the power meter. For this setup, we
strictly followed Monsoon indications monsoon in terms of cable type and
length, and connectors to be used. Next we evaluate a relay scenario, where
the relay circuit is introduced to enable ’s programmable switching between
battery bypass and regular battery operation (see Section sec:sys:remote).
Finally, a mirroring scenario where the device screen is mirrored to an open
noVNC session. While the relay is always “required” for to properly function,
device mirroring is only required for usability testing. Since we currently do
not fully support usability testing for iOS (see Section sec:sys:server), we
here only focus on Android.

figure=/direct-relay-mirroring-comp, width=0.7

Figure : CDF of current drawn(direct, relay, direct-mirroring, relay-
mirroring).

Figure  shows the Cumulative Distribution Function (CDF) of the current
consumed in each of the above scenarios during a 5 minutes test. For
completeness, we also consider a _direct-mirroring_ scenario where the device
is directly connected to Monsoon and device mirroring is active. During the
test, we play an MPEG4 video pre-loaded on the SD card of the device (J7DUO,
UK). The rationale is to force the device mirroring mechanism to constantly
update as new frames are initiated. The figure shows negligible difference
between the “direct” and “relay” scenarios, regardless of the device mirroring
status being active or not. A larger gap (median current grows from 160 to 220
mA) appears with device mirroring. This is because of the background process
responsible for screencasting to the controller which causes additional CPU
usage on the device ($\sim$15%). At the end of this section, we investigate a
more challenging usability testing scenario along with a potential solution to
minimize the additional power consumption caused by device mirroring.

figure=/soft-vs-hard, width=0.7

Figure : Current over time under variable screen brightness ($B$) from 0 to
250, Android’s max value. Software versus hardware measurements (LMX210).

A related question is: _what is the accuracy that offers compared to software
measurements?_ Having verified that is as accurate as a local setup, and
granted that hardware-based battery measurements are the “ground truth”, the
question is really how accurate are software-based battery measurements? While
this question is out of scope for this paper, it has to be noted that Android
software-based battery readings can be realized in via ADB111Either using
Android bug-report files or with adb shell cat
sys/class/power_supply/*/uevent. With respect to iOS, while some high level
_energy usage_ reports are available — reporting battery consumption every
second on an arbitrary 0 to 20 scale — they are currently unavailable to since
they require a developer-enabled macOS. We find that pure software
measurements are _enough_ to identify trends in measured current, but have
limited overall accuracy and granularity, a 30 seconds reporting frequency
across all our Android devices. As an example, Figure  shows the time
evolution of the current measured via (hardware) and software while increasing
the screen brightness from minimum (0) to maximum (250) by 50 units over 60
seconds, as indicated by the vertical dashed lines. This plot shows that pure
software measurements are _enough_ to identify trends, but have limited
overall accuracy and granularity – while the plot refers to the LMX210, we
measured a similar reporting frequency (30 seconds) across all Android
devices. To further investigate the reporting frequency, we have performed the
same test also on Samsung’s Remote Test Lab [samsung].222These tests were not
possible on AWS Device Farm [awsfarm] due to lack of ADB access. We find a 10
seconds reporting frequency on Samsung Galaxy S5 (Android 6) and S7 (Android
8), and 30 seconds on S8 and S9 (Android 9). When repeating the same tests on
newer models, we find that the reported sampling rate improves to a mean of
$2.23$ sec. ($\pm 1.65$) for Google Pixel 3a (Android 12), $0.66$ ($\pm 0.24$)
for Google Pixel 4 (Android 12) and $0.60$ ($\pm 0.25$) for Google Pixel 5.
The sampling rate was unaffected from different configurations (screen on,
off, or streaming a HD video). Note that internal battery readings can be
enhanced with additional data ( cpu, screen usage), alongside device
calibration, to achieve higher accuracy, as discussed in [chenSIGMETRICS15].

##  System Performance

Next, we benchmark overall performance. We start by evaluating the CPU
utilization at the controller. Figure  shows the CDF of the CPU utilization
during the previous experiments (when a relay was used) with active and
inactive device mirroring, respectively. When device mirroring is inactive,
the controller is mostly underloaded, constant CPU utilization at 25%. This
load is caused by the communication with the power meter to pull battery
readings at the highest frequency (5 kHz). With device mirroring, the median
load increases to $\sim$75%. Further, in 10% of the measurements the load is
quite high and over 95%. Device mirroring only impacts the CPU usage. The
impact on memory consumption is minimal (extra 6%, on average). Overall,
memory does not appear to be an issue given less than 20% utilization of the
Raspberry Pi’s 1 GB. The networking demand is also minimal, with just 32 MB of
upload traffic for a $\sim$7 minutes test (due to device mirroring). Note that
we set scrcpy’s video encoding (H.264) rate to 1 Mbps, which produces an upper
bound of about 50 MB. The lower value depends on extra compression provided by
noVNC.

figure=/cpu-pie-cdf-comparison, width=0.7

Figure : CDF of CPU consumption at the controller (Raspberry Pi 3B+)

Finally, we investigate the “responsiveness” of device mirroring. We call
_latency_ the time between when an action is requested (either via automation
or a click in the browser), and when the consequence of this action is
displayed back in the browser, after being executed on the device. This
depends on a number of factors like network latency (between the browser and
the test device), the load on the device and/or the controller, and software
optimizations. We estimate such latency by recording audio (44,100 Hz) and
video (60 fps) while interacting with the device via the browser. We then
manually annotated the video using ELAN multimedia annotator software [elan]
and compute the latency as the time between a mouse click (identified via
sound) and the first frame with a visual change in the app. We repeat this
test 40 times while co-located with the vantage point (1 ms network latency)
and measure an average latency of 350 ($\pm$80) ms.

figure=/current-time-comp-full, width=0.95

Figure : Time evolution of current usage per device at rest (off and on).

##  Devices and Locations

’s distributed nature is both a _feature_ and a _necessity_. It is a feature
since it allows battery measurements under diverse device and network
conditions which is, to the best of our knowledge, a first for research and
development in this space. It is a necessity since it is the way in which the
platform can scale without incurring high costs. We here explore the impact of
such diversity on battery measurements. Figure  displays the evolution over
time (600 seconds) of the current used by each device at “rest”, displaying
the default phone desktop after having run ’s API DEVICE_SETUP (Section
LABEL:sec:sys:server) to ensure equivalent device settings. We further
differentiate between the case when was active or not. For Android, regardless
of settings, the figure shows that the J7DUO consumes the most, while the
LMX210 consumes the least – about 25% less (270 vs 359 J over 600 seconds).
Overall, the similar results in the case without suggest that the difference
between the device is intrinsic of the device configurations, more power-
hungry hardware and different Android versions with potential vendor
customization. Understanding the event responsible of the variations shown in
Figure  is out of the scope of this analysis. It is worth noticing some
correlations between peaks suggesting vendor specific operations, the peak
around 580 seconds for the J7DUO and SMJ337A, both Samsung devices. The
IPHONE7 consumes the least when considering active , while the LMX210 consumes
the least in absence of . The take away of this analysis is that ’s devices
(and locations) have the potential to offer a large set of heterogeneous
conditions for the experimenters to test with.

Speedtest Server (Kms) | Download (Mbps) | Upload (Mbps) | Latency (ms)
---|---|---|---
| South Africa
---
Johannesburg (3.21)
6.26 | 9.77 | 222.04
[0.5pt/5pt]  | China
---
Hong Kong (4.86)
7.64 | 7.77 | 286.32
[0.5pt/5pt]  | Japan
---
Bunkyo (2.21)
9.68 | 7.76 | 239.38
[0.5pt/5pt]  | Brazil
---
Sao Paulo (8.84)
9.75 | 8.82 | 235.05
[0.5pt/5pt]  | CA, USA
---
Santa Clara (7.99)
10.63 | 14.87 | 215.16
Table : ProtonVPN statistics.

Next, we compare the performance of the _same_ device at different locations.
Since we do not have such testing condition, we emulate the presence of one
device (J7DUO) at different locations via a VPN. We use a basic subscription
to ProtonVPN [protonvpn] set up at the controller. Table  summarizes five
locations we choose, along with network measurements from SpeedTest (upload
and download bandwidth, latency). VPN vantage points are sorted by download
bandwidth, with the South Africa node being the slowest and the California
node being the fastest. Since the SpeedTest server is always within 10 km from
each VPN node, the latency here reported is mostly representative of the
network path between the vantage point and the VPN node. Next, we leverage
(see Section LABEL:sec:webtest) to investigate the battery consumption of
Chrome in comparison to a new privacy-preserving browser (Brave). We assume a
simple workload where each browser is instrumented to sequentially load $10$
popular news websites. After a URL is entered, the automation script waits 6
seconds – emulating a typical page load time (PLT) – and then interact with
the page by executing multiple “scroll up” and “scroll down” operations.
Figure  shows the average energy consumption (J) over 5 runs (standard
deviation as errorbars) per VPN location and browser. The figure does not show
significant differences among the battery measurements at different network
location. For example, while the available bandwidth almost doubles between
South Africa and California, the average discharge variation stays between
standard deviation bounds. This is encouraging for experiments where ’s
distributed nature is a _necessity_ and its noise should be minimized. Figure
also shows an interesting trend when comparing Brave and Chrome when tested
via the Japanese VPN node. In this case, Brave’s energy consumption is in line
with the other nodes, while Chrome’s is minimized. This is due to a
significant (20%) drop in bandwidth usage by Chrome, due to a systematic
reduction in the overall size of ads shown in Japan. This is an interesting
result for experiments where ’s distributed nature is a _feature_.

figure=/energy-VPN, width=0.7

Figure : Brave and Chrome energy consumption measured through VPN tunnels.

##  Usability Testing

The above analysis indicates that the extra (CPU) cost of device mirroring can
invalidate the power measurements reading. Accordingly, our recommendation is
to only leverage device mirroring when debugging an application over , but
then disable it during the actual power measurements. This is not possible in
case of usability testing where, by definition, a remote tester requires
access to a device. “Action replay” (see Section LABEL:sec:sys:action) is a
potential solution to this limitation. The intuition is that a usability test
can be split in two parts. First, the tester performs the required test while
action replay is used to record her actions. Then, the tester’s actions are
replayed without the extra cost associated with device mirroring. While this
approach provides, in theory, better accuracy, record and replay of human
actions is challenging.

figure=/action-replay-comp, width=0.7

Figure : Evolution over time of current (mA) measured during “action” (one
human interacting with 10 news websites in sequence) and “replay” (a bot
reproducing human activity).

Figure  shows current measured over time at SMJ337A when a human interacts
with the news workload in Brave (_action_ curve), versus a bot generated by
the action replay tool (_replay_ curve). The figure shows overall lower
current usage in the replay case versus the action case, resulting in an
overall lower energy consumption: 345 versus 399 J over 380 seconds. The
figure also shows high correlation between the two curves, suggesting accurate
replay. Nevertheless, the overall error for energy estimation is fairly low
(about 10%) and overall constant, similar to what suggested by Figure  and now
confirmed in a more challenging scenario. Record and replay of human actions
is generally challenging. Not all applications behave equally between
successive runs. For example, in our testing scenario, a webpage could
suddenly slow down and the replay might fail to click on an article that was
not loaded yet. This opens up a potential interesting research area of
building ML-driven tools for app testing based on human input, as previously
discussed in [almeida2018chimp]. This is currently out of the scope of this
work, but pairing such research with device behavior monitoring is an
interesting avenue for future work.