'A-Team' de matemática prova uma ligação crítica entre adição e conjuntos | Revista Quanta

Em um conjunto de números escolhido aleatoriamente, a adição pode dar errado.

Some todos os pares desse conjunto e você terminará com uma nova lista que provavelmente terá muito mais números do que a que você começou. Comece com 10 números aleatórios e esta nova lista (chamada sumset) terá cerca de 50 elementos. Comece com 100 e a soma provavelmente terá cerca de 5,000; 1,000 números iniciais aleatórios formarão uma soma de 500,000 números.

Mas se o seu conjunto inicial tiver estrutura, o sumset pode acabar com menos números do que isso. Considere outro conjunto de 10 números: todos os números pares de 2 a 20. Como a soma de pares diferentes resultará no mesmo número - 10 + 12 é igual a 8 + 14 e 6 + 16 - o conjunto de soma tem apenas 19 números, não 50. Esta diferença torna-se cada vez mais profunda à medida que os conjuntos aumentam. Uma lista estruturada de 1,000 números pode ter um conjunto com apenas 2,000 números.

Na década de 1960, um matemático chamado Gregório Freiman começou a investigar conjuntos com pequenas somas em um esforço para sondar a ligação entre adição e estrutura de conjuntos – uma conexão crucial que define o campo matemático da combinatória aditiva. Freiman fez progressos impressionantes, provando que um conjunto com um conjunto pequeno deve ser contido por um conjunto maior cujos elementos são espaçados num padrão altamente regular. Mas então o campo estagnou. “A prova original de Freiman era extraordinariamente difícil de entender, a ponto de ninguém ter certeza absoluta de que estava correta. Portanto, não teve realmente o impacto que poderia ter tido”, disse Timothy Gowers, matemático do Collège de France e da Universidade de Cambridge e medalhista Fields. "Mas então Imre Ruzsa irrompeu em cena.”

Em uma série de dois papéis na década de 1990, Ruzsa provou novamente o teorema de Freiman com um novo argumento elegante. Alguns anos depois, Katalin Marton, um influente matemático húngaro que morreu em 2019, ajustou a questão do que uma pequena soma implica sobre a estrutura do conjunto original. Ela substituiu os tipos de elementos que apareciam no conjunto e o tipo de estrutura que os matemáticos deveriam procurar, pensando que isso permitiria aos matemáticos extrair ainda mais informações. A conjectura de Marton tem ligações com sistemas de prova, teoria de codificação e criptografia, e ocupa um lugar de destaque na combinatória aditiva.

Sua conjectura “parece realmente uma das coisas mais básicas que não entendemos”, disse Ben Green, um matemático da Universidade de Oxford. Isso “simplesmente sustentou muitas coisas que me interessam”.

Green juntou forças com Gowers, Freddie Maneiras da Universidade da Califórnia, San Diego, e Terence tao, medalhista Fields na Universidade da Califórnia, em Los Angeles, para formar o que o matemático e blogueiro israelense Gil Kalai chamado de “Um time”dos matemáticos. Eles provaram uma versão da conjectura em um artigo compartilhado em 9 de novembro.

Redes Katz, um matemático da Universidade Rice que não esteve envolvido no trabalho, descreve a prova como “maravilhosamente simples” – e “mais ou menos completamente inesperada”.

Tao então iniciou um esforço para formalizar a prova em Lean, uma linguagem de programação que ajuda os matemáticos a verificar teoremas. Em apenas algumas semanas, esse esforço foi bem-sucedido. Na manhã de terça-feira, 5 de dezembro, Tao anunciou que Lean provou a conjectura sem qualquer “desculpe” – a afirmação padrão que aparece quando o computador não consegue verificar uma determinada etapa. Este é o uso de maior destaque desse tipo ferramentas de verificação desde 2021, e marca um ponto de inflexão na maneira como os matemáticos escrevem provas em termos que um computador pode compreender. Se essas ferramentas se tornarem fáceis de usar pelos matemáticos, elas poderão substituir o processo de revisão por pares, muitas vezes prolongado e oneroso, disse Gowers.

