Investigador da Microsoft ajuda a provar conjetura com 31 anos

Desde 1995, uma questão sobre geometria de alta dimensão tem-se interposto entre os matemáticos e uma resposta clara sobre a forma como os passeios aleatórios exploram uma distribuição. A conjetura de Kannan–Lovász–Simonovits pergunta se, para uma ampla classe de distribuições de probabilidade, o melhor corte plano é quase tão eficaz como o melhor corte de qualquer forma. A Microsoft Research anuncia agora que dois investigadores, incluindo Xinzhi Zhang, do seu grupo de Aprendizagem Automática e Otimização, a demonstraram: a diferença entre os dois tipos de corte mantém-se abaixo de um limite fixo, qualquer que seja o número de dimensões.

Um corte plano é uma fatia de uma forma feita com uma lâmina plana, um hiperplano em termos matemáticos. Para as distribuições log-côncavas, uma família ampla de distribuições de probabilidade, a conjetura prevê que o melhor corte plano difere do melhor corte de qualquer forma em não mais do que uma constante universal, por maior que seja o número de dimensões. A geometria destes cortes determina a rapidez com que um passeio aleatório consegue explorar a distribuição, razão pela qual o problema está no centro da amostragem em alta dimensão, a família de métodos que extraem pontos aleatórios de distribuições complexas.

O problema foi reconhecido como central muito antes de ser resolvido. O Mathematical Sciences Research Institute chamou-lhe «um problema central em aberto na geometria convexa de alta dimensão» no seu Relatório Anual de 2017-18, e o Instituto Simons descreveu-o como «um dos problemas abertos mais importantes da geometria convexa». O melhor resultado conhecido, estabelecido em julho de 2026, deixava o limite crescer lentamente à medida que as dimensões aumentavam. Os autores começaram por o aperfeiçoar: na versão publicada a 1 de outubro de 2026, a dependência da dimensão reduziu-se ao logaritmo iterado, uma função que cresce muito lentamente, mas que ainda cresce, pelo que a conjetura ainda não estava resolvida.

As últimas etapas vieram de um processo pouco habitual. Trabalhando com agentes de IA num processo estruturado e dirigido por humanos, os autores exploraram mais de 100 abordagens candidatas, muitas delas envolvendo cálculos extensos com tensores de ordem superior. Uma delas produziu um novo critério que se tornou o fundamento da demonstração. O passo final foi repetir todo o refinamento recursivo em vez de o aplicar uma única vez, uma ideia inspirada no trabalho anterior dos autores sobre algoritmos rápidos para programação linear. Mostraram que os pequenos erros introduzidos em cada etapa diminuem com rapidez suficiente para que o seu total fique limitado por uma constante universal, independente da dimensão. A versão publicada a 4 de outubro de 2026 completou a demonstração. Os autores afirmam que as ferramentas de IA ajudaram a explorar, deduzir e verificar, enquanto os investigadores escolheram a direção, selecionaram as ideias e verificaram o argumento.

A afirmação tem suscitado trabalho paralelo. No mesmo dia em que a equipa da Microsoft publicou a sua demonstração completa, um grupo separado de especialistas de renome publicou uma demonstração completa que tinha desenvolvido em paralelo, referindo-se à primeira versão da Microsoft como «o passo crucial da demonstração». Uma terceira demonstração, publicada nesse dia, assenta numa ideia muito próxima. A publicação da Microsoft refere ainda que vários investigadores independentes validaram o trabalho e que se seguiu uma verificação formal assistida por computador. Não indica se o artigo já foi aceite por uma revista.

Para os investigadores que desenvolvem e analisam métodos de amostragem e otimização, a mudança está nas garantias: um limite que já não cresce com a dimensão substitui outro que crescia, ainda que lentamente. A publicação apresenta isto como a remoção de um grande obstáculo teórico à compreensão da eficiência dos algoritmos aleatorizados usados em toda a ciência e na computação. Não estabelece qualquer data para um efeito prático, nem indica se o resultado se traduzirá em ferramentas mais rápidas.