Philippe Biane

Gog and Magog Triangles

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

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

An alternating sign matrix is a square matrix having coefficients in {-1, 0, 1} so that, in each row and in each column, if one forgets the zeros, the 1 and -1 entries alternate and the sum is 1, e.g.

(1.1)

    0 0 1 0 1 0 -1 1 0 1 0 0 0 0 1 0    
These matrices were introduced by Robbins and Rumsey [START_REF] Robbins | Determinants and alternating sign matrices[END_REF] in 1986 as a generalization of permutation matrices, after they discovered some startling properties of the λ-determinant, a deformation of usual determinants of matrices.

Around the same time interest in the enumeration of plane partitions lead to the question of enumerating several symmetry classes of plane partitions. Among these classes the so-called totally symmetric self complementary plane partitions (TSSCPP in short), as the one below, stood as the most symmetric ones. Empirical data showed that both the enumeration of ASM and of TSSCPP according to their size started with the numbers 1, 2, 7, 42, 429, 7436, 218348, 10850216 . . . which could be put into the closed form A n = n-1 j=0 (3j+1)! (n+j)! . There was then two main problems: prove the enumeration formula and find a bijective proof of the coincidence, if it exists. As we explain below, the enumeration problems were finally solved around 1994/5, but the proofs gave no hint as to the existence of a natural bijection between these objects. It turns out that both classes of objects, the ASM and the TSSCPP, can be encoded as triangles of positive integers whose rows interlace, like the following (such triangles are usually called Gelfand-Tsetlin triangles in representation theory where they occur as labels for bases of irreducible representations) Thus one can reformulate the problem as finding a bijection between two species of such Gelfand-Tsetlin triangles, which makes this problem completely elementary.

The purpose of this paper is to present a recent approach to this question which has lead to some progress towards the solution of the bijection poblem. In particular we will introduce a new class of objects, the GOGAm triangles and present some new conjectures. We also study the distribution of inversions and coinversions in Gog triangles. In particular we determine the pairs (p, q) for which there exists Gog triangles of a given size with p inversions and q coinversions.

The paper is organized as follows. In the first part we present a short survey of plane partitions and their enumeration, in particular the TSSCPP and the Magog triangles. In the second part we present the other combinatorial objects in which we are interested, the alternating sign matrices. As we briefly expalin, these objects arise in many places of algebra, representation theory and statistical physics. Much more information about these two parts can be found for example in the book by D. Bressoud [START_REF] Bressoud | Proofs and Confirmations, The Story of the Alternating Sign Matrix Conjecture[END_REF]. Then we present the approach to the bijection problem. Finally we give some results on the joint enumeration of inversions and coinversions in Gog triangles.

I thank both referees for their useful remarks and comments which lead to improvements in the presentation of this paper, in particular for correcting the statement of Proposition 5.3.

Plane partitions

2.1. Partitions, tableaux and triangles. A partition of n is a nonincreasing sequence of nonnegative integers with sum

n n = λ 1 + λ 2 + . . . , λ 1 λ 2 . . . , λ i 0.
This is a fundamental notion in mathematics which occurs in algebra, representation theory, combinatorics, number theory etc. See e.g. Andrews [START_REF] Andrews | The theory of partitions[END_REF], Fulton [START_REF] Fulton | Young tableaux[END_REF], Macdonald [START_REF] Macdonald | Symmetric functions and Hall Polynomials[END_REF], Ramanujan [START_REF] Andrews | Ramanujan's lost notebook. Part III[END_REF]. The usual way to depict a partition is by drawing superposed rows of squares with λ i squares in row i from above:

It is easy to derive the following generating series for the set of all partitions, where |λ| = i λ i λ

q |λ| = ∞ n=1 1 (1 -q n )
which is closely related to Dedekind's eta function.

A semi-standard tableau is obtained by putting positive integers in the boxes of a partition which are i) weakly increasing from left to right ii) strictly increasing from top to bottom as below.

4 1 1 3 2 2 4 1
The shape of the tableau is the underlying partition λ.

The semi-standard tableaux themselves can be encoded by Gelfand-Tsetlin triangles.

such that X i+1,j X i,j X i+1,j+1 for n -1 i j 1.

Given a semi-standard tableau filled with numbers from 1 to n, one can construct a Gelfand-Tsetlin triangle of size n whose row k, as counted from below, consists of the partition, read backwards, formed by the boxes containing numbers from 1 to k in the semi-standard tableau. In the case of the semi-standard tableau above this gives

