\documentclass[a4paper]{article}
\usepackage{latexsym}

\newcommand{\Cc}{{\bf C}}
\newcommand{\Qq}{{\bf Q}}
\newcommand{\Rr}{{\bf R}}
\newtheorem{Theorem} {Theorem} [section]
\newtheorem{Proposition} [Theorem] {Proposition}
\newtheorem{Lemma} [Theorem] {Lemma}
\newtheorem{Corollary} [Theorem] {Corollary}
\newcommand{\Proof}{ \noindent{\bf Proof:}\quad }
\newcommand{\Remark}{ \noindent{\bf Remark:}\quad }
\newcommand{\qed}{\hfill$\Box$\medskip}
\newcommand{\eps}{{\epsilon}}

\title{On a conjecture of Bannai and Ito.
There are only finitely many distance-regular graphs of
valency five, six or seven}
\author{J. H. Koolen}
\begin{document}
\maketitle

\begin{abstract}
In this paper we study a conjecture of Bannai and Ito,
which states that there are only finitely many distance-regular
graphs of a given valency $k$. We shall show that this is true for
$k = 5,6,7$.
\end{abstract}

\section{Introduction}
Bannai and Ito conjectured in \cite{BI0} that for a fixed valency there
are only finitely many distance-regular graphs with this valency.
In a sequence of papers \cite{BI1,BI2,BI3,BI4} they showed that
their conjecture is true for bipartite distance-regular graphs
and for distance-regular graphs of valency 3 and 4.
Using this work, Biggs, Boshier and Shawe-Taylor \cite{BBS}
(for valency 3) and Brouwer and Koolen \cite{BK} (for valency 4)
classified the distance-regular graphs of valency 3 and 4.
It was shown by Ivanov \cite{Ivanov} that only the geometrical girth $g$
has to be bounded by a function of the valency.
In this paper we show that $g$ can be bounded in case the valency
is five, six or seven.

\medskip

Our terminology and notation follows \cite{BCN}.
In particular, the valency and intersection array of a
distance-regular graph $\Gamma$ of diameter $d$
will always be noted $k$ and $\{b_0,...,b_{d-1};\,c_1,...,c_d\}$,
where $b_0 = k$ and $c_1 = 1$.
The parameter $a_i$ is defined by $c_i + a_i + b_i = k$.

For a distance-regular graph $\Gamma$, define
$l_{(c,a,b)} = \#\{i|(c_i,a_i,b_i) = (c,a,b)\}$,
and put $r := l_{(1,a_1,b_1)}$ and $s := l_{(b_1,a_1,1)}$.

For $N > 0$, let $A = A(N)$ be the set of ordered triples
of nonnegative integers $(c,a,b)$ different from
$(1,a_1,b_1),(b_1,a_1,1)$ with $l_{(c,a,b)} > N$.

For $N > 0$, let $(*)_N$ be the condition (on $\Gamma$):

\medskip
{\it There is a real number $\kappa$ with $\kappa > a_1 + 2\sqrt{b_1}$
such that $|\kappa-a| < 2\sqrt{bc}$ for each triple $(c,a,b)$ in $A$.}

\begin{Theorem} \label{Th1}
There exists a function $f:\Rr\times\Rr\times\Rr \rightarrow \Rr$ such that
any distance-regular graph of valency $k > 2$ satisfying condition
$(*)_N$ and with $d-r-s > \eps r$ has diameter at most $f(k,N,\eps)$.
\end{Theorem}

