SQUARE-ICE ENUMERATION

Alain Lascoux

Dedicated to George Andrews on the occasion of his sixtieth birthday

ABSTRACT. Starting with plane partitions possessing certain type of symmetries, many combinatorial objects came to the fore, the enumeration of which was the subject of intensive studies during the last twenty years, with of course, seminal contributions of George Andrews. Thanks to a detour through two-dimensional ice models, algebraic computations cristallised to the description of a certain determinant of Cauchy type. Dividing this determinant by some straightforward factors, one is reduced to studying a symmetric polynomial in two sets of variables. We show how to separate the variables with the help of divided differences, and obtain the desired symmetric function as a product of two rectangular matrices, each of them involving only one set of variables. In the same run, we reduce the dimension by 1 and factorize the determinant associated to the Bethe model of a 1-dimensional gas of bosons.

1. A combinatorial promenade

We first evoke some different combinatorial objects related to the algebraic computations of section 2.

The following figures appear in a forthcoming book by Bressoud [Br]. The elementary pieces (shown in Fig. 1) are the different models of planar frozen water molecules.

H − O − H  \begin{matrix}H \\ O \\ H \end{matrix}  \begin{aligned}H & – & O \\ & & H \end{aligned}  \begin{aligned}& & H \\ H & – & O \end{aligned}  \begin{matrix}O & – & H \\ H \end{matrix}  \begin{matrix}H \\ O & – & H \end{matrix}

Fig. 1

In Fig. 2 we have represented a display of those frozen water molecules on a square grid. Keeping the oxygens and replacing each hydrogen atom by an arrow pointing toward the oxygen to which it is attached transforms Fig. 2 into an oriented graph shown in Fig. 3. (One has added a top and bottom row of arrows, so that each vertex has two incoming arrows and two outgoing ones. The ice becomes electrically balanced.)

ALAIN LASCOUX

H – O H – O – H O – H O – H O – H
H  H  H  H  H
H – O – H O H – O H – O – H O – H
H  H  H  H  H
H – O H – O – H O – H O H – O – H
H  H  H  H  H
H – O H – O H – O H – O – H O – H
H  H  H  H  H
H – O H – O H – O – H O – H O – H

Fig. 2

↑  ↑  ↑  ↑  ↑
→ • → • ← • ← • ← • ←
↑ ↓ ↑ ↑ ↑
→ • ← • → • → • ← • ←
↓ ↑ ↑ ↓ ↑
→ • → • ← • ← • → • ←
↓ ↓ ↑ ↑ ↓
→ • → • → • → • ← • ←
↓ ↓ ↑ ↓ ↓
→ • → • → • ← • ← • ←
↓  ↓  ↓  ↓  ↓

Fig. 3

Instead of drawing arrows, one can write the numbers 0, 1 or −1 on the vertices of the preceding grid, according to the orientations of the arrows, the precise coding of each of the six possible water molecules being: 1 for the horizontal molecules, −1 for the vertical ones, and 0 for the others.

A matrix thereby obtained has the property that non zero entries alternate in each row and column, always starting and finishing with a 1 (alternating sign matrix); continuing with the same example we get

( \begin{matrix}0 & 1 & 0 & 0 & 0 \\ 1 & −1 & 0 & 1 & 0 \\ 0 & 1 & 0 & −1 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{matrix} ) .

Now, interpreting the alternating sign matrix as a history, according to Viennot’s paradigm (the entry +1 (resp. −1) in row i, column j, means that the letter i appears (resp. disappears) at time j), we get a staircase (for bats) Young tableau if we write the letters which are present at time j in decreasing order

2 3 5 5 5 1 3 4 4 1 2 3 1 2 1^{time 1 2 3 4 5}

The foregoing tableaux satisfy the usual conditions of being weakly increasing in rows, and strictly decreasing in columns, but also the condition that diagonals are weakly decreasing ; conversely any such “monotonous triangle” (we shall simply say triangle) corresponds to an alternating sign matrix, as well as to some ice state.

Enumerating triangles, or more general planar partitions has been studied by Andrews [Axx], Mills, Robbins, Rumsey [MRR1], [MRR2], the story being told by Bressoud in his book [Br].

The previous model is also related with the “Ehresmann-Bruhat order” on the symmetric group (cf. [LS2]). It stems from the remark that the set of triangles of a given order is a lattice (in fact a distributive lattice): the supremum (boxwise) of two triangles is still a triangle. Now, it is easy to see that the generators of the lattice are exactly those triangles having exactly one entry with the property that the triangle remains monotonous if that entry is reduced by 1.

For example,

1 5 6 6 6 6 7
1 V 5 5 5 6
1 2 3 4 5
1 2 3 4
1 2 3 1 2 1

is such a generator (the special entry, which is allowed to decrease, is denoted by V and yields a monotonous triangle for V = 4).

Now, the alternating sign matrix corresponding to such a triangle is a bigrassmannian permutation matrix : The bigrassmannian permutations are exactly those permutations obtained from the identity permutation by cutting it into four blocks, and exchanging the two middle blocks. For instance, flipping 234 and 56

[1 | 234 | 56 |7] ↦ [1 | 56 | 234 | 7]

yields the bigrassmannian permutation associated with the previous triangle.

Of course, such permutations can be coded by the successive lengths of the blocks, the two middle blocks being non empty ( in the preceeding case, the sequence of lengths is 1, 2, 3, 1, and the permutation will be denoted by [[1, 2, 3, 1]]).

Taking the boxwise order on triangles into account, one gets the following ordered set for the generators of the lattice of triangles of dimension 4

