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.
Agree 100% on wanting machinr verification of AI generated math.
But in regards to beauty, i feel like multiplication already has a lot of non beautiful exponents. Best known matrix multiply is O(n^2.371). For integer factorization, the inverse of this problem, general number field sieve is a crazy subexponential.
If factorization is just barely subexponential, is it really that surprising that multiplication is just barely sub n lg n ?
This also reaffirms my (wishful) thinking that if there’s a way to do FTL communication it’ll be something with an absurdly tiny factor like 2^-182 with a slight asymmetry in a probability somewhere.
Then you’re not violating FTL, just gaining a very slight chance that you might know something FTL – probably.
Given that c is the speed of causality itself, FTL communications would effectively be like predicting the future.
From that angle, beating light speed by some absurdly tiny factor would probably correspond to a means of predicting the future at some almost absurdly tiny factor better than random guessing.
Edit: Actually...it doesn't make sense to call this FTL communication, it's just predicting the future state of a system given some previous state. FTL comms would have to be predicting the future state of a system without information about the previous state.
Practically speaking predictive modeling would be a means of achieving a similar effect as FTL comms, kind of like branch prediction in processors or speculative decoding in LLMs, but that wouldn't actually be FTL comms.
Exactly! It’s not forbidden, just very unlikely and would be very strange.
It’d likely involve exponentially more energy as well. It’d be a good sci-if plot point if FTL communications required machines the size of Jupyter to get a few milliseconds of prescience.
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.
Sure, all of this might end up being very unpleasant, and I'm glad not to be a mathematician right now. But that's still better than a future where there aren't even any questions left that we can understand and an AI can't solve.
Also, it still seems that AI has a much different style from humans, with more brute force and using obscure literature results, and the future might still end up human/AI complementary. We aren't in an AlphaZero situation where the AI learns everything through self-play. (Yet? But we don't even seem to be moving that way much? Can anybody qualified help out?) Things are just moving really fast now and it's hard to process everything.
If you view them as "theories of computational limits" instead of "proposed practical speedups" they can be a lot more interesting.
It's most interesting when the lower bound can actually be proven. In lack of that, we have to guess what the best possible algorithm might yield (generalized or not). This tells us that need not be O(n log n) and we have the opportunity to still find better algorithms than we typically thought would be possible. This does the latter, which is interesting, but it just leaves us to hunger more for what the real limit must be :).
i understand this, but it always feels like we are being tricked when they say "integer multiplication below nlogn" because we intuit that that must mean "faster integer multiplication below nlogn EVERYWHERE!". but in reality it comes with 15 asterisks about the conditions that must be true for their statement to hold true.
Your issue is that I am viewing this proof as what it really is in terms of progressing the field and not from an imaginative perspective. I think that it is important to ground our selves somewhat in reality when discussing research like this because at the end of the day open ai is not doing for fun either.
openai wants to show the world what their product can do and i am simply not impressed
O(n lg n) is a bit of a threshold value. For a lot of algorithms, this is the best you can do, even in theory (similar to how O(n^2) is also a threshold for many algorithms). So for many algorithms, people stop trying when they get close to O(n lg n) on the belief that you'll never do better than that.
The fact that you can in principle go faster than n lg n, even if just by an almost imperceptible amount, is kind of surprising. It raises the question of, if n lg n isn't the limit, what is? How far down can we get the speed? If we can get it a little past n lg n, maybe we can go a lot further.
[or at least that is my understanding. not a theoretical computer scientist]
It's like when Tony Hawk did a 900 for the first time. Now 900s in skateboarding aren't a big deal, kids can do it now. It was proving to the world what was possible was the mental hurdle that inspires others to actually try at the problem harder.
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.
It's 50 pages and cites this other paper in the same repo:
OpenAI. An explicit power saving for the exact discrete Fourier transform.
Here's a random excerpt:
8.3 The middle transform and the final permutation
The factor QFt in (35) can be computed from a cyclic convolution and two pointwise phase multiplications. The chirp identity below performs the frequency change in Q without applying Q as a separate permutation of the array. The second identity shows how the retained source permutation R cancels when computing a convolution. Here ∗ denotes cyclic convolution on the product of the coordinate groups and a dot denotes coordinatewise multiplication.
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.
Agree 100% on wanting machinr verification of AI generated math.
But in regards to beauty, i feel like multiplication already has a lot of non beautiful exponents. Best known matrix multiply is O(n^2.371). For integer factorization, the inverse of this problem, general number field sieve is a crazy subexponential.
If factorization is just barely subexponential, is it really that surprising that multiplication is just barely sub n lg n ?
Matrix multiplication is <=O(n^2.25) actually... [1]
1. https://github.com/openai/math/blob/main/preprints/Matrix-Mu...
We can just wait for whomever they stole THIS proof from to come forward with threatening emails sent by OpenAI.
I laughed out loud at the n lg n ^ (1 - 2^{-182}). It is so funny.
Wowzers!
This also reaffirms my (wishful) thinking that if there’s a way to do FTL communication it’ll be something with an absurdly tiny factor like 2^-182 with a slight asymmetry in a probability somewhere.
Then you’re not violating FTL, just gaining a very slight chance that you might know something FTL – probably.
Given that c is the speed of causality itself, FTL communications would effectively be like predicting the future.
From that angle, beating light speed by some absurdly tiny factor would probably correspond to a means of predicting the future at some almost absurdly tiny factor better than random guessing.
Edit: Actually...it doesn't make sense to call this FTL communication, it's just predicting the future state of a system given some previous state. FTL comms would have to be predicting the future state of a system without information about the previous state.
Practically speaking predictive modeling would be a means of achieving a similar effect as FTL comms, kind of like branch prediction in processors or speculative decoding in LLMs, but that wouldn't actually be FTL comms.
I think that is entirely expected from what we know of modern physics. It doesn't say you can't do it, just things are very weird if you can.
Exactly! It’s not forbidden, just very unlikely and would be very strange.
It’d likely involve exponentially more energy as well. It’d be a good sci-if plot point if FTL communications required machines the size of Jupyter to get a few milliseconds of prescience.
If there was a way to do FTL communications you’d expect that Jane Street would have found it already
Dangit! I was betting on -183.
This is better
You didn't believe!
Why is that funny?
The -182 feels highly arbitrary.
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.
But who is going to be the one solving them? Just query an LLM no?
Sure, all of this might end up being very unpleasant, and I'm glad not to be a mathematician right now. But that's still better than a future where there aren't even any questions left that we can understand and an AI can't solve.
Also, it still seems that AI has a much different style from humans, with more brute force and using obscure literature results, and the future might still end up human/AI complementary. We aren't in an AlphaZero situation where the AI learns everything through self-play. (Yet? But we don't even seem to be moving that way much? Can anybody qualified help out?) Things are just moving really fast now and it's hard to process everything.
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
If you view them as "theories of computational limits" instead of "proposed practical speedups" they can be a lot more interesting.
It's most interesting when the lower bound can actually be proven. In lack of that, we have to guess what the best possible algorithm might yield (generalized or not). This tells us that need not be O(n log n) and we have the opportunity to still find better algorithms than we typically thought would be possible. This does the latter, which is interesting, but it just leaves us to hunger more for what the real limit must be :).
i understand this, but it always feels like we are being tricked when they say "integer multiplication below nlogn" because we intuit that that must mean "faster integer multiplication below nlogn EVERYWHERE!". but in reality it comes with 15 asterisks about the conditions that must be true for their statement to hold true.
Your issue is that I am viewing this proof as what it really is in terms of progressing the field and not from an imaginative perspective. I think that it is important to ground our selves somewhat in reality when discussing research like this because at the end of the day open ai is not doing for fun either.
openai wants to show the world what their product can do and i am simply not impressed
For the uninitiated, why is this interesting given it doesn't seem to be so much below the threshold?
O(n lg n) is a bit of a threshold value. For a lot of algorithms, this is the best you can do, even in theory (similar to how O(n^2) is also a threshold for many algorithms). So for many algorithms, people stop trying when they get close to O(n lg n) on the belief that you'll never do better than that.
The fact that you can in principle go faster than n lg n, even if just by an almost imperceptible amount, is kind of surprising. It raises the question of, if n lg n isn't the limit, what is? How far down can we get the speed? If we can get it a little past n lg n, maybe we can go a lot further.
[or at least that is my understanding. not a theoretical computer scientist]
It's interesting because people wondered if it was possible to go below the threshold at all, that's all. Many suspected it was not possible.
It's like when Tony Hawk did a 900 for the first time. Now 900s in skateboarding aren't a big deal, kids can do it now. It was proving to the world what was possible was the mental hurdle that inspires others to actually try at the problem harder.
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 :)
I only skimmed the paper but it doesn’t see particularly dense, mostly just relying on college math?
It's 50 pages and cites this other paper in the same repo:
OpenAI. An explicit power saving for the exact discrete Fourier transform.
Here's a random excerpt:
8.3 The middle transform and the final permutation The factor QFt in (35) can be computed from a cyclic convolution and two pointwise phase multiplications. The chirp identity below performs the frequency change in Q without applying Q as a separate permutation of the array. The second identity shows how the retained source permutation R cancels when computing a convolution. Here ∗ denotes cyclic convolution on the product of the coordinate groups and a dot denotes coordinatewise multiplication.
Sure, I don’t see what’s horrible about this? It is a lot to read, sure, but it doesn’t seem unreasonably advanced