The idea of the proof is the following.
(i) By Ivanov's theorem (see Theorem \ref{Ithm} below)
it suffices to bound the geometric girth
of $\Gamma$, that is, to bound $r$.
(ii) The condition that $d-r-s > \eps r$ makes sure that
the `middle' part of the intersection array is sufficiently long.
In particular, $A$ will be nonempty.
(iii) Choose a sufficiently small interval $I$ around $\kappa$.
(Where $I$ does not depend on $r$ or $\Gamma$, but only on $A$.)
(iv) By interlacing we see that the eigenvalues are spaced
roughly regularly in $I$.
(v) By carefully estimating multiplicities we see that eigenvalues
in $I$ have different multiplicities, and hence cannot be conjugate,
unless they are really close together.
(vi) Only few eigenvalues have small degree, so most eigenvalues
have many conjugates.
(vii) Starting with the eigenvalues in $I$ and taking all conjugates
we find more eigenvalues than $\Gamma$ has, contradiction.

The details are fairly technical, and will take most of the rest
of this paper. In order to apply this theorem, we need a condition
that will guarantee that $d-r-s > \eps r$.

For $N > 0$, let $(**)_N$ be the condition (on $\Gamma$):

\medskip
{\it There is a real number $\kappa$ with
$\kappa > a_1 + b_1^{1/4} + b_1^{3/4}$
such that $|\kappa-a| < 2\sqrt{bc}$ for each triple $(c,a,b)$ in $A$.}

Clearly, $(**)_N$ implies $(*)_N$.

\begin{Theorem} \label{Th2}
There exists a function $g:\Rr\times\Rr \rightarrow \Rr$ such that
any distance-regular graph of valency $k > 2$ satisfying condition
$(**)_N$ has diameter at most $g(k,N)$.
\end{Theorem}

\medskip
Now, let us show how the above theorem can be applied.

\begin{Theorem} Only finitely many distance-regular graphs have valency 5.
\end{Theorem}
\Proof
If $a_1 > 0$, then $c_2 > 1$ (for if $c_2 = 1$ then each point neighbourhood
is a disjoint union of $(a_1+1)$-cliques, so that $(a_1+1) | k$, which is
impossible for $k = 5$). But then $r = 1$, and by Ivanov's theorem
$d$ is bounded.

If $a_1 = 0$, then the triples $(c_i,a_i,b_i)$ that can occur for $0 < i < d$
and differ from $(1,a_1,b_1),(b_1,a_1,1)$ are $(3,0,2)$, $(2,0,3)$,
$(3,1,1)$, $(1,1,3)$, $(2,1,2)$, $(2,2,1)$, $(1,2,2)$, $(1,3,1)$.
The corresponding intervals $(a-2\sqrt{bc},a+2\sqrt{bc})$ are
$(-4.89,4.89)$, $(-2.46,4.46)$, $(-3,5)$, $(-0.82,4.82)$, $(1,5)$.
Now $\kappa = 4.4$ lies in all required intervals, and satisfies
$\kappa > a_1 + b_1^{1/4} + b_1^{3/4}$, so $(**)_N$ is satisfied for $N = 1$.
By the Theorem \ref{Th2}, $d$ is bounded.
\qed

Almost the same proof works for $k = 7$.

\begin{Theorem} Only finitely many distance-regular graphs have valency 7.
\end{Theorem}
\Proof
Again we may assume that $a_1 = 0$ since 7 is prime.
Now $|\kappa - a| < 2\sqrt{bc}$ is equivalent to
$(\sqrt{b} - \sqrt{c})^2 < k - \kappa < (\sqrt{b} + \sqrt{c})^2$.
Pick $\kappa = 5.4$, so that $\sqrt{k - \kappa} = 1.26$ and
$\kappa > 6^{1/4} + 6^{3/4}$.
The values of $b$ and $c$ in triples $(c_i,a_i,b_i)$ that can occur
for $0 < i < d$ and differ from $(1,a_1,b_1),(b_1,a_1,1)$ range from 1 to 5,
so that $|\sqrt{b} - \sqrt{c}| < 1.24 < \sqrt{k - \kappa} < 2 \le
|\sqrt{b} + \sqrt{c}|$. Consequently, for this choice of $\kappa$
condition $(**)_N$ is satisfied for $N = 1$, and by Theorem \ref{Th2},
$d$ is bounded.
\qed

For $k = 6$ we have to worry a little about the case $a_1 > 0$.

\begin{Theorem} Only finitely many distance-regular graphs have valency 6.
\end{Theorem}
\Proof
If $a_1 = 0$ then reasoning as before we find that $\kappa = 4.9$
satisfies all requirements. (Now $\sqrt{k - \kappa} = 1.05$.
The values of $b$ and $c$ range from 1 to 4, so
$|\sqrt{b} - \sqrt{c}| \le 1 < \sqrt{k - \kappa} < 2 \le
|\sqrt{b} + \sqrt{c}|$. Also $\kappa > 5^{1/4} + 5^{3/4}$.)

If $a_1 > 0$ (and $r > 1$, i.e., $c_2 = 1$) then $a_1 + 1$ divides $k$
so that $a_1 = 1$ or $a_1 = 2$.

If $a_1 = 1$, pick $\kappa = 5.25 > 1 + 4^{1/4} + 4^{3/4}$,
so that $\sqrt{k - \kappa} = 0.87$.
This suffices. (Indeed, the triple $(5,0,1)$ cannot occur since we
have singular lines of size 3, and $(4,1,1),(1,1,4)$ are not in $A$,
so it suffices when $\sqrt{k - \kappa} > \sqrt{3} - \sqrt{1} = 0.73$.)

If $a_1 = 2$, then there are singular lines of size 4, two on each point.
That means that $\Gamma$ is the line graph of the graph on these
singular lines, adjacent when they intersect. But all distance-regular
line graphs are known (see \cite{BCN}, Theorem 4.2.16) and have
bounded diameter (for $k > 2$).
\qed

With more work similar results can be obtained for larger $k$.
Details will be published elsewhere.

\bigskip
The theorem of Ivanov alluded to in the above is the following.

\begin{Theorem} \label{Ithm}
{\rm (Ivanov \cite{Ivanov}, cf. \cite{BCN}, Theorem 5.9.8)}
The diameter $d$ of a distance-regular graph $\Gamma$ satisfies
$d \le 4^k r$.
\end{Theorem}

This theorem shows that when $k$ is fixed and $r$ is bounded, also
$d$ is bounded, so that only finitely many different intersection
arrays are possible, and hence the number of vertices is bounded,
and hence only finitely many nonisomorphic graphs are possible.

In order to prove Theorem \ref{Th2}, we need two more results.

\begin{Theorem} \label{BIthm} {\rm (Bannai \& Ito \cite{BI4})}
There exists a function $F:\Rr\times\Rr \rightarrow \Rr$ such that
for all distance-regular graphs $\Gamma$ of valency $k \ge 3$
we have $r \le F(k,d-r-s)$.
\end{Theorem}

This theorem says for fixed $k$ that $r$ is bounded when $d-r-s$
is bounded. It follows that we may assume that $d-r-s$ grows with $r$.
But in order to apply Theorem \ref{Th1} we need linear growth,
not just growth. This will follow from the Terwilliger-Koolen
estimate on eigenvalue multiplicities.

\begin{Theorem} \label{TKthm} {\rm (Terwilliger \cite{Terwilliger} and
Koolen \cite{Kthesis}, Proposition 7.5)}
Let $\Gamma$ be a distance-regular graph of valency $k$
with $r := l_{(1,a_1,b_1)}$. Let $\theta \ne \pm k$ be an eigenvalue
of $\Gamma$. Then $\theta$ has multiplicity
$m \ge b_1^{(r-1)/2}$.
\end{Theorem}
\Proof
The graph $\Gamma$ has geometric girth at least $2r+1$.
Now \cite{Kthesis}, Proposition 7.5 says that if
$\theta \ne \pm k$ then if $r$ is even,
$m \ge {1 \over 2} k b_1^{r/2 - 1}$,
and if $r$ is odd, $m \ge b_1^{(r-1)/2}$.
\qed

\section{Distribution of the eigenvalues of $\Gamma$}
The following observations make precise that `eigenvalues are spaced
roughly regularly in $I$\/'.

