Sminaire Lotharingien de Combinatoire 66 (2012), Article B66d

GOG AND MAGOG TRIANGLES, AND THE SCHÜTZENBERGER INVOLUTION

HAYAT CHEBALLAH AND PHILIPPE BIANE

Abstract. We describe an approach to finding a bijection between Alternating Sign Matrices and Totally Symmetric Self-Complementary Plane Partitions, which is based on the Schützenberger involution. In particular, we give an explicit bijection between Gog and Magog trapezoids with two diagonals.

1. Introduction

1.1. Alternating Sign Matrices. An alternating sign matrix (ASM) is a square matrix with entries in {−1, 0, +1} such that, along each line and along each column, the non-zero entries alternate in sign, the sum of the entries in each line and in each column being equal to 1. The number of such matrices of size n is

(1.1)  A_{n} = ∏_{j=0}^{n−1} \frac{(3j + 1)!}{(n + j)!} = 1, 2, 7, 42, 429, …

as proved by Zeilberger [11] and Kuperberg [8]. More of this story can be found in [2]. There have been still other proofs since then, e.g., [4].

It has been known for a long time (see [1]) that the numbers A_{n} also count the number of Totally Symmetric Self-Complementary Plane Partitions (TSSCPP), however no explicit bijection between these classes of objects has been constructed, and finding one is a major open problem in combinatorics.

In this paper we propose an approach to this question which is based on the Schützenberger involution. More precisely, we consider Gog and Magog triangles (in the terminology of Zeilberger), which are triangular arrays of positive integers, satisfying some growth conditions, in simple bijection with ASMs and TSSCPPs, respectively. The basic idea underlying our approach is that these triangles are examples of Gelfand–Tsetlin patterns to which one can apply some known transformations, such as the Schützenberger involution. In fact we conjecture the existence of a bijection between Gog and Magog triangles which can be obtained in two steps: first by making a “modification” of a Gog triangle, based on its inversion pattern, then by applying the Schützenberger involution. This bijection should also preserve trapezoids, which are particular classes of triangles, and which are equi-enumerous, due to Zeilberger’s result [11]. As a first step towards a full bijection we construct here a bijection between (n, 2) Gog and Magog trapezoids (the terminology is explained below).

The paper is organized as follows. In Section 2 we introduce the definitions of Gelfand–Tsetlin triangles, the Gog and Magog triangles and trapezoids, and the Schützenberger involution. In Section 3 we give a bijection between (n, 2) Gog and Magog trapezoids.

We thank the referees of this paper for their constructive comments leading to improvements in the presentation.

2. Gog and Magog triangles and trapezoids

2.1. Gelfand-Tsetlin.

Definition 1. A Gelfand–Tsetlin triangle of size n is a triangular array X = (x_{i,j})_{n⩾i⩾j⩾1} of positive integers

x_{n,1}  x_{n,2}  …  x_{n,n−1}  x_{n,n}
x_{n−1,1}  x_{n−1,2}  …  x_{n−1,n−1}
…  …  …
x_{2,1}  x_{2,2}
x_{1,1}

such that, whenever the entries belong to the array, one has

x_{i+1,j} ⩽ x_{i,j} ⩽ x_{i+1,j+1}.

In other words, the triangle is made of n diagonals in the Northwest-Southeast (NW-SE) direction, of lengths n, n−1, …, 2, 1 (from left to right), and it is weakly increasing in the SE and in the NE directions. For example,

\begin{matrix}1 \\ 2 \\ 2 \\ 3 \\ 6 \\ 1 \\ 2 \\ 2 \\ 5 \\ 2 \\ 2 \\ 4 \\ 2 \\ 4 \\ 3 \\ ⩽ \\ ⩾ \end{matrix}

is a Gelfand–Tsetlin triangle of size 5.

Gog and Magog triangles will be obtained from Gelfand–Tsetlin triangles by imposing further conditions on the entries.

2.2. Gog.

2.2.1. Triangles.

Definition 2. A Gog triangle of size n is a Gelfand–Tsetlin triangle such that

(i)  x_{i,j} < x_{i,j+1},  j < i ⩽ n − 1

in other words, such that its rows are strictly increasing, and such that

(ii)  x_{n,j} = j,  1 ⩽ j ⩽ n.

Here is an example with n = 5:

1  2  3  4  5
1  3  4  5
1  4  5
2  4

3

There is a simple bijection between Gog triangles and alternating sign matrices (see, e.g., [2]). If (M_{ij})_{1⩽i,j⩽n} is an ASM of size n, then the matrix M̃_{ij} = ∑_{k=i}^{n} M_{ij} has exactly i − 1 entries 0 and n − i + 1 entries 1 in row i. Let (x_{ij})_{j=1,...,i} be the indices (in increasing order) of the columns containing an entry 1 in row n − i + 1 of M̃. The triangle X = (x_{ij})_{n⩾i⩾j⩾1} is the Gog triangle corresponding to M.

For example, the above Gog triangle corresponds to the following alternating sign matrix

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

2.2.2. Trapezoids.

Definition 3. An (n, k) Gog trapezoid (for k ≤ n) is a Gog triangle of size n, X = (x_{i,j})_{n⩾i⩾j⩾1} such that

(2.1)  x_{i,j} = j for i − j ≥ k.

Below is a (5, 2) Gog trapezoid.

1 2 3 4 5 1 2 4 5 1 3 4 1 3 2

The entries outside the box are frozen by condition (2.1).

2.3. Magog.

2.3.1. Triangles.

Definition 4. A Magog triangle of size n is a Gelfand–Tsetlin triangle such that

x_{i,i} ⩽ i, 1 ⩽ i ⩽ n.

The set of Magog triangles of size n is in simple bijection with the set of Totally Symmetric Self Complementary Plane Partitions (see [2]).

2.3.2. Trapezoids.

Definition 5. An (n, k) Magog trapezoid (with k ⩽ n) is a Magog triangle X = (x_{i,j})_{n⩾i⩾j⩾1,} such that x_{i,j} = 1 for i − j ≥ k.

Below is a (5, 2) Magog trapezoid.

1 1 1 2 4 1 1 2 2 1 1 2 1 1 1

Again, the entries outside the box are frozen.

2.4. Remark. Our definitions of trapezoids differ from Zeilberger’s [11] definitions in that we chop off the last diagonals instead of the first ones. One can add a parameter m to the definition; thus, an (n, k, m) Gog (respectively Magog) trapezoid will be an (n, k) Gog (respectively Magog) trapezoid such that

x_{i,j} = max(j, x_{m,m−j+i}) for m < i ≤ j + k − 1

(respectively x_{i,j} = 1 for j ≤ n − m).

Here is a (5, 2, 3) Gog trapezoid:

1 2 3 4 5 1 2 3 5 1 2 5 2 3 3

This is the smallest (entrywise) Gog triangle containing the boxed entries. On the other hand, here is a (5, 2, 3) Magog trapezoid:

1 1 1 2 4 1 1 2 4 1 1 2 1 1 1

