# Association schemes with given stratum dimensions: on a paper of Peter M.
Neumann

Marina Anagnostopoulou-Merkouri and Peter J. Cameron
School of Mathematics and Statistics, University of St Andrews, St Andrews,
Fife KY16 9SS, UK

###### Abstract

In January 1969, Peter M. Neumann wrote a paper entitled “Primitive
permutation groups of degree $3p$”. The main theorem placed restrictions on
the parameters of a primitive but not $2$-transitive permutation group of
degree three times a prime. The paper was never published, and the results
have been superseded by stronger theorems depending on the classification of
the finite simple groups, for example a classification of primitive groups of
odd degree.

However, there are further reasons for being interested in this paper. First,
it was written at a time when combinatorial techniques were being introduced
into the theory of finite permutation groups, and the paper gives a very good
summary and application of these techniques. Second, like its predecessor by
Helmut Wielandt on primitive groups of degree $2p$, it can be re-interpreted
as a combinatorial result concerning association schemes whose common
eigenspaces have dimensions of a rather limited form. This result uses neither
the primality of $p$ nor the existence of a permutation group related to the
combinatorial structure. We extract these results and give details of the
related combinatorics.

In memory of Peter Neumann: teacher, colleague, friend

##  1 Introduction

In 1956, Helmut Wielandt [23] proved the following result:

######  Theorem 1.1.

Let $G$ be a primitive permutation group of degree $2p$, where $p$ is prime.
If $G$ is not $2$-transitive, then $n=2a^{2}+2a+1$ for some positive integer
$a$, and $G$ has rank $3$ and subdegrees $a(2a+1)$ and $(a+1)(2a+1)$.

The proof of this theorem is also given in Chapter $5$ of his book [24]. It
illustrates an extension of the methods of Schur rings using representation
theory. He mentioned that, for $a=1$, we have two examples: the groups $S_{5}$
and $A_{5}$, acting on the set of $2$-element subsets of $\\{1,\ldots,5\\}$.

Now it is possible to show that there are no others. For example, using the
Classification of Finite Simple Groups, all the finite primitive rank $3$
permutation groups have been determined [11, 13, 15], and the observation can
be verified by checking the list.

However, there is more to be said. Wielandt’s proof falls into two parts. The
first involves showing that the permutation character of $G$ decomposes as
$1_{G}+\chi_{1}+\chi_{2}$, where $1_{G}$ is the principal character of $G$ and
$\chi_{1},\chi_{2}$ are irreducibles with degrees $p-1$ and $p$. It follows
from this that $G$ has rank $3$ and is contained in the automorphism group of
a strongly regular graph, having the property that the eigenvalues of its
adjacency matrix have multiplicities $1$, $p-1$, and $p$. Now the argument
shows something much more general. Neither the existence of a rank $3$ group
of automorpisms nor the primality of $p$ are needed.

First, a definition: a graph $\Gamma$ is _strongly regular_ with parameters
$(n,k,\lambda,\mu)$ if it has $n$ vertices, every vertex has $k$ neighbours,
and two vertices have $\lambda$ or $\mu$ common neighbours according as they
are joined by an edge or not. Every rank $3$ group of even order is the
automorphism group of a strongly regular graph, but not conversely; many
strongly regular graphs have no non-trivial automorphisms. Any regular graph
has the all-$1$ vector as an eigenvector; a regular graph is strongly regular
if and only if its adjacency matrix, acting on the space orthogonal to the
all-$1$ vector, has just two eigenvalues.

######  Theorem 1.2.

Let $\Gamma$ be a strongly regular graph on $2n$ vertices, with the property
that the eigenvalues of the adjacency matrix, on the space of vectors
orthogonal to the all-$1$ vector, have dimensions $n-1$ and $n$. Then either

  1. (a)

$\Gamma$ is a disjoint union of $n$ complete graphs of size $2$, or the
complement of this; or

  2. (b)

for some positive integer $a$, we have $n=2a^{2}+2a+1$, and up to
complementation the parameters of the graph $\Gamma$ are given by

$n=(2a+1)^{2}+1,\quad k=a(2a+1),\quad\lambda=a(a+2),\quad\mu=(a+1)^{2}.$

We are not aware of who first pointed this out. The result is given, for
example, as Theorem 2.20 in [1].

In the case $a=1$, the complementary strongly regular graphs are the line
graph of the complete graph $K_{5}$ and the Petersen graph. But, unlike in
Wielandt’s case, there are many others. For example, suppose that there exists
a Steiner system $S(2,a+1,2a^{2}+2a+1)$. Then the strongly regular graph whose
vertices are the blocks, two vertices adjacent if the corresponding blocks
intersect, has the parameters given in the theorem. For example, when $a=2$,
the two Steiner triple systems on $13$ points give non-isomorphic strongly
regular graphs on $26$ vertices. (We discuss examples further in the last
section.)

Now to the subject of this paper. In 1969, Peter Neumann wrote a long paper
[16] extending Wielandt’s result from $2p$ to $3p$, where $p$ is prime. His
conclusion is that, if such a group is not $2$-transitive, then $p$ is given
by one of three quadratic expressions in a positive integer $a$, or one of
three sporadic values; the rank is at most $4$, and the subdegrees are given
in each case.

Like Wielandt’s, Neumann’s proof falls into two parts: first find the
decomposition of the permutation character, and then in each case find the
combinatorial implications for the structure acted on by the group. In
contrast to Wielandt, the first part is much easier, since in the intervening
time, Feit [3] had given a characterisation of groups with order divisible by
$p$ having a faithful irreducible representation of degree less than $p-1$. On
the other hand, the second part is much harder; rather than just one possible
decomposition of the permutation character, he finds eight potential
decompositions, some of which require many pages of argument.

Again like Wielandt’s, Neumann’s conclusions have been superseded by results
obtained using the classification of finite simple groups. For example, all
the primitive permutation groups of odd degree have been classified [10, 14].

The paper was never published. It happened that both Leonard Scott and Olaf
Tamaschke had produced similiar results. There was a plan for Neumann and
Scott to collaborate on a joint paper, but for unknown reasons this never
happened. The authors are grateful to Leonard Scott [21] for providing a scan
of Peter Neumann’s original typescript together with some historical material
about the proposed collaboration. The second author has re-typed the paper and
posted it on the arXiv [17].

Our task is to produce a combinatorial version of this, as we have seen for
Wielandt’s theorem. We give some historical background to the theorem with
some comments on the place of Neumann’s paper in the introduction of
combinatorial methods into the study of permutation groups, and to check in
detail that his arguments give combinatorial results which do not depend on
either the existence of a primitive group or the primality of $p$. Indeed we
find some families of parameters which do not occur in Neumann’s case since
the number of vertices is even.

##  2 History

The 1960s saw a unification of combinatorial ideas which had been developed
independently in three different areas of mathematics. In statistics, R C.
Bose and his colleagues and students developed the concept of an _association
scheme_. Extracting information from experimental results requires inversion
of a large matrix, and Bose realised that the task would be much simpler if
the matrix belonged to a low-dimensional subalgebra of the matrix algebra;
requiring entries to be constant on the classes of an association scheme
achieves this. In the former Soviet Union, Boris Weisfeiler and his colleagues
were studying the graph isomorphism problem, and developed the concept of a
_cellular algebra_ , an isomorphism invariant of graphs, to simplify the
problem, and an algorithm, the _Weisfeiler–Leman algorithm_ , to construct it.
In Germany, Helmut Wielandt was extending the method of _Schur rings_ to study
permutation groups with a regular subgroup; by using methods from
representation theory he was able to dispense with the need for the regular
subgroup. These techniques were further developed by Donald Higman in the USA,
under the name _coherent configuration_.

The three concepts are very closely related. We begin with Higman’s
definition. A _coherent configuration_ consists of a set $\Omega$ together
with a set $\\{R_{1},R_{2},\ldots,R_{r}\\}$ of binary relations on $\Omega$
with the properties

  1. (a)

$\\{R_{1},\ldots,R_{r}\\}$ form a partition of $\Omega\times\Omega$;

  2. (b)

there is a subset of $R_{1},\ldots,R_{r}$ which is a partition of the
_diagonal_ $\\{(\omega,\omega):\omega\in\Omega\\}$ of $\Omega^{2}$;

  3. (c)

the converse of each relation $R_{i}$ is another relation in the set;

  4. (d)

for any triple $(i,j,k)$ of indices, and any $(\alpha,\beta)\in R_{k}$, the
number $p_{ij}^{k}$ of $\gamma\in\Omega$ such that $(\alpha,\gamma)\in R_{i}$
and $(\gamma,\beta)\in R_{j}$ depends only on $(i,j,k)$ and not on the choice
of $(\alpha,\beta)\in R_{k}$.

The number $r$ is the _rank_ of the configuration. Combinatorially, a coherent
configuration is a partition of the edge set of the complete directed graph
with loops.

A coherent configuration is _homogeneous_ if the diagonal is a single
relation. In the group case, this means that the group is transitive. All the
configurations in this paper will be homogeneous.

If $G$ is a permutation group on $\Omega$, and we take the relations $R_{i}$
to be the orbits of $G$ on $\Omega^{2}$, we obtain a coherent configuration.
This was Higman’s motivating example, which he called the _group case_. Not
every coherent configuration falls into the group case; indeed, our task is to
extend Neumann’s results from the group case to the general case.

The notion of a cellular algebra is the same apart from an inessential small
difference (the diagonal is replaced by some equivalence relation).
Association schemes form a special case, where all the relations $R_{i}$ are
symmetric. It follows that, in an association scheme, the diagonal is a single
relation. (Statisticians deal with symmetric matrices, for example covariance
matrices.)

A coherent configuration with rank $2$ is _trivial_ : one relation is the
diagonal, the other is everything else. For rank $3$, we can suppose without
loss that $R_{1}$ is the diagonal. There are then two possibilities:

  * •

$R_{3}$ is the converse of $R_{2}$. Then $R_{2}$ is a _tournament_ (an
orientation of the edges of the complete graph on $\Omega$); condition (d)
shows that it is a _doubly regular_ tournament [19].

  * •

$R_{2}$ and $R_{3}$ are symmetric. Then each is the edge set of a graph, and
these graphs are _strongly regular_ [1, Chapter 2].

The definition of coherent configuration has an algebraic interpretation. Let
$A_{i}$ be the _adjacency matrix_ of the relation $R_{i}$, the
$\Omega\times\Omega$ matrix with $(\alpha,\beta)$ entry $1$ if
$(\alpha,\beta)\in R_{i}$. Then $A_{1},\ldots,A_{r}$ are zero-one matrices
satisfying the following conditions:

  1. (a)

$A_{1}+\cdots+A_{r}=J$, the all-$1$ matrix;

  2. (b)

there is a subset of these matrices whose sum is the identity $I$;

  3. (c)

for any $i$ there is a $j$ such that $A_{i}^{\top}=A_{j}$;

  4. (d)

$\displaystyle{A_{i}A_{j}=\sum_{k=1}^{r}p_{ij}^{k}A_{k}}$.

Condition (d) says that the linear span over $\mathbb{C}$ of
$A_{1},\ldots,A_{r}$ is an algebra (closed under multiplication), and
condition (c) implies that this algebra is semi-simple. In the group case, it
is the _centraliser algebra_ of the permutation group, consisting of matrices
which commute with every permutation matrix in the group. In the case of
association schemes, it is known as the _Bose–Mesner algebra_ of the scheme.
In this case, all the matrices are symmetric, the algebra is commutative, and
we can work over $\mathbb{R}$. In the group case, the centraliser algebra is
commutative if and only if the permutation character is multiplicity-free.

If the algebra is commutative, then the matrices are simultaneously
diagonalisable; the common eigenspaces are called the _strata_ of the
configuration. In the rank $3$ case where we have a strongly regular graph and
its complement, the stratum dimensions are simply the multiplicities of the
eigenvalues. We occasionally extend the use of the word “stratum” to the non-
commutative case, where it means a submodule for the algebra spanned by the
matrices which is maximal with respect to being a sum of isomorphic
submodules.

In all cases which arise in Peter Neumann’s paper, the algebra turns out to be
commutative, although there are two potential cases where the permutation
character is not multiplicity-free; both of these are eliminated.

It seems clear to the authors that, had the paper been published in 1969, it
would have been very influential: it provides both a clear account of the
theory and how it can be used to study permutation groups, and also a non-
trivial example of such an application. The second author of the present paper
read it at the start of his DPhil studies in Oxford under Peter Neumann’s
supervision, and considers himself fortunate to have been given such a good
grounding in this area; he has worked on the interface of group theory and
combinatorics ever since.

##  3 The results

The main theorems in this paper are the following. They are numbered to
correspond to the eight cases in Neumann’s paper.

######  Theorem 3.1.

Let $\mathcal{A}=\\{I_{n},A_{1},A_{2}\\}$ be a coherent configuration of
$n\times n$ matrices. If the eigenvalues of $A_{1}$ have multiplicities
$1,\frac{n-1}{2},\frac{n-1}{2}$ then one of the two following cases must hold:

  * •

$n\equiv 1\pmod{4}$ and $A_{1}$ and $A_{2}$ are the adjacency matrices of
conference graphs;

  * •

$n\equiv 3\pmod{4}$ and $A_{1}$ and $A_{2}$ are the adjacency matrices of
doubly regular tournaments.

######  Theorem 3.2.

Let $G$ be a strongly regular graph on $3n$ vertices. If the multiplicities of
the eigenvalues of $G$ are $1,n,2n-1$ then $G$ or its complement have the
following parameters in terms of a non-negative integer $a$:

  * •

$3n=144a^{2}+54a+6$, $k_{1}=48a^{2}+14a+1$,
$\lambda=16a^{2}+6a,\mu=16a^{2}+2a$;

  * •

