alt Hacker NewsInteger multiplication below n log n
Comments
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.
I laughed out loud at the n lg n ^ (1 - 2^{-182}). It is so funny.
For the uninitiated, why is this interesting given it doesn't seem to be so much below the threshold?
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
Why is an openai release in .pdf? Isn't all ai in .md now?
I wonder if the AI spent extra time on this without being told to
I mean, cracking anything below the nlogn bound implies that there might be much more room for improvement. Often a very minor win over the theory opens up enough extra attention to later truly move the needle.
This is pretty remarkable, IF someone can understand it :)
There are several of these "exponent used to be 1.0, we reduced it to 0.9999999" results in the "catalog".
There are also a bunch of other stinkers, like building a Turing machine out of Navier-Stokes fluids -- except that it only works if you can encode literally infinite amounts of data in the relative positions of two particles. I.e. assuming physics is based on set-theoretic real numbers, something we've known is wildly false for over a century: https://en.wikipedia.org/wiki/Banach-Tarski_paradox
Just like vuln reporting, the AI industry has put zero effort into triage here, and the models are really good at making their findings sound more important than they really are.
The cynic in me suspects this is a smokescreen for the Navier-Stokes tokenstream plagarism fiasco.
I love this, entirely separate from any applications or even understanding. It's incredible that we needed this trillion-dollar technology to learn about a faster way to multiply two numbers!
Math is incredibly rich, and even the simplest things have insanely complicated structure when you zoom in. However this all ends up, math is bigger than LLMs, and the people who claim it is getting "solved" and we are running out of open problems haven't stared into the abyss enough.
We shaved a whole: 1/6129982163463555433433388108601236734474956488734408704 off the nlogn