Séminaire Lotharingien de Combinatoire 56 (2007), Article B56e

REFINED COUNTING OF FULLY PACKED LOOP CONFIGURATIONS

Johan Thapper

Department of Mathematics, Linköpings universitet S-581 83 Linköping, Sweden

Abstract. We give a generalisation of a conjecture by Propp on a summation formula for fully packed loop configurations. The original conjecture states that the number of configurations in which each external edge is connected to its neighbour is equal to the total number of configurations of size one less. This conjecture was later generalised by Zuber to include more types of configurations. Our conjecture further refines the counting and provides a general framework for some other summation formulas observed by Zuber. It also implies similar summation formulas for half-turn symmetric configurations.

1. Introduction

An alternating sign matrix of size n is an n × n matrix with entries in {−1, 0, 1} where in each row and column, the −1 and 1 alternate and such that all rows and columns sum to 1. Let the number of such matrices be A_{n}. Then,

A_{n} = ∏_{k=0}^{n−1} \frac{(3k + 1)!}{(n + k)!},  (1)

which was conjectured by Mills, Robbins and Rumsey [15] and finally settled by Zeilberger [24]. The fascinating story behind this result is found in Bressoud’s book, Proofs and Confirmations [2].

Shortly after Zeilberger’s proof, Kuperberg [13] presented a very different one. This proof made connections to the six-vertex model. Here lies the connection between alternating sign matrices and fully packed loop configurations. The latter are also in bijection with configurations in the six-vertex model. In the fully packed loop model one can find a natural refinement of these numbers, which is non-obvious in the alternating sign matrix case. See Sections 2 and 2.1 for the definitions of the fully packed loop model and the refined numbers, A_{n}(π).

In two papers, [19] and [22], Razumov and Stroganov made some interesting remarks on the ground state vector of finite XXZ spin chains. They conjectured that, if scaled so that the smallest entry was equal to 1, the entire vector was integral and summed to the number of alternating sign matrices. Batchelor, de Gier and Nienhuis [1] expanded on this and stated the conjecture in the setting of the O(1) loop model with both periodic and open boundaries. Following this line, Razumov and Stroganov [20] found numerical evidence for an element by element correspondence between the ground state vector of the periodic O(1) loop model and refined numbers of fully packed loop configurations.

The author was supported by the Programme for Interdisciplinary Mathematics, Department of Mathematics, Linköpings universitet and partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe”.

The Razumov–Stroganov conjecture for the sum of the entries of the ground state vector of the O(1) loop model with periodic boundary boundaries was proven in [8]. An alternative proof, due to Pasquier, can be found in [17]. Similar sum rules for different models and boundary conditions can be found in [7, 25, 6, 11]. For the refined conjecture, on the individual ground state entries, Zinn-Justin has given a proof for some infinite families in [26].

These remarkable observations sparked an interest for these numbers and led to many conjectures on the entries of the ground state vectors and, via the Razumov– Stroganov conjecture, also on particular families of the refined fully packed loop numbers. In several subsequent papers, many of these conjectures were proven (on the level of fully packed loop numbers) by different constellations of authors [3, 4, 9, 10, 12].

An older conjecture due to Propp, also dealing with refined fully packed loop numbers, states that the number of configurations in which each external edge is connected to its neighbour is equal to the total number of configurations of size one less. This was generalised by Zuber in [27] and in the same paper, Zuber conjectured additional summation formulas for which he could find no apparent pattern.

In this paper we use methods which were developed following the Razumov– Stroganov conjecture to derive conjectures for some more refined summation formulas which also, implicitly, provide the systematics behind some of the sums observed by Zuber.

Section 2 deals with the definition of the fully packed loop model. In Section 2.1 we look at how to do a refined counting according to the matching pattern of the configurations. The method we will use to do this counting is based on work by de Gier [5] and is described in Section 2.2. In Section 3 we then develop our main conjecture, Conjecture 3.5. This is done through Sections 3.1, 3.2 and 3.3. After this, we briefly sidestep to present a conjecture on a related set of matrices which could point in a direction to prove the main conjecture. In Section 3.5 the aforementioned conjectures by Propp and Zuber are derived, in greater generality, from Conjecture 3.5. We conclude the paper in Section 4 with some open problems related to this conjecture.

2. Fully packed loop configurations

Let Q_{n} be the square grid of n times n vertices in the plane, see Figure 1(a). On this vertex set we take the graph in Figure 1(b). It has edges between horizontally and vertically adjacent vertices as well as 4n external edges which are incident to only one vertex on the boundary of Q_{n}.

A configuration in the fully packed loop model, an FPL configuration for short, is a subset of this graph such that each vertex has degree 2. In addition to this condition one assumes some boundary conditions for the external edges.

In combinatorial literature these are usually the domain wall boundary conditions which are equivalent to including precisely every second external edge in the configuration. We will always assume these boundary conditions.

An example of an FPL configuration with domain wall boundary conditions is given in Figure 1(c). The reader should for now ignore the numbering of the external edges. The connected components of a configuration are called loops,

(a)  (b)  (c)  15 14 13 12 11 10 6 7 8 9 5 4 3 2 1 20 19 18 17 16

Figure 1. (a) Q_{10}, (b) potential edges, (c) an FPL configuration

even though they are not always cycles in the graph, as can be seen in the example.

The FPL configurations on Q_{n} are, as mentioned in the introduction, equinumerous to the alternating sign matrices of size n × n, see for example [23]. Other enumerative problems arise if we impose various symmetries on the FPL configurations, or equivalently, on the alternating sign matrices. For example, we can choose to count only those configurations which are left unchanged by a reflection in the horizontal and/or the vertical axis. Such configurations are called horizontally (and/or vertically) symmetric FPL configurations. Another possibility is to count those that are invariant under a 180 degrees rotation of the graph. These are called half-turn symmetric FPL configurations, or HTFPL configurations for short, and they are of particular interest to us as it turns out that, for our purposes, they can be treated in much the same way as the non-restricted ones.

The total number of configurations being half-turn symmetric is

A_{2n}^{HT} = ∏_{j=0}^{n−1} \frac{3j + 2}{3j + 1}A_{n}^{2}  (2)

A_{2n+1}^{HT} = \frac{n!(3n)!}{(2n)!^{2}}A_{2n}^{HT}  (3)

The even case was proven by Kuperberg in [14] while the odd case was proven by Razumov and Stroganov in [18].

2.1. Refined enumeration. We will now label the external edges with integers from 1 to 2n starting at the top, on the left boundary, and proceeding counterclockwise around the square, see Figure 1(c). Then, every FPL configuration induces, in the natural way, a matching on [2n]. In fact, it induces a perfect, non-crossing matching, i.e, a perfect matching such that if a is matched to c and b is matched to d with a < c, b < d and a < b, then either a < c < b < d or a < b < d < c. This is equivalent to saying that we can represent the matching as in Figure 2 with non-crossing arches.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Figure 2. The matching associated to the configuration in Figure 1(c).

Let ∏_{2n} be the set of all such matching. We call π ∈ ∏_{2n} the matching associated to an FPL configuration if this configuration induces π.

