David Harvey: el algoritmo de multiplicación de enteros o(n log n) es plausible, aunque no lo entiendo del todo
The recently proposed o(n log n) integer multiplication algorithm [pdf]
David Harvey, coautor del algoritmo O(n log n) de 2021, analiza la reciente propuesta de multiplicación de enteros en o(n log n) atribuida a un modelo de IA de una gran tecnológica. Aunque no ha leído los artículos originales, conversó con Claude Fable 5.1 para comprender el argumento y considera que el resultado es posiblemente correcto. La mejora (log n)^ε, con ε = 2^-182, es minúscula en apariencia pero exponencialmente mayor que avances previos. Harvey reflexiona sobre el impacto de la IA en la investigación matemática y la velocidad de comprensión de las máquinas frente a los humanos.
No culpo a la Compañía por haber llegado primero. Quién llegó primero es un detalle irrelevante, una nota a pie de página histórica.
- jdb1729
> Sería bueno tener una prueba formalizada del resultado o(n log n), por ejemplo en Lean. Hasta donde sé, todavía no existe una.
El resultado está completamente formalizado en Lean por @platypii y yo mismo (en la máquina TM2 de Mathlib), con mejoras continuas en el exponente (actualmente en 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
¡Las contribuciones son bienvenidas!
- Kapura
> En realidad no he leído el artículo. De hecho, hay tres artículos estrechamente relacionados [TC26a], [TC26b], [TC26c], y no he leído ninguno de ellos. Lo intenté, pero pronto me di por vencido. El volcado de matemáticas no parece ser fuerte en exposición. En cambio, le pedí a Fable que me explicara [TC26a]. Fable parece entender el argumento y cree que es correcto.
esto no parece un lugar saludable para estar
- kenferry
> Hay otro aspecto de la situación que me gustaría enfatizar. Después de dos semanas de muy
trabajo duro, he logrado entender solo una pequeña fracción de [TC26a]. Cuando le pregunto a Fable sobre
el artículo, parece leer y entender todo en solo unos minutos, incluso partiendo
de un contexto nuevo. Sé que algunos lectores pueden sentirse incómodos con mi terminología
antropomórfica, pero creo que "entender" es preciso, en el sentido de que el LLM parece ser capaz
de responder correcta y lúcidamente todo tipo de preguntas sobre el artículo, incluidas algunas
muy intricadas cuestiones técnicas. Así es exactamente como yo diría que un colega humano ha "entendido"
algo. Este abismo entre la "velocidad de pensamiento" humana y la del LLM es inquietante, cuanto menos.
Esto es muy extraño, porque simplemente no coincide en absoluto con mi experiencia con estos sistemas. Sí, generalmente SUENAN seguros, pero el código (digamos) que es difícil de entender para mí suele ser también difícil de entender para la máquina, y aunque es más incansable que yo, no es más brillante.
Este matemático está en una muy buena posición para evaluar si Fable lo entiende o no, pero es raro y contrario a mi experiencia.
- jdb1729
> El nuevo resultado no implica directamente nuevas cotas de complejidad para la multiplicación de polinomios sobre un cuerpo finito fijo, digamos la multiplicación en F2[x]. El estado del arte para este problema es un algoritmo que multiplica polinomios de grado n en tiempo O(n log n 4^log*(n)) [HvdH19].
@platypii y yo obtuvimos una prueba en Lean de la misma mejora para la DFT sobre cuerpos finitos de orden primo (lo que produce la multiplicación de polinomios mediante el teorema de convolución): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
- flebron
Nota que en este caso el título dice "O(n log n)", pero la parte importante es que esto es "o(n log n)", no solo "O(n log n)". Lo primero es un subconjunto estricto de lo segundo. Ya sabíamos cómo multiplicar dos enteros de n bits en tiempo O(n log n), mediante la FFT.
- CH-Abhinav
Soy nuevo aquí, pero ¿cómo ayuda esto en general? La mayoría de las veces usamos GEMM en lugar de Strassen aunque la complejidad temporal sea menor. Solo pregunto, no sé nada :)
- kleiba2
Es interesante que la IA aparentemente no escribe artículos para humanos: incluso los expertos luchan por entenderlos. Pero otras IA sí. Así que básicamente la IA escribe artículos para otras IA.
- yaoke259
¡Excelente artículo e introducción de un compañero de Sídney, me mantuvo enganchado! Como alguien que no es un mago de las matemáticas, los detalles técnicos me pasaron por encima, pero la prosa me permitió empatizar profundamente con los que están en el campo, fue muy esclarecedor. Nunca me di cuenta de lo importante que era el volcado de matemáticas y cuánto ha sacudido el campo. Supongo que todos estamos tratando de entender esto de la "inteligencia a demanda" juntos.