Кольцо симметрических функций в алгебраической комбинаторике

Введение

кольцо симметричных функций в алгебраической комбинаторике
В алгебре и, в частности, в алгебраической комбинаторике, кольцо симметричных функций представляет собой специфический предел колец симметричных многочленов от n переменных, при стремлении n к бесконечности. Это кольцо служит универсальной структурой, в которой соотношения между симметричными многочленами могут быть выражены способом, не зависящим от числа n переменных (однако его элементы не являются ни многочленами, ни функциями). Среди прочего, это кольцо играет важную роль в теории представлений симметрической группы. Кольцо симметричных функций допускает определение копроизведения и билинейной формы, превращающих его в положительную самосопряжённую градуированную алгебру Хопфа, которая является одновременно коммутативной и кокоммутативной.

Кольцо симметричных функций

Большинство соотношений между симметричными многочленами не зависят от числа *n* переменных, за исключением того, что для определения некоторых многочленов в соотношении может потребоваться достаточно большое значение *n*. Например, тождество Ньютона для полинома третьей степени *p3* приводит к следующему:

где обозначают элементарные симметричные многочлены; эта формула справедлива для всех натуральных чисел *n*, и единственная существенная зависимость от *n* заключается в том, что *ek(X1, ..., Xn) = 0* при *n < k*. Было бы желательно записать это в виде тождества, не зависящего от *n* вовсе, что можно сделать в кольце симметричных функций. В этом кольце существуют ненулевые элементы *ek* для всех целых чисел *k ≥ 1*, и любой элемент кольца может быть представлен полиномиальным выражением относительно элементов *ek*.

Определения

Кольцо симметричных функций может быть определено над любым коммутативным кольцом R и обозначается ΛR; базовый случай соответствует R = Z. Кольцо ΛR фактически является градуированной R-алгеброй. Существует два основных способа его построения; первый из них, представленный ниже, можно найти в (Stanley, 1999), а второй по сути совпадает с представленным в (Macdonald, 1979).

В качестве алгебраического предела

Другая конструкция ΛR требует несколько больше времени для описания, но лучше отражает связь с кольцами R[X1, …,Xn]Sn симметричных многочленов от n неопределенных. Для каждого n существует сюръективный гомоморфизм колец ρn из аналогичного кольца R[X1, …,Xn+1]Sn+1 с одним дополнительным неопределенным на R[X1, …,Xn]Sn, определяемый установкой последнего неопределенного Xn+1 равным 0. Хотя ρn имеет нетривиальное ядро, ненулевые элементы этого ядра имеют степень не меньше (они кратны X1X2…Xn+1). Это означает, что ограничение ρn на элементы степени не выше n является биективным линейным отображением, и ρn(ek(X1, …,Xn+1)) = ek(X1, …,Xn) для всех k ≤ n. Обратное к этому ограничению можно единственным образом расширить до гомоморфизма колец φn из R[X1, …,Xn]Sn в R[X1, …,Xn+1]Sn+1, что следует, например, из фундаментальной теоремы о симметричных многочленах. Поскольку образы φn(ek(X1, …,Xn)) = ek(X1, …,Xn+1) для k = 1, …,n по-прежнему алгебраически независимы над R, гомоморфизм φn является инъективным и может рассматриваться как (несколько необычное) включение колец; применение φn к многочлену сводится к добавлению всех мономов, содержащих новое неопределенное, полученное симметрией из уже присутствующих мономов. Кольцо ΛR является тогда "объединением" (прямой границей) всех этих колец относительно этих включений. Поскольку все φn согласованы с градуировкой по полной степени участвующих колец, ΛR приобретает структуру градуированного кольца. Эта конструкция немного отличается от представленной в (Macdonald, 1979). Эта конструкция использует только сюръективные морфизмы ρn, не упоминая инъективные морфизмы φn: она строит однородные компоненты ΛR по отдельности и наделяет их прямую сумму структурой кольца, используя ρn. Также отмечается, что результат можно описать как обратный предел в категории градуированных колец. Однако это описание несколько затемняет важное свойство, типичное для прямой границы инъективных морфизмов, а именно, что каждый отдельный элемент (симметричная функция) уже верно представлен в некотором объекте, используемом в предельной конструкции, здесь в кольце R[X1, …,Xd]Sd. Достаточно взять для d степень симметричной функции, поскольку часть степени d этого кольца отображается изоморфно в кольца с большим числом неопределенных посредством φn для всех n ≥ d. Это означает, что для изучения соотношений между отдельными элементами нет принципиальной разницы между симметричными многочленами и симметричными функциями.

