Bachelorarbeit in Mathematik
eingereicht an der Fakultät für Mathematik und Informatik
der Georg-August-Universität Göttingen
am

Überarbeitete Fassung vom 23. September 2019

von

Erstgutachter:

Prof. Dr. Harald Andrés Helfgott

Zweitgutachter:

Prof. Dr. Stephan Waack

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Permutation Groups and their actions
    2. 2.2 Graph and String Isomorphism Problem
    3. 2.3 Canonicity
    4. 2.4 Measures of Complexity
    5. 2.5 Combinatorial structures
    6. 2.6 Twins and Symmetry Defects
    7. 2.7 Colored partitions
  3. 3 Algorithmic Building Blocks
    1. 3.1 Orbits and Blocks
    2. 3.2 Schreier-Sims and derived algorithms
    3. 3.3 Luks’ method
    4. 3.4 Identification of groups and schemes
    5. 3.5 Partition pullback
    6. 3.6 Design Lemma
  4. 4 Overview of the Algorithm
    1. 4.1 First steps
    2. 4.2 The primitive case and the case of large symmetry
  5. 5 Local certificates
    1. 5.1 Construction of local certificates
    2. 5.2 Comparing certificates
    3. 5.3 Aggregation of certificates
    4. 5.4 Effect of the discovery of canonical structures
  6. 6 Time complexity
  7. Acknowledgements

##  Chapter 1 Introduction

Graphs are fundamental combinatorial objects. Defined as a tuple $(V,E)$ of a
set of vertices $V$ and a set of edges $E\subseteq V\times V$ connecting the
vertices, they can be used to formalize structures in many areas of
mathematics, computer science and other fields. For example, a graph could
represent a molecule with atoms as vertices and covalent bonds as edges, or a
social network with individuals as vertices and friendships as edges.

Given two graphs $X_{1}=(V,E_{1})$ and $X_{2}=(V,E_{2})$ on the same set of
vertices $V$ of size $n$ one may ask whether these two graphs are essentially
the same, i.e. whether there exists a bijection $\pi:V\to V$ such that two
vertices $v,w\in V$ are adjacent in $X_{1}$ if and only if their images
$\pi(v)$ and $\pi(w)$ are adjacent in $X_{2}$. Being capable of answering this
question efficiently would help us to search for chemical compounds in a
database or to recognize patterns in social networks. Hence, it is desirable
to design a fast algorithm which either computes such a bijection $\pi$ or
confirms that no such $\pi$ exists – in which case the two graphs are said to
be not isomorphic. The _Graph Isomorphism Problem_ (GI) is the problem of
computationally determining $\pi$ or confirming that no such $\pi$ exists.

Trivially, one could try to scan through all possible bijections and check
whether they preserve adjacency. Since the total number of possible bijections
is $n!$, this simplest strategy satisfies by Stirling’s formula

$T(n)\leq Cn!\asymp\sqrt{n}\left(\frac{n}{e}\right)^{n}$ (1.1)

for a constant $C>0$ and with $T(n)$ denoting the number of elementary
operations required to obtain an answer given two graphs with $n$ vertices.
This enormous growth behavior renders the trivial approach practically useless
and theoretically uninteresting.

An open question in complexity theory is whether the Graph Isomorphism Problem
can be decided in polynomial time, that is,

$T(n)\leq n^{C}$ (1.2)

for a constant $C>0$. In 2015, László Babai [Bab15] proposed an algorithm
which decides GI in quasi-polynomial time, that is,

$T(n)\leq\exp\left((\log n)^{C}\right)$ (1.3)

for a constant $C>0$. Babai’s algorithm is based on the work of Eugene Luks
[Luk82], who proved in 1981 that the isomorphicity of graphs with bounded
degree can be tested in polynomial time. Pushing down the bound from
exponential (eq. 1.1) to quasi-polynomial (eq. 1.3), was a huge leap.
Nevertheless a polynomial bound (eq. 1.2) remains out of reach. Therefore, GI
continues to be an interesting problem for exploring the connection between
the two main complexity classes P and NP.

This thesis provides an explanation of Babai’s algorithm with a particular
focus on the case that cannot be dealt with by Luks’ method. Group theoretic
and combinatorial arguments are used to tackle this situation, which prevented
significant progress for more than thirty years. The thesis extends the
explanations provided by Harald Andrés Helfgott [Hel17a]111For linguistic
reasons, we will henceforth not refer to the French original [Hel17a] but to
its English translation [HBD17]. and by Babai [Bab15, Bab18]222The more recent
[Bab18] represents an extended yet incomplete revision of the main article
[Bab15]. We will mostly refer to [Bab15] except for one minor part of section
5.3. himself. After introducing the relevant objects and some of their
properties in chapter 2, we will describe important subroutines and general
strategies which will be used repeatedly throughout the algorithm in chapter
3. Chapter 4 gives an overview of the algorithm laying the ground work for
chapter 5 which treats Luks’ barrier case with local certificates. In chapter
6 we will justify the algorithms’ quasi-polynomial complexity. We will
reproduce Helfgott’s stronger result that $C=3$ suffices in eq. 1.3.

Even though the Graph Isomorphism Problem is of vast theoretical interest, the
applications of Babai’s algorithm in – for instance – chemistry or social
sciences are limited. For practical use cases, faster heuristic methods
suffice to test whether graphs are isomorphic or to find patterns in graphs.
[MP13] provides an overview of these strategies and their implementation in
tools such as _nauty_ and _Traces_.

##  Chapter 2 Preliminaries

In its most basic version the Graph Isomorphism Problem takes as an input two
graphs and returns an adjacency-preserving bijection of the set of vertices or
the confirmation that the two graphs are not isomorphic. In this section we
want to describe a more general setting. In order to do so, we need some basic
vocabulary. The starting point are permutation groups which arise from the
bijections between the two graphs. We will then formalize the Graph
Isomorphism Problem and finally state the definitions and properties of some
combinatorial objects.

###  2.1 Permutation Groups and their actions

We state some notions for permutation groups and their actions. See [DM96] for
a comprehensive introduction.

######  Definition 1.

Let $\Omega$ be a finite set. We denote the symmetric group acting with its
canonical action on $\Omega$ as $\Sym(\Omega)$ and the alternating group
respectively as $\Alt(\Omega)$. When simply $\Omega=\\{1,\dots,n\\}$, we
denote these groups as $\Sym_{n}$ and $\Alt_{n}$. For $\omega\in\Omega$ and
$\sigma\in\Sym(\Omega)$ we write $\omega^{\sigma}$ for $\sigma(\omega)$. We
write $A^{g}\coloneqq\\{a^{g}\mid a\in A\\}$ for $A\subseteq\Omega$, $g\in G$
and $A^{H}\coloneqq\left\\{a^{h}\ \middle|\ a\in A,\ h\in H\right\\}$ for
$H\subseteq G$.

We will write $(a\ b)$ for the transposition sending $a\mapsto b$ and
$b\mapsto a$ and analogously $(a_{1}\ a_{2}\ \cdots\ a_{m})$ for longer
cycles. For groups $H$ and $G$ we write $H\leq G$ if $H$ is a subgroup of $G$.
The index of a subgroup will be denoted as $\gindex{G}{H}$. We will generally
use the superscript notation for maps, i.e. for $\psi:A\to B$ we write
$a^{\psi}$ instead of $\psi(a)$ for $a\in A$. For a set
$B\subseteq\Sym(\Omega)$ we write $\generate{B}$ for the subgroup of
$\Sym(\Omega)$ generated by the elements in $B$. For a map $\psi:A\to B$ and a
subset $A^{\prime}\subseteq A$ we write $\restrict{\psi}{A^{\prime}}$ for the
restriction of $\psi$ to the map $A^{\prime}\to B$,
$a^{\prime}\mapsto\psi(a^{\prime})$.

######  Definition 2.

A _permutation group_ is a subgroup $G\leq\Sym(\Omega)$ of the symmetric
group. $\Omega$ is said to be the _domain_ of $G$.

The two largest permutation groups are $\Sym(\Omega)$ and $\Alt(\Omega)$.
Babai calls them the _giants_. In disguise they appear in chapter 5 when we
discuss the core group-theoretic algorithm.

Central to the entire thesis are strings since we will reduce the Graph
Isomorphism Problem shortly to the problem of determining string isomorphisms.

######  Definition 3 (Strings).

A string $\str x$ is a map $\Omega\to\Sigma$ from a finite set $\Omega$ of
_positions_ to a finite set $\Sigma$ of _letters_ , the _alphabet_. Let
$\Sigma^{\Omega}$ denote the set of all strings.

In examples we will write strings simply as chains of characters, e.g. $\str
x=\mathsf{raspberry}$ for $\Omega=\\{1,\dots,9\\}$ and the lower case English
alphabet $\Sigma=\\{\mathsf{a},\dots,\mathsf{z}\\}$.

The action of $\Sym(\Omega)$ on $\Omega$ induces an action on
$\Sigma^{\Omega}$. We define $\str x^{\sigma}(i)\coloneqq\str
x\left(i^{\sigma^{-1}}\right)$ for all $i\in\Omega$, $\str
x\in\Sigma^{\Omega}$, $\sigma\in\Sym(\Omega)$. This twist is necessary in
order to have for all $i\in\Omega$ the convenient relation

$\str x^{\sigma\tau}(i)=\str x\left(i^{(\sigma\tau)^{-1}}\right)=\str
x\left(\left(i^{\sigma^{-1}}\right)^{\tau^{-1}}\right)=\str
x^{\sigma}\left(i^{\tau^{-1}}\right)=\left(\str x^{\sigma}\right)^{\tau}(i).$
(2.1)

Moreover, the action of $\Sym(\Omega)$ on $\Omega$ induces an action on
$\binom{\Omega}{k}=\\{A\subseteq\Omega\mid\abs{A}=k\\}$ for $k\geq 1$, the set
of $k$-sized subsets of $\Omega$. Without lost of generality we can assume
that $k\leq\abs{\Omega}/2$.

######  Definition 4 (Johnson groups, [Bab15, §1.2.1]).

If the groups $\Alt(\Omega)$ or $\Sym(\Omega)$ act on $\binom{\Omega}{k}$ with
their induced actions, they are called _Johnson groups_. We will write
$\Alt^{(k)}(\Omega)$ or $\Sym^{(k)}(\Omega)$, respectively. For
$\Omega=\\{1,\dots,m\\}$, we write $\Sym_{m}^{(k)}$ and $\Alt_{m}^{(k)}$,
respectively.

Johnson groups are the barrier that prevented the Graph Isomorphism Problem to
be decided in polynomial time for over thirty years. They are the automorphism
groups of Johnson schemes, cf. lemma 2.5.6.

[Stabilizers] A subset $\Delta\subseteq\Omega$ is said to be invariant under
$G$ if $\Delta^{g}=\Delta$ for all $g\in G$. We denote the _setwise
stabilizer_ of $\Delta$, i.e. the set of all $g\in G$ such that
$\Delta^{g}=\Delta$, as $G_{\Delta}$. The _pointwise stabilizer_ will be
denoted as $G_{(\Delta)}$. It is the set of all $g\in G$ satisfying
$\delta^{g}=\delta$ for all $\delta\in\Delta$.

For a permutation group $G\leq\Sym(\Omega)$, a subset $\Delta\subseteq\Omega$
and a group $H\leq G_{\Delta}$ we will write $\restrict{H}{\Delta}$ for the
group of permutations restricted to the domain $\Delta$ and taken from $H$.
Hence, $\restrict{H}{\Delta}\leq\Sym(\Delta)$.

######  Definition 5 (Transitivity, Primitivity).

Let $G\leq\Sym(\Omega)$ act on $\Omega$. The _orbit_ of an $\omega\in\Omega$
is the set $\omega^{G}$. The orbits partition the domain $\Omega$. If $G$
acting on $\Omega$ admits only one orbit, namely $\Omega$, the action is said
to be _transitive_ and $G$ is called _transitive_ whenever the action is
evident from the context. The action of $G$ is said to be _$k$ -transitive_
for $1\leq k\leq\abs\Omega$ if the induced action on the set of distinct
$k$-tuples drawn from $\Omega$ is transitive.

Suppose that $G$ is transitive. A non-empty subset $\Delta\subseteq\Omega$ is
called a _block_ of $G$ if for each $g\in G$ either $\Delta^{g}=\Delta$ or
$\Delta^{g}\cap\Delta=\emptyset$. For a block $\Delta$ the set
$\left\\{\Delta^{g}\ \middle|\ g\in G\right\\}$ is called a _system of
blocks_. Such a system partitions $\Omega$. A block is said to be _non-
trivial_ if it is neither a singleton nor the entire domain. If $G$ acting
transitively on $\Omega$ does not admit non-trivial blocks, the action is said
to be _primitive_ and $G$ is called _primitive_.

A transitive group action induces an action on any system of blocks
$\mathscr{B}$. This can be rephrased by inferring a homomorphism
$\psi:G\to\Sym(\mathscr{B})$. A system of blocks $\mathscr{B}$ is said to be
_minimal_ if the induced action on it is primitive, i.e. $G^{\psi}$ acts
primitively on $\mathscr{B}$. The _stabilizer_ of a system of blocks
$\mathscr{B}=\\{\Delta_{1},\dots,\Delta_{m}\\}$ is the subgroup $N\leq G$ of
permutations $g\in G$ with the property $\Delta_{i}^{g}=\Delta_{i}$ for all
$1\leq i\leq m$. We have, $N=\ker\psi$.

######  Example 2.1.1.

Let $n\in\mathbb{N}$. The symmetric group $\Sym_{n}$ is $n$-transitive and
hence $k$-transitive for all $1\leq k\leq n$. The alternating group $\Alt_{n}$
is $(n-2)$-transitive: For given tuples $x\coloneqq(x_{1},\dots,x_{n-2})$ and
$y\coloneqq(y_{1},\dots,y_{n-2})$ we can construct an arbitrary permutation
$\sigma\in\Sym_{n}$ mapping $x$ to $y$. Let $x^{\prime},x^{\prime\prime}$
denote the two values not contained in $x$ and $y^{\prime},y^{\prime\prime}$
the two values not contained in $y$. Then either
$\sigma(x^{\prime})=y^{\prime}$ and
$\sigma(x^{\prime\prime})=y^{\prime\prime}$ or
$\sigma(x^{\prime})=y^{\prime\prime}$ and
$\sigma(x^{\prime\prime})=y^{\prime}$ by bijectivity. The two possibilities
differ by a single transposition, namely $(y^{\prime}\ y^{\prime\prime})$.
Hence, either $\sigma$ or $\sigma(y^{\prime}\ y^{\prime\prime})$ is even and
maps $x$ to $y$. We have constructed an element from $\Alt_{n}$ mapping $x$ to
$y$.

######  Example 2.1.2.

An example for a non-primitive group is the symmetry group of the square known
as the dihedral group $D_{8}\leq\Sym_{4}$. We number the vertices of the
square clockwise as $1,2,3,4$. The elements of $G$ send
$\Delta\coloneqq\\{1,3\\}$ either to itself or to its complement. Thus,
$\mathscr{B}\coloneqq\left\\{\\{1,3\\},\\{2,4\\}\right\\}$ is a system of
blocks. We have a map $D_{8}\to\Sym(\mathscr{B})$ with the property that its
kernel is generated by the reflections across the square’s diagonals. The
induced action is primitive, hence $\mathscr{B}$ is minimal.

The term minimal must be used carefully. It is the number of blocks that is
minimal whereas their size is maximal in the sense that the action on any
courser system of blocks would admit non-trivial blocks. We make a
straightforward observation:

######  Lemma 2.1.3.

Let $A,B\subseteq\Omega$ be two non-disjoint blocks under the action of
$G\leq\Sym(\Omega)$. Then $A\cap B$ is a block under the same action.

######  Proof 2.1.4.

We distinguish two cases. First assume that $g\in G$ satisfies $A^{g}=A$ and
$B^{g}=B$. Then clearly, $(A\cap B)^{g}=A^{g}\cap B^{g}=A\cap B$ since $g$ is
bijective. Contrarily, let without loss of generality $A^{g}\cap A=\emptyset$.
Then, $(A\cap B)^{g}\cap(A\cap B)=A^{g}\cap B^{g}\cap A\cap B=\emptyset$.
Hence, $A\cap B\neq\emptyset$ is a block.

######  Definition 6.

Two permutation groups $G\leq\Sym(\Omega)$ and
$G^{\prime}\leq\Sym(\Omega^{\prime})$ are said to be _permutation isomorphic_
if their exists a group isomorphism $\varphi:G\to G^{\prime}$ and a bijection
$\iota:\Omega\to\Omega^{\prime}$ satisfying for all $\omega\in\Omega$ and
$g\in G$,

$\iota\left(\omega^{g}\right)=\iota(\omega)^{\varphi(g)}.$

Throughout the algorithm we will maintain two maps with similar properties.
They originate in section 3.4. We establish one final convention:

######  Definition 7.

From a computational perspective, groups are given to us as sets of
generators. We refer to such a set as a _description_ of the group.
_Describing_ a group means to compute a description. A homomorphism $\varphi$
between two groups is stored a collection of tuples $(g,g^{\varphi})$ where
$g$ runs through a set of generators. Such a representation is said to be a
_description_ of the homomorphism.

The complexity estimates for many fundamental procedures, e.g. in sections 3.1
and 3.2, will depend on the size of the set of generators. Potentially, the
set of generators could be as large as the permutation group itself. However,
by [Bab86], the size of any minimal set of generators for a subgroup of
$\Sym_{n}$ is bounded by $2n$. We can hence assume that the sizes of the
generating sets that we deal with are polynomially bounded in $n$, cf. section
2.4.

###  2.2 Graph and String Isomorphism Problem

In chapter 1 we introduced a first basal version of the Graph Isomorphism
Problem: Given two directed graphs $X_{1}=(V,E_{1})$ and $X_{2}=(V,E_{2})$ on
a shared finite vertex set $V$ with edge sets $E_{1},E_{2}\subseteq V\times
V$, we are asked to decide whether there exists an adjacency-preserving
bijection $\pi:V\to V$, i.e. a map satisfying $(v,w)\in
E_{1}\iff(\pi(v),\pi(w))\in E_{2}$ for all $v,w\in V$. The result consists
either of such a map $\pi$ or the verification that no such map exists.

However, we will ask a more general question. Given the same input, we want to
compute the set of all adjacency-preserving bijections $\pi$. If we can
compute this set in quasi-polynomial time, cf. eq. 1.3, we can clearly also
answer the question from above in quasi-polynomial time.

Numerous data formats are used for encoding graphs. For instance, they can be
stored as linked objects, edge lists or vertex lists. A widely used data
format are adjacency matrices. The adjacency matrix of $G=(V,E)$ is a string
$\str x:V\times V\to\\{0,1\\}$ with $\str x(v,w)=1\iff(v,w)\in E$. Thinking of
graphs as such strings leads to a further reduction of the problem. Instead of
asking for graph isomorphisms, one may ask for string isomorphism.

######  Definition 8.

Given two strings $\str x,\str y:\Omega\to\Sigma$ and a group
$G\leq\Sym(\Omega)$, the _String Isomorphism Problem_ is the task of
determining

$\Iso_{G}(\str x,\str y)=\left\\{\pi\in G\ \middle|\ \str x^{\pi}=\str
y\right\\},$

