%%%%%%%%% TIENE 12 PAGINAS COMPILADAS --- PAPER 11 --- %%%%%%%%%
%%%%%%%%% Ronveaux 

%%%%%%%%% revisado y corregido listo para su publicacion, 11 de enero 1997 
%%%%%%%%%%%%%%%%%%%%%%%%%%%  LATEX  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle[11pt,twoside]{iwop96}

\textwidth= 16.3cm
\textheight=24cm
\oddsidemargin .5cm
\evensidemargin -.8cm
\topmargin -1cm



\def\ung{\hbox{1\hskip -4.2pt \rm 1}}
\def\rit{ {\sf I}\hspace*{-1.5pt}{\sf R}}

 \begin{document}
\pagestyle{myheadings} 
\markboth{\sc \centerline{Proceedings of the IWOP'96} }{\sc \centerline{Proceedings of the IWOP'96} }


\thispagestyle{plain}

\input referencia

\begin{center}
{  \bf ORTHOGONAL POLYNOMIALS:  CONNECTION AND LINEARIZATION COEFFICIENTS}
%{\Large \bf Orthogonal polynomials:  connection and linearization coefficients}
\end{center}
\begin{center}
{   \bf A. Ronveaux  }
\end{center}



\begin{abstract}
\noindent Let $\{P_n(x)\}_{n=0}^{\infty}$ and $\{Q_m(x)\}_{m=0}^{\infty}$ 
be two families of orthogonal polynomials.
The linearization problem involves only one family via the relation:
$$
P_i(x)\ P_j(x) =\sum\limits^{i+j}_{k=|i-j|} L_{ijk}\ P_k(x)
$$
and the connection problem mixes both families: 
$$
P_n(x) = \sum\limits^n_{m=0}C_m(n)\ Q_m(x).
$$
In many cases, it is possible to build a recurrence
relation involving only $m$~, satisfied by the linearization
coefficients $L_{ijk}$ and connection coefficients $C_m(n)$~, in
particular if the families $P_n(x)$ and $Q_m(x)$ are classical:
continuous or discrete.  We intend to examine these coefficients from
the point of view of recurrence properties, emphasizing mainly the structure of
these recurrence relations.  This article contains some results already
published, in print or in preparation, by A. Ronveaux, A. Zarzo, E. Godoy, I. Area, 
R. \'Alvarez-Nodarse, S. Belmehdi, N. M. Hounkonnou and S. Lewanowicz.
\end{abstract}

\vspace*{1cm}

\setcounter{section}{0}  % comment these two lines out.
\pagenumbering{arabic}   % Tipo de numeros {roman}
\setcounter{page}{131}     %Leave this line commented out.

\section{Connection problem.}

Let  $\{P_n(x)\}_{n=0}^{\infty}$ and $\{Q_m(x)\}_{m=0}^{\infty}$ 
 be two sequences of polynomials of
degree exactly equal to $n$.  The so-called Connection Problem asks to
find the coefficients $C_m(n)$ in the expansion:
\begin{equation}P_n(x) =\sum^n_{m=0} C_m(n)\ Q_m(x)\;,\end{equation}
and goes back to Stirling \cite{Stirling1} as pointed out by Askey in
his 1975  survey \cite{Askey1}.

Let us represent the polynomials $P_n(x)$ and $Q_m(x)$ in the monomial basis
$\{x^k\}_{k=0}^{\infty}$~, and analyze the structure of the connection coefficients $C_m(n)$
as depending on several assumptions on families $P_n(x)$ and $Q_m(x)$
\begin{equation}
P_n(x) = \sum^n_{k=0} a_{n,k}x^k\;,\qquad
Q_m(x)=\sum^m_{k=0}\overline
a_{m,k}x^k\;,\qquad  a_{n,k},\overline a_{n,k}\in\rit\;.
\end{equation}

Other bases like $x^{[n]}$~, $(x)_n$ or Bernstein basis can also be used, and
polynomials $P_n(x)$ and $Q_m(x)$ can be defined by some properties or
equations.  So let us use in this article the following definitions:

\begin{enumerate}
\def\labelenumi{\theenumi.}
\def\theenumi{{\bf \arabic{enumi}}}
\item {\bf Falling factorial or Stirling polynomial} \cite{AbramoEtAl}\\
$x^{[n]}=x(x-1)\cdots (x-n+1)=\sum\limits^n_{m=0}S^{(m)}_nx^m$~,
where $S^{(m)}_n$ are Stirling numbers of first kind \cite{Stirling1}.

\item {\bf Rising factorial or Pochhammer symbols} \cite{AbramoEtAl}\\
$ (x)_n=x(x+1)\cdots (x+n-1)$, $(x)_0 =1$~.

\item {\bf Appell family $\{P_n(x)\}$} \cite{Chihara}\\
$P'_n(x)=\lambda(n)P _{n-1}(x)$

\item {\bf Orthogonal family $\{ P_n(x)\}$} \cite{Chihara,Erdelyi}\\  Monic
polynomial $P_n(x)$ of degree $n$ generated by the three-term Recurrence
Relation
(R.R.) \[xP_n(x)=P_{n+1}(x)+\beta _nP_n(x)+\gamma _nP_{n-1}(x)\;,\qquad
n\ge 0\;,\]
\[P_{-1}(x)=0\;,\quad P_0(x)=1\;,\qquad \gamma _n\neq 0\;,\;  n\ge 0\;.\]