$3n=144a^{2}+90a+15$,
$k_{1}=48a^{2}+34a+6,\lambda=16a^{2}+10a+1,\mu=16a^{2}+14a+3$;

  * •

$3n=144a^{2}+198a+69$,
$k_{1}=48a^{2}+62a+20,\lambda=16a^{2}+22a+7,\mu=16a^{2}+18a+5$;

  * •

$3n=144a^{2}+234a+96$,
$k_{1}=48a^{2}+82a+35,\lambda=16a^{2}+26a+10,\mu=16a^{2}+30a+14$.

######  Theorem 3.3.

Let $G$ be a strongly regular graph on $3n$ vertices. If the multiplicities of
the eigenvalues of $G$ are $1,2n,n-1$ then either $G$ or its complement is a
disjoint union of $n$ copies of $K_{3}$ or $G$ or its complement have the
following parameters for some non-negative integer $a$:

  * •

$3n=9a^{2}+9a+3$, $k_{1}=3a^{2}+5a+2,\lambda=a^{2}+3a+1,\mu=(a+1)^{2}$;

  * •

$3n=9a^{2}+9a+3$, $k_{1}=3a^{2}+a,\lambda=a^{2}-a-1,\mu=a^{2}$.

######  Theorem 3.4.

Let $\mathcal{A}=\\{I_{3n},A_{1},A_{2},A_{3}\\}$ be a coherent configuration
of $3n\times 3n$ matrices. If the multiplicities of the eigenvalues of
$A_{1},A_{2},A_{3}$ are $1,n,n,n-1$ then one of the following hold:

  * •

$A_{2}=A_{3}^{T}$ and the row sums of $A_{1},A_{2},$, and $A_{3}$ are
$n-2a-1,n+a$, and $n+a$ respectively for some even integer $a$;

  * •

$A_{2}=A_{3}^{T}$ and the row sums of $A_{1},A_{2}$, and $A_{3}$ are
$n+2a+1,n-a-1$, and $n-a-1$ respectively for some odd integer $a$;

  * •

All matrices are symmetric and the row sums of $A_{1},A_{2},A_{3}$ are
$n+2a+1,n-a-1$, and $n-a-1$ respectively for some non-negative integer $a$.

######  Theorem 3.5.

There exists no coherent configuration
$\mathcal{A}=\\{I_{3n},A_{1},A_{2},A_{3},A_{4},A_{5}\\}$ of $3n\times 3n$
matrices such that the multiplicities of the eigenvalues of
$A_{1},\ldots,A_{5}$ are $1,n,n,n-1$.

######  Theorem 3.6.

There is no strongly regular graph on $3n$ vertices with eigenvalue
multiplicities $1,n+1,2(n-1)$.

######  Theorem 3.7.

Let $\mathcal{A}=\\{I_{3n},A_{1},A_{2},A_{3}\\}$ be a coherent configuration
of $3n\times 3n$ matrices. If the eigenvalues of $A_{1},\ldots,A_{3}$ have
multiplicities $1,n+1,n-1,n-1$, then $\mathcal{A}$ is an association scheme
and one of the following hold:

  * •

$n=7$ and the row sums of $A_{1},A_{2},A_{3}$ are $4,8$, and $8$;

  * •

$n=19$ and the row sums of $A_{1},A_{2},A_{3}$ are $6,20$, and $30$;

  * •

$n=31$ and the row sums of $A_{1},A_{2},A_{3}$ are $32,40$, and $20$.

######  Theorem 3.8.

There exists no coherent configuration
$\mathcal{A}=\\{I_{3n},A_{1},A_{2},A_{3},A_{4},A_{5}\\}$ of $3n\times 3n$
matrices, where $A_{1},\ldots,A_{5}$ have eigenvalues with multiplicities
$1,n+1,n-1,n-1$.

##  4 The proofs

###  4.1 A lemma

We start with a lemma that will be used throughout the paper.

######  Lemma 4.1.

Let $\mathcal{A}$ be a homogeneous coherent configuration on $n$ points.
Suppose that the dimension of a non-trivial stratum for $\mathcal{A}$ is at
least $n/3-1$. Then one of the following happens:

  1. (a)

One of the relations in $\mathcal{A}$ has at least $n/3$ connected components.

  2. (b)

Any matrix in $\mathcal{A}$ has the property that any eigenvalue $\lambda$
apart from the row sum $r$ satisfies $|\lambda|<r$.

###### Proof.

We use the _Perron–Frobenius Theorem_ , see [4]. For any non-negative matrix
$A$, one of the following holds:

  * •

Under simultaneous row and column permutations, $A$ is equivalent to a matrix
of the form $\begin{pmatrix}B&O\\\ O&C\\\ \end{pmatrix}$. In our case the
constancy of the row sum $r$ means that $r$ has multiplicity equal to the
number of connected components; so there are at least $n/3$ connected
components, and (a) holds.

  * •

$A$ is decomposable, that is, under simultaneous row and column permutations
it is equivalent to a matrix of the form $\begin{pmatrix}B&X\\\ O&C\\\
\end{pmatrix}$, where $X\neq O$. But this contradicts the fact that the row
sum is constant.

  * •

$A$ is imprimitive, that is, equivalent under simultaneous row and column
permutations to a matrix of the form

$\begin{pmatrix}O&B_{1}&\ldots&\ldots&0\\\ O&O&B_{2}&\ldots&O\\\
\ldots&\ldots&\ldots&\ldots&\ldots\\\ B_{t}&O&O&\ldots&O\end{pmatrix}.$

But then $r\mathrm{e}^{2\pi\mathrm{i}k/t}$ is a simple eigenvalue for
$k=0,1,\ldots,t-1$, contrary to assumption.

  * •

$A$ is primitive. Then the Perron–Frobenius Theorem asserts that there is a
single eigenvalue with largest absolute value, as required.

∎

###  4.2 Proof of Theorem 3.1

We first prove a lemma about strongly regular graphs that will be used in the
proof of Theorem 3.1.

######  Lemma 4.2.

Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ and
let $k,r,s$ be the eigenvalues of the adjacency matrix of $G$. If $r$ and $s$
have equal multiplicities then $G$ is a conference graph.

###### Proof.

It is known for a strongly regular graphs that the multiplicities of $r$ and
$s$ are

$f,g=\frac{1}{2}(n-1\pm\frac{(n-1)(\mu-\lambda)-2k}{\sqrt{(\mu-\lambda)^{2}-4(k-\mu)}})$

respectively. Hence, if $f=g$ then it follows that

$(n-1)(\mu-\lambda)-2k=-(n-1)(\mu-\lambda)+2k\Rightarrow
2k=(n-1)(\mu-\lambda)$

and thus $G$ is a conference graph, as required. Moreover,
$f=g=\frac{n-1}{2}$. ∎

###### Proof of Theorem 3.1.

Since $\mathcal{A}$ is a coherent configuration, $A_{0}+A_{1}+A_{2}=J_{n}$ and
moreover $A_{i}^{T}=A_{j}$ for $i,j\in\\{1,2\\}$. Hence, there are two
possibilities. Either $A_{i}=A_{i}^{T}$ for $i\in\\{1,2\\}$ or
$A_{i}=A_{j}^{T}$ for $i,j\in\\{1,2\\}$ and $i\neq j$.

In the first case, the graphs with adjacency matrices $A_{1}$ and $A_{2}$ are
undirected. Moreover, since $A_{1}$ and $A_{2}$ are symmetric, $\mathcal{A}$
is an association scheme and hence those graphs are strongly regular and one
is the complement of the other. It follows by Lemma 4.2 that $A_{1}$ and
$A_{2}$ are the adjacency matrices of conference graphs and in fact two copies
of the same conference graph. Moreover, for a conference graph to exist, it is
known that $n\equiv 1\pmod{4}$.

In the second case, since $\mathcal{A}$ is a coherent configuration, it
follows that $A_{1}$ and $A_{2}$ must have constant row and column sums and
hence their digraphs are regular. Let $G_{1},G_{2}$ be the digraphs with
adjacency matrices $A_{1}$ and $A_{2}$ respectively and $V$ be the vertex set
of those digraphs. For $u,v\in V$, we write $u\rightarrow_{G_{1}}v$ if $v$ is
an out-neighbour of $u$ in $G_{1}$ and similarly $u\rightarrow_{G_{2}}v$ if
$v$ is an out-neighbour of $u$ in $G_{2}$. Since $A_{1}+A_{2}=J-I$, it follows
that $u\rightarrow_{G_{1}}v\iff u\not\rightarrow_{G_{2}}v$ and vice versa and
also that either $(A_{k})_{ij}=1$ or $(A_{k})_{ji}=1$ for $k\in\\{1,2\\}$.
Hence, $G_{1}$ and $G_{2}$ are regular tournaments. Also, notice that since
$\mathcal{A}$ is a coherent configuration, it follows that for
$m,n\in\\{1,2\\},m\neq n$, there exists a constant $p_{mn}^{m}$ such that for
any $i,j\in V$, such that $(A_{m})_{ij}=1$,
$|\\{k\mid(A_{m})_{ik}=1,(A_{n})_{kj}=1\\}|=|\\{k\mid(A_{m})_{ij}=1,(A_{m})_{jk}=1\\}|=p_{mn}^{m}$.
Hence, both $G_{1}$ and $G_{2}$ are doubly regular, and it is known that
$n\equiv 3\pmod{4}$ for doubly regular tournaments. ∎

###  4.3 Proof of Theorem 3.2

###### Proof.

Let $A_{1}$ be the adjacency matrix of $G$ and $A_{2}$ be the adjacency matrix
of its complement. Since $G$ is strongly regular, the eigenvalues of $A_{1}$
and $A_{2}$ have the same multiplicities. Moreover, if $A_{1}$ has eigenvalues
$k_{1},r_{1},s_{1}$ then $A_{2}$ has eigenvalues
$k_{2}=3n-k_{1}-1,r_{2}=-1-r_{1},s_{2}=-1-s_{1}$. We know that for
$i\in\\{1,2\\}$

$Tr(A_{i})=k_{i}+nr_{i}+(2n-1)s_{i}=0$

Reducing modulo $n$ gives that $k_{i}\equiv s_{i}\pmod{n}$. Therefore, since
by Lemma 4.1 $k_{i}>s_{i}$, it follows that $k_{i}-s_{i}=\epsilon_{i}n$ for
$\epsilon_{i}\in\\{1,2\\}$. Therefore,

$n_{1}+n_{2}-s_{1}-s_{2}=(\epsilon_{1}+\epsilon_{2})n\Rightarrow
3n-1-s_{1}+1+s_{1}=(\epsilon_{1}+\epsilon_{2})n\Rightarrow\epsilon_{1}+\epsilon_{2}=3.$

Assume without loss of generality that $\epsilon_{1}=1$ and $\epsilon_{2}=2$.
Then, $k_{1}=n+s_{1}$ and also

$n+s_{1}+nr_{1}+(2r-1)s_{1}=0\Rightarrow r_{1}=-1-2s_{1}.$

Also, we have that

$Tr(A_{1}^{2})=k_{1}^{2}+nr_{1}^{2}+(2n-1)s_{1}^{2}=3nk_{1}.$

Appropriate substitution gives

$(n+s_{1})^{2}+n(1+2s_{1})^{2}+(2n-1)s_{1}^{2}=3n(n+s_{1})$

which simplifies to

$6s_{1}^{2}+3s_{1}+1-2n=0.$

Therefore,

$s_{1}=\frac{1}{4}\left(-1\pm\sqrt{\frac{16n-5}{3}}\right)$

Since $G$ is strongly regular and its eigenvalues have different
multiplicities, it is not a conference graph, and hence its eigenvalues are
integer. Hence, $16n-5=3b^{2}$ for some non-negative integer $b$. This gives
us that $3b^{2}+5\equiv 0\pmod{16}$. It follows that $b=3,5,11$ or
$13\pmod{16}$. We therefore need to examine the following four cases:

Case 1: $b=16a+3$.

In this case we get:

$16n=3(16a+3)^{2}+5\Rightarrow n=48a^{2}+18a+2.$

and $s_{1}=-4a-1$. Notice that only the negative solution works, since $16a+2$
is not divisible by 4. Consequently $k=48a^{2}+14a+1$. We also get
$r_{1}=8a+1$

Now, using the formulae for the eigenvalues of strongly regular graphs, namely

$r_{1},s_{1}=\frac{1}{2}\left((\lambda-\mu)\pm\sqrt{(\lambda-\mu)^{2}+4(k_{1}-\mu)}\right)$

we get

$\displaystyle\lambda-\mu=r_{1}+s_{1}$ $\displaystyle
4\mu=(\lambda-\mu)^{2}-(r-s)^{2}+4k.$

Solving this system we obtain $\lambda=16a^{2}+6a$ and $\mu=16a^{2}+2a$.

Case 2: $b=16a+5$.

In this case we get:

$16n=3(16a+5)^{2}+5\Rightarrow n=48a^{2}+3a+5.$

and $s_{1}=4a+1$. Hence, $k=48a^{2}+7a+6$. We also get $r_{1}=-8a-3$
As above, knowing $r_{1},s_{1}$ we can obtain $\lambda$ and $\mu$ which in
this case are equal to $16a^{2}+10a+1$ and $16a^{2}+14a+3$ respectively.

Case 3: $b=16a+11$.

In this case we get:

$16n=3(16a+11)^{2}+5\Rightarrow n=48a^{2}+66a+23.$

and $s_{1}=-4a-3$. Hence, $k=48a^{2}+62a+20$. Also, $r_{1}=8a+5$ and routine
calculation as above gives $\lambda=16a^{2}+22a+7,\mu=16a^{2}+18a+5$.

Case 4: $b=16a+13$.

In this case we get:

$16n=3(16a+13)^{2}+5\Rightarrow n=48a^{2}+78a+32.$

and $s_{1}=4a+3$. Hence, $k=48a^{2}+82a+35$, $r_{1}=-8a-7$,
$\lambda=16a^{2}+26a+10,\mu=16a^{2}+20a+14$. ∎

###  4.4 Proof of Theorem 3.3

###### Proof.

Let $A_{1}$ be the adjacency matrix of $G$ and $A_{2}$ be the adjacency matrix
of its complement. Since $G$ is strongly regular we know that the eigenvalues
of $A_{1}$ and $A_{2}$ have the same multiplicities. Also, if $A_{1}$ has
eigenvalues $k_{1},r_{1},s_{1}$, then $A_{2}$ has eigenvalues
$k_{2}=3n-k_{1}-1,r_{2}=-1-r_{1},s_{2}=-1-s_{1}$. We know that for
$i\in\\{1,2\\}$

$Tr(A_{i})=k_{i}+2nr_{i}+(n-1)s_{i}=0.$

Reducing modulo $n$ gives that $k_{i}\equiv s_{i}\pmod{n}$, and since by Lemma
4.1 either one of $A_{1},A_{2}$ is the disjoint union of $n$ copies of $K_{3}$
or $k_{i}>|s_{i}|$. In the second case, it follows that
$k_{i}-s-i=\epsilon_{i}n$ for $\epsilon_{i}\in\\{1,2\\}$. Also, as before,
$\epsilon_{1}+\epsilon_{2}=3$ and hence we may suppose without loss of
generality that $\epsilon_{1}=1$ and $\epsilon_{2}=2$. Then, $k_{1}=n+s_{1}$
and $r_{1}=\frac{-s_{1}-1}{2}$. We therefore get

$Tr(A_{1}^{2})=(n+s_{1})^{2}+2n\left(\frac{s_{1}+1}{2}\right)^{2}+(n-1)s_{1}^{2}=3n(n+s_{1}).$

and simplifying gives $3s_{1}^{2}=4n-1$. Therefore,

$s_{1}^{2}=\frac{4n-1}{3}.$

We can thus write $s_{1}^{2}$ as $(2a+1)^{2}$ for some $a\geq 0$ and we get

$(2a+1)^{2}=\frac{4n-1}{3}\Rightarrow n=3a^{2}+3a+1$

and $s_{1}=\pm 2a+1$. We therefore get the following cases:

Case 1: $s_{1}=2a+1$.

In this case we get $k_{1}=3a^{2}+5a+2$ and $r_{1}=-a-1$, and computing
$\lambda$ and $\mu$ as in the proof of Theorem 3.2 we obtain
$\lambda=a^{2}+3a+1$ and $\mu=(a+1)^{2}$.

Case 2: $s_{1}=-2a-1$.

Here, routine calculation gives $k_{1}=3a^{2}+a$, $r_{1}=a$,
$\lambda=a^{2}-a-1,\mu=a^{2}$. ∎

###  4.5 Proof of Theorem 3.6

###### Proof.

Suppose for a contradiction that there exists such a strongly regular graph,
and let $A_{1}$ be its adjacency matrix and $A_{2}$ be the adjacency matrix of
its complement and suppose that $k_{1},r_{1},s_{1}$ and $k_{2},r_{2},s_{2}$
are the eigenvalues of $A_{1}$ and $A_{2}$ respectively. Then, for
$i\in\\{1,2\\}$ we get

$Tr(A_{i})=k_{i}+(n+1)r_{i}+2(n-1)s_{i}=0$

and

$Tr(A_{i}^{2})=k_{i}^{2}+(n+1)r_{i}^{2}+(2n-1)s_{i}^{2}=3nk_{i}.$

Reducing modulo $n$ gives

$\displaystyle k_{i}\equiv 2s_{i}-r_{i}\pmod{n}$ $\displaystyle
k_{i}^{2}\equiv 2s_{i}^{2}-r_{i}^{2}\pmod{n}$

Hence, $(2s_{i}-r_{i})^{2}\equiv 2s_{i}^{2}-r_{i}^{2}$. By routine
calculation, it follows that $s_{i}\equiv r_{i}\pmod{n}$ and consequently
$k_{i}\equiv r_{i}\pmod{n}$. Therefore, $k_{i}=\epsilon_{i}n+r_{i}$ and
$s_{i}=\eta_{i}n+r_{i}$ for some $\epsilon_{i},\eta_{i}\in\\{1,2\\}$.

Substituting into the trace equations and reducing modulo $n^{2}$ gives

$\displaystyle\epsilon_{i}n+r_{i}+(n+1)r_{i}+2(n-1)r_{i}-2\eta_{i}n\equiv
0\pmod{p^{2}}$ $\displaystyle
2\epsilon_{i}nr_{i}+r_{i}^{2}+(n+1)r_{i}^{2}+2(n-1)r_{i}^{2}-4r_{i}\eta_{i}n\equiv
3nr_{i}\pmod{p^{2}}.$

We now collect terms and divide by $n$ and we get

$\displaystyle\epsilon_{i}+3r_{i}-2\eta_{i}\equiv 0\pmod{n}$ $\displaystyle
3r_{i}^{2}+r_{i}(2\epsilon_{i}-4\eta_{i}-3)\equiv 0\pmod{n}.$

Since $1+r_{1}+r_{2}=0$ it cannot be the case that both $r_{1}$ and $r_{2}$
are divisible by $n$. Hence, interchanging $A_{1}$ and $A_{2}$ if necessary we
may assume that $r_{1}\not\equiv 0\pmod{n}$. Then,

$\displaystyle 3r_{1}\equiv 2\eta_{1}-\epsilon_{1}\pmod{n}$ $\displaystyle
3r_{1}\equiv 4\eta_{1}-2\epsilon_{1}+3\pmod{n}.$

Eliminating $2\eta_{1}-\epsilon_{1}$ gives $r_{1}\equiv-1\pmod{n}$. Therefore,
since $k_{1}\equiv r_{1}\pmod{n}$, either $k_{1}=n-1$ or $k_{1}=2n-1$. If
$k_{1}=n-1$, then since $r_{1}\equiv s_{1}\equiv-1\pmod{n}$ and by Lemma 4.1
$|r_{1}|<k_{1}$ and $|s_{1}|<k_{1}$, it follows that $r_{1}=s_{1}=-1$.
However, by looking at the formulae for $r_{1}$ and $s_{1}$ for a strongly
regular graph, we deduce that $r_{1}\neq s_{1}$, a contradiction. Similarly,
if $k_{1}=2n-1$, then $k_{2}=n$ which forces $r_{2}=s_{2}=0$, again a
contradiction. Hence, there is no strongly regular graph with those eigenvalue
multiplicities. ∎

###  4.6 Proof of Theorem 3.4

###### Proof.

Let $k_{i},r_{i},s_{i},t_{i}$ be the eigenvalues of $A_{i}$ for
$i\in\\{1,2,3\\}$ with multiplicities $1,n,n,n-1$ respectively. Firstly notice
that $t_{i}$ must be a rational integer and $r_{i}$ and $s_{i}$ must either
both be rational integers or algebraically conjugate algebraic integers. Then,
we get

$\displaystyle Tr(A_{i})=k_{i}+nr_{i}+ns_{i}+(n-1)t_{i}=0$

Hence, $n$ must divide $k_{i}-t_{i}$, and since by Lemma 4.1 $n_{i}>t_{i}$, it
follows that $k_{i}=\epsilon_{i}n+t_{i}$ for some $\epsilon_{i}>0$. Moreover,
by Equation (6.9) in [16], $\epsilon_{1}+\epsilon_{1}+\epsilon_{3}=3$ and
hence $\epsilon_{i}=1$ for all $i\in\\{1,2,3\\}$. Thus, $k_{i}=n+t_{i}$.

There are now two cases to consider. Either all matrices are symmetric or two
of them, say $A_{2}$ and $A_{3}$ without loss of generality are such that
$A_{2}^{T}=A_{3}$. We first consider the second case. In this case the
eigenvalues of $A_{2}$ and $A_{3}$ are the same. Hence, $t_{2}=t_{3}$ and
either $r_{2}=r_{3}$ and $s_{2}=s_{3}$ or $r_{2}=s_{3}$ and $r_{3}=s_{2}$.
Notice that the algebra spanned by the matrices of this coherent configuration
is commutative and therefore $A_{2}$ and $A_{3}$ can be simultaneously
diagonalised. Let $U$ be the matrix that simultaneously reduces $A_{2}$ and
$A_{3}$. If $r_{2}=r_{3}$ and $s_{2}=s_{3}$ then $U^{-1}A_{2}U=U^{-1}A_{3}U$,
which implies that $A_{2}=A_{3}$, a contradiction. Hence, $r_{2}=s_{3}$ and
$r_{3}=s_{2}$.

Now adding $A_{2}$ and $A_{3}$ together produces an association scheme of the
type arising in Theorem 3.3. Hence, $n=3a^{2}+3a+1$ and either $k_{1}=n-2a-1$
and $k_{2}=k_{3}=n+a$ or $k_{1}=n+2a+1$ and $k_{2}=k_{3}=n-a-1$.

We now show that if $k_{1}=n-2a-1$ then $a$ is even and if $k_{1}=n+2a+1$ then
$a$ is odd. In the first case, the remaining eigenvalues of $A_{1},A_{2}$, and
$A_{3}$ are as shown below:

$\displaystyle r_{1}=a,s_{1}=a,t_{1}=-2a-1$ $\displaystyle
r_{2}=r,s_{2}=s,t_{2}=a$ $\displaystyle r_{3}s,s_{3}=r,t_{3}=a.$

where $r+s=-a-1$. Now Equation (6.7) in [16] gives

$rs=\frac{1}{2}(2n-a-a^{2})=\frac{1}{2}(5a+2)(a+1)$

and Equation (6.8) in [16] gives

$3n(n+a)a_{22}^{3}=(n+a)^{3}+nrs(r+s)+(n-1)a^{3}.$

Eliminating $rs$ and simplifying gives $a_{22}^{3}=a^{3}+\frac{3a}{2}$ and
since $a_{22}^{3}\in\mathbb{Z}$, $a$ must be even.

In the second case, the eigenvalues of $A_{1},A_{2}$, and $A_{3}$ are the ones
given below:

$\displaystyle r_{1}=-a-1,s_{1}=-a-1,t_{1}=2a+1$ $\displaystyle
r_{2}=r,s_{2}=s,t_{2}=-a-1$ $\displaystyle r_{3}=s,s_{3}=r,t_{3}=-a-1$

where $r+s=1$ by Equation (6.6) in [16]. Equation (6.7) in [16] gives
$rs=\frac{1}{2}a(5a+3)$ and from Equation (6.8) in [16] we get

$3n(n-a-1)a_{22}^{3}=(n-a-1)^{3}+nrs(r+s)-(n-1)(a+1)^{3}.$

Simplifying gives $a_{22}^{3}=a^{2}+\frac{a-1}{2}$, and since
$a_{22}^{3}\in\mathbb{Z}$, it follows that $a$ is odd, as claimed.

We now consider the symmetric case. We get the following equations

$s_{i}+r_{i}=-1-t_{i}$ (1) $\displaystyle
Tr(A_{i}^{2})=k_{i}^{2}+nr_{i}+ns_{i}+(n-1)t_{i}=3nk_{i}\Rightarrow(t_{i}+n)^{2}+nr_{i}^{2}+ns_{i}^{2}+nt_{i}^{2}-t_{i}^{2}=3n(n+t_{i})\Rightarrow$
$r_{i}^{2}+s_{i}^{2}=-t_{i}^{2}+t_{i}+2n$ (2)

From this we get $2r_{i}s_{i}=1+t_{i}+2t_{i}^{2}+2n$ and hence we deduce that
$s_{i}$ is odd. Also, we can calculate $r_{i}$ and $s_{i}$ and we find that
$r_{i},s_{i}=\frac{1}{2}(-1-t_{i}\pm\sqrt{4n-1-3t_{i}^{2}})$. Without loss of
generality we set

$\displaystyle r_{i}=\frac{1}{2}(-1-t_{i}+\sqrt{4n-1-3t_{i}^{2}})$
$\displaystyle s_{i}=\frac{1}{2}(-1-t_{i}-\sqrt{4n-1-3t_{i}^{2}}).$

Since $A_{i}$ is symmetric for all $i\in\\{1,2,3\\}$, it has real eigenvalues
and therefore

$3t_{i}^{2}\leq 4n-1.$ (3)

Now, from Equation (6.9) in [16] we get

$\begin{cases}t_{1}+t_{2}+t_{3}=-1\\\
\sqrt{4n-1-3t_{1}^{2}}+\sqrt{4n-1-3t_{2}^{2}}+\sqrt{4n-1-3t_{3}^{2}}=0\end{cases}$
(4)

Now eliminating $t_{3}$ and rationalising gives us

$\displaystyle t_{1}^{2}(3t_{2}+2n+1)+t_{1}(3t_{2}^{2}+2nt_{2}+4t_{2}+2n+1)$
$\displaystyle+(2n+1)(t_{2}^{2}+t_{2})-2n(n-1)=0.$

Notice that

$3t_{2}^{2}+2nt_{2}+4t_{2}+2n+1=(3t_{2}+2n+1)(t_{2}+1).$

Therefore, $3t_{2}+2n+1$ divides $(2n+1)(t_{2}^{2}+t_{2})-2n(n-1)$. Now
consider the equation

$2n(2n+1)(t_{2}^{2}+t_{2})-4n(n-1)\equiv 0\pmod{3t_{2}+2n+1}$

If we eliminate $n$ from the equation, we deduce that $3t_{2}+2n+1$ must
divide $3(t_{2}+1)^{2}(2t_{2}+1)$.