[figure: [[0, 3, 1, 0]]; [[0, 2, 2, 0]]; [[0, 1, 3, 0]]; [[1, 2, 1, 0]]; [[1, 1, 2, 0]]; [[0, 2, 1, 1]]; [[0, 1, 2, 1]]; [[2, 1, 1, 0]]; [[1, 1, 1, 1]]; [[0, 1, 1, 2]]]

Antichains in the preceeding set (i.e. k-uples of non comparable bigrassmannian permutations) are by definition in bijection with elements of the lattice of triangles of size n, or alternating sign matrices of order n, or square ice configurations with n^{2} molecules. The reader may be willing to derive the 42 alternating sign matrices of order 4 from the above figure; there are, indeed, 42 antichains in this poset. For other connections, see [La] and for more information about the Ehresmann-Bruhat order on finite Coxeter groups, see [GK].

The problem of enumerating alternating sign matrices, due to Mills, Robbins, and Rumsey [MRR1], [MRR2] has resisted many attempts, till Zeilberger [Z1] gave a solution with the collaboration of his computer, the control of eighty eight of his friends (he has a lot more), and many references to the Bible. Shorter proofs were given by Kuperberg [Ku] and [Z2] again, after realizing that the partition function of square ice models had already been obtained by Korepin, Bogoliubov and Izergin [KBI]: it is expressed as a determinant generalizing Cauchy determinant. We are now ready to enumerate square ice models.

2. Cauchy type determinants

Given two sets of variables X = {x}, Y = {y}, of the same cardinality Cauchy introduced two matrices (we do not burden variables with indices, because they play a symmetrical role; however, to write matrices one chooses an arbitrary total order on the x’s∈ X and the y’s ∈ Y)

M_{0} = [\frac{1}{1 − xy} ]_{x∈X,y∈Y}  and  M_{1} = [\frac{1}{x − y} ]_{x∈X,y∈Y} .

From them one can extract a scalar product on symmetric functions, as well as several pairs of adjoint bases, the most conspicuous one being the self-adjoint basis of Schur functions.

Pulling out from det(M_{1}) the Vandermonde determinants Δ(X), Δ(Y) and the product ∏_{x∈X,y∈Y} (1/(x − y)), one is left with a symmetric polynomial

F_{1}(X, Y) = det(M_{1})\frac{∏(x − y)}{Δ(X) Δ(Y)} .  (1)

One easily checks that F_{1} is equal to 1, and this fact, in a sense, could summarize the first chapter of Macdonald’s book [Ma].

Borchardt [Bo] went one step further, and considered

M_{2} := [\frac{1}{(x − y)^{2}} ] .

He proved that

det(M_{2}) = det(M_{1}) Perm(M_{1}) ,

where

Perm(M_{1}) = ∑_{μ∈𝔖(X)} (\frac{1}{(x_{1} − y_{1}) ⋯ (x_{n} − y_{n})})^{μ}

is the usual permanent, the summation being over all the permutations of the x’s. Therefore the symmetric function

F_{2}(X, Y) = det(M_{2})\frac{∏(x − y)^{2}}{Δ(X) Δ(Y)}  (2)

is expressed by a summation over the symmetric group.

Now, thanks to some giants, the shoulders of which Zeilberger [Z2] escalated to provide a short alternating-sign-matrices enumeration, we know that we must polarize squares, the simplest versions being

(x − y)^{2} ⟶ (x − y)(qx − y);  (ice)
(x − y)^{2} ⟶ (x − y)(x − y + γ);  (Bethe)

with q and γ some fixed constants independent of the x’s and y’s.

Introducing another set of variables Z = {z} of the same cardinality as X and Y, one can more generally polarize as follows

(x_{i} − y_{j}) ⟶ (x_{i} − y_{j}) (z_{i} − y_{j}).

We intend to describe the symmetric polynomial

F_{Z}(X, Y) := det ([\frac{1}{(x_{i} − y_{j})(z_{i} − y_{j})}]) \frac{∏(x − y) ∏(z − y)}{Δ(X) Δ(Y)} (3)

in the two cases of physical interest

z_{i} = qx_{i}  or  z_{i} = x_{i} + γ.

In order to to this we will make use of the divided differences ∂_{i} involving pairs of variables x_{i}, z_{i}

∂_{i} : f ↦ \frac{f − f^{σ_{i}}}{x_{i} − z_{i}} ,

where σ_{i} is the transposition exchanging x_{i} and z_{i}. We also need complete functions S_{k}(A − B) of differences of sets of variables (alphabets) that can be defined by the following generating function :

∑_{0}^{∞} u^{k} S_{k}(A − B) := \frac{∏_{b∈B}(1 − ub)}{∏_{a∈A}(1 − ua)} .

We write x_{i} + z_{i} for the alphabet A = {x_{i}, z_{i}} and S_{α,β}(A − B, C − D) for the two-row Schur function

S_{α,β}(A − B, C − D) := | \begin{matrix}S_{α}(A − B) & S_{α+1}(A − B) \\ S_{β−1}(C − D) & S_{β}(C − D) \end{matrix} | .

In particular, z_{i}^{k} ∏_{y∈Y} (x_{i} − y) can be written as S_{n,k}(x_{i} − Y, x_{i} + z_{i}). However, the image of ∏_{y∈Y} (1 − y)/(1 − x_{i}) under ∂_{i} is

∏_{y∈Y} (1 − y)/(1 − x_{i})(1 − z_{i}) .

In other words, ∂_{i} sends S_{j}(x_{i} − Y) onto S_{j−1}(x_{i} + z_{i} − Y) for any j ∈ ℤ. Hence the image of S_{n,k}(x_{i} − Y, x_{i} + z_{i}) under ∂_{i} is

