Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution

Este artículo presenta un nuevo método automatizado que combina la sustitución con una búsqueda de retroceso para demostrar que la complejidad bilineal de multiplicar matrices de $3 \times 3$sobre$\mathbb{F}_2$ es al menos 20, superando la antigua cota inferior de 19.

Lo esencial

Imagina que tienes que resolver un rompecabezas matemático muy antiguo y complicado: multiplicar dos matrices de números (piensa en ellas como tableros de cálculo) usando la menor cantidad de "pasos" o "multiplicaciones" posibles.

En el mundo de la informática, cada vez que multiplicas dos números, cuentas como un "golpe". El objetivo es encontrar la forma más eficiente de multiplicar tableros enteros. Para tableros pequeños (como de 3x3), los matemáticos llevaban décadas intentando saber cuál es el número mínimo de golpes necesario.

Este paper es como la historia de un detective (el autor, Chengu Wang) que usa una nueva estrategia de "búsqueda y sustitución" para resolver este misterio en un mundo donde solo existen dos números: el 0 y el 1 (el campo finito $F_2$, que es la base de todo lo digital).

Aquí te explico cómo lo hizo, usando analogías sencillas:

1. El Problema: El Rompecabezas de los 3x3

Imagina que tienes dos tableros de 3x3. La pregunta es: ¿Cuál es el número mínimo de multiplicaciones necesarias para obtener el resultado?
Durante años, los expertos pensaron que la respuesta era 19. Pero el autor dice: "No, es imposible hacerlo en 19. Necesitas al menos 20".

2. La Estrategia: El "Juego de las Restricciones"

Para probar que no se puede hacer en 19, el autor no intenta adivinar la solución perfecta. En su lugar, hace lo contrario: intenta destruir las soluciones malas.

Imagina que tienes una habitación llena de muebles (las posibles formas de multiplicar). El autor decide poner restricciones en la habitación:

• "¡Prohibido tener muebles en la esquina!"
• "¡Prohibido que la mesa sea simétrica!"
• "¡Prohibido que la silla esté en el centro!"

Cada vez que pone una restricción, la habitación se vuelve más pequeña y el problema más fácil de analizar.

• El truco: Si el autor puede demostrar que, incluso con todas las restricciones posibles, siempre necesitas 20 golpes, entonces la habitación original (sin restricciones) también necesita al menos 20.

3. La Herramienta: El "Espejo Mágico" (Simetría)

El autor se dio cuenta de que muchas restricciones son engañosas. Por ejemplo, prohibir la esquina superior izquierda es lo mismo que prohibir la esquina inferior derecha si giras el tablero.
Para no perder tiempo revisando lo mismo una y otra vez, usó un algoritmo de "simetría". Es como si tuviera un espejo mágico que le dice: "Oye, esa restricción que acabas de poner es idéntica a una que ya revisaste hace un minuto, ¡no la contes de nuevo!".
Esto le permitió organizar el caos en "grupos" (órbitas) y solo revisar un representante de cada grupo.

4. El Motor: Búsqueda con "Retroceso" (Backtracking)

Aquí es donde entra la magia de la computadora. El autor construyó un explorador automático:

1. Pone una restricción.
2. Comprueba: ¿Con esta restricción, el número de golpes baja de 20?
   • Si SÍ: ¡Genial! Esa restricción no sirve para probar que se necesitan 20.
   • Si NO (o si el número sigue siendo alto): ¡Bien! Significa que esa restricción nos acerca a la verdad.
3. El Retroceso: Si se atasca, el programa "deshace" la última decisión y prueba otra restricción. Es como un laberinto donde, si tocas una pared, retrocedes y pruebas otro camino.

5. La Prueba: "El Abogado y el Juez"

El programa encontró la prueba en 1.5 horas en una laptop normal.

• El Abogado (El programa de búsqueda): Es muy rápido, prueba millones de caminos, pero a veces comete errores o es complejo.
• El Juez (El verificador): Es un programa pequeño y simple que solo revisa si el Abogado siguió las reglas.
  El autor generó un "caso" (una prueba de 32 MB) que el Juez pudo verificar en 10 segundos. Esto es crucial: cualquiera puede confiar en el resultado porque el Juez es tan simple que es imposible que se equivoque.

6. El Resultado Final

Gracias a esta combinación de:

• Restricciones (poner límites al problema).
• Simetría (no repetir lo mismo).
• Búsqueda automática (probar y retroceder).
• Verificación independiente (un juez simple).

El autor demostró que multiplicar dos matrices de 3x3 en el mundo binario (0 y 1) requiere obligatoriamente 20 multiplicaciones, rompiendo el récord anterior de 19 que llevaba vigente desde 2003.

En resumen:
Imagina que intentas demostrar que no puedes cruzar un río saltando solo 19 piedras. En lugar de saltar tú mismo, construyes un robot que prueba millones de combinaciones de piedras, descarta las que son iguales por simetría, y finalmente te entrega un mapa irrefutable que dice: "Mira, aquí hay un hueco que no puedes saltar si solo tienes 19 piedras. Necesitas 20". Y lo mejor es que un juez simple puede revisar ese mapa en segundos para confirmar que el robot no mintió.

Resumen técnico

Resumen Técnico: Límites Inferiores de Complejidad para la Multiplicación de Matrices Pequeñas sobre Campos Finitos

1. El Problema

El objetivo central del trabajo es determinar el rango tensorial (complejidad bilineal) de la multiplicación de matrices pequeñas sobre el campo finito $\mathbb{F}_2$ (aritmética binaria).