This suggests that we may do a refined counting on the FPL configurations. Let A_{n}(π) be the number of FPL configurations of size n×n with associated matching π. Wieland showed in [23] that A_{n}(π) is invariant under the action of the dihedral group. That is, it does not matter where we start the labelling of the external edges, and furthermore, it does not matter in which direction we proceed around the square.

Formally, the theorem is stated as follows.

Theorem 2.1 (Wieland 2000). Let d ∈ D_{2n} be an element of the dihedral group of order 2n. Then,

A_{n}(π) = A_{n}(dπ)

Theorem 2.1 shows that we may forget the exact labels and represent the matchings as chord diagrams, see Figure 3.

Figure 3. A chord diagram of the matching in Figure 2.

Now, let A_{n}^{HT} (π) be the number of half-turn symmetric FPL configurations with associated matching π. We show that, with minor additions, Wieland’s proof of Theorem 2.1 goes through also for HTFPL configurations.

Corollary 2.2. For d ∈ D_{2n},

A_{n}^{HT} (π) = A_{n}^{HT} (dπ).

Proof. We refer to Wieland’s original paper [23] for details of the proof and present only an outline, with the appropriate modifications.

A square consists of the 4 edges or non-edges between the 4 vertices with coordinates (i, j), (i + 1, j), (i, j + 1) and (i + 1, j + 1) in a configuration. For each square S, we define a function G_{S} on the set of FPL configurations as follows. If S is not on the boundary and the edges and non-edges in S alternate, then G_{S} flips the edges of S, otherwise it leaves them unchanged. G_{S} is local in the sense that everything which is not a part of S is left unchanged.

Let G_{0} be the composition of all G_{S} where S is an even square (i + j ≡_{2} 0) and G_{1} be the composition of all G_{S} where S is an odd square. Note that the G_{S} commute (for even or odd squares) and therefore the order of the composition is irrelevant. Wieland proves that the associated matching of the composition G := G_{0} ∘ G_{1} is a single-step rotation of the original matching.

We need to show that for half-turn symmetric configurations, the image of G is again half-turn symmetric. Let r be the rotation of a configuration by 180 degrees. It sends even (odd) squares to even (odd) squares, so r ∘ G_{k} = G_{k} ∘ r for k = 0, 1 which implies r ∘ G = G ∘ r. Thus, for a half-turn symmetric configuration C,

r(G(C)) = G(r(C)) = G(C)

which proves that G(C) is indeed half-turn symmetric.

For the reflection part, let R be the function that takes the complement of the configuration with respect to the graph in Figure 1(b). Introduce H_{k} = G_{k} ∘ R. Now, R is an involution and it’s easy to see that R commutes with G_{k} and therefore that H_{0} ∘ H_{1} = G_{0} ∘ G_{1} = G. Let d be the function that reflects the configuration in the line y = x. This does not preserve the external edges, but H_{k} ∘ d does, for k = 0, 1. Since d preserves the even and odd squares, it commutes with H_{k} so H_{k} ∘ d are involutions. Now, {H_{k} ∘ d} generates D_{2n} and again, since the half-turn rotation r commutes with these two reflections we have, for a half-turn symmetric configuration C,

r((H_{k} ∘ d)(C)) = (H_{k} ∘ d)(r(C)) = (H_{k} ∘ d)(C)

which finishes the proof. □

Note. The corresponding statement for vertically or horizontally symmetric FPL configurations is false. The part of the proof that fails is that when n is odd the vertical and horizontal reflections send squares to squares of opposite parity.

In what follows, when we talk about matchings which describe the connectivities of the external edges of FPL configurations, we will leave out perfect, non-crossing and simply write matching.

We will find it convenient to present matchings using a parenthesis notation. This is done in the obvious way in which every matching is represented by a wellformed string of ( and ). In addition, we will use the following short notation from [16] for certain constructions.

• For a matching π, let (π)_{m} be the matching which has {m + 1, …, m + n} matched as [n] in π and in addition i matched to n+2m+1−i for i ∈ [m], that is (π)_{m} = ((⋯ (π)) ⋯).

• Let ()^{n} denote the matching in which i is matched to i + 1 for odd values of i in [2n], that is ()^{n} = ()() ⋯ ().

Example 2.1.

(()^{2})_{3} = (((()()))).

2.2. A method for determining A_{n}(π). As a consequence of the growing interest in the ground state vector of the O(1) loop model many conjectures were made on the values of its entries and also, explicitly or implicitly via the Razumov– Stroganov conjecture on the numbers A_{n}(π), see for example [16, 27]. In [5], de Gier provided a simple, but fruitful method for determining these numbers. In this section we will present the tools involved in de Gier’s method.

We start by introducing the notion of fixed edges. These are edges that, given a matching π and a placement of π on the external edges, have to be present in every FPL configuration with associated matching π and the particular placement chosen. For some classes of matchings and well-chosen placements of these the problem then reduces, via a simple and nice bijection (see Proposition 2.5), to that of calculating the number of rhombus tilings of a π-dependant triangulated region. The problem of determining the number of rhombus tilings of different regions is well-studied. In many cases this yields determinantal formulas with known closed forms.

The basis for finding fixed edges is the following lemma due to de Gier [5].

Lemma 2.3. If an FPL configuration contains the edges a, b and c on the lefthand side of Figure 4, where a and c belong to different loops and furthermore if either of the following holds,

(1) b belongs to a third loop.

(2) b belongs to the same loop as a (c) and b is connected to a (c) by a vertical

edge. then the implication in Figure 4 holds. That is, d must also be included in the configuration.

⇒^{c}^{a}^{b}  ^{a}^{b} ^{c} ^{d}

Figure 4. Implication for fixed edges.

If a and c are external edges, b is not in the configuration, but the condition that a and c belong to different loops still forces d to be included in the configuration.

Proof. In the first case, the loop on which b lies has to pass between a and c. For the second case, the following figure shows that d must be in the configuration since the two connected components do not lie on the same loop.

a b c  c b a

When a and c are external edges, then either d is in the configuration or a and c are connected by two vertical edges. The latter is impossible due to the condition on a and c. □

By repeatedly applying Lemma 2.3 we get the following corollary which can be used to identify large regions of fixed edges.

Corollary 2.4. Assume that we have a sequence of consecutive external edges {e_{1}, e_{2}, …, e_{k}} where e_{1} lies on the lower boundary and e_{2} is next to e_{1} following the boundary in counter-clockwise order. Assume further that no pair of adjacent edges e_{i}, e_{i+1} are matched. Depending on k and on the position of e_{1} we will have one of the cases in Figure 5.

e_{1} e_{2} ⋯ e_{k}

e_{1} e_{2} ⋯  e_{k}

e_{1} e_{2}e_{k}⋯

Figure 5. Fixed edges in Corollary 2.4

Note. There can never be an unbroken sequence of more than n external edges without two adjacent ones being matched. Thus k ≤ n in Corollary 2.4.

Now assume that we have determined some fixed edges for a particular matching π and a given placement. Call this graph of edges G_{π}, the fixed edge graph. If in G_{π}, every vertex v is incident to at least one edge, then we can enumerate the number of configurations by passing to a rhombus tiling enumeration problem.

