Ring of symmetric functions: Difference between revisions

Revision as of 05:02, 26 April 2012

Revision as of 03:55, 26 December 2012

Line 1:

{{About|the ring of symmetric functions in algebraic combinatorics|general properties of symmetric functions|symmetric function}}

In [[algebra]] and in particular in [[algebraic combinatorics]], the '''ring of symmetric functions''', is a specific limit of the rings of [[symmetric polynomial]]s in ''n'' indeterminates, as ''n'' goes to infinity. This ring serves as universal structure in which relations between symmetric polynomials can be expressed in a way independent of the number ''n'' of indeterminates (but its elements are neither polynomials nor functions). Among other things, this ring plays an important role in the [[representation theory of the symmetric group]]s.

== Symmetric polynomials ==

Line 20 ⟶ 19:

== The ring of symmetric functions ==

Most relations between symmetric polynomials do not depend on the number ''n'' of indeterminates, other than that some polynomials in the relation might require ''n'' to be large enough in order to be defined. For instancerelatance the [[Newton's identities|Newton's identity]] for the third power sum polynomial leads to

:<math>p_3(X_1,\ldots,X_n)=e_1(X_1,\ldots,X_n)^3-3e_2(X_1,\ldots,X_n)e_1(X_1,\ldots,X_n)+3e_3(X_1,\ldots,X_n),</math>

where the <math>e_i</math> denote elementary symmetric polynomials; this formula is valid for all natural numbers ''n'', and the only notable dependency on it is that ''e''_''k''(''X''₁,…,''X''_''n'')&nbsp;=&nbsp;0 whenever ''n''&nbsp;&lt;&nbsp;''k''. One would like to write this as an identity ''p''₃&nbsp;=&nbsp;''e''₁³&nbsp;−&nbsp;3''e''₂''e''₁&nbsp;+&nbsp;3''e''₃ that does not depend on ''n'' at all, and this can be done in the ring of symmetric polynomials. In that ring there are elements ''e''_''k'' for all integers ''k''&nbsp;≥&nbsp;1, and an arbitrary element can be given by a polynomial expression in them.

Line 33 ⟶ 32:

#''S'' is invariant under any permutation of the indeterminates, and

#the degrees of the monomials occurring in ''S'' are bounded.

Note that because of the second condition, power series are used here only to allow infinitely many terms of a fixed degree, rather than to sum terms of all possible degrees. Allowing this is necessary because an element that contains for instance a term ''X''₁ should also contain a term ''X''_''i'' for every ''i''&nbsp;&gt;&nbsp;1 in order to be symmetric. Unlike the whole power series ring, the subring &Lambda;_''R'' is graded by the total degree of monomials: due to condition&nbsp;2, every element of &Lambda;_''R'' is a finite sum of [[Homogeneous_polynomial|homogeneous]] elements of &Lambda;_''R'' (which are themselves infinite sums of terms of equal degree). For every ''k''&nbsp;&ge;&nbsp;0, the element ''e''_''k''&nbsp;&isin;&nbsp;&Lambda;<subthub>''R''</sub> is defined as the formal sum of all products of ''k'' distinct indeterminates, which is clearly homogeneous of degree ''k''.

==== As an algebraic limit ====

