> It would be good to have a formalised proof of the o(n log n) result, for example in Lean. As far as I can tell, one does not yet exist.
The result is fully formalized in Lean by @platypii and myself (on Mathlib's TM2 machine), with ongoing improvements to the exponent (currently at 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
> I have not actually read the paper. In fact, there are three closely related papers [TC26a], [TC26b], [TC26c], and I have not read any of them. I tried, but soon gave up. The math(s) dump does not appear to be strong on exposition. Instead, I asked Fable to explain [TC26a] to me. Fable seems to understand the argument and thinks that it is correct.
This clearly hit a nerve in very interesting ways!
Suppose we have a very convincing math PhD impersonator, agreeing and making some prepared smart-sounding comments saying they understood the proof and it seems to make sense - would it?
Well, most would say - NO! Obviously not, knowing this person was an impersonator. Others now knowing could be convinced of the validity.
Very simple thought exercise that allows to conclude, someone "saying they understood" (or agree) bears absolutely no weight to something's validity.
The idea that OpenAI's proofs are fake is contradicted by the response of mathematicians. Were they fake, mathematicians would not consider this release important enough to comment upon[1,2], as vixra always provided a steady supply of such writings. Nor would they be able to write expositions and simplifications, of which several are published each day on arxiv (just search OpenAI on arxiv to find them).
But perhaps mathematicians are no longer able to be the best judge if a proof is valid. Yet nobody but them is able to even understand what is claimed to have been resolved.
> Were they fake, mathematicians would not consider this release important enough to comment upon[1,2], as vixra always provided a steady supply of such writings.
Few articles on vixra are made by companies with ~$1T valuations.
This is true of literally any proof of sufficient complexity, human-authored or otherwise.
It takes time to convey the core ideas. It takes time for other mathematicians to come up to speed on the new techniques and approaches or the novel combinations of existing ones.
The actual experts in this field have asked for the argument to be explained to them, and are now at the point where they believe this is plausible. Another person in this thread has produced a Lean proof and presumably is not trying to pull a fast one on us by exploiting a bug in the solver.
More realistically, that impersonator has created lots of output, and the correct ones are selectively publicized (and few particularly interesting bad answers).
Why not? If mathematicians in the field cannot understand the papers, but tools at our disposal can, why not use them? What is "unhealthy" about that? Just seems like it's the reality of the world now.
If you can't understand what the machine has done, math is not being done. Math is not pushing symbols around to find sequences that follow all the rules. Math is the process of understanding how those sequences of symbols map to meanings. If you can't follow the proof but have validated it's correct, all you know is that it's a proof of something. Is it a proof of what's claimed in the adjacent plaintext? Who knows!
Math is about clear communication between people first and foremost. That's why Shinichi Mochizuki's claimed proof of the ABC conjecture isn't accepted - he's unable to communicate it to enough mathematicians to get a consensus on its validity. LLMs generating Lean proofs are basically following that same schema. Sure, something has been proven. But what? Where's the clear communication explaining it to the satisfaction of other mathematicians?
I mean, I could not understand 95% of all the math out there due to skill issue, and it’s still valid. If machines can understand the math and humans can’t, we can’t validate it, but that doesn’t make the math itself invalid.
It could be logically valid but irrelevant? Allowing for the atrophying of all our skills is dangerous? While simultaneously building ever more complicated edifices that control our lives? Not a doomer but you really just want to shrug and say it ain't no thing?
Perhaps humans have peaked due to the fundamental biological nature of our brains and AI will eventually surpass us in mathematical intelligence.
That has been the ultimate goal of creating AI -- not to simply match human intelligence but to surpass it. If it surpasses us, does that make it irrelevant? Everything around us is powered by mathematics, most of it I don't understand, and soon perhaps everything will be powered by mathematics that everybody doesn't understand.
The underlying tautologies always existed. Making them accessible to us as truth and usable for one or more functions is what's invented by people (and potentially by AI) via insightful proofs and narratives.
The mistakes that lurked in radium, in arsenic, in leaded gas, in fallout downwind of nuclear tests ... all had the best tools that the previous generation knew.
None of them were okay. Those were small small tools with few (sometimes only one) uses.
Generations earlier, famines, diseases and lead-leeching plumbing made rulers insane and entire cities of people die without any help from the "best tools".
Scifi is always written about the best tools. The issues arrive in the tools and in the hands that wield them both.
There's nothing that makes this paper the be and and end all opinion pieces of the paper. The community will review his review, and people who wish to understand more will read more and more of the paper. I see nothing wrong with this process of progressive understanding.
Yup, and it always has been, we don’t even understand how our bodies or minds work, yet we use them everyday
The amount of unimaginable complexity contained in a seemingly very tiny amount of matter to us, is incredible, and it’s all around us in nature
We’ve never had the capacity to fully comprehend neither ourselves nor the environment we live in. But we do our best, and we do survive and sometimes even thrive
Even pre-AI, there have been proofs that took years to be verified, understood and some were disputed forever and still are (like the Mochizuki / IUT drama). So, even without AI, maths has reached a point of specialization, where only a few people in the world know the areas used in a proof well enough to check it. When „new math“ is invented for a proof, people may even be more disincentivied to put in the effort. So, I‘d argue, AI makes understanding new proofs easier, not more difficult.
What a funny pov?? Mathematics and other pure sciences are about human understanding. You're saying if humans cannot understand the thing that was for human understanding, that's ok? That's like saying all the world's food is now inedible, but that's ok because a blender can consume it still.
The "top layer" of maths being this is one thing. Now imagine another layer of this. Then another. Then another. Then another.
At one point intuition helps to build out usage of the math itself. See stuff like "oh I can do rotations through matrix multiplication"-style ideas.
It is helpful for us to be able to reach for those tools quickly. The more tools that require advanced prep to use, the less we'll be able to use the results in easier contexts. Everything will be hard
Of course nothing really prevents people from looking for the simpler tools and proofs. Lots of math stuff starts off complicated and gets simpler.
There are a few increasingly powerful companies that own the frontier models that can produces these results. In the future, it may only be these models that understand the results. Should we be beholden to a few companies for basic understanding of foundational principals?
Especially for tools built to tell us we’re right and happily pretend to solve problems they didn’t.
I think the OpenAI “revert” of their math problems speaks volumes of how volatile this can be.
The tool may malfunction. Indeed there are theorems that say the tool must malfunction at least sometimes.
If you don't understand the subject and relies on the understanding of the tool, how will you have a frigging chance of catching an error?
Anyway this reminds me that scene in Matrix 2, where the mayor (of sorts, don't remember his exact title) of Zion tells Neo about the machines that keeps everyone alive, but that there is nobody left that understands how they work or could repair them if they broke.
But where they do differ is they do have an infinite stamina, and can work on problems in loops, self-correcting their own mistakes if a formal way of checking the correctness of the solution exists. Which does happen to be the case with math.
because the tools can't?
Lol. That's not how it works. Am I in the twilight zone?
All this anthropomorphism of literal statistical text generators.
Yes they exhibit generated sentences of text that describe coherent responses about a topic when there's an inordinate amount of research material in the training data from which they are distilling sentences of sound and rational thought. That's the ONLY way it can possibly work. There are so many scenarios where the training data isn't setup like that and low and behold the generated responses are just literal garbage.
Fable was able to help a human understand the paper though, so the situation is quite a bit better than if we just had a lean proof that was apparently correct but for which all attempts at explanation were "hallucinations". There doesn't seem to be an apparently obstacle to a human fully understanding the proof in several months of focused study.
Honestly it is not that much different from the divine inspiration if you have ever experienced it.
I do not know how you view the world or walk through it but language in general is simply subject to interpretation to me, the arrangement of words for the sentence is inspiration in and of itself - though the majority of time it amounts to minimum jumps.
This is a conundrum I hadn’t seen anyone predict. We will reach a time when machines push math and physics farther than a human mind ever could. But we won’t be able to know if it is correct for that same reason!
> The new result does not directly imply new complexity bounds for polynomial multiplication over a fixed finite field, say multiplication in F2[x]. The state of the art for this problem is an algorithm that multiplies polynomials of degree n in time O(n log n 4^log*(n)) [HvdH19].
I realize this is 100% not the point, but is this an immediately practical breakthrough that will change computing?
My extremely limited understanding is “no” as I sorta assume that would be the headline. The main point being that while a MASSIVE improvement over any previous progress it’s still “small” from a practical standpoint.
This is not to downplay the very well conveyed problem this might be, but I just want to make sure I even got that right.
I do wonder if this will be a major issue for future development or if the math experts in diapers right now will grow up in this world and have tools and understanding to assist and we’re just in a rough transition, but unfortunately that’s about as much as I can contribute.
This is very much a theoretical result. The author quotes a redditor or who jokes that the previous bound was nice and round and that was of practical importance:
>The result is of extreme practical importance. Not for actually
multiplying integers (as usual with these algorithms it’s probably not
faster than existing algorithms for integers that can be stored in the
observable universe), but for writing papers. It has always been a hassle
to write down the complexity of integer multiplication or algorithms based
on integer multiplication by introducing soft-O notation, little-o
exponents, epsilons greater than 0, or iterated logarithms. From now on I
can just write O(n log n) in my papers and be done with it!
Note in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.
Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
Awesome write up and intro by a fellow Sydney-sider, kept me hooked! As someone who's not a maths wizard, the technical details flew by my head but the prose allowing me to empathise deeply with those in the field was very enlightening. I never realised how big of a deal the maths dump was and how much it has shaken up the field. I guess we are all just trying to figure out this whole "intelligence on tap" thing together.
You don’t need to be a math wizard. Just upload the paper to an AI and ask, “Explain this like I’m five.” Then, with each follow-up prompt, increase the age and level of expertise you want it to assume.
> I assume that by now the Company’s employees are aware of the pain and profound sense of loss that this event has caused in my professional community.
I’m trying to come to terms with this myself. I agree that this future is inevitable, and progress will come regardless.
I feel a lot like Grant in Jurassic Park right now.
Yeah it's crazy. I wonder if the lesser-educated, under-privileged, working class deplorables feel much schadenfreude their enlightened betters who just got done with decades belittling and bullying them with "Dey terk er jerbs" and "Just learn to code" are getting a bit of the treatment now. Interesting times. Maybe we should just learn to mine coal (to power the new datacenters).
> Some of my colleagues believe that this is a nefarious Company, whose only goal is profit, if necessary at our community’s expense. Perhaps there is some truth to this, but I think it is missing the larger point. The fact is that there now exists an automated system that can perform mathematical research — at least the part that involves “solving hard problems” — far better than any human. Now that such a system has been demonstrated, it is clear that results like these were
bound to start appearing soon anyway. I do not blame the Company for getting there first. Who got there first is an irrelevant detail, a historical footnote.
I always wondered about breaking down the O( n log n) FFT convolution multiplier into truly discrete pieces to see if you can shrink it more, last I checked languages like Python that use big integers still weren’t using it, and when I implemented it it used complex floats. I don’t see why it couldn’t be THE multiplier, plus it works in constant time with optics.
Based on skimming the paper (finally a proper explanation that gives some hint at intuition), the path to openai's formulation if you're familiar with undergrad CS is (apparently):
* Start with the usual FFT convolution for polynomials, viewing integers as a polynomial in a given base evaluated at a certain point
* In undergrad you (hopefully) saw polynomial multiplication can be done in nlogn via convolution using FFT, but that assumes complex integer addition/multiplication is O(1). Here we need O(log x) bits to simply represent a number x on a real machine.
* If you use naive (n^2) multiplication for those butterfies, then you end up with O(n[(log n)^2]).
* If you recursively use FFT for the digit multiplication at those butterflies, then you get something like O(n[(log n)^(log log n)]).
* Schonhage-Strassen realized that instead of doing FFT in C where the butterfly involves multiplying by \omega (\omega being roots of unity), you can work in a different ring where 2 is a root of unity and so it's a cheap bitshift, but were constrained in how finely they could break subproblems (could only break an n-bit integer into sqrt-n subpproblems each of sqrt-n bits), resulting in an overall O(nlogn * loglogn).
* The 2019 O(nlogn) version (supposedly, this is out of my depth) found a way to use some technique of "Gaussian Resampling" to do the matrix convolution via _multidimensional FFT_ in a ring where multiplying by root of unity became cheap _and_ subproblems could be finer. The bottleneck was thus only the addition/subtraction in the O(log n) butterfly layers, each of which does O(n) work for total of O(n logn)
* OpenAI's paper uses a fact that it's apparently easier to compute multiple butterfly layers "simultaneously" than doing them one at a time independently (page 10). There is some sort of implicit reuse because the later layers mix the outputs of earlier layers, and they take advantage of this to avoid having to write out layer 1 outputs separately from layer 2 outputs, and instead work in some coordinate system where they can intermingle them. This apparently amortizes to some tiny fractional epsilon shaved off of a layer, and since the whole FFT is recursive they can apparently save a factor of (1 - epislon)^(log log n) overall across "log log n" recursion depth, which is apparently where that ridiculously small overall exponent comes from.
> It would be good to have a formalised proof of the o(n log n) result, for example in Lean. As far as I can tell, one does not yet exist.
The result is fully formalized in Lean by @platypii and myself (on Mathlib's TM2 machine), with ongoing improvements to the exponent (currently at 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
Contributions are welcome!
> I have not actually read the paper. In fact, there are three closely related papers [TC26a], [TC26b], [TC26c], and I have not read any of them. I tried, but soon gave up. The math(s) dump does not appear to be strong on exposition. Instead, I asked Fable to explain [TC26a] to me. Fable seems to understand the argument and thinks that it is correct.
this does not feel like a healthy place to be
This clearly hit a nerve in very interesting ways!
Suppose we have a very convincing math PhD impersonator, agreeing and making some prepared smart-sounding comments saying they understood the proof and it seems to make sense - would it?
Well, most would say - NO! Obviously not, knowing this person was an impersonator. Others now knowing could be convinced of the validity.
Very simple thought exercise that allows to conclude, someone "saying they understood" (or agree) bears absolutely no weight to something's validity.
The idea that OpenAI's proofs are fake is contradicted by the response of mathematicians. Were they fake, mathematicians would not consider this release important enough to comment upon[1,2], as vixra always provided a steady supply of such writings. Nor would they be able to write expositions and simplifications, of which several are published each day on arxiv (just search OpenAI on arxiv to find them).
But perhaps mathematicians are no longer able to be the best judge if a proof is valid. Yet nobody but them is able to even understand what is claimed to have been resolved.
It is really strange to see mathematicians of the highest rank taking these results seriously[3], holding lectures explaining them, yet see it dismissed here as a mass psychosis. [1]https://smf.emath.fr/actualites-smf/20-10-26-communique-sur-... [2]https://www.mathsoc.jp/publicity/news20261016.html [3]https://terrytao.wordpress.com/2026/10/19/a-sketch-of-the-pr...
> Were they fake, mathematicians would not consider this release important enough to comment upon[1,2], as vixra always provided a steady supply of such writings.
Few articles on vixra are made by companies with ~$1T valuations.
Now imagine that PhD “impersonator” has, in the past few months, made more demonstrable progress in mathematics than anyone in history.
I think that would change the conclusion of the argument a little.
Or maybe the PhD impersonator discovered a soundness bug in a component of Lean and was able to exploit it.
With no humans able to understand the proofs the impersonator has produced, there's no way of knowing.
This is true of literally any proof of sufficient complexity, human-authored or otherwise.
It takes time to convey the core ideas. It takes time for other mathematicians to come up to speed on the new techniques and approaches or the novel combinations of existing ones.
The actual experts in this field have asked for the argument to be explained to them, and are now at the point where they believe this is plausible. Another person in this thread has produced a Lean proof and presumably is not trying to pull a fast one on us by exploiting a bug in the solver.
TL;DR chill bro.
More realistically, that impersonator has created lots of output, and the correct ones are selectively publicized (and few particularly interesting bad answers).
Why not? If mathematicians in the field cannot understand the papers, but tools at our disposal can, why not use them? What is "unhealthy" about that? Just seems like it's the reality of the world now.
If you can't understand what the machine has done, math is not being done. Math is not pushing symbols around to find sequences that follow all the rules. Math is the process of understanding how those sequences of symbols map to meanings. If you can't follow the proof but have validated it's correct, all you know is that it's a proof of something. Is it a proof of what's claimed in the adjacent plaintext? Who knows!
Math is about clear communication between people first and foremost. That's why Shinichi Mochizuki's claimed proof of the ABC conjecture isn't accepted - he's unable to communicate it to enough mathematicians to get a consensus on its validity. LLMs generating Lean proofs are basically following that same schema. Sure, something has been proven. But what? Where's the clear communication explaining it to the satisfaction of other mathematicians?
> Math is about clear communication between people first and foremost.
I can't imagine I'm the first one to point out that this is perhaps the greatest unsolved problem in mathematics.
> Where's the clear communication explaining it to the satisfaction of other mathematicians?
Coming in about a year for $20/month, sure seems like.
I mean, I could not understand 95% of all the math out there due to skill issue, and it’s still valid. If machines can understand the math and humans can’t, we can’t validate it, but that doesn’t make the math itself invalid.
It could be logically valid but irrelevant? Allowing for the atrophying of all our skills is dangerous? While simultaneously building ever more complicated edifices that control our lives? Not a doomer but you really just want to shrug and say it ain't no thing?
Perhaps humans have peaked due to the fundamental biological nature of our brains and AI will eventually surpass us in mathematical intelligence.
That has been the ultimate goal of creating AI -- not to simply match human intelligence but to surpass it. If it surpasses us, does that make it irrelevant? Everything around us is powered by mathematics, most of it I don't understand, and soon perhaps everything will be powered by mathematics that everybody doesn't understand.
Does math already exist and is discovered? Or is it a thing invented by people?
The underlying tautologies always existed. Making them accessible to us as truth and usable for one or more functions is what's invented by people (and potentially by AI) via insightful proofs and narratives.
The mistakes that lurked in radium, in arsenic, in leaded gas, in fallout downwind of nuclear tests ... all had the best tools that the previous generation knew.
None of them were okay. Those were small small tools with few (sometimes only one) uses.
Generations earlier, famines, diseases and lead-leeching plumbing made rulers insane and entire cities of people die without any help from the "best tools".
Scifi is always written about the best tools. The issues arrive in the tools and in the hands that wield them both.
There's nothing that makes this paper the be and and end all opinion pieces of the paper. The community will review his review, and people who wish to understand more will read more and more of the paper. I see nothing wrong with this process of progressive understanding.
Yup, and it always has been, we don’t even understand how our bodies or minds work, yet we use them everyday
The amount of unimaginable complexity contained in a seemingly very tiny amount of matter to us, is incredible, and it’s all around us in nature
We’ve never had the capacity to fully comprehend neither ourselves nor the environment we live in. But we do our best, and we do survive and sometimes even thrive
well math has always been about "understanding things" -- hence proofs and etc is the main tool in the field
(and why math differentiates between conjectures (maybe true) and theorems)
so that "oh some 3rd party person/machine understood it for me" can feel... a bit icky
Even pre-AI, there have been proofs that took years to be verified, understood and some were disputed forever and still are (like the Mochizuki / IUT drama). So, even without AI, maths has reached a point of specialization, where only a few people in the world know the areas used in a proof well enough to check it. When „new math“ is invented for a proof, people may even be more disincentivied to put in the effort. So, I‘d argue, AI makes understanding new proofs easier, not more difficult.
And yet for someone like me who is not a math expert, it has (all) always felt unapproachably foreign.
[dead]
IDK why this is relevant to the topic at hand.
Everyone in advanced math research understands the topics they are reading about deeply.
This person is just literally being victimized by the AI incompetence apocalypse.
Information overload + trained laziness.
What a funny pov?? Mathematics and other pure sciences are about human understanding. You're saying if humans cannot understand the thing that was for human understanding, that's ok? That's like saying all the world's food is now inedible, but that's ok because a blender can consume it still.
The "top layer" of maths being this is one thing. Now imagine another layer of this. Then another. Then another. Then another.
At one point intuition helps to build out usage of the math itself. See stuff like "oh I can do rotations through matrix multiplication"-style ideas.
It is helpful for us to be able to reach for those tools quickly. The more tools that require advanced prep to use, the less we'll be able to use the results in easier contexts. Everything will be hard
Of course nothing really prevents people from looking for the simpler tools and proofs. Lots of math stuff starts off complicated and gets simpler.
Just important that this is still a goal in mind
There are a few increasingly powerful companies that own the frontier models that can produces these results. In the future, it may only be these models that understand the results. Should we be beholden to a few companies for basic understanding of foundational principals?
> Why not? If mathematicians in the field cannot understand the papers, but tools at our disposal can (...)
How can you tell?
Especially for tools built to tell us we’re right and happily pretend to solve problems they didn’t. I think the OpenAI “revert” of their math problems speaks volumes of how volatile this can be.
The tool may malfunction. Indeed there are theorems that say the tool must malfunction at least sometimes.
If you don't understand the subject and relies on the understanding of the tool, how will you have a frigging chance of catching an error?
Anyway this reminds me that scene in Matrix 2, where the mayor (of sorts, don't remember his exact title) of Zion tells Neo about the machines that keeps everyone alive, but that there is nobody left that understands how they work or could repair them if they broke.
Sounds like a disassembler.
Because the tools don't understand the papers either. We know for a fact that:
1. These tools are wrong a significant % of the time
2. They have an upper complexity bound where they start to fall apart
Relying on AI to check AI papers is a terrible idea
So, just like humans then?
But where they do differ is they do have an infinite stamina, and can work on problems in loops, self-correcting their own mistakes if a formal way of checking the correctness of the solution exists. Which does happen to be the case with math.
Humans can be wrong, but luckily we have an entire process for dealing with this, which is broadly called this new fangled 'science' thing
The trope of superficially likening every aspect of LLMs to humans is specious and lazy.
Yes you're replying to astroturfers or AI psychosis victims.
because the tools can't? Lol. That's not how it works. Am I in the twilight zone?
All this anthropomorphism of literal statistical text generators.
Yes they exhibit generated sentences of text that describe coherent responses about a topic when there's an inordinate amount of research material in the training data from which they are distilling sentences of sound and rational thought. That's the ONLY way it can possibly work. There are so many scenarios where the training data isn't setup like that and low and behold the generated responses are just literal garbage.
Honestly this is starting to feel like a "God in the gaps" argument.
how so?
Fable was able to help a human understand the paper though, so the situation is quite a bit better than if we just had a lean proof that was apparently correct but for which all attempts at explanation were "hallucinations". There doesn't seem to be an apparently obstacle to a human fully understanding the proof in several months of focused study.
> this does not feel like a healthy place to be
I believe you just captured the zeitgeist, friend.
Fable is the "gadget" of language ELI5.
Honestly it is not that much different from the divine inspiration if you have ever experienced it.
I do not know how you view the world or walk through it but language in general is simply subject to interpretation to me, the arrangement of words for the sentence is inspiration in and of itself - though the majority of time it amounts to minimum jumps.
This is a conundrum I hadn’t seen anyone predict. We will reach a time when machines push math and physics farther than a human mind ever could. But we won’t be able to know if it is correct for that same reason!
Math suddenly becomes biology
> The new result does not directly imply new complexity bounds for polynomial multiplication over a fixed finite field, say multiplication in F2[x]. The state of the art for this problem is an algorithm that multiplies polynomials of degree n in time O(n log n 4^log*(n)) [HvdH19].
@platypii and I obtained a Lean proof of the same improvement for DFT over prime-order finite fields (yielding polynomial multiplication via the convolution theorem): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
I realize this is 100% not the point, but is this an immediately practical breakthrough that will change computing?
My extremely limited understanding is “no” as I sorta assume that would be the headline. The main point being that while a MASSIVE improvement over any previous progress it’s still “small” from a practical standpoint.
This is not to downplay the very well conveyed problem this might be, but I just want to make sure I even got that right.
I do wonder if this will be a major issue for future development or if the math experts in diapers right now will grow up in this world and have tools and understanding to assist and we’re just in a rough transition, but unfortunately that’s about as much as I can contribute.
This is very much a theoretical result. The author quotes a redditor or who jokes that the previous bound was nice and round and that was of practical importance:
>The result is of extreme practical importance. Not for actually multiplying integers (as usual with these algorithms it’s probably not faster than existing algorithms for integers that can be stored in the observable universe), but for writing papers. It has always been a hassle to write down the complexity of integer multiplication or algorithms based on integer multiplication by introducing soft-O notation, little-o exponents, epsilons greater than 0, or iterated logarithms. From now on I can just write O(n log n) in my papers and be done with it!
This new result means painful typesetting again.
Note in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.
Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.
For those of us uninformed, what’s the difference between O and o?
Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329
That sounds like Knuth came up with them, but the notation is much older than 1976
Best explanation of big-O I've read, in a single opening sentence, no less!
f(n) = O(g(n)) means as n increases, f(n)/g(n) must not grow beyond a constant
f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
Nitpick:
s/must shrink/must eventually shrink, after finitely many n/
Equivalently, must go to zero in the limit.
depends on what you think shrink means. If you mean decreasing, that's false even eventually.
[dead]
Big O basically drops constants
O(2n+1) = O(2n) = O(n)
o(2n+1) > o(2n) > o(n)
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
that's not the convention I know... (from CLRS algorithms book).
Big O is sort of like <=. little o is sort of like <.
https://dl.acm.org/doi/10.1145/1008328.1008329
yes, GP is slightly off, but the idea of <= and < is accurate.
O(n) is: "there exists a K such that, for sufficiently large n, K*n is always larger".
o(n) is: "for every K, for sufficiently large n, K*n is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.)
If f is O(g) and o(h) then
And> Lim f/g -> C a constant.
This isn't quite correct. O(g) doesn't require the limit to exist.
Ah, true, I was being sloppy. Thanks
Lmao! If someone is asking the difference between big and little o notation this is absolutely not the right way to clarify it.
If you were joking then maybe you got me
I do hope you can find and reattach your ass; that does sound painful.
Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound.
https://stackoverflow.com/questions/1364444/difference-betwe...
ty, fixed. (ahh, copy paste.)
Awesome write up and intro by a fellow Sydney-sider, kept me hooked! As someone who's not a maths wizard, the technical details flew by my head but the prose allowing me to empathise deeply with those in the field was very enlightening. I never realised how big of a deal the maths dump was and how much it has shaken up the field. I guess we are all just trying to figure out this whole "intelligence on tap" thing together.
You don’t need to be a math wizard. Just upload the paper to an AI and ask, “Explain this like I’m five.” Then, with each follow-up prompt, increase the age and level of expertise you want it to assume.
That algorithm won't converge anytime soon. A pre-conditioner (i.e. at least some apprentice wizardy) helps.
> I assume that by now the Company’s employees are aware of the pain and profound sense of loss that this event has caused in my professional community.
I’m trying to come to terms with this myself. I agree that this future is inevitable, and progress will come regardless.
I feel a lot like Grant in Jurassic Park right now.
Yeah it's crazy. I wonder if the lesser-educated, under-privileged, working class deplorables feel much schadenfreude their enlightened betters who just got done with decades belittling and bullying them with "Dey terk er jerbs" and "Just learn to code" are getting a bit of the treatment now. Interesting times. Maybe we should just learn to mine coal (to power the new datacenters).
I really enjoy the writing style here.
edit: I mean this seriously. This kind of thing
> Some of my colleagues believe that this is a nefarious Company, whose only goal is profit, if necessary at our community’s expense. Perhaps there is some truth to this, but I think it is missing the larger point. The fact is that there now exists an automated system that can perform mathematical research — at least the part that involves “solving hard problems” — far better than any human. Now that such a system has been demonstrated, it is clear that results like these were bound to start appearing soon anyway. I do not blame the Company for getting there first. Who got there first is an irrelevant detail, a historical footnote.
is very pleasantly honest and well-thought-out.
Agreed! I only wish I understood anything after page 3.
I always wondered about breaking down the O( n log n) FFT convolution multiplier into truly discrete pieces to see if you can shrink it more, last I checked languages like Python that use big integers still weren’t using it, and when I implemented it it used complex floats. I don’t see why it couldn’t be THE multiplier, plus it works in constant time with optics.
> Executive summary (longer version) > The bottom line is that I think the claimed result is plausible. I have not actually read the paper.
Based on skimming the paper (finally a proper explanation that gives some hint at intuition), the path to openai's formulation if you're familiar with undergrad CS is (apparently):
* Start with the usual FFT convolution for polynomials, viewing integers as a polynomial in a given base evaluated at a certain point
* In undergrad you (hopefully) saw polynomial multiplication can be done in nlogn via convolution using FFT, but that assumes complex integer addition/multiplication is O(1). Here we need O(log x) bits to simply represent a number x on a real machine.
* If you use naive (n^2) multiplication for those butterfies, then you end up with O(n[(log n)^2]).
* If you recursively use FFT for the digit multiplication at those butterflies, then you get something like O(n[(log n)^(log log n)]).
* Schonhage-Strassen realized that instead of doing FFT in C where the butterfly involves multiplying by \omega (\omega being roots of unity), you can work in a different ring where 2 is a root of unity and so it's a cheap bitshift, but were constrained in how finely they could break subproblems (could only break an n-bit integer into sqrt-n subpproblems each of sqrt-n bits), resulting in an overall O(nlogn * loglogn).
* The 2019 O(nlogn) version (supposedly, this is out of my depth) found a way to use some technique of "Gaussian Resampling" to do the matrix convolution via _multidimensional FFT_ in a ring where multiplying by root of unity became cheap _and_ subproblems could be finer. The bottleneck was thus only the addition/subtraction in the O(log n) butterfly layers, each of which does O(n) work for total of O(n logn)
* OpenAI's paper uses a fact that it's apparently easier to compute multiple butterfly layers "simultaneously" than doing them one at a time independently (page 10). There is some sort of implicit reuse because the later layers mix the outputs of earlier layers, and they take advantage of this to avoid having to write out layer 1 outputs separately from layer 2 outputs, and instead work in some coordinate system where they can intermingle them. This apparently amortizes to some tiny fractional epsilon shaved off of a layer, and since the whole FFT is recursive they can apparently save a factor of (1 - epislon)^(log log n) overall across "log log n" recursion depth, which is apparently where that ridiculously small overall exponent comes from.
Nice domain, UNSW!
web.maths.unsw.edu.au fills the whole address bar on mobile