# Normalisers of primitive permutation groups in quasipolynomial time

Colva M. Roney-Dougal and Sergio Siccha

###### Abstract

We show that given generators for subgroups $G$ and $H$ of ${\mathrm{S}_{n}}$,
if $G$ is primitive then generators for $\operatorname{{\mathrm{N}}}_{H}(G)$
may be computed in quasipolynomial time, namely $2^{O(\log^{3}n)}$. The
previous best known bound was simply exponential.

##  1 Introduction and outline

The _normaliser problem_ has as input generating sets $X$ and $Y$ for
subgroups $G$ and $H$ of ${\mathrm{S}_{n}}$, and asks one to return generators
for $\operatorname{{\mathrm{N}}}_{H}(G)$. The asymptotically best known
algorithm is due to Wiebking [16], and runs in simply exponential time
$2^{O(n)}$. In practice, there are no efficient general algorithms to solve
the normaliser problem.

Any generating set $X$ for a subgroup $G$ of ${\mathrm{S}_{n}}$ can be reduced
to one of size at most $n$ in time $O(|X|n^{2}+n^{5})$ (see Lemma 2.5(a)), so
we shall generally assume that our generating sets have size at most $n$. A
problem about subgroups of ${\mathrm{S}}_{n}$, input via their generating
sets, can be solved in _polynomial time_ if there exists an algorithm to solve
it in time bounded polynomially in $n$. It can be solved in _quasipolynomial_
time if there exists an algorithm to solve it in time bounded by
$2^{O(\log^{c}n)}$, for some absolute constant $c$.

Polynomial time solutions are known for many permutation group problems.
However, in addition to the normaliser problem, polynomial time algorithms for
computing set stabilisers, centralisers and intersections of permutation
groups have so far proven elusive. Amongst these problems, the normaliser
problem occupies a special place. Luks showed in [12] that the other problems
listed above are polynomial time equivalent: we call their polynomial time
equivalence class the _Luks class_. Luks also proved in [12] that the set-
stabiliser problem is polynomial time reducible to the normaliser problem, but
no reduction in the other direction is known.

Although the normaliser problem appears to be harder than the problems in the
Luks class, they are not without similarities. Luks showed that the set-
stabiliser problem is solvable in polynomial time if one restricts the
composition factors of the group in question. This yielded a polynomial time
algorithm for testing isomorphism of graphs with bounded degree [11]. Almost
30 years later, Luks and Miyazaki were able to show that the same holds for
the normaliser problem: if one restricts the composition factors of $H$ then
one can compute $\operatorname{{\mathrm{N}}}_{H}(G)$ in polynomial time [13].

The majority of our paper consists of the proof of the following theorem,
concerning the solution of the normaliser problem in ${\mathrm{S}_{n}}$.

######  Theorem 1.1.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ be a primitive
permutation group. Then $\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(G)$ can
be computed in time $|X|\cdot 2^{O(\log^{3}n)}$.

###### Proof.

This will follow from Theorem 3.4 if $G$ is not large (see Definition 2.2),
and from Corollary 4.8 if $G$ is large. ∎

The _string isomorphism_ problem (as stated in [1, Definition 3.2]) asks one
to find the elements $\sigma$ in a group $G\leq{\mathrm{S}_{n}}$ that map a
function $f:\\{1,\ldots,n\\}\rightarrow\Sigma$ to a function
$g:\\{1,\ldots,n\\}\rightarrow\Sigma$, where the action is
$(i)f^{\sigma}=(i^{\sigma^{-1}})f$. In a dramatic breakthrough, Babai proved
(see [1, 2]) that the string isomorphism problem can be solved in
quasipolynomial time. Babai also gave a polynomial time reduction from the
graph isomorphism problem to the string isomorphism problem, and hence showed
that the graph isomorphism problem can also be solved in quasipolynomial time.
The set stabiliser problem is a special case of the string isomorphism
problem, where $f=g$ and $|\Sigma|=2$, and so it also follows that all
problems in the Luks class can be solved in quasipolynomial time.

Helfgott went on to prove a more precise bound in [9], namely that the string
isomorphism problem can be solved in time $2^{O(\log^{3}n)}$. Hence, given
subgroups $G$ and $H$ of ${\mathrm{S}_{n}}$, the intersection
$G\mathbin{\cap}H$ can be computed in time $2^{O(\log^{3}n)}$. Our main result
now follows immediately:

######  Theorem 1.2.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ and
$H=\left\langle\,Y\,\right\rangle\leq{\mathrm{S}_{n}}$ be permutation groups,
with $G$ primitive. Then $\operatorname{{\mathrm{N}}}_{H}(G)$ can be computed
in time $(\left|X\right|+\left|Y\right|)2^{O(\log^{3}n)}$.

A _base_ of a permutation group $G\leq{\mathrm{S}_{n}}$ is a sequence $B$ of
elements of $\\{1,\ldots,n\\}$, such that the pointwise stabiliser in $G$ of
$B$ is trivial. We write $b(G)$ for the size of the smallest base for $G$. A
technical tool in our proof, which may be of independent interest, is the
following easy corollary of beautiful recent work [5, 8] of Duyan, Halasi,
Liebeck and Maróti. This bound is noted in [8, Proof of Corollary 1.3], but we
state and prove it in slightly more generality.