These trapezoids are in one-to-one correspondence with the trapezoids defined by Krattenthaler in [7]; more precisely, if a_{ij} is an (m, n, k) Gog trapezoid according to Krattenthaler’s definition, then the numbers m + n + 1 − a_{ij}, suitably reindexed, form the nonfrozen entries of an (n + m, n, k) Gog trapezoid according to our definition, and similarly the b_{ij} entries of an (m, n, k) Magog trapezoid according to Krattenthaler’s definition correspond to the nonfrozen entries of an (n + m, n, k) Magog trapezoid according to our definition.

2.5. Schützenberger involution.

2.5.1. Gelfand–Tsetlin triangles label bases of irreducible representations of general linear groups. As such, they are in simple bijection with semi-standard Young tableaux (SSYT). It follows that the Schützenberger involution, which is defined on SSYTs, can be transferred to Gelfand–Tsetlin triangles. The following description of this involution has been studied by Berenstein and Kirillov [6].

First define operators s_{k}, for k ⩽ n − 1, acting on the set of Gelfand–Tsetlin triangles of size n. If X = (x_{i,j})_{n⩾i⩾j⩾1} is such a triangle, the action of s_{k} on X is given by s_{k}X = (x̃_{i,j})_{n⩾i⩾j⩾1} with

x̃_{i,j} = x_{i,j},  if i ≠ k,
x̃_{k,j} = max(x_{k+1,j}, x_{k−1,j−1}) + min(x_{k+1,j+1}, x_{k−1,j}) − x_{i,j}.

It is understood that max(a, b) = max(b, a) = a and min(a, b) = min(b, a) = a if the entry b of the triangle is not defined. The geometric meaning of the transformation of an entry is the following: in row k, any entry x_{k,j} is surrounded by four (or less if it is on the boundary) numbers, increasing from left to right:

x_{k+1,j}  x_{k+1,j+1}
x_{k,j}
x_{k−1,j−1}  x_{k−1,j}

These four numbers determine a smallest interval containing x_{k,j}, namely

[max(x_{k+1,j}, x_{k−1,j−1}), min(x_{k+1,j+1}, x_{k−1,j})] ,

and the transformation maps x_{k,j} to its mirror image with respect to the center of this interval.

Define ω_{j} = s_{j}s_{j−1} ⋯ s_{2}s_{1}.

Definition 6. The Schützenberger involution, acting on Gelfand–Tsetlin triangles of size n, is given by the formula

S = ω_{1}ω_{2} ⋯ ω_{n−1}.

It is a non trivial result that S is an involution (see [6]), and it coincides with the Schützenberger involution when transferred to SSYTs. Note that the s_{k} do not satisfy the braid relations.

Below, we give an example of the action of the Schützenberger involution S = ω_{1}ω_{2}ω_{3} = s_{1}s_{2}s_{1}s_{3}s_{2}s_{1} on a Gelfand–Tsetlin triangle of size 4, the entries to be changed being in red:

\begin{matrix}1 \\ 2 \\ 2 \\ 5 \\ 2 \\ 2 \\ 4 \\ 2 \\ 3 \\ 2 \\ s_{1} \\ 1 \\ 2 \\ 2 \\ 5 \\ 2 \\ 2 \\ 4 \\ 2 \\ 3 \\ 3 \\ s_{2} \\ 1 \\ 2 \\ 2 \\ 5 \\ 2 \\ 2 \\ 4 \\ 2 \\ 4 \\ 3 \\ s_{3} \\ 1 \\ 2 \\ 2 \\ 5 \\ 1 \\ 2 \\ 5 \\ 2 \\ 4 \\ 3 \\ s_{1} \\ 1 \\ 2 \\ 2 \\ 5 \\ 1 \\ 2 \\ 5 \\ 2 \\ 4 \\ 3 \\ s_{2} \\ 1 \\ 2 \\ 2 \\ 5 \\ 1 \\ 2 \\ 5 \\ 1 \\ 4 \\ 3 \\ s_{1} \\ 1 \\ 2 \\ 2 \\ 5 \\ 1 \\ 2 \\ 5 \\ 1 \\ 4 \\ 2 \end{matrix}

2.5.2. One can compute the rightmost diagonal of SX.

Lemma 1. Let X = (X_{i,j}) be a Gelfand–Tsetlin triangle and Y = SX its image under the Schützenberger involution. Then

(2.2) Y_{nn} = X_{nn}
(2.3) Y_{kk} = max_{n=j_{0}>j_{1}>j_{2}>...>j_{n−k}≥1} [( ∑_{i=0}^{n−k−1} X_{j_{i}+i,j_{i}} − X_{j_{i+1}+i,j_{i+1}}) + X_{j_{n−k}+n−k,j_{n−k}}]
for 1 ≤ k < n.

Proof. We recall the description of the Schützenberger involution in terms of words and the Robinson–Schensted correspondence. To the Gelfand–Tsetlin triangle X let us associate the semi-standard Young tableau, with entries in [1, n], such that the shape of the tableau formed with letters u ≤ i is the partition X_{ij}, j = 1, …, i. For example, our Gelfand–Tsetlin triangle

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

3

corresponds to the tableau (in French notation)

5 / (4 5 3 3) 2 2 5

1 1 1 2 4 5

To such a tableau we associate the word w obtained by reading the tableau from top to bottom and from left to right. In our example, this is

w = 5 | 4 5 | 3 3 | 2 2 5 | 1 1 1 2 4 5.

Then we perform the Schützenberger involution on the word: we read it backwards and replace each letter i by n + 1 − i to yield a word Sw. In our example, we obtain

Sw = 1 2 4 5 5 5 | 1 4 4 | 3 3 | 1 2 | 1.

This word is a concatenation of nondecreasing words (Sw)_{1}|(Sw)_{2}| … corresponding to the successive rows of the tableau read from bottom to top and from right to left.

It is easy to verify that these nondecreasing words, viewed as partitions, are the partitions conjugate to the successive SW-NE diagonals of the original Gelfand–Tsetlin triangle (starting from the rightmost one). E.g., in our example (Sw)_{2} is the word 144 which is the partition conjugate to 3222, the second rightmost SW-NE diagonal of the triangle. It follows that, for 1 ≤ i ≤ j < k,

(2.4) X_{k,k−i+1} − X_{j,j−i+1} is the number of letters of (Sw)_{i} which belong to [n − k + 1, n − j].

Looking again at our example, with i = 2, j = 4, k = 5, one has X_{5,4}−X_{4,3} = 3−2 = 1, the number of 1’s in the word (Sw)_{2} = 144.

Applying the Robinson–Schensted algorithm to the word Sw yields an insertion tableau which is the image of our tableau under the Schützenberger involution. The shape of the insertion tableau is the same as that of the original tableau, therefore the top row of the Gelfand–Tsetlin triangle is unchanged (this follows also easily from Definition 6). This yields (2.2).

By a fundamental property of the Robinson–Schensted algorithm, the largest element of the i^{th} row (from bottom) in the Gelfand–Tstelin triangle is equal to the length of the longest nondecreasing subsequence of the subword Sw^{i} of Sw made of the numbers ≤ i.

