Arquivo mensais:julho 2012

O teorema das cores

Rookie

Na coleção de meus teoremas favoritos, o teorema das cores tem um lugar especial. Eu trabalhava na usina nuclear de Belleville-sur-Loire quando o responsável de meu setor explicava as divisões e departamentos da central. Ele tomou uma planta dos principais encanamentos, aquecedores e turbinas e pôs-se a remarcar os setores da usina: os aquecedores primários, os secundários, a transmissão do reator às válvulas, o condensador, cada setor era marcado com uma cor, e setores vizinhos possuíam cores diferentes, para não causar confusão. Ele usava aqueles marcadores Stabilo coloridos, e, olhando para sua coleção de canetas, apenas quatro cores, disse: “acho que não vou ter canetas para marcar todos”. Quase eufórico, respondi: não, você vai!

Nenhum atlas que se preze tentaria um desenho tão minimalista dos mapas, em geral vemos países em várias cores e tons, e sempre temos aquela caixa de doze cores da Faber-Castell para colorir o papel-vegetal em nossas aulas de geografia na infância, o teorema, por isso, nem é tão famoso. Ainda, quatro cores colorem qualquer mapa, e esse resultado foi um dos de mais difícil demonstração na história da matemática.

Esse teorema, o das quatro cores, era conjecturado havia muito antes de sua demonstração, que é tida como uma das mais feias da matemática. Antes de comentar a prova, vamos comentar o teorema.

Esse teorema é apenas válido para mapas cujos países são conexos, ou seja, o caso do Alaska, parte dos EUA e desconexo do resto do país, não pode ser incluído. Com apenas regiões conexas, é fácil perceber que você precisa de ao menos quatro cores para colorir um mapa; é possível encontrar quatro países vizinhos uns dos outros de forma a exigir quatro cores. Temos, como exemplo simples, o Paraguai e Luxemburgo. Deste último, usando todas as minhas habilidades de cartografia, compus um pequeno diagrama de suas fronteiras: França, Alemanha e Bélgica. Esses três países fazem fronteira entre si e com Luxemburgo, preciso de quatro cores para pintar esse mapa:

Mas é completamente impossível, em um mapa plano ou em uma esfera, desenhar cinco países tais que todos fazem fronteiras com todos. Esse é um exercício divertido, tentar compor o mais estranho dos mapas e ir colorindo pouco a pouco, convencendo-se do teorema, tentando exigir uma quinta cor, e jamais precisando. A Wikipédia possui um exemplo interessante de mapa caótico, irreal e muito mais bagunçado que o de um atlas seria, e ainda conseguimos colori-lo com não mais que quatro cores.

A demonstração desse teorema é surpreendente. Abandonando os ideais de beleza matemáticos, a busca de uma prova elegante e concisa de um resultado tão bonito, dois matemáticos em 1961, Appel e Haken, demonstraram, grosso modo, que todas as situações de mapas planos que precisam ser coloridos caem em 1 de 1.936 casos. É isso mesmo: eles demonstraram, em um abuso de linguagem, que todo mapa não é mais que um caso levemente modificado ou composto de 1.936 tipos possíveis de mapa. Com esse conjunto em mãos, eles coloriram todos com quatro cores e o teorema estava provado.

É importante notar que tanto para encontrar os 1.936 mapas quanto para os colorir, Haken e Appel usaram os computadores disponíveis na época, tornando essa a primeira grande demonstração a ser realizada por exaustão através de um computador. Beleza matemática é algo relativo, mas dificilmente um matemático diria que enumerar 1.936 casos possíveis do teorema e provar um resultado para todos configura estética matemática.

Pouco a pouco a demonstração foi aceita, e hoje é tida como a demonstração padrão do problema das cores. Em uma esfera ou plano, apenas quatro são necessárias. Se, contudo, seu planeta fosse uma rosquinha, você precisaria de sete cores para preencher todos os mapas. O número de cores necessárias para colorir um mapa possui uma relação profunda com a geometria do objeto, e abre diversas questões ainda mais difíceis de responder que o teorema das quatro cores.