the set of _string isomorphism_ between $\str x$ and $\str y$ taken from $G$.
We write $\Aut_{G}(\str x)=\Iso_{G}(\str x,\str x)$. If $\Iso_{G}(\str x,\str
y)\neq\emptyset$, we can write

$\Iso_{G}(\str x,\str y)=\Aut_{G}(\str x)\sigma$

for a $\sigma\in\Iso_{G}(\str x,\str y)$. We present the solution of the
String Isomorphism Problem as a description of the group $\Aut_{G}(\str x)$
and a suitable $\sigma$.

Imposing the condition that the bijections have to be taken from a certain
group is very natural. For example, the problem of computing the adjacency-
preserving bijections between the digraphs $X_{1}$ and $X_{2}$ reduces in
polynomial time to the problem of finding $\Iso_{G}(\str x_{1},\str x_{2})$
where $\str x_{i}$ is the adjacency matrix of $X_{i}$ for $i=1,2$ and $G$ is
the image of $\Sym(V)$ under the canonical homomorphism
$\Sym(V)\to\Sym(V\times V)$. Intuitively, the group encodes which positions in
the strings belong together as they represent edges sharing a common vertex.
We have reduced the Graph Isomorphism Problem to the String Isomorphism
Problem in polynomial time. If we can solve the latter in quasi-polynomial
time, we can solve the former in quasi-polynomial time. The fact that a graph
of $n$ vertices transforms into a string of length $n^{2}$ does only affect
the implicit constants. Overtly, the String Isomorphism Problem is far more
general than the initial Graph Isomorphism Problem as it deals with arbitrary
alphabets with possibly more than two letters and arbitrary permutation
groups.

For undirected graphs the reduction is similar. A graph $G=(V,E)$ with
$E\subseteq\binom{V}{2}$ is encoded as an adjacency matrix $\str
x:\binom{V}{2}\to\\{0,1\\}$ as above.

Now we are ready to state Babai’s grand result whose justification will occupy
us for the rest of this thesis.

######  Theorem 2.2.1 (Babai, [Bab15]).

The String Isomorphism Problem can be solved in quasi-polynomial time in the
length of the strings.

###  2.3 Canonicity

The notion of canonicity will be important throughout the entirety of the
algorithm. In particular, we will be interested in computing canonical
structures based on the two input strings $\str x,\str y:\Omega\to\Sigma$.
Suppose that a group $G\leq\Sym(\Omega)$ acts on $\Omega$ and hence on the set
of strings $\Sigma^{\Omega}$. Let $\mathscr{X}$ denote a set of structures,
e.g. a set of partitions of the domain $\Omega$. Suppose additionally that $G$
acts on $\mathscr{X}$, for example by permuting the sets of the partition. An
assignment $C:\Sigma^{\Omega}\to\mathscr{X}$ is said to be _canonical_ with
respect to $G$ if the action of $G$ commutes with $C$.

A basal example for canonical assignments are colorings according to letter
multiplicities. For a string $\str x\in\Sigma^{\Omega}$ we color
$\omega\in\Omega$ according to the multiplicity of $\str x(\omega)$ in $\str
x$. For instance, $\str x=\mathsf{banana}$ would be mapped to the sequence
$(1,3,2,3,2,3)$. Clearly, $G\leq\Sym(\Omega)$ acts on the set of such
colorings by permuting the positions. The assignment commutes with the group
actions.

A non-canonical assignment would be a coloring of $\omega\in\Omega$ according
to whether $\str x(\omega)$ is surrounded by vowels. The example string $\str
x$ would be mapped to $(0,1,0,1,0,0)$ where $1$ encodes yes. Applying the
transposition $\tau=(1\ 2)$ results in the non-edible $\str
x^{\tau}=\mathsf{abnana}$ which is mapped to $(0,0,0,0,1,0)$. Thus, this
assignment does not satisfy $C(\str x^{\tau})=\left(C(\str x)\right)^{\tau}$.
$C$ is not canonical with respect to any supergroup of $\generate{(1\ 2)}$.

Canonical structures are an important tool for refuting isomorphicity. This
happens based on the fact that the set $\Iso_{G}(\str x,\str y)$ can only be
non-empty if $\Iso_{G}\left(C(\str x),C(\str y)\right)$ is non-empty. For
example, two strings can only be isomorphic if there exists a permutation
respecting their letter multiplicities. In any case, $\Iso_{G}(\str x,\str
y)\subseteq\Iso_{G}\left(C(\str x),C(\str y)\right)$. This allows us to limit
the set of possible isomorphisms. The challenge will be to compute canonical
structures sufficiently fast.

###  2.4 Measures of Complexity

We will use Landau’s and Vinogradov’s notation for denoting the asymptotic
growth behavior of functions under the tacit assumption that we take limits
towards $+\infty$. For example, $f(n)=O(g(n))$ and $f(n)\ll g(n)$ are by
definition equivalent to $\limsup_{n\to\infty}\abs{f(n)/g(n)}<\infty$ for
$f,g:\mathbb{R}\to\mathbb{R}$. We write $f(n)\asymp g(n)$ if $f(n)=O(g(n))$
and $g(n)=O(f(n))$. For measuring complexity, we introduce the following
classes of functions.

######  Definition 9.

We call a function $f:\mathbb{R}\to\mathbb{R}$

  1. 1.

poly-logarithmic if $f(n)\ll(\log n)^{O(1)}$,

  2. 2.

polynomial if $f(n)\ll n^{O(1)}$,

  3. 3.

quasi-polynomial if $f(n)\ll\exp\left((\log n)^{O(1)}\right)$.

The natural logarithm will be denoted by $\log$. Furthermore, $\log_{b}$ will
denote the logarithm with respect to base $b$.

In chapter 6 we will analyze the complexity of the entire algorithm. Our aim
is to obtain a quasi-polynomial bound on the overall execution time, cf. eq.
1.3. Central to the algorithm is the divide-and-conquer paradigm of
recursively breaking down a problem into several subproblems. It will turn out
that the tree spanned by the branching subproblems is of poly-logarithmic
depth. Until we make this rigorous, we should keep in mind that we can in
general afford polynomial non-recursive operations. This means that we do not
care about the exponents in polynomial bounds. Even quasi-polynomial
subroutines are affordable, although they occur rarely.

###  2.5 Combinatorial structures

Despite that this thesis focuses on Babai’s group theoretic tools, we will
still require some combinatorial structures and methods. The presentation will
be very limited. See [Bab15, §§2.3–2.6] and [HBD17, §§2.3, 2.4] for a full
overview.

In each of the following definitions we have a finite set $\Gamma$ on which we
want to define a structure, and a set of colors $\mathscr{C}$, as well finite.
We generalize the notion of colored graphs. In a vertex-colored graph every
vertex is assigned a color. This induces on the one hand a partition of the
vertex set in color classes and on the other hand a map from the set of
vertices to the set of colors. We will use the same principle but for coloring
vectors of vertices instead of single nodes. Note that we do not ask two
adjacent vertices two have different colors as it is often done when studying
graph colorings.

The graphs that are colored in this section are neither of the input graphs –
which have long ago been encoded as strings anyways. The following notions are
meant to be used for abstract correspondences between the two input strings
that restrict the set of possible isomorphisms as outlined in section 2.3.

######  Definition 10 (Relational structure, partition structure).

Let $\Gamma$ be a finite set, $k\geq 1$. A _$k$ -ary relational structure_ on
$\Gamma$ is a tuple
$\mathfrak{X}=\left(\Gamma,(R_{i})_{i\in\mathscr{C}}\right)$ where
$R_{i}\subseteq\Gamma^{k}$ for each $i\in\mathscr{C}$. We call the $R_{i}$
_relations_ on $\Gamma$. The _rank_ of $\mathfrak{X}$ is $\abs{\mathscr{C}}$.
If furthermore all $R_{i}$ are non-empty and partition $\Gamma^{k}$, we call
$\mathfrak{X}$ a _$k$ -ary partition structure_. In this case, we describe
$\mathfrak{X}$ by a function $c:\Gamma^{k}\to\mathscr{C},x\mapsto i$ such that
$x\in R_{i}$ and write $\mathfrak{X}=(\Gamma,c)$. $c(x)$ is said to be the
_color_ of $x\in\Gamma^{k}$.

For two $k$-ary relational structures
$\mathfrak{X}=\left(\Gamma,(R_{i})_{i\in\mathscr{C}}\right)$ and
$\mathfrak{X}^{\prime}=\left(\Gamma^{\prime},(R^{\prime}_{i})_{i\in\mathscr{C}}\right)$
a bijection $f:\Gamma\to\Gamma^{\prime}$ is said to be an _isomorphism_
between $\mathfrak{X}$ and $\mathfrak{X}^{\prime}$ if for all
$i\in\mathscr{C}$ and $(x_{1},\dots,x_{k})\in\Gamma^{k}$,
$(x_{1},\dots,x_{k})\in R_{i}\iff(x_{1}^{f},\dots,x_{k}^{f})\in
R^{\prime}_{i}$. We write $\Iso(\mathfrak{X},\mathfrak{X}^{\prime})$ for the
set of isomorphisms and
$\Aut(\mathfrak{X})=\Iso(\mathfrak{X},\mathfrak{X})\leq\Sym(\Gamma)$ for the
set of automorphisms.

We will impose further regularity conditions on the structures. Note that
$\Sym_{k}$ acts naturally on $\Gamma^{k}$ by permuting the coordinates.

######  Definition 11 (Configuration).

A $k$-ary partition structure
$\mathfrak{X}=(\Gamma,c)=\left(\Gamma,(R_{i})_{i\in\mathscr{C}}\right)$ is
called _$k$ -ary configuration_ if the following conditions are satisfied:

  1. 1.

If $c(x_{1},\dots,x_{k})=c(x^{\prime}_{1},\dots,x^{\prime}_{k})$, then
$\left(x_{i}=x_{j}\iff x^{\prime}_{i}=x^{\prime}_{j}\right)$ for all $1\leq
i,j\leq k$.

  2. 2.

For all $\pi\in\Sym_{k}$ and all $i\in\mathscr{C}$ there exists
$j\in\mathscr{C}$ such that $R_{i}^{\pi}=R_{j}$.

The case $k=2$ offers some intuition for these conditions: We can think of a
$2$-ary (or binary) configuration structure as an edge-colored complete
digraph with vertices $\Gamma$. Item 1 implies that when two nodes $y\neq z$,
then $c(x,x)\neq c(y,z)$. Loops are colored differently than proper links.
Since $\Sym_{2}=\left\\{(1),(1\ 2)\right\\}$, item 2 simplifies: We have for
each color $i\in\mathscr{C}$ a color $j\in\mathscr{C}$ such that
$R_{i}=R_{j}^{-}\coloneqq\\{(y,x)\mid(x,y)\in R_{j}\\}$. This means that
$c(x,y)$ determines $c(y,x)$. If an out-edge is colored with the first color,
then the reverse in-edge is colored with the second. We call the digraph
$X_{i}=(\Gamma,R_{i})$ the _color- $i$ constituent graph_ for $\mathfrak{X}$.

######  Definition 12 (Coherent Configuration).

A $k$-ary configuration $\mathfrak{X}=(\Gamma,c)$ is called _$k$ -ary coherent
configuration_ if the following additional condition holds:

  1. 3.

There exists a function
$\gamma:\mathscr{C}^{k}\times\mathscr{C}\to\mathbb{Z}_{\geq 0}$ such that for
all $v\in\mathscr{C}^{k}$ and $j\in\mathscr{C}$ and for any $x\in\Gamma^{k}$
such that $c(x)=j$,

$\gamma(v,j)=\abs{\\{z\in\Gamma\mid c(x^{i}(z))=v_{i}\ \forall 1\leq i\leq
k\\}},$

where $x^{i}(z)=(x_{1},\dots,x_{i-1},z,x_{i+1},\dots,x_{k})$.

A coherent configuration is said to be _classical_ if $k=2$. If a classical
coherent configuration has only two colors, one for the _diagonal_
$\diag\Gamma=\\{(x,x)\mid x\in\Gamma\\}$ and one for its complement, then it
is said to be _trivial_ or a _clique_.

We will again look at the case $k=2$ in order to provide some intuition. See
fig. 2.1 for an example. The existence of $\gamma$ guarantees that for each
choice of three colors $i,j,l\in\mathscr{C}$ the number
$\abs{\\{z\in\Gamma\mid c(x,z)=j\land c(z,y)=l\\}}$ is independent of
$x,y\in\Gamma$ whenever $c(x,y)=i$. This means that for all pairs of nodes
that are linked with a red edge, say, there is the same number of $2$-paths
connecting them and containing first a blue and secondly a yellow edge. If
$k>2$, this generalizes to the number of colored walks following a given
sequence of colors.

An important example for classical coherent configurations occurs in the
context of group actions:

######  Lemma 2.5.1 (Orbital configuration).

Let $G\leq\Sym(\Gamma)$ for a finite set $\Gamma$. Let
$\\{R_{1},\dots,R_{n}\\}$ denote the set of orbits of the induced action on
$\Gamma\times\Gamma$, i.e. the _orbitals_. Then
$\mathfrak{X}=(\Gamma;R_{1},\dots,R_{n})$ defines a classical coherent
configuration, the _orbital configuration_.

######  Proof 2.5.2.

Clearly, $\mathfrak{X}$ is a 2-ary partition structure. For item 1 take an
arbitrary orbital $R$ and let
$(x_{1},x_{2}),(x^{\prime}_{1},x^{\prime}_{2})\in R$. Thus
$(x_{1},x_{2})^{g}=(x^{\prime}_{1},x^{\prime}_{2})$ for some $g\in G$.
Clearly, $x_{1}=x_{2}\iff x_{1}^{g}=x_{2}^{g}\iff
x^{\prime}_{1}=x^{\prime}_{2}$. For item 2 it is to show that
$R^{-}=\\{(y,x)\mid(x,y)\in R\\}$ is an orbital. We have that
$R=\\{(x_{0},y_{0})^{g}\mid g\in G\\}$ for some $(x_{0},y_{0})\in\Gamma^{2}$.
Trivially, $R^{-}$ is the orbital containing $(y_{0},x_{0})$. The function
$\gamma$ in item 3 must be independent of $x$. We therefore choose three
colors, here orbitals, $1\leq v_{1},v_{2},j\leq n$ and
$(x_{1},x_{2}),(y_{1},y_{2})\in R_{j}$ arbitrarily. Let $g\in G$ such that
$(x_{1},x_{2})=(y_{1},y_{2})^{g}$. Then,

$\displaystyle\abs{\left\\{z\in\Gamma\ \middle|\ (z,x_{2})\in
R_{v_{1}},(x_{1},z)\in R_{v_{2}}\right\\}}$
$\displaystyle=\abs{\left\\{z\in\Gamma\ \middle|\ (z,y_{2}^{g})\in
R_{v_{1}},(y_{1}^{g},z)\in R_{v_{2}}\right\\}}$
$\displaystyle=\abs{\left\\{z\in\Gamma\ \middle|\ (z,y_{2})\in
R_{v_{1}}^{g},(y_{1},z)\in R_{v_{2}}^{g}\right\\}}$
$\displaystyle=\abs{\left\\{z\in\Gamma\ \middle|\ (z,y_{2})\in
R_{v_{1}},(y_{1},z)\in R_{v_{2}}\right\\}}$

where we replaced $z$ by its image under the bijection $g^{-1}$ and used that
the $R_{v_{i}}$ are as orbitals $G$-invariant. Concluding that $\gamma$ in
item 3 is well-defined completes the proof.

######  Example 2.5.3.

We compute the orbital configuration for the dihedral group $D_{8}$, that is
the symmetry group of the square. We have $D_{8}=\generate{(1\ 2\ 3\ 4),(2\
4)}$. Clearly, the diagonal is one orbital. Applying the generators shows that
the orbital configuration for $D_{8}$ acting on the set of four elements is of
rank 3. We can think of the orbital configuration as a colored complete
digraph. For clarity, we draw the edges of the three colors in three separate
graphs, cf. fig. 2.1.

Reverting to item 3, we note that for example
$\gamma(\text{turquoise},\text{ultramarine},\text{violet})=0$ because there
are no turquoise-ultramarine paths from the source to the sink of a violet
edge. This number is independent of the chosen violet edge.

$1$$2$$3$$4$ (a) the turquoise diagonal orbital

$1$$2$$3$$4$ (b) the ultramarine orbital

$1$$2$$3$$4$ (c) the violet orbital

Figure 2.1: Orbital configuration of $D_{8}$

######  Definition 13.

A $k$-ary coherent configuration $\mathfrak{X}=(\Gamma,c)$ is said to be
_homogeneous_ if the $(x,\dots,x)\in\Gamma^{k}$ have the same color for all
$x\in\Gamma$. If $k=2$, $\mathfrak{X}$ is called _primitive_ if it is
homogeneous and all _constituent graphs_
$X_{i}=\left(\Gamma,\\{(x,y)\in\Gamma^{2}\mid c(x,y)=i\\}\right)$ except the
diagonal $X_{c(x,x)}$ are connected. It is said to be _uniprimitive_ if it is
primitive and non-trivial.

As an example, the orbital configuration of a transitive group is homogeneous.
Figure 2.1 shows a non-primitive coherent configuration. The violet
constituent graph is not connected. When working with local certificates, we
will need another elementary result. First we introduce some elementary graph
theoretic notions. The concerning digraph $X=(V,E)$ induces a binary partition
structure $\mathfrak{X}=(V;E,V\times V\setminus E)$. We can thus regard the
automorphism group of $X$ as the automophism group of $\mathfrak{X}$.

######  Definition 14.

Let $X=(V,E)$ be a digraph. Then $X$ is said to be _trivial_ if
$\Aut(X)=\Sym(V)$. That is the case if and only if $E\in\\{\emptyset,V\times
V,\diag V,V\times V\setminus\diag V\\}$ where $\diag V=\\{(v,v)\mid v\in
V\\}$, the _diagonal_. $X$ is said to be _irreflexive_ if $E\cap\diag
V=\emptyset$. It is _biregular_ if there exists $d\in\mathbb{N}$ such that
$d=\deg^{+}(v)=\deg^{-}(v)$ for all $v\in V$ where $\deg^{+}(v)$ and
$\deg^{-}(v)$ denote the in- and out-degree of the vertex $v$ respectively.

######  Lemma 2.5.4 (Degree awareness, [Bab15, Observation 2.5.3]).

Let $\mathfrak{X}=(\Gamma,c)$ be a classical coherent homogeneous
configuration. Then every constituent graph $X=(\Gamma,R)$ is biregular.

######  Proof 2.5.5.

Let $v\in\Gamma$. Let amber be the color of the edges in $X$. Let, by item 2,
burgundy be the color of the reverse edges. Since $\mathfrak{X}$ is
homogeneous all loops have the same color. Call this color carmine. Then, by
item 3,

$\displaystyle\deg^{+}(v)$ $\displaystyle=\abs{\\{z\in\Gamma\mid(v,z)\in
R\\}}=\abs{\\{z\in\Gamma\mid c(v,z)=\text{amber},c(z,v)=\text{burgundy}\\}}$
$\displaystyle=\gamma(\text{amber},\text{burgundy},\text{carmine}).$

