The puzzle conjecture for the cohomology of two-step flag manifolds

Abstract

We prove a conjecture of Knutson asserting that the Schubert structure constants of the cohomology ring of a two-step flag variety are equal to the number of puzzles with specified border labels that can be created using a list of eight puzzle pieces. As a consequence, we obtain a puzzle formula for the Gromov–Witten invariants defining the small quantum cohomology ring of a Grassmann variety of type A. The proof of the conjecture proceeds by showing that the puzzle formula defines an associative product on the cohomology ring of the two-step flag variety. It is based on an explicit bijection of gashed puzzles that is analogous to the jeu de taquin algorithm but more complicated.

1 Introduction

At the end of the last millennium, Knutson gave an elegant conjecture for the Schubert structure constants of the cohomology ring of any partial flag variety ${{\mathrm{SL}}}(n)/P$ of type A [6]. The conjecture states that each Schubert structure constant in $H^*({{\mathrm{SL}}}(n)/P; {\mathbb Z})$ is equal to the number of triangular puzzles with specified border labels that can be created using a list of puzzle pieces. The special case for Grassmannians was established in [8, 9]. Unfortunately, Knutson quickly discovered counterexamples to his general conjecture. Buch, Kresch, and Tamvakis later proved that the Gromov–Witten invariants defining the small quantum cohomology ring of a Grassmann variety are equal to Schubert structure constants on two-step flag varieties, and it was suggested that Knutson’s conjecture might be true in this important special case [2]. This was supported by verifying with the help of a computer that the conjecture is correct for all two-step varieties ${{\mathrm{Fl}}}(a,b;n)$ with $n \le 16$. The purpose of the present paper is to give a proof of Knutson’s conjecture for arbitrary two-step flag varieties. As a consequence, we obtain a quantum Littlewood–Richardson rule: a puzzle formula for the three point, genus zero Gromov–Witten invariants on any Grassmannian of type A, see Sect. 8.

After Knutson formulated his general conjecture and the work [2] appeared, a different positive formula for the Schubert structure constants on two-step flag varieties was proved by Coskun [4]. This rule expresses the structure constants as the number of certain chains of diagrams called mondrian tableaux, which correspond to the components of a degeneration of an intersection of Schubert varieties. Although it is well adapted to the geometry, Coskun’s rule does not address the validity of Knutson’s conjecture for two-step flag varieties.

Recent work of Knutson and Purbhoo [7] shows that the Belkale–Kumar coefficients [1] for ${{\mathrm{SL}}}(n)/P$ are computed by a special case of Knutson’s original puzzle conjecture. This special case uses only a subset of the puzzle pieces, and it is not limited to 2-step flag varieties. On the other hand, the set of Belkale–Kumar coefficients is a proper subset of the structure constants of the cohomology ring of any flag variety other than a Grassmannian.

In this paper, a puzzle piece means a (small) triangle from the following list.

In Knutson’s original conjecture, the side labels of the puzzle pieces were parenthesized strings of the integers 0, 1, and 2. The labels that are greater than two can be translated to such strings as follows:

$$\begin{aligned} 3 = 10, \ 4 = 21, \ 5 = 20, \ 6= 2(10), \quad \text {and} \quad 7 = (21)0. \end{aligned}$$

This description adds intuition to the puzzle pieces. However, we will stick to labels in the set $\{0,1,2,3,4,5,6,7\}$ in this paper. The labels 0, 1, 2 are called simple and the other labels 3, 4, 5, 6, 7 are called composed.

A triangular puzzle is an equilateral triangle made from puzzle pieces with matching labels. The puzzle pieces may be rotated but not reflected. If all labels on the border of a puzzle are simple, then all composed labels in the puzzle are uniquely determined from the simple labels. One may therefore omit the edges with composed labels in pictures of puzzles. The following two pictures show the same puzzle with and without its composed labels.

A puzzle with simple border labels is the same as an equilateral triangle made of composed puzzle pieces from the following list. All can be rotated and the fourth and sixth can be stretched in the direction of the longest side:

The Schubert varieties $X_u$ of the flag manifold $X = {{\mathrm{Fl}}}(a,b;n)$ are indexed by integer vectors u of length n, with a entries equal to 0, $b-a$ entries equal to 1, and $n-b$ entries equal to 2, see Sect. 2. Such vectors will be called 012-strings for X. Knutson’s conjecture for two-step flag varieties is the following result.

Theorem 1

Let $X_u$, $X_v$, and $X_w$ be Schubert varieties in ${{\mathrm{Fl}}}(a,b;n)$. Then the triple intersection number

$$\begin{aligned} \int _{{{\mathrm{Fl}}}(a,b;n)} [X_u] \cdot [X_v] \cdot [X_w] \end{aligned}$$

is equal to the number of triangular puzzles for which u, v, and w are the labels on the left, right, and bottom sides, in clockwise order.

Theorem 1 is proved by establishing that the puzzle rule defines an associative product on the cohomology ring of X, following the strategy introduced in [3] in the case of Grassmannians. The corresponding identities among structure constants are obtained from an explicit bijection of puzzles. This bijection is a generalization of the classical jeu de taquin algorithm on semistandard Young tableaux (see [12] for a discussion of the bijections between tableaux and puzzles), but is significantly more involved and is defined by a list of 80 different rules for propagating a gash from one side of a puzzle to another. A gash involves a pair of puzzle edges where the puzzle pieces do not have matching labels, a notion introduced by Knutson and Tao [8], and extended to our setting in Sect. 5. The large number of propagation rules makes a few parts of our proof tedious but still straightforward to verify.

One important property of the jeu de taquin algorithm for tableaux is that consecutive Schützenberger sliding paths do not cross each other (see e.g. [3, section 2]). This implies that a suitable bijection of tableaux can be obtained by repeating the jeu de taquin algorithm several times, an idea which has been used in many proofs of the classical Littlewood–Richardson rule for Grassmannians, see e.g. [3, 5, 14] and the references therein. Unfortunately, this property does not hold for the corresponding propagation paths in puzzles for two-step flags, which may in fact cross each other. Example 7.7 illustrates the problem. We overcome this difficulty by carrying out several propagations simultaneously, interlacing the individual steps, to obtain the desired bijection. Naturally, this requires some care, and the precise manner in which the simultaneous propagations are controlled is the main technical innovation in this paper. The issue of crossing propagation paths shapes our proof in subtle but significant ways; for example, while there are many possible ways to formulate the propagation rules, our presentation is tailored to handle crossings as seamlessly as possible.

This paper is organized as follows. In Sect. 2 we reduce the proof of Theorem 1 to the verification of two identities which roughly state that the puzzle rule defines an associative ring. Section 3 proves one of these identities, which says that multiplication by one has the expected result. We also reformulate the puzzle rule in terms of rhombus-shaped puzzles and identify the required properties of a bijection on such puzzles. Section 4 defines a relation on strings of puzzle labels that generalizes the Pieri rule for two-step flag varieties. This relation is crucial for carrying out multiple propagations simultaneously and for dealing correctly with crossing propagation paths. In Sect. 5 we give an informal discussion of propagations in two-step puzzles, after which Sect. 6 gives the complete list of propagation rules together with case-by-case analysis that verifies that every (unfinished) gash can be moved by a unique rule. At a first reading, Sect. 6.1 through 6.6 may very well be skimmed, with greater attention given to Sect. 6.7, which records properties essential to the proof of the main result. Section 7 puts the combinatorial constructions together to obtain the required bijection and finish the proof. Finally, Sect. 8 applies Theorem 1 to obtain a quantum Littlewood–Richardson rule for the Gromov–Witten invariants on Grassmannians.

2 Strategy of the proof

Theorem 1 will be proved by applying the following principle to the multiplicative action of the cohomology ring $H^*(X;{\mathbb Z})$ on itself. This principle was first applied to classical Schubert calculus in [3]. A related principle in the setting of equivariant cohomology was introduced in [11] and used in [8].

Lemma 2.1

Let R be an associative ring with unit 1, let $S \subset R$ be a subset that generates R as a ${\mathbb Z}$-algebra, and let M be a left R-module. Let $\mu {:} R \times M \rightarrow M$ be any ${\mathbb Z}$-bilinear map satisfying that, for all $r \in R$, $s \in S$, and $m \in M$ we have $\mu (1,m) = m$ and $\mu (rs,m) = \mu (r,sm)$. Then $\mu (r,m) = rm$ for all $(r,m) \in R \times M$.

