A GOG–MAGOG CONJECTURE

C. Krattenthaler

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

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

Abstract. We present a conjecture relating magog trapezoids to gog trapezoids. This generalizes a conjecture due to Mills, Robbins and Rumsey [J. Combin. Theory A 42 (1986), 277–292]. In the second part of this note, we show how to simplify Act I of Zeilberger’s celebrated proof [Electron. J. Combin. 3 (no. 2, “The Foata Festschrift”) (1996), Art. #R13] of the alternating sign matrix conjectre.

Definition. An (m, n, k)-Gog trapezoid is an array of positive integers consisting of the first k columns of an array

a_{11} a_{12} . . . . . . . . . . . . . a_{1n}
a_{21} a_{22} … a_{2,n−1}
. . . . . . . . . . . . .
a_{n1}

such that rows are strictly increasing, columns are weakly increasing, and diagonals from lower-left to upper-right are weakly increasing, and such that the entries in the right-most column are bounded by a_{1k} ≤ m + k, a_{2k} ≤ m + k + 1, …, a_{n+1−k,k} ≤ m + n.

Definition. An (m, n, k)-Magog trapezoid is an array of positive integers consisting of the first k rows of an array

b_{11} b_{12} . . . . . . . . . . . b_{1n}
b_{21} b_{22} … b_{2,n−1}
. . . . . . . . . . . . .
b_{n1}

such that rows are weakly increasing, columns are weakly decreasing, and such that the entries in the first row are bounded by b_{11} ≤ m + 1, b_{12} ≤ m + 2, …, b_{1n} ≤ m + n.

Typeset by AMS-TEX

Conjecture. The number of (m, n, k)-Gog trapezoids with s Maxima in the rightmost column and t Minima in the left-most column equals the number of (m, n, k)- Magog trapezoids with t Maxima in the first row and s Minima in the last row. Here, a Maximum is an entry that is equal to its upper bound, whereas a Minimum is an entry that is 1.

What we would like to find is a bijection between the two sets in question.

What is known about this conjecture?

(1) If m = 0 and k = n, and if we forget about Maxima and Minima, then the conjecture reduces to the equality of the number of n × n alternating sign matrices and the number of totally symmetric self-complementary plane partitions contained in a (2n) × (2n) × (2n) box. As we know, this is a theorem, thanks to Andrews [1] and Zeilberger [6], but no bijection is known. The translation of alternating sign matrices into the relevant Gog trapezoids is explained in Section 5 of [4]. The translation of totally symmetric self-complementary plane partitions into the relevant Magog trapezoids is explained in Section 2 of [5].

(2) If m = 0 and if we forget about Maxima and Minima, then this is Zeilberger’s main theorem in [6] (namely Lemma 1), but, again, his proof is highly nonbijective.

(3) If m = 0, then the above conjecture reduces to Conjecture 7’ in [5].

(4) If k = 1 then we want to show that the number of arrays of positive integers

a_{1} a_{2} … a_{n}

with a_{k} ≤ m + k and with s Maxima and t Minima is exactly the same as the number of arrays of the same type but with t Maxima and s Minima. It is easy to show that the number in question is

\binom{m + 2n − s − t − 2}{m + n − 2} − \binom{m + 2n − s − t − 2}{m + n − 1},

which is indeed symmetric in s and t.

There is also a bijective way to do this, which is as follows: Start with the array. At each step look for the left-most entry with minimal difference to its corresponding upper-bound (i.e., find k minimal such that (m + k) − a_{k} is minimal). Remove it (i.e., remove a_{k}), and record this difference + 1 (i.e., record (m + k) − a_{k} + 1).

Here is an example for n = 6, m = 1, s = 2, t = 1: The first line indicates the upper bounds. The second line is the array with which we start. The subsequent lines show the rest of the array after each step. In the right-most column the difference (m + k) − a_{k} is displayed.

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

Thus the output of the algorithm is the array

1 1 2 2 5 7 ,

which has indeed t = 1 Maxima and s = 2 Minima.

It is obvious that this mapping translates Maxima into Minima. Since it can also be shown that this map is an involution (i.e., if one applies the same mapping to the output one recovers the input), it follows that Minima are mapped into Maxima.

(5) If k = 2, and if we forget about Maxima and Minima, bijective proofs have been found by Cheballah and Biane [3], and by Bettinelli [2]. The bijection of Cheballah and Biane makes use of an involution of Schützenberger on semistandard tableaux. It is rather involved, but it preserves certain statistics (not the number of Maxima and Minima, though). Bettinelli’s bijection is short and elegant. It uses very simple moves of entries, but it does not preserve any natural statistics.

Now, let us consider (m, n, k)-Magog trapezoids with last entry in each row fixed, say

\begin{matrix}b_{11} & & & b_{12} & & & . . . . . . . . . . . . . & B_{1} \\ b_{21} & b_{22} & . . . . . . . . & B_{2} \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ b_{k1} & b_{k2} & … & B_{k} \end{matrix}  (1)

with B_{1}, B_{2}, …, B_{k} fixed.

Proposition. The number of (m, n, k)-Magog trapezoids with last entries in each row as shown in (1) equals

CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{B_{i}+k−i−1}(1 − x_{i})^{k+n+m}} ) ,  (2)

