Alphabet splitting

Some comments about the mathematical work of

GIAN-CARLO ROTA

Alain Lascoux CNRS, Institut Gaspard Monge, Université de Marne-la-Vallée 77454 Marne-la-Vallée Cedex, France Alain.Lascoux@univ-mlv.fr

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”.

I met Gian-Carlo in 1976, landing in MIT trying to establish Western connections. I was already working with Marcel-Paul Schützenberger 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 λ-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 [13], Moebius functions [14], Hopf algebras [19], Baxter algebras [16], 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 without loss of information.

It is clear, for example, that in a linear identity one is allowed to replace a_{i}, i = 1, 2 … by a^{1}, a^{2}, …, supposing that a is an indeterminate or a transcendental element. But why is it that inside straightening relations, so dear to Rota [21], between minors of matrices, one can restrict to Vandermonde matrices

[\begin{matrix}a^{1} & a^{2} & a^{3} & ⋯ \\ b^{1} & b^{2} & b^{3} & ⋯ \\ · & · & · & ⋯ \end{matrix} ]

instead of having to take a generic one

[\begin{matrix}a_{1} & a_{2} & a_{3} & ⋯ \\ b_{1} & b_{2} & b_{3} & ⋯ \\ · & · & · & ⋯ \end{matrix} ] ?

Umbral calculus rules are simple, but it is far less elementary to determine the limits of their domain of validity [23]. 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:

(𝔸 = {a} , 𝔹 = {b}) ↦ 𝔸 + 𝔹 := {a} ∪ {b} .

Restrict for the moment to finite sets. Taking an extra indeterminate z, one can write generating functions

λ_{z}(𝔸) := ∏_{a∈𝔸}(1 + za) , σ_{z}(𝔸) := ∏_{a∈𝔸} \frac{1}{1 − za}.  (1)

the expansion of which defines complete functions S^{i}(𝔸) and elementary functions Λ^{i}(𝔸)

λ_{z}(𝔸) = ∑ z^{i} Λ^{i}(𝔸) , σ(𝔸) = ∑ z^{i} S^{i}(𝔸) .  (2)

Addition of alphabets translate into product of generating functions

λ_{z}(𝔸 + 𝔹) = λ_{z}(𝔸) λ_{z}(𝔹) , σ_{z}(𝔸 + 𝔹) = σ_{z}(𝔸) σ_{z}(𝔹) .  (3)

One also needs power sums ψ_{i}:

ψ_{i}(𝔸) = ∑_{a∈𝔸}a^{i} , ∑_{i=1}^{∞} ψ_{i}(𝔸)\frac{z^{i}}{i} = log(σ_{z}(𝔸)) .  (4)

However, having learnt addition, one knows how to multiply by a positive integer

𝔸 = {a} → 2𝔸 := {a′} ∪ {a′′} , 3𝔸 := {a′} ∪ {a′′} ∪ {a′′′} , …

that is, one knows how to double, triple, ..., each letter ( erasing the diacritic signs at the final stage)

λ_{z}(2𝔸) = λ_{z}(𝔸)^{2} , λ_{z}(3𝔸) = λ_{z}(𝔸)^{3} …

These tools are sufficient to invert formal series f(z) = z+f_{1}z^{2}+f_{2}z^{3}+⋯, that is, to find g(z) = z + g_{1}z^{2} + g_{2}z^{3} + ⋯ such that

f(g(z)) = z & 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σ_{−z}(𝔸) (every formal series factorizes formally!), one finds that the powers of g are

g^{k}(z) = k z^{k} ∑ \frac{z^{i}}{i + k} Λ^{i}((i + k)𝔸) ,  (5)

