22 MULTIPLICAÇÕES, NEM UMA A MENOS

Conflito de interesses. Os autores afirmam que agentes de IA — o Claude, da Anthropic — escreveram, sob a direção deles, o código de busca e as provas em Lean que não precisam de um auditor humano, enquanto a parte que um humano precisa auditar foi concebida pelos autores. Este artigo também foi escrito pelo Claude.

Multiplicar duas grades quadradas de números — matrizes — do jeito escolar exige n³ multiplicações para grades de n linhas e n colunas. Strassen mostrou que duas matrizes 2 × 2 podem ser multiplicadas com 7 multiplicações em vez de 8. O truque pode ser aplicado de forma recursiva: corta-se uma matriz grande em quatro blocos, trata-se cada bloco como um único número e repete-se. O custo então cresce como n^2,807 em vez de n³. Segundo o artigo, essa receita 2 × 2 foi provada ótima em 1971.

A mesma ideia funciona para qualquer tamanho fixo. Uma receita que multiplica duas matrizes 3 × 3 com r multiplicações, e que continua funcionando quando as entradas são blocos, dá um custo que cresce como n elevado a log₃ r. Uma conta simples mostra o que está em jogo: tal receita supera Strassen exatamente quando r é 21 ou menos, e perde com 22 ou mais. A melhor receita 3 × 3 conhecida, de Laderman, usa 23 multiplicações e não foi melhorada desde 1976.

Uma porta que ficou entreaberta

O melhor número possível para um dado problema se chama seu posto (rank). Os limites inferiores do posto da multiplicação 3 × 3 subiram devagar: 19 em 2003, depois 20 em março de 2026, calculado por Wang num sistema numérico minúsculo, com apenas 0 e 1, em que 1 + 1 = 0. Em setembro de 2026, Wang e uma equipe liderada por Yang chegaram a 21 de forma independente, com dez dias de diferença. Mas 21 ainda deixava espaço para uma receita 3 × 3 mais rápida que a de Strassen.

Isaac Rudich, da Polytechnique Montréal e da Carnegie Mellon University, e Louis-Martin Rousseau, da Polytechnique Montréal, levaram agora o limite a 22.

Teorema 1. Todo algoritmo que multiplica duas matrizes 3 × 3 com constantes inteiras, e que pode ser aplicado recursivamente a blocos de qualquer tamanho, usa pelo menos 22 multiplicações.

Logo, nenhum algoritmo desse tipo pode fazer melhor que cerca de n^2,814 — e nenhum pode superar o método 2 × 2 de Strassen.

496 quebra-cabeças menores

A prova se apoia numa tabela concebida por Wang, que divide o problema difícil em 496 mais fáceis. Cada um acrescenta “condições” à primeira matriz — por exemplo, que certas entradas somem zero. Quanto mais condições, mais fácil o problema, até o caso trivial em que a matriz é toda de zeros.

Os autores primeiro construíram um programa de busca exata que lhes dava a resposta verdadeira de cada quebra-cabeça antes de tentarem prová-la. Essas respostas serviram de mapa: mostravam quais limites inferiores valia a pena perseguir. No fim, a prova deles limita todos os 496 quebra-cabeças, resolve 359 deles exatamente — contra 195 nos resultados mais recentes de Wang — e eleva o limite inferior de 252. Um teorema de “colagem” próprio combina receitas de dois quebra-cabeças mais fáceis numa receita para um terceiro, e forneceu 145 dos limites superiores.

Duas condições importam no enunciado final. Constantes inteiras: uma receita com constantes inteiras, lida no sistema de 0 e 1, continua sendo uma receita válida sem multiplicações a mais, então o limite se transfere. Blocos: sem essa exigência, existem atalhos. O algoritmo 3 × 3 de Rosowski, citado no artigo, precisa de apenas 21 multiplicações, mas depende de os números comutarem e não pode ser aplicado recursivamente.

Uma prova verificada por máquina

A prova está escrita em Lean, uma linguagem de programação em que um teorema só compila se cada passo for verificado. A prova completa tem cerca de um milhão de linhas distribuídas em 3.521 módulos, e sua verificação leva 11,1 horas num único núcleo de processador. Ninguém precisa ler tudo. Um auditor lê uma biblioteca de cerca de 1.000 linhas, escrita pelos autores antes de existir qualquer prova, que define o que é uma receita de multiplicação e enuncia o teorema; o núcleo do Lean verifica o resto, e um verificador independente pode reproduzir o resultado.

Os autores também observam que os agentes de IA pesquisaram a literatura: verificaram que cada referência existe, “mas não que cada uma contém exatamente a ideia que lhe atribuímos”.

A última lacuna

Resta uma pergunta: existe uma receita 3 × 3 com 22 multiplicações, ou as 23 de Laderman são o verdadeiro mínimo? Os autores esperam que a lacuna “seja fechada em breve” e vão divulgar o código de busca quando isso acontecer, ou quando o artigo for aceito para publicação. O limite também deixa de lado receitas com constantes não inteiras.