Тождества Ньютона (Mk';yvmfg U,Zmkug)

В математике тождества Ньютона, также известные как формулы Ньютона — Жирара, задают соотношения между двумя типами симметрических многочленов, а именно между элементарными симметрическими многочленами и степенными суммами Ньютона. Для произвольного многочлена P они дают возможность выразить сумму k-х степеней всех корней P (с учётом кратности) через коэффициенты P, без фактического нахождения корней. Эти тождества были открыты Исааком Ньютоном около 1666 года, и возможно, в ранних работах (1629) Альберта Жирара. Они находят применение во многих областях математики, в том числе в теории Галуа, теории инвариантов, теории групп, комбинаторике, а также в других науках, в том числе в общей теории относительности.

Формулировка тождеств

Для переменных $x_{1},\dots ,x_{n}$ и для $k\geq 1$ рассмотрим суммы $k$-тых степеней этих переменных:

$p_{k}(x_{1},\ldots ,x_{n})=\sum \nolimits _{i=1}^{n}x_{i}^{k}=x_{1}^{k}+\cdots +x_{n}^{k}.$

Обозначим также через $e_{k}(x_{1},\dots ,x_{n})$ элементарные симметрические многочлены. Многочлен $e_{k}(x_{1},\dots ,x_{n})$ представляет собой сумму всех возможных произведений $k$ разных переменных, в частности

${\begin{aligned}e_{0}(x_{1},\ldots ,x_{n})&=1,\\e_{1}(x_{1},\ldots ,x_{n})&=x_{1}+x_{2}+\cdots +x_{n},\\e_{2}(x_{1},\ldots ,x_{n})&=\textstyle \sum _{1\leq i<j\leq n}x_{i}x_{j},\\&{}\ \ \vdots \\e_{n}(x_{1},\ldots ,x_{n})&=x_{1}x_{2}\cdots x_{n},\\e_{k}(x_{1},\ldots ,x_{n})&=0,\quad {\text{for}}\ k>n.\\\end{aligned}}$

Тогда тождества Ньютона могут быть записаны следующим образом:

$ke_{k}=\sum _{i=1}^{k}(-1)^{i-1}e_{k-i}p_{i},$

для всех $k\geq 1$. В частности, для $k>n\geq 1$

$0=\sum _{i=k-n}^{k}(-1)^{i-1}e_{k-i}p_{i},$

Для нескольких первых значений $k$ получим:

${\begin{aligned}e_{1}&=p_{1},\\2e_{2}&=e_{1}p_{1}-p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+p_{3},\\&{}\ \ \vdots \end{aligned}}$

Истинность этих тождеств не зависит от количества переменных, даже когда левая и правая части равны нулю. Эти равенства позволяют рекуррентно выразить $p_{i}$ через $e_{i}$:

${\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}p_{1}-2e_{2},\\p_{3}&=e_{1}p_{2}-e_{2}p_{1}+3e_{3},\\p_{4}&=e_{1}p_{3}-e_{2}p_{2}+e_{3}p_{1}-4e_{4},\\&{}\ \ \vdots \end{aligned}}$

Способы доказательства

Каждое отдельное из тождеств Ньютона может быть проверено с помощью элементарных алгебраических операций, однако общая формула требует доказательства. Существует несколько различных способов вывода тождеств.

Ниже мы обозначаем количество переменных через $n$, а номер тождества (количество слагаемых в сумме в правой части) через $k$.

Через специальный случай $k=n$

По определению, $\prod _{i=1}^{k}(t-x_{i})=\sum _{i=0}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k})t^{i}$

Следовательно, при $t=x_{j}$ имеем

$0=\sum _{i=0}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k}){x_{j}}^{i},\quad 1\leq j\leq k$

Суммируя по всем $j$, получаем

$0=(-1)^{k}ke_{k}(x_{1},\ldots ,x_{k})+\sum _{i=1}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k})p_{i}(x_{1},\ldots ,x_{k}),$

Из этого выражения немедленно следует $k$-тое тождество Ньютона при $k$ переменных. Поскольку оно является тождеством между симметрическими однородными многочленами.

Далее всё выводится из этого факта. При $n<k$ тождество очевидным образом получается из присваивания $x_{n+1}=x_{n+2}=\dots =x_{k}=0$ в тождестве для $n=k$

Пусть теперь $n=k+1$. Обозначим через $f(x_{1},\dots ,x_{n})$ и $g(x_{1},\dots ,x_{n})$ соответственно левую и правую части тождества. Из выполнения тождества при $n=k$ следует, что

