# Gog, Magog and Schützenberger II: left trapezoids

Philippe Biane and Hayat Cheballah

Institut Gaspard-Monge, université Paris-Est Marne-la-Vallée, France

**Abstract.** We are interested in finding an explicit bijection between two families of combinatorial objects: Gog and Magog triangles. These two families are particular classes of Gelfand-Tsetlin triangles and are respectively in bijection with alternating sign matrices (ASM) and totally symmetric self complementary plane partitions (TSSCPP). For this purpose, we introduce left Gog and GOGAm trapezoids. We conjecture that these two families of trapezoids are equienumerated and we give an explicit bijection between the trapezoids with one or two diagonals.

**Résumé.** Nous nous intéressons ici à trouver une bijection explicite entre deux familles d'objets combinatoires: les triangles Gog et Magog. Ces deux familles d'objets sont des classes particulières des triangles de Gelfand-Tsetlin et sont respectivement en bijection avec les matrices à signes alternants (ASMs) et les partitions planes totalement symétriques auto-complémentaires (TSSCPPs). Pour ce faire, nous introduisons les Gog et les GOGAm trapèzes gauches. Nous conjecturons que ces deux familles de trapèzes sont équipotents et nous donnons une bijection explicite entre ces trapèzes à une et deux lignes.

**Keywords:** Gog, Magog triangles and trapezoids, Schützenberger Involution, alternating sign matrices, totally symmetric self complementary plane partitions

## 1 Introduction

This paper is a sequel to [1], to which we refer for more on the background of the Gog-Magog problem (see also [2] and [3] for a thorough discussion). It is a well known open problem in bijective combinatorics to find a bijection between alternating sign matrices and totally symmetric self complementary plane partitions. One can reformulate the problem using so-called Gog and Magog triangles, which are particular species of Gelfand-Tsetlin triangles. In particular, Gog triangles are in simple bijection with alternating sign matrices of the same size, while Magog triangles are in bijection with totally symmetric self complementary plane partitions. In [4], Mills, Robbins and Rumsey introduced trapezoids in this problem by cutting out $k$ diagonals on the right (with the conventions used in the present paper) of a triangle of size $n$, and conjectured that Gog and Magog trapezoids of the same size are equienumerated. Zeilberger [7] proved this conjecture, but no explicit bijection is known, except for $k = 1$ (which is a relatively easy problem) and for $k = 2$, this bijection being the main result of [1]. In this last paper a new class of triangles and trapezoids was introduced, called GOGAm triangles (or trapezoids), which are in bijection with the Magog triangles by the Schützenberger involution acting on Gelfand-Tsetlin triangles.
2. and such that
$$X_{n,j} = j, \quad 1 \le j \le n. \tag{4}$$

Here is an example of Gog triangle of size $n = 5$.

$$
\begin{array}{ccccc}
1 & 2 & 3 & 4 & 5 \\
\cline{1-5}
1 & 3 & 4 & 5 & \\
\cline{1-4}
1 & 4 & 5 & & \\
\cline{1-3}
2 & 4 & & & \\
\cline{1-2}
3 & & & & \\
\end{array}
\tag{5}
$$

It is immediate to check that the set of Gog triangles of size $n$ is a sublattice of the Gelfand-Tsetlin triangles.

**Definition 2.3** A $(n, k)$ right Gog trapezoid (for $k \le n$) is an array of positive integers $X = (X_{i,j})_{n \ge i \ge j \ge 1; i-j \le k-1}$ formed from the $k$ rightmost SW-NE diagonals of some Gog triangle of size $n$.

Below is a (5, 2) right Gog trapezoid.

$$
\begin{array}{ccccc}
    & 4 & 5 & & \\
    &   &   &   & \\
    & 4 & 5 & & \\
    3 & 4 & & & \\
    1 & 3 & & & \\
    2 & & & & \\
\end{array}
\tag{6}
$$

**Definition 2.4** A $(n, k)$ left Gog trapezoid (for $k \le n$) is an array of positive integers $X = (X_{i,j})_{n \ge i \ge j \ge 1; k \ge j}$ formed from the $k$ leftmost NW-SE diagonals of a Gog triangle of size $n$.