S_{n−1,k}(x_{i} + z_{i} − Y, x_{i} + z_{i}) = | \begin{matrix}S_{n−1}(x_{i} + z_{i} − Y) & S_{n}(x_{i} + z_{i} − Y) \\ S_{k−1}(x_{i} + z_{i}) & S_{k}(x_{i} + z_{i}) \end{matrix} | (4)

that can be developped by linearity in Y into

∑_{h=−1}^{n−1} S_{h,k}(x_{i} + z_{i}, x_{i} + z_{i}) S_{n−1−h}(−Y) (5)

= ∑_{h=k}^{n−1} S_{h,k}(x_{i} + z_{i}) S_{n−1−h}(−Y) − ∑_{h=0}^{k−1} S_{k−1,h}(x_{i} + z_{i}) S_{n−h}(−Y). (6)

On the other hand, the image of the Cauchy determinant |1/(z − y)| under the product ∂_{1}, …, ∂_{n} is the determinant of

M_{Z} := [\frac{1}{(x_{i} − y_{j}) (z_{i} − y_{j})}] ,

since each ∂_{i} acts on row i only. Write R(X, Y) for the product of differences ∏(x − y). The Cauchy determinant |1/(z − y)| is equal to

\frac{Δ(Y)}{R(X, Y) R(Z, Y)}Δ(Z) R(X, Y) = \frac{Δ(Y)}{R(X, Y) R(Z, Y)} det(M_{3}) , (7)

with

M_{3} := [S_{n,j−1}(x_{i} − Y, x_{i} + z_{i})]

Now, the factor Δ(Y) (R(X, Y) R(Z, Y))^{−1} commutes with the product of the ∂_{i}, since it is symmetrical in the x_{i} and z_{i}. According to (4), the image of det(M_{3}) is therefore equal to the determinant of

M_{4} := [S_{n−1,j−1}(x_{i} + z_{i} − Y, x_{i} + z_{i})] .  (8)

Expansion (5) exactly tells that the matrix M_{4} factorizes into a product of a matrix of two-part Schur functions in (x_{i} + z_{i}), and a matrix of Λ_{i} := S_{1^{i}}(Y) or zeroes.

For example, for n = 2, one has

( \begin{matrix}s_{0}(x_{1} + z_{1}) & s_{1}(x_{1} + z_{1}) & s_{1,1}(x_{1} + z_{1}) \\ s_{0}(x_{2} + z_{2}) & s_{1}(x_{2} + z_{2}) & s_{1,1}(x_{2} + z_{2}) \end{matrix} ) ( \begin{matrix}−Λ_{1} & −Λ_{2} \\ Λ_{0} & 0 \\ 0 & Λ_{0} \end{matrix} ) .

For n = 3,

(\begin{matrix}1 & s_{1}(x_{1} + z_{1}) & s_{2}(x_{1} + z_{1}) & s_{1,1}(x_{1} + z_{1}) & s_{2,1}(x_{1} + z_{1}) & s_{2,2}(x_{1} + z_{1}) \\ 1 & s_{1}(x_{2} + z_{2}) & s_{2}(x_{2} + z_{2}) & s_{1,1}(x_{2} + z_{2}) & s_{2,1}(x_{2} + z_{2}) & s_{2,2}(x_{2} + z_{2}) \\ 1 & s_{1}(x_{3} + z_{3}) & s_{2}(x_{3} + z_{3}) & s_{1,1}(x_{3} + z_{3}) & s_{2,1}(x_{3} + z_{3}) & s_{2,2}(x_{3} + z_{3}) \end{matrix})

×  ( \begin{matrix}Λ_{2} & Λ_{3} & 0 \\ −Λ_{1} & 0 & Λ_{3} \\ Λ_{0} & 0 & 0 \\ 0 & −Λ_{1} & −Λ_{2} \\ 0 & Λ_{0} & 0 \\ 0 & 0 & Λ_{0} \end{matrix} ) .

Finally, for n = 4, writing s_{λ} for the Schur functions of x_{i} + z_{i}, i = 1, …, 4, the factorization is

[s_{0}, s_{1}, s_{2}, s_{3}, s_{11}, s_{21}, s_{22}, s_{31}, s_{32}, s_{33}] ( \begin{matrix}−Λ_{3} & −Λ_{4} & 0 & 0 \\ Λ_{2} & 0 & −Λ_{4} & 0 \\ −Λ_{1} & 0 & 0 & −Λ_{4} \\ Λ_{0} & 0 & 0 & 0 \\ 0 & Λ_{2} & Λ_{3} & 0 \\ 0 & −Λ_{1} & 0 & Λ_{3} \\ 0 & 0 & −Λ_{1} & −Λ_{2} \\ 0 & Λ_{0} & 0 & 0 \\ 0 & 0 & Λ_{0} & 0 \\ 0 & 0 & 0 & Λ_{0} \end{matrix} ) .

Any specialization z_{i} = g(x_{i}), g being an arbitrary function of one variable, will allow to factor out a matrix of determinant Δ(X) from the left matrix, and thus to explicit the symmetric function F_{Z}(X, Y). The two-row Schur function S_{α,β}(x_{i} + z_{i}) becomes a polynomial f(x_{i}; α, β) of degree n(α, β) that can be formally written S_{n(α,β)}(x_{i} − A_{α,β}), for some alphabet A_{α,β} of cardinality n(α, β) (= the “alphabet of zeroes” of the polynomial f(x_{i}; α, β) ).

Now, for any integer k, one has the expansion

