Product and puzzle formulae for GL n Belkale-Kumar coefficients

Product and puzzle formulae for GL _n Belkale-Kumar coefficients

Allen Knutson

Department of Mathematics Cornell University Ithaca, New York, USA allenk@math.cornell.edu

Kevin Purbhoo

Combinatorics & Optimization Department University of Waterloo

Waterloo, Ontario, Canada kpurbhoo@math.uwaterloo.ca

Submitted: Oct 1, 2010; Accepted: Mar 24, 2011; Published: Mar 31, 2011 Mathematics Subject Classificaion: 05E10

Abstract

The Belkale-Kumar product onH^∗(G/P)is a degeneration of the usual cup product on the cohomology ring of a generalized flag manifold. In the case G= GL_n, it was used by N. Ressayre to determine the regular faces of the Littlewood-Richardson cone.

We show that forG/Pa(d−1)-step flag manifold, each Belkale-Kumar structure constant is a product of ^d₂

Littlewood-Richardson numbers, for which there are many formulae available, e.g. the puzzles of [Knutson-Tao ’03]. This refines previously known factor- izations intod−1factors. We define a new family of puzzles to assemble these to give a direct combinatorial formula for Belkale-Kumar structure constants.

These “BK-puzzles” are related to extremal honeycombs, as in [Knutson-Tao-Woodward

’04]; using this relation we give another proof of Ressayre’s result.

Finally, we describe the regular faces of the Littlewood-Richardson cone on which the Littlewood-Richardson number is always1; they correspond to nonzero Belkale-Kumar coefficients on partial flag manifolds where every subquotient has dimension1or2.

1 Introduction, and statement of results

Let 0 = k0 < k1 < k2 < . . . < kd = n be a sequence of natural numbers, and Fℓ(k₁, . . . , kd) be the space of partial flags{(0 < V₁ < . . . < Vd =Cⁿ) : dimVi =ki}in Cⁿ.

∗AK was supported by NSF grant 0303523.

†KP was supported by an NSERC discovery grant.

Schubert varieties onFℓ(k1, . . . , kd)are indexed by certain words σ=σ1. . . σnon a totally ordered alphabet of sized(primarily, we will use{1, 2, . . . , d}). Thecontentofσ is the sequence(n1, n2, . . . , nd), whereniis the number ofis inσ. We associate to σa permutationwσ, whose one-line notation lists the positions of the1s in order, followed by the positions of the2s, and so on (e.g. w12312 = 14253; ifσis the one-line notation of a permutation, i.e. ∀i,n_i= 1, thenw_σ =σ⁻¹). We say that(p, q)is aninversionof σifp < q,wσ(p)> wσ(q); more specifically(p, q)is anij-inversionif additionally we haveσq=i > j=σp. Letinv(σ)(resp.inv_ij(σ)) denote the number of inversions (resp.

ij-inversions) ofσ.

Given a word σof content (k1, k2−k1, . . . , kd−kd−1), and a complete flagF•, the Schubert varietyXσ(F•)⊂Fℓ(k₁, . . . , kd)is defined to be the closure of

(0 < V₁< . . . < V_d) : (V_σp ∩F_n−p+1)6= (V_σp ∩Fn−p)forp=1, . . . , n .

(In many references, this is the Schubert variety associated to wσ.) With these con- ventions, the codimension ofXσ(F•)isinv(σ); hence the corresponding Schubert class, denoted[X_σ], lies inH^2inv(σ)(Fℓ(k₁, . . . , k_d)).

Letπ, ρ, σbe words with the above content. TheSchubert intersection number c_πρσ=

Z

Fℓ(k1,...,kd)

[X_π][X_ρ][X_σ]