Call a vertex fixed if it is incident to two fixed edges. Now create a triangulated region, in a sense dual to G_{π}, called P (G_{π}) in the following way. For every nonfixed vertex in G_{π}, there is a triangle in P (G_{π}). This triangle consists of three edges, corresponding to the non-edges of G_{π}. Edges in P (G_{π}) which corresponds to the same non-edges of G_{π} are identified. Because of the special structure of G_{π}, determined by Lemma 2.3, P (G_{π}) can be drawn on top of G_{π} so that the vertices of P (G_{π}) are placed on edges of G_{π} and the edges of P (G_{π}) cross their corresponding non-edge. See Figure 6 for an example of a fixed edge graph and its corresponding triangulated region.

\begin{aligned}& (b) \\ (a) \end{aligned}

Figure 6. (a) G_{π} with π from Figure 2. (b) P (G_{π}).

We will now make the connection to rhombus tilings, which are defined as follows.

Definition 2.1. A rhombus tiling of a triangulated region P is a perfect matching of the triangles in P such that two matched triangles share a common edge.

The following proposition can be seen as the formal statement of de Gier’s method.

Proposition 2.5. Let G_{π} be a fixed edge graph corresponding to a matching π and a given placement such that all vertices in G_{π} are incident to at least one fixed edge.

Then, the number of completions of G_{π} to an FPL configuration equals the number of rhombus tilings of the region P (G_{π}).

Proof. This is a simple observation. Choosing an edge between two vertices corresponds to choosing the rhombus consisting of those two triangles and each vertex (triangle) must be connected to exactly one other vertex (triangle). □

Thus, in order to determine A_{n}(π), one can use the methods developed for enumerating such rhombus tilings, most notably the enumeration of non-crossing lattice paths.

Note. Although each FPL configuration with associated matching π necessarily includes every edge of G_{π}, in general not all completions of G_{π} yield an FPL configuration with associated matching π. There may be some overcounting involved which must be taken into account.

3. Sums of FPL configurations

In this section we will generalise and study a conjecture which can be traced back, via Wieland’s paper [23], to Jim Propp. For future convenience, let

0_{n} = ()_{n} 1^{n} = ()^{n}.

That is, 0_{n} is the pattern with n arches nested on top of each other and 1^{n} is the pattern with n small arches next to each other. The notation is explained by the fact that we will later partially order the matchings, with 0_{n} and 1^{n} being the bottom and top elements, respectively, of that partial order.

The conjecture is stated as follows.

Conjecture 3.1. For n > 1

A_{n}(1^{n}) = ∑ ; π∈∏_{2(n−1)} A_{n−1}(π).

In words, the number of FPL configurations where each external edge is matched to its neighbour is equal to the total number of FPL configurations of size one less.

In [27, Conjecture 8], Zuber conjectures the same to be true for some more general cases where a fixed number of arches are nested around each pattern involved in Conjecture 3.1.

Conjecture 3.2 (Zuber 2003). For n > 1 and m ≥ 1

A_{m+n}((1^{n})_{m}) = ∑ ; π∈∏_{2n} A_{m+n−1}((π)_{m−1}).

Furthermore, he conjectured some additional summation formulas involving FPL configuration numbers, some of which turn out to be consequences of our generalisation (Conjecture 3.5). Note that Conjecture 3.1 follows from Conjecture 3.2 with m = 1 since 1^{n} is obtained from (1^{n−1}) by a single rotation.

Let π ∈ ∏_{2n} and m ≥ 3n. We apply the method described in Section 2.2 to the matching (π)_{m}. Again, according to Theorem 2.1 we may choose a placement for the matching on the external edges. Here we do so by placing the part of the matching which corresponds to π on the lower boundary. Assuming we orient the matching counter-clockwise, the remaining choice to make is from which external edge on the lower boundary we will place π. Let k denote this position, with k = 1 meaning π starts on the first external edge from the left. Since π is arbitrary, we can in general not expect to have all vertices of G_{π} fixed. Therefore we disregard everything that may be fixed by π and look only at those edges which are fixed by the part of the matching that corresponds to the m nested arches around π. This fixed edge graph is shown in Figure 7.

To enumerate the configurations on this fixed edge graph we now divide the non-fixed vertices into three regions. Let T_{n} denote the triangular shaped region in the middle, shown in Figure 8.

\overbrace{π}

Figure 7. The fixed edge graph when n = 3, m = 17 and k = 1.

On the left and the right side of T_{n} there are 2n−2 possible positions for vertical edges. Let E = {e_{1}, e_{2}, …, e_{2n−2}} be the set of these edges on the left-hand side and E′ = {e′_{1}, e′_{2} …, e′_{2n−2}} be the set of edges on the right-hand side as indicated in Figure 8.

e_{1}e_{2}e_{3}e_{4}  e′_{4}e′_{3}e′_{2}e′_{1}

Figure 8. The triangular region T_{3}. The potential vertical edges are dotted.

For convenience we will identify a subset of E (or E′) with a subset of [2n−2] = {1, 2, …, 2n − 2} in the obvious way. We choose two subsets σ, τ ⊆ [2n − 2] where σ is the edges chosen on the left-hand side and τ the edges chosen on the righthand side. This separates the problem of enumerating configurations on T_{n} from the problem of enumerating the configurations on the two non-fixed regions to the left and to the right of T_{n}.

3.1. Patterns. The edge sets σ and τ of T_{n} are not arbitrary. Given a matching π there are only certain possible σ and τ that can occur in an FPL configuration. Let E ⊆ 2^{E} be the set of edge sets that occur in at least one configuration. We will now look at some bijections between E and other combinatorial objects. First, we observe that in any FPL configuration,

|σ| = |τ| = n − 1.

To see this, remember that there are m nested arches around π. In Figure 7, we see that m − n + 1 of the loops corresponding to these arches will pass above T_{n}. The remaining n − 1 passes through T_{n}. Since n − 1 loops pass through the left boundary of T_{n} side we must have precisely 2n − 2 − (n − 1) edges from E in the configuration. The same argument applies to the right boundary and E′. Therefore the cardinalities of σ and τ are as stated.

A Dyck path of length 2n is a path made up of north-east (NE) and south-east (SE) steps, starting from (0, 0) and ending on (2n, 0) without ever going below the line y = 0. It is well-known that the number of such paths equals C_{n}, the Catalan number.

Lemma 3.1. There is a bijection Δ : E → {Dyck paths of length 2n}.

Proof. The path Δ(σ) is constructed from σ as follows. First, there is an NE step. Then, the i:th step is an NE step if 2n−1−i ∉ σ and an SE step otherwise. After the 2n − 2:nd and last step, there is an SE step. This is obviously a path in the integer lattice which ends on (2n, 0) (since |σ| = n − 1). Caselli, Krattenthaler, Lass and Nadeau [4] shows that unless Δ(σ) is a Dyck path, there are no possible ways to complete the FPL configuration. See Lemma 3.6(a) for this result. □

A Ferrers diagram is a graphical representation of a partition. Given a partition λ = (λ_{1}, λ_{2}, …, λ_{p}), such that λ_{i} ∈ ℤ^{+} and λ_{1} ≥ λ_{2} ≥ … ≥ λ_{p}, the Ferrers diagram is constructed by drawing λ_{i} boxes in the i:th row, keeping all rows left justified. The lower part of Figure 9 shows an example.