Thus $\deg^{+}(v)$ is in fact independent of $v$. The out-degree and
analogously the in-degree of all vertices must be the same. From elementary
graph theory we know that $\abs
R=\sum_{v\in\Gamma}\deg^{+}(v)=\sum_{v\in\Gamma}\deg^{-}(v)$. Consequently,
there exists $d\in\mathbb{N}$, such that $d=\deg^{+}(v)=\deg^{-}(v)$ for all
$v\in\Gamma$. Hence, $X$ is biregular.

In order to be able to state the Design Lemma, we introduce two more classes
of coherent configurations following [Bab15, §2.5.5]. They are clearly
homogeneous.

######  Definition 15.

Let $\mathfrak{X}=(\Gamma,c)$ be a classical coherent configuration. Then
$\mathfrak{X}$ is said to be an _association scheme_ if $c(x,y)=c(y,x)$ for
every $x,y\in\Gamma$.

######  Definition 16.

Let $t\geq 2$ and $k\geq 2t+1$. Let $\Omega$ be a set with $k$ elements and
let $\Gamma=\binom{\Omega}{t}$. The _Johnson scheme_
$\mathfrak{J}(k,t)=(\Gamma;R_{0},\dots,R_{t})$ is an association scheme with
the relations $(T_{1},T_{2})\in R_{i}\iff\abs{T_{1}\setminus T_{2}}=i$ for
$0\leq i\leq t$.

The following result will be useful when we want to determine automorphisms
which respect to Johnson schemes:

######  Lemma 2.5.6 (Automorphisms of Johnson schemes, [Bab15, Proposition
2.5.23]).

If $t\geq 2$ and $k\geq 2t+1$, then
$\Aut(\mathfrak{J}(k,t))=\Sym^{(t)}(\Omega)$ where $\Omega$ is the set of $k$
elements in the preceding definition.

###  2.6 Twins and Symmetry Defects

For combinatorial arguments we need more notions to describe correspondences
and symmetries. A recurring theme are twins.

######  Definition 17.

Let $G\leq\Sym(\Omega)$. Two elements $x,y\in\Omega$ are called _twins_
111Babai distinguishes strong und weak twins. These technical details shall
not bother us. What we call _twins_ are _strong twins_ in Babai’s
nomenclature. with respect to $G$ if $x=y$ or the transposition $(x\ y)$ is
contained in $G$. The notion of being a twin induces an equivalence relation
on $\Omega$. The partitions inferred from this relation are said to be the
_twin classes_ of $\Omega$.

Clearly, the relation is symmetric and reflexive. Transitivity is implied by
the fact that $(y\ z)(x\ y)(y\ z)=(x\ z)$.

######  Definition 18.

Let $G\leq\Sym(\Omega)$. Let $T\subseteq\Omega$ be a smallest subset of
$\Omega$ such that $\Omega\setminus T$ is symmetrical, i.e. all distinct pairs
drawn from $\Omega\setminus T$ are twins with respect to $G$. We call $\abs T$
the _symmetry defect_ and $\abs T/\abs\Omega$ the _relative symmetry defect_
of $G$.

In other words, $\Omega\setminus T$ is the biggest twin class in $\Omega$ by
cardinality. For example, if we take

$G\coloneqq\Sym(\\{1,\dots,4\\})\times\Sym(\\{5,\dots,12\\})\leq\Sym(\\{1,\dots,12\\}),$

then $T=\\{1,\dots,4\\}$ and the relative symmetry defect is $1/3$. The
preceding definitions for general groups naturally extend to relational
structures.

######  Definition 19.

Let $\mathfrak{X}$ be a relational structure on $\Gamma$. Two elements
$x,y\in\Gamma$ are called _twins_ with respect to $\mathfrak{X}$ if they are
twins with respect to $\Aut(\mathfrak{X})$. Analogously, the _(relative)
symmetry defect_ of $\mathfrak{X}$ is the (relative) symmetry defect of
$\Aut(\mathfrak{X})$.

As an example, we state one of Babai’s corollaries which will be relevant in
section 5.3. Such results will allow us to perform efficient reduction.
Remember that we have identified digraphs and binary partition structures in
section 2.5.

######  Lemma 2.6.1 (Symmetry defect of digraphs, [Bab15, Corollary 2.4.13]).

Let $X=(V,E)$ be a non-trivial irreflexive biregular digraph. Suppose $\abs
V\geq 4$. Then the relative symmetry defect of $X$ is $\geq 1/2$.

###  2.7 Colored partitions

We summarize some definitions from [Bab15, §5] which will be necessary to
formulate the Design Lemma.

######  Definition 20.

A _colored partition_ $\Pi$ of a set $\Omega$ is a coloring of the elements of
$\Omega$ along with a partition of each color class, i.e. each set of elements
of a given color. Let $C_{1},\dots,C_{r}$ denote the color classes and
$\\{B_{ij}\mid 1\leq j\leq k_{i}\\}$ the blocks of $C_{i}$ where $k_{i}$
denotes the number of blocks in $C_{i}$. Let $0<\alpha\leq 1$. Then $\Pi$ is
said to be a _colored $\alpha$-partition_ if it satisfies the following
conditions:

  1. 1.

For each color class $C_{i}$ such that $\abs{C_{i}}\geq 2$ all blocks have
size $\abs{B_{ij}}\geq 2$.

  2. 2.

All blocks $B_{ij}$ satisfy $\abs{B_{ij}}\leq\alpha\abs{\Omega}$.

  3. 3.

All blocks within the same color class are of same size.

The original definition does not contain item 3. However, we can canonically
refine any structure which satisfies only the other two conditions such that
it satisfies the last. We encode the size of the block in the color.
Automorphism and isomorphisms of colored partitions must preserve the color
classes but can permute the blocks within them. Of course, also the elements
within a block can be permuted.

##  Chapter 3 Algorithmic Building Blocks

In this chapter we will present basal algorithmic strategies which will be
used throughout the entirety of this thesis. First, we will explain how to
determine orbits and blocks of group actions. Schreier-Sims’ method for
computing fundamental group theoretic objects such as generators, subgroups,
kernels and cosets etc. will be the subject of the second section. Thirdly, a
brief introduction to Luks’ techniques for reduction and recurrence will be
provided. At the end of the chapter we will discuss other parts of Babai’s
algorithm such as the Extended Design Lemma which will only appear as a black
box.

###  3.1 Orbits and Blocks

Orbits and blocks are fundamental objects for describing group actions, cf. 5.
At numerous points, we will need to map out the orbit structure or require
systems of blocks. From a computational perspective, group actions are
described by the images of the points in the domain under the action of the
generators. See [Hol05, §§4.1, 4.3] for background information and more
efficient algorithms.

We can determine the orbits of $G\leq\Sym(\Omega)$ given by a set of
generators $A$ by computing the connected components of the graph with
vertices $\Omega$ that contains an edge linking
$\omega_{1},\omega_{2}\in\Omega$ whenever there exists an $a\in A$ sending
$\omega_{1}$ to $\omega_{2}$. Constructing the graph takes $O(\abs
A\abs\Omega)$. For every vertex we apply a breadth-first or depth-first search
in $O\left(\abs\Omega^{2}\right)$ obtaining the connected components which are
precisely the orbits of the action. This takes in total $O\left(\abs
A\abs\Omega+\abs\Omega^{3}\right)$. By a remark in section 2.1, $\abs A$ can
be assumed to be polynomially bounded in $\abs\Omega$. Hence, computing orbits
takes polynomial time.

The orbit of a single element can be rapidly extracted from this result.
Moreover, we can determine in polynomial time whether an action is transitive.

Suppose now that $G$ is transitive. We want to determine whether its action is
furthermore primitive. Following [Sim67, Proposition 4.4], we analyze for
given distinct $a,b\in\Omega$ the graph
$\mathscr{G}_{a,b}\coloneqq\left(\Omega,\left\\{\\{a,b\\}^{g}\ \middle|\ g\in
G\right\\}\right)$ with vertices $\Omega$ and edges taken from the orbit of
$\\{a,b\\}$ under the induced action of $G$ on $\binom{\Omega}{2}$. Again
using breadth- or depth-first search we can determine the connected components
of $\mathscr{G}_{a,b}$ in polynomial time. The connected components cannot be
singletons since by transitivity every $\Omega\ni c=a^{g}$ is adjacent to
$b^{g}$ for a suitable $g\in G$.

Each connected component $C$ forms a block: Let $g\in G$ be fixed. Suppose
that $C^{g}\cap C\neq\emptyset$. Then there exist $c,d\in C$ such that
$c=d^{g}$. Thus, in $C$ we have a path $d=a^{h_{1}}\rightarrow
b^{h_{1}}\rightarrow\dots\rightarrow a^{h_{k}}\rightarrow b^{h_{k}}=c=d^{g}$
for certain $h_{i}\in G$. Let $e\in C$ be arbitrary. This means that there
exist $h^{\prime}_{i}\in G$ such that,

$e=a^{h^{\prime}_{1}}\rightarrow\dots\rightarrow
b^{h^{\prime}_{k^{\prime}}}=d=a^{h_{1}}\rightarrow\dots\rightarrow
b^{h_{k}}=d^{g}=b^{h^{\prime}_{k^{\prime}}g}\rightarrow\dots\rightarrow
a^{h^{\prime}_{1}g}=e^{g}.$

Hence, $e^{g}\in C$ and $C^{g}\subseteq C$. Moreover, if $a,b\in C$, then $C$
is the smallest block containing $a$ and $b$. Suppose that there exists a
smaller block $C^{\prime}$ containing $a$ and $b$, i.e.
$\abs{C^{\prime}}<\abs{C}$. Then by lemma 2.1.3, $C^{\prime}\cap C\subsetneq
C$ is as well a block. Since $C$ is connected there exists an edge
$\\{c,c^{\prime}\\}$ in $C$ connecting $C^{\prime}\cap C$ with its complement,
i.e. $c\in C\setminus(C^{\prime}\cap C)$ and $c^{\prime}\in C^{\prime}\cap C$.
By construction, there exists $g\in G$ such that
$\\{a,b\\}^{g}=\\{c,c^{\prime}\\}$. But $C^{\prime}\cap C$ is supposed to be a
block implying that $c\in C^{\prime}\cap C$, a contradiction.

We observe that $G$ is primitive if and only if there exists $a\in\Omega$ such
that $\mathscr{G}_{a,b}$ is connected for all $b\in\Omega$: Let $a,b\in\Omega$
such that $\mathscr{G}_{a,b}$ is disconnected. Then the connected components
of this graph form non-trivial blocks. Thus, $G$ is not primitive. Conversely,
assume that $\Gamma$ is a non-trivial block of $G$. Choose $a\in\Omega$ with
the property stated in the claim. Then $\mathscr{G}_{a,b}$ is connected for
arbitrary $b\in\Gamma$. Choose $c\in\Gamma\setminus\\{b\\}$. $\Gamma$ is a
block containing $c$ and $b$. But since $\mathscr{G}_{a,b}$ is connected, its
only connected component $\Omega$ is the smallest block containing $c$ and
$b$. $\Gamma$ must equal $\Omega$, again a contradiction.

We have justified a method for testing primitivity in polynomial time. We pick
an arbitrary $a\in\Omega$ and scan through all $b\in\Omega$ checking whether
$\mathscr{G}_{a,b}$ is disconnected. If one of the graphs is disconnected, we
know that $G$ is imprimitive, otherwise $G$ is primitive. This idea for
verifying primitivity was efficiently implemented by Atkinson, cf. [Hol05,
§4.3]. However, any polynomial algorithm suffices, as always, for our needs.
Figure 2.1 shows an example for the correspondence of connected components and
blocks.

Moreover, we can compute a minimal system of blocks in polynomial time
supposing that $G$ is imprimitive. For suitable $a,b\in\Omega$ we compute the
smallest block $B$ containing both elements as described above. We then
analyze the action of $G$ on the systems of blocks given by $\\{B^{g}\mid g\in
G\\}$. If it is primitive, we have found the desired minimal system. In the
contrarian case, we compute a new system of blocks for this action. The new
blocks are courser than their predecessors guaranteeing that this process
terminates after $\leq\abs\Omega$ iterations.

It remains to be seen how to compute the stabilizer of a system of blocks
$\mathscr{B}$ in polynomial time. Reverting to 5 and anticipating section 3.2,
this is simple. We consider the homomorphism $G\to\Sym(\mathscr{B})$ induced
by the action on the blocks. Using Schreier-Sims we can compute its kernel
which is precisely the desired stabilizer.

###  3.2 Schreier-Sims and derived algorithms

At many points throughout the algorithm we have to compute group theoretic
objects such as stabilizers, kernels and preimages. Schreier-Sims is the
fundamental toolkit that allows us to complete these tasks in polynomial time.
Note that there exist many faster and more sophisticated strategies for
solving these problems deterministically or employing randomization, cf.
[Ser03]. Since we are interested in an overall quasi-polynomial bound, we can
afford applying subprocedures with any polynomial complexity. Following
[Luk82, §1.2], we state a basic version of Schreier-Sims which is definitely
rapid enough for our needs.

[Schreier-Sims, [HBD17, §2.1.1], [Luk82, §1.2]] a set
$\Omega=\\{x_{1},\dots,x_{n}\\}$, a set $A$, such that $A$ generates
$G\leq\Sym(\Omega)$.
sets $C_{i}$ of representatives of $G_{i}/G_{i+1}$, such that $\bigcup_{i\leq
j<n-1}C_{j}$ generates the chain of pointwise stabilizer
$G_{i}=G_{(x_{1},\dots,x_{i})}$ for $0\leq i<n-1$, i.e.

$G=G_{0}\geq G_{1}\geq\dots\geq G_{n-1}=\\{1\\}.$

$O(n^{5}+n\abs{A})$ or $O(n^{5})$ by the following remark

We will roughly present the algorithm in order to justify the claim on the
complexity and the derived procedures stated below. Central to the procedure
is the function _filter_ which determines the generating set $C_{i}$ that a
group element belongs to.

Filter a group element $g\in G$, current $(C_{i})$ modified $(C_{i})$ filter

for $i=0,\dots,n-2$:

if $\gamma^{-1}\alpha\in G_{i+1}$ for some $\gamma\in C_{i}$:

$\alpha\leftarrow\gamma^{-1}\alpha$

add $\alpha$ to $C_{i}$, remember $x_{i+1}^{\alpha}$

return $(C_{i})$, enlarged set of representatives

end

end

return $(C_{i})$, nothing changed

The condition in line 3.2 is equivalent to
$x_{i+1}^{\alpha}=x_{i+1}^{\gamma}$. This can be surely tested in constant
time. We store the elements of $C_{i}$ in a dictionary indexed by
$x_{i+1}^{\alpha}$. This allows us to find a $\gamma\in C_{i}$ which satisfies
the condition in $O(1)$. In this way, line 3.2 contains just a dictionary
look-up and the entire procedure runs in $O(n)$. We can now state the
instructions for section 3.2:

initialize $C_{i}\leftarrow\\{1\\}$ for all $i=0,\dots,n-1$

filter $A$, the set of generators for $G$

filter $C_{i}C_{j}$ for $i\geq j$

return $(C_{i})$

For all $0\leq i<n-1$, it holds that $\abs{C_{i}}=\gindex{G_{i}}{G_{i+1}}\leq
n-i\leq n$, as the coset representatives of $G_{i+1}$ in $G_{i}$ are limited
by the possible (non-stabilized) images of $x_{i+1}$. Therefore, we obtain the
desired result in $O(n^{5}+n\abs A)$.

Schreier-Sims allows us to refine the set of generators $A$. As $G_{0}=G$ is
generated by $C=\bigcup_{j<n-1}C_{j}$, we have
$\abs{C}\leq\sum_{i=0}^{n-2}(n-i)$. Thus, we can find a set of generators for
$G$ of size $O(n^{2})$ ensuring that the new generators are products of the
former generators. Therefore, we may assume from now on that all groups acting
on sets of size $n$ are generated by $O(n^{2})$ elements.

Several basal tasks can be fulfilled in polynomial time using Schreier-Sims.
Let $G\leq\Sym(\Omega)$ and $\abs\Omega=n$.

First of all, we can compute $\abs{G}$ and verify whether $g\in\Sym(\Omega)$
satisfies $g\in G$. We have that $\abs G=\prod_{i=0}^{n-2}\abs{C_{i}}$ and
$g\in G$ if and only if $\abs{\generate{G,g}}=\abs G$. Secondly, we can
describe the pointwise stabilizer $G_{(\Delta)}$ of a set
$\Delta\subseteq\Omega$ by ordering $\Omega$ such that the elements of
$\Delta$ come first, calling Schreier-Sims and returning
$\bigcup_{\abs{\Delta}\leq j<\abs{\Omega}-1}C_{j}$. This is further explained
in [Luk82, §1.2] and [Ser03, §5.1.1].

Of interest will also be whether the group $G$ contains $\Alt(\Omega)$, or
even $\Sym(\Omega)$. Let without loss of generality $\Omega=\\{1,\dots,n\\}$.
For this, [Ser03, §10.2] does not only describe excelling algorithms but also
presents useful generators of $\Sym_{n}$ and $\Alt_{n}$, $n\geq 2$, which
together with the preceding membership test suffice to verify $\Alt_{n}\leq G$
polynomially:

$\displaystyle\Sym_{n}$ $\displaystyle=\generate{(1\ 2\ \cdots\ n),(1\ 2)}$
(3.1) $\displaystyle\Alt_{n}$ $\displaystyle=\begin{cases}\generate{(3\ 4\
\cdots\ n),(1\ 2\ 3)},&n\text{ odd}\\\ \generate{(1\ 2)(3\ 4\ \cdots\ n),(1\
2\ 3)},&n\text{ even}\\\ \end{cases}$ (3.2)

Following [HBD17, Exercise 2.1c], we are furthermore able to describe the
preimage $\varphi^{-1}(H)$ of a subgroup $H\leq\Sym(\Omega^{\prime})$ under a
given homomorphism $\varphi:G\to\Sym(\Omega^{\prime})$ if we assume that
$\abs{\Omega^{\prime}}\ll\abs{\Omega}^{O(1)}$. Similarly, we can compute the
preimage of a single element $\sigma\in\Sym(\Omega^{\prime})$ which is either
empty or a coset of $\ker\varphi$, cf. [Ser03, §5.1.2]. Homorphisms are given
to us, in general, as a set of tuples $\left(g,g^{\varphi}\right)$ where $g$
runs through a set of generators of the domain group.

When looking at a subgroup $H\leq G$ which has bounded index
$\gindex{G}{H}\ll\abs{\Omega}^{O(1)}$ and admits polynomial time membership
testing, we are able to describe $H$ in terms of generators of $G$.
Furthermore we can compute coset representatives for $H$ in $G$. We do so by
using the alternative chain of stabilizers

$G\geq H=H_{0}\geq H_{1}\geq\dots\geq H_{n-1}=\\{1\\}.$