######  Corollary 1.3.

Let $G$ be primitive and not large. Then

$b(G)\leq 2\lfloor\log n\rfloor+26.$

(Throughout the paper, logarithms are to base $2$, unless specified
otherwise.)

In future work, we plan to consider the normaliser problem for imprimitive
groups, but the required techniques will be quite different. The proof of
Theorem 1.1 relies on the fact that primitive groups have generating sets of
size $\mathrm{max}\\{2,\log n\\}$ (see [10]), and either have a small base, as
in Corollary 1.3, or have a very precisely specified structure: in general,
imprimitive groups have no logarithmic bound on generating sets or base size.

The paper is structured as follows. In Section 2 we divide the primitive
groups into small, large and almost simple groups, state the results from
which Corollary 1.3 will follow, and collect various well known facts about
the complexity of permutation group algorithms. In Section 3 we present an
algorithm to solve the normaliser problem in ${\mathrm{S}_{n}}$ when $G$ is
not large. In Section 4 we first show that the normaliser in
${\mathrm{S}_{n}}$ of the socle of any large primitive group of type PA can be
computed in polynomial time. We then give a “moderately” quasipolynomial time
algorithm (time $2^{O(\log n\log\log n)}$) to solve the normaliser problem in
${\mathrm{S}_{n}}$ when $G$ is large and of type PA, and a polynomial time
method when $G$ is almost simple.

##  2 Small and large primitive groups

In this section we first divide the primitive groups into three (non-disjoint)
families: small groups, large groups and almost simple groups. We then present
some standard complexity results.

###  2.1 Small and large primitive groups

We write $\operatorname{Sym}(\Omega)$ to denote the symmetric group on an
arbitrary (finite) set $\Omega$, and reserve ${\mathrm{S}_{n}}$ for the
symmetric group on $\\{1,\ldots,n\\}$.

######  Definition 2.1.

Let $H\leq\operatorname{Sym}(\Omega)$ and $K\leq\operatorname{Sym}({\hskip
0.5pt\Gamma})$. A _permutation isomorphism_ from $H$ to $K$ is a pair
$(f,\phi)$, where $f:\Omega\rightarrow{\hskip 0.5pt\Gamma}$ is a bijection,
$\phi:H\rightarrow K$ is an isomorphism, and $(\alpha^{h})f=(\alpha
f)^{h\phi}$ for all $\alpha\in\Omega$ and $h\in H$.

######  Definition 2.2.

Let $G\leq{\mathrm{S}_{n}}$ be primitive. Then $G$ is _large_ if there exist
natural numbers $m$, $k$ and $\ell$ such that $n=\binom{m}{k}^{\ell}$, and $G$
is permutation isomorphic to a group $\widehat{G}$ with
$\mathrm{A}_{m}^{\ell}\leq\widehat{G}\leq\mathrm{S}_{m}\wr\mathrm{S}_{\ell}$,
where the action of $\mathrm{A}_{m}$ and $\mathrm{S}_{m}$ is on $k$-element
subsets of $\\{1,\ldots,m\\}$ and $\widehat{G}$ is in product action. (For a
detailed description of product action, see [4, Section 4.5].)

######  Theorem 2.3 ([14, Theorem 1.1]).

Let $G\leq{\mathrm{S}_{n}}$ be primitive. Then one of the following holds:

  1. a)

$G$ is large;

  2. b)

$G=\mathrm{M}_{11}$, $\mathrm{M}_{12}$, $\mathrm{M}_{23}$ or $\mathrm{M}_{24}$
with their $4$-transitive actions; or

  3. c)

$|G|<n^{1+\lfloor\log n\rfloor}$.

We shall say that $G$ is _small_ if $|G|<n^{1+\lfloor\log n\rfloor}$. Thus
each primitive group $G$ is small, large, or almost simple.

We shall combine Theorem 2.3 with the following recent result, which builds on
Duyan, Halasi and Maróti’s proof [5] of Pyber’s base size conjecture.

######  Theorem 2.4 ([8]).

Let $G\leq{\mathrm{S}_{n}}$ be primitive. Then $b(G)\leq\frac{2\log|G|}{\log
n}+24.$

Proof of Corollary 1.3: Since $G$ is primitive and not large, $G$ falls in
Case (b) or (c) of Theorem 2.3. If $G$ is in Case (b) then $b(G)\leq 7$, and
the result is immediate. If $G$ is in Case (c) then we use Theorem 2.4 to see
that

$b(G)\leq\frac{2\log|G|}{\log n}+24\leq\frac{2(1+\lfloor\log n\rfloor)\log
n}{\log n}+24\leq 2\lfloor\log n\rfloor+26$

as required. $\Box$

###  2.2 Complexity preliminaries

The following results are classical: see, for example [6, 15]. Recall from
Section 1 that if we say that a permutation group algorithm runs in
_polynomial time_ , we mean polynomial in the degree $n$.

######  Lemma 2.5.

Let $G=\langle X\rangle\leq{\mathrm{S}_{n}}$.

  1. a)