\begin{Lemma} The $(t \times t)$-matrix
$$M = M_{cab} = \left(\begin{array}{cccccc}
a & b \\
c & a & b \\
  & c & . & . \\
  &   & . & . & . \\
  &   &   & . & . & b \\
  &   &   &   & c & a \\
\end{array}\right)$$
has eigenvalues $a + 2 \sqrt{bc}\, \cos ({j\pi \over t+1})$
for $j = 1,2,...,t$.
\qed
\end{Lemma}

The eigenvalues of $\Gamma$ are the eigenvalues of the tridiagonal
matrix
$$N = \left(\begin{array}{cccccc}
a_0 & b_0 \\
c_1 & a_1 & b_1 \\
    & c_2 &  .  & . \\
    &     &  .  & . &  . \\
    &     &     & . &  .  & b_{d-1} \\
    &     &     &   & c_d & a_d \\
\end{array}\right) .$$
Since $b_i \ge b_{i+1}$ and $c_i \le c_{i+1}$ and $c_i + a_i + b_i = k$,
the difference $b_i - c_i$ decreases from $k$ to not less than $-k$,
so that there are at most $2k+1$ distinct triples $(c_i,a_i,b_i)$.
(In fact fewer---for example, $b_i - c_i$ does not take the value $k-1$.)
Thus, after deleting at most $2k$ rows and columns from $N$ we obtain
a matrix $N'$ that is the direct sum of a number of matrices $M_{cab}$,
and the spectrum of $N'$ is the union of the spectra of these matrices
$M_{cab}$. By interlacing, each interval between two successive
eigenvalues of $N'$ contains at most $2k+1$ distinct eigenvalues of $\Gamma$,
and all but at most $2k$ of these intervals contain a unique
eigenvalue of $\Gamma$.