LABEL:proc:filter needs to be modified for being able to return a set of
representatives $C_{-1}$ for $G/H$. For $i=-1$, line 3.2 changes to
$\gamma^{-1}\alpha\in H$ which can be verified in polynomial time by
assumption. Here we find a suitable $\gamma\in C_{-1}$ by iteratively checking
$\abs{C_{i-1}}\leq\gindex{G}{H}$ elements. The group $H$ is then described by
$\bigcup_{0\leq i<n-1}C_{i}$ and $C_{-1}$ is a set of coset representatives
for $H$ in $G$. Let $\mu(n)\ll n^{O(1)}$ denote the complexity of the
membership test. Then the complexity of this modified version of section 3.2
is $O\left(\left(\abs
A+n^{4}+\gindex{G}{H}n^{2}\right)\left(\mu(n)\gindex{G}{H}+n\right)\right)$
which is by assumption polynomial.

In some situations we cannot demand that $\gindex{G}{H}$ is polynomially
bounded. For example, it may be the case that $\gindex{G}{H}$ grows quasi-
polynomially in $n$, e.g. $\gindex{G}{H}\ll n^{O(\log n)}$. By the complexity
estimate from above, a call to Schreier-Sims costs then $n^{O(\log n)}$
assuming that $\abs A$ is not too large. This will be affordable.

###  3.3 Luks’ method

The following strategies are based on [Luk82] who proved that the Graph
Isomorphism Problem for graphs with bounded degree can be decided in
polynomial time. The algorithm that he proposed includes two kinds of
reductions which are used many times throughout Babai’s algorithm. See [HBD17,
§2.2] and [Bab15, §3.1] for more details.

The rather simple strategy is called _weak Luks reduction_ and is used
whenever we want to pass to a subgroup. The subgroup’s index determines the
number of subproblems that we have to deal with after the reduction. Clearly,
we will require some bounds on that index to ensure efficiency. _Strong Luks
reduction_ is the more sophisticated method. It can be used to recur on a
partition which is invariant under the group’s action. The most basal example
is the recurrence on orbits. For both strategies we require the notion of
partial isomorphisms which formalizes the idea of considering parts of the
input only.

######  Definition 21 (Partial isomorphisms).

Let $\str x,\str y:\Omega\to\Sigma$ be two strings, $G\leq\Sym(\Omega)$ and
$\Delta\subseteq\Omega$ a subset called the _window_ , then

$\Iso_{G}^{\Delta}(\str x,\str y)=\left\\{\sigma\in G\ \middle|\ \str
x(x)=\str y(x^{\sigma})\ \forall x\in\Delta\right\\}$

denotes the set of _partial isomorphisms_ with respect to $\Delta$.
Correspondingly, $\Aut_{G}^{\Delta}(\str x)=\Iso_{G}^{\Delta}(\str x,\str x)$
denotes the set of _partial automorphisms_.

Clearly, $\Iso_{G}^{\Omega}(\str x,\str y)=\Iso_{G}(\str x,\str y)$, cf. 8.
The following lemma is crucial in both situations.

######  Lemma 3.3.1.

Let $\str x,\str y:\Omega\to\Sigma$ be two strings,
$K,K_{1},K_{2}\subseteq\Sym(\Omega),\sigma\in\Sym(\Omega)$ and
$\Delta\subseteq\Omega$ the window. Then the following holds:

  1. 1.

_(Shift identity)_ $\Iso^{\Delta}_{K\sigma}(\str x,\str
y)=\Iso^{\Delta}_{K}\left(\str x,\str{y}^{\sigma^{-1}}\right)\sigma$,

  2. 2.

$\Iso^{\Delta}_{K_{1}\cup K_{2}}(\str x,\str y)=\Iso_{K_{1}}^{\Delta}(\str
x,\str y)\cup\Iso_{K_{2}}^{\Delta}(\str x,\str y)$,

  3. 3.

If furthermore $G\leq\Sym(\Omega)$ is a subgroup which leaves $\Delta$
invariant, then $\Aut^{\Delta}_{G}(\str x)\leq G$. For all
$\sigma\in\Sym(\Omega)$, $\Iso_{G\sigma}^{\Delta}(\str x,\str y)$ is either
empty or of the form $\Aut_{G}^{\Delta}(\str x)\tau$ for any
$\tau\in\Iso_{G\sigma}^{\Delta}(\str x,\str y)$.

  4. 4.

_(Chain rule,[Bab15, Proposition 3.1.7])_ Let
$\Delta_{1},\Delta_{2}\subseteq\Omega$ invariant as sets under
$G\leq\Sym(\Omega)$. Then for a subgroup $G_{1}\leq G$ and $\tau\in G$ such
that $\Iso^{\Delta_{1}}_{G}(\str x,\str y)=G_{1}\tau$, it holds that

$\Iso^{\Delta_{1}\cup\Delta_{2}}_{G}(\str x,\str
y)=\Iso^{\Delta_{2}}_{G_{1}\tau}(\str x,\str
y)=\Iso^{\Delta_{2}}_{G_{1}}\left(\str x,\str{y}^{\tau^{-1}}\right)\tau.$

######  Proof 3.3.2.

Clearly, items 2 and 3 hold. It is worth looking at the proofs of the other
claims in order to internalize the implications of eq. 2.1. The shift identity
follows basically from the definition:

$\Iso^{\Delta}_{K\sigma}(\str x,\str y)=\left\\{\tau\in K\ \middle|\ \str
x(x)=\str y(x^{\tau\sigma})\ \forall x\in\Delta\right\\}\sigma=\left\\{\tau\in
K\ \middle|\ \str x(x)=\str y^{\sigma^{-1}}(x^{\tau})\ \forall
x\in\Delta\right\\}\sigma=\Iso^{\Delta}_{K}\left(\str
x,\str{y}^{\sigma^{-1}}\right)\sigma.$

For the chain rule note that $\Iso^{\Delta_{1}\cup\Delta_{2}}_{G}(\str x,\str
y)=\Iso^{\Delta_{1}}_{G}(\str x,\str y)\cap\Iso^{\Delta_{2}}_{G}(\str x,\str
y)$ which implies the first equation. The second is an application of the
shift identity.

Now we are ready to state the two types of Luks reductions.

Weak Luks Reduction Descriptions of groups $H\leq G\leq\Sym(\Omega)$, two
strings $\str x,\str y:\Omega\to\Sigma$, a window $\Delta\subseteq\Omega$
$\Iso_{G}^{\Delta}(\str x,\str y)$ by reduction to $\gindex{G}{H}$ instances
of $\Iso_{H}^{\Delta}\left(\str x,\str y^{\sigma}\right)$ for certain
$\sigma\in G$ weak-luks

compute a set $S$ right coset representatives of $H$ in $G$ calling section
3.2

for $\sigma_{i}\in S$:

collect the $\Iso_{H}^{\Delta}\left(\str x,\str
y^{\sigma_{i}^{-1}}\right)\sigma_{i}$ which are of the form $F\tau_{i}$ for
$F=\Aut_{H}^{\Delta}(\str x)$ or empty; if so, set $\tau_{i}\leftarrow 1$

end

return the combined coset $\generate{F\cup\left\\{\tau_{i}\tau_{1}^{-1}\
\middle|\ 1<i\leq\abs S\right\\}}\tau_{1}$ That the procedure works correctly
follows directly from item 2 of lemma 3.3.1 given the coset decomposition
$G=\bigcup_{i}H\sigma_{i}$. Line 3.3.2 is justified by the fact that

$\bigcup_{1\leq i\leq\abs
S}F\tau_{i}=\generate{F\cup\left\\{\tau_{i}\tau_{1}^{-1}\ \middle|\
1<i\leq\abs S\right\\}}\tau_{1}.$ (3.3)

The left-hand side is contained in the right-hand side since
$F\tau_{i}=F\tau_{i}\tau_{1}^{-1}\tau_{1}$. Conversely, the generators on the
right are contained in the left-hand side when multiplied with $\tau_{1}$.

The time complexity crucially depends on $\gindex{G}{H}$. Reverting to section
3.2, the computation of the coset representatives takes polynomial time
whenever $H$ admits polynomial membership testing and additionally
$\gindex{G}{H}\ll\abs{\Omega}^{O(1)}$. If such a bound is exceeded and
$\gindex{G}{H}$ grows quasi-polynomially in $\abs\Omega$, then the execution
time grows quasi-polynomially as well. Since we recur to $\gindex{G}{H}$
subproblems, the additive costs do not outweigh the multiplicative costs.

The situation in which we apply strong Luks reduction is slightly more subtle.
The action of the group $G$ on $\Omega$ admits an invariant subset $\Delta$
which is partitioned into blocks $\\{B_{1},\dots,B_{m}\\}$ themselves
invariant under $G$. Formally, for all $g\in G$ and $1\leq i\leq m$ there is
$1\leq j\leq m$ such that $B_{i}^{g}=B_{j}$. Thus, the action of $G$ induces
an action on the blocks. We therefore have a homomorphism $\psi:G\to\Sym_{m}$
where the image acts on the blocks. The kernel of this map is precisely the
stabilizer of the blocks, i.e. $\sigma\in\ker\psi$ iff $B_{i}^{\sigma}=B_{i}$
for all $i=1,\dots,m$, cf. 5.

[Strong Luks Reduction] a group $G\leq\Sym(\Omega)$, a $G$-invariant subset
$\Delta\subseteq\Omega$, a $G$-invariant partition $\\{B_{1},\dots,B_{m}\\}$
of $\Delta$, two strings $\str x,\str y:\Omega\to\Sigma$
$\Iso_{G}^{\Delta}(\str x,\str y)$ by reduction to $m\gindex{G}{\ker\psi}$
instances of $\Iso_{M_{i}}^{B_{i}}\left(\str x,\str y^{\sigma_{i}}\right)$ for
certain $\psi:G\to\Sym_{m}$ as described above, $M_{i}\leq\ker\psi$,
$\sigma_{i}\in G$

We present the steps of the procedure in full prose: First we compute the
kernel of $\psi$ and call it $H$. This can be done by using Schreier-Sims in
polynomial time, cf. section 3.2, since $m\leq\abs\Omega$. Using weak Luks
reduction with input groups $H\leq G$ we simplify the problem to
$\gindex{G}{\ker\psi}$ instances of subproblems of the form
$\Iso_{H}^{\Delta}(\str x,\str y^{\sigma_{j}})$. Every orbit of $H$ acting on
$\Delta$ is now contained in one of the blocks $B_{i}$. We can look for
partial isomorphism on each of the blocks separately. We iteratively let
$B\in\\{B_{1},\dots,B_{m}\\}$ and analyze the block following [Bab15,
Observation 3.1.10]:

That $\Iso_{\restrict{H}{B}}\left(\restrict{\str x}{B},\restrict{\str
y^{\sigma_{j}}}{B}\right)$ is empty if and only if $\Iso_{H}^{B}(\str x,\str
y^{\sigma_{j}})$ is empty, will allow us to pass to shorter strings. While
restricting $H$ to $\restrict{H}{B}$, we remember how the elements of $H$ act
on the rest of the domain. Maintaining this additional information does not
make the subsequent computations more complicated because we do not need to
remember the entire action of $H$. For every element of $\restrict{H}{B}$ we
just remember one possible extension to $H$ resulting in negligible additional
data.

In this fashion we compute the subproblem
$\Iso_{\restrict{H}{B}}\left(\restrict{\str x}{B},\restrict{\str
y^{\sigma_{j}}}{B}\right)$ and obtain either an empty result or a set of
generators $R\subseteq H$ and a $\tau\in H$, such that $R$ generates
$\Aut_{\restrict{H}{B}}(\str x)$ and
$\restrict{\tau}{B}\in\Iso_{\restrict{H}{B}}\left(\restrict{\str
x}{B},\restrict{\str y^{\sigma_{j}}}{B}\right)$. Schreier-Sims can then be
used to compute generators for $H_{(B)}$ which together with $R$ generate
$H^{\prime}=\Aut_{H}^{B}(\str x)$. Thus, $\Iso^{B}_{H}(\str x,\str
y^{\sigma_{j}})=\Aut_{H}^{B}(\str x)\tau$. By the chain rule, cf. lemma 3.3.1,
$\Iso^{\Delta}_{H}(\str x,\str y^{\sigma_{j}})=\Iso^{\Delta\setminus
B}_{H^{\prime}}\left(\str x,(\str y^{\sigma_{j}})^{\tau^{-1}}\right)\tau$. We
proceed with the next block until there are no more blocks left.

It can be readily verified that we have divided the problem into
$m\gindex{G}{\ker\psi}$ subproblems with strings of length
$\leq\max_{i}\abs{B_{i}}$. The additive costs are polynomial in $\abs\Omega$
when leaving the computation of coset representatives for $\ker\psi$ in $G$
apart. If $\gindex{G}{\ker\psi}$ is bounded polynomially in $\abs\Omega$, then
the entire reduction costs only a polynomial amount of time.

A straightforward application of strong Luks reduction is the recurrence on
orbits. Suppose that $G$ acts intransitively on $\Omega$. Then the orbits of
this action form a partition of $\Omega$ into blocks. The induced action on
the blocks is trivial as no permutation moves an element from one block to
another. Thus, $\ker\psi=G$. Strong Luks reduction yields as many subproblems
as $G$ has orbits on $\Omega$. The short strings are as long as the orbits and
in total as long as the original domain. Of course, this reduction was nothing
else than the application of the chain rule, cf. lemma 3.3.1, wrapped in a
fancy subprocedure. Importantly, we did not have to compute coset
representatives in this case. The costs of this reduction on orbits are
therefore negligible.

Most frequently, we will apply strong Luks reduction when $G$ acts
transitively but not primitively on $\Omega$. Then we can compute a minimal
system of blocks in polynomial time, cf. section 3.1. Suppose we have found
$m$ blocks. They equipartition $\Omega$. Consequently, we can reduce to
$m\gindex{G}{N}$ subproblems of length $\abs\Omega/m$ where $N$ denotes the
stabilizer of these blocks.

###  3.4 Identification of groups and schemes

In this section we want to map out isomorphisms between permutation groups
which are known to be abstractly permutation isomorphic, cf. 6. Let $\Omega$
be a set of size $n$ and let $m\in\mathbb{N}$ be an integer. We are given a
permutation group $G\leq\Sym(\Omega)$ satisfying $G\cong\Alt_{m}$. Two
permutation isomorphic groups must admit a bijection between their domains.
Thus, if $m>n$, $\Alt_{m}$ must act as $\Alt^{(k)}_{m}$ for a given $1<k\leq
m/2$ such that $n=\binom{m}{k}$.

We will impose an additional condition of the form $k^{2}\ll m$ in order to
simplify the procedure. However, this does not really come with a loss of
generality. If contrarily $m\ll k^{2}$, we have that,

$n^{\log
n}\gg\binom{m}{\floor{\sqrt{m}}}^{\log\binom{m}{\floor{\sqrt{m}}}}\gg\frac{m!}{\floor{\sqrt{m}}!(m-\floor{\sqrt{m}})!}\left(\frac{m}{\sqrt{m}}\right)^{\sqrt{m}(\sqrt{m}\log
m-1)}\geq m!\sqrt{m}^{m\log m-2\sqrt{m}-2m}\gg m!,$

because in general,
$\binom{\nu}{\kappa}\geq\left(\frac{\nu}{\kappa}\right)^{\kappa}$ and
$\log\binom{m}{\floor{\sqrt{m}}}\geq\floor{\sqrt{m}}\log\frac{m}{\floor{\sqrt{m}}}\asymp\sqrt{m}\log
m$ for arbitrary $\nu,\kappa,m\in\mathbb{N}$. Hence, in this case $\abs
G=m!/2\ll n^{\log n}$ and we can afford to brutally iterate through the entire
group and compute the desired information. If, for example, $G$ is a quotient
$H/N$ as in section 4.1, the bound $\gindex{H}{N}\ll n^{\log n}$ makes a weak
Luks reduction, cf. LABEL:proc:weak-luks, to the smaller group affordable. In
section 5.4 when we will need the procedure for identifying two Johnson
schemes, the bound allows us to freely scan through all possibilities.

set $\Omega$, $n=\abs\Omega$, integers $m\in\mathbb{N}$, $1\leq k\leq m/2$
such that $n=\binom{m}{k}$ and $m>k(k+1)+1$, a group $G\leq\Sym(\Omega)$
satisfying $G\cong\Alt_{m}$.
a set $\Gamma$ of size $m$, a bijection $\iota:\Omega\to\binom{\Gamma}{k}$ and
an isomorphism $\varphi:G\to\Alt(\Gamma)$ such that

$\iota\left(\omega^{g}\right)=\iota(\omega)^{\varphi(g)}\quad\forall\omega\in\Omega,\
g\in G.$ (3.4)

polynomial in $n$.

Providing an isomorphism means, as always, to give images of the generators of
the domain group, here $G$. The explanation follows [HBD17, §2.8] who quotes
[BLS87]. We will define $\iota$ and $\varphi$ at the very end of the
procedure. When referring to $\iota_{0}$ and $\varphi_{0}$ until then, we
think of general maps satisfying eq. 3.4. Similarly, $\Gamma_{0}$ remains an
abstract set of $m$ elements until we define $\Gamma$ at the end of the
procedure. We infer the correspondence between $G$ and $\Alt_{m}^{(k)}$ from
the orbital structures of the two group actions.

For two sets $S_{1},S_{2}\in\binom{\Gamma_{0}}{k}$ and arbitrary
$\sigma\in\Alt_{m}^{(k)}$, clearly $\abs{S_{1}\cap
S_{2}}=\abs{S_{1}^{\sigma}\cap S_{2}^{\sigma}}$. Therefore two pairs
$(S_{1},S_{2}),(T_{1},T_{2})\in\binom{\Gamma_{0}}{k}\times\binom{\Gamma_{0}}{k}$
can only be in the same orbital of $\Alt_{m}^{(k)}$ if $\abs{S_{1}\cap
S_{2}}=\abs{T_{1}\cap T_{2}}$. Conversely, $\Alt_{m}$ acts
$(m-2)$-transitively, cf. example 2.1.1. Hence, given two such pairs
satisfying $\abs{S_{1}\cup S_{2}}=\abs{T_{1}\cup T_{2}}\leq 2k$ we can find an
element in $\Alt_{m}^{(k)}$ mapping them onto each other whenever $2k\leq
m-2$. This is clearly the case under the assumption that $m>k(k+1)+1$.
Consequently, we have mapped out the orbital structure of $\Alt_{m}^{(k)}$:
The orbitals are $\\{R_{0},\dots,R_{k}\\}$ for
$R_{i}=\left\\{(S_{1},S_{2})\in\binom{\Gamma_{0}}{k}\times\binom{\Gamma_{0}}{k}\
\middle|\ \abs{S_{1}\cap S_{2}}=i\right\\}$. Ordering them by size allows us
to identify the corresponding $G$-orbitals.

We claim that $\abs{R_{i+1}}<\abs{R_{i}}$ for all $0\leq i<k$. Suppose that
$m>k(k+1)$. Let $0\leq i<k$ be arbitrary. Under these assumptions,
$(m-i)(i+1)\geq m-i>m-k>k(k+1)-k=k^{2}>(k-i)^{2}.$ We proceed with the main
estimation:

$\abs{R_{i}}=\binom{m}{i}\binom{m-i}{k-i}^{2}=\frac{m!(m-i)!}{i!(k-i)!^{2}(m-k)!^{2}}=\abs{R_{i+1}}\frac{(m-i)(i+1)}{(k-i)^{2}}>\abs{R_{i+1}}.$

