Представление симметрического полинома через элементарные

[ellipse]

Какие есть методы нахождения представления симметрического полинома через элементарные симметрические?
Я написал программу, в которой реализуется алгоритм, который используется для док-ва классической теоремы о существовании такого представления. Но он наверно слишком сложный, т.к. уже для $n=5$ вычисления занимали часы.
Есть идея, использовать метод неопределенных коэффициентов, то есть задавать переменным $x_1,...,x_n$ произвольные значения, вычислять значения основного полинома и элементарных при этих значениях, зачем из линейной системы вычислить коэффициенты. Тут проблема выбрать значения $x_1,...,x_n$ так, чтоб система имела одно решение. Но может этот алгоритм будет еще более сложный? Не могу оценить и сравнить степени сложности.

[Sonic86]

ellipse в сообщении #492189 писал(а):

Какие есть методы нахождения представления симметрического полинома через элементарные симметрические?

Есть метод Ньютона, он описан в Куроше Курс высшей алгебры (возможно, есть литература лучше).

ellipse в сообщении #492189 писал(а):

Но он наверно слишком сложный, т.к. уже для $n=5$ вычисления занимали часы.

Странно А у Вас точно все оптимизировано?

ellipse в сообщении #492189 писал(а):

Есть идея, использовать метод неопределенных коэффициентов, то есть задавать переменным $x_1,...,x_n$ произвольные значения, вычислять значения основного полинома и элементарных при этих значениях, зачем из линейной системы вычислить коэффициенты. Тут проблема выбрать значения $x_1,...,x_n$ так, чтоб система имела одно решение. Но может этот алгоритм будет еще более сложный? Не могу оценить и сравнить степени сложности.

Можно посчитать квадратную матрицу коэффициентов, потом считать ее ранг. Если ранг равен 0, то брать следующее значение $x_1$, сохраняя остальные $x_j$ - считать еще одну строку матрицы, добавлять ее в общую матрицу, снова считать ранг и т.п. до тех пор, пока ранг матрицы не станет равным ее числу ее столбцов (т.е. когда решение однозначно существует).

Я ручками делал так (мой метод кустарный, не факт, что хороший). Обозначим $\sigma _j$ - $j$-й симметрический многочлен, $j=1,...,n$. если $F$ - симметрический многочлен от $x_1,...,x_n$, то его можно разбить в сумму многочленов, каждый из которых инвариантен относительно $S_n$ (например $F=x+x^2+y+y^2+z+z^2=(x+y+z)+(x^2+y^2+z^2)$). Далее, с каждым таким многочленом работаем отдельно. Пусть $k=k(F)$ - число различных переменных в каждом одночлене $F$ (говорить о $k$ корректно, поскольку оно одно и то же для всех одночленов, поскольку $S_n$ действует транзитивно на $F$). Если $k(F)=n$, то $\sigma _n$ делит $F$ - степень понижается и рассматриваем $\frac{F}{\sigma _n}$. Если $k(F)<n$ и одночлен имеет вид $x_{j_1}^{a_1}...x_{j_s}^{a_s}$, $a_j>0$, $b_1,...,b_r$ - отсортированные $a_j$ без дублей, то тогда мы можем вычесть из $F$ произведение симметрических многочленов, порожденных одночленами $x_{j_1}^{b_1}...x_{j_s}^{b_1},x_{j_1}^{b_2-b_1}...x_{j_s}^{b_2-b_1},x_{j_1}^{b_3-b_2}...x_{j_s}^{b_3-b_2}$ (например $x_1x_2$ порождает $x_1x_2+x_2x_3+x_3x_1$ - порожденных в этом смысле), причем $k(\text{разности})>k(F)$, что потом позволяет уменьшить степень $F$, когда дойдем до $k=n$. Только не пугайтесь - это несложно. Частный случай: если мы хотим выразить $x_1^n+...+x_n^n$ через $\sigma _j$, то сначала по этому алгоритму следует отнять $(x_1+...+x_n)^n$ - получим новый многочлен с $k=2>1$.
Пример: выразить $xy^2+yz^2+xz^2, k=2$. Вычитаем $(x+y+z)(xy+yz+xz)=2(xy^2+yz^2+xz^2) +3xyz$, подбираем коэффициент - получаем $2F- \sigma _1 \sigma _2 = 3xyz, k=3>2$ - дальше уже понятно.
Сложность не оценю, но ручками было довольно легко, для $n=5$ я точно работал меньше 5 часов
С одночленом подробнее напишу: пусть $F$ - сумма образов при всех перестановках одночлена $x_1^2x_2x_4^4x_5$. Представляет одночлен в "произведение по этажам" $x_1^2x_2x_4^4x_5=(x_1x_2x_4x_5)x_1x_4^3=(x_1x_2x_4x_5)(x_1x_4)x_4^2=(x_1x_2x_4x_5)(x_1x_4)(x_4^2)$ и тогда вычитаем $\sigma _4 \sigma _2 \sigma_1^2$