Meu chefe na usina nuclear não conseguiu usar apenas quatro cores. Em sua pressa de enumerar os departamentos, fez escolhas ruins e achou que precisaria de cinco, tentando provar triunfante que essa história de teorema era furada. Nada pude dizer, sorri, culpei as canetas e passei toda aquela tarde tentando entender as siglas de muito mais que 1936 encanamentos, turbinas, aquecedores e motores.

Deixe um comentário

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

Informação e demônios

Geek

demônio de maxwell

Sorry, but you must be THIS hot to get in.

Uma das leis físicas mais mal citadas, em diversos contextos e por ser um pouco difícil de explicar, é a segunda lei da termodinâmica: a lei responsável por prever que, ao colocar sua panela no fogo, não é o fogo que esquenta e ela que esfria; mas o contrário. Ela tem uma formulação complicada, a definição de entropia, de desordem e de reversibilidade, não vou me meter nisso hoje. Uma consequência dela, no entanto, é a seguinte propriedade: um sistema em equilíbrio térmico (todo mundo à mesma temperatura) precisa gastar energia para criar uma diferença de temperatura, ou seja, um lado quente e um frio. E essa propriedade é bem evidente, não por menos sua geladeira é ligada na tomada: ela usa essa energia para criar um ambiente frio (o interior do refrigerador) e um quente (aquela parte atrás que você usa para secar roupas e não devia).

Quando esse princípio foi formulado, no meio do século XIX, foi um dos pais da termodinâmica, o gigante na física James C. Maxwell, o primeiro a elaborar uma tortuosa ideia em busca de uma melhor compreensão da lei. Um bom jeito de entender uma lei da física é tentar imaginar um sistema que a viola, e foi o que ele fez. Imagine uma caixa com um gás, dividida em dois compartimentos (esquerda e direita) separados por uma parede. Essa parede, contudo, possui uma pequena porta, e essa porta é controlada por um pequeno demônio que possui informações sobre cada partícula na caixa. Cada vez que uma partícula rápida do lado esquerdo se aproxima da porta, o demônio a deixa passar para o direito; e cada vez que uma partícula lenta no lado direito se aproxima da porta, o demônio a deixa passar para o lado esquerdo. Essa figura ajuda, tirada do site phys.com.

Como temperatura não é nada mais que a medida da agitação média das partículas, esse demônio acaba de separar o gás em um lado quente e um lado frio. Se essa porta for leve o suficiente, ou uma porta rolante de atrito zero, o trabalho de abrir a porta é nulo e o demônio, sem gastar energia, criou uma diferença de temperatura. Sem precisar ligar na tomada, o demônio criou uma geladeira. Essa ideia, que de fato é um pouco absurda, ainda assim tenta provar um ponto: alguém com bastante informação sobre o sistema pode violar a segunda lei da termodinâmica.

Gostamos de nossas leis, não queremos que elas sejam violadas tão facilmente. O demônio de Maxwell assombrou físicos por quase um século, demoramos para perceber onde estava a energia gasta pelo demônio para dividir o gás em quente e frio. Enquanto muitos tentaram atacar a parede no problema, ou a própria natureza irreal da situação, a resposta estava no cérebro do demônio.

Maxwell foi muito malandro na escolha de palavras, pois o problema logo no início tenta te enganar: ele usa um demônio, uma criatura imaterial, para fazer o serviço. Ele sabe tudo, ou ao menos sabe o que se passa em torno da porta, e decide abrir ou não a porta com essa informação. Mas precisamos imaginar que, se ele sabe, essa informação está armazenada em algum lugar. Surpreendentemente, a energia gasta pelo demônio de Maxwell está no fato de sobre-escrever a informação que possuía sobre a partícula levando em conta o fato de ter aberto a porta e tê-la deixado passar.