0 1 3 4 0 2 4 2 3 3
Let (x i ) i 1 be a family of indeterminates. For a standard tableau t, let t i be the number of i occuring in the tableau and x t = i x ti i . The generating function of semi-standard tableaux with shape λ, filled with numbers from 1 to n, is a Schur function

s λ (x 1 , . . . , x n ) = t tableau of shape λ x t .
These are symmetric functions, which occur as characters of irreducible representations of the group GL n (see e.g. Macdonald [21]).

Plane Partitions.

A plane partition is a stack of cubes in a corner. Putting the stack on a square basis and collecting the heights of the piles of cubes, one gets an array of integers:

5 4 3 2 2 2 1 1 2 2 0 0 1 0 0 0
Splitting the array into its left and right parts yields two Gelfand-Tsetlin triangles sharing the same upper row (which is the vertical diagonal of the square array):

0 0 2 5 0 1 4 0 2 1 0 0 2 5 0 2 3 1 2 2
From this one can infer that the generating series of plane partitions π according to their size (i.e. the number of cubes in the stack) is equal to π q |π| = λ s λ (q, q 2 , . . . , q j , . . .) 2 . Using Cauchy's formula (2.1) λ s λ (x 1 , x 2 , . . . , x j , . . .)s λ (y 1 , y 2 , . . . , y j , . . .) = i,j 1 1 -x i y j one obtains Mac Mahon's formula which gives the generating function for plane partitions according to their size

π q |π| = ∞ n=1 1 (1 -q n ) n .
Choosing a large cube that contains a plane partition, one can also encode it as a lozenge tiling of an hexagon.

The symmetry group of the hexagon is a dihedral group. For each subgroup of this group, one can consider the class of plane partitions which are invariant under these symmetries of the hexagon. Various enumeration formulas have been derived for such symmetry classes. We will be interested in one of them.

2.3. Totally Symmetric Self-Complementary Plane Partitions. A Totally Symmetric Self-Complementary Plane Partition (TSSCPP in short), of size n, is a plane partition, inside a cube of side 2n, such that the lozenge tiling has all the dihedral symmetries of the hexagon, as in the picture below, where n = 3. Remarkably, a plane partition with all these symmetries can be superposed with its complement in the cube.

TSSCPPs can be encoded by non-intersecting paths as below, where the paths go through the yellow and blue tiles of a fundamental domain for the action of the dihedral group:

The paths can be drawn on a lattice using vertical steps to record blue tiles and diagonal steps for yellow tiles:

This correspondence has allowed J. Stembridge [START_REF] Stembridge | Nonintersecting paths, Pfaffians, and plane partitions[END_REF], building upon the Lindström-Gessel-Viennot technique, to express the number of these paths as a Pfaffian

t n = pf (a ij ) n i<j n-1 a ij = 2j-i r=2i-j+1 i + j r , n = 0 if n is even, 1 if it is odd
It is not an easy task however to evaluate this Pfaffian explicitly, but this was done by G.

Andrews [START_REF] Andrews | Plane partitions. V. The TSSCPP conjecture[END_REF], who proved that (2.2)

t n = n-1 j=0 (3j + 1)! (n + j)! t n = 1 2 7 42 429 7436 218348 • • • 2.4. Magog triangles.
Definition 2.2. A Magog triangle of size n is a Gelfand-Tsetlin triangle of positive integers such that X jj j for all 1 j n.

Reading the heights of the cubes of a TSSCPP in a fundamental domain of the dihedral group gives a Magog triangle e.g. for the example above, with the heights starting at 1

1 1 2 1 2 1 1 1 2 1 2 1
This gives a bijection between Magog triangles of size n and TSSCPPs of size n. Thus the rather complicated objects which are TSSCPPs can be encoded by these triangles, satisfying a very simple condition.

Alternating sign matrices

3.1. Jacobi-Desnanot identity and Dodgson algorithm. There are many polynomial identities relating the different minors of a matrix. One of them is the Jacobi-Desnanot identity which we now explain. For a square n × n matrix M let M i1...ir j1...jr be the matrix obtained by deleting rows i 1 , . . . , i r and columns j 1 , . . . , j r . Then one has

det(M ) det(M 1n 1n ) = det(M 1 1 ) det(M n n ) -det(M 1 n ) det(M n 1
). For a 2 × 2 matrix (the empty determinant is 1) this is just

a b c d = ad -bc.
Using this identity Charles Dodgson (better known under the name of Lewis Carroll) devised an algorithm for computing the determinant of a matrix which uses only the computation of 2 × 2 determinants. For example, if you want to compute the determinant of the matrix