A nondecreasing subsequence of maximal length in Sw^{i} is of the form [1, k_{1}] ∩ (Sw^{i})_{1} | [k_{1}, k_{2}] ∩ (Sw^{i})_{2} | … [k_{l−1}, k_{l}] ∩ (Sw^{i})_{l} for some sequence 1 ≤ k_{1} ≤ … ≤ k_{l} ≤ i.

Using (2.4), formula (2.3) follows from these considerations. □

2.5.3. GOGAm triangles. Since the Schützenberger involution consists in reading a word backwards and inverting the letters, we introduce the following definition.

Definition 7. A GOGAm triangle of size n is a Gelfand–Tsetlin triangle such that its image under the Schützenberger involution is a Magog triangle of size n.

Here is an example of a GOGAm triangle with n = 5:

1  2  3  3  5
2  3  3  5
3  3  5
3  5

5

By Lemma 1, we can give a description of GOGAm triangles.

Proposition 1. Let X = (X_{i,j}) be a Gelfand–Tsetlin triangle. Then X is a GOGAm triangle if and only if X_{nn} ≤ n and, for all 1 ≤ k ≤ n − 1, and all n = j_{0} > j_{1} > j_{2} > … > j_{n−k} ≥ 1, one has

( ∑_{i=0}^{n−k−1} X_{j_{i}+i,j_{i}} − X_{j_{i+1}+i,j_{i+1}}) + X_{j_{n−k}+n−k,j_{n−k}} ≤ k.

Proof. Immediate from Lemma 1. □

2.5.4. GOGAm trapezoids. If a Magog triangle contains a triangle of 1’s forming its first leftmost diagonals, then this triangle remains invariant under all transformations s_{k}, and therefore also under the Schützenberger involution. This justifies the following definition.

Definition 8. An (n, k) GOGAm trapezoid is a GOGAm triangle of size n such that x_{i,j} = 1 for i − j ≥ k. Equivalently, it is the image under the Schützenberger involution of an (n, k) Magog trapezoid.

Here is a (5, 2) GOGAm trapezoid:

1 1 1 2 4 1 1 2 4 1 2 4 1 4 3

2.6. Krattenthaler’s conjecture. Zeilberger [11] proved that there exists as many (n, k) Gog trapezoids as (n, k) Magog trapezoids for all k ≤ n. Krattenthaler [7] conjectures a refined equi-enumeration: according to this conjecture, there are as many (n, k, m) Gog and Magog trapezoids. Actually he also introduces two more statistics on these trapezoids which he conjectures to coincide.

In the remaining sections we shall give a bijection between (n, 2) Gog trapezoids and (n, 2) GOGAm trapezoids, which restricts to a bijection between (n, 1) Gog trapezoids and (n, 1) GOGAm trapezoids. If we compose with the Schützenberger involution, we obtain a bijective proof of Zeilberger’s result in this case. We also give a natural statistic on Gog trapezoids which is transformed into a natural statistic on Magog trapezoids by this bijection, see Section 3.5.3. Our bijection also maps (n, 2, m) Gog trapezoids to (n, 2, m) Magog trapezoids, however the two statistics of Krattenthaler on Gog and Magog trapezoids are not mapped to one another.

2.7. Some motivation. The bijection presented below was found by first considering the cases of (n, 2, 2) and (n, 3, 3) trapezoids, which can be considered as integer polytopes, and looking for piecewise linear bijections. The explicit bijections found in this way turned out to involve the Schützenberger involution, which motivated us to try this for larger trapezoids. During this study, two statistics on Magog triangles were used, one of them corresponding by the bijection to the position of the 1 in the bottom row of the ASM (see Section 3.5.3), while the other, conjecturally, corresponds to the position of the 1 in the righmost column of an ASM. More on these topics can be found in [3].

3. (n, 2) Gog and Magog trapezoids

3.1. Inversions.

Definition 9. An inversion in a Gog triangle is a pair (i, j) such that x_{i,j} = x_{i+1,j}.

For example, the following Gog triangle contains three inversions, (2, 2), (3, 1), (4, 1), the respective equalities being in red in this figure:

1 2 3 4 5 1 3 4 5 1 4 5 2 4 3

Remark 1. The number of inversions of a Gog triangle coincides with the number of inversions of its associated ASM as defined by Mills, Robbins, Rumsey [10] minus the number of −1s.

Definition 10. Let X = (x_{i,j})_{n⩾i⩾j⩾1} be a Gog triangle and let (i, j) be such that 1 ⩽ i ⩽ j ⩽ n.

An inversion (k, l) covers (i, j) if i = k + p and j = l + p for 1 ⩽ p ⩽ n − k.

The entries (i, j) covered by an inversion are marked by ” + ” in the following figure:

\begin{matrix}∘ \\ ∘ \\ ∘ \\ + \\ ∘ \\ ∘ \\ ∘ \\ + \\ ∘ \\ ∘ \\ ∘ \\ ∘ \\ ∘ \\ ∘ \\ ∘ \end{matrix}

The basic idea for our bijection is that, for any inversion in the Gog triangle, we should subtract 1 from the entries covered by this inversion. This simple minded procedure works for (n, 1) trapezoids, as we will show as a byproduct of our bijection for (n, 2) trapezoids. It is a good exercise to check this directly. The procedure does not work for (n, k) trapezoids with k > 1 but, by making some adequate adaptations, we will obtain a bijection for trapezoids of size (n, 2).

3.2. (n, 2) trapezoids. Consider an (n, 2) Gog trapezoid. This is an array of the form

1  2  3  ⋯  ⋯  n − 2  n − 1  n
1  2  ...  ...  n − 3  b_{2}  a_{1}
1  ...  ...  n − 4  b_{3}  a_{2}
...  2  ...  ...  ...
1  2  b_{n−3}  a_{n−4}
1  b_{n−2}  a_{n−3}
b_{n−1}  a_{n−2}
a_{n−1}

We shall give an algorithm which builds a GOGAm triangle from the Gog triangle by successively adding NW-SE diagonals of increasing lengths, and making appropriate changes to the triangle. In the end we will obtain a triangle of the form

1  1  1  ⋯  ⋯  1  β_{1}  α_{0}
1  1  ...  ...  1  β_{2}  α_{1}
1  ...  ...  ...  β_{3}  α_{2}
...  1  ...  ...  ...
1  1  β_{n−3}  α_{n−4}
1  β_{n−2}  α_{n−3}
β_{n−1}  α_{n−2}
α_{n−1}

By Proposition 1, such a triangle is a GOGAm triangle if and only if

α_{0} ≤ n
α_{0} − α_{i} + β_{i} ≤ n − 1 for 1 ≤ i ≤ n − 1,
α_{0} − α_{i} + β_{i} − β_{j} + 1 ≤ j − 1 for 1 ≤ i < j ≤ n − 1.

3.3. The algorithm. First step: the rightmost NW-SE diagonal consists of one entry n and is not changed, yielding the triangle of size 1 equal to X^{(1)} = n.

Second step: The triangle formed by the two first diagonals is

\begin{aligned}n − 1 & & n \\ & a_{1} \end{aligned}

where a_{1} = n or n − 1. In the first case, the algorithm yields the triangle

X^{(2)} = \begin{aligned}n − 1 & & n \\ & n \end{aligned}

