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.
> 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].
> 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
> 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.
I mean, this gets to the heart of the is mathematics invented or discovered question. It seems like maybe you haven't thought about this before but his point seems to be, if this sort of machinery does exist, it can be discovered. It has now been discovered, it was waiting for us the whole time, who was the first to find it doesn't matter. I'm not sure what you're implying either. Should there be forbidden math? How is that not silly?
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.
> 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.
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 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.
More realistically, that impersonator has created lots of output, and the correct ones are selectively publicized (and few particularly interesting bad answers).
The recent progress does not imply that the "impersonator" has a deep understanding of mathematics. By formalizing a problem in Lean, constructing the proof is essentially a complex search. Because Lean is the arbitrator of correctness, the "impersonator" can make as many mistakes as they want until they find a solution that passes the checker. That is very different from checking a paper for correctness.
To an extent, that is what automated theorem provers (e.g., SAT/SMT solvers) do quite successfully. The monkeys have very good heuristics and avoid going down unnecessary paths, but they are still monkeys. Similarly, AI might be very good at recognizing patterns (which is very useful!), but doesn't necessarily demonstrate any kind of real understanding.
Not at all. It's an open question and it's also probably semantically ambiguous. It's cliche to the extent that recently it comes up repeatedly. Regardless of all that it's nonetheless a valid question.
Please go ahead and provide a working definition of what "understanding" means, in a way that an information processing system can be objectively classified as "understanding" or "non-understanding".
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.
You seem to be agreeing with me. I said it's an open question so expecting me to rigorously answer it in an HN comment is quite absurd, no?
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.
It's not just an open question. It's such a fundamentally vague and imprecise concept, that it is not approachable, even in principle. Just like consciousness, as you correctly point out.
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.
Of course humans make mistakes, but (outside of Lean at least) they attempt to solve it with experience, understanding, and a certain amount of creativity instead of mashing things together until something works out.
complex searches are quite valuable in mathematics. For example, Maryna Viazovska's fields medal was for finding the right gadget (roughly, a complex search) to prove optimality results in sphere packings.
Right, my comment was not about its usefulness. I was merely pointing out that those results do not necessarily imply any kind of actual understanding.
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.
> But perhaps mathematicians are no longer able to be the best judge if a proof is valid
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.
> It seems they are still the best judge of whether a proof is useful or insightful though.
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.
> Very simple thought exercise that allows to conclude, someone "saying they understood" (or agree) bears absolutely no weight to something's validity.
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.
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!
I've seen this claim repeated a bunch of times, it spreads as a meme, but the analogy doesn't work that well? This is not a special feature of biology! Chemical engineering involves lots of trial and error, physics is all about neglecting complicated aspects of a situation and hoping the result is still useful, even fundamental physics has a bunch of cancelations that work with no very good justification (see troubles around renormalization) and then fail when you try to do quantum gravity. Even math has things we know are true but have no good conception of why -- see John Conway on the Monster Group ("there's never been any kind of explanation for why it's there"): https://m.youtube.com/watch?v=xOCe5HUObD4
The whole world has always been like this. It's just showing up with force here.
Why, some morons have been summoning the Singularity for quite a while. Ask them what they're gonna do in that Singularity and get an answer along the lines of "pursuing hobbies".
There's a huge lot of suicidal people that idealize their afterlife as "pursuing hobbies".
The same is happening with AI-written codebase. You don't read AI written code, you ask an AI to explain it to you. Not that it's either a healthy place to be...
In my experience dealing with people who use LLMs, approximately none of them do this. The feeling of productivity LLMs create is maximized if you just blindly accept everything they produce, and apparently as a field we've broadly given up on what little quality we had before to chase that feeling (and to boost the valuation of a couple companies).
This is typical of working with agents, not only maths. "I implemented this with agent A, and don't understand the logic, but agent B think its correct". But then you ask a simple clarifying questions to B on a random thing in the code and it'll tell you that this part is actually wrong. At least in maths they have Lean...
This is just textbook Gell-Mann amnesia. If the author doesn't read the paper how can he possibly know that? Even in this case when it's someone who has related knowledge, how can you know that you're being told something that's actually in the paper? LLMs confidently state nonsense all the time because there's no difference between how they produce a correct or incorrect answer. LLMs seem incredibly good at convincing people that they're now experts in everything. "Drilling down" is just giving more and more opportunities for that to happen.
Gell-Mann amnesia doesn't really apply to the world expert on a topic discussing a paper that builds on his own work. It might apply to a world expert on a topic discussing a topic on which he is not an expert.
- The author is already the world's best expert on this topic.
- 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.
Who thought four years ago or even two years ago that we would be in a place where these models are coming up with solutions that our best minds have a hard time comprehending and can’t do it without their help. What a time to be alive.
If I didn’t know David Harvey personally (though a decade removed) I would agree. I’m reconsidering my stance on AI lately and while I still find much of this disconcerting, I begrudgingly accept that his approach of "feed the paper into a different model and make it explain the technical bits until I fully understand it" is perhaps an increasingly valid approach to digesting mathematics. One needs to be incredibly principled in this practice. But that’s exactly how I’d describe David.
> 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
why does the website force people to log in to see the proofs? also, why does it not have something like a "export all lean" button to download all of the lean code that proves a theorem (dependencies included) so it can be easily checked offline? finally, the campaign you gave has a mission "Integer Multiplication in O(n (log n)^(1-κ)) Time" and it's listed as completed, but i checked the graph and it directly depends on something that's listed as "Open" ("Full multiplication bound at κ = 0.000051016920170078"). is it fair to call it completed then?
Thanks for checking out the site. All of the Lean that is generated with an open-source license is exported daily here: https://github.com/prove2me/formalpedia
The graph has an AND-OR structure. Each node (circle) is a theorem statement, and each directed hyperedge (square) is an implication. To prove a theorem statement, all of the children of one implication must be proved.
- What personal data you process and retain (login details, access logs, statistics, etc.)
- How long you retain it
- Who (which human, name and email) to contact when you have questions
- Which third parties get the data (if you use Google fonts, Google would be one of those, since it gets the users IP), etc.
That's the sort of default stuff that must be in a privacy policy, there are a few more things that you'd need to comply with GDPR and the UK's equivalent, but that's the kind of thing you need. :)
yes f(n) tending to 1 as n tends to infinity is the worthy goal. how slowly it gets there would determine whether the growth is effectively O(n) or something slightly larger but that refinement can come later.
Either you care about advancing the frontier of knowledge or you don't. If you care, then you should use every tool available to you. If you don't, then society has no obligation to fund your personal hobby interests. Calling this "selling out" is ridiculous.
Remote alien knowledge doesn't give us new useful tools unless we make contact with them. Fortunately we now have contact with alien intelligence right here that is providing us with useful tools.
True, but something is qualitatively different. Similar to open-source software projects, where people used to participate for the love of the game. Now that machines are doing the work, there is less human connection and feeling of community.
Why bother contributing when there's no one on the other side. There's value being produced, but the beneficiary is mainly the corporations who run the models. Even if the result eventually benefits society in general, the credit goes to them. Not that "credit" or "clout" means much practically, but there used to be emotional and social value for the people involved.
There is still emotional and social value. The AI is a tool in the hands of a competent operator.
You’re blinded by your hate for corporations, if you cannot see value here. The actual human who’s working on it responds, and you can’t help but make it about the AI that you believe is somehow only benefiting the corporation.
David Harvey, the author of the paper linked here, hasn't even read the paper on the topic. He says as much in the paper, directly. The repo linked in response shows little sign of human authorship.
Has anyone actually gone through and fully understood the contents? My bet would be that nobody has looked, let alone understood, anything in there.
If you know something to be true, without knowing why, does that reduce the value of said truth? And what if that truth has positive effects on your ability to invent and leverage technology, treat/cure disease, etc? Would you still say it is of no value and people are “falling for it”?
This is called faith, and as strange as it may sound, in a few decades this kind of faith in the machine will be commonplace, because it will prove its utility over and over and over again, and save mountains of human effort in the process. In 3-7 years we’ll start to see major practical applications from AI-led advances.
As a second-order effect we may even see the rise of an actual religion around AI. I’m not saying these are all positive effects, but it’s what I see happening - and like all technological revolutions there will be a huge number of positive effects alongside some deeply disturbing developments.
Why should humans care about any of this when the machine can just refill our cat food dish and wave some feathers on a string to keep us entertained?
Either what you say is true, in which case I see no reason to care about truth, science, or math (the machines will figure it out for me), or it isn't, and people are falling for dealing with slop on behalf of people too lazy to look at the turds they purchased.
Either way, I don't see any reason to participate in AI projects without getting paid.
Yes, that I agree is definitely happening already. Like Arthur Clarke's famous saying about sufficiently advanced technology being indistinguishable from magic.
And it's true that these changes are not all positive or negative, that there is actual social value being produced by machine-generated mathematics, software, writing, visual works, etc. And that it's changing human culture in ways difficult to imagine while we're in the midst of the transformation.
I'll add another prediction: AI will become more and more "human" until it becomes indistinguishable practically. Eventually we will merge with it to become something more than human.
> Has anyone actually gone through and fully understood the contents?
It happened before. For example in Wiles' proof of Fermat's Last Theorem it took like half a year until someone found an error, another year until Wiles and Taylor fixed the proof and another half year until it was reviewed and published. Add a few years until it was widely understood (where widely is a small set of people that excludes me for now). Now there are even shorter proof.
The new thing here is that we are seen the internal discussion published online. Also, the chatbots like to make long pdf, so expect to see a pile of intermediate pdf created by chatbots+humans until we get a nice proof that is widely understood (this is more related to my area, I have a hope that I may understand it).
Why not embrace nihilism now instead taking the long way to get there?
At the end of the day there is no reason, there is no purpose but the one you make for yourself. The universe doesn't care and will slowly wind itself down to thermal noise.
If they want to make a lean solution and publish it then they can because that's what they want to do.
And if you're breaking this much already, the future is going to be really really hard on you. You are not ready for what is coming.
You keep saying this human connection thing, but it has no bearing on moving the frontier forward. A lot of these problems have remained unsolved for hundreds of years. What is your claim here, that they should remain unsolved artificially for 100 more years so that human mathematicians can have careers and community?
We need to design an AIGPL - you can only use the collective expertise that created our code to train a model if the model, its training data and potentially its output are also available via AIGPL.
> Why would someone contribute to an AI project without getting paid?
Because there exist people who are in deep love for mathematics, but weren't able to get a research position (or cannot afford to take a temporary position at some university for which they would even have to relocate).
So, your question is more like: why would someone play a video game without getting paid?
It is just going to help the capitalist of the world. Last time I checked many people are having $0 in their bank balance. Contributing is officially a scam for humanity.
>
For this work, you're either inserting coins into Codex, effectively donating money
Rather: as a necessary evil you give money to OpenAI/Anthropic because you really want to see (ideally fast) progress on this mathematical/algorithmic problem.
That's like saying "you love cooking, so for fast progress you insert coins into doordash to make fast progress on a meal". If you do that, you don't love cooking.
It's fundamentally incongruous with someone that "loves the game". And I hope that you have a good excuse for ruining it, hopefully a seven or eight figure excuse.
> That's like saying "you love cooking, so for fast progress you insert coins into doordash to make fast progress on a meal". If you do that, you don't love cooking.
Rather, it's like saying "I love eating good food."
One approach is to learn to cook excellently, buy high-quality ingredients etc. Then invest time to cook a delicious meal. This is like learning math, becoming exceptional in one area, and then work on the problem.
Another approach is to go to a well-rated restaurant, order some food there, and pay a decent amount of money for the food. This is like buying AI tokens, and setting up some agents to work on math problems.
Both approaches are suitable. And I guess/hope many people who really would love to contribute to progress in mathematics would really prefer to go the first way. But because
- they are not highly gifted
- have a time-consuming daily job and/or family
- simply cannot afford the high opportunity cost to get to a suitable level in math
- ...
the only way such people can contribute to progress in math is the second approach. That's why these people behave like they do.
I am quite confident that most of such contributors don't like that their money lands in the hands of OpenAI/Anthropic.
So: Which approach would you recommend these people who are really eager to contribute to progress on some mathematical problems?
So, what's the game you claim to love? Wading through piles of poorly written proof and trying to de-slop it?
If people can't contribute to math, then they can't contribute to math. Making things unpleasant for mathematics may give you revenge, but it won't make you happy.
Coming back to the particular project at the top of this thread (not TFA but the top comment), I don't see a problem with contributing to Lean verifications. One of the problems with the OpenAI dump is that half of it might be wrong, and formalizations resolve that. This is particularly relevant for this result, which is one of the few claims that didn't go in the direction one would expect before the drop.
You can for sure criticize OpenAI for not having done it themselves (I hereby do!). I guess you could make a case that engaging with their results somehow legitimizes their actions, but a) I don't expect OpenAI to care about this enough for it to matter, and b) you aren't making this case but a stronger one that any engagement somehow ruins mathematics and must be done for money. I don't think so! [1]
I personally am a complete amateur, but find this result one of the few overwhelmingly positive aspects of the drop. It's something people weren't expecting, so it probably saves time that would have been spent on trying to prove the O(n log n) lower bound; it's about a question that is extremely natural ("how fast can you multiply really big numbers", that's like the eight-year-old's vision of what math is!) and shows that there is absurdly complicated structure even behind the simplest things, which is why math is not getting "solved"; it didn't kill the question but started a whole program of trying to optimize the algorithm (currently AI-assisted, but I hope that if all AI magically disappeared tomorrow, in a few years people would be able to get there unassisted), plus TFA lists several other problems this algorithm could help with at the end of section 4.
That's the game I love, at least.
[1]: This was best put by Nestor Guillen (https://terrytao.wordpress.com/2026/09/13/happy-those-able-t...): AI with all its drama (of economic and political origin) is separate from LLMs the technology, which only work because they build on a corpus of intelligent text, including a lot of math. Had it been made by a responsible organization, and had it appeared more gradually, it could be treated as an amazing tool for literature search and testing how far a brute-force approach can go, which would only help test the value of new ideas. There is some shard of this in our actual situation as well, beneath all the politics.
Those people generally care about learning, IME. "Why would someone play a video game without getting paid?", more like "Why would someone pay money to have a bot play a videogame without getting paid?". People IRL do, of course; they tend to be antisocial and make the game worse for everyone else.
Mostly because it's been a social project where humans collaborate with each other. As AI usage expands, though, I increasingly don't expect to be contributing without getting paid.
Can you explain why the author makes this remark? I'm not a math person. I thought having a Lean formalized proof was the only way these models were able to get through complex math proofs. My naive thought was that you could set an LLM loose on a math problem and it would try to build the Lean to get you from your starting point to a proven result. And the fact that Lean is machine checkable is how AI tools are able to do this autonomously.
So why would the author claim there isn't a Lean proof available? Shouldn't there be?
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's interesting that in terms of practical implementations, since each multiply can be done as a series of bit-shifts and additions, and since each element of an FFT is just the solution of a polynomial (a series of multiply-accumulates), in theory it's theoretically possible to do a full FFT in a single cpu clock cycle, much as it's possible to do a single multiply or multiply-accumulate in a single clock cycle (via parallel shift-accumulate operations). It would take a ridiculous number of transistors to implement though.
Whether something can be done in a single clock cycle is not useful to know, because this does not say how long is that clock cycle.
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.
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.
> 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).
> 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).
Which is exactly what the capitalists that own these systems want. Divide and conquer.
"Pay no attention to the men who are responsible for you situation, instead pointlessly fight amongst yourselves."
I don't think integrity is the reason for it. If you don't see it as an irredeemable moral issue for people to have worked at AI companies, then it is not a matter of integrity that you don't shun them.
Or, you might consider it a moral issue but may not believe that shunning is not the way to achieve a positive result. Also not a failure of integrity.
> Which is exactly what the capitalists that own these systems want. Divide and conquer.
> "Pay no attention to the men who are responsible for you situation, instead pointlessly fight amongst yourselves."
Maybe so, but that advice is for the western left, who openly and boastfully despises the working class these days. They might have thought about that if they wanted any "working class solidarity". It's been a staggering achievement either incompetence or coordinated malice that they could flip the balance of blue collar voters to right-wing parties in a generation. They chose who they wanted to lie with.
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!
not at all. even the previous O(n \log n) multiplier is almost never used in practice. In general fourier-based multipliers only start being useful at a minimum when you are multiplying 1000-digit numbers, but even that threshold is low/contentious. they have a definite advantage for ~10,000-digit numbers. this likely has larger overhead, so is only plausibly useful for even larger numbers. you do not often have to multiply these extremely large numbers.
To understand the new integer multiplication algorithm, one must first understand essentially everything in the 2021 algorithm. It is impossible for me to explain all of this here ... Readers interested in the details should consult [HvdH21 - his paper], which by all accounts is a superbly written paper.
The one part that sort of surprises me is he says "The second thing we are missing is that the Model has not in fact found a way of obtaining
a program with g < m. (Moreover, Fable tells me this is impossible, but I do not follow the argument yet.)"
I'm not sure what argument fable gave him, but this part seems not horriblydifficult 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 the a transform that would enable g < m must turn a single nonzero entry into (2^m) nonzero entries.
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 model given (where you can only do slices and permutes) because of the need to create 2^m non-zero entries where each individual op can only double the number.
I think you have an also have not disproven the existence of a magical gadget of this general style. The programs mentioned in the paper have a very restrictive form, and I think you’re right that a program of that sort cannot propagate information through the array faster than the naive algorithm. But the actual average-case-ish gadget mentioned later is not of that form - it also has additions and maybe other things going on.
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 twenty 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 :)
The answer I got back makes me suspicious that quite a few of the recent OpenAI improvements on problems that involve some sort of multiplication are are related to each other and may even be, in some sense, examples of the same insight.
I actually agree with what you wrote. I'm specifically referring to the very restricted instruction set and not the later one where it is allowed another type of operation. It is actually the earlier he claims not to understand the argument about and that is the one I tjink is fairly straightforward.
Question is: do i still use the integer mull command of my cpu or should i write it myself in c. I think the hardware still wins. But will it have a impact on future cpu ALU designs?
Interesting that AI apparently doesn't write papers for humans: even experts struggle to understand them. But other AIs do. So AI basically writes papers for other AIs.
That's what reinforcement learning does when done this way, the AI is literally trained to write to itself in the way that will aid it to get to a solution most efficiently. I assume they still have some additional fine-tuning on top to keep the writing somewhat natural, but still.
> There is one other aspect of the situation that I would like to emphasise. After two weeks of very
hard work, I have managed to understand only a small fraction of [TC26a]. When I ask Fable about
the paper, it seems to read and understand the whole thing in just a few minutes, even starting
from a fresh context. I know that some readers may be uncomfortable with my anthropomorphic
terminology, but I believe that “understand” is accurate, in the sense that the LLM seems to be able
to correctly and lucidly answer all kinds of questions about the paper, including about some very
fiddly technical details. That is exactly how I would tell that a human colleague has “understood”
something. This chasm between human and LLM “speed of thought” is unsettling to say the least.
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.
All models still gets things wrong. Even Fable 5.1 I have to regularly correct when working on sufficiently complex code. So, I still want models to get smarter!
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.
As an aside, getting things wrong isn’t simply about not being smart enough, it’s also about the model insufficiently assessing whether it actually knows enough to conclude that some hypothesis is correct. As a human I have inner feelings of certainty and uncertainty regarding the things I am thinking about, which guide me in what I need to ascertain or verify more closely. My impression is that LLMs are lacking in that area, and it’s why they are most effective when there are external verification mechanisms.
These models have no self awareness. I just spent days having it write some test framework with very clear goals and it was highly confident understanding exactly what I wanted only for the whole thing to be complete bullshit, one remark from me about the work being useless and it goes “oh you’re absolutely right that’s on me”…
But your code was probably written by a human. This proof was generated by an LLM. Is it surprising then that it’s easier for an LLM to read than for a human?
Because a math proof is generally de-composable into smaller constituent arguments that can be independently evaluated for correctness. So you can audit a sample of these arguments for correctness without reviewing everything. You would then verify that the arguments being true implies the conclusion.
I would indeed expect most modern models to read the paper and be able to answer questions about them, usually even in a manner consistent with the original intent, irrespective of whether the source material is correct!
Heck, I can do this too, with my eyeballs and brain! Just slower and will less overall memorized knowledge than modern LLMs.
Author says he reads Zvi Mowshowitz because he agrees with the writer's views on AI; anyone have a quick summary or good article to check out to get a sense?
Zvi is a rationalist blogger who writes a lot of takes on AI news, here's recent coverage of how Washington is reacting to AI x-risk going mainstream with Jacob Coxon, the Hugging Face incident, etc: https://thezvi.substack.com/p/the-ai-preference-cascade-reac...
The main thing Zvi puts out is a weekly dump of everything that has happened in AI; it's super wide coverage but usually not a lot of analysis. As a warning, here's what he had to say about Midjourney Medical: https://thezvi.substack.com/p/ai-173-ai-pauses?open=false#%C... It's links to hypeful people with conflicts of interest, presented with no warnings about that. (For a more balanced response by Scott Alexander (a medical doctor), see https://www.astralcodexten.com/p/preliminary-thoughts-on-the...)
If anything, I'd treat him as a table of contents to things other people do.
I understand that because this was how I saw it until the Midjourney moment. Zvi is clearly a smart person (has a math and poker background) and very voluminous and confident. He's also often proven right, contrary to people like Ed Zitron or Gary Marcus, who tend to be dragged by events. Now I think that makes him dangerous if he's wrong about something, and also his writing usually made me vaguely anxious.
Not a mathematician, but I don't think there's any point to trying to put it in code at this point. Improvements seem to be coming rapidly at the moment.
This is integer multiplication, not matrix multiplication. The OpenAI dump also has a matrix multiplication improvement though.
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.
it doesn't. it might if you're multiplying numbers in the thousands of digits (but even that is almost assuredly too low). for essentially everyone this is purely a theoretical result.
yes, but even the dramatic underestimate shows how useless it is. I also imagine that current estimates could be significantly optimized if there was some usecase for them. the 1k-10k multiplication regime has actual usecases, so there has been some optimized implementations of theoretical integer multiplication algorithms in this regime.
Because it's an interesting case study of how quickly individual top human experts can understand and verify these mostly-autonomous breakthroughs in math and science. In this case, the world expert on integer multiplication algorithms has taken two weeks and only understood a fraction of the generated paper.
that's a fair point and that part is indeed interesting to a degree, and I would fully agree if it wouldn't be stated multiple times that the author did not actually read, i.e., properly engage with, any of the involved papers, but only used an LLM to talk about them. The author also emphasizes that they did not check the proof, or fully believe that the result is feasible. (Yes, I did in fact go back and read it)
I think you may be interpreting the author’s self-deprecating style and gallows humour a little too literally. I took “I have not read the paper” to mean “I have not been able to understand the paper by reading it”, or perhaps “I read the paper but could not follow it”. There’s no doubt that every word on the page did at some point enter the author’s eyeballs.
> Instead, I asked Fable to explain [TC26a] to me. Fable seems to understand the argument and thinks that it is correct. I expect that thousands of frontier LLM instances around the world have come to the same conclusion over the last two weeks. If not, surely we would have heard by now.
This is the future, and something I've been warning about for years.
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.
You have completely misunderstood the author's point - a misunderstanding that would have been easily avoided by reading just a little bit more of the 23 pages of detailed exposition which is very clearly not the outcome of a 'lack of effort'
I don't really understand any of the maths in this article, and spent ten minutes at the beginning trying to remember/rediscover what little-o is (I'm familiar with big-O, but not little-o), but this is absolutely one of the best things I have read in a very long time.
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.
Not only can these systems produce novel math proofs, they can write songs lamenting the feat (from the perspective of us humans). Ironically, I kind of like it:
https://youtu.be/zONGVaONKe8
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.
This is a very interesting read, but it causes me some concern. When I went to college, I majored in Computer Science, but I minored in Philosophy. A substantial part of philosophy deals with how arguments are explained and proven, and mathematics is a fairly direct outgrowth of that. Reading mathematics and computer science papers or proofs is quite different from reading more typical prose. They are often very rigid and extremely precise. A single symbol or word can change the integrity of the argument from unshakably true to entirely false. It requires much more care and effort to gain what feels like a true understanding of what they communicate - and that is an important and necessary part of their character.
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.
191 comments
[ 2.8 ms ] story [ 32.4 ms ] thread@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 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.
this does not feel like a healthy place to be
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.
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.
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...
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 that idealize 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.
- 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.
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!
The graph has an AND-OR structure. Each node (circle) is a theorem statement, and each directed hyperedge (square) is an implication. To prove a theorem statement, all of the children of one implication must be proved.
- How long you retain it
- Who (which human, name and email) to contact when you have questions
- Which third parties get the data (if you use Google fonts, Google would be one of those, since it gets the users IP), etc.
That's the sort of default stuff that must be in a privacy policy, there are a few more things that you'd need to comply with GDPR and the UK's equivalent, but that's the kind of thing you need. :)
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!!
The people using AI should be paid well enough that they can justify selling out their peers.
Why bother contributing when there's no one on the other side. There's value being produced, but the beneficiary is mainly the corporations who run the models. Even if the result eventually benefits society in general, the credit goes to them. Not that "credit" or "clout" means much practically, but there used to be emotional and social value for the people involved.
You’re blinded by your hate for corporations, if you cannot see value here. The actual human who’s working on it responds, and you can’t help but make it about the AI that you believe is somehow only benefiting the corporation.
Has anyone actually gone through and fully understood the contents? My bet would be that nobody has looked, let alone understood, anything in there.
This is called faith, and as strange as it may sound, in a few decades this kind of faith in the machine will be commonplace, because it will prove its utility over and over and over again, and save mountains of human effort in the process. In 3-7 years we’ll start to see major practical applications from AI-led advances.
As a second-order effect we may even see the rise of an actual religion around AI. I’m not saying these are all positive effects, but it’s what I see happening - and like all technological revolutions there will be a huge number of positive effects alongside some deeply disturbing developments.
Either what you say is true, in which case I see no reason to care about truth, science, or math (the machines will figure it out for me), or it isn't, and people are falling for dealing with slop on behalf of people too lazy to look at the turds they purchased.
Either way, I don't see any reason to participate in AI projects without getting paid.
Yes, that I agree is definitely happening already. Like Arthur Clarke's famous saying about sufficiently advanced technology being indistinguishable from magic.
And it's true that these changes are not all positive or negative, that there is actual social value being produced by machine-generated mathematics, software, writing, visual works, etc. And that it's changing human culture in ways difficult to imagine while we're in the midst of the transformation.
I'll add another prediction: AI will become more and more "human" until it becomes indistinguishable practically. Eventually we will merge with it to become something more than human.
Assuming it becomes capable end, why would it want to merge with meat? That's like predicting that humans will merge with goldfish.
It's simply predicting that the neo-neo-cortex will remain merged with the thing that it grew out of.
Intelligence is just a tool.
It happened before. For example in Wiles' proof of Fermat's Last Theorem it took like half a year until someone found an error, another year until Wiles and Taylor fixed the proof and another half year until it was reviewed and published. Add a few years until it was widely understood (where widely is a small set of people that excludes me for now). Now there are even shorter proof.
The new thing here is that we are seen the internal discussion published online. Also, the chatbots like to make long pdf, so expect to see a pile of intermediate pdf created by chatbots+humans until we get a nice proof that is widely understood (this is more related to my area, I have a hope that I may understand it).
At the end of the day there is no reason, there is no purpose but the one you make for yourself. The universe doesn't care and will slowly wind itself down to thermal noise.
If they want to make a lean solution and publish it then they can because that's what they want to do.
And if you're breaking this much already, the future is going to be really really hard on you. You are not ready for what is coming.
Because there exist people who are in deep love for mathematics, but weren't able to get a research position (or cannot afford to take a temporary position at some university for which they would even have to relocate).
So, your question is more like: why would someone play a video game without getting paid?
For this work, you're either inserting coins into Codex, effectively donating money, or you're shoveling your way through slop.
Rather: as a necessary evil you give money to OpenAI/Anthropic because you really want to see (ideally fast) progress on this mathematical/algorithmic problem.
It's fundamentally incongruous with someone that "loves the game". And I hope that you have a good excuse for ruining it, hopefully a seven or eight figure excuse.
Rather, it's like saying "I love eating good food."
One approach is to learn to cook excellently, buy high-quality ingredients etc. Then invest time to cook a delicious meal. This is like learning math, becoming exceptional in one area, and then work on the problem.
Another approach is to go to a well-rated restaurant, order some food there, and pay a decent amount of money for the food. This is like buying AI tokens, and setting up some agents to work on math problems.
Both approaches are suitable. And I guess/hope many people who really would love to contribute to progress in mathematics would really prefer to go the first way. But because
- they are not highly gifted
- have a time-consuming daily job and/or family
- simply cannot afford the high opportunity cost to get to a suitable level in math
- ...
the only way such people can contribute to progress in math is the second approach. That's why these people behave like they do.
I am quite confident that most of such contributors don't like that their money lands in the hands of OpenAI/Anthropic.
So: Which approach would you recommend these people who are really eager to contribute to progress on some mathematical problems?
If people can't contribute to math, then they can't contribute to math. Making things unpleasant for mathematics may give you revenge, but it won't make you happy.
Coming back to the particular project at the top of this thread (not TFA but the top comment), I don't see a problem with contributing to Lean verifications. One of the problems with the OpenAI dump is that half of it might be wrong, and formalizations resolve that. This is particularly relevant for this result, which is one of the few claims that didn't go in the direction one would expect before the drop.
You can for sure criticize OpenAI for not having done it themselves (I hereby do!). I guess you could make a case that engaging with their results somehow legitimizes their actions, but a) I don't expect OpenAI to care about this enough for it to matter, and b) you aren't making this case but a stronger one that any engagement somehow ruins mathematics and must be done for money. I don't think so! [1]
I personally am a complete amateur, but find this result one of the few overwhelmingly positive aspects of the drop. It's something people weren't expecting, so it probably saves time that would have been spent on trying to prove the O(n log n) lower bound; it's about a question that is extremely natural ("how fast can you multiply really big numbers", that's like the eight-year-old's vision of what math is!) and shows that there is absurdly complicated structure even behind the simplest things, which is why math is not getting "solved"; it didn't kill the question but started a whole program of trying to optimize the algorithm (currently AI-assisted, but I hope that if all AI magically disappeared tomorrow, in a few years people would be able to get there unassisted), plus TFA lists several other problems this algorithm could help with at the end of section 4.
That's the game I love, at least.
[1]: This was best put by Nestor Guillen (https://terrytao.wordpress.com/2026/09/13/happy-those-able-t...): AI with all its drama (of economic and political origin) is separate from LLMs the technology, which only work because they build on a corpus of intelligent text, including a lot of math. Had it been made by a responsible organization, and had it appeared more gradually, it could be treated as an amazing tool for literature search and testing how far a brute-force approach can go, which would only help test the value of new ideas. There is some shard of this in our actual situation as well, beneath all the politics.
So why would the author claim there isn't a Lean proof available? Shouldn't there be?
* 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.
web.maths.unsw.edu.au fills the whole address bar on mobile
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.
Which is exactly what the capitalists that own these systems want. Divide and conquer.
"Pay no attention to the men who are responsible for you situation, instead pointlessly fight amongst yourselves."
Or, you might consider it a moral issue but may not believe that shunning is not the way to achieve a positive result. Also not a failure of integrity.
> "Pay no attention to the men who are responsible for you situation, instead pointlessly fight amongst yourselves."
Maybe so, but that advice is for the western left, who openly and boastfully despises the working class these days. They might have thought about that if they wanted any "working class solidarity". It's been a staggering achievement either incompetence or coordinated malice that they could flip the balance of blue collar voters to right-wing parties in a generation. They chose who they wanted to lie with.
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.
That made me chuckle...
I'm not sure what argument fable gave him, but this part seems not horriblydifficult 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 the a transform that would enable g < m must turn a single nonzero entry into (2^m) nonzero entries.
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 model given (where you can only do slices and permutes) because of the need to create 2^m non-zero entries where each individual op can only double the number.
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 twenty 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 :)
All of these algorithms are neat but utterly ridiculous :)
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.
If anything, I'd treat him as a table of contents to things other people do.
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.
Stopped reading right after that. Why is this so high up on HN? It's literally nothing.
Your question would have been answered if you'd just read a little more
This is the future, and something I've been warning about for years.
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.
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
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.
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.