cdfi是什么意思

百度 　　作为本届活动的公益大使，好声音著名歌手吉克隽逸不仅参与了公益宣传片的拍摄，更在庆典现场与大家分享了自己的环保心得，并以一曲《带我到山顶》为现场观众带来一份绿意。

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 importancia 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