in the second case we have an inversion and accordingly subtract 1 from the upper right entry, which gives the triangle

X^{(2)} = \begin{aligned}n − 1 & & n − 1 \\ & n − 1 \end{aligned}

Assume now that the first k diagonals have been treated and a triangle X^{(k)} of size k, of the form

n − k + 1  n − k + 1  ⋯  n − k + 1  v_{1}  u_{0}
...  ...  ...  v_{2}  u_{1}
...  ...  ...  ...
n − k + 1  v_{k−2}  u_{k−3}
v_{k−1}  u_{k−2}
u_{k−1}

has been obtained.

Furthermore assume that this triangle satisfies the inequalities

(3.1)  u_{0} ≤ n
(3.2)  u_{0} − u_{i} + v_{i} ≤ n − 1 for 1 ≤ i ≤ k − 1,
(3.3)  u_{0} − u_{i} + v_{i} − v_{j} + 1 ≤ j − 1 for 1 ≤ i < j ≤ k − 1,

and that

(3.4)  u_{k−1} = a_{k−1}.

Let us add, on the left of this triangle, the diagonal

n − k

n − k
...
n − k
v_{k}
u_{k}

with u_{k} = a_{k}, v_{k} = b_{k}. This yields a triangle Z^{(k)} of size k + 1 (this triangle will not, in general, be a Gelfand–Tsetlin triangle, because the inequality v_{k} ≤ v_{k−1} may be broken). The algorithm will modify Z^{(k)} to get a triangle X^{(k+1)} of size k + 1. First we consider all the inversions created by the entries of the left diagonal equal to n − k (except maybe those coming from u_{k} and v_{k}), and accordingly subtract ones from the above triangle. This transforms the entries n − k + 1 in the upper left triangle into n − k’s. Then we treat the entries u_{k}, v_{k}, and the ones lying on the same SW-NE diagonal, according to the algorithm described below, which will yield a triangle of the form

n − k  n − k  ⋯  ⋯  n − k  v′_{1}  u′_{0}
n − k  ...  ...  ...  v′_{2}  u′_{1}
...  ...  ...  ...  u′_{2}
...  ...  ...  ...
n − k  v′_{k−1}  u′_{k−2}
v′_{k}  u′_{k−1}
u′_{k}

We will check that the new triangle is a Gelfand–Tsetlin triangle and that (3.1), …, (3.4) are satisfied for this new triangle. The modification will depend on the inversion pattern in the leftmost diagonal that we have added. In all cases, we will have

(3.5)  u′_{k} = u_{k},

the remaining entries being modified as follows, according to the four possibilities for the inversions in the two bottom rows.

(i) The first case is v_{k} = n − k, u_{k} = n − k, when there are two inversions. Then the modification consists in subtracting 1 from each of the entries of the previous triangle, that is, we put u′_{i} = u_{i} − 1, v′_{i} = v_{i} − 1, for i ≤ k − 1, and v′_{k} = v_{k} = n − k.

(ii) The second is the case v_{k} = n − k < u_{k}. Then we put u′_{i} = u_{i}, v′_{i} = v_{i} − 1, for i ≤ k − 1, and v′_{k} = v_{k} = n − k.

(iii) The third case is when n − k < v_{k} = u_{k}. We put u′_{i} = u_{i} − 1 for i ≤ k − 1. Observe that v_{k} = b_{k} = u_{k} < a_{k−1} = u_{k−1}, therefore u_{i}, 0 ≤ i ≤ k, is nonincreasing. Two subcases occur:

(iiia) if the triangle we obtain is a Gelfand–Tsetlin triangle, then we keep it as the modified triangle, i.e., we put v′_{i} = v_{i} for i ≤ k.

(iiib) if the triangle is not Gelfand–Tsetlin, then there must exist j ≤ k − 1 with v_{j} = u_{j}. In this case, we put v′_{i} = v_{i} − 1, for i ≤ k − 1, and we put v′_{k} = n − k.

(iv) Finally the last case is when n − k < v_{k} < u_{k}. There are two possibilities.

(iva) if v_{k} ≤ v_{k−1}, then Z^{(k)} is a Gelfand–Tsetlin triangle, and we do not modifiy it, i.e., we put u′_{i} = u_{i}, v′_{i} = v_{i} for all i ≤ k, thus X^{(k+1)} = Z^{(k)}.

(ivb) The last subcase is v_{k} > v_{k−1}. First we put u′_{i} = u_{i} for all i. Let
(3.6)  l = max{i|v_{k−i} ≤ v_{k} − i}.

Since v_{k−i} is nondecreasing and v_{k} − i is decreasing, one has l ≥ 1 and v_{k−i} ≤ v_{k} − i for all i ≤ l. We put v′_{k} = v′_{k−1} = … = v′_{k−l+1} = n − k and v′_{k−l} = v_{k} − l, all the other entries being unchanged: v′_{i} = v_{i} for i < k − l.

Remark 2. Rules (i), (ii), (iiia), (iva) consist just in subtracting 1 from entries covered by the inversions in the SE-NW diagonal which has been added. The rules (iiib) and (ivb) are more subtle.

3.3.1. Proof of the algorithm, first part. Let us now check that, in each case, we obtain a Gelfand–Tsetlin triangle X^{(k)} satisfying inequalities (3.1), (3.2), (3.3) (the identity (3.4) is immediate from (3.5)).

We start with rules (i), (ii), (iiia), (iiib), (iva).

(i) Since a_{k−1} = u_{k−1} > v_{k} and v_{k−1} ≥ n−k +1, X^{(k+1)} is a Gelfand–Tsetlin triangle. For 1 ≤ i < j ≤ k − 1, one has u′_{0} − u′_{i} + v′_{i} − v′_{j} = u_{0} − u_{i} + v_{i} − v_{j} hence (3.3) is satisfied for these values. Since

u′_{0} − u′_{i} + v′_{i} − v′_{k} = u_{0} − u_{i} + v_{i} − 1 − (n − k) ≤ n − 1 − 1 − (n − k) = k − 2,

we see that (3.3) is satisfied for all values. Since u′_{0} = u_{0} − 1 ≤ n − 1 and u′_{i} ≥ v′_{i}, one has (3.2) and (3.1).

(ii) Again, X^{(k+1)} is clearly a Gelfand–Tsetlin triangle. For 1 ≤ i < j ≤ k, we check (3.3) as above, while (3.1) is clear. Finally u′_{0} − u′_{i} + v′_{i} = u_{0} − u_{i} + v_{i} − 1 ≤ n − 2, and u′_{0} − u′_{k} + v′_{k} ≤ n − 1, since −u′_{k} + v′_{k} ≤ −1, which gives (3.2).

(iiia) Since u_{i} > v_{i}, one has u′_{i} ≥ v′_{i} for i ≤ k, and the triangle X^{(k+1)} is a Gelfand– Tsetlin triangle.

One has

