Newtonin identiteetit

Matematiikassa Newtonin identiteetit , jotka tunnetaan myös nimellä Newton-Girard-kaavat , määrittelevät suhteita kahden tyyppisten symmetristen polynomien välillä, nimittäin alkeissymmetristen polynomien ja Newtonin potenssisummien välillä . Satunnaiselle polynomille P ne mahdollistavat P :n kaikkien juurien k :nnen potenssien summan ilmaisemisen (ottaen huomioon moninkertaisuuden) P :n kertoimilla ilman, että juuria löydetään. Isaac Newton löysi nämä identiteetit noin vuonna 1666 ja mahdollisesti Albert Girardin varhaisessa työssä (1629) . Niitä voidaan soveltaa monilla matematiikan aloilla, mukaan lukien Galois'n teoria , invarianttiteoria , ryhmäteoria , kombinatoriikka sekä muut tieteet, mukaan lukien yleinen suhteellisuusteoria .

Ilmoitus henkilöllisyydestä

Muuttujat ja näiden muuttujien potenssien summat : $x_1,\pisteet,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}.

Merkitään myös alkeissymmetrisillä polynomeilla . Polynomi on erityisesti eri muuttujien kaikkien mahdollisten tulojen summa $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{tasattu}}

Sitten Newtonin identiteetit voidaan kirjoittaa seuraavasti:

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}),

kaikille . Erityisesti varten $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}),

Muutamista ensimmäisistä arvoista saamme: $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{tasattu}}

Näiden identiteettien totuus ei riipu muuttujien lukumäärästä, vaikka vasen ja oikea puoli olisivat nolla. Nämä yhtäläisyydet antavat meille mahdollisuuden ilmaista rekursiivisesti : $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}}

Todistusmenetelmät

Jokainen Newtonin identiteetin yksilö voidaan varmentaa alkebrallisten operaatioiden avulla, mutta yleinen kaava tarvitsee todisteen. On olemassa useita eri tapoja johtaa identiteettiä.

Alla merkitään muuttujien lukumäärä merkillä ja tunnistenumero (oikealla puolella olevan summan termien määrä) . $n$ $k$

Erikoistapauksen kautta $k = n$

Määritelmän mukaan $\prod _{i=1}^{k}(t-x_{i})=\sum _{i=0}^{k}(-1)^{ki}e_{ki}(x_ {1},\ldots ,x_{k})t^{i}$

Siksi meillä on ${\näyttötyyli 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

Yhteenvetona kaiken saamme $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}),

Tämä lauseke merkitsee välittömästi Newtonin -:nnen identiteetin muuttujille. Koska se on identiteetti symmetristen homogeenisten polynomien välillä . $k$ $k$

Kaikki seuraa tästä tosiasiasta. Sillä , identiteetti seuraa ilmeisesti identiteetin tehtävästä $n<k$ $x_{n+1}=x_{n+2}=\pisteet =x_{k}=0$ $n=k$

Anna nyt . Merkitse identiteetin vasenta ja oikeaa puolta ja vastaavasti . Henkilöllisyyden täyttymisestä osoitteessa , seuraa, että $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,\pisteet ,x_{k},x_{k+1})=g(x_{1},0,\pisteet ,x_{k },x_{k+1})\\&\dots \\&f(x_{1},x_{2},\dots ,0,x_{k+1})=g(x_{1},x_{ 2},\pisteet ,0,x_{k+1})\\&f(x_{1},x_{2},\pisteet ,x_{k},0)=g(x_{1},x_{2 },\pisteet ,x_{k},0)\end{tasattu}}

Tästä kuitenkin seuraa, että ero voidaan esittää muodossa millä tahansa (jos ei, niin joillekin ero olisi nollasta poikkeava ja yksi yllä mainituista yhtälöistä ei päde). Siksi ero voidaan esittää muodossa , mutta tämä on mahdotonta, koska ja ja :n täysi teho on yhtä suuri kuin . $fg$ ${\displaystyle h(x_{1},\dots ,x_{n})x_{i))$ $i$ ${\displaystyle x_{1},\dots ,x_{i-1},x_{i+1},\dots ,x_{k+1))$ $fg$ ${\displaystyle h(x_{1},\dots ,x_{n})x_{1}x_{2}\dots x_{k}x_{k+1))$ $f$ $g$ $k$

Samanlaiset argumentit antavat induktiivisen siirtymän ja todistavat identiteetit mielivaltaiselle . $n>k+1$ $n$

Muodollisen tehosarjan kautta

Avaamalla kiinnikkeet suoraan saat sen

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

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

Merkitsemällä saamme . $s={\frac {1}{t))$ $\prod _{i=1}^{n}(1-x_{i}s)=\sum _{k=0}^{n}(-1)^{k}e_{k}( x_{1},\pisteet ,x_{n})s^{k}$