[Sonic86]

Может выпишите свой многочлен 5-й степени?

[VAL]

Sonic86 в сообщении #492303 писал(а):

Может выпишите свой многочлен 5-й степени?

Насколько я понял, $n$ - это количество переменных, а не степень.

[Sonic86]

VAL в сообщении #492308 писал(а):

Насколько я понял, $n$ - это количество переменных, а не степень.

Да, ошибся, имел ввиду количество переменных

[Klad33]

ellipse! А можно конретно - что за полином и как его представлять? Для меня это тоже одна из важных задач.

[ellipse]

Klad33 писал(а):

ellipse! А можно конретно - что за полином и как его представлять? Для меня это тоже одна из важных задач.

Пусть есть полином $f(x_1,\dots,x_n)$ от $n$ переменных $x_1,\dots,x_n$. Пусть $G$ - подругппа перестановок из $S_n$. Определяется действие группы $G$ на множестве всех полиномов от $n$ переменных $x_1,\dots,x_n$ по правилу: $gf(x_1,\dots,x_n):=f(g(x_1),\dots,g(x_n))$.
Полином называется симметрическим, если он не меняется при действии группы $S_n$, то есть $\forall g\in S_n \ gf=f$.
Элементарными симметрическими называются полиномы вида
$\delta_1=x_1+x_2+\dots+x_n$
$\delta_2=x_1x_2+x_1x_3+\dots+x_{n-1}x_n$
...
$\delta_k=\displaystyle\sum_{1\leq i_1<i_2<\dots<i_k \leq n} x_{i_1}\dots x_{i_k}$
...
$\delta_n = x_1\dots x_n$

Есть теорема, о том, что любой симметричсекий полином $f(x_1,\dots,x_n)$ можно представить в виде полинома с целыми коэффициентами от элементарных симметрических $f(x_1,\dots,x_n)=R(\delta_1,\dots,\delta_n)$

-- Сб окт 15, 2011 14:21:21 --

Sonic86 в сообщении #492311 писал(а):

VAL в сообщении #492308 писал(а):

Насколько я понял, $n$ - это количество переменных, а не степень.

Да, ошибся, имел ввиду количество переменных

Степень больше $20$.

[Sonic86]

ellipse в сообщении #492763 писал(а):

Степень больше $20$.

Если хотите - можете выписать. Тут и разложим.

[ellipse]

Цитата:

Если хотите - можете выписать. Тут и разложим.

Вы вручную хотите разложить?
Для примера, полином с $n=4$ и степенью $12$. Формат записи следующий.
Каждой строке $d_1\ d_2\ d_3\ d_4\ K$ соответствует слагаемое-моном $Kx_1^{d_1}x_2^{d_2}x_3^{d_3}x_4^{d_4}$

(длинный код)

