Identidades de Newton

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido (desde agosto de 2007). Ajude e colabore com a tradução.

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 idéias em geometria algébrica computacional, particularmente bases de Gröbner.

Formulação matemática[editar | editar código-fonte]

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 - 2 a_2
t_3 = a_1 t_2 - a_2 t_1 + 3 a_3
t_4 = a_1 t_3 - a_2 t_2 + a_3 t_1 - 4 a_4
t_5 = a_1 t_4 - a_2 t_3 + a_3 t_2 - a_4 t_1 + 5 a_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 - 2 a_2
t_3 = a_1^3 - 3 a_1 a_2 + 3 a_3
t_4 = a_1^4 - 4 a_1^2 a_2 + 4 a_1 a_3 + 2 a_2^2 - 4 a_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 - 3 t_1 t_2 + 2 t_3 \right)
a_4 = \frac{1}{24} \left( t_1^4 - 6 t_1^2 t_2 + 3 t_2^2 + 8 t_1 t_3 - 6 t_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[editar | editar código-fonte]

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 spaç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[editar | editar código-fonte]

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:

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çao 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 gurpo simétrico a partir da fórmula de Polya.

Relação com combinatória enumerativa[editar | editar código-fonte]

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 particionaro número natural n como uma soma de números naturais,
  • o número de florestas binárias n-nodais,
  • o número de digrafos 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 desevolvimento 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 conhcidos 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 digrafos 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çao indicial atributiva enumerando em termos de algum atributo com valor inteiro.

Relação com a geometria algébrica computacional[editar | editar código-fonte]

A geometria algébrica lida primariamante 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 recuçã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 involvendo 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 uam 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çao 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.

Veja também[editar | editar código-fonte]