Erottamalla muodollisesti (ottamalla derivaatan) suhteessa ja kertomalla molemmat osat : lla , saamme $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 \nlimits _{j\neq i}(1-x_{j}s)\oikea] \\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}s}{1-x_{i}s}}\right)\prod \nlimits _{j =1}^{n}(1-x_{j}s)\\&=-\left[\sum _{i=1}^{n}\sum _{j=1}^{\infty }( x_{i}s)^{j}\oikea]\vasen[\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}\oikea]\vasen[\sum _{\ell =0}^{n}(-1)^{\ell -1}e_{\ell }(x_{1}, \ldots ,x_{n})s^{\ell }\right],\\\end{aligned}}

Koska polynomien identtinen yhtäläisyys merkitsee kaikkien kertoimien yhtäläisyyttä , tämä tarkoittaa polynomien kertolaskusääntöjen mukaan suoraan, että

(-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}),

Teleskooppialueen läpi

Osa korjataan . Merkitään kaikkien monomien summalla , joka koostuu eri muuttujista, joista yksi sisältyy monomiin asteella , ja kaikki muut - asteella 1. Tällaisia monomialeja syntyy luonnollisesti tulossa (muuttujat, joiden aste "tulevat" polynomista , ja loput sisältyvät monomiaaliin ensimmäisen asteen kanssa - alkaen ). $k\geq 1$ $r_{i}^{(k)}(x_{1},\pisteet ,x_{n})$ $k$ $i$ $p_{i}(x_{1},\pisteet ,x_{n})e_{ki}(x_{1},\pisteet ,x_{n})$ $i$ $p_{i}$ ${\displaystyle e_{ki))$

Tarkemmin sanottuna seuraavat henkilöllisyydet on helppo tarkistaa:

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

Ensimmäisen erikoisuus johtuu karkeasti ottaen siitä, että monomille on yksiselitteisesti selvää, mikä muuttuja on otettu ja mikä - mistä , joten jokainen tällainen polynomi sisältyy tuloon kertoimella . Siinä tapauksessa polynomi esiintyy tuotteessa täsmälleen kerran - koska jokainen muuttujan mahdollinen kertolasku monomin muun osan kanssa: . Tämä antaa kertoimen $i\geq 2$ ${\displaystyle x_{0}^{i}x_{1}\dots x_{ki))$ $p_{i}$ ${\displaystyle e_{ki))$ ${\displaystyle p_{i}e_{ki))$ $yksi$ $i=1$ ${\displaystyle x_{1},\dots ,x_{k))$ ${\displaystyle 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}\cpiste x_{1}x_{3}\pisteet x_{k-1}x_{k}=\pisteet =x_{k}\cpiste x_{1}x_{2}\pisteet x_{k -2}x_{k-1}$ $k$ $e_{k}$

Yllä olevista identiteeteistä se on helppo saada

{\begin{aligned}&p_{1}e_{k-1}-p_{2}e_{k-2}+\dots +(-1)^{k-1}p_{k}=\ \&=ke_{k}+r_{2}^{(k)}-\vasen({r_{2}^{(k)}+r_{3}^{(k)}}\oikea)+\ vasen({r_{3}^{(k)}+r_{4}^{(k)}}\oikea)-\pisteet +(-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)}\pisteet +(-1)^{k-1}r_{k}^{(k)}+( -1)^{k}r_{k}^{(k)}=\\&=ke_{k}\\\end{tasattu}}

Aiheeseen liittyvät identiteetit

Elementaaristen symmetristen polynomien suorat esitykset potenssisummilla

Laajennamalla ilmaisua eksplisiittisesti kautta saamme esitykset $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}}

Yleinen kaava voidaan myös kirjoittaa uudelleen muotoon

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

missä on Bellin polynomi . Tällainen esitys johtaa erityisesti seuraavan luovien funktioiden identiteetin luomiseen: $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}\oikea).

Potenssisummien suora esitys alkeissymmetrisillä polynomeilla

Vastaavasti laajentamalla rekursiolausekkeita suoraan, se voidaan saada

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

Ensimmäiset neljä kaavaa sai Albert Girard ennen Newtonia vuonna 1629. Yleinen kaava on seuraava:

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

Tämä voidaan muotoilla uudelleen Bell-polynomeilla:

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

Sovellukset

Sovellukset polynomien juuriin

Polynomi , jolla on juuret, voidaan esittää muodossa $f(x)$ $x_{1},\pisteet ,x_{n}$

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

jossa kertoimet ovat edellä määriteltyjä symmetrisiä polynomeja. Tunnetuille potenssisumman arvoille polynomin kertoimet löytyvät rekursiivisista kaavoista. $e_{k}=e_{k}(x_{1},\pisteet ,x_{n})$ $p_{k}(x_{1},\dots ,x_{n})=\sum \limits _{i=1}^{n}{{x_{i}}^{k}}$ $f(x)$