Given $\eps > 0$, we shall choose $I$ inside the intersection of a number
of intervals $(a-2\sqrt{bc}+\eps, a+2\sqrt{bc}-\eps)$ that between them
contain a positive fraction of all eigenvalues. Then the number of
eigenvalues inside $I$ will be roughly proportional to $|I|$.

\section{Estimating multiplicities (1)}
The spectrum of a graph $\Gamma$ is that of its adjacency matrix.
For distance-regular $\Gamma$ we found the distinct eigenvalues
as eigenvalues of the tridiagonal matrix $N$ of the previous section
(that has eigenvalues of multiplicity one).
The multiplicities of the eigenvalues of $\Gamma$ are found
using Biggs' formula below.

Given a distance-regular graph $\Gamma$, define polynomials $u_i$
of degree $i$ by
$$u_0(x) = 1,~~u_1(x) = x/k,$$
$$b_i u_{i+1}(x) = (x-a_i)u_i(x) - c_i u_{i-1}(x)~~(1 \le i \le d-1).$$
Then for each eigenvalue $\theta$ of $\Gamma$ the vector
$(u_0(\theta),...,u_d(\theta))^\top$ is a right eigenvector of
the matrix $N$ (with eigenvalue $\theta$).

\begin{Proposition} \label{Biggs}
{\rm (Biggs formula, cf. \cite{BCN}, Theorem 4.1.4)}
The multiplicity $m(\theta)$ of the eigenvalue $\theta$ of $\Gamma$
is given by $m(\theta) = v / M(\theta)$, where $v$ is the number
of vertices of $\Gamma$ and $M(\theta) = \sum_{i=0}^d k_i u_i(\theta)^2$.
\end{Proposition}

Here $k_i$ is the number of vertices at distance $i$ from a given point,
so that $k_0 = 1$ and $k_i = k_{i-1} b_{i-1} / c_i$ $(1 \le i \le d)$.

Algebraically conjugate eigenvalues have the same multiplicity.
Our aim is to give accurate estimates for $M(\theta)$, in order
to prove for eigenvalues in some interval $I$ that either they
are very close together, or they have different multiplicities
and hence are not conjugate.

We need a lemma describing the growth of things defined by a 3-term
recurrence relation with constant coefficients.

\begin{Lemma} \label{recurr}
Let $c,a,b$ be nonnegative integers with nonzero $b,c$.
Let $x_0,x_1,\theta \in \Rr$, with $x_0,x_1$ not both zero.
Define $x_2,...,x_{t-1}$ recursively by
$x_{i-1} + {(a-\theta) \over \sqrt{bc}} x_i + x_{i+1} = 0$
$(1 \le i \le t-2)$.
Let $z_1,z_2$ be the two roots of
$1 + {(a-\theta) \over \sqrt{bc}} z + z^2 = 0$.
Then

{\rm (i)}
If $|\theta - a| \ne 2\sqrt{bc}$, then
$$x_i = \sigma_1 z_1^i + \sigma_2 z_2^i ~~(0 \le i \le t-1)$$
where $\sigma_1 = (z_2x_0-x_1)/(z_2-z_1)$ and
$\sigma_2 = (z_1x_0-x_1)/(z_1-z_2)$, and
$$\sum_{i=0}^{t-1} x_i^2 =
\sigma_1^2 {{z_1^{2t} - 1} \over {z_1^2 - 1}}
+ 2\sigma_1\sigma_2t +
\sigma_2^2 {{z_2^{2t} - 1} \over {z_2^2 - 1}} .$$

{\rm (ii)}
Given $\eps > 0$, there are positive constants $C_1,C_2,C_3,C_4,T$
such that if $|\theta - a| < 2\sqrt{bc} - \eps$ then
$$C_1 t \max\{x_0^2,x_1^2\} \le
\sum_{i=0}^{t-1} x_i^2 \le
C_2 t \max\{x_0^2,x_1^2\}~~for~t \ge T$$
and
$$C_3 \max\{|x_0|,|x_1|\} \le
\max\{|x_{t-1}|,|x_t|\} \le
C_4 \max\{|x_0|,|x_1|\} .$$
(Here the constants depend on $c,a,b,\eps$ but not on $x_0,x_1,\theta$.)