counts the number of points in a triple intersectionXπ(F•)∩Xρ(G•)∩Xσ(H•), when this intersection is finite and transverse. These numbers are also the structure constants of the cup product for the cohomology ringH^∗(Fℓ(k1, . . . , kd). Writec^σ_πρ :=c_πρσ^∨, where σ^∨isσreversed. The correspondence[X_σ]7→[X_σ^∨]takes the Schubert basis to its dual under the Poincar´e pairing, and so

[X_π][X_ρ] =X

σ

c^σ_πρ[X_σ]

inH^∗(Fℓ(k1, . . . , kd)).

We are interested in a different product structure onH^∗(Fℓ(k₁, . . . , kd)), theBelkale- Kumar product[BeKu06],

[Xπ]⊙0[Xρ] =X

σ

e c^σ_πρ[Xσ]

whose structure constants can be defined as follows (see proposition 2):

e c^σ_πρ=

c^σ_πρ ifinv_ij(π) +inv_ij(ρ) =inv_ij(σ)for1≤j < i≤d

0 otherwise. (1)

If our flag variety is a Grassmannian, this coincides with the cup product; otherwise, it can be seen as a degenerate version. The Belkale-Kumar product has proven to be the more relevant product for describing the Littlewood-Richardson cone (recalled in§4).

Our principal results are a combinatorial formula for the Belkale-Kumar structure constants, and using this formula, a way to factor each structure constant as a product of ^d₂

Littlewood-Richardson coefficients.¹ There are multiple known factorizations (such as in [Ri09]) intod−1factors, of which this provides a common refinement.

The factorization theorem is quicker to state. For S ⊂ {1, . . . , d}, define the S- deflation D_S(σ) of σ to be the word on the totally ordered alphabet S obtained by deleting lettersnot inσ. In particularDij(σ)has only the letters iandj.

Theorem 3.(in§3) Letπ, ρ, σbe words with the same content. Then e

c^σ_πρ=Y

i>j

c^D_D^ijσ

ijπ,Dijρ.

The opposite extreme from Grassmannians is the case of a full flag manifold. Then the theorem says that[Xπ]⊙0[Xρ]is nonzero only ifπandρ’s inversion sets are disjoint, and their union is an inversion set of another permutationσ. In that case,[Xπ]⊙0[Xρ] = [X_σ], in agreement with [BeKu06, corollary 44] and [Ri09, corollary 4].

We prove this theorem by analyzing a combinatorial model for Belkale-Kumar co- efficients, which we callBK-puzzles.² Define the twopuzzle piecesto be

1. A unit triangle, each edge labeled with the same letter from our alphabet.

2. A unit rhombus (two triangles glued together) with edges labeledi, j, i, jwhere i > j, as in figure 1.

They may be rotated in 60^◦ increments, but not reflected because of thei > jrequire- ment.

i j i i

i i

j

Figure 1: The two puzzle pieces. On the rhombus,i > j.

A BK-puzzleis a triangle of side-length nfilled with puzzle pieces, such that ad- joining puzzle pieces have matching edge labels. An example is in figure 2. We will occasionally have need ofpuzzle duality: if one reflects a BK-puzzle left-rightandre- verses the order on the labels, the result is again a BK-puzzle.

1Since finishing this paper, we learned that N. Ressayre had been circulating a conjecture that some such factorization formula should exist.

2In 1999, the first author privately circulated a puzzle conjecture for full Schubert calculus, not just the BK product, involving more puzzle pieces, but soon discovered a counterexample. The2-step flag manifold subcase of that conjecture seems likely to be true; it has been checked up to n = 16 (see [BuKrTam03]).

1 1

1 1

1

1 1 2 2 1

3

3 2

2

2 2 2

2 3 3 3

3 2

1 1 1 1

1 3 2

2 2 2 2 1 1

2

Figure 2: A BK-puzzle whose existence shows thatec³²¹²¹12132,23112≥ 1. (In fact it is1). The edge orientations are explained in§4.

Theorem 1.(in§3) The Belkale-Kumar coefficientec^σ_πρis the number of BK-puzzles withπon the NW side,ρon the NE side,σon the S side, all read left to right.

Puzzles were introduced in [KnTao03, KnTaoWo04], where the labels were only al- lowed to be0, 1. In this paper BK-puzzles with only two numbers will be calledGrass- mannian puzzles. As we shall see, most of the structural properties of Grassmannian puzzles hold for these more general BK-puzzles. Theorem 2 corresponds a BK-puzzle to a list of ^d₂

Grassmannian puzzles, allowing us to prove theorem 3 from theorem 1.

Call a BK-puzzlerigidif it is uniquely determined by its boundary, i.e. if the corre- sponding structure constant is1. Theorem D of [Re10], plus the theorem above, then says that regular faces of the Littlewood-Richardson cone (defined in§4) correspond to rigid BK-puzzles. We indicate an independent proof of this result, and in§5 determine which regular faces hold the Littlewood-Richardson coefficients equaling1.

Acknowledgments

We thank Shrawan Kumar for correspondence on the BK product, and Nicolas Ressayre and Mike Roth for suggesting some references. The honeycomb-related work was de- veloped a number of years ago with Terry Tao, without whom this half of the paper would have been impossible.

2 The Belkale-Kumar product on H

(Fℓ(k

, . . . , k

))

For the moment let G be a general complex connected reductive Lie group, and P a parabolic with Levi factor Land unipotent radicalN. Very shortly we will specialize to theG=GLncase.

Proposition 1. The Schubert intersection number cπρσ is non-zero if and only if there exist a1, a2, a3∈Psuch that

n = (a₁n_πa⁻¹₁ )⊕(a₂n_ρa⁻¹₂ )⊕(a₃n_σa⁻¹₃ ). (2) The definition of n_σ for G = GLn will be given shortly. Briefly, proposition 1 is proven by interpreting n_σas the conormal space at a smooth point (V₁ < . . . < Vd) to some Schubert varietyXσ(F•). The condition (2) measures whether it is possible to make(V1< . . . < Vd)a transverse point of intersection of three such Schubert varieties.

See [BeKu06] or [PuSo08] for details.

Belkale and Kumar define the triple(π, ρ, σ)to beLevi-movableif there exista1, a2, a3∈Lsuch that (2) holds. Using this definition, they consider the numbers

e cπρσ:=

cπρσ if(π, ρ, σ)is Levi-movable 0 otherwise,

and show that the numbersec^σ_πρ =ec_πρσ^∨ are the structure constants of a commutative, associative product onH^∗(G/P).

Our first task is to show that, in our special caseG = GLn, this definition of ec^σ_πρis equivalent to the definition (1) given in the introduction. In this context P ⊂ GL_n is the stabilizer of a coordinate flag(V₁ < . . . < Vd) ∈Fℓ(k₁, . . . , kd), andN⊂GL_nis the unipotent Lie group with Lie algebra

n ={A∈Mat_n:Apq=0ifp > kj−1,q≤kjfor somej}.

We denote the set (not the number) of all inversions of a wordσ (resp. ij-inversions) byInv(σ)(resp. Inv_ij(σ)). Definen_σ⊂ n to be the subspace spanned by{e_pq : (p, q) ∈ Inv(σ)}; here epq ∈ Mat_n denotes the matrix with a 1 in row p, column q, and 0s elsewhere.

Proposition 2. The triple(π, ρ, σ^∨)is Levi-movable if and only ifc^σ_πρ6=0and for all1≤j <

i ≤d, we have

inv_ij(π) +inv_ij(ρ) =inv_ij(σ).

Proof. By duality (replacingσbyσ^∨), we may rephrase this as follows. Assumecπρσ6=

0. We must show that(π, ρ, σ)is Levi-movable iff for alli > j,

inv_ij(π) +inv_ij(ρ) +inv_ij(σ) = (k_i−ki−1)(k_j−kj−1). (3) The center ofL=∼ Qd

i=1GL(n_i)is ad-torus, and acts onnby conjugation. This action defines a weight function on the standard basis forn, which may be written:wt(e_pq) = yj−yiwhere ki−1 < q ≤ ki and kj−1 < p ≤ kj. In particular, we have wt(epq) = yj−yiif (p, q)is an ij-inversion of π, ρorσ. The action of the center ofL, and hence the weight function, extends to the exterior algebraV∗

(n). The weights are partially ordered: Pd

i=1αiyiis higherthanPd

i=1βiyiif their difference is in the cone spanned by{yi−yi+1}i=1,...,d−1.

Let Λπ = V

(p,q)∈Inv(π)epq and Λ^ij_π = V

(p,q)∈Inv_ij(π)epq, with Λρ, Λ^ij_ρ, etc. defined analogously. By proposition 1, there exista₁, a₂, a₃∈Psuch that

a1Λπa⁻¹₁ ∧a2Λρa⁻¹₂ ∧a3Λσa⁻¹₃ 6=0 (4) Writeam = bmcmwhere bm ∈ N, cm∈ L, m =1, 2, 3. Note thatcmepqc⁻¹_m is a sum of terms of the same weight ase_pq, and that

amepqa⁻¹_m =cmepqc⁻¹_m +terms of higher weight.

Hence the left hand side of (4) can be written as

c1Λπc⁻¹₁ ∧c2Λρc⁻¹₂ ∧c3Λσc⁻¹₃ +terms of higher weight. (5) Now V^dim(n)

(n) has only one weight, which is P

i>j(k_i−ki−1)(k_j −kj−1)(y_j−y_i). If (3) holds, then the first term of (5) has this weight, and the terms of higher weight are zero; thus

c₁Λ_πc⁻¹₁ ∧c₂Λ_ρc⁻¹₂ ∧c₃Λ_σc⁻¹₃ =a₁Λ_πa⁻¹₁ ∧a₂Λ_ρa⁻¹₂ ∧a₃Λ_σa⁻¹₃ 6=0 , which shows that(π, ρ, σ)is Levi-movable.

Conversely, if (π, ρ, σ)is Levi-movable, then there exist a1, a2, a3 ∈ Lsuch that (4) holds. SinceΛπ=V

i>jΛ^ij_π, we have

a1Λ^ij_πa⁻¹₁ ∧a2Λ^ij_ρa⁻¹₂ ∧a3Λ^ij_σa⁻¹₃ 6=0

for all i > j. Since the action of L on n preserves the weight spaces, this calculation is happening insideV∗

yj−yiweight space ofn

. This weight space has dimension (k_i−ki−1)(k_j−kj−1), so

inv_ij(π) +inv_ij(ρ) +inv_ij(σ)≤(k_i−k_i−1)(k_j−kj−1).

If any of these inequalities were strict, then summing them would yieldinv(π)+inv(ρ)+

inv(σ) < dim(Fℓ(k₁, . . . , kn)). But this contradicts cπρσ 6= 0, and hence we deduce (3).

Remark1. Belkale and Kumar give a different numerical criterion for Levi-movability [BeKu06, theorem 15]. When expressed in our notation, their condition asserts that (π, ρ, σ^∨)is Levi-movable iffc^σ_πρ6=0and for all1≤l < d,

X

j≤l<i

inv_ij(π) +inv_ij(ρ) −inv_ij(σ)

=0 .

It is is an interesting exercise to show combinatorially that this is equivalent to the condition in proposition 2.

Recall from the introduction the deflation operations DSon words. Next, consider an equivalence relation ∼ on {1, . . . , d}such that i ∼ j, i > l > j =⇒ i ∼ l ∼ j, and defineA∼(σ) :=σ/∼(whereAintroducesAmbiguity).

Given such an equivalence relation, letS1 < S2 < . . . < Sd^′ be the (totally ordered) equivalence classes of∼, and letk_i^′ =k^max(Si). There is a natural projection

α∼:Fℓ(k1, . . . , kd)→Fℓ(k₁^′ . . . , k_d^′′). whose fibres are isomorphic to products of partial flag varieties:

Fℓ(kj:j∈S1)×Fℓ(kj−k₁^′ :j∈S2)× · · · ×Fℓ(kj−k_d^′′−1:j∈Sd^′).

The image of a Schubert varietyXσ(F•)is the Schubert varietyXA∼(σ)(F•). The fibre over a smooth point(V₁^′ < . . . < V_d^′′)is a product of Schubert varietiesXD_S1(σ)×· · ·×XDS

d′(σ). We will denote this fibre byXD∼(σ)(F•, V^′).

It is easy to verify that

codimXD∼(σ)(F•, V^′) =X

i∼j

inv_ij(σ) (6)

codimXA∼(σ)(F•) =X

i≁j

inv_ij(σ). (7)

The main result we’ll need in subsequent sections is the next lemma. We sketch a proof here; a more detailed proof can be found in [Ri09, Theorem 3].

Lemma 1. Assume(π, ρ, σ^∨)is Levi-movable. Then e

c^σ_πρ=ec^A_A^∼_∼^(σ)_(π)A∼(ρ)·

d^′

Y

m=1

e c^D_D^Sm(σ)

Sm(π)D_Sm(ρ).

Proof. First observe that for generic complete flagsF•, G•, H•, the intersections

Xπ(F•)∩Xρ(G•)∩X_σ^∨(H•) (8) X_A∼(π)(F•)∩X_A∼(ρ)(G•)∩X_A∼(σ^∨)(H•) (9) XD∼(π)(F•, V^′)∩XD∼(ρ)(G•, V^′)∩X_D∼(σ^∨)(H•, V^′) (10) are all finite and transverse. (In (10),V^′ is any point of (9).) The fact that the expected dimension of each intersection is finite can be seen using (6), (7) and proposition 2.

Transversality follows from Kleiman’s transversality theorem. For (8) and (9) this is a standard argument; for (10), we use the fact a Levi subgroup of the stabilizer ofV^′acts transitively on the fibreα⁻¹∼ (V^′).

This shows that the number of points in (8) is the product of the numbers of points in (9) and (10), i.e.

c^σ_πρ=c^A_A^∼_∼^(σ)_(π)A∼(ρ)·

d^′

Y

m=1

c^D_D^Sm(σ)

Sm(π)D_Sm(ρ).

Again, using proposition 2, we find that(A^∼(π), A^∼(ρ), A^∼(σ^∨))and(DSm(π), DSm(ρ), DSm(σ^∨)),m =1, . . . , d^′, are Levi-movable; hence we may add tildes everywhere.

3 BK-puzzles and their disassembly

Say that two puzzle pieces in a BK-puzzleP of exactly the same type, and sharing an edge, arein the same region, and let the decomposition intoregionsbe the transitive closure thereof. Each region is either made of(i, i, i)triangles, and called ani-region, or(i, j, i, j)-rhombi, and called an(i, j)-region.

The basic operation we will need on BK-puzzles is “deflation” [KnTaoWo04, §5], extending the operationDSdefined in the introduction on words.

Proposition 3. LetP be a BK-puzzle, andSa set of edge labels. Then one can shrink all ofP’s edges with labelsnot inSto points, and obtain a new BK-puzzle DSP whose sides have been S-deflated.

Proof. It is slightly easier to discuss the caseS^c = {s}, and obtain the general case by shrinking one numbersat a time.

Let t ∈ [0, 1], and change the puzzle regions as follows: keep the angles the same, but shrink any edge with label s to have length t. (This wouldn’t be possible if e.g.

we had triangles with labels s, s, j 6= s, but we don’t.) For t = 1 this is the original BK-puzzle P, and for all t the resulting total shape is a triangle. Consider now the BK-puzzle att =0: all the s-edges have collapsed, and each(i, s)- or(s, i)-region has shrunk to an interval, joining twoi-regions together.

Call this operation theS-deflationDSPof the BK-puzzleP.

Proposition 4. LetP be a BK-puzzle. Then the content(n1, n2, . . . , nd) on each of the three sides is the same. There are ⁿⁱ₂⁺¹

right-side-upi-triangles and ⁿ₂ⁱ

upside-downi-triangles, andninj(i, j)-rhombi, for alliandj.

More specifically, the number of (i, j)-rhombi (for i > j) with a corner pointing South equals the number ofij-inversions on the South side. (Similarly for NW or NE.)

Proof. Deflate all numbers except fori, resulting in a triangle of sizeni, or all numbers except for i and j, resulting in a Grassmannian puzzle. Then invoke [KnTaoWo04, proposition 4] and [KnTao03, corollary 2].

Now fix π, ρ, σof the same content, and let ∆^σ_πρdenote the set of BK-puzzles with π, ρ, σon the NW, NE, and S sides respectively, all read left to right. ThenD_Son BK- puzzles is a map

DS:∆^σ_πρ→∆^D_D^S_S^σ_π,DSρ.

Corollary 1. Letπ, ρ, σbe three words. If they do not have the same content, then∆^σ_πρ=∅. If they have the same content, but for somei > jwe haveinvij(π) +invij(ρ)6= invij(σ), then

∆^σ_πρ=∅.

It is easy to see that any ambiguatorA∼extends to a map A^∼:∆^σ_πρ→∆^A_A^∼_∼^π_π,A∼ρ

which one does not expect to be1 : 1or onto in general. The only sort we will use is

“Ai]”, which amalgamates all numbers ≤ i, and all numbers > i. In particular, each Ai]Pis a Grassmannian puzzle.