A =     1 4 6 0 2 1 -3 1 3 2 1 5 3 2 2 0    
start with two matrices, A and another matrix B, of size (n -1) × (n -1), with all its entries equal to one, then inside A insert a (red) matrix formed with the two by two minors of A divided by the corresponding entries of B; inside B insert the (blue) values of A in the inner columns and rows

          1 4 6 0 -7 -18 6 2 1 -3 1 1 7 -16 3 2 1 5 0 2 -10 3 2 2 0                 1 1 1 1 -3 1 1 1 2 1 1 1 1      
then iterate with the new pair of matrices

A =   -7 -18 6 1 7 -16 0 2 -10   B = 1 -3 2 1 to get       -7 -18 6 -31 -82 1 7 -16 1 -38 0 2 -10         1 -3 7 2 1   finally det(A) = -31 -82 1 -38 7 = 180.
(3.1) det λ (A) = M ∈ASM (d) (1 + λ) s(M ) λ i(M ) ij A Mij ij
The sum is over the set of alternating sign matrices, defined at the beginning of the introduction while i(M ) is the number of inversions of M (to be defined later) and s(M ) is the number of -1 coefficients.

This is an example of the "Laurent phenomenon" which is at the heart of the deep theory of cluster algebras, see e.g. [START_REF] Fomin | The Laurent phenomenon[END_REF].

3.3. Alternating sign matrices. For the convenience of the reader we remind the definition of alternating sign matrices. Definition 3.2. An alternating sign matrix is a square matrix having coefficients in {-1, 0, 1} so that, in each row and in each column, if one forgets the zeros, the 1 and -1 entries alternate and the sum is 1.

Here is an example where we show an alternating sign matrix matrix and the alternance of +1 and -1 in each row and column, once the zeros are removed:

      0 0 0 1 0 0 0 1 -1 1 1 0 -1 1 0 0 1 0 0 0 0 0 1 0 0             1 1 -1 1 1 -1 1 1 1      
In particular, the alternating sign matrices without -1 are exactly the permutation matrices and (3.1) for λ = -1 gives the classical formula for the usual determinant. It turns out that alternating sign matrices occur in a number of different contexts, in statistical physics, representation theory, or combinatorics. We shall give a few examples now.

3.3.1.

The six-vertex model. An entry of an alternating sign matrix can take at most three values {-1, 0, 1}. For each entry with value zero consider the sum of entries lying respectively, on the right and on the left of this entry, then one of these sums is equal to 0 and the other is equal to 1. A similar property holds for the sum of entries lying above and the sum of entries lying below. It follows that one can divide the entries of the matrix into six groups, two corresponding to entries with the value 1 and -1 and four groups corresponding to the configurations of an entry with value 0. There are thus six possible configurations of each entry of an alternating sign matrix, listed below

(3.2) 1 -1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0
The configurations so obtained form an instance of a famous statistical physic model, known as the six-vertex model, which is one of the most studied models in statistical mechanics (see e.g. [START_REF] Baxter | Exactly Solved Models in Statistical Mechanics[END_REF]). In order to study this model it is convenient to weigh the configurations as follows. Introduce indeterminates q, x i and y j , the indices ranging from 1 to n and corresponding to the rows and columns of the matrix. Endow each entry of an alternating sign matrix with a weight w(i, j) (where i, j are the row and column of the entry) given by the following value, according to the configuration of the entry, as in (3.2)

(3.3) x i /y j y j /x i [qx i /y j ] [qx i /y j ] [x i /y j ] [x i /y j ]
The convention used here is that [a] = a-a -1 q-q -1 . One can then put on every alternating sign matrix the product of the weights of its entries. It turns out that the particular form of the weights (3.3) allows one to use the Yang-Baxter equation to compute the partition function of this model, i.e. the sum over all alternating sign matrices of the weights, under the form of a remarkable determinant, the Izergin-Korepin determinant [START_REF] Izergin | Partition function of a six vertex model in a finite volume[END_REF] ASM ij

w(i, j) = i (x i /y i ) i,j [x i /y j ][qx i /y j ] i,j [x i /x j ][y i /y j ] det 1 [x i /y j ][qx i /y j ]
Using appropriate specializations of the variables x i , y j and the parameter q, G. Kuperberg [START_REF] Kuperberg | Another proof of the alternating sign matrix conjecture[END_REF] was able to deduce from this that the number of alternating sign matrices of size n is again, as in (2.2)

