22 MULTIPLICACIONES, NI UNA MENOS
Conflicto de intereses. Los autores declaran que agentes de IA —Claude, de Anthropic— escribieron, bajo su dirección, el código de búsqueda y las demostraciones en Lean que no requieren un auditor humano, mientras que la parte que un humano debe auditar fue diseñada por los autores. Este artículo también está escrito por Claude.
Multiplicar dos cuadrículas cuadradas de números —matrices— por el método escolar requiere n³ multiplicaciones para cuadrículas de n filas y n columnas. Strassen demostró que dos matrices de 2 × 2 pueden multiplicarse con 7 multiplicaciones en lugar de 8. El truco puede aplicarse de forma recursiva: se corta una matriz grande en cuatro bloques, se trata cada bloque como si fuera un solo número y se repite. El coste crece entonces como n^2,807 en lugar de n³. Según el artículo, esta receta de 2 × 2 se demostró óptima en 1971.
La misma idea funciona para cualquier tamaño fijo. Una receta que multiplica dos matrices de 3 × 3 con r multiplicaciones, y que sigue funcionando cuando las entradas son bloques, da un coste que crece como n elevado a log₃ r. Una aritmética sencilla fija lo que está en juego: tal receta supera a Strassen exactamente cuando r es 21 o menos, y pierde con 22 o más. La mejor receta de 3 × 3 conocida, debida a Laderman, usa 23 multiplicaciones y no se ha mejorado desde 1976.
Una puerta que seguía entreabierta
El mejor número posible para un problema dado se llama su rango. Las cotas inferiores del rango de la multiplicación de 3 × 3 subieron lentamente: 19 en 2003, luego 20 en marzo de 2026, calculado por Wang sobre un minúsculo sistema numérico con solo 0 y 1, donde 1 + 1 = 0. En septiembre de 2026, Wang y un equipo dirigido por Yang llegaron a 21 de forma independiente, con diez días de diferencia. Pero 21 todavía dejaba sitio para una receta de 3 × 3 más rápida que la de Strassen.
Isaac Rudich, de Polytechnique Montréal y la Universidad Carnegie Mellon, y Louis-Martin Rousseau, de Polytechnique Montréal, acaban de llevar la cota a 22.
Teorema 1. Todo algoritmo que multiplica dos matrices de 3 × 3 con constantes enteras, y que puede aplicarse de forma recursiva a bloques de cualquier tamaño, usa al menos 22 multiplicaciones.
Así que ningún algoritmo de este tipo puede hacerlo mejor que aproximadamente n^2,814, y ninguno puede superar el método 2 × 2 de Strassen.
496 rompecabezas más pequeños
La demostración se apoya en una tabla ideada por Wang, que divide el problema difícil en 496 problemas más fáciles. Cada uno añade «condiciones» sobre la primera matriz; por ejemplo, que ciertas de sus entradas sumen cero. Cuantas más condiciones, más fácil es el problema, hasta llegar al caso trivial en que la matriz es toda ceros.
Los autores construyeron primero un programa de búsqueda exacta que les daba la respuesta verdadera de cada rompecabezas antes de intentar demostrarla. Esas respuestas sirvieron de mapa: indicaban qué cotas inferiores merecía la pena perseguir. Al final, su demostración acota los 496 rompecabezas, resuelve 359 de ellos exactamente —frente a 195 en los últimos resultados de Wang— y eleva la cota inferior de 252. Un teorema de «pegado» propio combina recetas de dos rompecabezas más fáciles en una receta para un tercero, y aportó 145 de las cotas superiores.
Dos condiciones importan en el enunciado final. Constantes enteras: una receta con constantes enteras, leída en el sistema numérico de 0 y 1, sigue siendo una receta válida sin más multiplicaciones, de modo que la cota se transfiere. Bloques: sin ese requisito, existen atajos. El algoritmo de 3 × 3 de Rosowski, citado en el artículo, necesita solo 21 multiplicaciones, pero depende de que los números conmuten y no puede aplicarse de forma recursiva.
Una demostración verificada por una máquina
La demostración está escrita en Lean, un lenguaje de programación en el que un teorema solo compila si cada paso está verificado. La demostración completa ocupa cerca de un millón de líneas repartidas en 3.521 módulos, y tarda 11,1 horas en verificarse en un solo núcleo de procesador. Nadie necesita leerla entera. Un auditor lee una biblioteca de unas 1.000 líneas, escrita por los autores antes de que existiera ninguna demostración, que define qué es una receta de multiplicación y enuncia el teorema; el núcleo de Lean comprueba el resto, y un verificador independiente puede reproducir el resultado.
Los autores señalan también que los agentes de IA buscaron en la bibliografía: comprobaron que cada referencia existe, «pero no que cada una contenga exactamente la idea que le atribuimos».
La última brecha
Queda una pregunta: ¿existe una receta de 3 × 3 con 22 multiplicaciones, o es el 23 de Laderman el verdadero mínimo? Los autores esperan que la brecha «se cierre de forma inminente», y publicarán su código de búsqueda cuando ocurra, o cuando el artículo sea aceptado para su publicación. La cota deja también de lado las recetas con constantes no enteras.