Hence, the largest orbital is $R_{0}$, the smallest is $R_{k}$. We map out the
orbital structure of $G$ acting on $\Omega$ in polynomial time, cf. section
3.1. Let $\Xi\subseteq\Omega\times\Omega$ denote the smallest orbital of $G$
outside the diagonal $\diag\Omega$. Let $\Delta\subseteq\Omega\times\Omega$ be
the largest orbital. By the argument from above, $\iota_{0}(\Xi)=R_{k-1}$ and
$\iota_{0}(\Delta)=R_{0}$.

$\Gamma_{0}$$\iota_{0}(B(x,y))$$\iota_{0}(x)$$\iota_{0}(y)$ Figure 3.1:
Schematic example of the construction in section 3.4 with $k=4$. The distinct
element $\delta(x,y)$ of $\Gamma_{0}$ that is contained in $\iota_{0}(x)$ but
not in $\iota_{0}(y)$ is encircled. The dashed shapes represent some
$\iota_{0}(z)$ for $z\in B(x,y)$. They are disjoint to $\iota_{0}(y)$ while
having a non-empty intersection with $\iota_{0}(x)$.

For $(x,y)\in\Xi$ we compute the sets

$\displaystyle B(x,y)$
$\displaystyle=\\{z\in\Omega\mid(x,z)\not\in\Delta,(y,z)\in\Delta\\},$
$\displaystyle C(x,y)$ $\displaystyle=\Omega\setminus\bigcup_{z\in
B(x,y)}\\{r\in\Omega\mid(z,r)\in\Delta\\}.$

Note that the condition that defines $B(x,y)$ is equivalent to
$\iota_{0}(x)\cap\iota_{0}(z)\neq\emptyset$ and
$\iota_{0}(y)\cap\iota_{0}(z)=\emptyset$, since a pair is in $\Delta$ if and
only if its $\iota_{0}$-image is disjoint. Then, we apply the definition:

$\displaystyle\iota_{0}(C(x,y))$
$\displaystyle=\iota_{0}\left(\left\\{a\in\Omega\ \middle|\
(z,a)\not\in\Delta\quad\forall z\in\Omega\text{ such that
}(x,z)\not\in\Delta\text{ and }(y,z)\in\Delta\right\\}\right)$
$\displaystyle=\left\\{A\in\binom{\Gamma_{0}}{k}\ \middle|\ A\cap
Z\neq\emptyset\quad\forall Z\in\binom{\Gamma_{0}}{k}\text{ such that
}\iota_{0}(x)\cap Z\neq\emptyset\text{ and }\iota_{0}(y)\cap
Z=\emptyset\right\\}$ $\displaystyle=\left\\{A\in\binom{\Gamma_{0}}{k}\
\middle|\ \delta(x,y)\in A\right\\},$ (3.5)

where $\delta(x,y)$ is the element in the singleton
$\iota_{0}(x)\setminus\iota_{0}(y)$, that is the unique element in
$\iota_{0}(x)$ that is not simultaneously contained in $\iota_{0}(y)$.

Equation 3.5 only holds if $\binom{\Gamma_{0}}{k}$ is big enough. In
particular, it must not happen that a set with non-empty intersection with all
$\iota_{0}(z)$ for $z\in B(x,y)$ does not contain $\delta(x,y)$ but another
shared point, cf. fig. 3.1. However, under the assumption $m>k(k+1)$ we can
have $z_{1},\dots,z_{k}\in B(x,y)$ such that
$\iota_{0}(z_{i})\cap\iota_{0}(z_{j})=\\{\delta(x,y)\\}$ for all $i\neq j$.
They use up $k(k-1)+1$ elements. Since $\iota_{0}(y)$ must also exist
disjointly, we require $k(k-1)+1+k=k^{2}+1\leq k(k+1)<m$ elements in
$\Gamma_{0}$, in accordance with the assumption.

Set $\Gamma=\\{C(x,y)\mid(x,y)\in\Xi\\}$ without multiplicities. We will
immediately see that indeed $\abs\Gamma=m$. $B(x,y)$ and $C(x,y)$ can be
computed and compared in polynomial time. The action of $G$ on $\Xi$ induces a
group action on $\Gamma$. The corresponding isomorphism
$\varphi:G\to\Alt(\Gamma)$ is similarly computable in polynomial time. Thus,
by definition, $C(x,y)^{\varphi(g)}=C(x^{g},y^{g})$ for all $g\in G$.

It follows from eq. 3.5 by applying the bijection $\iota_{0}$ to the left-hand
side, that for all $\omega\in\Omega$ and $(x,y)\in\Xi$:

$\omega\in C(x,y)\iff\delta(x,y)\in\iota_{0}(\omega).$ (3.6)

We have a bijection $j:\Gamma\to\Gamma_{0},C(x,y)\mapsto\delta(x,y)$. Clearly,
$j$ is onto. Well-definedness and injectivity follow directly from eq. 3.6. We
finally obtain the bijection $\iota:\Omega\to\binom{\Gamma}{k}$,
$\omega\mapsto\\{C(x,y)\in\Gamma\mid\omega\in C(x,y)\\}$. Since $\varphi$
represents the naturally induced action of $G$ on $\Gamma$, eq. 3.4 is
satisfied. We have built a tangible set $\Gamma$ and maps $\iota$ and
$\varphi$ which have the desired properties.

###  3.5 Partition pullback

Throughout the algorithm we maintain an auxiliary set $\Gamma$ which is linked
to the permutation group of interests $G\leq\Sym(\Omega)$ and its permutation
domain $\Omega$ by an epimorphism $\varphi:G\to\Alt(\Gamma)$ and a surjection
$\iota:\Omega\to\binom{\Gamma}{k}$ for some $k\in\mathbb{N}$. $\iota$ has the
additional property that the preimage of each singleton in $\Gamma$ is of the
same size.

In this section, we study the case in which we are given a partition
$\Delta_{1},\dots,\Delta_{t}$ of $\Gamma$. We want to pullback this partition
to a partition of $\Omega$ in order to treat the individual subsets
separately. See [Bab15, §5.2] for background information.

[Partition pullback] a partition $\Delta_{1},\dots,\Delta_{t}$ of $\Gamma$, a
surjection $\iota:\Omega\to\binom{\Gamma}{k}$
a canonical partition in color classes $\Omega_{v}$ for
$v\in\mathscr{C}_{t}\coloneqq\left\\{v\in\\{0,\dots,k\\}^{t}\ \middle|\ \sum
v_{i}=k\right\\}$ of $\Omega$ such that the following conditions hold:

  1. 1.

The color of $\omega\in\Omega$ is the vector
$(\abs{\iota(\omega)\cap\Delta_{i}}\mid 1\leq i\leq t)$.

  2. 2.

For all color classes $\abs{\Omega_{v}}\leq(2/3)\abs\Omega$ except one with
$v=(0,\dots,0,k,0,\dots,0)$.

polynomial in $\abs\Omega$

In the case $t=2$, this simply means that we obtain a canonical partition
$\Omega_{0},\dots\Omega_{k}$ where $\omega\in\Omega_{j}$ if and only if
$\iota(\omega)$ contains $j$ elements of $\Delta_{1}$ and hence $k-j$ elements
of $\Delta_{2}$. For all $0\leq j\leq k$ with the possible exception of either
$j=0$ or $j=k$, the color classes satisfy
$\abs{\Omega_{j}}\leq(2/3)\abs\Omega$. The procedure depends on a binomial
inequality proven by Babai with elementary means, cf. [Bab15, Proposition
5.2.3].

######  Lemma 3.5.1.

Let $m_{1},m_{2},t_{1},t_{2}$ be integers. Let $m\coloneqq m_{1}+m_{2}$ and
$t\coloneqq t_{1}+t_{2}$. Suppose that $t\leq m/2$ and $t_{1},t_{2}\geq 1$.
Then

$\binom{m_{1}}{t_{1}}\binom{m_{2}}{t_{2}}\leq\frac{2}{3}\binom{m}{t}.$

Having this result at hand, we begin with the procedure: We first color the
elements of $\binom{\Gamma}{k}$. Let
$\Gamma_{v}\coloneqq\left\\{T\in\binom{\Gamma}{k}\ \middle|\
\abs{T\cap\Delta_{i}}=v_{i}\ \forall 1\leq i\leq t\right\\}$ for
$v\in\mathscr{C}_{t}$. In other words, we color the $k$-sized subsets of
$\Gamma$ according the number of elements they contain from each of the
$\Delta_{i}$. We verify inductively that indeed
$\abs{\Gamma_{v}}\leq(2/3)\abs{\Gamma}$ for each $v$ with one possible
exception. If $t=1$, there is only one such set and the condition is vacuous.
We will study the case $t=2$ at length since it appears in the application in
case 2a of section 5.3.

Here, the color classes of $\binom{\Gamma}{k}$ can be indexed more intuitively
as $\\{\Gamma_{0},\dots,\Gamma_{k}\\}$ where $\gamma\in\Gamma_{j}$ if and only
if $\gamma$ contains $k-j$ elements of $\Delta_{1}$ and thus $j$ elements of
$\Delta_{2}=\Gamma\setminus\Delta_{1}$. Without loss of generality, we can
assume that $k\leq\abs\Gamma/2$. Hence, by lemma 3.5.1, for $0<j<k$,

$\abs{\Gamma_{j}}=\abs{\left\\{\alpha\mathbin{\dot{\cup}}\beta\ \middle|\
\alpha\in\binom{\Delta_{1}}{k-j},\beta\in\binom{\Delta_{2}}{j}\right\\}}=\binom{\abs{\Delta_{1}}}{k-j}\binom{\abs{\Delta_{2}}}{j}\leq\frac{2}{3}\binom{\abs\Gamma}{k}.$

Suppose without loss of generality that $\abs{\Delta_{1}}\leq\abs\Gamma/2$.
Then
$\abs{\Gamma_{0}}=\binom{\abs{\Delta_{1}}}{k}\leq\binom{\abs\Gamma/2}{k}\leq\frac{1}{2}\binom{\abs\Gamma}{k}$.
The only possible exception to the bound is thus $\Gamma_{k}$ corresponding to
$v=(0,k)$.

We revert to the original notation and suppose that the claim holds for
$t-1\in\mathbb{N}$. We apply the hypothesis to the partition
$\Delta_{1},\dots,\Delta_{t-2},\Delta^{\prime}$ for
$\Delta^{\prime}\coloneqq\Delta_{t-1}\cup\Delta_{t}$ obtaining a partition
$\Gamma^{\prime}_{v}$ for $v\in\mathscr{C}_{t-1}$ satisfying the desired bound
with one possible exception. The colors are aware of the number of elements
from $\Gamma^{\prime}$ but cannot tell how many elements are from
$\Delta_{t-1}$ and $\Delta_{t}$. If the exception is not
$\Gamma^{\prime}_{(0,\dots,0,k)}=\binom{\Delta^{\prime}}{k}$, we can simply
encode the numbers $\abs{T\cap\Delta_{t-1}}$ and $\abs{T\cap\Delta_{t}}$ for
$T\in\binom{\Gamma}{k}$ in the colors of $\Gamma^{\prime}$ not enlarging the
color classes. Otherwise we apply the induction hypothesis to the partition
$\Delta_{t-1},\Delta$ obtaining a coloring $\Gamma^{\prime\prime}_{v}$ of
$\Delta^{\prime}$ for $v\in\mathscr{C}_{2}$. These color classes satisfy
$\abs{\Gamma^{\prime\prime}_{v}}\leq(2/3)\abs{\Delta^{\prime}}\leq(2/3)\abs\Gamma$
with one possible exception. We refine the coloring $\Gamma^{\prime}$ as above
using $\Gamma^{\prime\prime}$ for the sets from $\binom{\Delta^{\prime}}{k}$.
All color classes except one have admissible size and the only exception is
the class corresponding to either $\binom{\Delta_{t-1}}{k}$ or
$\binom{\Delta_{t}}{k}$. This finishes the induction.

It remains to infer the coloring of $\Gamma$. For $v\in\mathscr{C}_{t}$ we set
$\Omega_{v}=\iota^{-1}(\Gamma_{v})$. By the properties of $\iota$,
$\abs{\Omega_{v}}=\abs{\Omega}\binom{\abs\Gamma}{k}^{-1}\abs{\Gamma_{v}}\leq(2/3)\abs\Omega$
for all $v$ except one. For computing the color classes we need to evaluate
$\iota$ for each $\omega\in\Omega$ and compute the cardinalities of the
intersection with the $\Delta_{i}$. This takes polynomial time.

###  3.6 Design Lemma

The two main mostly combinatorial tools of Babai’s algorithm are the Design
Lemma [Bab15, §6] and the Split-or-Johnson routine [Bab15, §7]. Their powers
are combined in the following Extended Design Lemma. It is used to descend
from a $k$-ary relational structure with large symmetry defect either to a
canonical $\alpha$-partition or to a canonically embedded Johnson scheme, cf.
10, 19, 20 and 16. That a Johnson scheme $\mathfrak{J}(m,t)$ is non-trivial
means in particular that $t\geq 2$.

[Extended Design Lemma, [Bab15, Theorem 7.3.3]] a threshold parameter
$3/4\leq\alpha<1$, a $k$-ary relational structure
$\mathfrak{X}=(\Omega,\mathscr{R})$ with relative symmetry defect $>1-\alpha$,
such that $2\leq k\leq n/4$ for $n=\abs\Omega$.
Either

  1. 1.

a canonical colored $\alpha$-partition of $\Omega$, or

  2. 2.

a canonically embedded non-trivial Johnson scheme on a subset
$W\subseteq\Omega$ of size $\abs W\geq\alpha n$.

multiplicative and additive costs of $n^{O(k+\log n)}$

The Extended Design Lemma with its various parts is one of the core elements
of Babai’s algorithm. That its discussion here will be rather brief should not
disguise that its justification in [Bab15] takes more than twenty pages of
elaborate arguments. The included case of uniprimitive coherent configurations
(UPCC) was the part where Helfgott in 2017 found a mistake invalidating the
overall quasi-polynomial bound. The issue has long been resolved by Babai, cf.
[Hel17b].

We will give a short overview of the Extended Design Lemma’s internal
mechanisms and justify the complexity claim following [HBD17, §5, p. 41]. The
first step is to transform the $k$-ary relational structure $\mathfrak{X}$
into a $k$-ary coherent configuration
$\mathfrak{Y}=(\Omega,c:\Omega^{k}\to\mathscr{C})$, cf. 12. The algorithm of
Weisfeiler-Leman is the method of choice, cf. [HBD17, §2.5]. In time
$k^{2}n^{2k+1}\log k\ll n^{O(k)}$ it iteratively refines the color classes of
$\mathfrak{X}$ until the resulting structure satisfies the desired regularity
conditions. Importantly, the assignment of the coherent configuration to the
input structure is canonical. Hence, the algorithm does not incur any
multiplicative costs. Note that we simplified the explanation hiding that
Weisfeiler-Leman actually takes configurations as an input, cf. 11. In fact,
the given relational structure is first refined to a partition structure and
then to a configuration. This process is formalized in [HBD17, §2.3]. The
additional costs can be hidden in the implicit constants of the estimates for
Weisfeier-Leman.

After having obtained the coherent configuration $\mathfrak{Y}$, we start a
brute force search for tuples of distinct elements
$(x_{1},\dots,x_{l})\in\Omega^{l}$ for $l\leq k-1$. For each of these tuples
we check in $n^{O(1)}$ the following two conditions:

  1. 1.

There exists no color $i\in\mathscr{C}$ such that there are
$\geq\alpha\abs\Omega$ values of $\gamma\in\Omega$ with $c^{\prime}(\gamma)=i$
in the partition structure $\mathfrak{Z}^{\prime}$ defined as

$\mathfrak{Z}^{\prime}\coloneqq\left(\Omega,\
c^{\prime}:\Omega\to\mathscr{C},\omega\mapsto
c(x_{1},\dots,x_{l},\omega,\dots,\omega)\right).$

  2. 2.

It holds that $l\leq k-2$ and there exists a color $i\in\mathscr{C}$ from
$\mathfrak{Z}^{\prime}$ such that $c^{\prime}(\gamma)=i$ for
$\geq\alpha\abs\Omega$ values of $\gamma\in\Omega$. Let furthermore
$C\subseteq\Omega$ denote the color class of $i$. The structure

$\mathfrak{Z}^{\prime\prime}\coloneqq\left(C,\ c^{\prime\prime}:C\times
C\to\mathscr{C},(\omega_{1},\omega_{2})\mapsto
c(x_{1},\dots,x_{l},\omega_{1},\omega_{2},\dots,\omega_{2})\right)$

is not a clique, i.e. it admits at least one non-trivial color class.

That we can find a tuple satisfying at least one of the above conditions is
guaranteed by the Design Lemma, cf. [HBD17, Proposition 5.1], under the
assumption that $\mathfrak{X}$ and hence $\mathfrak{Y}$ have large symmetry
defect. Thus, finding a suitable tuple takes $n^{O(k)}$. We would like to
utilize the structure $\mathfrak{Z}^{\prime}$ or respectively
$\mathfrak{Z}^{\prime\prime}$ which is associated to the tuple. Unfortunately,
the choice of the tuple is not canonical. We have to individualize the tuple
in order to treat the structure afterwards as a canonical feature, cf. section
5.3 for a detailed explanation of this strategy. The total number of tuples
equals the incurred multiplicative costs of $n^{O(k)}$.

We will now work with $\mathfrak{Z}^{\prime}$ and
$\mathfrak{Z}^{\prime\prime}$. In item 1 we have found nothing else than a
coloring of $\Omega$ with no color class larger than $\alpha\abs\Omega$.
Taking the color classes as blocks we obtain a colored $\alpha$-partition as
desired and terminate. If contrarily item 2 holds, we use
$\mathfrak{Z}^{\prime\prime}$ as an input for the Split-Or-Johnson routine,
cf. [HBD17, Theorem 3.5]. We observe that $\mathfrak{Z}^{\prime\prime}$
inherits the property of being a coherent configuration from $\mathfrak{Y}$,
cf. [HBD17, Exercises 2.11, 2.13]. Overtly, $\mathfrak{Z}^{\prime\prime}$ is
classical and by construction homogeneous. In the case that
$\mathfrak{Z^{\prime\prime}}$ is not primitive we obtain by [HBD17, Exercise
2.16] a colored $1/2$-partition as desired, cf. 13. We have now ensured that
$\mathfrak{Z}^{\prime\prime}$ is a uniprimitive classical coherent
configuration. Hence, we are ready to invoke Split-Or-Johnson. In time
$n^{O(1)}$ we find either a colored $\alpha$-partition or a Johnson scheme on
a subset $W\subseteq\Omega$ of size $\abs W\geq\alpha\abs\Omega$. Again, these
findings are not canonical. The conducted individualization accounts for
multiplicative costs of $n^{O(\log n)}$.

##  Chapter 4 Overview of the Algorithm

Main Procedure Input: $G\leq\Sym(\Omega)$, $\str x,\str y:\Omega\to\Sigma$
Output: $\Iso_{G}(\str x,\str y)=\Aut_{G}(\str x)\sigma$ or $\emptyset$ $G$
small Brute Force $G$ transitive Reduction $G/N$ small Reduction $G$ primitive
$k=1$ Large Symmetry Reduction Local Certificates Reduction Canonical
structure Extended Design Lemma Johnson scheme Colored partition Reduction
Reduction Trivial Case noyesnoyesnonoyesnoc. 2acases 2b, 3case 1yesnoyesyes