In time $O(|X|n^{2}+n^{5})$ we can replace $X$ by a generating set for $G$ of
size at most $n$.

  2. b)

Given a generating set for $G$ of size at most $n$, in polynomial time we can:
compute the stabiliser in $G$ of any given point; compute a base and strong
generating set for $G$; show that $G$ is primitive; compute $|G|$; find (at
most $n$) generators for the socle $\operatorname{soc}G$; and compute the
composition factors of $G$.

  3. c)

Given a base $B=(\beta_{1},\ldots,\beta_{b})$ and a strong generating set for
$G$, in time $O(n^{2})$ we can test whether for a tuple
$D\in\\{1,\ldots,n\\}^{b}$ there exists $y\in G$ such that $B^{y}=D$, and if
there exists such a $y\in G$ then determine $y$.

Let $H=\left\langle\,a_{1},\ldots,a_{k}\,\right\rangle\leq\mathrm{S}_{m}$ and
$K=\left\langle\,b_{1},\ldots,b_{\ell}\,\right\rangle\leq\mathrm{S}_{n}$. We
encode a homomorphism $\varphi\colon H\rightarrow K$ by a list
$[a_{1},\ldots,a_{k},b_{1},\ldots,b_{\ell},(a_{1})\varphi,\ldots,(a_{k})\varphi].$
We say that $\varphi$ is _given by generator images_.

The following lemma is standard, and follows from Lemma 2.5.

######  Lemma 2.6.

Let $G_{i}=\left\langle\,X_{i}\,\right\rangle\leq{\mathrm{S}}_{n_{i}}$, for
$i=1,2,3$. Furthermore let $\varphi\colon G_{1}\rightarrow G_{2}$ and
$\psi\colon G_{2}\rightarrow G_{3}$ be homomorphisms given by generator
images. Then in time polynomial in $|X_{1}|n_{1}+|X_{2}|n_{2}+|X_{3}|n_{3}$ we
can: evaluate $\varphi$; compute $\varphi\psi$; compute $\varphi^{-1}$, if
$\varphi$ is an isomorphism; compute the restriction of $\varphi$ to $H_{1}$,
for any subgroup $H_{1}$ of $G_{1}$ with given generators.

We shall also need to be able to compute a permutation isomorphism when given
a suitable group isomorphism. The following lemma is well known: see for
example [4, Lemma 1.6B] for a statement equivalent to Part (a), and [13, Lemma
3.5] for a somewhat more general statement than Part (b).

######  Lemma 2.7.

Let $H=\left\langle\,A\,\right\rangle\leq\operatorname{Sym}(\Omega)$ and
$K=\left\langle\,B\,\right\rangle\leq\operatorname{Sym}({\hskip 0.5pt\Gamma})$
both be transitive, and let $\varphi\colon H\rightarrow K$ be an isomorphism.

  1. a)

There exists a bijection $f$ such that $(f,\varphi)$ is a permutation
isomorphism from $H$ to $K$ if and only if $\varphi$ maps each point
stabiliser of $H$ to a point stabiliser of $K$.

  2. b)

If such an $f$ exists, and $\varphi$ is given by generator images, then $f$
can be computed in time polynomial in
$(\left|A\right|+\left|B\right|)|\Omega|$.

##  3 The normaliser problem for small groups

In this section, we present an algorithm to compute the normaliser in
${\mathrm{S}_{n}}$ of a transitive group of degree $n$, in time exponential in
$\log n$ and the sizes of a given base and (not necessarily strong) generating
set. For primitive groups which are not large we show that this yields a
quasipolynomial time algorithm.

First we show that we can decide in polynomial time whether a primitive group
$G$ is small.

######  Lemma 3.1.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ be primitive, with
$|X|\leq n$. We can decide in polynomial time whether $G$ is small, and
whether $G$ is almost simple.

###### Proof.

By Lemma 2.5(b), we can verify that $G$ is primitive and compute the order of
$G$ in polynomial time, and hence determine whether $G$ is small. By the same
lemma, we can also compute the composition factors of $\operatorname{soc}G$ in
polynomial time, and hence determine whether $\operatorname{soc}G$ is non-
abelian simple. ∎

Next we show that for primitive groups that are not large we can find
generating sets and bases of size $O(\log n)$ in quasipolynomial time.

######  Lemma 3.2.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ be primitive and
not large, with $\left|X\right|\leq n$.

  1. a)

We can compute a generating set of size $t\leq\max\\{\log n,2\\}$ for $G$ in
time $2^{O(\log^{3}n)}$.

  2. b)

We can compute a base $B$ of size $b\leq 2\lfloor\log n\rfloor+26$ for $G$ in
time $2^{O(\log^{2}n)}$.

###### Proof.

(a) By [10] the group $G$ has such a generating set. The number of $t$-tuples
of elements of $G$ is at most $|G|^{t}$. If $G$ is a Mathieu group then
$|G|^{t}$ is bounded by a constant, and otherwise by Theorem 2.3

$|G|^{t}<n^{t(1+\lfloor\log n\rfloor)}<2^{2t\log^{2}n}\leq 2^{2\log^{3}n}.$