(3.4) A n = n-1 j=0 (3j + 1)! (n + j)!
This result had been obtained earlier by D. Zeilberger [START_REF] Zeilberger | Proof of the alternating sign matrix conjecture[END_REF] in an indirect way, by showing that the alternating sign matrices of sign n are equienumerated with TSSCPPs of the same size and using (2.2). Recently a new proof of this result and related enumerations has been given by I. Fischer [START_REF] Fischer | A new proof of the refined alternating sign matrix theorem[END_REF].

3.3.2. Fully packed loops. Another way to encode the six-vertex model is to replace each of the possible six configurations by one of the following

0 ±1 0 0 ±1 0
After fixing boundary conditions, there is a unique way to complete the diagram in a fully packed loop as in the picture below, which corresponds to the matrix (1.1).

0 0 1 0 0 1 0 0 1 0 -1 1 0 0 1 0
Observe that in each configuration the 2n vertices on the boundary are related by noncrossing paths. This observation has lead to the famous Razumov-Stroganov conjecture [START_REF] Razumov | Combinatorial nature of ground state vector of O(1) loop model[END_REF], relating alternating sign matrices and the O(n) model, which has been solved recently [START_REF] Cantini | Proof of the Razumov-Stroganoff conjecture[END_REF].

3.3.3.

Alternating sign matrices, the Bruhat order and Gog triangles. Recall that almost all invertible matrices can be factorized as X = LU into a product of a lower and an upper triangular matrix (the LU-factorization) This can be refined into the Bruhat decomposition, expressing the general linear group as a disjoint union of cells indexed by the symmetric group

GL d = ∪ w∈S d BwB
where B is the Borel subgroup of upper triangular matrices. For example, the matrices X having LU factorization are those such that w 0 X ∈ Bw 0 B where w 0 is the permutation of [1, d] such that w 0 (i) = d+1-i. They form the cell of largest dimension. This decomposition induces an order relation (the Bruhat order) on the symmetric group by declaring for σ, τ ∈ S n :

σ τ iff BσB ⊂ Bτ B
e.g. for S 3 we get the order relation with Hasse diagram

0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0
The Bruhat order on S 3

As we are going to explain, alternating sign matrices can be used to complete this order into a lattice order as in the following diagram

0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 1 -1 0
The lattice of 3 × 3 alternating sign matrices For this we need to introduce a new species of Gelfand-Tsetlin triangles. Definition 3.3. 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.
There is a simple bijection between the sets of Gog triangles and of Alternating sign matrices of the same size, which goes as follows: If (M ij ) 1 i,j n is an ASM of size n, then the matrix Mij = n k=i M kj has exactly i -1 entries 0 and n -i + 1 entries 1 on row i. Let (X ij ) j=1,...,i be the columns (in increasing order) with a 1 entry of M on row n -i + 1. The triangle X = (X ij ) n i j 1 is the Gog triangle corresponding to M .

For example, below are an alternating sign matrix of size 5 and its associated Gog triangle

      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       1 2 3 4 5 1 3 4 5 1 4 5 2 4 3
There is an order relation on Gog triangles obtained by entrywise comparison: for triangles X, Y of the same size, X Y if and only if each entry of X is smaller than the corresponding entry of Y . Clearly the Gog triangles of fixed size form a lattice for this order. It turns out that the restriction of this order relation to Gog triangles corresponding to permutations is exactly the reversed Bruhat order. The set of alternating sign matrices thus appears as the lattice completion of the set of permutations endowed with the Bruhat order, as first proved by Lascoux and Schützenberger [START_REF] Lascoux | Treillis et bases des groupes de Coxeter[END_REF].

The Gog-Magog problem

4.1. The question. Since the sets of Gog and Magog triangles of size n have the same number of elements it is sensible to ask, in view of their very similar definitions, if there exists a natural bijection between these two sets. This problem is at the time of this writing still largely open. Observe that, although in our dicussion we have encountered rather sophisticated mathematical objects, the actual definitions of the Gog and Magog triangles are completely elementary, one needs only to know what are the positive integers and how to compare two positive integers, it is not even necessary to know how to add or multiply them! Also many results have been obtained on the refined enumeration of Gog and Magog triangles according to different statistics and it has been observed that some of these refined enumerations coincide cf [START_REF] Behrend | Multiply-refined enumeration of alternating sign matrices[END_REF]. All these facts point towards the existence of a mathematical structure which would explain all these coincidences by showing that Gog and Magog triangles give two different ways of parametrizing the same mathematical objects, however for the moment the nature of this mathematical structure remains elusive.