A more direct way of checking that a left Gelfand-Tsetlin trapezoid is a left Gog trapezoid is to verify that its rows are strictly increasing and that its SW-NE diagonals are bounded by 1, 2, ..., $n$ as it is shown in the figure below which represents a (5, 2) left Gog trapezoid.

$$
\begin{array}{ccccc}
    & 1 & 2 & & \\
    \le &   &   &   & \\
    1 & 2 & 3 & & \\
    \cline{2-5}
    1 & 3 & 4 & & \\
    \cline{2-4}
    2 & 3 & 5 & & \\
    \cline{2-3}
    2 & 4 & & & \\
    \cline{2-2}
    4 & & & & \\
\end{array}
\tag{7}
$$
There is a simple involution $X \to \tilde{X}$ on Gog triangles given by

$$ \tilde{X}_{i,j} = n + 1 - X_{i,i+1-j} \quad (8) $$

which exchanges left and right trapezoids of the same size. This involution corresponds to a vertical symmetry of associated ASMs.

### 2.2.1 Minimal completion

Since the set of Gog triangles is a lattice, given a left (resp. a right) Gog trapezoid, there exists a smallest Gog triangle from which it can be extracted. We call this Gog triangle the *canonical completion* of the left (resp. the right) Gog trapezoid. Their explicit value is computed in the next Proposition.

**Proposition 2.5**

1. Let $X$ be a $(n, k)$ right Gog trapezoid, then its canonical completion satisfies

$$ X_{ij} = j \quad \text{for} \quad i \ge j + k. \quad (9) $$

2. Let $X$ be a $(n, k)$ left Gog trapezoid, then its canonical completion satisfies

$$ X_{i,j} = \max(X_{i,k} + j - k, X_{i-1,k} + j - k - 1, \dots, X_{i-j+k,k}) \quad \text{for } j \ge k. \quad (10) $$

**Proof:** The first case (right trapezoids) is trivial, the formula for the second case (left trapezoids) is easily proved by induction on $j - k$. $\square$

For example, the completion of the (5, 2) left Gog trapezoid in (7)

$$ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ \cline{1-5} 1 & 3 & 4 & 5 & \\ 2 & 3 & 4 & & \\ 2 & 4 & & & \\ 4 & & & & \\ \end{array} \quad (11) $$

Remark that the supplementary entries of the canonical completion of a left Gog trapezoid depend only on its rightmost NW-SE diagonal.

The right trapezoids defined above coincide (modulo easy reindexations) with those of Mills, Robbins, Rumsey [4], and Zeilberger [7]. They are in obvious bijection with the ones in [1] (actually the Gog trapezoids of [1] are the canonical completions of the right Gog trapezoids defined above).

### 2.3 GOGAm triangles and trapezoids

**Definition 2.6** A GOGAm triangle of size $n$ is a Gelfand-Tsetlin triangle such that $X_{nn} \le n$ and, for all $1 \le k \le n-1$, and all $n = j_0 > j_1 > j_2 > \dots > j_{n-k} \ge 1$, one has

$$ \left( \sum_{i=0}^{n-k-1} X_{j_i+i, j_i} - X_{j_{i+1}+i, j_{i+1}} \right) + X_{j_{n-k}+n-k, j_{n-k}} \le k \quad (12) $$
In the next section we will give a bijective proof of this conjecture for (n, 1) and (n, 2) trapezoids.

Remark that the right and left Gog trapezoids of shape (n, k) are equ (in fact a simple bijection between them was given above).

If we consider left GOGAm trapezoids as GOGAm triangles, using the canonical completion, then we can take their image by the Schützenberger involution and obtain a subset of the Magog triangles, for each (n, k). It seems however that this subset does not have a simple direct characterization. This shows that GOGAm triangles and trapezoids are a useful tool in the bijection problem between Gog and Magog triangles.

# 4 Bijections between Gog and GOGAm left trapezoids

## 4.1 (n, 1) left trapezoids

The sets of (n, 1) left Gog trapezoids and of (n, 1) left GOGAm trapezoids coincide with the set of sequences X$_{n,1}$, ..., X$_{1,1}$ satisfying $X_{j,1} \le n - j + 1$ (note that these sets are counted by Catalan numbers). Therefore the identity map provides a trivial bijection between these two sets.

