Introdução
Em meados de outubro, Justin Gilmer voou da Califórnia para Nova York para assistir ao casamento de um amigo. Enquanto estava na Costa Leste, ele visitou seu ex-conselheiro, Michael Saks, um matemático da Rutgers University, onde Gilmer havia recebido seu doutorado sete anos antes.
Saks e Gilmer conversaram durante o almoço, mas não conversaram sobre matemática. Na verdade, Gilmer não pensava seriamente em matemática desde que terminou na Rutgers em 2015. Foi quando ele decidiu que não queria uma carreira acadêmica e, em vez disso, começou a aprender a programar sozinho. Enquanto ele e Saks comiam, Gilmer contou a seu antigo mentor sobre seu trabalho no Google, onde trabalha com aprendizado de máquina e inteligência artificial.
Estava ensolarado no dia em que Gilmer visitou Rutgers. Enquanto caminhava, ele se lembrou de como em 2013 passou a maior parte do ano percorrendo os mesmos caminhos do campus, pensando em um problema chamado conjectura de sindicato fechado. Fora uma fixação, embora infrutífera: apesar de todo o seu esforço, Gilmer só conseguira aprender a si mesmo por que o problema aparentemente simples sobre conjuntos de números era tão difícil de resolver.
“Acho que muitas pessoas pensam sobre o problema até ficarem satisfeitas por entenderem por que é difícil. Provavelmente passei mais tempo nisso do que a maioria das pessoas”, disse Gilmer.
Após sua visita em outubro, algo inesperado aconteceu: ele teve uma nova ideia. Gilmer começou a pensar em maneiras de aplicar técnicas da teoria da informação para resolver a conjectura de união fechada. Ele perseguiu a ideia por um mês, sempre esperando que ela falhasse. Mas, em vez disso, o caminho para uma prova continuou se abrindo. Finalmente, em 16 de novembro, ele postou um resultado inédito isso ajuda os matemáticos a provarem a conjectura completa.
O jornal desencadeou uma enxurrada de trabalhos de acompanhamento. Matemáticos da Universidade de Oxford, do Instituto de Tecnologia de Massachusetts e do Instituto de Estudos Avançados, entre outras instituições, desenvolveram rapidamente os novos métodos de Gilmer. Mas antes disso, eles fizeram uma pergunta: quem é esse cara?
Meio cheio
A conjectura de união fechada é sobre coleções de números chamados conjuntos, como {1, 2} e {2, 3, 4}. Você pode realizar operações em conjuntos, inclusive tomando sua união, o que significa combiná-los. Por exemplo, a união de {1, 2} e {2, 3, 4} é {1, 2, 3, 4}.
Uma coleção, ou família, de conjuntos é considerada “união fechada” se a união de quaisquer dois conjuntos na família for igual a qualquer conjunto existente na família. Por exemplo, considere esta família de quatro conjuntos:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Combine qualquer par e você terá um conjunto que já está na família, tornando a união familiar fechada.
Matemáticos conversaram sobre versões da conjectura de união fechada já na década de 1960, mas ela recebeu sua primeira declaração formal em 1979, em um artigo de Pedro Frankl, um matemático húngaro que emigrou para o Japão na década de 1980 e que conta com a performance de rua entre suas atividades.
Frankl conjecturou que, se uma família de conjuntos é fechada por união, ela deve ter pelo menos um elemento (ou número) que aparece em pelo menos metade dos conjuntos. Era um limite natural por dois motivos.
Em primeiro lugar, existem exemplos prontamente disponíveis de famílias fechadas por união nas quais todos os elementos aparecem em exatamente 50% dos conjuntos. Como todos os diferentes conjuntos que você pode fazer dos números de 1 a 10, por exemplo. Existem 1,024 desses conjuntos, que formam uma família fechada por união, e cada um dos 10 elementos aparece em 512 deles. E segundo, na época em que Frankl fez a conjectura, ninguém jamais havia produzido um exemplo de família fechada em que a conjectura não fosse válida.
Portanto, 50% parecia a previsão certa.
Isso não significava que era fácil de provar. Nos anos que se seguiram ao artigo de Frankl, houve poucos resultados. Antes do trabalho de Gilmer, esses artigos só conseguiam estabelecer limites que variavam com o número de conjuntos na família (em vez de ser o mesmo limite de 50% para famílias de conjuntos de todos os tamanhos).
“Parece que deveria ser fácil e é semelhante a muitos problemas fáceis, mas resistiu aos ataques”, disse Will Sawin da Universidade de Columbia.
A falta de progresso refletia tanto a natureza complicada do problema quanto o fato de que muitos matemáticos preferiam não pensar nele; eles temiam perder anos de suas carreiras perseguindo um problema sedutor que era impossível de resolver. Gilmer se lembra de um dia em 2013 em que foi ao escritório da Saks e levantou a conjectura do fechamento do sindicato. Seu conselheiro - que no passado lutou sozinho com o problema - quase o expulsou da sala.
“Mike disse: 'Justin, você vai me fazer pensar sobre esse problema novamente e não quero fazer isso'”, disse Gilmer.
Uma Visão de Incerteza
Após sua visita a Rutgers, Gilmer revirou o problema em sua mente, tentando entender por que era tão difícil. Ele se inspirou em um fato básico: se você tem uma família de 100 conjuntos, existem 4,950 maneiras diferentes de escolher dois e obter sua união. Então ele se perguntou: como é possível que 4,950 uniões diferentes sejam mapeadas em apenas 100 conjuntos se nenhum elemento aparece nessas uniões com pelo menos alguma frequência?
Mesmo naquele ponto, ele estava a caminho de uma prova, embora ainda não soubesse. As técnicas da teoria da informação, que fornecem uma maneira rigorosa de pensar sobre o que esperar quando você puxa um par de objetos ao acaso, o levariam até lá.
A teoria da informação desenvolvida na primeira metade do século 20, mais famosa com o artigo de 1948 de Claude Shannon, “Uma teoria matemática de comunicação.” O artigo forneceu uma maneira precisa de calcular a quantidade de informações necessárias para enviar uma mensagem, com base na quantidade de incerteza sobre o que exatamente a mensagem diria. Esse link - entre a informação e a incerteza — foi o insight notável e fundamental de Shannon.
Para dar um exemplo de brinquedo, imagine que eu jogo uma moeda cinco vezes e envio a sequência resultante para você. Se for uma moeda normal, são necessários cinco bits de informação para serem transmitidos. Mas se for uma moeda carregada - digamos, com 99% de probabilidade de dar cara - leva muito menos. Por exemplo, podemos combinar antecipadamente que enviarei a você um 1 (um único bit de informação) se a moeda carregada der cara todas as cinco vezes, o que é muito provável que aconteça. Há mais surpresa no resultado de um cara ou coroa justo do que em um tendencioso e, portanto, mais informações.
O mesmo pensamento se aplica às informações contidas em conjuntos de números. Se eu tiver uma família de conjuntos fechados de união – digamos os 1,024 conjuntos feitos dos números de 1 a 10 – eu poderia escolher dois conjuntos aleatoriamente. Então eu poderia comunicar os elementos de cada conjunto para você. A quantidade de informação necessária para enviar essa mensagem reflete a quantidade de incerteza sobre quais são esses elementos: há 50% de chance, por exemplo, de que o primeiro elemento no primeiro conjunto seja 1 (porque 1 aparece na metade dos conjuntos em a família), assim como há 50% de chance de o primeiro resultado em uma sequência de jogadas justas de moeda ser cara.
A teoria da informação aparece com frequência na combinatória, uma área da matemática preocupada com a contagem de objetos, que foi o que Gilmer estudou quando era aluno de pós-graduação. Mas, enquanto voava de volta para a Califórnia, ele se preocupou com o fato de que a maneira como pensava em conectar a teoria da informação à conjectura da união fechada fosse o insight ingênuo de um amador: certamente os matemáticos já haviam encontrado esse objeto brilhante antes e o reconheceram como ouro dos tolos. .
“Para ser sincero, estou um pouco surpreso por ninguém ter pensado nisso antes”, disse Gilmer. “Mas talvez eu não devesse me surpreender, porque eu mesmo pensei nisso por um ano e conhecia a teoria da informação.”
Mais provável que não
Gilmer trabalhou no problema à noite, após terminar seu trabalho no Google, e nos finais de semana durante a segunda quinzena de outubro e início de novembro. Ele foi encorajado por ideias que um grupo de matemáticos havia explorado anos antes em um colaboração aberta no blog de um proeminente matemático chamado Tim Gowers. Ele também trabalhou com um livro ao seu lado para poder procurar fórmulas que havia esquecido.
“Você pensaria que alguém que apresenta um ótimo resultado não deveria ter que consultar o Capítulo 2 de Elementos da Teoria da Informação, mas eu fiz ”, disse Gilmer.
A estratégia de Gilmer foi imaginar uma família fechada em que nenhum elemento aparecesse em 1% de todos os conjuntos — um contra-exemplo que, se realmente existisse, invalidaria a conjectura de Frankl.
Digamos que você escolha dois conjuntos, A e B, desta família aleatoriamente e considere os elementos que poderiam estar nesses conjuntos, um de cada vez. Agora pergunte: quais são as chances de que o conjunto A contenha o número 1? E conjunto B? Como cada elemento tem um pouco menos de 1% de chance de aparecer em qualquer conjunto, você não esperaria que A ou B contivessem 1. O que significa que há pouca surpresa - e pouca informação obtida - se você descobrir que nenhum dos dois de fato faz.
Em seguida, pense na chance de que a união de A e B contenha 1. Ainda é improvável, mas é mais provável que apareça em qualquer um dos conjuntos individuais. É a soma da probabilidade de aparecer em A e a probabilidade de aparecer em B menos a probabilidade de aparecer em ambos. Então, talvez pouco menos de 2%.
Isso ainda é baixo, mas está mais próximo de uma proposta de 50-50. Isso significa que são necessárias mais informações para compartilhar o resultado. Em outras palavras, se houver uma família fechada de união na qual nenhum elemento apareça em pelo menos 1% de todos os conjuntos, haverá mais informação na união de dois conjuntos do que em qualquer um dos próprios conjuntos.
“A ideia de revelar as coisas elemento por elemento e observar a quantidade de informações que você aprende é extremamente inteligente. Essa é a ideia principal da prova”, disse Ryan Alweiss da Universidade de Princeton.
Nesse ponto, Gilmer estava começando a se aproximar da conjectura de Frankl. Isso porque é fácil demonstrar que em uma família fechada por união, a união de dois conjuntos necessariamente contém menos informações do que os próprios conjuntos — não mais.
Para ver por que, pense naquela família fechada de união contendo os 1,024 conjuntos diferentes que você pode fazer dos números de 1 a 10. Se você escolher dois desses conjuntos aleatoriamente, em média, terminará com conjuntos contendo cinco elementos. (Desses 1,024 conjuntos, 252 contêm cinco elementos, tornando-o o tamanho de conjunto mais comum.) Também é provável que você acabe com uma união contendo cerca de sete elementos. Mas existem apenas 120 maneiras diferentes de fazer conjuntos contendo sete elementos.
A questão é que há mais incerteza sobre o conteúdo de dois conjuntos escolhidos aleatoriamente do que sobre sua união. A união se desvia para conjuntos maiores com mais elementos, para os quais há menos possibilidades. Quando você pega a união de dois conjuntos em uma família fechada por união, você meio que sabe o que vai obter — como quando joga uma moeda viciada — o que significa que a união contém menos informações do que os conjuntos dos quais é composta.
Com isso, Gilmer tinha uma prova. Ele sabia que se nenhum elemento aparecesse mesmo em 1% dos conjuntos, a união é forçada a conter mais informações. Mas o sindicato deve conter menos informações. Portanto, deve haver pelo menos um elemento que apareça em pelo menos 1% dos conjuntos.
O empurrão para 50
Quando Gilmer postou sua prova em 16 de novembro, ele incluiu uma nota dizendo que achava que era possível usar seu método para chegar ainda mais perto de uma prova da conjectura completa, aumentando potencialmente o limite para 38%.
Cinco dias depois, três diferente grupos dos matemáticos publicaram artigos com poucas horas de intervalo, baseados no trabalho de Gilmer para fazer exatamente isso. Adicional papéis seguido, mas a explosão inicial parece ter levado os métodos de Gilmer o mais longe possível; chegar a 50% provavelmente exigirá novas ideias adicionais.
Ainda assim, para alguns dos autores dos artigos subsequentes, chegar a 38% foi relativamente simples, e eles se perguntaram por que Gilmer não fez isso sozinho. A explicação mais simples acabou sendo a correta: depois de mais de meia década fora da matemática, Gilmer simplesmente não sabia como fazer parte do trabalho técnico analítico necessário para realizá-la.
“Eu estava um pouco enferrujado e, para ser honesto, estava preso”, disse Gilmer. “Mas eu estava ansioso para ver onde a comunidade iria levar isso.”
No entanto, Gilmer pensa que as mesmas circunstâncias que o deixaram fora da prática provavelmente tornaram sua prova possível em primeiro lugar.
“É a única maneira de explicar por que pensei no problema por um ano na pós-graduação e não fiz nenhum progresso. Deixei a matemática por seis anos, depois voltei ao problema e fiz essa descoberta”, disse ele. “Não sei como explicar, exceto que estar no aprendizado de máquina influenciou meu pensamento.”
Correção: 3 de janeiro de 2023
A manchete original referia-se a Gilmer como um “engenheiro do Google”. Na verdade, ele é um pesquisador.
