Séminaire Lotharingien de Combinatoire 75 (2016), Article B75e

A SIMPLE EXPLICIT BIJECTION BETWEEN (n, 2)-GOG AND MAGOG TRAPEZOIDS

JÉRÉMIE BETTINELLI

Abstract. A sub-problem of the open problem of finding an explicit bijection between alternating sign matrices and totally symmetric self-complementary plane partitions consists in finding an explicit bijection between so-called (n, k)-Gog trapezoids and (n, k)-Magog trapezoids. A quite involved bijection was found by Biane and Cheballah in the case k = 2. We give here a simpler bijection for this case.

Key words and phrases: bijection, Gog, Magog, alternating sign matrix, totally symmetric self-complementary plane partition. AMS classification: 05A19.

1. Introduction

One of the most famous open problems in bijective combinatorics is to find an explicit bijection between alternating sign matrices of a given size and totally symmetric self-complementary plane partitions of the same size. These objects of combinatorial interest have been known since the end of the ’90s to be equinumerous [And94, Zei96] but, as of today, there is no direct bijective proof of this fact. We refer the reader to [Bre99, Che11] for more information on this story.

The previous objects are in known bijections with arrays of integers called Gog and Magog triangles. These triangles of size n are Young diagrams of shape (n, n − 1, …, 2, 1) filled with positive integers satisfying monotonicity conditions along vertical, horizontal and possibly diagonal lines. Although they satisfy very similar monotonicity conditions, nobody managed to find a direct bijection between these integer-filled triangles so far. Another surprising fact is that, if we only consider the first k rows of the triangles, the objects we obtain are also equinumerous. These objects, called (n, k) trapezoids, were introduced in [MRR86], where they were conjectured to be equinumerous. This was later proved by Zeilberger [Zei96, Lemma 1].

CNRS & Laboratoire d’Informatique de l’École polytechnique; normalesup.org/�bettinel; jeremie.bettinelli@normalesup.org.

The supposedly simplest problem of finding an explicit bijection between (n, k)- Gog trapezoids and (n, k)-Magog trapezoids has been solved only for k ≤ 2. In fact, for k = 1, the objects are exactly the same, so there is nothing to prove. There is, however, a refined conjecture appearing in [MRR86], which involves the number of entries equal to 1 and the number of entries equal to the maximum possible value in the first and last rows. Proving this conjecture in a bijective way, even in the case k = 1 is nontrivial; it was achieved by Krattenthaler [Kra]. In fact, Krattenthaler conjectured that more general objects called (ℓ, n, k) trapezoids are equinumerous and that the previous statistics coincide; his bijection was established in this more general context, that is, between (ℓ, n, 1)-Gog and Magog trapezoids.

For k = 2, a bijection was found by Biane and Cheballah [BC12]. Their bijection is relatively complicated and uses the so-called Schützenberger involution. It does not match the previous statistics of Mills, Robbins, and Rumsey. It does, however, match different statistics, expressed in terms of the rightmost entry for a Gog trapezoid and in terms of the two rightmost entries of both rows for Magog trapezoids. In this note, we give a different bijection for this case. Our bijection is very simple and involves only one operation. It does not match either aforementioned statistics.

Acknowledgment. I thank Jean-François Marckert for introducing this problem to me.

2. Magog and Gog trapezoids

In this note, we are solely considering (n, 2) trapezoids, and we furthermore impose that n ≥ 3 in order to avoid trivialities. Let us give proper definitions (see Figure 1 for more graphical definitions and examples).

Definition 1. Let n be an integer ≥ 3. An (n, 2)-Magog trapezoid is an array of 2n − 1 positive integers m_{1,1}, …, m_{1,n−1}, m_{2,1}, …, m_{2,n} such that

(i) m_{i,j} ≤ m_{i,j+1} for all i ∈ {1, 2} and j ∈ {1, …, n + i − 3}; (ii) m_{1,j} ≤ m_{2,j} ≤ j for all j ∈ {1, …, n − 1} and m_{2,n} ≤ n.