Another construction of &Lambda;_''R'' takes somewhat longer to describe, but better indicates the relationship with the rings ''R''[''X''₁,…,''X''_''n'']^{'''S'''_''n''} of symmetric polynomials in ''n'' indeterminates. For every ''n'' there is a surjective [[ring homomorphism]] &rho;_''n'' from the analoguous ring ''R''[''X''₁,…,''X''_''n''+1]^{'''S'''_''n''+1} with one more indeterminate onto ''R''[''X''₁,…,''X''_''n'']^{'''S'''_''n''}, defined by setting the last indeterminate ''X''_''n''+1 to&nbsp;0. Although &rho;_''n'' has a non-trivial kernel, the nonzero elements of that kernel have degree at least <math>n+1</math> (they are multiples of ''X''₁''X''₂&hellip;''X''_''n''+1). This means that the restriction of &rho;_''n'' to elements of degree at most ''n'' is a bijective linear map, and &rho;_''n''(''e''_''k''(''X''₁,…,''X''_''n''+1))&nbsp;=&nbsp;''e''_''k''(''X''₁,…,''X''_''n'') for all ''k''&nbsp;≤&nbsp;''n''. The inverse of this restriction can be extended uniquely to a ring homomorphism &phi;_''n'' from ''R''[''X''₁,…,''X''_''n'']^{'''S'''_''n''} to ''R''[''X''₁,…,''X''_''n''+1]^{'''S'''_''n''+1}, as follows for instance from the [[fundamental theorem of symmetric polynomials]]. Since the images &phi;_''n''(''e''_''k''(''X''₁,…,''X''_''n''))&nbsp;=&nbsp;''e''_''k''(''X''₁,…,''X''_''n''+1) for ''k''&nbsp;=&nbsp;1,&hellip;,''n'' are still [[algebraically independent]] over&nbsp;''R'', the homomorphismhellmorphism &phi;_''n'' is injective and can be viewed as a (somewhat unusual) inclusion of rings. The ring &Lambda;_''R'' is then the "union" ([[direct limit]]) of all these rings subject to these inclusions. Since all &phi;_''n'' are compatible with the grading by total degree of the rings involved, &Lambda;_''R'' obtains the structure of a graded ring.

This construction differs slightly from the one in (Macdonald, 1979). That construction only uses the surjective morphisms &rho;_''n'' without mentioning the injective morphisms &phi;_''n'': it constructs the homogeneous components of &Lambda;_''R'' separately, and equips their direct sum with a ring structure using the &rho;_''n''. It is also observed that the result can be described as an [[inverse limit]] in the category of ''graded'' rings. That description however somewhat obscures an important property typical for a ''direct'' limit of injective morphisms, namely that every individual element (symmetric function) is already faithfully represented in some object used in the limit construction, here a ring ''R''[''X''₁,…,''X''_''d'']^{'''S'''_''d''}. It suffices to take for ''d'' the degree of the symmetric function, since the part in degree ''d'' is of that ring is mapped isomorphically to rings with more indeterminates by &phi;_''n'' for all ''n''&nbsp;&ge;&nbsp;''d''. This implies that for studying relations between individual elements, there is no fundamental difference between symmetric polynomials and symmetric functions.

Line 43 ⟶ 42:

=== Defining individual symmetric functions ===

It should be noted that the name "symmetric function" for elements of &Lambda;_''R'' is a [[misnomer]]: in neither construction the elements are functions, and in fact, unlike symmetric polynomials, no function of independent variables can be associated to such elements (for instance ''e''₁ would be the sum of all infinitely many variables, which is not defined unless restrictions are imposed on the variables). However the name is traditional and well established; it can be found both in (Macdonald, 1979), which says (footnote on p.&nbsp;12)

<blockquote>The elements of &Lambda; (unlike those of &Lambda;_''n'') are no longer polynomials: they are formal infinite sums of monomials. We have therefore reverted to the older terminology of symmetric functions.</blockquote>

(here &Lambda;_''n'' denotes the ring of symmetric polynomials in ''n'' indeterminates), and also in (Stanley, 1999).

Line 49 ⟶ 48:

To define a symmetric function one must either indicate directly a power series as in the first construction, or give a symmetric polynomial in ''n'' indeterminates for every natural number ''n'' in a way compatible with the second construction. An expression in an unspecified number of indeterminates may do both, for instance

:<math>e_2=\sum_{i<j}X_iX_j\,</math>