Another construction of ΛR takes somewhat longer to describe, but better indicates the relationship with the rings R[X1, ,Xn]Sn of symmetric polynomials in n indeterminates. For every n there is a surjective ring homomorphism ρn from the analogous ring R[X1, ,Xn+1]Sn+1 with one more indeterminate onto R[X1, ,Xn]Sn, defined by setting the last indeterminate Xn+1 to 0. Although ρn has a non trivial kernel, the nonzero elements of that kernel have degree at least (they are multiples of X1X2 Xn+1). This means that the restriction of ρn to elements of degree at most n is a bijective linear map, and ρn(ek(X1, ,Xn+1)) = ek(X1, ,Xn) for all k ≤ n. The inverse of this restriction can be extended uniquely to a ring homomorphism φn from R[X1, ,Xn]Sn to R[X1, ,Xn+1]Sn+1, as follows for instance from the fundamental theorem of symmetric polynomials. Since the images φn(ek(X1, ,Xn)) = ek(X1, ,Xn+1) for k = 1, ,n are still algebraically independent over R, the homomorphism φn is injective and can be viewed as a (somewhat unusual) inclusion of rings; applying φn to a polynomial amounts to adding all monomials containing the new indeterminate obtained by symmetry from monomials already present. The ring ΛR is then the "union" (direct limit) of all these rings subject to these inclusions. Since all φn are compatible with the grading by total degree of the rings involved, Λ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 ρn without mentioning the injective morphisms φn: it constructs the homogeneous components of ΛR separately, and equips their direct sum with a ring structure using the ρ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[X1, ,Xd]Sd. It suffices to take for d the degree of the symmetric function, since the part in degree d of that ring is mapped isomorphically to rings with more indeterminates by φn for all n ≥ d. This implies that for studying relations between individual elements, there is no fundamental difference between symmetric polynomials and symmetric functions.

Определение отдельных симметричных функций

Название "симметричная функция" для элементов ΛR – неточное: ни в одной из конструкций элементы не являются функциями, и, более того, в отличие от симметричных многочленов, к таким элементам нельзя сопоставить функцию независимых переменных (например, e1 было бы суммой всех бесконечного числа переменных, которая не определена без ограничений на переменные). Однако название традиционно и широко распространено; его можно встретить как в (Macdonald, 1979), где говорится (примечание на с. 12), что элементы Λ (в отличие от элементов Λn) больше не являются многочленами: они представляют собой формальные бесконечные суммы мономов. Поэтому мы вернулись к более старой терминологии симметричных функций. (Здесь Λn обозначает кольцо симметричных многочленов от n неопределенных), а также в (Stanley, 1999). Чтобы определить симметричную функцию, необходимо либо непосредственно указать степенной ряд, как в первой конструкции, либо задать симметричный многочлен от n неопределенных для каждого натурального числа n согласованным образом со второй конструкцией. Выражение от неопределенного числа неопределенных может выполнять обе эти функции; например, его можно принять за определение элементарной симметричной функции, если число неопределенных бесконечно, или за определение элементарного симметричного многочлена при любом конечном числе неопределенных. Симметричные многочлены, соответствующие одной и той же симметричной функции, должны быть совместимы с гомоморфизмами ρn (уменьшение числа неопределенных достигается путем приравнивания некоторых из них к нулю, так что коэффициенты любого монома в оставшихся неопределенных остаются неизменными), и их степень должна оставаться ограниченной. (Примером семейства симметричных многочленов, не удовлетворяющим обоим условиям, является ; семейство не удовлетворяет только второму условию.) Любой симметричный многочлен от n неопределенных можно использовать для построения совместимого семейства симметричных многочленов, используя гомоморфизмы ρi для i < n для уменьшения числа неопределенных и φi для i ≥ n для увеличения числа неопределенных (что эквивалентно добавлению всех мономов в новых неопределенных, полученных симметрией из уже существующих мономов). Ниже приведены фундаментальные примеры симметричных функций. Мономиальные симметричные функции mα. Пусть α = (α1, α2, ...) – последовательность неотрицательных целых чисел, лишь конечное число которых отлично от нуля. Тогда можно рассмотреть мономиал, определенный α: Xα = X1α1X2α2X3α3. Тогда mα – симметричная функция, определяемая Xα, то есть суммой всех мономов, полученных из Xα посредством симметрии. Для формального определения определим β ~ α, если последовательность β является перестановкой последовательности α, и определим Эта симметричная функция соответствует мономиальному симметричному многочлену mα(X1, ..., Xn) для любого n, достаточно большого, чтобы содержать мономиал Xα. Различные мономиальные симметричные функции параметризуются целыми разбиениями (каждый mα имеет уникальный представительный мономиал Xλ с частями λi в неубывающем порядке). Поскольку любая симметричная функция, содержащая какой-либо из мономов некоторого mα, должна содержать все их с одним и тем же коэффициентом, каждая симметричная функция может быть записана как R-линейная комбинация мономиальных симметричных функций, и поэтому различные мономиальные симметричные функции образуют базис ΛR как R-модуль. Элементарные симметричные функции ek для любого натурального числа k; ek = mα, где как степенной ряд это сумма всех различных произведений k различных неопределенных. Эта симметричная функция соответствует элементарному симметричному многочлену ek(X1, ..., Xn) для любого n ≥ k. Силовые суммы симметричных функций pk для любого положительного целого числа k; pk = m(k), мономиальная симметричная функция для монома X1k. Эта симметричная функция соответствует силовому сумме симметричному многочлену pk(X1, ..., Xn) = X1k + ... + Xnk для любого n ≥ 1. Полные однородные симметричные функции hk для любого натурального числа k; hk – это сумма всех мономиальных симметричных функций mα, где α является разбиением k. Как степенной ряд, это сумма всех мономов степени k, что и мотивирует его название. Эта симметричная функция соответствует полному однородному симметричному многочлену hk(X1, ..., Xn) для любого n ≥ k. Функции Шура sλ для любого разбиения λ, которые соответствуют многочлену Шура sλ(X1, ..., Xn) для любого n, достаточно большого, чтобы содержать мономиал Xλ. Силовой суммы симметричной функции p0 не существует: хотя и возможно (и в некоторых контекстах естественно) определить как симметричный многочлен от n переменных, эти значения не согласованы с морфизмами ρn. "Дискриминант" – еще один пример выражения, задающего симметричный многочлен для всех n, но не определяющего симметричную функцию. Выражения, определяющие многочлены Шура как частное от чередующихся многочленов, в некотором смысле похожи на выражение для дискриминанта, но многочлены sλ(X1, ..., Xn) оказываются совместимыми при изменении n и, следовательно, определяют симметричную функцию.

