Тождества Ньютона

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

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

Для переменных [math]\displaystyle{ x_1,\dots,x_n }[/math] и для [math]\displaystyle{ k \ge 1 }[/math] рассмотрим суммы [math]\displaystyle{ k }[/math]-тых степеней этих переменных:

[math]\displaystyle{ p_k(x_1,\ldots,x_n)=\sum\nolimits_{i=1}^nx_i^k = x_1^k+\cdots+x_n^k. }[/math]

Обозначим также через [math]\displaystyle{ e_k (x_1,\dots,x_n) }[/math] элементарные симметрические многочлены. Многочлен [math]\displaystyle{ e_k (x_1,\dots,x_n) }[/math] представляет собой сумму всех возможных произведений [math]\displaystyle{ k }[/math] разных переменных, в частности

[math]\displaystyle{ \begin{align} 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\lt j\leq n}x_ix_j,\\ & {}\ \ \vdots \\ e_n(x_1,\ldots,x_n) &= x_1x_2\cdots x_n,\\ e_k(x_1,\ldots,x_n) &= 0, \quad\text{for}\ k\gt n.\\ \end{align} }[/math]

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

[math]\displaystyle{ ke_k(x_1,\ldots,x_n) = \sum_{i=1}^k(-1)^{i-1} e_{k-i} (x_1,\ldots,x_n) p_i(x_1,\ldots,x_n), }[/math]

для всех [math]\displaystyle{ k \ge 1 }[/math]. В частности, для [math]\displaystyle{ k \gt n \ge 1 }[/math]

[math]\displaystyle{ 0 = \sum_{i=k-n}^k(-1)^{i-1} e_{k - i} (x_1, \ldots, x_n) p_i(x_1, \ldots, x_n), }[/math]

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

[math]\displaystyle{ \begin{align} e_1(x_1,\ldots,x_n) &= p_1(x_1,\ldots,x_n),\\ 2e_2(x_1,\ldots,x_n) &= e_1(x_1,\ldots,x_n)p_1(x_1,\ldots,x_n)-p_2(x_1,\ldots,x_n),\\ 3e_3(x_1,\ldots,x_n) &= e_2(x_1,\ldots,x_n)p_1(x_1,\ldots,x_n) - e_1(x_1,\ldots,x_n)p_2(x_1,\ldots,x_n) + p_3(x_1,\ldots,x_n).\\ \end{align} }[/math]

Истинность этих тождеств не зависит от количества переменных, даже когда левая и правая части равны нулю. Эти равенства позволяют рекуррентно выразить [math]\displaystyle{ p_i }[/math] через [math]\displaystyle{ e_i }[/math]:

[math]\displaystyle{ \begin{align} p_1 &= e_1,\\ p_2 &= e_1p_1-2e_2,\\ p_3 &= e_1p_2 - e_2p_1 + 3e_3 ,\\ p_4 &= e_1p_3 - e_2p_2 + e_3p_1 - 4e_4, \\ & {}\ \ \vdots \end{align} }[/math]

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

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

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

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

По определению, [math]\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 }[/math]

Следовательно, при [math]\displaystyle{ t=x_j }[/math] имеем

[math]\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 }[/math]

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

[math]\displaystyle{ 0= (-1)^k k e_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), }[/math]

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

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

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

[math]\displaystyle{ \begin{align} & 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{align} }[/math]

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

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

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

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

[math]\displaystyle{ \prod_{i=1}^n (t - x_i) = \sum_{k=0}^n (-1)^{k} e_k(x_1,\dots,x_n) t^{n-k} }[/math]

[math]\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} }[/math]

Обозначая [math]\displaystyle{ s=\frac{1}{t} }[/math], получаем [math]\displaystyle{ \prod_{i=1}^n (1 - x_i s) = \sum_{k=0}^n (-1)^{k} e_k(x_1,\dots,x_n) s^k }[/math].

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

