# Using Schur Rings to Produce GRRs for Dihedral Groups.

Jonathan Ebejer, Josef Lauri
University of Malta

###### Abstract

In this paper we shall be looking at several results relating Schur rings to
sufficient conditions for a graph to be a graphical regular representation
(GRR) of finite group, and then applying these specifically in the case of
certain subfamilies of dihedral groups. Numerical methods are given for
constructing trivalent GRRs for these dihedral groups very quickly.

##  1 Foundations

###  1.1 Introduction

######  Definition 1.1.1 (Graphical Regular Representations).

Let $\Gamma$ be a finite group and let $G$ be a graph. If
$\mbox{Aut}(G)\equiv\Gamma$ acts regularly on $V(G)$, then we say that $G$ is
a graphical regular representation (GRR) of $\Gamma$.

The question asking which finite groups have at least one GRR has been
completely solved [13, 14, 15, 16, 17, 18, 23, 24]. Specifically:

  1. 1.

The only abelian groups which have a GRR are $\mathbb{Z}^{n}_{2}$ for $n\geq
5$.

  2. 2.

Except for generalised dicyclic groups and a finite number of known groups,
all non-abelian groups have a GRR.

However, it remains a challenge to discern whether a group known to have GRRs
has GRRs with specific properties, such as being trivalent. It is well-known,
by means of Frucht’s Theorem [4], that every group is isomorphic to the
automorphism group of some trivalent graph but it is not guaranteed that this
graph is a GRR. Furthermore, it is not known how one can easily construct such
GRRs when they do exist. In Section 2 we will be using the foundations laid
out in this section to produce infinite families of trivalent GRRs for certain
dihedral groups. Coxeter, Frucht, and Powers had given a thorough treatment of
trivalent GRRs in their book _Zero-Symmetric Graphs: Trivalent Graphical
Representations of Groups_ [7] which shows how interesting such GRRs can be.

######  Definition 1.1.2 (Cayley graphs).

The Cayley graph of a group $\Gamma$ is the graph, denoted by
$\mbox{Cay}(\Gamma,S)$, whose vertex-set is $\Gamma$ and two vertices $u$ and
$v$ are adjacent if $v=us$ where $s\in S$ and $S$ is a subset of $\Gamma$ such
that $1\not\in S$, $S$ generates $\Gamma$, and $S^{-1}=S$. We call the set $S$
the connecting set of the Cayley graph.

In dealing with Schur rings we might encounter Cayley graphs where the
condition $S^{-1}=S$ is not satisfied. We refer to such graphs as Cayley
digraphs.

It is an easy and well-known corollary of Sabidussi’s Theorem [25] that if a
graph $G$ is a GRR of a group $\Gamma$, then it isomorphic to a Cayley graph
$\mbox{Cay}(\Gamma,S)$ of $\Gamma$. Therefore, if $G$ is cubic then the
connecting set must either consist of three elements all of order 2 or else it
must consist of one element $a$ and its inverse $a^{-1}\not=a$ and one other
element $b$ of order 2.

###  1.2 Schur rings

We now present an introduction to Schur rings which is just sufficient for our
purposes.

######  Definition 1.2.1 (Group Rings).

Let $\Gamma$ be a finite group. Then the group ring $\mathbb{Z}[\Gamma]$
consists of all formal linear combinations

$\sum_{\gamma\in\Gamma}z_{\gamma}\cdot\gamma$

Where each $z_{\gamma}$ is in $\mathbb{Z}$. Addition and multiplication in
$\mathbb{Z}[\Gamma]$ is carried out in the natural way. If
$B=\\{b_{1},b_{2},\ldots,b_{p}\\}\subseteq\Gamma$, then the element

$b_{1}+b_{2}+\ldots+b_{p}$

of $\mathbb{Z}[\Gamma]$ is denoted by $\overline{B}$ and it is said to be a
simple quantity of $\mathbb{Z}[\Gamma]$.

######  Definition 1.2.2 (Schur Rings).

A subring $\mathcal{S}$ of the group ring $\mathbb{Z}[\Gamma]$ is called a
Schur ring or an $\mathcal{S}$-ring over $\Gamma$, of rank $r$, if the
following conditions hold:

  * •

$\mathcal{S}$ is closed under addition and multiplication including
multiplication by elements of $\mathbb{Z}$ from the left (i.e. $\mathcal{S}$
is a $\mathbb{Z}[\Gamma]$-module).

  * •

Simple quantities $\overline{B}_{0},\overline{B}_{1},...,\overline{B}_{r-1}$
exist in $\mathcal{S}$ such that every element ${C}\in\mathcal{S}$ has a
unique representation:

${C}=\sum_{i=0}^{r-1}\alpha_{i}\overline{B}_{i}$

where the $\alpha_{i}$ are integers.

  * •

$\overline{B}_{0}=\overline{\\{1\\}}$.

  * •

$\displaystyle\sum_{i=0}^{r-1}\overline{B}_{i}=\overline{\Gamma}$, that is,
$\\{B_{0},B_{1},...,B_{r-1}\\}$ is a partition of $\Gamma$.

  * •

For every $i\in\\{0,1,2,...,r-1\\}$ there exists a $j\in\\{0,1,2,...,r-1\\}$
such that $\overline{B}_{j}=\overline{B}^{-1}_{i}(=\overline{\\{b^{-1}:b\in
B_{i}\\})}$.

We call the set of simple quantities
$\overline{B}_{0},\overline{B}_{1},\ldots,\overline{B}_{r-1}$the basis of the
Schur ring and we denote it by ${\mathcal{B}}[{\mathcal{S}}]$. Each simple
quantity $\overline{B}_{i}$ of the basis is referred to as a basic element of
the Schur ring. Sometimes we need to refer to the set $B_{i}$ which we call a
basic set. If $\gamma\in\Gamma$ and $\overline{\\{\gamma\\}}$ is a basic
element of $\mathcal{S}$, then we say the $\gamma$ is isolated or a singleton
in ${\mathcal{B}}[{\mathcal{S}}]$. If the basis of a Schur ring is completely
made up of singletons then we say that the Schur ring is trivial.

We say a Schur ring is larger than another if its basic sets form a partition
which is finer than the partition formed by the other’s basic sets. The
“largest” Schur ring of a group $\Gamma$ is therefore the Schur ring whose
basic sets form the finest possible partition of $\Gamma$, that is, the basic
sets are all the singleton elements of $\Gamma$. Similarly, we say a Schur
ring is smaller than another if its basic sets form a partition which is
coarser than the partition formed by the other’s basic sets. The “smallest”
Schur ring is therefore the one which gives the coarsest partition, with basic
sets $\\{1\\}$ and $\Gamma-\\{1\\}$.

The example below deals with a special kind of Schur ring known as a
cyclotomic Schur ring [8, 27].

######  Example 1.2.1.

Let $\Delta$ be a group of automorphisms of the group $\Gamma$. Then the
orbits of $\Gamma$ under the action of $\Delta$ form the basic sets of a Schur
ring over $\Gamma$.

In particular, the conjugacy classes of $\Gamma$ form the basic sets of a
Schur ring over $\Gamma$. The basic elements in this case would here be the
well-known “class sums” which are very important in linear representations of
groups.

Because of closure under multiplication, the product of two linear
combinations of $\overline{B}_{0},\overline{B}_{1},...,\overline{B}_{r-1}$
must also be a linear combination of these simple quantities. Therefore we can
make the following definition:

######  Definition 1.2.3 (Structure Constants).

Let $\overline{B}_{i}$ and $\overline{B}_{j}$ be two basis elements of an
r-rank Schur ring $\mathcal{S}$. For all values $i,j,k\in[r]$ there exist non-
negative integers $\beta_{i,j}^{k}$ called structure constants, such that

$\overline{B}_{i}\cdot\overline{B}_{j}=\sum_{k=1}^{r}\beta_{i,j}^{k}\overline{B}_{k}$

We shall soon see that the structure constants have a very nice graph
theoretic interpretation.

######  Example 1.2.2.

Let $\Gamma$ be the cyclic group $\langle\gamma:\gamma^{8}=1\rangle$. The
following simple quantities are the basic sets of a Schur ring of $\Gamma$:

$\\{\\{1\\},\\{\gamma^{1},\gamma^{5}\\},\\{\gamma^{3},\gamma^{7}\\},\\{\gamma^{2},\gamma^{6}\\},\\{\gamma^{4}\\}\\}.$

One can verify that, if we let
$B_{0}=\\{1\\},B_{1}=\\{\gamma^{1},\gamma^{5}\\},B_{2}=\\{\gamma^{3},\gamma^{7}\\},B_{3}=\\{\gamma^{2},\gamma^{6}\\}$,
and $B_{4}=\\{\gamma^{4}\\}$, then,
$\overline{B_{2}}\cdot\overline{B_{4}}=\overline{B_{2}}$, therefore
$\beta_{2,4}^{2}=1$ while all the other $\beta^{k}_{2,4}=0$.

###  1.3 Graph theoretic interpretation

######  Definition 1.3.1 (Basic Cayley Graphs).