{\rm (iii)}
Given $\eps > 0$, there are positive constants $C_1,C_2,C_3,C_4,T$
such that if $|\theta - a| > 2\sqrt{bc} + \eps$
and $|\theta| \le k$ and $|z_1| > |z_2|$ and
$|z_1x_1 - x_0| > \eps |x_0|$,
then for $t \ge T$ we have
$$C_1 z_1^{2t} \max\{x_0^2,x_1^2\} \le
\sum_{i=0}^{t-1} x_i^2 \le
C_2 z_1^{2t} \max\{x_0^2,x_1^2\}$$
and
$$C_3 |z_1|^t \max\{|x_0|,|x_1|\} \le \max\{|x_{t-1}|,|x_t|\} \le
C_4 |z_1|^t \max\{|x_0|,|x_1|\} .$$
(Here the constants depend on $k,c,a,b,\eps$ but not on $x_0,x_1,\theta$.)
\end{Lemma}
\Proof
(i) $|\theta - a| \ne 2\sqrt{bc}$ says $z_1 \ne z_2$.
Now the values of $x_0$ and $x_1$ are right by inspection,
and those of $x_i$, $i > 1$, follow by the recurrence relation.
The second equation follows by substituting the first and summing
a geometric series.

(ii) In this case $z_1,z_2$ are conjugate complex numbers
with absolute value 1, bounded away from $\pm 1$, so that the absolute value
of ${z^{2t} - 1} \over {z^2 - 1}$ is bounded by a constant for $z=z_1,z_2$.
The complex numbers $\sigma_1,\sigma_2$ are complex conjugates and nonzero,
so for large $t$ the right hand side of the second equation in (i) is
dominated by the term $2 \sigma_1 \sigma_2 t$.
Substituting the definitions of $\sigma_1,\sigma_2$ from (i)
we find the first inequality. Concerning the second inequality,
the right hand part is immediately clear, and the left hand part
then follows by applying the right hand part to
$x_i^\prime := x_{t-i}$ $(0 \le i \le t)$, satisfying the same recurrence.

(iii) In this case $z_1,z_2$ are distinct real numbers with product 1,
bounded away from $\pm 1$. Since $|z_1| > 1 > |z_2|$ and
$\sigma_1^2$ is bounded away from $0$, the right hand side
of the second equation in (i) is dominated by the term
$\sigma_1^2 {z_1^{2t} \over {z_1^2 - 1}}$.
Now both inequalities follow since $z_1$ is bounded away from
$\pm 1$, and is also bounded since $\theta$ is bounded,
and $\sigma_1^2$ is bounded from below by a constant times
$\max\{|x_0|,|x_1|\}$ since $|z_1x_1 - x_0| > \eps |x_0|$.
\qed

One might wonder how it can be that the recurrence relation
is symmetric with respect to increasing or decreasing $i$,
while the conclusion in (iii) above is very asymmetric:
$\max\{|x_{t-1}|,|x_t|\}$ is much larger than $\max\{|x_0|,|x_1|\}$.
The answer is that also the hypothesis is asymmetric:
$|z_1x_1 - x_0| > \eps |x_0|$ says that $x_0/x_1$ is very different from $z_1$,
while $x_t/x_{t-1}$ will be very close to $z_1$ for large $t$.

In the applications the requirement $|z_1x_1 - x_0| > \eps |x_0|$
will be automatically satisfied. We shall use part (iii) of this
lemma with $\theta > a + 2\sqrt{bc}$ where
$a = a_1$, $b = b_1$, $c = c_1 = 1$, $u_0 = 1$, $u_1 = \theta/k$,
$x_i = u_i \sqrt{k_i}$, so that $x_0 = 1$ and $x_1 = \theta/\sqrt{k}$.
So it suffices to show that $|\theta/\sqrt{k} - z_2| > \eps$,
and then again, that $a_1 + 2\sqrt{b_1} > (1+\eps)\sqrt{k}$.
But with $0 < \eps < sqrt{2} - 1$ (and $a_1 \ge 0$, $b_1 \ge 1$),
this is satisfied.

\section{Proof of Theorem \ref{Th2}}
At this point we can prove Theorem \ref{Th2}, assuming Theorem \ref{Th1}.

\medskip
\Proof
We have to show that there is an $\eps$, independent of $\Gamma$,
but depending on $k$ and $A$ only, such that
$d-r-s > \eps r$. First of all, by Bannai and Ito (Theorem \ref{BIthm}),
$d-r-s$ tends to infinity (or we are happy already).
Thus, $A$ is nonempty, and there are eigenvalues $\theta \ne k$
larger than $\kappa$. By Biggs' formula (Theorem \ref{Biggs}),
$v = m(\theta)M(\theta)$.
The Terwilliger-Koolen bound (Theorem \ref{TKthm})
yields $m(\theta) > C b_1^{r/2}$ for some positive constant $C$.
Lemma \ref{recurr} (iii) yields $M(\theta) > C' b^{r/2}$ for some
positive constant $C'$ and a constant $b > b_1$.