Notice that there is complete symmetry between $t_{1},t_{2}$, and $t_{3}$.
Hence, we deduce that

$3(t_{i}+1)^{2}(2t_{i}+1)\equiv 0\pmod{3t_{i}+2n+1}$ (5)

for all $i\in\\{1,2,3\\}$.

Using the equation for $Tr(A_{i}^{3})$ we deduce that $3nk_{i}$ must divide
$k_{i}^{3}+n(r_{i}^{3}+s_{i}^{3})+(n-1)t_{i}^{3}$. Substitution for
$k_{i},r_{i},s_{i}$ in terms of $t_{i}$ and algebraic manipulation gives

$2n^{2}-6n-6t_{i}^{2}+2t_{i}^{3}+(1+t_{i})(4t_{i}^{2}-t_{i}+1)\equiv
0\pmod{6(n+t_{i})}.$ (6)

Reducing modulo $2n+t_{i}$, we deduce that $2n^{2}-6n\equiv 2t_{i}(t_{i}+3)$
and simplifying gives

$(t_{i}+1)(2t_{i}+1)(3t_{i}+1)\equiv 0\pmod{2n+t_{i}}.$ (7)

Since $t_{1}+t_{2}+t+3=-1$ and $t_{i}\in\mathbb{Z}$ for all $i\in\\{1,2,3\\}$,
not all them can be negative. Let $b$ be one of them such that $b\geq 0$.
Then, it follows by 5 and 7 that

$\displaystyle(b+1)(2b+1)(3b+1)=u.(2n+b)$
$\displaystyle(b+1)(2b+1)(3b+3)=v.(2n+3b+1)$

for some $u,v\in\mathbb{Z}$. Now subtracting gives

$2(b+1)(2b+1)=2(v-u)(n+b)+v(b+1)$

.

Now set $w=v-u$. We want to show that $w=0$. Firstly notice that

$\displaystyle
w=(b+1)(2b+1)\left(\frac{3b+3}{2n+3b+1}-\frac{3b+1}{2(n+b)}\right)$ (8)
$\displaystyle=\frac{(b+1)(2b+1)(4n-1-3b^{2})}{2(2n+3b+1)(n+b)}$ (9)

and hence, by Equation 3, $w\geq 0$. Rearranging gives

$3(b+1)^{3}(2b+1)=(2n+3b+1)\left(2(b+1)(2b+1)-2w(n+b)\right).$

Setting $n+b=x$ and refactorising we get the following quadratic in terms of
$x$:

$4wx^{2}-2(n+1)(4b+2-w)x+(b+1)^{2}(2b+1)(3b+1)=0.$

By definition $x$ is real and hence, the discriminant of this quadratic must
be non-negative. Therefore,

$4(b+1)^{2}(4b+2-w)^{2}-16w(b+1)^{2}(2b+1)(3b+1)\geq 0$

and hence

$\displaystyle(4b+2-w)^{2}\geq 4w(2b+1)(3b+1)$ (10)
$\displaystyle=w(4b+2)(6b+2).$ (11)

By 8 we have that $w<2b+1$. Now since $w\geq 0$ it follows that
$2b+1<4b+2-w\leq 4b+2$. Now, by 10, we get that $w\leq 0$ and hence $w=0$, as
claimed. Therefore, by 8 $4n-1=3b^{2}$ and hence $b$ must be odd. We therefore
set $b=2a+1$ for $a\geq 0$ and it follows that $n=3a^{2}+3a+1$. Now suppose
without loss of generality that $t_{1}$ was $b$. Then from 4

$t_{2}^{2}=t_{3}^{2}$

and therefore

$t_{2}=\pm t_{3}.$

But we know that $t_{2}+t_{3}=-1-t_{1}\neq 0$ and hence

$t_{2}=t_{3}=\frac{-1-t_{1}}{2}.$

Hence, $t_{1}=2a+1,t_{2}=t_{3}=-a-1$.

Moreover, since we’ve shown that $v_{i}$ is odd, $a$ must be even and

$k_{1}=n+2a+1$ $k_{2}=k_{3}=n-a-1$

as required. ∎

###  4.7 Proof of Theorem 3.5

###### Proof.

Let $k_{i},r_{i},s_{i},t_{i}$ be the eigenvalues of $A_{i}$ for
$i\in\\{1,\ldots,5\\}$ with multiplicities $1,n,n,n-1$ respectively. If the
matrices $\Theta_{i,1}$ are as in [16], then they must be $2\times 2$ matrices
with eigenvalues $r_{i},s_{i}$, where $r_{i}$ and $s_{i}$ are the eigenvalues
of $A_{i}$ with multiplicity $n$. We know that $r_{i},s_{i}$ must necessarily
be rational integers. Now from the linear trace equation

$Tr(A_{i})=k_{i}+n(r_{i}+s_{i})+(n-1)t_{i}$

we deduce that $n$ must divide $k_{i}-t_{i}$ and since by Lemma 4.1
$|t_{i}|<k_{i}$, it follows that $k_{i}=\epsilon_{i}n+t_{i}$ for
$\epsilon_{i}\geq 1$ for all $i$. Therefore, $\sum_{i=1}^{5}\epsilon_{i}\geq
5$. On the other hand,

$3n-1=\sum_{i=1}^{5}k_{i}=(\sum_{i=1}^{5}\epsilon_{i})n+\sum_{i=1}^{5}t_{i}=(\sum_{i=1}^{5}\epsilon_{i})n-1$

and hence $\sum_{i=1}^{5}\epsilon_{i}=3$, a contradiction. Therefore, this
type of coherent configuration cannot exist. ∎

###  4.8 Proof of Theorems 3.7 and 3.8

In this section we deal with the cases arising in Theorems 3.7 and 3.8
together. We prove both statements through a series of lemmas that eliminate
the case arising in Theorem 3.8 and force the parameters stated in Theorem
3.7.

######  Lemma 4.3.

If $\mathcal{A}=\\{A_{1},A_{2},A_{3},A_{4}\\}$ is a homogeneous coherent
configuration of rank 4, where its matrices have eigenvalue multiplicities
$1,n+1,n-1$, and $n-1$, then all matrices are symmetric.

###### Proof.

Suppose for a contradiction that this is not the case. Then, since
$\mathcal{A}$ is a homogeneous coherent configuration, one of the matrices say
$A_{1}$ must be symmetric and $A_{2},A_{3}$ are such that $A_{2}^{T}=A_{3}$.
Then, $A_{2}$ and $A_{3}$ would have the same eigenvalues. Let
$k_{i},r_{i},s_{i},t_{i}$ for $i\in\\{1,2,3\\}$ be the eigenvalues of
$A_{1},A_{2},A_{3}$ respectively with multiplicities $1,n+1,n-1,n-1$
respectively. Then, since $A_{2}=A_{3}^{T}$, $A_{2}$ and $A_{3}$ have the same
eigenvalues with the same multiplicities. Hence, $s_{2}+t_{2}=s_{3}+t_{3}$.
But then, since by Equation (6.9) in [16]

$\displaystyle s_{1}+s_{2}+s_{3}=-1$ $\displaystyle t_{1}+t_{2}+t_{3}=-1$

it follows that $s_{1}=t_{1}$. However, Theorem 3.6 such a matrix cannot
exist, a contradiction. Therefore, all matrices of $\mathcal{A}$ must be
symmetric. ∎

For the remainder of the section, given a coherent configuration $\mathcal{B}$
we consider the association scheme $\mathcal{A}$ arising by adding every non-
symmetric matrix and its transpose together to make a symmetric matrix. In
this case notice that if $B_{i}$ has eigenvalues
$n_{i},\lambda_{i},\mu_{i},\nu_{i}$ then $A_{i}=B_{i}+B_{i}^{T}$ has
eigenvalues $k_{i}=2n_{i},r_{i}=2\lambda_{i},s_{i}=2\mu_{i},t_{i}=2\nu_{i}$
again with eigenvalue multiplicities $1,n+1,n-1,n-1$ respectively.

######  Lemma 4.4.

If $\mathcal{A}$ is as defined above, then $k_{i}=\epsilon_{i}(n-1)-2r_{i}$
for some $\epsilon_{i}\leq 0$ for all $i$. Moreover, $\sum\epsilon_{i}=3$.

###### Proof.

By the linear trace relation for $A_{i}$ we get

$Tr(A_{i})=k_{i}+(n+1)r_{i}+(n-1)(s_{i}+t_{i})$

Hence, $k_{i}\equiv-2r_{i}\pmod{n-1}$ and we can write

$k_{i}=\epsilon_{i}(n-1)-2r_{i}$

as claimed.

Also, notice that

$3n-1=\sum_{i}k_{i}=(n-1)\sum_{i}\epsilon_{i}-2\sum_{i}r_{i}.$

Since by Equation (6.9) in [16] $\sum_{i}r_{i}=-1$, it follows that
$\sum_{i}\epsilon_{i}=3$.

Now suppose for a contradiction that $\epsilon_{i}<0$. Since $k_{i}\geq 0$ it
follows that $r_{i}<0$. In particular, since by Lemma 4.1 $|r_{i}|<k_{i}$ we
have that $-r_{i}<(n-1)\epsilon_{i}-2r_{i}$ and hence $|r_{i}|>n-1$ and thus
$|r_{i}|\geq n$. By the quadratic trace relation we get

$k_{i}^{2}+(n+1)r_{i}^{2}\leq Tr(A_{i}^{2})=3nk_{i}.$

Hence, $(n+1)r_{i}^{2}\leq k_{i}(3n-k_{i})$, and basic calculus shows that
$k_{i}(3n-k_{i})$ is maximised at $k_{i}=\frac{2n}{2}$. Hence,

$nr_{i}<(n+1)r_{i}\leq\left(\frac{3n}{2}\right)^{2}.$

Dividing through by $n$ and applying sqare roots gives us
$|r_{i}|<\frac{3\sqrt{n}}{2}<n$, a contradiction. Hence $\epsilon_{i}>0$ for
all $i$. ∎

Now considering the quadratic trace equation again and reducing modulo $n-1$
we get

$Tr(A_{i}^{2})=k_{i}^{2}+(n+1)r_{i}^{2}+(n-1)(\lambda_{i}^{2}+\mu_{i}^{2})=3nk_{i}\Rightarrow$
$(-2r_{i})^{2}+2r_{i}^{2}=-6r_{i}\Rightarrow 6r_{i}(r_{i}+1)\equiv
0\pmod{n-1}.$

We now show that in fact $n-1$ divides $3r_{i}(r_{i}+1)$.

######  Lemma 4.5.

If $r_{i}$ is as defined above, then $n-1$ divides $3r_{i}(r_{i}+1)$.

###### Proof.

The trace equations give

$s_{i}+t_{i}=-\epsilon_{i}-r_{i}$
$(n-1)(s_{i}^{2}+t_{i}^{2})=3n(\epsilon_{i}(n-1)-2r_{i})-(\epsilon_{i}(n-1)-2r_{i})^{2}-(n+1)r_{i}^{2}$

Now $s_{i}t_{i}$ is a rational integer by assumption and also
$2s_{i}t_{i}=(s_{i}+t_{i})^{2}-(s_{i}^{2}+t_{i}^{2})$. Calculating modulo
$2(n-1)$ we get

$\displaystyle
0\equiv(n-1)(\epsilon_{i}+r_{i})^{2}-3n(\epsilon_{i}(n-1)-2r_{i})-(\epsilon_{i}(n-1)-2r_{i})^{2}-(n+1)r_{i}^{2}$
$\displaystyle\equiv(n-1)(\epsilon_{i}^{2}+r_{i}^{2})-\epsilon_{i}(n-1)+6r_{i}+4r_{i}^{2}+(n-1)r_{i}^{2}+2r_{i}^{2}$
$\displaystyle\equiv(n-1)(\epsilon_{i}^{2}-\epsilon_{i})+6r_{i}+6r_{i}^{2}.$

Since $\epsilon_{i}^{2}-\epsilon_{i}$ is a product of consecutive integers it
is even and hence $2(n-1)$ must divide $6r_{i}(r_{i}+1)$ and hence $n-1$
divides $3r_{i}(r_{i}-1)$, as claimed. ∎

We now prove another inequality that we will use later.

######  Lemma 4.6.

$\epsilon_{i}(n-1)(6n-2\epsilon_{i}n+\epsilon_{i})-6r_{i}(2n-\epsilon_{i}n+\epsilon_{i})-(3n+9)r_{i}^{2}\geq
0$

###### Proof.

Consider the quadratic equation whose roots are $s_{i}$ and $t_{i}$. Since
$s_{i}$ and $t_{i}$ are real, it follows that the discriminant of this
equation, namely $(s_{i}+t_{i})^{2}-4s_{i}t_{i}=(s_{i}-t_{i})^{2}$ is non-
negative. Notice that
$(s_{i}-t_{i})^{2}=2(s_{i}^{2}+t_{i}^{2})-(s_{i}+t_{i})^{2}$ and hence using
the trace equations we get

$6n(\epsilon_{i}(n-1)-2r_{i})-2(\epsilon_{i}(n-1)-2r_{i})^{2}-2(n-1)r_{i}^{2}-(n-1)(\epsilon_{i}+r_{i})^{2}\geq
0.$

This can be rearranged to give the required statement. ∎

From Lemma 4.4 we know that either one of the $\epsilon_{i}$s is zero say
$\epsilon_{1}$ without loss of generality, or there are just three non-
identity matrices and $\epsilon_{1}=\epsilon_{2}=\epsilon_{3}=1$. We first
consider the former case.

######  Proposition 4.7.

If $\epsilon_{1}=0$, then $n=7$ or $19$ and the coherent configurations are
symmetric.

###### Proof.

If $\epsilon_{1}=0$, then $k_{1}=-2r_{1}$ and since $k_{1}>0$, it follows that
$r_{1}<0$. Using Lemma 4.6 we get