[math]\displaystyle{ \begin{align} \sum_{k=0}^n (-1)^{k}k e_k(x_1,\ldots,x_n) s^k &= s \sum_{i=1}^n \left[(-x_i) \prod\nolimits_{j \neq i}(1 - x_js)\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{align} }[/math]

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

[math]\displaystyle{ (-1)^{k}k e_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), }[/math]

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

Пусть фиксировано некоторое [math]\displaystyle{ k \ge 1 }[/math]. Обозначим через [math]\displaystyle{ r^{(k)}_i(x_1,\dots,x_n) }[/math] сумму всех одночленов, состоящих из [math]\displaystyle{ k }[/math] различных переменных, одна из которых входит в одночлен со степенью [math]\displaystyle{ i }[/math], а все другие - со степенью 1. Такие одночлены естественным образом возникают в произведении [math]\displaystyle{ p_i(x_1,\dots,x_n) e_{k-i}(x_1,\dots,x_n) }[/math] (переменные со степенью [math]\displaystyle{ i }[/math] "приходят" из полинома [math]\displaystyle{ p_i }[/math], а остальные, входящие в одночлен с первой степенью - из [math]\displaystyle{ e_{k-i} }[/math]).

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

[math]\displaystyle{ \begin{align} & p_1 e_{k-1} = k e_k + r^{(k)}_2 \\ & p_i e_{k-i} = r^{(k)}_i + r^{(k)}_{i+1}, & 1 \lt i \lt k \\ & p_k e_0 = p_k = r^{(k)}_k \end{align} }[/math]

Особенность первого из них обусловлена, грубо говоря, тем, что при [math]\displaystyle{ i \ge 2 }[/math] для одночлена [math]\displaystyle{ x_0^i x_1 \dots x_{k-i} }[/math] однозначно понятно, какая переменная взята из [math]\displaystyle{ p_i }[/math], а какие - из [math]\displaystyle{ e_{k-i} }[/math], так что каждый такой многочлен входит в произведение [math]\displaystyle{ p_i e_{k-i} }[/math] с коэффициентом [math]\displaystyle{ 1 }[/math]. В случае же [math]\displaystyle{ i=1 }[/math] многочлен [math]\displaystyle{ x_1,\dots,x_k }[/math] встретится в произведении [math]\displaystyle{ p_1 e_{k-1} }[/math] ровно [math]\displaystyle{ k }[/math] раз - как каждое возможное перемножение одной из переменных с остальной частью одночлена: [math]\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} }[/math]. Это даёт коэффициент [math]\displaystyle{ k }[/math] при [math]\displaystyle{ e_k }[/math]

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

[math]\displaystyle{ \begin{align} & p_1 e_{k-1} - p_2 e_{k-2} + \dots + (-1)^{k-1} p_k = \\ & = k e_k + r^{(k)}_2 - \left({r^{(k)}_2 + r^{(k)}_3}\right) + \left({r^{(k)}_3 + r^{(k)}_4}\right) - \dots + (-1)^k r^{(k)}_k = \\ & = k e_k + r^{(k)}_2 - r^{(k)}_2 - r^{(k)}_3 + r^{(k)}_3 + r^{(k)}_4 - r^{(k)}_4 \dots + (-1)^{k-1} r^{(k)}_k + (-1)^k r^{(k)}_k = \\ & = k e_k \\ \end{align} }[/math]

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

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

Раскрывая явно выражение [math]\displaystyle{ e_i }[/math] через [math]\displaystyle{ p_i }[/math], получим представления

[math]\displaystyle{ \begin{align} e_1 &= p_1,\\ e_2 &= \textstyle\frac12p_1^2 - \frac12p_2 &&= \textstyle\frac12 ( p_1^2 - p_2 ),\\ e_3 &= \textstyle\frac16p_1^3 - \frac12p_1 p_2 + \frac13p_3 &&= \textstyle\frac{1}{6} ( p_1^3 - 3 p_1 p_2 + 2 p_3 ),\\ e_4 &= \textstyle\frac1{24}p_1^4 - \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 - \frac14p_4 &&= \textstyle\frac1{24} ( p_1^4 - 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 - 6 p_4 ),\\ &~~\vdots\\ e_n &= (-1)^n \sum_{m_1 + 2m_2 + \cdots + nm_n = n \atop m_1 \ge 0, \ldots, m_n \ge 0} \prod_{i=1}^n \frac{(-p_i)^{m_i}}{m_i ! i^{m_i}} \\ \end{align} }[/math]

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