Lemma 3.2. There is a bijection λ between E and Ferrers diagrams which fit inside the diagram (n − 1, n − 2, …, 1).

Proof. Take the path Δ(σ) and rotate it 45 degrees counter-clockwise. Align the left border of (n−1, n−2, …, 1) with the first NE step and the upper border with the last SE step. Removing the first and the last step of the path and interpreting the remaining path as the contour of a diagram λ(σ) yields the bijection. □

Finally, from Dyck paths there is an obvious bijection to (non-crossing) perfect matchings. An NE step corresponds to an opening, left, parenthesis and an SE step corresponds to a closing parenthesis. Figure 9 shows an example of the presented bijections.

Using these bijections, we may interchangeably use edge sets, Dyck paths, Ferrers diagrams or matchings when we describe the configurations on the sides of T_{n}. We will use the common term pattern for all of these. Since there is also a matching associated with the lower side of T_{n}, we may think of the triangle as labelled by three patterns.

For Ferrers diagrams, we have a natural partial order, namely inclusion of diagrams. This extends to the other objects as well. Specifically, for Dyck paths, the partial order becomes that of one path being weakly below another.

3.2. Rhombus tilings. Given σ and τ we will now look at the remaining two regions of non-fixed vertices on each side T_{n}. In these regions, each vertex is incident to at least one fixed edge. The counting of these configurations can therefore be turned into a rhombus tiling enumeration problem. The two triangulated regions are shown in Figure 10. The shaded triangles belong to the left (or right) region if and only if the corresponding vertical edge is not in σ (or τ).

e_{2}e_{3} e_{5} e_{7}  ()(()()()) λ(σ) = (3, 2, 1, 1)  Δ λ^{σ = {2, 3, 5, 7}}  (2n, 0) (0, 0)

Figure 9. The images of {2, 3, 5, 7} ∈ E under the presented bijections.

m − 3n − 2k + 4 n − 1 n − 1 2k − 1 n − 1 n − 1

Figure 10. R(λ(σ), n − 1, 2k − 1) and R(λ(τ), n − 1, m − 3n − 2k + 4)

The enumeration of rhombus tilings of such pentagonal regions has been carried out by Caselli, Krattenthaler, Lass and Nadeau in [4]. Following their notation, we will call the left region R(λ(σ), n − 1, 2k − 1) and the right region R(λ(τ), n − 1, m − 3n − 2k + 4).

A semi-standard Young tableau (SSYT for short) is a Ferrers diagram in which each box is labelled with an integer so that the rows of the diagram are weakly increasing and the columns are strictly increasing. Let λ be a SSYT and (i, j) ∈ λ be a box at position (i, j). Let SSY T (λ, N) denote the number of SSYT with entries in [N]. Let λ′ denote the transpose of λ. The hook length, h_{i,j}^{λ}, is defined to be λ_{i} + λ′_{j} − i − j + 1.

Caselli, Krattenthaler, Lass and Nadeau prove the following theorem.

Theorem 3.3. The number of rhombus tilings of the region R(λ, d, h) is given by SSY T (λ, d + h) where

SSY T (λ, N) = ∏_{(i,j)∈λ} \frac{j − i + N}{h_{i,j}^{λ}} .

To see that there is no overcounting involved in these regions, consider Figure 11 which corresponds to the right triangulated region. It is clear that the pattern of fixed edges forces 1′, 2′ and 3′ to be connected to vertices from the set {1, …, 15} and i′ to be connected to vertices from the set {i − 2, …, 15} for i > 3. Since two loops can’t cross and all vertices must be fixed we conclude that any completion of Figure 11 must connect 1 to 1′, …, 11 to 11′ and the two free vertices of {12, 13, 14, 15} (after fixing τ) to 12′ and 13′ respectively.

3’ 4’ 5’ 6’ 7’ 8’ 9’ 10’ 11’ 12’ 13’  1’ 2’ 1 2 3 4 5 6 7 8 9 10 11 12131415

Figure 11. A part of the fixed edge graph of Figure 7.

Let a(σ, π, τ) be the number of configurations of the triangle T_{n} such that the vertical edges on the sides are σ and τ and the matching on the external edges in the triangle is π. After separating the problem into T_{n} and the triangulated regions in Figure 10, using Theorem 3.3, we can express total number of configurations as

A_{n+m}((π)_{m}) =

∑ ; σ,τ∈∏_{2n} SSY T (λ(σ), n + 2k − 2)a(σ, π, τ)SSY T (λ(τ), m − 2n − 2k + 3). (4)

Here we have taken the liberty of summing over σ, τ ∈ ∏_{2n} since a(σ, π, τ) = 0 unless the edge sets σ and τ both correspond to matchings.

Thus, what remains to study in expression (4) are the numbers a(σ, π, τ). We will see that Conjecture 3.1 generalises to the triangular domain T_{n} and that in this setting we get more general conjectures of the type observed by Zuber in [27]. This will include a conjecture for the case of HTFPL configurations.

The condition m ≥ 3n may look like a restriction, but the next two results, conjectured by Zuber in [27], and partially proven by Caselli, Krattenthaler, Lass and Nadeau in [4] indicates that this is likely to be an artificial restriction. Let λ = λ(π), λ′ = λ(π′) and let |λ(π)| denote the number of boxes in the Ferrers diagram associated to the matching π. Let dim λ denote the dimension of the representation of the symmetric group S_{|λ|} labelled by λ.

Theorem 3.4 (Caselli, Krattenthaler, Lass and Nadeau). For m ≥ 0,

A_{n+m}((π)_{m}) = \frac{1}{|λ|!}P_{λ}(m)

where P_{λ}(m) is a polynomial of degree |λ| with coefficients in ℤ and its highest degree coefficient is equal to dim λ.

Thus, if we know an expression, polynomial in m, for A_{n+m}((π)_{m}), m ≥ 3n, then we can draw the conclusion that this expression holds for all m ≥ 0.

The second theorem concerns the situation when the pattern is composed of two patterns, π ∈ ∏_{2n} and π′ ∈ ∏_{2n′} separated by m arches. In this case, however, the restriction to large m has not yet been successfully removed.

Theorem 3.5 (Caselli, Krattenthaler, Lass and Nadeau). For m ≥ 3n − n′,

A_{n+n′+m}((π)_{m}π′) = \frac{1}{|λ|!} \frac{1}{|λ′|!}P_{λ,λ′}(m)

where P_{λ,λ′}(m) is a polynomial of degree |λ| + |λ′| with coefficients in ℤ and its highest degree coefficient is equal to dim λ dim λ′

Conjecture 3.3. Theorem 3.5 is true for all m ≥ 0.

Note. Both Theorem 3.4 and Theorem 3.5 are given here in the form conjectured in [27]. They were proven in a more explicit form, similar to our sum in (4). Conjecture 3.3 was a part of Zuber’s original conjecture and is still open.

The following lemma was referred to when we were proving the bijection from E to Dyck paths. It was also proven in [4, Lemma 4.1].

Lemma 3.6 (Caselli, Krattenthaler, Lass and Nadeau). Let π, τ ∈ ∏_{2n}. (a) If λ(τ) ⊈ λ(π), then a(σ, π, τ) = 0 for all σ ∈ ∏_{2n}.