and only require multiplication of alphabets by integers if k ∈ ℤ (formulae are still valid for k ∈ ℂ; 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 Λ^{i}((i + k)𝔸) 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 [9] and to its implementation [10].

In short, the compact notation Λ^{i}((i + k)𝔸) contains the following formulae (see the comments about symmetric functions at the end) :

\begin{aligned}Λ^{i}((i + k)𝔸) & = & (−1)^{i} ∑_{|J|=i} ψ_{J}(−(i + k))S^{J}(𝔸) & (a) \\ & = & ∑_{|J|=i} ψ_{J}(i + k)Λ^{J}(𝔸) & (b) \\ & = & ∑_{|J|=i} S_{J}(i + k)S_{J^{∼}}(𝔸) & (c) \\ & = & ∑_{|J|=i} Λ^{J}(i + k)ψ_{J}(𝔸) & (d) \\ & = & (−1)^{i} ∑_{|J|=i} \frac{(−i−k)^{ℓ(J)}}{m_{1}!m_{2}!···} (\frac{ψ_{1}}{1} )^{m_{1}}(\frac{ψ_{2}}{2} )^{m_{2}}(\frac{ψ_{3}}{3} )^{m_{3}} ⋯ & (e) \end{aligned} (6)

are the expansion in terms of the basis of products of complete functions S^{J}, products of elementary functions Λ^{J}, Schur functions S_{J}, monomial functions ψ_{J}, products of power sums ψ^{J}, noting in (6e) the partitions exponentially: J = 1^{m_{1}}2^{m_{2}} · · ·.

Let us stress once more that all these expansions are a consequence of the operation 𝔸 → k 𝔸, using (1),...,(4).

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} → Q = D + a_{1}D^{2} + a_{2}D^{2} + ⋯

while preserving properties like the existence of a distinguished basis {x^{n}} : Dx^{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

Q = D σ_{−D}(𝔸) = D − S^{1}(𝔸)D^{2} + S^{2}(𝔸)D^{2} − S^{3}(𝔸)D^{3} + ⋯  (7)

One wants polynomials P_{n}, n = 1, 2 …, P_{0} := 1, such that

Q(P_{n}) = nP_{n−1} & P_{n}(0) = 0 , n ≥ 1 .  (8)

Rota’s theorem ([17], th. 4), is

P_{n} = x λ_{D}(n𝔸) x^{n−1} , n ≥ 1 .  (9)

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) = λ_{D}(−𝔸), one has Q = D f = f D and

Q P_{n} = f DP_{n} = f Dxf^{−n} x^{n−1}
= f f^{−n} x^{n−1} + fx Df^{−n}x^{n−1} = f^{−n+1} xx^{n−2} + fxf^{−n}Dx^{n−1}

= (1−n)f′ f^{−n} x^{n−2} +xf^{−n+1}x^{n−2} +xf′ f^{−n} (n−1)x^{n−2} +xf^{−n+1}(n−1)x^{n−2}

= n P_{n−1}

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

• existence of a reproducing kernel

∑ \frac{P_{n}(y)}{n!} Q^{n}(f(x)) = f(x + y) ,  (10)

• existence of a Cauchy formula

∑ \frac{P_{n}(y)}{n!} x^{n}σ_{−x}(n𝔸) = exp(xy) ,  (11)

• existence of a binomiality property

P_{n}(x + y) = ∑ \binom{n}{i}P_{i}(x)P_{n−i}(y) .  (12)

These formulae can be interpreted as a result of replacing the usual exponential by ∑ x^{n}P_{n}(x)/n!. They may appear much more surprising once specialized.

For example, let Q = D(1−D), i.e. 𝔸 is such that S^{1}(𝔸) = 1, S^{i}(𝔸) = 0, i > 1. Then Λ^{i}(n𝔸) = \binom{n+i−1}{i},

P_{n} = ∑ \frac{(n − i) ⋯ (n + i − 1)}{i!} x^{n−i} ,  (13)

and Cauchy formula gives the expansion of exp

exp(xy) = ∑ \frac{P_{n}(y)}{n!} x^{n} (1 − x)^{n}  (14)

used by Schur [24] to compute sin(πx).

Abel polynomials occur for

Q = D + aD^{2}/1! + a^{2}D^{3}/2! + ⋯,

that is for Q such thate Q(f(x)) = \frac{d}{dx}f(x + a).

The corresponding “Abel alphabet” is such that S^{i}(𝔸) = (−a)^{i}/i!, Λ^{i}(n𝔸) = S^{i}(n𝔸) = (−na)^{i}/i!, and finally

P_{n}(x) = x (x − na)^{n−1} .  (15)

In this case, power sums are simpler since :

