TWO POLYNOMIAL IDENTITIES

C. Krattenthaler and A. Lascoux

Fakultät für Mathematik der Universität Wien, Nordbergstraße 15, A-1090 Wien, Austria.

                 WWW: http://www.mat.univie.ac.at/~kratt

Institut Gaspard Monge, Université de Marne-la-Vallée, F-77454 Marne-la-Vallée Cedex 2, France

                   WWW: http://www-igm.univ-mlv.fr/~al

Abstract. We establish two polynomial identities. One of which generalizes a key identity in “A factorization theorem for classical group characters, with applications to plane partitions and rhombus tilings” by Mihai Ciucu and the first author [preprint 2008]. The other shows that the two sides in the identity can be expressed alternatively in form of a Pfaffian.

The purpose of this note is to establish two polynomial identities. The first (see Theorem 1 below) generalizes an identity in [1] which was crucial there to prove certain factorization theorems for classical group characters, and for numbers of rhombus tilings of certain regions. The second (see Theorem 2) provides a surprising alternative expression for the two sides in the identity involving a Pfaffian.

In the statement of our results, we use additive notation for sets of variables (“alphabets”) as in [2]. Further notations that we use are: the symbol X_{M} denotes the alphabet x_{1} + x_{2} + ⋯ + x_{M}; given an alphabet A, we write V (A) for the “Vandermonde product”

∏_{a,b∈A} ; a<b(a − b).

The following theorem generalizes Lemma 1 in [1].

Typeset by AMS-TEX

2000 Mathematics Subject Classification. Primary 05A19; Secondary 05A15 05A17 05E15 11P81 20C15 20G05.

Key words and phrases. Vandermonde determinant, polynomial identities.

The research of the first author was partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S9607-N13, the latter in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory.”

Theorem 1. Let a, b be two variables. Then there holds the identity

∑_{A+B=X_{2N}} ; |A|=NV (a + A + A^{−1})V (b + B + B^{−1}) = ∑_{A+B=X_{2N}} V (a + A + B^{−1})V (b + B + A^{−1}), (1)

where A^{−1} denotes the alphabet ∑_{α∈A} α^{−1}, with an analogous meaning for B^{−1}.

Proof. We prove the assertion by induction on N. In fact, the induction proof will prove two assertions at the same time, namely (1) and

(−1)^{N}_{∑_{A+B=X_{2N−1}} ; |A|=N}V (A + A^{−1})V (a + b + B + B^{−1})

= ∑_{A+B=X_{2N−1}}(−1)^{|A|}V (a + A + B^{−1})V (b + B + A^{−1}). (2)

For N = 1, identity (1) reduces to

(a − x_{1})(a − x_{1}^{−1})(x_{1} − x_{1}^{−1})(b − x_{2})(b − x_{2}^{−1})(x_{2} − x_{2}^{−1})
+ (a − x_{2})(a − x_{2}^{−1})(x_{2} − x_{2}^{−1})(b − x_{1})(b − x_{1}^{−1})(x_{1} − x_{1}^{−1})
= (a − x_{1}^{−1})(a − x_{2}^{−1})(x_{1}^{−1} − x_{2}^{−1})(b − x_{1})(b − x_{2})(x_{1} − x_{2})
+ (a − x_{1})(a − x_{2}^{−1})(x_{1} − x_{2}^{−1})(b − x_{2})(b − x_{1}^{−1})(x_{2} − x_{1}^{−1})
+ (a − x_{2})(a − x_{1}^{−1})(x_{2} − x_{1}^{−1})(b − x_{1})(b − x_{2}^{−1})(x_{1} − x_{2}^{−1})
+ (a − x_{1})(a − x_{2})(x_{1} − x_{2})(b − x_{1}^{−1})(b − x_{2}^{−1})(x_{1}^{−1} − x_{2}^{−1}),

while (2) reduces to

−(x_{1} − x_{1}^{−1})(a − b) = −(a − x_{1})(b − x_{1}^{−1}) + (a − x_{1}^{−1})(b − x_{1}),

both of which can be readily verified.