We will need to study a deflation (of the single label1) and an ambiguation together:

A1]×D1^c :∆^σ_πρ→∆^A_A^1]σ

1]π,A_1]ρ×∆^D_D^1cσ

1cπ,D_1cρ.

Our key lemma (lemma 3) will be that either this map is an isomorphism or the source is empty. That suggests that we try to define an inverse map, but to a larger set.

Define the set (∆¹)^σ_πρ of BK¹-puzzles to be those made of the following labeled pieces, plus the stipulation that only single numbers (not multinumbers like(53)) may appear on the boundary of the puzzle triangle:

i i j (ij) 1 i

i

((ij)1)

(ij)

Againi > j, and on the third piecesi > j > 1. If we disallow the((ij)1)labels (and with them, the third type of piece), then any triangle of the second type must be matched to another such, and we recover an equivalent formulation of ∆^σ_πρ. In this way there is a natural inclusion ∆^σ_πρ → (∆¹)^σ_πρ, cutting each (i, j)-rhombus into two triangles of the second type. In figure 3 we give an example of a BK¹-puzzle that actually uses the ((32)1)label.

3 3 3 2 3

32 32

(32)1

31

c

32

D1

2 3

1 1 1

1 1 3

2

2 2 3 3 3 2 2

2

Figure 3: The BK¹-puzzle on the left deflates to the Grassmannian puzzle on the right, which naturally carries a honeycomb remembering where the1-edges were, as in the proof of lemma 3.