Here are the seven Gog and Magog triangles of size 3. Already finding a "natural" bijection between them does not seem so obvious.

1 1 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 1 2 1 2 1 1 1 3 1 2 1 1 2 2 1 2 1 1 2 3 1 2 1
Magog triangles of size 3 Analogously there is a notion of right and left Magog trapezoids. We will use only the right ones, of which below is a (5, 2) example

1 2 3 1 2 1 1 2 3 1 3 1 1 2 3 1 2 2 1 2 3 1 3 2 1 2 3 1 3 3 1 2 3 2 3 2
2 3 1 3 1 2 1 2 1
There is no known simple formula for enumerating Gog or Magog trapezoids of a fixed shape, however the following holds Theorem 4.2 (Zeilberger [START_REF] Zeilberger | Proof of the alternating sign matrix conjecture[END_REF]). For all k n, the (n, k) right Gog and Magog trapezoids are equienumerated.

The proof of Zeilberger uses transformations of generating series for these objects and it does not seem possible to transform it into a bijective proof. Some conjectures on the enumeration of Gog and Magog trapezoids refined by some further statistics have been formulated by Krattenthaler [START_REF] Krattenthaler | A Gog-Magog conjecture[END_REF]. A bijection between permutation matrices and a subset of Magog triangles has been proposed by J. Striker [START_REF] Striker | A direct bijection between permutations and a subclass of totally symmetric self-complementary plane partitions[END_REF]. In the case of (n, 2) right trapezoids a bijective proof incorporating a further statistic has been obtained in [START_REF] Biane | Gog and Magog triangles and the Schützenberger involution[END_REF]. This proof is based on the Schützenberger involution, to be defined below, and uses the inversions of a Gog triangle. Bettinelli [START_REF] Bettinelli | A simple explicit bijection between (n,2)-Gog and Magog trapezoids[END_REF] found another, simpler bijection which however does not seem to preserve any of the statistics considered by Krattenthaler.

4.

3. An approach to the bijection problem. In this section we will describe an approach to the bijection problem which has lead to some recent progress. For this approach we need to introduce some statistics on Gog and Magog triangles.

For a Gog triangle X we define

β Gog (X) = X 1,1
For a Magog triangle of size n we let

β M agog (X) = n i=1 X n,i - n-1 i=1 X n-1,i
Remark that if we identify a Gog triangle with an alternating sign matrix, then the statistics β Gog (X) corresponds to the position of the 1 in the bottom line. Some recent results on the joint enumeration of this and other similar statistics can be found in [START_REF] Ayyer | Romik New enumeration formulas for alternating sign matrices and square ice partition functions[END_REF], [START_REF] Behrend | Multiply-refined enumeration of alternating sign matrices[END_REF]. In particular, it is known that the number of Gog triangles of size n with β Gog (X) = k is equal to the number of Magog triangles of size n with β M agog (X) = k.

• if a < c map a b c to a b a + b -c • if a = c map a b a to a b -1 b -1 .
We leave to the reader the task of verifying that this is a bijection. Observe that it can be obtained in two steps: first we make the transformation

a b c → a b c if a < c a b a → a b -1 a if a = c then a symmetry a b c → a b a + b -c
This idea was generalized in [START_REF] Biane | Gog and Magog triangles and the Schützenberger involution[END_REF]. The first step leads to considering inversions of Gog triangles while the second leads to the Schützenberger involution. We shall explain these two ideas now.

4.3.1.

Inversions. An inversion in a Gog triangle X is a pair (i, j) such that X i,j = X i+1,j .

For example the triangle below has 5 inversions. The Schützenberger involution is a fundamental tool in the theory of Young tableaux, which has a nice geometric interpretation [START_REF] Van Leeuwen | Flag varieties and interpretations of Young tableaux algorithms[END_REF]. Its simplest description uses the RSK transformation, which is a bijection between the set of two-dimensional arrays of nonnegative integers, (M ij ) i,j 1 and pairs (S, T ) of semi-standard Young tableaux of the same shape λ. This bijection allows to give a bijective proof of Cauchy's identity (2.1).

Using the bijection between semi-standard tableaux and Gelfand-Tselin triangles the Schützenberger involution can be transported to Gelfand-Tsetlin triangles. The following description of this involution has been given by Berenstein and Kirillov [START_REF] Berenstein | Groups generated by involutions, Gelfand-Tsetlin patterns and combinatorics of Young tableaux[END_REF]. First define involutions 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 = ( Xi,j ) n i j 1 with Xi,j = X i,j , if i = k Xk,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: on 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 .