## 4.2 (n, 2) left trapezoids

In order to treat the (n, 2) left trapezoids we will recall some definitions from [1].

### 4.2.1 Inversions

**Definition 4.1** An inversion in a Gelfand-Tsetlin triangle is a pair $(i, j)$ such that $X_{i,j} = X_{i+1,j}$.

For example, the Gog triangle in (18) contains three inversions, (2, 2), (3, 1), (4, 1), the respective equalities being in red on this picture.

<figure><img src="image_1.png" /></figure>

**Definition 4.2** Let $X = (X_{i,j})_{n \ge i \ge j \ge 1}$ be a Gog triangle and let $(i, j)$ be such that $1 \le j \le i \le n$.

An inversion $(k, l)$ covers $(i, j)$ if $i = k + p$ and $j = l + q$ for some $p$ with $1 \le p \le n - k$.

The entries $(i, j)$ covered by an inversion are depicted with " + " on the following picture.

<figure><img src="image_2.png" /></figure>
Let us assume that we have constructed the trapezoids up to $Y^{(l)}$, that $Y^{(l)} \le X$, that $Y_{ij}^{(l)} = X_{ij}$ for $i \le i_l$, and that inequalities (21) and (22) are satisfied by $Y^{(l)}$ for $i \ge i_l + 1$. This is the case for $l = 0$.

Let $m$ be the largest integer such that $Y_{m,2}^{(l)} = Y_{i_{l+1}+1,2}^{(l)}$. We put

$$Y_{i,1}^{(l+1)} = Y_{i,1}^{(l)} \quad \text{for} \quad n \ge i \ge m \quad \text{and} \quad i_{l+1} \ge i$$

$$Y_{i,1}^{(l+1)} = Y_{i+1,1}^{(l)} \quad \text{for} \quad m-1 \ge i > i_{l+1}$$

$$Y_{i,2}^{(l+1)} = Y_{i,2}^{(l)} \quad \text{for} \quad n \ge i \ge m+1 \quad \text{and} \quad i_{l+1} \ge i$$

$$Y_{i,2}^{(l+1)} = Y_{i,2}^{(l)} - 1 \quad \text{for} \quad m \ge i \ge i_{l+1} + 1.$$

From the definition of $m$, and the fact that $X$ is a Gog trapezoid, we see that this new triangle is a Gelfand-Tsetlin triangle, that $Y^{(l+1)} \le X$, and that $Y_{ij}^{(l+1)} = X_{ij}$ for $i \le i_{l+1}$. Let us now check that the trapezoid $Y^{(l+1)}$ satisfies the inequalities (21) and (22) for $i \ge i_{l+1} + 1$. The first series of inequalities, for $i \ge i_{l+1} + 1$, follow from the fact that $Y^{(l)} \le X$. For the second series, they are satisfied for $i \ge m+1$ since this is the case for $Y^{(l)}$. For $m \ge i \ge i_{l+1} + 1$, observe that

$$Y_{i,2}^{(l+1)} - Y_{i+1,1}^{(l+1)} + Y_{i+1,1}^{(l+1)} \le Y_{i,2}^{(l+1)} = Y_{m,2}^{(l+1)} = Y_{m,2}^{(k)} - 1 \le n - m + 1$$

by (21) for $Y(l)$, from which (22) follows.

This proves that $Y^{(l+1)}$ again satisfies the induction hypothesis. Finally $Y = Y^{(k)}$ is a GOGAm triangle: indeed inequalities (21) follow again from $Y^{(l+1)} \le X$, and (22) for $i \le i_k$ follow from the fact that there are no inversions in this range. It follows that the above algorithm provides a map from $(n, 2)$ left Gog trapezoids to $(n, 2)$ left GOGAm trapezoids. Observe that the number of inversions in the leftmost diagonal of $Y$ is the same as for $X$, but the positions of these inversions are not the same in general.

### 4.2.5 Inverse map

We now describe the inverse map, from GOGAm left trapezoids to Gog left trapezoids.

We start from an $(n, 2)$ GOGAm left trapezoid $Y$, and construct a sequence $Y = Y^{(k)}, Y^{(k-1)}, Y^{(k-2)}, \dots, Y^{(0)} = X$ of intermediate Gelfand-Tsetlin trapezoids.

