\documentstyle[a4,12pt]{article}
\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\qed  }{\hfill$\Box$\medskip}
\newcommand{\Ff}{{\bf F}}
\newcommand{\Qq}{{\bf Q}}
\newcommand{\Zz}{{\bf Z}}
\newcommand{\eps}{\epsilon}
\newcommand{\mod}{{\rm mod\,}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\title{The distance-regular graphs of valency four}
\author{A.E. Brouwer \& J.H. Koolen}
\date{November 16, 1996}
\begin{document}
\maketitle

\begin{abstract}
We show that each distance-regular graph of valency four
has known parameters.
\end{abstract}

In this note we report on a computer search that proves that
each distance-regular graph of valency four has known parameters.
Here we describe first the known examples, next how putative arrays
were disposed of, and finally how the search could be limited
to a manageable number of arrays.

The distance-regular graphs of valency 3 have been determined by
Biggs, Boshier \& Shawe-Taylor \cite{BBSt}.
Bannai \& Ito worked on the general project of bounding the diameter
of a distance-regular graph as a function of its valency $k$. They succeeded
in the bipartite case (\cite{BIval3}) and in case $k = 4$
(\cite{BIval4})\footnote{The second author very recently succeeded
in handling the cases $k = 5,6,7$.}.
This means that finding the feasible arrays for distance-regular graphs
of valency 4 was reduced to a finite amount of work, but the diameter bounds
obtained were not small enough to straightforwardly settle this case.
In this note we obtain some additional conditions, and thus reduce the
parameter space to be searched, and describe a way to test a parameter
set using (small) integer arithmetic, thus avoiding accuracy problems.

Our notation for distance-regular graphs is standard -- cf. \cite{B,BI,BCN}.

\section{The known distance-regular graphs of valency four}
The following distance-regular graphs of valency four are known
(we give an ordinal number, the number of vertices $v$,
the diameter $d$, the intersection array and the spectrum).

\noindent
\begin{tabular}{rrcll}
\# & $v$ & $d$ & intersection array & spectrum \\
\hline \\
1. & 5 & 1 & \{4;1\} & $4^1 ~ (-1)^4$ \\
2. & 6 & 2 & \{4,1;1,4\} & $4^1 ~ 0^3 ~ (-2)^2$ \\
3. & 8 & 2 & \{4,3;1,4\} & $\pm 4^1 ~ 0^6$ \\
4. & 9 & 2 & \{4,2;1,2\} & $4^1 ~ 1^4 ~ (-2)^4$ \\
5. & 10 & 3 & \{4,3,1;1,3,4\} & $\pm(4^1 ~ 1^4)$ \\
6. & 14 & 3 & \{4,3,2;1,2,4\} & $\pm(4^1 ~ \sqrt{2}{\,}^6)$ \\
7. & 15 & 3 & \{4,2,1;1,1,4\} & $4^1 ~ 2^5 ~ (-1)^4 ~ (-2)^5$ \\
8. & 16 & 4 & \{4,3,2,1;1,2,3,4\} & $\pm(4^1 ~ 2^4) ~ 0^6$ \\
9. & 21 & 3 & \{4,2,2;1,1,2\} & $4^1 ~ (1\pm\sqrt{2})^6 ~ (-2)^8$ \\
10. & 26 & 3 & \{4,3,3;1,1,4\} & $\pm(4^1 ~ \sqrt{3}{\,}^{12})$ \\
11. & 32 & 4 & \{4,3,3,1;1,1,3,4\} & $\pm(4^1 ~ 2^{12}) ~ 0^6$ \\
12. & 35 & 3 & \{4,3,3;1,1,2\} & $4^1 ~ 2^{14} ~ (-1)^{14} ~ (-3)^6$ \\
13. & 45 & 4 & \{4,2,2,2;1,1,1,2\} & $4^1 ~ 3^9 ~ 1^{10} ~ (-1)^9 ~ (-2)^{16}$ \\
14. & 70 & 7 & \{4,3,3,2,2,1,1;1,1,2,2,3,3,4\} & $\pm(4^1 ~ 3^6 ~ 2^{14} ~ 1^{14})$ \\
15. & 80 & 4 & \{4,3,3,3;1,1,1,4\} & $\pm(4^1 ~ \sqrt{6}{\,}^{24}) ~ 0^{30}$ \\
16. & 189 & 6 & \{4,2,2,2,2,2;1,1,1,1,1,2\} & $4^1 ~ (1\pm\sqrt{6})^{21} ~ (1\pm\sqrt{2})^{27} ~ 1^{28} ~ (-2)^{64}$ \\
17. & 728 & 6 & \{4,3,3,3,3,3;1,1,1,1,1,4\} & $\pm(4^1 ~ 3^{104} ~ \sqrt{3}{\,}^{168}) ~ 0^{182}$ 
\end{tabular}
\medskip

Descriptions of these graphs: 1. Complete graph $K_5$.
2. $K_{3\times2}$ (octahedron).
3. Complete bipartite graph $K_{4,4}$.
4. $3 \times 3$ grid.
5. $K_{5,5}$ minus a matching.
6. Nonincidence graph of $PG(2,2)$.
7. Line graph of the Petersen graph.
8. 4-cube.
9. Flag graph of $PG(2,2)$.
10. Incidence graph of $PG(2,3)$.
11. Incidence graph of $AG(2,4)$ minus a parallel class.
12. Odd graph $O_4$.
13. Flag graph of $GQ(2,2)$.
14. Doubled Odd graph.
15. Incidence graph of $GQ(3,3)$.
16. Flag graph of $GH(2,2)$.
17. Incidence graph of a $GH(3,3)$.
(Here $PG(2,q)$ and $AG(2,q)$ denote the projective and affine
planes of order $q$, $GQ(q,q)$ and $GH(q,q)$ denote a
generalized quadrangle or hexagon of order $q$.)

In each of these cases there is a unique graph with these parameters,
except possibly in the last case, since uniqueness of $GH(3,3)$ (a
generalized hexagon of order 3) is not known.
Each of these graphs is distance-transitive, except for those under 15.
and 16. -- indeed, $GQ(3,3)$ and $GH(2,2)$ are not self-dual.
(The single known example of a $GH(3,3)$ is distance-transitive;
any further examples will not be.)

Nomura \cite{Nom} found the seven distance-regular graphs with
valency four and girth three. Thus, we may assume that $a_1 = 0$.

(The classification is very easy: If $a_1 = 3$ then we are in
case 1; if $a_1 = 2$ then $\Gamma$ is locally a quadrangle,
and hence is the octahedron, case 2; finally, if $a_1 = 1$,
then $\Gamma$ is locally $2K_2$, and hence the line graph of a
cubic graph. But the distance-regular line graphs are known
(Mohar \& Shawe-Taylor \cite{MS}; \cite{BCN}, 4.2.16)
and we find cases 4 and 7, and the flag graphs of generalized
polygons of order $(2,2)$, cases 9, 13, 16. In all cases the
graph is uniquely determined by the parameters. For the uniqueness
(up to duality) of $GH(2,2)$, see Cohen \& Tits \cite{CT}.)

Our main theorem is:

\begin{Theorem}
Any distance-regular graph of valency 4 has one of the 17
intersection arrays listed above
(and hence is one of the 16 graphs described above,
or is the point-line incidence graph a generalized hexagon of order 3).
\end{Theorem}

\section{A test for feasibility}
\label{test}
Let $\Gamma$ be a distance-regular graph with $v$ vertices,
of diameter $d$, and with intersection array
$\{b_0,b_1, ..., b_{d-1}; c_1,c_2, ..., c_d\}$.
Then $\Gamma$ is regular of valency $k := b_0$, and
there are $k_i := b_0 b_1 ... b_{i-1} / c_1 c_2 ... c_i$
vertices at distance $i$ from any given vertex.
Let $M$ be the tridiagonal matrix
$$\left(\begin{array}{ccccc}
0 & b_0 \\
c_1 & a_1 & b_1 \\
 & c_2 & a_2 & b_2 \\
 & & . & . & . \\
 & & & c_d & a_d
\end{array}\right)$$
and define polynomials $u_i$ of degree $i$ ($0 \le i \le d$)
by $u_0(x) = 1$ and $c_i u_{i-1}(x) + a_i u_i (x) + b_i u_{i+1} (x)
= x u_i (x)$, i.e.,
$u_{i+1}(x) = ((x-a_i) u_i (x) - c_i u_{i-1} (x))/b_i$.
(Here $c_0 u_{-1}(x) = 0$.)
Put $f(x) = (x-a_d)u_d(x) - c_d u_{d-1}(x)$, and
$F(x) = \sum_{i=0}^d k_i u_i(x)^2$.
Then $f$ has $d+1$ distinct roots, the eigenvalues of $\Gamma$,
and if $f(\theta) = 0$, then $\theta$ is an eigenvalue of $\Gamma$
of multiplicity $f_{\theta} = v / F(\theta)$.
(All this is completely standard -- see \cite{B,BI,BCN}.)

A well-known and very strong criterion for the existence of a
distance-regular graph with given intersection array is the condition
that the $d+1$ multiplicities $f_{\theta}$ must be integral.
However, actually computing the $\theta$ and $v$ and $v/F(\theta)$
numerically yields practical difficulties: $v$ is very large,
possibly of the order of $(k-1)^d$, and one would have to compute
$\theta$ to an extreme precision in order to conclude that
$v/F(\theta)$ is not integral.
Therefore, we chose a different approach that allowed us to compute
with small integers only.

First observe that if $\theta_1$ and $\theta_2$ are algebraically
conjugate, then $f_{\theta_1} = f_{\theta_2}$, so that
$F(\theta_1) = F(\theta_2) = c$, say. If $m(x)$ is the irreducible
factor of $f(x)$ that has $\theta_1$ as zero, we find that
$m(x) | (F(x) - c)$.

This is a strong existence condition. Indeed, a priori one would
expect $F(x)$ mod $m(x)$ to have degree one less than the degree
of $m(x)$, while in fact it has degree zero, so the higher the
degree of $m(x)$, the stronger this condition. In fact, we do not
know of examples, apart from the polygons, where $m(x)$ has degree
higher than 3. Degree 3 occurs for the Biggs-Smith graph but for
no other known graph of valency more than 2.

Thus, if $f(x) = \prod_j m_j(x)$ is the factorization over $\Qq$
of $f$ into irreducible factors, then there are rational numbers
$c_j$ such that $m_j(x) | (F(x) - c_j)$, and hence
$$f(x) | \prod_j \gcd (f(x), F(x) - c_j) .$$
Unfortunately, we don't know the constants $c_j$, and they may be
quite large. So, let us reduce mod $p$.
Let $p$ be a prime not dividing $b_0 b_1 ... b_{d-1}$.
Then all denominators occurring in the coefficients of
$u_i$ and $f$ and $F$ are nonzero mod $p$, and we can reduce mod $p$
to conclude that
$$f(x) | \prod_{c=0}^{p-1} \gcd(f(x), F(x) - c)^{e_c} ~~~ (\mod p)$$
for certain exponents $e_c$.

It is possible to avoid all fractions, by using
$w_i = b_0 b_1 ... b_{i-1} u_i$ and
$g = b_0 ... b_{d-1} f$ and $G = b_0 ... b_{d-1} c_1 ... c_d F$.
Then $w_0(x) = 1$, $w_{i+1}(x) = (x - a_i) w_i(x) - b_{i-1} c_i w_{i-1}(x)$,
$g(x) = (x - a_d) w_d(x) - b_{d-1} c_d w_{d-1}(x)$ and
$G(x) = \sum_i b_i ... b_{d-1} c_{i+1} ... c_d w_i(x)^2$
(so that $w_i$, $g$ and $G$ are monic).
Again we have
$$g(x) | \prod_{c=0}^{p-1} \gcd(g(x), G(x) - c)^{e_c} ~~~ (\mod p),$$
this time for all primes $p$ (indeed, for all positive integers $p$).
For $p = 2$ this is useless (the condition reduces to the condition
that a polygon exists), but for $p \ge 3$ it produces restrictions.

This is the condition we applied: for $p=5,7,11,13$ compute
the $w_i$, $g$, $G$ (all mod $p$), compute $p$ times a gcd and remove
all factors found from $g$, possibly repeatedly. (If a nonlinear factor
is removed, additional gcds are necessary to see whether part of that
factor can be removed more than once.)
If after doing this a quotient of positive degree is left, no graph
with this intersection array exists.

[Usually, taking $p = 5$ sufficed; in a few cases also $p = 7$,
and in very few cases also $p = 11$ was required. After that only
the actual examples and four other arrays, of diameters
4, 6, 6, 6, survived.
Indeed, if $g$ completely factors into linear factors, or if $\Gamma$
is bipartite, and $g$ factors completely into factors $x^2 - a$
and possibly $x$, then our condition will be empty for all $p$.
This happens for three arrays:
for $\{4,3,3,2;1,1,2,4\}$ we have $g(x) = x(x^2 - 5)(x^2 - 16)$,
and for both $\{4,3,3,2,1,1;1,1,2,3,3,4\}$ and
$\{4,3,3,3,1,1;1,1,1,3,3,4\}$ we have
$g(x) = x(x^2 - 3)(x^2 - 7)(x^2 - 16)$.
However, it is easy to rule out these arrays -- for example,
each has nonintegral multiplicities.
In the nonbipartite case there is one additional parameter set:
$\{4,3,3,1,1,1;1,1,1,3,3,4\}$ for a nonexistent double cover
of $O_4$. Here $g(x) = x(x+1)(x-2)(x+3)(x-4)(x^2-7)$ and the
multiplicities are integral -- combinatorial considerations are
required to rule out this case (cf. \cite{BCN}, Proposition 9.1.9).]

Note that we have the Christoffel-Darboux formula
$G(x) = w_d(x) g'(x) - w_d'(x) g(x)$, so that we may replace
$G(x)$ by $w_d(x) g'(x)$ in the above formula. (This will speed up
the computations: the naive way of computing $G$ takes order $d^3$
steps, but for $w_d(x) g'(x)$ only order $d^2$ steps are required.)



\section{A divisibility condition}
Let $\Gamma$ be a distance-regular graph and $p$ a prime, such that
$c_{r+1}$ is divisible by $p$, but $c_i$ with $1 \le i \le r$ is not.
Consider the parameters $a_i, b_i, c_i$ and the matrices $A_i$
as being defined over the integers mod $p$.
Then $\langle I, A, ... , A_r \rangle$ is closed under multiplication,
and $A_i = f_i (A)$ for some polynomial $f_i$ of degree $i$ ($1 \le i \le r$).
(If $p$ divides the valency $k$ of $\Gamma$, then the same holds for
$\langle A , ... , A_r \rangle$.) Thus, $f(A) = 0$ for some polynomial
$f$ of degree $r+1$, but for no nonzero polynomial of smaller degree.

Now suppose moreover that $b_m = c_{m+t+1} = 0$ (mod $p$), and
$c_{m+i} , b_{m+i} \ne 0$ (mod $p$) for $1 \le i \le t$.
Then $\langle A_{m+1} , ... , A_{m+t} \rangle$ is closed under
multiplication by $A$, and if we put $B := A_{m+1}$, then
$A_{m+i} = g_{i-1}(A)B$ for some polynomial
$g_{i-1}$ of degree $i-1$ ($1 \le i \le t$).
Thus, $g(A)B = 0$ for some polynomial $g$ of degree $t$, but for no nonzero
polynomial of smaller degree. It follows that $g | f$.

This is a very useful condition. In order to apply it to the bipartite case,
we first need a lemma.

\begin{Lemma}
Define polynomials $p_i$ over any field $F$ by
$p_0 = 0$, $p_1(x) = x$, $p_{i+1}(x) = xp_i(x) - \lambda p_{i-1}(x)$
$(i \ge 1)$, where $\lambda$ is a nonzero constant.
Then $(p_i,p_j) = p_{(i,j)}$ (where $(-,-)$ denotes the g.c.d.).
In particular, $p_i | p_j$ if and only if $i | j$.
\end{Lemma}
\Proof
Modulo $p_i$ we find that $p_{i+k} = - \lambda^k p_{i-k}$
for $0 \le k \le i$ (by induction on $k$).
\qed

Let us give two applications of the above divisibility condition.

\begin{Proposition}
\label{divis}
Let $\Gamma$ be a distance-regular graph such that
$(c_i,a_i,b_i) \equiv (1,0,1)$ $(\mod 2)$ for $1 \le i \le r$
and for $d-t \le i \le d-1$, while
$b_0 \equiv c_{r+1} \equiv b_{d-t-1} \equiv c_d \equiv 0$ $(\mod 2)$.
Then $(t+1) | (r+1)$.
\end{Proposition}
\Proof
Take $F = \Ff_2$, $\lambda = 1$. With the notation of the lemma we have
(over $F$) $A_i = p_i (A)$ for $1 \le i \le r$, and $p_{r+1}(A) = 0$.
Similarly, $A_{d-i} = p_i(A) B$ ($1 \le i \le t$), where $B = A_d$,
and $p_{t+1}(A) B = 0$. It follows that $p_{t+1} | p_{r+1}$,
and the conclusion follows.
\qed

\begin{Proposition}
Let $\Gamma$ be a distance-regular graph such that
$(c_i,a_i,b_i) \equiv (1,0,1)$ $(\mod 2)$ for $1 \le i \le r$
and for $d-t \le i \le d-1$, while
$b_0 \equiv c_{r+1} \equiv b_{d-t-1} \equiv 0$ $(\mod 2)$ and
$c_d \equiv 1$ $(\mod 2)$.
Then $(2t+3) | (r+1)$.
\end{Proposition}
\Proof
With $B = A_d$ we find $A_{d-i} = q_i(A)B$ for $1 \le i \le t$,
and $q_{t+1}(A)B = 0$, where $q_i = p_i + p_{i-1} + ... + p_1 + 1$
(with notation as in the above lemma). By induction one sees that
$p_{2t+1}(x) = x q_t(x)^2$.
Thus, $q_{t+1} | p_{r+1}$ implies that $(p_{2t+3}, p_{r+1})$ has degree
at least $t+2$, so $(2t+3,r+1) \ge t+2$, so $(2t+3) | (r+1)$.
\qed


Let $\Gamma$ be a bipartite distance-regular graph of valency four.
Then there are integers $r,s,t$ such that
$(c_i,a_i,b_i) = (0,0,4)$, $(1,0,3)$, $(2,0,2)$, $(3,0,1)$, $(4,0,0)$
for $i = 0$, for $1 \le i \le r$, for $r+1 \le i \le r+s$,
for $r+s+1 \le i \le r+s+t$, and for $i = r+s+t+1$, respectively.
The diameter $d$ of $\Gamma$ equals $d = r+s+t+1$.
In this case the divisibility condition says: if $s > 0$, then
$(t+1) | (r+1)$.


\medskip
\medskip


After writing the above we discovered that (the case $t > 1$ of)
Proposition 3.2 is the contents of Nomura \cite{Nom3}.
More generally, Nomura \cite{Nom2} communicates a result which
is the case $\eps = -1$ of the following:

\begin{Proposition}
Let $\Gamma$ be a distance-regular graph such that, for some prime $p$
and integer $\eps = \pm 1$, we have
$(c_i,a_i,b_i) \equiv (1,0,-1)$ $(\mod p)$ for $1 \le i \le r$
and
$(c_i,a_i,b_i) \equiv (\eps ,0,-\eps )$ $(\mod p)$ for $m+1 \le i \le m+t$,
while $b_0 \equiv c_{r+1} \equiv b_m \equiv c_{m+t+1} \equiv 0$ $(\mod p)$.
If $t > 1$, then $(t+1) | (r+1)$.
\end{Proposition}
\Proof
Put $\lambda = -1$. With $B = A_{m+1}$ we find
$\eps^{i-1} A_{m+i} = (p_i/p_1)(A) B$ and $(p_{t+1}/p_1)(A) B = 0$
so that $p_{t+1} (x) | x p_{r+1} (x)$, and $(t+1,r+1) \ge t$. \qed

\section{The intersection array in case $k = 4$}
Given any distance-regular graph with intersection array
$\{b_0,b_1, ..., b_{d-1}; c_1,c_2, ..., c_d\}$, we put
$k = b_0$ and $a_i = k - b_i - c_i$ as usual.
Let $e_{cab}$ denote the number of indices $i$ for which
$(c_i,a_i,b_i) = (c,a,b)$.

\begin{Lemma}
Let $\Gamma$ be a distance-regular graph of valency $4$.
Then we have one of three cases.
\begin{enumerate}
\item[{\rm (i)}]
$\Gamma$ is bipartite.
\item[{\rm (ii)}]
$\Gamma$ is a generalized Odd graph ($a_i = 0$ for $i < d$, $a_d \ne 0$).
\item[{\rm (iii)}]
$\Gamma$ has $a_i > 0$ for some $i < d$, and $e_{202} = 0$.
\end{enumerate}
\end{Lemma}
\Proof
By the Brouwer-Lambeck inequalities (if $a_i \ne 0$, and $i < d$, then
$b_i \le a_i + a_{i+1}b_i/a_i$, and if $i > 1$ then
$c_i \le a_i + a_{i-1}c_i/a_i$, see \cite{BCN}, Proposition 5.5.4)
it follows that if $(c_i,a_i,b_i) = (1,1,2)$, then $a_{i+1} \ne 0$,
and if $(c_i,a_i,b_i) = (2,1,1)$, then $a_{i-1} \ne 0$.
It follows that if $e_{202} > 0$, then $e_{211} = e_{112} = e_{121} = 0$,
so that $a_i = 0$ for $i < d$.
\qed

Once Case (i) has been handled, Case (ii) is easy:
If $\Gamma$ is a generalized Odd graph, then its bipartite double is
distance-regular of diameter $2d+1$, an antipodal 2-cover of $\Gamma$,
so that $\Gamma$ can be retrieved from it by folding
(see \cite{BCN}, Proposition 4.2.11).
We shall find that the only bipartite graphs of odd diameter that are
antipodal 2-covers are $K_{5,5}$ minus a matching ($v = 10$)
and the doubled Odd graph ($v = 70$);
folding these we find $K_5$ ($v = 5$) and $O_4$ ($v = 35$).

{}From now on, we shall assume that we are not in Case (ii).
This leaves us with two cases: the bipartite case, where we put
$r = e_{103}$, $s = e_{202}$, $t = e_{301}$,
and the case where $a_i > 0$ for some $i < d$, where we put
$r = e_{103}$, $s_1 = e_{112}$, $s_2 = e_{121}$, $s_3 = e_{211}$,
$t = e_{301}$.

\begin{Lemma}
\label{bcsmall}
Let $\Gamma$ be a distance-regular graph of valency $4$.
Then
\begin{enumerate}
\item[{\rm (i)}]
$t \le r$.
\item[{\rm (ii)}]
If $t > 0$, then $a_d = 0$.
\item[{\rm (iii)}]
If $s_1 > 0$, $s_2 = s_3 = 0$, then $t = 0$ and $a_d \ne 0$.
\end{enumerate}
\end{Lemma}
\Proof
(i) This follows since $k_d$ is integral.
(ii) This follows from \cite{BCN}, Proposition 5.5.7.
(iii) This follows from the Brouwer-Lambeck inequalities.
\qed

A bound on $e_{112}$ is provided by the following two results.

\begin{Proposition} {\rm (Boshier \& Nomura \cite{BN}, cf.\ \cite{BCN}, 5.10.1)}
Let $\Gamma$ be a distance-regular graph of valency $k$.
If $e_{1,1,k-2} \ge 3$ then $3 | e_{1,0,k-1}$, and
if moreover $e_{1,0,k-1} > 0$ then $e_{1,1,k-2} \le 4$.
\end{Proposition}

\begin{Proposition} {\rm (Hiraki \cite{Hi2})}
Let $\Gamma$ be a distance-regular graph
of valency $k > 3$ with $a_1 = 0$. Then $e_{1,1,k-2} \le 3$, and if
$e_{1,1,k-2} = 3$, then $c_{r+4} > 1$, where $r = e_{1,0,k-1}$.
\end{Proposition}

In our case this means that $s_1 \le 3$,
and if $s_1 = 3$, then $3 | r$ and $s_2 = 0$ and $c_d > 1$.

\begin{Lemma}
$s_3 \le s_1$.
\end{Lemma}
\Proof
Indeed, $k_d = 4.3^{r-t}.2^{s_1 - s_3} / c_d$.
If $c_d = 4$, then the conclusion follows by integrality of $k_d$.
Otherwise, the conclusion follows by integrality of $p_{dd}^1 =
k_d p_{1d}^d / k_1 = 3^{r-t}.2^{s_1 - s_3}.(4 - c_d)/c_d$.
\qed

\begin{Lemma}
Assume $t > 0$, so that $s_2 + s_3 > 0$.
\begin{enumerate}
\item[{\rm (i)}]
If $s_3 > 0$, then either $t = r$ or $t \le (r + s_1 - s_3 - 2)/2$.
\item[{\rm (ii)}]
If $s_3 = 0$, $s_2 > 0$, then either $t = r$ or $(s_1,s_2,s_3) = (0,1,0)$
or $t \le \frac{1}{2}r - 1$.
\end{enumerate}
\end{Lemma}
\Proof
$\Gamma$ has girth $2r+3$, so if $t < r$, then no path
of length at most $2t+4$ can be a circuit.
Fix a vertex $x$, and put $D := \Gamma_d(x)$.
Let $N_l$ be the number of paths of length $l$ from $D$ to $D$.
If $\gamma_m$ is the number of geodesics between two vertices
at distance $m$, then there are precisely $\gamma_m \sum_{i=0}^m a_i$
paths of length $m+1$ between any two such vertices.

(i) Suppose $s_3 > 0$. On the one hand, we find
$N_{2t+3} = k_d p_{d,2t+3}^d c_1 ... c_{2t+3} = p_{d,d}^{2t+3} b_0 ... b_{2t+2}$.
On the other hand, we have
$N_{2t+3} = k_d \cdot 4 \cdot 3^t = k_{d-1-t} = 4 \cdot 3^r \cdot 2^{s_1-s_3}$.
It follows that $2t+3 \le 1 + r + s_1 - s_3$.

(ii) Suppose $s_3 = 0$, $s_2 > 0$.
We have $N_{2t+3} = 4 \cdot 3^t \cdot 2 \cdot k_d$
and $N_{2t+4} = 4 \cdot 3^t \cdot (2 + b_{d-t-2}-1) \cdot k_d$
so that $b_{d-t-2} + 1 \ge 2 \sum_{i=0}^{2t+3} a_i$, and
either $s_2 = 1$, $s_1 = 0$ or $2t+3 \le r+1$.
\qed

For the bipartite case we have two more restrictions:

\begin{Lemma}
If $s > 0$, then $(t+1) | (r+1)$.
\end{Lemma}
\Proof
This is just Proposition~\ref{divis}.
\qed

\begin{Proposition} {\rm (Suzuki \cite{Suz})}
Let $\Gamma$ be a distance-regular graph of valency $k$ and diameter $d$,
and with intersection array $\{b_0,b_1, ..., b_{d-1}; c_1,c_2, ..., c_d\}$.
Let $r := e_{1,0,k-1}$. If
$(c_{r+1},a_{r+1},b_{r+1}) = (c_{r+2},a_{r+2},b_{r+2}) = (2,0,k-2)$,
then $r$ is even.
\end{Proposition}

Using this saves (more than) half of the work in case $s \ge 2$.
However, since the total amount of work in the bipartite case
turned out to be rather small anyway, we have not used this proposition.
(But omitting it caused the prime $p = 13$ to be used twice.)

A bound on $s$ (in the bipartite case) or $s_2$ (in the non-bipartite case)
follows from Terwilliger's multiplicity bound, see Section \ref{terw} below.

\section{Location of the eigenvalues}
We shall need bounds on the eigenvalues of tridiagonal matrices $T$
such as $M$ (with positive entries on the diagonals above and below
the main diagonal). Write $\theta_{\rm min}(T)$, $\theta_{\rm max}(T)$
and $\theta_2(T)$ for the smallest, the largest, and the second largest
eigenvalue of $T$.

Perron-Frobenius tells us that if $S$ is a matrix obtained from $T$
by decreasing some elements, keeping the off-diagonal elements nonnegative,
then $\theta_{\rm max}(S) < \theta_{\rm max}(T)$.
Interlacing tells us that if $S$ is a principal submatrix of $T$, then
$\theta_{\rm min}(T) \le \theta_{\rm min}(S)$ and
$\theta_2(S) \le \theta_2(T)$ and
$\theta_{\rm max}(S) \le \theta_{\rm max}(T)$.
But we can be more precise. If $p_n$ is a series of orthogonal polynomials,
then for $n > m$ there is a root of $p_n$ between any two roots of $p_m$.
Since the characteristic polynomials $u_i$ of the upper right hand corner
$T_i$ (of order $i$) of $T$ form a sequence of orthogonal polynomials,
there is an eigenvalue of $T$ between any two eigenvalues of $T_i$.

The eigenvalues distinct from $k$ of the tridiagonal matrix $M$
are the eigenvalues of
$$M' = \left(\begin{array}{ccccc}
-c_1 & b_1 \\
c_1 & k-b_1-c_2 & b_2 \\
 & . & . & . \\
 & & c_{d-2} & k-b_{d-2}-c_{d-1} & b_{d-1} \\
 & & & c_{d-1} & k-b_{d-1}-c_d
\end{array}\right)$$
(cf. \cite{BCN}, p.\,130).