$-12nr_{1}-(3n+9)r_{1}^{2}\geq 0$

and hence $r_{1}\geq\frac{-4n}{n+3}>-3$.

Therefore, $r_{1}=-3$ or $r_{1}=-2$, or $r_{1}=-1$ and $k_{1}=6,4$, or $2$.
Consider the case where $k_{1}=2$ and $r_{1}=-1$. The trace equations give us

$s_{1}+t_{1}=1$ $(n-1)(s_{1}^{2}+t_{1}^{2})=5n-5\Rightarrow
s_{1}^{2}+t_{1}^{2}=5.$

Therefore, $s_{1}$ and $t_{1}$ are equal to $2$ and $-1$ respectively.
However, $r_{1}=-1$ and $k_{1}=2$ but by Lemma 4.1 $|s_{1}|<k_{1}$, a
contradiction. Hence, $k_{1}=2$ cannot hold.

It now follows by Lemma 4.5 that $n-1$ divides $18$ or $n-1$ divides $6$.
Using the inequality from Lemma 4.6 we deduce that either $r_{1}=-3$ and
$n=10$ or $n=19$, or $r_{1}=-2$ and $n=3,4$, or $7$.

Now define $A=\sum\\{A_{i}\mid\epsilon_{i}=0\\}$. Then, $A$ must be a
symmetric matrix of row sum $k=\sum k_{i}$ and eigenvalue $r=\sum r_{i}$. What
we have said above for matrices $A_{i}$ with $\epsilon_{i}=0$ applies to $A$
as well and therefore $A$ must consist of only one summand, $A_{1}$ without
loss of generality. Now since by Lemma 4.4 $\sum\epsilon_{i}=3$ there are two
possibilities. There are either 5 matrices and
$\epsilon_{2}=\epsilon_{3}=\epsilon_{4}=1$ or there are 4 matrices and
$\epsilon_{2}=2$ and $\epsilon_{3}=1$.

Now we check this case individually to see which of those can hold.

Case 1: $r_{1}=-2,n=3$.

In the case that $\epsilon_{2}=\epsilon_{3}=\epsilon_{4}=1$ the inequality
from Lemma 4.6 gives us

$13-12r_{i}-9r_{i}^{2}\geq 0$

for $i\in\\{2,3,4\\}$ and since $r_{i}$ is integer, $-3\leq r_{i}\leq 0$.
Since by Equation (6.9) in [16] $r_{1},r_{2},r_{3},r_{4}$ must sum up to $-1$,
it follows that $r_{2},r_{3},r_{4}$ must sum up to $1$, but this cannot hold
since none of them can be positive.

Now we examine the case where we have four matrices and $\epsilon_{2}=1$ and
$\epsilon_{3}=2$. In this case Lemma 4.6 gives us

$\displaystyle-3\leq r_{2}\leq 0$ $\displaystyle-2\leq r_{3}\leq 1.$

The only way $r_{2}$ and $r_{3}$ could sum up to $1$ is $r_{2}=0$ and
$r_{3}=1$. In this case we get $k_{1}=4,k_{2}=2,k_{3}=2$ and checking for such
coherent configurations in [6] we find that there is a unique coherent
configuration with such row and column sums, but checking the rational
eigenvalues using GAP [5] shows that the $r_{i}$s are not equal to $-2,0,1$ as
we wish and hence there is no such association scheme.

Case 2: $r_{1}=-2,n=4$.

First we look at the case where $\epsilon_{2}=\epsilon_{3}=\epsilon_{4}=1$. By
Lemma 4.6 we get

$-7r_{i}^{2}-15r_{i}+17\geq 0$

Since $r_{i}$ is integer for $i\in\\{2,3,4\\}$ this gives

$-2\leq r_{i}\leq 0$

Again in this case we want the $r_{i}$s for $i\in\\{2,3,4\\}$ to sum up to $1$
but none of them is positive, so this case cannot hold.

Now let $\epsilon_{2}=1$ and $\epsilon_{3}=2$. In this case Lemma 4.6 gives

$\displaystyle-2\leq r_{2}\leq 0$ $\displaystyle-2\leq r_{3}\leq 1.$

The only combination that could work is $k_{2}=0$ and $k_{3}=1$. In this case
we would get $k_{1}=4,k_{2}=3,k_{3}=4$. Checking in [6] we don’t find any
coherent configurations with such row and column sums and appropriate
eigenvalues and hence $n=4$ cannot hold either.

Case 3: $r_{1}=-2,n=7$.

In the case that $\epsilon_{2}=\epsilon_{3}=\epsilon_{4}=1$ Lemma 4.6 gives us

$-15r_{i}^{2}-16r_{i}+58\geq 0$

and hence, since $r_{i}\in\mathbb{Z}$ for $i\in\\{2,3,4\\}$,

$-2\leq r_{i}\leq 1$

The only combinations (up to permutation) that would give us
$r_{1}+r_{2}+r_{3}+r_{4}=-1$ are $r_{2}=1,r_{3}=0,r_{4}=0$ and
$r_{2}=-1,r_{3}=1,r_{4}=1$. We then get $k_{1}=4,k_{2}=4,k_{3}=6,k_{4}=6$ or
$k_{1}=4,k_{2}=4,k_{3}=4,k_{4}=8$ respectively. Looking at [6], we deduce that
there aren’t any coherent configurations with such matrix row and column sums.

For $\epsilon_{2}=1,\epsilon_{3}=2$, as shown in [16] we need
$k_{1}=4,k_{2}=8,k_{3}=8$ and looking at [6] we deduce that there is a unique
coherent configuration with such matrix row and column sums and hence, it is
the one arising in [16]. The corresponding $s_{i}$s and $t_{i}$s can be
calculated to be

$\displaystyle s_{1}=1+\sqrt{2},t_{1}=1-\sqrt{2}$ $\displaystyle
s_{2}=-2\sqrt{2},t_{2}=2\sqrt{2}$ $\displaystyle
s_{3}=-2+\sqrt{2},t_{3}=-2-\sqrt{2}.$

Case 4: $r_{1}=-3,n=10$.

In this case it suffices to check the subcase $\epsilon_{2}=1,\epsilon_{3}$,
since $r_{1}$ is odd and hence it cannot be the case that $A_{1}$ is the sum
of a matrix and its transpose. Therefore, all the matrices in the initial
coherent configuration must be symmetric and we must have four of them. In
this case by Lemma 4.6 we get

$\displaystyle-13r_{2}^{2}-33r_{2}+123\geq 0$
$\displaystyle-39r_{3}^{2}-2r_{3}+396\geq 0$

which gives

$\displaystyle-4\leq r_{2}\leq 2$ $\displaystyle-3\leq r_{3}\leq 3.$

The $(r_{2},r_{3})$ pairs consistent with Equation (6.9) in [16] are
$(2,0),(1,1),(0,2),(-1,3)$ and all of those give row and column sums for which
an association scheme does not exist.

Case 5: $r_{1}=-3,n=19$.

In this case, as shown in [16] $k_{1}=6,k_{2}=20,k_{3}=30$ and the
corresponding $s_{i}$s and $t_{i}$s are

$\displaystyle s_{1}=\frac{3+\sqrt{5}}{2},t_{1}=\frac{3-\sqrt{5}}{2}$
$\displaystyle s_{2}=-2\sqrt{5},t_{2}=2\sqrt{5}$ $\displaystyle
s_{3}=\frac{-5+3\sqrt{5}}{2},t_{3}=\frac{-5-3\sqrt{5}}{2}.$

∎

We now deal with the case where $\epsilon_{1}=\epsilon_{2}=\epsilon_{3}=1$.
Notice that in this case, since the $\epsilon_{i}$s are all odd,
$\mathcal{B}=\mathcal{A}$ and by Lemma 4.3 all matrices are symmetric.

######  Lemma 4.8.

If $\epsilon_{1}=\epsilon_{2}=\epsilon_{3}=1$ then $r_{1},r_{2},r_{3}$ are all
different.

###### Proof.

Suppose for a contradiction that this is not the case and without loss of
generality, let $r_{1}=r_{2}$. Then, since $\epsilon_{1}=\epsilon_{2}$, it
follows that $k_{1}=k_{2}$. Thus, either $s_{1}=s_{1}$ and $t_{1}=t_{2}$ or
$s_{1}=t_{2}$ and $s_{2}=t_{1}$, and since our coherent configuration has rank
$4$, the matrices are simultaneously diagonalisable and it follows that

$\displaystyle s_{1}+s_{2}+s_{3}=-1$ $\displaystyle t_{1}+t_{2}+t_{3}=-1.$

But this means that $s_{3}=t_{3}$ and thus $A_{3}$ is a matrix of the kind
that Theorem 3.6 forbids, a contradiction. ∎

######  Lemma 4.9.

Let $a_{i}=\frac{3r_{i}(r_{i}+1)}{n-1}$. Then, $a_{i}\leq 4$ and if $r_{i}\geq
0$, then $a_{i}\leq 3$.

###### Proof.

Firstly notice that by Lemma 4.5, $a_{i}\in\mathbb{Z}$. By Lemma 4.6 we get

$(n-1)(4n+1)-6(n+1)r_{i}-(3n+9)r_{i}^{2}\geq 0.$

Therefore,

$(3n+9)(r_{i}^{2}+r_{i})\leq(n-1)(4n+1)-(3n-3)r_{i}$

and hence

$\displaystyle
a_{i}=\frac{3r_{i}(r_{i}+1)}{n-1}\leq\frac{4n+1}{n+3}-\frac{3r_{i}}{n+3}$
$\displaystyle=4-\frac{11}{n+3}-\frac{3r_{i}}{n+3}.$

Now, if $r_{i}\geq 0$, we get $a_{i}<4$, and hence $a_{i}\leq 3$. If $r_{i}<0$
and $n\geq 19$, using the inequality from Lemma 4.4 stating that
$r_{i}<\frac{3\sqrt{n}}{2}$, we deduce that $\frac{-3r_{i}}{n+3}\leq 1$ and
hence $a_{i}<5$ and so $a_{i}\leq 4$. Now, if $n<19$ and $r_{i}\leq 0$
checking gives that $a_{i}\leq 3$. ∎

######  Lemma 4.10.

If none of $a_{1},a_{2},a_{3}$ are zero, then $a_{1},a_{2},a_{3}$ are all
different.

###### Proof.

Suppose for a contradiction that without loss of generality, $a_{1}=a_{2}$.
Then, both $r_{1}$ and $r_{2}$ are roots of the equation

$3r(r+1)-a_{1}(n-1)=0.$

Since by Lemma 4.8 $r_{1}\neq r_{2}$, we must have $r_{1}+r_{2}=-1$. But from
Equation (6.9) in [16], $r_{1}+r_{2}+r_{3}=-1$ and hence $r_{3}=0$. But then,
$a_{3}=0$, a contradiction. ∎

######  Lemma 4.11.

If $a>0$ and $r$ is a root of the equation

$x^{2}+x-a=0$

then $r=-\frac{1}{2}\pm\sqrt{a}+\eta$, where $|\eta|<\frac{1}{8\sqrt{a}}$.

###### Proof.

Notice that
$\left(r+\frac{1}{2}\right)^{2}=r^{2}+r+\frac{1}{4}=a+\frac{1}{4}$.

Now, by squaring both $\sqrt{a+\frac{1}{4}}$ and
$\sqrt{a}+\frac{1}{8\sqrt{a}}$ we see that $|\eta|<\frac{1}{8\sqrt{a}}$, as
claimed. ∎

######  Lemma 4.12.

One of $a_{1},a_{2},a_{3}$ must be zero.

###### Proof.

Suppose that this is not the case. Then, by Lemma 4.10, $a_{1},a_{2},a_{3}$
are all different. Since $a_{i}=\frac{3r_{i}(r_{i}+1)}{n-1}$, it follows that
$r_{i}$ is a root of the equation

$x^{2}+x-\frac{a_{i}(n-1)}{3}=0.$

By Lemma 4.11 we get that

$r_{i}=-\frac{1}{2}\pm\sqrt{\frac{a_{i}(n-1)}{3}}+\eta_{i}$

where $|\eta_{i}|<\frac{1}{8}\sqrt{\frac{3}{a_{i}(n-1)}}<\frac{1}{8}$.

Now, it follows by Equation (6.9) in [16] that

$r_{1}+r_{2}+r_{3}=-1$

and hence

$-\frac{3}{2}+\sqrt{\frac{n-1}{3}}(\pm\sqrt{a_{1}}\pm\sqrt{a_{2}}\pm\sqrt{a_{3}})+\eta_{1}+\eta_{2}+\eta_{3}=-1.$

Rearranging and taking absolute values gives

$\left|\sqrt{\frac{n-1}{3}}(\pm\sqrt{a_{1}}\pm\sqrt{a_{2}}\pm\sqrt{a_{3}})\right|<\frac{7}{8}.$

Since $a_{i}\neq 0$, by Lemmas 4.9 and 4.10 we get that $a_{1},a_{2},a_{3}$
must be among the numbers $1,2,3,4$ and all different. Hence, crude
approximations to $sqrt{2}$ and $\sqrt{3}$ give the estimate

$|\pm\sqrt{a_{1}}\pm\sqrt{a_{2}}\pm\sqrt{a_{3}}|>\frac{4}{10}$

and hence

$\frac{4}{10}\sqrt{\frac{n-1}{3}}<\frac{7}{8}$

This gives $n<15$, but checking all cases shows that no integer less than $15$
has three different representations in the form
$1+\frac{3r_{i}(r_{i}+1)}{a_{i}}$ with $r_{i},a_{i}$ integral, all different
for every $i$, and $1\leq a_{i}\leq 4$, a contradiction. Hence, one of
$a_{1},a_{2},a_{3}$ must be zero, as claimed. ∎