Figure 4.1: Overview of the main procedure. Some trivial branches have been
omitted.

As this thesis focuses on one particular case of Babai’s algorithm, it is
worth obtaining an impression of the overall algorithm that decides the String
Isomorphism Problem. We will refer to it as the _main procedure_. As outlined
earlier, it requires three arguments: the strings $\str x,\str
y:\Omega\to\Sigma$ and a description of a permutation group
$G\leq\Sym(\Omega)$, i.e. a set of its generators. Principally, our result
will be either that $\Iso_{G}(\str x,\str y)$ is empty or that

$\Iso_{G}(\str x,\str y)=\Aut_{G}(\str x)\sigma$

for $\sigma\in\Iso_{G}(\str x,\str y)$. In the latter case we aim at computing
generators for $\Aut_{G}(\str x)$ and a suitable $\sigma$. The following steps
are undertaken to decide the problem. Details beyond the case of imprimitivity
will be omitted. For these aspects, the reader is pointed to [HBD17, §3.1] and
[Bab15, §3.3].

###  4.1 First steps

We can first exclude some trivial cases. If $G\leq\Aut(\str x)$, then
$\Iso_{G}(\str x,\str y)=G$ if $\str x=\str y$ or empty if not. We recall that
$G$ is without loss of generality described by polynomially many generators,
cf. section 3.2. Thus the condition is testable in polynomial time. If
furthermore $\abs{G}<C$ for some absolute constant $C$, then we compute
$\Iso_{G}(\str x,\str y)$ with brute force in constant time. Many theorems
require some absolute lower bounds on $\abs G$. These restrictions should not
bother us because we are always interested in asymptotic behaviors only.
Sufficiently small subproblems will be solved brutally.

If $G$ acts intransitively on $\Omega$, strong Luks reduction can be used to
recur on the orbits, that is on shorter strings, cf. 3.3.2. Now suppose that
$G$ is transitive. We aim at passing to a primitive action which allows us to
use a group theoretic result by Cameron-Maróti. Using polynomial time
algorithms described in section 3.1 we compute a minimal system of blocks
$\mathscr{B}$. Let $n=\abs{\mathscr{B}}$. The induced action on the blocks
presents itself as an epimorphism $G\to G^{\prime}$ where
$G^{\prime}\leq\Sym(\mathscr{B})$. Let $N$ denote the kernel of this map. $N$
stabilizes the blocks, i.e. $B^{g}=B$ for each $B\in\mathscr{B}$ and all $g\in
N$. The group $G/N\cong G^{\prime}$ acts primitively on $\mathscr{B}$. Under
these circumstances, Cameron-Maróti implies one of the three following cases:

######  Theorem 4.1.1 (Cameron-Maróti, [Mar02, Theorem 1.1], [Bab15, Theorem
3.2.1]).

Let $G^{\prime}\leq\Sym_{n}$ be a primitive permutation group. Then one of the
following holds:

  1. 1.

$G^{\prime}$ is a _Cameron group_. That is, there exist $m,k,r\in\mathbb{N}$
such that $n=\binom{m}{k}^{r}$. The group $G^{\prime}$ is a subgroup of
$\Sym_{m}^{(k)}\wr\Sym_{r}$ with the primitive product action111See [DM96,
§§2.6, 2.7] for definitions of the wreath product and its primitive action. on
$\binom{\Gamma}{k}^{r}$ for $\Gamma=\\{1,\dots,m\\}$. $G^{\prime}$ admits the
normal subgroup $\left(\Alt_{m}^{(k)}\right)^{r}$. Furthermore,
$\gindex{G^{\prime}}{\left(\Alt_{m}^{(k)}\right)^{r}}\leq n$.

  2. 2.

$G^{\prime}$ is a Mathieu group with $n<25$.

  3. 3.

$\abs{G^{\prime}}<n^{1+\log_{2}n}$.

As explained above, we are not interested in item 2. For distinguishing
footnotes 1 and 3 we compute $\gindex{G}{N}=\abs{G^{\prime}}$ in polynomial
time using Schreier-Sims. In case of item 3 we perform strong Luks reduction
to reduce from $G$ to $N$, cf. 3.3.2. We obtain $n\cdot n^{1+\log_{2}n}$
subproblems of length $\leq\abs{\Omega}/n$.

In the last case, we find a subgroup with admissibly small index and well
understood action: We know that $G/N$ contains a normal subgroup $M$ which
acts on $\mathscr{B}$ as $\left(\Alt_{m}^{(k)}\right)^{r}$. $M$ must be
understood as contained in the base $\left(\Sym_{m}^{(k)}\right)^{r}$ of the
wreath product. Hence, it acts on $\binom{\Gamma}{k}^{r}$ as
$a^{\sigma}(i)=a(i)^{\sigma(i)}$ for $a\in\binom{\Gamma}{k}^{r},1\leq i\leq
r,\sigma\in M$, where we understand $M$ as the group of all maps
$\\{1,\dots,r\\}\to\Alt_{m}^{(k)}$ with pointwise multiplication. Clearly,
this action admits a coarser system $\mathscr{B}^{\prime}$ of $\binom{m}{k}$
blocks of size $\binom{m}{k}^{r-1}$, i.e. those that arise when fixing the
first entry in the tuples of $\binom{\Gamma}{k}^{r}$. On these blocks, $M$
acts as Johnson group $\Alt_{m}^{(k)}$ inducing a homomorphism
$M\to\Alt(\Gamma)$.

We have to transform this abstract structural knowledge into tangible
information. [BLS87] provides us with the tools to map out the structure of
the Cameron group $G/N$ and the blocks of its action. This takes polynomial
time. Let $\pi:G\to G/N$ denote the projection of $G$ onto $G/N$ and set
$M^{\prime}=\pi^{-1}(M)$. Then $M^{\prime}$ acts on $\Omega$ admitting the
blocks $\mathscr{B}^{\prime}$ on which it acts as Johnson group. Let
$N^{\prime}\leq M^{\prime}$ denote the stabilizer of $\mathscr{B}^{\prime}$.

We apply section 3.4 with input
$M^{\prime}/N^{\prime}\leq\Sym(\mathscr{B}^{\prime})$ and $m$, $k$, obtaining
a bijection $\iota^{\prime}:\mathscr{B}^{\prime}\to\binom{\Gamma^{\prime}}{k}$
and an isomorphism $\varphi:M^{\prime}/N^{\prime}\to\Alt(\Gamma^{\prime})$
where $\Gamma^{\prime}$ is a set of $m$ elements constructed by that
procedure. $\iota^{\prime}$ can be naturally extended to a surjection
$\iota:\Omega\to\binom{\Gamma^{\prime}}{k}$ with the property that each
$\gamma\in\binom{\Gamma^{\prime}}{k}$ has precisely
$\abs\Omega\binom{m}{k}^{-1}$ preimages.

Using weak Luks reduction we pass from $G$ to $M^{\prime}$. The multiplicative
costs are linear since
$\gindex{G}{M^{\prime}}=\gindex{G}{\pi^{-1}(M)}=\frac{\abs G}{\abs
M\abs{\ker\pi}}=\gindex{G/N}{M}\leq n$. Call $M^{\prime}$ from now on $G$ and
let $\Gamma\leftarrow\Gamma^{\prime}$. We then hold an epimorphism
$\varphi:G\to\Alt(\Gamma)$. The stabilizer of the blocks in
$\mathscr{B}^{\prime}$ is precisely the kernel of the map $\varphi$. Thus, the
epimorphism $\varphi$ is injective if and only if the action of $G$ on
$\Omega$ is primitive. The case of $\varphi$ having a non-trivial kernel is
therefore called the _imprimitive case_. It is the main subject of this
thesis.

We rename $N\leftarrow\ker\varphi=N^{\prime}$, obtaining
$\varphi:G/N\to\Alt(\Gamma)$, an isomorphism. Moreover, we can exclude the
case $\abs\Gamma\ll\log\abs\Omega$. If this holds, we have
$\gindex{G}{N}=\frac{1}{2}\abs\Gamma!<\abs\Gamma^{\abs\Gamma}\ll\abs\Omega^{O(\log\abs\Omega)}$
and can afford a strong Luks reduction from $G$ to $N$. Since $N$ is a
stabilizer of $\binom{m}{k}$ blocks, we obtain
$n\abs{\Omega}^{O(\log\abs\Omega)}\ll\abs{\Omega}^{O(\log\abs\Omega)}$
subproblems for strings of length
$\leq\abs\Omega/\binom{m}{k}\leq\abs\Omega/2$.

Let us summarize the setting which will occupy us for the rest of this thesis:
Being given two strings $\str x,\str y:\Omega\to\Sigma$ as inputs, we have
reduced the problem to a group $G\leq\Sym(\Omega)$ for which we hold a
description of an epimorphism $\varphi:G\to\Alt(\Gamma)$. During the reduction
the original input strings have been manipulated, in particular shifted by
permutations. We will refer to the updated strings as $\str x$ and $\str y$.
The set $\Gamma$ is explicitly known, we even possess a surjection
$\iota:\Omega\to\binom{\Gamma}{k}$ respecting $\varphi$. We can suppose that
$\abs\Gamma\gg\log\abs\Omega$ and that $G$ acts transitively on $\Omega$.

###  4.2 The primitive case and the case of large symmetry

The subject of this thesis is the imprimitive case which is treated using
local certificates. In this case, $G$ acts imprimitively on $\Omega$, i.e.
admitting non-trivial blocks. Before looking at this case, we want to give an
overview of the other parts of the algorithm, in particular of the primitive
case. $G$ acts primitively on $\Omega$, $\varphi:G\to\Alt(\Gamma)$ is an
isomorphism and $\iota:\Omega\to\binom{\Gamma}{k}$ is a bijection.

If $k=1$, we are in the very comfortable situation in which
$G=\Alt(\Omega)=\Alt(\Gamma)$. We can compute $\Iso_{G}(\str x,\str y)$
rapidly. The two strings are isomorphic if and only if their letters occur
with the same multiplicities. This can be verified in polynomial time. In
order to describe $\Aut_{G}(\str x)$, we color the letters in $\Sigma$
according to their multiplicities in $\str x$. $\Aut_{G}(\str x)$ consists
then of all permutations that swap letters of the same color. We can now
describe $\Aut_{G}(\str x)$ in polynomial time. The strategy is described in
the following example. Finally, we require a permutation
$\sigma\in\Alt(\Omega)$ mapping $\str x$ to $\str y$. We obtain $\sigma$ by
computing the same coloring on $\str y$ and imposing the additional condition
that the permutation must belong to $\Alt(\Omega)$, as well in polynomial
time. Our result is then

$\Iso_{G}(\str x,\str y)=\Aut_{G}(\str x)\sigma.$

######  Example 4.2.1.

We want to construct $\Aut_{G}(\str x)$ explicitly for $\str
x=\mathsf{hippopotomonstrosesquippedaliophobia}$, i.e.
$\Omega=\\{1,\dots,36\\}$, $\Sigma=\\{\mathsf{a},\dots,\mathsf{z}\\}$. The
coloring is induced by the multiplicities:

color/multiplicity | 7 | 6 | 4 | 3 | 2 | 1
---|---|---|---|---|---|---
letters | o | p | i | s | a, e, h, t | b, d, l, m, n, q, r, u

For the colors 7, 6, 4, 3 and 1 we obtain rather simple contributions to
$\Aut_{G}(\str x)$ because here no blocks need to be considered. For example
for color 7, we add generators for $\Sym(\\{5,7,9,11,16,30,33\\})$. Color
class 2 is more complicated. On the upper level, the four letters can be
permuted while on the lower level the positions carrying the same letter can
be swapped. The contribution of this color class is therefore isomorphic to
$\Sym_{2}\wr\Sym_{4}$. We add permutations for the lower level, e.g. $(27\
36)$ for $\mathsf{a}$, and permutations for the upper level, e.g. $(18\
27)(25\ 36)$ corresponding to a swap of $\mathsf{a}$ and $\mathsf{e}$. After
we have computed generators for all these building blocks, we may have added
odd permutations. However, we can apply Schreier-Sims, cf. section 3.2, to
make sure that the resulting group is indeed a subgroup of $\Alt(\Omega)$.

Before considering the more complex case, we note that
$k\leq\log_{2}\abs\Omega$. This follows from
$\abs\Omega=\binom{\abs\Gamma}{k}\geq(\abs\Gamma/k)^{k}\geq 2^{k}$, since by
construction $1\leq k\leq\abs\Gamma/2$.

Let us now look at the case $k>1$ and $G$ primitive. We want to rule out the
case of large symmetry since it cannot be treated by the Design Lemma, cf.
section 3.6. The Design Lemma processes $k$-ary relational structures with
little symmetry (or large symmetry defect), cf. 10 and 19. We want to build
such structures, one for each of the input strings. Let

$\mathfrak{X}(\str
x)\coloneqq\left(\Gamma,(R_{\alpha})_{\alpha\in\Sigma}\right),\quad
R_{\alpha}\coloneqq\left\\{(\gamma_{1},\dots,\gamma_{k})\in\Gamma^{k}\
\middle|\ \str
x\left(\iota^{-1}\left(\\{\gamma_{1},\dots,\gamma_{k}\\}\right)\right)=\alpha\right\\}\text{
for }\alpha\in\Sigma$

and $\mathfrak{X}(\str y)$ respectively. Both are $k$-ary partition
structures. An edge in $\Gamma^{k}$ carries a color corresponding to the
letter at the position in the string which is associated to the edge in virtue
of $\iota$. This definition is possible since
$\iota:\Omega\to\binom{\Gamma}{k}$ is a bijection. The structures canonically
depend on the two strings. Hence, whenever we witness that $\mathfrak{X}(\str
x)$ and $\mathfrak{X}(\str y)$ have differing canonical properties, we can
refute isomorphicity. We can map out the two structures in
$\abs\Gamma^{k}\ll\abs\Omega^{O(\log\abs\Omega)}$ many steps.

In order to distinguish cases, we have to compute the twin classes of the
relational structures. Two elements $\gamma_{1},\gamma_{2}\in\Gamma$ are twins
in $\mathfrak{X}(\str x)$, if the transposition $(\gamma_{1}\
\gamma_{2})\in\Aut(\mathfrak{X}(\str x))$. This equivalence relation can be
written alternatively222We cannot pull out $(\gamma_{1}\ \gamma_{2})$ of
$\iota$ using eq. 3.4 because this transposition is clearly not contained in
$G^{\varphi}=\Alt(\Gamma)$. as

$\gamma_{1}\sim_{\str x}\gamma_{2}\iff\forall j\in\binom{\Gamma}{k}:\ \str
x\left(\iota^{-1}(j)\right)=\str x\left(\iota^{-1}\left(j^{(\gamma_{1}\
\gamma_{2})}\right)\right),$

Here, the transposition acts naturally on sets, i.e. $(\gamma_{1}\
\gamma_{2})\in\Sym^{(k)}(\Gamma)$. The condition can be verified for all pairs
$\gamma_{1},\gamma_{2}$ in polynomial time. Since there are
$\binom{\abs\Gamma}{2}\ll\abs\Omega^{2}$ such pairs, we obtain the entire twin
class structure in polynomial time. Having computed the twin classes, we can
easily determine the symmetry defect. Let $T\subseteq\Gamma$ such that
$\Gamma\setminus T$ is a largest twin class by cardinality. The (relative)
symmetry defect is defined as $\abs{T}/\abs{\Gamma}$. Again, the twin classes
of $\mathfrak{X}(\str x)$ and $\mathfrak{X}(\str y)$ may not be identical as
sets. However, if they differ in size we can refute isomorphicity.

Suppose that we are in the case of large symmetry, i.e. both structures have
symmetry defect $\leq 1/2$. Let $C_{\str x}$ and $C_{\str y}$ denote the large
twin classes satisfying $\abs{C_{\str x}}=\abs{C_{\str y}}>\abs\Gamma/2$. Due
to their size they are unique and thus canonical. We can without loss of
generality assume that $\abs{C_{\str x}}=\abs{C_{\str y}}$.

The next step is to _align_ the two dominating twin classes. This strategy
will be used often throughout the entire algorithm. By enumerating both
classes, we can construct a $\sigma\in\Alt(\Gamma)$. We lift this permutation
along $\varphi$ to a $\tau=\varphi^{-1}(\sigma)\in G$ using Schreier-Sims.
Replacing $\str y$ by $\str y^{\tau}$ is what Babai calls alignment, cf.
[Bab15, §14.1]. Shifting $\str y$ to $\str y^{\tau}$ does not curtail our
capability of determining $\Iso_{G}(\str x,\str y)$, given that by lemma
3.3.1,

$\Iso_{G}(\str x,\str y)=\Iso_{G\tau^{-1}}(\str x,\str y)=\Iso_{G}\left(\str
x,\str y^{\tau}\right)\tau^{-1}.$

After having completed the alignment, we can assume that $C\coloneqq C_{\str
x}=C_{\str y}$. Applying section 3.5, we let the partition
$\Gamma=(\Gamma\setminus C)\mathbin{\dot{\cup}}C$ induce a partition
$\Omega_{0}\mathbin{\dot{\cup}}\cdots\mathbin{\dot{\cup}}\Omega_{k}$ of
$\Omega$. The resulting partition satisfies $\abs{\Omega_{i}}\leq\abs\Omega/2$
for $0<i\leq k$ since
$\abs{\Omega_{0}}=\abs{\iota^{-1}\binom{C}{k}}>\abs\Omega/2$. Every
isomorphism $\sigma$ from $\str x$ to $\str y$ must preserve the former
partition, i.e. $C^{\varphi(\sigma)}=C$. Hence, we have reduced the problem
such that $\Iso_{G}(\str x,\str y)=\Iso_{H}(\str x,\str y)$ for
$H=\varphi^{-1}(\Alt(\Gamma)_{C})$.

We can easily compute $H$ despite that it is the preimage of a setwise
stabilizer. The computation merely involves taking the preimage of five
generators applying Schreier-Sims: By eq. 3.2, $\Alt(C)$ and
$\Alt(\Gamma\setminus C)$ are generated each by two elements, thus
$\Alt(C)\times\Alt(\Gamma\setminus C)$ requires four generators. The fifth is
of the form $\tau\coloneqq(a_{1}\ a_{2})(b_{1}\ b_{2})$ where $a_{1},a_{2}\in
C$ and $b_{1},b_{2}\in\Gamma\setminus C$ and adds elements that are products
of two odd permutations taken from the two alternating groups. We can pass to
an even smaller group, namely
$H^{\prime}=\varphi^{-1}(\Alt(C)\times\Alt(\Gamma\setminus C))$. Here, we
must, of course, read $\Alt(C)\times\Alt(\Gamma\setminus C)$ as a subgroup of
$\Alt(\Gamma)$. The quotient $H/H^{\prime}$ contains apart from the identity
only $H^{\prime}\tau$. Applying weak Luks reduction, cf. LABEL:proc:weak-luks,
the task reduces to the two problems of determining $\Iso_{H^{\prime}}(\str
x,\str y)$ and $\Iso_{H^{\prime}}\left(\str x,\str y^{\tau^{-1}}\right)$. Even
in the latter case $C$ remains a twin class because $\tau$ leaves this set
invariant. We treat both instances of the subproblem similarly. Let $\str y$
denote the second string in any case.

