The recently proposed o(n log n) integer multiplication algorithm [pdf]
web.maths.unsw.edu.au
web.maths.unsw.edu.au
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 conjecture the true growth rate is O(n(log(n))^(1-f(n))) where f(n) is a slowly increasing function of n.
So larger the integers, more efficient the multiplication gets.
AIs of the world, make this your target, and have centuries worth of fun!!
So why would the author claim there isn't a Lean proof available? Shouldn't there be?
this does not feel like a healthy place to be
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
(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
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.
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
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.
and why does this "peer-review" new-age thing cannot be used to scrutinize AI-writted/AI-assisted papers?
Aaaa, you mean 'peer-review' by AI?
Then the answer is: What is the use of a paper no human understands? Then no human can see that the techniques from the paper can be used to build something useful for real human life.
OK, ok, AI can decide to use those techniques to do something in real life it considers useful.
Are you now getting scared? Why not?
How can you tell?
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.
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.
We can explain how LLMs generates this output.
Humans can't be that simple, there must be some ~~divine~~ unique human touch to what we do.
Every day LLMs, running in frameworks that add earlier "thoughts" to the context and iterate, reflecting on their own thought process, gets better and better at doing something even less distinguishable from human output.
The gap gets smaller. The "unique human touch" will always be in the gap.
You just fly in from astroturfer kookoo town or what?
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
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?
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.
“Hey guys, the human condition can be experienced by these machines more efficiently than we are able to! Now we can finally die off!”
Why are we enabling a world that outpaces us? Is this going to lead to anything other than displacement in the long term?
Do you ever stop and ask why we’re building the world we’re building?
To what end does a world we cannot comprehend or rebuild from first principles serve us?
Obviously not every disease can be cured, but even diseases that were essentially gone are coming back because people have just decided they don't care anymore. There are measles outbreaks happening all over the place right now.
mRNA vaccines are a medical marvel and a significant portion of the population has been convinced that horse paste is a better solution.
There are enough resources available that poverty and starvation could be essentially eliminated or at the very least drastically reduced. We just don't do it because people would rather hoard wealth instead.
The technology is here, but too many people profit from not solving the problems
Because we kinda suck. Wars, poverty, destruction of the environment, etc. Maybe AI will be worse -- the are plenty of movies on that subject -- or maybe it will be better.
> Is this going to lead to anything other than displacement in the long term?
We may have already damaged the environment enough that we're going to die off soon anyway. So without AI, we were already on that path to "displace" ourselves -- I don't think that argument is that compelling.
Perhaps this is the natural evolution of intelligent life. Eventually the sun will die and everything we are will be gone forever, maybe this is the only way that something of us survives.
> Do you ever stop and ask why we’re building the world we’re building?
We're not building a world. We're just ants. Individuals making individual decisions that have nothing to do with the rest of the world. You don't have to look too far to find humans that literally care nothing about humanity as a whole and everything about themselves.
> To what end does a world we cannot comprehend or rebuild from first principles serve us?
We already live in that world. You wouldn't even be able to build a toaster from first principles without the knowledge and infrastructure that already exists.
They killed your comment, but you should know that you've posted it on the world's #1 AI propaganda site, where literally trillions of dollars are at stake and ROI depends on the correctness of the discourse running among the meat LLMs foraging or lurking here.
Everything is potentially interconnected.
What separates things is course-graining, not ontological separation per se.
Your opinion is a possibility but it is not grounded by any proof, as such it is nothing more than an assumption. I think the more intellectually healthy approach is to list out the possibilities and figure out what they entail, rather than to throw all your eggs in one basket blindly, which amounts to a leap of faith or a retreat to commitment.
But that's just my two cents, take it or leave it.
I absolutely do not understand what are you talking about.
The question whether the tautologies exists regardless of whether we know about them or not is absolutely not a problem that is studied by mathematics and can be proven by mathematics.
How can humans tell whether machines understand the math if they themselves don't? Math is a human language for quantitative reasoning.
If large sectors of the population decline in their ability to read and write <natural language>, how will they be able to evaluate machine-generated <natural language>?
The second one is very important. While it is a matter of pride that some do understand, and (given enough time, in my opinion) will continue to understand, it is sufficient to be merely correct even if one does not understand why. This is a nice feature of math: it remains true regardless of understanding.
The obvious caveat is the machine needs to prove it in the end, even if we can not.
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.
People can do math alone. They don't have to share it with others. Mochizuki was doing math (with errors). The aliens from Arrival could do math and we wouldn't necessarily be entitled to that. It doesn't make these things not valid math.
The only benefit of defining math through this vulgar social reductivism is to benefit the status quo. So you see some experts and expert-adjacent commentators using these math slogans but never critically justifying those words. Case in point, the above commenter asserts "...math is foremost about communication.", but the very next sentence does not explain why it is foremost, it just uses the sentence as a premise for the following sentence. Guess what, that is exactly how ideologues argue, by question begging fallacy. Ironic that STEM people who ought know better fail to catch this simple rational mistake.
Applies to STEM generally, because the foundation of STEM is peer review and independent testing and confirmation.
Even if the practice never quite lives up to the theory (true) that's no excuse to hand-wave away the requirement as if it doesn't matter.
Proofs that can't be confirmed are valueless because no one learns anything from them. The value of a proof isn't just in proving something but in inventing new techniques and insights that can be reused for other applications.
Brute force searches are fundamentally less valuable, because the creative foundation of math is discovering leaps of logic that solve problems with insightful shortcuts that can be generalised and reused for other applications.
That is quite a bold claim.
Math can always be used as a tool just to achieve results. This can include even novel math. Due to the maturity of the field it is just becoming more and more unlikely that somebody will come up with something novel without realizing the significance.
One example: Quicksort was almost not published because Tony Hoare initially considered the idea behind the algorithm trivial. In the end, all he wanted to do was to sort some numbers.
Maybe there is a polynomial time SAT solver running somewhere just because some overworked engineer implemented it for a completely different problem. And he was just annoyed that all existing libraries were so slow and he doesn't realize that he is sitting on a proof that P=NP. Who knows.
https://mathoverflow.net/questions/43690/whats-a-mathematici...
If we consider the reductionist view that "math is just a tool" to solve problems, and machines can generate new tools that are actually useful, then it can be argued that we don't need to understand how those tools work internally for us to benefit from its usefulness.
My hope is that such a view is given its proper place as a worthy pursuit but that it does not consume the entirety of the field of mathematics as a human activity with culture, philosophy, and art. And I feel the same for the field of software.
The fundamental argument boils down to: "who is all this being made for"? And the answer should be "us, humans". A lot of people here seem to breathlessly fawn over AI as some sort of value in itself, but this is incorrect. There is no absolute value in the universe (as far as we know), the only value to us as humans is subjective.
If AI is not generating value for humans, it isn't generating value, full stop.
Hence the question: "what's the point if we can't understand it?" is perfectly valid and should be discussed. The broader question of "what's the point of AI if not for improving human lives" gets lost in breathless adoration of a technology where nobody knows the outcome.
I'm not saying we need to abandon the pursuit of AI, but we must ask difficult questions at every step because if the technology ends up being as ground-breaking as many here think, it could just as well precipitate a dystopia.
I will be "why don't you go in first", for sure.
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.
Gödel's incompleteness theorem only states that there are true statements that can never be proved to be true. That limits what tools can do, but it's not a "malfunction". The exact same limitation applies to humans. A genuine malfunction would be if the tool "proved" a false statement to be true. That actually has happened before because of bugs in proof checkers, but software bugs can be found and fixed, and proof checkers are simple enough that it's possible to write many different implementations. It's extraordinarily unlikely that the same malfunction occurs in all of them.
> 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.
Which talked about using LLMs to understand math, not to prove theorems
edit: to be clearer, on my areas of expertise, I regularly spot LLMs making false or misleading statements, which usually comes accompanied with a lot of truthful ones. If I push back, they often backtrack and admit they were wrong.
On areas I do not have expertise, I can't be a good judge. And this was my initial point: if you don't understand the subject, how will you catch errors?
So I don't think you can or should use to replace understanding the subject yourself. It's unhealthy to offload your thinking to a tool because it makes you kind of useless.
The author of those sentences is also the author of the main result that this generated improvement builds on, and prior to this improvement his work was thought to be unimprovable. He is, in all of the important ways, literally the single most qualified human on the planet to asses this result. And his assessment is 1) this improvement is real, 2) this improvement is exponentially bigger than his work and the work he improved on, 3) it is effectively impossible for him (and by implication, humanity) to understand the result as presented, 4) it is seemingly trivial for “frontier circa 2026”-class models to understand the result as presented, and 5) to the extent that he is able to understand it, it is only with significant frontier model assistance.
So the place we are at, at least for this highly intellectual field, is “intelligence is the property of ~2 corporations, you must pay them a fee and agree to their terms and conditions to access it”.
At risk of stating the obvious, this is not a healthy place to be because intelligence is now structurally subordinate to the profit motives of particular corporations and at the mercy of all the attendant economic/sociopolitical incentives that apply to them. If the landscape is such that it is in these corporations interests to withhold this intelligence from some and make it available to others, that is simply what will happen.
One trivial example, of which there are an arbitrary number: An elderly leader is convinced to issue a decree that all number-math-computation intelligence is to be made available only to the intelligence agencies of his nation, and failure to comply means no IPO and no further investment. From this point on there would be a permanent nation-state-shaped shadow over practically all modern cryptography, with no recourse possible.
If the Church had a Large Astronomy Model in the time of Copernicus, the earth would have stood still - regardless of what it may privately prove about heliocentrism, it would never declare e pur si muove.
Observing the LLM output on problems that have clear solutions invented by humans, I tend to believe that too many people are jumping to conclusions too soon and interpreting b) as a).
If the LLMs are truly so great, we should see (in a short time, i.e. in order of months) a transformation of the math proofs generated by LLMs from the current state of indigestible mess to something that indeed looks like written by human for humans.
Only then would one be able to claim that we got into situation a).
If a paper/proof is impossible to understand by humans, it could be considered useless (irrelevant) for most intents & purposes.
Regardless how interesting or valid looking, might as well be gibberish pulled from /dev/random. Until:
a) Written down in a form that humans can understand. And/or
b) Turned into practical applications that are demonstrated to work.
In other words: safe to ignore, until a) and/or b) occurs.
If any of those papers were sent to a scientific conference, they would have been rejected as inscrutable gibberish: "resubmit once the presentation is significantly improved".
Yet, mathematicians spend their time trying to understand them.
Real life prisoner's dilemma.
"Our previous version was super-smart, but a bit autistic, even the smartest mathematicians had problems understanding it. The new version is not only super-smart, but can also efficiently communicate its ideas, so that they can be used in real life."
2) Actually, try to use the AI's smarts to gain in real life (not only convincing others to pay you, but actually do the smartest things). Hmmmm, scratch that, that is too idealistic. Use the AI's smarts to become the strongest meanest bastard the others will have no choice but to obey, or else.
Who would staff those intelligence agencies if humans are no longer able to understand the work product?
In any case, it was just one example, I am sure we can think of plentiful others.
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.
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.
I think that would change the conclusion of the argument a little.
With no humans able to understand the proofs the impersonator has produced, there's no way of knowing.
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.
It's highly implausible that the same bug is present in all of them.
I don't know how much was created by LLMs but can you still call these independent implementations?
Galois had built modern algebra before dying at 20. What agents did so far is flash in a pan.
No he hadn’t. You are clearly consuming mathematics through a pop culture lens.
2. It really doesn't work well in other industries either.
That is an unfalsifiable non-argument, a thought-terminating cliché.
Bonus points if it is able to discriminate between human understanding and nonhuman understanding, without vaguely referring to biology.
Failing that, the question seems to me unfalsifiable as per Popper.
There's nothing unfalsifiable about pointing out that we don't know something.
Closely related, "is this machine conscious" is an important question when it comes to ethics yet runs into the exact same problem. Yet you can hopefully see the issue with blindly deciding in either direction on that one.
We don't have a tool or a ruleset to determine whether something is "conscious" or "has real understanding", as the other user put it. And, thus, the statement "X has real understanding" is unfalsifiable.
It is also a thought-terminating cliche [0], because by opening that can of worms the conversation is automatically derailed, as we just saw exemplified here.
[0] https://en.wikipedia.org/wiki/Thought-terminating_clich%C3%A...
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...
Few articles on vixra are made by companies with ~$1T valuations.
Analysing all the proofs and finding contradictions or not takes time.
Not the way they're written, and not at the rate they're dumped on the math community, at least.
It seems they are still the best judge of whether a proof is useful or insightful though. AI is going to reward hack and try to eke out a win whatever it takes - which is fine if you regard these problems as trophies to be won, but not so fine if you take them in the spirit intended.
The famous problems that OpenAI (primarily) are trying to trophy-shoot with AI are famous because some human mathematician such as Erdos had the taste to judge them as fruitful grounds for new math to be developed in the pursuit.
Until we're at the point where AI is capable of things like creativity, curiosity and continual learning, AI will remain reliant on humans to fundamentally advance math and give it new tools to apply. For humans to do this it is helpful if they are inspired by the challenges set by their peers, which is why AI solving these human challenges is so counter productive - the snake is eating it's own tail.
How can you be so sure of that? Like we know that human mathematicians can judge usefulness or insightfullnes. But we don't really know whether AI can do it even better. Like I don't think anyone has set up an evaluation of that.
Well, it is always was so? It doesn't matter if the person claiming things is impersonator or not, either you dive into the topic yourself and decide for yourself, or you wait for a consensus among specialists to settle.
I mean, in 2026, after the rise of the Internet, where lies are widespread, AND after the rise of an AI, that removed such anchors of truth as a video proof for example, I believe everyone smart spend some time meditation on an operational definition of truth and now has something that doesn't depend on knowledge that the source is not an impersonator.
About 2y ago, before AI was all the rage - lookup: controversy, scientific fraud networks, "paper mills"
The whole world has always been like this. It's just showing up with force here.
There's a huge lot of suicidal people who ideate their afterlife as "pursuing hobbies".
I believe you just captured the zeitgeist, friend.
Rather: you reject AI-written code if it is not of really good quality.
> At first I did not understand Fable’s explanations. But I asked questions, and then asked more questions, and drilled down towards the core of the problem. Gradually I started to understand parts of the argument. I have seen enough now to arrive at the tentative belief that the main result is possibly correct […] In the sections below I will try to explain what I have learned so far, and why I lean towards thinking it might be correct.
So the whole paper is about things the author does understand. (BTW the author David Harvey was behind the big advances in integer multiplication, in 2014 and 2019/2021.)
- You're right that it's possible Fable came up with a different o(n log n) algorithm that is not in OpenAI's paper, but (apart from being unlikely) it doesn't matter, as he talks of the belief that “the main result is possibly correct”, not necessarily that OpenAI's paper is: whether the argument comes from the paper or from Fable, the question of interest is whether multiplication is really possible in o(n log n) time. The point is that there's a genuine idea here, somewhere between OpenAI's paper and Fable's explanation of it and the author's understanding of it.
- This is in fact how mathematicians have evaluated papers for decades: is there any way this result could be true? Is there an actual idea here that could help? Do I understand enough of the argument to be convinced it's likely true, modulo some details that need to be filled in? The last step (actually filling in the details) happens when teaching it to someone else or writing it again in one's own words.
@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...
This is very odd, because it just doesn't match my experience with these systems at all. Yes, they do generally SOUND confident, but code (say) that's hard for me to understand is usually hard for the machine to understand as well, and while it is more indefatigable than I am, it's not brighter.
This mathematician is in a very good place to evaluate whether Fable gets it or not, but it's weird and counter to my experience.
Fable is good, especially at conceptual stuff, don’t get me wrong, but it has limits. Opus 5.5 is a machine at getting correct code out once the concepts are in place. But I can’t trust either to not make mistakes.
Heck, I can do this too, with my eyeballs and brain! Just slower and will less overall memorized knowledge than modern LLMs.
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 _____"
Big O is sort of like <=. little o is sort of like <.
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.)
For what it's worth you can leave out the 'sufficiently large n' part, assuming we're talking about positive integers (or continuous functions on the nonnegative reals). I like to leave it in though because it makes the jump to defining both o, O and Theta in terms of lim sup f/g a little easier.
I don't think any of those are right. The latter two are trivially equivalent, the former also is since it differs by a factor of at most 3 for all n >= 1.
I still think the simplest definition for o(f) is 'g in o(g) iff O(g) is a proper subset of O(f)'. Or you can just say g is dominated by f in the sense that lim sup g/f = 0.
I'm fairly sure those two are equivalent, but it's a good little exercise.
Lim f/g -> C a constant
Lim f/h -> 0If you were joking then maybe you got me
This isn't quite correct. O(g) doesn't require the limit to exist.
https://stackoverflow.com/questions/1364444/difference-betwe...
f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
s/must shrink/must eventually shrink, after finitely many n/
Equivalently, must go to zero in the limit.
But you're not right in that the upper bound of that expression eventually stops decreasing, in fact for simple f and g as long as f is positive and eventually bounded by g the expression will decrease infinitely often if my intuition is correct
In fact, he refers to Landau for the definition of little-o.
The big O notation is very often used to denote exact complexity of an algorithm even if the notation is technically an upper bound.
The little o notation is usually used to denote a small asymptotic improvement over some known complexity.
For example if some sublinear algorithm would have n^(7/8) complexity - would be probably advertised as big O of that. But n^(1-eps) is shared as o(n) with exact constant provided as a detail.
This is the future.
Advanced AIs are basically genie's bound only by the laws of nature (which are necessarily the known laws). You ask the genie for something and if it's possible, it will grant your wish. What it does will seem like magic to you or I, and while in theory there is an explanation for the magic it's preforming, in reality an explanation could be as complex as understanding how the AI itself works at the level of its weights. It's not something a human mind can do.
The genie might give you a cure for cancer, but you won't know how it works. It's possible it will cure all cancer but with some hidden cost. A cost we cannot know and one we must trust the genie is both aware of and would inform us of. Maybe it will make us more trusting of the genie, or maybe it will just make us all drop dead in 20 years time.
The world we are now entering will look similar to the world native populations entered when they encountered Europeans. Suddenly people were turning off the sun and yielding magic kill sticks. It was basically impossible to reason about what might or might not be possible.
This future, is for now, still optional. We can still decide if we want it, but when the genie in its final arrives, perhaps one of the only things it won't be able to grant us is the ability to undo time and take back our decision if we later decide it was a mistake.
The most important thing about this paper is that it's describing human loss of control. A world where we are no longer the masters of our own destiny.
I'm not sure what argument fable gave him, but this part seems not horribly difficult to prove. I'm sure i'm missing something since i'm not that great at this kind of math.
The short reason is that each slice call can at most double the number of nonzero entries, but a transform that would enable g < m must turn a single nonzero entry into (2^m) nonzero entries in a single call.
Since the permutes can't generate non-zero entries (since they only move things around), you actually need exactly m slice calls in the initial 2-instruction model given (where you can only do slices and permutes) precisely because of the need to create 2^m non-zero entries where each individual slice op can only double the number (and permutes do nothing)
Astra actually comes up with a variant of this argument as well: https://gist.github.com/dberlin/e785c51aff0285c9c0a3ea0f24fa...
Interestingly, the operations discussed in this part of the note are, I think, pretty much exactly the operations needed to operate on classical representations of an m-qubit quantum state, implementing single-qubit unitary quantum gates on each qubit.
I suspect that, if you had asked me fifteen years ago if I thought you could do the same exact operations like this on each of n different states (on a classical computer) faster than n times however long it would take to do it once, I would have said “sure, why not?” It probably helps that I worked with people who really liked matrix multiplication and similar problems :)
For fun, I have ChatGPT Pro chewing on the following prompt:
Suppose I have a m-qubit quantum state. I can do an operation U = U_1 \otimes ... \otimes U_m, which is just a unitary operation on each individual register.
I can also simulate this on a classical computer. Start with the state, written out classically as a complex amplitude for each state in the computational basis (i.e. 2^m complex numbers). U acts on this state in a linear manner to produce a new state. What's the classical time complexity of this? (Assume a model of computation with exact complex addition, multiplication, conjugation, etc taking unit time, but don't cheat by encoding absurd things into complex numbers. Assume data movement is free.)
Now suppose I want to apply the same U to n separate input states. Can I do better than n times however long it takes to do the operation once?
All of these algorithms are neat but utterly ridiculous :)
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.
I can't quite work out whether the author is demonstrating comedy, is having a hysteria from a breakdown, or if it's something in between, but it completely captures the feeling at the moment of being usurped and out-gunned by AI tooling as a knowledge worker.
That made me chuckle...
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.
>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.
There are many ways to communicate ideas, and most people in most situations rely not upon proofs derived through deductive logic. They rely instead upon persuasion, intuition, and building associations between ideas. Those tactics are in many ways more natural (as in, fairly direct consequences of brain structure rooted in biology) but with known flaws. LLMs are pure persuasion, and operate entirely in that realm. They can be cajoled into repeating logically unsound ideas in much the same ways humans can. And, they can do the same back to us.
My concern is that having one model generate a paper, and then using another model to explain and answer questions about the paper, could run the risk, especially in arenas where the number of individuals with deep deductive knowledge of the subject is small, of optimizing for persuading those individuals rather than proving real results to them. Since it's reasonable to presume the model has been trained on other explanations which have convinced the expert, and on convincing people generally (which, on balance, uses more flawed intuitive explanations to persuade rather than prove), it should be very good at least at creating an environment where the expert would need to practice extreme skepticism and fully utilize critical thinking to attack every element of every claim. That can be very challenging.
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.
> I do not blame the Company for getting there first. Who got there first is an irrelevant detail, a historical footnote
Oh, such a noble mathematician, he's so above the questions of moral, Truth is all that matters.
Almost as much as a paycheck from the Company.
Higgledy-piggledy,
Schönhage–Strassen’s old
Floor was supposed to be
Perfectly sound.
Little o n log n
Unsentimentally
Sends their conjecture six
Feet underground.In either case, no practical algorithm is expected to come from it, because the asymptotic gain isn't realized for practical input sizes--sometimes called a "galactic algorithm". But it's theoretically very interesting for breaking through a conjectured barrier.
* 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.
A useful performance measure for the evaluation of a function in hardware is the latency of the operation expressed as a multiple of the delay through some standard simple logic gate, e.g. the FO4 delay (of an inverter with a fan-out of 4) that is frequently used in CMOS technology.
While a multiplication can be done in a single clock-cycle if you choose so, the duration of that clock cycle in FO4 delays increases with the size of the numbers that are multiplied, and it is interesting to know how fast it increases with a given multiplication algorithm.
If a multiplication algorithm that claims to be faster when expressed in some abstract operations leads to a FO4 delay number that actually grows faster with the length in bits of the operands, than that algorithm is worse in practice.
Treating OAI's name like Voldemort reads as emotionally immature to me
If anything, I'd treat him as a table of contents to things other people do.
Previous time it was "I don't care about ai papers by default, so who cares"
either way it's not good to not even try and to "proudly" put your lack of effort front and forward
Oh? Well I have not checked most of the details either, but I think that the claimed o(n log n) bound is not plausible at all.
Can someone please check most of the details of the paper and resolve our disagreement with Mr Harvey?
For one thing, this is a model that works; see for example Terry Tao's usage of ChatGPT (https://chatgpt.com/share/6a5fdc7a-d6f8-83e8-bbea-8deb42cfed...) to understand the counterexample to the Jacobian conjecture (though in that case there was no paper to read), and then writing it up (https://terrytao.wordpress.com/2026/07/21/a-digestion-of-the...). This seems exactly parallel here?
For another thing, mathematicians have always followed a practice of not reading papers, or at least not reading them very closely. Writing is a poor medium for the transmission of ideas (Thurston has written about this in many places), and see also https://x.com/littmath/status/2107670379858895001:
> I once had a conversation with Akshay Venkatesh where he was explaining some result to me and I commented “wow, you read that [difficult] paper?” And he replied “well, I imagined I read it.” Made a big impression on me.
and https://x.com/littmath/status/2107827516367110211:
> A lot of people—me included—do not enjoy reading LLM outputs. There’s an alternative!
> Personally I have always been very bad at reading mathematics. But you don’t have to read it by reading it, if that makes sense. Rather, you think in its general vicinity.
The fact that he didn't read the paper and he's talking about it as if he did.
As I said in the comment above, reading a paper has never been a good way of understanding what is in it; usually you either have someone give a talk or get it explained to you. Besides, as in another thread above (https://news.ycombinator.com/item?id=50195392), what matters here is not what the paper says, but whether an o(n log n) algorithm exists. Harvey's write-up is about some (new) intuition around why we should expect one (i.e. why we should expect something like the paper's proposed algorithm to be correct).
To be specific: is your problem that, having been provoked by the announcement into thinking more carefully about the problem, he has shared whatever understanding he has arrived at, without literally reading every word of the (poorly written) paper? Why is that a problem, according to you?
As I said in the linked comment, it does not matter whether the idea came from OpenAI's paper, or was hallucinated by Fable, or was arrived at by the reader while reading a potential nonsensical explanation from Fable: the main message is that the “o(n log n) bound is plausible” and it is valuable to have it come from a human expert.
Stopped reading right after that. Why is this so high up on HN? It's literally nothing.
The expansion (on p3) of the statement after which you stopped reading goes on to explain that one of the issues is that these results have not been delivered in a humanly intelligible form. (“… the maths dump does not appear to be strong on exposition”).
Your question would have been answered if you'd just read a little more
web.maths.unsw.edu.au fills the whole address bar on mobile