Now let us suppose that we have proved (1) and (2) with N replaced by N − 1. Below, we shall show that this implies that identities (1) and (2) are true if we specialize x_{1} to x_{2}. Let us for the moment suppose that this is already done. It is easy to see that both sides of (1) are symmetric in the variables x_{1}, x_{2}, …, x_{2N}, while both sides of (2) are symmetric in the variables x_{1}, x_{2}, …, x_{2N−1}. Moreover, both sides of (1) and both sides of (2) remain invariant up to an overall multiplicative sign if we replace x_{1} by x_{1}^{−1} (on the left-hand sides of (1) respectively (2), the latter assertion already applies to each individual summand; on the right-hand sides, one has to group the summands in pairs: the summands corresponding to a pair of alphabets (A, B) and the pair of symmetric differences (A△{x_{1}}, B△{x_{1}}) have to be considered together).

This means that identity (2) holds for all specializations of x_{1} to one of x_{2}, x_{2}^{−1}, x_{3}, x_{3}^{−1}, …, x_{2N−1}, x_{2N−1}^{−1}. These are 4N − 4 specializations. The previously observed fact that the replacement of x_{1} by x_{1}^{−1} changes the sign of both sides of (2) implies that both sides vanish for x_{1} = ±1. Thus, we have 4N − 2 specializations of x_{1} for which (2) holds.

We now specialize x_{1} = a on both sides of (2). Under this specialization, terms corresponding to alphabets B which contain x_{1} vanish on the left-hand side of (2) due to the appearance of the Vandermonde product V (a + b + B + B^{−1}), while terms corresponding to alphabets A which contain x_{1} vanish on the right-hand side of (2) due to the appearance of the Vandermonde product V (a + A + B^{−1}). Therefore, if x_{1} = a, identity (2) reduces to

(−1)^{N}(a − a^{−1})(a − b)( ∏_{j=2}^{2N−1}(a − x_{j})(a − x_{j}^{−1}))

×_{∑_{A+B=X′} ; |A|=N−1}V (A + a^{−1} + A^{−1})V (b + B + B^{−1})

= (a − a^{−1})(b − a)( ∏_{j=2}^{2N−1}(a − x_{j})(a − x_{j}^{−1}))

× ∑_{A+B=X′}(−1)^{|A|}V (A + a^{−1} + B^{−1})V (b + B + A^{−1}), (3)

where X′ = x_{2} + x_{3} + ⋯ + x_{2N−1}. After clearing the product which is common to both sides, and after little rearrangement, we see that the remaining identity is an instance of (1) with N replaced by N − 1, the latter being true due to the induction hypothesis.

In summary, we have found 4N − 1 specializations of x_{1} for which both sides of (2) agree. On the other hand, as Laurent polynomials in x_{1}, the degree of both sides of (2) is at most 2N − 1. (That is, the maximal exponent e of a power x_{1}^{e} is e = 2N − 1, and the minimal exponent is e = −(2N − 1).) Hence, both sides of (2) must be identical.

The earlier arguments show as well that identity (1) holds for all specializations of x_{1} to one of x_{2}, x_{2}^{−1}, x_{3}, x_{3}^{−1}, …, x_{2N}, x_{2N}^{−1} and ±1. These are 4N specializations.

We now specialize x_{1} = a on both sides of (1). Under this specialization, terms corresponding to alphabets A which contain x_{1} vanish on both sides of (1) due to the appearance of the Vandermonde products V (a + A + A^{−1}) respectively V (a + A + B^{−1}). Therefore, if x_{1} = a, identity (1) reduces to

(a − a^{−1})(b − a)( ∏_{j=2}^{2N}(a − x_{j})(a − x_{j}^{−1}))

×_{∑_{A+B=X′′} ; |A|=N}V (A + A^{−1})V (b + B + a^{−1} + B^{−1})

= (a − a^{−1})(b − a)( ∏_{j=2}^{2N}(a − x_{j})(a − x_{j}^{−1}))

× ∑_{A+B=X′′} V (A + a^{−1} + B^{−1})V (b + B + A^{−1}), (4)

where X′′ = x_{2} + x_{3} + ⋯ + x_{2N}. After clearing the product which is common to both sides, and after little rearrangement, we see that the remaining identity is an instance of (2) which has been just established.

In summary, we have found 4N + 1 specializations of x_{1} for which both sides of (1) agree. On the other hand, as Laurent polynomials in x_{1}, the degree of both sides of (1) is at most 2N. (That is, the maximal exponent e of a power x_{1}^{e} is e = 2N, and the minimal exponent is e = −2N.) Hence, both sides of (1) must be identical.

It remains to prove that, under the induction hypothesis, Equations (1) and (2) hold for x_{1} = x_{2}. We provide the argument establishing this fact for (1). The argument for (2) is completely analogous.