u′_{0} = u_{0} − 1
u′_{0} − u′_{i} + v′_{i} = u_{0} − u_{i} + v_{i} i < k
u′_{0} − u′_{k} + v′_{k} = u_{0} − 1 ≤ n − 1
u′_{0} − u′_{i} + v′_{i} − v′_{j} = u_{0} − u_{i} + v_{i} − v_{j}  i < j < k
u′_{0} − u′_{i} + v′_{i} − v′_{k} < n − 1 − (n − k) = k − 1 (since v′_{k} > n − k),

from which inequalities (3.1), (3.2), (3.3) follow.

(iiib) The new triangle is clearly Gelfand–Tsetlin. Furthermore, one has

u′_{0} = u_{0} − 1
u′_{0} − u′_{i} + v′_{i} = u_{0} − u_{i} + v_{i} − 1 i < k
u′_{0} − u′_{k} + v′_{k} < u′_{0} ≤ n
u′_{0} − u′_{i} + v′_{i} − v′_{j} = u_{0} − u_{i} + v_{i} − v_{j}  i < j < k
u′_{0} − u′_{i} + v′_{i} − v′_{k} = u_{0} − u_{i} + v_{i} − 1 − (n − k) ≤ k − 2,

which imply inequalities (3.1), (3.2), (3.3).

(iva) The fact that X^{(k+1)} is Gelfand–Tsetlin is immediate. The inequalities are preserved, indeed, all inequalities involving indices < k are immediate, and one has

u′_{0} − u′_{k} + v′_{k} ≤ u′_{0} − 1 ≤ n − 1, since u′_{k} > v′_{k},
u′_{0} − u′_{i} + v′_{i} − v′_{k} ≤ n − 1 − (n − k + 1) = k − 2, since v′_{k} > n − k.

3.3.2. Proof of the algorithm, second part. We now consider the last rule, (ivb). This is the most delicate part of the proof. We first gather some information on the algorithm which has been constructed up to now.

Lemma 2. Just after a step where rule (i) or (ii) is applied, rule (iiib) never applies.

Proof. Suppose that rule (i) applies to Z^{(k)}, then n − k = b_{k} = v_{k} = a_{k} = u_{k}, and n − k − 1 < b_{k+1} = a_{k+1} is impossible since this would yield b_{k+1} ≥ a_{k} contradicting the Gog strict inequality for the original triangle. If rule (ii) applies to Z^{(k)} then v_{i} < u_{i} in X^{(k+1)}, for all i < k, therefore rule (iiib) cannot be applied to Z^{(k+1)}. □

Lemma 3. If rule (ivb) applies at step k, then necessarily at the previous step either rule (iiib) or (ivb) was applied.

Proof. If one of the other rules had been applied at the previous step, one would have v_{k−1} ≥ v_{k}. □

Lemma 4. If rule (ivb) is applied to the triangle Z^{(k)}, then to each of the triangles Z^{(k−l)}, Z^{(k−l+1)}, …, Z^{(k−1)} either rule (iiib) or (ivb) was applied.

Proof. Assume that at some step t < k in the algorithm we have applied rule (iiia) or (iva) to Z^{(t)}. Then the entry v_{t}^{(t+1)} in the triangle X^{(t+1)} (we emphasize the dependence on the step by adding a superscript) satisfies b_{t} = v_{t}^{(t+1)}. At each next step s, we will subtract at most 1 from v_{t}^{(s)}, therefore, in the triangle Z^{(k)},

v_{t}^{(k)} ≥ b_{t} − (k − t − 1) ≥ b_{k} − (k − t − 1) = v_{k}^{(k)} − (k − t − 1) > v_{k}^{(k)} + t − k.

