%EuclidOrthogonal.tex     Nov 03   Tianjin 
\documentclass[a4paper,11pt]{article}
\usepackage{amsmath,amsfonts,amssymb}

\def\A{{\mathbb A}}
\def\B{{\mathbb B}}
\def\N{{\mathbb N}}
\def\AB{ {\mathbb A}\moins {\mathbb B}}
\def\xA{x\moins {\mathbb A}}
\def\xB{x\moins {\mathbb B}}
\def\cR{{\mathcal R}}
\def\cD{{\mathcal D}}
\def\Bez{{ \mathfrak{B \hspace{-0.1 em}e\hspace{-0.07 em} z}}}

\def\moins{\raise 1pt\hbox{{$\scriptstyle -$}}}
\def\plus{\raise 1pt\hbox{{$\scriptstyle +$}} }

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\begin{document}
\title{EUCLID and ORTHOGONAL POLYNOMIALS}

\author{\small Alain Lascoux\\
\small CNRS, Institut Gaspard Monge, Universit\'e de Marne-la-Vall\'ee\\
\small 77454 Marne-la-Vall\'ee Cedex, France\\
\small Center for Combinatorics, Nankai University\\
\small Tianjin 300071, P.R. China\\
\small  Alain.Lascoux@univ-mlv.fr }

\date{November 03}
\maketitle
\begin{abstract}
In the classical theory of elimination, or of Sturm sequences, one encounters
 relations which are better understood when translated in terms of orthogonal
polynomials. Conversely, one may safely associate to the 
Tchebychef-Christoffel-Darboux
kernel the names of B\'ezout, Sylvester, Hermite, Brioschi, and 
recognize that these mathematicians treated the case of a 
finite discrete measure, with the help of the Euclidean algorithm and
of the Lagrange interpolation.
\end{abstract}

Given two generic polynomials $f(x)$, $\phi(x)$ 
of consecutive degrees, that I shall write 
in a factorized form: $f(x)=\prod_{a\in\A}(x\moins a):=R(x,\A)$, 
 $\phi(x)=\prod_{b\in\B}(x\moins b):=R(x,\B)$,
