Arquivo da tag: Álgebra

5 sextas, 5 sábados, 5 domingos

Rookie

Chega.

Já chega.

Por favor, chega de enviar correntes de e-mails me dizendo que Janeiro terá cinco sextas, cinco sábados e cinco domingos. Já não consigo mais receber essas mensagens sem espumar de raiva, por diversos motivos, e tomo meu tempo para escrever esse post, um pouco fora do tema desse blog, para dissertar sobre um de meus combates épicos: o spam mal feito.

Tenho vários combates, todos perfeitamente justificados. Coxinha comida pelo lado errado, e-mail escrito em azul (ou qualquer outra cor além de preto), e-mails @hotmail, gente que vai “guardar mesa” enquanto outra pessoa está na fila, spoilers na internet, gente que conta o final da piada quando eu estou perto de terminar de contar, mensagens-imagens de “boa quinta-feira” no grupo de WhatsApp da família, astrologia, Windows Vista, café solúvel, francês que deseja “bonne année!” em fevereiro, teclados com switch de borracha, notebooks da HP, tomada de três pinos (sou clichê assim), texto “científico” escrito em Word, gente que critica arte moderna dizendo que “fazia pintura mais bonita quando tinha cinco anos”, emissora de televisão que acha que perguntar para gente aleatória na rua o que eles acharam daquilo configura “jornalismo”, qualquer uso de caps lock que não seja para siglas; todos esses eventos são bandeiras que carrego com mais ou menos intensidade. Poucos deles, no entanto, provocam em mim meus instintos mais primitivos quanto spam mal feito, mal pesquisado, mal compartilhado.

E o e-mail das cinco sextas, sábados e domingos é um exemplo primoroso dessa ojeriza que me é evocada. Sim, janeiro 2016 é um mês com essas características, mas isso não é surpreendente ou impressionante porque não só é um evento comum, mas acontece pela simples passagem do tempo que, por definição, é a coisa mais previsível que existe. Podemos fazer uma conta rápida para estimar a frequência com que isso acontece. Para que um mês possua cinco desses dias, basta que comece em uma sexta-feira e tenha 31 dias. As chances de um mês aleatório começar em uma sexta, pela isotropia da semana, são $\frac{1}{7}$. São sete meses no ano com 31 dias (usando os ossos da mão para contar fica fácil), então a chance de um mês ter essas duas características é $\frac{1}{7}\times\frac{7}{12}=\frac{1}{12}$.

Esse evento acontece, em média, uma vez por ano, não uma vez a cada 823 anos, de onde tiraram esse número?! Ele nem funciona! Janeiro de 2839 não terá cinco sexta, cinco sábados e cinco domingos! O primeiro dia de janeiro de 2839 é um sábado, não uma sexta. Se você quer repetição, um número desses seria formado com o produto da duração de todos os ciclos envolvidos nessa repetição. Por exemplo, a semana tem sete dias e ano bissexto acontece uma vez a cada quatro anos, então tenho certeza de que o mês de janeiro de daqui a $4\times 7=28$ anos terá também cinco sextas, cinco sábados e cinco domingos. Isso não funciona sempre porque ano bissexto tem problemas quando o ano é múltiplo de 100 e 400, o que me forçaria a multiplicar por coisa demais, mas isso é um jeito de garantir a periodicidade e é conhecido como teorema de Lagrange. Se você começar uma atividade no domingo e repeti-la de dois em dois dias, depois de sete repetições você voltará a fazê-la no domingo. Se repetir de três em três dias, de quatro em quatro dias, de cinco em cinco dias, não importa; depois de sete repetições você estará sempre no domingo, com certeza absoluta.

O número correto de anos seria um número formado do produto de diversos outros números, cada um correspondente à duração dos ciclos envolvidos nessa periodicidade (semana, ano bissexto). Mas 823 não é apenas o número errado, ele é primo! E não é tão fácil chutar um primo tão alto assim, então parabéns aos criadores do spam, eles conseguiram, por azar, escolher um dos números mais errados possíveis, se existe uma gradação de errado para esse problema.

E o compartilhamento desse spam me causa tanto desgosto porque uma simples volta ao calendário poderia resolver o problema. Esse mesmo evento aconteceu em maio do ano passado, meu aniversário foi em um desses “sábados sagrados dos chineses”. E o que chineses têm a ver com isso? Eles nem usavam o calendário gregoriano!