${\begin{aligned}&f(0,x_{2},\dots ,x_{k},x_{k+1})=g(0,x_{2},\dots ,x_{k},x_{k+1})\\&f(x_{1},0,\dots ,x_{k},x_{k+1})=g(x_{1},0,\dots ,x_{k},x_{k+1})\\&\dots \\&f(x_{1},x_{2},\dots ,0,x_{k+1})=g(x_{1},x_{2},\dots ,0,x_{k+1})\\&f(x_{1},x_{2},\dots ,x_{k},0)=g(x_{1},x_{2},\dots ,x_{k},0)\end{aligned}}$

Однако из этого следует, что разность $f-g$ представима в виде $h(x_{1},\dots ,x_{n})x_{i}$ для любого $i$ (если бы не была, то при каких-то $x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{k+1}$ разность была бы ненулевой и одно из равенств, обозначенных выше, не выполнялось бы). Следовательно, разность $f-g$ представима в виде $h(x_{1},\dots ,x_{n})x_{1}x_{2}\dots x_{k}x_{k+1}$, однако это невозможно так как полная степень и $f$ и $g$ равна $k$.

Аналогичные рассуждения для $n>k+1$ дают индукционный переход и доказывают тождества для произвольного $n$.

Через формальные степенные ряды

Прямым раскрытием скобок можно получить, что

$\prod _{i=1}^{n}(t-x_{i})=\sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\dots ,x_{n})t^{n-k}$

$\prod _{i=1}^{n}(1-{\frac {x_{i}}{t}})=\sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\dots ,x_{n}){\frac {1}{t^{k}}}$

Обозначая $s={\frac {1}{t}}$, получаем $\prod _{i=1}^{n}(1-x_{i}s)=\sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\dots ,x_{n})s^{k}$.

Формально дифференцируя (беря производную) по $s$ и домножая обе части на $s$, получаем

${\begin{aligned}\sum _{k=0}^{n}(-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})s^{k}&=s\sum _{i=1}^{n}\left[(-x_{i})\prod \nolimits _{j\neq i}(1-x_{j}s)\right]\\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}s}{1-x_{i}s}}\right)\prod \nolimits _{j=1}^{n}(1-x_{j}s)\\&=-\left[\sum _{i=1}^{n}\sum _{j=1}^{\infty }(x_{i}s)^{j}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell }e_{\ell }(x_{1},\ldots ,x_{n})s^{\ell }\right]\\&=\left[\sum _{j=1}^{\infty }p_{j}(x_{1},\ldots ,x_{n})s^{j}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell -1}e_{\ell }(x_{1},\ldots ,x_{n})s^{\ell }\right],\\\end{aligned}}$

Так как тождественное равенство многочленов влечёт равенство всех коэффициентов, то по правилам умножения многочленов из этого напрямую следует, что

$(-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})=\sum _{j=1}^{k}(-1)^{k-j-1}p_{j}(x_{1},\ldots ,x_{n})e_{k-j}(x_{1},\ldots ,x_{n}),$

Через телескопический ряд

Пусть фиксировано некоторое $k\geq 1$. Обозначим через $r_{i}^{(k)}(x_{1},\dots ,x_{n})$ сумму всех одночленов, состоящих из $k$ различных переменных, одна из которых входит в одночлен со степенью $i$, а все другие - со степенью 1. Такие одночлены естественным образом возникают в произведении $p_{i}(x_{1},\dots ,x_{n})e_{k-i}(x_{1},\dots ,x_{n})$ (переменные со степенью $i$ "приходят" из полинома $p_{i}$, а остальные, входящие в одночлен с первой степенью - из $e_{k-i}$).

Конкретнее, легко проверяются следующие тождества:

${\begin{aligned}&p_{1}e_{k-1}=ke_{k}+r_{2}^{(k)}\\&p_{i}e_{k-i}=r_{i}^{(k)}+r_{i+1}^{(k)},&1<i<k\\&p_{k}e_{0}=p_{k}=r_{k}^{(k)}\end{aligned}}$

Особенность первого из них обусловлена, грубо говоря, тем, что при $i\geq 2$ для одночлена $x_{0}^{i}x_{1}\dots x_{k-i}$ однозначно понятно, какая переменная взята из $p_{i}$, а какие - из $e_{k-i}$, так что каждый такой многочлен входит в произведение $p_{i}e_{k-i}$ с коэффициентом $1$. В случае же $i=1$ многочлен $x_{1},\dots ,x_{k}$ встретится в произведении $p_{1}e_{k-1}$ ровно $k$ раз - как каждое возможное перемножение одной из переменных с остальной частью одночлена: $x_{1}x_{2}\dots x_{k-1}x_{k}=x_{1}\cdot x_{2}x_{3}\dots x_{k-1}x_{k}=x_{2}\cdot x_{1}x_{3}\dots x_{k-1}x_{k}=\dots =x_{k}\cdot x_{1}x_{2}\dots x_{k-2}x_{k-1}$. Это даёт коэффициент $k$ при $e_{k}$