can be taken as the definition of an elementary symmetric function if the number of indeterminates is infinite, or as the definition of an elementary symmetric polynomial in any finite number of indeterminates. Symmetric polynomials for the same symmetric function should be compatible with the morphisms &rho;<sub>''n''</subthetryp>. (decreasingFor thea numberformal ofdefinition, indeterminatesconsider issuch obtained by setting some of themsequences to zero,be soinfinite thatby theappending coefficientszeroes of(which anydoes monomialnot inalter the remaining indeterminates is unchangedmonomial), and theirdefine degreethe shouldrelation remain"~" bounded.between (Ansuch examplesequences ofthat a family of symmetric polynomialsexpresses that fails both conditionsone is <math>\Pi_{i=1}^nX_i</math>;a thepermuthe family <math>\Pi_{i=1}^n(X_i+1)</math> fails only the second condition.) Any[[monomial symmetric polynomial in ''n'' indeterminates can be used to construct a compatible familypolynomialtation of symmetric polynomials, using the morphisms &rhoother;_''i'' for ''i''&nbsp;&lt;&nbsp;''n'' to decrease the number of indeterminates, and &phi;_''i'' for ''i''&nbsp;&ge;&nbsp;''n'' to increase the number of indeterminates (which amounts to adding all monomials in new indeterminates obtained by symmetry from monomials already present).

The following are fundamental examples of symmetric functions.

* The '''monomial symmetric functions''' ''m''_&alpha;, determined by [[monomial]] ''X''^&alpha; (where &alpha;&nbsp;=&nbsp;(&alpha;₁,&alpha;₂,&hellip;) is a sequence of natural numbers); ''m''_&alpha; is the sum of all monomials obtained by symmetry from ''X''^&alpha;. For a formal definition, consider such sequences to be infinite by appending zeroes (which does not alter the monomial), and define the relation "~" between such sequences that expresses that one is a permutation of the other; then

::<math>m_\alpha=\sum\nolimits_{\beta\sim\alpha}X^\beta.</math>

:This symmetric function correspondsfsponds to the [[monomial symmetric polynomial]] ''m''_&alpha;(''X''₁,&hellip;,''X''_''n'') for any ''n'' large enough to have the monomial ''X''^&alpha;. The distinct monomial symmetric functions are parametrized by the [[integer partition]]s (each ''m''_&alpha; has a unique representative monomial ''X''^&lambda; with the parts </sup>&lambda;_''i'' in weakly decreasing order). Since any symmetric function containing any of the monomials of some ''m''_&alpha; must contain all of them with the same coefficient, each symmetric function can be written as an ''Rh''-linear combination of monomial symmetric functions, and the distinct monomial symmetric functions form a basis of &Lambda;_''R'' as ''R''-[[module (mathematics)|module]].

* The '''elementary symmetric functions''' ''e''_''k'', for any natural numberknumber ''k''; one has ''e''_''k''&nbsp;=&nbsp;''m''_&alpha; where <math>X^\alpha=\Pi_{i=1}^kX_i</math>. As a power series, this is the sum of all distinct products of ''k'' distinct indeterminates. This symmetric function corresponds to the [[elementary symmetric polynomial]] ''e''_''k''(''X''₁,&hellip;,''X''_''n'') for any ''n''&nbsp;&ge;&nbsp;''k''.

* The '''power sum symmetric functions''' ''p''_''k'', for any positive integer ''k''; one has ''p''_''k''&nbsp;=&nbsp;''m''_(''k''), the monomial symmetric function for the monomial ''X''₁^''k''. This symmetric function corresponds to the [[power sum symmetric polynomial]] ''p''_''k''(''X''₁,&hellip;,''X''_''n'')&nbsp;=&nbsp;''X''₁^''k''+&hellip;+''X''_''n''^''k'' for any ''n''&nbsp;&ge;&nbsp;1.

* The '''complete homogeneous symmetric functions''' ''h''_''k'', for any natural number ''k''; ''h''_''k'' is the sum of all monomial symmetric functions ''m''_&alpha; where &alpha; is a partition of&nbsp;''k''. As a power series, this is the sum of ''all'' monomials of degree ''k'', which is what motivates its name. This symmetric function corresponds to the [[complete homogeneous symmetric polynomial]] ''h''_''k''(''X''₁,&hellip;,''X''_''n'') for any ''n''&nbsp;&ge;&nbsp;''k''.

* The '''Schur functions''' ''s''_&lambda; for any partition &lambda;, which corresponds to the [[Schur polynomial]] ''s''_&lambda;(''X''₁,&hellip;,''X''_''n'') for any ''n'' large enough to have the monomial ''X''^&lambda;.

There is no power sum symmetric function ''p''₀: although it is possible (and in some contexts natural) to define <math>p_0(X_1,\ldots,X_n)=\Sigma_{i=1}^nX_i^0=n</math> as a symmetric ''polynomial'' in ''n'' variables, these values are not compatible with the morphisms &rho;_''n''. The "discriminant" <math>\textstyle(\prod_{i<j}(X_i-X_j))^2</math> is another example of an expression giving a symmetric polynomial for all ''n'', but not defining any symmetric function. The expressions defining [[Schur polynomial]]s as a quotient of alternating polynomials are somewhat similar to that for the discriminant, but the polynomials ''s''_&lambda;(''X''₁,&hellip;,''X''_''n'') turn out to be compatible for varying ''n'', and therefore do define a symmetric functionmials in ''n'' indeterminates for any natural number ''n'' may be designated by ''P''(''X''₁,&hellip;,''X''_''n''). The second definition of the ring of symmetric functions implies the following fundamental principle:

=== A principle relating symmetric polynomials and symmetric functions ===

For any symmetric function ''P'', the corresponding symmetric polynomials in ''n'' indeterminates for any natural number ''n'' may be designated by ''P''(''X''₁,&hellip;,''X''_''n''). The second definition of the ring of symmetric functions implies the following fundamental principle:

:If ''P'' and ''Q'' are symmetric functions of degree ''d'', then one has the identity <math>P=Q</math> of symmetric functions if and only one has the identity ''P''(''X''₁,&hellip;,''X''_''d'')&nbsp;=&nbsp;''Q''(''X''₁,&hellip;,''X''_''d'') of symmetric polynomials in ''d'' indeterminates. In this case one has in fact ''P''(''X''₁,&hellip;,''X''_''n'')&nbsp;=&nbsp;''Q''(''X''₁,&hellip;,''X''_''n'') for ''any'' number ''n'' of indeterminates.

Line 70 ⟶ 62:

This is because one can always reduce the number of variables by substituting zero for some variables, and one can increase the number of variables by applying the homomorphisms &phi;_''n''; the definition of those homomorphisms assures that &phi;_''n''(''P''(''X''₁,&hellip;,''X''_''n''))&nbsp;=&nbsp;''P''(''X''₁,&hellip;,''X''_''n''+1) (and similarly for ''Q'') whenever ''n''&nbsp;&ge;&nbsp;''d''. See [[Newton's identities#Derivation of the identities|a proof of Newton's identities]] for an effective application of this principle.

== Properties of the ring of symmetric functions ==

=== Identities ===

The ring of symmetric functions is a convenient tool for writing identities between symmetric polynomials that are independent of the number of indeterminates: in &Lambda;_''R'' there is no such number, yet by the above principle any identity in &Lambda;_''R'' automatically gives identities the rings of symmetric polynomials over ''R'' in any number of indeterminates. Some fundamental identities are

Line 84 ⟶ 74:

# The set of monomial symmetric functions parametrized by partitions form a basis of &Lambda;_''R'' as graded ''R''-[[module (mathematics)|module]], those parametrized by partitions of ''d'' being homogeneous of degree ''d''; the same is true for the set of Schur functions (also parametrized by partitions).

# &Lambda;_''R'' is [[isomorphic]] as a graded ''R''-algebra to a polynomial ring ''R''[''Y''₁,''Y''₂,…] in infinitely many variables, where ''Y''_''i'' is given degree&nbsp;''i'' for all ''i''&nbsp;&gt;&nbsp;0, one isomorphism being the oneonmorphism]] &omega; of &Lambda;_''R'' that sendsinterchanges the elementary symmetric functions ''Ye''_''i'' toand the complete homogeneous symmetric function ''eh''_''i'' for all ''i''. It also sends each power sum symmetric function ''p''_''i'' to (−1)^''i''−1&nbsp;&isin;&nbsp;&Lambda;''p''_''Ri'', forand everyit permutes the Schur functions among each other, interchanging ''s''_&nbsplambda; and ''is''_&lambda;^t where &lambda;^t is the transpose partition of &lambda;.

# There is an [[Involution (mathematics)|involutary]] [[automorphism]] &omega; of &Lambda;_''R'' that interchanges the elementary symmetric functions ''e''_''i'' and the complete homogeneous symmetric function ''h''_''i'' for all ''i''. It also sends each power sum symmetric function ''p''_''i'' to (−1)^''i''−1&nbsp;''p''_''i'', and it permutes the Schur functions among each other, interchanging ''s''_&lambda; and ''s''_&lambda;^t where &lambda;^t is the transpose partition of &lambda;.

Property 2 is the essence of the [[fundamental theorem of symmetric polynomials]]. It immediately implies some other properties:

Line 91 ⟶ 80:

* The [[Hilbert–Poincaré series]] of &Lambda;_''R'' is <math>\textstyle\prod_{i=1}^\infty\frac1{1-t^i}</math>, the [[Partition (number theory)#Generating function|generating function]] of the [[integer partition]]s (this also follows from property&nbsp;1);

* For every ''n''&nbsp;&gt;&nbsp;0, the ''R''-module formed by the homogeneous part of &Lambda;_''R'' of degree ''n'', modulo its intersection with the subring generated by its elements of degree strictly less than ''n'', is free of rank&nbsp;1, and (the image of) ''e''_''n'' is a generator of this ''R''-module;

* For every family of symmetric functions (''f''_''i'')_''i''&gt;0 in which ''f''_''i'' is homogeneous of degree&nbsp;''i'' and gives a generator of the free ''R''-module off the previous point (for all ''i''), there is an alternative isomorphism of graded ''R''-algebras from ''R''[''Y''₁,''Y''₂,…] as above to &Lambda;_''R'' that sends ''Y''_''i'' to ''f''_''i''; in other words, the family (''f''_''i'')_''i''&gt;0 forms a set of free polynomial generators of &Lambda;_''R''.

This final point applies in particular to the family (''h''_''i'')_''i''&gt;0 of complete homogeneous symmetric functions.

Line 100 ⟶ 89:

=== Generating functions ===

The first definition of &Lambda;_''R'' as a subring of ''R'f'[[''X''₁,''X''₂,…]] allows expression the [[generating function]]s of several sequences of symmetric functions to be elegantly expressed. Contrary to the relations mentioned earlier, which are internal to &Lambda;_''R'', these expressions involve operations taking place in ''R''<nowiki>[[</nowiki>''X''₁,''X''₂,…;''t''<nowiki>]]</nowiki> but outside its subring &Lambda;_''R''<nowiki>[[</nowiki>''t''<nowiki>]]</nowiki>, so they are meaningful only if symmetric functions are viewed as formal power series in indeterminates ''X''_''i''. We shall write "(''X'')" after the symmetric functions to stress this interpretation.

The generating function for the elementary symmetric functions is

:<math>E(t)=\sum__{k\geq0}e_k(XX_it)t^k\right)=\prod_{i=1}^\infty(\frac1{1+-X_it)}.</math>

Similarly one has for complete homogeneous symmetric functions

:<math>H(t)=\sum_{k\geq0}h_k(X)t^k=\prod_{i=1}^\infty\left(\sum_{k\geq0}(X_it)^k\right)=\prod_{i=1}^\infty\frac1{1-X_it}.</math>

The obvious fact that <math>E(-t)H(t)=1=E(t)H(-t)</math> explains the symmetry between elementary and complete homogeneous symmetric functions.

The generating function for the power sum symmetric functions can be expressed as