(b) a(0_{n}, π, π) = 1 and a(σ, π, π) = 0 for all σ ≠ 0_{n}.

Lemma 3.6 can of course be used on either side of the triangle by switching the roles of σ and τ. An additional restriction on σ and τ is given by the following lemma. We present and prove it here. It gives certain restrictions on the Amatrices presented in Section 3.3, but we will not need it in the remainder of this paper.

Lemma 3.7. Let π, σ, τ ∈ ∏_{2n}. If |λ(σ)| + |λ(τ)| > |λ(π)|, then a(σ, π, τ) = 0.

Proof. Assume 4|m and let k = m/4. As polynomials in m, the leading terms of X(σ, m) := SSY T (λ(σ), n + m/2 − 2) and Y (τ, m) := SSY T (λ(τ), m − 2n − m/2 + 3) have positive coefficients and degrees |λ(σ)| and |λ(τ)| respectively. For a given π ∈ ∏_{2n} choose σ, τ ∈ ∏_{2n} for which a(σ, π, τ) ≠ 0 and such that M := |λ(σ)| + |λ(τ)| is maximal. Since a(σ, π, τ) > 0 we have

[m^{M}] ∑ ; σ,τ∈∏_{2n},|λ(σ)|+|λ(τ)|=M X(σ, m)a(σ, π, τ)Y (τ, m) > 0.

Since M was maximal, deg(A_{n+m}((π)_{m})) = M, and according to Theorem 3.4 we have M = λ(π). We conclude that if we choose σ and τ so that |λ(σ)| + |λ(τ)| > |λ(π)| = M, then a(σ, π, τ) = 0. □

3.3. The matrices A, B and C. To continue the study of the numbers a(σ, π, τ) we will find it convenient to arrange these in matrices. Define the two C(n)×C(n) matrices A = A(σ) = {a(σ, β, α)}_{α,β} and Ā = Ā(π) = {a(α, π, β)}_{α,β} where C(n) are the Catalan numbers. To do this we need to fix an order on the rows and columns. We have a partial order ≤ on the patterns (inclusion with respect to the Ferrers diagram) in which 0_{n} ≤ π ≤ 1^{n} for all π. Now choose any of the extensions of this partial order to a linear order and denote this linear order by ≤_{p}. We will order the rows of A top-down and the columns from left to right by ≤_{p}. The rows and columns of Ā are ordered in the same way.

The numbers A_{n+m}((π)_{m}) are expressed in (4) in terms of three regions. Now, instead of T_{n}, we choose the region in Figure 12 as the middle part. We call

Figure 12. The extended region T′_{3}

this extended region T′_{n}. The triangulated regions in Figure 10 will remain the same, except that in the right part the length m − 3n − 2k + 4 will be replaced by m − 3n − 2k + 3 to compensate for the larger T′_{n}. Let a′(α, π, β) be the number of configurations on T′_{n} with pattern σ on the left, π on the lower and τ on the right, extended border. We define matrices A′ and Ā′ analogously to A and Ā above, with the same order on the rows and columns.

We will show that the operation of extending T_{n} to T′_{n} is a linear operation on the matrices A and Ā and we will describe the matrix of this operation explicitly. For this we introduce the following annotated Dyck path.

Definition 3.1. A marked Dyck path is a pair (P, i) where P is a Dyck path and 1 ≤ i ≤ n − 1 is an integer.

Intuitively, the additional integer indicates a position on the Dyck path. More precisely, it indicates the i:th descending edge from the right. There are two types of simple moves that can be performed on (P, i), see Figure 13(a) and (b). The first is to simply increase the position by one, i.e, (P, i) ↦ (P, i + 1). The other is to remove a peak of P which is located at position i, (P, i) ↦ (P′, i). These two simple moves determines a partial order on the marked Dyck paths.

Definition 3.2. (P, i) ≤ (Q, j) if and only if (Q, j) can be formed from (P, i) by a sequence of simple moves.

Now define the matrix B as

B = \{B_{αβ}\} where B_{αβ} = \begin{cases}1 & if (β, 1) ≤ (α, i) for some i, \\ 0 & otherwise. \end{cases}  (5)

\begin{matrix}(a) \\ (b) \end{matrix}

Figure 13. Simple moves on marked Dyck paths.

B is by definition an upper-triangular 0/1-matrix with 1 on the main diagonal. It is defined in terms of a partial order, but information is lost when the position is forgotten so B itself does in general not describe a partial order. The following proposition states that B is the matrix of our extension operation.

Proposition 3.8. A′(σ) = BA(σ) and Ā′(π) = BĀ(π) for all π and σ.

Proof. Figure 14(a) shows the extended part of a configuration. The pattern τ = {e_{1}, e_{2}, e_{5}, e_{7}} is the pattern on the extended boundary and τ′ is the pattern on the boundary of T_{5}.

(a)  (b) τ′  e_{1} e_{7} e_{5} e_{2} τ  f_{1} f_{2} f_{3} f_{4} f_{5} f_{6} f_{7} f_{8} f_{8}f_{7}f_{6}f_{5}f_{4}f_{3}f_{2}f_{1}  e_{7}  e_{5}  e_{2} e_{1} τ′ τ

Figure 14. The extended part of T′_{5}.

To see if τ and τ′ may be connected by valid edge configurations and in how many ways this can be done, we pass once again to the rhombus tiling problem. This region is shown in Figure 14(b). If we regard the dotted edges of τ′ as part of this graph, we see that the edges of τ separate the region into 2-connected blocks with an additional edge to the right in case e_{1} ∈ τ. In order for these blocks to be tilable, we need to remove one dotted edge in each of them. In terms of edge sets this corresponds to including one edge in τ′ for each block. Thus, for each consecutive pair e_{i}, e_{j} ∈ τ we must have an edge f_{k} ∈ τ′ such i ≤ k < j and additionally, for the highest edge e_{l} ∈ τ we must have f_{k} ∈ τ′ with l ≤ k < 2n − 1.

Translated to simple moves on marked Dyck paths, moving the marker corresponds to letting k = i (or k = l) in the aforementioned description while k > i (or k > l) corresponds to removing a sequence of boxes followed by moving the marker. □

The extension of T_{n} to T′_{n} can of course be made to the left instead of to the right. This operation sends Ā(π) ↦ Ā(π)B^{T}. In the case when π is symmetric, it is obvious that extending to the right or to the left is equivalent, i.e, BĀ(π) = Ā(π)B^{T}. We conjecture that this is true in general.

Conjecture 3.4. For all π,

BĀ(π) = Ā(π)B^{T} .

We are now ready to present our main conjecture.

Conjecture 3.5. Let C = A(0_{n})^{−1}BA(0_{n}). Then, C is integer valued, uppertriangular and

(a) BA(σ) = A(σ)C, ∀σ ∈ ∏_{2n}.

(b) C_{α1^{n}} = 1, ∀α ∈ ∏_{2n}.

Lemma 3.6(a) gives the upper-triangularity of A(0_{n}) and Lemma 3.6(b) shows that the main diagonal of A(0_{n}) contains all ones. This implies that A(0_{n})^{−1} is upper-triangular and integral and finally the same holds for C due to the uppertriangularity and integrality of B. Conjecture 3.5 has been shown to be true for n ≤ 5 by explicit calculation of the matrices involved.