It follows that, in Z^{(k)}, one has l < k − t (where l is defined by (3.6). We conclude that, to each of the triangles Z^{(k−l)}, Z^{(k−l+1)}, …, Z^{(k−1)} either rule (i), (ii), (iiib) or (ivb) was applied. But we have seen that rule (iiib) cannot follow immediately rule (i) or (ii) and that rule (ivb) always follows either rule (iiib) or (ivb), so that in fact only rule (iiib) or (ivb) has been applied to each of the triangles Z^{(k−l)}, Z^{(k−l+1)}, …, Z^{(k−1)}. □

Lemma 5. If rule (ivb) is applied to the triangle Z^{(k)}, then one has

v_{k−1} = … = v_{k−l} = n − k + 1.

Proof. Since n − k + 1 ≤ v_{k−1} ≤ … ≤ v_{k−l}, it suffices to prove that v_{k−l} ≤ n − k + 1. By the preceding Lemma, either rule (iiib) or (ivb) has been applied to the triangles Z^{(k−l)}, Z^{(k−l+1)}, …, Z^{(k−1)}. Let us look at the successive values of the entry v_{k−l}^{(s)} in the triangle X^{(s)} (or Z^{(s)}). One has v_{k−l}^{(k−l+1)} = n − k + l, since rule (iiib) or (ivb) has been applied to Z^{(k−l)}. Each time rule (iiib) is applied v_{k−l}^{(s)} is decreased by 1. There are two cases:

(a) If only rule (iiib) is applied to Z^{(k−l)}, Z^{(k−l+1)}, …, Z^{(k−1)}, then one has v_{k−l}^{(k)} = n − k + 1.

(b) If not, let i be the least index l ≥ i ≥ 1 such that rule (ivb) is applied to Z^{(k−i)}, and let l′ = max{j|v_{k−i}^{(k−i)} − j ≥ v_{k−i−j}^{(k−i)}}. By rule (ivb), one has

v_{k−l′−i}^{(k−i+1)} = b_{k−i} − l′, v_{k−i−j}^{(k−i+1)} = n − k + i, j = 0, 1, …, l′ − 1.

Since rule (iiib) is applied to Z^{(k−i+1)}, …, Z^{(k−1)}, one has v_{k−l′−i}^{(k)} = b_{k−i} − l′ − i + 1 and

(3.7)  v_{k−p}^{(k)} = n − k + 1, p = 1, 2, …, l′ + i − 1.

It follows that

v_{k−l′−i}^{(k)} = b_{k−i} − l′ − i + 1 ≥ b_{k} − l′ − i + 1 = v_{k}^{(k)} − l′ − i + 1,

hence, by (3.6),

v_{k−l′−i}^{(k)} > v_{k}^{(k)} − l′ − i.

Consequently, we have l < l′ + i, and v_{k−l} = n − k + 1 by (3.7). □

Lemma 6. If rule (iiib) or (ivb) is applied to the triangle Z^{(k)}, then there exists some i < k − l such that u′_{i} = v′_{i}.

Proof. For rule (iiib) this is easy to see.

In the case of rule (ivb), there exists some step before k, when rule (iiib) has been applied and then only rules (iiib) or (ivb) have been applied. If rule (iiib) is applied, there must exist an i with u_{i} = v_{i}, and then applying either rule (iiib) or (ivb) cannot destroy this pair u_{i} = v_{i}. This implies that there exists some i such that u′_{i} = v′_{i}. Such a pair cannot exist for i ≥ k − l by the preceding lemma, therefore i < k − l. □

3.3.3. Proof of the algorithm, end. Assuming that rule (ivb) is applied to the triangle Z^{(k)}, we can now check that our triangle X^{(k+1)} satisfies all the required properties. Since v′_{k−l} = v_{k} − l, and v_{k−l−1} > v_{k} − l − 1, by the definition of l, one has v′_{k−l−1} ≥ v′_{k−l}. This implies that X^{(k+1)} is a Gelfand–Tsetlin triangle, as is easily verified.

Let us check the inequalities (3.1), (3.2), (3.3).

First, since u′_{0} = u_{0}, (3.1) is clear. Consider u′_{0} − u′_{i} + v′_{i}. Since u′_{i} = u_{i} is unchanged and v′_{i} ≤ v_{i} for all values of i, except v′_{k−l}, in order to check (3.2) it suffices to consider u′_{0} − u′_{k−l} + v′_{k−l} and u′_{0} − u′_{k} + v′_{k}. One has

u′_{k−l} = u_{k−l} ≥ u_{k} > v_{k} − l = v′_{k−l},

and therefore

u′_{0} − u′_{k−l} + v′_{k−l} ≤ n − 1.

Since u′_{k} > v′_{k}, one has

u′_{0} − u′_{k} + v′_{k} ≤ n − 1.

Consider u′_{0} − u′_{i} + v′_{i} − v′_{j}, for i < j ≤ k.

If j < k − l, then u′_{0} − u′_{i} + v′_{i} − v′_{j} = u_{0} − u_{i} + v_{i} − v_{j}, so (3.3) is preserved.

If j = k − l, then u′_{i} = u_{i}, v′_{i} = v_{i}, v′_{j} ≥ v_{j}, therefore the inequality is again true. If j > k − l > i, then v′_{j} = n − k = v_{k−l} − 1 (by Lemma 5), therefore

u′_{0} − u′_{i} + v′_{i} − v′_{j} = u_{0} − u_{i} + v_{i} − v_{k−l} + 1 ≤ k − l − 1 ≤ j − 2.

If j > k − l = i then

u′_{0} − u′_{i} + v′_{i} − v′_{j} = u_{0} − u_{k−l} + v_{k} − l − n + k
= u_{0} − n + v_{k} − u_{k−l} − l + k ≤ k − l − 1 ≤ j − 2

since v_{k} < u_{k−l}.

If k > j > i > k − l then v′_{i} − v′_{j} = v_{i} − v_{j} and u′_{0} − u′_{i} = u_{0} − u_{i} therefore

u′_{0} − u′_{i} + v′_{i} − v′_{j} = u_{0} − u_{i} + v_{i} − v_{j} ≤ j − 2.

Finally if k = j > i > k − l, then

u′_{0} − u′_{i} + v′_{i} − v′_{k} = u_{0} − u_{i} + v_{i} − 1 − (n − k) ≤ n − 1 − 1 − (n − k) = k − 2. □

Applying the algorithm until we have treated all diagonals, we obtain thus an (n, 2) GOGAm trapezoid from our (n, 2) Gog trapezoid.

3.3.4. Invertibility. We can infer from the leftmost SE-NW diagonal of X^{(k+1)} which rule was applied to Z^{(k)}. The only ambiguity is whether rule (ii), (iiib) or (ivb) has been applied when n − k = v′_{k} < u′_{k}. Rule (ii) has been applied if and only if one has u′_{i} > v′_{i} for all i < k. In order to distinguish between rules (iiib) and (ivb), we now state the following lemma.

Lemma 7. Assume X^{(k+1)} is obtained from Z^{(k)} by applying rule (iiib) or (ivb), and let l = 1 + max{i|v′_{k−i} = n − k}. Then

(a) v′_{k−l} + l < u′_{k} if rule (ivb) has been applied.

(b) v′_{k−l} + l ≥ u′_{k} if rule (iiib) has been applied.

Proof. Part (a) is obvious from the statement of rule (ivb), since v′_{k−l}+l = v_{k} < u_{k} = u′_{k}.

In order to prove part (b), note that in case (iiib) is applied to Z^{(k)}, then by Lemma 2, to all the triangles Z^{(k−i)} for 1 ≤ i ≤ l − 1 either rule (iiib) or (ivb) has been applied. If only rule (iiib) has been applied to Z^{(k−l+1)}, …, Z^{(k−1)}, then rule (iiia) or (iva) must have been applied to Z^{(k−l)}, therefore v′_{k−l} = b_{k−l} − l which implies v′_{k−l} + l = b_{k−l} ≥ b_{k} = a_{k} = u′_{k}.

If rule (ivb) has been applied at some step t with k − l + 1 ≤ t ≤ k − 1, then let i be the smallest number such that (ivb) has been applied to Z^{(k−i)}. By Lemma 5 there exists an l′ ≥ 1 such that

v_{k−i}^{(k−i+1)} = … = v_{k−i−l′+1}^{(k−i+1)} = n − k + i − 1

and

v_{k−i−l′}^{(k−i+1)} = b_{k−i} − l′ > n − k + i − 1.

Since rule (iiib) is applied to Z^{(k−i+1)}, …, Z^{(k−1)} it follows that

v′_{k} = … = v′_{k−i−l′−1} = n − k

and

v′_{k−i−l′} = b_{k−i} − l′ − i + 1 > n − k.

Therefore l = l′ + i and v′_{k−l} + l ≥ u′_{k} since v′_{k−l} + l = b_{k−i} ≥ b_{k} = a_{k} = u′_{k}. □

3.4. The inverse map.

3.4.1. The algorithm. We now prove that the map defined above has an inverse. Let X be a (n, 2) GOGAm trapezoid of shape

1  1  1  ⋯  ⋯  1  β_{1}  α_{0}
1  1  ...  ...  1  β_{2}  α_{1}
1  ...  ...  ...  β_{3}  α_{2}
...  ...  ...  ...  ...
1  1  β_{n−3}  α_{n−4}
1  β_{n−2}  α_{n−3}
β_{n−1}  α_{n−2}
α_{n−1}

One has

α_{0} ≤ n,
α_{0} − α_{i} + β_{i} ≤ n − 1 for 1 ≤ i ≤ n − 1,
α_{0} − α_{i} + β_{i} − β_{j} + 1 ≤ j − 1 for 1 ≤ i < j ≤ n − 1.

We shall give an algorithm which is the inverse of the one above.

Let k be an integer decreasing from k = n − 1 to k = 0. Let Y^{(n)} be an empty set, and X^{(n)} = X; at each step we will have a pair (Y^{(k+1)}, X^{(k+1)}) where Y^{(k+1)} is an array (non empty only for k < n − 1)

1  2  ⋯  n − k − 1
1  2  ...  ...
...  ...  ...  n − k − 1
...  ...  ...  b_{k+1}
...  2  ...  a_{k+1}
1  b_{n−2}  ...
b_{n−1}  a_{n−2}
a_{n−1}

which forms the leftmost NW-SE diagonals of a Gog triangle, and X^{(k+1)} is a Gelfand– Tsetlin triangle:

n − k  n − k  ⋯  n − k  v′_{1}  u′_{0}
n − k  n − k  ...  v′_{2}  u′_{1}
...  ...  ...  ...
n − k  v′_{k−1}  u′_{k−2}
v′_{k}  u′_{k−1}
u′_{k}

satisfying the inequalities (3.1), (3.2), (3.3). Then we make a modification of the triangle X^{(k+1)}, according to the rules below, to get a triangle Z^{(k)}

n − k  n − k + 1  ⋯  n − k + 1  v_{1}  u_{0}
n − k  ...  ...  v_{2}  u_{1}
...  ...  ...  ...
n − k  v_{k−1}  u_{k−2}
v_{k}  u_{k−1}
u_{k}

Then we add the leftmost NW-SE diagonal of this triangle to the right of Y^{(k+1)} to get Y^{(k)} (thus b_{k} = v_{k} and a_{k} = u_{k}), and take the remaining triangle as X^{(k)}. We will prove that, at each step, X^{(k)} is a Gelfand–Tsetlin triangle which satisfies the inequalities (3.1), (3.2), (3.3). Furthermore, we will prove that, at the next step of the algorithm, the entries a_{k−1}, b_{k−1} satisfy

(3.8)  n − k + 1 ≤ b_{k−1}, b_{k} ≤ b_{k−1},  b_{k} < a_{k−1}, b_{k} ≤ a_{k} ≤ a_{k−1} ≤ n,

which imply that the triangle Y^{(0)} is a Gog triangle.

We will use the following notation: if v′_{k} = n − k and there exists i < k such that u′_{i} = v′_{i}, then

(3.9)  l = 1 + max{j | v′_{k−j} = n − k}.

Let us now describe the modification map yielding triangle Z^{(k)} from X^{(k+1)} by the inverse algorithm, for which we consider several cases, inverse to the cases considered in the forward algorithm.

(i) n − k = v′_{k} = u′_{k}, then we put u_{i} = u′_{i} + 1, v_{i} = v′_{i} + 1 for i ≤ k − 1 and v_{k} = v′_{k}, u_{k} = u′_{k}.

(ii) The second case is n − k = v′_{k} < u′_{k}, and v′_{i} < u′_{i} for all i < k. Then we put u_{i} = u′_{i}, v_{i} = v′_{i} + 1, for i ≤ k − 1, and v_{k} = v′_{k}, u_{k} = u′_{k}.

(iiia) n − k < v′_{k} = u′_{k}, then we put u_{i} = u′_{i} + 1, v_{i} = v′_{i} for i ≤ k − 1, and v_{k} = v′_{k}, u_{k} = u′_{k}.

(iiib) n − k = v′_{k} < u′_{k}, there exists i < k such that u′_{i} = v′_{i}, and v′_{k−l} + l ≥ u′_{k} (recall (3.9)), then we put u_{i} = u′_{i} + 1, v_{i} = v′_{i} + 1, for i ≤ k − 1, and v_{k} = u_{k} = u′_{k}.

(iva) n − k < v′_{k} < u′_{k}, then we put u_{i} = u′_{i}, v_{i} = v′_{i}, i ≤ k.

(ivb) n − k = v′_{k} < u′_{k}, there exists i < k such that u′_{i} = v′_{i}, and v′_{k−l} + l < u′_{k}, then we put u_{i} = u′_{i}, for i ≤ k, v_{i} = n − k + 1 for k − l ≤ i ≤ k − 1, v_{k} = v′_{k−l} + l, and v_{i} = v′_{i} for all other i.

Let us now check that this map is well defined. By Section 3.3.4, it is an inverse of our modification map. We consider the cases (i),…,(iv) above. First, by checking the cases one after the other, one sees that the sequence a_{i} constructed by the rules above is nonincreasing (a_{i} ≤ a_{i−1}), and that b_{i} ≥ n − i. The remaining inequalities in (3.8) will be checked case by case. We also have to check that the triangles X^{(k)} are Gelfand– Tsetlin, and that they satisfy (3.1), (3.2), (3.3). The equality (3.4) is immediate by inspection.

We start with an observation about rules (iiib) and (ivb).

Lemma 8. If rule (iiib) or (ivb) has been applied to the triangle X^{(k+1)} then in the triangle X^{(k)} there exists a pair u_{i} = v_{i}.

Proof. This is immediate for rule (iiib), since adding 1 to both u′_{i} and v′_{i} does not destroy the equality u′_{i} = v′_{i}.

For rule (ivb) we notice that n − k = v′_{k} < u′_{k}, and v′_{k−l} + l < u′_{k} ≤ u′_{k−l} imply that v′_{k−j} < u′_{k−j} for j = 1, …, l, therefore the inequality u′_{i} = v′_{i} must be realized for some i < k − l, and then u_{i} = u′_{i} = v′_{i} = v_{i} by rule (ivb). □

3.4.2. Proof of the algorithm. We now check all rules of the inverse algorithm. (i) It is clear that the triangle X^{(k)} is Gelfand–Tsetlin. We have u′_{0} = u′_{0} − u′_{k} + v′_{k} ≤ n − 1, this proves (3.1). Since u_{0} −1−u_{i} +v_{i} −(n−k) = u′_{0} −u′_{i} +v′_{i} −v′_{k} ≤ k −2 we have u_{0} −u_{i} +v_{i} ≤ n−1. All other inequalities in (3.2), (3.3) involve differences like u_{0} − u_{i} or v_{i} − v_{j} which

are not unchanged by the replacement u′ → u, v′ → v.

Moreover, the inequalities (3.8) are immediate.

(ii) Since v′_{i} < u′_{i} for all i, one has v_{i} ≤ u_{i}, hence X^{(k)} is a Gelfand–Tsetlin triangle, and (3.1) is immediate since u_{0} = u′_{0}.

Since u′_{0} − u′_{i} + v′_{i} − v′_{k} ≤ k − 2, one has u_{0} − u_{i} + v_{i} ≤ n − 1, thus (3.2) holds. Finally (3.3) comes from u′_{0} − u′_{i} = u_{0} − u_{i} and v′_{i} − v′_{j} = v_{i} − v_{j}. The inequalities (3.8) at the next step are immediate.

(iiia) Again it is easy to see that X^{(k)} is a Gelfand–Tsetlin triangle. Since u′_{0} − u′_{k} + v′_{k} ≤ n − 1 and u′_{k} = v′_{k} we get u_{0} = u′_{0} + 1 ≤ n, hence (3.1).

The other inequalities (3.2), (3.3) are checked similarly. The inequalities (3.8) at the next step are immediate.

(iiib) The fact that X^{(k)} is a Gelfand–Tsetlin triangle is immediate. Since there exists j with u′_{j} = v′_{j}, one has u′_{0} = u′_{0} − u′_{j} + v′_{j} ≤ n − 1, thus u_{0} =

u′_{0} + 1 ≤ n.

Since u′_{0}−u′_{i}+v′_{i}−v′_{k} ≤ k−2, it follows that u′_{0}−u′_{i}+v′_{i} ≤ n−2 and u_{0}−u_{i}+v_{i} ≤ n−1. The other inequalities are satisfied since u′_{0} − u′_{i} + v′_{i} − v′_{j} = u_{0} − u_{i} + v_{i} − v_{j} for

1 ≤ i < j ≤ k − 1.

We now check the inequalities (3.8). One has b_{k} = a_{k} < a_{k−1} = u′_{k−1} + 1. It remains to see that b_{k} ≤ b_{k−1}. If v′_{k−1} > n − k, then v_{k−1} = v′_{k−1} + 1 ≥ u′_{k} = a_{k} = b_{k} since we are applying rule (iiib)

to X^{(k+1)} (in this case, l = 1). At the next step, we will have b_{k−1} ≥ v_{k−1} ≥ b_{k}.

If v′_{k−1} = n − k, then one has l > 1, and by Lemma 8 either rule (iiib) or rule (ivb) applies to X^{(k)}. In either case it is easy to see that b_{k} ≤ b_{k−1}.

(iva) In this case, the fact that X^{(k)} is a Gelfand–Tsetlin, as well as the inequalities (3.1), (3.2), (3.3), is immediate. Also the inequalities (3.8) are immediate.

(ivb) Since n − k < u′_{k} ≤ u′_{i} for i ≤ k − 1, it follows that u_{i} ≥ n − k + 1 for all i. It is then clear that X^{(k)} is a Gelfand–Tsetlin triangle.

Let us check the inequalities (3.1), (3.2), (3.3) for X^{(k)}. Since u_{0} = u′_{0}, inequality (3.1) is obvious. One has u_{0} − u_{i} + v_{i} = u′_{0} − u′_{i} + v′_{i} ≤ n − 1 for i < k − l. For k > i ≥ k − l, one has

v_{i} = n − k + 1 ≤ v_{k−l} + l < u_{k} ≤ u_{i}, therefore −u_{i} + v_{i} ≤ −1, and inequality (3.2) holds. Inequality u_{0} − u_{i} + v_{i} − v_{j} + 1 = u′_{0} − u′_{i} + v′_{i} − v′_{j} + 1 ≤ j − 1 holds if i < j < k − l. If i < k − l, one has

u_{0} − u_{i} + v_{i} − (n − k) + 1 = u′_{0} − u′_{i} + v′_{i} − v′_{k−l+1} + 1 ≤ k − l,

hence

u_{0} − u_{i} + v_{i} − v_{k−l} + 1 = u_{0} − u_{i} + v_{i} − (n − k + 1) + 1 ≤ k − l − 1,

which proves (3.3) for i < j = k − l.

If i < k − l < j, then v_{i} = v′_{i} and v_{j} ≥ v′_{j}, therefore (3.3) holds as well. One has

u_{0} − u_{k−l} + v_{k−l} − v_{j} + 1 ≤ u′_{0} − u′_{k−l} + v′_{k−l} − v_{j} + 1 ≤ k − l − 1,

proving (3.3) for i = k − l < j.

If k − l < i < j, then v_{i} = v_{j}, and v′_{i} = v′_{j}. Consequently,

u_{0} − u_{i} + v_{i} − v_{j} + 1 = u′_{0} − u′_{i} + v′_{i} − v′_{j} + 1 ≤ j − 1.

It remains to check inequalities (3.8). After rule (ivb) is applied, one has v_{k−1} = n − k + 1 and, for some i < k − 1, u_{i} = v_{i}.

Therefore rule (iiib) or (ivb) applies to the next step. In either case one has b_{k} < a_{k−1}.

Recall that

b_{k} = v′_{k−l} + l < u′_{k} = a_{k}

and

v_{k−1} = … = v_{k−l} = n − k + 1.

It follows that l′ = 1 + max{i|v_{k−1−i} = n − k + 1} ≥ l.

If v_{k−1−l′} + l′ < u_{k−1} then rule (ivb) applies to X^{(k−1)} and

b_{k−1} = v_{k−1−l′} + l′ ≥ v′_{k−l} + l = b_{k}.

If v_{k−1−l′} + l′ ≥ u_{k−1} then l = l′, u_{k} = u_{k−1} and

b_{k−1} = v_{k−1−l′} + l′ = v_{k−1−l} + l = u_{k−1} > b_{k}.
□

3.5. Some properties of the bijection.

3.5.1. (n, 1) trapezoids. If one starts from an (n, 1) trapezoid, then only rules (i) and (ii) apply, and it is easy to see that one gets in the end an (n, 1) GOGAm trapezoid, and that it is obtained by subtracting from any entry of the Gog trapezoid the number of inversions which cover it. The same remark applies to the inverse map, so that our bijection restricts to a bijection between (n, 1) trapezoids.

3.5.2. (n, 2, m) trapezoids. One can check that our bijection restricts to a bijection between (n, 2, m) Gog trapezoids and (n, 2, m) Magog trapezoids for all m ≤ n. This does not cause any difficulty, but is somewhat cumbersome to write down, so we leave this verification to the interested reader.

3.5.3. A statistic. For a Gog triangle X, the entry X_{11} gives the position of the 1 in the bottom row of the associated alternating sign matrix. If X is an (n, 2) Gog triangle, it follows from our algorithm that the 11 entry of the GOGAm triangle has value X_{11}. From Lemma 1 we conclude that, for the (n, 2) Magog triangle T, associated to X, one has X_{11} = ∑_{i=1}^{n} T_{i,n} − ∑_{i=1}^{n−1} T_{i,n−1}. It is known that, more generally, these two statistics on Gog and Magog triangles coincide (see, e.g., [5], where the corresponding statistics for ASM and TSSCPP are shown to coincide).

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] D. M. Bressoud, Proofs and Confirmations, The Story of the Alternating Sign Matrix Conjecture, Cambridge University Press, Cambridge, (1999).