Proof

Since R is generated by S and $\mu$ is linear in its first argument, it is enough to show that $\mu (r,m) = rm$ whenever $m \in M$ and $r = s_1 s_2 \cdots s_k$ is a product of factors $s_i \in S$. This follows from the assumptions by induction on k. $\square$

Let $X = {{\mathrm{Fl}}}(a,b;n) = \{(A,B){:} A \subset B \subset {\mathbb C}^n$ and $\dim (A)=a$ and $\dim (B)=b \}$ be the variety of two-step flags in ${\mathbb C}^n$ of dimensions (a, b). Let $e_1,\ldots ,e_n$ be the standard basis for ${\mathbb C}^n$. For a subset $S \subset {\mathbb C}^n$, we let $\langle S \rangle \subset {\mathbb C}^n$ denote the span of S. A 012-string for X is a string $u = (u_1,\ldots ,u_n)$ with a zeros, $b-a$ ones, and $n-b$ twos; this corresponds to a minimal length coset representative for the parabolic subgroup $S_a \times S_{b-a} \times S_{n-b}$ of the Weyl group $S_n$.

Given a 012-string for X, consider the point $(A_u,B_u) \in X$, where $A_u = \langle e_i{:} u_i=0 \rangle$ and $B_u = \langle e_i{:} u_i \le 1 \rangle$. The Schubert variety $X_u \subset X$ is the closure of the orbit of $(A_u,B_u)$ for the action of the lower triangular matrices in ${{\mathrm{GL}}}(n)$. Equivalently, $X_u$ is the variety of points $(A,B) \in X$ for which $\dim (A \cap \langle e_p,\ldots ,e_n \rangle ) \ge \dim (A_u \cap \langle e_p,\ldots ,e_n \rangle )$ and $\dim (B \cap \langle e_p,\ldots ,e_n \rangle ) \ge \dim (B_u \cap \langle e_p,\ldots ,e_n \rangle )$ for all $p \in [1,n]$. The codimension of $X_u$ in X is equal to the number of inversions $\ell (u) = \# \{ (i,j){:} 1 \le i < j \le n$ and $u_i > u_j \}$. The Schubert classes $[X_u]$ given by all 012-strings for X form a basis for the cohomology ring $H^*(X;{\mathbb Z})$. The Poincaré dual of the 012-string $u = (u_1,u_2,\ldots ,u_n)$ is the reverse string $u^\vee = (u_n,u_{n-1},\ldots ,u_1)$. With this notation we have $\int _X [X_u] \cdot [X_v] = \delta _{u^\vee ,v}$.

Given 012-strings u, v, and w for X, we let $C^w_{u,v}$ be the number of triangular puzzles with labels u, v, and w on the left, right, and bottom borders, with u and v in clockwise direction and w in counter-clockwise direction.

Define a ${\mathbb Z}$-bilinear map $\mu {:} H^*(X;{\mathbb Z}) \times H^*(X;{\mathbb Z}) \rightarrow H^*(X;{\mathbb Z})$ by

$$\begin{aligned} \mu ([X_u], [X_v]) = \sum _w C^w_{u,v} [X_w] \,, \end{aligned}$$

where the sum is over all 012-strings w for X. It follows from Poincaré duality that Theorem 1 is equivalent to the identity

$$\begin{aligned} \mu ([X_u], [X_v]) = [X_u] \cdot [X_v] \end{aligned}$$

(1)

for all 012-strings u and v for X. We will prove this by identifying a generating subset $S \subset H^*(X;{\mathbb Z})$ of special Schubert classes that satisfies the conditions of Lemma 2.1.

Given two 012-strings u and $u'$, with $u = (u_1,u_2,\ldots ,u_n)$, we write $u \xrightarrow {1} u'$ if there exist indices $i<j$ such that (1) $u_i \in \{0,1\}$, (2) $u_j = 2$, (3) $u_k < u_i$ for all k with $i< k < j$, and (4) $u'$ is obtained from u by interchanging $u_i$ and $u_j$. This corresponds to a covering relation in the ordering induced from the Bruhat order on $S_n$. More generally, for $p \in {\mathbb N}$ we write $u \xrightarrow {p} u'$ if there exists a sequence $u = u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p = u'$ such that, if $u^t$ is obtained from $u^{t-1}$ by interchanging the entries of index $i_t$ and $j_t$, then $j_t \le i_{t+1}$ for all $t \in [1,p-1]$. For example, the chain

$$\begin{aligned}&\displaystyle 02110020202 \xrightarrow {\,1\,} 20110020202 \xrightarrow {\,1\,} 20120010202 \\&\displaystyle \xrightarrow {\,1\,} 20120020102 \xrightarrow {\,1\,} 20120020120 \end{aligned}$$

implies that

$$\begin{aligned} \begin{aligned} 02110020202 \xrightarrow {\,4\,} 20120020120 \,. \end{aligned} \end{aligned}$$

Given an integer p with $0 \le p \le n-b$, we let $\mathbf {p}$ denote the 012-string $\mathbf {p} = (0^a, 1^{b-a-1}, 2^p, 1, 2^{n-b-p})$. This string defines the special Schubert variety

$$\begin{aligned} X_{\mathbf p} = \{ (A,B) \in X \mid B \cap \langle e_{b+p},\ldots ,e_n \rangle \ne 0 \} \,. \end{aligned}$$

The corresponding special Schubert class is the Chern class $[X_{\mathbf p}] = c_p({\mathbb C}^n_X/{\mathcal B})$, where ${\mathcal A}\subset {\mathcal B}\subset {\mathbb C}^n_X = {\mathbb C}^n\times X$ is the tautological flag of subbundles on X. The Pieri formula for X states that [13, 13]

$$\begin{aligned}{}[X_{\mathbf p}] \cdot [X_u] = \sum _{u \xrightarrow {p} u'} [X_{u'}] \,, \end{aligned}$$

(2)

where the sum is over all 012-strings $u'$ for which $u \xrightarrow {p} u'$.

We will derive (1) as a consequence of the following two identities, which will be proved later using an explicit bijection of puzzles (c.f. [3, Proposition 1]). Recall that $\mathbf {0} = (0^a, 1^{b-a}, 2^{n-b})$ is the identity 012-string for which $[X_{\mathbf 0}] = 1 \in H^*(X;{\mathbb Z})$.

Proposition 2.2

Let u, v, and w be 012-strings for X and let $p \ge 0$ be an integer. Then we have

$$\begin{aligned} C^w_{\mathbf {0},u} = \delta _{u,w} \end{aligned}$$

(3)

and

$$\begin{aligned} \sum _{u \xrightarrow {p} u'} C^w_{u',v} = \sum _{v \xrightarrow {p} v'} C^w_{u,v'} \,. \end{aligned}$$

(4)

Fix an orthogonal form on ${\mathbb C}^n$ and set $\widehat{X} = {{\mathrm{Fl}}}(n-b,n-a;n)$. Then the map $\phi {:} X \rightarrow \widehat{X}$ that sends a point (A, B) to $(B^\perp ,A^\perp )$ is an isomorphism of varieties, called the duality isomorphism. The corresponding isomorphism of cohomology rings $\phi ^*{:} H^*(\widehat{X}; {\mathbb Z}) \rightarrow H^*(X;{\mathbb Z})$ is given by $\phi ^* [\widehat{X}_{\widehat{u}}] = [X_u]$, where $\widehat{u} = (2-u_n,2-u_{n-1},\ldots ,2-u_1)$.

For each integer $p \in [0,a]$, define the 012-string $\widetilde{\mathbf p} = (0^{a-p}, 1, 0^p, 1^{b-a-1}, 2^{n-b})$. This string defines the special Schubert variety

$$\begin{aligned} X_{\widetilde{\mathbf p}} = \{ (A,B) \in X \mid \dim (A \cap \langle e_{a-p+2},\ldots ,e_n \rangle ) \ge p \} \end{aligned}$$