By Lemma 2.5(b), each such $t$-tuple can be tested for whether it generates
$G$ in polynomial time.

(b) By Corollary 1.3, such a $B$ exists. There are fewer than $n^{2\lfloor\log
n\rfloor+26}\leq 2^{2\log^{2}n+26\log n}$ candidate $b$-tuples $B$ of elements
from $\\{1,\ldots,n\\}$ to test. We can check, in polynomial time by Lemma
2.5(b), whether $B$ is a base. ∎

Our next result applies to all transitive groups, not just primitive ones.

######  Theorem 3.3.

Let $G\leq{\mathrm{S}_{n}}$ be transitive. Assume that a generating set
$X=\\{x_{1},\ldots,x_{t}\\}$ and a base $B=(\beta_{1},\ldots,\beta_{b})$ for
$G$ are known. Then $\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$ can be
computed in time $2^{O(tb\log n)}$.

###### Proof.

Let $\Omega=\\{1,\ldots,n\\}$. We iterate over all possible choices of
$A=(\alpha_{1},\ldots,\alpha_{b})\in\Omega^{b}$, and $D=(\delta_{ij}\ :\ 1\leq
i\leq t,1\leq j\leq b)\in\Omega^{bt}$. For each such $A$ and $D$ we proceed as
follows.

Let $\gamma_{ij}=\alpha_{j}^{x_{i}}$, and let
$\overline{\sigma}:\alpha_{j}\mapsto\beta_{j}$,
$\gamma_{ij}\mapsto\delta_{ij}$. We first test whether $\overline{\sigma}$ is
a well-defined bijection from its domain $\Delta\subseteq\Omega$ to its image
${\hskip 0.5pt\Gamma}\subseteq\Omega$. To do so, we check whether the
$\alpha_{i}$ are pairwise distinct, whether
$\gamma_{{i_{1}}{j_{1}}}=\gamma_{{i_{2}}j_{2}}$ if and only if
$\delta_{i_{1}j_{1}}=\delta_{i_{2}j_{2}}$, and whether
$\gamma_{ij}=\alpha_{k}$ if and only if $\delta_{ij}=\beta_{k}$. If the answer
is ever “no”, then we move on to the next choice of $A$ and $D$. For a fixed
$A$ and $D$, this step requires time $O(n^{2}t^{2})$.

If $\sigma\in{\mathrm{S}_{n}}$ satisfies $\sigma|_{\Delta}=\overline{\sigma}$,
then $x_{i}^{\sigma}:\beta_{j}\mapsto\delta_{ij}$ for $1\leq i\leq t$ and
$1\leq j\leq b$. Since $B$ is a base, for $1\leq i\leq t$ there is at most one
$y_{i}\in G$ such that $B^{y_{i}}=(\delta_{i1},\ldots,\delta_{ib})$. The
existence of such $y_{i}$, and their determination, can be calculated in time
$O(n^{2}t)$ by Lemma 2.5(c). If for some $i$ no corresponding $y_{i}$ exists,
then we move on to the next choice of $A$ and $D$.

We now show how to determine the (unique) $\sigma\in{\mathrm{S}_{n}}$ such
that $x_{i}^{\sigma}=y_{i}$ for $1\leq i\leq t$, or show that no such $\sigma$
exists. The identity $\mu^{x_{i}\sigma}=\mu^{\sigma y_{i}}$ must hold for all
$\mu\in\Delta$ and all $x_{i}\in X$. Since $G$ is transitive, if
$\Delta\subsetneq\Omega$ we can find $x_{j}\in X$ and $\mu\in\Delta$ with
$\mu^{x_{j}}\not\in\Delta$. Then $(\mu^{x_{j}})^{\sigma}=\mu^{\sigma
y_{j}}=\mu^{\overline{\sigma}y_{j}}\not\in{\hskip 0.5pt\Gamma}.$ Hence we can
define and check the image of one more point under $\sigma$ by examining at
most $|\Delta||X|=O(nt)$ images of points under permutations until we find a
$\mu$ and $x_{j}$ as specified. This must be carried out $O(n)$ times to fully
specify $\sigma$, so the total time is $O(n^{2}t)$.

Hence, given $A$ and $D$, in time $O(n^{2}t^{2})$ we can either determine a
corresponding element
$\sigma\in\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$, or show that no
such element exists. There are $n^{b+tb}=2^{(t+1)b\log n}$ such sequences of
elements $A$ and $D$ to test. Thus we can compute
$\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$ in time $O(n^{2}t^{2}\cdot
2^{(t+1)b\log n})\subseteq 2^{O(t\,b\log n)}$. ∎

Finally we present our main result for primitive groups that are not large.

######  Theorem 3.4.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ be primitive and
not large. Then we can compute
$\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(G)$ in time $|X|\cdot
2^{O(\log^{3}n)}$.

###### Proof.

By Lemma 2.5, in $O(|X|n^{5})$ we can replace $X$ by a generating set of size
at most $n$, and in polynomial time we can compute a base and strong
generating set for $G$. By Lemma 3.1 we can deduce that $G$ is small or almost
simple in polynomial time, and hence whether $G$ is not large. The result now
follows from Lemma 3.2 and Theorem 3.3. ∎