Theorem 4.3 (Berenstein and Kirillov [START_REF] Berenstein | Groups generated by involutions, Gelfand-Tsetlin patterns and combinatorics of Young tableaux[END_REF]). The Schützenberger involution, acting on Gelfand-Tsetlin triangles of size n, is given by the formula

S = ω 1 ω 2 . . . ω n-1
Using inversions and the Schützenberger involution a bijection between (n, 2) Gog and Magog trapezoids was given in [START_REF] Biane | Gog and Magog triangles and the Schützenberger involution[END_REF]. Remark 4.5. The name GOGAm is obtained from Magog by reading backwards and changing the case as a reminder of the description of the Schützenberger involution on words (cf [START_REF] Fulton | Young tableaux[END_REF]).

It is shown in [START_REF] Biane | Gog and Magog triangles and the Schützenberger involution[END_REF] that the GOGAm triangles of size n are the Gelfand-Tsetlin triangles X = (X i,j ) n i j 1 such that 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 (4.1)

n-k-1 i=0 X ji+i,ji -X ji+1+i,ji+1 + X j n-k +n-k,j n-k k
The problem of finding an explicit bijection between Gog and Magog triangles can therefore be reduced to that of finding an explicit bijection between Gog and GOGAm triangles. Again one can define right or left GOGAm trapezoids. Conjecture 4.6. For all k n, the (n, k) left Gog and GOGAm trapezoids are equienumerated.

In [START_REF] Biane | Gog and GOGAm pentagons[END_REF] it was shown that the ideas of [START_REF] Biane | Gog and Magog triangles and the Schützenberger involution[END_REF] could be used to provide a simple bijection between (n, 2) Gog and GOGAm left trapezoids. These bijections suggested some further conjectures which we describe in the next section.

Pentagons.

Definition 4.7. For (n, k, l, m), with n k, l, m, an (n, k, l, m) Gog (resp. GOGAm) pentagon is an array of positive integers X = (x i,j ) n i j 1;k j;j+l i+1 formed from the intersection of the k leftmost NW-SE diagonals, the l rightmost SW-NE diagonals and the m bottom lines of a Gog (resp. GOGAm) triangle of size n. This conjecture can even be refined into Conjecture 4.9. For each n, k, l the (n, k) left Gog and GOGAm trapezoids with bottom entry X 1,1 = l are equienumerated. Some numerical evidence for these conjectures has been given in [START_REF] Biane | Gog and GOGAm pentagons[END_REF].

5. On the distribution of inversions and coinversions 5.1. We recall the definition of inversions and introduce the dual notion of coinversion. Definition 5.1. An inversion in a Gog triangle X is a pair (i, j) such that X i,j = X i+1,j .

A coinversion is a pair (i, j) such that X i,j = X i+1,j+1 .

For example, the Gog triangle in (5.1) contains three inversions, (2, 2), (3, 1), (4, 1) and five coinversions, (3, 2), [START_REF] Ayyer | Romik New enumeration formulas for alternating sign matrices and square ice partition functions[END_REF][START_REF] Ayyer | Romik New enumeration formulas for alternating sign matrices and square ice partition functions[END_REF], (4, 2), (4, 3), [START_REF] Baxter | Exactly Solved Models in Statistical Mechanics[END_REF][START_REF] Baxter | Exactly Solved Models in Statistical Mechanics[END_REF]. We denote by µ(X) (resp. ν(X)) the number of inversions (resp. coinversions) of a Gog triangle X. Since a pair (i, j) cannot be an inversion and a coinversion at the same time in a Gog triangle and the top row does not contain any inversion or coinversion, one has ν(X) + µ(X) n(n -1) 2

Actually one can easily see that n(n-1)

2

-ν(X) -µ(X) is the number of -1's in the alternating sign matrix associated to the Gog triangle X. Also inversions and coinversions correspond to different types of vertices in the six vertex model, see e.g. [START_REF] Behrend | On the weighted enumeration of alternating sign matrices and descending plane partitions[END_REF].

Let us denote by Z(n, x, y) the generating function of Gog triangles of size n according to ν and µ.

(5.2)

Z(n, x, y) = X∈Gogn x ν(X) y µ(X) .
where the sum is over the set Gog n of Gog triangles of size n.

The following formula has been proved in [START_REF] Behrend | On the weighted enumeration of alternating sign matrices and descending plane partitions[END_REF], using properties of the six vertex model.

Proposition 5.2.

(5.3)

Z(n, x, y) = det 0≤i,j≤n-1   -y i δ i,j+1 + min(i,j+1) k=0 i -1 i -k j + 1 k x k   .
For example, for Gog triangles of size 3, we have