\item {\bf Classical orthogonal polynomials (continuous)} \cite{Niki,Niki1}\\
Polynomial solution $P_n(x)$ of degree $n$ of the second order Differential
Equation (D.E.):
\[ {\cal L}_{2,n}[P_n(x)]\equiv \sigma P''_n+\tau P'_n-n\tau
'_{(n-1)/2}P_n=0\;, \]
$\tau  _r=\tau +r \sigma '$~, $\sigma =\sigma (x)$ polynomial of degree 2:
Jacobi (J), Bessel (B); of degree 1: Laguerre (L); of degree 0: Hermite
(He),  and
$\tau \equiv \tau (x)$ polynomial of first degree.

\item {\bf Classical orthogonal polynomial (discrete)} \cite{Niki,Niki1}\\
Polynomial solution $P_n(x)$ of degree $n$ of the second order Difference
Equation
\[ {\cal D}_{2,n}[P_n(x)]\equiv \sigma \Delta\nabla P_n+\tau \Delta P_n-n\tau
'_{(n-1)/2}P_n=0\]
$\sigma \equiv \sigma (x)$ polynomial of degree 2: Hahn (H) and Hahn-Eberlein
(H-E), and polynomial of degree 1: Krawtchouk (K), Meixner (M), Charlier (C).
  $\tau=\tau (x)$ polynomial of first degree. \\
$(\Delta f(x)=f(x+1)-f(x)\ ,\; \nabla f(x)=\Delta f(x-1))$

\item {\bf Semi-classical orthogonal family (continuous and discrete)}
\cite{HendriksenEtAl,Maroni1}\\ Family of orthogonal polynomial $P_n(x)$ which
satisfies a structure relation (S.R.)
\[ \sigma (x)LP_n(x)=\sum^{n+t-1}_{k=n-s-1} \alpha _{k,n}P_k(x)\qquad (\alpha
_{k,n}\mbox{\ constants})\]
where $L=d/dx$ (continuous) or $L=\Delta$ (discrete).\\
 For $t=0,1,2$ and $s=0$
semi-classical orthogonal polynomials (O.P.)  are classical O.P.

\item {\bf Hildebrandt classical polynomial (continuous)} \cite{Hilde}\\
Polynomial solution $P_n(x,k)$ of degree $n$ of the Differential Equation:
\[ \sigma (x)P''_n(x,k)+\tau _{k-n}(x)P'_n(x,k)-n\tau
'_{k-n/2-1/2}P_n(x,k)=0\;.\]
These polynomials: H-J, H-B, H-L, H-He, reduce to the family \#5. (orthogonal)
when $k=n$~, and to the family $P_n^{(r)}(x)$~, when $k-n=r$ (~$P_n^{(r)}(x)$~,
$r$-th derivative of $P_n(x)$~; $[P_{n+r}(x;n+r)]^{(r)}=P_n(x,n+r)$~).\\
For fixed
$k$~,
$P_n(x,k)$ is an Appell family.

\item {\bf Bernstein Basis (continuous)} \cite{Sablonniere}
\[ B^n_i(x)=\left(\begin{array}{c} n\\ i\end{array}\right)
x^i(1-x)^{n-i}=\sum^n_{j=i}(-1)^{j-i}
\left(\begin{array}{c} n\\ j\end{array}\right)
\left(\begin{array}{c} j\\ i\end{array}\right)x^j\;,\qquad 0\le i\le n\;.\]

\item {\bf Bernstein Basis (discrete)} \cite{Sablonniere}
\[ b^n_i(N,x)=\left(\begin{array}{c} n\\ i\end{array}\right)
\frac{x^{[i]}(N-x)^{[n-i]}}{N^{[i]}}\;, \quad 0 \leq i \leq n \leq N\]
The bases $B^n_i(x)$ and $b^n_i(N,x)$ are of degree $n$ (~$0\le i\le n\le N$~)
for all $i$~, contrary to the previous polynomials $P_n(x)$ and $Q_n(x)$ of
degree
equal to
$n$~.
\end{enumerate}
\vskip 11pt

The vectors $\vec P_n^t=(P_0,\cdots,P_n)$ and $\vec Q_n^t=(Q_0,\cdots,Q_n)$
define now a lower triangular connection matrix $[C_{n,m}]$
\begin{equation}\vec P_n=[C_{n,m}]\vec Q_n  \qquad \mbox{with\ }
C_{n,m}=C_m(n)\end{equation}
which  has a specific structure (see Table 1) following the assumptions \#1 to
\#10.

In general, we work with monic polynomials (~$a_{n,n}=\overline a_{n,n}=1$~).  In that
case, the set of all connection matrix of size $n+1$ by $n+1$ forms a multiplicative group
called $T(n+1,\rit)$~, subgroup of $SL(n+1,\rit)$~.

Let us emphasize the structure of the connection coefficients in two following
cases: i) assumption \#4 (families $P_n$ and $Q_n$ both orthogonal) and ii)
assumption \#7 (families $P_n$ and $Q_n$ both semi-classical).

It is important to realize first (and to prove easily by derivation of the
S.R.) that the existence of a S.R. for the family $P_n(x)$ implies that
$P_n(x)$ is solution of a second order differential (or difference) equation:

\begin{equation}
{\cal L}_{2,n}[P_n(x)]=0\;,\qquad (\; {\cal D}_{2,n}[P(x)]=0\;).
\end{equation} 
These operators ${\cal L}_{2,n}$  and ${\cal D}_{2,n}$  are of
course more general than the operators considered in the assumptions \#5 and \#6.

\begin{table}
\begin{center}
\[\fbox{$\displaystyle{P_n(x)=\sum^n_{m=0}C_m(n)Q_m(x)}$}\]

\vskip 11pt

{  \renewcommand{\arraystretch}{1.8}
\begin{tabular}{||c|c|c||}\hline\hline
$P_n(x)$ & $Q_m(x)$ & \begin{tabular}{c}{\bf Connection matrix}\\
$[C_{n,m}]=[C_m(n)]$\end{tabular}
\\
\hline\hline arbitrary & arbitrary & no structure (except $C_n(n)\neq
0$~)\\\hline
$x^n $ & $x^{[m]}$ & \begin{tabular}{c} hook structure\\
$s_n^{(m)}=s_{n-1}^{(m-1)}+ms_{n-1}^{(m)}$\\
$s_n^{(m)}=$ Stirling   numbers \\of second kind\end{tabular}\\ \hline
$x^{[n]}$ & $x^{m}$ &\begin{tabular}{c} hook structure\\
$s_n^{(m)}=s_{n-1}^{(m-1)}-(n-1)s_{n-1}^{(m)}$\\
$s_n^{(m)}=$ Stirling   numbers \\of first kind\end{tabular}\\ \hline
Appell & $\left\{ \begin{array}{l}
x^m \\ \mbox{Appell}\end{array}\right.$ & \begin{tabular}{c}
diagonal structure \\
$C_{m+1}(n+1)=k(m,n)C_m(n)$\end{tabular}\\ \hline
orthogonal & orthogonal & cross structure \\ \hline
semi-classical O.P. & semi-classical O.P. & row structure \\ \hline
$x^n$ & semi-classical O.P. & row structure \\ \hline
Hildebrandt classical & semi-classical O.P. & row structure \\ \hline
$\left\{ \begin{array}{l}
{\cal L}_{r,n}[P_n(x)]=0 \\
{\cal D}_{r,n}[P_n(x)]=0\end{array}\right.$
& semi-classical O.P. & row structure \\ \hline
primitive of semi-classical& semi-classical O.P. & row structure \\ \hline
arbitrary& \begin{tabular}{c} Bernstein basis \\  (continuous or
discrete)\end{tabular}
 & \begin{tabular}{c} no structure\\  (full square matrix)\end{tabular} \\
\hline\hline
\end{tabular}}
\caption{Structure of the connection matrix.}\end{center}
\end{table}

\begin{enumerate}
\def\labelenumi{\theenumi)}
\def\theenumi{\roman{enumi}}
\item
{\bf $\{P_n(x)\}_{n=0}^{\infty}$ and $\{Q_m(x)\}_{m=0}^{\infty}$  are both orthogonal
families.\/} (assumption \#4).    Both families of polynomials involved in
the connection problem (1)
satisfy a three-term recurrence relation which, considering monic
polynomials without loss of generality, are respectively:
\begin{eqnarray}
x\ P_n(x) &=& P_{n+1}(x)+\beta_n\ P_n(x) + \gamma_n\ P_{n-1}(x)\;,\qquad n\ge
0\;,\\
 P_{-1}(x)&=&0\;,\qquad P_0(x)=1\;, \nonumber\\
\noalign{\vskip 6pt}
x\ Q_m(x) &=& Q_{m+1}(x)+\overline\beta_m\ Q_m(x) + \overline\gamma_m\
Q_{m-1}(x)\;,\qquad m\ge
0\;,\\
 Q_{-1}(x)&=&0\;,\qquad Q_0(x)=1\;,\nonumber\end{eqnarray}
where $\gamma_n\neq 0$ and $\overline\gamma_m\neq 0$~.  Then, multiplication
of (1) by $x$~, the use of (5) and (6) and expansion of $P_{n+1}$~,
$P_n$ and $P_{n-1}$ in terms of $Q_m$ by means of (1), generates the
``cross-rule":
\begin{equation}
(\overline\beta_m-\beta_n)\ C_m (n)+C_{m-1}(n)+ \overline\gamma_{m+1}\
C_{m+1}(n)-
C_m(n+1)- \gamma_n\ C_m(n-1)=0\end{equation}
which is valid for $m=0,1,\cdots,n+1$~, with the convention $C_k(j)=0$ when
$k<0$ or $k>j$~.  Notice that this ``cross-rule" mixes the
three adjacent coefficients (~$m-1,m,m+1$~) of the row $n$~, crossing at the
$(m,n)$ position the column $m$ of the aforementioned
$[C_{n,m}]$--matrix.  Any coefficient $C_m(n)$ can be computed from this
``cross-rule" starting from the initial condition: $C_n(n)=1$ (monic
polynomials), $C_{n-1}(n) = a_n-\overline a_n$ and $C_{n-2}(n)=b_n-\overline
b_n-(a_n-\overline a_n)\overline a_{n-1}$~, where $a_n$ and $b_n$ (respectively
 $\overline a_n$ and $\overline b_n$~) are the first coefficients in the
expansions
of $P_n(x)$ and $Q_n(x)$~, $a_n=\frac{a_{n,n-1}}{a_{n,n}}$~,
$b_n=\frac{a_{n,n-2}}{a_{n,n}}$~.


\item {\bf $\{P_n(x)\}_{n=0}^{\infty}$ and $\{Q_m(x)\}_{m=0}^{\infty}$ 
 are both semi-classical\/} (assumption
\#7)  These assumptions transform the ``cross-rule" given in (7) in a
``row-rule", avoiding the mixing between $m$ and $n$~.

The connection coefficients $C_m(n)$ are now linked by the relation ($n$
fixed):
\begin{equation}{\cal L}_{2,n}[P_n(x)]=\sum^n_{m=0}C_m(n){\cal
L}_{2,n}[Q_m(x)]=0\qquad (\mbox{same with\ } {\cal D}_{2,n}\; )\end{equation}
from the Differential (or Difference) Equation satisfied by $P_n$~. Each term
$x^k\  L^j[Q_m(x)]$ can be expanded in $Q_m(x)$ using iteration of the S.R.,
the R.R., and also by multiplication by polynomials.  This is the basis of our
algorithm described and summarized in Section 3.
\end{enumerate}

\section{Linearization problems}

Let  $\{P_k(x)\}_{k=0}^{\infty}$ be a system of polynomials of degree exactly equal to
$k$~.  The traditional linearization problem \cite{Askey1}
 is based in the expansion of  the product
$P_i  P_j$ in the $\{P_k(x)\}_{k=0}^{\infty}$  basis 
\begin{equation}
P_iP_j=\sum^{i+j}_{k=0}L_{i,j,k} \ P_k\;.
\end{equation}

The first attempt to find the coefficients $L_{i,j,k}$ goes back to Neumann
\cite{Hobson} in the Legendre case using the $4$-th order differential equation
satisfied by a product of two Legendre polynomials.
In the linear space of polynomials $P_i\equiv P_i(x)$~, the problem of
linearization of products of two polynomials occurs very naturally in a lot of
situations ranging from combinatorics and statistical mechanics, to group
theory in relation with Clebsch-Gordan coefficients
\cite{Hylleraas,Godsil,Niki1,Labelle}.

From the algebraic point of view, the coefficients $L_{i,j,k}=L_{j,i,k}$ are the
structure constants $C^k_{ij}$ of the basis $e_i\equiv P_i$ in the infinite
dimensional associative and commutative algebra of polynomials:
\begin{equation}e_ie_j=C^k_{ij}e_k\;,\end{equation}
using Einstein summation convention.
\\
Again the following assumption changes drastically the relation satisfied by
$L_{i,j,k}$~.

\begin{enumerate}
\def\labelenumi{\theenumi)}
\def\theenumi{\roman{enumi}}
\item At the level of this associative and commutative algebra, $L_{i,j,k}$
verify complicated {\bf nonlinear algebraic\/} relation obtained by expanding
relation (9) after multiplication by $P_r$
\begin{equation}\sum_{s=0}^{r+i}L_{r,i,s}P_sP_j=\sum^{i+j}_{k=0}L_{i,j,k}P_r
P_k\;,\end{equation}
and expanding in terms of $P_t$
\begin{equation}\sum^{r+i}_{s=0}L_{r,i,s} \sum^{s+j}_{t=0}L_{s,j,t}=
\sum^{i+j}_{k=0}L_{i,j,k} \sum^{r+k}_{t=0}L_{r,k,t}\qquad\forall\
i,j,r\;;\end{equation}
\item The orthogonality structure, inside the $P_i$ family (making now the
summation from $k=|i-j|$ to $k=i+j$~), gives a three-term recurrence relation.


Multiplying the R.R. (assumption \#4 in section 1) by $P_i$ and using equation
(9), we get
\begin{eqnarray}
\lefteqn{\sum^{i+j}_{k=|i-j|}L_{i,j,k}(P_{k+1}+\beta _kP_k+\gamma
_kP_{k-1})}\nonumber \\
\noalign{\vskip 11pt}
&=& \sum^{i+j+1}_{k=|i-j-1|}L_{i,j+1,k} P_k
+\sum^{i+j}_{k=|i-j|}\beta _jL_{i,j,k} P_k
+\sum^{i+j-1}_{k=|i-j+1|}\gamma _jL_{i,j-1,k} P_k\quad\forall\ i,j\end{eqnarray}
from which, using the linear independence of $P_k$~, we get a {\bf linear
relation\/} between the $L_{i,j,k}$

\begin{eqnarray}
\lefteqn{\sum_kL_{i,j+1,k}+\beta _jL_{i,j,k}+\gamma
_{j}L_{i,j-1,k}}\nonumber\\
\noalign{\vskip 11pt}
&=&\sum_kL_{i,j,k-1}+\sum_k\beta _kL_{i,j,k}+\sum_k\gamma
_{k}L_{i,j,k+1}\quad\forall\ i,j\;.
\end{eqnarray}
Even the fact that the orthogonality structure inside the $P_i$ family
transforms nonlinear relations into linear relations, equation (14) is
practically intractable because {\bf two\/} families of indices (~$i$ and $j$~)
are already involved in this recurrence.

\item The restriction to {\bf semi-classical\/} orthogonal polynomials allows to
obtain again the linear relation between the $L_{i,j,k}$ but involving only
{\bf one\/} index $k$, using the fourth order differential (or difference) equation
satisfied by the product  $P_iP_j$ and reducing therefore the linearization
problem in this case to a connection problem (see section 1).\end{enumerate}

\section{Algorithm building $R[C_{m+p}(n),C_{m-q}(n)]=0$}

In this work, we approach the connection and linearization coefficients as
solution of a recurrence relation.    Let us summarize the algorithm we have
developed in \cite{Ronveaux1,Ronveaux2} building a {\bf one index\/} recurrence
relation for the connection coefficient $C_m(n)$~.  The assumptions are
slightly
more general than the assumptions used in the derivation of the ``row-rule" in
section 1.

Our method requires only two
assumptions:
\begin{enumerate}
\item The  $\{P_n(x)\}$-family in equation (1) has to be a solution of a
linear differential or difference equation of any order $r$~:
\begin{equation}\sum^r_{j=0} A_j(x;n)\ L^j[P_n(x)]=0\end{equation}
where the operator $L$ can be either the derivative (~$D=d/dx$~) or the
difference operator (~$\Delta$~) and $A_j(x;n)$ are polynomials in the
variable $x$~, of {\bf degree\/} independent of $n$~.
\item The   $\{Q_m(x)\}$--family in equation (1) should satisfy first
a recurrence relation of type:
\begin{equation}x\ Q_m(x) =\sum^{m+1}_{k=m-h} \beta _{k,m}\ Q_k(x)\end{equation}
and also:
\begin{equation}\sigma(x)\ LQ_m(x) = \sum^{n-1+t}_{k=n-1-s} \alpha _{k,m}\
Q_k(x) \end{equation}
where $\sigma(x)$ is a polynomial of degree $t$~, $\beta _{k,m}$ and $\alpha
_{k,m}$~, are constants.  When $h=1$~, the $\{Q_m(x)\}_{m=0}^{\infty}$  family is orthogonal.
\end{enumerate}

The relation (17) (also called ``Structure Relation" in orthogonal
context \cite{Maroni1}) is satisfied not only by classical orthogonal
polynomials continuous and discrete, but also by a very large class of
orthogonal polynomials called semi-classical \cite{HendriksenEtAl}.
Any family of orthogonal polynomials which satisfy second order
differential or difference equations of the form (15) is
semi-classical and for such family a structure relation exists.  All
orthogonal polynomials with orthogonality measure $\rho(x)
=\rho_c(x)+\sum\limits_iM_i\ \delta (x-c_i)$~, $\rho (x)=\pi (x)\rho _c(x)$ or
$\rho (x)=\theta _\lambda \rho _c(x)$~, where
$\rho_c$ denotes a classical weight, are for example semi-classical (~$\pi (x)$
 rational function of $x$~, $\theta _\lambda (x)$  the step function:
$\theta _\lambda (x)=0$~, $x<\lambda $~; $\theta _\lambda (x)=1$~, $\lambda \le
x$~).

The algorithm runs in the following steps
\begin{enumerate}
\item Apply relation (15) to the definition (1)
\[ \sum^n_{m=0}\sum^r_{j=0}C _m(n)A_j(x;n)L^j[Q _m(x)]=0\;.\]

\item Expand all terms in $A_j(x;n)L^j[Q_m(x)]$ in a constant coefficient
relation between the polynomials $Q_m(x)$~.  In order to do that, all power
in $A_j(x;n)$ and all derivatives (or differences) in $L^j[Q_m(x)]$ are
expanded using relation (16) and (17), iterates a number of times depending on
the highest degree in $A_j(x;n)$ and the order $j$ in $L^j[Q_m(x)]$~.

\item From the linear independence of polynomial $Q_m(x)$ (other basis like
$Q'_m(x)$ or $Q''_m(x)$ are possible and sometimes more appropriate
\cite{Godoy,Area}), a shift of indices generates the search recurrence
\[ R[C _{m+p}(n),\cdots,C _{m-q}(n)]=0\;.\]
\end{enumerate}

For  problems involving classical orthogonal continuous or discrete (sect. 1,
assumptions \#5 and \#6), all the data contained in (15), (16), (17) are
computed
via relations given in \cite{Yanez} from the polynomials $\sigma (x)$ and
$\tau(x)$ appearing in assumptions \#5 and \#6 of section 1.  These
$\sigma (x)$ and $\tau (x)$ give also the orthogonality weight $\rho =\rho (x)$
via the Pearson equations
\[ (\sigma \rho )'=\tau\rho  \;,\qquad \Delta(\sigma  \rho )=\tau \rho \;.\]
These two polynomials $\sigma $ and $\tau $ are the basic input in the program
which follows automatically steps 1 to 3.

Among the many results partly published, let us select the connection
between two Meixner polynomials (assumption \#6).

\paragraph{Meixner-Meixner}\mbox{}
\[ \sigma (x)=x\;,\quad \tau (x)=\gamma \mu  -x(1-\mu  )\qquad \gamma >0\ ,
\; 0<\mu <1\;.\] The coefficients for the connection problem
\[ M_n^{(\gamma ,\mu   )}(x)=\sum^n_{m=0}C_m(n)M_m^{(\delta ,\nu )}(x)\]
satisfy the {\bf three-terms\/} recurrence relation
\begin{eqnarray}
&&(1-\mu )(1-m+n)(-1+\nu )^2C_{m-1}(n) \nonumber \\
&&+ m(-1+\nu )[(-1+\delta +2m-n)\nu +\mu (1-\gamma -m+(-\delta +\gamma -m+n)\nu
)]C_m(n)\nonumber\\
&&+ m(1+m)(\delta +m)(\mu -\nu )\nu C_{m+1}(n)=0\end{eqnarray}
valid for $1\le m\le n$~, with initial conditions
\begin{eqnarray*}
C_n(n)&=&1\\
\noalign{\vskip 6pt}
C_{n-1}(n)&=&\frac{n[\mu (1-\gamma -n)+(-1+\delta +(-\delta +\gamma )\mu +n)\nu
]}{(1-\mu )(1-\nu )}\;.\end{eqnarray*}
In case $\mu =\nu $~, it reduces to a two-terms recurrence relation, whose
solution is \cite{Ronveaux2,Lewa0}:
\begin{equation}C_m(n) =\left(\begin{array}{c} n\\ m\end{array}\right)
\left(\frac\mu
{1-\mu }\right)^{n-m}(\gamma -\delta )_{n-m}\;.\end{equation}
In case $\gamma =\delta $~, the (new) result is \cite{Area}
\begin{equation}C_m(n) =\left(\begin{array}{c} n\\ m\end{array}\right)
\left(\frac{\Gamma(n+\delta )} {\Gamma(m+\delta ) }\right)
\left( \frac{\nu -\mu }{(1-\mu )(1-\nu )}\right)^{n-m}\;.\end{equation}

Table 2 presents informations on explicit results or on the structure of the
recurrence relation satisfied by $C_m(n)$ connecting essentially Classical
Orthogonal Polynomials.  Many results are already published, in print or in
preparation.  We refer mainly to works related to the recurrence relation
approach in which, of course, other approaches and results are mentioned.

\begin{table}

{\renewcommand{\arraystretch}{1.4}\begin{tabular}{||c|c|c||} \hline\hline
$P_n(x)$ & $Q_m(x)$ &
$R[C _{m+p}(n),\cdots,C_{m-q}(n)]=0$ \\ \hline\hline
$x^n$ & (J,B,L,He) & max 3 terms, solved, \cite{Zarzo,Luke}\\ \hline
$x^{[n]}$ & (H,H-E,,K,M,C)) & max 3 terms, solved, \cite{Zarzo}\\ \hline
(J,B,L,He) & (J,B,L,He) & max 3 terms, partly solved, \cite{Godoy}\\ \hline
(H,H-E,K,M,C)) & $\left\{ \begin{array}{l}
\mbox{(H,H-E,K,M,C)}\\  x^{([m]}\end{array}\right.$ &
\hspace{-2mm}\begin{tabular}{l} max 3 terms, partly solved,
\cite{Ronveaux2,Area,Lewa0}\\ max 3 terms, partly solved,
\cite{Zarzo}\end{tabular}\hspace{-2mm}\\
\hline
 $\left\{ \begin{array}{l}
P_n(x+b),P_n(ax)\\ P_n=\mbox{(J,B,L,He)}\end{array}\right.$ &(J,B,L,He)&
 $\left\{ \begin{array}{l} Q_m(x)\equiv P_m(x)\\
\mbox{max 5 terms, partly solved,
\cite{Godoy}}\end{array}\right.$\\
\hline
 $\left\{ \begin{array}{l}
P_n(x+y),\\ P_n=\mbox{(H,H-E,K,M,C)}\end{array}\right.$ &(H,H-E,K,M,C)&
\hspace{-2mm}$\left\{ \hspace{-2mm}\begin{array}{l} Q_m(x)\equiv P_m(x)\\
\mbox{max 3 terms, partly solved,
\cite{Ronveaux2,Area}}\end{array}\right. $\hspace{-2mm}\\
\hline \begin{tabular}{l} Bernstein basis\\
 $ \begin{array}{l}
 \mbox{- continuous}\\  \mbox{- discrete}\end{array}$ \end{tabular}&
 $ \begin{array}{l}\mbox{}\\
\mbox{shifted Jacobi}\\ \mbox{Hahn polynomial}\end{array} $&
  5 terms, solved, \cite{Ronveaux5}\\ \hline
(H-J,H-B,H-L,H-He) & (J,B,L,He) & \begin{tabular}{c} no mixture\\ max 3
terms, in
progress\end{tabular}\\
\hline
 \hspace{-2mm}$\left\{ \hspace{-2mm}\begin{array}{l}P_iP_j\\
\noalign{\vskip 6pt}
P_i,P_j=\mbox{(J,B,L,He)}\\ \noalign{\vskip 6pt}
P_i,P_j=\mbox{(H,H-E,K,M,C)}\end{array}\right.$ &
 $\begin{array}{l}\mbox{}\\ \noalign{\vskip 3pt}
\mbox{(J,B,L,He)}\\  \noalign{\vskip 6pt}\mbox{(H,H-E,K,M,C)}\end{array} $&
 \begin{tabular}{l} \mbox{}\\ $\left\{ \begin{array}{l} \mbox{JJ,BB,LL,HeHe\ 3
terms \cite{RonveauxEtal,Lewanowicz1}}\\ \mbox{mixture, max 5 terms,
\cite{Ronveaux4}}\end{array}\right. $\\ no mixture, max 3 terms,
\cite{Belmehdi}\end{tabular}
\\
\hline
 $\left\{ \begin{array}{l}[P_i]^N\\
P_i=\mbox{(J,B,L,He)}\\ P_i=\mbox{(H,H-E,K,M,C)}\end{array}\right.$ &
 $ \begin{array}{l}\mbox{}\\
\mbox{(J,B,L,He)}\\ \mbox{(H,H-E,K,M,C)}\end{array}$&
 \begin{tabular}{l}\mbox{}\\in progress ($N=2$, max 5 terms)
\cite{RonveauxEtal}\\ in progress ($N=2$, max 9 terms)
\cite{LewaEtAl}\end{tabular}\\
\hline
 $\left\{ \begin{array}{l} P_n^{(r)},\ r\mbox{\
associated}\\ \noalign{\vskip 6pt} P_n=\mbox{(J,B,L,He)}\\
\mbox{}\\P_n=\mbox{(H,H-E,K,M,C)}\end{array}\right.$ &
 $ \begin{array}{l}\mbox{}\\ \noalign{\vskip 6pt}
\mbox{(J,B,L,He)}\\ \mbox{}\\ \mbox{(H,H-E,K,M,C)}\end{array}$&
 \begin{tabular}{l} \mbox{}\\ \noalign{\vskip 6pt}
$\left\{ \begin{array}{l} r=1\; , \mbox{\
\cite{Ronveaux1,Lewanowicz2,Lewanowicz3}}\\ \mbox{arbitrary
$r$~, \cite{Ronveaux0,Lewanowicz2,Lewanowicz3}}\end{array}\right.$\\
$\left\{ \begin{array}{l} r=1\;, \mbox{\
\cite{Ataki,Ronveaux3}}\\ \mbox{arbitrary
$r$~, in progress}\end{array}\right.$\end{tabular} \\ \hline
 $\left\{ \begin{array}{l}
\mbox{(J,B,L,He)}\\\mbox{(H,H-E,K,M,C)}\end{array}\right.$ &
 $\left\{ \begin{array}{l}
D^m\mbox{(J,B,L,He)}\\ \Delta^m\mbox{(H,H-E,K,M,C)}\end{array}\right.$&
 \begin{tabular}{c} Gram-Charlier series\\ in progress\end{tabular}\\ \hline
 $\left\{ \begin{array}{l}
 \mbox{even part of (J,B,L)}\\ \mbox{odd
part of (J,B,L)}\end{array}\right.$ &
 (J,B,L,He) &
 in progress\\ \hline
reciprocal of (J,B,L,He) & (J,B,L,He) & in progress \\
\hline\hline\end{tabular}}
\caption{Applications of the algorithm involving classical O.P.}
\end{table}

\section{Group properties}

The Lie group $T(n+1,\rit)$ of lower triangular $n+1$ matrices with diagonal
elements being equal to 1 contains $\frac{n(n+1)}2$ parameters.  If for
a family
of polynomials $\vec P_n(x,\alpha _i)$ with $r$ parameters $i=1,\cdots ,r$~, we
can  solve explicitly the connection problem, we generate automatically a $r$
dimensional subgroup of
$T(n,\rit)$ as a realization of this.

The group property generates the following multiplicative law between the
matrices connecting parameters $\alpha  ,\overline \alpha
 ,\overline{\overline\alpha } $~:
\[ [C _{n,m}]^{\alpha ,\overline\alpha } [C _{m,k}]^{\overline\alpha,
\overline{\overline\alpha }}= [C _{n,k}]^{\alpha ,\overline{\overline\alpha }}\]
with
\[ \vec P_n(x,\alpha _i)=[C _{n,m}]^{\alpha ,\overline\alpha }\vec
P_n(x,\overline\alpha _i)\]
\[ [C _{n,m}]^{\alpha, \overline\alpha } [C _{m,k}]^{\overline\alpha , \alpha
}=\ung= [C _{n,k}]^{\alpha, \alpha }\;.\]
As an example of one dimensional subgroup, let us consider the Charlier-Charlier
connection problem:
\[ C _n^{(\alpha )}(x)=\sum^n_{m=0}C _m(n)C _m^{(\overline\alpha )}(x)\]
for which $C _m(n)=\left(\begin{array}{c} n\\ m\end{array}\right)
(\overline\alpha
-\alpha )^{n-m}$~.

With $\lambda =\overline\alpha -\alpha $~, the one dimensional subgroup
appears as
\[ 
[C _{n,m}]^\lambda =\left[
\begin{array}{ccccc}
1&0&0&\cdots & 0\\
\lambda &1&0&\cdots & 0\\
\lambda ^2&\lambda &1&\cdots & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots\\
\lambda ^k& \left( k\atop 1\right)\lambda ^{k-1}& 0 & \cdots & 0\\
\vdots &\vdots & \vdots &\vdots & \vdots \\
\lambda ^n&\left( n\atop 1\right)\lambda ^{n-1}&
\left( n\atop 2\right)\lambda ^{n-2}&\cdots & 1\end{array}\right]\]
which gives the matrix property
\[ [C _{n,m}]^\lambda [C _{m,k}]^{\overline\lambda }=[C _{n,k}]^{\lambda
+\overline\lambda }\]
\[ \{ [C _{n,m}]^\lambda \}^{-1}=[C _{n,m}]^{-\lambda }
\]
This one-dimensional subgroup  is, of course, abelian, but it should be
interesting to investigate two dimensional subgroups coming from Jacobi-Jacobi,
Meixner-Meixner, Hahn-Hahn, \ldots\  From the fact that there exists only two
real Lie algebras of dimension two (nine of dimension three, \ldots), which
family of two parameter orthogonal polynomials corresponds to the abelian or
solvable case?

\paragraph{Remarks:} This short survey presents in some way a new approach
in order to study systematically connection and linearization problems
involving polynomials orthogonal and also not orthogonal.  An one variable recurrence
relation is the   basic tool which allows to compute or to study these connection and
linearization coefficients.  For a large class of polynomials these recurrence
relations are built almost automatically by a very simple algorithm which
applies in all cases.

In many situations, these recurrences are solved by the computer using
Mathematica, Maple, Reduce, \ldots\  Even if the explicit solution is not
given by the computer, properties of these coefficients can be obtained:
positivity, asymptotics, limit relations, \cite{Szwarc1,Szwarc2,Lasser}.

This global approach, which applies already for some $q$-orthogonal polynomials
\cite{Alvarez}, is quite different from other more traditional approaches using
for each family an ad hoc technique: generating functions, hypergeometric series
properties (se e.g. \cite{Askey1}).

\vspace*{0.3cm}

\underline{ACKNOWLEDGEMENTS} It is a pleasure to thank the Universidad Carlos
III de Madrid for the kind invitation and for the financial support which
allowed me to present this material in Legan\'es with the ocasion of the 
International Workshop on Orthogonal Polynomials and Mathematical Physics
(24-26 June 1996). Parts of the
published results presented in this work were supported by a NATO grant
(CRG-960213).


\vspace*{0.3cm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The bibliography %%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In alphabetical order %%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{50} %%% In alphabetical order, see examples:

\bibitem{AbramoEtAl}{\sf M. Abramowitz and I.A. Stegun:} {\sc Handbook of
Mathematical Functions.\/} Dover, 1965.

\bibitem{Alvarez}  {\sf  R. \'Alvarez-Nodarse and A. Ronveaux:}
{\em Recurrence relations for connection coefficients between $q$-orthogonal
polynomials of discrete variables in the non-uniform lattice $X(s)=q^{2s}$.\/}
{\sc J. Phys. A: Math. Gen.} {\bf 29\/} (1996), 1--11.

\bibitem{Area}  {\sf I. Area, E. Godoy, A. Ronveaux and A. Zarzo:} {\em
Minimal recurrence relations for connection coefficients between classical
orthogonal polynomials: Discrete case.\/} 1996 (submitted).



\bibitem{Askey1}  {\sf R. Askey:} {\em Orthogonal Polynomials and Special
Functions.\/} {\sc Regional Conference in Applied  Mathematics.} {\bf 21\/},
SIAM, Philadelphia, Pennsylvania, 1975.


\bibitem{Ataki} {\sf N. M. Atakishiyev, A. Ronveaux and K.B. Wolf:} {\em
Difference equations for the associated polynomials on the linear lattice.\/} 
{\sc J. Theor. Math. Phys.} (Moscow) {\bf 106} (1996), 76--83.

%B

\bibitem{Belmehdi} {\sf S. Belmehdi, S. Lewanowicz and A. Ronveaux:}
 {\em Linearization of product of orthogonal polynomials of a discrete
variable.\/} (1996), (submitted).

%C

\bibitem{Chihara} {\sf T. S. Chihara:} {\em An Introduction to Orthogonal Polynomials.\/}
Gordon and Breach Publ., New York, 1978.

%D  %E

\bibitem{Erdelyi} {\sf A. Erd\' elyi Ed.:} {\em Higher Transcendental
Functions.\/}  {\bf Vol. I}, McGraw-Hill, New York, 1953.

%F %G

\bibitem{Godoy}  {\sf E. Godoy,  I. Area, A. Ronveaux and A. Zarzo:}
 {\em Minimal recurrence relations for connection coefficients between classical
orthogonal polynomials: Continuous case.\/} (1996), (submitted).


\bibitem{Godsil} {\sf C. D. Godsil:} {\sc Algebraic Combinatorics.\/}
 Chapman and Hall, New York, 1993.

%H

\bibitem{HendriksenEtAl} {\sf E. Hendriksen and H. van Rossum:}
{\em Semiclassical orthogonal polynomials.\/} {\sc Lecture Notes in Math.} {\bf
1171\/}, Springer, Berlin (1984), 354--361.

\bibitem{Hilde}  {\sf E. H. Hildebrandt:} {\em Systems of polynomials connected with
the Charlier expansions and the Pearson differential and difference equation.\/}
{\sc Ann. Math. Statist.} {\bf 2\/}, (1931), 379--439.


\bibitem{Hobson} {\sf  W. Hobson:} {\sc The Theory of Spherical and
Ellipsoidal Harmonics.\/}  Chelsea, New York, 1965.

\bibitem{Hylleraas} {\sf E. Hylleraas:} {\em Linearization of products of
Jacobi polynomials.\/} {\sc Math. Scand.} {\bf 10\/} (1962), 189--200.

%I %J  %K  %L

\bibitem{Labelle} {\sc J. Labelle and Y.N. Yeh:} {\em The combinatorics of
Laguerre, Charlier and Hermite polynomials.\/} {\sc Studies in Appl. Math.}
{\bf 80\/} (1980), 25--36.

\bibitem{Lasser} {\sf R. Lasser:} {\em Linearization of the product of
associated Legendre polynomials.\/} {\sc SIAM J. Math. Anal.} {\bf 14\/}
(1983), 403--408.

\bibitem{Lewanowicz3} {\sf S. Lewanowicz:} {\em Quick construction of recurrence
relations for the Jacobi coefficients.\/} {\sc J. Comput. Appl. Math.}  {\bf 43\/}
(1992), 355--372.


\bibitem{Lewanowicz2} {\sf S. Lewanowicz:}  {\em Results on the associated
classical orthogonal polynomials.\/} {\sc J. Comput. Appl. Math.}  {\bf 65\/}
(1995), 215--231.

\bibitem{Lewanowicz2-1} {\sf S. Lewanowicz:} {\em Results on the associated 
Jacobi and Gegenbauer polynomials.\/} {\sc J. Comput. Appl. Math. } {\bf 49\/}
(1993), 137--143.


\bibitem{Lewanowicz1} {\sf S. Lewanowicz:}  {\em Second order recurrence
relations for the linearization coefficients of the classical
orthogonal polynomials.\/} {\sc J. Comput. Appl. Math. } {\bf 69\/}
(1996), 159--170.


\bibitem{Lewa0}{\sf S. Lewanowicz:}   {\em Recurrence relations for the connection
coefficients of orthogonal polynomials of a discrete variable.\/} 
{\sc  J. Comput. Appl. Math.} {\bf 76\/} (1996), 213--229.

\bibitem{LewaEtAl} {\sf S. Lewanowicz  and A. Ronveaux:} {\em Linearization of
powers of an orthogonal polynomial of a discrete variable.\/} (1996) (submitted).

\bibitem{Luke} {\sf Y. L. Luke:}  {\sc The Special Functions and their
Approximations.} Academic Press, New York, 1969.

%M


\bibitem{Maroni1} {\sf P. Maroni:} {\em Prol\'egom\`enes \`a l'\' etude des
polyn\^ omes orthogonaux semi-classiques.\/} {\sc Annal. di Mat. Pura et Appl.}
{\bf 149\/} (4) (1987), 165--184.

%N

\bibitem{Niki} {\sf A.F. Nikiforov and V.B. Uvarov:} {\sc
Fonctions Sp\'eciales de la Physique Math\'ematique.\/}
MIR, Moscou, 1983.


\bibitem{Niki1} {\sf A.F. Nikiforov, S.K. Suslov and V.B. Uvarov:} {\em
Classical Orthogonal Polynomials of a Discrete Variable.\/} 
Springer-Verlag, Berlin, 1991.


%O  %P  %Q  %R

\bibitem{Ronveaux0} {\sf A. Ronveaux:} {\em 4th order differential equations and
orthogonal polynomials of the Laguerre-Hahn class.\/} In: 
{\sc Orthogonal Polynomials and Their Application\/} (C. Brezinski, L. Gori
and A. Ronveaux eds.) IMACS Annals on Computing and Applied Math., 
{\bf Vol. 9 }(1--4); CIV (1991), J.C. Baltzer A.G. Basel, 379--385.



\bibitem{RonveauxEtal} {\sf A. Ronveaux, M.N. Hounkonnou and  S. Belmehdi:} {\em
Recurrence relations between linearization coefficients of orthogonal
polynomials.\/} Report, Laboratoire de Physique Math\'ematique (1993), FUNDP
Namur.


\bibitem{Ronveaux1} {\sf A. Ronveaux, A. Zarzo and E. Godoy:} {\em Recurrence
relations for connection coefficients between two families of
orthogonal polynomials.\/} {\sc J. Comput. Appl. Math.} {\bf 62\/} (1995), 67--73.

\bibitem{Ronveaux4} {\sf A. Ronveaux, M.N. Hounkonnou and  S. Belmehdi:} {\em
Generalized linearization problems.\/} {\sc J. Phys. A: Math. Gen.}
 {\bf 28\/} (1995), 4423--4430.


\bibitem{Ronveaux2} {\sf A. Ronveaux, S. Belmehdi, E. Godoy and A. Zarzo:} {\em
Recurrence relations approach for connection coefficients.
Applications to classical discrete orthogonal polynomials\/},
{\sc CRM. Proceedings  and Lecture Notes Series.} {\bf Vol.9}, AMS, Providence, RI, 1996,
 321--337.

\bibitem{Ronveaux3} {\sf A. Ronveaux,  E. Godoy and A. Zarzo:} {\em
First associated and co-recursive of classical discrete orthogonal
polynomials.  Difference equations and connection problems.\/} (1996), (submitted).


\bibitem{Ronveaux5} {\sf A. Ronveaux, A. Zarzo, I. Area and E. Godoy:} {\em Bernstein
bases and Hahn-Eberlein orthogonal polynomials.\/} (1996), (submitted).


%S

\bibitem{Sablonniere} {\sf P. Sablonni\`ere:} {\em Discrete Bernstein bases and Hahn
polynomials.\/} {\sc J. Comput. Appl. Math.}   {\bf 49\/} (1993), 233--241.


\bibitem{Stirling1} {\sf J. Stirling:} {\sc Methodus differentialis: sive, Tractatus de summatione et
interpolatione serierum infinitarum.\/} London, 1730.

\bibitem{Szwarc1} {\sf R. Szwarc:} {\em Connection coefficients of orthogonal
polynomials.\/} {\sc Canad. Math. Bull.} {\bf 35\/} (1970), 100--102.

\bibitem{Szwarc2} {\sc R. Szwarc:} {\em Linearization and connection
coefficients of orthogonal polynomials.\/} {\sc Monat. Math.} {\bf 113\/}
(1992), 319--329.

\bibitem{Yanez}  {\sf R. J. Y\'a\~nez, J.S. Dehesa and A.F.  Nikiforov:} {\em
The three term recurrence relations and differential formulas for
hypergeometric-type functions.\/} {\sc J. Math. Ann. Appl.} {\bf 188\/} (1994),
855--866.


\bibitem{Zarzo} {\sf A. Zarzo, I. Area, E. Godoy and A. Ronveaux:} {\em Results
on some inversion problems for classical continuous and discrete orthogonal
polynomials.\/} {\sc J. Phys. A: Math. Gen.} (1997) (In print).

\end{thebibliography}

%%%\vfill

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Your adress %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{\sc
\begin{flushleft}
  {  A. Ronveaux  } \\
Facult\' es Univ. N.D. de
la Paix, Namur, Belgium   \\
{\sf E-mail}: {\tt Andre.Ronveaux@fundp.ac.be }  
\end{flushleft}
}
\end{document}

