Identidades de newton

En matemáticas , las identidades de Newton , también conocidas como fórmulas de Newton-Girard , definen relaciones entre dos tipos de polinomios simétricos , a saber, entre polinomios simétricos elementales y sumas de potencias de Newton. Para un polinomio arbitrario P , permiten expresar la suma de las k -ésimas potencias de todas las raíces de P (teniendo en cuenta la multiplicidad) en función de los coeficientes de P , sin llegar a encontrar las raíces. Estas identidades fueron descubiertas por Isaac Newton alrededor de 1666, y posiblemente en los primeros trabajos (1629) de Albert Girard . Encuentran aplicación en muchas áreas de las matemáticas, incluida la teoría de Galois , la teoría de invariantes , la teoría de grupos , la combinatoria , así como otras ciencias, incluida la relatividad general .

Declaración de identidades

Para variables y para considerar las sumas de las -ésimas potencias de estas variables: $x_1,\puntos,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}.

También denotamos por polinomios simétricos elementales . Un polinomio es la suma de todos los productos posibles de diferentes variables, en particular $e_{k}(x_{1},\puntos,x_{n})$ $e_{k}(x_{1},\puntos,x_{n})$ $k$

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

Entonces las identidades de Newton se pueden escribir de la siguiente manera:

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

para todos En particular, para $k\geq 1$ ${\ Displaystyle 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}),

Para los primeros valores , obtenemos: $k$

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

La verdad de estas identidades no depende del número de variables, incluso cuando los lados izquierdo y derecho son iguales a cero. Estas igualdades nos permiten expresar recursivamente en términos de : $Pi}$ $e_{yo}$

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

Métodos de prueba

Cada individuo de las identidades de Newton se puede verificar usando operaciones algebraicas elementales, pero la fórmula general necesita prueba. Hay varias maneras diferentes de derivar identidades.

A continuación denotamos el número de variables por , y el número de identidad (el número de términos en la suma del lado derecho) por . $norte$ $k$

A través de un caso especial $k=n$

Por definición, $\prod_{i=1}^{k}(t-x_{i})=\sum_{i=0}^{k}(-1)^{ki}e_{ki}(x_ {1},\ldots,x_{k})t^{i}$

Por lo tanto, porque tenemos ${\ Displaystyle 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

Sumando sobre todo , obtenemos $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}),

Esta expresión implica inmediatamente la -ésima identidad de Newton para las variables. Porque es una identidad entre polinomios homogéneos simétricos . $k$ $k$

Todo se sigue de este hecho. Para , la identidad obviamente se sigue de la asignación en la identidad para ${\ estilo de visualización n<k}$ $x_{n+1}=x_{n+2}=\puntos =x_{k}=0$ $n = k$

Deja ahora . Denote por y respectivamente los lados izquierdo y derecho de la identidad. Del cumplimiento de la identidad en , se sigue que $n=k+1$ ${\ estilo de visualización f (x_ {1}, \ puntos, x_ {n})}$ $g(x_{1},\puntos,x_{n})$ $n = k$

{\begin{alineado}&f(0,x_{2},\puntos,x_{k},x_{k+1})=g(0,x_{2},\puntos,x_{k} ,x_{k+1})\\&f(x_{1},0,\puntos,x_{k},x_{k+1})=g(x_{1},0,\puntos,x_{k },x_{k+1})\\&\puntos \\&f(x_{1},x_{2},\puntos,0,x_{k+1})=g(x_{1},x_{ 2},\puntos,0,x_{k+1})\\&f(x_{1},x_{2},\puntos,x_{k},0)=g(x_{1},x_{2 },\puntos,x_{k},0)\end{alineado}}

Sin embargo, de esto se deduce que la diferencia se puede representar en la forma de cualquiera (si no, entonces para algunos la diferencia sería distinta de cero y una de las igualdades indicadas anteriormente no se cumpliría). Por lo tanto, la diferencia se puede representar como , pero esto es imposible porque la potencia total de y es igual a . $fg$ ${\displaystyle h(x_{1},\dots,x_{n})x_{i))$ $i$ ${\displaystyle x_{1},\puntos,x_{i-1},x_{i+1},\puntos,x_{k+1))$ $fg$ ${\displaystyle h(x_{1},\puntos,x_{n})x_{1}x_{2}\puntos x_{k}x_{k+1))$ $F$ $gramo$ $k$

Argumentos similares para dar una transición inductiva y probar identidades para un . ${\ estilo de visualización n> k + 1}$ $norte$

A través de series de potencias formales