\begin{Lemma}
\label{pfi}
Let $\iota = \{b_0,...,b_{d-1};~c_1,...,c_d\}$ be an intersection array,
and put $r = e_{1,0,k-1}$ and $t = e_{k-1,0,1}$, where $k = b_0$.
Then the second largest eigenvalue $\theta_2$ of the array will
decrease if we decrease $r$ or $t$ or $a_d$ $(= k-c_d)$.
\end{Lemma}
\Proof
By interlacing and Perron-Frobenius.
(i) Decreasing $r$ by one means removing the first row and column
of $M'$ and then decreasing the top left corner element.
(ii) Decreasing $t$ by one means removing the last row and column
of $M'$ possibly followed by decreasing the bottom right corner element.
(iii) $a_d$ only occurs in the diagonal element $a_d - b_{d-1}$ of $M'$.
\qed

Let us apply these ideas in the case of valency 4.

\begin{Lemma}
\label{bound202}
Let $\Gamma$ be a bipartite distance-regular graph of valency 4,
and put $s = e_{202}$. Then $\theta_2 (\Gamma) > 4 \cos {\pi \over s+1}$.
\end{Lemma}
\Proof
Decrease both $r$ and $t$ to 0. Now $M$ is twice the tridiagonal matrix
of a circuit of size $2(s+1)$ and has eigenvalues
$4 \cos {2 \pi j \over 2s+2}$ $(0 \le j \le 2s+1)$.
\qed