\begin{aligned}S_{k}(x_{i} − A_{α,β}) & = S_{k}((x_{i} − X) + (X − A_{α,β})) \\ & = ∑_{0≤j≤n−1} S_{k−j}(x_{i} − X) S_{j}(X − A_{α,β}) . \end{aligned}

Therefore, from the matrix [S_{n(α,β)}(x_{i} − A_{α,β})], one can extract the left factor [S_{j−1}(x_{i} − X)]_{1≤j,i≤n} (the determinant of which is Δ(X)) and one is left with the matrix

[S_{n(α,β)−i+1}(X − A_{α,β})]_{n−1≥α≥β≥0;1≤i≤n} .  (9)

Let us be more precise in the case of Bethe’s function (we refer to [Ga] for many other expressions of this function). For z = x + γ, the Schur function S_{α,β}(x + z) specializes to

\frac{1}{γ} | \begin{matrix}(x + γ)^{α+1} & (x + γ)^{β} \\ x^{α+1} & x^{β} \end{matrix} | = (x + γ)^{β} ∑_{i=0}^{α−β} x^{α−i}γ^{i}\binom{α + 1 − β}{i + 1}  (10)

= ∑_{0}^{α} γ^{i}x^{α+β−i} (\binom{α + 1}{i} − \binom{i}{α + 1 − i})

Let us write the preceding polynomial as

∑_{0≤i≤α+β} c_{α,β}^{i}γ^{i}x^{α+β−i}

and for any alphabet X, and any partition of length ≤ 2, define

S_{α,β}^{k}(X) := ∑_{0≤i≤α+β} c_{α,β}^{i}γ^{i}S_{α+β−i−k}(X) .  (11)

Write χ(a = b) for the Boolean function which tests equality. The combination of (8) and (10) produces the following factorization.

Theorem γ . Let X and Y be two alphabets of cardinality n, γ an extra parameter. Then the symmetric function

F^{γ}(X, Y) := |\frac{1}{(x − y)(x − y + γ)}|_{x∈X,y∈Y} \frac{∏(x − y)(x − y + γ)}{Δ(X) Δ(Y)} (12)

is the determinant of the product of matrices

[S_{α,β}^{i−1}(X)]_{1≤i≤n}^{n−1≥α≥β≥0}

× [χ(β =j−1)S_{n−1−α}(−Y)−χ(α=j−2)S_{n−β}(−Y)]_{n−1≥α≥β≥0}^{1≤j≤n} .

The following factorizations and Bethe functions are readily computed by ACE [AV], the output being randomly distributed by Maple. Writing Λ_{i} for (−1)^{i}S_{i}(−Y), and s_{i} for S_{i}(X), we get:

( \begin{matrix}1 & γ + 2s_{1} & γs_{1} + s_{2} \\ 0 & 2 & γ + s_{1} \end{matrix} ) ( \begin{matrix}−Λ_{1} & −Λ_{2} \\ Λ_{0} & 0 \\ 0 & Λ_{0} \end{matrix} )

= (2Λ_{2} + g^{2} − gΛ_{1}) + (g − Λ_{1})s_{1} + 2s_{1,1} ;

( \begin{matrix}1 & γ + 2s_{1} & γ^{2} + 3γs_{1} + 3s_{2} & γs_{1} + s_{2} & γ^{2}s_{1} + 3γs_{2} + 2s_{3} \\ 0 & 2 & 3γ + 3s_{1} & γ + s_{1} & γ^{2} + 3γs_{1} + 2s_{2} \\ 0 & 0 & 3 & 1 & 3γ + 2s_{1} \end{matrix}

\begin{matrix}γ^{2}s_{2} + 2γs_{3} + s_{4} \\ γ^{2}s_{1} + 2γs_{2} + s_{3} \\ γ^{2} + 2γs_{1} + s_{2} \end{matrix} ) × ( \begin{matrix}Λ_{2} & Λ_{3} & 0 \\ −Λ_{1} & 0 & Λ_{3} \\ Λ_{0} & 0 & 0 \\ 0 & −Λ_{1} & −Λ_{2} \\ 0 & Λ_{0} & 0 \\ 0 & 0 & Λ_{0} \end{matrix} )

= 6s_{2,2,2} + (γ^{6} − 2Λ_{1}γ^{5} + 4Λ_{1}Λ_{3}γ^{2} + 2Λ_{2}^{2}γ^{2} + 3γ^{4}Λ_{2} + Λ_{1}^{2}γ^{4} + 6Λ_{3}^{2} − 6Λ_{3}Λ_{2}γ − 3Λ_{1}Λ_{2}γ^{3} − 3Λ_{3}γ^{3}) + (−4Λ_{3}γ^{2} − 4Λ_{1}γ^{4} + 2Λ_{2}^{2}γ + 4Λ_{1}Λ_{3}γ − 4Λ_{1}γ^{2}Λ_{2} + 2γ^{5} − 4Λ_{2}Λ_{3} + 2Λ_{1}^{2}γ^{3} + 4Λ_{2}γ^{3})s_{1} + (γ^{4} + Λ_{1}^{2}γ^{2} − Λ_{1}Λ_{2}γ + 2Λ_{1}Λ_{3} +Λ_{2}γ^{2} −2Λ_{1}γ^{3} −3Λ_{3}γ)s_{2} +(−4Λ_{1} +6γ)s_{2,2,1} +(3γ^{3} −3Λ_{3} −Λ_{1}Λ_{2} − 4Λ_{1}γ^{2} + 3Λ_{2}γ + Λ_{1}^{2}γ)s_{2,1} + (2Λ_{2}^{2} + 2Λ_{1}^{2}γ^{2} − 4Λ_{1}Λ_{2}γ − 6Λ_{1}γ^{3} + 4γ^{4} + 6Λ_{2}γ^{2})s_{1,1} + (12Λ_{3} − 8Λ_{1}γ^{2} + 6γ^{3} − 4Λ_{1}Λ_{2} + 4Λ_{1}^{2}γ)s_{1,1,1} + (2Λ_{2} + 2γ^{2} − 2Λ_{1}γ)s_{2,2} + (2Λ_{1}^{2} + 6γ^{2} − 6Λ_{1}γ)s_{2,1,1}