Lemma 2. For a wordτ, letY(τ) :=P

iinvi1(τ)yi. Then for each puzzleP ∈(∆¹)^σ_πρ, X

e labeled((ij)1)

yj−yi = Y(π) +Y(ρ) −Y(σ).

Proof. Consider the vector space R²⊗R^d, where R² is the plane in which our puzzles are drawn, and R^dhas basis{x1, . . . , xd}. Assign to each directed edgee ofP a vector ve∈R²⊗R^d, as follows:

e=−→ⁱ =⇒ ve =−→⊗xi

e=−^(ij)→ =⇒ ve = ( −→⊗xi) + (−

→⊗xj) e=⁽⁽−^ij)1)→ =⇒ v_e = (←−⊗x_i) + (−→⊗x_j) + (

←−⊗x₁)

Ifepoints in another direction,veis rotated accordingly (e7→veis rotation-equivariant).

This assignment has the property that if the edgese, f, gof a puzzle piece are directed to to form a cycle, then ve +vf +vg = 0. Consider the bilinear form ⊡ on R²⊗R^d satisfying:

• ⊡is rotationally invariant;

• (e⊗xi)⊡(f⊗xj) =0, ifi =1orj6=1;

• (−→⊗xi)⊡(−→ ⊗x1) = (−→⊗xi)⊡(−

→ ⊗x1) = yi, ifi 6=1.

These conditions completely determine⊡. For example, bilinearity and rotational in- variance give

( −→⊗xi)⊡(−

→ ⊗x1) = (−→⊗xi)⊡(

←−⊗x1) = (−→⊗xi)⊡((−

→ − −→)⊗x1)

= (−→⊗xi)⊡(−

→ ⊗x1) − (−→⊗xi)⊡(−→⊗x1) =yi−yi=0 . Let Ω = (e₁, . . . , e_m) be a path from the southwest corner of P to the southeast corner. LetY(Ω) :=P

r<sver ⊡ves. We claim the following:

1. IfΩis the path along the south side, thenY(Ω) =Y(σ).

2. IfΩis the path that goes up the northwest side and down the northeast side, then Y(Ω) =Y(π) +Y(ρ).

3. If Ωis any path, then Y(Ω) = Y(σ) +P