Indeed, under this specialization, terms corresponding to alphabets A which contain both x_{1} and x_{2} and to those which contain neither x_{1} nor x_{2} vanish on both sides of (1), because of the appearance of the Vandermonde products V (A) respectively V (B). Therefore, if x_{1} = x_{2}, identity (1) reduces to

2(a−x_{1})(a−x_{1}^{−1})(b−x_{1})(b−x_{1}^{−1})(x_{1}−x_{1}^{−1})^{2}( ∏_{j=3}^{2N}(x_{1}−x_{j})(x_{1}^{−1}−x_{j}^{−1})(x_{1}−x_{j}^{−1})(x_{j}−x_{1}^{−1}))

×_{∑_{A+B=X′′′} ; |A|=N−1}V (a + A + A^{−1})V (b + B + B^{−1})

= 2(a−x_{1})(a−x_{1}^{−1})(b−x_{1})(b−x_{1}^{−1})(x_{1}−x_{1}^{−1})^{2}( ∏_{j=3}^{2N}(x_{1}−x_{j})(x_{1}^{−1}−x_{j}^{−1})(x_{1}−x_{j}^{−1})(x_{j}−x_{1}^{−1}))

× ∑_{A+B=X′′′} V (a + A + B^{−1})V (b + B + A^{−1}), (5)

where X′′′ = x_{3} + x_{4} + ⋯ + x_{2N}. After clearing the product which is common to both sides, we see that the remaining identity is equivalent to (1) with N replaced by N − 1, the latter being true due to the induction hypothesis. This finishes the proof of the theorem. □

Theorem 2. Let a, b be two variables, and let

Φ(a, b; x_{i}, x_{j}) = \frac{(a − x_{i})(a − x_{i}^{−1})(b − x_{j})(b − x_{j}^{−1}) + (a − x_{j})(a − x_{j}^{−1})(b − x_{i})(b − x_{i}^{−1})}{(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1})}.

Then there holds the identity

∏_{i=1}^{2N}(x_{i} − x_{i}^{−1}) ∏_{1≤i<j≤2N}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1}) Pf_{1≤i<j≤2N} (Φ(a, b; x_{i}, x_{j}))

= _{∑_{A+B=X_{2N}} ; |A|=N}V (a + A + A^{−1})V (b + B + B^{−1}). (6)

Proof. We prove the assertion by induction on N. Again, the induction proof will prove two assertions at the same time, namely (6) and

a^{2N−2} ∏_{i=1}^{2N−1}(x_{i} − x_{i}^{−1}) ∏_{1≤i<j≤2N−1}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1})

× Pf_{1≤i<j≤2N} ( \begin{matrix}b − a & i = 1 \\ Φ(a^{−1}, b; x_{i−1}, x_{j−1}) & i ≥ 2 \end{matrix} )

= (−1)^{N}_{∑_{A+B=X_{2N−1}} ; |A|=N}V (A + A^{−1})V (a + b + B + B^{−1}). (7)

For N = 1, both (6) and (7) reduce to tautologies.

Now let us suppose that we have proved (6) and (7) with N replaced by N − 1. Below, we shall show that this implies that identities (6) and (7) are true if we specialize x_{1} to x_{2}. Let us for the moment suppose that this is already done. It is easy to see that both sides of (6) are symmetric in the variables x_{1}, x_{2}, …, x_{2N}, while both sides of (7) are symmetric in the variables x_{1}, x_{2}, …, x_{2N−1}. Moreover, both sides of (6) and both sides of (7) remain invariant up to an overall multiplicative sign if we replace x_{1} by x_{1}^{−1}.

This means that identity (7) holds for all specializations of x_{1} to one of x_{2}, x_{2}^{−1}, x_{3}, x_{3}^{−1}, …, x_{2N−1}, x_{2N−1}^{−1}. These are 4N − 4 specializations. The previously observed fact that the replacement of x_{1} by x_{1}^{−1} changes the sign of both sides of (7) implies that both sides vanish for x_{1} = ±1. Thus, we have 4N − 2 specializations of x_{1} for which (7) holds.

We now specialize x_{1} = a on both sides of (7). Since

Φ(a^{−1}, b; a, x_{j}) = a^{−1}(b − a)(b − a^{−1}),

under this specialization, the left-hand side of (7) becomes