(5.4) Z(3, x, y) = det   1 1 1 -y + x 2x 3x x -y 2 + 2x + x 2 3x + 3x 2   = x 3 + xy + y 3 + 2x 2 y + 2xy 2 .
which matches part (a) of Table 1.

It is however not so easy to use this formula in order to prove results on the distribution of inversion and coinversions. We remark that the numbers on the antidiagonal are the Mahonian numbers counting permutations according to the number of their inversions.

5.2.

Let us denote by A n,k the set of pairs of nonnegative integers (i, j) such that

i k(k + 1) 2 , j (n -k -1)(n -k) 2 , i + j n(n -1)

and let

A n = ∪ n-1 k=0 A n,k . We will give a simple combinatorial proof of the following.

Theorem 5.3. There exists a Gog triangle of size n, with i inversions and j coinversions, if and only if (i, j) belongs to the set A n . If i = k(k+1) 2 and j = (n-k-1)(n-k) 2 for some k ∈ [0, n-1] then this triangle is unique, furthermore its bottom value is n -k. coinversions. Indeed the triangle is defined by

X ij = j for j i -n + k (5.5) X ij = n + j -i for j k + 1 (5.6) X ij = n -k + 2j -i -1 for i -n + k + 1 j k (5.7)
The bottom entry of this triangle is n -k, as expected.

We give an example below: for n = 6 and k = 3, the triangle has 6 inversions and 3 coinversions: Observe that the entries which are neither inversions nor coinversions form a rectangle of size k × (n -k -1) at the bottom of the triangle.

The ASM corresponding to such a triangle has a diamond shape:

        0 0 0 1 0 0 0 0 1 -1 1 0 0 1 -1 1 -1 1 1 -1 1 -1 1 0 0 1 -1 1 0 0 0 0 1 0 0 0        
Starting from this triangle, it is not difficult, for a pair of integers (l, m) such that l

k(k+1) 2 , m (n-k-1)(n-k) 2
, and l + m

n(n-1) 2
, to construct (at least) one triangle with l inversions and m coinversions, for example one can add inversions by decreasing some entries, starting from the westmost corner of the rectangle, and add coinversions by increasing entries, starting from the eastmost corner. Here is an example with n = 6, l = 9, m = 5, details of the general case are left to the reader.

Standardization of Gog triangles.

In order to prove the only if part of the Theorem, as well as the uniqueness statement, we now introduce two standardization operations. These operations build a Gog triangle of size n -1 from a Gog triangle of size n.

Left standardization.

Let X be a Gog triangle of size n then its (n -1) th row (counted from bottom to top) has the form 1, 2, . . . , k, k + 2, . . . , n for some k ∈ [1, n]. For j k, let m j be the smallest integer such that X n,j = X mj ,j = j.

The left standardization of X is the triangle LX of size n -1 obtained as follows:

LX i,j = X i,j = j for j k and n -1 i m j . (5.8) LX i,j = X i,j -1 for other values of i, j.

(5.9) 5.3.4. Right standardization. Let X be a Gog triangle of size n with (n -1) th row of the form 1, 2, . . . , k, k + 2, . . . , n, and for j k + 1 let p j 1 be the largest integer such that X n,j = X n-pj ,j+1-pj = j + 1.

The right standardization of X is the triangle RX of size n -1 obtained as follows:

RX n-l,j+1-l = X n-l,j+1-l -1 = j for j k + 1 and 1 l p j . (5.10) RX i,j = X i,j for other values of i,j. (5.11) Below are a Gog triangle of size 6, together with its left and right standardizations: Then LX is a Gog triangle of size n -1 with at most m -n + k + 1 coinversions and at most l inversions.

Similarly, RX is a Gog triangle of size n -1 with at most l -k inversions and at most m coinversions.

Proof. We prove the proposition only for the left standardization. The case of right standardization can be proven in an analogous way, or by noticing that the mapping X → (n + 1 -X i,i+1-j ) i,j is an involution, which exchanges inversions and coinversions.

Observe that there are exactly k inversions and n -k -1 coinversions on row n -1 of X. It follows that X has l -k inversions and m -n + k + 1 coinversions on rows 1, . . . , n -2.

We first prove that LX is a Gog triangle. For any i, j we have to prove that LX i,j LX i-1,j-1 , LX i,j LX i+1,j , LX i,j > LX i,j-1 .