Essa resposta parece um pouco roubada, mas foi uma das grandes descobertas do meio do século XX, o nascimento da teoria da informação. Quando os computadores começaram a surgir, muita gente se colocou a tentar estabelecer os limites de cálculo de uma máquina daquelas, e quanta energia ela gastaria para realizar operações. No início, acreditava-se que toda operação feita pelo computador possuía uma energia mínima para ser realizada, o valor $k_BT\log 2$, onde $k_B$ é a constante de Boltzmann e $T$ é a temperatura. Esse limite, proposto por von Neumann, não está correto, mas quase. Se estivesse correto, seria impossível criar computadores funcionais, a quantidade de energia necessária para fazê-los rodar seria alta demais e resfriá-los seria quase impossível. Apenas em 1961 Laudauer explicaria o limite corretamente: apenas uma operação do computador precisa de gasto de energia: a operação de apagar uma memória.

O argumento de Laudauer é simples e bonito. Vamos pensar na forma mais simples de se armazenar uma informação: o bit. Essa variável vale 0 ou 1, e deve ser armazenada de alguma forma, seja uma alavanca para um lado e não para outro, seja um aparato que permite ou não passar corrente. De forma bem geral, representamos o bit da seguinte forma:

Essa figura é um potencial, que podemos deformar à vontade, mantendo uma pequena bolinha de um lado e não do outro, representando o bit 1, enquanto no lado esquerdo seria o 0. Vamos supor que a temperatura da bolinha seja baixa o suficiente para que a chance de mudar de lado nesse potencial seja desprezível, como uma colina alta demais para que a bolinha vermelha, na velocidade em que está, possa atravessar e chegar ao outro lado.

Queremos operar esse bit, transformá-lo de 1 em 0, ou seja, fazer a bolinha passar da direita para a esquerda. Esse processo é o equivalente a sobre-escrever uma informação: devemos primeiro esquecer o que havia e depois forçar a bolinha a ficar do lado que queremos. A primeira coisa que precisamos fazer, portanto, é descer a barreira e “apagar” a informação:

Agora a bolinha passeia livremente entre os dois bits. Esse gif não é muito honesto, a bolinha, para ser coerente com a física, precisa ir e voltar muitas vezes, esse processo de descer a barreira deve ser feito de forma quasi-estacionária, ou seja, devemos descer a barreira levando um tempo muito maior que o tempo característico da bolinha de ir de um lado para o outro. Assim, a bolinha faria o caminho de ida e voltas muitas vezes antes de ver a barreira descer. Logo mais discutiremos se isso é realmente possível.

O próximo passo, escrever a informação, consiste em levantar a barreira de potencial de forma a forçar pouco a pouco a bolinha a ir para o lado que queremos. Enquanto ela vai e vem, vamos aumentando a barreira da direita. Isso forçará a bolinha a ficar confinada na esquerda. Em seguida, descemos a barreira da direita e temos a bolinha confinada do lado que queremos. O processo todo é resumido no seguinte gif, feito com algum esforço e uma tarde livre:

Vamos conversar agora sobre cada etapa desse processo, e as energias envolvidas. Queremos saber se precisamos gastar energia para sobre-escrever a memória e, se precisamos, em qual etapa exatamente. Para tal, vamos dar nomes às etapas:

Para entender o que está acontecendo, precisamos de algumas noções de termodinânica. Dizemos que um processo é reversível quando não há aumento de entropia, o caminho inverso pode acontecer.  É importante notar que todo processo reversível deve ser quasi-estacionário: é necessário que cada ponto desse processo seja um estado de equilíbrio, o equivalente a dizer, de maneira grosseira, que não podemos mexer o sistema muito rapidamente se temos a pretensão de seguir o caminho inverso. A ideia é mover um pouco, bem pouco, esperar o equilíbrio chegar, mover mais um pouquinho, esperar o equilíbrio chegar, e continuar dessa maneira. Em uma situação idealizada, podemos dizer que as mudanças são infinitesimais e que o processo, a cada instante, está em equilíbrio.