e(y_j−yi) where the sum is taken over edgeselabeled((ij)1), lying strictly belowΩ.

The first two assertions are easily checked (the second uses the calculation in the ex- ample above). For the third, we proceed by induction on the number of puzzle pieces below Ω. We show that if we alter the path so as to add a single puzzle piece, Y(Ω) doesn’t change, except when new the piece is attached to an edge ofΩlabeled((ij)1), in which case it changes by yj−yi. To see this, note that when a piece is added, the sequence(ve₁, . . . , vem)changes in a very simple way: either two consecutive vectors ver and ver+1 are replaced by their sum, or the reverse—a vector ver in the sequence is replaced by two consecutive vectors ve_r^′, ve_r^′′ with sumver. When the first happens, Y(Ω)changes by−ver⊡ver+1; in the second case, byve_r^′⊡ve_r^′′. It is now a simple matter to check that this value is0oryj−yias indicated.

The lemma follows from assertions 1 and 3 in the claim.

Lemma 3. Fixπ, ρ, σ, and letc=Y(π) +Y(ρ) −Y(σ)be the statistic from lemma 2.

1. The mapA1]×D1^c defined above factors as the inclusion ∆^σ_πρ → (∆¹)^σ_πρfollowed by a bijection(∆¹)^σ_πρ−g→∆^A_A^1]_1]^σ_π,A1]ρ×∆^D_D^1cσ

1cπ,D_1cρ.

2. Ifc=0, then the inclusion∆^σ_πρ→(∆¹)^σ_πρis an isomorphism.

3. Ifc6=0, then∆^σ_πρis empty. Ifcis not in the cone spanned by{yi−yi+1}_{i=1,...,d−1}, then (∆¹)^σ_πρand at least one of∆^A_A^1]_1]^σ_π,A1]ρ,∆^D_D^1cσ

1cπ,D_1cρis empty.

To define the reverse map will require the concept of “honeycomb” from [KnTao99].

Decompose the equilateral triangle of size n into n² unit triangles, and consider a “multiplicity” function from the 3 ⁿ⁺¹₂

edges of this decomposition to the naturals.

Define the “tension” on a vertex to be the vector sum of its incident edges (thought of as outward unit vectors), weighted by these multiplicities. Abounded honeycombis a multiplicity function such that

• the tension of internal vertices is zero,

• the tension of vertices on the NW edge (except the North corner) is horizontal, and

• the120^◦, 240^◦ rotated statements hold for the remainder of the boundary.

One can add two such multiplicity functions, giving an additive structure on the set of bounded honeycombs of sizen, calledoverlayand denoted⊕(as it is related to the direct sum operation on Hermitian matrices [KnTao99]). Thedimensionof a bounded honeycomb is the sum of the multiplicities on the horizontal edges meeting the NW edge, and is additive under⊕. A bounded honeycomb has only simple degeneracies if all multiplicities are1, and there are no vertices of degree> 4. If it also has no vertices of degree4, it isgeneric.

If one relieves the tension on the boundary by attaching rays to infinity, one obtains (a 30^◦ rotation of) a honeycomb as defined in [KnTao99]. (In this way one can see that the dimension of a bounded honeycomb is invariant under rotation.) Bounded honeycombs already arose in [KnTaoWo04,§5, theorem 1].

Proof of lemma 3. (1) It is easy to extendA^∼to a map(∆¹)^σ_πρ→∆^A_A^1]σ

1]π,A_1]ρ, by

j>1 j=1

*

* *

i j

1

(ij) 1

*

(ij)

(*1)

((ij)1)

where∗represents the equivalence class “numbers larger than1”.

To extendD1^c to a map(∆¹)^σ_πρ→∆^D_D^1cσ

1cπ,D_1cρ, first erase any puzzle edge that has an (i1)or((ij)1)on it, which results in a decomposition into triangles and rhombi. Then as before, shrink the1-edges.

Given a pair(G, P)∈∆^A_A^1]σ

1]π,A1]ρ×∆^D_D^1cσ

1cπ,D1cρ, we knowD1^cGandPare the same size, and D₁^cGis a trivial puzzle in the sense that all edges are labeled∗. But this triangle has more structure, if one remembers where the deflated(∗, 1)-rhombi are in it: it has a bounded honeycomb of dimension equal to the number of1s in each ofπ, ρ, σ. (This is the content of [KnTaoWo04,§5, theorem 1].) An example is in figure 3.

Take this bounded honeycomb onD1^cGand overlay it onP. Then “reinflate”P to a BK¹-puzzle Q with D1^cQ = P, where each honeycomb edge of multiplicity m and P-label I (which may bei or (ij)) is inflated to m (I, 1) rhombi with label (I1) across their waists. This is the inverse map.

(2) Ifc = 0, by lemma 2 eachP ∈ (∆¹)^σ_πρhas no ((ij)1) labels, and hence is in the image of the inclusion∆^σ_πρ→(∆¹)^σ_πρ.

(3) Ifc 6= 0, by lemma 2 everyP ∈ (∆¹)^σ_πρhas some((ij)1)labels, and hence is not in the image of the inclusion∆^σ_πρ→(∆¹)^σ_πρ. So∆^σ_πρ=∅.

By lemma 2, if P is in (∆¹)^σ_πρ, then c is in the positive span of{yi−yi+1}i=1,...,n−1. Contrapositively, if cis not in this span, there can be no suchP. Since the empty set (∆¹)^σ_πρis isomorphic to∆^A_A^1]σ

1]π,A1]ρ×∆^D_D^1cσ

1cπ,D1cρ, one of these factors must be empty.

Theorem 1. Suppose that π, ρ, σhave the same content. Then the BK coefficientec^σ_πρequals the cardinality|∆^σ_πρ|.

Proof. Ifinv_ij(π) +inv_ij(ρ) 6=inv_ij(σ)for somei > j, thenec^σ_πρ =0 = |∆^σ_πρ|, by proposi- tion 2 and corollary 1.

If inv_ij(π) +inv_ij(ρ) = inv_ij(σ)for alli > j, the statistic from lemma 2 is zero, and we proceed by induction ond. Ifd=2, this is the Grassmannian case, where the result is known, so assumed≥3. From lemma 3, we have