Indeed, $M(\theta) > \sum_{i=1}^r k_i u_i^2 = \sum_{i=1}^r x_i^2$
where $x_i = u_i \sqrt{k_i}$ satisfies the three-term recurrence
$x_{i-1} + {(a-\theta) \over \sqrt{bc}} x_i + x_{i+1} = 0$
$(1 \le i \le r)$ for $a = a_1$, $b = b_1$, $c = 1$.
The above lemma now says that $\sum_{i=1}^r x_i^2$
is of the order $z_1^{2r}$, where $z_1$ is the largest root of
$1 + {(a_1 - \theta) \over \sqrt{b_1}} z + z^2$.
But $\theta > \kappa > a_1 + b_1^{1/4} + b_1^{3/4}$
means that $1 + {(a_1 - \theta) \over \sqrt{b_1}} b_1^{1/4} + b_1^{1/2} < 0$,
so that $z_1 > \sqrt{b_1}$, and $b := z_1^2$ satisfies our claim.

Altogether we have $v = m(\theta)M(\theta) > b_1^r c^r$
for some constant $c > 1$ and sufficiently large $r$.
More precisely, the largest root $z_1 = z_1(\theta)$ of
$1 + {(a_1 - \theta) \over \sqrt{b_1}} z + z^2$
is an increasing function of $\theta$, and we can take
$b := z_1(\kappa)^2$ and $c := b/b_1$ to find $c$ a function
of $k$ and $A$ but not of $\Gamma$.

We have $v = \sum_{i=0}^d k_i$, and by Ivanov (Theorem \ref{Ithm})
$d < 4^k r$, so that, after replacing $c$ by a slightly smaller constant
larger than 1, we have $v > k(d+1) b_1^r c^r$, so that for some $i$
we have $k_i > k b_1^r c^r$. Now $k_i < k b_1^i$, so
$i > r + r \log(c)/\log(b_1)$. On the other hand, if $b_j = 1$
then $k_{j+1} \le k_j$, so for the smallest such $i$ we have
$i \le d-s$, and it follows that $d-r-s > \eps r$ for
$\eps = \log c/\log b_1$, as desired.
\qed

\section{Estimating multiplicities (2)}
Property $(*)_N$ talks about a single number $\kappa$, but in fact
we need an entire interval. Let us say that (for a positive integer $N$
and a closed real interval $I$) $(*)_{N,I}$ is the
condition (on a distance-regular graph $\Gamma$)

\medskip
{\it For each real number $\kappa \in I$ we have
$a_1 + 2\sqrt{b_1} < \kappa < k$ and $|\kappa-a| < 2\sqrt{bc}$
for each triple $(c,a,b)$ in $A$.}

Clearly, given a set of triples $A$ there is an interval $I = I_A$
of positive length
such that every graph that satisfies $(*)_N$ also satisfies
$(*)_{N,I}$.

\begin{Proposition}
Fix integers $k, b_1$ with $k > b_1 > 0$, and put $a_1 = k - b_1 - 1$.
Let $I$ be a closed real interval contained in
the interval $(a_1 + 2\sqrt{b_1} + \eps, \,k)$.
For $\theta \in I$, let $\rho(\theta)$ be the largest
zero of $p(x) = 1 + {(a_1 - \theta) \over \sqrt{b_1}} x + x^2$.
There are positive constants $C_1,C_2,R_0$ depending only on
$k,N,\eps$, such that every distance-regular graph $\Gamma$
with these given parameters $k,b_1$ and satisfying $(*)_{N,I}$
and such that $d-r-s > \eps r$ satisfies
$$C_1 r \rho(\theta)^{2r} \le M(\theta) \le C_2 r \rho(\theta)^{2r}$$
where $\theta$ is any eigenvalue in $I$ and $r = l_{(1,a_1,b_1)}$
and $r > R_0$.
\end{Proposition}
\Proof
Let us say that $g(t)$ is {\em of order} $f(t)$ when there
are positive constants $R,S$ (not depending on $\Gamma$ or $\theta$
but only on $k$ and $A$ and $I$) such that $Rf(t) \le g(t) \le Sf(t)$.

We estimate $M(\theta) = \sum_{i=0}^d k_i u_i^2$
(with $u_i = u_i(\theta)$) using Lemma \ref{recurr}.

Put $x_i = \sqrt{k_i} u_i$, so that on intervals for $i$
where $(c_i,a_i,b_i)$ is constant, say $(c,a,b)$, we have
the recurrence
$x_{i-1} + {(a-\theta) \over \sqrt{bc}} x_i + x_{i+1} = 0$,
and everywhere we have the estimate
$$\max\{|x_j|,|x_{j+1}|\} \le
(2k)^{|j-i|} \max\{|x_i|,|x_{i+1}|\} ~~ {\rm for} ~ 0 \le i,j \le d-1 .$$