Por fim, me acalmo. Sei que o combate é vão, que spam são meus gigantes em moinhos de vento, bem como e-mail em azul e a tomada de três pinos, não vencerei. Fica esse desabafo, e esse comentário sobre essa interessante propriedade de repetição de teoria dos grupos. Sei que esse post é inútil, a intersecção de leitores desse blog com quem compartilha esse tipo de abominação é perto de zero, meu alcance é baixo, meu poder evangelístico de apresentar as boas novas de pegar o calendário deste ano e verificar que a mesma coisa acontecerá em julho é pequeno.

5 respostas

Correlações e matrizes I

Rookie

Muitos pediram para que eu dedicasse um post à técnica que usei no estudo de correlação dos votos dos políticos nos últimos posts. Gostei das análises e confio em minhas conclusões, mas isso aqui é ciência, meus métodos precisam estar claros para que eu ganhe credibilidade. Pretendo ainda explorar a montanha de dados que tenho das votações dos deputados, mas, como meu computador foi furtado e com ele foram os scripts de análise que tinha feito, mando um post intermediário sobre a técnica antes de continuar com mais resultados. Este post será um pouco árido, mas peço paciência, o assunto é fascinante e as aplicações são imensas em todas as áreas da ciência ou da análise de dados. Seguindo este roteiro, você pode encontrar correlações entre quaisquer duas variáveis em sua pesquisa, em sua empresa, em sua sala de aula.

Vou começar tratando um problema diferente, na área da pedagogia. Eu tenho as notas de física e matemática de dez alunos: Alice, Bruno, Carolina, Daphny, Eduardo, Frederico, Gabriela, Hugo, Igor e Jonas, que serão referidos apenas por sua letra inicial:

Aluno: A B C D E F G H I J
Fís 5,0 8,0 10,0 2,0 4,5 9,0 6,0 3,0 9,0 8,0
Mat 6,0 7,0 9,5 0,0 4,5 7,0 4,5 2,5 8,0 8,0

Quando eu me pergunto se há alguma correlação entre física e matemática, quero saber, sabendo a nota de um aluno em física, se consigo dar um bom chute de qual será sua nota de matemática. Essa tabela não ajuda muito, melhor seria se eu visualizasse meus alunos como os pontos em um gráfico:

correlacao_1Com o gráfico é mais fácil ver que parece haver uma forte correlação positiva entre física e matemática. Se um aluno é bom em matemática, esses pontos me dizem que é um bom chute dizer que ele também é bom em física. Como queremos um método decente de dizer isso, medimos a chamada correlação entre duas matérias. Há diversas maneiras de definir correlação, sendo a correlação de Pearson o exemplo mais clássico de medida de correlação. Intuitivamente, queremos que essa correlação seja alta quando as notas de física e matemática andam juntas, que seja perto de zero se as variáveis parecem independentes e que seja muito negativa se ter nota em física parece atrapalhar a nota em matemática.

Precisamos matematizar isso de uma maneira coerente. Quando um aluno tirar nota baixa nas duas matérias, quero que a correlação entre as matérias aumente, e também quero que ela aumente quando um aluno tirar nota alta nas duas. A correlação deve diminuir quando um aluno tirar nota alta em uma e baixa em outra. Mas qual seria a melhor definição de alta ou baixa? Por justiça e senso comum, uso a média da sala como parâmetro, e defino nota alta e baixa como acima ou abaixo da média. Para que as coisas fiquem bem claras, eu subtraio a média de cada nota e terei o novo gráfico:

correlacao_2E aqui já percebemos que a correlação entre essas matérias certamente é positiva. Notamos que pontos nos quadrantes 1 e 3 (positivo-positivo e negativo-negativo) são pontos que contribuem com a correlação entre as matérias, enquanto pontos nos quadrantes 2 e 4 diminuem essa correlação. Como tenho apenas um ponto no quarto quadrante, e ele está quase na fronteira, é fácil admitir que a correlação é positiva entre as matérias. Contudo, ver não é o suficiente, quero um número para essa correlação.