[math]\displaystyle{ e_n = \frac{(-1)^n}{n!} B_{n}(- p_1, -1! p_2, - 2! p_3, \ldots, - (n-1)! p_n ), }[/math]

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

[math]\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). }[/math]

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

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

[math]\displaystyle{ \begin{align} p_1 &= e_1,\\ p_2 &= e_1^2 - 2 e_2,\\ p_3 &= e_1^3 - 3 e_2 e_1 + 3 e_3,\\ p_4 &= e_1^4 - 4 e_2 e_1^2 + 4 e_3 e_1 + 2 e_2^2 - 4 e_4,\\ p_5 &= e_1^5 - 5 e_2 e_1^3 + 5 e_3 e_1^2 + 5 e_2^2 e_1 - 5 e_4 e_1 - 5 e_3e_2 + 5 e_5,\\ p_6 &= e_1^6 - 6 e_2 e_1^4 + 6 e_3 e_1^3 + 9 e_2^2 e_1^2 - 6 e_4 e_1^2 - 12 e_3 e_2 e_1 + 6 e_5 e_1 - 2 e_2^3 + 3 e_3^2 + 6 e_4 e_2 - 6e_6. \end{align} }[/math]

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

[math]\displaystyle{ p_m = \sum_{r_1 + 2r_2 + \cdots + mr_m = m \atop r_1\ge 0, \ldots, r_m\ge 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}. }[/math]

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

[math]\displaystyle{ p_m = (-1)^m m \sum_{k=1}^m \frac{1}{k} \hat{B}_{m,k}(-e_1,\dots,-e_{m-k+1}). }[/math]

Приложения

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

Многочлен [math]\displaystyle{ f(x) }[/math] с корнями [math]\displaystyle{ x_1, \dots, x_n }[/math] может быть представлен как

[math]\displaystyle{ f(x) = \prod_{i=1}^n \left( x - x_i \right) = \sum_{k=0}^n (-1)^{n-k} e_{n-k} x^{k}, }[/math],

где коэффициенты [math]\displaystyle{ e_k = e_k (x_1, \dots, x_n) }[/math] - симметрические многочлены, определённые выше. При известных значениях степенных сумм [math]\displaystyle{ p_k (x_1, \dots, x_n) = \sum \limits_{i=1}^{n} {{x_i}^k} }[/math] коэффициенты многочлена [math]\displaystyle{ f(x) }[/math] можно найти из рекуррентных формул.

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

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

Рассмотрим характеристический многочлен некоторой матрицы [math]\displaystyle{ A }[/math]. Его корни [math]\displaystyle{ x_1, \dots, x_n }[/math] являются собственными числами этой матрицы (каждый корень представлен со своей кратностью). Тогда коэффициенты характеристического многочлена выражаются через симметрические многочлены [math]\displaystyle{ e_i }[/math].

Для любого положительного [math]\displaystyle{ k }[/math] собственными числами матрицы [math]\displaystyle{ A^k }[/math] являются степени [math]\displaystyle{ {x_1}^k, \dots, {x_n}^k }[/math]. Поскольку сумма собственных чисел матрицы равна её следу, то

[math]\displaystyle{ p_k (x_1, \dots, x_n) = tr(A^k) }[/math]

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

• вычисление степеней матрицы [math]\displaystyle{ A }[/math] и их следа
• решение системы линейных уравнений с треугольной матрицей

Оба этапа относятся к классу сложности 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. 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, 2007. — P. 637–648.

• 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