%
%
%
%   Accepted to E-JC
%   19.2.2018
%
%
%
\documentclass[a4paper,12pt]{article}
\catcode`\"=13          
\def"#1{\v#1}
\usepackage[dvips]{epsfig,graphicx}
\usepackage{amsmath,amsfonts,amssymb,verbatim} 
\usepackage{e-jc}
\specs{P1.52}{25(1)}{2018}


\newcommand{\CC}{{\mathbb C}}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\B}[1]{\boldsymbol{#1}}
\newcommand{\bi}[1]{\hbox{\boldmath{$#1$}}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\ths}{\theta^*}
\newcommand{\qed}{\hfill\hbox{\rule{3pt}{6pt}}}
\newcommand{\proof}{{\sc Proof. }}
%\newcommand{\Label}[1]{\marginpar{\footnotesize #1} \label{#1}}
\newcommand{\Label}{\label}
\newcommand{\mat}{{\rm Mat}}
\newcommand{\MX}{\mat_X(\CC)}
\newcommand{\G}{\Gamma}
\newcommand{\Es}{E^*}
\newcommand{\pceq}{\preccurlyeq}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{conjecture}{Conjecture}[section]
\newtheorem{problem}{Problem}[section]
%\hoffset=-15mm
%\textwidth=16cm
%\voffset=-16mm
%\textheight=23cm
%
%
\title{On bipartite $Q$-polynomial distance-regular graphs with diameter 9, 10, or 11}


\author{"Stefko Miklavi"c 
\thanks{This work is supported in part by the Slovenian Research Agency (research program P1-0285 and research projects N1-0032, N1-0038, N1-0062, J1-6720, and J1-7051).
} \\ 
\small Andrej Maru\v si\v c Institute,  University of Primorska \\[-0.8ex]
\small Muzejski trg 2, 6000 Koper, Slovenia, and \\[-0.8ex]
\small Institute of Mathematics, Physics and Mechanics \\[-0.8ex]
\small Jadranska 19, 1000 Ljubljana, Slovenia \\
\small\tt stefko.miklavic@upr.si\\
}




\date{\dateline{Sep 20, 2017}{Feb 19, 2018}{Mar 2, 2018}\\
\small Mathematics Subject Classifications: 05C50, 05E30}

\begin{document}
 \maketitle
 
\begin{abstract}
Let $\Gamma$ denote a bipartite distance-regular graph with diameter $D$. In [J.\ S.\ Caughman, Bipartite Q-polynomial distance-regular graphs, {\it Graphs Combin.} {\bf 20} (2004), 47--57], Caughman showed that if $D \ge 12$, then $\G$ is $Q$-polynomial if and only if one of the following (i)-(iv) holds: (i) $\G$ is the ordinary $2D$-cycle, (ii) $\G$ is the Hamming cube $H(D,2)$, (iii) $\G$ is the antipodal quotient of the Hamming cube $H(2D,2)$, (iv) the intersection numbers of $\G$ satisfy
$c_i = (q^i - 1)/(q-1), \, b_i = (q^D-q^i)/(q-1) \; (0 \le i \le D)$, where $q$ is an integer at least $2$. In this paper we show that the above result is true also for bipartite distance-regular graphs with $D \in \{9,10,11\}$. 

\bigskip\noindent \textbf{Keywords:} 
bipartite distance-regular graph; $Q$-polynomial property
 \end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction} \Label{sec:intro}

As a classification of all distance-regular graphs is currently beyond our reach, classifications of some subclasses of distance-regular graphs are also very important projects. One such subclass is the class of $Q$-polynomial bipartite distance-regular graphs. This paper is part of an effort to understand and classify $Q$-polynomial bipartite distance-regular graphs (see \cite{Ca1, Ca2, Ca3, Ca4, Ca5} for relevant literature). A crucial step towards a classification of this class was made by Caughman, who proved the following result.
\begin{theorem}
\label{thm:caug}
(\cite[Theorem 1.1]{Ca5}) Let $\G$ denote a bipartite distance-regular graph with diameter $D \ge 12$. Then $\G$ is $Q$-polynomial if and only if one of the following (i)-(iv) holds: 
\begin{itemize}
\item[(i)] $\G$ is the ordinary $2D$-cycle.
\item[(ii)] $\G$ is the Hamming cube $H(D,2)$.
\item[(iii)] $\G$ is the antipodal quotient of the Hamming cube $H(2D,2)$.
\item[(iv)] The intersection numbers of $\G$ satisfy
$$
  c_i = \frac{q^i - 1}{q-1}, \qquad b_i = \frac{q^D-q^i}{q-1} \qquad (0 \le i \le D),
$$
where $q$ is an integer at least $2$. 
\end{itemize}
\end{theorem}

In this paper we prove an analogue of Theorem \ref{thm:caug} for bipartite distance-regular graphs with diameter $D \in \{9,10,11\}$. We follow the ideas of Caughman \cite{Ca5} and use the Terwilliger algebra of $\G$ to prove our result. Generalization of Theorem \ref{thm:caug} to bipartite distance-regular graphs with diameter less than 12 is also mentioned as an open problem in the recent survey paper  {\em Distance-regular graphs} by van Dam, Koolen and Tanaka, see \cite[Section 18.3]{DKT}.  

The paper is organized as follows. In Sections \ref{sec:prelim}, \ref{sec:Q-poly}, \ref{sec:ter} we review some basic definitions and results about distance-regular graphs, the $Q$-polynomial property of distance-regular graphs, and the Terwilliger algebra of distance-regular graphs. In Section \ref{sec:mult} we review and prove some results concerning multiplicities of irreducible modules of the Terwilliger algebra. In Sections \ref{sec:bound} and \ref{sec:main} we prove our main result.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries} 
\label{sec:prelim}

In this section we review some definitions and basic concepts. See the book of
Brouwer, Cohen and Neumaier \cite{BCN} for more background information.

Throughout this paper, $\Gamma=(X,R)$ will denote a finite, undirected, connected
graph, without loops or multiple edges, with vertex set $X$, edge set
$R$, path length distance function $\partial$, and diameter
$D:=\max \{\partial(x,y) | x,y \in X \}$. For a vertex $x \in X$ 
define $\Gamma_i(x)$ to be the set of vertices at distance $i$ from $x$. We
abbreviate $\Gamma(x):=\Gamma_1(x)$. Let $k$ denote a nonnegative integer. Then 
$\Gamma$ is said to be {\it regular} with {\it valency} $k$ whenever 
$|\Gamma(x)|=k$ for all $x \in X$. The graph $\Gamma$ is said to be 
{\it distance-regular} whenever for all integers $h,i,j$ $(0 \le h,i,j \le D)$,
and all $x,y \in X$ with $\partial(x,y)=h$, the number
\begin{equation}
  p_{ij}^h := | \{z \, | \, z \in X, \, \partial(x,z)=i, \, 
                          \partial(y,z)=j \} | 
\end{equation}
is independent of $x,y$. The constants $p_{ij}^h$ are
known as the {\it intersection numbers} of $\Gamma$. 
For convenience, set 
$c_i:=p_{1 i-1}^i$ for $1 \le i \le D, \, a_i:=p_{1i}^i$ for $0 \le i \le D, \,
 b_i:=p_{1 i+1}^i$ for $0 \le i \le D-1, k_i:=p_{ii}^0$ for $0 \le i \le D$,
and $c_0=b_D=0$. We observe $a_0=0, \; c_1=1$. Moreover, $\Gamma$ is regular with
valency $k=b_0$, and $c_i+a_i+b_i=k$ for $0 \le i \le D$. 
It is well-known that 
\begin{equation}
\label{eq:k}
k_i=\frac{b_0 \cdots b_{i-1}}{c_1 \cdots c_i} \qquad (0 \le i \le D).
\end{equation}
Observe that $\Gamma$ is bipartite 
if and only if $a_i=0$ for $0 \le i \le D$. In this case $b_i+c_i=k$ for 
$0 \le i \le D$. 

\medskip

From now on we assume $\Gamma$ is distance-regular with diameter $D \ge 3$
and valency $k \ge 3$. We recall the Bose-Mesner algebra of $\Gamma$.
Let $\MX$ denote the $\CC$-algebra consisting of the matrices over $\CC$
which have rows and columns indexed by $X$. 
For $0 \le i \le D$ let $A_i$ denote the matrix in $\MX$ with $x,y$ entry
\begin{equation}
  (A_i)_{x y} = \left\{ \begin{array}{lll}
                 1 & \hbox{if } \; \partial(x,y)=i,    & \\
                   &                                   & (x,y \in X). \\
                 0 & \hbox{if } \; \partial(x,y) \ne i & \end{array} \right. 
\end{equation}
We call $A_i$ the $i$-th {\em distance matrix} of $\Gamma$. We abbreviate
$A=A_1$ and call $A$ the {\em adjacency matrix} of $\Gamma$. 
The matrices $A_0,A_1, \ldots, A_D$ form a basis for a commutative semi-simple
$\CC$-algebra $M$, known as the {\it Bose-Mesner algebra}, see for example 
\cite[Lemma 11.2.2]{Go}. The algebra $M$ has a second basis 
$E_0,E_1, \ldots, E_D$ such that $E_i E_j = \delta_{ij} E_i \; (0 \le i,j \le D)$,
see \cite[Theorem 2.6.1]{BCN}.
The $E_0,E_1, \ldots, E_D$ are known as the {\it primitive idempotents} of 
$\Gamma$, and $E_0$ is the {\it trivial} idempotent.

For $0 \le i \le D$ define a real number $\theta_i$ by
$A = \sum_{i=0}^D \theta_i E_i$. 
Then $AE_i = E_iA =\theta_i E_i$ for $0 \le i \le D$. The 
scalars $\theta_0, \theta_1, \ldots, \theta_D$ are distinct, since $A$ 
generates $M$ \cite[p. 197]{BI}. The $\theta_0, \theta_1, \ldots, \theta_D$ 
are known as the {\it eigenvalues} of $\Gamma$. We remark  
$k \ge \theta_i \ge -k$ for $0 \le i \le D$, and $\theta_0=k$ \cite[p. 45]{BCN}.

Let $\theta$ denote an eigenvalue of $\Gamma$, and let $E$ denote the 
associated primitive idempotent. For $0 \le i \le D$ define a real number 
$\ths_i$ by $E = |X|^{-1}\sum_{i=0}^D \ths_i A_i$.
We call the sequence $\ths_0, \ths_1, \ldots, \ths_D$ the 
{\it dual eigenvalue sequence} associated with $\theta, E$. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The $Q$-polynomial property}
\label{sec:Q-poly}

In this section we recall the $Q$-polynomial property of distance-regular graphs.
Let $\Gamma$ denote a distance-regular graph with diameter $D \ge 3$ and valency $k \ge 3$, and let $A_0, A_1, \ldots, A_D$ denote the distance matrices of $\G$. Observe that $A_i \circ A_j = \delta_{ij}A_i \; (0 \le i,j \le D)$, where $\circ$ denotes entrywise multiplication, and so algebra $M$ is closed under $\circ$. Let $E_0, E_1, \ldots, E_D$ denote the primitive idempotents of $\G$.
The {\it Krein parameters} $q_{ij}^h \; (0 \le h,i,j \le D)$ of $\Gamma$ are 
defined by
\begin{equation}
E_i \circ E_j = |X|^{-1} \sum_{h=0}^D q_{ij}^h E_h \;\;\; 
(0 \le i,j \le D).
\end{equation}
We say $\Gamma$ is 
{\it $Q$-polynomial} (with respect to the given ordering 
$E_0, E_1, \ldots, E_D$ of the primitive idempotents), whenever for all 
distinct integers $i,j \; (0 \le i,j \le D)$ the following holds:
$q_{ij}^1 \ne 0 \; \hbox{ if and only if } \; |i-j|=1$.
Let $E$ denote a nontrivial primitive idempotent of $\Gamma$. We say $\Gamma$ 
is {\it $Q$-polynomial with respect to $E$} whenever there exists an ordering
$E_0, E_1=E, \ldots, E_D$ of the primitive idempotents of $\Gamma$, with 
respect to which $\Gamma$ is $Q$-polynomial. 

\smallskip \noindent
We have the following important result about bipartite $Q$-polynomial distance-regular graphs,
see \cite[Lemma 3.2, Lemma 3.3]{Ca5}.

\begin{lemma}
\label{lem:caug}
Let $\Gamma$ denote a bipartite distance-regular graph with diameter $D \ge 4$, valency 
$k \ge 3$, and intersection numbers $b_i, c_i$ $(0 \le i \le D)$. 
We assume $\Gamma$ is $Q$-polynomial with respect to 
$E_0, E_1, \ldots, E_D$. For $0 \le i \le D$ let $\theta_i$ denote the eigenvalue associated 
with $E_i$. Let $\ths_0, \ths_1, \ldots, \ths_D$ denote the dual eigenvalue sequence 
associated with $E_1$.
Assume $\Gamma$ is not the $D$-cube or 
the antipodal quotient of the $2D$-cube. Then there exist scalars $q,s^* \in \RR$ such
that {\rm (i)--(iii)} hold below.
\begin{itemize}
\item[{\rm (i)}]   $|q| > 1, \;$ $s^* q^i \ne 1 \qquad (2 \le i \le 2D+1)$;
\item[{\rm (ii)}]  $\theta_i=h(q^{D-i}-q^i), \;$ $\ths_i=\ths_0 + h^*(1-q^i)(1-s^* q^{i+1})q^{-i} \;$ 
                   for $0 \le i \le D$, where 
                   $$
                     h=\frac{1-s^* q^3}{(q-1)(1-s^* q^{D+2})}, \; \;
                     h^*=\frac{(q^D+q^2)(q^D+q)}{q(q^2-1)(1-s^* q^{2D})}, \; \;
                     \ths_0=\frac{h^*(q^D-1)(1-s^* q^2)}{q(q^{D-1}+1)};
                   $$
\item[{\rm (iii)}] $k=c_D=h(q^D-1)$, and
                   $$
                     c_i=\frac{h(q^i-1)(1-s^* q^{D+i+1})}{1-s^* q^{2i+1}}, \qquad 
                     b_i=\frac{h(q^D-q^i)(1-s^* q^{i+1})}{1-s^* q^{2i+1}} \qquad (1 \le i \le D-1).
                   $$
\end{itemize}
\end{lemma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The Terwilliger algebra}
\label{sec:ter}

In this section we recall the Terwilliger algebra of a distance-regular graph.
Let $\Gamma$ denote a distance-regular graph with diameter $D \ge 3$,
valency $k \ge 3$, and distance matrices $A_0, A_1, \ldots, A_D$.
Fix any vertex $x \in X$. For $0 \le i \le D$ let $E_i^*=E_i^*(x)$ denote the diagonal matrix in 
$\MX$ with $y,y$ entry $(A_i)_{xy}$ $(y \in X)$. Let $T=T(x)$ denote the subalgebra of $\MX$ generated by 
$A$ and $E_0^*, \ldots, E_d^*$. We call $T$ the {\em Terwilliger algebra} of $\Gamma$ with respect to $x$. 
We remark that $T$ is finite dimensional and semisimple.

\smallskip \noindent
Let $V$ denote the $\CC$-vector space consisting of the column vectors over $\CC$ which have rows indexed by $X$. Observe that $\MX$ acts on $V$ by left multiplication. We refer to $V$ as the {\em standard module of} $T$. By a $T$-{\em module} we mean a subspace $W$ of the standard module $V$ such that $BW \subseteq W$ for all  $B \in T$. Let $W$ denote a $T$-module. Then $W$ is said to be {\em irreducible} whenever
$W$ is nonzero and $W$ contains no $T$-modules other than zero and~$W$.

\smallskip \noindent
Let $W$ and $W'$ denote $T$-modules. 
By a $T$-{\em isomorphism} from $W$ to $W'$, we mean a vector space isomorphism $\sigma:W \to W'$ such that $(\sigma B - B \sigma)W=0$ for all $B \in T$. The modules $W$ and $W'$ are said to be {\em isomorphic} whenever there exists a $T$-isomorphism from $W$ to $W'$.

\smallskip \noindent
Let $W$ denote a $T$-module and let $W'$ denote a $T$-module contained in $W$. Then the orthogonal complement of $W'$ in $W$ is a $T$-module. From this we find $W$ is an orthogonal direct sum of irreducible $T$-modules. Taking $W=V$ we find $V$ is an orthogonal direct sum of irreducible $T$-modules. Let $W$ denote an irreducible $T$-module. By the {\em multiplicity} with which $W$ 
appears in $V$, we mean the number of irreducible $T$-modules in this sum which are isomorphic to $W$. It is known that the multiplicity of $W$ is independent of the decomposition of $V$.

\smallskip \noindent
Let $W$ denote an irreducible $T$-module. 
We define the {\em endpoint} $r$ and the {\em diameter} $d$ of $W$ by
$r = \min \{i \mid 0 \le i\le D, \; E^*_i W \ne 0 \}$ and $d=|\{i \mid 0 \le i \le D, \; E^*_i W \ne 0\}|-1$. Similarly, the {\em dual endpoint} $t$ and {\em dual diameter} $d^*$of $W$ are defined by
$t = \min \{i \mid 0 \le i\le D, \; E_i W \ne 0 \}$ and $d^*:=|\{i \mid 0 \le i \le D, \; E_i W \ne 0\}|-1$.  
We say $W$ is {\em thin}, whenever ${\rm dim}(\Es_i W) \le 1$ for every $0 \le i \le D$.

\noindent
Assume now that our distance-regular graph $\G$ is $Q$-polynomial.
Let $W$ denote an irreducible $T$-module with endpoint $r$, dual endpoint $t$, diameter $d$ and dual diameter $d^*$. Then $W$ is thin by \cite[Theorem 9.3]{Ca2}. We comment on $r,t,d$ and $d^*$. By \cite[Lemma 5.1(ii)]{Ca2} we have $2r+d^* \ge D$, and by \cite[Lemma 9.2(ii)]{Ca2} we have that $d=d^*$. It follows that $(D-d)/2 \le r$. It is also clear that $r + d \le D$, and so we have that
$$
  \frac{D-d}{2} \le r \le D-d.
$$  
We have $2t+d=D$ by \cite[Theorem 9.4(ii)]{Ca2}, and so $D-d$ is even. By \cite[Theorem 13.1]{Ca2}, the isomorphism class of $W$ is determined by $r$ and $d$.
For the rest of the paper we will consider the following situation.
\begin{notation}
\label{blank} 
Let $\G=(X,R)$ denote a bipartite distance-regular graph with diameter $D \ge 4$, valency $k \ge 3$,
intersection numbers $b_i, c_i$, and distance matrices $A_i \; (0 \le i \le D)$. 
We fix $x \in X$ and let $\Es_i = \Es_i(x) \; (0 \le i \le D)$ and $T=T(x)$
denote the dual idempotents and the Terwilliger algebra of $\G$ with respect to $x$, respectively.
Let $V$ denote the standard module for $\G$.
Let $H(D,2)$ denote the $D$-dimensional hypercube, and let $\overline{H}(2D,2)$ denote the antipodal quotient of $H(2D,2)$.
\end{notation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Multiplicities of the irreducible $T$-modules}
\label{sec:mult}

With reference to Notation \ref{blank}, assume that $\G$ is $Q$-polynomial. In this section we review and prove some results about  the multiplicities of irreducible $T$-modules (see also \cite[Section 14]{Ca2}).

Fix a decomposition of the standard module $V$ into an orthogonal direct sum of irreducible $T$-modules. Let $W$ denote an irreducible $T$-module. Recall that the multiplicity of $W$ equals the number of irreducible $T$-modules in this sum which are isomorphic to $W$. 
As the isomorphism class of $W$ is determined by its endpoint and diameter, we introduce the following notation. For any integers $r,d \; (0 \le r,d \le D)$, we define mult$(r,d)$ to be the number of irreducible $T$-modules in this decomposition which have endpoint $r$ and diameter $d$. If no such modules exist, then we set mult$(r,d)=0$. Note that if $W$ has endpoint $r$ and diameter $d$, then the multiplicity of $W$ equals mult$(r,d)$.

\begin{definition}
\label{def:pairs}
(\cite[Definition 14.2]{Ca2})
With reference to Notation \ref{blank}, assume that $\G$ is $Q$-polynomial. Define a set $\Upsilon$ by
$$
  \Upsilon := \{(r,d) \in \ZZ^2 \mid 0 \le d \le D, D-d \text{ even }, \frac{D-d}{2} \le r \le D-d \}.
$$
\end{definition}  

Observe that mult$(r,d) = 0$ for all integers $r,d$ such that $(r,d) \not\in \Upsilon$. We define a partial order $\pceq$ on $\Upsilon$ by
$$
  (r',d') \pceq (r,d) \quad \text{ if and only if } \quad r' \le r \text{ and } r+d \le r'+d'.
$$

To further describe mult$(r,d)$, we need a definition. Let $(r,d) \in \Upsilon$. Following \cite[pp. 87-88]{Ca2} we define scalars $c_i(r,d) \; (1 \le i \le d)$ and $b_i(r,d) \; (0 \le i \le d-1)$ by
\begin{equation}
\label{cW}
  c_i(r,d) =\frac{\theta_t(\ths_{r+i+1}-\ths_{r+1})-\theta_{t+1}(\ths_{r+i}-\ths_r)}
              {\ths_{r+i+1}-\ths_{r+i-1}} \qquad (1 \le i \le d-1),
\end{equation}
\begin{equation}
\label{bW}
  b_i(r,d) =\frac{\theta_t(\ths_{r+1}-\ths_{r+i-1})+\theta_{t+1}(\ths_{r+i}-\ths_r)}
              {\ths_{r+i+1}-\ths_{r+i-1}} \qquad (1 \le i \le d-1),
\end{equation}
where $t=(D-d)/2$. We also set $b_0(r,d)=c_d(r,d)=\theta_t$, $b_d(r,d)=c_0(r,d)=0$. Assume now that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Then using Lemma \ref{lem:caug}(ii) we get that
\begin{equation}
\label{cWqs}
  c_i(r,d) =\frac{h(q^i-1)(1-s^* q^{2r+d+i+1})}
              {q^{d+t}(1-s^*q^{2r+2i+1})} \qquad (1 \le i \le d-1),
\end{equation}
\begin{equation}
\label{bWqs}
  b_i(r,d) =\frac{h(q^d-q^i)(1-s^* q^{2r+i+1})}
              {q^{d+t}(1-s^*q^{2r+2i+1})} \qquad (1 \le i \le d-1),
\end{equation}
and $b_0(r,d)=c_d(r,d)=h(q^{-t}-q^{t-D})$, $b_d(r,d)=c_0(r,d)=0$.


\begin{theorem}
\label{thm:mult-formula}
(\cite[Theorem 14.7]{Ca2})
With reference to Definition \ref{def:pairs}, fix any $(r,d) \in \Upsilon$. Then
$$
  k_r \prod_{i=r}^{r+d-1} b_i c_{r+d-i} = \sum_{{(r',d') \in \Upsilon \atop (r',d') \pceq (r,d)}}
                                                               {\rm mult}(r',d') \prod_{i=r-r'}^{r+d-r'-1} b_i(r',d') c_{i+1}(r',d').
$$
\end{theorem}

\begin{corollary}
\label{cor:r+d=D}
With reference to Definition \ref{def:pairs}, fix any $(r,d) \in \Upsilon$ such that $r+d=D \; (1 \le r \le D-1)$. Then $r$ is even and 
$$
  k_r \prod_{i=r}^{D-1} b_i c_{D-i} =
              \sum_{\ell=0}^{r/2} {\rm mult}(2\ell,D-2\ell) \prod_{i=r-2\ell}^{D-2\ell-1} b_i(2\ell,D-2\ell) c_{i+1}(2\ell,D-2\ell).
$$
\end{corollary}

\proof
Recall that $r=D-d$ is even by definition of the set $\Upsilon$. As $r+d=D$, it follows from the definition of $\pceq$ that the only pairs $(r',d') \in \Upsilon$ such that $(r',d') \pceq (r,d)$ are pairs with $r' \le r$ and $r'+d'=D$. Note that $r'+d'=D$ implies $r'$ is even, and so the result follows from Theorem \ref{thm:mult-formula}. \qed

\begin{lemma}
\label{lem:r+d=D}                                     
With reference to Definition \ref{def:pairs}, fix any $(r,d) \in \Upsilon$ such that $r+d=D \; (1 \le r \le D-1)$. Assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. If there exists an irreducible $T$-module with endpoint $r$ and diameter $d$, then
$$
 \prod_{i=0}^{D-r-1} b_i(r,D-r) c_{i+1}(r,D-r) \ne 0.
$$
\end{lemma}
\proof
Let $q, s^*$ be as in Lemma \ref{lem:caug}. Recall that $|q|>1$ and $s^*q^i \ne 1$ for $2 \le i \le 2D+1$. Using this, equations \eqref{cWqs}, \eqref{bWqs} and $b_0(r,d)=c_d(r,d)=h(q^{-t}-q^{t-D})$, we find that $b_i(r,D-r) \ne 0$ and $c_{i+1}(r,D-r) \ne 0$ for $0 \le i \le D-r-1$. The result follows.  \qed 

\begin{corollary}
\label{cor-a:r+d=D}
With reference to Definition \ref{def:pairs}, fix any $(r,d) \in \Upsilon$ such that $r+d=D \; (1 \le r \le D-1)$.  Assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Then ${\rm mult}(r,d)$ is equal to the quantity 
$$
  k_r \prod_{i=r}^{D-1} b_i c_{D-i} -
              \sum_{\ell=0}^{r/2-1} {\rm mult}(2\ell,D-2\ell) \prod_{i=r-2\ell}^{D-2\ell-1} b_i(2\ell,D-2\ell) c_{i+1}(2\ell,D-2\ell),
$$
divided by the quantity
$$
 \prod_{i=0}^{D-r-1} b_i(r,D-r) c_{i+1}(r,D-r).
$$
\end{corollary}
%
\proof 
Immediately from Corollary \ref{cor:r+d=D} and Lemma \ref{lem:r+d=D}. \qed

\smallskip
We now give explicit formulae for $mult(r,d)$ for some specific values of $r,d$. To do this we need the following definition. For $a,b \in \RR$ and for a non-negative integer $n$ we set
$$
  (a;b)_n = \prod_{i=1}^n (1-ab^{i-1}).
$$

\begin{theorem}
\label{thm:mult}
With reference to Definition \ref{def:pairs} assume $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. Then the following {\rm (i)--(iii)} hold.
\begin{itemize}
\item[{\rm (i)}]
${\rm mult}(0,D)=1$.
\item[{\rm (ii)}]
If $r \in \{2,4\}$, then 
$$
  {\rm mult}(r,D-r)=
  \frac{(-1)^t q^{t(t-1)} (1-s^* q^{2r}) (q^{d+1};q)_r (-s^* q^{D+1};q)_t (s^*q^2;q^2)_{t-1}}
    {(q^2;q^2)_t (s^* q^{D+t+1};q)_t (s^*q^{D+d+2};q^2)_t};
$$
where $d=D-r$ and $t=(D-d)/2=r/2$.
\item[{\rm (iii)}]
If $r \in \{6,8\}$ and $D \in \{9,10,11\}$, then 
$$
  {\rm mult}(r,D-r)=
  \frac{(-1)^t q^{t(t-1)} (1-s^* q^{2r}) (q^{d+1};q)_r (-s^* q^{D+1};q)_t (s^*q^2;q^2)_{t-1}}
    {(q^2;q^2)_t (s^* q^{D+t+1};q)_t (s^*q^{D+d+2};q^2)_t};
$$
where $d=D-r$ and $t=(D-d)/2=r/2$.
\end{itemize}
\end{theorem}
\proof
(i), (ii) This is \cite[Theorem 15.6 (i),(iii),(vii)]{Ca2}.

\noindent
(iii)  The proof (although a bit tedious and lengthy) follows straightforward from Corollary \ref{cor-a:r+d=D} using \eqref{cWqs}, \eqref{bWqs}. We omit the details. \qed

\begin{remark} 
With reference to Definition \ref{def:pairs} assume $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. We conjecture that the formula for {\rm mult}$(r,D-r)$ given in Theorem \ref{thm:mult} holds for any diameter $D$ and for any even number $r \le D$. See also \cite[Conjecture 15.8]{Ca2} for an extended conjecture about the multiplicities of irreducible $T$-modules of $\G$. However, for the purpose of this paper, Theorem \ref{thm:mult} suffices.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Some results about parameter $s^*$}
\label{sec:bound}

With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial, and let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. In this section we derive some restrictions on parameter $s^*$. We first recall some results of Caughman. 

\begin{theorem}
\label{thm:q}
(\cite[Theorem 4.1, Lemma 5.1, Lemma 6.6]{Ca5})
With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. Then the following {\rm (i)--(iii)} hold.
\begin{itemize}
\item[{\rm (i)}]
If $D \ge 6$, then $q > 1$.
\item[{\rm (ii)}]
If $q > 1$, then $-q^{-D-1} \le s^* < q^{-2D-1}$.
\item[{\rm (iii)}]
If $D \ge 7$ and $-q^{-13} \le s^* \le q^{-13}$, then $s^*=0$.
\end{itemize}
\end{theorem}

\begin{lemma}
\label{lem:beta}
With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. Set $\beta = q + 1/q$. If $D \ge 5$, then $\beta$ is a rational number.
\end{lemma}
\proof
Assume that $\G$ is $Q$-polynomial with respect to $E_0, E_1, \ldots, E_D$ and let $\theta_1$ denote the eigenvalue of $\G$ corresponding to $E_1$. By \cite[Lemma 3.2]{Ca4} we have that $\theta_1 \ne -1$ and
$$
  \beta = \frac{\theta_1^2 + c_2 \theta_1 + b_2 (k-2)}{b_2(\theta_1 +1)}.
$$
If $D \ge 5$ then $\theta_1$ is integer by \cite[Theorem 8.1.3]{Di}, see also \cite[Lemma 3.3(i)]{Ca4}.
The result follows. \qed

We note that it is easy to see that $q^2 + q^{-2} = \beta^2-2$, $q^3 + q^{-3} = \beta^3-3\beta$ and $q^4+q^{-4}=\beta^4-4\beta^2+2$. Also, if $D \ge 6$, then $q > 1$ by Theorem \ref{thm:q}(i), and so $\beta > 2$ in this case.

The following result was proved by Lang.
\begin{proposition}
\label{prop:s1}
(\cite[Lemma 9.3]{La})
With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. If $D \ge 5$, then $s^* \ne -q^{-D-3}$.
\end{proposition}
\begin{comment}
\proof
Assume on contrary that $D \ge 9$ and $s^* = -q^{-D-3}$. Observe that this implies $s^* < 0$ as $q>1$ by Theorem \ref{thm:q}(i). If $D \ge 10$, then $s^* = -q^{-D-3}$ implies $-q^{-13} \le s^* \le q^{-13}$. But then $s^*=0$ by Theorem \ref{thm:q}(iii), a contradiction.  
Assume now $D=9$. Then using Lemma \ref{lem:caug}(iii) we find
$$
    c_2 = \frac{2(q^2-q+1)(q^6-q^3+1)}{q(q^6-q^5+q^4-q^3+q^2-q+1)} = 
              \frac{2(\beta - 1)(\beta^3-3\beta - 1)}{\beta^3-\beta^2-2\beta+1},
$$
where $\beta$ is as in Lemma \ref{lem:beta}.
This shows that $\beta$ is a root of a polynomial with coefficients in $\ZZ$ and with leading coefficient equal to $2$.  As $\beta$ is rational by Lemma \ref{lem:beta}, this implies that $\beta=n$ or $\beta=n/2$ for some integer $n$. Recall also that $\beta > 2$ (and so $n$ is positive).

Now consider the above formula for $c_2$ and note that
$$
  c_2 = 2\beta - \frac{2 \beta^2-2\beta-2}{\beta^3-\beta^2-2\beta+1}.
$$
This shows that $(2 \beta^2-2\beta-2) / (\beta^3-\beta^2-2\beta+1)$ is an integer. Observe that 
$2 \beta^2-2\beta-2$ and  $\beta^3-\beta^2-2\beta+1$ are both positive for $\beta \ge 2$ and so $\beta^3-\beta^2-2\beta+1 \le 2\beta^2-2\beta-2$, or equivalently, $\beta^3-3\beta^2+ 3\le 0$. However, $\beta^3-3\beta^2+ 3 > 0$ for $\beta \ge 3$, and so $\beta=5/2$ (recall that $\beta > 2$). But this implies $c_2 = 171/43$, a contradiction. This shows that $s^* \ne -q^{-D-3}$. \qed
\end{comment}

\begin{proposition}
\label{prop:s2}
With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. If $D \ge 9$, then $s^* \ne -q^{-D-2}$.
\end{proposition}
\proof
Assume on contrary that $D \ge 9$ and $s^* = -q^{-D-2}$. Observe that this implies $s^* < 0$ as $q>1$ by Theorem \ref{thm:q}(i). If $D \ge 11$, then $s^* = -q^{-D-2}$ implies $-q^{-13} \le s^* \le q^{-13}$. But then $s^*=0$ by Theorem \ref{thm:q}(iii), a contradiction.  

If $D \in \{9,10\}$ then the proof is similar to the proof of Proposition \ref{prop:s1} for the case $D=9$. Let $\beta$ be as in Lemma \ref{lem:beta}. Assume first that $D=10$. In this case we have 
$$
  2 c_2 = \beta^2+2\beta-1 - \frac{2\beta^2-\beta-3}{\beta^3-\beta^2-2\beta+1},
$$
which shows that $\beta$ is an algebraic integer. As $\beta$ is rational by Lemma \ref{lem:beta}, this implies that $\beta$ is an integer, and so $(2\beta^2-\beta-3)/(\beta^3-\beta^2-2\beta+1)$ is an integer. Observe that $2\beta^2-\beta-3$ and $\beta^3-\beta^2-2\beta+1$ are both positive for $\beta \ge 2$, so $2\beta^2-\beta-3 \ge \beta^3-\beta^2-2\beta+1$. But this implies $\beta=2$, a contradiction (recall that $\beta > 2$).

Assume now $D=9$. In this case we have 
$$
  2 c_2 = \beta^2+2\beta-1 - \frac{2\beta^2+\beta-4}{\beta(\beta^2-3)},
$$
which again shows that $\beta$ is an algebraic integer. As $\beta$ is rational by Lemma \ref{lem:beta}, this implies that $\beta$ is an integer, and so $(2\beta^2+\beta-4)/(\beta(\beta^2-3))$ is an integer. Observe that $2\beta^2+\beta-4$ and $\beta(\beta^2-3)$ are both positive for $\beta \ge 2$, so $2\beta^2+\beta-4 \ge \beta(\beta^2-3)$. But this implies $\beta=2$, a contradiction. This shows that $s^* \ne -q^{-D-2}$. \qed

\begin{proposition}
\label{prop:s3}
With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. If $D \ge 6$, then $s^* \ne -q^{-D-1}$.
\end{proposition}
\proof
We assume $s^* = -q^{-D-1}$ and derive a contradiction. By Theorem \ref{thm:mult}(ii) we find that ${\rm mult}(2,D-2)=0$. But now $\G$ has, up to isomorphism, a unique irreducible $T$-module with endpoint $2$, and this module has diameter $D-4$.  By \cite[Theorem 3.12]{Cu1}, $\G$ is $2$-homogeneous in the sense of Nomura \cite{No}. However, as $D \ge 6$ we have that $\G$ is $H(D,2)$ by \cite[Theorem 1.2]{No1} (see also \cite[Theorem 4.1]{Cu1}), a contradiction. This shows that $s^* \ne -q^{-D-1}$. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proof of the main theorem}
\label{sec:main}

In this section we prove our main theorem. To do this we first need the following result.

\begin{theorem}
\label{thm:bound}
With reference to Notation \ref{blank} assume $\G$ is $Q$-polynomial and assume that $\G$ is not $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. Assume further that $D \in \{9,10,11\}$. Then $s^* \ge -q^{-D-4}$.
\end{theorem}
\proof
The result obviously holds if $s^* \ge 0$ (recall that $q > 1$ by Theorem \ref{thm:q}(i)), so assume that $s^* < 0$. Consider ${\rm mult}(2,D-2)$ and recall that this number is non-negative. It follows from Theorem \ref{thm:mult}(ii) that 
$$
  (1+s^* q^{D+1}) \ge 0.
$$
As $s^* \ne -1/q^{D+1}$ by Proposition \ref{prop:s3}, we have that $s^* > -q^{-D-1}$. 

Consider now ${\rm mult}(4,D-4)$ and recall that this number is non-negative. It follows from Theorem \ref{thm:mult}(ii) that 
$$
  (1+s^* q^{D+1})(1+s^* q^{D+2}) \ge 0.
$$
We have just proved that $s^* > -q^{-D-1}$ and so $1+s^* q^{D+1} > 0$, implying that $1+s^* q^{D+2} \ge 0$. As $s^* \ne -q^{-D-2}$ by Proposition \ref{prop:s2}, this shows that $s^* > -q^{-D-2}$. 

Consider now ${\rm mult}(6,D-6)$ and recall that this number is non-negative. It follows from Theorem \ref{thm:mult}(iii) that 
$$
  (1+s^* q^{D+1})(1+s^* q^{D+2}) (1+s^* q^{D+3})\ge 0.
$$
We have just proved that $s^* > -q^{-D-2}$ and so $(1+s^* q^{D+1})(1+s^* q^{D+2}) > 0$, implying that $1+s^* q^{D+3} \ge 0$. As $s^* \ne -q^{-D-3}$ by Proposition \ref{prop:s1}, this shows that $s^* > -q^{-D-3}$. 

Finally, consider ${\rm mult}(8,D-8)$ and recall that this number is non-negative. It follows from Theorem \ref{thm:mult}(iii) that 
$$
  (1+s^* q^{D+1})(1+s^* q^{D+2}) (1+s^* q^{D+3}) (1+s^* q^{D+4})\ge 0.
$$
We have just proved that $s^* > -q^{-D-3}$ and so $(1+s^* q^{D+1})(1+s^* q^{D+2})(1+s^* q^{D+3}) > 0$, implying that $1+s^* q^{D+4} \ge 0$. This shows that $s^* \ge -q^{-D-4}$. \qed 

We are now ready to prove our main result.
\begin{theorem}
\label{thm:main}
Let $\G$ denote a bipartite distance-regular graph with diameter $D \ge 9$. Then $\G$ is $Q$-polynomial if and only if one of the following (i)--(iv) holds: 
\begin{itemize}
\item[(i)] $\G$ is the ordinary $2D$-cycle.
\item[(ii)] $\G$ is the Hamming cube $H(D,2)$.
\item[(iii)] $\G$ is the antipodal quotient of the Hamming cube $H(2D,2)$.
\item[(iv)] The intersection numbers of $\G$ satisfy
\begin{equation}
\label{eq:int}
  c_i = \frac{q^i - 1}{q-1}, \qquad b_i = \frac{q^D-q^i}{q-1} \qquad (0 \le i \le D),
\end{equation}
where $q$ is an integer at least $2$. 
\end{itemize}
\end{theorem}
\proof
If $D \ge 12$ then this is \cite[Theorem 1.1]{Ca5}, therefore we assume $D \in \{9,10,11\}$. Assume first that $\G$ is $Q$-polynomial and that $\G$ is not a $2D$-cycle, $H(D,2)$ or $\overline{H}(2D,2)$. Let parameters $q, s^*$ be as in Lemma \ref{lem:caug}. By Theorem \ref{thm:bound} we have $s^* \ge -q^{-D-4}$. Together with Theorem \ref{thm:q}(ii) this implies that $-q^{-13} \le s^* \le q^{-13}$, and so $s^*=0$ by Theorem \ref{thm:q}(iii). It follows from Lemma \ref{lem:caug} that 
$$
  c_i = \frac{q^i - 1}{q-1}, \qquad b_i = \frac{q^D-q^i}{q-1} \qquad (0 \le i \le D).
$$
But now $c_2 = q+1$, and so $q$ is an integer. As $q > 1$ we have that $q \ge 2$.

Concerning the converse, assume that one of the cases (i)-(iv) holds.  If (i) or (iii) holds, then $\G$ is $Q$-polynomial by \cite[Corollary 8.5.3(i),(iii)]{BCN}. If (ii) or (iv) holds, then $\G$ has classical parameters and it is $Q$-polynomial by \cite[Corollary 8.4.2]{BCN}. \qed

\subsection*{Acknowledgement}
The author thanks John Caughman for giving this paper a close
reading and offering valuable suggestions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{99}

%{\small

\bibitem{BI} E.\ Bannai, T.\ Ito, {\it Algebraic Combinatorics I: Association
 Schemes}, The Benjamin-Cummings Lecture Notes Ser. 58, Menlo Park, CA, 1984.

\bibitem{BCN} A.\ E.\ Brouwer, A.\ M.\ Cohen, and A.\ Neumaier, 
 {\it Distance-Regular Graphs}, Springer-Verlag, Berlin, Heidelberg, 1989.

\bibitem{Ca1} J.\ S.\ Caughman, Spectra of bipartite $P$- and $Q$-polynomial 
association schemes, {\em Graphs Combin.} {\bf 14} (1998), 321--343.

\bibitem{Ca2} J.\ S.\ Caughman, The Terwilliger algebras of bipartite $P$- and $Q$-polynomial 
schemes, {\em Discrete Math.} {\bf 196} (1999), 65--95.

\bibitem{Ca3} J.\ S.\ Caughman, Bipartite $Q$-polynomial quotients of antipodal distance-regular graphs, {\em J. Combin. Theory Ser. B} {\bf 76} (1999), 291--296.

\bibitem{Ca4} J.\ S.\ Caughman, The parameters of bipartite $Q$-polynomial distance-regular graphs, {\em J. Algebraic Combin.} {\bf 15} (2002), 223--229.

\bibitem{Ca5} J.\ S.\ Caughman, Bipartite $Q$-polynomial distance-regular graphs,
{\it Graphs Combin.} {\bf 20} (2004), 47--57.

\bibitem{Cu1} B.\ Curtin, Almost $2$-homogeneous bipartite distance-regular graphs, {\em European J. Combin.} {\bf 21} (2000), 865--876.

\bibitem{Di} G. Dickie, {\it Q-polynomial structures for association schemes and distance-regular graphs}, Ph.D. Thesis, University of Wisconsin, 1995.

\bibitem{DKT} E.\ R.\ van Dam, J.\ H.\ Koolen, and H.\ Tanaka, Distance-regular graphs, {\em Electron. J. Combin.} {\#DS22} (2016).

\bibitem{Go} C.\ D.\ Godsil, {\it Algebraic combinatorics}, Chapman and Hall, 
 New York, 1993.

\bibitem{La} M.\ S.\ Lang, Bipartite distance-regular graphs: The Q -polynomial property and pseudo primitive idempotents,
{\em Discrete Math.} {\bf 331} (2014), 27--35.

\bibitem{No} K.\ Nomura, Homogeneous graphs and regular near polygons, {\em J. Combin. Theory Ser. B} {\bf 60} (1994), 63--71.

\bibitem{No1} K.\ Nomura, Spin models on bipartite distance-regular graphs, {\em J. Combin. Theory Ser. B} {\bf 64 (2)} (1994), 300--313.


\end{thebibliography}

\end{document}                          
