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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

${\displaystyle 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}$

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

${\displaystyle 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}),}$

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

${\displaystyle \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}}}}$

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

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

${\displaystyle {\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}}}$

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

${\displaystyle (-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}),}$

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

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

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

${\displaystyle {\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}}}$

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

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

${\displaystyle {\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 году. Общая формула имеет следующий вид:

${\displaystyle 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}}.}$

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

• вычисление степеней матрицы ${\displaystyle 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. (неопр.) . — 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 : . Bibcode : . {{ 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. (англ.) // The American Mathematical Monthly : journal. — Mathematical Association of America, 1992. — Vol. 99 , no. 8 . — P. 749—751 . — doi : . — JSTOR .
• Stanley, Richard P. Enumerative Combinatorics, Vol. 2 (неопр.) . — Cambridge University Press , 1999. — ISBN 0-521-56069-1 .
• Прасолов В.В. Многочлены. — 3-е изд., испр. — М.: МЦНМО, 2003. — 336 с. — ISBN 5-94057-077-1