Sovellukset matriisien ominaispolynomeille

Newtonin identiteetit mahdollistavat matriisin ominaispolynomin kertoimien laskemisen pelkistämisen sen eri potenssien jäljen laskemiseen . $A$

Tarkastellaan jonkin matriisin ominaispolynomia . Sen juuret ovat tämän matriisin ominaisarvot (jokainen juuri esitetään omalla moninkertaisuudellaan). Sitten ominaispolynomin kertoimet ilmaistaan symmetrisinä polynomeina . $A$ $x_{1},\pisteet ,x_{n}$ $e_{i}$

Jokaiselle positiiviselle matriisin ominaisarvot ovat potenssit . Koska matriisin ominaisarvojen summa on yhtä suuri kuin sen jälki , niin $k$ $A^{k}$ ${x_{1}}^{k},\dots ,{x_{n}}^{k}$

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

Siksi ja , ja ominaispolynomin kertoimet voidaan ilmaista lineaarisesti . Polynomin kertoimien laskenta supistuu siten kahteen vaiheeseen: $e_{1},\pisteet ,e_{n}$ $tr(A),\dots ,tr(A^{n})$

matriisipotenssien ja niiden jäljen laskeminen $A$
lineaarisen yhtälöjärjestelmän ratkaisu kolmiomatriisilla

Molemmat asteet kuuluvat NC-kompleksisuusluokkaan , joten myös ominaispolynomin kertoimien löytämisongelma kuuluu NC-luokkaan. Fadeev-Leverrier-algoritmi (1840) perustuu tähän ajatukseen .

Koska Hamilton-Cayleyn lauseen mukaan mikä tahansa matriisi on sen ominaispolynomin juuri, tämän polynomin kertoimien nopea laskenta antaa nopean tavan löytää käänteinen matriisi.

Sovellukset trigonometrisiin summiin

Newtonin identiteettejä voidaan käyttää arvioitaessa rationaalisia trigonometrisiä summia modulo prime, jotta löydetään yksiselitteisesti Vinogradov-integraalin erikoistapaus, jossa on yhtä suuri määrä muuttujia ja yhtälöitä.

Muistiinpanot

Tignol, Jean-Pierre. Galois'n algebrallisten yhtälöiden teoria (uuspr.) . - Singapore: World Scientific , 2001. - ISBN 978-981-02-4541-2 .
Bergeron, F.; Labelle, G.; Leroux, P. Kombinatoriset lajit ja puumaiset rakenteet (englanniksi) . - Cambridge: Cambridge University Press , 1998. - ISBN 978-0-521-57323-8 .
Cameron, Peter J. Permutaatioryhmät (määrittämätön) . - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-65378-7 .
Cox, David; Little, John ja O'Shea, Donal. Ihanteet, lajikkeet ja algoritmit (epämääräinen) . - New York: Springer-Verlag , 1992. - ISBN 978-0-387-97847-5 .
Eppstein, D.; Goodrich, M.T. (2007). "Avaruustehokas räjähdysten tunnistus edestakaisissa tietovirroissa Newtonin identiteetin ja käännettävien Bloom-suodattimien avulla". Algoritmit ja tietorakenteet, 10. kansainvälinen työpaja, WADS 2007 . Springer-Verlag, Tietojenkäsittelytieteen luentomuistiinpanot 4619. s. 637-648. arXiv : 0704.3313 . Bibcode : 2007arXiv0704.3313E .
Littlewood, D.E. Ryhmämerkkien teoria ja ryhmien matriisiesitys . - Oxford: Oxford University Press , 1950. - P. viii+310. — ISBN 0-8218-4067-3 .
Macdonald, I. G. Symmetriset funktiot ja Hall-polynomit . — Oxford: The Clarendon Press, Oxford University Press, 1979. — P. viii+180. - (Oxford Mathematical Monographs). — ISBN 0-19-853530-9 .
Macdonald, I. G. Symmetriset funktiot ja Hall-polynomit . — Toiseksi. — New York: Oxford Science Publications. The Clarendon Press, Oxford University Press, 1995. S. x+475. - (Oxford Mathematical Monographs). — ISBN 0-19-853489-2 .
Mead, DG Newtonin identiteetit // The American Mathematical Monthly : päiväkirja. - Mathematical Association of America, 1992. - Voi. 99 , ei. 8 . - s. 749-751 . - doi : 10.2307/2324242 . — .
Stanley, Richard P. Enumerative Combinatorics, Voi. 2 (uuspr.) . - Cambridge University Press , 1999. - ISBN 0-521-56069-1 .
Prasolov V.V. Polynomit. - 3. painos, Rev. — M.: MTsNMO, 2003. — 336 s. — ISBN 5-94057-077-1