We now choose notation such that $a_{1}=0$.

######  Lemma 4.13.

If $r_{1}$ is as defined above, then $r_{1}=-1$.

###### Proof.

Since $a_{1}=0$, $r_{1}=0$ or $r_{1}=-1$. Assume now that $r_{1}=0$. One of
$a_{2},a_{3}$ must be zero, for otherwise, all $r_{i}$s would be solutions of
the equation $x^{2}+x=0$ and hence they would not all be different, as Lemma
4.8 states. Suppose without loss of generality that $a_{2}\neq 0$. Then,

$n=\frac{3r_{2}(r_{2}+1)}{a_{2}}+1$

If $3$ does not divide $a_{2}$ then $n\equiv 1\pmod{3}$. If $3$ divides
$a_{2}$ then by Lemma 4.9, it follows that $a_{2}=3$ and
$n=r_{2}^{2}+r_{2}+1$. Hence $n\equiv 1\pmod{3}$ or $n\equiv 0\pmod{3}$. From
the linear and quadratic trace equations for $A_{1}$ we get

$\displaystyle s_{1}+t_{1}=-1$ $\displaystyle s_{1}^{2}+t_{1}^{2}=3n.$

Now
$p_{11}^{1}=|\\{j\in\\{1,\ldots,3n\\}\mid(A_{1})_{ij}=1,(A_{1})_{jk}=1\\}|$ is
an integer constant for any $i,k\in\\{1,\ldots,3n\\}$ such that
$(A_{1})_{ik}=1$. Moreover, the cubic trace equation for $A_{1}$ gives

$\displaystyle
3np_{11}^{1}=(n-1)^{2}+\frac{3}{2}(s_{1}+t_{1})(s_{1}^{2}+t_{1}^{2})-\frac{1}{2}(s_{1}+t_{1})^{3}$
$\displaystyle=(n-1)^{2}-\frac{3}{2}(2n+1)+\frac{1}{2}$
$\displaystyle=n^{2}-5n.$

Thus, $3p_{11}^{1}=n-5$ and since $p_{11}^{1}\in\mathbb{Z}$, it follows that
$n\equiv 5\pmod{3}$, a contradiction. Hence $r_{1}\neq 0$ and therefore
$r_{1}=-1$. ∎

######  Lemma 4.14.

$n=31$.

###### Proof.

Since $r_{1}=-1$ and $r_{1}+r_{2}+r_{3}=-1$ by Equation (6.9) in [16], it
follows that $r_{2}=-r_{3}=r\in\mathbb{Z}$. Then, since $a_{2},a_{3}$ are
integers,

$\displaystyle n-1\text{ divides }3r(r+1)$ $\displaystyle n-1\text{ divides
}3(-r)(-r+1).$

Hence, $n-1$ divides $3r(r+1)-3(-r)(-r+1)=6r$.

By interchanging $A_{2}$ and $A_{3}$ if necessary we may assume that $r\geq
0$. Then since by Lemma 4.8, $r_{1},r_{2},r_{3}$ are all different, it follows
that $r\neq 0$ and $r\neq 1$. Hence, $r\geq 2$. Moreover, from Lemma 4.9 we
know that

$\frac{6r}{n-1}\cdot\frac{r+1}{2}\leq 3.$

It follows that $r+1\leq 6$ and if $6r\neq n-1$ then since $n-1$ divides $6r$,
$r+1\leq 3$. Now considering that $\frac{6r}{n-1}\cdot\frac{r+1}{2}$ must be
integer and that the above inequality must hold for our choices of $n$ and $r$
we can check all cases and find that the only possibilities are:

$\displaystyle 6r=n-1,r=5,n=31$ $\displaystyle 6r=n-1,r=3,n=19$ $\displaystyle
3r=n-1,r=2,n=7.$

For $n=7$ we see that $k_{1},k_{2},k_{3}$ are equal to $8,2,10$ respectively
and checking in [6], we see that there is no association scheme with such row
and column sums.

If $n=19$, then the trace equations give

$\displaystyle s_{1},t_{1}\text{ are }\pm 2\sqrt{5}$ $\displaystyle
s_{2},t_{2}\text{ are }\pm-2\pm\sqrt{6}$ $\displaystyle s_{3},t_{3}\text{ are
}\pm 5,-3$

Now, no possible tuple $(s_{1},s_{2},s_{3})$ satisfies $s_{1}+s_{2}+s_{3}=-1$
and hence this case cannot arise.

Finally, for $n=31$ for suitable choices of roots we get

$\displaystyle s_{1}=4\sqrt{2},t_{1}=-4\sqrt{2}$ $\displaystyle
s_{2}=-3-\sqrt{2},t_{2}=-3+\sqrt{2}$ $\displaystyle
s_{3}=2-3\sqrt{2},t_{3}=2+3\sqrt{2}.$

∎

###### Proof of Theorem 3.7.

Follows directly by Proposition 4.7 and Lemma 4.14. ∎

###### Proof of Theorem 3.8.

Follows directly by proposition 4.7. ∎

##  5 Examples

In this section we provide examples with the parameters found in Theorems 3.1
to 3.8, in cases where they are known to exist.

###  5.1 Theorem 3.1

The classic examples of symmetric conference graphs are the Paley graphs. The
vertex set of such a graph is the set of elements of a finite field whose
order is congruent to $1$ (mod $4$), and two vertices are connected by an edge
if and only if their difference is a square in the field.

Similarly, the classic examples of doubly regular tournaments are the Paley
tournaments; the vertex set is the set of elements of a finite field of order
congruent to $3$ (mod $4$), wich an arc from $a$ to $b$ if $b-a$ is a square.

###  5.2 Theorem 3.2

For the second set of parameters arising in Theorem 3.2, a known example (with
$a=0$) is the triangular graph $T(6)$ and its complement; no further examples
are known. For the other sets of parameters, no known example with fewer than
512 vertices is known. Moreover, due to the large number of vertices that the
given parameters force, it would be very hard to construct one.

###  5.3 Theorem 3.3

For the first set of parameters arising in Theorem 3.3 and for $a\geq 2$, the
graphs arising from Steiner systems of the type $S(2,a+1,n)$ with
$a\in\\{1,2,3\\}$ are known examples. The number of non-isomorphic Steiner
systems $(2,3,19)$ is $11,084,874,829$ (see [12]); these give pairwise non-
isomorphic graphs. There is no known example of graphs with the second set of
parameters, and the nonexistence in the case $a=2$ has been shown by Wilbrink
and Brouwer [25].

###  5.4 Theorem 3.4

We do not have any examples for this theorem. Is it possible to take a graph
of the type arising in Theorem 3.3, and either split the edges into two
classes or put directions on the edges so as to form a coherent configuration?

###  5.5 Theorem 3.7

The cases $n=21$ and $n=57$ are realised by the groups $\mathrm{PGL}(2,7)$ and
$\mathrm{PSL}(2,19)$ respectively. These can be found in the GAP [5] database
of primitive permutation groups as PrimitiveGroup(21,1) and
PrimitiveGroup(57,1) respectively.

The database [6] gives the basis matrices for the first of these, and
certifies its uniqueness. In the second case, the association scheme is also
known to be unique [2]; the graph of valency $6$ is the distance-transitive
_Perkel graph_ [18]. Existence in the final case with $93$ points is
undecided, as far as we know.

#### Acknowledgement

The research of the first author was supported by an Undergraduate Research
Bursary, number XCLM18, from the London Mathematical Society. The second
author acknowledges the Isaac Newton Institute for Mathematical Sciences,
Cambridge, for support and hospitality during the programme Groups,
representations and applications: new perspectives (supported by EPSRC grant
no. EP/R014604/1), where he held a Simons Fellowship.

## References

  * [1] P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links, London Math. Soc. Student Texts 22, Cambridge University Press, Cambridge, 1991. [Theorem 2.20.]
  * [2] K. Coolsaet and J. Degraer, A computer assisted proof of the uniqueness of the Perkel graph, Designs, Codes Crypt. 34 (2005), 155–171X.
  * [3] W. Feit, On finite linear groups, J. Algebra 5 (1967), 3778–400.
  * [4] Felix Gantmacher, The Theory of Matrices, Volume 2, AMS Chelsea Publishing, ISBN 978-0-8218-2664-5 (reprint of 1959 edition Applications of the theory of matrices).
  * [5] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.11.1; 2021; https://www.gap-system.org.
  * [6] Akihide Hanaki and Izumi Miyamoto , Classification of association schemes of small vertices, http://math.shinshu-u.ac.jp/~hanaki/as/, Visited on 3 July 2022.
  * [7] D. G. Higman, Finite permutation groups of rank $3$, Math. Zeitschrift 86 (1964), 145–156.
  * [8] D. G. Higman, Intersection matrices for finite permutation groups, J. Algebra 6 (1967), 22–42.
  * [9] D. G. Higman, Combinatorial Considerations about Finite Permutation Groups, Mathematical Institute Lecture Notes, Oxford, 1970.
  * [10] W. M. Kantor, Primitive permutation groups of odd degree, and an application to finite projective planes, J. Algebra 106 (1987), 15–45.
  * [11] W. M. Kantor and R. A. Liebler, The rank $3$ permutation representations of the finite classical groups, Trans. Amer. Math. Soc. 271 (1982), 1–71.
  * [12] Petteri Kaski and Patric R. J. Östergård, The Steiner triple systems of order $19$, Math. Computation 73 (2004), 2075–2092.
  * [13] Martin W. Liebeck, The affine permutation groups of rank $3$, Proc. London Math. Soc. (3) 54 (1987), 477–516.
  * [14] Martin W. Liebeck and Jan Saxl, The primitive permutation groups of odd degree, J. London Math. Soc. (2) 31 (1985), 250–264.
  * [15] Martin W. Liebeck and Jan Saxl, The finite primitive permutation groups of rank $3$, Bull. London Math. Soc. 18 (1986), 165–172.
  * [16] Peter M. Neumann, Primitive permutation groups of degree $3p$, unpublished manuscript, 1969.
  * [17] Peter M. Neumann, Primitive permutation groups of degree $3p$, arXiv version, re-typed from the original, https://arxiv.org/abs/2204.06926.
  * [18] Manley Perkel, Bounding the valency of polygonal graphs with odd girth, Canad. J. Math. 31 (1979), 1307–1321.
  * [19] K. B. Reid and Ezra Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices, J. Combinatorial Theory (A) 12 (1972), 332–338.
  * [20] L. L. Scott, Thesis, Yale 1968.
  * [21] L. L. Scott, personal communication, 2022.
  * [22] O. Tamaschke, Primitive Permutationsgruppen vom Grad $3p$, Thesis, Tübingen, 1959.
  * [23] H. Wielandt, Primitive Permutationsgruppen vom Grad $2p$, Math. Zeitschrift 63 (1956) 478–485.
  * [24] H. Wielandt, Finite Permutation Groups, Academic Press 1964.
  * [25] H. A. Wilbrink and A. E. Brouwer, A $(57,14,1)$ strongly regular graph does not exist, Indag. Math. 86 (1983), 117–121.


# Tidal disruption of near-Earth asteroids during close encounters with
terrestrial planets

Mikael Granvik Asteroid Engineering Laboratory, Luleå University of
Technology, Box 848, Kiruna, Sweden  Department of Physics, P.O. Box 64, 00014
University of Helsinki, Finland  Kevin J. Walsh Southwest Research Institute,
1050 Walnut St, Suite 300, Boulder, CO 80302, U.S.A.

(Received October 11, 2023; Revised December 8, 2023; Accepted December 10,
2023)

###### Abstract

Numerical modeling has long suggested that gravitationally-bound (or so-called
rubble-pile) near-Earth asteroids (NEAs) can be destroyed by tidal forces
during close and slow encounters with terrestrial planets. However, tidal
disruptions of NEAs have never been directly observed nor have they been
directly attributed to any families of NEAs. Here we show population-level
evidence for the tidal disruption of NEAs during close encounters with the
Earth and Venus. Debiased model distributions of NEA orbits and absolute
magnitudes based on observations by the Catalina Sky Survey during 2005–2012
underpredict the number of NEAs with perihelion distances coinciding with the
semimajor axes of Venus and the Earth. A detailed analysis of the orbital
distributions of the excess NEAs shows that their characteristics agree with
the prediction for tidal disruptions, and they cannot be explained by
observational selection effects or orbital dynamics. Accounting for tidal
disruptions in evolutionary models of the NEA population partly bridges the
gap between the predicted rate of impacts by asteroids with diameters of tens
of meters and observed statistics of fireballs in the same size range.

Asteroids(72) — Near-Earth objects(1092) — Orbital evolution(1178) — Tidal
disruption(1696) — Sky surveys(1464)

††journal: ApJL

##  1 Introduction

The disruption of comet Shoemaker-Levy 9 during a close passage of Jupiter
illuminated the weak gravitationally-bound interior structure of small bodies
now often referred to as rubble piles (Richardson et al., 2002; Walsh, 2018).
The details of the disruption, the size and spacing of the fragment train in
particular, provided significant leverage for models of tidal disruption to
constrain the comet’s original size and density (Asphaug & Benz, 1994).
Numerical models of the tidal disruption of rubble piles continued to gain
capability and sophistication, and have since surveyed possible outcomes of
encounters of rubble-pile asteroids with terrestrial planets. These
simulations have accounted for minimum encounter distance and encounter speed,
as well as the progenitors shape and spin (Richardson et al., 1998), and shear
strength by way of surface friction (Zhang & Michel, 2020).