##  4 The normaliser problem for large groups

Recall Definition 2.2 of a large primitive group. In this section we show that
if $G$ is large then we can construct
$\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$ in polynomial time.

######  Definition 4.1.

Let $G\leq{\mathrm{S}_{n}}$ be primitive. The group $G$ is of _type PA_ if
there exist an $\ell\geq 2$, an almost simple primitive group
$A\leq\operatorname{Sym}(\Delta)$ with socle $T$, and a group
$\widehat{G}\leq\operatorname{Sym}(\Delta^{\ell})$ permutation isomorphic to
$G$ with

$\hskip 30.00005pt\operatorname{soc}G\cong T^{\ell}\leq\widehat{G}\leq
A\wr\mathrm{S}_{\ell},$

in product action on $\Delta^{\ell}$.

From Definition 2.2, it is immediate that a large primitive group is either
almost simple or of type PA.

###  4.1 Constructing the normaliser of the socle

In this subsection, we construct
$\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(\operatorname{soc}G)$ when $G$
is large and of type PA. We will require the following well known property:
see [4, Lemma 4.5A], for example.

######  Lemma 4.2.

Let $G$ be primitive of type PA. With the notation of Definition 4.1,
$\operatorname{{\mathrm{N}}}_{\operatorname{Sym}(\Delta^{\ell})}(\operatorname{soc}\widehat{G})=\operatorname{{\mathrm{N}}}_{\operatorname{Sym}(\Delta)}(T)\wr\mathrm{S}_{\ell}$,
in product action.

######  Lemma 4.3.

Let $G=\langle X\rangle\leq{\mathrm{S}_{n}}$ be a large primitive group of
type PA, with $|X|\leq n$. Then we can compute a generating set of size four
for $\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(\operatorname{soc}G)$ in
polynomial time.

###### Proof.

Let $S=\operatorname{soc}G$. Since $G$ is large and of type PA, there exist an
$\ell\geq 2$, $m$ and $k$ such that $S$ is permutation isomorphic to
${\mathrm{A}}_{m}^{\ell}$ acting component-wise on the set of $\ell$-tuples of
$k$-element subsets of $\\{1,\ldots,m\\}$. Let $\Delta$ be the set of
$k$-subsets of $\left\\{1,\ldots,m\right\\}$, and write ${\mathrm{A}}_{k,m}$
and ${\mathrm{S}}_{k,m}$ for the actions of ${\mathrm{A}}_{m}$ and
${\mathrm{S}}_{m}$ on $\Delta$. Let ${\hskip 0.5pt\Gamma}=\Delta^{\ell}$, and
let $W={\mathrm{S}}_{k,m}\wr{\mathrm{S}}_{\ell}\leq\operatorname{Sym}({\hskip
0.5pt\Gamma})$, in product action. Let
$A:=\operatorname{soc}W={\mathrm{A}}_{k,m}^{\ell}\leq\operatorname{Sym}({\hskip
0.5pt\Gamma})$. Then $S$ is permutation isomorphic to $A$. We shall proceed by
first constructing the permutation isomorphism, and then using it to construct
$\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(S)$ as the pre-image of
$\operatorname{{\mathrm{N}}}_{\operatorname{Sym}({\hskip 0.5pt\Gamma})}(A)$.
It is immediate from Lemma 4.2 that
$\operatorname{{\mathrm{N}}}_{\operatorname{Sym}({\hskip 0.5pt\Gamma})}(A)=W$.

We first compute a base and strong generating set for $G$, and find generators
for, and the composition factors of, $S$. Hence we determine $\ell$ and $m$,
and calculate $k$ from $n={m\choose k}^{\ell}$. This can all be done in
polynomial time by Lemma 2.5.

We shall now proceed in three steps. First we will compute an isomorphism
$\iota$ from $S$ to $A$, and generators for
$W=\operatorname{{\mathrm{N}}}_{\operatorname{Sym}({\hskip 0.5pt\Gamma})}(A)$.
Secondly, we will use $\iota$ to construct a permutation isomorphism
$(f,\varphi)$ from $S$ to $A$. Finally, we shall use $f$ to construct
generators for $\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(S)$.