a^{2N−2}(a − a^{−1}) ∏_{i=2}^{2N−1}(x_{i} − x_{i}^{−1}) ∏_{j=2}^{2N−1}(a + a^{−1} − x_{j} − x_{j}^{−1}) ∏_{2≤i<j≤2N−1}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1})

× Pf_{1≤i<j≤2N} ( \begin{matrix}b − a & i = 1 \\ a^{−1}(b − a)(b − a^{−1}) & i = 2 \\ Φ(a^{−1}, b; x_{i−1}, x_{j−1}) & i ≥ 3 \end{matrix} )

= a^{2N−2}(a − a^{−1})(b − a)

× ∏_{i=2}^{2N−1}(x_{i} − x_{i}^{−1}) ∏_{j=2}^{2N−1}(a + a^{−1} − x_{j} − x_{j}^{−1}) ∏_{2≤i<j≤2N−1}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1})

× Pf_{1≤i<j≤2N} ( \begin{matrix}1 & i = 1, j = 2 \\ b − a & i = 1, j > 2 \\ a^{−1}(b − a^{−1}) & i = 2 \\ Φ(a^{−1}, b; x_{i−1}, x_{j−1}) & i ≥ 3 \end{matrix} ) .

Here, the Pfaffian can be simplified. To see this most transparently, it is useful to display the skew symmetric matrix of which the Pfaffian is taken:

( \begin{matrix}0 & 1 & b − a & b − a & … & b − a \\ −1 & 0 & a^{−1}(b − a^{−1}) & a^{−1}(b − a^{−1}) & … & a^{−1}(b − a^{−1}) \\ −(b − a) & −a^{−1}(b − a^{−1}) \\ ⋮ & ⋮ & & * \\ −(b − a) & −a^{−1}(b − a^{−1}) \end{matrix} ) .

If we subtract a(b − a)/b − a^{−1} times the second row from the first row (and subsequently do the same operation with the corresponding columns), then this matrix is transformed to

( \begin{matrix}0 & 1 & 0 & 0 & … & 0 \\ −1 & 0 & a^{−1}(b − a^{−1}) & a^{−1}(b − a^{−1}) & … & a^{−1}(b − a^{−1}) \\ 0 & −a^{−1}(b − a^{−1}) \\ ⋮ & ⋮ & & * \\ 0 & −a^{−1}(b − a^{−1}) \end{matrix} ) ,

without changing the Pfaffian. The Pfaffian of the last matrix however is Pf(*). Therefore, under the specialization x_{1} = a, the left-hand side of (7) is equal to

= a^{2N−2}(a − a^{−1})(b − a) ∏_{i=2}^{2N−1}(x_{i} − x_{i}^{−1}) ∏_{j=2}^{2N−1}(a + a^{−1} − x_{j} − x_{j}^{−1})

× ∏_{2≤i<j≤2N−1}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1}) Pf_{1≤i<j≤2N−2} (Φ(a^{−1}, b; x_{i+1}, x_{j+1})) .

On the other hand, the specialization of the right-hand side of (7) to x_{1} = a is exactly the left-hand side in (3). Hence, after clearing common factors, we see that for x_{1} = a identity (7) reduces to

∏_{i=2}^{2N−1}(x_{i} − x_{i}^{−1}) ∏_{2≤i<j≤2N−1}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1}) Pf_{1≤i<j≤2N−2} (Φ(a^{−1}, b; x_{i+1}, x_{j+1}))

= _{∑_{A+B=X′} ; |A|=N−1}V (a^{−1} + A + A^{−1})V (b + B + B^{−1}),

where X′ = x_{2} + x_{3} + ⋯ + x_{2N−1}. Clearly, this is an instance of (6) with N replaced by N − 1, the latter being true due to the induction hypothesis.

In summary, we have found 4N − 1 specializations of x_{1} for which both sides of (7) agree. On the other hand, as Laurent polynomials in x_{1} (the left-hand side of (7) is indeed a Laurent polynomial in the x_{i}’s since the denominators in the Pfaffian cancel with the product over 1 ≤ i < j ≤ 2N − 1 !), the degree of both sides of (7) is at most 2N − 1. Hence, both sides of (7) must be identical.

The earlier arguments show as well that identity (6) holds for all specializations of x_{1} to one of x_{2}, x_{2}^{−1}, x_{3}, x_{3}^{−1}, …, x_{2N}, x_{2N}^{−1} and ±1. These are 4N specializations.