On the other hand, when the z_{i} specialize to qx_{i}, one has a more convenient factorization into smaller matrices. Indeed,

S_{α,β}(x + qx) = x^{α+β}(q^{β} + q^{β+1} + ⋯ + q^{α}) = x^{α+β}q^{β} [α − β + 1]_{q} , (13)

with [k]_{q} := 1 + q + ⋯ + q^{k−1}. Combining these values with expansion (6), one gets the following property.

Theorem q. Let X and Y be two alphabets of cardinality n, q an extra parameter. Then the symmetric function

F_{q}(X, Y) := |\frac{1}{(x − y)(qx − y)}|_{x∈X,y∈Y} \frac{∏(x − y)(qx − y)}{Δ(X) Δ(Y)}  (14)

is the determinant of the product of

[S_{j−i}(X)]_{1≤i≤n,1≤j≤2n−1}[\frac{q^{j−k+1} − q^{k−1}}{q − 1} S_{n−j+k−1}(−Y)]_{1≤j≤2n−1,1≤k≤n}

The coefficient of any Schur function S_{λ}(X), λ_{1} ≥ ⋯ ≥ λ_{n} ≥ 0, in the expansion of F_{q}(X, Y) is equal to the minor on rows λ_{n} + 1, …, λ_{1} + n, columns 1, …, n of the matrix in Y.

For example, for n = 2, F_{q}(X, Y) is the determinant of the product

( \begin{matrix}S_{0} & S_{1} & S_{2} \\ 0 & S_{0} & S_{1} \end{matrix} )·( \begin{matrix}−Λ_{1} & −Λ_{2} \\ 1 + q & 0 \\ 0 & q \end{matrix} ) = (1+q)Λ_{2}−q(x_{1}+x_{2})Λ_{1}+(q+q^{2}) x_{1}x_{2}

still writing S_{k} for S_{k}(X), and Λ_{i} for (−1)^{i}S_{i}(−Y), i.e. for the i-th elementary symmetric function of Y.

For n = 3, 4, 5, writing [k] for the q-integer [k]_{q}, ACE [AV] produces the right matrices

( \begin{matrix}Λ_{2} & Λ_{3} & 0 \\ −[2]Λ_{1} & 0 & [2]Λ_{3} \\ [3] & −qΛ_{1} & −qΛ_{2} \\ 0 & q[2] & 0 \\ 0 & 0 & q^{2} \end{matrix} ) , ( \begin{matrix}−Λ_{3} & −Λ_{4} & 0 & 0 \\ [2]Λ_{2} & 0 & −[2]Λ_{4} & 0 \\ −[3]Λ_{1} & qΛ_{2} & qΛ_{3} & −[3]Λ_{4} \\ [4] & q[2]Λ_{1} & 0 & q[2]Λ_{3} \\ 0 & q[3] & −q^{2}Λ_{1} & −q^{2}Λ_{2} \\ 0 & 0 & q^{2}[2] & 0 \\ 0 & 0 & 0 & q^{3} \end{matrix} ) ,

Λ_{4}  Λ_{5}  0  0  0
−[2]Λ_{3}  0  [2]Λ_{5}  0  0
[3]Λ_{2} −qΛ_{3}  −qΛ_{4}  [3]Λ_{5}  0
−[3]Λ_{1} q[2]Λ_{2}  0  −q[2]Λ_{4} [4]Λ_{5}
[5] −q[3]Λ_{1} q^{2}Λ_{2}  q^{2}Λ_{3} −q[3]Λ_{4}
0  q[4] −q^{2}[2]Λ_{1}  0  q^{2}[2]Λ_{3}
0  0  q^{2}[3]  −q^{3}Λ_{1} −q^{3}Λ_{2}
0  0  0  q^{3}[2]  0
0  0  0  0  q^{4}

and the expansion of F_{q}(X, Y), for n = 3, is (writing, for each Schur function of X, its coefficient in Y as a sum of Schur functions in Y)

s_{0}(X) : (q + 1)(q^{2} + q + 1)(s_{111111} + s_{21111} + s_{222} + s_{2211}) s_{1}(X) : −q(q + 1)^{2}(s_{11111} + s_{221} + s_{2111}) s_{2}(X) : q^{2}(s_{1111} + s_{211})(q + 1) s_{11}(X) : q^{2}(s_{1111} + s_{22} + s_{211})(q + 1) s_{21}(X) : −q^{2}(qs_{21} + 2qs_{111} + s_{111}q^{2} + s_{111}) s_{22}(X) : q^{3}s_{11}(q + 1) s_{111}(X) : q(q + 1)^{2}(s_{111}q^{2} − qs_{21} + s_{111}) s_{211}(X) : (q + 1)q^{3}(s_{2} + s_{11}) s_{221}(X) : −s_{1}q^{3}(q + 1)^{2} s_{222}(X) : sq^{3}(q + 1)(q^{2} + q + 1).

Lastly, for n = 4 one has the following expansion of the function F_{q}(X, Y) (that it is impossible to obtain directly from the expansion of (3), the object being to large for Maple):