Tidal disruption has been pointed to as a likely mechanism in re-shaping some
enigmatic asteroids, where the shape of asteroid (1620) Geographos is a
primary suspect (Richardson et al., 1998). Similarly, Schunová et al. (2014)
postulated that tidal disruption during a close Earth encounter was a source
for near-Earth-object (NEO) families and estimated the orbital evolution of
these families over time to understand why none have been identified to date
(see, e.g., Schunová et al., 2012). They concluded that the decoherence time
of NEO families is too short compared to the frequency of tidal-disruption
events to allow NEO families to be identified at any given time. There has
thus never been any observational evidence suggesting that the tidal
disruption of asteroids during close planetary encounters would be an
important aspect of asteroid evolution in the inner Solar System.

Meanwhile, the discrepancy between the observed (Brown et al., 2013) and
predicted (Harris & D’Abramo, 2015; Harris & Chodas, 2021) rate of small
asteroid or meteoroid impacts with the Earth has not been conclusively solved
to date. The explanations range from extrinsic reasons such as systematic
errors in the analysis of optical impact flashes to intrinsic reasons such as
the asteroid albedo changing with diameter. Detailed analysis by Boslough et
al. (2015) reduced the discrepancy but a factor of few still remains. An
excess of low-inclination Aten asteroids (semimajor axis $a<a_{\rm Earth}$ and
aphelion distance $Q>q_{\rm Earth}$, where $q_{\rm Earth}$ is the perihelion
distance of the Earth) has also been reported but conclusive evidence for its
origin has so far been lacking (Mainzer et al., 2012; Greenstreet & Gladman,
2013).

The actual population of objects on near-Earth orbits is vastly better
constrained than just a decade ago owing to numerous surveys with
complementary approaches and long timelines of operation such as the Catalina
Sky Survey (CSS). These data provide powerful constraints on numerical models
describing the debiased distribution of orbital elements and absolute
magnitudes of NEOs (Granvik et al., 2016, 2018; Nesvorný et al., 2023). While
nominally simulating the entire near-Earth population in a steady-state
scenario, one outcome focused primarily on the discrepancy between observed
and predicted number of asteroids at small perihelion distances. After
carefully making sure that the discrepancy is statistically significant and
that it is not caused by errors in any aspects of the modeling, Granvik et al.
(2016) concluded that asteroids are essentially completely destroyed—hence the
term super-catastrophic disruption—close to the Sun but at distances that are
nontrivial to explain. The finding has later been confirmed (Granvik et al.,
2018; Nesvorný et al., 2023).

The fidelity of the latest NEO population models allow for a direct comparison
with observed Earth and/or Venus crossing populations to search of over-
predictions or under-predictions that could be related to tidal disruption.
Here we take a closer look at the region in orbital-element space surrounding
the orbits of Venus and Earth, and compare the observed population to
theoretical predictions for tidal disruptions during close encounters with
these planets.

##  2 Data and methods

Let us first summarize the data and methods that underlie the debiased model
of NEO orbits and absolute magnitudes. The choice to focus on the model by
Granvik et al. (2016) rather than a more recent model, such as Granvik et al.
(2018) or Nesvorný et al. (2023), is that the former was extensively
scrutinized to give credibility to the discovery of super-catastrophic
disruptions by ruling out all possible issues with the modeling approach. In
addition, Granvik et al. (2016) model super-catastrophic disruption explicitly
as a cut-off affecting individual test asteroids during the orbital
integrations rather than a mathematical penalty function affecting the
resulting orbit distribution, and is therefore conceptually intuitive and easy
to understand. Finally, all of the aforementioned models are based on the same
observational data set from CSS, and have been shown to be in general
agreement with each other.

The fundamental equation solved when constructing an NEO population model is

$\displaystyle n(a,e,i,H)=\epsilon(a,e,i,H)\,\times\,M(a,e,i,H)=$
$\displaystyle\epsilon(a,e,i,H)\,\times\,\sum_{s=1}^{N_{\rm
ER}}N_{s}(H)\,R_{s}(a,e,i)\,,$ (1)

where $n(a,e,i,H)$ is the number distribution of NEOs detected by a survey
during some time interval in the space of orbital elements (semimajor axis
$a$, eccentricity $e$, and inclination $i$) and absolute magnitude ($H$),
$\epsilon(a,e,i,H)$ is the so-called bias correction function which provides
an absolutely-calibrated estimate for the number of NEOs that should be
detected by the same survey during the same time interval (Jedicke et al.,
2016), and $M(a,e,i,H)$ is the debiased model that we want to derive. To
constrain the model in a physically-meaningful way, we separate the debiased
model into its components: $N_{\rm ER}$ is the number of escape regions (ER)
from which asteroids and comets enter the NEO region (also sometimes called
source regions) considered in the model, and $N_{s}(H)$ and $R_{s}(a,e,i)$ are
the $H$-frequency distribution and the normalized, steady-state orbit
distribution, respectively, for NEOs originating in ER $s$. The steady-state
orbital distributions, $R_{s}(a,e,i)$, are estimated numerically by following
the orbital evolution of numerous test bodies from the main asteroid belt and
cometary reservoirs into the NEO region, and recording the time that the test
bodies spend in various parts of the ($a,e,i$) space in the NEO region
(Granvik et al., 2016, 2017, 2018).

Granvik et al. (2016) used a parameterization for the differential $H$
distribution that allows for a smooth, second-degree variation of the slope:

$\displaystyle N_{s}(H)=$ $\displaystyle N_{s}(H;N_{0,s},\alpha_{{\rm
min},s},H_{{\rm min},s},c_{s})=$ $\displaystyle
N_{0,s}\,10^{\int_{H_{0}}^{H}\left[\alpha_{{\rm
min},s}+c_{s}(H^{\prime}-H_{{\rm min},s})^{2}\right]\,dH^{\prime}}=$
$\displaystyle N_{0,s}\,10^{\alpha_{{\rm
min},s}(H-H_{0})+\frac{c_{s}}{3}\left[(H-H_{{\rm min},s})^{3}-(H_{0}-H_{{\rm
min},s})^{3}\right]}\,.$ (2)

The model by Granvik et al. (2016) is calibrated with CSS’s detections of NEOs
with $17<H<25$ obtained during 2005–2012. The free parameters fitted with a
simplex method are those describing the $H$ distributions, that is, $N_{0,s}$,
$\alpha_{{\rm min},s}$, $H_{{\rm min},s}$, and $c_{s}$.

There are thus no knobs that could be turned in the presented methodology to
either produce or get away with features in the resulting debiased orbit and
absolute-magnitude distribution, $M(a,e,i,H)$, other than by introducing new
escape regions or source regions for NEOs, or otherwise modify the input orbit
distributions.

##  3 Results and discussion

Granvik et al. (2016) found that, by assuming a complete, instantaneous
destruction of asteroids at an average perihelion distance
$q=0.076\,\mathrm{au}$, the model could reproduce the observed perihelion
distances $q\lesssim 0.6\,\mathrm{au}$ significantly more accurately than
without assuming a destruction (see their Fig. 1). Note, however, that the
rather simplistic disruption model, which averages over all orbits, taxonomic
types, and sizes, and is agnostic about the physical description of the
disruption, has some limitations in accurately reproducing perihelion
distances. By plotting the same distribution on a linear scale and as a
difference between the observed and the predicted distributions, it becomes
clear that there are two additional offsets at $q\sim 0.7\,\mathrm{au}$ and
$q\sim 1\,\mathrm{au}$ where the model under-predicts the number of NEO
detections (Fig. 1). That is, there are systematically more NEOs on orbits for
which perihelion distance coincides with the semimajor axes of Venus and the
Earth, respectively, and the same trend is also apparent in Fig. 11 by Granvik
et al. (2018) which presents an alternative approach to modeling the lack of
NEOs at small $q$.

Figure 1: The difference between observed and predicted number of NEO
detections by CSS during the years 2005–2012 as a function of perihelion
distance $q$ (blue line). The model prediction assumes a super-catastrophic
disruption when $q\sim 0.076\,\mathrm{au}$ (Granvik et al., 2016). The
observed population is substantially larger than the predicted population for
$q\sim a_{\rm Venus}\sim 0.7\,\mathrm{au}$ and $q\sim a_{\rm Earth}\sim
1\,\mathrm{au}$. The difference cannot be explained by selection effects or
orbital dynamics. The gray histogram shows an arbitrarily-normalized
distribution of the perihelion distances of synthetic gravitational aggregates
that in numerical simulations have undergone B-type tidal disruptions during
encounters with the Earth or Venus.

First we need to consider the possibility that the model’s inability to
predict enough NEO detections with $q~{}\sim a_{\rm planet}$ would be a
modeling artifact. Given that we have no direct influence on the outcome of
the fitting procedure—the debiased orbital model—the only alternative
explanations are that the correction bias function and/or the input steady-
state orbit distributions are erroneous. It is rather straightforward to rule
out the possibility that the correction bias would be erroneous: despite the
fact that the bias function has been carefully scrutinized, we could imagine
an unlikely scenario where the detectability of Earth-approaching NEOs as
observed from the Earth would have been estimated incorrectly. However, there
is no conceivable reason why the detectability of NEOs with $q\sim a_{\rm
Venus}$, as observed from the Earth, would also have been estimated
incorrectly. Note that these excess NEOs are not necessarily detected close to
the planet in question.

The orbital integrations that were carried out to produce the steady-state
orbit distributions took into account gravitational perturbations by all
planets, and used a time step of 12 hours (Granvik et al., 2018). Only
incorrectly modelled close encounters with terrestrial planets could change
the orbit distribution so that the discrepancy is only apparent for orbits
that have $q~{}\sim a_{\rm planet}$. In principle, a close encounter by an NEO
with a very high encounter speed could go undetected and thus produce
artifacts in the orbit distributions. There is no evidence for such artifacts
in the orbit distributions, and it is not even clear that such an artifact
would produce an offset in the correct direction. In addition, the excess
detections are related to low-inclination and low-to-moderate-eccentricity
orbits, that is, orbits that generally lead to slow encounter velocities (Fig.
2), so an explanation based on undetected close encounters is not viable.

Figure 2: The difference (blue line) between observed and predicted number of
NEO detections by CSS during the years 2005–2012 as a function of eccentricity
$e$ (top panels) and inclination $i$ (bottom panels) for perihelion distances
coinciding the semimajor axis of Venus (left panels) and the semimajor axis of
the Earth (right panels). The model prediction assumes a super-catastrophic
disruption when $q\sim 0.076\,\mathrm{au}$ (Granvik et al., 2016). The gray
histograms show arbitrarily-normalized distributions of $e$ and $i$ of
synthetic gravitational aggregates that in numerical simulations have
undergone B-type tidal disruptions during encounters with the Earth or Venus.

The excess detections in the Granvik et al. (2016) model primarily correspond
to smaller NEOs with $18<H<22$ for those with $q\sim 0.7\,\mathrm{au}$ and
$19<H<25$ for those with $q\sim 1\,\mathrm{au}$ (Fig. 3). The largest NEOs
considered by Granvik et al. (2016), that is, those with $17<H<18$ do not show
any evidence of excess detections. The breakdown of the excess detections into
bins of $H$ are less certain than their bulk signature, and there are some
caveats that need to be considered when interpreting the $H$ distributions of
the excess detections. First, the fitting routine is trying to reproduce the
observed distribution of NEO orbits and absolute magnitudes as accurately as
possible, which implies that it will try to compensate for any shortcomings in
the model’s physical representation of the NEO population. That is, misleading
compensation occurs, and we can only argue that some essential physics is
missing from the model setup when there are too many (or too few) detections
that can no longer be compensated for—which is exactly the case here with the
excess detections. Hence the $H$ distribution of the excess detections, that
the model cannot reproduce, will be a misleading representation of the $H$
distribution that would result if the missing physics would be accounted for.
Second, low-eccentricity NEOs with $H>22$ are largely undetectable at
$q<0.8\,\mathrm{au}$ (cf. Fig. 2) and $q>1.2\,\mathrm{au}$. Third, the fitting
by Granvik et al. (2016) was done using an extended maximum-likelihood scheme
which aims to reproduce the total number of detections in addition to their
distribution. Hence an excess in one part of the model may be counteracted
with deficit in another. In summary, the excess detections preferentially
correspond to small NEOs but the detailed $H$ distribution remains a topic of
future studies.

Figure 3: The difference between observed and predicted number of NEO
detections by CSS during the years 2005–2012 as a function of perihelion
distance $q$ separated into four different ranges in absolute magnitude $H$.
The model prediction assumes a super-catastrophic disruption when $q\sim
0.076\,\mathrm{au}$ (Granvik et al., 2016). The excess detections at $q\sim
0.7\,\mathrm{au}$ and $q\sim 1\,\mathrm{au}$ correspond, in general, to
smaller NEOs. See main text for caveats affecting interpretation.

Let us now assume that the excess detections correspond to fragments from
tidal disruptions, and compare the expected orbits of those fragments to the
orbits of the NEOs corresponding to the excess detections. Tidal disruptions
have been classified by the amount of mass remaining in the disrupted body
following its encounter with a planet: S-type encounters are extremely
disruptive removing 90% of the total mass whereas B-type disruptions remove
50-90% of the total mass, and M-types remove less than 10% (Richardson et al.,
1998). S-type and B-type disruptions can thus generate a few or more large
tidal-disruption fragments (compared to the parent body) and a significantly
larger number of smaller fragments, whereas M-type disruptions only result in
small fragments. While the details of the encounters such as spin and shape do
matter, here we adopt the encounters that produce B-type disruptions for
bodies with an average rotation period, and extract about 100 samples of
progenitor orbits for close-enough and slow-enough encounters from published
NEO orbit simulations (Nesvorný et al., 2010, Zhang and Michel personal
communication). The disruption limits are scaled to a bulk density of
$1.6\,\mathrm{g}\,\mathrm{cm}^{-3}$ and to a rotation period of 7 hr, both
approximate averages for the NEO population (Warner et al., 2021). The
arbitrarily-normalized distributions of orbits leading to and immediately
following B-type tidal disruptions are shown as the gray histograms in Figs. 1
and 2, and show an excellent agreement with the orbits corresponding to excess
NEOs: objects that are most susceptible to tidal disruptions have low-to-
moderate eccentricities and low inclinations. The lack of excess low-$e$ NEO
detections with $0.6\,\mathrm{au}<q<0.8\,\mathrm{au}$ can be explained by
accounting for the fact that NEOs with $e\lesssim 0.2$ and
$q<0.8\,\mathrm{au}$ never reach opposition as seen from the Earth, which
makes them challenging to detect. That is, we cannot rule out tidal
disruptions of NEOs with $e\lesssim 0.2$ at Venus just based on an apparent
lack of excess detections obtained from the Earth. We propose that the excess
of low-$i$ Aten asteroids is at least partly explained as fragments from tidal
disruptions (Mainzer et al., 2012; Greenstreet & Gladman, 2013).