Os ingredientes da prova estavam fervendo há décadas. Gowers concebeu seus primeiros passos no início dos anos 2000. Mas foram necessários 20 anos para provar o que Kalai chamou de “um Santo Graal” da área.

O grupo

Para entender a conjectura de Marton, é útil estar familiarizado com o conceito de grupo, um objeto matemático que consiste em um conjunto e uma operação. Pense nos inteiros – um conjunto infinito de números – e na operação de adição. Cada vez que você soma dois números inteiros, você obtém outro número inteiro. A adição também obedece a algumas outras regras de operações de grupo, como a associatividade, que permite alterar a ordem das operações: 3 + (5 + 2) = (3 + 5) + 2.

Dentro de um grupo, às vezes você pode encontrar conjuntos menores que satisfazem todas as propriedades do grupo. Por exemplo, se você adicionar dois números pares, obterá outro número par. Os números pares são um grupo em si, tornando-os um subgrupo dos inteiros. Os números ímpares, por outro lado, não são um subgrupo. Se você somar dois números ímpares, obterá um número par – não no conjunto original. Mas você pode obter todos os números ímpares simplesmente adicionando 1 a cada número par. Um subgrupo deslocado como este é chamado de coset. Ele não possui todas as propriedades de um subgrupo, mas mantém a estrutura de seu subgrupo de várias maneiras. Por exemplo, assim como os números pares, os números ímpares são todos espaçados uniformemente.

Marton supôs que se você tiver um aparelho que ligaremos A composto por elementos de grupo cuja soma não é muito maior do que A em si, então existe algum subgrupo - chame-o G - com uma propriedade especial. Mudança G algumas vezes para fazer cosets, e esses cosets, juntos, conterão o conjunto original A. Além disso, ela supôs que o número de cosets não cresce muito mais rápido do que o tamanho do sumset — ela acreditava que deveria estar relacionado por um fator polinomial, em oposição a um crescimento exponencial muito mais rápido.

Isso pode soar como uma curiosidade altamente técnica. Mas porque se trata de um teste simples - o que acontece quando você adiciona apenas dois elementos ao conjunto? — para a estrutura abrangente de um subgrupo, é muito importante para matemáticos e cientistas da computação. A mesma ideia geral aparece quando cientistas da computação tentam criptografar mensagens para que você possa decodificar apenas uma parte da mensagem de cada vez. Também aparece em provas verificáveis ​​probabilisticamente, uma forma de prova que os cientistas da computação podem verificar verificando apenas algumas informações isoladas. Em cada um desses casos, você trabalha com apenas alguns pontos em uma estrutura – decodificando apenas alguns bits de uma mensagem longa ou verificando uma pequena parte de uma prova complicada – e conclui algo sobre uma estrutura maior e de nível superior.

“Você pode fingir que tudo é um grande subconjunto de um grupo”, disse Tom Sanders, um ex-aluno de Gowers que agora é colega de Green em Oxford, ou você pode “conseguir tudo o que queria com a existência de muitas coincidências aditivas. Ambas as perspectivas são úteis.”

Ruzsa publicou a conjectura de Marton em 1999, dando-lhe todo o crédito. “Ela chegou a essa conjectura independentemente de mim e de Freiman, e provavelmente antes de nós”, disse ele. “É por isso que, quando conversei com ela, decidi chamar isso de conjectura dela.” Ainda assim, os matemáticos agora se referem a ela como conjectura polinomial de Freiman-Ruzsa, ou PFR.

Zeros e uns

Os grupos, como muitos objetos matemáticos, assumem muitas formas diferentes. Marton supôs que sua conjectura fosse verdadeira para todos os grupos. Isso ainda não foi mostrado. O novo artigo prova isso para um tipo específico de grupo, que toma como elementos listas de números binários como (0, 1, 1, 1, 0). Como os computadores funcionam em binário, esse grupo é crucial na ciência da computação. Mas também tem sido útil em combinatória aditiva. “É como um cenário de brinquedo onde você pode brincar e experimentar coisas”, disse Sanders. “A álgebra é muito, muito melhor” do que trabalhar com números inteiros, acrescentou.