[3] H. Cheballah, Combinatoire des matrices à signes alternants et des partitions planes, Ph.D. thesis, Université Paris Nord, 2011; available at

http://www-lipn.univ-paris13.fr/˜ cheballah/memoires/these.pdf.

[4] I. Fischer,A new proof of the refined alternating sign matrix theorem, J. Combin. Theory Ser. A 114 (2007), 253–264.

[5] T. Fonseca and P. Zinn-Justin, On the Doubly Refined Enumeration of Alternating Sign Matrices and Totally Symmetric Self-Complementary Plane Partitions, Electron. J. Combin. 15, (2008), Research Paper 81, 35 pp.

[6] A. N. Kirillov and A. D. Berenstein, Groups generated by involutions, Gelfand–Tsetlin patterns and combinatorics of Young tableaux, St.Petersburg Math. J. 7(1) (1996), 77–127.

[7] C. Krattenthaler, A Gog-Magog conjecture, unpublished manuscript; available at

http://www.mat.univie.ac.at/˜ kratt/artikel/magog.html.

[8] G. Kuperberg, Another proof of the alternating-sign matrix conjecture, Internat. Math. Notices no. 3 (1996), 139–150.

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

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

[11] D. Zeilberger, Proof of the alternating sign matrix conjecture, Electronic J. Combin 3 (1996), Article R13, 84 pp.

Laboratoire d’Informatique de Paris Nord, UMR 7030 CNRS, Université Paris 13, F-93430 Villetaneuse, France

E-mail address: Hayat.Cheballah@lipn.univ-paris13.fr

CNRS, IGM–Université Paris-Est, 77454 Marne-la-Vallée Cedex2, France

E-mail address: biane@univ-mlv.fr