Al abrir los paréntesis directamente, se puede obtener que

\prod_{i=1}^{n}(t-x_{i})=\sum_{k=0}^{n}(-1)^{k}e_{k}(x_ {1},\puntos,x_{n})t^{nk}

{\displaystyle \prod_{i=1}^{n}(1-{\frac {x_{i}}{t}})=\sum_{k=0}^{n}(-1)^ {k}e_{k}(x_{1},\puntos,x_{n}){\frac{1}{t^{k))))

Denotando , obtenemos . $s={\frac{1}{t))$ $\prod_{i=1}^{n}(1-x_{i}s)=\sum_{k=0}^{n}(-1)^{k}e_{k}( x_{1},\puntos,x_{n})s^{k}$

Derivando formalmente (tomando una derivada) con respecto a y multiplicando ambas partes por , obtenemos $s$ $s$

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

Dado que la igualdad idéntica de polinomios implica la igualdad de todos los coeficientes, entonces, de acuerdo con las reglas de multiplicación de polinomios, esto implica directamente que

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

A través de la gama telescópica

Que se arreglen algunos . Indicar por la suma de todos los monomios , que consisten en diferentes variables, una de las cuales está incluida en el monomio con grado , y todas las demás, con grado 1. Dichos monomios surgen naturalmente en el producto (las variables con grado "vienen" del polinomio , y el resto incluido en monomio con el primer grado - de ). $k\geq 1$ $r_{i}^{(k)}(x_{1},\puntos,x_{n})$ $k$ $i$ $p_{i}(x_{1},\puntos,x_{n})e_{ki}(x_{1},\puntos,x_{n})$ $i$ $Pi}$ ${\ Displaystyle e_ {ki}}$

Más específicamente, las siguientes identidades se verifican fácilmente:

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

La peculiaridad del primero de ellos se debe, en términos generales, al hecho de que para un monomio es único y claro de qué variable se toma y de cuál , de modo que cada polinomio se incluye en el producto con un coeficiente . En el caso, el polinomio ocurrirá exactamente una vez en el producto - como cada posible multiplicación de una de las variables con el resto del monomio: . Esto da el coeficiente $i\geq 2$ ${\displaystyle x_{0}^{i}x_{1}\puntos x_{ki))$ $Pi}$ ${\ Displaystyle e_ {ki}}$ ${\ Displaystyle p_ {i} e_ {ki}}$ $una$ $yo=1$ ${\displaystyle x_{1},\puntos,x_{k))$ ${\displaystyle p_{1}e_{k-1))$ $k$ $x_{1}x_{2}\puntos x_{k-1}x_{k}=x_{1}\cdot x_{2}x_{3}\puntos 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}$

De las identidades anteriores es fácil obtener que

{\begin{alineado}&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)+\ izquierda({r_{3}^{(k)}+r_{4}^{(k)}}\derecha)-\puntos +(-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)}\puntos +(-1)^{k-1}r_{k}^{(k)}+( -1)^{k}r_{k}^{(k)}=\\&=ke_{k}\\\end{alineado}}

Identidades relacionadas

Representaciones directas de polinomios simétricos elementales mediante sumas de potencias

Expandiendo explícitamente la expresión a través de , obtenemos las representaciones $e_{yo}$ $Pi}$

{\begin{alineado}e_{1}&=p_{1},\\e_{2}&=\textstyle {\frac {1}{2}}p_{1}^{2}-{ \frac {1}{2}}p_{2}&&=\estilo de texto {\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{alineado}}

La fórmula general también se puede reescribir como

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

donde es el polinomio de Bell . Tal representación, en particular, conduce a la siguiente identidad de funciones generadoras: $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}\derecha).

Representación directa de sumas de potencias en términos de polinomios simétricos elementales

De manera similar, al expandir las expresiones de recursión directamente, se puede obtener que

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

Las primeras cuatro fórmulas fueron obtenidas por Albert Girard antes que Newton, en 1629. La fórmula general es la siguiente:

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

Esto se puede reformular en términos de polinomios de Bell:

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

Aplicaciones

Aplicaciones a raíces de polinomios

Un polinomio con raíces se puede representar como $f(x)$ $x_{1},\puntos,x_{n}$

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

donde los coeficientes son los polinomios simétricos definidos anteriormente. Para valores conocidos de sumas de potencias , los coeficientes de un polinomio se pueden encontrar a partir de fórmulas recursivas. $e_{k}=e_{k}(x_{1},\puntos,x_{n})$ $p_{k}(x_{1},\dots,x_{n})=\sum \limits _{i=1}^{n}{{x_{i}}^{k}}$ $f(x)$