We now specialize x_{1} = a on both sides of (6). Since

Φ(a, b; a, x_{j}) = a(b − a)(b − a^{−1}),

under this specialization, the left-hand side of (6) becomes

(a − a^{−1})a(b − a) ∏_{i=2}^{2N}(x_{i} − x_{i}^{−1}) ∏_{j=2}^{2N}(a + a^{−1} − x_{j} − x_{j}^{−1})

× ∏_{2≤i<j≤2N}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1}) Pf_{1≤i<j≤2N} ( \begin{matrix}b − a^{−1} & i = 1 \\ Φ(a, b; x_{i}, x_{j}) & i ≥ 2 \end{matrix} ) .

On the other hand, the specialization of the right-hand side of (6) to x_{1} = a is exactly the left-hand side in (4). Hence, after clearing common factors, we see that for x_{1} = a identity (6) reduces to

a^{2−2N} ∏_{i=2}^{2N}(x_{i} − x_{i}^{−1}) ∏_{2≤i<j≤2N}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1}) Pf_{1≤i<j≤2N} ( \begin{matrix}b − a^{−1} & i = 1 \\ Φ(a, b; x_{i}, x_{j}) & i ≥ 2 \end{matrix} )

= (−1)^{N}_{∑_{A+B=X′′} ; |A|=N}V (A + A^{−1})V (a^{−1} + b + B + B^{−1}),

where X′′ = x_{2} + x_{3} + ⋯ + x_{2N}. This is an instance of (7) which has been just established.

In summary, we have found 4N + 1 specializations of x_{1} for which both sides of (6) agree. On the other hand, as Laurent polynomials in x_{1}, the degree of both sides of (6) is at most 2N. Hence, both sides of (6) must be identical.

It remains to prove that, under the induction hypothesis, Equations (6) and (7) hold for x_{1} = x_{2}. We provide the argument establishing this fact for (6). The argument for (7) is completely analogous.

Indeed, under this specialization, due to the term

∏_{1≤i<j≤2N}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1})

on the left hand side of (6), in the expansion of the Pfaffian only terms survive which contain the (1, 2)-entry of the Pfaffian. Thus, for x_{1} = x_{2}, the left-hand side of (6) reduces to

2(a − x_{1})(a − x_{1}^{−1})(b − x_{1})(b − x_{1}^{−1})(x_{1} − x_{1}^{−1})^{2} ∏_{i=3}^{2N}(x_{i} − x_{i}^{−1})( ∏_{j=3}^{2N}(x_{1} + x_{1}^{−1} − x_{j} − x_{j}^{−1})^{2})

× ∏_{3≤i<j≤2N}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1}) Pf_{3≤i<j≤2N} (Φ(a, b; x_{i}, x_{j})) .

On the other hand, the specialization of the right-hand side of (6) to x_{1} = a is exactly the left-hand side of (5). Hence, after clearing common factors, we see that for x_{1} = a identity (6) reduces to

∏_{i=3}^{2N}(x_{i} − x_{i}^{−1}) ∏_{3≤i<j≤2N}(x_{i} + x_{i}^{−1} − x_{j} − x_{j}^{−1}) Pf_{3≤i<j≤2N} (Φ(a, b; x_{i}, x_{j}))

= _{∑_{A+B=X′′′} ; |A|=N−1}V (a + A + A^{−1})V (b + B + B^{−1}),

where X′′′ = x_{3} + x_{4} + ⋯ + x_{2N}. This identity is equivalent to (6) with N replaced by N − 1, the latter being true due to the induction hypothesis. This finishes the proof of the theorem. □

References

1. M. Ciucu annd C. Krattenthaler, A factorization theorem for classical group characters, with applications to plane partitions and rhombus tilings, Advances in Combinatorial Mathematics: Proceedings of the Waterloo Workshop in Computer Algebra 2008 (I. Kotsireas, E. Zima, eds.), Springer–Verlag, New York (to appear).

2. A. Lascoux, Symmetric functions and combinatorial operators on polynomials, CBMS Regional Conference Series in Mathematics, vol. 99, Amer. Math. Soc., Providence, RI, 2003.

Fakultät für Mathematik der Universität Wien, Nordbergstraße 15, A-1090 Wien, Austria.

Institut Gaspard Monge, Université de Marne-la-Vallée, F-77454 Marne-la-Vallée Cedex 2, France.