Mathematician calls AI's claimed integer multiplication breakthrough 'plausible' after two weeks of study
The recently proposed o(n log n) integer multiplication algorithm [pdf]
David Harvey, co-author of the 2021 O(n log n) integer multiplication algorithm, assesses a new paper claiming a sub-O(n log n) bound. He hasn't read the papers himself—he asked an LLM, Claude Fable 5.1, to explain them—but after extensive questioning he tentatively believes the result may be correct. He notes the (log n)^ε improvement is exponentially larger than past gains, and reflects on AI's unsettling speed at mathematical research.
I doubt that it is possible for humans to be taken seriously as authors of mathematics research papers for much longer, for the same reason that we no longer accept written assignments from our undergraduates.
- jdb1729
> It would be good to have a formalised proof of the o(n log n) result, for example in Lean. As far as I can tell, one does not yet exist.
The result is fully formalized in Lean by @platypii and myself (on Mathlib's TM2 machine), with ongoing improvements to the exponent (currently at 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
Contributions are welcome!
- Kapura
> I have not actually read the paper. In fact, there are three closely related papers [TC26a], [TC26b], [TC26c], and I have not read any of them. I tried, but soon gave up. The math(s) dump does not appear to be strong on exposition. Instead, I asked Fable to explain [TC26a] to me. Fable seems to understand the argument and thinks that it is correct.
this does not feel like a healthy place to be
- kenferry
> There is one other aspect of the situation that I would like to emphasise. After two weeks of very
hard work, I have managed to understand only a small fraction of [TC26a]. When I ask Fable about
the paper, it seems to read and understand the whole thing in just a few minutes, even starting
from a fresh context. I know that some readers may be uncomfortable with my anthropomorphic
terminology, but I believe that “understand” is accurate, in the sense that the LLM seems to be able
to correctly and lucidly answer all kinds of questions about the paper, including about some very
fiddly technical details. That is exactly how I would tell that a human colleague has “understood”
something. This chasm between human and LLM “speed of thought” is unsettling to say the least.
This is very odd, because it just doesn't match my experience with these systems at all. Yes, they do generally SOUND confident, but code (say) that's hard for me to understand is usually hard for the machine to understand as well, and while it is more indefatigable than I am, it's not brighter.
This mathematician is in a very good place to evaluate whether Fable gets it or not, but it's weird and counter to my experience.
- jdb1729
> The new result does not directly imply new complexity bounds for polynomial multiplication over a fixed finite field, say multiplication in F2[x]. The state of the art for this problem is an algorithm that multiplies polynomials of degree n in time O(n log n 4^log*(n)) [HvdH19].
@platypii and I obtained a Lean proof of the same improvement for DFT over prime-order finite fields (yielding polynomial multiplication via the convolution theorem): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
- flebron
Note in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.
- CH-Abhinav
New here but how does this help in general? Most of the time we use GEMM over Strassen even though time complexity is lower. Just ask idk anything :)
- kleiba2
Interesting that AI apparently doesn't write papers for humans: even experts struggle to understand them. But other AIs do. So AI basically writes papers for other AIs.
- yaoke259
Awesome write up and intro by a fellow Sydney-sider, kept me hooked! As someone who's not a maths wizard, the technical details flew by my head but the prose allowing me to empathise deeply with those in the field was very enlightening. I never realised how big of a deal the maths dump was and how much it has shaken up the field. I guess we are all just trying to figure out this whole "intelligence on tap" thing together.