Inequalities between Littlewood–Richardson coefficients

INEQUALITIES BETWEEN LITTLEWOOD-RICHARDSON COEFFICIENTS FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS Abstract. We prove that a conjecture of Fomin, Fulton, Li, and Poon, associated to ordered pairs of partitions, holds for many infinite families of such pairs. We also show that the bounded height case can be reduced to checking that the conjecture holds for a finite number of pairs, for any given height. Moreover, we propose a natural generalization of the conjecture to the case of skew shapes. Contents 1. Introduction 1 2. Combinatorial properties of the ∗-operation and implications 3 3. Main results 8 4. Proofs of the combinatorial properties 9 5. Extension of the ∗-operation to tableaux 13 6. Background on Littlewood-Richardson coefficients 15 7. Proof of special instances 16 8. Reduction to a finite set of pairs in bounded height case 21 9. Final remarks 23 10. Acknowledgments 23 References 23 1. Introduction In the course of their study of Horn type inequalities for eigenvalues and singular values of complex matrices, Fomin, Fulton, Li, and Poon [2] come up with a very interesting conjecture concerning the Schur-positivity of special differences of products of Schur functions. More precisely, they consider differences of the form sµ∗sν∗−sµsν, where µ∗and ν∗are partitions constructed from an ordered pair of partitions µand ν through a seemingly strange procedure at first glance. In our presentation, their transformation (µ, ν)7→ (µ∗, ν∗) on ordered pairs of partitions, will rather be denoted (1.1) (µ, ν)7−→ (µ, ν)∗= (λ(µ, ν), ρ(µ, ν)) F. Bergeron is supported in part by NSERC and FQRNT. 1 2 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS and will be called the ∗-operation. As we shall see, this change of notation is essential in order to simplify the presentation of the many nice combinatorial properties of this operation. On the other hand, it underlines that both entries, λand ρof the image (µ, ν)∗ of (µ, ν), actually depend on both µand ν. With this slight change of notation, the original definition of the ∗-operation is as follows. Let µ= (µ1, µ2,...,µn) and ν= (ν1, ν2,...,νn) two partitions with the same number of parts, allowing zero parts. From these, two new partitions λ(µ, ν) = (λ1, λ2,...,λn) and ρ(µ, ν) = (ρ1, ρ2,...,ρn) are constructed as follows (1.2) λk:= µk−k+ #{j|1≤j≤n, νj−j≥µk−k}; ρj:= νj−j+ 1 + #{k|1≤k≤n, µk−k > νj−j}. Although this definition does not make it immediately clear, both λ(µ, ν) and ρ(µ, ν) are truly partitions, and they are such that |λ(µ, ν)|+|ρ(µ, ν)|=|µ|+|ν|, where as usual |µ|denotes the sum of the parts of µ. Recall that the product of two Schur functions can always be expanded as a linear combination sµsν=X θ cθ µ νsθ, of Schur functions indexed by partitions θof the integer n=|µ|+|ν|, since these Schur functions constitute a linear basis of the homogeneous symmetric functions of degree n. It is a particularly nice feature of this expansion that the coefficients cθ µ ν are always nonnegative integers. They are called the Littlewood-Richardson coefficients. More generally, we say that a symmetric function is Schur positive whenever the coefficients in its expansion, in the Schur function basis, are all non-negative integers. For more details on symmetric function theory see Macdonald’s classical book [3], whose notations we will mostly follow. We can then state the following: Conjecture 1.1 (Fomin-Fulton-Li-Poon).For any pair of partitions (µ, ν), if (µ, ν)∗= (λ, ρ), then the symmetric function (1.3) sλsρ−sµsν is Schur-positive. In other words, this says that cθ µ ν ≤cθ λ ρ, for all θsuch that sθappears in the expansion of sµsν. For an example of one of the simplest case of the ∗-operation, let µ= (a) and ν= (b), with a > b, be two one-part partitions. In this case, we get ((a),(b))∗= (a−1, b + 1), SCHUR-POSITIVITY 3 so that Conjecture 1.1 corresponds exactly to an instance of the classical Jacobi-Trudi identity: sa−1sb+1 −sasb= det sa−1sa sbsb+1  =sa−1,b+1. In this paper we give a new recursive combinatorial description of the ∗-operation. This recursive description allows us to prove many instances of Conjecture 1.1 and to show that it reduces to checking a finite number of instances for any fixed ν, if we bound the number of parts of µ. Moreover we show how to naturally generalize the conjecture to pairs of skew partitions. 2. Combinatorial properties of the ∗-operation and implications We first derive some nice combinatorial properties of the transformation ∗. To help in the presentation of these properties, let us introduce some further notation. For any undefined notation we refer to [3]. We often identify a partition with its (Ferrers) diagram. Diagrams are drawn here using the “French” convention of ordering parts in decreasing order from bottom to top. We write µ=−→ αi, if the partition µis obtained from the partition αby adding one cell in line i; and µ=α↑k, if µis obtained from αby adding one cell in column k. In other words, µ=−→ αimeans that µi=αifor all i6=ℓ, and µℓ=αℓ+ 1. This is illustrated in Figure 1 in term of diagrams. −→2 =x  2= Figure 1 Observe that, µ=−→ αiiff µ′=−→ α′µi iff µ=α↑µi iff µ′=α′↑i We can now state our recursive description of the ∗-operation. Proposition 2.1 (Recursive formula).For any partitions αand ν, let µ=−→ αiand (λ, ρ) = (α, ν)∗, then we have (2.1) (µ, ν)∗=     (λ, ρ↑µi)if there exists jsuch that νj−j=αi−i, (−→ λi, ρ)otherwise. 4 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS Similarly, when ν=−→ βiand (λ, ρ) = (µ, β)∗, we have (2.2) (µ, ν)∗=     (λ↑νi, ρ)if there exists jsuch that µj−j=νi−i, (λ, −→ ρi)otherwise. We can clearly use Proposition 2.1 to recursively compute λ(µ, ν) and ρ(µ, ν). This is discussed more extensively in Section 5. The actual computation of the ∗-operation can be simplified in view of the following property (see Lemma 4.1). For any pair of partitions (µ, ν), we have (µ, ν)∗= (λ, ρ) iff (ν′, µ′)∗= (λ′, ρ′),(2.3) where, as usual, µ′stands from the conjugate of µ. Using the fact that the involution ω (which is the linear operator that maps sµto sµ′) is multiplicative, it easily follows that Proposition 2.2. Conjecture 1.1 holds for the pair (µ, ν)if and only if it holds for the pair (ν′, µ′). In practice, there are many ways to describe the ∗-operation recursively, since we can freely choose how to make partitions grow. It is sometimes convenient to start from the pair (0, ν), with 0 standing for the empty partition, whose image under the ∗-operation has a simple description. Lemma 2.3. Let νbe any partition. Then ρ(0, ν) = (ν1, ν2−1,...,νk−(k−1)) λ′(0, ν) = (ν′ 1−1, ν′ 2−2,...,ν′ k−k), where k= max{i|νi≥i}. We will sometimes use respectively νand νto denote the partitions λ(0, ν) and ρ(0, ν). For example if ν= 866554421, then ν= 44432211 and ν= 85421 as is illustrated in Figure 2. ν ν ν ∗ −→ Figure 2 In Section 5 we elaborate on the various ways that Proposition 2.1 can be used to compute the ∗-operation. This gives rise to a ∗-operation on pairs of Young tableaux. In Figure 3 we illustrate the effect of the ∗-operation on pairs of the form ((n), ν). SCHUR-POSITIVITY 5 ∗ ∗ ∗ ∗ −→ −→ −→ −→ Figure 3 Given partitions µand ν, define the partition µ+νby (µ+ν)i:= µi+νi. and set µ∪ν:= (µ′+ν′)′. For example, if µ= 33221 and ν= 531, then µ∪ν= 53332211 and µ+ν= 86321. For µ and νtwo partitions of n,µis said to be dominated by ν, written µν, if for all k≥1: µ1+µ2+···+µk≤ν1+ν2+···+νk. Another remarkable property of the ∗-operation is that its image behaves nicely under the dominance order. More precisely: Lemma 2.4. For any pair of partitions (µ, ν), if (λ, ρ) = (µ, ν)∗, then we have µ∪νλ∪ρ, and equivalently(2.4) µ+νλ+ρ.(2.5) Observe that when sθappears in sµsνwith a nonzero coefficient, then µ∪νθµ+ν. Thus (2.4) and (2.5) imply that λ∪ρθλ+ρ, which is compatible with Conjecture 1.1. 6 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS Lemma 2.4 immediately implies a statement very similar to that of Conjecture 1.1. As is usual (See [3]), hµdenotes the complete homogeneous symmetric function: hµ:= hµ1hµ2···hµk, with ha:= sa. Proposition 2.5. For any pair of partitions (µ, ν), if (λ, ρ) = (µ, ν)∗, then (2.6) hλhρ−hµhν is Schur-positive. Recalling that hµhν=hµ∪ν, this follows from the fact that a difference of two homogeneous symmetric functions hα−hβis Schur-positive, if and only if αβ(see [5, Chapter 2]). A clear link between this proposition and Conjecture 1.1 is established through the classical identity: (2.7) hα=sα+X βα Kβαsβ, where as usual Kβα, the Kostka numbers, count the number of semistandard tableaux of shape βand type α. In fact, (2.6) contains (1.3) as “top component” via (2.7). It follows directly from Proposition 2.1 that the ∗-operation is compatible with “inclusion” of partitions. Here, we say that αis included in µ, if the diagram of αis included in the diagram of µ. We will simply write (α, β)⊆(µ, ν),whenever α⊆µand β⊆ν, and we have: Lemma 2.6. For α,β,µand νpartitions such that (α, β)⊆(µ, ν), the following inclusions hold λ(α, β)⊆λ(µ, ν),and ρ(α, β)⊆ρ(µ, ν). An immediate, but interesting, consequence of this lemma is the following observation. Observation 2.7. Let (α, β)and (γ, δ)be two fixed points of the ∗-operation such that (α, β)⊆(γ, δ). Writing simply λfor λ(µ, ν)and ρfor ρ(µ, ν), we see (using Lemma 2.6) that (α, β)⊆(µ, ν)⊆(γ, δ), implies (α, β)⊆(λ, ρ)⊆(γ, δ). As is underlined in [2], a pair of partitions (α, β) is a fixed point of the ∗-operation if and only if (2.8) β1≥α1≥β2≥α2≥ · · · ≥ βn≥αn. Let us underline here that, for any (µ, ν), it is easy to characterize the “largest” (resp. “smallest”) fixed point contained in (resp. containing) the pair (µ, ν). We will see below how this observation can be used to link properties of λand ρto properties of µand ν. SCHUR-POSITIVITY 7 Recall that a hook is a shape of the form (a, 1b) with a, b ≥0, a n-line partition is a shape contained in a rectangle (an) with a, n ≥0, a horizontal strip is a skew shape µ/α with no two squares in the same column, and that a ribbon is a connected skew shape with no 2 ×2 squares (see [6, Chapter 7], for more details). If we drop the condition of being connected in this last definition, we say that we have a weak ribbon. Another striking consequence of Lemma 2.6 is that it allows a natural extension of the ∗- operation to skew partitions. Denoting by (µ, ν)/(α, β) the pair of skew shapes (µ/α, ν/β), we can simply define (2.9) (µ/α, ν/β)∗:= (µ, ν)∗/(α, β)∗. In other words, we have (2.10) λ(µ/α, ν/β) := λ(µ, ν)/λ(α, β), and (2.11) ρ(µ/α, ν/β) := ρ(µ, ν)/ρ(α, β). The ∗-operation, or its extension as above, preserves (among others) the following families of pairs of (skew) shapes. Proposition 2.8. The ∗-operation preserves the families of (1) pairs of hooks; (2) pairs of n-line partitions; (3) pairs of horizontal strips; (4) pairs of weak ribbons. Note that (1) and (2) follow directly from Observation 2.7, and that the statements (3) and (4) are made possible in view of our extension of the ∗-operation. ∗ −→ Figure 4. The effect of the ∗-operation on hooks. Results outlined what follows, and extensive computer experimentation suggests that we have the following extension of Conjecture 1.1. Conjecture 2.9. For any skew partitions µ/α and ν/β, if (λ, ρ) = (µ/α, ν/β)∗, then the symmetric function (2.12) sλsρ−sµ/αsν/β is Schur-positive. 8 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS This has yet to be understood in geometrical terms. One should point out that there are many skew shapes giving the same expression for the symmetric function sµ/αsν/β. The result of the ∗-operation is dependent on the particular choice of the skew-shape, so that there are many identities encoded in (2.12). On the other hand, it is clear that Proposition 2.2 extends to skew partitions. Many others combinatorial properties of the ∗-operations can be obtained with approaches similar to those above. As an example, we state the following without proof. Let τand νbe two fixed partitions, and consider all possible µ’s such that ρ(µ, ν) = τ. We claim that there is a minimal such µ, if any, and we denote it θ(τ, ν). More precisely, we could easily show that θ(τ, ν)⊆µ. Furthermore, θ=θ(τ, ν) is exactly the partition θ=τb1 1τb2−b1 2τb3−b2 3··· , with bj=τj−νj+j−1. 3. Main results In this section we state our results concerning the validity of Conjecture 1.1 for certain families of pairs, as well as its reduction to a finite number of tests for other families. We will show (in Section 7) the following. Theorem 3.1. Conjecture 1.1 (or 2.9) holds (1) For any pair (µ, ν)of hook shapes. (2) For skew pairs of the form (µ/α, ν/β), where µ,ν,α,βare hooks, with α=β. (3) For skew pairs of the form (0, ν/β), with ν/β a weak ribbon. On another note, a careful study of the recursive construction of λ(µ, ν) and ρ(µ, ν) shows that, in a sense, Conjecture 1.1 follows, under some conditions, from a finite number of cases when νis fixed and µbecomes large. More precisely, we obtain the result below. As usual, the number of nonzero parts of µ is denoted by ℓ(µ) and called the height of µ. Theorem 3.2. For any positive integer p, let νbe a fixed partition with at most pparts, i.e. ℓ(ν)≤p. Then, the validity of Conjecture 1.1 for the infinite set of all pairs (µ, ν), with ℓ(µ)≤p, reduces to checking the validity of the conjecture for the finite set of pairs (α, ν), with αhaving at most pparts, and largest part bounded as follows (3.1) α1≤p(ν1+p). Theorem 3.2 can also be generalized in a straightforward manner to the set of skew shapes pairs (µ/α, ν/β) of bounded height, with νand αfixed. SCHUR-POSITIVITY 9 4. Proofs of the combinatorial properties In what follows, unless it is specifically mentioned, all partitions will be considered to have n(possibly zero) parts. We first observe that the set Ak(µ, ν) := {j|νj−j≥µk−k}, appearing in (1.2), has to be of the form Ak(µ, ν) = {1,2,...,ak}for some ak=ak(µ, ν), since ν1−1> ν2−2> . . . > νak−ak≥µk−k, and thus (4.1) ak(µ, ν) := #Ak(µ, ν). In other words, (4.2) µk−k≤νm−miff 1 ≤m≤ak. Thus definition (1.2) of λk(µ, ν) can be reformulated as (4.3) λk:= µk−k+ak(µ, ν). In the same spirit, we consider the set Bj(µ, ν) := {k|µk−k > νj−j},which also has to be of the form {1,2,...,bj}, with (4.4) bj(µ, ν) = #Bj(µ, ν), In other words, (4.5) νj−j < µm−miff 1 ≤m≤bj and (4.6) ρj:= νj−j+ 1 + bj(µ, ν). Proof of Proposition 2.1. To prove our recursive formula for the computation of the ∗-operation, we first analyze the case µ=−→ αi. As we have already mentioned, this means that µk=αkfor all k6=i, and µi=αi+ 1. Let (λ, ρ) = (α, ν)∗. Now, suppose that there exists a j∈ {1,...,n}such that νj−j=αi−i. This implies that Ak(µ, ν) = Ak(α, ν) for all k6=iand that Ai(α, ν) = {1,2,...,j},and Ai(µ, ν) = {1,2,...,j−1}. It follows that λk(µ, ν) = λkfor all k6=i, and that λi(µ, ν) = µi−i+ai(µ, ν) =αi+ 1 −i+ai(α, ν)−1 = λi Hence λ(µ, ν) = λ. On the other hand, we clearly have Bk(α, ν) = Bk(µ, ν) for all k6=j, and Bj(α, ν) = {1,2,...,i−1}and Bj(µ, ν) = {1,2, . . . , i}. Hence ρk(µ, ν) = ρkfor all k6=iand, ρj(µ, ν) = νj−j+ 1 + bj(µ, ν) =αi−i+ 1 + i=µi. Since ρj=µi−1 we conclude that ρ(µ, ν) = −→ ρj, and this settles the first case of (2.1). 16 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS 1,2,... that appear in it. Note that ∆(µ) (the antidiagonal reading of the natural filling of µ) is always a lattice permutation of type µ. The reverse reading word of a tableau, is the reading word of a tableau, read backwards. For a proof of the following assertion see [6]. Littlewood-Richardson Rule. The Littlewood-Richardson coefficient cθ µ ν is equal to the number of semistandard tableaux of shape θ/ν and type µwhose reverse reading word is a lattice permutation. When a semistandard tableaux of shape θ/ν has a lattice permutation as its reverse reading word, we say that it is a LR-filling of shape θ/ν. For θ= 4421, ν= 21 and µ= 431, we have cθ µ ν = 2 since there are exactly two LR-fillings of θ/ν. These are described in Figure 7. The two corresponding reverse reading words 11221312 and 11221213. They are clearly lattice permutations of type µ. 2 1 3 1 2 2 1 1 3 1 2 1 2 2 1 1 Figure 7. The two LR-fillings of 4421/21 of type 431. 7. Proof of special instances In this section we show that Conjecture 1.1 holds for pairs of hooks, pairs of two-row (or two-columns) shapes, and in a special case corresponding to our generalization of the conjecture to skew partitions. We first prove that Conjecture 1.1 holds when one of the partitions is empty. Lemma 7.1. For any partition ν, setting ν:= λ(0, ν)and ν:= ρ(0, ν),∆(ν)is the reverse reading word of a LR-filling of ν/ν of type ν. Proof. We show that ∆(ν) encodes a LR-filling of ν/ν of type ν. To this end, we proceed as follows. We “slide” the natural filling of νup the columns of ν. This gives a partial filling of νwith empty cells for the portion of νthat corresponds to ν. We will suppose that these empty cells are filled with zeros. We then sort each row in increasing order to get a filling of the skew shape ν/ν. By construction, we obtain a filling of ν/ν whose reverse reading word is the lattice permutation ∆(ν). An example is given in Figure 8. To show the lemma, we need only show that the resulting tableau is semistandard. We already have strict increase along rows, so we need only check that this is also true along columns. By construction, the right-most entry in the (k+ 1)th-row of the final filling of ν/ν is k. Since the integers in a row are consecutive by construction, the difference between two entries in the same column of ν/ν, one in the ith row and the other in the (i+ 1)th row, has to be equal to νi−νi+1 + 1, which is larger than zero.  SCHUR-POSITIVITY 17 ν ր ν  → ν/ν 8 6 3 2 7 4 3 1 5 4 2 1 6 5 3 2 4 3 12 1 8 7 6 5 6 5 4 4 4 3 3 3 3 2 2 2 1 1 21 1 3 2 1 4 3 2 1 6 5 4 3 2 1 8 7 6 5 4 3 2 1 Figure 8. The LR-filling of ν/ν with reverse reading word ∆(ν). It immediately follows that Corollary 7.2. For any partition νthe difference sνsν−sν is Schur positive. Thus, recalling that s0= 1, Conjecture 1.1 holds for pairs of the form (0, ν). |{z} a|{z} a b(d−1       |{z } c| {z } c d         b+1   ∗ −→ (a) Case a≤cand b≤d |{z} a|{z} a b        d( |{z } c| {z } c d(b         ∗ −→ (b) Case a≤cand b > d. |{z } a| {z } a−1 b(d−1       |{z} c|{z } c+ 1 d         b+1    ∗ −→ (c) Case a > c. Figure 9. Three cases of ∗-operation on pairs of hooks. 18 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS We are now ready to prove Theorem 3.1 about other special instances of Conjecture 1.1, and of our extension Conjecture 2.9. Proof of part (1) of Theorem 3.1. Let µ= (a, 1b) and ν= (c, 1d) be two hook shapes, and (λ, ρ) be equal to (µ, ν)∗. There are essentially 3 different cases for the effect of the ∗-operation on such a pair of hooks, depending on the relative values of a,b, cand d. These are illustrated in Figure 9. In each case, for sθthat appears both in the expansion of sµsνand sλsρ, our objective is to construct an injection between LR-fillings of θ/ν of type µand LR-fillings of θ/ρ of type λ. Under the above hypothesis, it is easy to check that sθcan appear in the product sµsν, with nonzero coefficient, only if θhas at most two parts larger than 2. Thus, in general, θhas the form θ= (r, s, 2t,1u). Moreover, it is also clear that r≥max(a, c), and t+u+2 ≥max(b+1, d+1), since otherwise it would be impossible to get a nonzero result using the Littlewood-Richardson Rule. d b cc 1111111111 1111111112 1111111111 1 b+1 i+1 . . . i 3 . . . 1111111112 b+2 d . . . 1 b+1 i+1 . . . i 3 . . . Figure 10. From a LR-filling of θ/ν to a LR-filling of θ/ρ. Case (a) (a) (a≤cand b≤d.) If b=dor b+ 1 = d, then (µ, ν) is a fixed point and the result is obvious. We can thus suppose that d≥b+ 2. This situation is illustrated in Figure 9 case (a), and we have λ= (a, 1d−1) and ρ= (c, 1b+1). Thus, the skew shape θ/ρ only differs from that of θ/ν in the first column. There are now d−(b+ 1) new boxes to be filled, which are all at the top end of the first column of θ. Moreover since d≥b+ 2, the first two columns of both θ/ρ and θ/ν are vertical strips. From a LR-filling of θ/ν, of type µ, we construct a filling of θ/ρ as follows. We simply slide down by d−(b+ 1) positions the entries appearing in the first column, and then add new entries b+2,...,din the d−(b+1) cells at the top of this first column. All the other entries of the original filling are kept as they were, and the results stays semistandard since there are no interaction between the first and second columns. The resulting LR-filling is clearly of type ρ. An example of this procedure is given in Figure 10. (b) (a≤cand b > d.) In this case λ= (a, 1d) and ρ= (c, 1b). Hence, contrary to case (a), the first column of θ/ρ now has less boxes to be filled than the first column of θ/ν. To SCHUR-POSITIVITY 19 obtain a LR-filling of θ/ρ starting from one for θ/ν, we rather proceed as follows. Push up by b−dpositions the d+ 1 first entries of the first column up to those in the (d+ 2)th row. Then delete all the entries labeled from d+ 2 to b+ 1, while leaving unchanged the part of the filling in the remaining columns. This clearly produces a LR-filling of θ/ρ. This is illustrated in Figure 11. d c b c . 1111111111 1111111112 1111111111 1 d+1 i+1 . . . i 3 . . . 1111111112 1 d+1 i+1 . . . i 3 . . . b+1 d+2 . . Figure 11. From a LR-filling of θ/ν to a LR-filling of θ/ρ. Case (b) (c) (a≤c.) In this case λ= (a−1,1d−1) and ρ= (c+ 1,1b+1), so that the first row of θ/ρ has one less box than that of θ/ν, so that λ1(µ, ν) = µ1(µ, ν)−1. Note that in every LR-filling involved, the entries in the first row can be only 1’s. We get a LR-filling of θ/ρ from one of θ/ν by the same procedures used for cases (a) or (b), depending on the relative values of band d, after which we remove a copy of 1 from the first row.  Proof of part (2) of Theorem 3.1. To show that Conjecture 2.9 holds for pairs of skew shapes (µ/α, ν/β),where all partitions involved are hooks, with α=β, we proceed as follows. If α=β= 0 then the result follows from part (1). So let α=β6= 0. We first recall (see Figure 9) that for a pair of hooks µ= (a, 1b) and ν= (c, 1d) the possible results of the ∗-operation (7.1) (µ, ν)∗= ((a,1b),(c,1d)) are (a)a=a, b=d−1 c=c, d=b+ 1 (b)a=a, b=d c=c, d=b(c)a=a−1,b=d−1 c=c+ 1,d=b+ 1 We also recall that the pair (α, β) = ((k, 1m),(k, 1m)) is a fixed point for ∗-operation, and that the skew Schur functions sµ/α and sν/β are simply sµ/α =ha−keb−m,and sν/β =hc−ked−m. It follows that the statement that we have to prove simply translates into (7.2) (ha−keb−m) |{z } sλ (hc−ked−m) | {z } sρ −(ha−keb−m) |{z } sµ/α (hc−ked−m) |{z } sν/β 20 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS being Schur positive. In case (b), this is simply vacuously true. For case (a), (7.2) equals (7.3) ha−khc−k(ed−m−1eb−m+1 −ed−meb−m). But a special case of the (dual) Jacobi-Trudi formula states that (7.4) s2k,1ℓ−k= det eℓeℓ+1 ek−1ek, when ℓ≥k≥1. Observe here that the determinant in (7.4) is equal to the determinant obtained by exchanging kand ℓ. To get the positivity of (7.3), we use (7.4) with ℓ=d−m−1 and k=b−m+ 1 when d > b + 1, and ℓ=b−m+ 1 and k=d−m−1 otherwise. Hence (7.3) is simply equal to ha−khc−ks2k,1ℓ−k, which is Schur positive by Pieri’s formula (see [6, Corollary 7.15.3]). Finally, for case (c), (7.2) equals ha−k−1hc−k+1ed−m−1eb−m+1−ha−khc−ked−meb−m= ha−k−1hc−k+1(ed−m−1eb−m+1 −ed−meb−m) + ed−meb−m(ha−k−1hc−k+1 −ha−khc−k) which is readily seen to be positive, by a similar argument.  Proof of part (3) of Theorem 3.1. For ν/β a ribbon, set (λ, ρ) = (0, ν/β)∗. We will show that sλsρcan be expanded as a (positive integer coefficient) sum of skew Schur functions indexed by ribbons, with sν/β appearing with nonzero coefficient. The slightly more general case of weak ribbons is entirely similar. We first need to recall that a N-cell ribbon R=ν/β is entirely described by the sequence of row lengths of R, reding down from the top. This results in a composition c(R) = (c1,...,cn) of N. In term of this composition description, it is classical that the product of two ribbon Schur functions can be expressed as a sum of two ribbon Schur functions: (7.5) sc1,...,cnsd1,...,dk=sc1,...,cn,d1,...,dk+sc1,...,cn+d1,...,dk The two resulting ribbons are illustrated in Figure 12. Let us split the ribbon R=ν/β in Figure 12. The two ribbons in the right hand side of (7.5). two sub-ribbons R′and R′′, according to the inequalities y > x and y≤x, respectively, for cells (x, y) of R. This is illustrated in the left hand side of Figure 13. From Lemma 2.3 it R′ R′′ ∗ −→ λ ρ Figure 13. The ribbons R′and R′′. easily follows that λ=ν/β is a vertical strip and that ρ=ν/β is a horizontal strip. More SCHUR-POSITIVITY 21 specifically, the column lengths of λare equal to the column lengths of R′. Whereas, the row lengths of ρare equal to the row lengths of R′′. This is illustrated in the right hand side of Figure 13. It follows from the definition of skew Schur functions (see [3]) that sλ is simply a product of elementary symmetric functions, one for each column length of R′. Similarly, sρis a product of complete homogeneous symmetric functions, one for each row length of R′′. Repeated applications of the multiplication rule for ribbons (7.5) clearly give non negative coefficient expansions sλ=sR′+X c acscand sρ=sR′′ +X c bcsc, which include respectively the terms sR′and sR′′ , each with coefficient 1. Yet another application of the multiplication rule makes it evident that sRappears in the ribbon expansion of the product of sλand sρ. Thus the theorem is proved.  8. Reduction to a finite set of pairs in bounded height case In this section we show that the bounded height case of Conjecture 1.1 can be reduced to checking that it holds for a finite number of pairs, for any given height. In order to do this, and to state our result, we need some definitions. Let µand θbe two partitions such that µ⊆θand consider the skew partition θ/µ. Given a partition µcontaining a column of height k, we denote µ−1kthe partition obtained by removing this column. In other words, (µ−1k)j:= µj−1,if j≤k, µj,if j > k. We say that µhas a k-full column in θ, if there is a jsuch that the jth column of µand θ Figure 14. A 6-full column. are both of height k. When this is the case, setting β:= θ−1kand γ:= µ−1k, we observe that (8.1) hsθ, sµsνi=hsβ, sγsνi, since, using (6.1), this is clearly equivalent to sθ/µ =sβ/γ which holds trivially. When µ⊆θ, the fact that µhas a k-full column in θis equivalent to (8.2) θk≥µk> θk+1, assuming that θk+1 = 0 when kis the number of parts of θ. 22 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS Proof of Theorem 3.2. We proceed by induction on the number of columns of µ, for the set of partitions µwith height bounded by p, and such that (8.3) µ1> p (ν1+p). Once again, let (λ, ρ) := (µ, ν)∗. For any θ, such that sθappears with nonzero coefficient in sµsν, we will show (8.3) implies that there exists a k, such that both µand λhave a k-full column in θ, and such that (8.4) λ(µ−1k, ν) = λ−1kand ρ(µ−1k, ν) = ρ. It will then follow that hsθ, sµsνi=hsθ−1k, sµ−1ksνiby (8.1) ≤ hsθ−1k, sλ(µ−1k,ν)sρ(µ−1k,ν)iby induction hypothesis =hsθ−1k, sλ−1ksρiby (8.4) =hsθ, sλsρiby (8.1) which will prove the theorem. To show that there is a kwith the properties announced above, we proceed as follows. Observe that at least one of the differences µj−µj+1, where 1 ≤j≤p, is strictly larger then ν1+p, since otherwise µ1= p X j=1 µj−µj+1 ≤p(ν1+p) which would contradict (8.3). We can thus choose kto be the smallest integer, between 1 and p, such that (8.5) µk> µk+1 +ν1+p. For θas above, we must clearly have µi≤θi≤µi+ν1. Thus θk≥µk > µk+1 +ν1+p > θk+1, so that µhas a k-full column in θ, by criteria (8.2). Moreover, for 1 ≤i≤k, it is clear that µi> ν1+p, and thus (1.2) simplifies to λi=µi−i, for 1 ≤i≤k. It follows that λk=µk−k > µk+1 +ν1+ (p−k) ≥θk+1, so that λalso has a k-full column in θ. The last verification that we need to do is that (8.4) holds. Now, it is clear that the first klines of γ:= µ−1kare all too large for the first part SCHUR-POSITIVITY 23 of (2.1) to apply. In fact, considering the way khas been chosen, we see that for 1 ≤i≤k γi−i=µi−(i+ 1) > µ1−(i−1) (ν1+p)−(i+ 1) >(p−i+ 1) (ν1+p)−(i+ 1) ≥ν1−1. This makes it obvious that (8.4) holds, thus finishing our proof.  9. Final remarks We believe that to get a better understanding of the ∗-operation, a refined study of its effect on tableaux and semistandard tableaux will be crucial. For instance this should lead to a proof of “monomial” versions of Conjectures 1.1 and 2.9. More precisely, recall that the expansion of any Schur function in the basis of monomial symmetric functions involves only positive integers. It would thus follow from the conjectures that the expansion of the difference of products considered have positive integer coefficients when expanded in term of monomial symmetric function. In particular, using definition (5.2), one should have (9.1) f(λ,ρ)≥f(µ,ν). whenever (λ, ρ) = (µ, ν)∗. An independent proof of these facts would clearly lend support to the conjectures. 10. Acknowledgments We would like to thank Peter McNamara for the proof of Lemma 2.4 presented in this paper, which is much nicer than our original proof, and for many interesting conversations. We are also grateful to Sergey Fomin for reading an earlier version of this manuscript, and for many useful suggestions. We would also like to thank the anonymous referee for many constructive suggestions. References [1] S. Fomin, D. Stanton,Rim hook lattices, St. Petersburg Math. J. 9 (1998), no. 5, 1007–101. [2] S. Fomin, W. Fulton, Chi-Kwong Li, and Yiu-Tung Poon,Eigenvalues, Singular Values, and Littlewood-Richardson Coefficients, Amer. J. Math.,127 (2005), 101–127. [3] I.G. Macdonald ,Symmetric functions and Hall polynomials. Second edition, Oxford University Press, New York, 1995. [4] P. McNamara,Personal communication. [5] B.E. Sagan,The Symmetric Group, Representations, Combinatorial Algorithms, and Symmetric Functions, GTM 203, Springer, 2000. [6] R.P. Stanley,Enumerative Combinatorics, Volume 2, Cambridge University Press, 1999. 24 FRANC¸OIS BERGERON, RICCARDO BIAGIOLI, AND MERCEDES H. ROSAS (F. Bergeron) D´ epartement de Math´ ematiques, Universit´ e du Qu´ ebec ` a Montr´ eal, Montr´ eal, Qu´ ebec, H3C 3P8, CANADA (R. Biagioli) LaCIM, Universit´ e du Qu´ ebec ` a Montr´ eal, Montr´ eal, Qu´ ebec, H3C 3P8, CANADA (M. Rosas) Department of Mathematics and Statistics, York University, N520 Ross Building, 4700 Keele St. Toronto, Ontario, CANADA E-mail address:[email protected], [email protected], [email protected]