Let $W_{1}\leq{\mathrm{S}}_{ml}$ be the wreath product of ${\mathrm{S}}_{m}$
and ${\mathrm{S}}_{\ell}$, in imprimitive action. We generate $W_{1}$ with a
set $Z$ of size four: two permutations acting non-trivially only on the first
block, to generate one copy of ${\mathrm{S}}_{m}$, and two permutations
generating the top group ${\mathrm{S}}_{\ell}$. Note that
$m\ell\leq\left|\Delta\right|\ell\leq n$, so $Z$ can be written down in
polynomial time. By [3, Theorem 4.1] we can compute in polynomial time an
isomorphism $\iota_{1,1}\colon G\rightarrow K$ for some $K\leq W_{1}$. Notice
that $\operatorname{soc}K=\operatorname{soc}W_{1}$. We can write down the
corresponding two generators for the action of ${\mathrm{S}}_{k,m}$ on
$\Delta$, and lift their action on $\Delta$ to an action on ${\hskip
0.5pt\Gamma}=\Delta^{\ell}$ by letting them act trivially on all but the first
components of ${\hskip 0.5pt\Gamma}$. Then we write down two generators for
the action of ${\mathrm{S}}_{\ell}$ on the components of ${\hskip
0.5pt\Gamma}$, corresponding to those in $Z$. Let $Y$ be this set of four
permutations. Mapping $Z$ to $Y$ yields an isomorphism by generator images
$\iota_{2,1}\colon W_{1}\rightarrow
W={\mathrm{S}}_{k,m}\wr{\mathrm{S}}_{\ell}\leq\operatorname{Sym}({\hskip
0.5pt\Gamma})$. Since $W$ acts on $\left|\Delta\right|^{\ell}=n$ points we can
compute and evaluate $\iota_{2,1}$ in polynomial time, by Lemma 2.6. We let
$\iota_{1}$ and $\iota_{2}$ be the restrictions of $\iota_{1,1}$ and
$\iota_{2,1}$ to the socles of the groups concerned: we can compute the socles
and restrictions in polynomial time by Lemma 2.5 and Lemma 2.6, respectively.
Finally, we let $\iota=\iota_{1}\iota_{2}$ be the isomorphism from $S$ to $A$
given by the composition of these maps.

The groups $A$ and $S$ are permutation isomorphic: denote one such permutation
isomorphism by

$(p,\psi),\mbox{ with }\psi\colon A\rightarrow S,\quad
p\colon\Delta^{\ell}\rightarrow\\{1,\ldots,n\\},$ (1)

and notice that $\psi\iota\in\operatorname{Aut}(A)$.

We shall now use $\iota$ to construct a permutation isomorphism $(f,\varphi)$
from $S$ to $A$. By Lemma 2.7(b), it suffices to find a suitable $\varphi$, as
then $f$ can be constructed in polynomial time. By Lemma 2.7(a), such an $f$
exists if and only if $\varphi$ maps the point stabilisers of $S$ to the point
stabilisers of $A$.

To determine $\varphi$, we first consider the homomorphism:

$\Psi\colon W\rightarrow\operatorname{Aut}(A),~{}x\mapsto(g\mapsto
x^{-1}\\!gx).$

Recall that $\operatorname{{\mathrm{N}}}_{\operatorname{Sym}({\hskip
0.5pt\Gamma})}(A)=W$. Thus $\mathrm{Im}(\Psi)$ consists of exactly those
automorphisms of $A={\mathrm{A}}_{k,m}^{\ell}$ which are induced by
permutations of ${\hskip 0.5pt\Gamma}$.

Assume first that $m=5$ or $m\geq 7$, so that $\Psi$ is surjective. In this
case we shall define $\varphi:=\iota$. To see that $\varphi$ maps point
stabilisers to point stabilisers, let $\psi$ be as in (1), so that
$\psi\iota=\psi\varphi\in\operatorname{Aut}(A)$. Then there exists an element
$w\in W\leq\operatorname{Sym}({\hskip 0.5pt\Gamma})$ with $w\Psi=\psi\varphi$.
Hence $\psi\varphi$ permutes the point stabilisers of $A$, and so by Lemma
2.7(a) the map $\varphi$ induces a permutation isomorphism.

Now let $m=6$, so that the image of ${\mathrm{S}}_{k,6}$ under
$\Psi_{0}\colon{\mathrm{S}}_{k,6}\rightarrow\operatorname{Aut}({\mathrm{A}}_{k,6})$
has index 2 in $\operatorname{Aut}({\mathrm{A}}_{k,6})$. Correspondingly the
index $[\operatorname{Aut}(A):W\Psi]=2^{\ell}$. In constant time we can
compute generator images for an involutory automorphism
$\tau\in\operatorname{Aut}({\mathrm{A}}_{k,6})\setminus({\mathrm{S}}_{k,6}\Psi_{0})$.
Hence we can compute generator images for
$\tau_{1},\ldots,\tau_{\ell}\in\operatorname{Aut}(A)$, where each $\tau_{i}$
induces $\tau$ on a distinct direct factor of $A$, and the identity on the
other factors. Notice that $L:=\langle\tau_{1}\ldots,\tau_{\ell}\rangle\cong
C_{2}^{\ell}$, so that $|L|=2^{\ell}\leq n$.

Let $(p,\psi)$ be as in (1), so that $\psi\iota\in\operatorname{Aut}(A)$. Then
there exists a $\theta\in L$ such that $\psi\iota\theta\in W\Psi$. In
particular, $\psi\iota\theta$ maps point stabilisers to point stabilisers, and
hence by Lemma 2.7(a) $\iota\theta$ does so too. We can test in polynomial
time whether the image of a point stabiliser is a point stabiliser, so we can
check each of the $O(n)$ elements of $L$ to find such a $\theta$ in polynomial
time. We then set $\varphi=\iota\theta$.

