Doubling (Dual) Hahn Polynomials: Classification and Applications

Doubling (Dual) Hahn Polynomials:
Classification and Applications

Roy OSTE and Joris VAN DER JEUGT

R. Oste and J. Van der Jeugt

Department of Applied Mathematics, Computer Science and Statistics, Ghent
University,
Krijgslaan 281-S9, B-9000 Gent, Belgium<EMAIL_ADDRESS><EMAIL_ADDRESS>
Received July 13, 2015, in final form January 04, 2016; Published online
January 07, 2016

We classify all pairs of recurrence relations in which two Hahn or dual Hahn
polynomials with different parameters appear. Such couples are referred to as
(dual) Hahn doubles. The idea and interest comes from an example appearing in
a finite oscillator model [Jafarov E.I., Stoilova N.I., Van der Jeugt J., J.
Phys. A: Math. Theor. 44 (2011), 265203, 15 pages, arXiv:1101.5310]. Our
classification shows there exist three dual Hahn doubles and four Hahn
doubles. The same technique is then applied to Racah polynomials, yielding
also four doubles. Each dual Hahn (Hahn, Racah) double gives rise to an
explicit new set of symmetric orthogonal polynomials related to the
Christoffel and Geronimus transformations. For each case, we also have an
interesting class of two-diagonal matrices with closed form expressions for
the eigenvalues. This extends the class of Sylvester–Kac matrices by
remarkable new test matrices. We examine also the algebraic relations
underlying the dual Hahn doubles, and discuss their usefulness for the
construction of new finite oscillator models.

Hahn polynomial; Racah polynomial; Christoffel pair; symmetric orthogonal
polynomials; tridiagonal matrix; matrix eigenvalues; finite oscillator model

33C45; 33C80; 81R05; 81Q65

##  1 Introduction

The tridiagonal $(N+1)\times(N+1)$ matrix of the following form

$\displaystyle C_{N+1}=\left(\begin{matrix}0&1&&&&\\\ N&0&2&&&\\\
&N-1&0&3&&\\\ &&\ddots&\ddots&\ddots&\\\ &&&2&0&N\\\
&&&&1&0\end{matrix}\right)$ (1.1)

appears in the literature under several names: the Sylvester–Kac matrix, the
Kac matrix, the Clement matrix, $\ldots$. It was already considered by
Sylvester [28], used by M. Kac in some of his seminal work [17], by Clement as
a test matrix for eigenvalue computations [9], and continues to attract
attention [6, 7, 29]. The main property of the matrix $C_{N+1}$ is that its
eigenvalues are given explicitly by

$\displaystyle-N,-N+2,-N+4,\dots,N-2,N.$ (1.2)

Because of this simple property, $C_{N+1}$ is a standard test matrix for
numerical eigenvalue computations, and part of some standard test matrix
toolboxes (e.g., [12]).

One of the outcomes of the current paper implies that $C_{N+1}$ has appealing
two-parameter extensions. For odd dimensions, let us consider the following
tridiagonal matrix

$\displaystyle
C_{2N+1}(\gamma,\delta)=\left(\begin{matrix}0&2\gamma+2&&&&&&\\\
2N&0&2&&&&&\\\ &2\delta+2N&0&2\gamma+4&&&&\\\ &&2N-2&0&4&&&\\\
&&&\ddots&\ddots&\ddots&&\\\ &&&&2\delta+4&0&2\gamma+2N&\\\ &&&&&2&0&2N\\\
&&&&&&2\delta+2&0\end{matrix}\right).$ (1.3)

In the following, we shall sometimes use the term “two-diagonal” [10] for
tridiagonal matrices with zero entries on the diagonal (not to be confused
with a bidiagonal matrix, which has also two non-zero diagonals, but for a
bidiagonal matrix the non-zero entries are on the main diagonal and either
superdiagonal or the subdiagonal). So, just as $C_{2N+1}$ the matrix (1.3) is
two-diagonal, but the superdiagonal of $C_{2N+1}$,

$\displaystyle[1,2,3,4,\ldots,2N-1,2N]$

is replaced by

$\displaystyle[2\gamma+2,2,2\gamma+4,4,\ldots,2\gamma+2N,2N],$

and in the subdiagonal of $C_{2N+1}$,

$\displaystyle[2N,2N-1,2N-2,\ldots,3,2,1]$

the odd entries are replaced, leading to

$\displaystyle[2N,2\delta+2N,2N-2,\ldots,2\delta+4,2,2\delta+2].$

Clearly, for $\gamma=\delta=-\frac{1}{2}$ the matrix $C_{2N+1}(\gamma,\delta)$
just reduces to $C_{2N+1}$. One of our results is that
$C_{2N+1}(\gamma,\delta)$ has simple eigenvalues for general $\gamma$ and
$\delta$, given by

$\displaystyle 0,\pm 2\sqrt{1(\gamma+\delta+2)},\pm
2\sqrt{2(\gamma+\delta+3)},\pm 2\sqrt{3(\gamma+\delta+4)},\ldots,\pm
2\sqrt{N(\gamma+\delta+N+1)}.$

This spectrum simplifies even further for $\delta=-\gamma-1$; in this case one
gets back the eigenvalues (1.2).

For even dimensions, we have a similar result. Let $C_{2N}(\gamma,\delta)$ be
the $(2N)\times(2N)$ tridiagonal matrix with zero diagonal, with superdiagonal

$\displaystyle[2\gamma+2,2,2\gamma+4,4,\ldots,2N-2,2\gamma+2N]$

and with subdiagonal

$\displaystyle[2\delta+2N,2N-2,2\delta+2N-2,\ldots,4,2\delta+4,2,2\delta+2].$

Then $C_{2N}(\gamma,\delta)$ has simple eigenvalues for general $\gamma$ and
$\delta$, given by111In this paper, we shall usually take $\gamma>-1$ and
$\delta>-1$, yielding real eigenvalues for the matrices under consideration.
But the expressions for the eigenvalues remain valid even when these
conditions are not satisfied.

$\displaystyle\pm 2\sqrt{(\gamma+1)(\delta+1)},\pm
2\sqrt{(\gamma+2)(\delta+2)},\ldots,\pm 2\sqrt{(\gamma+N)(\delta+N)}.$ (1.4)

This spectrum simplifies for $\delta=\gamma$, and obviously for
$\gamma=\delta=-\frac{1}{2}$ one gets back the eigenvalues (1.2) since in that
case $C_{2N}(\gamma,\delta)$ just reduces to $C_{2N}$.

What is the context here for these new tridiagonal matrices with simple
eigenvalue properties? Well, remember that $C_{N+1}$ also appears as the
simplest example of a family of Leonard pairs [24, 30]. In that context, this
matrix is related to symmetric Krawtchouk polynomials [13, 19, 23]. Indeed,
let $K_{n}(x)\equiv K_{n}(x;\frac{1}{2},N)$, where $K_{n}(x;p,N)$ are the
Krawtchouk polynomials [13, 19, 23]. Then their recurrence relation [19,
equation (9.11.3)] yields

$\displaystyle nK_{n-1}(x)+(N-n)K_{n+1}(x)=(N-2x)K_{n}(x),\qquad
n=0,1,\ldots,N.$ (1.5)

Writing this down for $x=0,1,\ldots,N$, and putting this in matrix form, shows
indeed that the eigenvalues of $C_{N+1}$ (or rather, of its transpose
$C_{N+1}^{T}$) are indeed given by (1.2). Moreover, it shows that the
components of the $k$th eigenvector of $C_{N+1}^{T}$ are given by $K_{n}(k)$.

So we can identify the matrix $C_{N+1}$ with the Jacobi matrix of symmetric
Krawtchouk polynomials, one of the families of finite and discrete
hypergeometric orthogonal polynomials. The other matrices
$C_{N}(\gamma,\delta)$ appearing in this introduction are not directly related
to Jacobi matrices of a simple set of finite orthogonal polynomials. In this
paper, however, we show how two sets of distinct dual Hahn polynomials [13,
19, 23] can be combined in an appropriate way such that the eigenvalues of
matrices like $C_{N}(\gamma,\delta)$ become apparent, and such that the
eigenvector components are given in terms of these two dual Hahn polynomials.
This process of combining two distinct sets is called “doubling”. We examine
this not only for the case related to the matrix $C_{N}(\gamma,\delta)$, but
stronger: we classify all possible ways in which two sets of dual Hahn
polynomials can be combined in order to yield a two-diagonal “Jacobi matrix”.
It turns out that there are exactly three ways in which dual Hahn polynomials
can be “doubled” (for a precise formulation, see later). By the doubling
procedure, one automatically gets the eigenvalues (and eigenvectors) of the
corresponding two-diagonal matrix in explicit form.

This process of doubling and investigating the corresponding two-diagonal
Jacobi matrix can be applied to other classes of orthogonal polynomials (with
a finite and discrete support) as well. In this paper, we turn our attention
also to Hahn and to Racah polynomials. The classification process becomes
rather technical, however. Therefore, we have decided to present the proof of
the complete classification only for dual Hahn polynomials (Section 3). For
Hahn polynomials (Section 4) we give the final classification and
corresponding two-diagonal matrices (but omit the proof), and for Racah
polynomials we give the final classification and some examples of two-diagonal
matrices in Appendix A.

We should also note that the two-diagonal matrices appearing as a result of
the doubling process are symmetric. So matrices like (1.3) do not appear
directly but in their symmetrized form. Of course, as far as eigenvalues are
concerned, this makes no difference (see Section 6).

The doubling process of the polynomials considered here also gives rise to
“new” sets of orthogonal polynomials. One could argue whether the term “new”
is appropriate, since they arise by combining two known sets. The peculiar
property is however that the combined set has a common unique weight function.
Moreover, we shall see that the support set of these doubled polynomials is
interesting, see the examples in Section 5. In this section, we also interpret
the doubling process in the framework of Christoffel–Geronimus transforms. It
will be clear that from our doubling process, one can deduce for which
Christoffel parameter the Christoffel transform of a Hahn, dual Hahn or Racah
polynomial is again a Hahn, dual Hahn or Racah polynomial with shifted
parameters.

In Section 6 we reconsider the two-diagonal matrices that have appeared in the
previous sections. It should be clear that we get several classes of two-
diagonal matrices (with parameters) for which the eigenvalues (and
eigenvectors) have an explicit and rather simple form. This section reviews
such matrices as new and potentially interesting examples of eigenvalue test
matrices.

In Section 7 we explore relations with other structures. Recall that in
finite-dimensional representations of the Lie algebra $\mathfrak{su}(2)$, with
common generators $J_{+}$, $J_{-}$ and $J_{0}$, the matrix of $J_{+}+J_{-}$
also has a symmetric two-diagonal form. The new two-diagonal matrices
appearing in this paper can be seen as representation matrices of deformations
or extensions of $\mathfrak{su}(2)$. We give the algebraic relations that
follow from the “representation matrices” obtained here. The algebras are not
studied in detail, but it is clear that they could be of interest on their
own. The general algebras have two parameters, and we indicate how special
cases with only one parameter are of importance for the construction of finite
oscillator models.

##  2 Introductory example

We start our analysis by the explanation of a known example taken from [27].
For this example, we first recall the definition of Hahn and dual Hahn
polynomials and some of the classical notations and properties.

The Hahn polynomial $Q_{n}(x;\alpha,\beta,N)$ [13, 19, 23] of degree $n$,
$n=0,1,\ldots,N$, in the variable $x$, with parameters $\alpha>-1$ and
$\beta>-1$ (or $\alpha<-N$ and $\beta<-N$) is defined by [13, 19, 23]

$\displaystyle
Q_{n}(x;\alpha,\beta,N)={}_{3}F_{2}\left(\genfrac{}{}{0.0pt}{}{-n,n+\alpha+\beta+1,-x}{\alpha+1,-N};1\right).$
(2.1)

Herein, the function ${}_{3}F_{2}$ is the generalized hypergeometric series
[4, 26]

$\displaystyle{}_{3}F_{2}\left(\genfrac{}{}{0.0pt}{}{a,b,c}{d,e};z\right)=\sum_{k=0}^{\infty}\frac{(a)_{k}(b)_{k}(c)_{k}}{(d)_{k}(e)_{k}}\frac{z^{k}}{k!}.$
(2.2)

In (2.1), the series is terminating because of the appearance of the negative
integer $-n$ as a numerator parameter. Note that in (2.2) we use the common
notation for Pochhammer symbols [4, 26] $(a)_{k}=a(a+1)\cdots(a+k-1)$ for
$k=1,2,\ldots$ and $(a)_{0}=1$. Hahn polynomials satisfy a (discrete)
orthogonality relation [13, 19]

$\displaystyle\sum_{x=0}^{N}w(x;\alpha,\beta,N)Q_{n}(x;\alpha,\beta,N)Q_{n^{\prime}}(x;\alpha,\beta,N)=h_{n}(\alpha,\beta,N)\,\delta_{n,n^{\prime}},$
(2.3)

where

$\displaystyle
w(x;\alpha,\beta,N)=\binom{\alpha+x}{x}\binom{N+\beta-x}{N-x},\qquad
x=0,1,\ldots,N,$ $\displaystyle
h_{n}(\alpha,\beta,N)=\frac{(-1)^{n}(n+\alpha+\beta+1)_{N+1}(\beta+1)_{n}n!}{(2n+\alpha+\beta+1)(\alpha+1)_{n}(-N)_{n}N!}.$

We denote the orthonormal Hahn functions as follows

$\displaystyle\tilde{Q}_{n}(x;\alpha,\beta,N)\equiv\frac{\sqrt{w(x;\alpha,\beta,N)}\,Q_{n}(x;\alpha,\beta,N)}{\sqrt{h_{n}(\alpha,\beta,N)}}.$

The Hahn polynomials satisfy the following recurrence relation [19, equation
(9.5.3)]

$\displaystyle\Lambda(x)y_{n}(x)=A(n)y_{n+1}(x)-\bigl{(}A(n)+C(n)\bigr{)}y_{n}(x)+C(n)y_{n-1}(x)$
(2.4)

with

$\displaystyle y_{n}(x)=Q_{n}(x;\alpha,\beta,N),\qquad\Lambda(x)=-x,$ (2.5)
$\displaystyle
A(n)=\frac{(n+\alpha+1)(n+\alpha+\beta+1)(N-n)}{(2n+\alpha+\beta+1)(2n+\alpha+\beta+2)},\qquad
C(n)=\frac{n(n+\alpha+\beta+N+1)(n+\beta)}{(2n+\alpha+\beta)(2n+\alpha+\beta+1)}.$

Related to the Hahn polynomials are the dual Hahn polynomials:
$R_{n}(\lambda(x);\gamma,\delta,N)$ of degree $n$, $n=0,1,\ldots,N$, in the
variable $\lambda(x)=x(x+\gamma+\delta+1)$, with parameters $\gamma>-1$ and
$\delta>-1$ (or $\gamma<-N$ and $\delta<-N$) which are defined similarly to
(2.1) [13, 19, 23]

$\displaystyle
R_{n}(\lambda(x);\gamma,\delta,N)={}_{3}F_{2}\left(\genfrac{}{}{0.0pt}{}{-x,x+\gamma+\delta+1,-n}{\gamma+1,-N};1\right).$
(2.6)

As is well known, the (discrete) orthogonality relation of the dual Hahn
polynomials is just the “dual” of (2.3)