∆^σ_πρ−g→∆^A_A^1]σ

1]π,A1]ρ×∆^D_D^1cσ

1cπ,D1cρ. By lemma 1 (applied to the equivalence relation “1]”) we have

e

c^σ_πρ=ec^A_A^1]σ

1]π,A1]ρ·ec^D_D^1cσ

1cπ,D1cρ. Inducting ond, we haveec^A_A^1]σ

1]π,A1]ρ =|∆^A_A^1]σ

1]π,A1]ρ|,ec^D_D^1cσ

1cπ,D1cρ= |∆^D_D^1cσ

1cπ,D1cρ|and soec^σ_πρ =

|∆^σ_πρ|as required.

Theorem 2. Letπ, ρ, σbe words with the same content, and for alli > j,inv_ij(π)+inv_ij(ρ) = invij(σ). Amalgamate the mapsDij:∆^σ_πρ→∆^D_D^ijσ

ijπ,Dijρinto a single map (D_ij) :∆^σ_πρ−→Y

i>j

∆^D_D^ijσ

ijπ,Dijρ. Then this map is a bijection.

1

2 2 2 3 3

2 3 2 2 3 2

2 2

3 1 1 3 2 2

1 2

2 1

1 1

1 2 2

2 2 2

2

1 1

2

1

1 1

1 2 2 1

2 2 1

3 3 3

1 1 1 1

3 1 1

1 1

Figure 4: The ³₂

deflations of the BK-puzzle from figure 2, from which it may be reassembled as in theorem 2.

An example of the image is in figure 4.

Proof. If the number of labels is1or2, the statement is trivial. So assume it is at least3.

We need to define the reverse map, associating a puzzleQ ∈ ∆^σ_πρto a tuple(Gij ∈

∆^D_D^ijσ

ijπ,Dijρ)_i>j. By induction on the number of labels, we may assume that there exists a puzzleP(with no1s on its boundary) mapping to the tuple(Gij)i>j>1. Then the desired Qmust haveD1^cQ=P.

Next we define a Grassmannian puzzleGfrom the tuple(G_i1)_i>1. EachD₁G_i1 is a triangle of the same size, all edges labeled1, but bearing a bounded honeycombhias in the proof of lemma 3. Then⊕i>1hiis a bounded honeycomb in this same triangle.

Again as in the proof of lemma 3, inflate⊕_i>1h_ito produce a puzzleGwith two labels

∗> 1. With this we similarly constrainQ, byA1]Q=G.

Now use lemma 3 parts (1) and (2) to constructQfrom the pair(P, G). Theorem 3. For allπ, ρ, σas in theorem 1,

e

c^σ_πρ=Y

i>j

c^D_D^ijσ

ijπ,Dijρ. Proof. This follows immediately from theorems 1 and 2.

Remark2. It has been observed several times now (e.g. [DeWe, KiTolTou09]) that when a Horn inequality is satisfied with equality, a Littlewood-Richardson number factors.

This fact can be seen from theorem 3 as follows.

Let π, ρ, σ ∈ {1, 2, 3}^∗ be words of length n. Let π = A2]π and π^′ = D₁₂(π), with similar notation forρ,σ, and assume thatc^σ_π^′′ρ^′ 6=0.

Under these conditions, inv_ij(π) + inv_ij(ρ) = inv_ij(σ) for all i > j is equivalent to asserting that the Horn inequality for (π, ρ, σ) associated to (π^′, ρ^′, σ^′) holds with equality (see [PuSo08,§4]). With this hypothesis, the Littlewood-Richardson number c^σ_πρfactors as

c^σ_πρ=c^D_D²³₂₃^σ_π,D23ρ·c^D_D¹³₁₃^σ_π,D13ρ.

This can be seen by comparing the result of lemma 1 e

c^σ_πρ=c^σ_πρ·c^σ_π^′′ρ^′

and theorem 3

e

c^σ_πρ=c^D_D²³₂₃^σ_π,D23ρ·c^D_D¹³₁₃^σ_π,D13ρ·c^σ_π^′′ρ^′.

4 Relation to extremal honeycombs

Let Rⁿ

+ denote the cone of weakly decreasing n-tuples. The Littlewood-Richardson cone BDRY(n) ⊂ (Rⁿ₊)³ is a rational polyhedral cone whose elements (λ, µ, ν)can be characterized in several ways including the following [Fu00, KnTaoWo04]:

• There exists a triple(Hλ, Hµ, Hν)of Hermitian matrices of sizen, adding to zero, whose spectra are(λ, µ, ν).

• There exists a honeycomb h of size nwhose boundary edges ∂h have constant coordinates given by (λ, µ, ν). (We will not use this characterization, and refer the interested reader to [KnTao99] for definitions.)

• (If(λ, µ, ν)are integral, hence may be thought of as dominant weights forGL_n(C).) There is aGLn(C)-invariant vector in the tensor productVλ⊗Vµ⊗Vνof irreducible representations with those high weights.

• For each puzzlePof sizen, with boundary labels0, 1, the inequalityNW(P)·λ+ NE(P)·µ+S(P)·ν ≤ 0 holds, where NW(P), NE(P), S(P)are the vectors of0s and1s around the puzzleall read clockwiseand·is the dot product.

The fourth says that each inequality definingBDRY(n)(other than thechamber inequal- ities that say λ, µ, νare decreasing) can be “blamed” on a Grassmannian puzzle. In [KnTaoWo04] it was shown that the puzzles that occur this way are exactly the rigid ones, meaning that they are uniquely determined by their boundaries. (The others define valid, but redundant, inequalities.)

In this section we extend this last connection to one between all regular faces of BDRY(n)(meaning, not lying on chamber walls) and rigid BK-puzzles. Then the con- nection between BK-puzzles and the BK product gives a new proof of [Re10, Theorem D], corresponding the regular faces to BK coefficients equaling1.

This section closely follows [KnTaoWo04, §3 and §4], and we will only point out where the proofs there need other than trivial modification. In any case, much of it can be avoided byinvoking[Re10, Theorem D], rather than reproving it combinatorially.