ψ_{1}(n𝔸) = −na & ψ_{i}(n𝔸) = 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}(𝔸) = 1/i!. Determinants in the S^{i}(n𝔸) 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}, …, j_{n}], 0 ≤ j_{1} ≤≤ ⋯ ≤ j_{n}, is :

S_{J}(n𝔸) = \frac{(−a n)^{|J|}}{|J|!} dim(J) = (−a n)^{|J|} det |\frac{1}{(j_{i} + k − i)!}|_{1≤i,k≤n} .

As a last example of deforming the derivative, leading to the Bernoulli numbers:

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} + ⋯)  (16)

Thus

S^{i}(𝔸) = B_{i}/i! & Λ^{i}(𝔸) = (−1)^{i}/(i + 1)! , i ≥ 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:

P_{n}(x) = x (\frac{exp(D) − 1}{D})^{n} x^{n−1} = x(1 + D/2! + D^{2}/3! + ⋯)^{n} x^{n−1} . (17)

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 [8], see also [7].

In the present case of the Bernoulli alphabet, the identity \frac{d}{dx} exp(x) = exp(x) implies ψ_{i}(𝔸) = −S^{i}(A) ∀i > 1, and therefore the Newton relations between complete functions S^{i} and power sums ψ_{k}

nS^{n} = ψ_{1}S^{n−1} + ψ_{2}S^{n−2} + ⋯ ψ_{n}S^{0}

give the following recursion (Gessel told me that this is classical)

−(n + 1)S^{n}(𝔸) = \frac{−n − 1}{n!}B_{n} = S_{2}(𝔸)S_{n−2}(𝔸) + S_{4}(𝔸)S_{n−4}(𝔸) + ⋯ + S_{n−2}(𝔸)S_{2}(𝔸) . (18)

One can compare the underlying algorithm to the one of Miss Augusta Adda, Lovelace countess,

\frac{2x − 1}{2(2x + 1)} = B_{2} \frac{2x}{2!} + B_{4} \frac{2x(2x − 1)(2x − 2)}{4!} + B_{6} \frac{2x ⋯ (2x − 4)}{6!} + ⋯ (19)

To close this chapter on Bernoulli numbers, may I express them in terms of Schubert polynomials [6] specialized in x_{1} = x_{2} = ⋯ = 1 ? For example,

(−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)}  (20)

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 |\binom{i}{2j−i}|, up to factors 2×(2^{2n}−1). For example, for n = 6, the product of B_{12} = −\frac{691}{2730} by 2×(2^{2n}−1) (= 8190), is equal to the determinant (=2073) of the following matrix (writing ‘·‘ for ‘0‘, the full shifted Pascal matrix from which it is extracted being written on the right) :

[\begin{matrix}1 & 1 & · & · & · & · \\ · & 1 & 1 & · & · & · \\ · & · & 3 & 1 & · & · \\ · & · & 1 & 6 & 1 & · \\ · & · & · & 5 & 10 & 1 \\ · & · & · & 1 & 15 & 15 \end{matrix}] ← [\begin{matrix}1 & 1 & · & · & · & · & · & · & · & · \\ · & 1 & 2 & 1 & · & · & · & · & · & · \\ · & · & 1 & 3 & 3 & 1 & · & · & · & · \\ · & · & · & 1 & 4 & 6 & 4 & 1 & · & · \\ · & · & · & · & 1 & 5 & 10 & 10 & 5 & 1 \\ · & · & · & · & · & 1 & 6 & 15 & 20 & 15 \end{matrix}]

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

They introduced a q-derivative D_{q} : f ↦ \frac{f(qx)−f(x)}{qx−x}. In the like manner as before, it can be deformed

D_{q} ↦ Q = D_{q}σ_{−D_{q}}(𝔸) = D_{q} − S^{1}(𝔸)D_{q}^{2} + S^{2}(𝔸)D_{q}^{2} − S^{3}(𝔸)D_{q}^{3} + ⋯ (21)

Since D_{q}(x^{n}) = [n] x^{n−1}, with [n] := 1 + q + ⋯ + q^{n−1}, one looks for polynomials P_{n}^{q} such that

Q(P_{n}^{q}) = [n]P_{n−1}^{q} & P_{n}^{q}(0) = 0 , n ≥ 1 .  (22)