As listas têm comprimentos fixos e cada bit pode ser 0 ou 1. Você os soma adicionando cada entrada à sua contraparte em outra lista, com a regra de que 1 + 1 = 0. Portanto (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR é uma tentativa de descobrir como seria um conjunto se não fosse exatamente um subgrupo, mas tivesse algumas características semelhantes a grupos.

Para tornar o PFR preciso, imagine que você tem um conjunto de listas binárias chamadas A. Agora pegue cada par de elementos de A e some-os. As somas resultantes constituem a soma de A, сhamado A + A. Se os elementos de A são escolhidos aleatoriamente, então a maioria das somas são diferentes umas das outras. Se houver k elementos em A, isso significa que haverá cerca k²/2 elementos no conjunto. Quando k é grande - digamos, 1,000 - k²/2 é muito maior que k. Mas se A é um subgrupo, cada elemento de A + A é em A, significa que A + A é do mesmo tamanho que A si.

O PFR considera conjuntos que não são aleatórios, mas também não são subgrupos. Nestes conjuntos, o número de elementos em A + A é um pouco pequeno - digamos, 10kOu 100k. “É realmente útil quando a sua noção de estrutura é muito mais rica do que apenas uma estrutura algébrica exata”, disse Shachar Lovett, cientista da computação da Universidade da Califórnia, em San Diego.

Todos os conjuntos que os matemáticos conheciam e que obedeciam a esta propriedade “são bastante próximos dos subgrupos reais”, disse Tao. “Essa foi a intuição, que não havia nenhum outro tipo de grupo falso por aí.” Freiman provou uma versão desta afirmação em seu trabalho original. Em 1999, Ruzsa estendeu o teorema de Freiman dos inteiros para a configuração de listas binárias. Ele provou que quando o número de elementos em A + A é um múltiplo constante do tamanho de A, A está contido em um subgrupo.

Mas o teorema de Ruzsa exigia que o subgrupo fosse enorme. O insight de Marton foi postular que, em vez de estar contido em um subgrupo gigante, A poderia estar contido em um número polinomial de cosets de um subgrupo que não é maior que o conjunto original A.

'Eu conheço uma ideia real quando vejo uma ideia real'

Por volta da virada do milênio, Gowers encontrou as provas de Ruzsa do teorema de Freiman enquanto estudava um problema diferente sobre conjuntos contendo sequências de números uniformemente espaçados. “Eu precisava de algo assim, obter informações estruturais a partir de informações muito mais vagas sobre um determinado conjunto”, disse Gowers. “Tive muita sorte porque, não muito antes, Ruzsa produziu esta prova absolutamente linda.”

Gowers começou a elaborar uma prova potencial da versão polinomial da conjectura. A ideia dele era começar com um set A cuja soma era relativamente pequena, então gradualmente manipulamos A em um subgrupo. Se ele pudesse provar que o subgrupo resultante era semelhante ao conjunto original A, ele poderia facilmente concluir que a conjectura era verdadeira. Gowers compartilhou suas ideias com colegas, mas ninguém conseguiu moldá-las em uma prova completa. Embora a estratégia de Gowers tenha sido bem-sucedida em alguns casos, em outros as manipulações levaram A mais longe da conclusão desejada da conjectura polinomial de Freiman-Ruzsa.

Eventualmente, o campo seguiu em frente. Em 2012, Sanders quase provou PFR. Mas o número de subgrupos deslocados de que ele precisava estava acima do nível polinomial, embora apenas um pouquinho. “Depois que ele fez isso, isso significou que se tornou uma coisa menos urgente, mas ainda assim um problema muito bom pelo qual tenho grande carinho”, disse Gowers.

Mas as ideias de Gowers sobreviveram nas memórias e nos discos rígidos de seus colegas. “Há uma ideia real aí”, disse Green, que também foi aluno de Gowers. “Eu reconheço uma ideia real quando vejo uma ideia real.” Neste verão, Green, Manners e Tao finalmente libertaram as ideias de Gowers do seu purgatório.

Green, Tao e Manners colaboraram por 37 páginas antes de pensarem em retornar às ideias de Gowers de 20 anos. Em 23 de junho papel, eles usaram com sucesso um conceito da teoria da probabilidade chamado variáveis ​​aleatórias para sondar a estrutura de conjuntos com somas pequenas. Ao fazer essa mudança, o grupo poderia manipular seus sets com mais sutileza. “Lidar com variáveis ​​aleatórias é, de certa forma, muito menos rígido do que lidar com conjuntos”, disse Manners. Com uma variável aleatória, “posso ajustar uma das probabilidades em uma pequena quantidade, e isso pode me dar uma variável aleatória melhor”.

Usando esta perspectiva probabilística, Green, Manners e Tao poderiam passar do trabalho com o número de elementos num conjunto para uma medição da informação contida numa variável aleatória, uma quantidade chamada entropia. A entropia não era novidade na combinatória aditiva. Na verdade, Tao tinha tentado para popularizar o conceito no final dos anos 2000. Mas ninguém ainda havia tentado usá-lo na conjectura polinomial de Freiman-Ruzsa. Green, Manners e Tao descobriram que era poderoso. Mas eles ainda não conseguiram provar a conjectura.

À medida que o grupo refletia sobre os novos resultados, eles perceberam que finalmente haviam construído um ambiente no qual as ideias adormecidas de Gowers poderiam florescer. Se medissem o tamanho de um conjunto utilizando a sua entropia, em vez do seu número de elementos, os detalhes técnicos poderiam funcionar muito melhor. “Em algum momento, percebemos que essas ideias antigas de Tim, de 20 anos atrás, tinham mais probabilidade de funcionar do que aquelas que estávamos tentando”, disse Tao. “E então trouxemos Tim de volta ao projeto. E então todas as peças se encaixam surpreendentemente bem.”

Ainda assim, havia muitos detalhes a serem descobertos antes que uma prova fosse obtida. “Foi meio tolo que nós quatro estivéssemos incrivelmente ocupados com outras coisas”, disse Manners. “Você quer publicar este ótimo resultado e contar ao mundo, mas na verdade ainda precisa redigir suas provas intermediárias.” Por fim, o grupo conseguiu avançar e, em 9 de novembro, publicaram seu artigo. Eles provaram que se A + A não é maior que k vezes o tamanho de A, Em seguida A pode ser coberto por não mais do que cerca k¹² mudanças de um subgrupo que não é maior que A. Este é um número potencialmente enorme de mudanças. Mas é um polinômio, então não cresce exponencialmente mais rápido à medida que k fica maior, como seria se k estavam no expoente.

Alguns dias depois, Tao começou a formalizar a prova. Ele executou o projeto de formalização de forma colaborativa, usando o pacote de controle de versão GitHub para coordenar contribuições de 25 voluntários em todo o mundo. Eles usaram uma ferramenta chamada Diagrama desenvolvido por Patrick Massot, um matemático da Universidade Paris-Saclay, para organizar os esforços para traduzir o que Tao chamado “Inglês Matemático” em código de computador. O Blueprint pode, entre outras coisas, criar um gráfico representando as várias etapas lógicas envolvidas na prova. Depois que todas as bolhas foram cobertas com o que Tao chamou de “lindo tom de verde”, a equipe terminou. Eles descobriram alguns pequenos erros de digitação no jornal - em uma publicação online mensagem, Tao observou que “as partes matematicamente mais interessantes do projeto eram relativamente simples de formalizar, mas foram as etapas técnicas 'óbvias' que demoraram mais”.

Marton morreu poucos anos antes de sua famosa conjectura ser provada, mas a prova ecoa sua trabalho da vida sobre entropia e teoria da informação. “Tudo funciona muito melhor quando você faz isso nesta estrutura de entropia do que na estrutura que eu estava tentando fazer”, disse Gowers. “Para mim, ainda parece um tanto mágico.”

Quanta está realizando uma série de pesquisas para melhor atender nosso público. Pegue nosso pesquisa com leitores de matemática e você estará inscrito para ganhar de graça Quanta mercadoria.