Aplicaciones a polinomios característicos de matrices

Las identidades de Newton nos permiten reducir el cálculo de los coeficientes del polinomio característico de una matriz al cálculo de la traza de sus distintas potencias. $A$

Considere el polinomio característico de alguna matriz . Sus raíces son los valores propios de esta matriz (cada raíz se representa con su propia multiplicidad). Entonces los coeficientes del polinomio característico se expresan en términos de polinomios simétricos . $A$ $x_{1},\puntos,x_{n}$ $e_{yo}$

Para todo positivo , los valores propios de la matriz son las potencias de . Como la suma de los valores propios de una matriz es igual a su traza , entonces $k$ $A^{k}$ ${x_{1}}^{k},\puntos,{x_{n}}^{k}$

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

Por lo tanto, y , y los coeficientes del polinomio característico se pueden expresar linealmente a partir de . El cálculo de los coeficientes de un polinomio se reduce así a dos pasos: $e_{1},\puntos,e_{n}$ $tr(A),\dots,tr(A^{n})$

cálculo de potencias matriciales y su traza $A$
solución de un sistema de ecuaciones lineales con matriz triangular

Ambas etapas pertenecen a la clase de complejidad NC , por lo que el problema de encontrar los coeficientes del polinomio característico también pertenece a la clase NC. El algoritmo Fadeev-Leverrier (1840) se basa en esta idea .

Dado que, según el teorema de Hamilton-Cayley, cualquier matriz es la raíz de su polinomio característico, un cálculo rápido de los coeficientes de este polinomio brinda una forma rápida de encontrar la matriz inversa.

Aplicaciones a las sumas trigonométricas

Las identidades de Newton se pueden usar para estimar sumas trigonométricas racionales módulo primo para encontrar de manera única un caso especial de la integral de Vinogradov con un número igual de variables y ecuaciones.

Notas

Tignol, Jean-Pierre. Teoría de las ecuaciones algebraicas de Galois (neopr.) . - Singapur: World Scientific , 2001. - ISBN 978-981-02-4541-2 .
Bergeron, F.; Labelle, G.; Leroux, P. Especies combinatorias y estructuras similares a árboles (inglés) . -Cambridge: Cambridge University Press , 1998. -ISBN 978-0-521-57323-8 .
Cameron, Peter J. Grupos de permutación (indefinidos) . -Cambridge: Cambridge University Press , 1999. -ISBN 978-0-521-65378-7 .
Cox, David; Little, John y O'Shea, Donal. Ideales, Variedades y Algoritmos (indefinido) . - Nueva York: Springer-Verlag , 1992. - ISBN 978-0-387-97847-5 .
Epstein, D.; Goodrich, MT (2007). "Identificación de rezagados eficiente en el espacio en flujos de datos de ida y vuelta a través de identidades de Newton y filtros Bloom invertibles". Algoritmos y Estructuras de Datos, 10º Taller Internacional, WADS 2007 . Springer-Verlag, Lecture Notes in Computer Science 4619. págs. 637-648. arXiv : 0704.3313 . Código Bib : 2007arXiv0704.3313E .
Littlewood, DE La teoría de los caracteres grupales y las representaciones matriciales de los grupos . - Oxford: Oxford University Press , 1950. - P. viii+310. — ISBN 0-8218-4067-3 .
Macdonald, I. G. Funciones simétricas y polinomios de Hall . — Oxford: The Clarendon Press, Oxford University Press, 1979. — P. viii+180. - (Monografías matemáticas de Oxford). — ISBN 0-19-853530-9 .
Macdonald, I. G. Funciones simétricas y polinomios de Hall . - Segundo. — Nueva York: Publicaciones científicas de Oxford. The Clarendon Press, Oxford University Press, 1995. P. x+475. - (Monografías matemáticas de Oxford). — ISBN 0-19-853489-2 .
Mead, Identidades de DG Newton // The American Mathematical Monthly : revista. - Asociación Matemática de América, 1992. - vol. 99 , núm. 8 _ - Pág. 749-751 . -doi : 10.2307/ 2324242 . — .
Stanley, Richard P. Combinatoria enumerativa, vol. 2 (neooperatorio) . - Prensa de la Universidad de Cambridge , 1999. - ISBN 0-521-56069-1 .
Prasolov V. V. Polinomios. - 3ra ed., rev. — M.: MTsNMO, 2003. — 336 p. — ISBN 5-94057-077-1