Actually one has to replace the relation P_{n} = xλ_{D}(n𝔸)x^{n−1} by an equivalent one to be able to q-ify it, and one finds

P_{n}^{q} = (1 + ∑(n − |J|)\frac{(n − 1) ⋯ (n − ℓ(J) + 1)}{∏ m_{i}!}Λ^{J}(𝔸) D_{q}^{|J|}) x^{n} , (23)

sum over all partitions J ≠ 0, J = 1^{m_{1}}2^{m_{2}}3^{m_{3}} ⋯, ℓ(J) = m_{1} + m_{2} + ⋯, |J| = m_{1} + 2m_{2} + 3m_{3} + ⋯, with Λ^{J} := (Λ^{1})^{m_{1}}(Λ^{2})^{m_{2}}(Λ^{3})^{m_{3}} · · ·.

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 [12].

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} ↦ 2𝔸 := {a′} ∪ {a′′}, but the inverse opration is required :

𝔸 ↦ \frac{1}{2}𝔸 = 𝔹 , 𝔹 = \{b\} ↦ \{b′\} ∪ \{b′′\} = 𝔸 .

Realizing that at the level of power sums one has :

ψ_{i}(2𝔸) = ∑(a′)^{i} + ∑(a′′)^{i} = 2ψ_{i}(𝔸) ,

one realizes that 𝔹 = k 𝔸, k ∈ ℂ can be defined by the equations

ψ_{i}(𝔹) := k ψ_{i}(𝔸) , i ≥ 1 .  (24)

It is however more illuminating to discover that every polynomial can play the rôle of an alphabet, that is, power sums ψ_{i} are operators on the ring of polynomials ( α ∈ ℂ, u monomial):

P = ∑_{α,u} α u ⇒ ψ_{i}(P) = ∑_{α,u} α u^{i} .  (25)

The ring of symmetric polynomials 𝔖ym being generated by the ψ_{i}, i = 1, 2, …, formula (25) transforms any symmetric polynomial into an operator on the ring of polynomials. Thus, the generating functions of the operators Λ^{i} or S^{i} are

P = ∑_{α,u} α u ↦ λ_{z}(P) = ∏(1 + zu)^{α} ,  (26)

P = ∑_{α,u} α u ↦ σ_{z}(P) = ∏(1 − zu)^{−α} .  (27)

Each formula (25), (26), (27), at one wishes, characterizes the structure of λring of the ring of polynomials. Grothendieck had choosen lambda operations, that is the exterior powers Λ^{i} of classes of vector bundles, the S^{i}’s being the symmetric powers. Algebraic topologists, for their part, prefer Adams operations ψ_{i} (see at the end some remarks about λ-rings).

Notice the different rôles played by constants α and monomials u:

\begin{cases}ψ_{i}(α) = α , & S^{i}(α) = \binom{α+i−1}{i} , & Λ^{i}(α) = \binom{α}{i} \\ ψ_{i}(u) = u^{i} , & S^{i}(u) = u^{i} , & Λ^{i}(u) = 0, i > 1, & Λ^{1}(u) = u \end{cases}  (28)

Computers cannot distinguish indeterminates α from monomials u. It is more correct to characterize “monomials” as rank 1 elements (i.e. elements x ≠ 0 such that Λ^{i}(x) = 0 ∀i > 1), and “constants” as elements invariant under all the ψ_{i}’s (Rota [17] called them elements of binomial type).

It is appropriate not to restrict to polynomials, but go to rational functions or formal series, keeping the definition

ψ_{i} (\frac{∑ αu}{∑ βv}) = \frac{∑ αu^{i}}{∑ βv^{i}} ,  (29)

with summations finite or not.

With some precautions, one can just as well use “Laurent monomials” with exponents in ℤ rather than in ℕ.

If q is a rank 1 element, one can now write \frac{1}{1−q} = 1 + q + q^{2} + ⋯, i.e. \frac{1}{1−q} is the infinite alphabet \{1, q, q^{2}, … \} and ψ_{i}(\frac{1}{1−q}) = \frac{1}{1−q^{i}}, i ≥ 1. By the way, we learn from Cauchy that :