Из представленных выше тождеств легко получить, что

${\begin{aligned}&p_{1}e_{k-1}-p_{2}e_{k-2}+\dots +(-1)^{k-1}p_{k}=\\&=ke_{k}+r_{2}^{(k)}-\left({r_{2}^{(k)}+r_{3}^{(k)}}\right)+\left({r_{3}^{(k)}+r_{4}^{(k)}}\right)-\dots +(-1)^{k}r_{k}^{(k)}=\\&=ke_{k}+r_{2}^{(k)}-r_{2}^{(k)}-r_{3}^{(k)}+r_{3}^{(k)}+r_{4}^{(k)}-r_{4}^{(k)}\dots +(-1)^{k-1}r_{k}^{(k)}+(-1)^{k}r_{k}^{(k)}=\\&=ke_{k}\\\end{aligned}}$

Связанные тождества

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

Раскрывая явно выражение $e_{i}$ через $p_{i}$, получим представления

${\begin{aligned}e_{1}&=p_{1},\\e_{2}&=\textstyle {\frac {1}{2}}p_{1}^{2}-{\frac {1}{2}}p_{2}&&=\textstyle {\frac {1}{2}}(p_{1}^{2}-p_{2}),\\e_{3}&=\textstyle {\frac {1}{6}}p_{1}^{3}-{\frac {1}{2}}p_{1}p_{2}+{\frac {1}{3}}p_{3}&&=\textstyle {\frac {1}{6}}(p_{1}^{3}-3p_{1}p_{2}+2p_{3}),\\e_{4}&=\textstyle {\frac {1}{24}}p_{1}^{4}-{\frac {1}{4}}p_{1}^{2}p_{2}+{\frac {1}{8}}p_{2}^{2}+{\frac {1}{3}}p_{1}p_{3}-{\frac {1}{4}}p_{4}&&=\textstyle {\frac {1}{24}}(p_{1}^{4}-6p_{1}^{2}p_{2}+3p_{2}^{2}+8p_{1}p_{3}-6p_{4}),\\&~~\vdots \\e_{n}&=(-1)^{n}\sum _{m_{1}+2m_{2}+\cdots +nm_{n}=n \atop m_{1}\geq 0,\ldots ,m_{n}\geq 0}\prod _{i=1}^{n}{\frac {(-p_{i})^{m_{i}}}{m_{i}!i^{m_{i}}}}\\\end{aligned}}$

Общая формула может быть также переписана как

$e_{n}={\frac {(-1)^{n}}{n!}}B_{n}(-p_{1},-1!p_{2},-2!p_{3},\ldots ,-(n-1)!p_{n}),$

где $B_{n}$ - многочлен Белла. Такое представление, в частности, приводит к следующему тождеству производящих функций:

$\sum _{n=0}^{\infty }e_{n}\,X^{n}=\exp \left(\sum _{n=1}^{\infty }{\frac {(-1)^{n+1}}{n}}p_{n}\,X^{n}\right).$

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

Аналогично, раскрывая напрямую рекуррентные выражения, можно получить, что

${\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}^{2}-2e_{2},\\p_{3}&=e_{1}^{3}-3e_{2}e_{1}+3e_{3},\\p_{4}&=e_{1}^{4}-4e_{2}e_{1}^{2}+4e_{3}e_{1}+2e_{2}^{2}-4e_{4},\\p_{5}&=e_{1}^{5}-5e_{2}e_{1}^{3}+5e_{3}e_{1}^{2}+5e_{2}^{2}e_{1}-5e_{4}e_{1}-5e_{3}e_{2}+5e_{5},\\p_{6}&=e_{1}^{6}-6e_{2}e_{1}^{4}+6e_{3}e_{1}^{3}+9e_{2}^{2}e_{1}^{2}-6e_{4}e_{1}^{2}-12e_{3}e_{2}e_{1}+6e_{5}e_{1}-2e_{2}^{3}+3e_{3}^{2}+6e_{4}e_{2}-6e_{6}.\end{aligned}}$

Первые четыре формулы были получены Альбером Жираром ещё до Ньютона, в 1629 году. Общая формула имеет следующий вид:

$p_{m}=\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,r_{m}\geq 0}(-1)^{m}{\frac {m(r_{1}+r_{2}+\cdots +r_{m}-1)!}{r_{1}!r_{2}!\cdots r_{m}!}}\prod _{i=1}^{m}(-e_{i})^{r_{i}}.$

Это может быть переформулировано в терминах многочленов Белла:

$p_{m}=(-1)^{m}m\sum _{k=1}^{m}{\frac {1}{k}}{\hat {B}}_{m,k}(-e_{1},\dots ,-e_{m-k+1}).$