$\displaystyle\sum_{x=0}^{N}\overline{w}(x;\gamma,\delta,N)R_{n}(\lambda(x);\gamma,\delta,N)R_{n^{\prime}}(\lambda(x);\gamma,\delta,N)=\overline{h}_{n}(\gamma,\delta,N)\delta_{n,n^{\prime}},$
(2.7)

where

$\displaystyle\overline{w}(x;\gamma,\delta,N)=\frac{(2x+\gamma+\delta+1)(\gamma+1)_{x}(-N)_{x}N!}{(-1)^{x}(x+\gamma+\delta+1)_{N+1}(\delta+1)_{x}x!},$
$\displaystyle\overline{h}_{n}(\gamma,\delta,N)=\left[\binom{\gamma+n}{n}\binom{N+\delta-n}{N-n}\right]^{-1}.$

Orthonormal dual Hahn functions are defined by

$\displaystyle\tilde{R}_{n}(\lambda(x);\gamma,\delta,N)\equiv\frac{\sqrt{\overline{w}(x;\gamma,\delta,N)}R_{n}(\lambda(x);\gamma,\delta,N)}{\sqrt{\overline{h}_{n}(\gamma,\delta,N)}}.$
(2.8)

Dual Hahn polynomials also satisfy a recurrence relation of the form (2.4),
with [19, equation (9.6.3)]

$\displaystyle
y_{n}(x)=R_{n}(\lambda(x);\gamma,\delta,N),\qquad\Lambda(x)=\lambda(x)=x(x+\gamma+\delta+1),$
$\displaystyle A(n)=(n+\gamma+1)(n-N),\qquad C(n)=n(n-\delta-N-1).$ (2.9)

In [27], the following difference equations involving two sets of Hahn
polynomials were derived (for convenience we use the notation $Q_{n}(x)\equiv
Q_{n}(x;\alpha,\beta+1,N)$ and $\hat{Q}_{n}(x)\equiv
Q_{n}(x;\alpha+1,\beta,N)$):

$\displaystyle(N+\beta+1-x)Q_{n}(x)-(N-x)Q_{n}(x+1)=\frac{(n+\alpha+1)(n+\beta+1)}{\alpha+1}\hat{Q}_{n}(x),$
(2.10)
$\displaystyle(x+1)\hat{Q}_{n}(x)-(\alpha+x+2)\hat{Q}_{n}(x+1)=-(\alpha+1)Q_{n}(x+1).$
(2.11)

Writing out these difference equations for $x=0,1,\ldots,N$, the resulting set
of equations can easily be written in matrix form. For this matrix form, let
us use the normalized version of the polynomials, and construct the following
$(2N+2)\times(2N+2)$ matrix $U$ with elements

$\displaystyle
U_{2x,N-n}=U_{2x,N+n+1}=\frac{(-1)^{x}}{\sqrt{2}}\tilde{Q}_{n}(x;\alpha,\beta+1,N),$
(2.12) $\displaystyle
U_{2x+1,N-n}=-U_{2x+1,N+n+1}=-\frac{(-1)^{x}}{\sqrt{2}}\tilde{Q}_{n}(x;\alpha+1,\beta,N),$
(2.13)

where $x,n\in\\{0,1,\ldots,N\\}$. By construction, this matrix is orthogonal
[27]: the fact that the columns of $U$ are orthonormal follows from the
orthogonality relation of the Hahn polynomials, and from the signs in the
matrix $U$. Thus $U^{T}U=UU^{T}=I$, the identity matrix.

The normalized difference equations (2.10), (2.11) for $x=0,1,\ldots,N$ can
then be cast in matrix form. The coefficients in the left hand sides of
(2.10), (2.11) give rise to a tridiagonal $(2N+2)\times(2N+2)$-matrix of the
form

$\displaystyle M=\left(\begin{matrix}0&M_{0}&0&&\\\ M_{0}&0&M_{1}&\ddots&\\\
0&M_{1}&0&\ddots&0\\\ &\ddots&\ddots&\ddots&M_{2N}\\\
&&0&M_{2N}&0\end{matrix}\right),$ (2.14)

with

$\displaystyle M_{2k}=\sqrt{(k+\alpha+1)(N+\beta+1-k)},\qquad
M_{2k+1}=\sqrt{(k+1)(N-k)}.$ (2.15)

Suppose $\alpha>-1$, $\beta>-1$ or $\alpha<-N-1$, $\beta<-N-1$ and let $U$ be
the orthogonal matrix determined in (2.12), (2.13). Then [27] the columns of
$U$ are the eigenvectors of $M$, i.e.,

$\displaystyle MU=UD,$ (2.16)

where $D$ is a diagonal matrix containing the eigenvalues of $M$

$\displaystyle
D=\operatorname{diag}(-\epsilon_{N},\ldots,-\epsilon_{1},-\epsilon_{0},\epsilon_{0},\epsilon_{1},\ldots,\epsilon_{N}),$
$\displaystyle\epsilon_{k}=\sqrt{(\alpha+k+1)(\beta+k+1)},\qquad
k=0,1,\ldots,N.$ (2.17)

Note that the eigenvalues of the matrix $M$ are (up to a factor 2) the same as
those of the matrix $C_{2N+2}(\alpha,\beta)$, the two-parameter extension of
the Sylvester–Kac matrix. As we will further discuss in Section 6, the above
result proves that the eigenvalues of $C_{2N+2}(\alpha,\beta)$ are indeed
given by (1.4). Even more: the orthonormal eigenvectors of $M$ are just the
columns of $U$.

Another way of looking at (2.16) is in terms of the dual Hahn polynomials.
Interchanging $x$ and $n$ in the expressions (2.12), (2.13), we have

$\displaystyle
U_{2n,N-x}=U_{2n,N+x+1}=\frac{(-1)^{n}}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\alpha,\beta+1,N),$
(2.18) $\displaystyle
U_{2n+1,N-x}=-U_{2n+1,N+x+1}=-\frac{(-1)^{n}}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\alpha+1,\beta,N),$
(2.19)

where $x,n\in\\{0,1,\ldots,N\\}$. In this way, each row of the matrix $U$
consists of a dual Hahn polynomial of a certain degree, having different
parameter values for even and odd rows. Now, the relation (2.16) can be
interpreted as a three-term recurrence relation with $M$ being the Jacobi
matrix. Two sets of (dual) Hahn polynomials (with different parameters) are
thus combined into a new set of polynomials such that the Jacobi matrix for
this new set has a simple two-diagonal form, with simple eigenvalues. The pair
of difference equations (2.10), (2.11) involving two sets of Hahn polynomials
then corresponds to the following relations involving the dual Hahn
polynomials $R_{n}(x)\equiv R_{n}(\lambda(x);\gamma,\delta+1,N)$ and
$\hat{R}_{n}(x)\equiv R_{n}(\lambda(x);\gamma+1,\delta,N)$:

$\displaystyle(N+\delta+1-n)R_{n}(x)-(N-n)R_{n+1}(x)=\frac{(x+\gamma+1)(x+\delta+1)}{(\gamma+1)}\hat{R}_{n}(x),$
(2.20)
$\displaystyle(n+1)\hat{R}_{n}(x)-(n+\gamma+2)\hat{R}_{n+1}(x)=-(\gamma+1)R_{n+1}(x).$
(2.21)

This is in fact a special case of the so-called Christoffel transform of a
dual Hahn polynomial with its transformation parameter chosen specifically so
that the result is again a dual Hahn polynomial (with different parameters).
We will further elaborate on this in Section 5.

This introductory example, taken from [27], opens the following question: in
how many ways can two sets of (dual) Hahn polynomials be combined such that
the Jacobi matrix is two-diagonal? This will be answered in the following
section.

##  3 Doubling dual Hahn polynomials: classification

The essential relation in the previous example is the existence of a pair of
“recurrence relations” (2.20), (2.21) intertwining two types of dual Hahn
polynomials (or equivalently a couple of difference equations (2.10), (2.11)
for two types of their duals, the Hahn polynomials). Let us therefore examine
the existence of such relations in general. Say we have two types of dual Hahn
polynomials with different parameter values for $\gamma$ and $\delta$ (and
possibly $N$) denoted by $R_{n}(\lambda(x);\gamma,\delta,N)$ and
$R_{n}(\lambda(\hat{x});\hat{\gamma},\hat{\delta},\hat{N})$, that are related
in the following manner

$\displaystyle
a(n)R_{n}(\lambda(x);\gamma,\delta,N)+b(n)R_{n+1}(\lambda(x);\gamma,\delta,N)={\hat{d}}(x)R_{n}(\lambda(\hat{x});\hat{\gamma},\hat{\delta},\hat{N})$
(3.1)
$\displaystyle\hat{a}(n)R_{n}(\lambda(\hat{x});\hat{\gamma},\hat{\delta},\hat{N})+\hat{b}(n)R_{n+1}(\lambda(\hat{x});\hat{\gamma},\hat{\delta},\hat{N})=d(x)R_{n+1}(\lambda(x);\gamma,\delta,N).$
(3.2)

If we want these relations to correspond to a matrix identity like (2.16),
then it is indeed necessary that the (unknown) functions $a(n)$, $\hat{a}(n)$,
$b(n)$ and $\hat{b}(n)$ are functions of $n$ and not of $x$, and that $d(x)$
and $\hat{d}(x)$ are functions of $x$ and not of $n$. Of course, the
parameters $\gamma$, $\delta$, $N$, $\hat{\gamma}$, $\hat{\delta}$, $\hat{N}$
can appear in these functions.

In order to lift this technique also to other polynomials than just the dual
Hahn polynomials, say we have the following relations between two sets of
orthogonal polynomials of the same class, denoted by $y_{n}$ and
$\hat{y}_{n}$, but with different parameter values

$\displaystyle a(n)y_{n}+b(n)y_{n+1}={\hat{d}}(x)\hat{y}_{n},$ (3.3)
$\displaystyle\hat{a}(n)\hat{y}_{n}+\hat{b}(n)\hat{y}_{n+1}=d(x)y_{n+1},$
(3.4)

where $a$, ${\hat{a}}$, $b$, ${\hat{b}}$ are independent of $x$ and $d$,
${\hat{d}}$ are independent of $n$. Although (3.3), (3.4) are not actual
recurrence relations since they involve both $y_{n}$ and $\hat{y}_{n}$, we
will refer to a couple of such relations intertwining two types of orthogonal
polynomials as “a pair of recurrence relations”.

When substituting (3.4) in (3.3), we arrive at the following recurrence
relation for $\hat{y}_{n}$

$\displaystyle
a(n)\bigl{[}\hat{a}(n-1)\hat{y}_{n-1}+\hat{b}(n-1)\hat{y}_{n}\bigr{]}+b(n)\bigl{[}\hat{a}(n)\hat{y}_{n}+\hat{b}(n)\hat{y}_{n+1}\bigr{]}=d(x){\hat{d}}(x)\hat{y}_{n}.$
(3.5)

In the same manner, $\hat{y}_{n}$ can be eliminated to find a recurrence
relation for $y_{n}$

$\displaystyle\hat{a}(n-1)\bigl{[}a(n-1)y_{n-1}+b(n-1)y_{n}\bigr{]}+\hat{b}(n-1)\bigl{[}a(n)y_{n}+b(n)y_{n+1}\bigr{]}={\hat{d}}(x)d(x)y_{n}.$
(3.6)

Of course, the orthogonal polynomials $y_{n}$ already satisfy a three-term
recurrence relation of the form (2.4). A comparison of the coefficients of
$y_{n+1}$, $y_{n}$, $y_{n-1}$ in (3.5), (3.6) with the known coefficients
given in (2.9) leads to the following set of requirements for $a$,
${\hat{a}}$, $b$, ${\hat{b}}$, $d$, ${\hat{d}}$

$\displaystyle a(n)\hat{a}(n-1)={\hat{C}}(n),$ (3.7) $\displaystyle
a(n-1)\hat{a}(n-1)=C(n),$ (3.8) $\displaystyle
a(n)\hat{b}(n-1)+\hat{a}(n)b(n)-d(x)\,{\hat{d}}(x)=-\bigl{[}\hat{\Lambda}(x)+{\hat{A}}(n)+{\hat{C}}(n)\bigr{]},$
(3.9) $\displaystyle
a(n)\hat{b}(n-1)+\hat{a}(n-1)b(n-1)-{\hat{d}}(x)d(x)=-\bigl{[}\Lambda(x)+A(n)+C(n)\bigr{]},$
(3.10) $\displaystyle b(n)\hat{b}(n)={\hat{A}}(n),$ (3.11) $\displaystyle
b(n)\hat{b}(n-1)=A(n).$ (3.12)

After a slight rearrangement of terms in the requirements (3.9) and (3.10), we
arrive at two new equations where the left hand side is independent of $x$
while the right hand side is independent of $n$, namely,

$\displaystyle
a(n)\hat{b}(n-1)+\hat{a}(n)b(n)+{\hat{A}}(n)+{\hat{C}}(n)=d(x){\hat{d}}(x)-\hat{\Lambda}(x),$
(3.13) $\displaystyle
a(n)\hat{b}(n-1)+\hat{a}(n-1)b(n-1)+A(n)+C(n)={\hat{d}}(x)d(x)-\Lambda(x).$
(3.14)

Hence, the two sides must be independent of both $n$ and $x$. By means of
(3.7)–(3.12) we can eliminate $A$, $\hat{A}$, $C$, $\hat{C}$ to find

$\displaystyle
a(n)\bigl{[}\hat{a}(n-1)+\hat{b}(n-1)\bigr{]}+b(n)\bigl{[}\hat{a}(n)+\hat{b}(n)\bigr{]}=d(x){\hat{d}}(x)-\hat{\Lambda}(x),$
$\displaystyle\hat{a}(n-1)\bigl{[}a(n-1)+b(n-1)\bigr{]}+\hat{b}(n-1)\bigl{[}a(n)+b(n)\bigr{]}={\hat{d}}(x)d(x)-\Lambda(x).$

Moreover, subtracting one from the other yields

$\displaystyle\Lambda(x)-\hat{\Lambda}(x)=\hat{a}(n-1)\bigl{[}a(n)-a(n-1)-b(n-1)\bigr{]}+b(n)\bigl{[}\hat{a}(n)+\hat{b}(n)-\hat{b}(n-1)\bigr{]}.\\!\\!\\!$
(3.15)

Now, for a given class of orthogonal polynomials with recurrence relation of
the form (2.4), we determine all possible functions $a$, $\hat{a}$, $b$,
$\hat{b}$, $d$, ${\hat{d}}$ satisfying the list of requirements (3.7)–(3.12).
Hereto, we proceed as follows

  * •

From (3.7) and (3.8) we observe that, up to a multiplicative factor, $C(n)$ is
split into two functions, $a(n-1)$ and $\hat{a}(n-1)$. When $a(n-1)$ is
shifted by 1 in $n$ and multiplied again by $\hat{a}(n-1)$ we must arrive at
$\hat{C}(n)$. Hence, $C$ and $\hat{C}$ consist of an identical part, and a
part which differs by a shift of 1 in $n$. This observation gives a first list
of possibilities for $a$ and $\hat{a}$.

  * •

Similarly we find a list for $b$ and $\hat{b}$ by means of (3.11) and (3.12).

  * •

These possibilities are then to be compared with requirements (3.9) and
(3.10). From (3.13), (3.14) and (3.15) we get an expression for the product
$d(x){\hat{d}(x)}$. Finally, the set of remaining choices for $a$,
${\hat{a}}$, $b$, ${\hat{b}}$ are to be plugged in (3.4) and (3.3) in order to
get $d$, ${\hat{d}}$ and to verify if these relations indeed hold.