O que a correlação de Pearson diz é que cada aluno contribuirá com a correlação com um valor de acordo com o produto de suas notas. Essa noção é boa, pois menos vezes menos dá mais, então pontos nos quadrantes um e três contribuirão para aumentar a correlação e pontos nos quadrantes dois e quatro diminuirão esse valor. É importante notar também que, nessa métrica, pontos mais distantes da média contribuem mais com a correlação que pontos próximos. Isso é razoável, pois um ponto próximo da média nas duas matérias poderia estar em qualquer quadrante com pouco esforço, enquanto trazer o ponto D, o mais extremo à esquerda, a outro quadrante exigiria muita aula particular.

Antes de calcular esse valor, precisamos sanar outro problema. Se esse estudo fosse feito na França, as notas iriam de 0 a 20, pois usar base 10 nesse país é démodé. Esses dados teriam uma flutuação maior e as correlações calculadas seriam diferentes, ainda que a proporção entre eles fosse a mesma. Ainda que eu subtraia a média, os valores deixariam de flutuar entre -6 e 6 para flutuarem entre -12 e 12, o que tornaria multiplicações entre eles maiores e a correlação maior. Se a distância em relação à média de algum aluno fosse 5 em matemática e 4,5 em física, a contribuição na correlação seria 22,5 no Brasil; na França, seria quatro-vintes e dez! Não é porque eu mudo a escala que a correlação aumenta, uma análise da correlação de altura e peso da população não pode depender do uso de centímetros ou polegadas ((Contudo, estudar em polegadas é moralmente errado.)) .

O ideal seria dividir os valores por algo que leve em conta a dispersão deles, e um excelente candidato é o chamado desvio padrão. Essa grandeza nada mais é que a raiz da média dos quadrados dos elementos. Se as notas de física são 3, 5, 8 e 10, eu primeiro subtraio de todos a média, que é  6,5, tendo como notas -3,5, -1,5, 1,5 e 3,5. O desvio padrão será

\[\sqrt{\frac{(-3,5)^2+(-1,5)^2+1,5^2+3,5^2}{4}}=2.89.\]

Uma interpretação possível do desvio padrão é o quão longe da média os dados estão. Em nosso caso, parece bem razoável dizer que os dados estão a uma distância de 2.89 da média; mas note que ele coincidir com os valores mais distantes é uma coincidência do exemplo. Esse desvio padrão das notas, que denotaremos por $\sigma_F$ e $\sigma_M$ para física e matemática, é a quantidade que queremos para deixar as notas comparáveis. Assim, a correlação entre duas matérias é calculada somando o produto de cada par de notas e dividindo pelos desvios-padrão de cada matéria, ou seja:

\[\text{Corr }=\frac{F_1M_1+F_2M_2+\cdots+F_{10}M_{10}}{\sigma_F\sigma_M},\]

onde $F_1$ é a nota de física de um aluno e $M_1$ é sua nota de matemática. É importante notar que nessa definição a correlação máxima entre dois pontos é 1 e a mínima é -1, o que nos permite comparar correlações de objetos completamente diferentes usando a mesma escala. Isso é resultado da subtração da média e divisão pelo desvio-padrão, ferramentas que nos permitem equiparar grandezas completamente diferentes e analisá-las com o mesmo termômetro e mesma régua.

Calculando finalmente a correlação entre física e matemática, encontramos o valor 0,94. Ele é, como esperado, extremamente alto, já que o valor máximo é 1, o que mostra que notas de física e matemática, entre nossos alunos, estão profundamente correlacionadas. Em um chute ingênuo, mas honesto, com esses dados, é possível dizer que alunos bons em uma matéria são bons em outra, enquanto os que não sabem matemática também não parecem saber física.

Isso é esperado, porque, como o gráfico mostra, as notas estão praticamente alinhadas. Com esse método, temos um número, uma medida, para dizer o quão alinhadas elas estão. Notas perfeitamente alinhadas nos dariam correlação 1.

Atravessei todas essas definições com carinho para que fique claro o que é aquela matriz colorida dos deputados e senadores. Cada elemento é a correlação entre dois deputados, eles são o equivalente às matérias no meu exemplo. As notas dos alunos, no caso dos deputados, são as decisões que eles tomaram em uma votação, sendo 1 para SIM, -1 para NÃO e 0 para abstenção. A matriz funciona como um jogo de batalha naval, o senador da linha $i$ terá uma correlação com o senador da coluna $j$ representada pelo número no quadrado $(i,j)$ da matriz, sendo esses números de -1 a 1.

