
%%  Rota_Maratea_txt    29 mai 2000 
%
%
\documentclass[a4paper,12pt]{article}
\usepackage{amsmath,amsfonts,amsthm}

\begin{document}
\title{Alphabet splitting\\
{\small\it Some comments about the mathematical work of}\\
{\small\bf  GIAN-CARLO ROTA}}

\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  Alain.Lascoux@univ-mlv.fr }

\date{}
\maketitle

\def\s{\scriptstyle }
\def\a{\alpha}
\def\b{\beta}
\def\l{\lambda}
\def\L{\Lambda}
\def\e{\epsilon}
\def\ss{\sigma}
\def\d{\partial}
\def\P{\psi}
\def\bu{$\bullet$\quad}

\def\S{{\mathfrak S}}
\def\Sym{{\mathfrak Sym}}


\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\A{{\mathbb A}}
\def\B{{\mathbb B}}
\def\C{{\mathbb C}}

\catcode`\@=11
\def\petitematrice#1{\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\thinspace  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}}

\def\moyennematrice#1{\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\   \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}}

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

\begin{abstract}
 We stress the importance of addition (of alphabets)
in the mathematical work of Gian-Carlo Rota, in particular
as concerns his "Finite Operator Calculus". 
\end{abstract}

I met Gian-Carlo in 1976, landing in MIT 
trying to establish Western connections. I was already working with 
Marcel-Paul Sch\"utzenberger who was one of his great friends
and I needed no further introduction.  Moreover, the few dollars 
that I had in my pocket were forcing me to eat fast, and this 
was contrary to Gian-Carlo's sense of hospitality. The outcome
was that I appeared several times on his list of professional expenses 
(section: restaurants). 
It was still an epoch where tax inspectors readily accepted 
to support combinatorics. This is no longer the case since combinatorics 
received the imprimatur 
of the  Bourbaki Seminar. 
 Let me however point out that meals were followed by long discussions
about the comparative merits of algebraic structures, Gian Carlo 
for his part tirelessly
asking me to repeat the definition of $\l$-rings that he copied 
each time in his
black  notebook with a new illustrative example.


Gian-Carlo thought of himself as an epigraphist of the richess of the past
and an advocate of the algebraic structures which permit 
to integrate them in the up-to-date research. 

For example, the inclusion-exclusion principle leads to the study of
ordered structures and to their Moebius function. Invariant theory 
opens onto umbral calculus, differential calculus has a discrete
couterpart, etc. 

However, it does not suffice to highlight algebraic structures
to give them life, one has furthermore to market them. 
This entails showing that the energy spent for learning them is 
compensated by a new light shed  on classical domains, connections between 
different fields and the creation of new mathematical objects -- one cannot
always grind the same grain, one also has to sow!

Umbral calculus \cite{R1}, 
 Moebius functions \cite{R2},  Hopf algebras \cite{R7}, 
 Baxter algebras  \cite{R4}, etc., 
all of them can be phrased in a few words.

For example, umbral calculus is the art of raising indices and lowering 
exponents, Moebius inversion consists of inverting triangular matrices
with unit diagonals, and so on.

But these notions are not as straightforward as it seems at first glance.
How to compute on ordered sets when one cannot represent them and experiment
on them as soon as they become voluminous enough? Even in the case of 
such a classical object as the symmetric group, though one can describe
its Moebius function (with respect to the Ehresmann-Bruhat order), 
one does not know much about its intervals. One conjecture that
Kazhdan-Lusztig depends only on the isomorphim type of the interval, 
but one does not know how to compute 
these polynomials in general, though they are
the first level in the description of intervals. 

As concerns raising indices, nothing prevents us from doing so, but 
one wants to do it {\it without loss of information}.

It is clear, for example, that in a linear identity one is allowed to replace
$a_i$, $i=1,2\ldots$ by $a^1, a^2, \ldots$, supposing that 
$a$ is an indeterminate or a transcendental element.  But why is it 
that inside {\it straightening} relations, so dear to Rota \cite{R9},
between minors of matrices,  one can restrict to Vandermonde matrices
$$\left[ \moyennematrice{ a^1 & a^2 & a^3 &\cdots \cr
 b^1 & b^2 & b^3 &\cdots\cr  \cdot & \cdot &\cdot &\cdots }\right] $$
instead of having to take a generic one  
 $$\left[  \moyennematrice{ a_1 & a_2 & a_3 &\cdots \cr
 b_1 & b_2 & b_3 &\cdots\cr  \cdot & \cdot &\cdot &\cdots }\right] \quad  ? $$

Umbral calculus rules are simple, but it is far less elementary 
to determine the limits of their domain of validity \cite{R11}.
I shall accost this territory through the simplest way I know,
that is, addition.

Addition of what? Addition of alphabets, i.e. a disjoint union of sets of
indeterminates:
$$ \left( \A=\{ a\} \ , \ \B= \{ b\} \right)\quad  
\mapsto \quad \A+ \B:= \{ a\} \cup  \{ b\}  \ .  $$

Restrict for the moment to finite sets. Taking an extra indeterminate $z$,
one can write generating functions
\begin{equation}
 \l_z(\A) := \prod_{a\in \A} (1 +za) \quad , \quad 
 \ss_z(\A):=  \prod_{a\in \A}  {\frac{1}{1-za}} .
\end{equation}
the expansion of which defines  {\it complete functions } 
$S^i(\A)$ and {\it elementary functions} $\L^i(\A)$
\begin{equation}
 \l_z(\A) =\sum z^i\, \L^i(\A)  \quad  , \quad 
 \ss(\A) = \sum z^i\, S^i(\A)  \ .
\end{equation}
Addition of alphabets translate into product of generating functions
\begin{equation}
 \l_z(\A+\B)= \l_z(\A)\, \l_z(\B) \quad ,
\quad \ss_z(\A+\B)=  \ss_z(\A)\,  \ss_z(\B) \ . 
\end{equation}
One also needs  {\it power sums} $\psi_i$:
\begin{equation}
\psi_i(\A)=\sum_{a\in \A} a^i \quad , \quad
\sum_{i=1}^\infty \psi_i(\A)\frac{z^i}{ i} =\log( \ss_z(\A)) \ . 
\end{equation}

However, having learnt addition, one knows how to multiply 
by a positive integer
$$ \A=\{ a\}  \rightarrow 2\A := \{ a' \} \cup \{ a''\} \quad , \quad
  3\A := \{ a' \} \cup \{ a''\} \cup \{ a'''\} \ , \  \ldots $$
that is, one knows how to double, triple, ..., 
 each letter ( erasing the diacritic signs
at the final stage)
$$ \l_z(2\A) = \l_z(\A)^2 \quad , \quad \l_z(3\A) = \l_z(\A)^3 \ldots $$

These tools are sufficient to invert formal series
$f(z) = z + f_1z^2 +f_2z^3 + \cdots$, that is, to find  
$g(z) = z + g_1z^2 + g_2z^3 + \cdots$ such that 
$$f(g(z)) =z  \quad \& \quad g(f(z))=z \ .$$
This problem has been solved by Lagrange, and it involves 
calculating successive derivatives of powers of $f$, 
which operations are easily expressed in terms of alphabets.

Indeed, writing $f$ as $f= z\ss_{-z}(\A)$ (every formal series 
factorizes formally!), one finds that the powers of $g$ are
\begin{equation}
 g^k(z) = k\, z^k \sum \frac{z^i}{i+k}\, \L^i\bigl( (i+k)\A \bigr) \ , 
\end{equation}
and only require multiplication of alphabets by integers
if $k\in\Z$ (formulae are still valid for $k\in\C$; the limit
case $k=0$ gives the logarithm).

The theory of symmetric functions gives, for every choice of pairs
of adjoint bases (with respect to the natural scalar product)
an expansion of $\L^i((i+k)\A)$ in terms of the coefficients of $f$
or $1/f$. The  expansions below appear in the classical litterature,
many mathematicians having desired to leave their own interpretation
of Lagrange inversion. We refer to Vincent Prosper's thesis \cite{Pr1} 
and to its implementation \cite{Pr2}. 

In short, the compact notation $\L^i( (i+k)\A)$ 
{\it contains} the following formulae (see the comments about symmetric
functions at the end)~:
\begin{equation}
\begin{matrix}
 \L^i((i+k)\A) &= &(-1)^i\sum\nolimits_{|J|=i} \P_J(-(i+k))S^J( \A) & (a)\\
&= &\sum\nolimits_{|J|=i}\P_J(i+k)\L^J( \A) & (b) \\
&=  &\sum\nolimits_{|J|=i}S_J(i+k)S_{J^\sim}( \A) &(c)  \\
&= &\sum\nolimits_{|J|=i}\L^J(i+k)\P_J( \A) &(d) \\
&= &(-1)^{i}
 \sum_{|J|=i}  \frac{(-i-k)^{\ell(J)}}{m_1!m_2!\cdots}
  (\frac{\P_1}{1})^{m_1}  (\frac{\P_2}{2})^{m_2}  
  (\frac{\P_3}{3})^{m_3} \cdots
& (e) \\ 
\end{matrix}
\end{equation}
are the expansion in terms of the basis of products of complete functions $S^J$,
products of elementary functions $\L^J$, Schur functions $S_J$, 
monomial functions $\P_J$, products of power sums  $\P^J$,
noting in $(6e)$ the partitions exponentially:
$J=1^{m_1} 2^{m_2}\cdots$. 

Let us stress once more that all these expansions are a consequence 
of the operation $\A \rightarrow k\, \A$, using (1),...,(4).

\smallskip
Let us go back to Gian-Carlo's opus. I say that the fundamental 
article "Finite Operator Calculus" [R1] 
rests upon Lagrange inversion, 
and eventually, upon multiplication of alphabets by integers.

To state the problem in a few words~: one wants to deform the derivative 
$$ D:= \frac{d}{dx} \rightarrow Q= D +a_1D^2+a_2D^2+\cdots $$
while preserving properties like the existence of a distinguished basis
$\{ x^n\} : D x^n= nx^{n-1}$, Taylor formula, etc., in other words,
the tools of classical analysis in one variable.

Let us introduce an alphabet $A$ (which will remain formal) and write 
\begin{equation}
 Q = D\, \ss_{-D}(\A) = D - S^1(\A)D^2 +S^2(\A)D^2 -S^3(\A)D^3
 +\cdots 
\end{equation}
One wants polynomials 
$P_n$, $n=1,2\ldots$, $P_0:=1$, such that
\begin{equation}
 Q(P_n) = n P_{n-1} \quad \&\quad  P_n(0) =0 \ , \ n\geq 1 \ . 
\end{equation}
Rota's theorem (\cite{R5}, th. 4), is
\begin{equation}
 P_n = x\, \l_D(n\A)\, x^{n-1}\quad ,\quad  \ n\geq 1 \ . 
\end{equation}

\begin{proof}   $f'$ being the derivative of a function $f(x)$ of  $x$,
one has 
$f(D) x = x\, f(D) + f'(D)$.
Taking  $f$ such that $f(D) =\l_D(-\A)$, one has $Q= D\,f =f\, D$ and
$$Q\, P_n= f\, DP_n= f\, D x f^{-n}\, x^{n-1} $$
$$= f\, f^{-n}\, x^{n-1} + fx\, Df^{-n} x^{n-1} \qquad
=  f^{-n+1 }\, x x^{n-2} + f x f^{-n} D x^{n-1} $$
$$ =(1-n)f'\,  f^{-n}\, x^{n-2} + x f^{-n+1} x^{n-2} +
xf'\,   f^{-n}\, (n-1) x^{n-2}+ x f^{-n+1} (n-1) x^{n-2}$$
$$= n\, P_{n-1} $$
\end{proof}

Rota's theorem has many corollaries which are  extensions of classical
analysis

\noindent \bu existence of a reproducing kernel 
\begin{equation}
\sum \frac{P_n(y)}{n!}\, Q^n(f(x)) = f(x+y) \ , 
\end{equation}
\bu existence of a  Cauchy formula 
\begin{equation}
\sum \frac{P_n(y)}{n!}\, x^n\ss_{-x}(n\A) = \exp(xy) \ , 
\end{equation}
\bu existence of a binomiality property
\begin{equation}
 P_n(x+y) = \sum \binom{n}{i} P_i(x) P_{n-i}(y) \ .
\end{equation}
These formulae can be interpreted as a result of replacing the
usual exponential by $\sum x^n P_n(x)/n!$.
They may appear much more surprising once specialized.

For example, let  $Q=D(1-D)$, i.e. $\A$ is such that $S^1(\A)=1$,
 $S^i(\A)=0$, $i>1$.  Then $\L^i(n\A) = \binom{n+i-1}{i}$, 
\begin{equation}
 P_n = \sum \frac{(n-i)\cdots(n+i-1)}{i!}\ x^{n-i} \ ,
\end{equation}
and Cauchy formula gives the expansion of $\exp$ 
\begin{equation}
 \exp(xy) = \sum \frac{P_n(y)}{n!}\, x^n\, (1-x)^n 
\end{equation} 
used by Schur \cite{Schur}  to compute $\sin(\pi x)$. 

 {\it Abel polynomials} occur for 
$$ Q= D+ aD^2/1! + a^2D^3/2!+\cdots\ , $$
that is for $Q$ such thate $Q(f(x))= \frac{d}{ dx} f(x+a)$.  

The corresponding \lq\lq Abel alphabet" is such that 
 $S^i(\A)=(-a)^i/i!$, $\L^i(n\A) = S^i(n\A) = (-na)^i/i!$, and finally
\begin{equation}
P_n(x) =x\, (x-na)^{n-1} \ . 
\end{equation}
In this case, power sums are simpler since~:
$$ \psi_1(n\A) = -na \quad \& \quad    \psi_i(n\A) =0 \ ,\, i>1 \ .$$
One may notice that dimensions 
$dim(J)$, $J$ partition, of representations of the symmetric group
are given by the specialization $S^i(\A)=1/i!$. Determinants in the
$S^i(n\A)$ can therefore be computed in terms of these dimensions
(for which one has many combinatorial interpretations). 
For example, the evaluation of Schur functions in a multiple of
Abel alphabet, 
for $J=[j_1,\ldots,j_n]$, $0\leq j_1 \leq 
\leq \cdots \leq j_n$, is~: 
$$ S_J(n\A) = \frac{(-a\, n)^{|J|}}{|J|!} \, dim(J) =
(-a\, n)^{|J|} \det\left| \frac{1}{ (j_i+k-i)!} \right|_{1\leq i,k\leq n}
 \ .$$


As a last example of deforming the derivative, leading to 
the Bernoulli numbers:
\begin{equation}
 Q =D \frac{D}{\exp(D) -1} = D\, (1- \frac{1}{2}D +\frac{B_2}{2!} D^2 
+\frac{B_4}{4!} D^4 + \cdots ) 
\end{equation}
Thus  
$$ S^i(\A) = B_i/i! \quad \& \quad \L^i(\A)= (-1)^i/(i+1)! \quad ,\quad i\geq
0 \ .$$
The elementary functions are the same as in Abel's case (for $a=1$),
up to a shift of indices which has consequences, 
which (in medical terminology) are termed drastic:
\begin{equation}
 P_n(x) = x \left(\frac{\exp(D)-1}{ D} \right)^n\, x^{n-1} =
   x(1+D/2! +D^2/3!+\cdots)^n\, x^{n-1} \ . 
\end{equation}

Compact notations for coefficients of powers of series
ease computations. Moreover, since these notations
refer to the symmetric functions, they permit to benefit
from the full machinery   that one can 
find in such good treatises of symmetric functions as \cite{Ma}, see also 
\cite{LS2}.

In the present case of the  Bernoulli alphabet, the identity
$ \frac{d}{dx}\exp(x) = \exp(x)$ implies
 $\psi_i(\A) = -S^i(A) \ \forall i>1$, and
therefore the Newton relations between complete functions $S^i$  and
power sums $\psi_k$ 
$$ nS^n= \psi_1 S^{n-1} + \psi_2 S^{n-2}+\cdots \psi_n S^{0} $$
give the following recursion (Gessel told me that this is 
classical)
\begin{equation}
 -(n+1)S^n(\A)= \frac{-n-1}{ n!} B_n= S_2(\A) S_{n-2}(\A) +
    S_4(\A) S_{n-4}(\A) + \cdots + S_{n-2}(\A) S_2(\A) \ . 
\end{equation}

One can compare the underlying algorithm to the one 
of Miss  
Augusta Adda,  Lovelace countess, 
\begin{equation}
\frac{2x-1}{2( 2x+1) } = B_2 \frac{2x}{2!} +  B_4 
\frac{2x(2x-1)(2x-2)}{4!} +  B_6 \frac{2x\cdots (2x-4)}{6!} +\cdots 
\end{equation}

To close this chapter on Bernoulli numbers, may I express them in
terms of Schubert polynomials  \cite{LS1} specialized in 
$x_1=x_2=\cdots =1$ ? For example,
\begin{equation}
 (-1)^{n-1} B_{2n}=\frac{ Y_{[ 2, (3,0)^{n-1}]}}{2^n (n-1)! (2^{2n}-1)  }
= \frac{  n\, Y_{ [1, (2,0)^{n-1}]}}{2^{2n}  (2^{2n}-1)  } 
\end{equation}
 $$B_{12}= Y_{[2,3,0,3,0,3,0,3,0,3]}\, \frac{1}{31449600} = 
Y_{[1,2,0,2,0,2,0,2,0,2]}\,  \frac{1}{1397760} \ .$$
One can reduce the determinants expressing the above 
Schubert polynomials, and finally one obtain Bernoulli numbers
as minors of Pascal matrix 
$\left| \binom{i}{2j-i}\right|$, up to factors  $2\times (2^{2n}-1)$.
For example, for $n=6$, the product of $B_{12} = -\frac{691}{2730}$
by $2\times (2^{2n}-1)$ (= 8190), is equal to the determinant (=2073)
of the following matrix (writing `$\cdot$` for `$0$`, 
the full shifted Pascal matrix from which it is extracted being written
on the right)~:
$$\left[ \moyennematrice{1& 1& \cdot& \cdot& \cdot& \cdot\cr \cdot& 
1& 1& \cdot& \cdot& \cdot\cr \cdot& \cdot&
3& 1& \cdot& \cdot\cr \cdot& \cdot& 1& 6& 1& \cdot\cr \cdot& \cdot& \cdot& 
5& 10& 1\cr \cdot& \cdot& \cdot& 1& 15& 15} \right]
\leftarrow \quad
\left[ \moyennematrice{
1& 1& \cdot& \cdot& \cdot& \cdot & \cdot& \cdot& \cdot &\cdot\cr
\cdot& 1& 2 &1& \cdot& \cdot& \cdot & \cdot& \cdot &\cdot\cr
\cdot& \cdot&
          1&3&3& 1& \cdot& \cdot&\cdot&\cdot\cr
\cdot& \cdot&\cdot&
      1&4& 6&4& 1& \cdot&\cdot \cr
\cdot& \cdot& \cdot&\cdot &
1&5& 10& 10&5&1\cr
\cdot& \cdot& \cdot&\cdot&\cdot& 1&6& 15&20& 15} \right]
$$

\medskip
Combinatorists tirelessly point out that they practised $q$-calculus 
long before specialists of quantum groups took it over.

They introduced a {\it $q$-derivative} $D_q: f\mapsto 
\frac{ f(qx) -f(x)}{qx-x}$. In the like manner as before, it can be
deformed
\begin{equation}
 D_q \mapsto Q= D_q \ss_{-D_q}(\A) =  
 D_q - S^1(\A)D_q^2 +S^2(\A)D_q^2 -S^3(\A)D_q^3
 +\cdots 
\end{equation}
Since $D_q(x^n) = [n]\, x^{n-1}$, with $[n]:= 1+q+\cdots + q^{n-1}$, 
one looks for polynomials  $P_n^q$ such that 
\begin{equation}
 Q(P_n^q) = [n] P_{n-1}^q \quad \&\quad  P_n^q(0) =0 \ , \ n\geq 1 \ . 
\end{equation}

Actually one has to replace  the relation $P_n= x\l_D(n\A) x^{n-1}$ 
by an equivalent one to be able to  $q$-ify it, and one finds 
\begin{equation}
 P_n^q=  \left( 1 +\sum (n-|J|)
\frac{(n-1)\cdots (n-\ell(J) +1)}{\prod m_i!} \L^J(\A)\, D_q^{|J|} 
\right) \, x^n \ , 
\end{equation}
sum over all  partitions $J \neq 0$, $J=1^{m_1} 2^{m_2}
3^{m_3}\cdots$,  $\ell(J)= m_1+m_2+\cdots$, $|J|=m_1+2m_2+3m_3+\cdots$,
with $\L^J:= (\L^1)^{m_1} (\L^2)^{m_2}(\L^3)^{m_3} \cdots $.

The $q$-integers only appear in the action of $D_q$ and not in the 
coefficients of the powers of $D_q$.  Since  $P_n^q$ is obtained from
 $x^n$ and not  $x^{n-1}$, formula (23) is not a straightforward 
consequence of (9).  For more about extensions of the umbral calculus,
see \cite{Ro}. 

I now have  to argue that addition and multiplication by integers 
do not cover all of mathematics.
Indeed, one must have recourse to rational numbers, or even complex numbers.

To state it differently: we met the doubling of alphabets 
$\A=\{ a\}  \mapsto 2\A := \{ a' \} \cup \{ a''\}$,
but the inverse opration is required :
$$ \A\mapsto \frac{1}{2}\A = \B \quad , \quad \B = \{ b \} \mapsto 
\{ b' \} \cup \{ b''\} = \A \ . $$
Realizing that at the level of  power sums one has :
$$ \psi_i(2\A) = \sum (a')^i + \sum (a'')^i = 2\psi_i(\A) \ , $$
one realizes that $\B=k\, \A$, $k\in \C$ can be defined by
the equations
\begin{equation}
 \psi_i(\B) := k\, \psi_i(\A) \ , \ i\geq 1 \ .
\end{equation}

It is however more illuminating to discover that every polynomial
can play the r\^ole of an alphabet, that is, power sums $\psi_i$
are operators on the ring of polynomials ( $\a\in \C$, $u$ monomial):
\begin{equation}
 P= \sum_{\a,u} \a\, u \Rightarrow \psi_i(P) = \sum_{\a,u} \a\, u^i
\ . 
\end{equation}
The ring of symmetric polynomials $\Sym$  being generated by the 
 $\psi_i$, $i=1,2,\ldots$, formula (25) transforms 
any symmetric polynomial into an operator on the ring of polynomials.
Thus, the generating functions of the operators $\L^i$ or $S^i$ are
\begin{equation}
 P= \sum_{\a,u} \a\, u \mapsto \l_z(P) = \prod (1+zu)^\a \ ,
\end{equation}
\begin{equation}
 P= \sum_{\a,u} \a\, u \mapsto
\ss_z(P)= \prod (1-zu)^{-\a} \ .   
\end{equation}
Each formula (25), (26), (27), at one wishes, characterizes the structure of 
 $\l$-ring of the ring of polynomials. Grothendieck had choosen 
 {\it lambda operations}, that is the  {\it exterior powers} 
$\L^i$ of classes of vector bundles, 
the $S^i$'s being the {\it symmetric powers}. 
Algebraic topologists, for their part, prefer 
 {\it Adams operations} $\psi_i$ (see at the end some remarks about
$\l$-rings).

Notice the different r\^oles played by constants $\a$ and
monomials $u$:
\begin{equation} \left\{   
\begin{matrix}  
\psi_i(\a) =\a \; , &S^i(\a) = \binom{\a+i-1}{i} \; , 
&\L^i(\a) = \binom{\a}{i} \\ 
\psi_i(u) =u^i \; , &S^i(u) =u ^i \; ,  &\L^i(u) = 0,\, i>1, &\L^1(u) =u
\\ 
\end{matrix} \right. 
\end{equation}

Computers cannot distinguish indeterminates  $\a$ from monomials $u$.
It is more correct to characterize \lq\lq monomials" as {\it 
rank 1 elements} (i.e. elements $x\neq 0$ such that $\L^i(x) = 0 \ \forall
i>1$), and \lq\lq constants" as elements invariant under all the 
$\psi_i$'s (Rota \cite{R5} called them {\it elements of binomial type}). 

It is appropriate not to restrict to polynomials, but go to rational
functions or formal series, keeping the definition
\begin{equation} \psi_i \left( \frac{\sum \a u}{\sum \b v}\right) = 
  \frac{\sum \a u^i}{\sum \b v^i}  \ , 
\end{equation}
with summations  finite or not.

With some precautions, one can just as well use 
\lq\lq Laurent monomials" with exponents in $\Z$ rather than in $\N$.

If $q$ is a rank 1 element, one can now write  
$\frac{1}{ 1-q}= 1+q+q^2+\cdots$, i.e. $\frac{1}{1-q}$
is the infinite alphabet $\{ 1,q,q^2,\ldots\}$ and
$\psi_i( \frac{1}{1-q}) = \frac{1}{1-q^i}$, $i\geq 1$. 
By the way,  we learn from Cauchy that :
\begin{equation} S_i(\frac{1}{1-q})= \frac{1}{(1-q)\cdots (1-q^i)}  
\end{equation}
and therefore 
\begin{equation}\ss_x(\frac{1}{ 1-q}) =\sum \frac{x^i}{(1-q)\cdots (1-q^i)} 
\end{equation}
is the $q$-exponential, the equality $\frac{1}{1-q}= 1+q+q^2+\cdots$
leading to the factorization 
\begin{equation}\ss_x(\frac{1}{1-q}) =\prod_{i=1}^\infty  \frac{1}{1-xq^i}  
\end{equation}
which turns the $q$-exponential into an object rather easier to
manipulate than the classical exponential \cite{R6}.

Combining elements of different types in a $\l$-ring, one can 
cover  various expansions  with the \lq\lq $+$" symbol. 
Let for example $x$ be of  binomial type, $q$ be of rank 1, and 
 $y$ be such that $y(1-q)$ 
is of rank 1.  $q$-Charlier polynomials are defined by : 
\begin{equation} Ch_n(x) := n!\, \L^n(x-y)   \ . 
\end{equation}
To get their explicit expression, it is preferable to introduce 
 $z:=y(1-q)$. By combining  (3), (28), (30), it  follows that 
$$\L^n(x-\frac{z}{1-q})= \sum \L^{n-i}(x) \L^i(\frac{-z}{1-q}) = 
\sum \L^{n-i}(x) (-z)^i S^i(\frac{1}{1-q}) $$
\begin{equation} 
Ch_n(x)= n! \sum \frac{x\cdots (x-n+i+1)}{(n-i)!} 
\frac{ (-y)^i (1-q)^i}{(1-q)\cdots (1-q^i)} \ , 
\end{equation}
For $y=1$, $q\rightarrow 1$, one recover the clasical polynomials
 (Rota \cite{R1}, p.64).

We can now go back to the umbral calculus, having in mind that 
several lifts are possible for $a_i$~:
$$ a_i \mapsto S_i(\A)\ ,\ a_i \mapsto \psi_i(\A)  \ ,\ 
a_i \mapsto i! S_i(\A) \ , \ \ldots $$
This is where  $\l$-wisdom is not enough, and some help is needed
to allow experimentation as with ACE \cite{AV},
and its library SFA \cite{Pr2} devoted to $\l$-rings.

Let us take for example the identity
\begin{equation} \exp(bx) = \sum \frac{b(ak+b)^{k-1}}{k!} (x\exp(-ax))^k \ , 
\end{equation}
that Riordan \cite{Ri} gives as an application of
Lagrange inversion.
How should we interpret it in a $\l$-ring ? One can introduce two alphabets 
$\A$, $\B$, replace $\exp(ax)$ by $\ss_x(\A)$, $\exp(bx)$ by $\ss_x(\B)$
and look for the coefficients $c_k$ of the expansion 
\begin{equation} \ss_x(\B) = \sum c_k (\frac{x}{\ss_x(\A)})^k 
= \sum c_k x^k\, \l_{-x}(k\A)  \ . 
\end{equation}
The first terms are 
$$ 1+xS^1(\B)+x^2S^2(\B) +\cdots =
1+ xS^1(\B)\l_{-x}(\A) +
 x^2(S^2(\B)+S^1(\B) S^1(\A))$$ 
$$ \l_{-x}(2\A) 
+ x^3(S^3(\B)+ 2S^2(\B) S^1(\A)+2S^1(\B)S^2(\A) + S^1(\B)S_{11}(\A) )
 \l_{-x}(3\A) +\cdots $$
One sees that the $c_k$'s are linear in the $S_i(\B)$'s. One can therefore
restrict to the case $\B:= b $ of cardinality 1. By homogeneity, one can 
even put $b=1$.  Finally one has to solve 
$$ \frac{1}{1-x}= \sum c_k x^k\, \l_{-x}(k\A) $$
i.e. 
$$1 = (1-x) \sum c_k x^k\, \l_{-x}(k\A)= \sum c_k x^k\, \l_{-x}(k\A+1) \, $$
the solution of this system combining  addition and multiplication:
\begin{equation}
 c_k= \frac{1}{k} S^{k-1}(k\A+2) \ , \ k\geq 1 \ . 
\end{equation}
For example, $c_3=\frac{1}{3}S_2(2\A+2)= 2S^2(\A)+S_{11}(\A) +2S^1(\A)+1$
and, going back to an homogeneous expression of degree 3
$$ c_3= 2S^2(\A) S^1(\B) +S_{11}(\A)S^1(\B) +2S^1(\A)S^2(\B) + S^3(\B)\ . $$

Riordan's identity can be found in the specialization 
$S^i(\A)= a^i/i!$, $S^i(\B)=b^i/i!$, since then :  
$$ c_3\mapsto 2\frac{a^2}{2}\frac{b}{1} + \frac{a^2}{2}
\frac{b}{1} +2 \frac{a}{1}\frac{b^2}{2} + \frac{b^3}{3!}= 
\frac{b(3a+b)^2}{3!}\ .$$
One may ponder over the fact that the generalization 
of Riordan's identity is proved by replacing $\exp(-bx)$ by $1-bx$.
This \lq\lq umbra" looks too paltry to shelter the exponential,
in that it uses only formula (25) and that it uncovers the integer 2
which was not present in the formulation of (25).

We could give numerous classical examples which can be decoded in terms
of multiples of alphabets (cf. the article of Brenti \cite{Br}).
The split alphabets promised by the title are more difficult 
to find, and I shall end with a single example, the one of Jack polynomials
indexed by partitions of length 1 \cite{Ma}. Indeed their generating
function is
\begin{equation}
 \sum \frac{z^k}{a^k k!} J^\a_k(x_1,\ldots,x_n) = 
\prod(1-zx_i)^{-\frac{1}{\a}} =
\ss_z(\frac{1}{\a}X) \ ,
\end{equation} 
the last expression supposing that the $x_i$'s be rank 1-elements,
with sum $X$. An example of computations related to Jack polynomials
and using $\l$-techniques can be found in \cite{LL}.

It will be much easier for me to give a longer list of examples when
$\l$-rings are taught at school. 

\vfill\eject 
\medskip\noindent
{\bf The Cauchy formula}

The space of symmetric functions  $\Sym$ in indeterminates $x_1,\ldots, x_n$
has a long history.  Newton showed that it is a space of polynomials 
in $\L^1,\ldots, \L^n$ or $\psi_1,\ldots, \psi_n$. 
A great many of classical problems in this field amount 
changing bases and linear algebra.

Kostka understood that there exists a canonical scalar product for
which Schur functions are an orthonormal basis, power sums, an
orthogonal basis; monomial functions  are adjoint to products of complete
functions, etc.  All these statements can be summarized by the existence
of a {\it Cauchy kernel}
$$K(X,Y):= \prod_{i,j} \frac{1}{1-x_iy_j}$$
(introducing a second set of indeterminates $y_1,\ldots, y_n$ that one can
suppose of the same cardinality).
This kernel defines the scalar product, that is, every expansion 
\lq\lq separating variables" 
$$K(X,Y) =\sum U_J(X) V_J(Y) $$
provides a pair of adjoint bases $\{U_J\}$,  $\{V_J\}$ of $\Sym$.

Thus expansions like 
$$K(X,Y)= \prod_i\sum_k y_i^k S^k(X) \quad \& \quad 
K(X,Y)= \prod_{i,j}\left( 1+ x_iy_j +(x_i y_j)^2+\cdots \right)$$
show that the monomial basis is adjoint to the basis of products
of complete functions, and that the basis of power sums is orthogonal. 
Diagonalizing $K(X,Y)$ is less straightforward and can be deduced from 
Binet-Cauchy theorem expressing minors of a product of matrices
(in that case the matrix $\left[\frac{1}{1-x_iy_j} \right]$
is  the product of two Vandermonde matrices, cf. \cite{Ma}).

The above three expansions, combined with the involution $X\mapsto -X$
and the symmetry in $X$ and $Y$ give
formulae $(6a),\ldots,(6e)$, when specializing $Y$ to the integer
$i+k$.

By deforming the Cauchy kernel by introducing one or two parameters, one
generalizes Schur functions into {\it Hall-Littlewood polynomials} 
or {\it Macdonald polynomials}.  However, these polynomials
constitute an orthogonal basis, not an orthonormal one and one needs to
introduce extra conditions to characterize them 
(contrary to Schur functions which are the only orthormal 
basis of  $\Sym$  over $\Z$). 

\medskip\noindent{\bf $\l$-rings}

 $\l$-rings are rings with operators $\l^i$, $i\in \N$,
satisfying three axioms expressing their compatibility with ring operations
(cf. \cite{Kn})~:
addition : $\l^i(x+y)$, multiplication $\l^i(xy)$, 
the third  axiom  stating a universality property with respect to composition
$x \mapsto \l^i(\l^j(x))$ (called {\it plethysm}
by Littlewood and combinatorists after him).

Instead of taking $\l^i$, one can use the  $S^i$ defined
by $S^i(x):= (-1)^i\, \l^i(-x)$, or the $\psi_k$'s  defined
by the generating function 
 (4) ( replacing $A$ by $x$). 

Our present knowledge of plethysm
is too scanty to allow  wide  use in explicit computations.  There remains only
addition (this is an avatar of Chu-Vandermonde formula) 
$$ S^k(x+y) = \sum_{i+j=k} S^i(x) S^j(y)$$
and multiplication, which is given by the Cauchy formula 
$$ S^k(xy) = \sum_{J:|J|=k} S_J(x) S_J(y) $$
(defining the $ S_J(x)$'s as  determinants in the 
$S^j(x)$'s). 

In short one can say that Cauchy's formula generates the majority of identities
in the theory of $\lambda$-rings, as well as in the theory of
classical symmetric functions.

We restricted our constructions to rings of polynomials, which renders
axiomatics simpler. The basic objects are monomials $u$ and scalars $\a$
(here taken in $\C$).
The three axioms can be written at a stroke in formula (25)  
$$ \psi_k \left(\sum \a\, u\right) = \sum \a\, u^k \quad ,
\quad k>0 \ .$$ 

In a general $\lambda$-ring, one has elements more general than 
  \lq\lq polynomials".

\medskip 
\noindent
{\bf Schubert polynomials}

These polynomials generalize Schur functions and constitute a linear basis
of the ring of polynomials in $x_1,x_2,\ldots$,
stable by divided differences. Their combinatorics involves permutations
rather than partitions in the case of symmetric functions.

Following Newton, for every $i$ one defines the {\it $i$-th 
divided difference} $\partial_i$  as the operator (written on the right)
$$ f\, \partial_i = \frac{
f(\ldots x_i,x_{i+1}\ldots) - f(\ldots x_{i+1},x_i \ldots)}
       { x_i - x_{i+1}  }$$

For every $k$, every $\nu:= [\nu_1,\ldots, \nu_k]$, $\nu_1\geq \cdots \geq 
\nu_k \geq 0$, one puts 
$$ Y_\nu:= x^\nu $$
and one defines recursively  {\it Schubert polynomials} by
\begin{equation}
Y_J\, \partial_i = Y_{[\ldots, j_{i+1},j_i-1,\ldots]} \quad {\rm si}
\quad j_i >j_{i+1} 
\end{equation}
(since $\partial_i^2=0$, then $Y_J\, \partial_i=0$ if 
$j_i\leq j_{i+1})$. 
In other terms,  Schubert polynomials are the images of {\it dominant}
monomials under iterated divided differences.

When $J$ is of the type $j_1\leq j_2\leq \cdots \leq j_n$, 
  $j_{n+1}=0=j_{n+2}=\cdots$, then $Y_J$ is equal to the Schur function 
of index  $[j_1,\ldots,j_n]$ in the variables $x_1,\ldots,x_n$.
Binomial determinants are obtained by applying (39) to Schur functions. Thus
$$Y_{2345}\ \stackrel{\d_4\d_5}{\longrightarrow} \ Y_{234003}\  
\stackrel{\d_3}{\longrightarrow} \ Y_{230303}
$$
$$Y_{1234}\ \stackrel{\d_4\d_5}{\longrightarrow} \ Y_{123002}\
\stackrel{\d_3}{\longrightarrow} \ Y_{120202}
$$

Techniques of divided differences replace manipulations of determinants
and provide identities on binomial determinants which are specializations
of Schubert polynomials ( $x_i=1$ for all $i$). In this way, one obtains the
determinants that we wrote in relation with Bernoulli numbers. 
Gessel and Viennot \cite{GV} prefer to use a combinatorics of non-intersecting
paths to study binomial determinants.

Similarly to the case of symmetric functions, the full theory can be 
condensed into the existence of a Cauchy kernel 
$$K_n(X,Y):=\prod_{i,j\, :\, i+j\leq n} (x_i-y_j)$$
which generalizes the  {\it resultant} $\prod_{i,j}(x_i-y_j)$
(this last one being diagonal in the basis of Schur functions). 

Let us remark that it is equivalent to consider $\prod_{i,j}(x_i-y_j)$ or\\
 $\prod_{i,j}1/(1-x_iy_j)$. This is not so in the non-symmetric case,
the expansion of $\prod_{i,j\, :\, i+j\leq n}1/(1-x_iy_j)$ 
involves  {\it key polynomials}
(associated to {\it isobaric divided differences})
and not  Schubert polynomials.

\begin{thebibliography}{1}
\bibitem{AV}
 ACE, S. Veigneau. \emph{an Algebraic Environment for the Computer
algebra system MAPLE},
{\tt http://phalanstere.univ-mlv.fr/$\sim$ace} (1998).

\bibitem{Br}
 F. Brenti. \emph{ A class of $q$-symmetric functions arsing from plethysm},
 pr\'epublication (1999).

\bibitem{GV} I. Gessel, X. Viennot, \emph{Binomial determinants, paths
and hook length formulae}, Advances in M. {\bf 58} (1985) 300--321.

\bibitem{Kn}
D. Knutson. \emph{$\lambda$-rings and the representation theory of the 
 symmetric group}, Lecture Notes in Mathematics \textbf{308}, Springer (1973).

\bibitem{LL}  A. Lascoux, M. Lassalle. 
\emph{Une identit\'e remarquable en th\'eorie des partitions},
Math. Annal., to appear (2000).  

\bibitem{LS1}  A. Lascoux \& M.P. Sch\"utzenberger.
     \emph{Polyn\^omes de Schubert},  Comptes Rendus \textbf{294} (1982) 447.

\bibitem{LS2}
 A. Lascoux \& M. P. Sch\"utzenberger. \emph{Formulaire raisonn\'e de fonctions
  sym\'etriques}, Universit\'e Paris 7 (1985).

\bibitem{Ma}
I.G. Macdonald. \emph{Symmetric functions and Hall polynomials}, Clarendon
Press, second edition, Oxford, 1995.

\bibitem{Pr1}
 V. Prosper. \emph{Combinatoire des polyn\^omes multivari\'es},
th\`ese, Universit\'e de Marne la Vall\'ee (1999)\\
{\tt http://schubert.univ-mlv.fr/$\sim$vince/vpthesis.html}

\bibitem{Pr2}
 V. Prosper. \emph{ SFA, a package on symmetric functions considered
       as operators over the ring of polynomials
       for the computer algebra system Maple},
 J. of Symb. Comp.  \textbf{29} (2000) 83--94.


\bibitem{Ri}\ J. Riordan. \emph{Combinatorial identities}, Wiley (1968).

\bibitem{Ro}\ S. Roman. \emph{More on the umbral calculus, 
 with emphasis on the q-umbral calculus}
J. Math. Anal. Appl. {\bf 107} (1985) 222--254.
 
\bibitem{R1}\ Gian-Carlo Rota. \emph{ Finite Operator Calculus}, 
Academic Press (1975).

\bibitem{R2}\ Gian-Carlo Rota. \emph{ Foundations I. 
Theory of Moebius functions}, 
 Zeit. f\"ur Wahr. {\bf 2} (1964) 340--368.
 
\bibitem{R3}\ Gian-Carlo Rota. \emph{The number of partitions of a set},
 Am. Math. M. {\bf 71} (1964) 498--504.

\bibitem{R4}  Gian-Carlo Rota. 
\emph{Baxter algebras and combinatorial identities I,II},
 Bull. A.M.S. {\bf 75} (1969) 325--334.

\bibitem{R5} R. Mullin, G-C Rota. 
\emph{Foundations III. Theory of binomial enumeration,
 Graph Theory and its Applications, B.Harris ed.},
Academic Press (1970) 167-213.

\bibitem{R6} J. Goldman,  G-C Rota. 
\emph{Foundations IV. Finite vector spaces and Eulerian
generating functions}, Studies in Appl. Math.  {\bf 49} (1970) 239--258.


\bibitem{R7} Gian-Carlo Rota. 
\emph{Hopf Algebra methods in combinatorics},
 Colloques internationaux C.N.R.S, Orsay (1976) 363--365.

\bibitem{R8} S.A. Joni, G-C Rota. 
\emph{Coalgebras and bialgebras in combinatorics},
 Stud. in Appl. Math. {\bf 61} (1979) 93-139.

\bibitem{R9} J.P. Kung,  G-C Rota. 
\emph{The invariant theory of binary forms},
 Bull. AMS {\bf 10} (1984) 27--85.

\bibitem{R10} W.Y.C. Chen,  G-C Rota. 
\emph{$q$-analogs of the inclusion-exclusion principle
and permutations with restricted position},  Discr. Math. {\bf 104}
(1992) 7--22. 

\bibitem{R11} G-C Rota. \emph{Report on the present state of combinatorics},
Discr. Math. {\bf 153} (1996) 289--303.

\bibitem{Schur} I. Schur. \emph{Bermerkungen sur Theorie der beschr\"ankten
Bilinearformen ...}~, Journal f\"ur die reine ... {\bf 140} (1911) 1--28.

\end{thebibliography}

\end{document}