Partition the summation $M(\theta) = \sum_{i=0}^d x_i^2$ into
sums with $i$ ranging over (the at most $2k$) subintervals
(of length $l_{(c,a,b)}$)
for which $(c_i,a_i,b_i)$ takes some fixed value, $(c,a,b)$, say.

When $l_{(c,a,b)}$ is small
(less than the $T$ of Lemma \ref{recurr} or the $N$ here)
then $\max\{|x_i|,|x_{i+1}|\}$ changes by at most a constant:
for each $i$ in the subinterval the value of
$\max\{|x_i|,|x_{i+1}|\}$ is bounded by a constant times
the value of that expression for the largest $i$ in the
previous subinterval. In particular, also the contributions $x_i^2$
are bounded by a constant times earlier contributions.

For the interval $1 \le i \le r$ with $(c_i,a_i,b_i) = (1,a_1,b_1)$
we apply Lemma \ref{recurr}(iii) and see that $\max\{|x_{r-1}|,|x_r|\}$
has order $\rho(\theta)^r$, while the contribution of that interval
to $\sum x_i^2$ is of order $\rho(\theta)^{2r}$.

For all following long intervals we apply Lemma \ref{recurr}(ii)
and see that $\max\{|x_i|,|x_{i+1}|\}$ changes by at most a constant
and hence remains of order $\rho(\theta)^r$. This means that each
interval of length $t$ contributes something of order
$t \rho(\theta)^{2r}$ to $\sum x_i^2$. But the sum of all interval lengths
is bounded by a constant times $r$ by Ivanov's theorem \ref{Ithm},
while at least one interval has length lower bounded by a constant
times $r$ by assumption. Thus, altogether, this part contributes
something of order $r \rho(\theta)^{2r}$ to $M(\theta)$.

If this was not all, then $s > 0$ and we have to look at the contribution
of the terms $x_i^2$ for $i$ with $(c_i,a_i,b_i) = (b_1,a_1,1)$.
Note that these must be the $i$ with $d-s-1 \le i \le d-1$.
Here $\max\{x_{d-i-1},x_{d-i}\}$ behaves like
$z_1^{2i} \max\{x_{d-1},x_d\}$ by Lemma \ref{recurr}(iii).
Indeed, we have to check that $|z_1 x_{d-1} - x_d | > \eps |x_d|$,
that is, that $|{(\theta - a_d) \over \sqrt {c_d}} - z_2| > \eps$.
(Note that $c_d u_{d-1} + (a_d - \theta)u_d = 0$.)
To this end it suffices that $2 \sqrt{b_1/c_d} > 1 + \eps$,
and since $b_1/c_d \ge 1/2$ this is true for $0 < \eps < sqrt{2} - 1$.
But this means that this final part does contribute something
of order $\rho(\theta)^{2r}$ to $M(\theta)$.

Altogether, $M(\theta)$ is found to be of order $r \rho(\theta)^{2r}$.
\qed

\section{Only few eigenvalues of bounded degree}
\begin{Proposition}
The number of algebraic integers $\theta$ of degree $h$
with the property that $\theta$ and all its conjugates are real and
lie in the interval $[-k,k]$ is bounded by a function of $h$ and $k$.
\end{Proposition}
\Proof
By definition an algebraic integer is a root of a monic polynomial $p$
with integral coefficients. If $p(x) = \sum_{i=0}^h e_i x^i$ with
$e_0 = 1$ has all roots in $[-k,k]$, then, since the coefficients
are symmetric functions of the roots,
$| e_i | \le {h \choose i} k^i$. Thus, there are only finitely many
choices for the polynomial $p$.
\qed

\section{Proof of Theorem \ref{Th1}}
At this point we can prove Theorem \ref{Th1}.

\medskip
\Proof
Assume that $r$ is unbounded, and choose an interval $I$
as in the above proposition.

Stage 1: Conjugate eigenvalues must lie really close together.