S_{i}(\frac{1}{1 − q}) = \frac{1}{(1 − q) ⋯ (1 − q^{i})}  (30)

and therefore

σ_{x}(\frac{1}{1 − q}) = ∑ \frac{x^{i}}{(1 − q) ⋯ (1 − q^{i})}  (31)

is the q-exponential, the equality \frac{1}{1−q} = 1 + q + q^{2} + ⋯ leading to the factorization

σ_{x}(\frac{1}{1 − q}) = ∏_{i=1}^{∞} \frac{1}{1 − xq^{i}}  (32)

which turns the q-exponential into an object rather easier to manipulate than the classical exponential [18].

Combining elements of different types in a λ-ring, one can cover various expansions with the “+” 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 :

Ch_{n}(x) := n! Λ^{n}(x − y) .  (33)

To get their explicit expression, it is preferable to introduce z := y(1 − q). By combining (3), (28), (30), it follows that

Λ^{n}(x − \frac{z}{1 − q}) = ∑ Λ^{n−i}(x)Λ^{i}(\frac{−z}{1 − q}) = ∑ Λ^{n−i}(x)(−z)^{i}S^{i}(\frac{1}{1 − q})

Ch_{n}(x) = n! ∑ \frac{x ⋯ (x − n + i + 1)}{(n − i)!} \frac{(−y)^{i}(1 − q)^{i}}{(1 − q) ⋯ (1 − q^{i})} ,  (34)

For y = 1, q → 1, one recover the clasical polynomials (Rota [13], p.64).

We can now go back to the umbral calculus, having in mind that several lifts are possible for a_{i} :

a_{i} ↦ S_{i}(𝔸) , a_{i} ↦ ψ_{i}(𝔸) , a_{i} ↦ i!S_{i}(𝔸) , …

This is where λ-wisdom is not enough, and some help is needed to allow experimentation as with ACE [1], and its library SFA [10] devoted to λ-rings.

Let us take for example the identity

exp(bx) = ∑ \frac{b(ak + b)^{k−1}}{k!} (x exp(−ax))^{k} ,  (35)

that Riordan [11] gives as an application of Lagrange inversion. How should we interpret it in a λ-ring ? One can introduce two alphabets 𝔸, 𝔹, replace exp(ax) by σ_{x}(𝔸), exp(bx) by σ_{x}(𝔹) and look for the coefficients c_{k} of the expansion

σ_{x}(𝔹) = ∑ c_{k}(\frac{x}{σ_{x}(𝔸)})^{k} = ∑ c_{k}x^{k} λ_{−x}(k𝔸) .  (36)

The first terms are

1 + xS^{1}(𝔹) + x^{2}S^{2}(𝔹) + ⋯ = 1 + xS^{1}(𝔹)λ_{−x}(𝔸) + x^{2}(S^{2}(𝔹) + S^{1}(𝔹)S^{1}(𝔸))

λ_{−x}(2𝔸)+x^{3}(S^{3}(𝔹)+2S^{2}(𝔹)S^{1}(𝔸)+2S^{1}(𝔹)S^{2}(𝔸)+S^{1}(𝔹)S_{11}(𝔸))λ_{−x}(3𝔸)+⋯ One sees that the c_{k}’s are linear in the S_{i}(𝔹)’s. One can therefore restrict to the case 𝔹 := b of cardinality 1. By homogeneity, one can even put b = 1. Finally one has to solve

\frac{1}{1 − x} = ∑ c_{k}x^{k} λ_{−x}(k𝔸)

i.e.

1 = (1 − x) ∑ c_{k}x^{k} λ_{−x}(k𝔸) = ∑ c_{k}x^{k} λ_{−x}(k𝔸 + 1)

the solution of this system combining addition and multiplication:

c_{k} = \frac{1}{k}S^{k−1}(k𝔸 + 2) , k ≥ 1 .  (37)

For example, c_{3} = \frac{1}{3}S_{2}(2𝔸 + 2) = 2S^{2}(𝔸) + S_{11}(𝔸) + 2S^{1}(𝔸) + 1 and, going back to an homogeneous expression of degree 3