Since $C$ is a twin class for $\str x$ and $\str y$, every permutation in
$\varphi^{-1}(\Alt(C))$ leaves $\str x$ and $\str y$ unchanged. By
construction, $C$ corresponds to $\Omega_{0}$. Hence, $\Iso_{H^{\prime}}(\str
x,\str y)$ is empty if $\restrict{\str x}{\Omega_{0}}\neq\restrict{\str
y}{\Omega_{0}}$. Let us thus suppose the contrary. In this case,
$\Iso_{H^{\prime}}(\str x,\str
y)=\Iso_{\restrict{H^{\prime}}{\Omega^{\prime}}}\left(\restrict{\str
x}{\Omega^{\prime}},\restrict{\str y}{\Omega^{\prime}}\right)$ for
$\Omega^{\prime}=\Omega\setminus\Omega_{0}$ holds. We have reduced the problem
significantly. $\restrict{H^{\prime}}{\Omega^{\prime}}$ acts on
$\Omega^{\prime}$. Section 3.5 ensures that $\Omega_{j}$ is the set of
elements $\omega\in\Omega$ with the property that $\abs{\iota(\omega)\cap
C}=k-j$. This value is an invariant under the action of
$\restrict{H^{\prime}}{\Omega^{\prime}}$ because the $\varphi$-image of this
group fixes $C$. Therefore, the orbits of
$\restrict{H^{\prime}}{\Omega^{\prime}}$ acting on $\Omega^{\prime}$ must
refine the partition
$\Omega^{\prime}=\Omega_{1}\mathbin{\dot{\cup}}\cdots\mathbin{\dot{\cup}}\Omega_{k}$.
Each orbit is hence of length $\leq\abs\Omega/2$. We recur on the orbits by
applying strong Luks reduction, cf. 3.3.2. This yields $k\ll\log\abs\Omega$
subproblems for strings of length $\leq\abs\Omega/2$ and total length
$\leq\abs\Omega$.

We have treated the case of large symmetry. Let us now assume that
$\mathfrak{X}(\str x)$ and $\mathfrak{X}(\str y)$ have symmetry defect $>1/2$.
On both structures we apply the Design Lemma, cf. section 3.6, obtaining
canonically colored partitions or canonically embedded non-trivial Johnson
schemes. We have prepared everything to finish the reduction with section 5.4.

##  Chapter 5 Local certificates

We will now discuss the crucial part of Babai’s algorithm. The situation is
the same as in the previous section. We possess an epimorphism
$\varphi:G\to\Alt(\Gamma)$ and a surjection $\iota:\Omega\to\Sym(\Omega)$. We
can suppose that $G$ acts imprimitvely. In order to exploit the correspondence
between $\Omega$ and $\Gamma$ we introduce the following slightly abusive
notions: For a homomorphism $\varphi:G\to\Alt(\Gamma)$ and a set
$T\subseteq\Gamma$ we define the stabilizers

$G_{T}=\left\\{g\in G\ \middle|\ T^{\varphi(g)}=T\right\\},\quad
G_{(T)}=\left\\{g\in G\ \middle|\ \forall t\in T:t^{\varphi(g)}=t\right\\}.$

The strategy is to turn local information into knowledge about the global
structure of the set of isomorphisms $\Iso_{G}(\str x,\str y)$. The procedure
works as follows: First, we look only at one of the strings, say $\str{x}$,
and try to encase its automorphism group $\Aut_{G}(\str{x})$ from above and
from below. Approximating it from above involves finding canonical structures
in the string which must be preserved by any automorphism, while for bounding
the group from below constructing explicit automorphisms will be crucial. We
attack this problem locally. For moderately sized test sets $T\subseteq\Gamma$
we verify either that the image under $\varphi$ of the stabilized automorphism
group $\Aut_{G_{T}}(\str{x})$ contains $\Alt(T)$ or that this image is
contained in a proper subgroup of $\Alt(T)$. The first outcome will be called
_certificate of fullness_ while we refer to the latter as a _certificate of
non-fullness_. After collecting certificates for all $T\subseteq\Gamma$ of a
certain size, this information is aggregated into knowledge about the global
structure of $\Aut_{G}(\str{x})$. Now, we proceed similarly with the second
string $\str{y}$. Section 5.1 is about the construction of local certificates.
Comparing local certificates will be the subject of section 5.2. In section
5.3 we will explain how these tools allow us to detect canonical structures
which are the basis for an efficient reduction of the problem described in
section 5.4.

Formally, the two types of certificates we wish for are defined as follows:

######  Definition 22.

Let $\str x:\Omega\to\Sigma$, $G\leq\Sym(\Omega)$, $\varphi:G\to\Sym(\Gamma)$.
Let $T\subseteq\Gamma$.

  1. 1.

A _certificate of non-fullness_ for $T$ is a tuple $(W,M(T))$ where
$W\subseteq\Omega$ the window, $M(T)\leq\Sym(T)$, $M(T)\neq\Alt(T)$ and
$\restrict{\varphi\left(\Aut_{G_{T}}^{W}(\mathbf{x})\right)}{T}\leq
M(T)$.111For $T\subseteq\Gamma$ and $H\leq G_{T}$, the set of permutations in
the image of $H$ is denoted as
$\restrict{\varphi(H)}{T}=\left\\{\restrict{\varphi(h)}{T}\mid h\in
H\right\\}$.

  2. 2.

A _certificate of fullness_ for $T$ is group
$K(T)\leq\Aut_{G_{T}}(\mathbf{x})$ and
$\left.\varphi(K(T))\right|_{T}=\Alt(T)$.

Note that the type of certificate which $T$ admits depends on the group $G$
and the string $\str x$. Thus, when considering different strings and the same
test set $T$ we may or may not arrive at the same type of certificate. The
window measures how much of the input is considered. The strategy will be to
iteratively enlarge the window by looking at specific elements in the domain
$\Omega$:

######  Definition 23.

Let $G\leq\Sym(\Omega)$, $\varphi:G\to\Sym(\Gamma)$. An element $x\in\Omega$
is called _affected_ with respect to $\varphi$ and a subgroup $H\leq G$ if
$\varphi(H_{x})$ does not contain $\Alt(\Gamma)$. Given a tuple $(H,\varphi)$,
$\Aff(H,\varphi)\subseteq\Omega$ denotes the set of all elements in $\Omega$
affected by $(H,\varphi)$.222This definition is consistent with [HBD17,
Definition 4.2] and adopted from [Bab15, Definition 10.1.4].

We quote one of Babai’s results which justifies the correctness of the
subsequent algorithm as proven in [Bab15, Theorem 8.3.5, Corollary 8.3.7], cf.
[HBD17, Proposition 4.4].

######  Theorem 5.0.1.

Let $G\leq\Sym(\Omega)$, $\varphi:G\to\Alt_{k}$ an epimorphism and
$U=\Omega\setminus\Aff(G,\varphi)$ the set of unaffected elements. Then the
following hold:

  1. 1.

_(Unaffected Stabilizer Theorem)_ Suppose
$k>\max\left\\{8,2+\log_{2}n_{0}\right\\}$ where $n_{0}$ is the length of the
largest $G$-orbit. Then $\left(G_{(U)}\right)^{\varphi}=\Alt_{k}$.

  2. 2.

_(Affected Orbit Lemma)_ Assume $k>5$. If $\Delta$ is a $G$-orbit containing
some affected elements, then each orbit of $ker\varphi$ contained in $\Delta$
is of length $\leq\abs\Delta/k$.

The Unaffected Stabilizer Theorem and the Affected Orbit Lemma are results
genuinely originating in the theory of permutation groups. The proof was
simplified by P. P. Pálfy, according to [Bab15], and depends on the
Classification of Finite Simple Group (CFSG), although Pyber [Pyb16] proved
the claims CFSG-independently for larger $k$. In contrary to section 3.6,
their justification is rather short but far from being trivial. The assumption
$k>\max\left\\{8,2+\log_{2}n_{0}\right\\}$ is tight as Babai outlines in
[Bab15, Remark 8.2.5].

$G\leq\Sym(\Omega)$$\Alt(\Gamma)$$\Omega$$\Gamma$$T$$\varphi$$\iota$$\Alt(\Gamma)_{T}$$W$$\Aut_{G_{T}}(\str
x)\leq\Aut_{G_{T}}^{W}(\str x)$$\Alt(T)$$M(T)$

(a) Certificate of non-fullness

$G\leq\Sym(\Omega)$$\Alt(\Gamma)$$\Omega$$\Gamma$$T$$\varphi$$\iota$$\Alt(\Gamma)_{T}$$\Alt(T)$$\Aut_{G_{T}}(\str
x)$$K(T)$

(b) Certificate of fullness

Figure 5.1: Schematic overview of local certificates. The group of interest in
gray is $\Aut_{G_{T}}(\str x)$ for the test set $T$. It is either encased by
$\Aut_{G_{T}}^{W}(\str x)$ from above (non-full) or by $K(T)$ from below
(full). Crucial is whether the restriction to $T$ of the encasing group’s
$\varphi$-image is $\Alt(T)$, a giant. $G$ and the smaller $\Alt(\Gamma)$ are
linked via $\varphi$ and $\iota:\Omega\to\binom{\Gamma}{l}$. For simplicity,
we do not make a strict distinction between $\varphi$ and
$g\mapsto\restrict{g^{\varphi}}{T}$.

###  5.1 Construction of local certificates

In this section we introduce an algorithm which verifies whether a test set
$T\subseteq\Gamma$ is full or non-full. As explained before, this property
does not depend on $T$ alone but also on $G$ and $\str x$. Throughout the
procedure we consider more and more of the input string. Babai visualizes this
strategy as “growing the beard”, cf. fig. 5.1(a). We will realize this
iterative enlargement of the window by looking at affected elements.

In contrary to [HBD17, §6.1.1], the algorithm will be presented in less
natural language following [Bab15, §10.1]. For convenience, $A(W)$ will stand
for $\Aut_{G_{T}}^{W}(\str x)\leq G_{T}$. As $W=\emptyset$ imposes an vacuous
condition on $A(W)$, the group equals $G_{T}$ at the beginning. Throughout the
procedure $W$ is enlarged which implies that $A(W)$ shrinks. For our test set
$T$ we set $k\coloneqq\abs T$ and suppose that
$\max\left\\{8,2+\log_{2}\abs\Omega\right\\}<k\ll\log\abs\Omega$. Thus, $T$ is
of logarithmic size in $\abs\Omega$.

Local Certificates test set $T\in\binom{\Gamma}{k}$, group
$G\leq\Sym(\Omega)$, epimorphism $\varphi:G\to\Alt(\Gamma)$, string $\str
x:\Omega\to\Sigma$ either a certificate of fullness $K(T)$ or a certificate of
non-fullness $(W,M(T))$ localcert

$W\leftarrow\emptyset$

$A(W)\leftarrow G_{T}=\varphi^{-1}(\Alt(\Gamma)_{T})$

while $\restrict{\varphi(A(W))}{T}\geq\Alt(T)$ and
$\Aff(A(W),\varphi)\not\subseteq W$:

$W^{+}\leftarrow\Aff(A(W),\varphi)$

$N\leftarrow\ker\restrict{\varphi}{A(W)}=A(W)_{(T)}$, where333As $A(W)\leq
G_{T}$, we can restrict $\varphi$ in a well-defined manner to a map
$A(W)\to\Alt(T)$. $\restrict{\varphi}{A(W)}:A(W)\to\Alt(T)$

$A(W^{+})\leftarrow\emptyset$

compute a set of right coset representatives $S$ for $N$ in $A(W)$

for $\sigma\in S$:

$A(W^{+})\leftarrow A(W^{+})\cup\Iso_{N}^{W^{+}}\left(\str
x,\str{x}^{\sigma^{-1}}\right)\sigma$, by recurring on orbits

end

$W\leftarrow W^{+},A(W)\leftarrow A(W^{+})$

end

if $\restrict{\varphi(A(W))}{T}\geq\Alt(T)$:

$K(T)\leftarrow A(W)_{(\Omega\setminus W)}$

return certificate of fullness $K(T)$

else:

$M(T)\leftarrow\restrict{\varphi(A(W))}{T}$

return certificate of non-fullness $(W,M(T))$

end

Our goal is to verify whether $\restrict{\varphi(\Aut_{G_{T}}(\str x))}{T}$ is
or is not equal to $\Alt(T)$. In every step we enlarge the window by the
elements affected by $\Aut_{G_{T}}^{W}(\str x)$. Two scenarios trigger a
termination. Either the window stops growing or $\restrict{\varphi(A(W))}{T}$
no longer contains the alternating group on $T$. Theorem 5.0.1 is crucial: If
as in the first case $W$ contains all $(A(W),\varphi)$-affected elements and
$\restrict{\varphi}{A(W)}:A(W)\to\Alt(T)$ is surjective, then
$\restrict{\varphi\left(A(W)_{(\Omega\setminus W)}\right)}{T}=\Alt(T)$.
Furthermore, $A(W)_{(\Omega\setminus W)}\leq\Aut_{G_{T}}(\str x)$ as the
points in the complement of $T$ are fixed. Consequently, we have evaluated the
action of a subgroup on the entire string without looking at the entirety of
the input. In the other case, i.e. when the restricted map is not surjective,
we computed a certificate of non-fullness which verifies that the automorphism
group of interest is not equal to the alternating group. Importantly, the
assignments of the certificates to $\str x$ are canonical.

The procedure contains a couple of non-trivial operations whose execution
times must be carefully analyzed. In line 5.1 we have to determine $G_{T}$ for
a given $T$. Reverting to sections 3.2 and 4.2, we do so by computing the
preimage of $\Alt(\Gamma)_{T}$ under $\varphi$ after choosing five generators
for the latter group. By the surjectivity of $\varphi$,
$\frac{\abs{\Gamma}!}{2}\leq\abs{G}\leq\abs{\Omega}!$ and thus
$\abs{\Gamma}\ll\abs{\Omega}$, which guarantees a polynomial running time.

The set of affected elements $\Aff(A(W),\varphi)$ in line 5.1 is computed by
iterating over all $x\in\Omega$, checking whether
$\restrict{\varphi(A(W)_{x})}{T}=\Alt(T)$. Both the computation of $A(W)_{x}$
and the subsequent verification, are done using a modified version of
Schreier-Sims. The conditions in line 5.1 are straightforward to check once we
have computed $\Aff(A(W),\varphi)$.

For line 5.1 we recall that we hold a description of $A(W)$ in terms of the
generators of $G$. Thus, we can compute the kernel of
$\restrict{\varphi}{A(W)}$ by taking the preimage of the trivial group in
polynomial time. We may have to modify the generators of $A(W)$ in order to
reflect the restriction of the image from $\Alt(\Gamma)$ to $\Alt(T)$, but by
Schreier-Sims the generating set is not too big.

The purpose of the for-loop is to compute $A(W^{+})$. Prior to iterating, we
start with computing a set $S$ of right coset representatives for $N$ in
$A(W)$, cf. section 3.2. It is clear that $N=A(W)_{(T)}$ admits polynomial
membership testing. Since the quotient $A(W)/N$ is isomorphic to $\Alt(T)$, we
find $k!/2$ such representatives. Thus, computing them took quasi-polynomial
time. As $A(W^{+})\subseteq A(W)$ and $A(W)=\bigcup_{\sigma\in S}N\sigma$, we
have by lemma 3.3.1 that

$A(W^{+})=\Aut_{A(W)}^{W^{+}}(\str x)=\Aut_{\bigcup N\sigma}^{W^{+}}(\str
x)=\bigcup_{\sigma}\Aut_{N\sigma}^{W^{+}}(\str
x)=\bigcup_{\sigma}\Iso_{N}^{W^{+}}\left(\str
x,\str{x}^{\sigma^{-1}}\right)\sigma.$ (5.1)

We can compute this union as in eq. 3.3.

Since all elements in $W^{+}$ are by definition $(A(W),\varphi)$-affected,
they are all $(N,\varphi)$-affected. Thus, by theorem 5.0.1, all orbits of $N$
that are contained in $W^{+}$ are of size
$\leq\abs{W^{+}}/k\leq\abs{\Omega}/k$. We exploit this intransitivity to
further reduce the subproblems.

For every $\sigma$, we perform strong Luks reduction: In polynomial time we
compute a partition of $W^{+}$ into the orbits under the action of $N$. This
partition is $N$-invariant and acted upon trivially by $N$. Calling 3.3.2 we
reduce to one subproblem for each orbit.

After passing through all $\leq\abs\Omega$ orbits and all $\sigma$ we will
have called the main procedure $\leq\abs{\Omega}(k!/2)$ times on strings of
length $\leq\abs{\Omega}/k$. The additive costs are
$\abs{\Omega}^{O(\log\abs{\Omega})}$ in every iteration. As $W\subseteq\Omega$
is constantly growing, the while-loop’s body will be executed
$\leq\abs{\Omega}$ times. Thus, in total we recur to
$\leq\abs{\Omega}^{2}(k!/2)$ subproblems of size $\leq\abs{\Omega}/k$. As
$k\ll\log\abs\Omega$, this complies with the desired bound as we will see in
chapter 6. All steps considered, the additive costs account for
$\abs{\Omega}^{O(\log\abs{\Omega})}$ operations.

###  5.2 Comparing certificates

In practice, that is in the application in section 5.3, we are not only
interested in local certificates for one string but in the correspondence of
the certificates for both input strings. Hence, we require a procedure which
allows us to efficiently compare local certificates. By comparing two
certificates we mean verifying whether there exist string isomorphisms sending
one test set pointwise to the other and respecting certain parts of the input
strings.

The setting is as follows: We are given two strings $\str x,\str
y:\Omega\to\Sigma$, two test sets $T,T^{\prime}\subseteq\Gamma$ of the same
size $k=\abs T=\abs{T^{\prime}}$. Again, we will look at increasing parts of
the strings. The following notation will be useful.

[Truncation of strings] Let $\str x:\Omega\to\Sigma$ a string,
$W\subseteq\Omega$ the window. Then the _truncated string_ $\str
x^{W}:\Omega\to\Sigma\mathbin{\dot{\cup}}\\{\text{glaucous}\\}$ is defined as

$\str x^{S}(i)\coloneqq\begin{cases}\str x(i),&i\in S,\\\
\text{glaucous},&i\in\Omega\setminus S,\end{cases}$

where glaucous is a symbol alien to the alphabet $\Sigma$.

For a homomorphism $\varphi:G\to\Alt(\Gamma)$ and two sets
$T,T^{\prime}\subseteq\Gamma$ whose elements are ordered, i.e.
$T=\\{t_{1},\dots,t_{k}\\},T^{\prime}=\\{t^{\prime}_{1},\dots,t^{\prime}_{k}\\}$,
we define

$G_{T,T^{\prime}}\coloneqq\left\\{g\in G\ \middle|\
T^{\varphi(g)}=T^{\prime}\right\\},\quad
G_{(T,T^{\prime})}\coloneqq\left\\{g\in G\ \middle|\ \forall
i=1,\dots,k:t_{i}^{\varphi(g)}=t^{\prime}_{i}\right\\}.$