The actual performance of the procedure just described is still quite long and
tedious, when carried out for a fixed class of polynomials. In what follows we
achieve this for the dual Hahn polynomials, which have the easiest recurrence
relation, and it takes about three pages to present this. The reader who
wishes to skip the details can advance to Theorem 1.

For dual Hahn polynomials, the data is given by (2.9)

$\displaystyle
y_{n}=R_{n}(\lambda(x);\gamma,\delta,N),\qquad\hat{y}_{n}=R_{n}\big{(}\lambda(\hat{x});\hat{\gamma},\hat{\delta},\hat{N}\big{)},\qquad\Lambda(x)=\lambda(x)=x(x+\gamma+\delta+1),$
$\displaystyle A(n)=(n+\gamma+1)(n-N),\qquad C(n)=n(n-\delta-N-1),$

and with similar expressions for $\hat{\Lambda}(x)$, $\hat{A}(n)$ and
$\hat{C}(n)$ (with $x$, $\gamma$, $\delta$, $N$ replaced by $\hat{x}$,
$\hat{\gamma}$, $\hat{\delta}$, $\hat{N}$). From (3.15), the following
expression must be independent of $x$

$\displaystyle\Lambda(x)-\hat{\Lambda}(x)=x(x+\gamma+\delta+1)-\hat{x}\big{(}\hat{x}+\hat{\gamma}+\hat{\delta}+1\big{)}.$

In order for the term in $x^{2}$ to disappear, we must have $\hat{x}=x+\xi$
which gives

$\displaystyle
x(x+\gamma+\delta+1)-(x+\xi)(x+\xi+\hat{\gamma}+\hat{\delta}+1)=(\gamma+\delta-\hat{\gamma}-\hat{\delta}-2\xi)x-\xi(\xi+\hat{\gamma}+\hat{\delta}+1)$

and as we require the coefficient of $x$ to be zero we find the following
condition for $\xi$

$\displaystyle\gamma+\delta-(\hat{\gamma}+\hat{\delta})=2\xi.$ (3.16)

From (3.8) we see that we have four distinct possible combinations for
$a(n-1)$ and $\hat{a}(n-1)$

$\displaystyle a(n-1)=1c_{a},\qquad$
$\displaystyle\hat{a}(n-1)=n(n-\delta-N-1)c_{a}^{-1},$ (a1) $\displaystyle
a(n-1)=nc_{a},\qquad$ $\displaystyle\hat{a}(n-1)=(n-\delta-N-1)c_{a}^{-1},$
(a2) $\displaystyle a(n-1)=(n-\delta-N-1)c_{a},\qquad$
$\displaystyle\hat{a}(n-1)=nc_{a}^{-1},$ (a3) $\displaystyle
a(n-1)=n(n-\delta-N-1)c_{a},\qquad$ $\displaystyle\hat{a}(n-1)=1c_{a}^{-1},$
(a4)

with $c_{a}$ a factor. Combining this with (3.7) we must have

$\displaystyle
a(n)\hat{a}(n-1)={\hat{C}}(n)=n\big{(}n-\hat{\delta}-\hat{N}-1\big{)}.$

This immediately implies that $c_{a}$ is independent of $n$, and (a1)–(a4)
yield the following possibilities

$\displaystyle n(n-\delta-N-1)=n(n-\hat{\delta}-\hat{N}-1)\ $
$\displaystyle\implies\ \delta+N=\hat{\delta}+\hat{N},$ (a1′)
$\displaystyle(n+1)(n-\delta-N-1)=n(n-\hat{\delta}-\hat{N}-1)\\!\\!\\!$
$\displaystyle\implies\
\delta+N+1=0\,\land\,\hat{\delta}+\hat{N}+2=0,\\!\\!\\!\\!\\!\\!\\!\\!$ (a2′)
$\displaystyle(n-\delta-N)n=n(n-\hat{\delta}-\hat{N}-1)\ $
$\displaystyle\implies\ \delta+N=\hat{\delta}+\hat{N}+1,$ (a3′)
$\displaystyle(n+1)(n-\delta-N)=n(n-\hat{\delta}-\hat{N}-1)\ $
$\displaystyle\implies\ \delta+N=0\,\land\,\hat{\delta}+\hat{N}+2=0.$ (a4′)

Because of the restriction on $\delta$ the option (a4′) is ineligible, leaving
(a1′)–(a3′) as only viable options.

In a similar way, from (3.12) we see that we have four possible combinations
for $b(n)$ and $\hat{b}(n)$,

$\displaystyle b(n)=1c_{b},\qquad$
$\displaystyle\hat{b}(n-1)=(n+\gamma+1)(n-N)c_{b}^{-1},$ (b1) $\displaystyle
b(n)=(n+\gamma+1)c_{b},\qquad$ $\displaystyle\hat{b}(n-1)=(n-N)c_{b}^{-1},$
(b2) $\displaystyle b(n)=(n-N)c_{b},\qquad$
$\displaystyle\hat{b}(n-1)=(n+\gamma+1)c_{b}^{-1},$ (b3) $\displaystyle
b(n)=(n+\gamma+1)(n-N)c_{b},\qquad$ $\displaystyle\hat{b}(n-1)=1c_{b}^{-1}.$
(b4)

Combining this with (3.11) we must have

$\displaystyle b(n)\hat{b}(n)={\hat{A}}(n)=(n+\hat{\gamma}+1)(n-\hat{N})$

This implies that $c_{b}$ is independent of $n$ and moreover for (b1)–(b4)
yields

$\displaystyle(n+\gamma+2)(n-N+1)=(n+\hat{\gamma}+1)(n-\hat{N})$
$\displaystyle\implies\ \gamma+1=\hat{\gamma}\,\land\,N-1=\hat{N},$ (b1′)
$\displaystyle(n+\gamma+1)(n-N+1)=(n+\hat{\gamma}+1)(n-\hat{N})$
$\displaystyle\implies\ \gamma=\hat{\gamma}\,\land\,N-1=\hat{N},$ (b2′)
$\displaystyle(n+\gamma+2)(n-N)=(n+\hat{\gamma}+1)(n-\hat{N})$
$\displaystyle\implies\ \gamma+1=\hat{\gamma}\,\land\,N=\hat{N},$ (b3′)
$\displaystyle(n+\gamma+1)(n-N)=(n+\hat{\gamma}+1)(n-\hat{N})$
$\displaystyle\implies\ \gamma=\hat{\gamma}\,\land\,N=\hat{N}.$ (b4′)

We thus have four viable options for $b$, $\hat{b}$ and three for $a$,
$\hat{a}$, giving a total of 12 possible combinations, which we will
systematically consider and treat.

Case (b1). Plugging (b1) in (3.14), we get

$\displaystyle
a(n)(n+\gamma+1)(n-N)\,c_{b}^{-1}+\hat{a}(n-1)c_{b}+(n+\gamma+1)(n-N)+n(n-\delta-N-1)$
$\displaystyle\qquad{}={\hat{d}}(x)d(x)-\Lambda(x).$

As the right hand side is independent of $n$, so must be the left hand side.
This eliminates options (a2) and (a3) for $a$, $\hat{a}$ as that would result
in a third order term in $n$ which cannot vanish. On the other hand, (a1)
yields

$\displaystyle(n+\gamma+1)(n-N)\frac{c_{a}}{c_{b}}+n(n-\delta-N-1)\frac{c_{b}}{c_{a}}+(n+\gamma+1)(n-N)+n(n-\delta-N-1)$
$\displaystyle\qquad{}={\hat{d}}(x)d(x)-\Lambda(x).$

This must be independent of $n$, so the coefficient of $n^{2}$ in the left
hand side must vanish, hence ${c_{a}}/{c_{b}}+{c_{b}}/{c_{a}}+2=0$ or thus
${c_{a}}/{c_{b}}=-1$. For this value of ${c_{a}}/{c_{b}}$ the left hand side
equals zero and is indeed independent of $n$. Note that this leaves one degree
of freedom as only the ratio ${c_{a}}/{c_{b}}$ is fixed. This is just a global
scalar factor for (3.3) and (3.4), also present in (2.4). Henceforth, for
convenience, we set $c_{a}=1$ and $c_{b}=-1$.

The combined options (b1) and (a1) thus give a valid set of equations of the
form (3.3) and (3.4), and they correspond to the parameter values

$\displaystyle\hat{\gamma}=\gamma+1,\qquad\hat{\delta}=\delta+1,\qquad\hat{N}=N-1.$

Moreover, by means of (3.16) we find $\xi=-1$ and so $\hat{x}=x-1$. Finally,
plugging these $a$, ${\hat{a}}$, $b$, ${\hat{b}}$ in (3.3) and (3.4), and
putting $n=0$ we find

$\displaystyle
R_{0}(\lambda(x);\gamma,\delta,N)-R_{1}(\lambda(x);\gamma,\delta,N)=\frac{x(x+\gamma+\delta+1)}{N(\gamma+1)}=\hat{d}(x)$

and similarly $d(x)=N(\gamma+1)$. Hence, for $R_{n}(x)\equiv
R_{n}(\lambda(x);\gamma,\delta,N)$ and $\hat{R}_{n}(x)\equiv
R_{n}(\lambda(x-1)$; $\gamma+1,\delta+1,N-1)$ we have the relations

$\displaystyle
R_{n}(x)-R_{n+1}(x)=\frac{x(x+\gamma+\delta+1)}{N(\gamma+1)}\hat{R}_{n}(x),$
$\displaystyle-(n+1)(N-n+\delta)\hat{R}_{n}(x)+(N-n-1)(n+\gamma+2)\hat{R}_{n+1}(x)=N(\gamma+1)R_{n+1}(x).$

Interchanging $x$ and $n$, these recurrence relations for dual Hahn
polynomials are precisely the known actions of the forward and backward shift
operator for Hahn polynomials [19, equations (9.5.6) and (9.5.8)].

Case (b2). Next, we consider the option (b2) for $b$, $\hat{b}$. Plugging (b2)
in (3.14), we get

$\displaystyle
a(n)(n-N)c_{b}^{-1}+\hat{a}(n-1)(n+\gamma)c_{b}+(n+\gamma+1)(n-N)+n(n-\delta-N-1)$
$\displaystyle\qquad{}={\hat{d}}(x)d(x)-\Lambda(x).$

Since the left hand side must be independent of $n$, option (a1) is ruled out.
Also option (a2) is ruled out: using (a2) and $\delta+N+1=0$ (from (a2′)), the
left hand side again cannot be independent of $n$. Only (a3) remains, giving

$\displaystyle(n-\delta-N)(n-N)\,\frac{c_{a}}{c_{b}}+n(n+\gamma)\frac{c_{b}}{c_{a}}+(n+\gamma+1)(n-N)+n(n-\delta-N-1)$
$\displaystyle\qquad{}={\hat{d}}(x)d(x)-\Lambda(x).$

In order for $n^{2}$ in the left hand side to vanish, we again require
${c_{a}}/{c_{b}}=-1$. This gives

$\displaystyle-N(N+\gamma+\delta+1)={\hat{d}}(x)d(x)-\Lambda(x),$

and we see that both sides are indeed independent of $n$.

The combined options (b2) and (a3) also give a valid set of equations of the
form (3.3) and (3.4), now corresponding to the parameter values

$\displaystyle\hat{\gamma}=\gamma,\qquad\hat{\delta}=\delta,\qquad\hat{N}=N-1.$

Moreover, by means of (3.16) we find $\xi=0$ and so $\hat{x}=x$. Putting again
$n=0$ in (3.3) and (3.4) for these $a$, ${\hat{a}}$, $b$, ${\hat{b}}$ we find

$\displaystyle\begin{split}&(-\delta-N)R_{0}(\lambda(x);\gamma,\delta,N)-(\gamma+1)R_{1}(\lambda(x);\gamma,\delta,N)\\\
&\qquad{}=-\frac{(N-x)(x+\gamma+\delta+N+1)}{N}=\hat{d}(x)\end{split}$

and similarly $d(x)=N$. The relations in question are then, for
$R_{n}(x)\equiv R_{n}(\lambda(x);\gamma,\delta,N)$ and $\hat{R}_{n}(x)\equiv
R_{n}(\lambda(x);\gamma,\delta,N-1)$

$\displaystyle(n-\delta-N)R_{n}(x)-(n+\gamma+1)R_{n+1}(x)=-\frac{(N-x)(x+\gamma+\delta+N+1)}{N}\hat{R}_{n}(x),$
$\displaystyle(n+1)\hat{R}_{n}(x)-(n-N+1)\hat{R}_{n+1}(x)=NR_{n+1}(x),$

which can be verified algebraically or by means of a computer algebra package.

Case (b3). The next option to consider is (b3), for which (3.14) becomes

$\displaystyle
a(n)(n+\gamma+1)c_{b}^{-1}+\hat{a}(n-1)(n-N-1)c_{b}+(n+\gamma+1)(n-N)+n(n-\delta-N-1)$
$\displaystyle\qquad{}={\hat{d}}(x)d(x)-\Lambda(x).$

The independence of $n$ in the left hand side again rules out options (a1) and
(a2), while (a3) gives

$\displaystyle(n-\delta-N)(n+\gamma+1)\frac{c_{a}}{c_{b}}+n(n-N-1)\frac{c_{b}}{c_{a}}+(n+\gamma+1)(n-N)+n(n-\delta-N-1)$
$\displaystyle\qquad{}={\hat{d}}(x)d(x)-\Lambda(x).$

Also here, we require ${c_{a}}/{c_{b}}=-1$ to arrive at a left hand side
independent of $n$, namely

$\displaystyle(\gamma+1)\delta={\hat{d}}(x)d(x)-\Lambda(x).$

The combined options (b3) and (a3) thus give a valid set of equations of the
form (3.3) and (3.4), and they correspond to the parameter values

$\displaystyle\hat{\gamma}=\gamma+1,\qquad\hat{\delta}=\delta-1,\qquad\hat{N}=N;$

by means of (3.16) we find $\xi=0$ and so $\hat{x}=x$. Finally, plugging these
$a$, ${\hat{a}}$, $b$, ${\hat{b}}$ in (3.3) and (3.4) and putting $n=0$ we
find

$\displaystyle(-\delta-N)R_{0}(\lambda(x);\gamma,\delta,N)+NR_{1}(\lambda(x);\gamma,\delta,N)=-\frac{(x+\gamma+1)(x+\delta)}{(\gamma+1)}=\hat{d}(x)$

and similarly $d(x)=\gamma+1$.

Hence we have the relations, for $R_{n}(x)\equiv
R_{n}(\lambda(x);\gamma,\delta,N)$ and $\hat{R}_{n}(x)\equiv
R_{n}(\lambda(x);\gamma+1$, $\delta-1,N)$

$\displaystyle-(n-\delta-N)R_{n}(x)+(n-N)R_{n+1}(x)=\frac{(x+\gamma+1)(x+\delta)}{(\gamma+1)}\hat{R}_{n}(x),$
$\displaystyle-(n+1)\hat{R}_{n}(x)+(n+\gamma+2)\hat{R}_{n+1}(x)=(\gamma+1)R_{n+1}(x).$

These can again be verified algebraically or by means of a computer algebra
package. Note that these relations coincide with (2.20), (2.21) from the
previous section (up to a shift $\delta\rightarrow\delta+1$).