and the special Schubert class $[X_{\widetilde{\mathbf p}}] = c_p({\mathcal A}^\vee ) \in H^*(X;{\mathbb Z})$. By applying $\phi ^*$ to both sides of the Pieri rule (2) for $\widehat{X}$, we obtain the identity

$$\begin{aligned}{}[X_{\widetilde{\mathbf p}}] \cdot [X_u] = \sum _{u \xrightarrow {\widetilde{p}} u'} [X_{u'}] \end{aligned}$$

(5)

in $H^*(X;{\mathbb Z})$, where we write $u \xrightarrow {\widetilde{p}} v$ if and only if $\widehat{u} \xrightarrow {p} \widehat{v}$.

The duality isomorphism has a corresponding bijection on puzzles that reflects a puzzle in a vertical line and substitutes all labels according to the following rule:

$$\begin{aligned} 0 \mapsto 2 \ ; \ \ 1 \mapsto 1 \ ; \ \ 2 \mapsto 0 \ ; \ \ 3 \mapsto 4 \ ; \ \ 4 \mapsto 3 \ ; \ \ 5 \mapsto 5 \ ; \ \ 6 \mapsto 7 \ ; \ \ 7 \mapsto 6 \,. \end{aligned}$$

This bijection implies that we have $C^w_{u,v} = C^{\widehat{w}}_{\widehat{v},\widehat{u}}$ for all 012-strings u, v, w for X. In particular, Eq. (4) applied to $\widehat{X}$ gives the identity

$$\begin{aligned} \sum _{u \xrightarrow {\widetilde{p}} u'} C^w_{u',v} = \sum _{v \xrightarrow {\widetilde{p}} v'} C^w_{u,v'} \,, \end{aligned}$$

(6)

for all 012-strings u, v, w for X and integers $p \in [0,a]$.

Proof of Theorem 1

Set $R = M = H^*(X;{\mathbb Z})$ and

$$\begin{aligned} S = \{ [X_{\mathbf p}]{:} 1 \le p \le n-b \} \cup \{ [X_{\widetilde{\mathbf p}}]{:} 1 \le p \le a \}\,. \end{aligned}$$

By using that X is a Grassmann bundle over a Grassmann variety, it follows that R is generated by S. The identity (3) shows that $\mu (1,[X_u]) = [X_u]$, and (4) and (6) together with the Pieri formulas (2) and (5) imply

$$\begin{aligned} \mu ([X_u] \cdot [X_{\mathbf p}], [X_v])= & {} \sum _{u \xrightarrow {p} u'} \mu ([X_{u'}], [X_v])\\= & {} \sum _{v \xrightarrow {p} v'} \mu ([X_u], [X_{v'}]) = \mu ([X_u], [X_{\mathbf p}] \cdot [X_v]) \end{aligned}$$

for all 012-strings u and v for X and $1 \le p \le n-b$, and an analogous identity with $[X_{\widetilde{\mathbf p}}]$ for $1 \le p \le a$. By the bilinearity of $\mu$, this shows that the conditions of Lemma 2.1 are satisfied. We deduce that Eq. (1) holds for all 012-strings u and v, as required. $\square$

3 Multiplication by one

In this section we prove the first claim in Proposition 2.2 and use it to reformulate the puzzle formula in terms of rhombus-shaped puzzles. We need the following lemma.

Lemma 3.1

Let ${\mathbf 0} = (0^{n_0},1^{n_1},2^{n_2})$ be an identity string and let $x \in \{0,1,2\}$ be a simple label that occurs in this string. Then there exists a unique union of matching puzzle pieces of the form