Let $n-1 \ge \iota_1 > \iota_2 > \dots > \iota_k \ge 1$ be the inversions of the leftmost diagonal of $Y$, and let $\iota_{k+1} = 0$. Assume that $Y^{(l)}$ has been constructed and that $Y_{ij}^{(l)} = Y_{ij}$ for $i-j \ge \iota_{l+1}$. This is the case for $l=k$.

Let $p$ be the smallest integer such that $Y_{i_{l+1},2}^{(l)} = Y_{p,2}^{(l)}$. We put

$$Y_{i,1}^{(l-1)} = Y_{i,1}^{(l)} \quad \text{for} \quad n \ge i \ge \iota_l + 1 \quad \text{and} \quad p \ge i$$

$$Y_{i,1}^{(l-1)} = Y_{i-1,1}^{(l)} \quad \text{for} \quad \iota_l \ge i \ge p$$

$$Y_{i,2}^{(l-1)} = Y_{i,2}^{(l)} \quad \text{for} \quad n \ge i \ge \iota_l + 2 \quad \text{and} \quad p-1 \ge i$$

$$Y_{i,2}^{(l-1)} = X_{i,2}^{(l)} - 1 \quad \text{for} \quad \iota_l + 1 \ge i \ge p.$$

It is immediate to check that if $X$ is an $(n, 2)$ left Gog trapezoid, and $Y$ is its image by the first algorithm then the above algorithm applied to $Y$ yields $X$ back, actually the sequence $Y^{(l)}$ is the same. Therefore
in order to prove the bijection we only need to show that if $Y$ is a $(n, 2)$ left GOGAm trapezoid then the algorithm is well defined and $X$ is a Gog left trapezoid. This is a bit cumbersome, but not difficult, and very similar to the opposite case, so we leave this task to the reader.

### 4.2.6 A statistic

Observe that in our bijection the value of the bottom entry $X_{1,1}$ is unchanged when we go from Gog to GOGAm trapezoids. The same was true of the bijection in [1] for right trapezoids. Actually we make the following conjecture, which extends Conjecture 3.2 above.

**Conjecture 4.4** For each $n, k, l$ the $(n, k)$ left Gog and GOGAm trapezoids with bottom entry $X_{1,1} = l$ are equinumerated.

## 4.3 An example

In this section we work out an example of the algorithm from the Gog trapezoid $X$ to the GOGAm trapezoid $Y$ by showing the successive trapezoids $Y^{(k)}$. At each step we indicate the inversion in green, as well as the entry covered by this inversion in shaded green, and the values of the parameters $i_l, p$. The algorithm also runs backwards to yield the GOGAm→Gog bijection.

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>
a triangle of size $n$.

**Conjecture 4.7** For any $(n, k, l)$ satisfying $k + l \le n + 1$ the $(n, k, l)$ Gog and GOGAm rectangles are equienumerated.

As in the case of trapezoids, there is also a refined version of the conjecture with the statistic $X_{11}$ preserved.

One can check, using standard completions, that our bijections, in [1] and in the present paper, restrict to bijections for rectangles of size $(n, k, 2)$ or $(n, 2, l)$. Furthermore, in the case of $(n, 2, 2)$ rectangles, the bijections coming from left and right trapezoids are the same.

## Acknowledgements

This work is based on computer exploration and the authors use the open-source mathematical software Sage [6] and one of its extention, Sage-Combinat [5]

## References

[1] P. Biane and H. Cheballah. Gog and magog triangles and the schützenberger involution. Séminaire Lotharingien de Combinatoire, B66d, apr 2012.

[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*. PhD thesis, LIPN, Université Paris-Nord, 2011.

[4] W. Mills, D. Robbins, and H. Rumsey. Self complementary totally symmetric plane partitions. *J. Combin. Theory Ser. A*, 42, 1986.

[5] T. Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2008. http://combinat.sagemath.org.

[6] W. Stein et al. *Sage Mathematics Software (Version 5.0.1)*. The Sage Development Team, 2012. http://www.sagemath.org.

[7] D. Zeilberger. Proof of the alternating sign matrix conjecture. *Electronic J. Combin.*, 3, 1996.