Finally, the bijection $f^{-1}$ induces an isomorphism from
$\operatorname{Sym}({\hskip 0.5pt\Gamma})$ to ${\mathrm{S}_{n}}$ that maps
$W={\mathrm{S}}_{k,l}\wr{\mathrm{S}}_{\ell}$ to the normaliser
$\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(S)$. Recall the set $Y$ of
generators for $W$. We can compute $Y{f^{-1}}$ in polynomial time, and
$\left\langle\,Yf^{-1}\,\right\rangle=\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(S)$.
∎

###  4.2 Computing the normaliser in ${\mathrm{S}_{n}}$ of a large group

Many of our results in this subsection apply directly to all primitive groups
$G$ that are either almost simple or of type PA. Our approach yields a “very
moderately” quasipolynomial time algorithm: $O(2^{\log n\log\log n})$.

Throughout this subsection, let $G\leq{\mathrm{S}_{n}}$, and let
$M=\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(\operatorname{soc}G)$. We
first relate the complexity of computing
$\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(G)$ to the index $[M:G]$.

######  Lemma 4.4.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ be primitive, with
$|X|\leq n$. Assume that a base and strong generating set for $G$ are known.
Furthermore, let a generating set $Y$ for $M$ be given, with $|Y|\leq n$. Then
we can compute the normaliser
$\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(G)$ in time $O(n^{3}[M:G]^{2})$.

###### Proof.

First notice that $\operatorname{soc}G$ is normal in
$\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(G)$, and so
$\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(G)$ is a subgroup of $M$. Since
$G\leq M$, to compute $\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$ it
suffices to test only the representatives of the right cosets $G\backslash M$
of $G$ in $M$.

We shall compute the representatives of $G\backslash M$ by a standard orbit
algorithm. To determine equality of cosets $Ga$ and $Gb$ we test whether
$ab^{-1}\in G$, in time $O(n^{2})$ by Lemma 2.5(c). The cost of the
computation of these coset representatives is then the product of the number
of generators $\left|Y\right|$, the size of the orbit $[M:G]$, and the cost
$[M:G]\cdot n^{2}$ for testing whether a representative of a newly computed
coset $(Ga)y$ for $y\in Y$ is contained in one of the up to $[M:G]$ already
computed cosets. In total this takes $O(\left|Y\right|\cdot
n^{2}\cdot[M:G]\cdot[M:G])=O(n^{3}[M:G]^{2})$ time.

Next, for $h$ a coset representative, we can test whether $x^{h}\in G$ for all
$x\in X$ in time $O(n^{3})$. We can therefore test all such representatives
$h$ in time $O(n^{3}\cdot[M\nobreak:\nobreak G])$. The result follows. ∎

Luks and Miyazaki showed in [13, Corollary 3.24] that normalisers in
${\mathrm{S}_{n}}$ of non-abelian simple groups can be computed in polynomial
time. We very slightly extend their argument, to almost simple groups: the
following result does not require transitivity.

######  Lemma 4.5.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ be almost simple,
with $|X|\leq n$. Then we can compute
$\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$ in polynomial time.

###### Proof.

By Lemma 2.5(b), we can compute a base and strong generating set for $G$, and
generators for $T:=\operatorname{soc}G$, in polynomial time.

By [13, Lemma 3.3] we can compute $C:=C_{{\mathrm{S}_{n}}}(G)$, and then
arguing as in the proof of [13, Corollary 3.24] we can determine in polynomial
time which elements of $\operatorname{Aut}T$ are induced by
$N_{{\mathrm{S}_{n}}}(T)$, and construct an almost simple group $A$ with socle
$T$ which induces all of these automorphisms. Let $M=\langle C,A\rangle$. Then
$M=\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(T)$. By [7, Lemma 7.7],
there exists an absolute constant $\kappa$ such that
$\left|\operatorname{Out}T\right|\leq\kappa\sqrt{n}$. Hence
$[M:G]\leq\kappa\sqrt{n}$. The result is now immediate from Lemma 4.4. ∎

Next we consider the normalisers of the socles of groups of type PA.

######  Proposition 4.6.

There exists a constant $c$ such that for all groups $G\leq{\mathrm{S}_{n}}$
of type PA

$[M:\operatorname{soc}G]\leq 2^{c\log n\log\log n}.$

###### Proof.

Let $T\leq\operatorname{Sym}\Delta$ be a non-abelian simple group such that
$S:=\operatorname{soc}G$ is permutation isomorphic to
$T^{\ell}\leq\operatorname{Sym}\Delta^{\ell}$. Then
$M\cong\operatorname{{\mathrm{N}}}_{\operatorname{Sym}\Delta}(T)\wr\mathrm{S}_{\ell}$,
by Lemma 4.2. Now $\ell=\log_{\left|\Delta\right|}n\leq\log n$ and by [7]
there exists a constant $\kappa$ such that
$\left|\operatorname{Out}T\right|\leq\kappa\sqrt{\left|\Delta\right|}=\kappa
n^{1/(2\ell)}$. Let $\lambda=\log\kappa$. Then

$\displaystyle[M:S]$
$\displaystyle\leq\left|\operatorname{Out}T\right|^{\ell}\left|\mathrm{S}_{\ell}\right|\leq\left(\kappa
n^{1/(2\ell)}\right)^{\ell}\cdot\ell^{\ell}\leq 2^{\lambda\log n}\cdot
n^{1/2}\cdot\left(\log n\right)^{\log n}$ $\displaystyle\leq 2^{\lambda\log
n+(1/2)\log n+\log n\log\log n}=2^{c\log n\log\log n},$