The fragments from recent tidal disruptions have small minimum orbital
intersection distances (MOID) and slow speeds relative to the planet that
caused the tidal disruption. Therefore, if tidal disruptions have occurred in
the relatively recent past, we should expect to see an excess of small NEOs
with slow relative speeds and close encounters when comparing to an orbital
model that does not account for tidal disruptions. This is exactly what is
seen in Figs. 5 (only NEOs detected by ATLAS) and 6 (all NEOs detected) in
Heinze et al. (2021), which compares NEO detections by ATLAS and other surveys
to the model by Granvik et al. (2018). Note that the normalization used makes
it challenging to estimate the magnitude of the discrepancy.

To further test the hypothesis of tidal disruptions being responsible for the
excess detections, we generated orbit distributions corresponding to tidal
disruptions at Venus and the Earth at different stages of their evolution and
re-fitted the population models with these additional source regions for NEOs
with $17<H<25$. The orbit distributions were derived by recording the
evolution of the test asteroids used for the steady-state orbit distributions
by Granvik et al. (2018) but selecting only those with orbital elements
similar to the simulated gravitational aggregates that suffered tidal
disruptions (gray histograms in Figs. 1 and 2). The time of entering the
orbital space potentially leading to tidal disruptions also marked the
starting point for recording their orbital evolution. Figure 4 shows two
examples of ensemble orbit distributions at different stages in their
evolution resulting from tidal disruptions during an encounter with the Earth.
The diffusion of the orbital elements over time is clearly visible, yet the
location of the core of the distribution hardly changes from
$10\,\mathrm{kyr}$ after the disruption until the time when all test asteroids
have reached a sink, that is, a collision with a planet or the Sun, or an
ejection from the inner Solar System due to a close encounter with a planet,
typically Jupiter. The average lifetime for a test asteroid to reach a sink
after a tidal disruption is $8.7\,\mathrm{Myr}$ whereas the 5th percentile is
$0.03\,\mathrm{Myr}$ and the 95th percentile is $47\,\mathrm{Myr}$.

Figure 4: Examples of ensemble orbit distributions that could result from a
large number of tidal disruptions of NEOs with $a<2\,\mathrm{au}$ and
$i<25^{\circ}$ during close encounters with the Earth $10\,\mathrm{kyr}$ after
the disruption (left) and when all test asteroids have reached a sink (right).
The assumption here is that the fragments are ejected at negligibly slow
speeds relative to the disrupting parent body, which is corroborated by
numerical simulations of tidal disruptions (Schunová et al., 2014), so only
the orbital evolutions of the parent bodies are considered here.

Since the focus here is on tidal disruptions occurring at relatively large
$q$, we decided to use the modeling approach described by Granvik et al.
(2018) who account for the super-catastrophic disruptions at small $q$ with a
linear, two-parameter penalty function in the $(q,N)$ space, where $N=N(q)$ is
the incremental number of NEO detections as a function of $q$. The chosen
method improves the accuracy of the fit at small $q$ at the cost of making the
interpretations somewhat less intuitive. The resulting $q$ distribution shows
a significantly better agreement with the observed $q$ distribution for large
$q$, and thus supports the hypothesis that tidal disruptions would be the
explanation for the excess NEO detections (Fig. 5).

Figure 5: The difference between observed and predicted number of NEO
detections by CSS during the years 2005–2012 as a function of perihelion
distance $q$ when including orbit distributions that could result from tidal
disruptions in the model (blue line). The model accounts for super-
catastrophic disruptions by fitting for the parameters of a penalty function
at small $q$ (Granvik et al., 2018). The gray histogram is the one not
accounting for tidal disruptions (Fig. 1).

An interesting feature arising from the new fit is the peak at
$0.4\,\mathrm{au}<q<0.5\,\mathrm{au}$, which coincides with the semimajor axis
of Mercury. Since tidal disruptions during Mercury encounters were not
considered, the excess detections could be a signal of unaccounted tidal
disruptions with Mercury. We note that Mercury encounters are not likely to
lead to a significant rate of tidal disruptions, because the mass of Mercury
is rather small, and the encounter speeds are typically large. The question
will remain a topic of future studies given the limited statistics in the
relevant part of the orbital space used in the present study as well as our
current lack of knowledge about the mechanism(s) causing super-catastrophic
disruptions—a major factor affecting the orbital distributions close to the
Sun.

The fragments resulting from a tidal disruption will remain on planet-
approaching orbits also for some time after a tidal-disruption event. Some
fragments may therefore undergo further tidal disruption during subsequent
close encounters with the planet, and thus increase the number of resulting
fragments whereas some may impact the planet. There should therefore be at
least an intermittent increase in the rate of close encounters and impacts
with the planet following a tidal disruption (cf. Shoemaker-Levy 9). We
estimated the increase in the long-term impact rate when accounting for tidal
disruptions, and found that for $H<25$ the annual impact rate increases from
0.0012 (Granvik et al., 2018) to 0.0018, or about 50%, when using the same
methodology for calculating the impact rate.

In addition to increasing the rate of impacts with the Earth, fragments from
tidal disruptions also increase the rate of impacts on nearby bodies. Williams
et al. (2018) describe the strong apex-to-antapex asymmetry of ”cold spot”
lunar craters that are only 0.023–2.3$\,\mathrm{km}$ in diameter and
interpreted to be only 0.5–1$\,\mathrm{Myr}$ old. The size and asymmetry may
be an indication of preferential formation by a population of projectiles with
low relative speeds with respect to the Earth-Moon system that match the
general properties of the fragments generated by tidal disruption.

Finally, as other mechanisms that lead to asteroid disruptions, also tidal
disruptions produce dust and small meteoroids. The consequence of the fact
that tidal disruptions happen close to planets is that the dust and small
meteoroids will also remain on orbits that intersect that of Earth’s for some
time after the disruption, and should be detectable by meteor radars. We note
that tidal disruptions are not necessarily one-off events, because close
encounters can come in sequences of so-called resonant returns (Valsecchi et
al., 2003). Hence, either the parent body or its fragments—the latter formed
in tidal disruptions during previous close encounters—may effectively produce
a cascade of tidal-disruption events over an extensive period of time. On the
other hand, the low-$i$ and low-$e$ of NEOs most prone to tidal disruption
decreases the encounter speed, which, in turn, reduces the ionization and thus
the radar detectability. In addition, the solar radiation pressure and
frequent planetary encounters on such orbits diffuse the stream relatively
fast until it becomes unidentifiable above the sporadic background. The
Poynting-Robertson drag works on longer timescales, and reduces the
heliocentric distance of the particles and circularizes the orbits. A detailed
study of the longevity of circumsolar dust rings formed by tidal disruptions
is left for future work, but they have been detected close to Mercury’s and
Venus’ orbits (Pokorný & Kuchner, 2019; Pokorný et al., 2023), and, to the
best of our knowledge, a formation scenario including tidal disruption of NEOs
has not been considered to date.

##  4 Conclusions

We have shown that the tidal disruption of asteroids during close encounters
with the Earth and Venus is an observational fact, and potentially solves a
number of open issues that are linked to NEOs on orbits that are either
similar or tangential to those of the terrestrial planets. The discovery
expands on the work by Binzel et al. (2010) who proposed that close encounters
with the Earth, that are more distant than those considered here, refresh the
surfaces of asteroids.

We speculate that, in the future, it will be possible to make a statistically-
significant identification of the much weaker signal from tidal disruptions
during Mercury encounters. Such an identification requires better statistics
of NEOs with $q\sim a_{\rm Mercury}\sim 0.4\,\mathrm{au}$ and also a
reasonably accurate model of the super-catastrophic disruptions at small $q$.

We stress that these results do not suggest that tidal disruption during close
planetary encounters would be the primary mechanism destroying gravitational
aggregates in the inner Solar System. Moreover, here we report an
overabundance of NEO detections, which implies a generation of more observable
NEOs, not fewer. The benefit compared to other disruption mechanisms, such as
rotational disruption, is that the frequency of planetary encounters and the
subsequent dynamical evolution of the fragments is well understood, which
allows for testing the susceptibility of asteroids for tidal disruption on the
population level.

We thank the anonymous referee whose suggestions improved the manuscript. MG
was partly funded by the Swedish Research Council’s award number 2022-04615.

## References

  * Asphaug & Benz (1994) Asphaug, E., & Benz, W. 1994, Nature, 370, 120, doi: 10.1038/370120a0
  * Binzel et al. (2010) Binzel, R. P., Morbidelli, A., Merouane, S., et al. 2010, Nature, 463, 331, doi: 10.1038/nature08709
  * Boslough et al. (2015) Boslough, M., Brown, P., & Harris, A. 2015, in 2015 IEEE Aerospace Conference, 1–12, doi: 10.1109/AERO.2015.7119288
  * Brown et al. (2013) Brown, P. G., Assink, J. D., Astiz, L., et al. 2013, Nature, 503, 238, doi: 10.1038/nature12741
  * Granvik et al. (2017) Granvik, M., Morbidelli, A., Vokrouhlický, D., et al. 2017, A&A, 598, A52, doi: 10.1051/0004-6361/201629252
  * Granvik et al. (2016) Granvik, M., Morbidelli, A., Jedicke, R., et al. 2016, Nature, 530, 303, doi: 10.1038/nature16934
  * Granvik et al. (2018) —. 2018, Icarus, 312, 181, doi: 10.1016/j.icarus.2018.04.018
  * Greenstreet & Gladman (2013) Greenstreet, S., & Gladman, B. 2013, ApJL, 767, L18, doi: 10.1088/2041-8205/767/1/L18
  * Harris & Chodas (2021) Harris, A. W., & Chodas, P. W. 2021, Icarus, 365, 114452, doi: 10.1016/j.icarus.2021.114452
  * Harris & D’Abramo (2015) Harris, A. W., & D’Abramo, G. 2015, Icarus, 257, 302, doi: 10.1016/j.icarus.2015.05.004
  * Heinze et al. (2021) Heinze, A. N., Denneau, L., Tonry, J. L., et al. 2021, , 2, 12, doi: 10.3847/PSJ/abd325
  * Jedicke et al. (2016) Jedicke, R., Bolin, B., Granvik, M., & Beshore, E. 2016, Icarus, 266, 173, doi: 10.1016/j.icarus.2015.10.021
  * Mainzer et al. (2012) Mainzer, A., Grav, T., Masiero, J., et al. 2012, ApJ, 752, 110, doi: 10.1088/0004-637X/752/2/110
  * Nesvorný et al. (2010) Nesvorný, D., Bottke, W. F., Vokrouhlický, D., Chapman, C. R., & Rafkin, S. 2010, Icarus, 209, 510, doi: 10.1016/j.icarus.2010.05.003
  * Nesvorný et al. (2023) Nesvorný, D., Deienno, R., Bottke, W. F., et al. 2023, AJ, 166, 55, doi: 10.3847/1538-3881/ace040
  * Pokorný et al. (2023) Pokorný, P., Deutsch, A. N., & Kuchner, M. J. 2023, , 4, 33, doi: 10.3847/PSJ/acb52e
  * Pokorný & Kuchner (2019) Pokorný, P., & Kuchner, M. 2019, ApJ, 873, L16, doi: 10.3847/2041-8213/ab0827
  * Richardson et al. (1998) Richardson, D. C., Bottke, W. F., & Love, S. G. 1998, Icarus, 134, 47, doi: 10.1006/icar.1998.5954
  * Richardson et al. (2002) Richardson, D. C., Leinhardt, Z. M., Melosh, H. J., Bottke, W. F., J., & Asphaug, E. 2002, in Asteroids III, 501–515
  * Schunová et al. (2012) Schunová, E., Granvik, M., Jedicke, R., et al. 2012, Icarus, 220, 1050, doi: 10.1016/j.icarus.2012.06.042
  * Schunová et al. (2014) Schunová, E., Jedicke, R., Walsh, K. J., et al. 2014, Icarus, 238, 156, doi: 10.1016/j.icarus.2014.05.006
  * Valsecchi et al. (2003) Valsecchi, G. B., Milani, A., Gronchi, G. F., & Chesley, S. R. 2003, A&A, 408, 1179, doi: 10.1051/0004-6361:20031039
  * Walsh (2018) Walsh, K. J. 2018, ARA&A, 56, 593, doi: 10.1146/annurev-astro-081817-052013
  * Warner et al. (2021) Warner, B. D., Harris, A. W., & Pravec, P. 2021, NASA Planetary Data System, 10, doi: 10.26033/j3xc-3359
  * Williams et al. (2018) Williams, J. P., Bandfield, J. L., Paige, D. A., et al. 2018, Journal of Geophysical Research (Planets), 123, 2380, doi: 10.1029/2018JE005652
  * Zhang & Michel (2020) Zhang, Y., & Michel, P. 2020, A&A, 640, A102, doi: 10.1051/0004-6361/202037856