Since X is a Gog triangle one has X i,j X i-1,j-1 , therefore the first inequality may fail only if LX i,j = X i,j -1 and LX i-1,j-1 = X i-1,j-1 . If this is the case then X i,j > j and 1 In the first version of this paper the statement of this proposition was incorrect. I would like to thank the referees for pointing out the mistake.

X i-1,j-1 = j -1, therefore LX i,j > LX i-1,j-1 . This shows also that LX cannot have more coinversions than X on its first n -2 rows, therefore the number of coinversions of LX is at most m -n + k + 1. A similar reasoning yields the other two inequalities, moreover the number of inversions of LX can increase at most by k with respect to that of X in its first n -2 rows, more precisely by at most one in each of the k leftmost NW-SE diagonals. It follows that LX has at most l inversions. 5.3.6. We can now finish the proof of Theorem 5.3 by induction on n. For n = 3 or 4, the claim follows by inspection of Table 1. Let X be a Gog triangle of size n, with l inversions and m coinversions. We have to prove that (l, m) belongs to some A n,r . We have seen that LX is a Gog triangle of size n -1 with at most m -n + k + 1 coinversions and at most l inversions, whereas RX is a Gog triangle of size n -1 with at most l -k inversions at most m coinversions. By induction hypothesis there exists some p such that (5.12) l p(p + 1) 2 , m -n + k + 1 (n -p -2)(n -p -1) 2 and there exists q such that (5.13) l -k q(q + 1) 2 , m (n -q -2)(n -q -1) 2 .

If p > q, then (5.12) implies l (q+1)(q+2) 2

and since m (n-q-2)(n-q-1) 2 by (5.13) one has (l, m) ∈ A n,q+1 .

Similarly if q > p then (5.13) implies l (p+1)(p+2) 2

3. 2 .

 2 The λ-determinant. In 1983 David Robbins had the idea of replacing, in the above algorithm, every occurrence of a b c d = ad -bc by a b c d λ = ad + λbc, for some indeterminate λ. This defines the λ-determinant. The result is surprising, indeed although the algorithm implies taking a lot of quotients of rational fractions the result is always a Laurent polynomial in the coefficients of the matrix, namely one has, for a d × d matrix A, Theorem 3.1. (D. Robbins, H. Rumsey [25])

2 .

 2 Gog and Magog trapezoids. Definition 4.1. An (n, k) right (resp. left) Gog trapezoid (for k n) is an array of positive integers formed from the k rightmost SW-NE diagonals (resp. leftmost NW-SE diagonals) of some Gog triangle of size n. Below are two (5, 2) Gog trapezoids.

1 .

 1 Consider now the bottom triangle a b c made of the two lowest rows of some Gog triangle of size n 2. Thus a, b, c are integers satisfying the inequalities 1 a c b n; a < b. Consider now a triangle a b c extracted from the two rightmost NW-SE diagonals of Magog triangle of size n, such as this one: It is now easy to find a bijection between these two sets of triangles, mapping the statistics β Gog to β M agog i.e. c to a + b -c , as follows: start from a triangle extracted from a Gog triangle a b c with 1 a c b n; a < b and then

2 .

 2 Schützenberger involution.

4. 3 . 3 .

 33 GOGAm triangles and trapezoids. Definition 4.4. A GOGAm triangle of size n is a Gelfand-Tsetlin triangle which is the image by the Schützenberger involution of a Magog triangle (of size n).

Conjecture 4 . 8 .

 48 pentagon Remark that if m k + l -1 then the pentagon is a rectangle, whereas if m k, l then it is a Gelfand-Tsetlin triangle of size m. For any n, k, l, m the (n, k, l, m) Gog and GOGAm pentagons are equienumerated.

Remark 5 . 4 . 2 . 5 . 3 .

 54253 Note, for future reference, that if (l, m) belongs to the set A n and if l < p(p+1) 2 then m (n-p)(n-p+1) Proof of Theorem 5.3.5.3.1.Existence. First we show that there exists a triangle of size n with k(k+1)2 inversions and(n-k-1)(n-k) 2

1

 1 Let X be a Gog triangle of size n, with l inversions and m coinversions with (n -1) th row 1, 2, 3, . . . , k, k + 2, . . . n.

Table 1 .

 1 Table 1 below shows the joint distribution ofµ and ν, for n = 3 and n = 4. The number of Gog triangles of size 3 (a) and 4 (b) with k inversions (horizontal values) and l coinversions (vertical values).

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

Definition 2.1. A Gelfand-Tsetlin triangle of size n is a triangular array X = (X i,j ) n i j 1 of nonnegative integersX 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