Example 3.1. Let n = 3,

σ_{0} := ((())) = 0_{3}, σ_{1} := (()()), σ_{2} := ()(()), σ_{3} := (())(), σ_{4} := ()()() = 1^{3}

and order the patterns in ∏_{6} by the rule σ_{i} ≤_{p} σ_{j} when i ≤ j. Explicit calculations give the matrices A(σ), B and C.

A(σ_{0}) = (\begin{matrix}1 & 4 & 6 & 6 & 17 \\ 0 & 1 & 3 & 4 & 13 \\ 0 & 0 & 1 & 0 & 4 \\ 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 1 \end{matrix})  A(σ_{1}) = (\begin{matrix}0 & 1 & 4 & 3 & 13 \\ 0 & 0 & 1 & 1 & 7 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})

A(σ_{2}) = (\begin{matrix}0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})  A(σ_{3}) = (\begin{matrix}0 & 0 & 1 & 0 & 3 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})

A(σ_{4}) = (\begin{matrix}0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})

B = (\begin{matrix}1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix})  C = (\begin{matrix}1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix})  (6)

Matrices for n = 2 and n = 4 are given in Appendix A.

3.4. A set of commuting matrices. Before we investigate the consequences of Conjecture 3.5 we will take a look at the following set of matrices. Let

M(σ) := A(σ)A^{−1}(0).  (7)

We have observed that the multiplication of these M-matrices seems to have a nice combinatorial description and that these matrices seem to commute.

Example 3.2. Figure 15 shows two M-matrix multiplications expressed as sums of M-matrices. The first is for n = 4 and the second for n = 5. The patterns are given as Ferrers diagrams. In particular, for all patterns α in the sums, we note that |λ(α)| = |λ(σ)| + |λ(σ′)|. We also note that all terms occur with positive coefficients.

M(  )M( ) =M(  ) + M(  ) + M(  ).