Definition 2. Let n be an integer ≥ 3. An (n, 2)-Gog trapezoid is an array of 2n − 1 positive integers g_{1,1}, …, g_{1,n}, g_{2,1}, …, g_{2,n−1} such that

(i) g_{i,j} ≤ g_{i,j+1} for all i ∈ {1, 2} and j ∈ {1, …, n − i}; (ii) g_{1,j} < g_{2,j} < j + 2 for all j ∈ {1, …, n − 1}; (iii) g_{1,j+1} ≤ g_{2,j} for all j ∈ {1, …, n − 1}.

We denote the sets of (n, 2)-Magog and Gog trapezoids by M_{n} and G_{n}, respectively.

A SIMPLE EXPLICIT BIJECTION BETWEEN (n, 2)-GOG AND MAGOG TRAPEZOIDS 3

PSfrag replacements

1 2 3 4 5 6 7 8

g_{1,1} g_{1,2} g_{1,3} g_{1,4} g_{1,5} g_{1,6} g_{1,7} g_{1,8} g_{2,1} g_{2,2} g_{2,3} g_{2,4} g_{2,5} g_{2,6} g_{2,7} m_{1,1} m_{1,2} m_{1,3} m_{1,4} m_{1,5} m_{1,6} m_{1,7} m_{2,1} m_{2,2} m_{2,3} m_{2,4} m_{2,5} m_{2,6} m_{2,7} m_{2,8}

(8, 2)-Gog trapezoid (8, 2)-Magog trapezoid PSfrag replacements

1 2 3 4 5 6 7 8

g_{1,1} g_{1,2} g_{1,3} g_{1,4} g_{1,5} g_{1,6} g_{1,7} g_{1,8} g_{2,1} g_{2,2} g_{2,3} g_{2,4} g_{2,5} g_{2,6} g_{2,7} m_{1,1} m_{1,2} m_{1,3} m_{1,4} m_{1,5} m_{1,6} m_{1,7} m_{2,1} m_{2,2} m_{2,3} m_{2,4} m_{2,5} m_{2,6} m_{2,7} m_{2,8}

(8, 2)-Gog trapezoid (8, 2)-Magog trapezoid

2 2 4 5 6 7 8 1 1 2 4 4 5 7 7 1 2 2 4 4 6 7 7 1 1 2 4 4 5 7 7

Figure 1. The conditions satisfied by (n, 2)-Magog and Gog trapezoids. Every sequence formed by numbers obtained by following the direction of a simple-arrowhead (respectively a double-arrowhead) arrow is nondecreasing (respectively increasing).

3. From Magog to Gog

Let us consider an (n, 2)-Magog trapezoid M = (m_{i,j}). We say that an integer j ∈ {1, …, n − 2} is a bug if m_{1,j+1} > m_{2,j} + 1. For instance, 3 is the only bug of the Magog trapezoid of Figure 1. We set Φ_{n}(M) := (g_{ij}), where (g_{ij}) is constructed as follows (see Figure 2).

First case: M has at least one bug. In this case, we let k be the smallest bug of M and we set

g_{2,j} := m_{2,j} + 1 for 1 ≤ j ≤ k − 1 ;  g_{2,j} := m_{2,j+1} for k ≤ j ≤ n − 1 ;
g_{1,j} := m_{1,j} for 1 ≤ j ≤ k; g_{1,k+1} := m_{2,k}; g_{1,j} := m_{1,j−1} − 2 for k + 2 ≤ j ≤ n .

Second case: M does not have bugs and m_{2,n−1} < m_{2,n}. In this case, we set

g_{2,j} := m_{2,j} + 1 for 1 ≤ j ≤ n − 2 ;  g_{2,n−1} := m_{2,n};
g_{1,j} := m_{1,j} for 1 ≤ j ≤ n − 1 ;  g_{1,n} := m_{2,n−1} .

