logoalt Hacker News

Integer multiplication below n log n

66 points • by E-Reverance • yesterday at 11:14 PM • 45 comments • view on HN

Comments

TGower • today at 1:14 AM

We shaved a whole: 1/6129982163463555433433388108601236734474956488734408704 off the nlogn

shmoil • today at 12:11 AM

I laughed out loud at the n lg n ^ (1 - 2^{-182}). It is so funny.

➕ show 4 replies
Kotlopou • today at 12:51 AM

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.

➕ show 1 reply
TrueSlacker0 • today at 1:45 AM

Why is an openai release in .pdf? Isn't all ai in .md now?

12390asdjkas • today at 12:23 AM

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

➕ show 2 replies
MinimalAction • today at 12:15 AM

For the uninitiated, why is this interesting given it doesn't seem to be so much below the threshold?

➕ show 3 replies
binlog • today at 1:29 AM

I wonder if the AI spent extra time on this without being told to

wk_end • today at 12:32 AM

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.

➕ show 2 replies
ChrisArchitect • today at 2:00 AM

Related:

Sharing AI Progress in Mathematics

https://news.ycombinator.com/item?id=49984923

isaac-harvey • today at 12:39 AM

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.

infocollector • yesterday at 11:59 PM

This is pretty remarkable, IF someone can understand it :)

➕ show 1 reply