M(  )M(  ) = 2M(  ) + M(  ) + M(  ) +M(  ) + M(  ). ) + M(

Figure 15. Observed sum rules for M-matrices.

For i = 0, …, n − 1, let

σ_{i} := (()_{i}())_{n−i}.  (8)

We conjecture the following basic rule for the decomposition of the multiplication.

Conjecture 3.6. Let σ ∈ ∏_{2n}. Then,

M(σ)M(σ_{i}) = ∑_{α:B_{ασ}=1 and |α|−|σ|=i} M(α).  (9)

In other words, the sum is taken over all patterns which can be reached from σ by simple moves while removing a total of i peaks (or adding i boxes when seen as Ferrers diagrams.)

We are interested in extending this decomposition, and in particular find integer coefficients D_{σσ′}^{α} such that

M(σ)M(σ′) = ∑ ; α∈∏_{2n} D_{σσ′}^{α}M(α).  (10)

for all σ′ ∈ ∏_{2n}. This can in fact be accomplished by the following inductive argument. We will temporarily assume a partial order ≤_{t} on ∏_{2n} where σ ≤_{t} τ if

• σ = τ, or

• σ has strictly fewer columns than τ, or

• σ and τ have the same number of columns, but σ has fewer boxes in its rightmost column.

Let σ′ ∈ ∏_{2n} be a diagram with more than one column and assume that we have determined D_{σβ}^{α} for all α ∈ ∏_{2n} and β <_{t} σ′. Let σ′_{∗} denote σ′ with its rightmost column removed and let l denote the length of this column. Then we can use (9) to decompose M(σ′_{∗})M(σ_{l}) and have

M(σ′) = M(σ′_{∗})M(σ_{l}) − ∑_{β<_{t}σ′} D_{σ′_{∗}σ_{l}}^{β}M(β)  (11)

Thus,

M(σ)M(σ′) = (M(σ)M(σ′_{∗}))M(σ_{l}) − ∑_{β<_{t}σ′} D_{σ′_{∗}σ_{l}}^{β}M(σ)M(β) =

∑_{γ} D_{σσ′_{∗}}^{γ}M(γ)M(σ_{l}) − ∑_{β<_{t}σ′,α} D_{σ′_{∗}σ_{l}}^{β}D_{σβ}^{α}M(α) =

∑_{γ,δ} D_{σσ′_{∗}}^{γ}D_{γσ_{l}}^{δ}M(δ) − ∑_{β<_{t}σ′,α} D_{σ′_{∗}σ_{l}}^{β}D_{σβ}^{α}M(α) =

∑_{α} ( ∑_{γ} D_{σσ′_{∗}}^{γ}D_{γσ_{l}}^{α} − ∑_{β<_{t}σ′} D_{σ′_{∗}σ_{l}}^{β}D_{σβ}^{α})M(α). (12)

Since σ′_{∗}, σ_{l} <_{t} σ′, we have determined D_{σσ′}^{α} in the last row of (12).

We note the close resemblance between Conjecture 3.6 and (a dual version of) Pieri’s rule (see for example [21]), the difference being that we force containment in the staircase diagram (n − 1, …, 2, 1). Starting from Pieri’s rule and extending to all diagrams, one obtains the Littlewood–Richardson coefficients, C_{σσ′}^{α}. This immediately leads us to the following description of the D-coefficients.

Proposition 3.9. Conjecture 3.6 implies that for all σ, σ′, α ∈ ∏_{2n},

D_{σσ′}^{α} = C_{σσ′}^{α}

The positivity of the D-coefficients follow from Proposition 3.9 (conditioned on the truth of Conjecture 3.6). We also have the following.

Proposition 3.10. Conjecture 3.6 implies that for all σ, σ′ ∈ ∏_{2n},

M(σ)M(σ′) = M(σ′)M(σ).  (13)

Proof. This can either be taken as a corollary of Proposition 3.9 and the symmetry of the Littlewood–Richardson coefficients or by noting that Conjecture 3.6 immediately gives M(σ_{i})M(σ_{j}) = M(σ_{j})M(σ_{i}) and extend this basic relation with an argument similar to that which was used to produce the D-coefficients. □

The most interesting consequence of Conjecture 3.6 is the following.

Proposition 3.11. Conjecture 3.6 and Conjecture 3.4 implies Conjecture 3.5(a).

Proof. Note that Conjecture 3.4 implies

BA(0_{n}) = ∑_{i=0}^{n−1} A(σ_{i})

where σ_{i} are defined in (8). By right multiplication with A^{−1}(0) we have

B = ∑_{i=0}^{n−1} M(σ_{i})

which, by Proposition 3.10 means that BM(σ) = M(σ)B. Finally, we multiply this expression on the right by A(0) to obtain

BA(σ) = M(σ)BA(0) = A(σ)(A^{−1}(0)BA(0)).
□

3.5. Consequences of Conjecture 3.5. We will now derive some consequences of the previous sections. They are given in Propositions 3.12, 3.13 and 3.14 and are all conditioned on the truth of Conjecture 3.5.

Proposition 3.12. Conjecture 3.5(a) implies the following equality.

A_{n+m}((π)_{m}) = ∑ ; α∈∏_{2n} C_{απ}A_{n+m−1}((α)_{m−1}).  (14)

Proof. Note that a(σ, π, τ) = A(σ)_{τπ}. To make the calculations clearer, let X(σ) := SSY T (λ(σ), n + 2k − 2) and Y (τ, m) := SSY T (λ(τ), m − 2n − 2k + 3). We then have

A_{n+m}((π)_{m}) = ∑ ; σ,τ∈∏_{2n} X(σ)A(σ)_{τπ}Y (τ, m) =

∑ ; σ,τ∈∏_{2n} X(σ)(BA(σ))_{τπ}Y (τ, m − 1) =

∑ ; σ,τ∈∏_{2n} X(σ)(A(σ)C)_{τπ}Y (τ, m − 1) =

∑ ; α∈∏_{2n} ∑ ; σ,τ∈∏_{2n} X(σ)A(σ)_{τα}C_{απ}Y (τ, m − 1) =

∑ ; α∈∏_{2n} C_{απ}A_{n+m−1}((α)_{m−1}).

□

Proposition 3.12 provides a summation formula for the configuration numbers in terms of configurations of size one less. If we choose π = 1^{n} and also assume Conjecture 3.5(b), the relation (14) turns into Zuber’s Conjecture 3.2. In addition, Proposition 3.12 provides conjectured sums for any π on the left-hand side.

Next, we will look at another type of pattern. Let π ∈ ∏_{2n} and π′ ∈ ∏_{2n′}. Then (π)_{m}π′ consists of the patterns π and π′ separated by m arches. We can follow the same reasoning as before except that we will not be able to remove the bound on m.

Assume that n ≥ n′ and that m ≥ 3n − n′. We place the pattern so that π is on the lower boundary (k = 1). The restriction on m forces π′ to be located on the upper boundary. The fixed edge graph for such a placement is shown in Figure 16.

π′ π

Figure 16. The fixed edge graph when n = 3, n′ = 2, m = 15 and k = 1.

We now have two triangular regions, T_{n} and T_{n′}. The regions between these two, on which can apply rhombus tilings are different from those in the previous case. They are shown in Figure 17.

m + n′ − 3n − 2k + 4 2k − 1  n + n′ − 2 n + n′ − 2 m − n − n′ − 2k + 4  2(k + n − n′) − 1

Figure 17. Rhombus tiling regions for matchings (π)_{m}π′.

We get the following proposition.

Proposition 3.13. Let n, n′ > 0, m ≥ 3n − n′ and π, π′ ∈ ∏_{2n}. Then, Conjecture 3.5(a) implies the following equality.

A_{n+n′+m}((π)_{m}π′) = ∑ ; α∈∏_{2n},β∈∏_{2n′} C_{απ}C′_{βπ′}A_{n+m−1}((α)_{m−1}β).  (15)

Proof. The enumeration of tilings of the regions in Figure 17 was carried out by Caselli, Krattenthaler, Lass and Nadeau in [4]. Here, we simply write X(σ, τ, m) for the number of tilings of the left region, where σ is the lower pattern, and τ the upper one. We write similarly Y (σ, τ, m) for the number of tilings of the right region. Let B′ and C′ be the matrices of size n′ ×n′ corresponding to the matrices B and C. The calculations follow the same pattern as those for Proposition 3.12.

A_{n+n′+m}((π)_{m}π′) =

∑ ; σ,τ∈∏_{2n},σ′,τ′∈∏_{2n′} X(σ, τ′, m)A_{n}(σ)_{τπ}Y (τ, σ′, m)A_{n′}(σ′)_{τ′π′} =

∑ ; σ,τ∈∏_{2n},σ′,τ′∈∏_{2n′} X(σ, τ′, m − 1)(BA_{n}(σ))_{τπ}Y (τ, σ′, m − 1)(B′A_{n′}(σ′))_{τ′π′} =

∑ ; σ,τ∈∏_{2n},σ′,τ′∈∏_{2n′} X(σ, τ′, m − 1)(A_{n}(σ)C)_{τπ}Y (τ, σ′, m − 1)(A_{n′}(σ′)C′)_{τ′π′} =

∑ ; α,σ,τ∈∏_{2n},β,σ′,τ′∈∏_{2n′} X(σ, τ′, m − 1)A_{n}(σ)_{τα}C_{απ}Y (τ, σ′, m − 1)A_{n′}(σ′)_{τ′β}C′_{βπ′} =

∑ ; α∈∏_{2n},β∈∏_{2n′} C_{απ}C′_{βπ′}A_{n+n′+m−1}((α)_{m−1}β).

□

The validity of Conjecture 3.5(a) and by that the validity of (15) would prove some of the sums conjectured by Zuber in [27]. The second part of his Conjecture 9 would follow, using π = 1^{n}, π′ = ()(()) and m = 1. Also, on page 12 of [27], the three identities would follow using π = 1^{n}, m = p and π′ = ()(), π′ = ()(()) or π′ = ()()() respectively. The matrix C encodes the systematics of these sums, which Zuber was asking for.

Example 3.3. For n ≤ 5, and π, π′ ∈ ∏_{2n} we know that Conjecture 3.5(a) holds and therefore also (15). An example of such a sum is given in Figure 18.

=  +  −  + +  −  + + m  m − 1  m − 1  m − 1  m − 1 m − 1  m − 1  m − 1  m − 1

Figure 18. Sum rule for π = (())(()), π′ = ()(()).

We conclude this section with an application of Conjecture 3.5 to half-turn symmetric configurations.

Proposition 3.14. Let n > 0, m ≥ 3n−n′ and π ∈ ∏_{2n}. Then, Conjecture 3.5(a) implies the following equality.

A_{n+m}^{HT}((π)_{m}π) = ∑ ; α∈∏_{2n} C_{απ}A_{n+m−1}^{HT}((α)_{m−1}α)  (16)

Proof. The matchings are of the form (π)_{m}π, similar to the previous case. But here, due to the symmetry, there is only one pattern π and the two rhombus tiled regions are identified, leading to simplified calculations.

A_{n+m}^{HT}((π)_{m}π) = ∑ ; σ,τ∈∏_{2n} X(σ, τ, m)A(σ)_{τπ}

∑ ; σ,τ∈∏_{2n} X(σ, τ, m − 1)(BA(σ))_{τπ}

∑ ; σ,τ∈∏_{2n} X(σ, τ, m − 1)(A(σ)C)_{τπ}

∑ ; α∈∏_{2n} ∑ ; σ,τ∈∏_{2n} X(σ, τ, m − 1)A(σ)_{τα}C_{απ} =

∑ ; α∈∏_{2n} C_{απ}A_{2n+m−1}^{HT}((α)_{m−1}α)

□

4. Open problems

In this section we briefly present some of the many interesting open problems related to Conjecture 3.5.

The matrix C is given explicitly in Section 3 for n = 3 and in Appendix A for n = 2 and n = 4. Implicitly it’s given by A^{−1}(0_{n})BA(0_{n}) or, conditioned on Conjecture 3.4, by A^{−1}(0_{n}) ∑_{i=0}^{n−1} A(σ_{i}).

Problem 1. Find a direct, combinatorial description of C, not involving the inverse of the A(0_{n}) matrix.

The relations (14) and (15) involve one, respectively two patterns separated by nested arches. A question one could ask is if something similar can be observed for three or more patterns.

Problem 2. Find a relation between configurations with patterns of the form (π)_{m}(π′)_{m′}(π′′)_{m′′} and sums of configurations of smaller sizes where the matrix C from Conjecture 3.5 shows up.

The final open problem that we mention is the restriction to m ≥ 3n − n′ in Propositions 3.13 and 3.14. As was mentioned, this comes from the still unresolved Conjecture 3.3 by Zuber.

Problem 3. Prove Conjecture 3.3.

Acknowledgements. The author wishes to thank the anonymous referee of an earlier version of this paper who suggested the connection between D_{σσ′}^{α} and the Littlewood–Richardson coefficients in Section 3.4.

References

[1] M. T. Batchelor, J. de Gier, and B. Nienhuis. The quantum symmetric XXZ chain at Δ = −\frac{1}{2}, alternating sign matrices and plane partitions. J. Phys. A, 34:L265, 2001.

[2] D. Bressoud. Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture. Cambridge University Press, 1999.

[3] F. Caselli and C. Krattenthaler. Proof of two conjectures of Zuber on fully packed loop configurations. J. Combin. Theory Ser. A, 108(1):123–146, 2004.

[4] F. Caselli, C. Krattenthaler, B. Lass, and P. Nadeau. On the number of fully packed loop configurations with a fixed associated matching. Electronic J. Combin., 11(2):R16, 2005.

[5] Jan de Gier. Loops, matchings and alternating-sign matrices. Discrete Math., 298:365–388, 2005.

[6] P. Di Francesco. Boundary qKZ equation and generalized Razumov–Stroganov sum rules for open IRF models. J. Stat. Mech.: Theory and Experiment, 11:P11003, 2005.

[7] P. Di Francesco. Inhomogeneous loop models with open boundaries. J. Phys. A: Math. Gen., 38:6091–6120, 2005.

[8] P. Di Francesco and P. Zinn-Justin. Around the Razumov–Stroganov conjecture: proof of a multi-parameter sum rule. Electronic J. Combin., 12:R6, 2005.

[9] P. Di Francesco, P. Zinn-Justin, and J.-B. Zuber. A Bijection between classes of fully packed loops and plane partitions. Electron. J. Combin., 11(1):R64, 2004.

[10] P. Di Francesco, P. Zinn-Justin, and J.-B. Zuber. Determinant formulae for some tiling problems and application to fully packed loops. Ann. Inst. Fourier (Grenoble), 55(6):2025– 2050, 2005.

[11] P. Di Francesco, P. Zinn-Justin, and J.-B. Zuber. Sum rules for the ground states of the O(1) loop model on a cylinder and the XXZ spin chain. J. Stat. Mech. Theory Exp. (2006):P08011.

[12] P. Di Francesco and J.-B. Zuber. On FPL configurations with four sets of nested arches. J. Stat. Mech. Theory Exp. (2004)(6), 005.

[13] G. Kuperberg. Another proof of the alternating sign matrix conjecture. Int. Math. Res. Notes, pages 139–150, 1996.

[14] G. Kuperberg. Symmetry classes of alternating-sign matrices under one roof. Ann. of Math., 156(3):835–866, 2002.

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

[16] S. Mitra, B. Nienhuis, J. de Gier, and M. T. Batchelor. Exact expressions for correlations in the ground state of the dense O(1) loop model. J. Stat. Mech. Theory Exp., (2004):P09010.

[17] Vincent Pasquier. Quantum incompressibility and Razumov Stroganov type conjectures. Ann. Henri Poincaré, 7:397–421, 2006.

[18] A. V. Razumov and Yu G. Stroganov. Enumerations of half-turn symmetric alternating-sign matrices of odd order. arχiv:math-ph/0504022. in Russian: Teoret. Mat. Fiz., 148(3):357– 386, 2006.

[19] A. V. Razumov and Yu. G. Stroganov. Spin chains and combinatorics. J. Phys. A, 34:3185, 2001.

[20] A. V. Razumov and Yu G. Stroganov. Combinatorial nature of ground state vector of O(1) loop model. Theor. Math. Phys., 138:333–337, 2004.

[21] R. P. Stanley. Enumerative Combinatorics, volume 2. Cambridge University Press, 1999.

[22] Yu. Stroganov. The importance of being odd. J. Phys. A, 34:L179, 2001.

[23] Benjamin Wieland. A large dihedral symmetry of the set of alternating sign matrices. Electronic J. Combin., 7(1):R37, 2000.

[24] D. Zeilberger. Proof of the alternating sign matrix conjecture. Electronic J. Combin., 3(2):R13, 1996.

[25] P. Zinn-Justin. Loop model with mixed boundary conditions, qKZ equation and Alternating Sign Matrices. J. Stat. Mech. Theory Exp., (2007)(1):P01007.

[26] P. Zinn-Justin. Proof of the Razumov–Stroganov conjecture for some infinite families of link patterns. Electronic J. Combin., 13:R110, 2006.

[27] J.-B. Zuber. On the counting of fully packed loop configurations: some new conjectures. Electron. J. Combin., 11(1):R13, 2004.

Appendix A. Matrices

For n = 2, there is only one possible ordering of the 2 patterns. The matrices are as follows.

A(0_{2}) = (\begin{matrix}1 & 2 \\ 0 & 1 \end{matrix})  A(1^{2}) = (\begin{matrix}0 & 1 \\ 0 & 0 \end{matrix})  B = (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix})  C = (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix})