We find that all eigenvalues $\theta \in I$ have
$C_1 r \rho(\theta)^{2r} \le M(\theta) \le C_2 r \rho(\theta)^{2r}$.
Thus, if $\theta,\theta' \in I$ are algebraically conjugate
(and hence have the same multiplicity), and, say $\theta < \theta'$,
then $C_1 r \rho(\theta')^{2r} \le C_2 r \rho(\theta)^{2r}$.
But if $\theta' = \theta + e$, then
$\rho(\theta') / \rho(\theta) > 1 + e/{2k}$.
Since $(\rho(\theta') / \rho(\theta))^{2r}$ is bounded, it follows that
$e r$ is bounded, say $\theta' - \theta < c/r$.

Stage 2: $I$ contains lots of eigenvalues.

Indeed, $I$ contains at least a number of eigenvalues that is of the
order of $|I| r$, with distance between successive ones of order $1/r$,
by the above remarks about interlacing.
(We consider only a single matrix $M_{cab}$ and only a single
eigenvalue in each of the intervals between the eigenvalues of $M_{cab}$.)

Stage 3: $I$ contains lots of mutually nonconjugate eigenvalues.

Indeed, by Stages 1 and 2 groups of mutually conjugate eigenvalues
(among those we consider) in $I$ have bounded size, so that
there are a number of mutually nonconjugate eigenvalues in $I$
of the order of $|I| r$.

Stage 4: Contradiction.

Since the total number of distinct eigenvalues of $\Gamma$ equals $d+1$,
hence is of order $r$, each conjugacy class of eigenvalues
(among those we consider) must have bounded size.
But there are only finitely many algebraic integers $\theta$
of bounded degree, so that for large $r$ there are too many
conjugacy classes represented in $I$.
\qed

\begin{thebibliography}{}

% \bibitem{BI} E. Bannai and T. Ito,
% {\em Algebraic Combinatorics I: Association Schemes},
% Benjamin Cummings Lecture Note Series {\bf 58},
% The Benjamin/Cummings Publishing Company, Inc., London (1984).

\bibitem{BI0} E. Bannai and T. Ito,
{\em The study of distance-regular graphs from the algebraic
(i.e. character theoretical) viewpoint},
Proceedings of Symposia in Pure Mathematics {\bf 47} (1987) 343--349.

\bibitem{BI1} E. Bannai and T. Ito,
{\em On distance-regular graphs with fixed valency},
Graphs and Combinatorics {\bf 3} (1987) 95--109.

\bibitem{BI2} E. Bannai and T. Ito,
{\em On distance-regular graphs with fixed valency II},
Graphs and Combinatorics {\bf 4} (1988) 219--228.

\bibitem{BI3} E. Bannai and T. Ito,
{\em On distance-regular graphs with fixed valency III},
Journal of Algebra {\bf 107} (1987) 43--52.

\bibitem{BI4} E. Bannai and T. Ito,
{\em On distance-regular graphs with fixed valency IV},
European Journal of Combinatorics {\bf 10} (1989) 137--148.

\bibitem{BBS} N. L. Biggs, A. G. Boshier and J. Shawe-Taylor,
{\em Cubic distance-regular graphs},
J. London Math. Soc. (2) {\bf 33} (1986) 385--394.

\bibitem{BN} A. Boshier and K. Nomura,
{\em A remark on the intersection arrays of distance-regular graphs},
J. Combinatorial Theory (B) {\bf 44} (1988) 147--153.

\bibitem{BCN} A. E. Brouwer, A. M. Cohen and A. Neumaier,
{\em Distance-regular graphs}, Springer, Heidelberg, 1989.

\bibitem{BK} A. E. Brouwer and J. H. Koolen,
{\em The distance-regular graphs of valency four},
J. Algebraic Combin. {\bf 10} (1999) 5--24.

\bibitem{Godsil} C.D. Godsil,
{\em Algebraic Combinatorics}, Chapman \& Hall, New York, 1993.

\bibitem{Hiraki} A. Hiraki,
{\em An improvement of the Boshier-Nomura bound},
J. Combinatorial Theory (B) {\bf 61} (1994) 1--4.

\bibitem{HNS} A. Hiraki, K. Nomura and H. Suzuki,
{\em The distance-regular graphs with $k = 6$ and $a_1 = 1$},
J. Algebraic Combin. {\bf 11} (2000) 101--134.

\bibitem{Ivanov} A. A. Ivanov,
{\em Bounding the diameter of a distance-regular graph},
Soviet Math. Dokl. {\bf 28} (1983) 149--152.

\bibitem{Kthesis} J. H. Koolen,
{\em Euclidean representations and substructures of distance-regular graphs},
Ph.D. Thesis, Eindhoven University of Technology, 1994.

\bibitem{Terwilliger} P. Terwilliger,
{\em Eigenvalue multiplicities of highly symmetric graphs},
Discrete Math. {\bf 41} (1982) 295--302.

\end{thebibliography}

\end{document}