Case (b4). The final option (b4) for $b$, $\hat{b}$ does not correspond to a
valid set of equations of the form (3.3) and (3.4) as the left hand side of
(3.14) can never be independent of $n$ for either options (a1), (a2) or (a3).

This completes the analysis in the case of dual Hahn polynomials, and we have
the following result

######  Theorem 1.

The only way to double dual Hahn polynomials, i.e., to combine two sets of
dual Hahn polynomials such that they satisfy a pair of recurrence relations of
the form (3.1), (3.2) is one of the three cases:

dual Hahn I, $R_{n}(x)\equiv R_{n}(\lambda(x);\gamma,\delta,N)$ and
$\hat{R}_{n}(x)\equiv R_{n}(\lambda(x-1);\gamma+1,\delta+1,N-1)$:

$\displaystyle
R_{n}(x)-R_{n+1}(x)=\frac{x(x+\gamma+\delta+1)}{N(\gamma+1)}\hat{R}_{n}(x),$
$\displaystyle-(n+1)(N-n+\delta)\hat{R}_{n}(x)+(N-n-1)(n+\gamma+2)\hat{R}_{n+1}(x)=N(\gamma+1)R_{n+1}(x).$

dual Hahn II, $R_{n}(x)\equiv R_{n}(\lambda(x);\gamma,\delta,N)$ and
$\hat{R}_{n}(x)\equiv R_{n}(\lambda(x);\gamma,\delta,N-1)$:

$\displaystyle(n-\delta-N)R_{n}(x)-(n+\gamma+1)R_{n+1}(x)=-\frac{(N-x)(x+\gamma+\delta+N+1)}{N}\hat{R}_{n}(x),$
$\displaystyle(n+1)\hat{R}_{n}(x)-(n-N+1)\hat{R}_{n+1}(x)=NR_{n+1}(x).$

dual Hahn III, $R_{n}(x)\equiv R_{n}(\lambda(x);\gamma,\delta,N)$ and
$\hat{R}_{n}(x)\equiv R_{n}(\lambda(x);\gamma+1,\delta-1,N)$:

$\displaystyle-(n-\delta-N)R_{n}(x)+(n-N)R_{n+1}(x)=\frac{(x+\gamma+1)(x+\delta)}{(\gamma+1)}\hat{R}_{n}(x),$
$\displaystyle-(n+1)\hat{R}_{n}(x)+(n+\gamma+2)\hat{R}_{n+1}(x)=(\gamma+1)R_{n+1}(x).$

By interchanging $x$ and $n$, each of the recurrence relations for dual Hahn
polynomials in the previous theorem gives rise to a set of forward and
backward shift operators for regular Hahn polynomials. The case dual Hahn I
corresponds just to the known forward and backward shift operators for Hahn
polynomials [19]: $Q_{n}(x)\equiv Q_{n}(x;\alpha,\beta,N)$ and
$\hat{Q}_{n}(x)\equiv Q_{n}(x;\alpha+1,\beta+1$, $N-1)$:

$\displaystyle
Q_{n}(x)-Q_{n}(x+1)=\frac{n(n+\alpha+\beta+1)}{N(\alpha+1)}\hat{Q}_{n-1}(x),$
$\displaystyle-(x+1)(N-x+\beta)\hat{Q}_{n-1}(x)+(N-x-1)(x+\alpha+2)\hat{Q}_{n-1}(x+1)$
$\displaystyle\qquad{}=N(\alpha+1)Q_{n}(x+1).$

The case dual Hahn III corresponds to our introductory example (2.10), (2.11)
(up to a shift $\beta\rightarrow\beta+1$), and appears already in [27]. The
case dual Hahn II yields a new set of relations (encountered recently in [16,
equations (16), (17)]), namely $Q_{n}(x)\equiv Q_{n}(x;\alpha,\beta,N)$ and
$\hat{Q}_{n}(x)\equiv Q_{n}(x;\alpha,\beta,N-1)$:

$\displaystyle(x-\beta-N)Q_{n}(x)-(x+\alpha+1)Q_{n}(x+1)=-\frac{(N-n)(n+\alpha+\beta+N+1)}{N}\hat{Q}_{n}(x),$
$\displaystyle(x+1)\hat{Q}_{n}(x)-(x-N+1)\hat{Q}_{n}(x+1)=NQ_{n}(x+1).$

The most important thing is, however, that we have classified the possible
cases.

Because the sets of recurrence relations are of the form (3.1), (3.2), they
can be cast in matrix form, like in (2.16), with a simple two-diagonal matrix.
For the case dual Hahn I, note that the $N$-values of $R_{n}(x)$ and
$\hat{R}_{n}(x)$ differ by 1, so the definition of the matrix $U$ (again in
terms of the normalized version of the polynomials) requires a little bit more
attention. The matrix $U$ is now of order $(2N+1)\times(2N+1)$ with matrix
elements

$\displaystyle
U_{2n,N-x}=U_{2n,N+x}=\frac{(-1)^{n}}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\gamma,\delta,N),\qquad
x=1,\ldots,N,$ $\displaystyle
U_{2n+1,N-x}=-U_{2n+1,N+x}=-\frac{(-1)^{n}}{\sqrt{2}}\tilde{R}_{n}(\lambda(x-1);\gamma+1,\delta+1,N-1),\qquad
x=1,\ldots,N,$ $\displaystyle
U_{2n,N}=(-1)^{n}\tilde{R}_{n}(\lambda(0);\gamma,\delta,N),\qquad
U_{2n+1,N}=0,$ (3.17)

where the row index of the matrix $U$ (denoted here by $2n$ or $2n+1$,
depending on the parity of the index) also runs over the integers from 0 up to
$2N$. This matrix $U$ is orthogonal: the orthogonality relation of the dual
Hahn polynomials (2.7) and the signs in the matrix $U$ imply that its rows are
orthonormal. Thus $U^{T}U=UU^{T}=I$, the identity matrix. Then the recurrence
relations for dual Hahn I of Theorem 1 are now reformulated in terms of a two-
diagonal $(2N+1)\times(2N+1)$-matrix of the form

$\displaystyle M=\left(\begin{matrix}0&M_{0}&0&&\\\ M_{0}&0&M_{1}&\ddots&\\\
0&M_{1}&0&\ddots&0\\\ &\ddots&\ddots&\ddots&M_{2N-1}\\\
&&0&M_{2N-1}&0\end{matrix}\right).$ (3.18)

Explicitly

######  Proposition 2 (dual Hahn I).

Suppose $\gamma>-1$, $\delta>-1$. Let $M$ be the two-diagonal matrix (3.18)
with

$\displaystyle M_{2k}=\sqrt{(k+\gamma+1)(N-k)},\qquad
M_{2k+1}=\sqrt{(k+1)(N+\delta-k)},$ (3.19)

and $U$ the orthogonal matrix determined in (3.17). Then the columns of $U$
are the eigenvectors of $M$, i.e., $MU=UD$, where $D$ is a diagonal matrix
containing the eigenvalues of $M$

$\displaystyle
D=\operatorname{diag}(-\epsilon_{N},\ldots,-\epsilon_{1},0,\epsilon_{1},\ldots,\epsilon_{N}),$
$\displaystyle\epsilon_{k}=\sqrt{k(k+\gamma+\delta+1)},\qquad k=1,\ldots,N.$
(3.20)

Note that we have kept only the conditions under which the matrix $M$ is real.
The other conditions for which the dual Hahn polynomials in (3.17) can be
normalized (namely $\gamma<-N$, $\delta<-N$) would give rise to imaginary
values in (3.19). In such a case, the relation $MU=UD$ remains valid, and also
$D$ would have imaginary values.

For the case dual Hahn II, the matrix $U$ is again of order
$(2N+1)\times(2N+1)$ with matrix elements

$\displaystyle
U_{2n,x}=U_{2n,2N-x}=\frac{1}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\gamma,\delta,N),\qquad
x=0,\ldots,N-1,$ $\displaystyle
U_{2n+1,x}=-U_{2n+1,2N-x}=-\frac{1}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\gamma,\delta,N-1),\qquad
x=0,\ldots,N-1,$ $\displaystyle
U_{2n,N}=\tilde{R}_{n}(\lambda(N);\gamma,\delta,N),\qquad U_{2n+1,N}=0,$
(3.21)

where the row indices are as in (3.17). The orthogonality relation of the dual
Hahn polynomials and the signs in the matrix $U$ imply that its rows are
orthonormal, so $U^{T}U=UU^{T}=I$. The pair of recurrence relations for dual
Hahn II of Theorem 1 yield

######  Proposition 3 (dual Hahn II).

Suppose $\gamma>-1$, $\delta>-1$. Let $M$ be a tridiagonal
$(2N+1)\times(2N+1)$-matrix of the form (3.18) with

$\displaystyle M_{2k}=\sqrt{(N+\delta-k)(N-k)},\qquad
M_{2k+1}=\sqrt{(k+1)(k+\gamma+1)},$ (3.22)

and $U$ the orthogonal matrix determined in (3.21). Then the columns of $U$
are the eigenvectors of $M$, i.e., $MU=UD$, where $D$ is a diagonal matrix
containing the eigenvalues of $M$

$\displaystyle
D=\operatorname{diag}(-\epsilon_{N},\ldots,-\epsilon_{1},0,\epsilon_{1},\ldots,\epsilon_{N}),$
$\displaystyle\epsilon_{k}=\sqrt{k(\gamma+\delta+1+2N-k)},\qquad
k=1,\ldots,N.$

Note that the order in which the normalized dual Hahn polynomials appear in
the matrix $U$ is different for (3.17) and (3.21). This is related to the
indices of the polynomials in the relations of Theorem 1.

Finally, for the case dual Hahn III, the matrix $U$ is given by (2.18), (2.19)
and we recapitulate the results given at the end of the previous section, now
in terms of the dual Hahn parameters $\gamma$ and $\delta$.

######  Proposition 4 (dual Hahn III).

Suppose $\gamma>-1$, $\delta>-1$ or $\gamma<-N-1$, $\delta<-N-1$. Let $M$ be
the tridiagonal matrix (2.14) with

$\displaystyle M_{2k}=\sqrt{(k+\gamma+1)(N+\delta+1-k)},\qquad
M_{2k+1}=\sqrt{(k+1)(N-k)},$ (3.23)

and $U$ the orthogonal matrix determined in (2.18), (2.19). Then the columns
of $U$ are the eigenvectors of $M$, i.e., $MU=UD$, where $D$ is a diagonal
matrix containing the eigenvalues of $M$

$\displaystyle
D=\operatorname{diag}(-\epsilon_{N},\ldots,-\epsilon_{1},-\epsilon_{0},\epsilon_{0},\epsilon_{1},\ldots,\epsilon_{N}),$
$\displaystyle\epsilon_{k}=\sqrt{(k+\gamma+1)(k+\delta+1)},\qquad
k=0,1,\ldots,N.$

To conclude for dual Hahn polynomials: there are three sets of recurrence
relations of the form (3.1), (3.2). Each of the three cases gives rise to a
two-diagonal matrix with simple and explicit eigenvalues, and eigenvectors
given in terms of two sets of dual Hahn polynomials.

##  4 Doubling Hahn polynomials

The technique presented in the previous section can be applied to other types
of discrete orthogonal polynomials with a finite spectrum. We have done this
for Hahn polynomials. One level up in the hierarchy of orthogonal polynomials
of hypergeometric type are the Racah polynomials. Also for Racah polynomials
we have applied the technique, but here the description of the results becomes
very technical. So we shall leave the results for Racah polynomials for
Appendix A.

For Hahn polynomials the analysis is again straightforward but tedious, so let
us skip the details of the computation and present just the final outcome
here. Applying the technique described in (3.3)–(3.15), with
$y_{n}=Q_{n}(x;\alpha,\beta,N)$ and
$\hat{y}_{n}=Q_{n}(\hat{x};\hat{\alpha},\hat{\beta},\hat{N})$ yields the
following result.

######  Theorem 5.

The only way to combine two sets of Hahn polynomials such that they satisfy a
pair of recurrence relations of the form (3.3), (3.4) is one of the four
cases:
Hahn I, $Q_{n}(x)\equiv Q_{n}(x;\alpha,\beta,N)$ and $\hat{Q}_{n}(x)\equiv
Q_{n}(x;\alpha+1,\beta,N)$:

$\displaystyle\frac{(n+\alpha+\beta+N+2)}{(2n+\alpha+\beta+2)}Q_{n}(x)-\frac{(N-n)}{(2n+\alpha+\beta+2)}Q_{n+1}(x)=\frac{(\alpha+x+1)}{(\alpha+1)}\hat{Q}_{n}(x),$
$\displaystyle-\frac{(n+1)(n+\beta+1)}{(2n+\alpha+\beta+3)}\hat{Q}_{n}(x)+\frac{(n+\alpha+\beta+2)(n+\alpha+2)}{(2n+\alpha+\beta+3)}\hat{Q}_{n+1}(x)=(\alpha+1)Q_{n+1}(x).$

Hahn II, $Q_{n}(x)\equiv Q_{n}(x;\alpha,\beta,N)$ and $\hat{Q}_{n}(x)\equiv
Q_{n}(x-1;\alpha+1,\beta,N-1)$:

$\displaystyle\frac{1}{(2n+\alpha+\beta+2)}Q_{n}(x)-\frac{1}{(2n+\alpha+\beta+2)}Q_{n+1}(x)=\frac{x}{N(\alpha+1)}\hat{Q}_{n}(x),$
$\displaystyle-\frac{(n+1)(n+\beta+1)(n+\alpha+\beta+N+2)}{(2n+\alpha+\beta+3)}\hat{Q}_{n}(x)$
$\displaystyle\qquad{}+\frac{(n+\alpha+\beta+2)(N-n-1)(n+\alpha+2)}{(2n+\alpha+\beta+3)}\hat{Q}_{n+1}(x)=N(\alpha+1)Q_{n+1}(x).$

Hahn III, $Q_{n}(x)\equiv Q_{n}(x;\alpha,\beta,N)$ and $\hat{Q}_{n}(x)\equiv
Q_{n}(x;\alpha,\beta+1,N)$:

$\displaystyle\frac{(n+\beta+1)(n+N+2+\alpha+\beta)}{(2n+\alpha+\beta+2)}Q_{n}(x)+\frac{(N-n)(n+\alpha+1)}{(2n+\alpha+\beta+2)}Q_{n+1}(x)$
$\displaystyle\qquad{}=(\beta+1+N-x)\hat{Q}_{n}(x),$
$\displaystyle\frac{(n+1)}{(2n+\alpha+\beta+3)}\hat{Q}_{n}(x)+\frac{(n+\alpha+\beta+2)}{(2n+\alpha+\beta+3)}\hat{Q}_{n+1}(x)=Q_{n+1}(x).$

Hahn IV, $Q_{n}(x)\equiv Q_{n}(x;\alpha,\beta,N)$ and $\hat{Q}_{n}(x)\equiv
Q_{n}(x;\alpha,\beta+1,N-1)$:

$\displaystyle\frac{(n+\beta+1)}{(2n+\alpha+\beta+2)}Q_{n}(x)+\frac{(n+\alpha+1)}{(2n+\alpha+\beta+2)}Q_{n+1}(x)=\frac{(N-x)}{N}\hat{Q}_{n}(x),$
$\displaystyle\frac{(n+1)(n+\alpha+\beta+N+2)}{(2n+\alpha+\beta+3)}\hat{Q}_{n}(x)+\frac{(N-n-1)(n+\alpha+\beta+2)}{(2n+\alpha+\beta+3)}\hat{Q}_{n+1}(x)=NQ_{n+1}(x).$