Note que esse raciocínio não é de todo desonesto, pois estamos buscando o limite mínimo de gasto de energia. Na busca do limite, trabalhamos com a situação mais idealizada possível, e concluímos que melhor que isso não conseguiremos jamais.

Assim, as etapas são realizadas em um processo quasi-estacionário, de forma a estar constantemente no estado de equilíbrio. Queremos um pouco mais que quasi-estacionário, queremos fazer todas essas etapas em processos reversíveis. Se conseguíssemos, como não aplicamos nenhum trabalho na bolinha (ela não ganhou energia nenhuma, não mudou sua altura máxima atingida no poço), não teremos gasto energia nenhuma e teremos trocado a bolinha de poço. É então que Landauer nos diz: isso não é possível. Para ser mais exato, todos os processos podem ser feitos sem gastar energia, exceto passar de A para B.

Apagar uma memória é a única operação que gasta energia. Nosso raciocínio do “quasi-estacionário” não se aplica ao processo AB, e é por isso que nossa ideia falha. Quando dizemos “um processo lento”, queremos dizer lento em relação ao tempo que o estado leva para estar em equilíbrio. Mas conforme vamos descendo o poço, notamos que, se o poço é muito alto, o tempo característico para que a bolinha mude de poço é muito alto. Ora, na situação A o tempo que a bolinha leva para mudar de poço é infinito, e na situação B ele é finito, é, portanto, impossível realizar o processo AB de forma quasi-estacionária, porque você, em algum momento, terá o tempo característico de mudança de poço igual ao tempo característico de descer o poço. Em outras palavras, é impossível realizar um processo mais lento que um processo cujo tempo característico para atingir o equilíbrio é infinito!

Todos os outros processos, se feitos de forma bem devagar, podem ser realizados de forma completamente reversível. O que pega é o processo de apagar a memória, de deixar o bit indeciso, e é aí que o demônio perde. Em seu cérebro, ou em seu supercomputador, ele deve, a cada vez que deixa uma partícula passar, reescrever sua informação sobre a trajetória da partícula, porque, pela vontade dele, ela mudou de lugar e não será mais a mesma. O demônio gasta energia, uma forma de “energia mental”, para reajustar seu conhecimento à nova configuração.

Isso resolve o problema do demônio de Maxwell, que deve gastar energia para criar essa geladeira microscópica. Por mais conhecimento que tenha, ele deve apagar e sobre-escrever bits no momento em que decide que a partícula mudará de lado. Para o demônio, nessas condições, o maior esforço não é lembrar, analisar ou mudar a partícula; seu maior esforço é, de forma quase poética, esquecê-la.

6 respostas

Nobel 2013 – O bóson de Higgs

Rookie

Hoje é um dia de festa para a física.

Há algumas horas, o CERN, Centro Europeu de Pesquisa Nuclear, anunciou a tão esperada descoberta: encontramos o bóson de Higgs. Depois de muito tempo, dinheiro e estudo, os físicos de partículas conseguiram, e hoje o dia é deles. Tenho lido bastante coisa na imprensa sobre essa descoberta, e infelizmente muita bobagem, em especial com o apelido “partícula de Deus”. De minha parte, acredito que vale a pena escrever um pequeno resumo sobre uma das aplicações do Higgs e sua importância para a física.

Para entender o Higgs, precisamos entender as forças da natureza. Todo tipo de interação acontece em uma de quatro formas possíveis: por força gravitacional, por força eletromagnética, por força forte ou por força fraca. As duas primeiras são bem conhecidas, é por elas que você é atraído pela Terra (gravitacional) mas não atravessa a Terra com seus pés (eletromagnética). As outras são menos famosas, mas igualmente importantes: a força forte é a atração que prótons e nêutrons sentem entre si, e o que torna o núcleo atômico possível; afinal, você nunca se perguntou como tanta carga positiva conseguia ficar junta? A fraca é mais sutil, ela age na desintegração de partículas e em uma boa parte do que conhecemos como radioatividade.