Similarly, we have for the nonbipartite case:

\begin{Lemma}
\label{bound121}
Let $\Gamma$ be a distance-regular graph of valency 4, with
$s_2 := e_{121} > 1$.
Then $\theta_2 (\Gamma) > 2 + 2 \cos { \pi \over s_2 }$.
If both $s_1 > 0$ and $s_3 > 0$, then even
$\theta_2 (\Gamma) > 2 + 2 \cos { \pi \over s_2 + 1}$.
\end{Lemma}
\Proof
$M'$ has a submatrix $2I+A$, where $A$ is the adjacency matrix of
a path of $s_2-1$ vertices, and hence has largest eigenvalue
$2 + 2\cos {\pi \over s_2}$.
If both $s_1$ and $s_3$ are nonzero, then we can pick a submatrix of size
$s_2+1$ and find $2I+C'$ where $C'$ is a matrix that has as its eigenvalues
the different eigenvalues other than $2$ of a circuit of size $2(s_2+1)$,
so that this submatrix has largest eigenvalue
$2 + 2\cos {2 \pi \over 2(s_2+1)}$.
\qed

\begin{Lemma}
\label{negbd}
Let $\Gamma$ be a distance-regular graph of valency 4, and put
$r := e_{103}$. If $r > 0$ then
$\theta_2 (\Gamma) > 2\sqrt{3}\cos {\pi \over r}$
and $\theta_{\rm min} (\Gamma) < -2\sqrt{3}\cos {\pi \over r+1}$.
Moreover, each interval
$(2\sqrt{3}\cos {\pi (j+1) \over r}, 2\sqrt{3}\cos {\pi j \over r+1})$
$(j=1,...,r-1)$ contains an eigenvalue of $\Gamma$.
\end{Lemma}
\Proof
The submatrix of $M'$ formed by rows and columns 1 up to $r$
has eigenvalues $\psi_j$ with
$2\sqrt{3}\cos {\pi j \over r} < \psi_j < 2\sqrt{3}\cos {\pi j \over r+1}$
$(j=1,...,r)$.
\qed