c_{3} = 2S^{2}(𝔸)S^{1}(𝔹) + S_{11}(𝔸)S^{1}(𝔹) + 2S^{1}(𝔸)S^{2}(𝔹) + S^{3}(𝔹) .

Riordan’s identity can be found in the specialization S^{i}(𝔸) = a^{i}/i!, S^{i}(𝔹) = b^{i}/i!, since then :

c_{3} ↦ 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 “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 [2]). 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 [8]. Indeed their generating function is

∑ \frac{z^{k}}{a^{k}k!}J_{k}^{α}(x_{1}, …, x_{n}) = ∏(1 − zx_{i})^{− \frac{1}{α}} = σ_{z}(\frac{1}{α}X) ,  (38)

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 λtechniques can be found in [5].

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

The Cauchy formula

The space of symmetric functions 𝔖ym in indeterminates x_{1}, …, x_{n} has a long history. Newton showed that it is a space of polynomials in Λ^{1}, …, Λ^{n} or ψ_{1}, …, ψ_{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 Cauchy kernel

K(X, Y) := ∏_{i,j} \frac{1}{1 − x_{i}y_{j}}

(introducing a second set of indeterminates y_{1}, …, y_{n} that one can suppose of the same cardinality). This kernel defines the scalar product, that is, every expansion “separating variables”

K(X, Y) = ∑ U_{J}(X)V_{J}(Y)

provides a pair of adjoint bases {U_{J}}, {V_{J}} of 𝔖ym.

Thus expansions like

K(X, Y) = ∏_{i} ∑_{k} y_{i}^{k}S^{k}(X) & K(X, Y) = ∏_{i,j} (1 + x_{i}y_{j} + (x_{i}y_{j})^{2} + ⋯)

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 [\frac{1}{1−x_{i}y_{j}} ] is the product of two Vandermonde matrices, cf. [8]).

The above three expansions, combined with the involution X ↦ −X and the symmetry in X and Y give formulae (6a), …, (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 Hall-Littlewood polynomials or 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 𝔖ym over ℤ).

λ-rings

λ-rings are rings with operators λ^{i}, i ∈ ℕ, satisfying three axioms expressing their compatibility with ring operations (cf. [4]) : addition : λ^{i}(x + y), multiplication λ^{i}(xy), the third axiom stating a universality property with respect to composition x ↦ λ^{i}(λ^{j}(x)) (called plethysm by Littlewood and combinatorists after him).

Instead of taking λ^{i}, one can use the S^{i} defined by S^{i}(x) := (−1)^{i} λ^{i}(−x), or the ψ_{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) = ∑_{i+j=k} S^{i}(x)S^{j}(y)

and multiplication, which is given by the Cauchy formula

S^{k}(xy) = ∑_{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 λ-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 α (here taken in ℂ). The three axioms can be written at a stroke in formula (25)

ψ_{k} (∑ α u) = ∑ α u^{k} , k > 0 .

In a general λ-ring, one has elements more general than “polynomials”.

Schubert polynomials

These polynomials generalize Schur functions and constitute a linear basis of the ring of polynomials in x_{1}, x_{2}, …, 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 i-th divided difference ∂_{i} as the operator (written on the right)

f ∂_{i} = \frac{f(… x_{i}, x_{i+1} …) − f(… x_{i+1}, x_{i} …)}{x_{i} − x_{i+1}}

For every k, every ν := [ν_{1}, …, ν_{k}], ν_{1} ≥ ⋯ ≥ ν_{k} ≥ 0, one puts

Y_{ν} := x^{ν} and one defines recursively Schubert polynomials by

Y_{J} ∂_{i} = Y_{[... ,j_{i+1},j_{i}−1,...]} si j_{i} > j_{i+1}  (39)

(since ∂_{i}^{2} = 0, then Y_{J} ∂_{i} = 0 if j_{i} ≤ j_{i+1}). In other terms, Schubert polynomials are the images of dominant monomials under iterated divided differences.

When J is of the type j_{1} ≤ j_{2} ≤ ⋯ ≤ j_{n}, j_{n+1} = 0 = j_{n+2} = ⋯, then Y_{J} is equal to the Schur function of index [j_{1}, …, j_{n}] in the variables x_{1}, …, x_{n}. Binomial determinants are obtained by applying (39) to Schur functions. Thus

Y_{2345} ⟶^{∂_{4}∂_{5}} Y_{234003} ⟶^{∂_{3}} Y_{230303}

Y_{1234} ⟶^{∂_{4}∂_{5}} Y_{123002} ⟶^{∂_{3}} 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 [3] 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) := ∏_{i,j: i+j≤n}(x_{i} − y_{j})