Essas quatro forças fundamentais possuem características muito diferentes. A forte é de alcance extremamente curto, mas muito intensa onde age, e sua forma exata ainda é desconhecida. A fraca age apenas em partículas “girando” em um determinado sentido, não em outro, como se preferisse a esquerda à direita, um comportamento muito estranho. A eletromagnética é talvez a mais bem comportada, conhecemos todas as suas leis e seu alcance, desde o século XIX ela não é mistério. A gravidade, no entanto, é a irmã bastarda das forças, resistindo a toda tentativa de unificação, sozinha, quase uma criança autista isolada em seu mundo e hostil a qualquer tentativa de se aproximar das outras. Pedi a um amigo que representasse as quatro forças em um desenho, que é um de meus favoritos:

No século XX, contudo, os físicos descobriram um passado comum entre a força fraca e a eletromagnética. Apesar de possuírem comportamentos completamente diferentes, descobrimos que, se estudamos partículas ou forças a altíssimas energias, essas duas forças são, na verdade, a mesma coisa nessa escala! Como irmãos gêmeos que depois de uma certa idade são completamente diferentes, essas forças já foram a mesma coisa, logo depois do Big Bang, quando a energia ainda era alta demais; mas hoje possuem apenas traços leves de parentesco.

Aí entra o Higgs. Essa partícula, que na verdade é mais um campo, é responsável pela quebra na simetria entre a força fraca e a eletromagnética. Em energias muito altas, elas são a mesma coisa, mas, conforme a energia vai baixando, o Higgs começa a agir e a tornar essas forças completamente diferentes.

Toda força é transmitida por uma partícula. As partículas da força fraca são os bósons W e Z, a partícula da eletromagnética é o fóton, e eles são radicalmente diferentes; para começar, W e Z têm massa, o fóton não. Isso é culpa do Higgs, por isso dizemos que ele é responsável por dar massa aos bósons, e até a mais outras coisas, porque podemos repetir esse raciocínio para explicar a existência de massa em todas as outras partículas! A presença do Higgs é a causa da separação entre a força eletromagnética e a fraca; sem ela, o universo seria um lugar bem diferente. Ele possui outras tarefas, mas talvez a mais importante seja essa, separar esses irmãos gêmeos e tornar um o bom aluno, enquanto o outro torna-se o rebelde.

A importância dessa descoberta é múltipla. Em primeiro lugar, temos nossa teoria confirmada, o que é fundamental para a ciência. Se isso fosse geografia, poderíamos dizer que há uma cidade ali, uma aqui, porque as observamos; e então dizermos: “Pelos meus estudos, deve haver uma cidade nas coordenadas 21º43’19”S, 44º59’06”W”, viajar e descobrir lá uma cidade, nunca antes observada, encontrando cidades e povos apenas porque sua geografia estava correta, porque a teoria está certa.

Em seguida, podemos aprofundar o estudo dessa partícula para desvendar outros mistérios, como o que é massa? Como a gravidade (que atrai massas) funciona? Por que a mesma massa que usamos para calcular a resistência a ser acelerado (aquela do $F = m.a$) é a mesma que serve para dizer o quanto um corpo atrai o outro? Como escrever a gravidade nessa linguagem de partículas? Pode o Higgs nos ajudar a entender toda aquela parte de matéria escura e energia escura que nos desafia e fascina, sem nos dar pista nenhuma?

Para mais detalhes, há um vídeo excepcional produzido pelo PhD Comics, de onde tirei a imagem inicial do post, que explica as dificuldades em medir o Higgs e que surpresas ainda nos aguardam.

Assim, parabenizo os físicos de partículas, em especial os experimentais, hoje o dia é de vocês. Uma vitória para os físicos, e para toda a ciência, que avançou mais um pouquinho na compreensão do universo, na busca pela verdade; uma pequena partícula para o CERN, um grande passo para a humanidade. E dou boas-vindas ao Higgs a nossa lista de partículas elementares, o tão esperado bóson que, depois de tanto fugir e se esquivar, cansou e voltou para casa.

3 respostas