B\'ezout considered  quadratic expressions in the coefficients of $f,\phi$,
that he called \emph{\'Equations d\'eriv\'ees}. 
Following Cayley \cite{Cayley},
one may reinterpret his system of equations as the quadratic form
 $$  \Bez(\A,\B) := \frac{f(x)\phi(y) - f(y)\phi(x)}{x-y}  \ .$$
This form can be expanded in a unique manner~:
\begin{equation}
  \Bez(\A,\B) = \gamma_0\, r_0(x) r_0(y) 
      + \gamma_1\, r_1(x) r_1(y)+\cdots +\gamma_n\, r_n(x) r_n(y)\ ,
\end{equation}
with $f(x)$ of degree $n\plus 1$, $\phi(x)$ of degree $n$, 
requiring that the polynomials $r_i(x)$, $i=0,\ldots,n$ be monic of degree
$n\moins i$, $\gamma_0,\ldots, \gamma_n$ being normalizing constants.

Let us first recognize that the $r_i(x)$ are, up to scalars, the successive remainders
in the Euclidean division of $f$ by $\phi$. 

Indeed, the equations defining the remainders $\cR_i(x)$, putting 
$\cR_{-1}(x) =f(x)$, $\cR_0(x)=\phi(x)$, are
\begin{equation}
  \cR_{i-1}(x) = q_i(x) \cR_i(x)   - \cR_{i+1}(x) \ ,\ i=0,\ldots, n,\
              d^0(\cR_{i+1})\leq n\moins i\moins 1 \ , 
\end{equation}
or, equivalently,
\begin{equation}
  \cR_{i-1}(x)\, /\, \cR_{i}(x) = q_i(x) - \cR_{i+1}(x)\, /\, \cR_{i}(x) \ .
\end{equation}

Eliminating the remainders, one can write the Euclidean division
as a continued fraction:
\begin{equation}    \label{ConFrac}
 \frac{\phi(x)}{f(x)}\ =\
     \cfrac{ 1}{q_0 -
      \cfrac{1}{q_1 -
       \cfrac{1}{ \ddots}
        \cfrac{}{
        \cfrac{1}{q_n}}}}   
\end{equation}

Keeping on the contrary the remainders, and the top coefficients 
$\alpha_i$ of the quotients $q_i=\alpha_i x+\beta_i$,
one sees that there exists normalization constants $(\star)$
such that
$$ \frac{\cR_{-1}(x) \cR_0(y) -\cR_{-1}(y) \cR_0(x)}{
         (x\moins y) \cR_0(x)\cR_0(y)}  = 
   \alpha_0 -\frac{1}{ (\star) \cR_0(x) \cR_0(y)}  \ , $$
and therefore, by iteration, 
\begin{multline}
\frac{f(x)\phi(y) - f(y)\phi(x)}{x-y}  \\
 =  \alpha_0\, \cR_0(x)\cR_0(y) + \alpha_1\, \cR_1(x)\cR_1(y) +\cdots +
    +\alpha_n\, \cR_n(x)\cR_n(y)  
\end{multline}
 %  R_{n+1} est nul. On decompose $f$ en quotients, il y en a $n+1$  $q_0.. q_n$
is the required decomposition of the B\'ezoutian.

To recover not only the remainders, but also the 
\emph{convergents} of the continued fraction, 
one uses the remark that 
the B\'ezoutian be identical with its remainder modulo $f(x), f(y)$
(because it is of
degree at most $n$ in $x$, resp. in $y$).  However
$$ \cR_i(x) \equiv S_{i^i}(\AB -x)\, \phi(x)  \  \mod\ f(x)  \ ,$$
the Schur functions\footnote{
Recall that, given two alphabets $\A$, $\B$, the \emph{complete functions}
$S_i(\AB)$ are defined by the generating function:   
$$\sum_i  z^i S_i(\AB) =
 \frac{\prod_{b\in\B} 1-zb)}{\prod_{a\in \A}  1-za} \ . $$ 
\emph{Schur functions} are determinants in complete functions,
but it is appropriate to generalize the usual definition 
and allow different alphabets in the successive columns.
Given $\lambda \in \mathbb{N}^n$, given $2n$ sets
of variables $\A_1, \ldots, \A_n$, $\B_1,\ldots, \B_n$,
 then the Schur function 
$S_{\lambda}(\A_1\moins \B_1, \ldots, \A_n\moins \B_n)$ is equal to 
$ \bigl|S_{\lambda_j+j-i}(\A_j\moins \B_j)\bigr|_{1\leq i,j\leq n}. $\\
When alphabets are the same in consecutive columns, one does not repeat
them. For example, one writes
 $S_\lambda(\AB)$ when the argument is $\AB$
in all columns. Adding a letter $x$ to an alphabet $\A$
is denoted $\A\to \A\plus x$, and $\A -\B\moins x$ stands for
$\A-(\B\plus x)$. More informations may be found in \cite{LaCbms}.
} 
 $S_{i^i}(\AB -x)$  being Euler's multiplicators\footnote{
Euler writes a remainder in the division of $R(x,\B)$ by 
 $R(x,\A)$  as a combination 
$A(x)\, R(x,\A) + B(x)\, R(x,\B)$, the coefficients $A(x)$, $B(x)$ 
being polynomials of the smallest possible degree.
Explicitely, for $|\A|=\alpha$, $|\B|=\beta $, the $k$-th remainder 
can be written 
$$ \cR_k  = (\moins 1)^{\alpha-k+1} 
S_{(\beta\moins \alpha \plus k)^{k-1}}(\AB\moins x) \, R(x,\B)   
   +  S_{k^{\beta-\alpha + k-1}}(\B\moins\A\moins x)\,  R(x,\A)\, .  $$
}
 for the remainders.

Consequently, one can write
\begin{multline}
   \Bez(\A,\B)  = \phi(x)\phi(y)\, 
      \Bigl( (\star) S_0 S_0 + (\star) S_1(\AB -x) S_1(\AB -y)  \\
     + (\star) S_{22}(\AB -x)S_{22}(\AB -y) +\cdots\\
        + (\star) S_{n^n}(\AB -x) S_{n^n}(\AB -y)  \Bigr)\ ,   
\end{multline} 
with some normalizing constants denoted $(\star)$~. 

We are now in the world of orthogonal polynomials, 
the polynomials $1,S_1(\AB-x),\ldots,
 S_{n^n}(\AB -x)$ being the 
 unique\footnote{up to normalization} orthogonal basis
$P_k(x)$, $k=0,\ldots,n$, $d^0(P_k)=k$, with respect to the functional
$$ g(x) \longrightarrow  \sum_{a\in\A}  g(a) \frac{\phi(a)}{R(a,\A-a)}  \ .$$

