Identidades de Newton

Em matemática, as identidades de Newton relacionam duas maneiras diferentes de descrever as raízes de um polinômio. Elas foram descobertas por Isaac Newton em cerca de 1666, aparentemente ignorando um trabalho anterior (1629) de Albert Girard. Estas identidades úteis têm imediatas aplicações em muita áreas da matemática, incluindo a teoria de Galois, teoria dos invariantes, teoria dos grupos, combinatória, bem como outras aplicações além da matemática, incluindo a relatividade geral. Elas podem ser consideradas como aplicações de ideias em geometria algébrica computacional, particularmente bases de Gröbner.

Formulação matemática

Considere o polinômio

$p(\lambda )=\prod _{\alpha =1}^{n}\left(\lambda -x_{\alpha }\right)=\sum _{j=0}^{n}a_{j}\lambda ^{j}$

onde $x_{\alpha }$ são as raízes e $a_{j}$ são os coeficientes. Freqüentemente, este polinômio é tido como o polinômio característico de um operador linear ou matriz; então as raízes são chamadas valor próprios ou autovalores.

Defina as somas de potências

$t_{j}=\sum _{\alpha =1}^{n}x_{\alpha }^{j}$

Se tivermos as raízes como autovalores de uma matriz $A$, então essas grandezas são os traços das potências da matriz

$t_{j}={\rm {tr}}\,\left(A^{j}\right)$.

Então a forma original das identidades de Newton é dada pela recorrência:

$t_{1}=a_{1}$

$t_{2}=a_{1}t_{1}-2a_{2}$

$t_{3}=a_{1}t_{2}-a_{2}t_{1}+3a_{3}$

$t_{4}=a_{1}t_{3}-a_{2}t_{2}+a_{3}t_{1}-4a_{4}$

$t_{5}=a_{1}t_{4}-a_{2}t_{3}+a_{3}t_{2}-a_{4}t_{1}+5a_{5}$

onde o padrão é óbvio. Para uma prova elementar veja o livro de Tygnol citado abaixo.

Destas fórmulas nós podemos obter facilmente fórmulas mais úteis, expressando as somas de potência em termos dos coeficientes:

$t_{1}=a_{1}$

$t_{2}=a_{1}^{2}-2a_{2}$

$t_{3}=a_{1}^{3}-3a_{1}a_{2}+3a_{3}$

$t_{4}=a_{1}^{4}-4a_{1}^{2}a_{2}+4a_{1}a_{3}+2a_{2}^{2}-4a_{4}$

Infelizmente, estas fórmulas têm a desvantagem de que o padrão não é mais óbvio.

Finalmente, pode-se resolvê-las para que se obtenha expressões fornecendo os coeficientes em termos das somas de potências:

$a_{1}=t_{1}$

$a_{2}={\frac {1}{2}}\left(t_{1}^{2}-t_{2}\right)$

$a_{3}={\frac {1}{6}}\left(t_{1}^{3}-3t_{1}t_{2}+2t_{3}\right)$

$a_{4}={\frac {1}{24}}\left(t_{1}^{4}-6t_{1}^{2}t_{2}+3t_{2}^{2}+8t_{1}t_{3}-6t_{4}\right)$

e assim por diante, onde pode-se ver um padrão parcial (fatoriais no denominador, primeiro e último termos), mas novamente o padrão geral provavelmente não é óbvio. Mas se se sabe algo sobre a teoria dos grupos finitos, pode-se olha-las com um olhar diferente (Spoiler em uma secção subseqüente.)

Newton parece ter deixado de lado aqui, tendo portanto omitido algumas descobertas interessantes.

Relação com a teoria dos invariantes

A teoria dos invariantes lida com invariantes polinomiais de vários objetos algébricos ou geométricos em matemática, incluindo invariantes polinomiais de formas quadráticas, e mais geralmente, invariantes polinomiais de tensores. Dos últimos, obtêm-se conexões com a teoria da representação de grupos.

Um tópico fundamental na teoria dos invariantes tem a ver com os polinômios simétricos, que surgem quando expressamos os coeficientes de um polinômio em termos de suas raízes. Ou seja, multiplicando

$p(\lambda )=\prod _{\alpha =1}^{n}\left(\lambda -x_{\alpha }\right)$

tem-se

$\alpha _{1}=-\sum _{j}x_{j}$

$\alpha _{2}=\sum _{j<k}x_{j}\,x_{k}$

$\alpha _{3}=-\sum _{j<k<\ell }x_{j}\,x_{k}\,x_{\ell }$

E assim por diante. Em particular, podem-se usar tais expressões para obter o polinômio característico de um operador linear se se conhecem os seus autovalores.

A conexão com a teoria dos invariantes é que se se considera os $\alpha _{j}(x_{1},x_{2},\dots )$ como sendo os polinômios em suas raízes, então para um dado n eles forma uma bases para o espaço das funções polinomiais simétricas das raízes. Ou seja, todo função polinomial das raízes que é invariante sob quaisquer permutações das raízes, tal como ao trocar $x_{1},x_{2}$, é dada por uma combinação linear específica de $\alpha _{j}$. Por esta razão, $\alpha _{1},\,\alpha _{2},\dots \alpha _{n}$ são chamados os polinômios elementares simétricos.