The name "symmetric function" for elements of ΛR is a misnomer: in neither construction are the elements functions, and in fact, unlike symmetric polynomials, no function of independent variables can be associated to such elements (for instance e1 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. 12)
The elements of Λ (unlike those of Λn) are no longer polynomials: they are formal infinite sums of monomials. We have therefore reverted to the older terminology of symmetric functions. (here Λn denotes the ring of symmetric polynomials in n indeterminates), and also in (Stanley, 1999). 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

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 homomorphisms ρn (decreasing the number of indeterminates is obtained by setting some of them to zero, so that the coefficients of any monomial in the remaining indeterminates is unchanged), and their degree should remain bounded. (An example of a family of symmetric polynomials that fails both conditions is ; the family fails only the second condition.) Any symmetric polynomial in n indeterminates can be used to construct a compatible family of symmetric polynomials, using the homomorphisms ρi for i < n to decrease the number of indeterminates, and φi for i ≥ 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α. Suppose α = (α1,α2, ) is a sequence of non negative integers, only finitely many of which are non zero. Then we can consider the monomial defined by α: Xα = X1α1X2α2X3α3 Then mα is the symmetric function determined by Xα, i. e. the sum of all monomials obtained from Xα by symmetry. For a formal definition, define β ~ α to mean that the sequence β is a permutation of the sequence α and set

This symmetric function corresponds to the monomial symmetric polynomial mα(X1, ,Xn) for any n large enough to have the monomial Xα. The distinct monomial symmetric functions are parametrized by the integer partitions (each mα has a unique representative monomial Xλ with the parts λi in weakly decreasing order). Since any symmetric function containing any of the monomials of some mα must contain all of them with the same coefficient, each symmetric function can be written as an R linear combination of monomial symmetric functions, and the distinct monomial symmetric functions therefore form a basis of ΛR as an R module. The elementary symmetric functions ek, for any natural number k; one has ek = mα where 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 ek(X1, ,Xn) for any n ≥ k.
The power sum symmetric functions pk, for any positive integer k; one has pk = m(k), the monomial symmetric function for the monomial X1k. This symmetric function corresponds to the power sum symmetric polynomial pk(X1, ,Xn) = X1k + + Xnk for any n ≥ 1. The complete homogeneous symmetric functions hk, for any natural number k; hk is the sum of all monomial symmetric functions mα where α is a partition of 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 hk(X1, ,Xn) for any n ≥ k.
The Schur functions sλ for any partition λ, which corresponds to the Schur polynomial sλ(X1, ,Xn) for any n large enough to have the monomial Xλ. There is no power sum symmetric function p0: although it is possible (and in some contexts natural) to define as a symmetric polynomial in n variables, these values are not compatible with the morphisms ρn. The "discriminant" is another example of an expression giving a symmetric polynomial for all n, but not defining any symmetric function. The expressions defining Schur polynomials as a quotient of alternating polynomials are somewhat similar to that for the discriminant, but the polynomials sλ(X1, ,Xn) turn out to be compatible for varying n, and therefore do define a symmetric function.

Принцип, относящий симметричные многочлены и симметричные функции

Для любой симметричной функции P соответствующие симметричные многочлены от n переменных для любого натурального числа n могут быть обозначены как P(X₁, …, Xₙ). Второе определение кольца симметричных функций влечет за собой следующий фундаментальный принцип:

Если P и Q – симметричные функции степени d, то тождество симметричных функций выполняется тогда и только тогда, когда выполняется тождество P(X₁, …, Xd) = Q(X₁, …, Xd) симметричных многочленов от d переменных. В этом случае, на самом деле, P(X₁, …, Xₙ) = Q(X₁, …, Xₙ) для любого числа n переменных. Это происходит потому, что всегда можно уменьшить число переменных, подставив нуль в некоторые из них, и увеличить число переменных, применяя гомоморфизмы φₙ; определение этих гомоморфизмов гарантирует, что φₙ(P(X₁, …, Xₙ)) = P(X₁, …, Xₙ₊₁) (и аналогично для Q) при n ≥ d. Доказательство тождеств Ньютона содержит эффективное применение этого принципа.