OpenAI Claims Integer Multiplication Below n log n
A preprint on OpenAI's math GitHub repository presents an algorithm for integer multiplication with complexity below n log n. The repository contains hundreds of other mathematical preprints, but this one stands out for challenging a long-standing barrier in computational complexity.
Integer multiplication below n log n
- TGower
We shaved a whole: 1/6129982163463555433433388108601236734474956488734408704 off the nlogn
- shmoil
I laughed out loud at the n lg n ^ (1 - 2^{-182}). It is so funny.
- wk_end
Is there an associated machine-checked proof of this?
We're in full vibe-code mode at work, so I understand both how powerful frontier models can be and how often they can over-confidently state subtly (or not so subtly) wrong things, even when you're taking great efforts to try to keep that from happening.
So without a Lean development or extensive human verification, I guess I'm a little bit skeptical, and even sort of hoping this is wrong - not just because of my not so positive feelings about AI, but by my disposition towards beauty in math. n log n is an awful lot nicer than what we have here.
- MinimalAction
For the uninitiated, why is this interesting given it doesn't seem to be so much below the threshold?
- 12390asdjkas
this is perfect for when i have an array of at LEAST 2^118000 items
i will NEVER care about proposed multiplication speedups unless they are truly generalized