O ponto é que as expressões acima dão uma base diferente para o espaço dos polinômios simétricos, a saber:

$\tau _{1}=\alpha _{1}$

$\tau _{2}=\alpha _{1}^{2}-2\alpha _{2}$

$\tau _{3}=\alpha _{1}^{3}-3\alpha _{1}\alpha _{2}+3\alpha _{3}$

$\tau _{4}=\alpha _{1}^{4}-4\alpha _{1}^{2}\alpha _{2}+4\alpha _{1}\alpha _{3}+2\alpha _{2}^{2}-4\alpha _{4}$

e assim por diante, onde $\tau _{j}$ é simplesmente a soma das j-ésimas potências das raízes. O fato de se poder obter desta maneira duas formas distintas de representar todas as funções simétricas das raízes de um polinômio, sem se conhecer as próprias raízes, é de fundamental importância para a teoria de Galois.

Pode-se obter decomposições mais "refinadas" ao escrever os polinômios simétricos gerais como somas de polinômios homogêneos; ou seja, um polinômio simétrico no qual todos os termos têm o mesmograu. Uma base conveniente para os polinômios simétricos homogêneos é dada pelos polinômios de Schur, que correspondem às partições de um número inteiro, as quais podem ser enumeradas pelos diagramas de Ferrers (este é o conceito combinatorial "não rotulado" correspondendo aos diagramas de Young). Por exemplo, correspondendo à partição 4+2+1 = 7, tem-seo polinômio de Schur

$\sigma _{4,2,1}(x_{1},x_{2},x_{3})={\frac {\det \left[{\begin{matrix}x_{1}^{6}&x_{2}^{6}&x_{3}^{6}\\x_{1}^{3}&x_{2}^{3}&x_{3}^{3}\\x_{1}&x_{2}&x_{3}\end{matrix}}\right]}{\det \left[{\begin{matrix}x_{1}^{2}&x_{2}^{2}&x_{3}^{2}\\x_{1}&x_{2}&x_{3}\\1&1&1\end{matrix}}\right]}}$

que é um polinômio homogêneo simétrico de grau sete em três variáveis. Surpreendentemente, o determinante no denominador cancela-se quando tudo é totalmente expandido:

$\sigma _{4,2,1}(x_{1},x_{2},x_{3})=x_{1}\,x_{2}\,x_{3}\;\left(x_{1}^{3}\,x_{2}+x_{1}\,x_{2}^{3}+x_{1}^{3}\,x_{3}+x_{1}\,x_{3}^{3}+x_{2}^{3}\,x_{3}+x_{2}\,x_{3}^{3}\right.$

$\;\;\;\left.+x_{1}^{2}\,x_{2}^{2}+x_{1}^{2}\,x_{3}^{2}+x_{2}^{2}\,x_{3}^{2}+2\,(x_{1}^{2}\,x_{2}\,x_{3}+x_{1}\,x_{2}^{2}\,x_{3}+x_{1}\,x_{2}\,x_{3}^{2})\right)$

Há três outras partições de sete me três partes, de tal forma que o espaço de polinômios homogêneos de grau sete em três variáveis tem dimensão quatro, com cada polinômio unicamente expressável como uma combinação linear de quatro polinômios de Schur. Cada um destes polinômios de Schur pode ser expresso por sua vez como uma combinação algébrica dos (um função polinomial dos) três polinômios simétricos elementares em três variáveis, $\alpha _{1},\,\alpha _{2},\,\alpha _{3}$.

Relação com grupos simétricos

O leitor atento com algum conhecimento da teoria dos grupos finitos, particularmente da fórmula da enumeração de Pólya, deve ter notado dois fatos notáveis na discussão acima:

• Os polinômios de Schur são definidos em termos departições inteiras (ou diagramas de Ferrers), os quais correspondem às classes de conjugação do grupo simétrico,
• a menos de sinais alternantes, as expressões achadas acima fornecendo os coeficientes em termos das somas de potências são exatamente polinômios de índices cíclicosdos grupos simétricos.

Desnecessário é dizer que isto não é coincidência! Joseph Lagrange (e, com uma pequena explicação prévia, Isaac Newton) teria entendido imediatamente a afirmação do seguinte teorema, o qual foi descoberto por George Polya nos anos de 1930:

Defina a função característica

$F(u,t_{1},t_{2},\dots )=\prod _{\alpha }\left(u-x_{\alpha }\right)=\sum _{n=0}^{\infty }a_{n}u^{n}$

onde $x_{\alpha }$ são símbolos os quais podem ser pensados como "raízes" formais da função característica, que por sua vez pode ser pensada como a função geratriz para os coeficientes $a_{j}$. Defina também as somas alternantes de potências

$t_{j}=(-1)^{j+1}\,\sum _{\alpha }x_{\alpha }^{j}$

(Os sinais alternantes surgem do fato de que transposições ou ciclos duais são permutações ímpares , ciclos ternários são permutações pares, e assim por diante). Então, a função característica é dada por