for a suitable choice of $c$. ∎

######  Proposition 4.7.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ be primitive of
type PA, with $|X|\leq n$. If a generating set $Y$ of size at most $n$ is
known for $M$, then we can compute the normaliser
$\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(G)$ in time $2^{O(\log n\log\log
n)}$.

###### Proof.

By Lemma 2.5(b) we can compute a base and strong generating set for $G$ in
polynomial time. Given this data and $Y$, by Lemma 4.4 we can compute
$\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$ in time
$O(n^{3}[M:G]^{2})$. By Proposition 4.6 the index $[M:G]\leq 2^{c\log
n\log\log n}$ for some constant $c$. The result follows. ∎

The following corollary completes the proof of Theorem 1.1.

######  Corollary 4.8.

Let $G=\left\langle\,X\,\right\rangle\leq{\mathrm{S}_{n}}$ be a large
primitive group. Then the normaliser
$\operatorname{{\mathrm{N}}}_{\mathrm{S}_{n}}(G)$ can be computed in time
$\left|X\right|\cdot 2^{O(\log n\log\log n)}$.

###### Proof.

By Lemma 2.5 we can replace $X$ by a set of at most $n$ generators in
$O(|X|n^{2}+n^{5})$, and we can determine whether $G$ is almost simple in
polynomial time. If $G$ is almost simple, then we can compute
$\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$ in polynomial time, by
Lemma 4.5. Otherwise, $G$ is of type PA. By Lemma 4.3 we can construct a
generating set of size four for
$M:=\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(\operatorname{soc}G)$ in
polynomial time. Hence by Proposition 4.7 we can compute
$\operatorname{{\mathrm{N}}}_{{\mathrm{S}_{n}}}(G)$ in time $2^{O(\log
n\log\log n)}$. ∎

#### Acknowledgements

The second author is supported by DFG research training group “Experimental
and Constructive Algebra”. The first author would like to thank the Isaac
Newton Institute for Mathematical Sciences for support and hospitality during
the programme “Groups, Representations and Applications: New perspectives”,
when work on this paper was undertaken. This work was supported by: EPSRC
grant number EP/R014604/1. We thank Professor Babai for drawing our attention
to the relationship between the string isomorphism problem and the Luks class.

## References

  * [1] L. Babai.  Graph isomorphism in quasipolynomial time.  arXiv e-prints 1512.03547, Dec 2015.
  * [2] L. Babai.  Graph isomorphism in quasipolynomial time.  In Proceedings of STOC’16, pages 684–697. ACM, New York, 2016\.
  * [3] L. Babai, E.M. Luks, and A. Seress.  Permutation groups in NC.  In Proceedings of STOC ’87, pages 409–420. ACM, 1987.
  * [4] J.D. Dixon and B. Mortimer.  Permutation Groups.  Springer, 1996.
  * [5] H. Duyan, Z. Halasi, and A. Maróti.  A proof of Pyber’s base size conjecture.  Adv. Math., 331:720–747, 2018.
  * [6] M. Furst, J. Hopcroft, and E. Luks.  Polynomial-time algorithms for permutation groups.  In Proc. SFCS ’80, pages 36–41, USA, 1980. IEEE.
  * [7] R.M. Guralnick, A. Maróti, and L. Pyber.  Normalizers of primitive permutation groups.  Adv. Math., 310:1017–1063, 2017.
  * [8] Z. Halasi, M.W. Liebeck, and A. Maróti.  Base sizes of primitive groups: bounds with explicit constants.  J. Algebra, 521:16–43, 2019.
  * [9] H.A. Helfgott.  Isomorphismes de graphes en temps quasi-polynomial (d’après Babai et Luks, Weisfeiler-Leman).  Astérisque, 407:135–182, 2019.
  * [10] D.F. Holt and C.M. Roney-Dougal.  Minimal and random generation of permutation and matrix groups.  J. Algebra, 387:195–214, 2013.
  * [11] E.M. Luks.  Isomorphism of graphs of bounded valence can be tested in polynomial time.  J. Comput. System Sci., 25(1):42 – 65, 1982.
  * [12] E.M. Luks.  Permutation groups and polynomial-time computation.  In L. Finkelstein and W.M. Kantor, editors, Groups and Computation, 1991. DIMACS/AMS, 1991.
  * [13] E.M. Luks and T. Miyazaki.  Polynomial-time normalizers.  Discrete Math. Theor. Comput. Sci., 13(4):61–96, 2011.
  * [14] A. Maróti.  On the orders of primitive groups.  J. Algebra, 258(2):631–640, 2002.
  * [15] C.C. Sims.  Computational methods in the study of permutation groups.  In J. Leech, editor, Computational Problems in Abstract Algebra, pages 169 – 183. Pergamon, 1970.
  * [16] D. Wiebking.  Normalizers and permutational isomorphisms in simply-exponential time.  arXiv e-prints 904.10454, Apr 2019.