Claro que em outras circunstâncias eu teria mais cuidado para dizer que 0,94 é uma correlação grande, pois uma objeção razoável a esse tratamento todo é: quão grande é grande? A partir de 0,8? 0,7? Ainda que em um estudo menos formal você possa tomar o critério que mais lhe pareça razoável, como, por exemplo, dizer que 0,8 é o limite, é intelectualmente mais honesto comparar mais grandezas (em nosso caso, mais matérias) e afirmar que matemática e física, por exemplo, possuem mais correlação que matemática e português, se no caso as notas de matemática e português possuírem uma menor correlação.

No próximo post disserto um pouco sobre como ordenei a matriz e sobre como essa ordenação revela a estrutura de blocos e nos traz informações que, na frieza das tabelas, não são evidentes. Todo esse processo que descrevi pode ser automatizado com tranquilidade em qualquer software de tratamento de planilhas, cujo principal expoente é o Microsoft Excel. Tenho certeza de que na área de funções estatísticas há uma que calcula a correlação de Pierson de duas grandezas, mas entender de onde ela ver e o que ela significa é muito mais importante que calcular 0,94.

7 respostas

O princípio do pombal

Rookie

Em física e matemática, é bem comum encontrarmos princípios que parecem óbvios com consequências complicadas. Meu exemplo favorito é a relação conhecida como equação mestra na física estatística que, se lida em português, seria: “o quanto variou é o quanto entrou menos o quanto saiu”. Por mais evidente que isso seja, essa equação toma formas cabulosas em situações não muito complicadas e exige bastante suor para ser resolvida.

Mas o assunto de hoje não é a equação mestra, mas outro princípio, talvez ainda mais simples: o princípio da casa dos pombos, ou princípio do pombal.

Princípio da casa dos pombos: se há mais pombos que casas em um pombal, alguma casa terá mais de um pombo.

Eis uma aplicação desse princípio:

E por mais óbvio que ele pareça, não é nada inútil se lembrar dele como técnica de demonstração de resultados bem interessantes. Um deles, meu favorito, é uma espécie de jogo com sequências. Para ilustrar, imagine uma rua com $n$ casas. Cada casa deve possuir um número, e você pode escolher o número que quiser. Eu afirmo que existe um grupo de casas vizinhas cujos números, somados, resultam em um múltiplo de $n$.

Vejamos um exemplo. Imagine treze casas que possuem os seguintes números: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 e 14. Se houvesse uma casa com o número 13, ela seria sozinha o múltiplo de 13 que quero, isso não me serve de muita coisa. Note que, nessa rua, temos os vizinhos 5, 6, 7 e 8, e 5+6+7+8=26, que é um múltiplo de 13.

Mas podemos pegar sequências mais complicadas, como, por exemplo, um antigo telefone meu: 41921561. Eu tenho certeza absoluta de que existem números vizinhos que, somados, resultam em um múltiplo de oito (que é o tamanho da sequência). Basta caçar um pouco para encontrar que 4+1+9+2=16.

Ou, ainda, tomemos essa permutação de meu RG: 158313734. Cacemos os vizinhos que somados dão um múltiplo de nove, e uma leve busca nos leva a 5+8+3+1+3+7=27. Você certamente pode encontrar combinações mais simples, eu não disse que era única, apenas que existe.

Esse resultado, que é um divertido jogo quando se está profundamente entediado em uma sala de espera ou durante uma viagem de trem, é provado com o princípio do pombal. Para tal, tome sua sequência de tamanho $n$, da forma $a_1,a_2,\ldots a_n$. Pense agora em todas as possíveis sequências com a mesma ordem dessa sua original que começam no $a_1$, ou seja, as sequências:

\[a_1\]

\[a_1,a_2\]

\[a_1,a_2,a_3\]

E assim por diante. Pense agora na soma dos elementos delas. Se alguma dessas somas já dá um múltiplo de $n$, nosso problema está resolvido, então vamos supor o pior dos casos, nenhuma delas é um múltiplo de $n$. Assim, a soma dessas sequências, dividida por $n$, deve dar algum resto, e haverá $n-1$ possibilidades de resto.

