O número 15 descreve o limite secreto de uma grade infinita

Como estudante de graduação na Universidade do Chile, Bernardo Subercaseaux teve uma visão obscura de usar computadores para fazer matemática. Parecia antitético à verdadeira descoberta intelectual.

“Existe algum instinto ou reação instintiva contra o uso de computadores para resolver seus problemas, como se isso fosse contra a beleza ideal ou a elegância de um argumento fantástico”, disse ele.

Mas então, em 2020, Subercaseaux se apaixonou e, como costuma acontecer, suas prioridades mudaram. O objeto de sua obsessão era uma pergunta que ele viu em um fórum online. A maioria dos problemas ele examinou e esqueceu, mas este chamou sua atenção. Ele deslizou para a direita.

“A primeira coisa que fiz foi curtir a postagem no grupo do Facebook, esperando receber uma notificação mais tarde, quando alguém postasse uma solução”, disse ele.

A questão era sobre preencher uma grade infinita com números. Não era, como se viu, o tipo de problema que se resolve de brincadeira. Para isso, Subercaseaux teve que deixar o Chile para fazer pós-graduação na Carnegie Mellon University.

Lá, em agosto de 2021, teve um encontro fortuito com Marijn Heule, um cientista da computação que usa enorme poder de computação para resolver questões matemáticas difíceis. Subercaseaux perguntou a Heule se ele queria tentar resolver o problema, dando início a uma colaboração que culminou em janeiro deste ano em uma prova que pode ser resumido em um único número: 15.

De todas as maneiras possíveis

Em 2002, Wayne Godard da Universidade de Clemson e alguns matemáticos que pensavam como eles estavam cuspindo problemas em combinatória, tentando encontrar novas reviravoltas nas principais questões do campo sobre colorir mapas dadas certas restrições.

Por fim, eles chegaram a um problema que começa com uma grade, como uma folha de papel quadriculado que dura para sempre. O objetivo é preenchê-lo com números. Há apenas uma restrição: a distância entre cada ocorrência do mesmo número deve ser maior que o próprio número. (A distância é medida somando a separação vertical e horizontal, uma métrica conhecida como distância de “taxicab” pela forma como se assemelha ao movimento em ruas urbanas gradeadas.) Um par de 1s não pode ocupar células adjacentes, que têm uma distância de táxi de 1, mas eles podem ser colocados em células diretamente diagonais, que têm uma distância de 2.

Inicialmente, Goddard e seus colaboradores queriam saber se era possível preencher uma grade infinita com um conjunto finito de números. Mas quando ele e seus quatro colaboradores publicou este problema de “coloração de embalagem” na revista Ars Combinatorial em 2008, eles provaram que pode ser resolvido usando 22 números. Eles também sabiam que não havia como resolver isso com apenas cinco números. Isso significava que a resposta real para o problema - o número mínimo de números necessários - estava em algum lugar no meio.

Os pesquisadores não preencheram uma grade infinita. Eles não precisavam. Em vez disso, basta pegar um pequeno subconjunto da grade - digamos um quadrado de 10 por 10 - preenchê-lo com números e mostrar que as cópias do subconjunto preenchido podem ser colocadas próximas umas das outras, da mesma forma que você cobriria um chão com cópias de um azulejo.

Quando Subercaseaux soube do problema, ele começou a procurar ladrilhos usando papel e caneta. Ele esboçava grades de números, riscava e tentava de novo. Ele logo se cansou dessa abordagem e pediu a um amigo que projetasse uma ferramenta baseada na Web que se assemelhasse ao jogo Minesweeper e permitisse que ele testasse combinações mais rapidamente. Depois de mais algumas semanas de trabalho, ele se convenceu de que não havia como preencher uma grade com oito números, mas não conseguiu ir além disso - havia muitas formas potenciais que os ladrilhos poderiam assumir e muitos maneiras diferentes de preenchê-los com números.

O problema, como ficaria claro mais tarde, é que é muito mais difícil mostrar que a grade não pode ser coberta por um certo conjunto de números do que mostrar que pode. “Não é apenas mostrar que uma maneira não funciona, é mostrar que todas as maneiras possíveis não funcionam”, disse Goddard.

Depois que Subercaseaux começou na CMU e convenceu Heule a trabalhar com ele, eles rapidamente encontraram uma maneira de cobrir a grade com 15 números. Eles também foram capazes de descartar a possibilidade de resolver o problema com apenas 12 números. Mas seus sentimentos de triunfo duraram pouco, pois perceberam que haviam apenas reproduzido resultados que já existiam há muito tempo: já em 2017, os pesquisadores sabiam que a resposta não era menor que 13 ou maior que 15 .

Para um aluno de graduação do primeiro ano que convenceu um professor importante a trabalhar em seu problema com animais de estimação, foi uma descoberta perturbadora. “Fiquei horrorizado. Eu basicamente trabalhei por vários meses em um problema sem perceber isso e, pior ainda, fiz Marijn perder tempo com isso!” Subercaseaux escreveu em um post de blog recapitulando seu trabalho.

Heule, no entanto, achou revigorante a descoberta de resultados anteriores. Demonstrou que outros pesquisadores acharam o problema importante o suficiente para trabalhar e confirmou para ele que o único resultado que valia a pena obter era resolver o problema completamente.

“Depois que descobrimos que havia 20 anos de trabalho no problema, isso mudou completamente o quadro”, disse ele.

Evitando o Vulgar