which generalizes the resultant ∏_{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 ∏_{i,j}(x_{i} − y_{j}) or ∏_{i,j} 1/(1 − x_{i}y_{j}). This is not so in the non-symmetric case, the expansion of ∏_{i,j: i+j≤n} 1/(1−x_{i}y_{j}) involves key polynomials (associated to isobaric divided differences) and not Schubert polynomials.

References

[1] ACE, S. Veigneau. an Algebraic Environment for the Computer algebra

   system MAPLE, http://phalanstere.univ-mlv.fr/∼ace (1998).

[2] F. Brenti. A class of q-symmetric functions arsing from plethysm, prépublication (1999).

[3] I. Gessel, X. Viennot, Binomial determinants, paths and hook length formulae, Advances in M. 58 (1985) 300–321.

[4] D. Knutson. λ-rings and the representation theory of the symmetric group, Lecture Notes in Mathematics 308, Springer (1973).

[5] A. Lascoux, M. Lassalle. Une identité remarquable en théorie des partitions, Math. Annal., to appear (2000).

[6] A. Lascoux & M.P. Schützenberger. Polynômes de Schubert, Comptes Rendus 294 (1982) 447.

[7] A. Lascoux & M. P. Schützenberger. Formulaire raisonné de fonctions symétriques, Université Paris 7 (1985).

[8] I.G. Macdonald. Symmetric functions and Hall polynomials, Clarendon Press, second edition, Oxford, 1995.

[9] V. Prosper. Combinatoire des polynômes multivariés, thèse, Université de Marne la Vallée (1999)

http://schubert.univ-mlv.fr/∼vince/vpthesis.html

[10] V. Prosper. SFA, a package on symmetric functions considered as operators over the ring of polynomials for the computer algebra system Maple, J. of Symb. Comp. 29 (2000) 83–94.

[11] J. Riordan. Combinatorial identities, Wiley (1968).

[12] S. Roman. More on the umbral calculus, with emphasis on the q-umbral calculus J. Math. Anal. Appl. 107 (1985) 222–254.

[13] Gian-Carlo Rota. Finite Operator Calculus, Academic Press (1975).

[14] Gian-Carlo Rota. Foundations I. Theory of Moebius functions, Zeit. für Wahr. 2 (1964) 340–368.

[15] Gian-Carlo Rota. The number of partitions of a set, Am. Math. M. 71 (1964) 498–504.

[16] Gian-Carlo Rota. Baxter algebras and combinatorial identities I,II, Bull. A.M.S. 75 (1969) 325–334.

[17] R. Mullin, G-C Rota. Foundations III. Theory of binomial enumeration, Graph Theory and its Applications, B.Harris ed., Academic Press (1970) 167-213.

[18] J. Goldman, G-C Rota. Foundations IV. Finite vector spaces and Eulerian generating functions, Studies in Appl. Math. 49 (1970) 239–258.

[19] Gian-Carlo Rota. Hopf Algebra methods in combinatorics, Colloques internationaux C.N.R.S, Orsay (1976) 363–365.

[20] S.A. Joni, G-C Rota. Coalgebras and bialgebras in combinatorics, Stud. in Appl. Math. 61 (1979) 93-139.

[21] J.P. Kung, G-C Rota. The invariant theory of binary forms, Bull. AMS 10 (1984) 27–85.

[22] W.Y.C. Chen, G-C Rota. q-analogs of the inclusion-exclusion principle and permutations with restricted position, Discr. Math. 104 (1992) 7–22.

[23] G-C Rota. Report on the present state of combinatorics, Discr. Math. 153 (1996) 289–303.

[24] I. Schur. Bermerkungen sur Theorie der beschränkten Bilinearformen ... , Journal für die reine ... 140 (1911) 1–28.