4 JÉRÉMIE BETTINELLI

PSfrag replacements

↦ +1 −2 < = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 PSfrag replacements

↦ +1 −2 < = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 PSfrag replacements

↦ +1 −2 < = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 1 2 2 4 4 6 6 8 1 1 2 3 4 4 5 2 3 3 5 5 7 8 1 1 2 3 4 4 5 6 PSfrag replacements

↦ +1 −2 < = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 1 2 2 4 4 6 6 8 1 1 2 3 4 4 5 2 3 3 5 5 7 8 1 1 2 3 4 4 5 6 PSfrag replacements

↦ +1 −2 < = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 1 2 2 4 4 6 6 8 1 1 2 3 4 4 5 2 3 3 5 5 7 8 1 1 2 3 4 4 5 6 1 2 2 4 4 6 6 6 1 1 2 3 4 4 5 2 3 3 5 5 7 7 1 1 2 3 4 4 5 7 PSfrag replacements

↦ +1 −2 < = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 1 2 2 4 4 6 6 8 1 1 2 3 4 4 5 2 3 3 5 5 7 8 1 1 2 3 4 4 5 6 1 2 2 4 4 6 6 6 1 1 2 3 4 4 5 2 3 3 5 5 7 7 1 1 2 3 4 4 5 7

Figure 2. The three cases of the bijection, from a Magog trapezoid to a Gog trapezoid. On the top line, the first bug is 3: it is symbolized by a small black diagonal line. The colored blocks are moved and, whenever there is a tag on a block, it is added to all the elements of the block.

Third case: M does not have bugs and m_{2,n−1} = m_{2,n}. In this case, we set

g_{2,j} := m_{2,j} + 1 for 1 ≤ j ≤ n − 1 ;
g_{1,j} := m_{1,j} for 1 ≤ j ≤ n − 1 ;  g_{1,n} := m_{2,n} + 1 .

A SIMPLE EXPLICIT BIJECTION BETWEEN (n, 2)-GOG AND MAGOG TRAPEZOIDS 5

Let us check that Φ_{n}(M) ∈ G_{n}. First, observe that, if j is not a bug, then, by definition, m_{1,j+1} ≤ m_{2,j} + 1, so that the yellow and purple blocks always satisfy the diagonal inequalities after the mapping. It is straightforward to verify that the other inequalities are satisfied in the second and third case. In the first case, notice that g_{1,k} = m_{1,k} ≤ m_{2,k} = g_{1,k+1} and g_{1,k+1} = m_{2,k} ≤ m_{1,k+1} − 2 = g_{1,k+2} as k is a bug. Furthermore, g_{2,k−1} = m_{2,k−1} + 1 ≤ m_{2,k} + 1 ≤ m_{1,k+1} − 1 ≤ m_{2,k+1} − 1 = g_{2,k} − 1 so that the horizontal inequalities are satisfied. Moreover, g_{1,k} = m_{1,k} ≤ m_{2,k} ≤ m_{1,k+1} −2 ≤ m_{2,k+1} −2 = g_{2,k} −2, g_{1,k+1} = m_{2,k} ≤ m_{2,k+2} −2 = g_{2,k+1} −2, g_{1,j} = m_{1,j−1} − 2 ≤ m_{2,j+1} − 2 = g_{2,j} − 2 for k + 2 ≤ j ≤ n − 1, and g_{2,j} = m_{2,j+1} < j + 2 for k ≤ j ≤ n − 1, so that the vertical inequalities are also satisfied. Finally, the diagonal inequalities are satisfied since g_{1,k+1} = m_{2,k} ≤ m_{2,k+1} = g_{2,k} and g_{1,j} = m_{1,j−1} − 2 ≤ m_{2,j} − 2 = g_{2,j−1} − 2 for k + 2 ≤ j ≤ n.