Note that when interchanging $x$ and $n$ the relations in Hahn II coincide
with the known forward and backward shift operator relations for dual Hahn
polynomials [19, equations (9.6.6) and (9.6.8)]. In the same way, the other
cases yield new forward and backward shift operator relations for dual Hahn
polynomials.

Since the recurrence relations are of the form (3.3), (3.4), they can be cast
in matrix form with a two-diagonal matrix. We shall write the matrix elements
again in terms of normalized polynomials. For the case Hahn I, the matrix $U$
of order $(2N+2)\times(2N+2)$, with elements

$\displaystyle
U_{2n,N-x}=U_{2n,N+x+1}=\frac{(-1)^{n}}{\sqrt{2}}\tilde{Q}_{n}(x;\alpha,\beta,N),$
$\displaystyle
U_{2n+1,N-x}=-U_{2n+1,N+x+1}=-\frac{(-1)^{n}}{\sqrt{2}}\tilde{Q}_{n}(x;\alpha+1,\beta,N)$
(4.1)

where $x,n\in\\{0,1,\ldots,N\\}$, is orthogonal, and the recurrence relations
yield

######  Proposition 6 (Hahn I).

Suppose that $\gamma,\delta>-1$. Let $M$ be a tridiagonal
$(2N+2)\times(2N+2)$-matrix of the form (2.14) with

$\displaystyle
M_{2k}=\sqrt{\frac{(k+\alpha+1)(k+\alpha+\beta+1)(k+\alpha+\beta+2+N)}{(2k+\alpha+\beta+1)(2k+\alpha+\beta+2)}},$
$\displaystyle
M_{2k+1}=\sqrt{\frac{(k+\beta+1)(k+1)(N-k)}{(2k+\alpha+\beta+2)(2k+\alpha+\beta+3)}},$

and $U$ the orthogonal matrix determined in (4.1). Then the columns of $U$ are
the eigenvectors of $M$, i.e., $MU=UD$, where $D$ is a diagonal matrix
containing the eigenvalues of $M$

$\displaystyle
D=\operatorname{diag}(-\epsilon_{N},\ldots,-\epsilon_{1},-\epsilon_{0},\epsilon_{0},\epsilon_{1},\ldots,\epsilon_{N}),$
$\displaystyle\epsilon_{k}=\sqrt{k+\alpha+1},\qquad k=0,1,\ldots,N.$ (4.2)

For the case Hahn II, the orthogonal matrix $U$ is of order
$(2N+1)\times(2N+1)$, with elements

$\displaystyle
U_{2n,N-x}=U_{2n,N+x}=\frac{(-1)^{n}}{\sqrt{2}}\tilde{Q}_{n}(x;\alpha,\beta,N),\qquad
x=1,\ldots,N,$ $\displaystyle
U_{2n+1,N-x}=-U_{2n+1,N+x}=-\frac{(-1)^{n}}{\sqrt{2}}\tilde{Q}_{n}(x-1;\alpha+1,\beta,N-1),\qquad
x=1,\ldots,N,$ (4.3) $\displaystyle
U_{2n,N}=(-1)^{n}\tilde{Q}_{n}(0;\alpha,\beta,N),\qquad U_{2n+1,N}=0,$

where the row indices are as in (3.17). The recurrence relations for Hahn II
yield

######  Proposition 7 (Hahn II).

Suppose that $\alpha,\beta>-1$ or $\alpha,\beta<-N$. Let $M$ be a tridiagonal
$(2N+1)\times(2N+1)$-matrix of the form (3.18) with

$\displaystyle
M_{2k}=\sqrt{\frac{(k+\alpha+1)(k+\alpha+\beta+1)(N-k)}{(2k+\alpha+\beta+1)(2k+\alpha+\beta+2)}},$
$\displaystyle
M_{2k+1}=\sqrt{\frac{(k+\beta+1)(k+\alpha+\beta+2+N)(k+1)}{(2k+\alpha+\beta+2)(2k+\alpha+\beta+3)}},$

and $U$ the orthogonal matrix determined in (4.3). Then the columns of $U$ are
the eigenvectors of $M$, i.e., $MU=UD$, where $D$ is a diagonal matrix
containing the eigenvalues of $M$:

$\displaystyle
D=\operatorname{diag}(-\epsilon_{N},\ldots,-\epsilon_{1},0,\epsilon_{1},\ldots,\epsilon_{N}),\qquad\epsilon_{k}=\sqrt{k},\qquad
k=1,\ldots,N.$

Note that for both cases, the two-diagonal matrix $M$ becomes more complicated
compared to the cases for dual Hahn polynomials, but the matrix $D$ of
eigenvalues becomes simpler.

For the two remaining cases we need not give all details: the matrix $M$ for
the case Hahn III is equal to the matrix $M$ for the case Hahn I with the
replacement $\alpha\leftrightarrow\beta$, and so its eigenvalues are
$\pm\sqrt{k+\beta+1}$, $k=0,1,\ldots,N$. And the matrix $M$ for the case Hahn
IV is equal to the matrix $M$ for the case Hahn II with the same replacement
$\alpha\leftrightarrow\beta$, so its eigenvalues are $0$ and $\pm\sqrt{k}$,
$k=1,\ldots,N$.

##  5 Polynomial systems, Christoffel and Geronimus transforms

So far, we have only partially explained why the technique in the previous
sections is referred to as “doubling” polynomials. It is indeed a fact that
the combination of two sets of polynomials, each with different parameters,
yields a new set of orthogonal polynomials. This can be compared to the well
known situation of combining two sets of generalized Laguerre polynomials
(both with different parameters $\alpha$ and $\alpha-1$) into the set of
“generalized Hermite polynomials” [8]. There, for $\alpha>0$, one defines

$\displaystyle
P_{2n}(x)=\sqrt{\frac{n!}{(\alpha)_{n}}}L_{n}^{(\alpha-1)}\big{(}x^{2}\big{)},\qquad
P_{2n+1}(x)=\sqrt{\frac{n!}{(\alpha)_{n+1}}}xL_{n}^{(\alpha)}\big{(}x^{2}\big{)}.$
(5.1)

Then the orthogonality relation of Laguerre polynomials leads to the
orthogonality of the polynomials (5.1):

$\displaystyle\int_{-\infty}^{+\infty}w(x)P_{n}(x)P_{n^{\prime}}(x)dx=\Gamma(\alpha)\delta_{n,n^{\prime}},$

where

$\displaystyle w(x)=e^{-x^{2}}|x|^{2\alpha-1}.$ (5.2)

Note that the even polynomials are Laguerre polynomials in $x^{2}$ (for
parameter $\alpha-1$), and the odd polynomials are Laguerre polynomials in
$x^{2}$ (for parameter $\alpha$) multiplied by a factor $x$. The weight
function (5.2) is common for both types of polynomials. It is this phenomenon
that appears here too in our doubling process of Hahn or dual Hahn
polynomials.

From a more general point of view, this fits in the context of obtaining a new
family of orthogonal polynomials starting from a set of orthogonal polynomials
and its kernel partner related by a Christoffel transform [8, 22, 32]. In a
way, our classification determines for which Christoffel parameter $\nu$ (see
[32] for the notation) the Christoffel transform of a Hahn, dual Hahn or Racah
polynomial is again a Hahn, dual Hahn or Racah polynomial with possibly
different parameters. This determines moreover quite explicitly the common
weight function.

For a dual Hahn polynomial $R_{n}(x)\equiv R_{n}(\lambda(x);\gamma,\delta,N)$,
with data given in (2.9), and a Christoffel parameter $\nu$ the kernel partner
is given by the transform

$\displaystyle
P_{n}(x)=\frac{R_{n+1}(x)-a_{n}R_{n}(x)}{\Lambda(x)-\Lambda(\nu)},\qquad
a_{n}=\frac{R_{n+1}(\nu)}{R_{n}(\nu)}.$ (5.3)

Because of the recurrence relation (2.4) and what is called the Geronimus
transform the original polynomials can also be expressed in terms of the
kernel partners. This is usually done for monic polynomials (see [32,
equations (3.2) and (3.3)]), but it can be extended to non-monic dual Hahn
polynomials as follows

$\displaystyle R_{n}(x)=A(n)P_{n}(x)-b_{n}P_{n-1}(x)$ (5.4)

where the coefficients $b_{n}$ are related to the recurrence relation (2.4) as
follows

$\displaystyle b_{n}a_{n-1}=C(n),\qquad
A(n)a_{n}+b_{n}=A(n)+C(n)+\Lambda(\nu).$ (5.5)

Our classification now shows that only for $\nu$ equal to one of the values
$0$, $N$ or $-\delta$, the kernel partner $P_{n}(x)$ will again be a dual Hahn
polynomial. Indeed, taking for example $\nu=0$ in (5.3) we have $R_{n}(0)=1$
and

$\displaystyle
P_{n}(x)=\frac{R_{n+1}(x)-R_{n}(x)}{\Lambda(x)}=\frac{-1}{N(\gamma+1)}R_{n}(\lambda(x-1);{\gamma+1},{\delta+1},{N-1}),$

where we used the first relation of dual Hahn I to obtain again a dual Hahn
polynomial. The reverse transform (5.4) follows immediately from the second
relation of dual Hahn I. Similarly, taking $\nu=N$ in (5.3) we have
$R_{n}(N)={(-N-\delta)_{n}}/{(\gamma+1)_{n}}$ and

$\displaystyle
P_{n}(x)=\frac{R_{n+1}(x)-R_{n}(x)(n-\delta-N)/(n+\gamma+1)}{(x-N)(x+N+\gamma+\delta+1)}=\frac{-1}{N(n+\gamma+1)}R_{n}(\lambda(x);\gamma,\delta,N-1),$

which we obtained using the first relation of dual Hahn II. For the reverse
transform (5.4) we find, using the second relation of dual Hahn II with
shifted $n\mapsto n-1$,

$\displaystyle
A(n)P_{n}(x)-b_{n}P_{n-1}(x)=\frac{-(n-N)}{N}R_{n}(\lambda(x);\gamma,\delta,N-1)+\frac{n}{N}R_{n-1}(\lambda(x);\gamma,\delta,N-1)$
$\displaystyle\hphantom{A(n)P_{n}(x)-b_{n}P_{n-1}(x)}{}=R_{n}(x).$

For the last case, taking $\nu=-\delta$ in (5.3) we have
$R_{n}(-\delta)={(-N-\delta)_{n}}/{(-N)_{n}}$ and

$\displaystyle
P_{n}(x)=\frac{R_{n+1}(x)-R_{n}(x)(n-\delta-N)/(n-N)}{(x+\gamma+1)(x+\delta)}$
$\displaystyle\hphantom{P_{n}(x)}{}=\frac{1}{(\gamma+1)(n-N)}R_{n}(\lambda(x);\gamma+1,\delta-1,N),$

which we obtained using the first relation of dual Hahn III. For the transform
(5.4) we have

$\displaystyle
A(n)P_{n}(x)-b_{n}P_{n-1}(x)=\frac{n+\gamma+1}{\gamma+1}R_{n}(\lambda(x);\gamma+1,\delta-1,N-1)$
$\displaystyle\hphantom{A(n)P_{n}(x)-b_{n}P_{n-1}(x)=}{}-\frac{n}{\gamma+1}R_{n-1}(\lambda(x);\gamma+1,\delta-1,N),$

which equals $R_{n}(x)$ by the second relation of dual Hahn III.

In a similar way, for the Hahn polynomials, putting $Q_{n}(x)\equiv
Q_{n}(x;a,b,N)$, using the data (2.5) in

$\displaystyle
P_{n}(x)=\frac{Q_{n+1}(x)-a_{n}Q_{n}(x)}{\Lambda(x)-\Lambda(\nu)},\qquad
a_{n}=\frac{Q_{n+1}(\nu)}{Q_{n}(\nu)},$

and in (5.4), (5.5), the cases Hahn I, II, III, V correspond respectively to
the choices $-\alpha-1$, $0$, $N+\beta+1$ and $N$ for $\nu$.

The task of determining for which Christoffel parameter $\nu$ the kernel
partner of a dual Hahn polynomial is again of the same family is not trivial.
It comes down to finding a pair of recurrence relations of the form (3.1),
(3.2) with coefficients related to $\nu$ as in (5.3). We have classified these
for general coefficients, without a relation to $\nu$, and we observe that
each solution indeed corresponds to a specific choice for $\nu$.

The transforms (5.3), (5.4) give rise to new orthogonal systems, but in
general there is no way of writing the common weight function. However, since
here both sets are of the same family, we can actually do this. Let us begin
with the dual Hahn polynomials, in particular the case dual Hahn I, for which
the corresponding matrix $U$ is given in (3.17). They give rise to a new
family of discrete orthogonal polynomials with the relation $MU=UD$
corresponding to their three term recurrence relation with Jacobi matrix $M$
(3.19). In general the support of the weight function is equal to the spectrum
of the Jacobi matrix [5, 18, 20, 21]. After simplifying with the normalization
factors (2.8), this leads to a discrete orthogonality of polynomials, with
support equal to the eigenvalues of $M$ (so in this case, the support follows
from (3.20)). Concretely, for the case under consideration, we have

######  Proposition 8.

Let $\gamma>-1$, $\delta>-1$, and consider the $2N+1$ polynomials

$\displaystyle{P}_{2n}(q)=\frac{(-1)^{n}}{\sqrt{2}}{R}_{n}\big{(}q^{2};\gamma,\delta,N\big{)},\qquad
n=0,1,\ldots,N,$ $\displaystyle
P_{2n+1}(q)=-\frac{(-1)^{n}}{\sqrt{2}}\frac{\sqrt{(n+\gamma+1)(N-n)}}{(\gamma+1)N}q{R}_{n}\big{(}q^{2}-\gamma-\delta-2;\gamma+1,\delta+1,N-1\big{)},$
$\displaystyle\hphantom{P_{2n+1}(q)=}{}n=0,1,\ldots,N-1.$

These polynomials satisfy the discrete orthogonality relation

$\displaystyle\sum_{q\in
S}\frac{(-1)^{k}(2k+\gamma+\delta+1)(\gamma+1)_{k}(-N)_{k}N!}{(k+\gamma+\delta+1)_{N+1}(\delta+1)_{k}k!}(1+\delta_{q,0})P_{n}(q)P_{n^{\prime}}(q)$
$\displaystyle\qquad{}=\left[\binom{\gamma+\lfloor n/2\rfloor}{\lfloor
n/2\rfloor}\binom{\delta+N-\lfloor n/2\rfloor}{N-\lfloor
n/2\rfloor}\right]^{-1}\delta_{n,n^{\prime}}$ (5.6)

with

$\displaystyle S=\big{\\{}0,\pm\sqrt{k(k+\gamma+\delta+1)},\
k=1,2,\ldots,N\big{\\}}.$