Ao longo dos anos, Heule fez carreira encontrando maneiras eficientes de pesquisar entre as vastas combinações possíveis. Sua abordagem é chamada de solução SAT - abreviação de "satisfabilidade". Envolve a construção de uma fórmula longa, chamada de fórmula booleana, que pode ter dois resultados possíveis: 0 ou 1. Se o resultado for 1, a fórmula é verdadeira e o problema está resolvido.

Para o problema de coloração de embalagem, cada variável na fórmula pode representar se uma determinada célula está ocupada por um determinado número. Um computador procura maneiras de atribuir variáveis ​​para satisfazer a fórmula. Se o computador puder fazer isso, você sabe que é possível empacotar a grade nas condições que você definiu.

Infelizmente, uma codificação direta do problema de coloração de empacotamento como uma fórmula booleana pode se estender a muitos milhões de termos - um computador, ou mesmo uma frota de computadores, pode rodar para sempre testando todas as diferentes maneiras de atribuir variáveis ​​dentro dele.

“Tentar fazer essa força bruta levaria até que o universo terminasse se você fizesse isso ingenuamente”, disse Goddard. “Então você precisa de algumas simplificações legais para reduzi-lo a algo que seja possível.”

Além disso, toda vez que você adiciona um número ao problema de coloração de embalagem, ele se torna cerca de 100 vezes mais difícil, devido à forma como as combinações possíveis se multiplicam. Isso significa que, se um banco de computadores trabalhando em paralelo pudesse descartar 12 em um único dia de computação, eles precisariam de 100 dias de tempo de computação para descartar 13.

Heule e Subercaseaux consideravam a ampliação de uma abordagem computacional de força bruta vulgar, de certa forma. “Tivemos várias ideias promissoras, então adotamos a mentalidade de 'Vamos tentar otimizar nossa abordagem até que possamos resolver esse problema em menos de 48 horas de computação no cluster'”, disse Subercaseaux.

Para fazer isso, eles tiveram que encontrar maneiras de limitar o número de combinações que o cluster de computação tinha que tentar.

“[Eles] não querem apenas resolvê-lo, mas resolvê-lo de uma maneira impressionante”, disse Alexandre Soifer da Universidade do Colorado, Colorado Springs.

Heule e Subercaseaux reconheceram que muitas combinações são essencialmente as mesmas. Se você está tentando preencher uma peça em forma de diamante com oito números diferentes, não importa se o primeiro número que você coloca é um para cima e um para a direita do quadrado central, ou um para baixo e outro para a esquerda. o quadrado central. Os dois posicionamentos são simétricos entre si e restringem seu próximo movimento exatamente da mesma maneira, então não há razão para verificar os dois.

Heule e Subercaseaux adicionaram regras que permitiram ao computador tratar combinações simétricas como equivalentes, reduzindo o tempo total de busca por um fator de oito. Eles também empregaram uma técnica que Heule havia desenvolvido em um trabalho anterior chamado cubo e conquista, o que lhes permitiu testar mais combinações em paralelo umas com as outras. Se você sabe que uma determinada célula deve conter 3, 5 ou 7, pode dividir o problema e testar cada uma das três possibilidades simultaneamente em diferentes conjuntos de computadores.

Em janeiro de 2022, essas melhorias permitiram que Heule e Subercaseaux descartassem 13 como a resposta para o problema de coloração de embalagem em um experimento que exigia menos de dois dias de tempo de computação. Isso os deixou com duas respostas possíveis: 14 ou 15.

uma grande vantagem

Para descartar 14 – e resolver o problema – Heule e Subercaseaux tiveram que encontrar maneiras adicionais de acelerar a busca por computador.

Inicialmente, eles escreveram uma fórmula booleana que atribuía variáveis ​​a cada célula individual na grade. Mas em setembro de 2022, eles perceberam que não precisavam proceder célula por célula. Em vez disso, eles descobriram que era mais eficaz considerar pequenas regiões compostas por cinco células na forma de um sinal de adição.

Eles reescreveram sua fórmula booleana para que diversas variáveis ​​representassem questões como: Existe um 7 em algum lugar dentro desta região em forma de mais? O computador não precisava identificar exatamente onde na região o 7 poderia estar. Ele só precisava determinar se estava lá ou não – uma questão que requer significativamente menos recursos computacionais para responder.

“Ter variáveis ​​que falam apenas sobre pontos positivos em vez de locais específicos acabou sendo muito melhor do que falar sobre eles em células específicas”, disse Heule.

Ajudados pela eficiência da pesquisa positiva, Heule e Subercaseaux descartaram 14 em um experimento de computador em novembro de 2022 que acabou levando menos tempo para ser executado do que o que eles usaram para descartar 13. Eles passaram os quatro meses seguintes verificando se a conclusão do computador estava correta - quase tanto tempo quanto eles gastaram permitindo que o computador chegasse a essa conclusão em primeiro lugar.

“Foi gratificante pensar que o que geramos como uma espécie de questão secundária em algum diário aleatório fez com que grupos de pessoas gastassem, como se viu, meses de seu tempo tentando descobrir como resolvê-lo”, Goddard disse.

Para Subercaseaux, foi o primeiro triunfo real de sua carreira de pesquisador. E embora possa não ter sido o tipo de descoberta que idealizou quando pensou em trabalhar com matemática, ele descobriu que, no final, tinha suas próprias recompensas intelectuais.

“Não é entender a forma em que você me dá uma lousa e eu posso te mostrar porque é 15”, disse ele. “Mas entendemos como funcionam as restrições do problema, como é melhor ter um 6 aqui ou um 7 ali. Nós ganhamos muita compreensão intuitiva.”