Identitatea lui Newton

În matematică , identitățile lui Newton , cunoscute și sub denumirea de formule Newton-Girard , definesc relațiile dintre două tipuri de polinoame simetrice , și anume între polinoamele simetrice elementare și sumele de putere ale lui Newton. Pentru un polinom arbitrar P , ele fac posibilă exprimarea sumei k --lea puteri ale tuturor rădăcinilor lui P (luând în considerare multiplicitatea) în termeni de coeficienți ai lui P , fără a găsi efectiv rădăcinile. Aceste identități au fost descoperite de Isaac Newton în jurul anului 1666 și, posibil, în lucrările timpurii (1629) ale lui Albert Girard . Ei găsesc aplicații în multe domenii ale matematicii, inclusiv teoria Galois , teoria invariante , teoria grupurilor , combinatorie , precum și în alte științe, inclusiv relativitatea generală .

Declarație de identități

Pentru variabile și pentru a lua în considerare sumele puterilor --lea ale acestor variabile: $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}.

Notăm și prin polinoame simetrice elementare . Un polinom este suma tuturor produselor posibile ale diferitelor variabile, în special $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{aliniat}}

Atunci identitățile lui Newton pot fi scrise după cum urmează:

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

pentru toată lumea . În special, pentru $k\geq 1$ $k>n\geq 1$

0=\sum _{i=kn}^{k}(-1)^{i-1}e_{ki}(x_{1},\ldots,x_{n})p_{i}( x_{1},\ldots ,x_{n}),

Pentru primele câteva valori , obținem: $k$

{\begin{aligned}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{aligned}}

Adevărul acestor identități nu depinde de numărul de variabile, chiar și atunci când părțile din stânga și din dreapta sunt egale cu zero. Aceste egalități ne permit să exprimăm recursiv în termeni de : $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}}

Metode de probă

Fiecare dintre identitățile lui Newton poate fi verificată folosind operații algebrice elementare, dar formula generală are nevoie de dovezi. Există mai multe moduri diferite de a obține identități.

Mai jos notăm numărul de variabile cu , iar numărul de identitate (numărul de termeni din suma din partea dreaptă) cu . $n$ $k$

Printr-un caz special $k=n$

Prin definitie, $\prod _{i=1}^{k}(t-x_{i})=\sum _{i=0}^{k}(-1)^{ki}e_{ki}(x_ {1},\ldots ,x_{k})t^{i}$

Prin urmare, pentru că avem $t=x_{j)$

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

Însumând peste tot , obținem $j$

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

Această expresie implică imediat identitatea lui Newton pentru variabile. Pentru că este o identitate între polinoame simetrice omogene . $k$ $k$

Totul decurge din acest fapt. Pentru , identitatea rezultă în mod evident din atribuirea în identitatea pentru $n<k$ $x_{n+1}=x_{n+2}=\dots =x_{k}=0$ $n=k$

Lasă acum . Indicați cu și , respectiv, părțile stânga și dreapta ale identității. Din îndeplinirea identității la , rezultă că $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}}

Cu toate acestea, rezultă din aceasta că diferența poate fi reprezentată sub formă pentru oricare (dacă nu, atunci pentru unii diferența ar fi diferită de zero și una dintre egalitățile indicate mai sus nu ar fi valabilă). Prin urmare, diferența poate fi reprezentată ca , dar acest lucru este imposibil deoarece puterea deplină a și și este egală cu . $fg$ $h(x_{1},\dots,x_{n})x_{i)$ $i$ ${\displaystyle x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{k+1))$ $fg$ $h(x_{1},\dots,x_{n})x_{1}x_{2}\dots x_{k}x_{k+1)$ $f$ $g$ $k$

Argumente similare pentru a da o tranziție inductivă și a dovedi identitățile pentru un arbitrar . $n>k+1$ $n$

Prin serie de putere formală

Deschizând direct parantezele, se poate obține asta

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

{\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))))

Indicând , obținem . $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}$

Diferențiând formal (luând o derivată) în raport cu și înmulțind ambele părți cu , obținem $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{aliniat}}

Deoarece egalitatea identică a polinoamelor implică egalitatea tuturor coeficienților, atunci, conform regulilor de înmulțire a polinoamelor, aceasta implică în mod direct că

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

Prin raza telescopică

Lasă unele să fie reparate . Se notează prin suma tuturor monomiilor , constând din diferite variabile, dintre care una este inclusă în monomiul cu grad , și toate celelalte - cu gradul 1. Astfel de monomii apar în mod natural în produs (variabile cu grad „vin” din polinom , iar restul cuprins în monom cu gradul I - din ). $k\geq 1$ $r_{i}^{(k)}(x_{1},\dots,x_{n})$ $k$ $i$ $p_{i}(x_{1},\dots,x_{n})e_{ki}(x_{1},\dots,x_{n})$ $i$ $p_{i}$ $e_{ki)$

Mai precis, următoarele identități sunt ușor de verificat:

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

Particularitatea primei dintre ele se datorează, în linii mari, faptului că pentru un monom este clar în mod unic din ce variabilă este luată și din care - , astfel încât fiecare astfel de polinom este inclus în produsul cu un coeficient . În acest caz, polinomul va apărea exact o dată în produs - ca fiecare posibilă înmulțire a uneia dintre variabile cu restul monomului: . Aceasta dă coeficientul $i\geq 2$ $x_{0}^{i}x_{1}\dots x_{ki)$ $p_{i}$ $e_{ki)$ $p_{i}e_{ki)$ $unu$ $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}$

Din identitățile de mai sus este ușor să obții asta