Note that for $q\in S$, $q^{2}=k(k+\gamma+\delta+1)\equiv\lambda(k)$, and the
polynomial $P_{2n}(q)$ is of the form $R_{n}(\lambda(k);\gamma,\delta,N)$. In
that case,
$q^{2}-\gamma-\delta-2=(k-1)((k-1)+(\gamma+1)+(\delta+1)+1)\equiv\lambda(k-1)$,
so the polynomial $P_{2n+1}(q)$ is of the form
$R_{n}(\hat{\lambda}(k-1);\gamma+1,\delta+1,N-1)$. The interpretation of the
weight function in the left hand side of (5.6) is as follows: each $q$ in the
support $S$ is mapped to a $k$-value belonging to $\\{0,1,\ldots,N\\}$, and
then the weight depends on this $k$-value.

Now we turn to the classification of Section 4, where the corresponding
orthogonal matrices $U$ are given in terms of (normalized) Hahn polynomials.
for the case Hahn I, the matrix $U$ is given in (4.1), and the spectrum of the
matrix $M$ is given by (4.2). After simplifying the normalization factors, the
orthogonality of the rows of $U$ gives rise to

######  Proposition 9.

Let $\alpha>-1$, $\beta>-1$, and consider the $2N+2$ polynomials,
$n=0,1,\ldots,N$,

$\displaystyle{P}_{2n}(q)=\frac{(-1)^{n}}{\sqrt{2}}{Q}_{n}\big{(}q^{2}-\alpha-1;\alpha,\beta,N\big{)},$
$\displaystyle
P_{2n+1}(q)=-\frac{(-1)^{n}}{\sqrt{2}}\frac{1}{(\alpha+1)}\sqrt{\frac{(n+\alpha+1)(n+\alpha+\beta+1)(2n+2+\alpha+\beta)}{(n+N+\alpha+\beta+2)(2n+\alpha+\beta+1)}}$
$\displaystyle\hphantom{P_{2n+1}(q)=}{}\times
q{Q}_{n}\big{(}q^{2}-\alpha-1;\alpha+1,\beta,N\big{)}.$

These polynomials satisfy the discrete orthogonality relation

$\displaystyle\sum_{q\in
S}\binom{q^{2}-1}{q^{2}-\alpha-1}\binom{N-q^{2}+\alpha+\beta+1}{N-q^{2}+\alpha+1}P_{n}(q)P_{n^{\prime}}(q)=h_{\lfloor
n/2\rfloor}(\alpha,\beta,N)\beta_{n,n^{\prime}}$

with

$\displaystyle
S=\big{\\{}{-}\sqrt{N+\alpha+1},-\sqrt{N+\alpha},\ldots,-\sqrt{\alpha+1},\sqrt{\alpha+1},\ldots,\sqrt{N+\alpha},\sqrt{N+\alpha+1}\big{\\}}$

and

$\displaystyle
h_{n}(\alpha,\beta,N)=\frac{(-1)^{n}(n+\alpha+\beta+1)_{N+1}(\beta+1)_{n}n!}{(2n+\alpha+\beta+1)(\alpha+1)_{n}(-N)_{n}N!}.$

So $P_{n}(q)$ is a polynomial of degree $n$ in the variable $q$, of different
type (with different parameters when expressed as a Hahn polynomial) depending
on whether $n$ is even or $n$ is odd. The support points of the discrete
orthogonality are given by

$\displaystyle q=\pm\sqrt{k+\alpha+1},\qquad k=0,\dots,N.$

In the same way, the dual orthogonality for the case Hahn II gives rise to

######  Proposition 10.

Let $\alpha>-1$, $\beta>-1$, and consider the $2N+1$ polynomials

$\displaystyle{P}_{2n}(q)=\frac{(-1)^{n}}{\sqrt{2}}{Q}_{n}\big{(}q^{2};\alpha,\beta,N\big{)},\qquad
n=0,1,\ldots,N,$ $\displaystyle
P_{2n+1}(q)=-\frac{(-1)^{n}}{\sqrt{2}}\frac{1}{(\alpha+1)N}\sqrt{\frac{(N-n)(n+\alpha+1)(n+\alpha+\beta+1)(2n+\alpha+\beta+2)}{(2n+\alpha+\beta+1)}}$
$\displaystyle\hphantom{P_{2n+1}(q)=}{}\times
q{Q}_{n}\big{(}q^{2}-1;\alpha+1,\beta,N-1\big{)},\qquad n=0,1,\ldots,N-1.$

These polynomials satisfy the discrete orthogonality relation

$\displaystyle\sum_{q\in
S}\binom{q^{2}+\alpha}{q^{2}}\binom{N-q^{2}+\beta}{N-q^{2}}(1+\delta_{q,0})P_{n}(q)P_{n^{\prime}}(q)=h_{\lfloor
n/2\rfloor}(\alpha,\beta,N)\beta_{n,n^{\prime}}$

with

$\displaystyle
S=\big{\\{}{-}\sqrt{N},-\sqrt{N-1},\ldots,-1,0,1,\ldots,\sqrt{N-1},\sqrt{N}\big{\\}}$

and

$\displaystyle
h_{n}(\alpha,\beta,N)=\frac{(-1)^{n}(n+\alpha+\beta+1)_{N+1}(\beta+1)_{n}n!}{(2n+\alpha+\beta+1)(\alpha+1)_{n}(-N)_{n}N!}.$

The ideas described in the three propositions of this section should be clear.
It would lead us too far to give also the explicit forms corresponding to the
remaining cases. Let us just mention that also for these cases the support of
the new polynomials coincides with the spectrum of the corresponding two-
diagonal matrix $M$.

##  6 First application: eigenvalue test matrices

In Sections 3 and 4 we have encountered a number of symmetric two-diagonal
matrices $M$ with explicit expressions for the eigenvectors and eigenvalues.
In general, if one considers a two-diagonal matrix $A$ of size
$(m+2)\times(m+2)$,

$\displaystyle A=\left(\begin{matrix}0&b_{0}&0&&\\\ c_{0}&0&b_{1}&\ddots&\\\
0&c_{1}&0&\ddots&0\\\ &\ddots&\ddots&\ddots&b_{m}\\\
&&0&c_{m}&0\end{matrix}\right),$ (6.1)

then it is clear that the characteristic polynomial depends on the products
$b_{i}c_{i}$, $i=0,\ldots,m$, only, and not on $b_{i}$ and $c_{i}$ separately.
So the same holds for the eigenvalues. Therefore, if all matrix elements
$b_{i}$ and $c_{i}$ are positive, the eigenvalues of $A$ or of the related
symmetric matrix

$\displaystyle A^{\prime}=\left(\begin{matrix}0&\sqrt{b_{0}c_{0}}&0&&\\\
\sqrt{b_{0}c_{0}}&0&\sqrt{b_{1}c_{1}}&\ddots&\\\
0&\sqrt{b_{1}c_{1}}&0&\ddots&0\\\ &\ddots&\ddots&\ddots&\sqrt{b_{m}c_{m}}\\\
&&0&\sqrt{b_{m}c_{m}}&0\end{matrix}\right)$

are the same. The eigenvectors of $A^{\prime}$ are those of $A$ after
multiplication by a diagonal matrix (the diagonal matrix that is used in the
similarity transformation from $A$ to $A^{\prime}$).

For matrices of type (6.1), it is sufficient to denote them by their
superdiagonal $[\mathbf{b}]=[b_{0},\ldots,b_{m}]$ and their subdiagonal
$[\mathbf{c}]=[c_{0},\ldots,c_{m}]$. So the Sylvester–Kac matrix from the
introduction is denoted by

$\displaystyle[\mathbf{b}]=[1,2,\ldots,N],\qquad[\mathbf{c}]=[N,\ldots,2,1],$

with eigenvalues given by (1.2).

The importance of the Sylvester–Kac matrix as a test matrix for numerical
eigenvalue routines has already been emphasized in the Introduction. In this
context, it is also significant that the matrix itself has integer entries
only (so there is no rounding error when represented on a digital computer),
and that also the eigenvalues are integers. Of course, matrices with rational
numbers as entries suffice as well, since one can always multiply the matrix
by an appropriate integer factor.

Let us now systematically consider the two-diagonal matrices encountered in
the classification process of doubling Hahn or dual Hahn polynomials. For the
matrix (3.18) of the dual Hahn I case, the corresponding non-symmetric form
can be chosen as the two-diagonal matrix with

$\displaystyle[\mathbf{b}]=[\gamma+1,1,\gamma+2,2,\ldots,\gamma+N,N],$
$\displaystyle[\mathbf{c}]=[N,N+\delta,N-1,N-1+\delta,\ldots,1,\delta+1].$
(6.2)

The eigenvalues are determined by Proposition 2 and given by $0$,
$\pm\sqrt{k(k+\gamma+\delta+1)}$, $k=1,\ldots,N$. This is (up to a factor 2)
the matrix (1.3) mentioned in the Introduction. As test matrix, the choice
$\gamma+\delta+1=0$ (leaving one free parameter) is interesting as it gives
rise to integer eigenvalues. In Proposition 2 there is the initial condition
$\gamma>-1$, $\delta>-1$. Clearly, if one is only dealing with eigenvalues,
the condition for (6.2) is just $\gamma+\delta+2\geq 0$. And when one
substitutes $\delta=-\gamma-1$ in (6.2), there is no condition at all for the
one-parameter family of matrices of the form (6.2).

For the dual Hahn II case, the matrix (3.22) is given in Proposition 3, and
its non-symmetric form can be taken as

$\displaystyle[\mathbf{b}]=[\gamma+N,1,\gamma+N-1,2,\ldots,\gamma+1,N],$
$\displaystyle[\mathbf{c}]=[N,\delta+1,N-1,\delta+2,\ldots,1,\delta+N].$ (6.3)

The eigenvalues are given by $0$, $\pm\sqrt{k(\gamma+\delta+1+2N-k)}$,
$k=1,\ldots,N$. There is no simple substitution that reduces these eigenvalues
to integers.

For the dual Hahn III case, the matrix (2.15) is given in Proposition 4, and
its simplest non-symmetric form is

$\displaystyle[\mathbf{b}]=[\gamma+1,1,\gamma+2,2,\ldots,\gamma+N,N,\gamma+N+1],$
$\displaystyle[\mathbf{c}]=[\delta+N+1,N,\delta+N,N-1,\ldots,\delta+2,1,\delta+1].$
(6.4)

The eigenvalues are given by (2.17), i.e.,
$\pm\sqrt{(\gamma+k+1)(\delta+k+1)}$, $k=0,\ldots,N$. Up to a factor 2, this
is the third matrix mentioned in the Introduction. The substitution
$\delta=\gamma$ leads to a one-parameter family of two-diagonal matrices with
square-free eigenvalues. And in particular when moreover $\gamma$ is integer,
all matrix entries and all eigenvalues are integers.

The two-diagonal matrices arising from the Hahn doubles or the Racah doubles
can also be written in a square-free form of type (6.1). However, for these
cases the entries in the two-diagonal matrices $M$ are already quite involved
(see, e.g., Propositions 6, 7, 12 or 13), and we shall not discuss them
further in this context. The three examples given here, (6.2)–(6.4), are
already sufficiently interesting as extensions of the Sylvester–Kac matrix as
potential eigenvalue test matrices.

##  7 Further applications: related algebraic structures
and finite oscillator models

The original example of a (dual) Hahn double, described here in Section 2, was
encountered in the context of a finite oscillator model [14]. In that context,
there is also a related algebraic structure. In particular, the two-diagonal
matrices $M$ of the form (2.14) or (3.18) are interpreted as representation
matrices of an algebra, which can be seen as a deformation of the Lie algebra
$\mathfrak{su}(2)$. Once an algebraic formulation is clear, this structure can
be used to model a finite oscillator. The close relationship comes from the
fact that for the corresponding finite oscillator model the spectrum of the
position operator coincides with the spectrum of the matrix $M$.

Therefore, it is worthwhile to examine the algebraic structures behind the
current matrices $M$. We shall do this explicitly for the three double dual
Hahn cases.

For the case dual Hahn I, we return to the form of the matrix $M$ given in
(3.18) or (3.19). For any positive integer $N$, let $J_{+}$ denote the lower-
triangular tridiagonal $(2N+1)\times(2N+1)$ matrix given below, and let
$J_{-}$ be its transpose

$\displaystyle J_{+}=2\left(\begin{matrix}0&0&&&\\\ M_{0}&0&0&&\\\
0&M_{1}&0&0&\\\ &0&M_{2}&0&\ddots\\\
&&\ddots&\ddots&\ddots\end{matrix}\right),\qquad J_{-}=J_{+}^{\dagger}.$ (7.1)

Let us also define the common diagonal matrix

$\displaystyle J_{0}=\operatorname{diag}(-N,-N+1,\ldots,N),$ (7.2)

and the “parity matrix”

$\displaystyle P=\operatorname{diag}(1,-1,1,-1,\ldots).$ (7.3)

Then it is easy to check that these matrices satisfy the following relations
(as usual, $I$ denotes the identity matrix)

$\displaystyle P^{2}=1,\qquad PJ_{0}=J_{0}P,\qquad PJ_{\pm}=-J_{\pm}P,$
$\displaystyle[J_{0},J_{\pm}]=\pm J_{\pm},$
$\displaystyle[J_{+},J_{-}]=2J_{0}+2(\gamma+\delta+1)J_{0}P-(2N+1)(\gamma-\delta)P+(\gamma-\delta)I.$
(7.4)

Especially the last equation is interesting. From the algebraic point of view,
it introduces some two-parameter deformation or extension of
$\mathfrak{su}(2)$. When $\gamma=\delta=-1/2$, the equations coincide with the
$\mathfrak{su}(2)$ relations. Another important case is when
$\delta=-\gamma-1$, leaving a one-parameter extension of $\mathfrak{su}(2)$
without quadratic terms.

For the case dual Hahn II, the corresponding expressions of $J_{+}$, $J_{-}$,
$J_{0}$ and $P$ are the same as above in (7.1)–(7.3), but with $M_{k}$-values
given by (3.22). As far as the algebraic relations are concerned, they are
also given by (7.4) but with the last relation replaced by

$\displaystyle[J_{+},J_{-}]=-2J_{0}+2(\gamma+\delta+2N+1)J_{0}P+(2N+1)(\gamma-\delta)P-(\gamma-\delta)I.$

For the case dual Hahn III, the size of the matrices changes to
$(2N+2)\times(2N+2)$. For $J_{+}$ and $J_{-}$ one can use (7.1), with
$M_{k}$-values given by (3.23). $P$ has the same expression (7.3), but for
$J_{0}$ we need to take

$\displaystyle
J_{0}=\operatorname{diag}\left(-N-\frac{1}{2},-N+\frac{1}{2},\ldots,N+\frac{1}{2}\right).$

With these expressions, the algebraic relations are given by (7.4) but with
the last relation replaced by

$\displaystyle[J_{+},J_{-}]=2J_{0}+2(\gamma-\delta)J_{0}P-((2N+2)(\gamma+\delta+1)+(2\gamma+1)(2\delta+1))P$
$\displaystyle\hphantom{[J_{+},J_{-}]=}{}+(\gamma-\delta)I.$ (7.5)

The structure of these algebras is related to the structure of the so-called
algebra ${\cal H}$ of the dual $-1$ Hahn polynomials, see [11, 31]. It is not
hard to verify that the algebra ${\cal H}$, determined by [11, equations
(3.4)–(3.6)] or [11, equations (6.2)–(6.4)], can be cast in the form (7.4) (or
vice versa). Indeed, starting from the form [11, equations (6.2)–(6.4)] coming
from dual $-1$ Hahn polynomials, we can take