$F(u,t_{1},t_{2},\dots )=\exp \left(\sum _{m=1}^{\infty }{\frac {t_{m}}{m}}\,u^{m}\right)$

Se se expandir o segundo membro (membro direito) como os primeiros termos de uma séries de Taylor na variável u (será preciso somente escrever os primeiros poucos termos no expoente), obter-se-ão os polinômios de índices cíclicos dos primeiros grupos simétricos! E, a menos de sinais alternantes, estes concordam com as expressões achadas antes dando os coeficientes do polinômio característico de um operador linear em termos dos traços das potências do operador. Tomando-se suficientemente muitos termos na série de potências, pode-se eficientemente obter os índices cíclicos de qualquer grupo simétrico a partir da fórmula de Polya.

Relação com combinatória enumerativa

A combinatória enumerativa lida com a contagem de objetos, usualmente objetos definidos por algum tipo de construção recursiva. Exemplos:

• o número de maneiras de se particionar o número natural n como uma soma de números naturais,
• o número de florestas binárias n-nodais,
• o número de dígrafos esparsos, os quais são digrafos n-nodais, tendo uma ou duas arestas para cada nó.

Em cada um destes exemplos, a resposta ao problema de contagem é uma função particular do número natural n, tomando valores nos números naturais. Quase invariavelmente, o maneira mais elegante de resolver tais problemas é o uso da técnica de funções geratrizes que foram introduzidas pelo infatigável Leonhard Euler.

Em anos mais recentes, com o desenvolvimento da teoria das categorias, um modo altamente abstrato de pensar sobre funções geratrizes tem sido introduzido por Andre Joyal, no qual a generalização dos polinômios de índices cíclicos de Polya tem diso introduzida. Estas funções indiciais de Joyal são definidas em termos de estructores (também conhecidos como espécies combinatoriais). Estes são certos funtores os quais elegante e precisamente expressam a noção combinatorial de uma construção recursiva. As funções indiciais de Joyal são de fato uma generalização natural da função indicial de Pólya ao grupo oligomórfico, um tipo de grupo de permutação infinito tratável. Este por sua vez conduz a uma bela conexão com a lógica de primeira ordem.

Freqüentemente tem-se um problema próximo relacionado com os problemas de contagem acima mencionados, a saber, contando

• o número de árvores binárias (florests conectadas),
• o número de dígrafos esparsos conectados.

Também, pode-se querer resolver problemas de contagem mais precisos , tais como contar:

• o número de maneiras de se particionar um número natural como soma de k números naturais,
• o número de florestas n-nodais binárias contendo k árvores.

Verifica-se que tais problemas são relacionados aos problemas originais por fórmulas que se assemelham á fórmula de Pólya dada na secção prévia. Informação máxima é obtida quando se pode achar o índice de Joyal do estructor conectado obtido de uma estrutura mais complicada, ou quando se pode obter uma função indicial atributiva enumerando em termos de algum atributo com valor inteiro.

Relação com a geometria algébrica computacional

A geometria algébrica lida primariamente com o problema algébrico de acharem-se as raízes de um sistema de polinômios em muitas varáveis e a interpretação geométrica deste problema em termos de variedades algébricas. Uma técnica computacional fundamental para a geometria algébrica, que tem implicações de longo alcance em muitos outros campos da matemática, incluindo as equações diferenciais, é a noção de uma base de Gröbner. Para os propósitos deste artigo não se necessita saber precisamente o que são, necessita-se somente saber que o algoritmo de Buchberger para se obter uma base de Gröbner generaliza dois dos mais fundamentais algoritmos em matemática:

• o Algoritmo de Gauss para o obtenção da Redução de linha (row reduction em Inglês) de uma matriz,
• o algoritmo da divisão para se dividir um polinômio em uma variável por outro de mesma forma

A base de Gröbner resultante de um ideal em um anel de polinômios em muitas variáveis é análogo a uma base vetorial para um subespaço de um espaço vetorial, e é apropriado (pelo menos idealmente) para computações envolvendo ideais em anéis polinomiais, os quais são os conceitos de base da geometria algébrica. De fato, o famoso Nullstellensatz de David Hilbert estabelece uma correspondência perfeita entre um conceito algébrico fundamental - os ideais de um tipo preciso tipo de anel - e um igualmente fundamental conceito geométrico - as variedades em um espaço afim, ou mesmo em um espaço projetivo.

As bases de Gröbner são definidas com respeito à escolha de um certo ordenamento de termos (o qual especifica "prioridades" entre monômios ao se levar a cabo o algoritmo de divisão generalizada), e uma das escolhas mais úteis para a geometria algébrica é a ordem de eliminação. Em particular, usando-se uma ordem de eliminação pode-se resolver um sistema de equações tais que as identidades resultando nas somas de potências em termos dos coeficientes, para obterem-se as equações que fornecem os coeficientes em termos das sumas de potências. Desnecessário é dizer que se obtém as expressões obtidas acima.

Ver também

• Polinômio simétrico elementar
• Polinômio de Schur