where

Δ_{k}(m; x_{1}, …, x_{k}) = det_{1≤i,j≤k} (x_{j}^{k−i}(1 − x_{j})^{m+k+i−1} − (1 − x_{j})^{k−i}x_{j}^{m+k+i−1})

= ∑_{g∈B_{k}} sgn g · g [∏_{i=1}^{k} x_{i}^{k−i}(1 − x_{i})^{m+k+i−1}] .

Here, B_{k} denotes the hyperoctahedral group of rank k, acting on (x_{1}, x_{2}, …, x_{k}) by permuting coordinates and by replacing x_{i} by 1 − x_{i}.

Remark. This generalizes Subsublemma 1.1.1 in [6]. At the same time, the proof below is much simpler than the one in [6].

Proof. First we convert the (m, n, k)-Magog trapezoids into arrays of the same form which are strictly increasing along rows, by adding k − i to each entry in the i-th row. Thus, we obtain arrays of the form

b_{11} b_{12} . . . . . . . . . . . . . . . . . . . . B_{1} + k − 1
b_{21} b_{22} . . . . . . . . B_{2} + k − 2
. . . . . . . . . . . . . . . . . .
b_{k1} b_{k2} … B_{k}

with B_{1}, B_{2}, …, B_{k} fixed, with weakly increasing rows, strictly increasing columns, and such that the entries in the first row satisfy b_{11} ≤ m + k, b_{12} ≤ m + k + 1, …. Now, by reading row-wise, we convert these arrays into families (P_{1}, P_{2}, …, P_{k}) of nonintersecting lattice paths, P_{i} running from A_{i} = (i − 1, k − i + 1) to E_{i} = (n − 1, B_{i} + k − i), all the paths staying below the line y = x + k + m, being allowed to touch it. In this correspondence, the i-th path corresponds to the i-th row of the array in the obvious way (heights of horizontal steps correspond to entries in the array, ignoring the last entry in each row, B_{i} + i − 1, which is encoded in the end point of the path anyway).

By Gessel–Viennot theory, the number of these families of nonintersecting lattice paths equals the determinant

det_{1≤i,j≤k} (P^{+}(A_{i} → E_{j})),  (3)

where P^{+}(A → E) denotes the number of lattice paths from A to E which stay (weakly) below the line y = x+k +m. By reflection principle, these paths numbers are the difference between two path numbers. So, writing P(A → E) for the number of paths from A to E (without any restriction), and R for the reflection with respect to the line y = x + k + m + 1, expression (3) becomes

det_{1≤i,j≤k}(P^{+}(A_{i} → E_{j})) = det_{1≤i,j≤k} (P(A_{i} → E_{j}) − P(RA_{i} → E_{j}))

= det_{1≤i,j≤k} (\binom{B_{j} + n − j − 1}{n − i} − \binom{B_{j} + n − j − 1}{n + m + i − 1})

= det_{1≤i,j≤k} (CT (\frac{(1 − x)^{−n+i−1}}{x^{B_{j}+i−j−1}} − \frac{(1 − x)^{−n−m−i}}{x^{B_{j}−m−i−j}} ))

= CT ( ∏_{i=1}^{k} \frac{1}{x_{i}^{B_{i}+k−i−1}(1 − x_{i})^{n+m+k}}

× det_{1≤i,j≤k} (x_{j}^{k−i}(1 − x_{j})^{m+k+i−1} − x_{j}^{m+k+i−1}(1 − x_{j})^{k−i}) ).

□

It is an easy exercise to show that in case m = 0 the determinant Δ_{k} simplifies to