Using Sturm sequences, we can show that in the nonbipartite case
the smallest eigenvalue is not too small. (In the bipartite case
the smallest eigenvalue equals $-k$, and only a bound on the second
smallest eigenvalue would be interesting.)
\begin{Theorem}
Let $\Gamma$ be a distance-regular graph of diameter $d > 1$,
and $\sigma$ a positive real number satisfying\\
(i) $\sigma^2 + a_1 \sigma - {1 \over 2}k \ge 0$, and\\
(ii) $\sigma^2 + a_i \sigma - b_{i-1} c_i \ge 0$ ($2 \le i \le d-1$), and\\
(iii) $\sigma^2 + {1 \over 2} a_d \sigma - {1 \over 2} b_{d-1} c_d \ge 0$.\\
Let $\theta$ be the smallest eigenvalue of $\Gamma$.
Then $\theta \ge -2 \sigma$ with equality if and only if equality holds
in all inequalities (i),(ii),(iii).
\end{Theorem}
\Proof
The number of eigenvalues larger than or equal to $\alpha$
equals the number of sign changes in the sequence $u_i(\alpha)$
$(0 \le i \le d+1)$ (where a sign change is either a zero entry
or a pair of subsequent elements of opposite sign), so we want to show that
$u_i(-2\sigma)$ has sign $(-1)^i$ for all $i$.
The $u_i$ are given by $u_0 = 1$, $u_1 = -2\sigma/k$,
$c_i u_{i-1} + (a_i + 2\sigma) u_i + b_i u_{i+1} = 0$.
Scale the $u_i$ by putting $q_i = b_0 b_1 ... b_{i-1} u_i / (-\sigma)^i$.
Then $q_0 = 1$, $q_1 = 2$ and
$q_{i+1} = (2 + {a_i \over \sigma}) q_i - {b_{i-1}c_i \over \sigma^2} q_{i-1}$.
Now the number of eigenvalues smaller than or equal to $-2\sigma$ equals
the number of sign changes of $q_i$ $(0 \le i \le d+1)$.
By induction on $i$ we show that $q_{i+1} \ge q_i \ge 2$ $(1 \le i \le d-1)$.
For $i = 1$ this follows from (i), and for $2 \le i \le d-1$ from (ii).
Finally, $q_{d+1} \ge 0$ then follows from (iii).
\qed

Examples with equality are the the flag graphs (of diameter $m$) of
the generalized $m$-gons of order $(s,t) = (q,q)$.
(These have intersection array $\{2q,q,...,q; 1,...,1,2\}$.
For $q = 1$ we find the even polygons.
For $m = 2$ these are the lattice graphs ($(q+1) \times (q+1)$ grid graphs).
Examples exist for $m = 3,4,6$.)
All these examples have $\sigma = 1$.

\begin{Corollary}
\label{lowbd}
Let $\Gamma$ be a distance-regular graph of valency 4, not bipartite
and not a generalized Odd graph.
Then the smallest eigenvalue of $\Gamma$ is larger than $-2\sqrt{3}$.
\end{Corollary}
\Proof
This follows directly from the above theorem and Lemma \ref{bcsmall} (iii).
\qed

According to Lemma \ref{negbd}, for large $r$
many roots lie close to $-2\sqrt{3}$, so this bound cannot be improved.