4. From Gog to Magog

We now consider an (n, 2)-Gog trapezoid G = (g_{i,j}) and construct Ψ_{n}(G) = (m_{ij}) as follows. We define

(1)  k := max {j ∈ {2, …, n − 1} : g_{2,j−1} ≤ g_{1,j+1} + 1}.

This number is well defined as g_{2,1} = 2 ≤ g_{1,3} + 1.

First case: k ≤ n − 2. We set

m_{2,j} := g_{2,j} − 1 for 1 ≤ j ≤ k − 1 ; m_{2,k} := g_{1,k+1} ; m_{2,j} := g_{2,j−1}, k + 1 ≤ j ≤ n;
m_{1,j} := g_{1,j} for 1 ≤ j ≤ k;  m_{1,j} := g_{1,j+1} + 2 for k + 1 ≤ j ≤ n − 1 .

Second case: k = n − 1 and g_{1,n} < g_{2,n−1}. We set

m_{2,j} := g_{2,j} − 1 for 1 ≤ j ≤ n − 2 ; m_{2,n−1} := g_{1,n}; m_{2,n} := g_{2,n−1} ;
m_{1,j} := g_{1,j} for 1 ≤ j ≤ n − 1 .

Third case: k = n − 1 and m_{1,n} = m_{2,n−1}. We set

m_{2,j} := g_{2,j} − 1 for 1 ≤ j ≤ n − 1  m_{2,n} := g_{1,n} − 1 ;
m_{1,j} := g_{1,j} for 1 ≤ j ≤ n − 1 .

We now show that Ψ_{n}(G) ∈ M_{n}. In the first and second case, the definition of k entails that m_{2,k−1} = g_{2,k−1} − 1 ≤ g_{1,k+1} = m_{2,k} , so that the horizontal

6 JÉRÉMIE BETTINELLI

PSfrag replacements

↦ −1 +2 > = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 PSfrag replacements

↦ −1 +2 > = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 PSfrag replacements

↦ −1 +2 > = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 1 2 2 4 4 6 6 8 1 1 2 3 4 4 5 2 3 3 5 5 7 8 1 1 2 3 4 4 5 6 PSfrag replacements

↦ −1 +2 > = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 1 2 2 4 4 6 6 8 1 1 2 3 4 4 5 2 3 3 5 5 7 8 1 1 2 3 4 4 5 6 PSfrag replacements

↦ −1 +2 > = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 1 2 2 4 4 6 6 8 1 1 2 3 4 4 5 2 3 3 5 5 7 8 1 1 2 3 4 4 5 6 1 2 2 4 4 6 6 6 1 1 2 3 4 4 5 2 3 3 5 5 7 7 1 1 2 3 4 4 5 7 PSfrag replacements

↦ −1 +2 > = 1 2 2 4 4 6 7 7 1 1 2 4 4 6 7 2 3 4 4 6 7 7 1 1 2 2 2 2 4 5 1 2 2 4 4 6 6 8 1 1 2 3 4 4 5 2 3 3 5 5 7 8 1 1 2 3 4 4 5 6 1 2 2 4 4 6 6 6 1 1 2 3 4 4 5 2 3 3 5 5 7 7 1 1 2 3 4 4 5 7

Figure 3. The three cases of the bijection, from a Gog trapezoid to a Magog trapezoid. On the top line, k = 3.

inequalities hold. In the second case, we get the desired conclusion by noticing that m_{2,n−1} = g_{1,n} ≤ g_{2,n−1} − 1 ≤ n − 1 and m_{2,n} = g_{2,n−1} ≤ n. In the first case,

by definition of k, m_{1,j} = g_{1,j+1} + 2 ≤ g_{2,j−1} = m_{2,j} for k + 1 ≤ j ≤ n − 1 and, by