Indeed, this functional is an avatar of the 
Lagrange interpolation in the points
$a\in\A$. It is characterized by the fact that it sends each 
$x^i$, $i\in \N$, onto the complete function $S^i(\AB)$ 
(which should be considered
as the \emph{$i$-th moment}). 

Therefore, it sends $S_{k^k}(\AB-x)x^i = S_{k^k;\, i}(\AB;\, x)$ onto
$S_{k^k;\, i}(\AB;\, \AB)$. When $i<k$, this last determinant vanishes,
having two identical columns. In other words, the polynomial
$P_k=S_{k^k}(\AB-x)$ is orthogonal to $x^0,\ldots, x^{k-1}$. 

Thus, the decomposition of the B\'ezoutian becomes
\begin{equation}
\Bez(\A,\B)  = \phi(x)\phi(y)\,
\Bigl( 1+ (\star) P_1(x) P_1(y)+ \cdots +(\star)  P_n(x) P_n(y)      \Bigr)  \ ,
\end{equation}
and inside the parenthesis, one recognizes the Christoffel-Darboux 
reproducing kernel\footnote{the image of $g(x)K(x,y)$ under the functional
is $g(y)$, if $g$ is of degree $\leq n$, and $K(x,y)$ is the kernel.}.

It is well known, in fact, that the denominators $\cD_i(x)$ of the 
convergents of the continued fraction (\ref{ConFrac}):
\begin{equation}    \label{ConFrac2}
\frac{N_i(x)}{D_i(x)}\  :=\ 
     \cfrac{ 1}{q_0 -
      \cfrac{1}{q_1 -
       \cfrac{1}{ \ddots}
        \cfrac{}{
        \cfrac{1}{q_i}}}}   \quad ,\quad i\leq n\, , 
\end{equation}
may be interpreted as orthogonal polynomials.  

One recovers this fact by noticing that the denominators satisfy
the recursions
\begin{equation}    \cD_{i-1} = q_i \cD_i  - \cD_{i+1} \ ,\ i=0,\ldots, n\ ,
\end{equation}
with initial conditions $\cD_0=1$, $\cD_1=q_1$  (or equivalently
$\cD_{-1}=0$, $\cD_0=1$). 
These are the same equations as for the remainders,
the initial conditions for  the remainders
being multiplied by $\phi(x)$, compared to those for the $\cD_i$'s. 
This time, recursions provide a sequence of polynomials of increasing
degrees, instead of decreasing degrees in the case of remainders.

In final, one has verified again that 
\begin{equation} \cR_i(x)  \equiv \phi(x) \cD_i(x) \ 
       \mod \ f(x),\ i=0,\ldots, n\ . 
\end{equation}

Let us now trace back related formulas in the classical literature.

For example, in his study of \emph{Sturm sequences}
(this is the case where $n \phi(x)$
is the derivative of $f(x)$), 
Sylvester stated without proof the vanishing of the 
following  determinant~: 
$$ \Bigl|   D_i(a_j)^2  \Bigr|_{0\leq i ,j\leq n}  \ ,   $$
where $a_0,\ldots, a_n$ are the roots of $f(x)$ 
(and thus are the letters of the
alphabet $\A$), and $D_0 =1$.  

In other words, Sylvester stated that there exists constants $c_i$ such that
the $n\plus 1$ following equations are satisfied~:
\begin{equation}
  c_0 + c_1 D_1(a)^2+ \cdots + D_n(a)^2  = 0  \quad \forall a\in \A \ .
\end{equation}

But this comes from the expression of 
the specializations  $x=y=a\in\A$ of the Bezoutian, 
divided by $\phi(a)^2= f'(a)^2/n^2$~:
\begin{multline}
 \Bez(\A,\B)\Big|_{x=y=a} =  f'(a)\phi(a)/\phi(a)^2 = n \\ 
        = (\star) +(\star) D_1(a)^2 + \cdots + (\star) D_n(a)^2 
\end{multline}

Brioschi generalized Sylvester's relation to an 
arbitrary $\phi(x)$ of degree $n\moins 1$. One still has the vanishing of the determinant  
 $$ \Bigl|   D_i(a_j)^2  \Bigr|_{0\leq i,j\leq n}  \ ,   $$