For n = 4 we give the matrices A(0_{4}), B and C. We used the following order on the patterns in ∏_{8}. (((()))) ≤ ((()())) ≤ (()(())) ≤ ()((())) ≤ ((())()) ≤ (()()()) ≤ ()(()()) ≤ (())(()) ≤ ()()(()) ≤ ((()))() ≤ (()())() ≤ ()(())() ≤ (())()() ≤ ()()()().

A(0_{4}) = ( \begin{matrix}1 & 6 & 15 & 20 & 15 & 60 & 95 & 50 & 165 & 20 & 95 & 180 & 165 & 534 \\ 0 & 1 & 5 & 10 & 6 & 31 & 64 & 40 & 139 & 15 & 80 & 171 & 160 & 556 \\ 0 & 0 & 1 & 4 & 0 & 6 & 25 & 15 & 66 & 0 & 15 & 65 & 60 & 271 \\ 0 & 0 & 0 & 1 & 0 & 0 & 6 & 0 & 15 & 0 & 0 & 15 & 0 & 60 \\ 0 & 0 & 0 & 0 & 1 & 5 & 10 & 10 & 34 & 6 & 31 & 64 & 65 & 225 \\ 0 & 0 & 0 & 0 & 0 & 1 & 4 & 5 & 21 & 0 & 6 & 25 & 31 & 135 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 5 & 0 & 0 & 6 & 0 & 31 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 4 & 0 & 0 & 0 & 6 & 25 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 5 & 10 & 10 & 34 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 4 & 5 & 21 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

B = ( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix} )

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

Explicit calculations of A(σ) for n = 4 and the case when n = 5 has also been carried out and are available by request from the author.