with left label x and bottom labels ${\mathbf 0}$ in right-to-left direction. The right border of this unique puzzle has label x, and the labels on the top border is the identity string ${\mathbf 0'}$ obtained by removing one copy of x from ${\mathbf 0}$.

Proof

We consider each possible value of x in turn. If $x=0$, then the shape must be filled with (unions of) puzzle pieces from the following list:

In fact, if we fill the shape from left to right, then we are forced to place the rhombus (a) above each 2 on the bottom border. After this we must place the rhombus (b) above each 1 on the bottom border; the only alternative rhombus

cannot be used because each 1-label on the bottom border is followed by a 0 or a 1 to the right. Finally, the triangle (c) must be placed above the first 0 on the bottom border, and the rest of the shape must be filled with the rhombus (d).

If $x=1$, then a similar argument shows that the shape must be filled with the (unions of) puzzle pieces:

And if $x=2$, then the shape must be filled with the pieces:

In all three cases exactly one single triangle is used, with the label x on all sides. This accounts for the removed x on the top border. $\square$

The first identity in Proposition 2.2 follows from the following corollary.

Corollary 3.2

Let v be any 012-string for X and let ${\mathbf 0} = (0^a,1^{b-a},2^{n-b})$ be the identity string. Then there exists a unique triangular puzzle with labels ${\mathbf 0}$ on the left border and labels v on the right border, both in clockwise direction.

The bottom labels of this unique puzzle are v, in counter-clockwise direction.

Proof

This follows by induction on the number of rows, using the $120^{\circ }$ clockwise rotation of Lemma 3.1. $\square$

For technical reasons, it is convenient to express the constants $C^w_{u,v}$ in terms of puzzles of rhombus shape. We will use this interpretation in the proof of the second identity of Proposition 2.2.

Corollary 3.3

The constant $C^{w}_{u,v}$ is equal to the number of puzzles of the following rhombus shape, with top border u, right border ${\mathbf 0}$, bottom border v, and left border w, with u, ${\mathbf 0}$, and v in clockwise direction and w in counter-clockwise direction.

Proof

Any such rhombus-shaped puzzle consists of the (rotated) unique puzzle from Corollary 3.2 in the lower-right half and a (rotated) triangular puzzle with border labels u, v, and w in the upper-left half. $\square$

Let u, v, and w be 012-strings for X and let $p \in [0,n-b]$. To prove the second identity of Proposition 2.2, it suffices to construct a bijection between the set of rhombus-shaped puzzles with border labels $u',{\mathbf 0},v,w$ such that $u \xrightarrow {p} u'$, and the set of rhombus-shaped puzzles with border labels $u,{\mathbf 0},v',w$ such that $v \xrightarrow {p} v'$.

We will construct a more general bijection where the top and bottom borders are not required to have simple labels. The advantage of this is that we can restrict our attention to puzzles with a single row. The first ingredient in our construction is an appropriate generalization of the Pieri relation $u \xrightarrow {p} v$ for strings of arbitrary labels. This is the subject of the next section.

4 A Pieri rule for label strings

Define a label string to be any finite sequence $u = (u_1,u_2,\ldots ,u_\ell )$ of integers from the set $[0,7] = \{0,1,2,3,4,5,6,7\}$. These strings are generalizations of the 012-strings that represent Schubert classes on two-step flag varieties. In this section we introduce a generalization of the Pieri relation $u \xrightarrow {p} v$ that has meaning when u and v are arbitrary label strings of the same length.

We start by defining the basic relation $u \xrightarrow {1} v$. This relation implies that v is obtained by changing exactly two entries of u. There are 15 possible rules for how the entries can be changed, and in each case there are restrictions on which entries can appear between the entries being changed. Each rule is determined by a triple $((a_1,b_1), S, (a_2,b_2))$ where $a_1,b_1,a_2,b_2 \in [0,7]$ and $S \subset [0,7]$. The corresponding rule says that, if u contains a substring consisting of $a_1$ followed by any number of integers from S and ending in $a_2$, then one may replace $a_1$ in the substring with $b_1$ and simultaneously replace $a_2$ with $b_2$. We will use the following graphical representation of the rule:

The set S is specified by listing its elements followed by a star to indicate that its elements can be repeated. If S is empty, then the middle third of the line segment is omitted. The complete list of rules is given in Table 1. These rules are organized into six types called A, B, C, D, E, F, (these have no relation to the classification of types in Lie theory!). Notice that just two of the rules relate 012-strings, and these reproduce the definition of $u \xrightarrow {1} v$ from Sect. 2; the remaining rules follow a similar pattern. As we will see in Sect. 5, the complete set of rules defining $u \xrightarrow {1} v$ arises as a subset of the gashes that can occur in propagation algorithm.

Definition 4.1

Let u and v be label strings of the same length. Then the relation $u \xrightarrow {1} v$ holds if and only if v can be obtained from u by using one of the rules in Table 1. In this case we say that the relation $u \xrightarrow {1} v$ has index (i, j), where $i<j$ are the unique integers such that $u_i \ne v_i$ and $u_j \ne v_j$.

Table 1 Rules for the Pieri relation on label strings

Example 4.2

According to the second rule of type D, we have $72{\mathbf 1}3033{\mathbf 5}644 \xrightarrow {1} 72{\mathbf 2}3033{\mathbf 7}644$, and this relation has index (3, 8).

Definition 4.3

Let u and v be label strings of the same length. A Pieri chain from u to v is a sequence $u = u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p = v$ such that, if $u^{t-1} \xrightarrow {1} u^t$ has index $(i_t,j_t)$ for each t, then $i_s < j_t$ whenever $s \le t$. The Pieri chain is right-increasing if it satisfies the stronger condition $j_1< j_2< \cdots < j_p$. We will write $u \xrightarrow {p} v$ if there exists a Pieri chain of length p from u to v.

Example 4.4

We have $04730202245 \xrightarrow {5} 40720522015$, with (right-increasing) Pieri chain $04730202245 \xrightarrow {1} {\mathbf {40}}730202245 \xrightarrow {1} 407{\mathbf 2}0{\mathbf 3}02245 \xrightarrow {1} 407203{\mathbf {20}}245 \xrightarrow {1} 4072032{\mathbf {20}}45 \xrightarrow {1} 40720{\mathbf 5}220{\mathbf 1}5$.

Notice that some swaps of integers in a Pieri chain can happen inside others: for instance, in Example 4.4 the fourth swap (at position (8, 9)) happens inside the fifth (at position (6, 10)). In Sect. 7, this property will be utilized to allow propagation paths to cross each other in a controlled way. The two results below are essential for this application. Notice also that the definitions imply that $u \xrightarrow {p} v$ if and only if $v^\vee \xrightarrow {p} u^\vee$, where $u^\vee$ denotes the label string u in reverse order.

Lemma 4.5

Let $u \xrightarrow {1} v \xrightarrow {1} w$ be a Pieri chain, where $u \xrightarrow {1} v$ has index (i, j) and $v \xrightarrow {1} w$ has index (k, l). Assume that $k < j$. Then we have either $i< k< l < j$, $u \xrightarrow {1} v$ has type E, and $v \xrightarrow {1} w$ has type A, or $k< i< j < l$, $u \xrightarrow {1} v$ has type A, and $v \xrightarrow {1} w$ has type E. Furthermore, there exists a unique label string $v'$ such that $u \xrightarrow {1} v' \xrightarrow {1} w$ is a Pieri chain with the inequalities and types interchanged.

Proof

Assume that $u \xrightarrow {1} v$ follows the rule $((a_1,b_1),S,(a_2,b_2))$ and that $v \xrightarrow {1} w$ follows the rule $((c_1,d_1),T,(c_2,d_2))$, both of which come from Table 1:

Then we have $v_i=b_1$, $v_j=b_2$, $v_k=c_1$, $v_l=c_2$, $v_s\in S$ for $i<s<j$, and $v_s\in T$ for $k<s<l$. By inspection of Table 1 we have $b_1,c_2 \in \{2,4,5,6\}$, $b_2,c_1 \in \{0,1,3,7\}$, and $S \cup T \subset \{0,2,3,4\}$. It follows that i, j, k, l are pairwise distinct integers, and the inequalities $i<j$, $k<l$, $i<l$, $k<j$ allow exactly four possibilities for their relative orderings. We consider these possibilities in turn.

Case 1 Assume that $i<k<j<l$. Then $c_1\in S$ and $b_2 \in T$. Using that $b_2,c_1 \in \{0,1,3,7\} \cap \{0,2,3,4\} = \{0,3\}$, we deduce that both of the applied rules are not of type A, C, D, or F. This in turn implies that $c_1=b_2=3$ and $S\cup T \subset \{0,2\}$, a contradiction.

Case 2 Assume that $k<i<l<j$. This case is impossible by an argument similar to Case 1.

Cases 3 and 4 Assume that $i<k<l<j$ or $k<i<j<l$. Then $c_1,c_2 \in S$ or $b_1,b_2 \in T$, which implies that the types of the rules are as stated in the lemma. In both cases the label string $v'$ is obtained by setting $v'_k=d_1$, $v'_l=d_2$, and $v'_s=u_s$ for $s \ne k,l$. $\square$

Corollary 4.6

Let u and v be label strings of the same length and let $p \in {\mathbb N}$.

• (a) Assume that $u \xrightarrow {p} v$. Then u is a 012-string if and only if v is a 012-string.

• (b) Assume that both u and v are 012-strings. Then the relation $u \xrightarrow {p} v$ of the Pieri rule (2) holds if and only if $u \xrightarrow {p} v$ holds in the sense of label strings.

Proof

Only the rule of type A and the first rule of type D in Table 1 can be applied to a 012-string, and they will replace such a string with a new 012-string. Part (a) and the special case of (b) in which $p=1$ follow from this. Let $u = u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p = v$ be a Pieri chain such that $u^{t-1} \xrightarrow {1} u^t$ has index $(i_t,j_t)$ for each t. Since no relation $u^{t-1} \xrightarrow {1} u^t$ has type E, it follows from Lemma 4.5 that $j_t \le i_{t+1}$ for each t. The general case of part (b) follows from this. $\square$

Proposition 4.7

• (a) Let u and v be label strings with $u \xrightarrow {p} v$. Then there exists a unique right-increasing Pieri chain from u to v.

• (b) Let $u = u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p = v$ be any Pieri chain from u to v, and let $(i_t,j_t)$ be the index of $u^{t-1} \xrightarrow {1} u^t$ for each $t \in [1,p]$. If $j_1 = \min \{j_1,\ldots ,j_p\}$, then $u^1$ belongs to the unique right-increasing Pieri chain from u to v.

Proof

Let $u = u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p = v$ be any Pieri chain, and let $u^{t-1} \xrightarrow {1} u^t$ have index $(i_t,j_t)$. Assume that $j_{t+1} \le j_t$ for some t. Then $i_{t+1} < j_t$, so Lemma 4.5 implies that $i_t< i_{t+1}< j_{t+1} < j_t$. Moreover, there exists a label string $v'$ such that $u^{t-1} \xrightarrow {1} v'$ has index $(i_{t+1},j_{t+1})$ and $v' \xrightarrow {1} u^{t+1}$ has index $(i_t,j_t)$. By replacing $u^t$ with $v'$, we obtain a new Pieri chain where the pairs $(i_t,j_t)$ and $(i_{t+1},j_{t+1})$ are interchanged. We repeat this procedure until $j_1<j_2<\cdots <j_p$. This shows that there exists at least one right-increasing Pieri chain from u to v. If the initial Pieri chain satisfies $j_1 = \min \{j_1,\ldots ,j_p\}$, then the string $u^1$ will never be replaced and will remain unchanged in the right increasing Pieri chain.

To see that the right-increasing Pieri chain is uniquely determined from u and v, assume that the last step $u^{p-1} \xrightarrow {1} v$ follows the rule $((a_1,b_1),S,(a_2,b_2))$, and let (i, j) be the index of the last step. Notice that j is the largest integer for which $u_j \ne v_j$, and we have $(a_2,b_2) = (u_j,v_j)$. This pair determines the type of the rule, which in turn determines the set S. Now i is the largest integer for which $i<j$ and $v_i \notin S$. We have $b_1 = v_i$, and the entire rule is determined by the triple $(b_1,a_2,b_2)$. We now obtain $u^{p-1}$ by applying the inverse rule to v, and by induction there exists a unique right-increasing Pieri chain from u to $u^{p-1}$. $\square$

5 Gashes and swap regions

In this section, we will work with parallelogram-shaped puzzles with a single row, such that the left and right border edges have simple labels. Such puzzles will be called single-row puzzles. We will say that a single-row puzzle has border $(c_1,u,v,c_2)$ if u is the string of labels on the top border from left to right, v is the string of labels on the bottom border from left to right, $c_1$ is the simple label on the left border, and $c_2$ is the simple label on the right border.

Given label strings u and $v'$ of the same length, simple labels $c_1,c_2 \in \{0,1,2\}$, and an integer $p \ge 0$, we will construct a bijection between the set of single-row puzzles with border $(c_1,u',v',c_2)$ for which $u \xrightarrow {p} u'$, and the set of single-row puzzles with border $(c_1,u,v,c_2)$ for which $v \xrightarrow {p} v'$. We start with the simplest case where $p=1$.

Table 2 Gashes allowed in a gashed puzzle

The bijection is formulated in terms of gashed single-row puzzles in which some puzzle pieces next to each other do not have matching labels. More precisely, a gash is a pair of puzzle edges with labels on both sides, together with a connected sequence of edges between them, so that certain conditions are satisfied. The two edges with labels on both sides are called the left leg and the right leg of the gash. By definition, every gash must have one of the types A, B, C, D, E, F, which correspond to the types of the Pieri relations in Table 1, but since the edges of a gash need not all be horizontal, the definitions are not identical. For each type there are a set of choices for the left leg, the middle segment of edges, and the right leg. These choices are listed in Table 2 and may be combined in any way, as long as the orientation of the edges remains as shown, and the height of the gash is at most one, i.e. at most one non-horizontal edge may be included. The labels of the edges in Table 2 should be understood in the same way as for the Pieri relation in the previous section. If a horizontal edge is labeled with a sequence of numbers followed by a star, then any number of connected horizontal edges with labels from the sequence may be included. A non-horizontal edge labeled with a sequence of numbers means a single edge whose label is one of these numbers. Notice that Table 1 lists all possible horizontal gashes.

Example 5.1

Here are two gashes, one of type D and another of type F.

Let P be a single-row puzzle with border $(c_1,u',v',c_2)$ such that $u \xrightarrow {1} u'$. Then the label string $u'$ can be obtained by interchanging two entries of u. Change the corresponding two edges on the top border of P to have the entries of u as their top labels and the entries of $u'$ as their bottom labels. This creates a horizontal gash on the top border of P, and the resulting gashed puzzle contains all the information required by the bijection. We will formulate the bijection as a transformation rule on gashed puzzles. This transformation takes a single-row puzzle with a gash on the top border and changes it by propagating the gash to the bottom border.

If a gash is not on the bottom border of its puzzle, then we define the front edge of the gash as follows. If the gash is horizontal on the top border, then the front edge is the left leg. Otherwise, the front edge is the unique non-horizontal edge of the gash. A propagation is carried out by one or more steps that move the front edge to the right. The labels between the old and new front edges may be changed in the process, and the type of the gash may change as well. The subset of puzzle pieces and edges that are changed is called a swap region, and the change itself is called a swap. The result of the bijection is the gashed puzzle obtained when the gash reaches the bottom border. Before we give the complete list of swap regions and the proof that propagations are well-defined (in Sect. 6), we first consider two examples.

Example 5.2

Let $u = 0241$, $u' = 2041$, and $v' = 5410$. If we start with the unique single-row puzzle with border $(2,u',v',0)$ and use u to introduce a gash on the top border, then this gash is propagated to the bottom border by the following sequence of swaps. Each of these swaps is carried out by applying a unique named swap region.

The swap region that is applied first is called AF. It has the following effect.

The name indicates that a gash of type A is replaced with a gash of type F. A more compact description of this rule is given in the following diagram.

This diagram shows the gashes both before and after the swap. To obtain the region before the swap, one replaces all gashes on the bottom and right sides with their outside labels. The region after the swap is obtained by replacing the gashes on the top and left sides with their outside labels. In both cases the labels of the inner edges are uniquely determined by requiring that the interior of a swap region is a union of puzzle pieces with matching labels. The other two swap regions used in the example are called FF11 and FF9.

Example 5.3

Let $u=1015$, $u'=1027$, and $v'=2031$, consider the unique single-row puzzle with border $(1,u',v',2)$, and use u to create a gash on the top border. In this case the propagation carries out the following sequence of swaps.

This example uses the swap regions DD2, DD11, DD17, and DD7.

The label $0*$ on the first swap region DD2 indicates that the corresponding edges may be repeated any number of times, including zero. The swap region DD11 does not cause any change to the puzzle; it simply allows the front edge of a gash to move to the right.

6 Propagation rules

In this section we give the complete list of swap regions required for carrying out the bijection for $p=1$. At the same time we prove that any gash that is not on the bottom border of its puzzle can be moved to the right by applying a unique swap region. This establishes that the list of swap regions gives a well-defined map on gashed puzzles.

Each gash type comes with its own set of swap regions. More precisely, a swap region may be used only if its name starts with the type of the gash at hand. The proof that the list of swap regions is complete consists of a case-by-case analysis of all possible gashes: we exhaustively consider all cases for how the puzzle may look near the gash and provide a unique swap region to cover every possibility. This analysis is organized by gash type and comprises Sect. 6.1 through 6.6. The reader who does not wish to verify the completeness of the analysis may safely skim these sections. In Sect. 6.7, we record the properties of the list that are essential to the proof of Proposition 2.2.

In the following we assume that we are given a gashed single-row puzzle, such that the gash is not located on the bottom border. We will identify the unique swap region that must be applied to propagate the gash. If the front edge of the gash is not horizontal, then this edge will be the left side of the swap region. Similarly, if applying the swap region results in a new gash that is not on the bottom border, then the front edge of the new gash is taken to be the right side of the swap region. In all cases, the reader should observe that the simplicity of the left and right border labels implies that the indicated swap regions are completely contained in the puzzle.

6.1 Swap regions for a gash of type A

Assume that the gash is of type A. Then it is located on the top border of the puzzle. Let a and b be the labels of the edges going south-west and south-east from the middle node of the gash.

The following table lists all possible values of a and b together with the unique swap region that can be applied in each case. Notice that the ‘Before’ and ‘After’ fields indicate only one particular instance of swap regions that include stretchable edges.

6.2 Swap regions for a gash of type B

Assume now that the gash is of type B, located on the top border of the puzzle. Let a and b be the labels of the edges indicated in the picture.

The table lists the possible values of a and b together with the corresponding swap regions.

6.3 Swap regions for a gash of type C

6.3.1. Assume that the gash has type C and is located at the top border of the puzzle. Let a be the indicated label.

The table lists the possible values of a and the corresponding swap regions.

6.3.2. Assume that the gash has type C with the following shape. Let a and b be the labels of the edges going south-east and east from the top node of the left leg. Notice that b may be the right leg of the gash, in which case the value of b is displayed as $\frac{4}{0}$.

The table lists the possible values of a and b together with the corresponding swap regions.

6.3.3. Assume that the gash has type C with the following shape. The unique applicable swap region is determined by the indicated label a.

6.4 Swap regions for a gash of type D

6.4.1. Assume that the gash has type D and is located on the top border of the puzzle. Let a be the labels of the left leg and let b be the label of the edge going south-west from the right node of the left leg.

The table lists the possible values of a and b and the corresponding swap regions.

6.4.2. Assume that the gash has type D with the following shape.

The unique applicable swap region is determined by the indicated label a.

6.4.3. Assume that the gash has type D with the following shape.

The unique applicable swap region is determined by the indicated label a.

6.4.4. Assume that the gash has type D with the following shape.

The unique applicable swap region is determined by the indicated labels a and b.

6.4.5. Assume that the gash has type D with the following shape (given by the solid black lines).

The unique applicable swap region is determined by the indicated labels a and b.

6.5 Swap regions for a gash of type E

6.5.1. Assume that the gash has type E and is located on the top border of the puzzle. Let a be the labels of the left leg and let b be the label of the edge going south-west from the right node of the left leg.

The table lists the possible values of a and b and the corresponding swap regions.

6.5.2. Assume that the gash has type E with the following shape. Let a be the label of the edge going south-east from the top node of the left leg, and let b be the first non-zero label on the horizontal part of the gash. The following could be the labels of the right leg of the gash.

The table lists the possible values of a and b and the corresponding swap regions. In two cases the value of b is omitted, as it does not influence on the choice of swap region.

6.5.3. Assume that the gash has type E with the following shape.

The unique applicable swap region is determined by the indicated label a.

6.5.4. Assume that the gash has type E with the following shape.

The unique applicable swap region is determined by the indicated labels a and b.

6.5.5. Assume that the gash has type E with the following shape (given by the solid black lines).

The unique applicable swap region is determined by the indicated labels a and b.

6.6 Swap regions for a gash of type F

6.6.1. Assume that the gash has type F and is located on the top border. Then the unique applicable swap region is determined by the labels a of the left leg.

6.6.2. Assume that the gash has type F with the following shape. Let a and b be the labels of the edges going south-east and east from the top node of the left leg. Notice that b may be the labels of the right leg.

The table lists the possible values of a and b together with the corresponding swap regions.

6.6.3. Assume that the gash has type F of the following shape. Then the unique applicable swap region is determined by the indicated label a.

6.7 Properties of the bijection

We finish this section by recording some consequences of the analysis just carried out. Given any single-row puzzle P with a gash on its top border, we let $\Phi (P)$ denote the puzzle obtained by propagating the gash to the bottom border, using the swap regions of this section. For any parallelogram-shaped puzzle P, let $\rho (P)$ denote the $180^{\circ }$ rotation of P.

Proposition 6.1

The assignment $\Phi$ is a well-defined map from the set of single-row puzzles with a gash on the top border into the set of single-row puzzles with a gash on the bottom border. Furthermore, if P is any single-row puzzle with a gash on the top border, then $\rho \, \Phi \, \rho \, \Phi (P) = P$.

Proof

The well definedness of $\Phi$ follows by observing that the swap regions of Sect. 6.1 through 6.6 cover all possible cases. For the second claim, suppose that P is a gashed puzzle and $P'$ is the result of applying a swap region ${\mathcal R}$ to P. An inspection of the swap region tables shows that also the $180^{\circ }$ rotation of ${\mathcal R}$ is a swap region, and this swap region can be applied to $\rho (P')$ to produce $\rho (P)$. If ${\mathcal R}$ is called XY, where X and Y are distinct gash types, then the $180^{\circ }$ rotation of ${\mathcal R}$ is called YX. And if ${\mathcal R}$ is called XXm, where X is a gash type and m is an integer, then the rotation of ${\mathcal R}$ is called XX$m'$ for a (possibly) different integer $m'$. The proposition follows from this. $\square$