Let $\mathcal{S}$ be a Schur ring of a group $\Gamma$. We can construct a
Cayley (di)graph $\mbox{Cay}(\Gamma,B_{i})$ for each of the basic sets $B_{i}$
of $\mathcal{S}$. These are called the basic Cayley graphs associated with the
Schur ring.

The basic Cayley graphs associated with the Schur ring in the previous example
are as shown in Figure 1.

Figure 1: The basic Cayley graphs associated with the Schur ring in Example
1.2.2

We can now give an interpretation to the structure constants
$\beta^{k}_{i,j}$: pick _any_ edge (or arc in the case of a Cayley digraph)
$ab$ in $\mbox{Cay}(G,B_{k})$ and count how many walks there are from $a$ to
$b$ by first passing through an edge/arc in $\mbox{Cay}(G,B_{i})$ followed by
an edge/arc in $\mbox{Cay}(G,B_{j})$. This is the value of $\beta^{k}_{i,j}$.

One can verify here that $\beta^{1}_{2,3}=2$ and $\beta^{4}_{2,1}=2$, for
example.

###  1.4 The Colour Graph

Basic Cayley graphs such as the ones in Figure 1 can be superimposed on the
vertex-set consisting of the elements of $\Gamma$ with each one having its
edges/arcs coloured a different colour. This gives a colouring of the arc-set
of the complete graph where the convention is to represent two arcs
$(u,v),(v,u)$ which happen to have the same colour represented as an edge of
that colour. Figure 2 shows the previous set of basic Cayley graphs without
the loops.

Figure 2: The colour graph for the Schur ring in Example 1.2.2

As we did above, we can verify here from the colour graph that
$\beta^{red}_{blue,green}=2=\beta^{black}_{blue,red}$, for example.

The adjacency matrices of the basic Cayley (di)graphs form what is called a
coherent configuration.

###  1.5 Automorphism groups of Schur rings

######  Definition 1.5.1 (Automorphisms of Schur Rings).

The automorphism group of a Schur ring is defined to be the intersection of
all automorphism groups of the basic Cayley graphs of the Schur ring. For any
Schur ring $\mathcal{S}$ we will denote its automorphism group as
$Aut(\mathcal{S})$.

The smallest (coarsest) Schur ring has the largest automorphism group, that
is, the symmetric group $S_{n}$, where $n$ is the order of the group. The
largest Schur ring has the smallest automorphism group, that is, the regular
action of the group on itself.

Let $C$ be a subset of the group $\Gamma$. Then $\langle\langle
C\rangle\rangle$ is the smallest (coarsest) Schur ring of $\Gamma$ containing
$\overline{C}$.

Theorem 1.5.1[22] and Theorem 1.5.2 [26] will be very important going forward.

######  Theorem 1.5.1.

$\mbox{Aut}(\mbox{Cay}(\Gamma,C))=\mbox{Aut}(\langle\langle C\rangle\rangle)$.

######  Theorem 1.5.2.

If $\langle\langle C\rangle\rangle$ is trivial then $Cay(\Gamma,C)$ is a GRR
of $\Gamma$.

###  1.6 Combining Results

Our recipe for finding GRRs for a group $\Gamma$ is simple. First, find $C$
such that $\langle\langle C\rangle\rangle$ is trivial. Theorem 1.5.2 then
gives us that, since $\langle\langle C\rangle\rangle$ is trivial,
$\mbox{Aut}(\mbox{Cay}(\Gamma,C))=\Gamma$ and so $\mbox{Cay}(\Gamma,C)$ is a
GRR of $\Gamma$.

Our work in Section 2 combines these two steps into one by identifying
properties of a connecting set of a dihedral group which imply that the Cayley
graph of that set must be a GRR. By selecting a connecting set consisting of
three elements of order 2, we will also be producing trivalent graphs. One
last result about Schur rings will be our main computational tool going
forward. A proof is given in [20].

######  Theorem 1.6.1 (Schur-Wielandt Principle).

Let $r=\sum z_{\gamma}\gamma$ be an element of a Schur ring $\mathcal{S}$ of a
group $\Gamma$. Then, for any integer $k$, the sum $\sum_{z_{\gamma}=k}\gamma$
is also in $\mathcal{S}$.

So, this result is saying, for example, that if $a+2b+c+3d+2f$ is in
$\mathcal{S}$, then so are $a+c$, $b+f$, and $d$.

We finish off this section with a concrete example of how we use these results
to show that a particular Cayley graph is a GRR using some simple GAP code.
[GAP] used to carry out the algebraic calculations.

######  Example 1.6.1.

Let $D_{7}$ be the dihedral group

$\langle a,b:a^{2}=b^{7}=abab=1\rangle.$

We show that $\mbox{Cay}(D_{7},C)$ where $C=\\{a,ab,ab^{3},b,b^{6}\\}$ is a
GRR of $G$.

    gap> d7:=DihedralGroup(14);;
    gap> Zd7:=GroupRing(Integers, d7);;
    gap> a:=Zd7.1;
    (1)*f1
    gap> b:=Zd7.2;
    (1)*f2

    gap> a^2;
    (1)*<identity> of ...
    gap> b^7;
    (1)*<identity> of ...

    gap> (a+a*b+a*b^3+b+b^6)^2;
    (5)*<identity> of ...+
    (4)*f1*f2^2+
    (2)*f1+(2)*f1*f2+(2)*f2^2+(2)*f1*f2^4+(2)*f2^5+(2)*f1*f2^6+
    (1)*f2^3++(1)*f2+(1)*f2^4+(1)*f2^6+
    ΨΨ

By computing $\overline{C}^{2}$ in $\mathbb{Z}[\Gamma]$ and using the Schur-
Wielandt Principle, we obtain that $x=ab^{2}$ and
$y=a+ab+b^{2}+ab^{4}+b^{5}+ab^{6}$ are in $\langle\langle C\rangle\rangle$.

Therefore, $xy=a+b^{2}+b^{4}+ab^{4}+b^{5}+b^{6}$ is in $\langle\langle
C\rangle\rangle$.

But $(xy)^{-1}=a+b^{5}+b^{3}+ab^{4}+b^{2}+b$. and basic elements are disjoint,
therefore either $b$ or $b+b^{3}$ is a basic element of $\langle\langle
C\rangle\rangle$. But by squaring the latter, we see that $b^{4}$ is a basic
element of the Schur ring, hence so is $b$. Multiplying $x$ by $b$ repeatedly
it follows that so is $a$. Therefore $\mathcal{S}$ is the finest Schur ring on
$D_{7}$ with all singleton sets as basic sets.

Therefore $\mbox{Aut}(\mbox{Cay}(D_{7},C))=\mbox{Aut}(\langle\langle
C\rangle\rangle)=D_{7}$.

We finish this section with the following simple observation.

Observation 1. Let $\overline{A}$ be an element of the Schur ring
$\mathcal{S}$. Then some partition of $A$ (which could be $A$ itself) gives a
set of basic elements in $\mathcal{B}[\mathcal{S}]$

##  2 Constructing cubic GRRs for dihedral groups

At its core, our work in Section 2 is conceptually identical to the final
example in the previous section, but rather than using specific values for the
powers of group elements, we generalise the example by using parametric
variables.

This will be our main result:

######  Theorem 2.1.

Let $n$ be an odd integer greater than 5 and let $r$, $s$, and $t$ be integers
less than $n$ such that the difference of any two of them is relatively prime
to $n$. If $3r-2s=t\bmod n$, then
$\mbox{Cay}(D_{n},\\{ab^{r},ab^{s},ab^{t}\\})$ is a GRR of $D_{n}$.

Which gives us the tidy corollary:

######  Corollary 2.1.

Let $n$ be an odd integer with its smallest prime factor being $p$ greater
than 5 and let $r$, $s$, and $t$ be distinct integers less than $p$. If
$3r-2s=t\bmod n$ then $\mbox{Cay}(D_{n},\\{ab^{r},ab^{s},ab^{t}\\})$ is a GRR
of $D_{n}$.

This will allow us to easily make trivalent GRRs for several dihedral groups
just by selecting appropriate values for $r$, $s$ and $t$. It will be
especially useful for those dihedral groups of order equal to twice a prime
greater than 5 (dihedral groups $D_{p}$), where all we would need would be
$r$, $s$, and $t$ such that $3r-2s=t\bmod p$.

To prove Theorem 2.1 however, we will need the help of the following two
lemmas:

######  Lemma 2.1.

Let $\gamma$ be an element of $\Gamma$ such that $\gamma$ has odd order $n$
and let $r$ and $t$ be two integers such that $r-t$ is relatively prime to
$n$. If $\gamma^{r}+\gamma^{t}$ is an element of some
$\mathcal{B}[\mathcal{S}_{\Gamma}]$ then $\gamma^{s}+\gamma^{-s}$ is also an
element of that same $\mathcal{B}[\mathcal{S}_{\Gamma}]$ for all integers $s$
relatively prime to $n$.

###### Proof.

First we observe that since $\mathcal{S}_{\Gamma}$ is closed then
$(\gamma^{r}+\gamma^{t})^{n}$ is in $\mathcal{S}_{\Gamma}$ whenever
$(\gamma^{r}+\gamma^{t})$ is in $\mathcal{S}_{\Gamma}$. We can use binomial
expansion to get:

$(\gamma^{r}+\gamma^{t})^{n}=\displaystyle\sum_{i=0}^{n}[\binom{n}{i}\gamma^{ri}\gamma^{t(n-i)}]$
which can be re-written as
$\displaystyle\sum_{i=0}^{n}[\binom{n}{i}\gamma^{(r-t)i)}]\gamma^{tn}$.
However, $\gamma$ is of order $n$ and so $\gamma^{tn}\equiv 1$. Therefore, the
sum can once more be rewritten as
$\displaystyle\sum_{i=0}^{n}[\binom{n}{i}\gamma^{(r-t)i)}]$.

Since $r-t$ is relatively prime to the order of $\gamma$ then the summation
$\displaystyle\sum_{i=0}^{n}[\binom{n}{i}\gamma^{(r-t)i)}]$ must include
exactly $n$ distinct terms. In other words every power of $\gamma$ appears in
that sum once and only once. Therefore, the coefficient of every
$\gamma^{(r-t)i}$ is exactly $\binom{n}{i}$. Moreover, we observe that
$\binom{n}{i}=\binom{n}{n-i}$ and so we can re-write this summation as
$\displaystyle\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}[\binom{n}{i}(\gamma^{(r-t)i}+\gamma^{(t-r)i})]$.
We use the floor function here as $n$ may be odd.

This means that for every $i\in[0,\frac{n}{2}]$ either $\gamma^{(r-t)i}$
occurs as a singleton in $\mathcal{B}[\mathcal{S}_{\Gamma}]$ or
$\gamma^{(r-t)i}+\gamma^{(t-r)i}$ occurs in
$\mathcal{B}[\mathcal{S}_{\Gamma}]$ due to the Schur-Wielandt principle.

However, in the cases where $i$ is relatively prime to $n$, $(r-t)i$ would
also be relatively prime to $n$, and so $\gamma^{(r-t)i}$ can generate every
power of $\gamma$. This would mean that should $\gamma^{(r-t)i}$ be a
singleton element of the basis, then every power of $\gamma$ would be a
singleton element of the basis also. However, $\gamma^{r}+\gamma^{t}$ is an
element of $\mathcal{B}[\mathcal{S}_{\Gamma}]$, and so this would imply a
contradiction. Therefore for every $i\in[0,\frac{n}{2}]$ which is relatively
prime to $n$, we have
$\gamma^{(r-t)i}+\gamma^{(t-r)i}\in\mathcal{B}[\mathcal{S}_{\Gamma}]$.

Let us recapitulate that at this point we have shown that if $n$ is the order
of some $\gamma\in\Gamma$, $r$ and $t$ are two integers such that $(r-t)$ are
relatively prime to $n$ and $(\gamma^{r}+\gamma^{t})$ is in
$\mathcal{B}[\mathcal{S}_{\Gamma}]$ then
$\displaystyle\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}[\binom{n}{i}(\gamma^{(r-t)i}+\gamma^{(t-r)i})]$
is in $\mathcal{S}_{\Gamma}$ and that those pairs of summands of the form
$\gamma^{(r-t)i}+\gamma^{(t-r)i}$ appear as a basis element in
$\mathcal{B}[\mathcal{S}_{\Gamma}]$ when $i$ is relatively prime to $n$. All
that is left to show is that every number less than $n$ which is also
relatively prime to it appears in the expression $\displaystyle\sum_{i=0;\
i\nmid
n}^{\lfloor\frac{n}{2}\rfloor}[\binom{n}{i}(\gamma^{(r-t)i}+\gamma^{(t-r)i})]$
as a power of $\gamma$ (or, equivalently, a value of $(r-t)i$) and this will
complete the proof.

We re-write $\displaystyle\sum_{i=0\ i\nmid
n}^{\lfloor\frac{n}{2}\rfloor}[\binom{n}{i}(\gamma^{(r-t)i}+\gamma^{(t-r)i})]$
as $\displaystyle\sum_{j\in S}[\binom{n}{j}\gamma^{j}]$ where $S$ is the set
$\\{(r-t)i$ mod $n:i\in[n];\ i\nmid n\\}$.

However, we now note that the set $S$ is in fact equivalent to the set of
integers less than $n$ which also divide $n$. This is because the modulo
multiplication of $[n]$ by any number relatively prime to $n$ can be
represented as a permutation of a set unto itself, which is a bijection.
Moreover the product of two numbers both relatively prime to $n$ is again
relatively prime to $n$, which means the subset of $[n]$ which consists only
of integers relatively prime to $n$ is fixed under such a bijection.

Therefore:

$\displaystyle\sum_{j\in
S}[\binom{n}{j}\gamma^{j}]\equiv\displaystyle\sum_{j\in[n];\ j\nmid
n}[\binom{n}{i}\gamma^{j}]$

Obviously every number less than $n$ which is less relatively prime to it
appears as a power of $\gamma$ on the right hand side above, meaning that
those powers of $\gamma$ also appear on the left hand side above.

This means that every $\gamma^{(r-t)i}$ such that $(r-t)i$ is relatively prime
to $n$ appears in the summation
$\displaystyle\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}[\binom{n}{i}(\gamma^{(r-t)i}+\gamma^{(t-r)i})]$
and as we stated above, this completes the proof.

∎

######  Lemma 2.2.

Let $n$ be an odd integer and let $a$ and $b$ be the generators of the group
$D_{n}$ with orders 2 and $n$ respectively. Also let $r$, $s$ and $t$ be
unique integers less than or equal to $n$. The Schur ring $\langle\langle
ab^{r}+ab^{s}+ab^{t}\rangle\rangle$ must be trivial if the following are true:

  1. 1.