vertical inequalities, m_{2,j} = g_{2,j−1} ≤ j for k + 1 ≤ j ≤ n. Finally, still by definition

of k, m_{2,k} = g_{1,k+1} ≤ g_{1,k+2} ≤ g_{2,k} − 2 ≤ k − 1. This establishes the claim in the first case. The third case is straightforward.

5. The previous mappings are inverses of each other

We now prove that the previous mappings are bijections.

Theorem 1. The mappings Φ_{n} : M_{n} → G_{n} and Ψ_{n} : G_{n} → M_{n} are bijections, which are inverse one from another.

Proof.We have already established that Φ_{n} : M_{n} → G_{n} and Ψ_{n} : G_{n} → M_{n}. It remains to show that Ψ_{n}∘Φ_{n} and Φ_{n}∘Ψ_{n} are the identity on M_{n} and G_{n}, respectively. In fact, we will see that the three cases we distinguished are in correspondence via the bijection.

First case. Let M = (m_{i,j}) ∈ M_{n} be a Magog trapezoid that has a bug, and let k be its smallest bug. As in Section 3, we define (g_{ij}) := Φ_{n}(M). We have g_{2,k−1} = m_{2,k−1} + 1 ≤ m_{2,k} + 1 = g_{1,k+1} + 1 and, for k + 1 ≤ j ≤ n − 1, g_{1,j+1} + 1 =

m_{1,j} − 1 < m_{2,j} = g_{2,j−1} for k + 2 ≤ j ≤ n − 1, so that

max {j ∈ {2, …, n − 1} : g_{2,j−1} ≤ g_{1,j+1} + 1} = k.

As the box moving procedure of Section 4 is clearly the inverse of that of Section 3, we conclude that (Ψ_{n} ∘ Φ_{n})(M) = M.

Let now G = (g_{ij}) ∈ G_{n} be such that the integer k defined by (1) is smaller than or equal to n − 2. In order to conclude that (Φ_{n} ∘ Ψ_{n})(G) = G, it is sufficient to show that k is the smallest bug of (m_{i,j}) := Ψ_{n}(G). This is indeed the case as m_{1,k+1} = g_{1,k+2} + 2 > g_{1,k+1} + 1 = m_{2,k} + 1 and, for 1 ≤ j ≤ k − 1, m_{1,j+1} =

g_{1,j+1} ≤ g_{2,j} = m_{2,j} + 1.

Second and third case. Let M = (m_{i,j}) ∈ M_{n} be a bug-free Magog trapezoid and (g_{ij}) := Φ_{n}(M). If we are in the second case, then g_{2,n−2} = m_{2,n−2} + 1 ≤

m_{2,n−1} + 1 = g_{1,n} + 1, and, if we are in the third case, then g_{2,n−2} = m_{2,n−2} + 1 ≤

m_{2,n} + 1 = g_{1,n} , so that, in both cases,

max {j ∈ {2, …, n − 1} : g_{2,j−1} ≤ g_{1,j+1} + 1} = n − 1.

We conclude as above that (Ψ_{n} ∘ Φ_{n})(M) = M.

Let now G = (g_{ij}) ∈ G_{n} be such that the integer k defined by (1)is equal to n−1. We see that (Φ_{n} ∘ Ψ_{n})(G) = G by noticing that (m_{i,j}) := Ψ_{n}(G) is bug-free as, for 1 ≤ j ≤ n − 1, m_{1,j+1} = g_{1,j+1} ≤ g_{2,j} = m_{2,j} + 1. □

8 JÉRÉMIE BETTINELLI

6. Extension to (ℓ, n, 2) trapezoids and perspectives

Our bijection can trivially be extended to (ℓ, n, 2) trapezoids, where ℓ ≥ 0 is an integer. Here, an (ℓ, n, 2)-Magog trapezoid is defined as an (n, 2)-Magog trapezoid, with the difference that item (ii)of Definition 1 is replaced by