6 4 2 0  1 
6 4 1 1  -2 
6 4 0 2  1 
6 3 3 0  -2 
6 3 2 1  2 
6 3 1 2  2 
6 3 0 3  -2 
6 2 4 0  1 
6 2 3 1  2 
6 2 2 2  -6 
6 2 1 3  2 
6 2 0 4  1 
6 1 4 1  -2 
6 1 3 2  2 
6 1 2 3  2 
6 1 1 4  -2 
6 0 4 2  1 
6 0 3 3  -2 
6 0 2 4  1 
5 5 2 0  -2 
5 5 1 1  4 
5 5 0 2  -2 
5 4 3 0  2 
5 4 2 1  -2 
5 4 1 2  -2 
5 4 0 3  2 
5 3 4 0  2 
5 3 3 1  -4 
5 3 2 2  4 
5 3 1 3  -4 
5 3 0 4  2 
5 2 5 0  -2 
5 2 4 1  -2 
5 2 3 2  4 
5 2 2 3  4 
5 2 1 4  -2 
5 2 0 5  -2 
5 1 5 1  4 
5 1 4 2  -2 
5 1 3 3  -4 
5 1 2 4  -2 
5 1 1 5  4 
5 0 5 2  -2 
5 0 4 3  2 
5 0 3 4  2 
5 0 2 5  -2 
4 6 2 0  1 
4 6 1 1  -2 
4 6 0 2  1 
4 5 3 0  2 
4 5 2 1  -2 
4 5 1 2  -2 
4 5 0 3  2 
4 4 4 0  -6 
4 4 3 1  4 
4 4 2 2  4 
4 4 1 3  4 
4 4 0 4  -6 
4 3 5 0  2 
4 3 4 1  4 
4 3 3 2  -6 
4 3 2 3  -6 
4 3 1 4  4 
4 3 0 5  2 
4 2 6 0  1 
4 2 5 1  -2 
4 2 4 2  4 
4 2 3 3  -6 
4 2 2 4  4 
4 2 1 5  -2 
4 2 0 6  1 
4 1 6 1  -2 
4 1 5 2  -2 
4 1 4 3  4 
4 1 3 4  4 
4 1 2 5  -2 
4 1 1 6  -2 
4 0 6 2  1 
4 0 5 3  2 
4 0 4 4  -6 
4 0 3 5  2 
4 0 2 6  1 
3 6 3 0  -2 
3 6 2 1  2 
3 6 1 2  2 
3 6 0 3  -2 
3 5 4 0  2 
3 5 3 1  -4 
3 5 2 2  4 
3 5 1 3  -4 
3 5 0 4  2 
3 4 5 0  2 
3 4 4 1  4 
3 4 3 2  -6 
3 4 2 3  -6 
3 4 1 4  4 
3 4 0 5  2 
3 3 6 0  -2 
3 3 5 1  -4 
3 3 4 2  -6 
3 3 3 3  24 
3 3 2 4  -6 
3 3 1 5  -4 
3 3 0 6  -2 
3 2 6 1  2 
3 2 5 2  4 
3 2 4 3  -6 
3 2 3 4  -6 
3 2 2 5  4 
3 2 1 6  2 
3 1 6 2  2 
3 1 5 3  -4 
3 1 4 4  4 
3 1 3 5  -4 
3 1 2 6  2 
3 0 6 3  -2 
3 0 5 4  2 
3 0 4 5  2 
3 0 3 6  -2 
2 6 4 0  1 
2 6 3 1  2 
2 6 2 2  -6 
2 6 1 3  2 
2 6 0 4  1 
2 5 5 0  -2 
2 5 4 1  -2 
2 5 3 2  4 
2 5 2 3  4 
2 5 1 4  -2 
2 5 0 5  -2 
2 4 6 0  1 
2 4 5 1  -2 
2 4 4 2  4 
2 4 3 3  -6 
2 4 2 4  4 
2 4 1 5  -2 
2 4 0 6  1 
2 3 6 1  2 
2 3 5 2  4 
2 3 4 3  -6 
2 3 3 4  -6 
2 3 2 5  4 
2 3 1 6  2 
2 2 6 2  -6 
2 2 5 3  4 
2 2 4 4  4 
2 2 3 5  4 
2 2 2 6  -6 
2 1 6 3  2 
2 1 5 4  -2 
2 1 4 5  -2 
2 1 3 6  2 
2 0 6 4  1 
2 0 5 5  -2 
2 0 4 6  1 
1 6 4 1  -2 
1 6 3 2  2 
1 6 2 3  2 
1 6 1 4  -2 
1 5 5 1  4 
1 5 4 2  -2 
1 5 3 3  -4 
1 5 2 4  -2 
1 5 1 5  4 
1 4 6 1  -2 
1 4 5 2  -2 
1 4 4 3  4 
1 4 3 4  4 
1 4 2 5  -2 
1 4 1 6  -2 
1 3 6 2  2 
1 3 5 3  -4 
1 3 4 4  4 
1 3 3 5  -4 
1 3 2 6  2 
1 2 6 3  2 
1 2 5 4  -2 
1 2 4 5  -2 
1 2 3 6  2 
1 1 6 4  -2 
1 1 5 5  4 
1 1 4 6  -2 
0 6 4 2  1 
0 6 3 3  -2 
0 6 2 4  1 
0 5 5 2  -2 
0 5 4 3  2 
0 5 3 4  2 
0 5 2 5  -2 
0 4 6 2  1 
0 4 5 3  2 
0 4 4 4  -6 
0 4 3 5  2 
0 4 2 6  1 
0 3 6 3  -2 
0 3 5 4  2 
0 3 4 5  2 
0 3 3 6  -2 
0 2 6 4  1 
0 2 5 5  -2 
0 2 4 6  1 

Ниже его представление через элементарные симметрические. Формат такой же. Каждой строке $d_1\ d_2\ d_3\ d_4\ K$ соответствует слагаемое-моном $K\delta_{1}^{d_1}\delta_2^{d_2}\delta_3^{d_3}\delta_4^{d_4}$

2 2 2 0  1
2 3 0 1  -4
3 0 3 0  -4
3 1 1 1  18
4 0 0 2  -27
0 3 2 0  -4
0 4 0 1  16
1 1 3 0  18
1 2 1 1  -80
2 0 2 1  -6
2 1 0 2  144
0 0 4 0  -27
0 1 2 1  144
0 2 0 2  -128
1 0 1 2  -192
0 0 0 3  256

[Sonic86]

ellipse в сообщении #492786 писал(а):

Вы вручную хотите разложить?
Для примера, полином с $n=4$ и степенью $12$. Формат записи следующий.

Ой! Я думал, он несколько короче Откуда же такая страшная задача?
Хотя максимальная степень не выше 6, порядка половины многочленов сразу делятся на $\sigma _4$. Просто громоздко...
Если покороче будет - приносите