Ainda em um exemplo, se minha sequência possuísse quatro elementos, as somas dessas subsequências teriam que ter resto ou 1, ou 2, ou 3. Se o resto fosse zero, seria divisível.

Como você tem $n$ sequências possíveis e apenas $n-1$ restos possíveis, então, pelo princípio do pombal, terá, necessariamente, duas sequências diferentes cuja soma tem o mesmo resto na divisão por $n$. Ora, subtraia uma da outra que você terá uma sequência de vizinhos cuja soma, dividida por $n$, possui resto zero, logo, é divisível!

Para entender melhor, vou aplicar esse raciocínio a uma sequência específica: 1 2 1 3 6. As subsequências possíveis são 1, 1 2, 1 2 1, 1 2 1 3 e 1 2 1 3 6. Suas somas serão, respectivamente, 1, 3, 4, 7 e 13. Note que, dividindo por 5, esses números produzem respectivamente resto 1, 3, 4, 2 e 3. A segunda e a última sequência possuem o mesmo resto! Então tirando a segunda da última teremos os elementos 1 3 6 que, somados, dão 10, um múltiplo de 5.

Não sei se ficou claro, na verdade, acho que ficou confuso, mas vou deixar assim enquanto não encontro maneira melhor de escrever. Provar o princípio do pombal, no entanto, me parece mais difícil que esse resultado que acabei de enunciar, talvez usando algum resultado dessa parte mais fundamental de teoria dos conjuntos, propriedades com bijeções, injeções e sobrejeções, a noção de cardinalidade, teria que pensar um pouco. Por enquanto, fica o resultado das sequências, das casas, e a demonstração dos pombos.

2 respostas

O corolário do relógio cruel

Geek

Hoje falamos de álgebra, mas não aquela álgebra linear, coisa séria, de gente grande. Comento com vocês um resultado interessante e bonito da teoria de grupos, chamado teorema de Lagrange. E antes de enunciá-lo, apresento seus elementos, vamos conversar sobre o que é um grupo.

A definição formal não é difícil, mas prefiro definir com palavras a símbolos. Um grupo é um conjunto de elementos que podem ser “somados”, não importando muito o que essa ideia de soma seja. É importante que haja um elemento do conjunto “eleito” como o elemento neutro, aquele que, somado a qualquer um, não afeta esse qualquer um. Na soma convencional, ele é o zero. Na multiplicação, ele é um 1. Nas multiplicação de matrizes, é a identidade. Também é importante que você, tendo somado um elemento, sejá capaz de “subtrai-lo”, ou seja, realizar a operação inversa. Na soma tradicional, o inverso de $a$ é $-a$, na multiplicação, é $1/a$. Nas matrizes, teremos a matriz inversa, o que nos prova que as matrizes não formam um grupo na multiplicação delas. Por fim, queremos que o conjunto seja fechado, ou seja, é impossível, com somas de gente do conjunto, obter alguém de fora dele.

Exemplos de grupos são fáceis de se encontrar: os inteiros com a operação soma, os reais sem o zero com a operação vezes, o conjunto de matrizes quadradas inversíveis de ordem n e os conjuntos de restos de divisão. Esse último merece alguma atenção, pois não só tem aplicações interessantes como é crucial em algumas áreas dessa matéria.

Ao fazer uma divisão por, digamos, 5, temos cinco opções como resto, 0, 1, 2, 3 e 4. Se um número dividido por 5 deixa resto 3 e outro número deixa resto 3, a soma deles deixará resto 1, essa será a regra de nosso grupo “resto de 5”, denotado $\mathbb{Z}/5\mathbb{Z}$. É como se você somasse números normalmente e, a cada vez que eles passam 5, você tira 5 do número. Nesse grupo, 1+1=2, 2+2=4 e 3+3=1. É fácil ver que todos possuem inverso, sendo, por exemplo, o inverso de 3 o número 2, o inverso de 4 o número 1 e assim por diante. Em particular, ele é um grupo finito, e por isso gosto dele. Neste post, vou falar apenas de grupos finitos, eles já atingem uma complexidade suficiente para deixar qualquer matemático feliz.

Se você acha o grupo descrito acima artificial, veja seu relógio. Ele é o grupo $\mathbb{Z}/24\mathbb{Z}$, pois 3+3=6, 6+6=12, mas 12+12=0, somar doze horas ao meio-dia não é ir à hora vinte e quatro, é voltar à meia-noite, hora zero.