$\displaystyle J_{0}=\widetilde{K_{1}}-\frac{\rho}{4},\qquad
J_{+}=\widetilde{K_{2}}+\widetilde{K_{3}},\qquad
J_{-}=\widetilde{K_{2}}-\widetilde{K_{3}},$

to get the same form as (7.4)

$\displaystyle P^{2}=1,\qquad PJ_{0}=J_{0}P,\qquad PJ_{\pm}=-J_{\pm}P,$
$\displaystyle[J_{0},J_{\pm}]=\pm J_{\pm},\qquad[J_{+},J_{-}]=2J_{0}+2\nu
J_{0}P+\frac{\sigma}{2}P+\frac{\rho}{2}I,$ (7.6)

where $\nu$, $\sigma$, $\rho$ depend on the parameters of the dual $-1$ Hahn
polynomials $\alpha$, $\beta$, $N$ through [11, equations (3.4)–(3.6)]. In our
case, the algebraic relations are the same, but the dependence of the
“structure constants” in (7.6) on the parameters $\gamma$, $\delta$, $N$ of
the dual Hahn polynomials is different.

As far as we can see, the doubling of dual Hahn polynomials as classified in
this paper gives a set of polynomials that is similar but in general not the
same as a set of dual $-1$ Hahn polynomials [31] (except for specific values
of parameters, e.g., $\delta=-\gamma-1$ does coincide with a specific dual
$-1$ Hahn polynomial). For general parameters, the support of the weight
function is different, the recurrence relations (or difference relations) are
different, and the hypergeometric series expression is different.

The algebraic structures obtained here (or special cases thereof) can be of
interest for the construction of finite oscillator models [1, 2, 3, 14]. Two
familiar finite oscillator models fall within this framework: the model
discussed in [14] corresponds to (7.5) with $\delta=\gamma$, and the one
analysed in [15] to (7.4) with $\delta=\gamma$. Observe that there are some
other interesting special values. For example, the case (7.4) with
$\delta=-\gamma-1$ gives rise to an interesting algebra, and in particular
also to a very simple spectrum (3.20). We intend to study the finite
oscillator that is modeled by this case, and study in particular the
corresponding finite Fourier transform; but this will be the topic of a
separate paper.

##  8 Conclusion

We have classified all pairs of recurrence relations for two types of dual
Hahn polynomials (i.e., dual Hahn polynomials with different parameters), and
refer to these as dual Hahn doubles. The analysis is quite straightforward,
and the result is given in Theorem 1, yielding three cases. For each case, we
have given the corresponding symmetric two-diagonal matrix $M$, its matrix of
orthonormal eigenvectors $U$ and its eigenvalues in explicit form. The same
classification has been obtained for Hahn polynomials and Racah polynomials.

The orthogonality of the matrix $U$ gives rise to new sets of orthogonal
polynomials. These sets could in principle also be obtained from, for example,
a set of dual Hahn polynomials and a certain Christoffel transform. In our
approach, the possible cases where such a transform gives rise to a polynomial
of the same type follow naturally, and also the explicit polynomials and their
orthogonality relations arise automatically.

As an interesting secondary outcome, we obtain nice one-parameter and two-
parameter extensions of the Sylvester–Kac matrix with explicit eigenvalue
expressions. Such matrices can be of interest for testing numerical eigenvalue
routines.

The first example of a (dual) Hahn double appeared in a finite oscillator
model [14]. For this model, the Hahn polynomials (or their duals) describe the
discrete position wavefunction of the oscillator, and the two-diagonal matrix
$M$ lies behind an underlying algebraic structure. Here, we have examined the
algebraic relations corresponding to the three dual Hahn cases. It is clear
that the analysis of finite oscillators for some of these cases is worth
pursuing.

##  Appendix A Appendix: doubling Racah polynomials

The technique presented in Sections 3 and 4 is applied here for Racah
polynomials.

Racah polynomials $R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta)$ of degree $n$
($n=0,1,\ldots,N$) in the variable $\lambda(x)=x(x+\gamma+\delta+1)$ are
defined by [13, 19, 23]

$\displaystyle
R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta)={}_{4}F_{3}\left(\genfrac{}{}{0.0pt}{}{-n,n+\alpha+\beta+1,-x,x+\gamma+\delta+1}{\alpha+1,\beta+\delta+1,\gamma+1};1\right),$

where one of the denominator parameters should be $-N$:

$\displaystyle\alpha+1=-N\qquad\hbox{or}\qquad\beta+\delta+1=-N\qquad\hbox{or}\qquad\gamma+1=-N.$
(A.1)

For the (discrete) orthogonality relation (depending on the choice of which
parameter relates to $-N$) we refer to [19, equation (9.2.2)] or [25, Section
18.25]

Racah polynomials satisfy a recurrence relation of the form (2.4) with

$\displaystyle
y_{n}(x)=R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta),\qquad\Lambda(x)=\lambda(x)=x(x+\gamma+\delta+1),$
$\displaystyle
A(n)=\frac{(n+\alpha+1)(n+\alpha+\beta+1)(n+\gamma+1)(n+\beta+\delta+1)}{(2n+\alpha+\beta+1)(2n+\alpha+\beta+2)},$
$\displaystyle
C(n)=\frac{n(n+\alpha+\beta-\gamma)(n+\alpha-\delta)(n+\beta)}{(2n+\alpha+\beta)(2n+\alpha+\beta+1)}.$
(A.2)

We have applied the technique described in (3.3)–(3.15), with
$y_{n}=R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta)$ and
$\hat{y}_{n}=R_{n}(\lambda(\hat{x});\hat{\alpha},\hat{\beta},\hat{\gamma},\hat{\delta})$.
The analysis is again straightforward but tedious, and the final outcome is

######  Theorem 11.

The only way to combine two sets of Racah polynomials such that they satisfy
difference relations of the form (3.3), (3.4) is one of the four cases:
Racah I, $R_{n}(x)\equiv R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta)$ and
$\hat{R}_{n}(x)\equiv R_{n}(\lambda(x);\alpha,\beta+1,\gamma+1,\delta-1)$:

$\displaystyle\frac{(n+\beta+\delta+1)(n+\alpha+1)}{(2n+\alpha+\beta+2)}R_{n+1}(x)-\frac{(n-\delta+\alpha+1)(n+\beta+1)}{(2n+\alpha+\beta+2)}R_{n}(x)$
$\displaystyle\qquad{}=\frac{(x+\delta)(x+\gamma+1)}{\gamma+1}\hat{R}_{n}(x),$
$\displaystyle\frac{(n+\alpha+\beta+2)(n+\gamma+2)}{(2n+\alpha+\beta+3)}\hat{R}_{n+1}(x)-\frac{(n+1)(n-\gamma+\alpha+\beta+1)}{(2n+\alpha+\beta+3)}\hat{R}_{n}(x)$
$\displaystyle\qquad{}=(\gamma+1)R_{n+1}(x).$

Racah II, $R_{n}(x)\equiv R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta)$ and
$\hat{R}_{n}(x)\equiv R_{n}(\lambda(x);\alpha,\beta+1,\gamma,\delta)$:

$\displaystyle\frac{(n+\gamma+1)(n+\alpha+1)}{(2n+\alpha+\beta+2)}R_{n+1}(x)-\frac{(n-\gamma+\alpha+\beta+1)(n+\beta+1)}{(2n+\alpha+\beta+2)}R_{n}(x)$
$\displaystyle\qquad{}=\frac{(x+\beta+\delta+1)(x+\gamma-\beta)}{\beta+\delta+1}\hat{R}_{n}(x),$
$\displaystyle\frac{(n+\beta+\delta+2)(n+\alpha+\beta+2)}{(2n+\alpha+\beta+3)}\hat{R}_{n+1}(x)-\frac{(n+1)(n-\delta+\alpha+1)}{(2n+\alpha+\beta+3)}\hat{R}_{n}(x)$
$\displaystyle\qquad{}=(\beta+\delta+1)R_{n+1}(x).$

Racah III, $R_{n}(x)\equiv R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta)$ and
$\hat{R}_{n}(x)\equiv R_{n}(\lambda(x-1);\alpha+1,\beta,\gamma+1,\delta+1)$:

$\displaystyle\frac{1}{(2n+\alpha+\beta+2)}R_{n+1}(x)-\frac{1}{(2n+\alpha+\beta+2)}R_{n}(x)=\frac{x(x+\gamma+\delta+1)}{(\gamma+1)(\beta+\delta+1)(\alpha+1)}\hat{R}_{n}(x),$
$\displaystyle\frac{(n+\gamma+2)(n+\beta+\delta+2)(n+\alpha+2)(n+\alpha+\beta+2)}{(2n+\alpha+\beta+3)}\hat{R}_{n+1}(x)$
$\displaystyle\qquad\quad{}-\frac{(n+1)(n-\gamma+\alpha+\beta+1)(n-\delta+\alpha+1)(n+\beta+1)}{(2n+\alpha+\beta+3)}\hat{R}_{n}(x)$
$\displaystyle\qquad{}=(\gamma+1)(\beta+\delta+1)(\alpha+1)R_{n+1}(x).$

Racah IV, $R_{n}(x)\equiv R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta)$ and
$\hat{R}_{n}(x)\equiv R_{n}(\lambda(x);\alpha+1,\beta,\gamma,\delta)$:

$\displaystyle\frac{(n+\gamma+1)(n+\beta+\delta+1)}{(2n+\alpha+\beta+2)}R_{n+1}(x)-\frac{(n-\gamma+\alpha+\beta+1)(x-\delta+\alpha+1)}{(2n+\alpha+\beta+2)}R_{n}(x)$
$\displaystyle\qquad{}=\frac{(x+\gamma+\delta-\alpha)(x+\alpha+1)}{(\alpha+1)}\hat{R}_{n}(x),$
$\displaystyle\frac{(n+\alpha+2)(n+\alpha+\beta+2)}{(2n+\alpha+\beta+3)}\hat{R}_{n+1}(x)-\frac{(n+1)(n+\beta+1)}{(2n+\alpha+\beta+3)}\hat{R}_{n}(x)=(\alpha+1)R_{n+1}(x).$

Note that after interchanging $n$ and $x$, and $\alpha\leftrightarrow\gamma$
and $\beta\leftrightarrow\delta$, the relations in Racah III coincide with the
known forward and backward shift operator relations [19, equations (9.2.6) and
(9.2.8)]. The relations in Racah I were already found in [16, equations (5)
and (6)].

In the context of Section 5 it is worth noting that the above relations also
correspond to Christoffel-Genonimus transforms. Taking $R_{n}(x)\equiv
R_{n}(\lambda(x);\alpha,\beta,\gamma,\delta)$ in the relations (5.3)–(5.5),
with data given by (A.2), the above cases Racah I, II, III, IV correspond
respectively to the choices $\nu=-\delta$, $\nu=\beta-\gamma$, $\nu=0$ and
$\nu=-\alpha-1$.

For each of the four cases, one can translate the set of difference relations
to a matrix identity of the form $MU=UD$. In fact, for each of the four cases,
there are three subcases depending on the choice of $-N$ in (A.1). We shall
not give all of these cases: they should be easy to construct for the reader
who needs one. Let us just give an example or two.

Consider the case Racah I with $\alpha+1=-N$. It is convenient to perform the
shift $\delta\rightarrow\delta+1$ in the two difference relations of Theorem
11. The orthogonal matrix $U$ is of order $(2N+2)\times(2N+2)$, with elements

$\displaystyle
U_{2n,N-x}=U_{2n,N+x+1}=\frac{(-1)^{n}}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\alpha,\beta,\gamma,\delta+1),$
$\displaystyle
U_{2n+1,N-x}=-U_{2n+1,N+x+1}=-\frac{(-1)^{n}}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\alpha,\beta+1,\gamma+1,\delta),$
(A.3)

where $\tilde{R}_{n}$ is the notation for a normalized Racah polynomial. Then,
one has

######  Proposition 12.

Suppose that $\gamma,\delta>-1$ and $\beta>N+\gamma$ or $\beta<-N-\delta-1$.
Let $M$ be a tridiagonal $(2N+2)\times(2N+2)$-matrix of the form (2.14) with

$\displaystyle
M_{2k}=\sqrt{\frac{(N-\beta-k)(\gamma+1+k)(N+\delta+1-k)(k+\beta+1)}{(N-\beta-2k)(2k-N+1+\beta)}},$
$\displaystyle
M_{2k+1}=\sqrt{\frac{(\gamma+N-\beta-k)(k+1)(N-k)(k+\beta+\delta+2)}{(N-\beta-2k-2)(2k-N+1+\beta)}},$

and $U$ the orthogonal matrix determined in (A.3). Then the columns of $U$ are
the eigenvectors of $M$, i.e., $MU=UD$, where $D$ is a diagonal matrix
containing the eigenvalues of $M$

$\displaystyle
D=\operatorname{diag}(-\epsilon_{N},\ldots,-\epsilon_{1},-\epsilon_{0},\epsilon_{0},\epsilon_{1},\ldots,\epsilon_{N}),$
$\displaystyle\epsilon_{k}=\sqrt{(k+\gamma+1)(k+\delta+1)},\qquad
k=0,1,\ldots,N.$

As a second example, consider the case Racah III with $\alpha+1=-N$. The
orthogonal matrix $U$ is now of order $(2N+1)\times(2N+1)$, with elements

$\displaystyle
U_{2n,N-x}=U_{2n,N+x}=\frac{(-1)^{n}}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\alpha,\beta,\gamma,\delta),\qquad
n=1,\ldots,N,$ $\displaystyle
U_{2n+1,N-x-1}=-U_{2n+1,N+x+1}=-\frac{(-1)^{n}}{\sqrt{2}}\tilde{R}_{n}(\lambda(x);\alpha+1,\beta,\gamma+1,\delta+1),$
$\displaystyle\hphantom{U_{2n+1,N-x-1}=-U_{2n+1,N+x+1}=}{}n=0,\ldots,N-1,$
$\displaystyle
U_{2n,N}=(-1)^{n}\tilde{R}_{n}(\lambda(0);\alpha,\beta,\gamma,\delta),\qquad
U_{2n+1,N}=0.$ (A.4)

Then, one has

######  Proposition 13.

Suppose that $\gamma,\delta>-1$ and $\beta>N+\gamma$ or $\beta<-N-\delta$. Let
$M$ be a tridiagonal $(2N+1)\times(2N+1)$-matrix of the form (3.18) with

$\displaystyle
M_{2k}=\sqrt{\frac{(k+\gamma+1)(-N+\beta+k)(N-k)(k+\beta+\delta+1)}{(N-\beta-2k)(N-\beta-2k-1)}},$
$\displaystyle
M_{2k+1}=\sqrt{\frac{(\gamma+N-\beta-k)(k+1)(k+\beta+1)(k-\delta-N)}{(N-\beta-2k-2)(N-\beta-2k-1)}},$

and $U$ the orthogonal matrix determined in (A.4). Then the columns of $U$ are
the eigenvectors of $M$, i.e., $MU=UD$, where $D$ is a diagonal matrix
containing the eigenvalues of $M$

$\displaystyle
D=\operatorname{diag}(-\epsilon_{N},\ldots,-\epsilon_{1},0,\epsilon_{1},\ldots,\epsilon_{N}),\qquad\epsilon_{k}=\sqrt{k(k+\gamma+\delta+1)},\qquad
k=1,\ldots,N.$

### Acknowledgements