s_{0}(X) : (q^{2}+1)(q^{2}+q+1)(q + 1)^{2}(s_{1...1}+2s_{21...1}+3s_{2211...1}+5s_{22221...1}+ 4s_{2221...1} + 3s_{2222211} + s_{31...1} + 2s_{321...1} + 4s_{3222111} + 3s_{3221...1} + s_{222222} + 2s_{322221} + s_{331...1} + 3s_{332211} + 2s_{3321...1} + s_{3333} + 2s_{33321} + s_{33222} + s_{333111})

s_{1}(X) : −q(q + 1)(q^{2} + q + 1)^{2}(2s_{21...1} + s_{1...111} + 2s_{222221} + s_{31...11} + 2s_{321...1} + 4s_{2221...1} + 3s_{221...1} + 4s_{2222111} + 3s_{3221...1} + 3s_{322211} + s_{3332} + s_{33311} + s_{331...1} + 2s_{33221} + 2s_{332111} + s_{32222})

s_{2}(X) : q^{2}(q^{2} + q + 1)(q + 1)^{2}(s_{1...11} + 2s_{21...11} + 3s_{221...1} + 3s_{222211} + 3s_{2221...1} + s_{22222} + s_{31...1} + 2s_{321...1} + 2s_{32221} + 2s_{322111} + s_{331...1} + s_{3322} + s_{33211})

s_{3}(X) : −q^{3}(q + 1)(q^{2} + q + 1)(s_{1...1} + 2s_{21...1} + 2s_{221...1} + 2s_{22221} + 2s_{222111} + s_{31...1} + s_{321...1} + s_{3222} + s_{32211})

s_{11}(X) : q^{2}(q + 1)^{2}(q^{2}s_{33211} + q^{2}s_{322111} + q^{2}s_{3331} + q^{2}s_{2221...1} + qs_{3331} + 3qs_{221...1} + 3qs_{222211} + 4qs_{2221...1} + 2qs_{21...11} + qs_{1...11} + qs_{331...1} + qs_{3322} + 2qs_{33211} + qs_{22222} + qs_{31...1} + 2qs_{321...1} + 2qs_{32221} + 3qs_{322111} + s_{33211} + s_{322111} + s_{3331} + s_{2221...1})

s_{21}(X) : −q^{3}(q + 1)^{3}(s_{1...1} + 2s_{2111...1} + 3s_{222111} + 3s_{221...1} + 2s_{22221} + s_{31...1} + 2s_{32211} + 2s_{321...1} + s_{3222} + s_{3321} + s_{33111})

s_{31}(X) : q^{3}(q + 1)^{2}(q^{2}s_{1...11} + q^{2}s_{21...1} + q^{2}s_{221...1} + q^{2}s_{2222} + q^{2}s_{22211} + qs_{1...11}+2qs_{21...1}+2qs_{221...1}+qs_{2222}+2qs_{22211}+qs_{31...1}+qs_{32111}+qs_{3221}+ s_{1...11} + s_{21...111} + s_{221...1} + s_{2222} + s_{22211})

s_{22}(X) : q^{4}(q + 1)^{2}(s_{1...11} + 2s_{2111111} + 3s_{221...1} + s_{2222} + 2s_{22211} + 2s_{32111} + s_{3311} + s_{31...1} + s_{3221})

s_{32}(X) : −q^{4}(q + 1)(q^{2}s_{1...1} + q^{2}s_{21...1} + q^{2}s_{22111} + q^{2}s_{2221} + qs_{31111} + qs_{3211}+3qs_{22111}+2qs_{2221}+2qs_{1...1}+3qs_{21...1}+s_{1...1}+s_{21...1}+s_{22111}+s_{2221})

s_{33}(X) : q^{5}(q + 1)^{2}(s_{1...1} + s_{21...1} + s_{2211})

s_{111}(X) : q^{2}(q + 1)(−q^{2}s_{333} − 2q^{2}s_{3321} − q^{2}s_{33111} + qs_{1...1} + 2qs_{21...1} + qs_{222111} +2qs_{221...1} +2qs_{22221} +qs_{31...1} +qs_{321111} −qs_{333} −qs_{3321} +qs_{3222} + q^{2}s_{3222}−q^{2}s_{32211}+q^{2}s_{1...1111}+2q^{2}s_{21...1}+q^{2}s_{221...1}+2q^{2}s_{22221}+q^{2}s_{31...1}+ 2q^{4}s_{21...1}+2q^{4}s_{222111}+2q^{4}s_{221...1}+2q^{4}s_{22221}+q^{4}s_{31...1}+q^{4}s_{32211}+q^{4}s_{1...11}+ q^{4}s_{321...1}+q^{4}s_{3222}+q^{3}s_{1...1}+2q^{3}s_{21...1}+q^{3}s_{222111}+2q^{3}s_{221...1}+2q^{3}s_{22221}+ q^{3}s_{31...1} + q^{3}s_{321...1} − q^{3}s_{333} − q^{3}s_{3321} + q^{3}s_{3222} + s_{31...1} + s_{321...1} + s_{3222} + s_{32211} + 2s_{221...1} + 2s_{22221} + 2s_{222111} + s_{1...1} + 2s_{21...1})

