Symmetric polynomial
In mathematics, a symmetric polynomial is a multivariate polynomial that remains invariant under any permutation of its variables; that is, for a polynomial f(x_1, \dots, x_n) in the polynomial ring over a field F, f is symmetric if f(x_{\sigma(1)}, \dots, x_{\sigma(n)}) = f(x_1, \dots, x_n) for every permutation \sigma in the symmetric group S_n.[1][2] The set of all symmetric polynomials in n variables forms a subring of the full polynomial ring F[x_1, \dots, x_n], generated by the elementary symmetric polynomials e_k(x_1, \dots, x_n) = \sum_{1 \leq i_1 < \cdots < i_k \leq n} x_{i_1} \cdots x_{i_k} for k = 1, \dots, n, which correspond to the coefficients (up to sign) of the monic polynomial (t - x_1) \cdots (t - x_n).[1][3] A foundational result, known as the fundamental theorem of symmetric polynomials, states that every symmetric polynomial can be uniquely expressed as a polynomial in these elementary symmetric polynomials, providing a complete set of generators for the ring.[1][4] Notable examples include the power sum polynomials p_k(x_1, \dots, x_n) = \sum_{i=1}^n x_i^k, which can be recursively expressed in terms of the elementary symmetric polynomials via Newton's identities, and simpler cases like the first elementary symmetric polynomial e_1 = x_1 + \cdots + x_n or the complete homogeneous symmetric polynomials h_k = \sum_{1 \leq i_1 \leq \cdots \leq i_k \leq n} x_{i_1} \cdots x_{i_k}.[1][3] Symmetric polynomials play a central role in algebraic contexts, such as determining the coefficients of polynomials from their roots without regard to order, and appear in applications to Galois theory, representation theory, and the study of invariants under group actions.[3][1] Historically, their properties were leveraged by Carl Friedrich Gauss in his second proof of the fundamental theorem of algebra around 1816, using symmetric functions to analyze polynomial roots.[1]Definition and Properties
Formal Definition
In mathematics, a symmetric polynomial in n variables x_1, \dots, x_n over a field K, typically the rationals \mathbb{Q} or the complexes \mathbb{C}, is a polynomial P \in K[x_1, \dots, x_n] such that P(\sigma(x_1), \dots, \sigma(x_n)) = P(x_1, \dots, x_n) for every permutation \sigma in the symmetric group S_n.[1][5] The set of all symmetric polynomials in n variables over K forms a subring of the polynomial ring K[x_1, \dots, x_n], denoted \Lambda_n(K) or \Sym_n(K).[5][2] Basic forms of symmetric polynomials include multilinear symmetric polynomials, which are linear in each variable separately and thus homogeneous of degree equal to the number of variables in the monomials. For instance, in three variables, a multilinear symmetric polynomial has degree 3 and consists of terms where each variable appears exactly once in the product, symmetrized over permutations.[6]Basic Properties and Invariance
A symmetric polynomial in the variables x_1, \dots, x_n over a field k is invariant under the action of the symmetric group S_n, which permutes the variables via \sigma \cdot f(x_1, \dots, x_n) = f(x_{\sigma(1)}, \dots, x_{\sigma(n)}) for \sigma \in S_n.[7] The ring of invariants \Lambda_n = k[x_1, \dots, x_n]^{S_n} thus consists precisely of the symmetric polynomials, and this fixed-point subring inherits the structure of a commutative ring from the polynomial ring.[7] The fundamental theorem of symmetric polynomials states that every element of \Lambda_n can be uniquely expressed as a polynomial in the elementary symmetric polynomials e_1, \dots, e_n.[4] This uniqueness follows from the algebraic independence of the e_i and the fact that they generate \Lambda_n as a k-algebra.[4] Newton's identities provide a recursive relation that expresses the power-sum symmetric polynomials in terms of the e_i, facilitating explicit computations of this representation.[4] The ring \Lambda_n is \mathbb{N}-graded by total degree, with the homogeneous component \Lambda_n^d spanned by the symmetric monomials of degree d.[7] The dimension of \Lambda_n^d equals the number of integer partitions of d into at most n parts, reflecting the combinatorial structure of the ring.[7] Since the e_i are homogeneous of degrees $1 through n and form a regular sequence of algebraically independent generators, \Lambda_n is isomorphic to a polynomial ring in n variables with the induced grading, yielding the Hilbert series H_{\Lambda_n}(t) = \prod_{k=1}^n \frac{1}{1 - t^k}. [4] The monomial symmetric polynomials m_\lambda, indexed by partitions \lambda of length at most n, form a \mathbb{Z}-basis for \Lambda_n.[7] This basis arises by averaging monomials over S_n-orbits and provides a monomial-like description of the ring's elements.[7]Examples and Illustrations
Elementary Examples
A fundamental example of a symmetric polynomial in two variables is P(x, y) = x + y. This expression remains unchanged under the permutation that swaps x and y, yielding y + x = x + y.[1] Constant polynomials, such as P(x, y) = 1, are trivially symmetric, as they do not depend on the variables and thus invariant under any permutation.[5] In three variables, consider P(x, y, z) = x^2 + y^2 + z^2. Any permutation of x, y, z, such as cycling to y, z, x, results in y^2 + z^2 + x^2, which equals the original polynomial.[1] Similarly, the linear sum x + y + z is symmetric for the same reason, with permutations merely reordering the terms without altering the value. To visualize this, expand (x + y + z)^2 = x^2 + y^2 + z^2 + 2(xy + xz + yz), where both the squared terms and the cross terms form symmetric polynomials, illustrating how symmetry preserves structure under variable exchanges.[5] For contrast, the polynomial Q(x, y, z) = xy + z is not symmetric. Applying the transposition permutation that swaps y and z (mapping x \to x, y \to z, z \to y) yields xz + y, which differs from the original unless y = z.[1] A common pitfall is assuming all simple expressions are symmetric; while constants and linear sums are invariant by design, polynomials like xy + z fail permutation invariance because they treat variables asymmetrically.[5]Applications in Simple Equations
Symmetric polynomials play a fundamental role in the analysis and solution of simple polynomial equations, where the roots exhibit symmetric relations under permutation. For a quadratic equation ax^2 + bx + c = 0 with roots \alpha and \beta, the sum \alpha + \beta = -b/a and the product \alpha \beta = c/a are elementary symmetric polynomials in the roots, remaining invariant under interchange of \alpha and \beta.[8] This symmetry allows the roots to be expressed via the quadratic formula \alpha, \beta = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}, where the discriminant b^2 - 4ac = a^2 (\alpha - \beta)^2 is also symmetric.[8] In cubic equations, symmetric polynomials similarly capture relations among the roots. Consider a depressed cubic x^3 + px + q = 0 with roots a, b, c satisfying a + b + c = 0; here, the identity a^3 + b^3 + c^3 - 3abc = 0 holds, linking the power-sum symmetric polynomial a^3 + b^3 + c^3 to the product abc.[9] This relation simplifies the substitution method for solving the cubic, as a^3 = -p a - q (and similarly for b, c), reducing the problem to finding roots invariant under permutation.[9] More generally, for a monic cubic x^3 + a_2 x^2 + a_1 x + a_0 = 0, the coefficients are symmetric polynomials in the roots: a_2 = -(a + b + c), a_1 = ab + bc + ca, and a_0 = -abc.[10] Higher-degree symmetric expressions can be constructed iteratively from lower-degree ones through substitution into elementary symmetric polynomials. For instance, starting with elementary symmetric polynomials e_1 = \sum x_i and e_2 = \sum_{i < j} x_i x_j, one substitutes to express power sums like p_3 = \sum x_i^3 = e_1^3 - 3 e_1 e_2 + 3 e_3, building recursively for increased degrees while preserving symmetry.[11] This process leverages the fundamental theorem of symmetric polynomials, ensuring unique representation and enabling efficient computation via lexicographic reduction.[11] The symmetry inherent in permutable variables significantly simplifies solving systems of polynomial equations. When variables are interchangeable under permutation groups like S_n, the solution set inherits the symmetry, reducing the effective dimension—for example, partial symmetry of type p on a variable subset collapses p-fold redundant solutions into orbits, shrinking the Gröbner basis computation from size r \times r to approximately r/p \times r/p.[12] This exploitation of invariance accelerates numerical solvers, as seen in applications where symmetric systems yield fewer distinct cases to enumerate.[12]Fundamental Symmetric Polynomials
Elementary Symmetric Polynomials
The elementary symmetric polynomials e_k(x_1, \dots, x_n) for k = 0, 1, \dots, n in n indeterminates x_1, \dots, x_n are defined as the sums of all distinct products of k variables, where e_0 = 1 and for k \geq 1, e_k(x_1, \dots, x_n) = \sum_{1 \leq i_1 < i_2 < \dots < i_k \leq n} x_{i_1} x_{i_2} \cdots x_{i_k}. [13] For small values of k, these take explicit forms such as e_1(x_1, \dots, x_n) = x_1 + x_2 + \dots + x_n and e_2(x_1, \dots, x_n) = \sum_{1 \leq i < j \leq n} x_i x_j.[13] These polynomials form a basis for the ring of symmetric polynomials and are central to the algebraic structure of symmetric functions.[14] The generating function for the elementary symmetric polynomials is given by the product \prod_{i=1}^n (1 + x_i t) = \sum_{k=0}^n e_k(x_1, \dots, x_n) t^k, which expands directly from the definition by collecting terms of each degree in t.[14] This formal power series encapsulates the structure of the e_k and facilitates computations in symmetric function theory.[14] Newton's identities provide recurrence relations connecting the elementary symmetric polynomials e_k to the power sums p_k = x_1^k + \dots + x_n^k. The identities state that for k = 1, 2, \dots, n, k e_k = \sum_{m=1}^k (-1)^{m-1} e_{k-m} p_m, with e_0 = 1 and e_k = 0 for k > n or k < 0. To derive this, consider the generating function E(t) = \prod_{i=1}^n (1 + x_i t) = \sum_{k=0}^n e_k t^k and the logarithmic derivative \frac{E'(t)}{E(t)} = \sum_{i=1}^n \frac{x_i}{1 + x_i t} = \sum_{i=1}^n \sum_{m=1}^\infty (-1)^{m-1} x_i^m t^{m-1} = \sum_{m=1}^\infty (-1)^{m-1} p_m t^{m-1}. On the other hand, E'(t) = \sum_{k=1}^n k e_k t^{k-1}, so \sum_{k=1}^n k e_k t^{k-1} = E(t) \sum_{m=1}^\infty (-1)^{m-1} p_m t^{m-1}. Equating coefficients of t^{k-1} on both sides yields the identity after multiplying through by t^{k-1} and collecting terms. These relations allow recursive computation of e_k from the p_m and vice versa, highlighting the interplay between bases in the symmetric polynomial ring. A fundamental result is that every symmetric polynomial in n variables admits a unique expression as a polynomial in the elementary symmetric polynomials e_1, \dots, e_n, which are algebraically independent over the base field.[15] This uniqueness theorem establishes the e_k as a universal generating set for the ring of symmetric polynomials.[15]Power-Sum Symmetric Polynomials
Power-sum symmetric polynomials are defined for positive integers k as p_k(x_1, \dots, x_n) = \sum_{i=1}^n x_i^k, where x_1, \dots, x_n are indeterminates. These polynomials are symmetric, as permuting the variables leaves them invariant, and they generate the ring of symmetric polynomials over the integers.[16] A key feature of the power-sum polynomials is their relation to the elementary symmetric polynomials via Newton's identities, which provide recursive formulas for converting between the two bases. For k \geq 1, the identities state that p_k - e_1 p_{k-1} + e_2 p_{k-2} - \cdots + (-1)^{k-1} e_{k-1} p_1 + (-1)^k k e_k = 0, where e_j denotes the j-th elementary symmetric polynomial (with e_j = 0 for j > n or j < 0). This relation allows expressing either set in terms of the other; for instance, solving for e_k yields k e_k = (-1)^{k-1} \left( p_k - e_1 p_{k-1} + \cdots + (-1)^{k-1} e_{k-1} p_1 \right). These identities, originally derived by Isaac Newton, facilitate computations in algebraic contexts where one basis may be more convenient than the other.[17] In linear algebra, the power sums evaluate the traces of matrix powers when applied to eigenvalues. Specifically, if \lambda_1, \dots, \lambda_n are the eigenvalues of an n \times n matrix A, then p_k(\lambda_1, \dots, \lambda_n) = \operatorname{tr}(A^k) = \sum_{i=1}^n \lambda_i^k. This connection arises from the spectral properties of matrices and is useful for analyzing powers and iterations without explicitly computing eigenvalues.[18] For computational purposes, the power sums can be calculated directly for small n and related to other symmetric polynomials using Newton's identities. Consider n=2 with variables x and y: then p_1 = x + y = e_1, and p_2 = x^2 + y^2 = e_1 p_1 - 2 e_2 = (x+y)^2 - 2xy. For n=3, p_3 = x^3 + y^3 + z^3 = e_1 p_2 - e_2 p_1 + 3 e_3, illustrating the recursive conversion. These examples highlight how power sums relate to statistical moments, as p_k corresponds to the k-th raw moment of the multiset \{x_1, \dots, x_n\} under uniform weighting.[17]Advanced Symmetric Polynomials
Complete Homogeneous Symmetric Polynomials
The complete homogeneous symmetric polynomial of degree k in n variables x_1, \dots, x_n, denoted h_k(x_1, \dots, x_n), is defined as the sum of all monomials of total degree k in these variables, where the sum is taken over all non-negative integer solutions to \alpha_1 + \cdots + \alpha_n = k, yielding h_k = \sum_{\alpha_1 + \cdots + \alpha_n = k} x_1^{\alpha_1} \cdots x_n^{\alpha_n}.[14] This construction ensures that h_k is symmetric in the variables, as permuting the x_i merely reorders the terms in the sum without altering its value. By definition, h_0 = 1 and h_k = 0 for k < 0. For a partition \lambda = (\lambda_1, \lambda_2, \dots), the complete homogeneous symmetric polynomial is extended multiplicatively as h_\lambda = h_{\lambda_1} h_{\lambda_2} \cdots.[14] The generating function for the sequence \{h_k\}_{k \geq 0} provides a compact way to encode these polynomials: \sum_{k=0}^\infty h_k t^k = \prod_{i=1}^n \frac{1}{1 - x_i t}.[14] In the case of infinitely many variables, the product extends over i \geq 1. This formal power series identity arises from expanding each geometric series \frac{1}{1 - x_i t} = \sum_{m=0}^\infty (x_i t)^m and collecting terms by total degree in t. The generating function highlights the combinatorial interpretation of h_k as the number of ways to distribute k indistinguishable items into n distinguishable bins, weighted by the product of the bin sizes raised to their occupancy powers.[14] Complete homogeneous symmetric polynomials exhibit a duality with the elementary symmetric polynomials \{e_k\}, manifested through their generating functions. Let E(t) = \sum_{k \geq 0} e_k t^k = \prod_{i=1}^n (1 + x_i t); then the relation H(t) E(-t) = 1 holds, where H(t) = \sum_{k \geq 0} h_k t^k.[14] Expanding this identity yields the recurrence \sum_{i=0}^k (-1)^i e_i h_{k-i} = \delta_{k0} for all k \geq 0, with e_0 = h_0 = 1 and the Kronecker delta \delta_{k0} = 1 if k=0 and $0 otherwise. For k \geq 1, this simplifies to \sum_{i=0}^k (-1)^i e_i h_{k-i} = 0, allowing recursive computation of h_k from the e_i. Specific low-degree cases include h_1 = e_1 and h_2 = e_1 h_1 - e_2 = e_1^2 - e_2.[14] For illustration, consider n=2 variables x_1, x_2: h_1 = x_1 + x_2, and h_2 = x_1^2 + x_1 x_2 + x_2^2. For n=3 variables x_1, x_2, x_3, h_1 = x_1 + x_2 + x_3, h_2 = x_1^2 + x_2^2 + x_3^2 + x_1 x_2 + x_1 x_3 + x_2 x_3, and h_3 = x_1^3 + x_2^3 + x_3^3 + x_1^2 x_2 + x_1^2 x_3 + x_2^2 x_1 + x_2^2 x_3 + x_3^2 x_1 + x_3^2 x_2 + x_1 x_2 x_3. These expansions confirm the symmetry and the inclusion of all possible monomial terms of the specified degree.[14]Schur Polynomials
Schur polynomials, denoted s_\lambda(x_1, \dots, x_n) where \lambda is a partition with at most n parts, provide a fundamental basis for the ring of symmetric polynomials and are intimately connected to the representation theory of the general linear group \mathrm{GL}_n and the symmetric group S_m, where the characters of irreducible representations are given by these polynomials evaluated at the eigenvalues of group elements.[14] Combinatorially, the Schur polynomial is defined as the sum over all semistandard Young tableaux T of shape \lambda with entries from \{1, \dots, n\}, where each tableau contributes the monomial \prod_{i=1}^n x_i^{m_i(T)} with m_i(T) being the multiplicity of i in T; semistandard tableaux require weakly increasing rows and strictly increasing columns.[14][19] This definition ensures that s_\lambda is symmetric and homogeneous of degree |\lambda|, forming an orthonormal basis under the Hall scalar product.[14] A key algebraic expression for Schur polynomials is the Jacobi-Trudi identity, which represents s_\lambda as a determinant involving complete homogeneous symmetric polynomials h_k: s_\lambda = \det\left( h_{\lambda_i - i + j} \right)_{1 \leq i,j \leq \ell}, where \ell \geq \ell(\lambda) is sufficiently large, and h_0 = 1 while h_k = 0 for k < 0.[14][20] There is a dual form using elementary symmetric polynomials e_k: s_\lambda = \det\left( e_{\lambda'_j - j + i} \right)_{1 \leq i,j \leq \ell}, with \lambda' the conjugate partition.[19] This determinant formula facilitates computations and proofs of positivity properties, as the entries are themselves positive sums of monomials.[14] Special cases of Schur polynomials recover other classical bases: for the single-row partition \lambda = (k), s_{(k)} = h_k, the k-th complete homogeneous symmetric polynomial; for the single-column partition \lambda = (1^k), s_{(1^k)} = e_k, the k-th elementary symmetric polynomial.[14][19] More generally, every Schur polynomial expresses as a positive integer linear combination of monomial symmetric polynomials, reflecting the combinatorial expansion via tableaux.[14] q-analogs of Schur polynomials have played a central role in the representation theory of quantum groups, particularly through q-Schur algebras—introduced by Dipper and James in 1989—that generalize classical Schur-Weyl duality to quantum settings.[21]Monomial Symmetric Polynomials
Monomial symmetric polynomials, denoted m_\lambda for a partition \lambda = (\lambda_1, \lambda_2, \dots, \lambda_l) of an integer k, are defined in n variables x_1, \dots, x_n (with n \geq l) as the sum m_\lambda(x_1, \dots, x_n) = \sum x_{i_1}^{\lambda_1} x_{i_2}^{\lambda_2} \cdots x_{i_l}^{\lambda_l}, where the sum runs over all distinct monomials arising from permutations of the indices i_1, \dots, i_l, i_{l+1}, \dots, i_n with i_{l+1} = \cdots = i_n assigned exponent 0, ensuring each unique monomial appears exactly once with coefficient 1.[14][22] The collection \{ m_\lambda \}, indexed by all partitions \lambda, forms a \mathbb{Z}-basis for the ring of symmetric polynomials in n variables over \mathbb{Z}, meaning every symmetric polynomial can be uniquely expressed as a finite integer linear combination of these monomials. This basis property holds because the monomial symmetric polynomials are the orbit sums under the action of the symmetric group S_n on the ordinary monomials, and they span the invariants without relations among themselves in the graded components.[14][22] The number of terms in m_\lambda equals the size of the orbit under S_n, given by n! / \prod_j m_j!, where m_j is the multiplicity of the exponent j in the padded partition (including m_0 = n - l(\lambda)). For example, for \lambda = (2) in n variables, there is one part 2 and n-1 zeros, so m_2 = 1, m_0 = n-1, yielding n! / (1! \cdot (n-1)!) = n terms, corresponding to \sum_{i=1}^n x_i^2. For \lambda = (1,1), m_1 = 2, m_0 = n-2, giving n! / (2! \cdot (n-2)!) = \binom{n}{2} terms, such as \sum_{1 \leq i < j \leq n} x_i x_j. For \lambda = (2,1), m_2 = 1, m_1 = 1, m_0 = n-2, resulting in n! / (1! \cdot 1! \cdot (n-2)!) = n(n-1) terms, like \sum_{i \neq j} x_i^2 x_j.[14] Monomial symmetric polynomials relate to other bases, such as the Schur polynomials s_\mu, via integer transition matrices involving Kostka numbers K_{\mu \lambda}, which count semistandard Young tableaux of shape \mu and weight \lambda. Specifically, s_\mu = \sum_\lambda [K_{\mu \lambda}](/page/Kostka_number) m_\lambda, and the inverse expresses m_\lambda in terms of Schur polynomials with signed coefficients. For small degrees, these matrices are lower unitriangular (in dominance order on partitions). The table below shows the transition matrix for expressing Schur polynomials in the monomial basis for degree 2, with partitions ordered lexicographically: (2), (1,1).| m_{(2)} | m_{(1,1)} | |
|---|---|---|
| s_{(2)} | 1 | 1 |
| s_{(1,1)} | 0 | 1 |
| m_{(3)} | m_{(2,1)} | m_{(1,1,1)} | |
|---|---|---|---|
| s_{(3)} | 1 | 1 | 1 |
| s_{(2,1)} | 0 | 1 | 2 |
| s_{(1^3)} | 0 | 0 | 1 |