Example 6.2

The $180^{\circ }$ rotation of the first propagation in Sect. 5 is carried out with the swap regions FF2, FF4, and FA.

The $180^{\circ }$ rotation of the second propagation in Sect. 5 is carried out with the swap regions DD3, DD5, DD16, and DD12.

We record two additional consequences that are important for the general bijection for $p \ge 2$. Let P be a gashed single-row puzzle with label $c_1$ on the left border and label $c_2$ on the right border. We will say that P has border $(c_1,\frac{u}{u'},v',c_2)$ if P has a horizontal gash on the top border corresponding to the relation $u \xrightarrow {1} u'$, and the bottom border of P has labels $v'$. Similarly we will say that P has border $(c_1,u,\frac{v}{v'},c_2)$ if P has a horizontal gash on the bottom border corresponding to the relation $v \xrightarrow {1} v'$, and the top border of P has labels u.

Lemma 6.3

Let P be a single-row puzzle with a gash on its top border. Let $(c_1,\frac{u}{u'},v',c_2)$ be the border of P, let $(c_1,u,\frac{v}{v'},c_2)$ be the border of $\Phi (P)$, let (i, j) be the index of $u \xrightarrow {1} u'$, and let (k, l) be the index of $v \xrightarrow {1} v'$. Then we have $i \le l$ and $k < j$. Moreover, if one of the relations $u\xrightarrow {1}u'$ or $v\xrightarrow {1}v'$ has type E, then $i-1 \le k$ and $j-1 \le l$.

Proof

The inequalities $i \le l$ and $k < j$ are equivalent to the existence of a non-horizontal puzzle edge e, such that the top node of e separates the left and right legs of the gash on P, and the bottom node of e separates the left and right legs of the gash on $\Phi (P)$. Assume at first that the propagation $P \mapsto \Phi (P)$ involves a swap region ${\mathcal R}$ that moves both legs of the gash. In this case an inspection of the propagation table shows that e may be taken as one of the interior edges of ${\mathcal R}$. Otherwise some intermediate puzzle in the propagation contains a non-horizontal gash whose front edge is different from both of its legs. We may then take e to be the front edge of this gash. If $u\xrightarrow {1}u'$ has type E, then the second claim follows because none of the legs of a gash of type E are able to move more than one step to the left during a propagation. This can be seen by inspecting the swap regions in Sect. 6.5. Finally, if $v\xrightarrow {1}v'$ has type E, then the same argument applies to $\rho \,\Phi (P)$. $\square$

Definition 6.4

Let P be a single-row puzzle with border $(c_1, \frac{u}{u'}, v', c_2)$, and let $(c_1, u, \frac{v}{v'}, c_2)$ be the border of $\Phi (P)$. We will say that the propagation $P \mapsto \Phi (P)$ has type X–Y if the relation $u \xrightarrow {1} u'$ has type X and the relation $v \xrightarrow {1} v'$ has type Y. Given a small triangle $\tau$ of P, the top part of $\tau$ is the intersection of $\tau$ with the top border of P, and the bottom part of $\tau$ is the intersection of $\tau$ with the bottom border of P. One of these ‘parts’ of $\tau$ is a point, and the other is a small horizontal line segment. We will say that $\tau$ is an interior triangle of the propagation $P \mapsto \Phi (P)$ if the top part of $\tau$ is located between the left and right legs of the gash on P, and the bottom part of $\tau$ is located between the left and right legs of the gash on $\Phi (P)$.

Lemma 6.5

Let P be a single-row puzzle with a horizontal gash on the top border, and assume that the propagation $P \mapsto \Phi (P)$ has type E–E. Then all interior triangles are unchanged by this propagation and come from the list:

Proof

This follows by inspection of the swap regions in Sect. 6.5. The triangles on the list correspond to the swap regions EE10, EE12, EE13, EE14, EE15, EE19, EE18, and EE20. $\square$

7 The general bijection

Let P be a single-row puzzle with border $(c_1,u',v',c_2)$ and let u be a label string such that $u \xrightarrow {p} u'$ for some p. We define a new single-row puzzle $\Phi ^u(P)$ as follows. If $u = u'$, then set $\Phi ^u(P) = P$. If $p=1$ and $u \xrightarrow {1} u'$, then let $P'$ be the puzzle obtained from P by changing the border to $(c_1,\frac{u}{u'},v',c_2)$, let $(c_1,u,\frac{v}{v'},c_2)$ be the border of $\Phi (P')$, and let $\Phi ^u(P)$ be the puzzle obtained from $\Phi (P')$ by changing this border to $(c_1,u,v,c_2)$. Otherwise let $u = u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p = u'$ be the unique right-increasing Pieri chain from u to $u'$. By induction on p we may assume that $\Phi ^{u^1}(P)$ has already been defined. We then set $\Phi ^u(P) = \Phi ^u(\Phi ^{u^1}(P))$.

Example 7.1

Let $u \!=\! (1,0,2,4,2,5)$, $u' = (4,2,0,6,2,0)$, and $v' \!=\! (2,5,1,2,2,0)$. We list the intermediate puzzles occurring when the map $\Phi ^u$ is applied to a puzzle with border $(1,u',v',2)$. For each step we have colored the union of the swap regions used to change the puzzle.

Lemma 7.2

Let $\widetilde{u}$ be any label string contained in the unique right-increasing Pieri chain from u to $u'$. Then we have $\Phi ^u(P) = \Phi ^u(\Phi ^{\widetilde{u}}(P))$.

Proof

Let $u = u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {p} u^p = u'$ be the right-increasing Pieri chain. It follows from the definition that $\Phi ^u(P) = \Phi ^u(\Phi ^{u^1}(P))$. If $\widetilde{u} \ne u$, then $\widetilde{u}$ is contained in the unique right-increasing Pieri chain from $u^1$ to $u'$, so by induction on p we obtain $\Phi ^u(\Phi ^{u^1}(P)) = \Phi ^u(\Phi ^{u^1}(\Phi ^{\widetilde{u}}(P))) = \Phi ^u(\Phi ^{\widetilde{u}}(P))$, as required. $\square$

Lemma 7.3

Let P be a single-row puzzle with border $(c_1,u^p,v^p,c_2)$, and let $u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p$ be a right-increasing Pieri chain. Let $(c_1,u^t,v^t,c_2)$ be the border of $\Phi ^{u^t}(P)$ for each $t \in [0,p]$. Then $v^0 \xrightarrow {1} v^1 \xrightarrow {1} \cdots \xrightarrow {1} v^p$ is a Pieri chain.

Before we prove Lemma 7.3, we emphasize that the produced Pieri chain $v^0 \xrightarrow {1} v^1 \xrightarrow {1} \cdots \xrightarrow {1} v^p$ is not necessarily right increasing; when this occurs, we say that the propagation paths cross. In addition, the lemma is false without the assumption that the Pieri chain $u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p$ is right increasing. These points are essential to how propagation paths are allowed to cross each other in a controlled way.

Proof

Since $\Phi ^{u^{t-1}}(P) = \Phi ^{u^{t-1}}(\Phi ^{u^t}(P))$ by Lemma 7.2, it follows from the definition of $\Phi$ in Sect. 6 that $v^{t-1} \xrightarrow {1} v^t$ for each $t \in [1,p]$. Let $(i_t,j_t)$ be the index of $u^{t-1} \xrightarrow {1} u^t$, and let $(k_t,l_t)$ be the index of $v^{t-1} \xrightarrow {1} v^t$ for each t. Then we have $j_1< j_2< \cdots < j_p$ by assumption, and Lemma 6.3 implies that $i_t \le l_t$ and $k_t < j_t$ for each t. Let $1 \le s < t \le p$; we must show that $k_s < l_t$. If $j_{t-1} \le i_t$, then this is true because $k_s < j_s \le j_{t-1} \le i_t \le l_t$. Otherwise, it follows from Lemma 4.5 that $u^{t-1} \xrightarrow {1} u^{t}$ has type E, so Lemma 6.3 implies that $j_t-1 \le l_t$. In this case we obtain $k_s < j_s \le j_t-1 \le l_t$, as required. $\square$

Corollary 7.4

Let P be a single-row puzzle with border $(c_1,u',v',c_2)$ such that $u \xrightarrow {p} u'$ for some u and p, and let $(c_1,u,v,c_2)$ be the border of $\Phi ^u(P)$. Then $v \xrightarrow {p} v'$.

Proof

This follows from Lemma 7.3. $\square$

Notice that if we turn the last puzzle in Example 7.1 upside-down and apply $\Phi ^{{v'}^\vee }$, then the sequence of propagations in the example will be undone in reverse order. However, when the propagation paths cross, we get a slightly different propagation order. This occurs when a propagation of type A–A is carried out inside a propagation of type E–E.

Example 7.5

We show the steps involved in applying $\Phi ^u$ to a single-row puzzle with border $(0,u',v',0)$, where $u = (3,0,0,2,2,4)$, $u' = (5,0,2,2,0,1)$, and $v' = u^\vee$. The first step is a propagation of type E–E, while the second and third steps are propagations of type A–A.

Notice that the resulting puzzle is equal to the $180^{\circ }$ rotation of the initial puzzle P, so we have $\rho \, \Phi ^u \rho \, \Phi ^u(P) = P$. However, the second application of $\Phi ^u$ does not undo the propagations of the first application of $\Phi ^u$ in the expected reverse order. This is the main issue in the proof of Proposition 7.6 below.

Let Q be a single-row puzzle with border $(c_1,u,v,c_2)$ such that $v \xrightarrow {p} v'$ for some $v'$ and p. Then we define $\Phi _{v'}(Q) = \rho \, \Phi ^{{v'}^\vee }\!\rho (Q)$. Lemma 7.3 implies that this puzzle has border $(c_1,u',v',c_2)$ for a label string $u'$ with $u \xrightarrow {p} u'$.

Proposition 7.6

Let P be a single-row puzzle with border $(c_1,u',v',c_2)$ and let u be a label string such that $u \xrightarrow {p} u'$ for some p. Then we have $\Phi _{v'}(\Phi ^u(P)) = P$.

Proof

We proceed by induction on p. The statement is clear if $p=0$, and for $p=1$ it follows from Proposition 6.1. Assume that $p \ge 2$ and let $u = u^0 \xrightarrow {1} u^1 \xrightarrow {1} \cdots \xrightarrow {1} u^p = u'$ be the unique right-increasing Pieri chain. For each $t \in [0,p]$ we set $P_t = \Phi ^{u^t}(P)$, and we let $(c_1,u^t,v^t,c_2)$ be the border of this puzzle. Then $v = v^0 \xrightarrow {1} v^1 \xrightarrow {1} \cdots \xrightarrow {1} v^p = v'$ is a Pieri chain by Lemma 7.3. Let $(i_t,j_t)$ be the index of $u^{t-1} \xrightarrow {1} u^t$ and let $(k_t,l_t)$ be the index of $v^{t-1} \xrightarrow {1} v^t$.

Assume first that $k_p = \max \{k_1,\ldots ,k_p\}$. Then it follows from Proposition 4.7(b) and Lemma 7.2 that $\Phi _{v'}(P_0) = \Phi _{v'}(\Phi _{v^{p-1}}(P_0))$. Since $P_0 = \Phi ^u(P_{p-1})$, we obtain from the induction hypothesis that $\Phi _{v^{p-1}}(P_0) = P_{p-1}$. We deduce that $\Phi _{v'}(\Phi ^u(P)) = \Phi _{v'}(P_0) = \Phi _{v'}(\Phi _{v^{p-1}}(P_0)) = \Phi _{v'}(P_{p-1}) = P$, as required.

Otherwise, we have $k_p < k_s$ for some $s \le p-1$. Since $\{ v^t \}$ is a Pieri chain, this implies that $k_p+1 \le k_s < \min (l_{p-1},l_p)$. It follows that the relation $v^{p-1} \xrightarrow {1} v^p$ is not of type A, and Lemma 4.5 implies that $k_p< k_{p-1}< l_{p-1} < l_p$, the relation $v^{p-2} \xrightarrow {1} v^{p-1}$ has type A, and $v^{p-1} \xrightarrow {1} v^p$ has type E. Lemma 6.3 now implies that $i_p \le k_p+1 \le k_{p-1} < j_{p-1}$, so another application of Lemma 4.5 shows that $i_p< i_{p-1}< j_{p-1} < j_p$, the relation $u^{p-2} \xrightarrow {1} u^{p-1}$ has type A, and the relation $u^{p-1} \xrightarrow {1} u^p$ has type E. Notice also that $k_t \le l_{p-1}-1 = k_{p-1}$ for each $t \in [1,p-1]$, so $k_{p-1} = \max \{k_1,\ldots ,k_p\}$.

The propagation $P = P_p \mapsto P_{p-1}$ is carried out by first changing the border of $P_p$ to $(c_1, \frac{u^{p-1}}{u^p}, v^p, c_2)$, then applying $\Phi$, and finally changing the border of the resulting puzzle to $(c_1,u^{p-1},v^{p-1},c_2)$. This application of $\Phi$ is therefore a propagation of type E–E. Furthermore, the step $P_{p-1} \mapsto P_{p-2}$ is carried out by changing the border of $P_{p-1}$ to $(c_1, \frac{u^{p-2}}{u^{p-1}}, v^{p-1}, c_2)$, applying $\Phi$, and changing the border of the result to $(c_1,u^{p-2},v^{p-2},c_2)$. Here, the application of $\Phi$ is a propagation of type A–A, which can happen only by applying a single swap region ${\mathcal R}$ of type AA1, AA2, AA3, or AA4. Notice that all small triangles of ${\mathcal R}$ (before the swap) must be interior triangles to the propagation $P_p \mapsto P_{p-1}$ of type E–E. We therefore deduce from Lemma 6.5 that ${\mathcal R}$ must have type AA1 or AA4. Since the triangles after a swap of type AA1 or AA4 are also on the list of Lemma 6.5, the E–E and A–A propagations can be carried out in the opposite order with the same result.

More precisely, let $\widetilde{u}$ be the unique label string described in Lemma 4.5, so that $u^{p-2} \xrightarrow {1} \widetilde{u} \xrightarrow {1} u'$ is a Pieri chain, $u^{p-2} \xrightarrow {1} \widetilde{u}$ has type E, and $\widetilde{u} \xrightarrow {1} u'$ has type A. Similarly, let $\widetilde{v}$ be the unique label string such that $v^{p-2} \xrightarrow {1} \widetilde{v} \xrightarrow {1} v'$ is a Pieri chain, $v^{p-2} \xrightarrow {1} \widetilde{v}$ has type E, and $\widetilde{v} \xrightarrow {1} v'$ has type A. Now set $\widetilde{P} = \Phi ^{\widetilde{u}}(P)$. Then $\widetilde{P}$ has border $(c_1,\widetilde{u},\widetilde{v},c_2)$ and $\Phi ^{u^{p-2}}(\widetilde{P}) = P_{p-2}$.

Using that $u^0 \xrightarrow {1} \cdots \xrightarrow {1} u^{p-2} \xrightarrow {1} \widetilde{u}$ is a right-increasing Pieri chain, we obtain $P_0 = \Phi ^u(P_{p-2}) = \Phi ^u(\Phi ^{u^{p-2}}(\widetilde{P})) = \Phi ^u(\widetilde{P})$. Since $v^0 \xrightarrow {1} \cdots \xrightarrow {1} v^{p-2} \xrightarrow {1} \widetilde{v} \xrightarrow {1} v'$ is a Pieri chain and $\widetilde{v} \xrightarrow {1} v'$ has index $(k_{p-1},l_{p-1})$ with $k_{k-1} = \max \{k_1,\ldots ,k_p\}$, we obtain from Proposition 4.7(b) and Lemma 7.2 that $\Phi _{v'}(P_0) = \Phi _{v'}(\Phi _{\widetilde{v}}(P_0))$. Finally, since the induction hypothesis implies that $\Phi _{\widetilde{v}}(P_0) = \Phi _{\widetilde{v}}(\Phi ^u(\widetilde{P})) = \widetilde{P}$, we obtain $\Phi _{v'}(\Phi ^u(P)) = \Phi _{v'}(P_0) = \Phi _{v'}(\Phi _{\widetilde{v}}(P_0)) = \Phi _{v'}(\widetilde{P}) = P$, as required. $\square$

Proof of Proposition 2.2

The identity (3) follows from Corollary 3.2. Let u, $v'$, $w_1$, and $w_2$ be 012-strings and let $p \in {\mathbb N}$. We will say that a parallelogram-shaped puzzle has border $(w_1,u,v',w_2)$ if u gives the labels of the top border, $v'$ gives the labels of the bottom border, $w_1$ gives the labels of the left border, and $w_2$ gives the labels of the right border, all in north-west to south-east order. Recall from Sect. 3 that to prove the identity (4) it suffices to construct a bijection between the set of parallelogram-shaped puzzles with border $(w_1,u',v',w_2)$ such that $u \xrightarrow {p} u'$, and the set of parallelogram-shaped puzzles with border $(w_1,u,v,w_2)$ such that $v \xrightarrow {p} v'$. We do this by modifying one row at the time.

Given a parallelogram-shaped puzzle $P'$ with border $(w_1,u',v',w_2)$, let n be the number of rows in this puzzle, let $P'_i$ be the subpuzzle in the i-th row for $1 \le i \le n$ (counted from top to bottom), and let $(c_i,{u'}^{i-1},{u'}^i,c'_i)$ be the border of $P'_i$. Then ${u'}^0 = u'$ and ${u'}^n = v'$. Set $u^0 = u$ and $P_1 = \Phi ^{u^0}(P'_1)$. Assume inductively that $P_1,\ldots ,P_i$ have already been defined. Then let $(c_i,u^{i-1},u^i,c'_i)$ be the border of $P_i$ and set $P_{i+1} = \Phi ^{u^i}(P'_{i+1})$. Finally, let $\Phi ^u(P')$ be the union of the rows $P_i$ for $i \in [1,n]$, and let v be the labels of the bottom border of this puzzle. Then $\Phi ^u(P')$ is a valid puzzle with border $(w_1,u,v,w_2)$ such that $v \xrightarrow {p} v'$. Finally, it follows from Proposition 7.6 that $\rho \, \Phi ^{{v'}^\vee } \! \rho \, \Phi ^u (P') = P'$, which implies that the map $P' \mapsto \Phi ^u(P')$ is a bijection. $\square$

Example 7.7

Here is an example of the bijection in the proof of Proposition 2.2 in a case where two propagation paths cross each other.

Here is what happens if the propagations are carried out one after another: that is, each gash is allowed to propagate to the bottom of the puzzle before the next propagation begins.

Notice that the resulting 012-strings $v = (2,0,1,2)$ and $v' = (2,2,0,1)$ on the bottom border do not satisfy $v \xrightarrow {2} v'$. This illustrates why several propagations must be handled simultaneously and in the correct sequence, in order to obtain a proof of Proposition 2.2.

8 A quantum Littlewood–Richardson rule

Let $Y={\mathrm G}(m,n)$ denote the Grassmannian parametrizing m-dimensional complex linear subspaces of ${\mathbb C}^n$. The Schubert varieties $Y_u$ in Y and their classes $[Y_u]$ in $H^*(Y,{\mathbb Z})$ may be indexed by 02-strings $u=(u_1,\ldots , u_n)$ with m zeroes and $n-m$ twos. The codimension of $Y_u$ in Y is equal to the number of inversions $\ell (u)$.

Let u, v, and w be three 02-strings as above and fix a nonnegative integer d such that $\ell (u)+\ell (v)+\ell (w)= m(n-m)+nd$. The three-point, genus zero Gromov–Witten invariant $\langle [Y_u], [Y_v], [Y_w] \rangle _d$ may be defined as the number of rational maps $f:{\mathbb P}^1\rightarrow Y$ of degree d such that $f(0)\in Y_u$, $f(1)\in Y_v$, and $f(\infty )\in Y_w$, whenever the Schubert varieties $Y_u$, $Y_v$, and $Y_w$ are taken to be in general position. When $d=0$, we have that $\langle [Y_u], [Y_v], [Y_w] \rangle _0$ is equal to the triple intersection number $\int _Y[Y_u]\cdot [Y_v]\cdot [Y_w]$, which is a Schubert structure constant in the cohomology of the Grassmannian Y, and given by the classical Littlewood–Richardson rule. In general, the invariants $\langle [Y_u], [Y_v], [Y_w] \rangle _d$ are Schubert structure constants in the small quantum cohomology ring of Y, which is a q-deformation of $H^*(Y,{\mathbb Z})$.

If $d \le \min (m,n-m)$, define a 012-string $u_d$ by changing the first d twos and the last d zeroes of u to ones. For example, if $Y={\mathrm G}(4,10)$, $d=2$, and $u=2,022,020,202$, then $u_d=1,012,021,212$. We similarly define the 012-strings $v_d$ and $w_d$. Our main theorem may now be used to establish the following conjecture of Buch, Kresch, and Tamvakis from [2, section 2.4].

Theorem 2

(Quantum Littlewood–Richardson rule) Let $Y_u$, $Y_v$, and $Y_w$ be Schubert varieties in $\mathrm {G}(m,n)$, and suppose that $\ell (u)+\ell (v)+\ell (w)= m(n-m)+nd$. The Gromov–Witten invariant $\langle [Y_u], [Y_v], [Y_w] \rangle _d$ is equal to the number of triangular puzzles for which $u_d$, $v_d$, and $w_d$ are the labels on the left, right, and bottom sides, in clockwise order, when $d \le \min (m,n-m)$, and is zero otherwise.

Proof

The 012-strings $u_d$, $v_d$, and $w_d$ index Schubert varieties $X_{u_d}$, $X_{v_d}$, and $X_{w_d}$ in the two-step flag variety $\mathrm {Fl}(m-d,m+d;n)$. According to [2, Corollary 1] we have

$$\begin{aligned} \langle [Y_u], [Y_v], [Y_w] \rangle _d = \int _{\mathrm {Fl}(m-d,m+d;n)} [X_{u_d}] \cdot [X_{v_d}] \cdot [X_{w_d}]. \end{aligned}$$

The desired result follows by applying Theorem 1. $\square$