It is clear, that these stabilizers can be written as
$G_{T,T^{\prime}}=G_{T}\sigma$ and $G_{(T,T^{\prime})}=G_{(T)}\tau$ for
$\sigma\in G_{T,T^{\prime}}$ and $\tau\in G_{(T,T^{\prime})}$.

The objective of this section is to compute $\Iso_{G_{T,T^{\prime}}}\left(\str
x^{W(T)},\str y^{W(T^{\prime})}\right)$ where $W(T)$ and $W(T^{\prime})$ are
the windows returned by LABEL:proc:localcert for inputs $T$ and $T^{\prime}$
respectively. In other words, we are interested in the elements of $G$ whose
$\varphi$-images send $T$ to $T^{\prime}$ and which respect the input strings
$\str x$ and $\str y$ at least on the given windows. We obtain the result by
running LABEL:proc:localcert in parallel for both input strings. While
enlarging the windows $W(T)$ and $W(T^{\prime})$ we keep track of
$\Iso_{G_{T,T^{\prime}}}\left(\str x^{W},\str y^{W^{\prime}}\right)$ which we
will call $Q(W,W^{\prime})$.

In the beginning, both windows are empty. Thus
$Q(W,W^{\prime})=G_{T,T^{\prime}}$. The more the windows are enlarged the more
$Q(W,W^{\prime})$ shrinks. Again, the test sets must satisfy
$\max\left\\{8,2+\log_{2}\abs\Omega\right\\}<k\ll\log\abs\Omega$ where $k=\abs
T=\abs{T^{\prime}}$.

Comparing Local Certificates test sets $T,T^{\prime}\in\binom{\Gamma}{k}$,
group $G\leq\Sym(\Omega)$, epimorphism $G\to\Alt(\Gamma)$, strings $\str
x,\str y:\Omega\to\Sigma$ windows $W(T),W(T^{\prime})\subseteq\Omega$, the
group $\Iso_{G_{T,T^{\prime}}}\left(\str x^{W(T)},\str
y^{W(T^{\prime})}\right)$ localcert2

$W\leftarrow\emptyset,W^{\prime}\leftarrow\emptyset$

$A(W)\leftarrow G_{T}=\varphi^{-1}(\Alt(\Gamma)_{T}),A(W^{\prime})\leftarrow
G_{T^{\prime}}=\varphi^{-1}(\Alt(\Gamma)_{T^{\prime}})$

$Q(W,W^{\prime})\leftarrow G_{T,T^{\prime}}=A(W)\sigma$, for any $\sigma\in
G_{T,T^{\prime}}$

while $\restrict{\varphi(A(W))}{T}\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \Alt(T)$ and $\Aff(A(W),\varphi)\leavevmode\nobreak\
\not\subseteq\leavevmode\nobreak\ W$ and
$\restrict{\varphi(A(W^{\prime}))}{T^{\prime}}\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \Alt(T^{\prime})$ and
$\Aff(A(W^{\prime}),\varphi)\leavevmode\nobreak\
\not\subseteq\leavevmode\nobreak\ W^{\prime}$:

$W^{+}\leftarrow\Aff(A(W),\varphi)$,
$W^{\prime+}\leftarrow\Aff(A(W^{\prime}),\varphi)$

$N\leftarrow\ker\restrict{\varphi}{A(W)}=A(W)_{(T)}$

$A(W^{+})\leftarrow\emptyset,Q^{+}\leftarrow\emptyset$

fix $\pi_{0}\in Q(W,W^{\prime})$

compute a set of right coset representatives $S$ for $N$ in $A(W)$

for $\sigma\in S$:

$A(W^{+})\leftarrow A(W^{+})\cup\Iso_{N}^{W^{+}}\left(\str
x,\str{x}^{\sigma^{-1}}\right)\sigma$

$\pi\leftarrow\sigma\pi_{0}$

$Q^{+}\leftarrow Q^{+}\cup\Iso_{N}\left(\str x^{W^{+}},\left({\str
y}^{W^{\prime+}}\right)^{\pi^{-1}}\right)\pi$

end

$W\leftarrow W^{+},A(W)\leftarrow A(W^{+})$

complete recomputing $W^{\prime}$ and $A(W^{\prime})$ as in
LABEL:proc:localcert lines 5.1-5.1.

if $Q^{+}=\emptyset$: reject isomorphicity, exit

$Q(W,W^{\prime})\leftarrow Q^{+}$

end

return windows $W$ as $W(T)$, $W^{\prime}$ as $W(T^{\prime})$ and
$Q(W,W^{\prime})$

Recomputing $Q(W,W^{\prime})$ requires some attention. Following eq. 5.1, we
reuse the coset representatives for $N=\ker\restrict{\varphi}{A(W)}$ in $A(W)$
which together with the fixed element $\pi_{0}\in Q(W,W^{\prime})$ serve as
representatives for the cosets $N\sigma\pi_{0}$ of $N$ in
$A(W)\pi_{0}=Q(W,W^{\prime})$. For $W\subseteq W^{+},W^{\prime}\subseteq
W^{\prime+}$, obviously $Q(W^{+},W^{\prime+})\leq Q(W,W^{\prime})\leq
G_{T,T^{\prime}}$. Hence, abbreviating $\pi\coloneqq\sigma\pi_{0}$, we have

$\displaystyle Q(W^{+},W^{\prime+})$
$\displaystyle=\Iso_{G_{T,T^{\prime}}}\left(\str x^{W^{+}},\str
y^{W^{\prime+}}\right)=\Iso_{Q(W,W^{\prime})}\left(\str x^{W^{+}},\str
y^{W^{\prime+}}\right)=\bigcup_{\sigma}\Iso_{N\sigma\pi_{0}}\left(\str
x^{W^{+}},\str y^{W^{\prime+}}\right)$
$\displaystyle=\bigcup_{\pi}\Iso_{N}\left(\str x^{W^{+}},\left(\str
y^{W^{\prime+}}\right)^{\pi^{-1}}\right)\pi$ (5.2)

As in the previous case, all orbits of $N$ in $W^{+}$ are of size
$\leq\abs{W^{+}}/k\leq\abs\Omega/k$. We resume with Luks reduction on the
$\leq\abs\Omega$ orbits. As $\gindex{A(W)}{N}=k!/2$, we have to make
additional $\abs{\Omega}^{2}(k!/2)$ calls to the main routine for strings of
length $\leq\abs\Omega/k$.

Finding an element $\sigma$ in line 5.2 satisfying
$G_{T,T^{\prime}}=G_{T}\sigma$ is possible in polynomial time by Schreier-
Sims, cf. section 3.2, as any $\rho\in\Alt(\Gamma)$ mapping
$T^{\rho}=T^{\prime}$ has a non empty preimage $\varphi^{-1}(\\{\rho\\})$ from
which $\sigma$ can be chosen. Such a $\rho$ can be easily constructed by
enumerating the elements of $T$ and $T^{\prime}$.

Besides the treatment of $Q(W,W^{\prime})$ the recomputation of $A(W)$ and
$A(W^{\prime})$ in lines 5.2 and 5.2 are expensive. Summing up, we have
recurred to $3\abs{\Omega}^{2}(k!/2)$ subproblems of size
$\leq\abs{\Omega}/k$. The additive costs account for
$\abs{\Omega}^{O(\log\abs\Omega)}$ operations. This complies with our desired
bound as we will see in chapter 6.

From a computational point of view, sets are much harder to handle than
indexed lists. Hence, we are not only interested in
$\Iso_{G_{T,T^{\prime}}}\left(\str x^{W(T)},\str y^{W(T^{\prime})}\right)=Q$
but in $\Iso_{G_{(T,T^{\prime})}}\left(\str x^{W(T)},\str
y^{W(T^{\prime})}\right)$, i.e. the set of isomorphism taken from $G$ which
map the tuple $T=\\{t_{1},\dots,t_{k}\\}$ to
$T^{\prime}=\\{t^{\prime}_{1},\dots,t^{\prime}_{k}\\}$ in the right order.
After obtaining the former from LABEL:proc:localcert2, it is passed to a
modified version of Schreier-Sims which in virtue of $\varphi$ provides
generators for $Q_{i}=\left\\{\sigma\in Q\ \middle|\ \forall
l=1,\dots,i:t_{l}^{\varphi(\sigma)}=t^{\prime}_{l}\right\\}$ for $i\leq k-1$.
As $Q\leq G_{T,T^{\prime}}$, $\gindex{Q_{i}}{Q_{i+1}}\leq k$, which assures a
polynomial execution time. Finally,
$Q_{k-1}=\Iso_{G_{(T,T^{\prime})}}\left(\str x^{W(T)},\str
y^{W(T^{\prime})}\right)$. This justifies the following procedure.

[Comparing Local Certificates for Tuples] test sets
$T,T^{\prime}\in\Gamma^{k}$, group $G\leq\Sym(\Omega)$, epimorphism
$G\to\Alt(\Gamma)$, strings $\str x,\str y:\Omega\to\Sigma$
windows $W(T),W(T^{\prime})\subseteq\Omega$, the group
$\Iso_{G_{(T,T^{\prime})}}\left(\str x^{W(T)},\str y^{W(T^{\prime})}\right)$
reduction to $3\abs{\Omega}^{2}(k!/2)$ subproblems of size
$\leq\abs{\Omega}/k$, additive costs $\abs{\Omega}^{O(\log\abs\Omega)}$

###  5.3 Aggregation of certificates

In this section we will combine the tools provided in the two preceding
sections in order to reduce the problem of determining $\Iso_{G}(\str x,\str
y)$ to subproblems that can be solved by other algorithmic building blocks. We
are again equipped with an epimorphism $\varphi:G\to\Alt(\Gamma)$. Choose
$k\in\mathbb{N}$ such that
$\max\left\\{8,2+\log_{2}\abs\Omega\right\\}<k<\abs{\Gamma}/10$ and
$k\ll\log\abs\Omega$, for example $k\coloneqq\ceil{8+\log_{2}\abs\Omega}$.
Then $\abs\Omega/k\leq\abs\Omega/2$.

After computing and comparing local certificates we will have obtained one of
the following results:

Case 1

canonical colored $1/2$-partitions on $\Gamma$ for the two strings $\str x$
and $\str y$,

Case 2a

reduction to $\leq 3\abs\Omega$ many subproblems for strings of length
$\leq\abs\Omega/2$,

Case 2b

canonically embedded binary relational structures on $\Gamma$ with symmetry
defect $\geq 1/2$ for the two strings $\str x$ and $\str y$ and
$\leq\abs\Omega$ subproblems of length $\leq\abs\Omega/2$ at additional
multiplicative costs,

Case 3

canonically embedded $k$-ary relational structures on $\Gamma$ with symmetry
defect $>4/5$ for the two strings $\str x$ and $\str y$ and $\leq\abs\Omega$
subproblems subproblem of length $\leq\abs\Omega/2$.

We will leave the overall cost estimate to chapter 6. Ludi incipiant:

First we run LABEL:proc:localcert for both input strings $\str x$ and $\str y$
and all test sets $T\subseteq\Gamma$ of size $k$. For every such test set and
both of the strings we obtain either a certificate of fullness or a
certificate of non-fullness. Let $F(\str x)\leq\Aut_{G}(\str x)$ denote the
group generated by the certificates of fullness $K(T)$ associated to $\str x$,
$F(\str y)$ respectively. Let $S(\str x)\subseteq\Gamma$ denote the support of
$F(\str x)^{\varphi}$, i.e. the set of all elements of $\Gamma$ that are not
fixed by all elements of the image of $F(\str x)$ under $\varphi$. In total,
we thus make $2\binom{\abs{\Gamma}}{k}\leq 2\frac{\abs\Gamma^{k}}{k!}\leq
2\abs\Gamma^{k}\ll\abs\Omega^{O(\log\abs\Omega)}$ calls to
LABEL:proc:localcert resulting in
$\leq\abs\Gamma^{k}\abs\Omega^{2}\ll\abs\Omega^{O(\log\abs\Omega)}$ many
subproblems of length $\leq\abs\Omega/2$ and additive costs
$\abs\Omega^{O(\log\abs\Omega)}$.

From now on, we omit the reference to the string in our notation. Implicitly,
we work on both strings, distinguishing cases. If we arrive with the two
strings in different cases, we can reject isomorphicity. By the canonicity of
the assignment of the certificates, $F(\str x)$ and $S(\str x)$ are canonical.
We will write $F\coloneqq F(\str x)$ and $S\coloneqq S(\str x)$. In
particular, we can assume that $F(\str x)$ and $F(\str y)$ are conjugate
subgroups of $\Sym(\Omega)$. $S(\str x)$ and $S(\str y)$ are not necessary
equal as sets but of the same size.

The numbering of the cases follows [HBD17, §6.2] and [Bab18, §13.2]. For
checking the case’s preconditions, we compute the orbits of the action of
$\varphi(F)$ on $\Gamma$ in polynomial time in $\abs\Gamma\ll\abs\Omega$.

#### Case 1

$\abs S\geq\abs\Gamma/2$, but no orbit of $\varphi(F)$ is of length
$>\abs\Gamma/2$.

We want to compute canonical colored $1/2$-partitions on $\Gamma$ depending on
the orbit structure of $\varphi(F)$, cf. 20. We will obtain two such
partitions associated to $\str x$ and $\str y$ respectively since
$\varphi(F(\str x))$ and $\varphi(F(\str y))$ are not identical but only
conjugate as subgroups of $\Alt(\Gamma)$. Below the reference to the string
will be omitted from the notation.

As the orbit structure is canonical, we can color the elements of $\Gamma$
according to the lengths of their respective orbits in a canonical way. This
is surely possible in polynomial time. If no color class dominates, i.e. no
set of elements in $\Gamma$ with a certain color is of size $>\abs\Gamma/2$,
we have found a canonical colored $1/2$-partition. If contrarily such a big
color class exists, it must partition at least into two sets of the same size
$\geq 2$, as there would otherwise be an orbit of length $>\abs\Gamma/2$ or a
trivial orbit in contradiction to the assumption. Refining the color classes
according to this partition yields a canonical colored $1/2$-partition as
well.

#### Case 2

$\abs S\geq\abs\Gamma/2$ and there is an orbit $\Phi$ of $\varphi(F)$ in
$\Gamma$ satisfying $\abs\Phi>\abs\Gamma/2$.

Since there can only be one such orbit associated to each string, $\Phi$ is
again canonical. Note that this does not mean that the string’s dominating
orbits are equal as sets. Let $\Phi_{\str x}$ and $\Phi_{\str y}$ denote the
orbits of this kind associated to the strings $\str x$ and $\str y$
respectively. They must be of the same size, otherwise we have refuted
isomorphicity. We align the two orbits as we did in section 4.2. First, we
construct $\sigma\in\Alt(\Gamma)$ such that $\Phi_{\str x}^{\sigma}=\Phi_{\str
y}$ by enumerating the orbits’ elements. Now $\sigma$ can be lifted along the
epimorphism $\varphi$ using Schreier-Sims to a $\tau\in G$ satisfying
$\tau^{\varphi}=\sigma$. Replacing $\str y\leftarrow\str y^{\tau}$ finishes
the alignment. We can hence assume that $\Phi_{\str x}=\Phi_{\str y}$, which
we will call $\Phi$ again.

Reverting to section 3.2, the preconditions of the two subsequent subcases can
be tested in polynomial time.

##### Case 2a

$\Alt(\Phi)\leq\restrict{\varphi(F)}{\Phi}$.

In this case we have found a feature of large symmetry in both strings.
Recall, that we hold a surjection $\iota:\Omega\to\binom{\Gamma}{l}$. Invoking
section 3.5, we let the partition
$(\Gamma\setminus\Phi)\mathbin{\dot{\cup}}\Phi$ of $\Gamma$ induce a partition
$\Omega_{0}\mathbin{\dot{\cup}}\cdots\mathbin{\dot{\cup}}\Omega_{l}$ of
$\Omega$. It is guaranteed that $\Omega_{0}=\iota^{-1}\binom{\Phi}{l}$ and
hence $\abs{\Omega_{j}}\leq\abs\Omega/2$ for all $0<j\leq l$ by the
precondition of case 2.

Due to the orbit’s canonicity, any possible isomorphism from $\str x$ and
$\str y$ must leave $\Phi$ as a set invariant, i.e. a $\sigma\in G$ can only
satisfy $\str x=\str y^{\sigma}$ if $\Phi^{\varphi(\sigma)}=\Phi$. Therefore
we have reduced the problem of determining $\Iso_{G}(\str x,\str y)$ to the
problem of computing $\Iso_{H}(\str x,\str y)$ where
$H=\varphi^{-1}\left(\Alt(\Gamma)_{\Phi}\right)$. Instead of brutally
computing a description for $H$, we scrutinize its structure and perform a
more sophisticated reduction. Let
$K=\varphi^{-1}\left(\Alt(\Gamma)_{(\Phi)}\right)$ and
$\sigma_{1},\sigma_{2}\in G$ be preimages under $\varphi$ of two generators of
$\Alt(\Phi)\leq\restrict{\Alt(\Gamma)}{\Phi}$, cf. eq. 3.2. Recalling section
3.2, we compute $K$ as a preimage of a pointwise stabilizer in polynomial
time. As $\Alt(\Phi)\leq\restrict{\varphi(F)}{\Phi}\leq\restrict{\Aut_{G}(\str
x)}{\Phi}$, the two sets $\Aut_{K\sigma_{i}}(\str x)$ for $i=1,2$ are non-
empty.

By the correspondence of $\varphi$ and $\iota$, $K$ acts on $\Omega$ but fixes
$\Omega_{0}$. The orbits of this action refine the partition of $\Omega$ into
the $\Omega_{j}$ because the number of elements from $\Phi$ in an element of
$\binom{\Gamma}{l}$ is invariant under the action of $K$. Thus all orbits of
$K$ are at most of length $\abs\Omega/2$. Consequently, we can compute the two
$\Aut_{K\sigma_{i}}(\str x)=\Iso_{K}\left(\str x,\str
x^{\sigma_{i}^{-1}}\right)\sigma_{i}$ by calling the main procedure for
strings of length $\leq\abs\Omega/2$ and total length $\leq 2\abs\Omega$. The
number of calls is $\leq 2l\leq 2\abs\Omega$ and the costs for the reduction
are negligible. As $\Alt(\Gamma)_{\Phi}/\Alt(\Gamma)_{(\Phi)}\cong\Alt(\Phi)$,
the two $\Aut_{K\sigma_{i}}(\str x)$ generate $\Aut_{H}(\str x)$. By the same
argument,

$\Iso_{H}(\str x,\str y)=\Aut_{H}(\str x)\Iso_{K}(\str x,\str y),$

iff $\Iso_{K}(\str x,\str y)$ is non-empty. The latter is the case if and only
if $\Iso_{H}(\str x,\str y)$ is non-empty because by assumption
$\Alt(\Phi)\leq\restrict{\varphi(F)}{\Phi}$. As above, the shortness of $K$’s
orbits allows us to compute $\Iso_{K}(\str x,\str y)$ by calling the main
procedure $\leq l\leq\abs\Omega$ times on strings of length $\leq\abs\Omega/2$
and total length $\leq\abs\Omega$. This completes the reduction.

##### Case 2b

$\Alt(\Phi)\not\leq\restrict{\varphi(F)}{\Phi}$.

Let $d\geq 1$ denote the maximal integer such that