s_{211}(X) : −q^{2}(q + 1)^{2}(qs_{21...1} − 2q^{2}s_{3221} + qs_{221...1} + qs_{2222} − q^{2}s_{332} + qs_{1...11} − q^{2}s_{3311} − q^{2}s_{31...1} − 2q^{2}s_{32111} − q^{2}s_{22211} + qs_{22211} + q^{2}s_{1...11} − q^{2}s_{221...1} + q^{2}s_{2222} + q^{3}s_{22211} + q^{3}s_{1...11} + q^{3}s_{21...1} + q^{3}s_{221...1} + q^{3}s_{2222} + q^{4}s_{2222} + s_{1...11} + s_{21...1} + s_{221...1} + s_{2222} + s_{22211} + q^{4}s_{22211} + q^{4}s_{1...11} + q^{4}s_{221111} + q^{4}s_{21...1})

s_{311}(X) : −q^{4}(q + 1)(q^{2}s_{22111} + q^{2}s_{2221} + q^{2}s_{1...1} + q^{2}s_{21...1} + 2qs_{2221} + qs_{3211} + qs_{31...1} + 2qs_{22111} + 2qs_{21...1} + qs_{1...1} + qs_{322} + s_{22111} + s_{2221} + s_{1...1} + s_{21...1})

s_{221}(X) : −(q +1)q^{3}(−q^{4}s_{1...1} −q^{4}s_{21...1} −q^{4}s_{22111} −q^{4}s_{2221} +q^{3}s_{3211} − q^{3}s_{1...1} + q^{3}s_{31...1} − q^{3}s_{2221} − q^{2}s_{1...1} + 2q^{2}s_{22111} + q^{2}s_{322} + q^{2}s_{21...1} + 2q^{2}s_{31...1} + 3q^{2}s_{3211} + q^{2}s_{331} + qs_{3211} − qs_{1...1} + qs_{31...1} − qs_{2221} − s_{1...1} − s_{21...1} − s_{22111} − s_{2221})

s_{321}(X) : q^{5}(2s_{1...1} +2q^{2}s_{1...1} +3q^{2}s_{21...1} +q^{2}s_{222} +2q^{2}s_{2211} +5qs_{21...1} + 3qs_{1...1} + qs_{321} + 2qs_{222} + 4qs_{2211} + 2qs_{3111} + s_{3111} + 2s_{2211} + q^{2}s_{3111} + 3s_{21...1} + s_{222})

s_{331}(X) : −q^{5}(q+1)(q^{2}s_{1...1}+q^{2}s_{2111}+2qs_{1...1}+qs_{221}+2qs_{2111}+s_{1...1}+ s_{2111})

s_{222}(X) : −q^{4}(q + 1)^{2}(q^{2}s_{222} − qs_{3111} − qs_{321} − qs_{2211} − qs_{21...1} + s_{222})

s_{322}(X) : −q^{5}(q+1)(q^{2}s_{1...1}+q^{2}s_{2111}+qs_{11...1}+2qs_{2111}+qs_{311}+qs_{221}+ s_{1...1} + s_{2111})

s_{332}(X) : q^{5}(q + 1)^{2}(q^{2}s_{1...1} + qs_{1...1} + qs_{211} + s_{1...1})

s_{333}(X) : −s_{111}q^{6}(q + 1)(q^{2} + q + 1)

s_{1...1}(X) : q(q + 1)^{2}(q^{2}s_{332} + s_{1...11} + s_{21...1} + s_{221...1} + s_{2222} + s_{22211} − 2q^{4}s_{32111} − 2q^{4}s_{31...1} + q^{4}s_{332} − q^{4}s_{3221} + 2q^{2}s_{1...1} + 2q^{2}s_{2222} + q^{2}s_{22211} − q^{5}s_{32111} − q^{5}s_{31...1} − q^{5}s_{3221} + q^{6}s_{1...1} + q^{6}s_{2111111} + q^{6}s_{221...1} + q^{6}s_{2222} + q^{6}s_{22211} + q^{3}s_{22211} − q^{3}s_{32111} − 2q^{3}s_{31...1} + q^{3}s_{332} − q^{3}s_{3221} + 2q^{3}s_{2222} + q^{3}s_{3311} + q^{4}s_{22211} + q^{5}s_{1...1} + q^{5}s_{2222} + 2q^{3}s_{1...1} + q^{3}s_{221...1} + 2q^{4}s_{1...1} + 2q^{4}s_{2222} + qs_{1...1} + qs_{2222} − 2q^{2}s_{31...1} − 2q^{2}s_{32111} − q^{2}s_{3221} − qs_{31...1} − qs_{32111} − qs_{3221})

s_{2111}(X) : q^{3}(q + 1)^{3}(2q^{2}s_{21...1}+q^{2}s_{1...1}+q^{2}s_{31...1}+2q^{2}s_{22111}+q^{2}s_{3211}+ q^{2}s_{2221} −qs_{322} −qs_{331} −qs_{3211} −qs_{2221} −qs_{22111} +2s_{21...1} +s_{1...1} +s_{31...1} + 2s_{22111} + s_{3211} + s_{2221})

s_{3111}(X) : −q^{4}(q + 1)^{2}(q^{2}s_{21...1} + q^{2}s_{3111} − qs_{321} − qs_{222} − qs_{2211} + s_{21...1} + s_{3111})

s_{2211}(X) : −q^{3}(q + 1)^{2}(q^{4}s_{2211} + q^{4}s_{1...11} + q^{4}s_{21...1} + 2q^{3}s_{2211} + 2q^{3}s_{21111} + 2q^{3}s_{1...1} + q^{2}s_{21...1} + 2q^{2}s_{1...1} − q^{2}s_{3111} − q^{2}s_{33} − 2q^{2}s_{321} − q^{2}s_{222} + 2qs_{2211} + 2qs_{21...1} + 2qs_{1...1} + s_{2211} + s_{111...1} + s_{21...1})

