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.
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 compensating for light speed 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.
Ah that's no fun. Maybe something like a quant sending a message to his mistress to get out of his vacation home because his wife is on the way, but the wife is cheating on the quant with the CEO of one of his investments which is the firm that's doing the FTL communication, and the signals get mixed up so the CEO the quant both arrive at the office, ready to go, and meet each other there and it's really awkward.
You can bootstrap a tiny duration of prescience into arbitrary durations by passing back the same message over and over as many times as you like.
If you know what will happen in one minute, write down the message you see yourself writing down in one minute. In a minute, do the same thing. Now you can pass messages back two minutes.
What if I see myself writing a message in one minute, and thus I dont need to send that message back in in time for me from the future, coz ive already seen it, so I wont write it down for me in a minute?
I think it's more likely that modern physics are wrong than that all of those weird things happen. We might simply discover a preferred reference frame, instead.
I mean, being pedantic a little, we don't actually know if c is constant, since measuring c is rather difficult. If c is not in fact constant in some medium or environment, then a huge number of things get very weird very fast.
So, yes, we could've measured c wrong. We just would have no idea if we did.
Source: Veritasium did a very fascinating video explaining this problem.
If we have variable c, it would be indistinguishable.
We even use the Lorentz transform, developed for post-Michelson aether theories, precisely because you cannot tell whether you’re in a varying aether or a varying geometry.
We define distance and time relative to c, so we cannot measure it in the usual sense.
> So, yes, we could've measured c wrong. We just would have no idea if we did.
We know we've got it pretty well close to accurate, for the bulk of the observable universe.
If c changes, then chemistry changes, and stuff like hydrogen absorption lines shift. This is how scientists have looked for changes in c in the early universe.
Ok. I liked how in this thread some people mentioned instead "faster than causality" instead. Which is both obviously non sense and more relevant than "light".
Causality is conceptually out of time, so it's not traveling. Instead we except causality to operate everywhere anytime uniformly, and all physical dimensions to be bound by causality.
Can causality even conceptually exist outside of time? That sounds like nonsense to me, whereas "faster than causality" seems like a pretty straightforward idea.
The relative difference is so absurdly small to be irrelevant at any realisable input size. At least that's my read; e.g. even at n=10^80 (~number atoms in universe), the relative difference is ~0. That's still probably underselling how similar this is to n log n.
this is how all the proofs today are looking, they seems so minimal even when compared to minor improvements in these fields from that last 10 years im wondering why even publish these and not just make research notes public
Me too. This is the sort of thing that would traditionally be hidden as n lg n ^ (1 - eps) for some eps > 0, but it's much more amusing this way.
No way this is the correct upper bound, and I imagine it'll get refined fairly quickly. IIRC, the GapCVP results were released with a 1/n^400 complexity term, but people quickly got it down to 1/n^8 by more careful accounting.
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.
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 potentially very interesting because there are a number of critical algorithms that are all related and share asymptotic lower bounds as a result. My first thought on seeing this was whether a proven result here would also open the door for FFTs to go below O(n log n).
"We give a deterministic algorithm that computes the discrete Fourier transform at every length n in O ( n ( log n ) ** (1 − 10 ** −13)) operations. The model uses exact complex arithmetic, unrestricted coefficients, specified Fourier roots, and unit-cost logarithmic-size indexing; scalar preparation and array organization are included."
It shows that nlogn is not the limit, how much better we can go? Not sure, probably not much, but breaking the barrier is important. Like in marathon for years nobody thought human could break the 2 hour barrier, then someone did and now it's become normal occurrences.
Multiplication can be done by FFT, which is an exceptionally efficient algorithm that has nlogn complexity, you'd be called crazy if you claim you have something more efficient than FFT.
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
This progresses the field a great deal, just perhaps not the field you're interested in? There's nothing wrong with a "and what can I apply that to in my life tomorrow" approach but it's certainly not the only approach worth having in the world.
I can respect your opinion if it's consistent- i.e. it's not just directed at OpenAI's results. But this seems to be an example of a common phenomenon with AI discourse: while disparaging LLM achievements, you indirectly insult the careers/accomplishments of 99% of mathematicians for whom this would easily be the crown jewel of their CV.
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 ?
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.
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.
What I meant is e.g. the unit distance construction, which (per mathematicial comments) needed a combination of distant fields, so nobody had the necessary expertise. That's different from working within one obscure field.
Incidentally, the previous most efficient known algorithm for integer multiplication was co-discovered by the chief author of GNU TeXmacs, a typesetting word processor.
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.
It’s not meant to be an engineering improvement, it’s an important theoretical result because it casts doubt on things that were previously thought to be impossible.
It is surprising, but physicists don't care much for set theory. Heck in their daily work they still use infinitesimals!
So yeah, among the few physicists who understand enough set theory to comment on this, most of them are totally fine with admitting that our reality is not based on set-theoretic real numbers.
For mathematicians, sets are the base reality and everything else is constructed in terms of those. For physicists experimental validation is the base reality, and if it disagrees with set theory that's okay with them; it just means that the set-theoretic real numbers aren't the correct real numbers for doing physics. They're very pragmatic when it comes to mathematical foundations, and that's probably the right approach to take for doing physics.
There have been a few attempts to formalize real numbers that more closely match our observed reality; look into measurable sets. Most of these require a large cardinal, so they go beyond ZFC.
infocollector | 22 hours ago
saagarjha | 22 hours ago
cr4zy | 22 hours ago
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.
saagarjha | 21 hours ago
shmoil | 22 hours ago
qarl | 22 hours ago
utopcell | 22 hours ago
ummonk | 21 hours ago
elcritch | 22 hours ago
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.
hgoel | 22 hours ago
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 compensating for light speed comms, kind of like branch prediction in processors or speculative decoding in LLMs, but that wouldn't actually be FTL comms.
Lerc | 21 hours ago
elcritch | 21 hours ago
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.
empraptor | 21 hours ago
fragmede | 17 hours ago
roywiggins | 21 hours ago
If you know what will happen in one minute, write down the message you see yourself writing down in one minute. In a minute, do the same thing. Now you can pass messages back two minutes.
MaxikCZ | 12 hours ago
roywiggins | 9 hours ago
cowlevel | 11 hours ago
saagarjha | 21 hours ago
mypalmike | 20 hours ago
binlog | 21 hours ago
ethin | 21 hours ago
So, yes, we could've measured c wrong. We just would have no idea if we did.
Source: Veritasium did a very fascinating video explaining this problem.
Good4boothee | 13 hours ago
davidmurdoch | 2 hours ago
zmgsabst | 9 hours ago
We even use the Lorentz transform, developed for post-Michelson aether theories, precisely because you cannot tell whether you’re in a varying aether or a varying geometry.
We define distance and time relative to c, so we cannot measure it in the usual sense.
dualvariable | 6 hours ago
We know we've got it pretty well close to accurate, for the bulk of the observable universe.
If c changes, then chemistry changes, and stuff like hydrogen absorption lines shift. This is how scientists have looked for changes in c in the early universe.
psychoslave | 19 hours ago
yacin | 19 hours ago
psychoslave | 16 hours ago
Causality is conceptually out of time, so it's not traveling. Instead we except causality to operate everywhere anytime uniformly, and all physical dimensions to be bound by causality.
Timon3 | 4 hours ago
CaptainNegative | 18 hours ago
dprkh | 21 hours ago
philipwhiuk | 21 hours ago
simon-b | 21 hours ago
12390asdjkas | 21 hours ago
NelsonMinar | 21 hours ago
keeganryan | 18 hours ago
No way this is the correct upper bound, and I imagine it'll get refined fairly quickly. IIRC, the GapCVP results were released with a 1/n^400 complexity term, but people quickly got it down to 1/n^8 by more careful accounting.
NooneAtAll3 | 17 hours ago
sqrt(n) now https://github.com/Mira-acc/cvp
MinimalAction | 22 hours ago
Chinjut | 22 hours ago
Fordec | 21 hours ago
bawolff | 21 hours ago
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]
ack_complete | 17 hours ago
aix1 | 16 hours ago
"We give a deterministic algorithm that computes the discrete Fourier transform at every length n in O ( n ( log n ) ** (1 − 10 ** −13)) operations. The model uses exact complex arithmetic, unrestricted coefficients, specified Fourier roots, and unit-cost logarithmic-size indexing; scalar preparation and array organization are included."
anvuong | 17 hours ago
Multiplication can be done by FFT, which is an exceptionally efficient algorithm that has nlogn complexity, you'd be called crazy if you claim you have something more efficient than FFT.
12390asdjkas | 22 hours ago
i will NEVER care about proposed multiplication speedups unless they are truly generalized
zamadatix | 22 hours ago
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 :).
12390asdjkas | 21 hours ago
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
zamadatix | 21 hours ago
pickleRick243 | 20 hours ago
inkysigma | 20 hours ago
wk_end | 22 hours ago
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.
reddozen | 21 hours ago
bawolff | 21 hours ago
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 ?
mmiyer | 21 hours ago
1. https://github.com/openai/math/blob/main/preprints/Matrix-Mu...
isaac-harvey | 21 hours ago
Kotlopou | 21 hours ago
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.
[OP] E-Reverance | 21 hours ago
Kotlopou | 21 hours ago
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.
ks2048 | 20 hours ago
Is that true? Look at the average math paper on arxiv. Of course it's obscure to those not in the exact sub-field - math has become very specialized.
Kotlopou | 20 hours ago
[OP] E-Reverance | 19 hours ago
TGower | 21 hours ago
WithinReason | 15 hours ago
binlog | 21 hours ago
TrueSlacker0 | 20 hours ago
octoberfranklin | 20 hours ago
F3nd0 | 17 hours ago
ChrisArchitect | 20 hours ago
Sharing AI Progress in Mathematics
https://news.ycombinator.com/item?id=49984923
octoberfranklin | 20 hours ago
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.
WhitneyLand | 20 hours ago
It’s not meant to be an engineering improvement, it’s an important theoretical result because it casts doubt on things that were previously thought to be impossible.
vessenes | 17 hours ago
octoberfranklin | 4 hours ago
So yeah, among the few physicists who understand enough set theory to comment on this, most of them are totally fine with admitting that our reality is not based on set-theoretic real numbers.
For mathematicians, sets are the base reality and everything else is constructed in terms of those. For physicists experimental validation is the base reality, and if it disagrees with set theory that's okay with them; it just means that the set-theoretic real numbers aren't the correct real numbers for doing physics. They're very pragmatic when it comes to mathematical foundations, and that's probably the right approach to take for doing physics.
There have been a few attempts to formalize real numbers that more closely match our observed reality; look into measurable sets. Most of these require a large cardinal, so they go beyond ZFC.
Agingcoder | 5 hours ago