(ii’) m_{1,j} ≤ m_{2,j} ≤ j + ℓ for all j ∈ {1, …, n − 1} and m_{2,n} ≤ n + ℓ. See Figure 4. Similarly, an (ℓ, n, 2)-Gog trapezoid is defined as an (n, 2)-Gog trapezoid with the difference that item (ii)of Definition 2 is replaced by

(ii’) g_{1,j} < g_{2,j} < j + 2 + ℓ for all j ∈ {1, …, n − 1}; PSfrag replacements

4 5 6 7 8 9 10 11 g_{1,1} g_{1,2} g_{1,3} g_{1,4} g_{1,5} g_{1,6} g_{1,7} g_{1,8} g_{2,1} g_{2,2} g_{2,3} g_{2,4} g_{2,5} g_{2,6} g_{2,7} m_{1,1} m_{1,2} m_{1,3} m_{1,4} m_{1,5} m_{1,6} m_{1,7} m_{2,1} m_{2,2} m_{2,3} m_{2,4} m_{2,5} m_{2,6} m_{2,7} m_{2,8}

(3, 8, 2)-Gog trapezoid (3, 8, 2)-Magog trapezoid

Figure 4. Definition of (ℓ, n, 2) trapezoids.

For any ℓ ≥ 1 and n ≥ 3, the mappings Φ_{n} and Ψ_{n} can be extended without any differences in the construction into bijections between the set of (ℓ, n, 2)-Magog trapezoids and the set of (ℓ, n, 2)-Gog trapezoids. The proofs can be copied almost verbatim, the only thing to do is to add ℓ whenever we use one of the bounds changed by these definitions.

Unfortunately, as of today, we did not manage to extend this bijection to (n, 3) trapezoids. The mapping Φ_{n} exchanges the sizes of two consecutive rows so that one could think that, in the case of (n, 3) trapezoids, we would need to apply a similar operation several times in order to pass from a Magog to a Gog trapezoid. Unfortunately, whenever a third row is present, we cannot slide the boxes of two consecutive rows without breaking the rules. This question remains under investigation.

It has also been brought to our attention that our construction bears some intriguing similarities with a construction used by Krattenthaler [Kra89, Section 2] in order to show the q-log-concavity of Gaussian binomial coefficients. In the latter construction, two rows of strictly increasing integers are considered and one carefully chosen entry of the second row is removed from it and inserted in the first row after addition of a constant. A major difference between both constructions lies in the fact that the entries in the latter one only satisfy monotonicity relations in one direction (along rows) so that the objects are less constrained.

References

[And94] George E. Andrews. Plane partitions. V. The TSSCPP conjecture. J. Combin. Theory Ser. A, 66(1):28–39, 1994.

[BC12] Philippe Biane and Hayat Cheballah. Gog and Magog triangles, and the Schützenberger involution. Sém. Lothar. Combin., 66:Art. B66d, 20, 2012.

[Bre99] David M. Bressoud. Proofs and confirmations. MAA Spectrum. Mathematical Association of America, Washington, DC; Cambridge University Press, Cambridge, 1999.

[Che11] Hayat Cheballah. Combinatoire des matrices à signes alternants et des partitions planes. PhD thesis, LIPN, Université Paris-Nord, 2011.

[Kra] Christian Krattenthaler. A gog-magog conjecture. Unpublished manuscript, available at

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

[Kra89] Christian Krattenthaler. On the q-log-concavity of Gaussian binomial coefficients. Monatsh. Math., 107(4):333–339, 1989.

[MRR86] William H. Mills, David P. Robbins, and Howard Rumsey, Jr. Self-complementary totally symmetric plane partitions. J. Combin. Theory Ser. A, 42(2):277–292, 1986.

[Zei96] Doron Zeilberger. Proof of the alternating sign matrix conjecture. Electron. J. Combin., 3(2):Research Paper 13, 84 pp., 1996.