The authors wish to thank the referees for their insightful remarks and
suggestions which helped to enhance the clarity of the matter covered here.

## References

  * [1] Atakishiev N.M., Suslov S.K., Difference analogues of the harmonic oscillator, Theoret. and Math. Phys. 85 (1990), 1055–1062.
  * [2] Atakishiyev N.M., Pogosyan G.S., Vicent L.E., Wolf K.B., Finite two-dimensional oscillator. I. The Cartesian model, J. Phys. A: Math. Gen. 34 (2001), 9381–9398.
  * [3] Atakishiyev N.M., Pogosyan G.S., Wolf K.B., Finite models of the oscillator, Phys. Part. Nuclei 36 (2005), 247–265.
  * [4] Bailey W.N., Generalized hypergeometric series, Cambridge Tracts in Mathematics and Mathematical Physics, Vol. 32, Stechert-Hafner, Inc., New York, 1964.
  * [5] Berezans’kiĭ Yu.M., Expansions in eigenfunctions of selfadjoint operators, Translations of Mathematical Monographs, Vol. 17, Amer. Math. Soc., Providence, R.I., 1968.
  * [6] Bevilacqua R., Bozzo E., The Sylvester–Kac matrix space, Linear Algebra Appl. 430 (2009), 3131–3138.
  * [7] Boros T., Rózsa P., An explicit formula for singular values of the Sylvester–Kac matrix, Linear Algebra Appl. 421 (2007), 407–416.
  * [8] Chihara T.S., An introduction to orthogonal polynomials, Mathematics and its Applications, Vol. 13, Gordon and Breach Science Publishers, New York – London – Paris, 1978.
  * [9] Clement P.A., A class of triple-diagonal matrices for test purposes, SIAM Rev. 1 (1959), 50–52.
  * [10] De Bie H., Genest V.X., Tsujimoto S., Vinet L., Zhedanov A., The Bannai–Ito algebra and some applications, J. Phys. Conf. Ser. 597 (2015), 012001, 16 pages, arXiv:1411.3913.
  * [11] Genest V.X., Vinet L., Zhedanov A., The algebra of dual $-1$ Hahn polynomials and the Clebsch–Gordan problem of ${\mathfrak{sl}}_{-1}(2)$, J. Math. Phys. 54 (2013), 023506, 13 pages, arXiv:1207.4220.
  * [12] Higham N., The test matrix toolbox for Matlab, Numerical Analysis Report No. 237, University of Manchester, 1993.
  * [13] Ismail M.E.H., Classical and quantum orthogonal polynomials in one variable, Encyclopedia of Mathematics and its Applications, Vol. 98, Cambridge University Press, Cambridge, 2005.
  * [14] Jafarov E.I., Stoilova N.I., Van der Jeugt J., Finite oscillator models: the Hahn oscillator, J. Phys. A: Math. Theor. 44 (2011), 265203, 15 pages, arXiv:1101.5310.
  * [15] Jafarov E.I., Stoilova N.I., Van der Jeugt J., The $\mathfrak{su}(2)_{\alpha}$ Hahn oscillator and a discrete Fourier–Hahn transform, J. Phys. A: Math. Theor. 44 (2011), 355205, 18 pages, arXiv:1106.1083.
  * [16] Jafarov E.I., Stoilova N.I., Van der Jeugt J., On a pair of difference equations for the ${}_{4}F_{3}$ type orthogonal polynomials and related exactly-solvable quantum systems, in Proceedings of Lie Theory and its Applications in Physics (Varna, 2013), Springer Proceedings in Mathematics & Statistics, Vol. 111, Editor V. Dobrev, Springer, Japan, 2014, 291–299, arXiv:1411.6125.
  * [17] Kac M., Random walk and the theory of Brownian motion, Amer. Math. Monthly 54 (1947), 369–391.
  * [18] Klimyk A.U., The ${\mathfrak{su}}(1,1)$-models of quantum oscillator, Ukr. J. Phys. 51 (2006), 1019–1027.
  * [19] Koekoek R., Lesky P.A., Swarttouw R.F., Hypergeometric orthogonal polynomials and their $q$-analogues, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010.
  * [20] Koelink H.T., Spectral theory and special functions, in Laredo Lectures on Orthogonal Polynomials and Special Functions, Editors R. Álvarez-Nodarse, F. Marcellán, W. Van Assche, Advances in the Theory of Special Functions and Orthogonal Polynomials, Nova Science Publishers, Inc., Hauppauge, NY, 2004, 45–84, math.CA/0107036.
  * [21] Koelink H.T., Van der Jeugt J., Convolutions for orthogonal polynomials from Lie and quantum algebra representations, SIAM J. Math. Anal. 29 (1998), 794–822, q-alg/9607010.
  * [22] Marcellán F., Petronilho J., Eigenproblems for tridiagonal $2$-Toeplitz matrices and quadratic polynomial mappings, Linear Algebra Appl. 260 (1997), 169–208.
  * [23] Nikiforov A.F., Suslov S.K., Uvarov V.B., Classical orthogonal polynomials of a discrete variable, Springer Series in Computational Physics, Springer-Verlag, Berlin, 1991.
  * [24] Nomura K., Terwilliger P., Krawtchouk polynomials, the Lie algebra $\mathfrak{sl}_{2}$, and Leonard pairs, Linear Algebra Appl. 437 (2012), 345–375.
  * [25] Olver F.W.J., Lozier D.W., Boisvert R.F., Clark C.W. (Editors), NIST handbook of mathematical functions, U.S. Department of Commerce, National Institute of Standards and Technology, Washington, DC, Cambridge University Press, Cambridge, 2010, available at http://dlmf.nist.gov/.
  * [26] Slater L.J., Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.
  * [27] Stoilova N.I., Van der Jeugt J., An exactly solvable spin chain related to Hahn polynomials, SIGMA 7 (2011), 033, 13 pages, arXiv:1101.4469.
  * [28] Sylvester J.J., Théorème sur les déterminants, Nouvelles Ann. Math. 13 (1854), 305–305.
  * [29] Taussky O., Todd J., Another look at a matrix of Mark Kac, Linear Algebra Appl. 150 (1991), 341–360.
  * [30] Terwilliger P., Introduction to Leonard pairs, J. Comput. Appl. Math. 153 (2003), 463–475.
  * [31] Tsujimoto S., Vinet L., Zhedanov A., Dual $-1$ Hahn polynomials: “classical” polynomials beyond the Leonard duality, Proc. Amer. Math. Soc. 141 (2013), 959–970, arXiv:1108.0132.
  * [32] Vinet L., Zhedanov A., A limit $q=-1$ for the big $q$-Jacobi polynomials, Trans. Amer. Math. Soc. 364 (2012), 5491–5507, arXiv:1011.1429.


* Agarwal and Duchi (2011) Alekh Agarwal and John C Duchi.  Distributed delayed stochastic optimization.  In _Advances in Neural Information Processing Systems_ , pages 873–881, 2011.
  * Balles and Hennig (2018) Lukas Balles and Philipp Hennig.  Dissecting Adam: The sign, magnitude and variance of stochastic gradients.  In _International Conference on Machine Learning_ , pages 404–413, 2018.
  * Barakat and Bianchi (2020) Anas Barakat and Pascal Bianchi.  Convergence rates of a momentum algorithm with bounded adaptive step size for nonconvex optimization.  In _Asian Conference on Machine Learning_ , pages 225–240. PMLR, 2020\.
  * Basu et al. (2018) Amitabh Basu, Soham De, Anirbit Mukherjee, and Enayat Ullah.  Convergence guarantees for RMSProp and ADAM in non-convex optimization and their comparison to nesterov acceleration on autoencoders.  _arXiv preprint arXiv:1807.06766_ , 2018.
  * Bernstein et al. (2018) Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar.  signSGD: Compressed optimisation for non-convex problems.  In _International Conference on Machine Learning_ , pages 560–569, 2018.
  * Bottou et al. (2018) Léon Bottou, Frank E Curtis, and Jorge Nocedal.  Optimization methods for large-scale machine learning.  _SIAM Review_ , 60(2):223–311, 2018.
  * Carnevale et al. (2020) Guido Carnevale, Francesco Farina, Ivano Notarnicola, and Giuseppe Notarstefano.  Distributed online optimization via gradient tracking with adaptive momentum.  _arXiv preprint arXiv:2009.01745_ , 2020.
  * Chen et al. (2021) Congliang Chen, Li Shen, Haozhi Huang, and Wei Liu.  Quantized adam with error feedback.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 12(5):1–26, 2021.
  * Chen et al. (2022) Congliang Chen, Li Shen, Wei Liu, and Zhi-Quan Luo.  Efficient-adam: Communication-efficient distributed adam with complexity analysis.  _arXiv preprint arXiv:2205.14473_ , 2022.
  * Chen et al. (2018a) Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong.  On the convergence of a class of Adam-type algorithms for non-convex optimization.  _arXiv preprint arXiv:1808.02941_ , 2018a.
  * Chen et al. (2020) Xiangyi Chen, Xiaoyun Li, and Ping Li.  Toward communication efficient adaptive gradient method.  In _Proceedings of the 2020 ACM-IMS on Foundations of Data Science Conference_ , pages 119–128, 2020.
  * Chen et al. (2018b) Zaiyi Chen, Tianbao Yang, Jinfeng Yi, Bowen Zhou, and Enhong Chen.  Universal stagewise learning for non-convex problems with convergence on averaged solutions.  _arXiv preprint arXiv:1808.06296_ , 2018b.
  * Dai et al. (2019) Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdinov.  Transformer-xl: Attentive language models beyond a fixed-length context.  _arXiv preprint arXiv:1901.02860_ , 2019.
  * Défossez et al. (2020) Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier.  A simple convergence proof of adam and adagrad.  _arXiv preprint arXiv:2003.02395_ , 2020.
  * Dozat (2016) Timothy Dozat.  Incorporating Nesterov momentum into Adam.  _International Conference on Learning Representations Workshop_ , 2016\.
  * Duchi et al. (2011) John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  _Journal of Machine Learning Research_ , 12(Jul):2121–2159, 2011.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 770–778, 2016.
  * Hinton et al. (2012) Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky.  Neural networks for machine learning lecture 6a overview of mini-batch gradient descent.  page 14, 2012.
  * Huang et al. (2018) Haiwen Huang, Chang Wang, and Bin Dong.  Nostalgic Adam: Weighing more of the past gradients when designing the adaptive learning rate.  _arXiv preprint arXiv:1805.07557_ , 2018.
  * Jain et al. (2017) Prateek Jain, Purushottam Kar, et al.  Non-convex optimization for machine learning.  _Foundations and Trends® in Machine Learning_ , 10(3-4):142–336, 2017.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Krizhevsky (2009) A Krizhevsky.  Learning multiple layers of features from tiny images.  _Master’s thesis, University of Tront_ , 2009.
  * Krizhevsky (2014) Alex Krizhevsky.  One weird trick for parallelizing convolutional neural networks.  _arXiv preprint arXiv:1404.5997_ , 2014.
  * LeCun et al. (1998) Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * LeCun et al. (2010) Yann LeCun, Corinna Cortes, and Christopher JC Burges.  Mnist handwritten digit database. 2010.  _URL http://yann. lecun. com/exdb/mnist_ , 2010.
  * Li et al. (2014) Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J Smola.  Efficient mini-batch training for stochastic optimization.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 661–670, 2014.
  * Li and Orabona (2019) Xiaoyu Li and Francesco Orabona.  On the convergence of stochastic gradient descent with adaptive stepsizes.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 983–992. PMLR, 2019.
  * Lian et al. (2017) Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu.  Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent.  In _Advances in Neural Information Processing Systems_ , pages 5330–5340, 2017.
  * Luo et al. (2019) Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun.  Adaptive gradient methods with dynamic bound of learning rate.  _arXiv preprint arXiv:1902.09843_ , 2019.
  * Merity et al. (2016) Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher.  Pointer sentinel mixture models.  _arXiv preprint arXiv:1609.07843_ , 2016.
  * Mukkamala and Hein (2017) Mahesh Chandra Mukkamala and Matthias Hein.  Variants of RMSProp and Adagrad with logarithmic regret bounds.  In _International Conference on Machine Learning_ , pages 2545–2553, 2017.
  * Nazari et al. (2019) Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis.  Dadam: A consensus-based distributed adaptive gradient method for online optimization.  _arXiv preprint arXiv:1901.09109_ , 2019.
  * Reddi et al. (2020) Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečnỳ, Sanjiv Kumar, and H Brendan McMahan.  Adaptive federated optimization.  _arXiv preprint arXiv:2003.00295_ , 2020.
  * Reddi et al. (2018) Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar.  On the convergence of Adam and beyond.  In _International Conference on Learning Representations_ , 2018.
  * Robbins and Monro (1985) Herbert Robbins and Sutton Monro.  A stochastic approximation method.  In _Herbert Robbins Selected Papers_ , pages 102–109. Springer, 1985\.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International journal of computer vision_ , 115(3):211–252, 2015.
  * Stich et al. (2018) Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi.  Sparsified sgd with memory.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Wang et al. (2020) Tong Wang, Yousong Zhu, Chaoyang Zhao, Wei Zeng, Yaowei Wang, Jinqiao Wang, and Ming Tang.  Large batch optimization for object detection: Training coco in 12 minutes.  In _European Conference on Computer Vision_ , pages 481–496. Springer, 2020.
  * Ward et al. (2018) Rachel Ward, Xiaoxia Wu, and Leon Bottou.  AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization.  _arXiv preprint arXiv:1806.01811_ , 2018.
  * Xie et al. (2019) Cong Xie, Oluwasanmi Koyejo, Indranil Gupta, and Haibin Lin.  Local adaalter: Communication-efficient stochastic gradient descent with adaptive learning rates.  _arXiv preprint arXiv:1911.09030_ , 2019.
  * Yan et al. (2018) Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang.  A unified analysis of stochastic momentum methods for deep learning.  _arXiv preprint arXiv:1808.10396_ , 2018.
  * You et al. (2017) Yang You, Igor Gitman, and Boris Ginsburg.  Large batch training of convolutional networks.  _arXiv preprint arXiv:1708.03888_ , 2017.
  * You et al. (2019) Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh.  Large batch optimization for deep learning: Training bert in 76 minutes.  _arXiv preprint arXiv:1904.00962_ , 2019.
  * Yu et al. (2019) Hao Yu, Rong Jin, and Sen Yang.  On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization.  _arXiv preprint arXiv:1905.03817_ , 2019.
  * Zaheer et al. (2018) Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar.  Adaptive methods for nonconvex optimization.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Zhang et al. (2019) Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J Reddi, Sanjiv Kumar, and Suvrit Sra.  Why are adaptive methods good for attention models?  _arXiv preprint arXiv:1912.03194_ , 2019.
  * Zhou et al. (2018a) Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu.  On the convergence of adaptive gradient methods for nonconvex optimization.  _arXiv preprint arXiv:1808.05671_ , 2018a.
  * Zhou et al. (2018b) Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu.  AdaShift: Decorrelation and convergence of adaptive learning rate methods.  _arXiv preprint arXiv:1810.00143_ , 2018b.
  * Zou et al. (2018) Fangyu Zou, Li Shen, Zequn Jie, Ju Sun, and Wei Liu.  Weighted adagrad with unified momentum.  _arXiv preprint arXiv:1808.03408_ , 2018.
  * Zou et al. (2019) Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu.  A sufficient condition for convergences of adam and rmsprop.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 11127–11135, 2019.