E se falamos de grupos, podemos falar de subgrupos. Algum subconjunto de nosso grupo pode ser, em si só, um grupo. No caso do relógio, os elementos 0, 3, 6, 9, 12, 15, 18 e 21 formam um subgrupo. Eles herdam a operação do grupo original e operados entre si continuam entre si, não há como você, somando esses horários, atingir um horário que não esteja nessa lista. O grupo total possui 24 elementos, e esse subgrupo possui 8 elementos. E o que o teorema de Lagrange nos diz é isso:

Teorema (de Lagrange): O número de elementos de um subgrupo de um grupo finito é sempre um divisor do número total de elementos do grupo.

No nosso caso, teremos que 8 é um divisor de 24. Como consequência, podemos perceber que todo grupo que possui um número primo de elementos não possui subgrupo que não seja ou ele mesmo, ou um subgrupo composto apenas pela identidade. Por mais elaborada que seja a construção de seu grupo, se ele possui 11 elementos, não possui nenhum subconjunto que em si seja um grupo, e esse é um resultado bem divertido.

A prova desse teorema não é tão trivial para quem começou agora a ver grupos, então dou apenas uma ideia da demonstração. Se $G$ é um grupo finito e $H \subset G$ é também um grupo com a mesma operação, logo é um subgrupo, então vamos chamar os elementos de $H$ de $h, h_2, h_3\ldots$. Se $H=G$, o teorema está provado para esse caso, então vamos supor que $H \neq G$, tomemos um $g\in G$ que não está em $H$. Note que se $g\not\in H$, então a operação de $g$ com qualquer elemento de $H$ também não está em $H$. Por quê?

Sabemos que $H$ é um grupo, então todos lá possuem inverso. Se $gh_i = h_j$, poderíamos operar os dois lados da equação com $h_i^{-1}$ pela direita e obter $g = h_jh_i^{-1}$. Se escrevemos $g$ como uma composição de elementos de $H$, ele tem que estar em $H$, o que é absurdo por hipótese.

Intuitivamente, a ideia é pensar em $G$ como um cilindro e $H$ como um disco desse cilindro, como essa figura mostra:

O subgrupo $H$ gera, para cada elemento que não pertence a si, todo um anel novo de elementos, apesar de eu hesitar em chamar isso de anel porque, em álgebra, esse nome já é usado para outra coisa, então prefiro chamar de círculo. Ora, dá pra perceber que todo elemento de $G$ pertencerá ou a $H$ ou a um desses círculos formados por $H$. Todos os círculos possuem a mesma quantidade de elementos (pois se $gh_i = gh_j$, podemos cortar $g$ dos dois lados e provar que $h_i = h_j$), logo, o número total de elementos de $G$ deve ser um múltiplo do número de elementos de $H$.

Esse teorema é um jeito de interessante de entender a razão de nossas horas serem contadas em 12 ou 24, esses números possuem muitos divisores! Como se houvesse um corolário do relógio cruel: não são feitos relógios com um número primo de horas, como, por exemplo, esse relógio cruel:

Nesse caso, nenhuma hora inteira seria sensata para se prescrever um medicamento, pois todas elas atravessariam todo o relógio antes de voltar para a mesma hora. Em outras palavras, percorrer este relógio de duas em duas, três em três ou quatro de quatro horas atravessará todo o relógio antes de repetir a primeira hora, pois o número de elementos de qualquer subgrupo deve ser um divisor do número de elementos do grupo. Isso faria o paciente acordar em todas as horas inteiras que deveria estar dormindo, e o mesmo aconteceria se, em nossos relógios, um médico receitasse um comprimido de sete em sete horas. Pode parecer uma aplicação estúpida, mas não é; o fato de nossa divisão do dia em vinte e quatro horas tem como razão histórica a grande quantidade de divisores que possui.

Você certamente pode chegar a essa mesma conclusão usando propriedades elementares de MMC e MDC, mas essa visão, mais abrangente dos grupos finitos, é capaz de nos levar a abstrações mais profundas e a grupos mais complexos, alguns nem numéricos, mas este resultado ainda vale. Muita coisa é grupo, e, em todos os finitos, vale o teorema de Lagrange.

2 respostas

O teorema de Szemerédi

Geek

