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-confidentially 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.
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. Depending on how predictable the thing being communicated with is and how far away it is,
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 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-confidentially 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.
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.
If there was a way to do FTL communications you’d expect that Jane Street would have found it already
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. Depending on how predictable the thing being communicated with is and how far away it is,
Why is that funny?
Dangit! I was betting on -183.
You didn't believe!
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 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.
For the uninitiated, why is this interesting given it doesn't seem to be so much below the threshold?
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.
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