SYMMETRIC FUNCTIONS Alain Lascoux CNRS, Institut Gaspard Monge, Universit(cid:19)e de Marne-la-Vall(cid:19)ee, 77454 Marne-la-Vall(cid:19)ee Cedex, France Currentaddress: CenterforCombinatorics,NankaiUniversity,Tianjin300071, P.R. China E-mail address: [email protected] URL: http://phalanstere.univ-mlv.fr/ al 1991 Mathematics Subject Classi(cid:12)cation. Primary 05, 05; Secondary 05, 05 To the Center of Combinatorics, and ProfessorB. Chen. Abstract. Course about symmetric functions, given at Nankai University, October-November 2001. Contents Chapter 1. Symmetric functions 1 1.1. Alphabets 1 1.2. Partitions 1 1.3. Generating Functions of symmetric functions 6 1.4. Matrix generating functions 8 1.5. Cauchy formula 13 1.6. Scalar Product 15 1.7. Di(cid:11)erential calculus 16 1.8. Operators on isobaric determinants 18 1.9. Pieri formulas 23 Exercises 25 Chapter 2. Recurrent Sequences 29 2.1. Recurrent Sequences and Complete Functions 29 2.2. Using the Roots of the Characteristic Polynomial 30 2.3. Invariants of Recurrent Sequences 31 2.4. Companion Matrix 33 2.5. Some Classical Sequences 36 Exercises 37 Chapter 3. Change of Basis 39 3.1. Complete to Schur : (SI; S ) 39 J 3.2. Monomial to Schur : ((cid:9) ; S ) 40 I J 3.3. Double Kostka matrices. 41 3.4. Complete to Monomials : (SI; SJ) 42 3.5. Power sums to Schur : ((cid:9)I; S ) 44 J 3.6. Newton relations and Waring formula 45 3.7. Monomial to Powersums : ( ; (cid:9)I) 47 J Exercises 49 Chapter 4. Symmetric Functions as Operatorsand (cid:21)-Rings 51 4.1. Algebraic Operations on Alphabets 51 4.2. Lambda Operations 52 4.3. Interpreting Polynomials and q-series 52 4.4. Lagrange Inversion 54 Exercises 56 Chapter 5. Transformation of alphabets 61 5.1. Specialization of alphabets 61 5.2. Bernoulli Alphabet 61 iii iv CONTENTS 5.3. Uniform shift on alphabets, and binomial determinants 64 5.4. Alphabet of successive powers of q 66 5.5. q-specialization of monomial functions 67 5.6. Square Root of an Alphabet 68 5.7. p-cores and p-quotients 71 5.8. p-th root of an alphabet 73 5.9. Alphabet of p-th roots of Unity 74 5.10. p-th root of 1 74 Exercises 76 Appendix A. Correction of exercises 81 .1 81 x .2 85 x .3 87 x .4 89 x .5 94 x Bibliography 101 Index 103 CHAPTER 1 Symmetric functions ooo’oooooo’ooo ooo’oooooo’oooooo’ooo oooo’ooooo’oooooo’ooo oooo’ooooo’ooo ooo’oooooo’oooooo’ooo oooo’ooooo’oooooo’ooo oooo’ooooo’ooo 1.1. Alphabets We shall handle functions on di(cid:11)erent sets of indeterminates (called alphabets, though we shall mostly use commutative indeterminates for the moment). A symmetric function of an alphabet A is a function of the letters which is invariant under permutation of the letters of A. Thesimplersymmetricfunctionsarebestde(cid:12)nedthroughgeneratingfunctions. We shall not use the classical notations for symmetric functions (as they can be found in Macdonald’s book), except in the programs (paragraphs beginning with ACE >andusingtypewritercharacters)becauseitwillbecomeclearinthecourse of these lectures that we need to consider symmetric functions as functors, and connect them with operations on vector spaces and representations. It is a small burden imposed on the reader,but the compact notations that we propose greatly simpli(cid:12)es manipulations of symmetric functions. Notice that exponents are used for products, and that SJ is di(cid:11)erent from S , except if J is of length one (i.e. is J an integer). J =[j ;j ;:::] (cid:3)J =(cid:3)j1(cid:3)j2 & SJ =Sj1Sj2 & (cid:9)J =(cid:9)j1(cid:9)j2 1 2 ) (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) (cid:1)(cid:1)(cid:1) are di(cid:11)erent from S , etc. J J Of course, when indices are of length 1, one has Sj =S ; (cid:3)j =(cid:3) ; (cid:9)j =(cid:9) : j j j We need operations on alphabets, the (cid:12)rst one being the addition, that is the disjoint union that we shall denote by a ‘+’-sign : A= a ; B= b A+B:= a b f g f g 7! f g[f g (cid:16) (cid:17) More operations will be introduced in Chapter 4. 1.2. Partitions A weakly increasing sequence of strictly positive numbers I =[i ; i ;:::; i ] is 1 2 ‘ called a partition of the number n of length ‘(I)=‘, where n= I :=i + +i . 1 ‘ j j (cid:1)(cid:1)(cid:1) Onealsousesweaklydecreasingsequencesinsteadofincreasingones,buttohandle minors of matrices, it is preferable to choose our convention. A partitionI has a graphicalrepresentationdue to Ferrers, which is calledits diagram: it is a diagram of square boxes left packed, i ; i ;:::; i being the num- 1 2 ‘ ber of boxes in the successiverows. Readingthe number of boxes in the successive 1 2 1. SYMMETRIC FUNCTIONS columns, one obtains another partition I which is called the conjugate partition. Conjugating partitionsis aninvolutiveoperationwhich canbe interpreted assym- metry along the main diagonal, for what concerns diagrams. e For example, when I =[2;3;5], then I =[1;1;2;3;3]and their diagrams are e & : ApartitionI willbeidenti(cid:12)edwithanyvectorobtainedbyconcatenatinginitial zeroes. Thisiscoherentwithidentifyingpartitionsandtheirdiagrams,becauseone can start by reading empty rows! Let Part(n) be the set of partitions of n. It is obtained by ACE> ListPart(4); [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]] The diagrams are given by the following function, where one can choose two symbols, one to represent the boxes the boxes of the diagram, another for the outside : ACE> [Part2Mat([5,3,2]), Part2Mat([5,3,2],’alphabet’=[‘#‘,‘.‘])]; [1 1 0 0 0] [# # . . .] [[1 1 1 0 0], [# # # . .]] [1 1 1 1 1] [# # # # #] There are two operations on partitions, ‘+’ and ‘ ’ : [ Part(m) Part(n) Part(m+n) (cid:2) ! whichareexchangedunderconjugation: (I;J) I+J istheadditionofpartitions, ! normalizingthemtobelongtothesamespaceNr,andI J isthepartitionobtained [ by reordering the concatenation of I and J into a partition. With I = [1;3;3;3], J =[2;4], one has : (cid:3) (cid:4)(cid:4) (cid:4) (cid:3)(cid:3)(cid:3) ; (cid:3)(cid:3)(cid:3)(cid:4) (cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:4)(cid:4) (cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:3)(cid:4)(cid:4) (cid:4)(cid:4)(cid:4)(cid:4) I J ; I +J [ To order Part(n), one uses, instead of partitions, their cumulative sums and e e one puts the componentwise order on these new vectors. Definition 1.2.1. Givenavectorinv Nn,itscumulativesum visthevector 2 v =[v1; v1+v2; :::;v1+v2+ +vn] : (cid:1)(cid:1)(cid:1) Then-thcumulativesum (resp. cumulativesum)ofapartitionI oflength‘(I) n (cid:20) isthecumulativesumofthevectorobtainedbyconcatenatingn ‘(I)initialzeroes (cid:0) to I (resp. n being the weight of I). 1.2. PARTITIONS 3 Given two partitions I;J of the same integer n, I is smaller than J for the dominance order i(cid:11) I is smaller than J componentwise, i.e. I J ; I J ; :::; I J : 1 1 2 2 n n (cid:20) (cid:20) (cid:20) Cumulative sums of partitions satisfy convexity inequalities that characterize them. It is immediate to check : Lemma 1.2.2. An element u Nn is the cumulative sum of a partition i(cid:11) 2 (1.2.1) 2u u +u ; 1<i<n : i i 1 i+1 (cid:20) (cid:0) But now the supremum (componentwise) of two vectors satisfying inequalities (1.2.1) also satis(cid:12)es the same inequalities, and this allows to de(cid:12)ne the supremum of two partitions : Definition 1.2.3. The supremum I J of two partitions I;J of n is the only _ partition K such that sup(I; J) is the n-th cumulative sum of K. One could have taken the r-th cumulative sum of I, J, for any r ‘(I);‘(J). (cid:21) One de(cid:12)nes the in(cid:12)mum I J of two partitions of the same weight by using ^ conjugation : (1.2.2) I J := I J ^ _ Beware that the minimum compone(cid:0)ntwise of(cid:1)two cumulative sums is not nec- essarily the cumulative sum of a partition.e e e For example, take I = [1;1;1;5], J = [0;2;2;4]. Then I = [1;2;3;8], J = [0;2;4;8], sup(I;J) = [1;2;4;8] = K, with K = [1;1;2;4] = I J. On the other _ hand, inf(I;J) = [0;2;3;8] is the cumulative sum of [0;2;1;5], which is not a partition. Conjugating, one has I = [1;1;1;1;4], J = [0;1;1;3;3], with cumulative sums [1;2;3;4;8],[0;1;2;5;8] and supremum [1;2;3;5;8]. Therefore I J = _ [1;1;1;2;3]and e e I J = I J =[1;1;1;2;3] =[1;2;5] : e e ^ _ Onecouldhaveusethe(cid:0)cumulati(cid:1)vesumsstartingfromtheright,orequivalently, the cumulative sums on desceendineg peartitions. e Thetwooperations ; ,de(cid:12)nealatticestructureonPart(n)(withminimum _ ^ element [n] and maximal element [1n]). The poset of partitions(partially ordered set { bad terminology,because every order is partial, unless otherwise speci(cid:12)ed !) is not a rank poset, i.e. maximal chains between two comparable elements do not have the same length. For example, Part(8) contains the following piece, which contains the four partitionsthatwehavejustconsidered,writingtheircumulativesumsontheright: 1124 1248 . & . & 224 0248 1115 1238 : # $ # 134 0148 & . & . 125 0138 However, it is easy to characterize consecutive elements : 4 1. SYMMETRIC FUNCTIONS Lemma 1.2.4. Let I; J be two partitions of the same number. If I <J & there is no K such that I <K <J ; then either p;k N: J =J0pk+2J00 & I =J0; p 1; pk; p+1; J00 or 9 2 (cid:0) p;q N: J =J0pqJ00 & I =J0; p 1; q+1; J00 : 9 2 (cid:0) Notice that the two cases are exchanged by conjugation of partition, so that the dominance order is reversed under conjugation. The possible pairs in Lemma 1.2.4 look like what follows : (cid:3) (cid:3) (cid:3) (cid:3) (cid:3)(cid:4) (cid:3) (cid:3) (cid:3) J = (cid:3)(cid:3) I = (cid:3)(cid:3) ; J = (cid:3) I = (cid:3) (cid:3)(cid:3) (cid:3)(cid:3) (cid:3)(cid:4) (cid:3) ) ) (cid:3)(cid:3) (cid:3)(cid:3)(cid:4) (cid:3)(cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:3)(cid:4) (cid:3)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3) Pushing a box down gives a smaller partition, but it is not true that it gives (cid:3)(cid:4) (cid:3) a pair of consecutive partitions : (cid:3)(cid:3)(cid:3) and (cid:3)(cid:3)(cid:3) are not consecutive, because (cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:4) the move of the black box can be performed in two steps: (cid:3)(cid:4) (cid:3)(cid:4) (cid:3) (cid:3)(cid:3) (cid:3)(cid:3) (cid:3)(cid:3)(cid:4) (cid:3)(cid:3)|(cid:3) ) (cid:3)(cid:3)(cid:3) ) (cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3) | | LetJ;I beapairofpartitionssuchthatthediagramofJ containsthediagram of I. Then the set di(cid:11)erence of the two diagrams is called a skew diagram and denoted J=I ( adding common boxes to I and J does not change J=I. In some problems, one has to consider pairs (J;I) rather than J=I). If J=I contains no 2 2 sub-diagram and is connected (resp. J=I contains no (cid:2) two boxes in the same column, res. no two boxes in the same row), then J=I is called a ribbon (resp. horizontal strip, resp. vertical strip). There are strips which are both vertical and horizontal, for example a single box. (cid:4)(cid:4) (cid:4)(cid:4) (cid:3)(cid:4) (cid:3)(cid:4)(cid:4)(cid:4) (cid:3)(cid:3)(cid:3)(cid:4) (cid:3)(cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:4)(cid:4) (cid:3)(cid:3)(cid:3)(cid:3)(cid:4) (cid:3)(cid:3)(cid:3)(cid:3)(cid:4) (cid:3)(cid:3)(cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:3)(cid:3) (cid:3)(cid:3)(cid:3)(cid:3)(cid:4) ribbon horizontal strip vertical strip A partition of the type [1(cid:12); (cid:11)+1] is called a hook and is denoted ((cid:11)&(cid:12)). The decomposition of the diagram of a partition I into its diagonal hooks (i.e. hooks having their head on the diagonal) is called the Frobenius code of I and denoted Frob(I) = ((cid:11) ;(cid:11) ;:::;(cid:11) &(cid:12) ;(cid:12) ;:::;b ) (where r, the number of boxes in the 1 2 r 1 2 r main diagonal, is called the rank of the partition). (cid:3)(cid:4) I =[2;4;5;6]= (cid:3)(cid:4) gives Frob([2;4;5;6])=(531&320): (cid:3)(cid:4)~(cid:4)~(cid:4)(cid:4) (cid:3)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3) Givenaboxinadiagram,itscontent isitsdistancetothe maindiagonal. The multiset of contents allows to recover the diagram, hence the partition. Replacing each box by its content, one has, for example, that I = [2;4;5;6] has contents 3 2 (cid:0)2(cid:0)101 and multiset ( 3)1; ( 2)2; ( 1)2; 03; 13; 22; 32; 41; 51 . (cid:0)1(cid:0)0 123 f (cid:0) (cid:0) (cid:0) g (cid:0)0 1 2345 1.2. PARTITIONS 5 Finally (for the moment!), one can code a partition by the word obtained by reading the border of its diagram : 0 for an horizontal step, 1 for a vertical step. 0 0 1 (cid:3)(cid:3) 0 0 1 I =[2;4;5;6] border= (cid:3)(cid:3)(cid:3)(cid:3) 0 1 =[0;0;1;0;0;1;0;1;0;1] ) (cid:3)(cid:3)(cid:3)(cid:3)(cid:3) 0 1 (cid:3)(cid:3)(cid:3)(cid:3)(cid:3)(cid:3) Taking reverse wordsand exchanging 0 and 1 corresponds to taking conjugate partitions. In fact, all operations on words on two letters induce operations on partitions that we leave to the reader the pleasure to discover. It is appropriate concatenate left 1’s and right 0’s to a border word. This amounts to consider that the partition is contained in a rectangular partition mn (where m is the total number of 0’s and n the total number of 1’s). Since a 0, 1 (cid:0) sequenceisspeci(cid:12)ed byits lengthand the position of the 0’s, onehasthe following lemma that one shall need in determinantal identities. Lemma 1.2.5. Let I = [i ;:::;i ] Nn be a partition contained in mn, and 1 n 2 J =[j ;:::;j ] be its conjugate. Then 1 m fi1+1; i2+2; :::;in+ng and fm+n+1(cid:0)j1(cid:0)1; m+n+1(cid:0)j2(cid:0)2; :::;m+n+1(cid:0)jm(cid:0)mg are complementary sets in 1; :::; m+n . f g For example, take m = 5; n = 4. Adding [1;2;3;4] to I = [0;0;2;4], one gets [1;2;5;8]; the partition I = [0;1;1;2;2] gives under the same operation [1;3;4;6;7], and [10 1;10 3;10 4;10 6;10 7] = [9;7;6;4;3] is the com- (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) plementary set of 1;2;5;8]. e ACE> Part2Frob([6,5,4,2]); [[5, 3, 1], [3, 2, 0]] ACE> Frob2Part(%); [6, 5, 4, 2] ACE> [Part2Border([6,5,4,2]), Part2Border(Part2Conjugate([6,5,4,2]))]; [[0, 0, 1, 0, 0, 1, 0, 1, 0, 1], [0, 1, 0, 1, 0, 1, 1, 0, 1, 1]] Given a box (cid:3) in the diagram of a partition J, let its leg be the set of boxes in the same column above it, its arm be the set of boxes in the same row, on its right. The hook relative to (cid:3) is the union of the leg, the arm and the box itself, the totalnumber of boxesbeing the hook length of (cid:3) in the diagram. It isusual to directly write the hook length of a box in the box itself. Thecontent ofaboxinadiagramisitsdistancetothemaindiagonal,counted negative in the North-West sector. For example, for J = [2;3;3;6;6], one has the following hook lengths and contents : 2 1 4 3 (cid:0) (cid:0) 4 3 1 3 2 1 (cid:0) (cid:0) (cid:0) 5 4 2 2 1 0 (cid:0) (cid:0) 9 8 6 3 2 1 1 0 1 2 3 4 (cid:0) 10 9 7 4 3 2 0 1 2 3 4 5 Hook lengths Contents These informations about a partition can also been read on the other codings of the partition, like its border, or its Frobenius decomposition in diagonal hooks. 6 1. SYMMETRIC FUNCTIONS One can relate the contents and hook lengths as follows. Let J be a partition in Nn (it can have initial zeros). Let v :=[j1+0; j1+1; :::; jn+n(cid:0)1]. Taking row r of the diagram of J, one sees that the set of hook lengths in this row is such that h(cid:3) = 1; 2; :::; vr (vr vi) : i<r ; f g f gnf (cid:0) g and therefore, in total, one has the following equality between multisets : (1.2.3) fh(cid:3) : (cid:3)2Diagr(J)g=[1(cid:20)r(cid:20)nf1; :::; vrgn[f(vr(cid:0)vi): 1(cid:20)i<r (cid:20)ng : 1.3. Generating Functions of symmetric functions Taking an extra indeterminate z, one has three fundamental series 1 1 (1.3.1) (cid:21) (A):= (1+za) ; (cid:27) (A):= ; (cid:9) (A):= ziai=i z z z 1 za a A a A (cid:0) i=1a A Y2 Y2 XX2 theexpansionofwhichgivestheelementarysymmetricfunctions(cid:3)i(A)thecomplete functions Si(A), and the power sums (cid:9) (A) : i 1 (1.3.2) (cid:21) (A)= zi(cid:3)i(A) ; (cid:27) (A)= ziSi(A) ; (cid:9) (A)= zi(cid:9) (A)=i : z z z i i=1 X X X Since log(1=(1 a)= ai=i, one has (cid:0) i>0 (1.3.3) (cid:27)z(A)=Pexp((cid:9)z(A)) ; (cid:9)z(A)=log((cid:27)z(A)) Addition of alphabets implies product of generating series (1.3.4) (cid:21) (A+B)=(cid:21) (A)(cid:21) (B) ; (cid:27) (A+B)=(cid:27) (A)(cid:27) (B) : z z z z z z However, since one can invert formal series beginning by 1, or take any power of them, one can extend (1.3.1) by setting : (1 zb) (1.3.5) (cid:27)z(A B):= b2B (cid:0) ; (cid:27)z(cA)=((cid:27)z(A))c ; c C : (cid:0) (1 za) 2 Qa A (cid:0) 2 WhenB=0,orA=0,oQnerecoversthetwoseries(cid:27)z(A)and(cid:27)z( B)=(cid:21) z(B). (cid:0) (cid:0) Notice that the addition of alphabets satisfy the usual properties of addition : (cid:27) ( A) is the inverse of (cid:27) (A) because A A = 0 and (cid:27) (0) = 1. Similarly, the z z z (cid:0) (cid:0) identity (A+C) (B+C)=A B translates, atthe levelof generatingseries,the (cid:0) (cid:0) fact that (1 zb) (1 zc) (1 zb) b (cid:0) c (cid:0) = b (cid:0) ; (1 za) (1 zc) (1 za) Qa (cid:0) Qc (cid:0) Qa (cid:0) andnobodywilldenythatonecansimplifyafactorcommontothe numeratorand Q Q Q denominator of a rational function ! Formal series in z beginning by z0 should be treated as generating series of complete or elementary symmetric functions of some formal alphabet, or of a dif- ferenceoftwoalphabets(onealphabetissu(cid:14)cient,butonehasmore(cid:13)exibilitywith twoalphabets),thatonecanmanipulatewithouthavingaccesstotheletterswhich compose them. This is indeed what one does with a polynomial, even when one is notabletofactorizeit. OnewritesamonicpolynomialP(x)asP(x)= (x a), Abeing the alphabet of zerosof P(x). Now, (x a)2, (x a2a)2,Atos(cid:0)how a A (cid:0) a A (cid:0)Q afewexamples,areperfectlyde(cid:12)nedpolynomial2swhosecoe(cid:14)ci2entscanbewritten Q Q in terms of the coe(cid:14)cients of P, though they have been de(cid:12)ned in terms of the roots of P (but we respected the symmetry between the roots of P!).