$ab^{r}+ab^{s}+ab^{t}\not\in\mathcal{B}[\langle\langle
ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$

  2. 2.

The absolute value of the difference between any two of $r$, $s$ and $t$ is
relatively prime to $n$.

  3. 3.

The sum of any two of $r$, $s$ and $t$ is not equal to twice the third
variable taken modulo $n$.

###### Proof.

We know from (1) that $ab^{r}+ab^{s}+ab^{t}\not\in\mathcal{B}[\langle\langle
ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$. But $ab^{r}+ab^{s}+ab^{t}$ is in
$\mathcal{B}[\langle\langle ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$. This
therefore leaves only two possibilities:

  * •

$ab^{r},ab^{s},ab^{t}$ are all isolated in $\mathcal{B}[\langle\langle
ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$, or,

  * •

Without loss of generality, $ab^{r}+ab^{t}$ is in $\mathcal{B}[\langle\langle
ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$ while $ab^{s}$ is isolated.

The first possibility implies that $\langle\langle
ab^{r}+ab^{s}+ab^{t}\rangle\rangle$ is trivial and so if this is true, we are
done. Let us turn our attention to the second possibility.

This gives us that $(ab^{r}+ab^{t})ab^{s}$ is in $\langle\langle
ab^{r}+ab^{s}+ab^{t}\rangle\rangle$. By expanding the brackets we get that
$b^{s-r}+b^{s-t}$ is in $\langle\langle ab^{r}+ab^{s}+ab^{t}\rangle\rangle$.
If $b^{s-r}$ and $b^{s-t}$ occur as singletons in the basis then it would
imply that the whole Schur ring is trivial since $ab^{s}$ is already known to
be in the basis and $\\{b^{s-r},b^{s-t},ab^{s}\\}$ generates the whole group
$D_{n}$. Let us assume then that $b^{s-r}+b^{s-t}$ is in
$\mathcal{B}[\langle\langle ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$, and mark
this assumption as _Asm 1_.

From the second part of our sufficient condition we also know that $t-r$ and
$r-s$ are both relatively prime to $n$. Now $b^{s-r}+b^{s-t}$ is in
$\mathcal{B}[\langle\langle ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$ and the
difference between the two powers is $t-r$ which we know is relatively prime
to $n$. Lemma 2.1 therefore gives us that $b^{r-s}+b^{s-r}$ must also be in
$\mathcal{B}[\langle\langle ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$ since $r-s$
is also relatively prime to $n$. Both the elements $b^{s-r}+b^{s-t}$ and
$b^{r-s}+b^{s-r}$ have $b^{s-r}$ within them, however, and under the
assumption _Asm 1_ these should be basis elements. This is only possible if
$b^{s-t}\equiv b^{r-s}$ and that implies that $r+t\equiv 2s$ mod $n$, which
contradicts the third part of our sufficient condition.

Hence it must be the case that our assumption _Asm 1_ is false and so
$\langle\langle ab^{r}+ab^{s}+ab^{t}\rangle\rangle$ must be trivial. ∎

We can now focus on proving Theorem 2.1:

###### Proof.

We will prove Theorem 2.1 by showing that $ab^{r}+ab^{s}+ab^{t}$ cannot be an
element of $\mathcal{B}[\langle\langle ab^{r}+ab^{s}+ab^{t}\rangle\rangle]$
and then use Lemma 2.2 to meet the sufficient conditions of Theorem 1.5.2 and
so bring about the result.

We substitute $t$ for $3r-2s$ at this point for simplicity’s sake. We will
begin by assuming that $ab^{r}+ab^{s}+ab^{3r-2s}$ is in
$\mathcal{B}[\langle\langle ab^{r}+ab^{s}+ab^{3r-2s}\rangle\rangle]$ and then
show how this must imply a contradiction. We label this assumption as _(Asm
2)_ for further reference.

So let us begin by considering the following statement, which we label as
_(i)_ for further reference:

$(ab^{r}+ab^{s}+ab^{3r-2s})^{2}=3(1)+b^{r-s}+b^{2(r-s)}+b^{3(r-s)}+b^{-(r-s)}+b^{-2(r-s)}+b^{-3(r-s)}$

Assuming that _(Asm 2)_ is true then by Observation 1 it must be possible to
express _(i)_ as the sum of elements of $\mathcal{B}[\langle\langle
ab^{r}+ab^{s}+ab^{3r-2s}\rangle\rangle]$. However, we shall show that doing so
implies a contradiction which means that _(Asm 2)_ must be false.

We begin by noting that the group elements on the right hand side of _(i)_
must either be isolated in the basis of the Schur ring or be grouped with
other elements also on the right hand side of _(i)_.

For the sake of brevity let us denote the sum of the elements on the right
hand side as $B_{6}$. We note now that $(B_{6})^{2}$ is equal to

$\displaystyle 6(1)+2B_{6}+b^{2(r-s)}+b^{-2(r-s)}+b^{6(r-s)}+b^{-6(r-s)}+$
$\displaystyle
2(b^{r-s}+b^{s-r}+b^{5(r-s)}+b^{-5(r-s)})+3(b^{4(r-s)}+b^{-4(r-s)}).$

We notice that the total coefficient of $b^{r-s}$ on the right hand side is 4
(remember it occurs in $B_{6}$), and so, by the Schur Wielandt principle the
only elements which $b^{r-s}$ can be grouped with in the Schur ring’s basis
must also have a coefficient of 4 in the expansion of $B_{6}^{2}$. However,
with the exception of $b^{s-r}$, achieving this requires that $\pm 4(r-s),\pm
5(r-s)$ or $\pm 6(r-s)$ is equal to some element in $B_{6}$. This implies
$x(r-s)$ = $y(r-s)$ for $x=\pm 1,\pm 2$ or $\pm 3$ and $y=\pm 4,\pm 5$ or $\pm
6$. Regardless of the values of $x$ and $y$ we get $r-s=0$ implies $r=s$ since
we are working in modulo $n$ where $n$ is definitely larger than 6. Therefore
$b^{r-s}$ can only possibly be grouped with $b^{s-r}$ or be an isolated
element in the basis.

Let us first consider the possibility that $b^{r-s}$ is an isolated element.
If so, then $b^{3(s-r)}$ must also be an isolated element in the basis. Since
our assumption is that $ab^{r}+ab^{s}+ab^{3r-2s}$ is in
$\mathcal{B}[\langle\langle ab^{r}+ab^{s}+ab^{3r-2s}\rangle\rangle]$ we can
consider the product of $ab^{r}+ab^{s}+ab^{3r-2s}$ and $b^{3(r-s)}$, which
must be in $\langle\langle ab^{r}+ab^{s}+ab^{3r-2s}\rangle\rangle$.

$(ab^{r}+ab^{s}+ab^{3r-2s})b^{3(r-s)}\equiv ab^{4r-3s}+ab^{3r-2s}+ab^{6r-5s}.$

Note how the term $ab^{3r-2s}$ appears on the right hand side above. Since we
are assuming that $ab^{r}+ab^{s}+ab^{3r-2s}$ is in $\mathcal{B}[\langle\langle
ab^{r}+ab^{s}+ab^{3r-2s}\rangle\rangle]$, $ab^{r}$ and $ab^{s}$ must appear
too. There are only two ways this is possible:

  * •

$4r-3s=s$ and $6r-5s=r$, or,

  * •

$4r-3s=r$ and $6r-5s=s$.

All the equations above, however, imply that $r=s$ which is a contradiction.
And so $b^{r-s}$ cannot be an isolated element in the basis without
contradicting _(Asm 2)_. Therefore, the only way to avoid contradicting _(Asm
2)_ is for $b^{r-s}+b^{s-r}$ to be an element in the basis.

This gives us that $(ab^{r}+ab^{s}+ab^{3r-2s})(b^{r-s}+b^{s-r})$ is in the
Schur ring. This expression expands to
$2ab^{2r-s}+ab^{2s-r}+ab^{4r-3s}+ab^{s}+ab^{r}$. Notably the terms
$ab^{s},ab^{r}$ appear here and due to _(Asm 2)_ this means that $ab^{3r-2s}$
must appear also. There are three ways this could happen:

  * •

$2r-s=3r-2s$ gives us $r=s$, or,

  * •

$4r-3s=3r-2s$ gives us $r=s$, or,

  * •

$2s-r=3r-2s$ gives us $r=s$.

But all these ways imply $r=s$ which is again a contradiction. This rules out
the possibility that $b^{r-s}+b^{s-r}$ is an element in the basis.

Therefore, _(Asm 2)_ must be false and $ab^{r}+ab^{s}+ab^{3r-2s}$ is not in
$\mathcal{B}[\langle\langle ab^{r}+ab^{s}+ab^{3r-2s}\rangle\rangle]$ for if it
were, then it would be a basis element which cannot be expressed as a linear
sum of basis elements when squared, which contradicts the definition of a
Schur ring. Lemma 2.2 gives us that this implies that $\langle\langle
ab^{r}+ab^{s}+ab^{t}\rangle\rangle$ is trivial and so
$\mbox{Aut}(\langle\langle ab^{r}+ab^{s}+ab^{t}\rangle\rangle)\equiv D_{n}$
meaning that $\mbox{Cay}(D_{n},\\{ab^{r},ab^{s},ab^{t}\\})$ is a GRR of
$D_{n}$ by Theorem 1.5.2.

∎

Corollary 2.1 follows immediately by observing that $r$, $s$ and $t$, being
less than $p$, immediately implies that both they and their differences are
relatively prime to $n$.

We also note the following theorem, although we invite the reader to read its
proof in a companion paper to this one which is available on arXiv [10] as
that proof is very similar to the proof above.

######  Theorem 2.2.

Let $n$ be an odd integer greater than 5 and let $r$, $s$, and $t$ be integers
less than $n$ such that the difference of any two of them is relatively prime
to $n$. If $3r+s=4t$ mod $n$, then
$\mbox{Cay}(D_{n},\\{ab^{r},ab^{s},ab^{t}\\})$ is a GRR of $D_{n}$.

Just as with the prior theorem, Theorem 2.2 has a tidy corollary for prime
numbers:

######  Corollary 2.2.

Let $n$ be an odd integer with its smallest prime factor being $p$ greater
than 5 and let $r$, $s$, and $t$ be distinct integers less than $p$. If
$3r+s=4t$ mod $n$, then $\mbox{Cay}(D_{n},\\{ab^{r},ab^{s},ab^{t}\\})$ is a
GRR of $D_{n}$.

In the next section we shall give a few examples in which the above results
are applied.

##  3 Examples of GRR constructions

We will be focusing on applying Corollary 2.1 to when $n$ itself is prime,
giving us GRRs of $D_{p}$, as this will provide clear and concise examples.

###  3.1 A simple application

First let us start with $p=11$. To satisfy the equation $3r-2s=t$ we will take
$r=3$, $s=4$ and $t=1$. Therefore $Cay(D_{11},\\{ab^{3},ab^{4},ab\\})$ is a
GRR of $D_{11}$. We present the Cayley colour graph for this connecting set in
Figure 3 so that the reader can see which element of the connecting set gave
rise to which edge: $ab$ is red, $ab^{3}$ is blue and $ab^{4}$ is green. These
edge-colourings hold true irrespective of which vertex is the identity element
of $D_{11}$ since every automorphism of a GRR only maps edges of the same
colour to each other [1].

Figure 3: $Cay(D_{11},\\{ab,ab^{3},ab^{4}\\})$, a GRR of $D_{11}$.

###  3.2 The inheritability of connecting sets

In the previous example we used the values $\\{3,4,1\\}$ for the parameters
$\\{r,s,t\\}$ respectively to construct a GRR for $D_{11}$. However, with a
very simple theorem we can show that these values for $\\{r,s,t\\}$ can be
used to construct GRRs for an infinite number of dihedral groups $D_{p}$ where
$p$ is prime.

To do this, we prove the following theorem. Note that all arithmetic in the
proof is only modular arithmetic if its explicitly said to be so, and all
order relations are to be understood as an ordering on the positive integers:

######  Theorem 3.2.1.

Let $p_{2}>p_{1}$ be prime. Suppose that, for a given $\alpha,\beta,\gamma$
there exist integers $r,s,t$ such that $\alpha r-\beta s\equiv\gamma t\ mod\
p_{1}.$ Then, if $\alpha r-\beta s\in[0,p_{1}]$ then $\alpha r-\beta
s\equiv\gamma t\ mod\ p_{2}$ also holds.

###### Proof.

$\alpha r-\beta s\equiv\gamma t\ mod\ p_{1}$ implies that $\alpha r-\beta
s=\gamma t+xp_{1}$ for some integer $x$. We observe that $\alpha r-\beta
s\in[0,p_{1}]$ means that $x=0$.

Now consider the expression $\alpha r-\beta s\ mod\ p_{2}$. Since
$p_{2}>p_{1}$ we can re-write this expression as $(\gamma t+xp_{1})\ mod\
p_{2}$. When $x=0$ this simplifies to $\gamma t\ mod\ p_{2}$.

Therefore if $\alpha r-\beta s\in[0,p_{1}]$ then $\alpha r-\beta s\equiv\gamma
t\ mod\ p_{2}$ holds.

∎

This theorem has a useful corollary:

######  Corollary 3.1.

Let $p_{2}>p_{1}$ be prime. Let $D_{p_{1}}$ be a dihedral group such that
$D_{p_{1}}\equiv\langle a,b:a_{1}^{2}\equiv b_{1}^{p_{1}}\equiv
a_{1}b_{1}a_{1}b_{1}\equiv 1\rangle$. Let $r,s,t$ be integers which satisfy
$3r-2s\equiv t\ mod\ p_{1}$ and therefore let us construct a connecting
$C_{1}$ set for a GRR of $D_{p_{1}}$ where
$C_{1}\equiv\\{a_{1}b_{1}^{r},a_{1}b_{1}^{s},a_{1}b_{1}^{t}\\}$. Then those
same integers $r,s,t$ can be used to construct a connecting set $C_{2}$ which
admits a GRR for $D_{p_{2}}$ where $D_{p_{2}}\equiv\langle a,b:a_{2}^{2}\equiv
b_{2}^{p_{2}}\equiv a_{2}b_{2}a_{2}b_{2}\equiv 1\rangle$ and
$C_{2}\equiv\\{a_{2}b_{2}^{r},a_{2}b_{2}^{s},a_{2}b_{2}^{t}\\}$.

With this, any solutions for $r,s,t$ which we find when trying to form a GRR
for some dihedral group $D_{p_{1}}$ with $p_{1}$ prime can be re-used to
construct connecting sets for an infinite number of other dihedral groups,
specifically those dihedral groups $D_{p_{2}}$ where $p_{2}>p_{1}$ and prime.

Figure 4 is a GRR of $D_{13}$ which we construct using the same values we
found when constructing a GRR for $D_{11}$ in the previous example.

Figure 4: $Cay(D_{13},\\{ab,ab^{3},ab^{4}\\})$, a GRR of $D_{13}$.

###  3.3 Some further solutions

Below is a table of connecting sets for $D_{p}$ for a few prime values of $p$,
found using the equation $3r-2s=t$ mod $p$ (see Corollary 2.1). While
constructing these connecting sets, the condition $\alpha r-\beta s\in[0,p]$
was respected and so we know from Corollary 3.1 that all the sets in the table
below are in fact connecting sets for GRRs of $D_{p}$ not just for the prime
number given in its row but for all prime numbers larger than it too.

For brevity we present only the prime numbers up to 100.

$p$ | $r$ | $s$ | $t$ | Connecting Set($\\{ab^{r},ab^{s},ab^{t}\\}$)
---|---|---|---|---
7 | 2 | 3 | 0 | $\\{ab^{2},ab^{3},a\\}$
11 | 3 | 4 | 1 | $\\{ab^{3},ab^{4},ab\\}$
13 | 4 | 6 | 0 | $\\{ab^{4},ab^{6},a\\}$
17 | 5 | 7 | 1 | $\\{ab^{5},ab^{7},ab\\}$
19 | 6 | 9 | 0 | $\\{ab^{6},ab^{9},a\\}$
23 | 7 | 10 | 1 | $\\{ab^{7},ab^{10},ab\\}$
29 | 9 | 13 | 1 | $\\{ab^{9},ab^{13},ab\\}$
31 | 10 | 15 | 0 | $\\{ab^{10},ab^{15},a\\}$
37 | 12 | 18 | 0 | $\\{ab^{12},ab^{18},a\\}$
41 | 13 | 19 | 1 | $\\{ab^{13},ab^{19},ab\\}$
43 | 14 | 21 | 0 | $\\{ab^{14},ab^{21},a\\}$
47 | 15 | 22 | 1 | $\\{ab^{15},ab^{22},ab\\}$
53 | 17 | 25 | 1 | $\\{ab^{17},ab^{25},ab\\}$
59 | 19 | 28 | 1 | $\\{ab^{19},ab^{28},ab\\}$
61 | 20 | 30 | 0 | $\\{ab^{20},ab^{30},a\\}$
67 | 22 | 33 | 0 | $\\{ab^{22},ab^{38},a\\}$
71 | 23 | 34 | 1 | $\\{ab^{23},ab^{34},ab\\}$
73 | 24 | 36 | 0 | $\\{ab^{24},ab^{36},a\\}$
79 | 26 | 39 | 0 | $\\{ab^{26},ab^{39},a\\}$
83 | 27 | 40 | 1 | $\\{ab^{27},ab^{40},ab\\}$
89 | 29 | 43 | 1 | $\\{ab^{29},ab^{43},ab\\}$
97 | 32 | 48 | 0 | $\\{ab^{32},ab^{48},a\\}$

##  4 Conclusion

By making use of a few theorems and lemmas about Schur rings we have shown
easy ways to construct trivalent GRRs for dihedral groups $D_{n}$ where $n$ is
an odd number. It is the opinion of the authors that these results are
evidence that even a basic study of Schur rings can be fruitful not only in
the search for GRRs but also in other areas of algebraic graph theory.

We are now in a position where we can produce two GRRs for each member of an
infinite family of dihedral groups within moments. For example,
$\\{a,ab^{2},ab^{3}\\}$ and $\\{a,ab^{3},ab^{4}\\}$ are connecting sets for
GRRs of all $D_{n}$ where $n$ is prime and larger than 11, by using
Corollaries 2.1, 2.2 and 3.1.

This can be the groundwork for several further lines of inquiry. For example,
are the methods we have outlined sufficient to find all possible trivalent
GRRs for the relevant dihedral groups? If no, can we perhaps find a similar
approach to account for the remaining ones? If yes, can these methods be used
as groundwork for enumeration theorems?

Moreover, the methods we have described here can be expanded to find GRRs for
dihedral groups with a valency greater than 3 and we can also slightly relax
the conditions on the parameter $n$. This is all to be discussed another time,
however.

These lines of inquiry we have outlined may yet yield further useful results.

## References

  * [1] M. Albert, J. Bratz, P. Cahn, T. Fargus, N. Haber, E. Mcmahon, J. Smith, S. Tekansik, Color-Permuting Automorphisms of Cayley Graphs, Congressus Numerantium Vol. 190, pages 161 - 171 (2008).
  * [2] A.V. Alexeevski, S.M. Natanzon, Algebras of conjugacy classes of partial elements, American Mathematical Society Translations Vol. 234, pages 1 - 12 (2014).
  * [3] L. Babel, I.V. Chuvaeva, M. Klin, D.V. Pasechnik, Algebraic Combinatorics in Mathematical Chemistry.Methods and Algorithms.II. Program Implementation of the Weisfeiler-Leman Algorithm, arXiv 1002.1921 (2010).
  * [4] L.W. Beineke, R.J. Wilson (ed.), Topics in Algebraic Graph Theory, Cambridge University Press, UK (2004).
  * [5] N. Biggs, Algebraic Graph Theory Second Edition, Cambridge Univeristy Press, UK (1993).
  * [6] C.Y. Chao, On Groups and Graphs, American Mathematical Society Vol. 118, pages 488 - 497 (1965).
  * [7] H.S.M. Coxeter, R. Frucht, D.L. Powers, Zero-Symmetric Graphs - Trivalent Graphical Regular Representations of Groups, Academic Press Inc., New York (1981).
  * [8] P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory, Philips Research Report Supplements Issue 10, (1973).
  * [9] M. Droste, M. Giraudet, R. Gobel, All Groups are Outer Automorphism Groups of Simple Groups, Journal of London Mathematical Society (2) Vol. 64, pages 565 - 575 (2001).
  * [10] J.Ebejer, J.Lauri Further Applications of Schur Rings to Produce GRRs for Dihedral Groups. arXiv preprint arXiv:2401.02690 (2024).
  * [11] J.Ebejer Schur rings: some theory and applications to graphical regular representations M.Sc. dissertation, University of Malta (2020).
  * [12] I.A. Faradžev, A.A. Ivanov, M.H. Klin, Galois Correspondence Between Permutation Groups and Cellular Rings (Association Schemes), Graphs and Combinatorics Vol. 6, pages 303 - 332 (1990).
  * [13] C.D. Godsil, Neighbourhoods of transitive graphs and GRRs, Journal of Combinatorial Theory (Ser. B) Vol. 29, pages 116 - 140 (1980).
  * [14] D. Hetzel, Über reguläre graphische Darstellungen von auﬂösbaren Gruppe, Diplomarbeit. Technische Universität Berlin (1976).
  * [15] W. Imrich, Graphical representations of groups of odd order, Combinatorics Colloq. Math. Soc. J. Bolyai Vol. 18, pages 611 - 621 (1976).
  * [16] W. Imrich, On graphs with regular groups, Journal of Combinatorial Theory (Ser. B) Vol. 19, pages 174 - 180 (1975).
  * [17] W. Imrich, M.E. Watkins, On graphical regular representation of cyclic extensions of groups, Pacific Journal of Mathematics Vol. 55, pages 461 - 477 (1974).
  * [18] W. Imrich, M.E. Watkins, On automorphism groups of Cayley graphs, Periodica Mathematica Hungarica Vol. 7, pages 243 - 258 (1976).
  * [19] V.N. Ivanov, S.V. Kerov, The Algebra of Conjugacy Classes in Symmetric Groups and Partial Permutations, Journal of Mathematical Sciences Vol. 107, pages 4212 - 4230 (2001).
  * [20] M. Klin, C. Rucker, G. Rucker, G. Tinhofer, Algebraic Combinatorics in Mathematical Chemistry. Methods and Algorithms. I. Permutation Groups and Coherent (Cellular) Algebras, MATCH Vol. 40, pages 7 - 138 (1999).
  * [21] J. Lauri, R. Scapellato, Topics in graph automorphisms and reconstruction, Cambridge University Press (2016).
  * [22] M. Muzychuk, I. Ponomarenko, Schur Rings, European Journal of Combinatorics Vol. 30, pages 1526 - 1539 (2009).
  * [23] L.A. Nowitz, M.E. Watkins, Graphical regular representations of non-abelian groups, I, Canadian Journal of Mathematics XXIV. Vol. 6, pages 993 - 1008 (1972).
  * [24] L.A. Nowitz, M.E. Watkins, Graphical regular representations of non-abelian groups, II, Canadian Journal of Mathematics XXIV. Vol. 6, pages 1009 - 1018 (1972).
  * [25] G. Sabidussi, On a Class of fixed-point free graphs, Proceedings of the American Mathematical Society Vol. 9, pages 800 - 804 (1958).
  * [26] B. Weisfeiler, On Construction and Identification of Graphs, Springer-Verlag, Berlin (1976).
  * [27] H. Wielandt, Finite Permutation Groups, Academic Press, New York-London (1964).
  * [GAP] The GAP Group, _GAP – Groups, Algorithms, and Programming, Version 4.12.2_ ; 2022, https://www.gap-system.org


instance, the mogp∗ is provided with auxiliary task labels for test molecules
where available (i.e. labels for tasks that are not being predicted). The null
hypothesis is that there is no significant difference arising from multitask
learning. In the case of the _E_ isomer $\pi-\pi^{*}$ transition, the
resultant p-value is $0.33$, meaning that the null hypothesis cannot be
rejected at the 95% confidence level. In the case of the _Z_ isomer
$\pi-\pi^{*}$ transition, the resultant p-value is $0.06$, meaning also that
the null hypothesis cannot be rejected at the 95% confidence level. In this
latter case, however, rejection of the null hypothesis depends on the
confidence level threshold specified. As such, it is concluded that only weak
evidence is available to support the benefits of multitask learning over
single task learning.

Table C.1: Test set performance in predicting the transition wavelengths of
the _E_ and _Z_ isomers. Best-performing models are highlighted in bold. MOGP∗
denotes a multioutput gp such that auxiliary task labels (i.e. not the task
being predicted) for test molecules are provided to the model where available.

_E_ isomer $\pi-\pi{{}^{*}}$ (nm) _E_ isomer _n_ $-\pi{{}^{*}}$ (nm) _Z_
isomer $\pi-\pi{{}^{*}}$ (nm) _Z_ isomer _n_ $-\pi{{}^{*}}$ (nm) RMSE RF +
Morgan $25.3\pm\>0.9$ $\textbf{10.2}\pm\>\textbf{0.4}$ $14.0\pm\>0.6$
$11.1\pm\>0.4$ RF + Fragments $26.4\pm\>1.1$ $11.4\pm\>0.5$ $17.0\pm\>0.8$
$14.2\pm\>0.6$ RF + Fragprints $23.4\pm\>0.9$ $11.0\pm\>0.4$ $14.2\pm\>0.6$
$11.3\pm\>0.6$ GP + Morgan $23.4\pm\>0.8$ $11.4\pm\>0.5$ $13.2\pm\>0.7$
$\textbf{11.0}\pm\>\textbf{0.7}$ GP + Fragments $26.3\pm\>0.8$ $11.6\pm\>0.5$
$15.5\pm\>0.8$ $12.6\pm\>0.5$ GP + Fragprints $20.9\pm\>0.7$ $11.1\pm\>0.5$
$13.1\pm\>0.6$ $11.4\pm\>0.7$ GP + SOAP $21.0\pm\>0.6$ $22.7\pm\>0.6$
$17.8\pm\>0.8$ $15.0\pm\>0.5$ GP + SMILES $26.0\pm\>0.8$ $12.3\pm\>0.4$
$12.5\pm\>0.5$ $11.8\pm\>0.6$ GP + SELFIES $23.5\pm\>0.7$ $12.9\pm\>0.5$
$14.4\pm\>0.5$ $12.2\pm\>0.5$ MOGP + Morgan $23.6\pm\>0.8$ $11.7\pm\>0.5$
$15.5\pm\>0.6$ $11.1\pm\>0.7$ MOGP + Fragments $27.0\pm\>0.9$ $11.9\pm\>0.6$
$16.4\pm\>0.9$ $13.1\pm\>0.6$ MOGP + Fragprints $21.2\pm\>0.7$ $11.3\pm\>0.5$
$13.5\pm\>0.6$ $11.4\pm\>0.7$ MOGP∗ \+ Morgan $22.6\pm\>0.8$ $11.6\pm\>0.4$
$12.3\pm\>0.7$ $10.9\pm\>0.7$ MOGP∗ \+ Fragments $26.9\pm\>0.8$ $12.1\pm\>0.6$
$16.2\pm\>0.8$ $13.8\pm\>0.6$ MOGP∗ \+ Fragprints
$\textbf{20.4}\pm\>\textbf{0.7}$ $11.2\pm\>0.5$
$\textbf{11.3}\pm\>\textbf{0.4}$ $11.4\pm\>0.7$ ANP + Morgan $28.1\pm\>1.3$
$13.6\pm\>0.5$ $13.5\pm\>0.6$ $\textbf{11.0}\pm\>\textbf{0.6}$ ANP + Fragments
$27.9\pm\>1.1$ $13.8\pm\>0.9$ $17.2\pm\>0.8$ $14.1\pm\>0.7$ ANP + Fragprints
$27.0\pm\>0.8$ $11.6\pm\>0.5$ $14.5\pm\>0.8$ $11.3\pm\>0.7$ GCN $22.0\pm\>0.8$
$12.8\pm\>0.8$ $16.3\pm\>0.8$ $13.1\pm\>0.8$ GAT $26.4\pm\>1.1$ $16.9\pm\>1.9$
$19.6\pm\>1.0$ $14.5\pm\>0.8$ DMPNN $27.1\pm\>1.4$ $13.9\pm\>0.6$
$17.5\pm\>0.7$ $13.8\pm\>0.4$ MAE RF + Morgan $15.5\pm\>0.5$
$\textbf{7.3}\pm\>\textbf{0.3}$ $10.1\pm\>0.4$ $\textbf{6.6}\pm\>\textbf{0.3}$
RF + Fragments $16.4\pm\>0.5$ $8.5\pm\>0.3$ $12.2\pm\>0.6$ $9.0\pm\>0.4$ RF +
Fragprints $13.9\pm\>0.4$ $7.7\pm\>0.3$ $10.0\pm\>0.4$ $6.8\pm\>0.3$ GP +
Morgan $15.2\pm\>0.4$ $8.4\pm\>0.3$ $9.8\pm\>0.4$ $6.9\pm\>0.3$ GP + Fragments
$17.3\pm\>0.4$ $8.6\pm\>0.3$ $11.5\pm\>0.5$ $8.2\pm\>0.3$ GP + Fragprints
$13.3\pm\>0.3$ $8.2\pm\>0.3$ $9.8\pm\>0.4$ $7.1\pm\>0.3$ GP + SOAP
$14.3\pm\>0.3$ $19.3\pm\>0.5$ $12.9\pm\>0.6$ $11.4\pm\>0.4$ GP + SMILES
$16.6\pm\>0.5$ $8.6\pm\>0.3$ $9.4\pm\>0.4$ $7.4\pm\>0.3$ GP + SELFIES
$14.7\pm\>0.7$ $8.8\pm\>0.3$ $11.1\pm\>0.3$ $8.1\pm\>0.2$ MOGP + Morgan
$15.3\pm\>0.4$ $8.6\pm\>0.3$ $11.9\pm\>0.5$ $7.0\pm\>0.3$ MOGP + Fragments
$17.6\pm\>0.5$ $8.8\pm\>0.4$ $12.1\pm\>0.6$ $8.3\pm\>0.3$ MOGP + Fragprints
$13.5\pm\>0.3$ $8.3\pm\>0.3$ $10.2\pm\>0.5$ $7.1\pm\>0.3$ MOGP∗ \+ Morgan
$14.4\pm\>0.4$ $8.5\pm\>0.3$ $9.6\pm\>0.4$ $6.9\pm\>0.4$ MOGP∗ \+ Fragments
$17.2\pm\>0.4$ $8.9\pm\>0.3$ $11.9\pm\>0.5$ $8.5\pm\>0.4$ MOGP∗ \+ Fragprints
$\textbf{13.1}\pm\>\textbf{0.3}$ $8.3\pm\>0.3$ $\textbf{8.8}\pm\>\textbf{0.3}$
$7.1\pm\>0.4$ ANP + Morgan $17.9\pm\>0.7$ $10.1\pm\>0.4$ $10.0\pm\>0.4$
$7.2\pm\>0.3$ ANP + Fragments $17.4\pm\>0.6$ $9.4\pm\>0.4$ $12.3\pm\>0.6$
$8.9\pm\>0.4$ ANP + Fragprints $18.1\pm\>0.5$ $8.6\pm\>0.3$ $10.4\pm\>0.5$
$7.0\pm\>0.3$ GCN $13.9\pm\>0.3$ $8.6\pm\>0.3$ $11.6\pm\>0.5$ $8.6\pm\>0.5$
GAT $18.1\pm\>0.7$ $10.7\pm\>0.6$ $14.4\pm\>0.8$ $10.8\pm\>0.7$ DMPNN
$17.1\pm\>0.8$ $10.6\pm\>0.4$ $12.8\pm\>0.6$ $9.8\pm\>0.3$ _R 2_ RF + Morgan
$0.85\pm\>0.01$ $\textbf{0.80}\pm\>\textbf{0.01}$ $0.25\pm\>0.06$
$0.36\pm\>0.06$ RF + Fragments $0.83\pm\>0.01$ $0.75\pm\>0.02$
$-0.15\pm\>0.11$ $-0.05\pm\>0.07$ RF + Fragprints $0.87\pm\>0.01$
$0.77\pm\>0.02$ $0.23\pm\>0.07$ $0.33\pm\>0.06$ GP + Morgan $0.87\pm\>0.01$
$0.76\pm\>0.01$ $0.34\pm\>0.05$ $\textbf{0.38}\pm\>\textbf{0.05}$ GP +
Fragments $0.84\pm\>0.01$ $0.74\pm\>0.02$ $0.07\pm\>0.08$ $0.19\pm\>0.05$ GP +
Fragprints $\textbf{0.90}\pm\>\textbf{0.01}$ $0.77\pm\>0.02$ $0.35\pm\>0.05$
$0.33\pm\>0.05$ GP + SOAP $0.89\pm\>0.01$ $-0.08\pm\>0.03$ $-0.05\pm\>0.02$
$-0.07\pm\>0.02$ GP + SMILES $0.84\pm\>0.02$ $0.72\pm\>0.02$ $0.39\pm\>0.05$
$0.29\pm\>0.04$ GP + SELFIES $0.86\pm\>0.01$ $0.68\pm\>0.02$ $0.20\pm\>0.05$
$0.23\pm\>0.04$ MOGP + Morgan $0.87\pm\>0.01$ $0.75\pm\>0.01$ $0.06\pm\>0.08$
$0.37\pm\>0.05$ MOGP + Fragments $0.83\pm\>0.01$ $0.73\pm\>0.02$
$-0.05\pm\>0.10$ $0.11\pm\>0.06$ MOGP + Fragprints $0.89\pm\>0.01$
$0.76\pm\>0.02$ $0.30\pm\>0.06$ $0.33\pm\>0.05$ MOGP∗ \+ Morgan
$0.88\pm\>0.01$ $0.75\pm\>0.01$ $0.34\pm\>0.12$ $0.39\pm\>0.05$ MOGP∗ \+
Fragments $0.83\pm\>0.01$ $0.72\pm\>0.02$ $-0.06\pm\>0.12$ $0.00\pm\>0.08$
MOGP∗ \+ Fragprints $\textbf{0.90}\pm\>\textbf{0.01}$ $0.76\pm\>0.01$
$\textbf{0.49}\pm\>\textbf{0.05}$ $0.33\pm\>0.06$ ANP + Morgan $0.70\pm\>0.02$
$0.66\pm\>0.02$ $0.30\pm\>0.06$ $\textbf{0.38}\pm\>\textbf{0.05}$ ANP +
Fragments $0.81\pm\>0.01$ $0.62\pm\>0.05$ $-0.16\pm\>0.11$ $-0.06\pm\>0.10$
ANP + Fragprints $0.83\pm\>0.01$ $0.75\pm\>0.01$ $0.18\pm\>0.08$
$0.35\pm\>0.05$ GCN $0.87\pm\>0.01$ $0.66\pm\>0.03$ $-0.41\pm\>0.22$
$-0.92\pm\>0.3$ GAT $0.81\pm\>0.02$ $0.57\pm\>0.04$ $0.39\pm\>0.17$
$-1.07\pm\>0.4$ DMPNN $0.82\pm\>0.02$ $0.63\pm\>0.02$ $-0.05\pm\>0.07$
$0.11\pm\>0.04$

Results with additional models on the property prediction benchmark for which
extensive hyperparameter tuning was not undertaken, are presented in Table
C.2. The black-box alpha divergence minimisation BNN was implemented in the
Theano library (2016_Theano) and is based on the implementation of
(2016_Lobato). The network has 2 hidden layers of size 25 with ReLU
activations. The alpha parameter was set to 0.5, the prior variance for the
variational distribution q was set to 1, and 100 samples were taken to
approximate the expectation over the variational distribution. For all tasks
the network was trained using 8 iterations of the Adam optimiser (2014_Adam)
with a batch size of 32 and a learning rate of 0.05. The MPNN was trained for
100 epochs in the case of the _E_ isomer $\pi-\pi{{}^{*}}$ task and 200 epochs
in the case of the other tasks with a learning rate of 0.001 and a batch size
of 32. The model architecture was taken to be the library default with the
same node and edge features used for the GCN and GAT models in the main paper.
The SMILES-X implementation remained the same as that of 2020_Lambard save for
the difference that the network was trained for 40 epochs without bo over
model architectures. In the case of SMILES-X 3 random train/test splits were
used instead of 20 for the _Z_ isomer tasks whereas 2 splits were used for the
_E_ isomer _n_ $-\pi{{}^{*}}$ task. For the _E_ isomer $\pi-\pi{{}^{*}}$
prediction task results are missing due to insufficient RAM on the machine
used to run the experiments.

Table C.2: Test set performance in predicting the transition wavelengths of
the _E_ and _Z_ isomers.

|  _E_ isomer $\pi-\pi{{}^{*}}$ (nm) |  _E_ isomer _n_ $-\pi{{}^{*}}$ (nm) |  _Z_ isomer $\pi-\pi{{}^{*}}$ (nm) |  _Z_ isomer _n_ $-\pi{{}^{*}}$ (nm)
---|---|---|---|---
RMSE |  |  |  |
BNN + Morgan | $27.0\pm\>0.9$ | $12.9\pm\>0.6$ | $13.9\pm\>0.6$ | $12.7\pm\>0.4$
BNN + Fragments | $31.2\pm\>1.1$ | $14.8\pm\>0.8$ | $16.9\pm\>0.8$ | $12.7\pm\>0.4$
BNN + Fragprints | $26.7\pm\>0.8$ | $13.1\pm\>0.5$ | $14.9\pm\>0.5$ | $13.0\pm\>0.6$
MPNN | $24.8\pm\>0.8$ | $12.5\pm\>0.6$ | $16.7\pm\>0.8$ | $12.8\pm\>0.7$
SMILES-X |  | $25.1\pm\>4.2$ | $17.8\pm\>0.6$ | $14.8\pm\>0.9$
MAE |  |  |  |
BNN + Morgan | $19.0\pm\>0.6$ | $9.9\pm\>0.4$ | $10.2\pm\>0.5$ | $8.6\pm\>0.3$
BNN + Fragments | $22.4\pm\>0.8$ | $10.6\pm\>0.4$ | $12.9\pm\>0.6$ | $8.6\pm\>0.3$
BNN + Fragprints | $19.1\pm\>0.6$ | $10.1\pm\>0.5$ | $10.8\pm\>0.4$ | $9.3\pm\>0.5$
MPNN | $15.4\pm\>0.8$ | $8.6\pm\>0.3$ | $11.6\pm\>0.6$ | $8.4\pm\>0.4$
SMILES-X |  | $20.6\pm\>3.1$ | $11.6\pm\>1.0$ | $11.2\pm\>1.0$
_R 2_ |  |  |  |
BNN + Morgan | $0.83\pm\>0.01$ | $0.69\pm\>0.02$ | $0.23\pm\>0.08$ | $0.18\pm\>0.05$
BNN + Fragments | $0.77\pm\>0.01$ | $0.58\pm\>0.04$ | $-0.15\pm\>0.14$ | $0.18\pm\>0.05$
BNN + Fragprints | $0.83\pm\>0.01$ | $0.68\pm\>0.02$ | $0.14\pm\>0.06$ | $0.11\pm\>0.08$
MPNN | $0.83\pm\>0.01$ | $0.63\pm\>0.06$ | $-0.70\pm\>0.34$ | $-0.68\pm\>0.27$
SMILES-X |  | $-0.44\pm\>0.30$ | $-0.08\pm\>0.06$ | $-0.09\pm\>0.04$

####  C.3.2 Prediction Error as a Guide to Representation Selection

On the _E_ isomer $\pi-\pi{{}^{*}}$ transition wavelength prediction task,
occasionally marked discrepancies were noted in the predictions made under the
Morgan fingerprint and fragment representations. The resultant analysis
motivated the expansion of the molecular feature set to include both
representations as fragprints.

####  C.3.3 Impact of Dataset Choice

In this section, the generalisation performance was evaluated for a model
trained on the _E_ isomer $\pi-\pi{{}^{*}}$ values of a large dataset of 6142
out-of-domain molecules (including non-azoarene photoswitches) from
2019_Beard, with experimentally-determined labels. A RF regressor was (due to
scalability issues with the mogp on 6000+ data points) implemented in the
scikit-learn library with 1000 estimators and a max depth of 300 on the
fragprint representation of the molecules. In Table C.3 results are presented
for the case when the train set consists of the large dataset of 6142
molecules and the test set consists of the entire photoswitch dataset. Results
are also presented on the original _E_ isomer $\pi-\pi{{}^{*}}$ transition
wavelength prediction task where the train set of each random 80/20 train/test
split was augmented with the molecules from the large dataset. The results
indicate that the data for out-of-domain molecules provides no benefit for the
prediction task and even degrades performance, when amalgamated, relative to
training on in-domain data only.

Table C.3: Performance comparison of curated dataset against large non-curated dataset. Dataset | Size | RMSE ($\downarrow$) | MAE ($\downarrow$) |  $R^{2}$ ($\uparrow$)
---|---|---|---|---
Large Non-Curated | 6142 | $85.2$ | $72.5$ | $-0.66$
Large Non-Curated + Curated | 6469 | $36.9\pm 1.2$ | $22.7\pm 0.7$ | $0.67\pm 0.02$
Curated | 314 | $\textbf{23.4}\pm\textbf{0.9}$ | $\textbf{13.9}\pm\textbf{0.4}$ | $\textbf{0.87}\pm\textbf{0.01}$

Based on these results the importance of designing synthetic molecular machine
learning benchmarks with a real-world application in mind is emphasised, as
well as the importance of involving synthetic chemists in the curation
process. By targeted data collation on a narrow and well-defined region of
chemical space where the molecules are in-domain relative to the task, it
becomes possible to mitigate generalisation error.

####  C.3.4 Human Performance Benchmark

Below in Table C.4 the full results breakdown of the human performance
benchmark study is provided.

Table C.4: Results breakdown for the human expert performance benchmark predicting the transition wavelength (nm) of the _E_ isomer $\pi-\pi^{*}$ transition for 5 molecules. Closest prediction for each molecule is underlined and highlighted in bold. mogp achieves the lowest MAE relative to all individual human participants. | Mol 1 | Mol 2 | Mol 3 | Mol 4 | Mol 5 | MAE ($\downarrow$)
---|---|---|---|---|---|---
True Value | 329 | 407 | 333 | 540 | 565 |
Postdoc 1 | 325 | 360 | 410 | 490 | 490 | 54.7
PhD 1 | 350 | 400 | 530 | 410 | 425 | 93.3
PhD 2 | 380 | 280 | 530 | 600 | 250 | 177.5
Postdoc 2 | 330 | 350 | 500 | 475 | 500 | 66.7
PhD 3 | 325 | 350 | 350 | 540 | 550 | 16.3
Postdoc 3 | 350 | 370 | 520 | 600 | 500 | 97.5
PhD 4 | 330 | 380 | 390 | 520 | 580 | 34.2
Undergraduate 1 | 340 | 420 | 400 | 540 | 570 | 41.8
Postdoc 4 | 321 | 345 | 340 | 500 | 520 | 28.7
PhD 5 | 330 | 360 | 340 | 500 | 520 | 24.2
PhD 6 | 303 | 367 | 435 | 411 | 450 | 78.7
PhD 7 | 280 | 350 | 450 | 430 | 460 | 85.5
PhD 8 | 270 | 390 | 420 | 420 | 440 | 73.8
PhD 9 | 330 | 310 | 462 | 512 | 512 | 55.3
mogp | 321 | 413 | 354 | 518 | 569 | 11.9

####  C.3.5 Confidence-Error Curves

An advantage of Bayesian models for the real-world prediction task is the
ability to produce calibrated uncertainty estimates. If correlated with
prediction error, a model’s uncertainty may act as an additional decision-
making criterion for the selection of candidates for lab synthesis. To
investigate the benefits afforded by uncertainty estimates, confidence-error
curves were produced using the gp-Tanimoto model in conjunction with the
fingerprints representation. The confidence-error curves for the RMSE and MAE
metrics are shown in Figure C.2 and Figure C.3 respectively. The x-axis,
confidence percentile, may be obtained simply by ranking each model prediction
of the test set in terms of the predictive variance at the location of that
test input. As an example, molecules that lie in the 80th confidence
percentile will be the 20% of test set molecules with the lowest model
uncertainty. The prediction error is then measured at each confidence
percentile across 200 random train/test splits to see whether the model’s
confidence is correlated with the prediction error. It is observed that across
all tasks, the gp-Tanimoto model’s uncertainty estimates are positively
correlated with prediction error, offering a proof of concept that model
uncertainty can be incorporated into the decision process for candidate
selection.

(a) _E_ Isomer $\pi-\pi{{}^{*}}$

(b) _E_ Isomer _n_ $-\pi{{}^{*}}$

(c) _Z_ Isomer $\pi-\pi{{}^{*}}$

(d) _Z_ Isomer _n_ $-\pi{{}^{*}}$

Fig. C.2: RMSE confidence-error curves for property prediction using gp
regression.

(a) _E_ Isomer $\pi-\pi{{}^{*}}$

(b) _E_ Isomer _n_ $-\pi{{}^{*}}$

(c) _Z_ Isomer $\pi-\pi{{}^{*}}$

(d) _Z_ Isomer _n_ $-\pi{{}^{*}}$

Fig. C.3: MAE confidence-error curves for property prediction using gp
regression.

####  C.3.6 TD-DFT Benchmark

Below, in Figure C.4 and Figure C.5 further plots are included analysing the
performance of the methods on the TD-DFT performance comparison benchmark.
These plots motivated the use of the Lasso-correction to the TD-DFT
predictions.

Fig. C.4: Regression plots for each method on the TD-DFT performance
comparison benchmark with the Spearman rank-order correlation coefficient
given as $\rho$. One may observe that the correlation between predictions and
ground truth experimental values increases with the linear Lasso correction to
the TD-DFT methods.

Fig. C.5: Signed error distributions for each method on the TD-DFT performance
comparison benchmark. Signed error is recorded for each heldout molecule in
leave-one-out-validation. Gaussian kernel density estimates are overlaid on
the histograms. One may observe that the linear Lasso correction for the TD-
DFT methods has a centering effect on the error distribution.

###  C.4 Further Screening Details

Reagents and solvents were obtained from commercial sources (MolPort) and used
as supplied. Experimental measurements were performed by Jake L. Greenfield at
Imperial College London and below is included his account of the experimental
procedure.

####  C.4.1 UV-Vis Absorption Spectroscopy

UV-Vis absorption spectra were obtained on an Agilent 8453 UV-Visible
Spectrophotometer G1103A. A sampler holder with four open faces was used to
enable in-situ irradiation (90° to the measurement beam). Samples were
prepared in a UV Quartz cuvette with a path length of 10 mm. Solutions of the
compounds were prepared in HPLC grade DMSO at a concentration of 25
$\mu\text{M}$.

####  C.4.2 Photoswitching

Samples were irradiated with a custom-built irradiation set up using 365 nm (3
× 800 mW Nichia NCSU276A LEDs, FWHM 9 nm), 405 nm (3 × 770 mW Nichia NCSU119C
LEDs, FWHM 11 nm), 450 nm (3 × 900 mW Nichia NCSC219B-V1 LEDs, FWHM 18 nm),
495 nm (3 × 750 mW Nichia NCSE219B-V1 LEDs, FWHM 32 nm), 525 nm (3 × 450 mW
NCSG219B-V1 LEDs, FWHM 38 nm) and 630 nm (3 × 780 mW Nichia NCSR219B-V1 LEDs,
FWHM 16 nm) light sources. Samples were irradiated until no further change in
the UV-vis absorption spectra was observed, indicating that the
Photostationary State (PSS) was reached. The PSS, and the predicted pure Z
spectra was determined using UV-vis following the procedure reported by
Fischer1967.

###  C.5 Novelty of Screened Candidates relative to The Photoswitch Dataset

In Figure C.6, for each of the 6 candidates satisfying both performance
criteria, some indication as to the novelty of the discovered photoswitch
candidates is provided by giving the 3 closest molecules by Tanimoto
similarity from the Photoswitch Dataset.

Fig. C.6: All 6 experimentally-tested candidates satisfying both performance
criteria together with the 3 closest molecules by Tanimoto similarity in the
Photoswitch Dataset.