s_{3211}(X) : q^{4}(q+1)(q^{4}s_{1...1}+q^{4}s_{2111}+q^{3}s_{1...1}−q^{3}s_{221}+q^{3}s_{2111}−q^{2}s_{32}+ q^{2}s_{1...1} − q^{2}s_{311} − 3q^{2}s_{221} + qs_{1...1} − qs_{221} + qs_{2111} + s_{11111} + s_{2111})

s_{3311}(X) : q^{6}(q + 1)^{2}(s_{1...1} + s_{22} + s_{211})

s_{2221}(X) : q^{4}(q + 1)^{3}(q^{2}s_{1...1} + q^{2}s_{221} + q^{2}s_{2111} − qs_{311} − qs_{32} − qs_{221} − qs_{2111} + s_{1...1} + s_{221} + s_{2111})

s_{3221}(X) : −q^{4}(q + 1)^{2}(s_{1...1}q^{4} + q^{3}s_{1...1} − q^{2}s_{31} + q^{2}s_{1...1} − q^{2}s_{22} − 2q^{2}s_{211} + qs_{1...1} + s_{1...1})

s_{3321}(X) : −q^{6}(q + 1)^{3}(s_{21} + s_{111})

s_{3331}(X) : s_{11}q^{6}(q^{2} + q + 1)(q + 1)^{2}

s_{2222}(X) : q^{3}(q + 1)^{2}(q^{6}s_{1...1} + s_{1...1}q^{5} − q^{5}s_{211} + 2s_{1...1}q^{4} − q^{4}s_{211} + q^{4}s_{31} − q^{3}s_{211} + q^{3}s_{31} + q^{3}s_{22} + 2q^{3}s_{1...1} + 2q^{2}s_{1...1} − q^{2}s_{211} + q^{2}s_{31} + qs_{1...1} − qs_{211} + s_{1...1})

s_{3222}(X) : q^{5}(q + 1)(q^{4}s_{111} − q^{3}s_{3} + q^{3}s_{111} − q^{3}s_{21} − q^{2}s_{3} − 2q^{2}s_{21} + q^{2}s_{111} − qs_{3} + qs_{111} − qs_{21} + s_{111})

s_{3322}(X) : q^{6}(q + 1)^{2}(s_{2}q^{2} + qs_{2} + qs_{11} + s_{2})

s_{3332}(X) : −s_{1}q^{6}(q + 1)(q^{2} + q + 1)^{2}

s_{3333}(X) : q^{6}(q^{2} + q + 1)(q^{2} + 1)(q + 1)^{2}

References

[AV] ACE, S. Veigneau, ACE. an algebraic environment for the computer algebra system MAPLE,

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

[A77] G. Andrews. Plane Partitions II: The equivalence of the Bender-Knuth and Mac Mahon conjecture. Pacific J. 72 (1977) 283–291.

[A78] G. Andrews. Plane Partitions I: The Mac Mahon conjecture. Studies in Foundations and Combinatorics, Advances in Maths Supplementary Studies 1 (1978) 131–150.

[A79] G. Andrews. Plane Partitions III: The weak Macdonald conjecture. Inventiones M. 53 (1979) 193–225.

[A87] G. Andrews. Plane Partitions IV: A conjecture of Mills-Robbins-Rumsey. Aequationes Math. 33 (1987) 230–250.

[Bo] C.W. Borchardt. Bestimmung der symmetrischen Verbindungen ihrer erzeugenden Funktion, Crelle J. 53 (1855) 193-198.

[Br] D. Bressoud. Proofs and Confirmations. The story of the alternating sign matrix conjecture. book to appear.

[Ga] M. Gaudin. La fonction d’onde de Bethe, Masson (1983).

[GK] M. Geck, S. Kim. Bases for the Bruhat-Chevalley order on all finite Coxeter groups, J. of Algebra 197 (1997) 278–310.

[KBI] V. Korepin, N. Bogoliubov, A. Izergin. Quantum inverse scattering method and correlation functions. Cambridge University Press (1993)

[Ku] G. Kuperberg. Another proof of the refined alternating sign matrix conjecture. Inter. Math. Res. Notes (1996) 139–150.

[La] A. Lascoux. Ordonner le groupe symétrique: pourquoi utiliser l’algèbre de Iwahori-Hecke ? ICM Berlin 1998, Documenta Mathematica, volume III, (1998) 355–364.

[LS1] A. Lascoux & M.P. Schützenberger, Algèbre des différences divisées, Discrete Maths 99 (1992) 165-179.

[LS2] A. Lascoux & M.P. Schützenberger, Treillis et bases des groupes de Coxeter, Electronic Journal of Combinatorics 3 (1996) R27

[Ma] I.G. Macdonald. Symmetric functions and Hall polynomials Oxford University Press (1995).

[MRR1] W. Mills, D. Robbins, H. Rumsey. Proof of the Macdonald conjecture. Inventiones M.66 (1982) 73–87.

[MRR2] W. Mills, D. Robbins, H. Rumsey. Alternating sign matrices and descending plane partitions. J.Comb. Theory A 34 (1983) 340–359.

[Z1] D. Zeilberger. Proof of the alternating sign matrix conjecture. Electronic J. Comb. 3 (1996) R 13.

[Z2] D. Zeilberger. Proof of the refined alternating sign matrix conjecture. New York J. Math 2 (1996) 59–68.

C.N.R.S., Institut Gaspard Monge Université de Marne-la-Vallée,

5 Bd Descartes, Champs sur Marne, 77454 Marne La Vallée Cedex 2 FRANCE

                                    Alain.Lascoux@univ-mlv.fr
                          http://phalanstere.univ-mlv.fr/∼al