Lemma 4. (Extension of [KnTaoWo04, lemma 3].) Letbbe a generic point on a regular face of BDRY(n)of codimensiond−1. Then there exists a honeycombhwith∂h =bsuch that

• h=h1⊕h2⊕ · · · ⊕hdis an overlay of generic honeycombs,

• hhas simple degeneracies, and

• hiintersectshj transversely for eachj < i, and at each pointpwherehicrosseshj, hj

turns clockwise tohi, meaning that a path going fromhjtohithroughpcould turn right60^◦, not left60^◦ (where continuing straight is turning0^◦).

Ifh=h₁⊕h₂⊕ · · · ⊕h_dsatisfies this third condition, call it aclockwise overlay.

Proof. The proof of [KnTaoWo04, lemma 3] goes by showing that a honeycomb of size mwith simple degeneracies that isnota clockwise overlay has a(3m−1)-dimensional space of perturbations. So if h is written as a clockwise overlay of fewer than d−1 honeycombs (e.g. as itself), one of them must itself be a clockwise overlay.

This already implies the interesting fact that whileBDRY(n)has faces of all dimen- sions2, . . . , 3n−1, its regular faces are of dimension at least2n.

Lemma 5. (Extension of [KnTaoWo04, theorem 2 and lemma 4].) Leth=h₁⊕h₂⊕ · · · ⊕h_d be a clockwise overlay. Then there is a codimensiond−1regular faceFofBDRY(n)containing

∂h. It is the intersection ofd−1regular facets.

Moreover, one can construct fromh a BK-puzzleP withdlabels, and for each labeli < d one can construct a Grassmannian puzzle Ai]P, such that F is the intersection of the facets corresponding to(A_i]P).

The construction of P from h is straightforward: each 3-valent vertex in hi is re- placed with ani-triangle; each4-valent vertex is replaced either with twoi-triangles (if the vertex lies only onhi) or an(i, j)-rhombus (if the vertex is wherehiand hjcross).

The clockwise condition causes the puzzle rhombi to have the requiredi > jcondition.

An example is in figure 5.

3

1 2

Figure 5: A clockwise overlayh₁⊕h₂⊕h₃, whose associated BK-puzzle is the one in figure 2. The Grassmannian puzzles associated toh1⊕h2, h1⊕h3, h2⊕h3are in figure 4.

Remark 3. Borrowing terminology from the study of toric varieties, call a face F of a polytope rationally smoothif F lies on onlycodimF many facets. Then lemma 5 im- plies the curious fact that BDRY(n)is rationally smooth on all its regular faces. (Note that this makes it easy to describe the partial order on faces, as is done in [Re2, The- orem D].) This does not follow from its interpretation as a moment polytope (see e.g.

[KnTaoWo04, appendix]); while the moment polytope of a full flag manifold has all rationally smooth faces, the moment polytope ofGr2(C⁴)is an octahedron.

Combining lemmas 4 and 5, we have

Theorem 4. (Extension of [KnTaoWo04, theorem 3].) LetFbe a codimensiond−1 regular face ofBDRY(n). Then there exists a BK-puzzleP withdlabels, from which one can construct d−1facets ofBDRY(n)whose intersection isF.

To characterize the BK-puzzles arising this way, we need to adapt the “gentle loop”

technology of [KnTaoWo04] for Grassmannian puzzles. Orient the region edges as follows:

• If the edge is between a triangle and an adjacent rhombus, orient it toward the obtuse vertex of the rhombus.

• If the edge is between an(i, j)-rhombus and an(i, k)-rhombus, i > j > k, orient it toward the obtuse vertex of the(i, k)-rhombus.

• If the edge is between an(i, k)-rhombus and an(j, k)-rhombus, i > j > k, orient it toward the obtuse vertex of the(i, k)-rhombus.

Mnemonic: the rhombus with the greater spread takes precedence. The BK-puzzle in figure 2 has its region edges oriented using this rule.

A gentle path was defined in [KnTaoWo04] as a path in this directed graph that, at each vertex, either goes straight or turns±60^◦ (not±120^◦). For its generalization in this paper, we need an additional constraint: if a vertex occurs as the intersection of two straight lines, a gentle path through itmust go straight through. Agentle loop is a gentle path whose first and last edges coincide (edges not vertices – the next turn after the last edge might not otherwise be gentle).

Proposition 5. (Extension of [KnTaoWo04, proposition 2].) Leth=h1⊕h2⊕ · · · ⊕hdbe a clockwise overlay of generic honeycombs, P the corresponding BK-puzzle,γ = (γ₁, . . . , γs)a list of edges along a gentle path inPof lengths > 1, andγ˜the corresponding sequence of edges inh. Then the lengths of the honeycomb edges(γ˜i)weakly decrease.

To prove this, we will study the possible internal vertices in a BK-puzzle, and use this classification to simultaneously prove

Lemma 6. (Extension of [KnTaoWo04, lemma 5].) LetPbe a BK-puzzle without gentle loops, and v an internal vertex. Label each region edge meetingv with the number of gentle paths starting at that edge and terminating on the BK-puzzle boundary. Then these labels are strictly positive, andvhas zero tension.

Proof. An internal vertexvof a puzzle may be an obtuse vertex of (a priori)0, 1, 2or3 rhombi. Consider the labels on the edges meetingv, clockwise: they strictly decrease across obtuse angles, stay the same across acute angles from triangles, and strictly increase across acute angles from rhombi.

So if there are no obtuse vertices atv, there can be no acute rhombus vertices either, just sixi-triangles for the samei. Such avhas no gentle paths going through it.

There cannot be three obtuse vertices atv, as that would have three strict increases with no room for any decreases.

That leaves either1or2obtuse vertices atv. We draw the possibilities up to rotation and puzzle duality that have no triangles at v, only acute rhombi. (As each triangle makes the situation simpler we leave those cases to the reader.) In each case the labels are ordereda > b > c > d > e, or possiblya > c > b > din the second case.

e b c c d d c

d

d d

a

b

d d c c

a c

b c b b

d c

c b

e

a b

a a a

a

d

b b

e b c c d d c

a

a a b

a a

d b

To prove the proposition, it suffices to check s = 2. We draw the region (in the clockwise overlay) dual to the puzzle vertex. The arrows within are dual to 2-step gentle paths.