where $a_0,\ldots, a_n$ are still the roots of $f(x)$,
and $D_0(x)$ is now equal to 
$$  D_0(x) = 1 - \frac{ f'(x)}{\phi(x)}   \  .   $$ 

Orthogonality properties have also been obtained by Brioschi, though he states
them only for two consecutive remainders in \cite{Brioschi1}. 

\begin{proposition}
Let $r_0,r_1,\ldots, r_{n-1}$ be the successive remainders in the division of
$f(x)= S^n(\xA)$ by $\phi(x)=S^{n-1}(\xB)$. Then, for any 
$k,j:\, 0\leq k <\leq j\leq n\moins 1$, 
one has the nullities    
\begin{equation}
  \sum_{a\in\A}   r_k(a) r_j(a) \frac{1}{\phi(a) R(a,\A\moins a)} = 0  \ .   
\end{equation}
\end{proposition}

Indeed, writing $r_k(a) = \phi(a) D_k(a)$, one recognizes the scalar product 
of the two orthogonal polynomials $D_k(x), D_j(x)$~:
\begin{equation}
  \sum_{a\in\A}   D_k(a) D_j(a) \frac{\phi(a)}{ R(a,\A\moins a)}   \ .
\end{equation}

However, in the article \cite{Brioschi2}, in the case where $\phi(x)=f'(x)/n$, 
Brioschi gives the following nullities~: 
\begin{equation}
    \sum_{a\in\A}   x^k D_j(a)  =0  \quad  0\leq k<j \leq n\moins 1 
\end{equation}

The functional looks different, because the term 
$\phi(a)/R(a,\A\moins a)= \phi(a)/f'(a)=1/n$
can be erased.

Notice that 
$$ f'(x)/f(x) =  \sum_{a\in\A}  \frac{1}{x-a} \ , $$
so that the case treated by Sylvester and Brioschi is the case of orthogonal
polynomials for a discrete  measure, in  relation with Lagrange
interpolation. As a matter of fact, it was also the starting point of Tchebychef.
Taking a more general $\phi(x)$ of degree $n\moins 1$, one has similarly
$$ \frac{\phi(x)}{f(x)}=   \sum_{a\in\A}  \phi(a)\, 
            \frac{R(x,\A\moins a)}{R(a,\A\moins a)}  \ ,  $$
thanks to Lagrange interpolation, and this time the weights are no
more the ``Lagrange weights'' $1/{R(a,\A\moins a)}$, 
but $\phi(a)/{R(a,\A\moins a)}$, and 
 still concentrated in the points of $\A$. 

Starting with two polynomials $f(x)$, $\phi(x)$ of the same degree $n$, 
one may homogeneize them, introducing an extra variable $y$,
 and use the Jacobian of $f$ and $\phi$.

 Sylvester obtained that there exists constants $c_1,\ldots, c_n$ such that~:
\begin{equation}
  \frac{1}{n} Jacobian(f,\phi)\Bigr|_{y=x}  = 
   \frac{ \cR_1(x)^2}{c_1}  + \cdots + \frac{ \cR_n(x)^2}{c_1\cdots c_n}  \ ,
\end{equation} 
where $\cR_1=\phi(x),\ldots, \cR_n$ are the successive remainders in the
division of $f(x)$ by $\phi(x)$.

Once more, this is a decomposition of the Christoffel-Darboux kernel
for $x=y$. We are back to our starting point,
which is also the one of Hermite \cite{Hermite}, 
the decomposition of quadratic forms.



\begin{thebibliography}{1}
\bibitem{Brioschi1} Brioschi. \emph{Th\'eorie des d\'eterminants},
 appendix to the French edition, Paris, Mallet-Bachelier (1856).

\bibitem{Brioschi2} Brioschi. \emph{Sur les fonctions de Sturm},
                         Nouvelles Annales 13 (1854) 71--80

\bibitem{Cayley} A. Cayley.
\emph{ Note sur la m\'ethode d'\'elimination de B\'ezout},
     Crelle J. {\bf 53} (1857) 366-367.

\bibitem{Hermite} C. Hermite.
\emph{Oeuvres}, ed. E. Picard, Gauthier-Villars , Paris (1908).

\bibitem{LaCbms} A. Lascoux. \emph{Symmetric Functions \& 
Combinatorial Operators on Polynomials}, CBMS-AMS Lecture Notes (2003).

\bibitem{Tchebychef} P. Tchebychef.
\emph{Oeuvres}, Chelsea reprints.
 
\bibitem{Sylvester53} J.J. Sylvester.
\emph{ A theory of the syzygetic relations of two rational integral
functions}, Phil. Trans. Royal Soc. London vol CXLIII, Part III (1853) 407--548.
\end{thebibliography}


  
\end{document}