Δ_{k}(0; x_{1}, …, x_{k}) = ∏_{i=1}^{k}(1 − 2x_{i}) ∏_{1≤i<j≤k}(x_{j} − x_{i})(x_{i} + x_{j} − 1),

which is the expression that appears in [6].

Theorem. The number of (m, n, k)-Magog trapezoids equals

CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−i−1}(1 − x_{i})^{k+n+m+1} ∏_{1≤i<j≤k}(1 − x_{i}x_{j})}) ,

A GOG–MAGOG CONJECTURE 5

where Δ_{k}(m; x_{1}, …, x_{k}) is defined as in the Proposition. Remark. This generalizes Sublemma 1.1 in [6]. Proof. This is done in the same way as in [6].

We have to sum the expressions (2) over m+n−1 ≥ B_{1} ≥ B_{2} ≥ ⋯ ≥ B_{k} ≥ −∞. That is,

∑_{m+n−1≥B_{1}≥···≥B_{k}≥−∞} CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{B_{i}+k−i−1}(1 − x_{i})^{k+n+m}} )

= ∑_{0≤λ_{1}≤···≤λ_{k}} CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−i−1−λ_{i}}(1 − x_{i})^{k+n+m}} )

= CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−i−1}(1 − x_{i})^{k+n+m}} \frac{1}{(1 − x_{k})(1 − x_{k−1}x_{k}) ⋯ (1 − x_{1} ⋯ x_{k})})

= \frac{1}{k!} CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−1}(1 − x_{i})^{k+n+m}}

× ∑_{π∈S_{k}} sgn π · π [\frac{x_{1}x_{2}^{2} ⋯ x_{k}^{k}}{(1 − x_{k}) ⋯ (1 − x_{1}x_{2} ⋯ x_{k})}] )

= \frac{1}{k!} CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−1}(1 − x_{i})^{k+n+m}} \frac{x_{1} ⋯ x_{k} ∏_{1≤i<j≤k}(x_{i} − x_{j})}{∏_{i=1}^{k}(1 − x_{i}) ∏_{1≤i<j≤k}(1 − x_{i}x_{j})})

= \frac{1}{k!} CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−1}(1 − x_{i})^{k+n+m}} \frac{x_{1} ⋯ x_{k}}{∏_{i=1}^{k}(1 − x_{i}) ∏_{1≤i<j≤k}(1 − x_{i}x_{j})}

× ∑_{π∈S_{k}} sgn π · π [x_{1}^{0}x_{2}^{1} ⋯ x_{k}^{k−1}] )

= \frac{1}{k!} ∑_{π∈S_{k}} CT (π [\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−1}(1 − x_{i})^{k+n+m+1}} \frac{x_{1}x_{2}^{2} ⋯ x_{k}^{k}}{∏_{1≤i<j≤k}(1 − x_{i}x_{j})}])

= \frac{1}{k!} ∑_{π∈S_{k}} CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−1}(1 − x_{i})^{k+n+m+1}} \frac{x_{1}x_{2}^{2} ⋯ x_{k}^{k}}{∏_{1≤i<j≤k}(1 − x_{i}x_{j})})

= CT (\frac{Δ_{k}(m; x_{1}, …, x_{k})}{∏_{i=1}^{k} x_{i}^{m+n+k−1}(1 − x_{i})^{k+n+m+1}} \frac{x_{1}x_{2}^{2} ⋯ x_{k}^{k}}{∏_{1≤i<j≤k}(1 − x_{i}x_{j})}) .

□

References

1. G. E. Andrews, Plane partitions V: The t.s.s.c.p.p. conjecture, J. Combin. Theory Ser. A 66

(1994), 28–39.

2. J. Bettinelli, A simple explicit bijection between (n, 2)-Gog and Magog trapezoids, Sém. Lothar. Combin. B75 (2016), Article B75e, 9 pp.

3. H. Cheballah and P. Biane, Gog and Magog triangles, and the Schützenberger involution, Sém. Lothar. Combin. B66 (2012), Article B66d, 20 pp.

4. W. H. Mills, D. H. Robbins and H. Rumsey, Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (1983), 340–359.

5. W. H. Mills, D. H. Robbins and H. Rumsey, Self–complementary totally symmetric plane partitions, J. Combin. Theory A 42 (1986), 277–292.

6. D. Zeilberger, Proof of the alternating sign matrix conjecture, Electron. J. Combin. 3 (no. 2, “The Foata Festschrift”) (1996), Article #R13, 84 pp.