c

a b

c d

d b

a c

c b

a d a

d b e

1. None of these are “gentle sinks” – any incoming path can be extended to be gently outgoing. This is why the number of gentle paths starting at an internal edge and terminating on the puzzle boundary is strictly positive.

2. In each case, the length of an edge with an in-pointing arrow is the sum of the lengths of the edges it points to. (This is where the modification of the [KnTaoWo04] definition of “gentle path” is important.) Therefore if we change the length of each honeycomb edge incident with a polygon to be the number of gentle paths emanating from it, possibly zero, the result is still a closed polygon.

Dually,vhas zero tension.

Lemma 7. (Extension of the corollary in [KnTaoWo04].) BK-puzzles associated to clockwise overlays have no gentle loops.

Proof. Letγ = (γ1, . . . , γs)be a path whose corresponding honeycomb edges all have the same length. Comparing to the BK-puzzle vertex classification above, every corre- sponding honeycomb region must be a parallelogram. (One possibility to remember is the leftmost vertex, but with b = c = d and the rightmost two rhombi replaced with triangles.) Chaining these together, the parallelograms all lie between the same two lines, soγcan not close up to a loop.

But by proposition 5, any gentle loop γ will have all corresponding honeycomb edges of the same length. So there can be no such loops.

Proposition 6. (Extension of [KnTaoWo04, proposition 3].) Let P be a BK-puzzle of size n with no gentle loops. Then there exists a clockwise overlay h such that the BK-puzzle that lemma 5 associates toh isP. By this lemma, thed−1 inequalities defined by the BK-puzzle determine a regular face ofBDRY(n).

The edges inh are assigned lengths according to the number of gentle paths start- ing at their corresponding puzzle edges. To know that the resulting h is a transverse clockwise overlay requires the strict positivity in lemma 6.

Theorem 5. (Extension of [KnTaoWo04, theorem 5].)

1. There is a1 : 1 correspondence between BK-puzzles of size nwithout gentle loops and regular faces ofBDRY(n).

2. (An analogue of [Re2, Theorem D].) One faceF1contains another,F2, if the corresponding BK-puzzleP₁is an ambiguationA∼P₂of the BK-puzzleP₂.

Proof. Claim (1) is a combination of lemma 4, lemma 5, and proposition 6. Claim (2) follows from lemma 5.

Remark4. The BK-puzzles for full flags (no repeated edge labels on a side) correspond to2n-dimensional regular faces. In the Hermitian sum context, if we fixλandµ, these become regular vertices and correspond to sums ofcommutingHermitian matrices. So they were easy to study, historically, and people found many of the inequalities on BDRY(n)by looking nearby these vertices.

One might hope, then, that every regular facet of BDRY(n) contains one of these 2n-dimensional regular faces. A counterexample is provided by the unique puzzle in

∆²¹¹²¹12112,12112, as any attempt to disambiguate the2s inside a finer BK-puzzle breaks the inv_ijcounts. Correspondingly, in the overlayh1⊕h2pictured here,

1 2

none of the internal edges ofh2can be shrunk to points while keepingh1⊕h2trans- verse, as those edges all cross edges ofh1.

Theorem 6. (Extension of [KnTaoWo04, theorems 6 and 7].) A BK-puzzle is rigid iff it has no gentle loops.

The hard direction, taking3pages in [KnTaoWo04], constructs a new BK-puzzleP^′ from a BK-puzzlePand a minimal gentle loop. We leave the reader to either check that those arguments generalize to BK-puzzles, or to invoke [Re2, Theorem C].

The reader may be wondering about the redundant inequalities onBDRY(n)speci- fied by nonrigid Grassmannian puzzles. Each one defines some face ofBDRY(n); what is the corresponding BK-puzzle? But [KnTaoWo04, theorem 8] says that these faces are never regular, so do not correspond to BK-puzzles.

5 Rigid regular honeycombs

As with puzzles, call a honeycombrigidif it is uniquely determined by its boundary.

These have received some study already; under the deflation map linking honeycombs to puzzles, these give the rigid puzzles indexing the regular facets of BDRY(n). Ful- ton’s conjecture (proven combinatorially in [KnTaoWo04] and geometrically in [Re1, BeKuRe]) is that an integral honeycomb that isZ-rigid is alsoR-rigid.

It is easy to see that the set of boundaries of rigid honeycombs is a union of faces of BDRY(n). In this theorem we characterize which regular faces arise this way.

Theorem 7. Lethbe a honeycomb such that∂his regular. Thenhis rigid iffhis a clockwise overlayh1⊕ · · · ⊕hdof honeycombs of size1or2.

Proof. Theorem 2 from [KnTao99] says that someh^′ with∂h^′ =∂h has simple degen- eracies, and if we elide them (thinking of them as a sort of local overlay, rather than actual vertices), the underlying graph of the resulting space is acyclic. Let{h_i^′}be the components of this forest, soh^′ =L

ih_i^′ (not yet necessarily clockwise). Eachh_i^′ auto- matically has simple degeneracies, and being acyclic, has size1or2.

=⇒ Now assume h is rigid, so h = h^′. Then for any pair h_i^′, h_j^′, one must be clockwise of the other, exactly as in the proof of [KnTaoWo04, lemma 3]. Since h_i^′, h_j^′ must intersect, who is clockwise of whom is uniquely determined.

Moreover, the clockwiseness relation must be transitive, or else there is some triple h_i^′,h_j^′, h_k^′ withh_i^′ meetingh_j^′ clockwise at p, h_j^′ meetingh_k^′ clockwise atq, h_k^′ meeting h_i^′clockwise atr. But then [KnTaoWo04, lemma 2] can perturbhalong the unique loop fromptoqtortop.

Hence “clockwiseness” is a total order on the{h_i^′}.

⇐=We wish to show that if∂h^′ =∂h, thenh^′ =h. Each of thed−1puzzleequalities satisfied by∂h^′ forceh^′ to be an overlay, since by the proof of [KnTaoWo04, theorem 2] the edges in h corresponding to rhombi must be length 0. So h^′ is an overlay of these honeycombs of size1and2, each of which is rigid. That is,handh^′ are the same overlay of the same size1or2honeycombs.