• Definición: Dado el tensor de multiplicación de matrices $\langle l, m, n \rangle$, el rango tensorial $R(\langle l, m, n \rangle)$ representa el número mínimo de multiplicaciones escalares necesarias para calcular el producto de una matriz $l \times m$ por una matriz $m \times n$ utilizando un algoritmo bilineal.
• Contexto: Determinar estos límites es un problema fundamental en la teoría de la complejidad computacional. Para matrices $3 \times 3$sobre$\mathbb{F}_2$, el límite inferior conocido desde 2003 (Bläser) era 19. El autor busca probar si este límite puede ser mejorado.

2. Metodología

El autor introduce un método híbrido que combina la método de sustitución con una búsqueda sistemática por retroceso (backtracking) sobre restricciones lineales aplicadas a la primera matriz $A$ en el producto $AB = C^T$.

La metodología se estructura en los siguientes componentes clave:

• Enumeración de Órbitas de Restricciones:

  • Se consideran restricciones lineales sobre los elementos de la matriz $A$ (ej. $a_{i,j} = 0$ o $a_{i,j} = a_{k,l}$).
  • Se utilizan las simetrías del tensor de multiplicación de matrices (simetría de "sándwich", simetría cíclica y simetría de transposición) para agrupar restricciones equivalentes en órbitas.
  • Se utiliza la forma escalonada reducida por filas (RREF) y un orden lexicográfico para seleccionar representantes canónicos de cada órbita, evitando redundancias.

• Técnicas de Cota Inferior:
  Para cada órbita de restricciones, el algoritmo aplica cuatro técnicas para establecer cotas inferiores:

  1. Aplanamiento (Flattening): Se aplanan dos dimensiones del tensor para formar una matriz y se calcula su rango. El rango del tensor es al menos el máximo de estos rangos.
  2. Producto Forzado (Forced Product): Se identifican términos que pueden expresarse como un único producto. Si son linealmente independientes, se asume que deben aparecer explícitamente en el esquema de descomposición, reduciendo el tensor restante y calculando su rango.
  3. Reducción Degenerada: Si un conjunto de restricciones $X$ está contenido en otro $Y$, el rango de $T_X$ es al menos el rango de $T_Y$.
  4. Retroceso (Backtracking) Automatizado: Si las técnicas anteriores no son suficientes, se aplica una búsqueda recursiva. Se enumeran factores canónicos de $A$, se establecen a cero y se reduce el problema a una órbita con más restricciones. Si la cota conocida de la órbita reducida más el número de factores eliminados cumple el objetivo, se ha encontrado una prueba.

• Optimizaciones Computacionales:
  Para manejar la explosión combinatoria, el algoritmo implementa varias optimizaciones:

  • Multihilo: Paralelización de órbitas con el mismo número de restricciones.
  • Mapa de Restricciones (Restriction Map): Uso de tablas hash para almacenar transformaciones de simetría, evitando recalcular permutaciones de matrices completas.
  • Gestión de Memoria: Cachés locales por hilo y eliminación aleatoria de elementos cuando la caché supera un umbral para evitar desbordamiento de memoria (OOM).
  • Límite de Pasos: Se establece un límite de iteraciones para abortar búsquedas que tardan demasiado.

3. Contribuciones Clave

1. Nuevo Algoritmo de Prueba: Desarrollo de un marco automatizado que combina búsqueda por retroceso con técnicas algebraicas clásicas para probar límites inferiores de rango tensorial.
2. Prueba Automatizada: La generación de la prueba para el caso $3 \times 3$ se realiza completamente de forma automática, sin intervención manual en la lógica de la demostración final.
3. Verificación Eficiente: El sistema genera archivos de prueba que pueden ser verificados en segundos, separando la complejidad de la búsqueda de la verificación.

4. Resultados Principales

El artículo presenta los siguientes resultados sobre $\mathbb{F}_2$:

• Teorema 1: $R(\langle 3, 3, 3 \rangle) \ge 20$.

  • Esto mejora el límite inferior anterior de 19 establecido por Bläser en 2003.
  • Tiempo de ejecución: 71 minutos en un MacBook Air M4 (8 núcleos, 16 GB RAM).
  • Tamaño de la prueba: ~32 MiB.
  • Tiempo de verificación: < 10 segundos.

• Teorema 2: $R(\langle 2, 3, 4 \rangle) \ge 19$.

  • Completa la prueba de un resultado mencionado pero no demostrado formalmente por Hopcroft y Kerr en 1971.
  • Tiempo de ejecución: 110 minutos.
  • Tamaño de la prueba: < 100 KiB.

• Reproducción de Resultados: El método reproduce correctamente los límites inferiores conocidos para otras formas de matrices ($2 \times 2 \times 2$,$2 \times 2 \times 3$, etc.), validando la robustez del enfoque.

5. Significado e Impacto

• Avance en Teoría de Complejidad: El resultado $R(\langle 3, 3, 3 \rangle) \ge 20$ es un hito importante, ya que rompe una barrera de 20 años en el conocimiento de la multiplicación de matrices $3 \times 3$ binarias.
• Validación de Métodos Computacionales: Demuestra que la búsqueda exhaustiva asistida por computadora, cuando se combina con simetrías algebraicas y optimizaciones de memoria, es viable para resolver problemas de complejidad que antes requerían argumentos puramente matemáticos o heurísticos.
• Reproducibilidad: El código y los archivos de prueba están disponibles públicamente, permitiendo a la comunidad científica auditar y verificar los resultados de manera independiente.
• Escalabilidad: Aunque el enfoque actual está optimizado para $\mathbb{F}_2$, el autor nota que las mismas técnicas son aplicables a otros campos finitos, aunque con tiempos de ejecución significativamente mayores.

En resumen, este trabajo representa un paso significativo hacia la comprensión de los límites fundamentales de la multiplicación de matrices, utilizando la potencia de la computación moderna para resolver problemas algebraicos profundos.