Esses dias, saiu o resultado do prêmio Abel 2012! Se a matemática tivesse um Nobel, seria o prêmio Abel. Em muitos sentidos, ele me parece mais justo que a medalha Fields, que é atribuída apenas a matemáticos cuja idade é menor que 40 anos e, dessa forma, ignora avanços matemáticos dos mais experientes. Muitos vão dizer que matemático bom é matemático novo, gosto de lembrar que Weierstrass demonstrou o teorema que leva seu nome quando já passava dos 70, mas esse debate vai longe.

E o ganhador foi Endre Szemerédi, um matemático que trabalha na área de combinatória extrema. É uma área de demonstrações elementares e complicadas, e com elementar eu quero dizer “que não se apoia em resultados sofisticados”, ou seja, bastante coisa é demonstrada na raça e todas as provas acabam saindo bem elaboradas. Caracterizar a área é mais fácil com exemplos, e o melhor deles é o próprio teorema de Szemerédi, cujo tipo de pergunta que ele se dispõe a responder é: dados todos os números de 1 a 10.000, quantas números eu posso escolher antes de, com eles, poder formar uma progressão aritmética de tamanho $k$?

E essa pergunta não é fácil, pois a escolha de uma trinca pode atrapalhar a escolha de outras. Para entender a pergunta com mais cuidado, é mais fácil pensar em um jogo. Eu tomo os números de 1 a 100, por exemplo, e você pode ir escolhendo números. O desafio é: quantos você consegue escolher antes de, com os que você escolheu, formar uma P.A. de três elementos? Digamos que você escolha o 1 e o 2, já não pode escolher o três. Se escolher o 4 e o 6, não pode mais escolher o 8, e assim por diante. Esse tipo de problema, da classe de combinatória extrema, é tratado pelo teorema de Szemerédi.

Ele não te conta quantas exatamente você pode formar, ele vai além, com um resultado bonitinho. Se você está interessado em não formar progressões aritméticas de tamanho $k$ (no exemplo do jogo $k=3$), e deve tomar números de 1 a $n$ (que no exemplo foi 10.000, depois 100), eis o que o teorema de Szemerédi vai te contar: dado o jogo descrito acima, com você querendo evitar progressões aritméticas de tamanho $k$, eu sempre posso escolher um $n$ suficientemente grande para que você, ainda que seja o melhor jogador do mundo nisso, não possa escolher mais que 1%, ou 0,1% dos números disponíveis, ou 0,001%, eu posso, aumentando o $n$, estabelecer uma porcentagem tão pequena quanto eu quiser dos números disponíveis para você escolher.

Pensando um pouco, quanto maior for o intervalo de números possíveis, maior é o número de razões possíveis para a P.A., mas esse resultado não é intuitivo e é, aliás, bem divertido, eu posso tomar um $n$ tão grande a ponto de deixar uma fração de $10^{-23}$ desses números possível de ser escolhida, mesmo que você use a melhor tática possível de escolha de números.

Falar em aplicações desse teorema é algo um pouco mais complicado, deixo para esse belo texto a respeito. Mais interessante que isso é tentar olhar de relance as engrenagens da demonstração, que é uma das mais sofisticadas que já vi. Enquanto muitos teoremas matemáticos possuem uma “linha direta” de demonstração (exemplo: cobre com abertos, tira uma subcobertura finita, prova que existe uma bola aberta centrada no ponto que não toca na cobertura, e você provou que todo espaço métrico compacto é fechado), o teorema de Szemerédi precisa de um diagrama para você entender o caminho que ele fez e, somente esse diagrama, já parece a penúltima fase do Metroid de Super Nintendo.

Você começa dos primeiros fatos (F’s), atravessa os lemas (L’s) e vai provando flecha por flecha até reunir ferramentas o suficiente para provar o T, o teorema de Szemerédi. Essa demonstração ganhou um espaço no meu coração apenas pelo pequeno carrossel no diagrama. E esse teorema possui aplicações também pelos resultados intermediários que demonstra, em especial o lema de regularidade de Szemerédi, usado para diversos outros resultados. E se não conseguimos contemplar completamente o poder e as aplicações desse teorema, ao menos apreciemos o intrincado jogo de demonstrações de sua prova que é, muito justamente, digno de um dos maiores matemáticos vivos da atualidade.

3 respostas