Приложения

Приложения к корням многочленов

Многочлен $f(x)$ с корнями $x_{1},\dots ,x_{n}$ может быть представлен как

$f(x)=\prod _{i=1}^{n}\left(x-x_{i}\right)=\sum _{k=0}^{n}(-1)^{n-k}e_{n-k}x^{k},$,

где коэффициенты $e_{k}=e_{k}(x_{1},\dots ,x_{n})$ - симметрические многочлены, определённые выше. При известных значениях степенных сумм $p_{k}(x_{1},\dots ,x_{n})=\sum \limits _{i=1}^{n}{{x_{i}}^{k}}$ коэффициенты многочлена $f(x)$ можно найти из рекуррентных формул.

Приложения к характеристическим многочленам матриц

Тождества Ньютона позволяют свести вычисление коэффициентов характеристического многочлена матрицы $A$ к вычислению следа различных её степеней.

Рассмотрим характеристический многочлен некоторой матрицы $A$. Его корни $x_{1},\dots ,x_{n}$ являются собственными числами этой матрицы (каждый корень представлен со своей кратностью). Тогда коэффициенты характеристического многочлена выражаются через симметрические многочлены $e_{i}$.

Для любого положительного $k$ собственными числами матрицы $A^{k}$ являются степени ${x_{1}}^{k},\dots ,{x_{n}}^{k}$. Поскольку сумма собственных чисел матрицы равна её следу, то

$p_{k}(x_{1},\dots ,x_{n})=tr(A^{k})$

Следовательно, и $e_{1},\dots ,e_{n}$, и коэффициенты характеристического многочлена можно выразить линейно из $tr(A),\dots ,tr(A^{n})$. Вычисление коэффициентов многочлена, таким образом, сводится к двум этапам:

• вычисление степеней матрицы $A$ и их следа
• решение системы линейных уравнений с треугольной матрицей

Оба этапа относятся к классу сложности NC, так что задача нахождения коэффициентов характеристического многочлена тоже относится к классу NC. На этой идее основан алгоритм Фадеева-Леверье (1840).

Поскольку по теореме Гамильтона-Кэли любая матрица является корнем своего характеристического многочлена, то быстрое вычисление коэффициентов этого многочлена даёт быстрый способ нахождения обратной матрицы.

Приложения к тригонометрическим суммам

Тождества Ньютона могут использоваться при оценке рациональных тригонометрических сумм по простому модулю для однозначного нахождения частного случая интеграла Виноградова при равном количестве переменных и уравнений.

Примечания

• Tignol, Jean-Pierre. Galois' theory of algebraic equations (неопр.). — Singapore: World Scientific, 2001. — ISBN 978-981-02-4541-2.
• Bergeron, F.; Labelle, G.; Leroux, P. Combinatorial species and tree-like structures (англ.). — Cambridge: Cambridge University Press, 1998. — ISBN 978-0-521-57323-8.
• Cameron, Peter J. Permutation Groups (неопр.). — Cambridge: Cambridge University Press, 1999. — ISBN 978-0-521-65378-7.
• Cox, David; Little, John, and O'Shea, Donal. Ideals, Varieties, and Algorithms (неопр.). — New York: Springer-Verlag, 1992. — ISBN 978-0-387-97847-5.
• Eppstein, D.; Goodrich, M. T. (2007). "Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters". Algorithms and Data Structures, 10th International Workshop, WADS 2007. Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637—648. arXiv:0704.3313. Bibcode:2007arXiv0704.3313E.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
• Littlewood, D. E. The theory of group characters and matrix representations of groups (англ.). — Oxford: Oxford University Press, 1950. — P. viii+310. — ISBN 0-8218-4067-3.
• Macdonald, I. G. Symmetric functions and Hall polynomials (англ.). — Oxford: The Clarendon Press, Oxford University Press, 1979. — P. viii+180. — (Oxford Mathematical Monographs). — ISBN 0-19-853530-9.
• Macdonald, I. G. Symmetric functions and Hall polynomials (англ.). — Second. — New York: Oxford Science Publications. The Clarendon Press, Oxford University Press, 1995. — P. x+475. — (Oxford Mathematical Monographs). — ISBN 0-19-853489-2.
• Mead, D.G. Newton's Identities (англ.) // The American Mathematical Monthly : journal. — Mathematical Association of America, 1992. — Vol. 99, no. 8. — P. 749—751. — doi:10.2307/2324242. — .
• Stanley, Richard P. Enumerative Combinatorics, Vol. 2 (неопр.). — Cambridge University Press, 1999. — ISBN 0-521-56069-1.
• Прасолов В.В. Многочлены. — 3-е изд., испр. — М.: МЦНМО, 2003. — 336 с. — ISBN 5-94057-077-1