\section{Terwilliger's multiplicity bound}
\label{terw}
\begin{Proposition}
{\rm (cf.\ Terwilliger \cite{Tw}).}
Let $\Gamma$ be a distance-regular graph of valency $k$, and $T$ a
tree in $\Gamma$ such that for all vertices $u,v,w \in T$, if
$d_T(u,v) = d_T(u,w)$ then also $d_{\Gamma} (u,v) = d_{\Gamma} (u,w)$.
Then the multiplicity $f$ of any eigenvalue $\theta \ne \pm k$
of $\Gamma$ is at least the number of leaves in $T$.
\end{Proposition}

\begin{Corollary}
If $(c_1,a_1,b_1) = (c_r,a_r,b_r) = (1,0,3)$, then
$f \ge 2 . 3^{r/2}$ (and if $r$ is odd, then even
$f \ge 4 . 3^{(r-1)/2}$).
\end{Corollary}

This lower bound on the multiplicity implies that the second largest
eigenvalue $\theta$ of $\Gamma$ cannot be too large, otherwise
its multiplicity $f$ would be too small.

Let us work out the details for bipartite $\Gamma$ of valency 4.
As before, let $r = e_{103}$, $s = e_{202}$, $t = e_{301}$, so
that $d = r+s+t+1$. Then
\begin{eqnarray*}
v & = & 1 + \underbrace{4 + ... + 4.3^{r-1}}_{r ~ {\rm terms}} +
\underbrace{2.3^r + ... + 2.3^r}_{s ~ {\rm terms}} +
\underbrace{4.3^{r-1} + ... + 4.3^{r-t}}_{t ~ {\rm terms}} + 3^{r-t} \\
& = & 1 + 2(3^r - 1) + 2s.3^r + 2.3^{r-t}(3^t - 1) + 3^{r-t}
~ \le ~ 2(s+2)3^r - 2
\end{eqnarray*}
(since $t \le r$).

For any eigenvalue $\theta$ distinct from $\pm 2 \sqrt{3}$, let us
compute $u_i = u_i(\theta)$. Using $u_0 = 1$,
$u_1 = \frac{1}{4} \theta$ and the three-term recurrence relation,
we find
$$u_i = \alpha \lambda^i - \beta \mu^i ~~~ ({\rm for} ~ 0 \le i \le r+1)$$
where $\alpha = (\frac{1}{4} \theta - \mu)/(\lambda - \mu)$
and $\beta = (\frac{1}{4} \theta - \lambda)/(\lambda - \mu)$,
and $\lambda, \mu$ are the two roots of $3 x^2 - \theta x + 1 = 0$.
Now assume that $2 \sqrt{3} < \theta < 4$. Then $\lambda$ and $\mu$
are real, and we can choose them such that
$\frac{1}{3} < \mu < \frac{1}{\sqrt{3}} < \lambda < 1$.

\newcommand{\approxless}{~ \begin{array}{c}
< \\*[-1.6ex] \sim
\end{array}  ~}
\newcommand{\approxmore}{~ \begin{array}{c}
> \\*[-1.6ex] \sim
\end{array}  ~}
For large $r$ we find $u_r \sim \alpha \lambda^r$, and
$$2.3^{r/2} \le f \le {v \over {k_r u_r^2}} \approxless
{{2(s+2)3^r} \over {\frac{4}{3}.3^r.\alpha^2.\lambda^{2r}}}$$
so that
$$(\lambda^2 \sqrt{3})^r \approxless
{{3(s+2)} \over {4\alpha^2}} \le {{3(r+2)} \over {4\alpha^2}}$$
(since $s \le r$, by Terwilliger, cf \cite{BCN}, 5.2.5).
Consequently, we find a bound on $r$ provided that
$\lambda^2 \sqrt{3} > 1$ (i.e., $\lambda \approxmore 0.76$),
i.e., provided that $\theta > 3^{1/4} + 3^{3/4}$
(i.e., $\theta \approxmore 3.6$).

\medskip
Let us do the precise calculations.
Assume that $\theta > 3^{1/4} + 3^{3/4}$ so that
$\lambda^2 \sqrt{3} > 1$.
Since $\theta < 4$ and $\lambda + \mu = \frac{1}{3} \theta$ and
$\lambda - \mu = \sqrt{\frac{1}{9} \theta^2 - \frac{4}{3}} > \frac{1}{3}$
we find $3 \lambda - \mu > \frac{2}{3} + \frac{1}{3}\theta >
\frac{1}{2}\theta$, so that $\alpha > 3 \beta$.

Also, $\alpha > 1$ since $\lambda < \frac{1}{4}\theta$
(because $(\lambda - \frac{1}{4}\theta)(\lambda - \frac{1}{12}\theta)
= \frac{1}{48}(\theta^2 - 16) < 0$).

Thus, $u_r > \left( ({\lambda \over \mu})^r - \frac{1}{3} \right) \mu^r$.

Since ${\lambda \over \mu} = {{\lambda^2} \over {\lambda \mu}} > \sqrt{3}$
we find for $r \ge 7$ that $u_r \ge 0.99 \lambda^r$.
Thus, for $r \ge 7$, we have
$$(\lambda^2 \sqrt{3})^r < {{s+2} \over {\frac{4}{3} (0.99)^2}} <
0.77 (s+2) \le 0.77 (r+2).$$

\medskip
{}From Lemma \ref{bound202} we know that if $s$ is large,
then $\theta := \theta_2$ is large.

Suppose $s \ge 8$. Then $\theta > 4 \cos {\pi \over 9} > 3.758$.
Next, $\lambda = (\theta + \sqrt{\theta^2 - 12})/6 > 0.869$
and $\lambda^2 \sqrt{3} > 1.3$ and $(\lambda^2 \sqrt{3})^8 > 8 >
0.77 \times 10$, a contradiction. Hence $s \le 7$.

Suppose $s = 7$. Then $\theta > 4 \cos {\pi \over 8} > 3.695$
and $\lambda > 0.83$ and $\lambda^2 \sqrt{3} > 1.193$.
Now from $1.193^r < 0.77(s+2) = 6.93$ we find $r \le 10$.

Suppose $s = 6$ and $r > 0$. Then by Lemma \ref{pfi}
we have $\theta > 3.64 > \sqrt{13}$.
But if $\theta \ge \sqrt{13}$ and $s \le 6$,
then $\lambda^2 \sqrt{3} > 1.02$.
Now from $1.02^r < 0.77(s+2) \le 6.16$ we find $r \le 91$.

Thus we proved: $s \le 7$, and if either $s \ge 6$ or
$\theta \ge \sqrt{13}$, then $r \le 91$.
Moreover, we have seen already that if $s > 0$, then $(t+1) | (r+1)$.

A small computer search of the region $\{(r,s,t) |
r \le 100,~ s \le 7,~ t \le r$ and if $s > 0$ then $(t+1) | (r+1) \}$
(using the test described in Section 2) finds only the known examples.

Thus we may now assume in the bipartite case that
$r > 100$ and $s \le 5$ and $\theta < \sqrt{13}$.

Next, consider the non-bipartite case.
As before, let
$r = e_{103}$, $s_1 = e_{112}$, $s_2 = e_{121}$, $s_3 = e_{211}$,
$t = e_{301}$, so that $d = r + s_1 + s_2 + s_3 + t + 1$. Then
\begin{eqnarray*}
v & = & 1 + \underbrace{4 + ... + 4.3^{r-1}}_{r ~ {\rm terms}} +
\underbrace{4.3^r + ... + 2.2^{s_1}.3^r}_{s_1 ~ {\rm terms}} +
\underbrace{4.2^{s_1}.3^r + ... + 4.2^{s_1}.3^r}_{s_2 ~ {\rm terms}} + \\ &&
\underbrace{4.2^{s_1 - 1}.3^r + ... + 4.2^{s_1 - s_3}.3^r}_{s_3 ~ {\rm terms}}
+ \underbrace{4.2^{s_1 - s_3}.3^{r-1} + ... +
4.2^{s_1 - s_3}.3^{r-t}}_{t ~ {\rm terms}} + \\&&
4.2^{s_1 - s_3}.3^{r-t}/c_d \\
& = & 1 + 2(3^r - 1) + 4.3^r.(2^{s_1}-1) + 4.2^{s_1}.3^r.s_2 + \\ &&
4.2^{s_1 - s_3}.3^r.(2^{s_3} - 1) + 2.2^{s_1 - s_3}.3^{r-t}.(3^t-1) + 
4.2^{s_1 - s_3}.3^{r-t}/c_d \\
& = & 4(s_2+2).2^{s_1}.3^r - 1 - 2.3^r - 2.2^{s_1-s_3}.3^r -
(2 - 4/c_d).2^{s_1-s_3}.3^{r-t} \\
& \le & 4(s_2+2).2^{s_1}.3^r - 1 - 2.3^r .
\end{eqnarray*}

Thus, we find here for $s_2 > 0$ that
$$2.3^{r/2} \le f \le {v \over k_r u_r^2} \le
{4(s_2+2).2^{s_1}.3^r \over {4 \over 3}.3^r.u_r^2 }$$
so that for $r \ge 7$ (using $u_r \ge 0.9928 \lambda^r$ and $s_1 \le 2$)
$$(\lambda^2 \sqrt{3})^r \le { 3 (s_2+2) 2^{s_1} \over 2 (0.9928)^2 }
< 6.09 (s_2+2) .$$

Now we want to bound $s_2$. In the bipartite case we could use $s \le r$.
Here we can use Ivanov's results (cf. \cite{BCN}, Corollary 5.9.6),
and find $s_2 \le r + s_1 + 1 \le r + 3$.

Suppose $s_2 \ge 13$. Then (by Lemma \ref{bound121})
$\theta > 2 + 2\cos {\pi \over 13} > 3.94$.
Next, $\lambda = (\theta + \sqrt{\theta^2 - 12})/6 > 0.969$
and $\lambda^2 \sqrt{3} > 1.626$
and $(\lambda^2 \sqrt{3})^r > 129 > 15 \times 6.09$, a contradiction.
Hence $s_2 \le 12$.

Suppose $s_2 \ge 6$. Then $\theta > 2 + 2\cos {\pi \over 6} = 2 + \sqrt{3}$,
and $\lambda > .8534$ and $\lambda^2 \sqrt{3} > 1.261$, so that
$1.261^r < 85.26$, and $r < 20$.

Suppose $s_2 = 5$ or $s_2 = 4$, $s_1 > 0$, $s_3 > 0$.
Then $\theta > 2 + 2\cos {\pi \over 5} > 3.61803$,
and $\lambda > 0.777$ and $\lambda^2 \sqrt{3} > 1.0456$, so that
$1.0456^r < 48.72$, and $r < 88$.

If $\theta \ge \sqrt{13} > 3.605$, then $\lambda > 0.7675$ and
$\lambda^2 \sqrt{3} > 1.02$, $r < 182$.

A computer search of the region $r < 200$ finds only the known
parameter sets. Thus, we may now assume in the nonbipartite case
that $r \ge 200$, $s_2 \le 4$, $\theta < \sqrt{13} \approx 3.60555$.

A few more cases can be ruled out using Lemma \ref{pfi}.
Indeed, if $r = 1$, $t = 0$, $(s_1,s_2,s_3) = (2,3,2)$ we find $\theta > 3.61$.
For $r = 1$, $t = 0$, $(s_1,s_2,s_3) = (1,4,0)$ we find $\theta > 3.61$.
For $r = t = 0$, $(s_1,s_2,s_3) = (2,4,0)$ we find $\theta > 3.64$.
Thus, $(s_1,s_2,s_3)$ is not (2,3,2), (1,4,0) or (2,4,0).

For the middle part $(s_1,s_2,s_3)$ the following 27 possibilities
are left: $(0,s_2,0)$ ($1 \le s_2 \le 4$),
$(1,s_2,0)$, $(2,s_2,0)$, $(1,s_2,1)$, $(2,s_2,1)$ ($0 \le s_2 \le 3$),
$(2,s_2,2)$, ($0 \le s_2 \le 2$),
$(3,0,s_3)$ ($0 \le s_3 \le 3$).

So, what is left now (in both cases) is to find an upper bound on $r$.
To this end, we follow Bannai \& Ito \cite{BIval4}.
The idea is to compute the multiplicity $f_{\theta}$ of an eigenvalue $\theta$
and show that it is different from the multiplicity $f_{\theta'}$ of an
algebraically conjugate eigenvalue $\theta'$, thus deriving a contradiction.
We first need some result that shows that conjugates $\theta'$ exist that
are sufficiently distinct from $\theta$.

\section{The distribution of conjugates of a totally real algebraic number}

Given an eigenvalue $\theta$ of $\Gamma$, we shall want to find
a conjugate $\theta'$ of $\theta$, not very close to $\theta$.
The following theorem shows that not all conjugates can lie
in a short interval.

\begin{Theorem} {\rm (Kronecker \cite{Kron})}
Suppose $\theta$ is an algebraic integer such that it and all its conjugates
are real and lie in $[-2,2]$. Then $\theta = 2 \cos { 2 \pi j \over m}$
for certain integers $j$ and $m$.
\end{Theorem}

All numbers $2 \cos { 2 \pi j \over m}$ with fixed $m$ and
$(j,m) = 1$ are conjugate. It follows that if $\theta$ and
all its conjugates lie in $(-2,2 \cos { 2 \pi \over n})$,
then $\theta = 2 \cos { 2 \pi j \over m}$ with $2 < m < n$.
In particular, if $\theta$ and all its conjugates
lie in $(-2,2 \cos {2\pi \over 7})$
(where $2 \cos {2\pi \over 7} \approx 1.2469796)$,
then $\theta \in \{ -1,0,1,(-1 \pm \sqrt{5})/2 \}$.

More generally, Schur \cite{Schur} (p. 391) shows that,
given an integer $a_0$ and a real interval $[p,q]$ of
length less than 4, there are only finitely many
polynomials $a_0 x^n + ... + a_n$ with integral
coefficients and real distinct roots, all in $[p,q]$.

A slightly better interval is provided by the following:

\begin{Theorem}
\label{algnumth}
Let $\alpha = (-3 + \sqrt{7 + 2 \sqrt{5}})/2 \approx 0.193527$.
Let $\theta$ be an algebraic integer such that all of its conjugates
are real. If $-\alpha < \theta < 3+\alpha$, then $\theta$ has an
algebraic conjugate $\theta'$ with $\theta' \le -\alpha$ or
$\theta' \ge 3+\alpha$, unless $\theta$ is one of the numbers
$0$, $1$, $2$, $3$, $(3 \pm \sqrt{5})/2$.
\end{Theorem}

\Proof
Let $p \in \Zz[X]$ be such that $0 < |p(\theta)| < 1$.
Since $\prod p(\theta')$ is integral, where $\theta'$ runs over
all conjugates of $\theta$, and is nonzero (since $\theta$ and
$\theta'$ are roots of the same polynomials in $\Zz[X]$), it has
absolute value at least 1, so that for some $\theta'$ conjugate
to $\theta$ we have $|p(\theta')| > 1$.
Remains to find, given any $\beta$ with $0 \le \beta < \alpha$
and $- \beta < \theta < 3+\beta$,
a polynomial $p \in \Zz[X]$ that satisfies
$|p(x)| \le 1$ for $-\beta \le x \le 3+\beta$ and $0 < |p(\theta)| < 1$.

Put $\tau = (1+\sqrt{5})/2$.
For any real $\xi$ with $|\xi| < \tau$, the sequence $\xi^{(i)}$
defined by $\xi^{(0)} = \xi$ and $\xi^{(i+1)} = (\xi^{(i)})^2 - 1$
satisfies $| \xi^{(i)} | \le 1$ for almost all $i$.
Starting with the function $f(X) = X^2 - 3X + 1$, which satisfies
$|f(x)| < \tau$ for $-\alpha < x < 3+\alpha$, we find after finitely
many steps a function $g(X) := f(X)^{(m)}$ that satisfies
$|g(x)| \le 1$ for $-\beta \le x \le 3+\beta$ and $|g( \theta )| < 1$.

Remains the question whether perhaps $g(\theta) = 0$.
We have $f^{(1)}(X) = X(X-1)(X-2)(X-3)$, which vanishes only on integers.
If $f^{(2)}(x) = 0$, then $|f^{(1)}(x)| = 1$, and we find
$x = (3 \pm \sqrt{5})/2$.
If $f^{(3)}(x) = 0$ but $f^{(1)}(x) \ne 0$, then $f^{(2)}(x) = 1$,
$f^{(1)}(x) = \pm \sqrt{2}$, but this only happens for $x$ that have
non-real conjugates.
\qed

For the application to distance-regular graphs, suppose that $\theta$
is an eigenvalue close to $2 \sqrt 3$. Then $\theta^2$ is close to
$12$, and has a conjugate outside $[9-\alpha,12+\alpha]$.
In other words, $\theta$ has a conjugate $\theta'$ with
$|\theta'| < 2.968$ or $|\theta'| > 3.491$.
Similarly, if $\sqrt{10} < \theta < \sqrt{13}$, then $\theta^2$
has a conjugate outside $[10-\alpha,13+\alpha]$, so there is
a conjugate $\theta'$ of $\theta$ with $|\theta'| < 3.132$ or
$|\theta'| > 3.632$.
In this latter case we need not worry about the possibility that
$\theta^2 = 10 + (3+\sqrt{5})/2$ in the nonbipartite case,
because $\theta$ would have a conjugate $- \sqrt{10 + (3+\sqrt{5})/2}$
and this is smaller than $-2 \sqrt{3}$, contradicting Corollary \ref{lowbd}.

\section{Formulas for the multiplicity}
Fix an eigenvalue $\theta$ of the tridiagonal matrix $M$.
If we define right and left eigenvectors $u$ and $v^\top$ of $M$
by $Mu = \theta u$ and $v^\top M = \theta v^\top$
and $u_0 = v_0 = 1$, then $v_i = k_i u_i$ and $\theta$ has
multiplicity
$f_\theta = v / \sum k_i u_i^2 = v / \sum u_i v_i =
v / \sum ( v_i^2 / k_i )$.

The $u_i$ satisfy the recurrence
$$c_i u_{i-1} + a_i u_i + b_i u_{i+1} = \theta u_i
~~ ({\rm and} ~ u_0 = 1,~ u_{-1} = 0)$$
and the $v_i$ satisfy the recurrence
$$b_{i-1} v_{i-1} + a_i v_i + c_{i+1} v_{i+1} = \theta v_i
~~ ({\rm and} ~ v_0 = 1,~ v_{-1} = 0).$$
In order to avoid fractions (and problems with the interpretation
of $v_{d+1}$), it is useful to define
$w_i = b_0 ... b_{i-1} u_i = c_1 ... c_i v_i$.
The $w_i$ satisfy the recurrence
$$w_{i+1} = (\theta - a_i)w_i - b_{i-1} c_i w_{i-1}
~~ ({\rm and} ~ w_0 = 1,~ w_{-1} = 0).$$
If we regard $\theta$ as a variable, then these recurrences
define polynomials $u_i$, $v_i$, $w_i$ of degree $i$ in $\theta$.

\begin{Lemma}
\label{darboux}
$$\sum_{i=0}^l b_i ... b_{l-1} c_{i+1} ... c_l \, w_i(X)^2 =
w_{l+1}'(X) w_l(X) - w_l'(X) w_{l+1}(X) .$$
\end{Lemma}
\Proof
Use induction on $l$. We have to show that
$w_{l+2}'(X) w_{l+1}(X) - w_{l+1}'(X) w_{l+2}(X) =
b_l c_{l+1} ( w_{l+1}'(X) w_l(X) - w_l'(X) w_{l+1}(X) ) + w_{l+1} (X)^2$,
and this is clear from the recurrence relation (applied to $w_{l+2}$).
\qed

\begin{Lemma}
$$f_\theta = { vb_0 ... b_{d-1} c_1 ... c_d  \over
w_{d+1}'(\theta) w_d(\theta)} .$$
\end{Lemma}
\Proof
From the above we find
$f_\theta = v / \sum k_i u_i^2 =
vb_0 ... b_{d-1} c_1 ... c_d / (w_{d+1}' w_d - w_d' w_{d+1})$
but $w_{d+1}(\theta) = 0$.
\qed

Put $F_i = c_1 ... c_i (v_0 + ... + v_i) =
\sum_{j=0}^i c_{j+1} ... c_i w_j$,
then $F_i$ satisfies the recurrence
$$F_{i+1} = (\theta - k + b_i + c_{i+1}) F_i - b_ic_i F_{i-1}
~~ ({\rm and} ~ F_0 = 1,~ F_{-1} = 0).$$
Now $w_{d+1} = (\theta - k)F_d$ and $w_d = F_d - c_d F_{d-1}$.

\begin{Lemma}
\label{multip}
If $\theta \ne k$, then $$f_\theta = { vb_0 ... b_{d-1} c_1 ... c_{d-1}
\over (k-\theta) F_d'(\theta) F_{d-1}(\theta)} .$$
\end{Lemma}
\Proof
From the above, since $F_d (\theta) = 0$.
\qed

The following theorem, due to Bannai \& Ito \cite{BIval4},
expresses the dependence of the multiplicity of an eigenvalue
$\theta$ on $r = e_{1,0,k-1}$. We see that if $\theta$ stays
away from $\pm 2\sqrt{k-1}$ the multiplicity behaves like
$Cr^{-1}$, while close to $\pm 2\sqrt{k-1}$ the multiplicity
is much smaller. A bound on $r$ is obtained by showing that
there are conjugate eigenvalues, one close to $\pm 2\sqrt{k-1}$,
the other not.

\begin{Theorem}
Let $\Gamma$ be a distance-regular graph with $v$ vertices,
and with valency $k$, and let $\theta$ be an eigenvalue of $\Gamma$
distinct from $\pm k$ and from $\pm 2\sqrt{k-1}$.
Put $r := e_{1,0,k-1}$ and $t := e_{k-1,0,1}$.
Put $\delta := 1 - a_d$ if $t > 0$ and $\delta := 0$ if $t = 0$.
If $a_1 = 0$, then the multiplicity $f_{\theta}$ of $\theta$
is given by
$$f_{\theta} = {1 \over 2} v k {4(k-1) - \theta^2 \over k^2 - \theta^2}
{1 \over M_{\theta}}$$
where
$$M_{\theta} = r + t {\lambda + \delta \over \lambda + 1}
{\mu + \delta \over \mu + 1} {P \bar{P} - Q \bar{Q} \over R \bar{R}}
+ {\lambda - \mu \over 2} {R \bar{D} - \bar{R} D \over R \bar{R}}$$
where $\lambda$, $\mu$ are the two roots of $X^2 - \theta X + k-1 = 0$
(so that $\lambda + \mu = \theta$ and $\lambda \mu = k-1$
and $(\lambda+1)(\mu+1)(\lambda - \mu) \ne 0$)
and $P$, $\bar{P}$, $Q$, $\bar{Q}$ are defined by
$$\left(\begin{array}{cc}
\bar{P} & \bar{Q} \\
Q & P
\end{array}\right) = \left(\begin{array}{cc}
\lambda^{-1} & 1 \\
\mu^{-1} & 1
\end{array}\right) T_{r+1} T_{r+2} ... T_{d-t} \left(\begin{array}{cc}
-\mu & -\lambda \\
1 & 1
\end{array}\right)$$
where
$$T_i = \left(\begin{array}{cc}
0 & -b_{i-1}c_{i-1} \\
1 & \theta - k + b_{i-1} + c_i
\end{array}\right)$$
(so that $P \bar{P} - Q \bar{Q} = (4(k-1) - \theta^2) b_{r+1} c_{r+1} ...
b_{d-t-1} c_{d-t-1}$)
and $R$, $\bar{R}$ are defined by
$$R = {\mu+\delta \over \lambda+1} P -
{\lambda+\delta \over \lambda+1} Q \sigma^t {~~and~~}
\bar{R} = {\lambda+\delta \over \mu+1}\bar{P} -
{\mu+\delta \over \mu+1} \bar{Q} \sigma^{-t}$$
with $\sigma = \lambda/\mu$, and $D$, $\bar{D}$ are defined by
$$D = ({\mu+\delta \over \lambda+1} P)' -
({\lambda+\delta \over \lambda+1} Q)' \sigma^t {~~ and ~~}
\bar{D} = ({\lambda+\delta \over \mu+1}\bar{P})' -
({\mu+\delta \over \mu+1} \bar{Q})' \sigma^{-t} .$$
Here $(...)'$ denotes differentiation with respect to $\theta$
(so that $\lambda' = {\lambda \over \lambda - \mu}$,
$\mu' = { - \mu \over \lambda - \mu}$,
$\sigma' = { 2 \sigma \over \lambda - \mu}$).
Note that in case $\theta^2 < 4(k-1)$ the roots $\lambda$, $\mu$
are conjugate complex numbers, and the bars above denote complex conjugation.
In general, the bars denote interchange of $\lambda$ and $\mu$.
For an eigenvalue $\theta$ of $\Gamma$, we have
$\bar{R} \sigma^{r+t} + R = 0$.
\end{Theorem}

\Proof
Apply Lemma~\ref{multip} and compute. See \cite{BIval4}.
\qed

This theorem is essentially the special case $a = 0$
of Theorem 2 of \cite{BIval4}. (We could have written the general case,
but have no need for that here.) But note that Bannai \& Ito take
$\delta = 1 - a_d$, which is correct only if $t > 0$ (that is, the
second sentence of their proof is false).
The restriction $a_1 = 0$ (that is, $r > 0$) is needed because otherwise
$P\bar{P} - Q\bar{Q} = R = 0$ and the expressions become indefinite.

\section{Estimates}
Now let us estimate $f_{\theta}$ for the case $| \theta | < 2 \sqrt{3}$.
Continue the notation of the foregoing theorem.
Put $\theta = 2\sqrt{3} \cos \phi$, so that $\lambda = \sqrt{3} e^{i \phi}$
and $\mu = \sqrt{3} e^{-i\phi}$ and $\sigma = e^{2i\phi}$.
Put $S = (12 - \theta^2) b_{r+1} c_{r+1} ... b_{d-t-1} c_{d-t-1}$
so that $P \bar{P} - Q \bar{Q} = S$.
From $|P-Q| \ge |P| - |Q|$ we find
$$ |R| \ge \left| {\lambda + \delta \over \lambda + 1} \right|
{ S \over |P|+|Q| } ~. $$
Finally, using $\lambda \mu = 3$ and $(\lambda+1)(\mu+1) = 4+\theta$,
$$ |\lambda-\mu|.|D| \le \left| {\lambda + \delta \over \lambda + 1} \right|.
|\lambda-\mu| (|P'|+|Q'|) +
\left| {6 + \mu + \delta \lambda  \over 4+\theta } \right| |P| +
\left| { (\delta - 1) \lambda  \over 4+\theta } \right| |Q|$$
and
$$M_{\theta} \le r + t {(|P|+|Q|)^2  \over  S} +
|\lambda - \mu| {|D| \over |R|} ~.$$

\medskip
Since $|P|^2 - |Q|^2 = S > 0$, we have $|Q| < |P|$.
If $t = 0$, then $\delta = 0$ and $2 |P|^2 / S$ gets
coefficient $(|6+\lambda| + |\lambda|)/|3+\lambda| \le 3 + \sqrt{3}$.
If $t > 0$, then $\delta = 1$ and $2 |P|^2 / S$ gets
coefficient $(6+\theta) / (4+\theta) \le 3 + \sqrt{3}$.
So, in both cases we have the estimate
$$M_{\theta} \le r + t { 4 |P|^2 \over S } +
{ 2 |P| \over S} |\lambda-\mu| (|P'|+|Q'|) +
{ 2 (3 + \sqrt{3}) |P|^2 \over S } .$$

\medskip
For the choices for $(s_1,s_2,s_3)$ listed below, we find
for $r \ge 100$, using Sturm, that $\Gamma$ has precisely two
eigenvalues larger than $2 \sqrt{3}$ namely the valency $4$ and
an eigenvalue $\theta$ bounded below as listed. 
Estimating as in Section \ref{terw} we find a lower bound
on $v/f_{\theta}$ that is exponential in $r$:
$${ v \over f_{\theta}} > \frac{4}{3} \alpha^2 (1 - 
{ \beta \over \alpha } ( { \mu \over \lambda } )^{100} )^2
(3 \lambda^2)^r =: a \cdot c^r .$$
On the other hand, by Theorem \ref{algnumth},
$\theta$ has a conjugate $\theta_1$ with $|\theta_1| < \sqrt{10}$,
and the above estimate yields (using
$v / f_{\theta_1} < \frac{3}{2} M_{\theta_1}$ and $t \le r$)
an upper bound on $v / f_{\theta_1}$ that is linear in $r$.
For sufficiently large $r$ this will yield a contradiction.

In the table below we list the estimates used to obtain a
contradiction (for $r \ge r_{\rm min}$). We write
${\bf s} := (s_1,s_2,s_3)$ and $\kappa := \lambda - \mu$
to save some space.

\medskip
\noindent
\begin{tabular}{cccccccc}
${\bf s}$ & $\theta$ & $a \cdot c^r$ & $|P|$ & $|\kappa P'|$ & $|\kappa Q'|$ & $\frac{3}{2} M_{\theta_1}$ & $r_{\rm min}$\\
\hline
(0,4,0) & 3.593 & $2 \cdot 1.7^r$ & 320 & 760 & 380 & $308000(r+5)$ & 100 \\
(2,3,1) & 3.591 & $2 \cdot 1.7^r$ & 2500 & 8000 & 4000 & $2350000(r+5)$ & 100 \\
(1,3,1) & 3.548 & $3 \cdot 1.55^r$ & 700 & 2100 & 860 & $368000(r+5)$ & 100 \\
(2,3,0) & 3.537 & $4 \cdot 1.5^r$ & 740 & 2200 & 1060 & $411000(r+5)$ & 100 \\
(2,2,2) & 3.502 & $6 \cdot 1.34^r$ & 1750 & 6000 & 3200 & $575000(r+6)$ & 100 \\
(1,3,0) & 3.484 & $10 \cdot 1.238^r$ & 210 & 560 & 230 & $66200(r+5)$ & 100 \\
(2,2,1) & 3.4703 & $29 \cdot 1.127^r$ & 480 & 1600 & 700 & $86500(r+5)$ & 110 \\
\end{tabular}

\medskip
Thus, assuming $r > 110$, we ruled out 7 of the 27 possible triples $(s_1,s_2,s_3)$.
Left are the 20 triples 010, 020, 030, 100, 101, 110, 111, 120,
121, 200, 201, 202, 210, 211, 212, 220, 300, 301, 302, 303.

\medskip
The second largest eigenvalue for an array increases with $t$,
and increases with $a_d$. The above 7 cases had a second largest
eigenvalue above $2\sqrt{3}$ in the worst case $t = a_d = 0$.
(And the same is true for 303, but a contradiction is only obtained
for large $r$.)
In a few other cases we find a sufficiently large $\theta_2$ assuming
a lower bound on $t$. The conclusion is that either $r < r_{\rm min}$
(and our computer search will handle the case), or $t < t_{\rm min}$
(and we will have a sharp bound on $M_{\theta}$ later).

\medskip
\noindent
\begin{tabular}{ccccccccc}
${\bf s}$ & $t_{\rm min}$ & $\theta$ & $a \cdot c^r$ & $|P|$ & $|\kappa P'|$ & $|\kappa Q'|$ & $\frac{3}{2} M_{\theta_1}$ & $r_{\rm min}$\\
\hline
(0,3,0) & 5 & 3.49 & $8 \cdot 1.27^r$ & 64 & 150 & 54 & $12300(r+5)$ & 100 \\
(3,0,3) & 2 & 3.475 & $17 \cdot 1.17^r$ & 800 & 3000 & 1800 & $30100(r+6)$ & 100 \\
(2,2,0) & 9 & 3.473 & $21 \cdot 1.154^r$ & 150 & 420 & 190 & $16900(r+5)$ & 105 \\
(1,2,1) & 18 & 3.466 & $86 \cdot 1.068^r$ & 140 & 400 & 150 & $14800(r+5)$ & 160 \\
(3,0,2) & 13 & 3.466 & $86 \cdot 1.068^r$ & 215 & 750 & 420 & $4400(r+6)$ & 140 \\
(2,1,2) & 18 & 3.466 & $86 \cdot 1.068^r$ & 350 & 1200 & 550 & $23000(r+5)$ & 165 \\
\end{tabular}

\medskip
If no eigenvalue much larger than $2\sqrt{3}$ is available, we can use
one very close to $-2\sqrt{3}$ and find a bound on its multiplicity
that decreases cubically with $r$, and again find a contradiction
for large $r$.

\begin{Theorem} {\rm (Bannai \& Ito \cite{BIval2}, Proposition 6)}
If we define $S_m$ by $S_m = \sum_{i=0}^m k_i u_i^2$, and
put $\theta = 2 \sqrt{k-1} \cos \phi$,
where $\phi$ is imaginary if $\theta > 2 \sqrt{k-1}$,
then $S_r$ is given by
\begin{eqnarray*}
S_r(\theta) = 1 + {2r \over k} +
{(k-2)^2 \over 2k(k-1)}{r \over \sin^2 \phi} + \quad\quad\quad\quad\quad\quad
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\\
\quad- {\sin r\phi \over 2k(k-1)\sin^3 \phi}
((k-1)^2 \cos (r+3)\phi -2(k-1) \cos (r+1)\phi + \cos (r-1)\phi ) .
\end{eqnarray*}
\end{Theorem}

In our case $k = 4$ this means
$$S_r (\theta) = 1 + r({1 \over 2} + {1 \over 6 \sin^2 \phi})
- { \sin r \phi \over 24 \sin^3 \phi }
(9 \cos (r+3)\phi - 6 \cos (r+1)\phi + \cos (r-1)\phi)  .$$

Now choose $\theta$ to be the smallest eigenvalue of $\Gamma$.
We saw earlier that in the nonbipartite case we have
$-2\sqrt{3} < \theta < -2\sqrt{3}\cos {\pi \over r+1}$.
Thus, $\theta = 2 \sqrt{3} \cos \phi$ with $0 < \pi - \phi < {\pi \over r+1}$.
Since $S_r (\theta)$ decreases on the interval
$0 \le \phi \le 2\pi/r$ (for any fixed $r \ge 11$),
and increases on the interval
$\pi - 2\pi/r \le \phi \le \pi$ (for any fixed $r \ge 10$),
we find
$$v / f_{\theta} > S_r (\theta) > {r^3 \over 6 \pi^2} .$$
The eigenvalue $\theta$ has a conjugate $\theta'$ with
$|\theta'| < 3.132 < \sqrt{10}$ (note that we already know that
$\theta' < \sqrt{13}$), and this conjugate is used with
the above estimate on $M_{\theta'}$ in the six cases listed
above (where we already have an upper bound on $t$).

\medskip
\noindent
\begin{tabular}{ccccccc}
${\bf s}$ & $|P|$ & $|\kappa P'|$ & $|\kappa Q'|$ & $t_{\rm max}$ & $\frac{3}{2} M_{\theta'}$ & $r_{\rm min}$\\
\hline
(0,3,0) & 64 & 150 & 54 & 4 & $\frac{3}{2}(r + 65536)$ & 185 \\
(1,2,1) & 140 & 400 & 150 & 17 & $\frac{3}{2}(r + 215600)$ & 270 \\
(2,1,2) & 331 & 1200 & 550 & 17 & $\frac{3}{2}(r + 301300)$ & 300 \\
(2,2,0) & 150 & 420 & 190 & 8 & $\frac{3}{2}(r + 147000)$ & 240 \\
(3,0,2) & 215 & 750 & 420 & 12 & $\frac{3}{2}(r + 52100)$ & 170 \\
(3,0,3) & 800 & 3000 & 1800 & 1 & $\frac{3}{2}(r + 140000)$ & 240
\end{tabular}
\medskip

In the remaining 14 cases we know (by use of Sturm) that
there are no eigenvalues $\theta' \ne \pm 4$ with
$|\theta'| > 2 \sqrt{3}$, and we have the stronger conclusion
that $\theta$ has a conjugate $\theta'$ with $|\theta'| < 2.968$.

\medskip
\noindent
\begin{tabular}{cccccccc}
${\bf s}$ & $|P|$ & $|\kappa P'|$ & $|\kappa Q'|$ & $\frac{7}{6} M_{\theta'}$ & $r_{\rm min}$\\
\hline
(0,1,0) & 5 & 8 & 2 & $41(r+3)$ & 100 \\
(0,2,0) & 12.1 & 30 & 10 & $229(r+5)$ & 120 \\
(1,0,0) & 7 & 10 & 4 & $40(r+4)$ & 100 \\
(1,0,1) & 8 & 21 & 9 & $27(r+5)$ & 100 \\
(1,1,0) & 8 & 22 & 6 & $51(r+5)$ & 100 \\
(1,1,1) & 28 & 80 & 28 & $307(r+5)$ & 140 \\
(1,2,0) & 39 & 110 & 37 & $1185(r+5)$ & 270 \\
(2,0,0) & 12 & 23 & 15 & $58(r+5)$ & 100 \\
(2,0,1) & 14 & 55 & 22 & $40(r+6)$ & 100 \\
(2,0,2) & 50 & 185 & 100 & $245(r+6)$ & 125 \\
(2,1,0) & 28 & 80 & 30 & $307(r+5)$ & 140 \\
(2,1,1) & 90 & 290 & 120 & $1577(r+6)$ & 310 \\
(3,0,0) & 42 & 122 & 74 & $345(r+5)$ & 150 \\
(3,0,1) & 50 & 185 & 82 & $245(r+6)$ & 125 \\
\end{tabular}
\medskip

Altogether, we used in the nonbipartite case $r \ge 182$
in the Terwilliger bound, and $r \ge 310$ here,
so checking $r < 310$ suffices to settle the nonbipartite case.

\medskip
In the bipartite case, Lemma \ref{negbd} guarantees
the existence of an eigenvalue $\theta$ with
$-2 \sqrt{3} < \theta < -2\sqrt{3}\cos {2\pi \over r}$, and we find
$$S_r (\theta) > {r^3 \over 24 \pi^2} .$$
Here we use the existence of a conjugate $\theta_1$ with
$|\theta_1| < \sqrt{10}$ (note that we already know that
$|\theta'| < \sqrt{13}$ for all eigenvalues $\theta' \ne \pm 4$),
and the same arguments as before settle these cases.

\medskip
\noindent
\begin{tabular}{cccccccc}
$s$ & $|P|$ & $|\kappa P'|$ & $|\kappa Q'|$ & $\frac{3}{2} M_{\theta_1}$ & $r_{\rm min}$\\
\hline
0 & 4.6 & 4 & 0 & $43(r+3)$ & 105 \\
1 & 7.5 & 12 & 6 & $30(r+4)$ & 100 \\
2 & 19 & 35 & 22 & $47(r+5)$ & 115 \\
3 & 35 & 100 & 65 & $40(r+5)$ & 100 \\
4 & 75 & 260 & 170 & $45(r+6)$ & 110 \\
5 & 150 & 650 & 450 & $45(r+7)$ & 110
\end{tabular}
\medskip

We did a computer search up to $r = 500$
and found only the known arrays (and four others, as described
in Section \ref{test}). These computations took about two months
on a 275 MHz DEC Alpha running Linux.
(The programs were written before many of the refinements
discussed above had been discovered. Probably one week
would suffice now.)

This completes the proof of our main theorem.


\begin{thebibliography}{}

\bibitem[BI]{BI} E. Bannai \& T. Ito,
{\it Algebraic Combinatorics I: Association Schemes\/},
Benjamin-Cummings Lecture Note Ser. 58, Benjamin/Cummings Publ. Co.,
London, 1984.

\bibitem[B]{B} N.L. Biggs,
{\it Algebraic Graph Theory\/},
Cambridge Tracts in Math. 67, Cambridge Univ. Press, 1974.

\bibitem[BCN]{BCN} A.E. Brouwer, A.M. Cohen \& A. Neumaier,
{\it Distance-regular graphs\/}, Springer, Heidelberg, 1989.

\bibitem[1]{BIval2} E. Bannai \& T. Ito,
{\it On distance-regular graphs with fixed valency, II\/},
Graphs and Combinatorics {\bf 4} (1988) 219-228.

\bibitem[2]{BIval3} E. Bannai \& T. Ito,
{\it On distance-regular graphs with fixed valency, III\/},
J. Algebra {\bf 107} (1987) 43-52.

\bibitem[3]{BIval4} E. Bannai \& T. Ito,
{\it On distance-regular graphs with fixed valency, IV\/},
Eur. J. Combin. {\bf 10} (1989) 137-148.

\bibitem[4]{BBSt} N.L. Biggs, A.G. Boshier \& J. Shawe-Taylor,
{\it Cubic distance-regular graphs\/},
J. London Math. Soc. (2) {\bf 33} (1986) 385-394.

\bibitem[5]{BN} A. Boshier \& K. Nomura,
{\it A remark on the intersection arrays of distance-regular graphs\/},
J. Comb. Th. (B) {\bf 44} (1988) 147-153.

\bibitem[6]{CT} A.M. Cohen \& J. Tits,
{\it On generalized hexagons and a near octagon whose lines
have three points\/}, Eur. J. Combin. {\bf 6} (1985) 13-27.

\bibitem[7]{Hi2} A. Hiraki,
{\it An improvement of the Boshier-Nomura bound\/},
J. Combin. Th. (B) {\bf 61} (1994) 1-4.

\bibitem[8]{Hir} A. Hiraki,
{\it A constant bound for the number of columns $(1,k-2,1)$ in the
intersection array of a distance-regular graph\/},
preprint.

\bibitem[9]{Kron} L. Kronecker,
{\it Zwei S\"atze \"uber Gleichungen mit ganzzahligen Coefficienten\/},
Crelle, Journal f. d. reine u. angew. Math. {\bf 53} (1857) 173-175.
Also found in {\it Leopold Kronecker's Werke\/},
K. Hensel (ed.), Chelsea reprint, 1968, pp. 105-108.

\bibitem[10]{MS} B. Mohar \& J. Shawe-Taylor,
{\it Distance-biregular graphs with 2-valent vertices and distance-regular
line graphs\/}, J. Combin. Th. (B) {\bf 38} (1985) 193-203.

\bibitem[11]{Nom} K. Nomura,
{\it Distance-regular graphs with valency four and girth three\/},
J. Combin. Th. (B), submitted -- long ago, Zbl 607.05055.

\bibitem[12]{Nom2} K. Nomura,
email communication, 16 May 1992.

\bibitem[13]{Nom3} K. Nomura,
{\it A remark on bipartite distance-regular graphs of even valency\/},
Graphs and Combinatorics, to appear.

\bibitem[14]{Schur} I. Schur,
{\it \"Uber die Verteilung der Wurzeln bei gewissen algebraischen
Gleichungen mit ganzzahlichen Koeffizienten\/},
Math. Zeitschrift {\bf 1} (1918) 377-402.
Also found in {\it Issai Schur, Gesammelte Abhandlungen\/},
Alfred Brauer \& Hans Rohrbach (eds.), Springer, Berlin, 1973,
Band 2, pp. 213-238.

\bibitem[15]{Suz} H. Suzuki,
{\it On distance-biregular graphs of girth divisible by four\/},
preprint.

\bibitem[16]{Tw} P. Terwilliger,
{\it Eigenvalue multiplicities of highly symmetric graphs\/},
Discrete Math. {\bf 41} (1982) 295-302.

\end{thebibliography}

\end{document}