{\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)+\ stânga({r_{3}^{(k)}+r_{4}^{(k)}}\dreapta)-\puncte +(-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{aliniat}}

Identități înrudite

Reprezentări directe ale polinoamelor simetrice elementare prin sume de putere

Expandând explicit expresia prin , obținem reprezentările $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}}

Formula generală poate fi rescrisă și ca

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

unde este polinomul Bell . O astfel de reprezentare, în special, conduce la următoarea identitate a funcțiilor generatoare: $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}\dreapta).

Reprezentarea directă a sumelor de putere în termeni de polinoame simetrice elementare

În mod similar, extinzând direct expresiile recursive, se poate obține asta

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

Primele patru formule au fost obținute de Albert Girard înainte de Newton, în 1629. Formula generală este următoarea:

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}}.

Aceasta poate fi reformulată în termeni de polinoame Bell:

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

Aplicații

Aplicații la rădăcinile polinoamelor

Un polinom cu rădăcini poate fi reprezentat ca $f(x)$ $x_{1},\dots ,x_{n}$

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

unde coeficienții sunt polinoamele simetrice definite mai sus. Pentru valorile cunoscute ale sumelor de putere , coeficienții unui polinom pot fi găsiți din formule recursive. $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)$

Aplicații la polinoame caracteristice ale matricelor

Identitățile lui Newton ne permit să reducem calculul coeficienților polinomului caracteristic al unei matrice la calculul urmei diferitelor sale puteri. $A$

Se consideră polinomul caracteristic al unei matrice . Rădăcinile sale sunt valorile proprii ale acestei matrice (fiecare rădăcină este reprezentată cu propria sa multiplicitate). Apoi coeficienții polinomului caracteristic sunt exprimați în termeni de polinoame simetrice . $A$ $x_{1},\dots ,x_{n}$ $e_{i}$

Pentru orice pozitiv , valorile proprii ale matricei sunt puterile lui . Deoarece suma valorilor proprii ale unei matrice este egală cu urma sa , atunci $k$ $A^{k}$ ${x_{1}}^{k},\dots ,{x_{n}}^{k}$

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

Prin urmare, și , și coeficienții polinomului caracteristic pot fi exprimați liniar din . Calculul coeficienților unui polinom se reduce astfel la două etape: $e_{1},\dots ,e_{n}$ $tr(A),\dots ,tr(A^{n})$

calculul puterilor matriceale și urma lor $A$
rezolvarea unui sistem de ecuații liniare cu matrice triunghiulară

Ambele etape aparțin clasei de complexitate NC , astfel încât problema găsirii coeficienților polinomului caracteristic aparține și ea clasei NC. Algoritmul Fadeev-Leverrier (1840) se bazează pe această idee .

Deoarece, conform teoremei Hamilton-Cayley, orice matrice este rădăcina polinomului său caracteristic, atunci un calcul rapid al coeficienților acestui polinom oferă o modalitate rapidă de a găsi matricea inversă.

Aplicații la sumele trigonometrice

Identitățile lui Newton pot fi utilizate în estimarea sumelor trigonometrice raționale modulo prime pentru a găsi în mod unic un caz special al integralei Vinogradov cu un număr egal de variabile și ecuații.

Note

Tignol, Jean-Pierre. Teoria ecuațiilor algebrice a lui Galois (neopr.) . - Singapore: World Scientific , 2001. - ISBN 978-981-02-4541-2 .
Bergeron, F.; Labelle, G.; Leroux, P. Specii combinatorii și structuri asemănătoare arborilor (engleză) . - Cambridge: Cambridge University Press , 1998. - ISBN 978-0-521-57323-8 .
Cameron, Peter J. Grupuri de permutare (nedefinite) . - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-65378-7 .
Cox, David; Little, John, și O'Shea, Donal. Idealuri, soiuri și algoritmi (nedefinite) . - New York: Springer-Verlag , 1992. - ISBN 978-0-387-97847-5 .
Eppstein, D.; Goodrich, M.T. (2007). „Identificarea rătăcitorilor eficientă în spațiu în fluxuri de date dus-întors prin identitățile lui Newton și filtrele Bloom inversabile”. Algoritmi și structuri de date, 10th International Workshop, WADS 2007 . Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637-648. arXiv : 0704.3313 . Cod biblic : 2007arXiv0704.3313E .
Littlewood, D.E. Teoria caracterelor de grup și reprezentările matriceale ale grupurilor . - Oxford: Oxford University Press , 1950. - P. viii+310. — ISBN 0-8218-4067-3 .
Macdonald, I. G. Funcții simetrice și polinoame Hall . — Oxford: The Clarendon Press, Oxford University Press, 1979. — P. viii+180. — (Monografii matematice din Oxford). — ISBN 0-19-853530-9 .
Macdonald, I. G. Funcții simetrice și polinoame Hall . - Al doilea. — New York: Oxford Science Publications. The Clarendon Press, Oxford University Press, 1995. P. x+475. — (Monografii matematice din Oxford). — ISBN 0-19-853489-2 .
Mead, DG Newton's Identities // The American Mathematical Monthly : jurnal. - Asociația de matematică din America, 1992. - Vol. 99 , nr. 8 . - P. 749-751 . - doi : 10.2307/2324242 . — .
Stanley, Richard P. Combinatorică enumerativă, voi. 2 (neopr.) . - Cambridge University Press , 1999. - ISBN 0-521-56069-1 .
Prasolov V.V. Polinomiale. - Ed. a 3-a, Rev. — M.: MTsNMO, 2003. — 336 p. — ISBN 5-94057-077-1