> 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?
> Why would someone contribute to an AI project without getting paid?
Because there exist people who are in deep love with 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?
> 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.
> 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.)
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.
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.
This clearly hit a nerve in very interesting ways!
Suppose we have a very convincing math PhD impersonator, agreeing and making some prepared smart-sounding comments saying they understood the proof and it seems to make sense - would it?
Well, most would say - NO! Obviously not, knowing this person was an impersonator. Others now knowing could be convinced of the validity.
Very simple thought exercise that allows to conclude, someone "saying they understood" (or agree) bears absolutely no weight to something's validity.
The idea that OpenAI's proofs are fake is contradicted by the response of mathematicians. Were they fake, mathematicians would not consider this release important enough to comment upon[1,2], as vixra always provided a steady supply of such writings. Nor would they be able to write expositions and simplifications, of which several are published each day on arxiv (just search OpenAI on arxiv to find them).
But perhaps mathematicians are no longer able to be the best judge if a proof is valid. Yet nobody but them is able to even understand what is claimed to have been resolved.
> 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.
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...
Why not? If mathematicians in the field cannot understand the papers, but tools at our disposal can, why not use them? What is "unhealthy" about that? Just seems like it's the reality of the world now.
If you can't understand what the machine has done, math is not being done. Math is not pushing symbols around to find sequences that follow all the rules. Math is the process of understanding how those sequences of symbols map to meanings. If you can't follow the proof but have validated it's correct, all you know is that it's a proof of something. Is it a proof of what's claimed in the adjacent plaintext? Who knows!
Math is about clear communication between people first and foremost. That's why Shinichi Mochizuki's claimed proof of the ABC conjecture isn't accepted - he's unable to communicate it to enough mathematicians to get a consensus on its validity. LLMs generating Lean proofs are basically following that same schema. Sure, something has been proven. But what? Where's the clear communication explaining it to the satisfaction of other mathematicians?
Why does this not feel like a healthy place to be?
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.
Yup, and it always has been, we don’t even understand how our bodies or minds work, yet we use them everyday
The amount of unimaginable complexity contained in a seemingly very tiny amount of matter to us, is incredible, and it’s all around us in nature
We’ve never had the capacity to fully comprehend neither ourselves nor the environment we live in. But we do our best, and we do survive and sometimes even thrive
The mistakes that lurked in radium, in arsenic, in leaded gas, in fallout downwind of nuclear tests ... all had the best tools that the previous generation knew.
None of them were okay. Those were small small tools with few (sometimes only one) uses.
Generations earlier, famines, diseases and lead-leeching plumbing made rulers insane and entire cities of people die without any help from the "best tools".
Scifi is always written about the best tools. The issues arrive in the tools and in the hands that wield them both.
What a funny pov?? Mathematics and other pure sciences are about human understanding. You're saying if humans cannot understand the thing that was for human understanding, that's ok? That's like saying all the world's food is now inedible, but that's ok because a blender can consume it still.
The "top layer" of maths being this is one thing. Now imagine another layer of this. Then another. Then another. Then another.
At one point intuition helps to build out usage of the math itself. See stuff like "oh I can do rotations through matrix multiplication"-style ideas.
It is helpful for us to be able to reach for those tools quickly. The more tools that require advanced prep to use, the less we'll be able to use the results in easier contexts. Everything will be hard
Of course nothing really prevents people from looking for the simpler tools and proofs. Lots of math stuff starts off complicated and gets simpler.
There are a few increasingly powerful companies that own the frontier models that can produces these results. In the future, it may only be these models that understand the results. Should we be beholden to a few companies for basic understanding of foundational principals?
I'm not a mathematician but from what I've heard from them that's generally not how mathematics works. You can "use" whatever you want, of course, but a mathematician's goal and main activity is finding and understanding proofs. The ones I knew also liked compiling error lists for math textbooks and sending them to the authors. (It opened my eyes because I admit to have been one of those ignorants who implicitly assumed "it's formal stuff in a book, sure it's going to be right".)
The tool may malfunction. Indeed there are theorems that say the tool must malfunction at least sometimes.
If you don't understand the subject and relies on the understanding of the tool, how will you have a frigging chance of catching an error?
Anyway this reminds me that scene in Matrix 2, where the mayor (of sorts, don't remember his exact title) of Zion tells Neo about the machines that keeps everyone alive, but that there is nobody left that understands how they work or could repair them if they broke.
because the tools can't?
Lol. That's not how it works. Am I in the twilight zone?
All this anthropomorphism of literal statistical text generators.
Yes they exhibit generated sentences of text that describe coherent responses about a topic when there's an inordinate amount of research material in the training data from which they are distilling sentences of sound and rational thought. That's the ONLY way it can possibly work. There are so many scenarios where the training data isn't setup like that and low and behold the generated responses are just literal garbage.
Honestly 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.
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 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 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!
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 who ideate their afterlife as "pursuing hobbies".
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.
> 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].
> 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.
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.
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.
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.
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”…
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.
To complement on other comments that have already provided definitions.
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.
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
Awesome write up and intro by a fellow Sydney-sider, kept me hooked! As someone who's not a maths wizard, the technical details flew by my head but the prose allowing me to empathise deeply with those in the field was very enlightening. I never realised how big of a deal the maths dump was and how much it has shaken up the field. I guess we are all just trying to figure out this whole "intelligence on tap" thing together.
You don’t need to be a math wizard. Just upload the paper to an AI and ask, “Explain this like I’m five.” Then, with each follow-up prompt, increase the age and level of expertise you want it to assume.
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 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)
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 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?
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 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 about their enlightened betters who just got done with decades belittling and bullying them with "Dey terk er jerbs" and "Just learn to code" getting a bit of the treatment. Interesting times, maybe we should quit whining about AI derkin der jerbs and 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 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.
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.
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.
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.
> 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.
> 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?
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
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.
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.
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.
Come on. Prof David Harvey is the leading expert on this exact topic (integer multiplication algorithms), and here he has spent a lot of effort and time to digest the main new idea(s), and write 30+ pages explaining exactly what he's understood and why he believes the result is plausible. About the main “gadget”, he writes “I have worked through all the steps pretty carefully, and I think it checks out.” All this is useful information, and is the best we have so far from a reliable human source. I think it deserves more than a flippant response to the first line.
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.
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.
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?
> 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.
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.
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.
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.
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)
Because the author is one of the only humans who fully understands the O(n log n) algorithm that this o(n log n) result claims to improve on - he is a co-author of the 2019 O(n log n) breakthrough result.
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”).
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?
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.
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...
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'
> It would be good to have a formalised proof of the o(n log n) result, for example in Lean. As far as I can tell, one does not yet exist.
The result is fully formalized in Lean by @platypii and myself (on Mathlib's TM2 machine), with ongoing improvements to the exponent (currently at 1-2^-14.38): https://github.com/platypii/integer-mult-bounds-lean
Contributions are welcome!
[dead]
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?
It's missing a privacy policy, so not sure why you require login for users
[flagged]
> Why would someone contribute to an AI project without getting paid?
Because there exist people who are in deep love with 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?
14 replies →
They're all equally contributing to mathematics?
27 replies →
What does AI have to do with it?
1 reply →
Why would someone contribute to open source without getting paid?
3 replies →
Why would someone help solve cancer if AI worked on it?
1 reply →
Well lets give these models a grand challenge then.
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!!
You forgot to specify that f(n) approaches 1 so that is an easy challenge
1 reply →
> I have not actually read the paper. In fact, there are three closely related papers [TC26a], [TC26b], [TC26c], and I have not read any of them. I tried, but soon gave up. The math(s) dump does not appear to be strong on exposition. Instead, I asked Fable to explain [TC26a] to me. Fable seems to understand the argument and thinks that it is correct.
this does not feel like a healthy place to be
The very next lines say:
> 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.)
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.
2 replies →
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.
This clearly hit a nerve in very interesting ways!
Suppose we have a very convincing math PhD impersonator, agreeing and making some prepared smart-sounding comments saying they understood the proof and it seems to make sense - would it?
Well, most would say - NO! Obviously not, knowing this person was an impersonator. Others now knowing could be convinced of the validity.
Very simple thought exercise that allows to conclude, someone "saying they understood" (or agree) bears absolutely no weight to something's validity.
The idea that OpenAI's proofs are fake is contradicted by the response of mathematicians. Were they fake, mathematicians would not consider this release important enough to comment upon[1,2], as vixra always provided a steady supply of such writings. Nor would they be able to write expositions and simplifications, of which several are published each day on arxiv (just search OpenAI on arxiv to find them).
But perhaps mathematicians are no longer able to be the best judge if a proof is valid. Yet nobody but them is able to even understand what is claimed to have been resolved.
It is really strange to see mathematicians of the highest rank taking these results seriously[3], holding lectures explaining them, yet see it dismissed here as a mass psychosis. [1]https://smf.emath.fr/actualites-smf/20-10-26-communique-sur-... [2]https://www.mathsoc.jp/publicity/news20261016.html [3]https://terrytao.wordpress.com/2026/10/19/a-sketch-of-the-pr...
7 replies →
> 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.
Now imagine that PhD “impersonator” has, in the past few months, made more demonstrable progress in mathematics than anyone in history.
I think that would change the conclusion of the argument a little.
22 replies →
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...
> You don't read AI written code, you ask an AI to explain it to you.
Rather: you reject AI-written code if it is not of really good quality.
1 reply →
> this does not feel like a healthy place to be
I believe you just captured the zeitgeist, friend.
Why not? If mathematicians in the field cannot understand the papers, but tools at our disposal can, why not use them? What is "unhealthy" about that? Just seems like it's the reality of the world now.
If you can't understand what the machine has done, math is not being done. Math is not pushing symbols around to find sequences that follow all the rules. Math is the process of understanding how those sequences of symbols map to meanings. If you can't follow the proof but have validated it's correct, all you know is that it's a proof of something. Is it a proof of what's claimed in the adjacent plaintext? Who knows!
Math is about clear communication between people first and foremost. That's why Shinichi Mochizuki's claimed proof of the ABC conjecture isn't accepted - he's unable to communicate it to enough mathematicians to get a consensus on its validity. LLMs generating Lean proofs are basically following that same schema. Sure, something has been proven. But what? Where's the clear communication explaining it to the satisfaction of other mathematicians?
30 replies →
Why does this not feel like a healthy place to be?
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.
8 replies →
Yup, and it always has been, we don’t even understand how our bodies or minds work, yet we use them everyday
The amount of unimaginable complexity contained in a seemingly very tiny amount of matter to us, is incredible, and it’s all around us in nature
We’ve never had the capacity to fully comprehend neither ourselves nor the environment we live in. But we do our best, and we do survive and sometimes even thrive
5 replies →
The mistakes that lurked in radium, in arsenic, in leaded gas, in fallout downwind of nuclear tests ... all had the best tools that the previous generation knew.
None of them were okay. Those were small small tools with few (sometimes only one) uses.
Generations earlier, famines, diseases and lead-leeching plumbing made rulers insane and entire cities of people die without any help from the "best tools".
Scifi is always written about the best tools. The issues arrive in the tools and in the hands that wield them both.
1 reply →
What a funny pov?? Mathematics and other pure sciences are about human understanding. You're saying if humans cannot understand the thing that was for human understanding, that's ok? That's like saying all the world's food is now inedible, but that's ok because a blender can consume it still.
4 replies →
The "top layer" of maths being this is one thing. Now imagine another layer of this. Then another. Then another. Then another.
At one point intuition helps to build out usage of the math itself. See stuff like "oh I can do rotations through matrix multiplication"-style ideas.
It is helpful for us to be able to reach for those tools quickly. The more tools that require advanced prep to use, the less we'll be able to use the results in easier contexts. Everything will be hard
Of course nothing really prevents people from looking for the simpler tools and proofs. Lots of math stuff starts off complicated and gets simpler.
Just important that this is still a goal in mind
There are a few increasingly powerful companies that own the frontier models that can produces these results. In the future, it may only be these models that understand the results. Should we be beholden to a few companies for basic understanding of foundational principals?
Because the tools don't understand the papers either. We know for a fact that:
1. These tools are wrong a significant % of the time
2. They have an upper complexity bound where they start to fall apart
Relying on AI to check AI papers is a terrible idea
10 replies →
Tools don't "understand" anything. They put together a probable string of tokens.
3 replies →
> Why not? If mathematicians in the field cannot understand the papers, but tools at our disposal can (...)
How can you tell?
1 reply →
I'm not a mathematician but from what I've heard from them that's generally not how mathematics works. You can "use" whatever you want, of course, but a mathematician's goal and main activity is finding and understanding proofs. The ones I knew also liked compiling error lists for math textbooks and sending them to the authors. (It opened my eyes because I admit to have been one of those ignorants who implicitly assumed "it's formal stuff in a book, sure it's going to be right".)
The tool may malfunction. Indeed there are theorems that say the tool must malfunction at least sometimes.
If you don't understand the subject and relies on the understanding of the tool, how will you have a frigging chance of catching an error?
Anyway this reminds me that scene in Matrix 2, where the mayor (of sorts, don't remember his exact title) of Zion tells Neo about the machines that keeps everyone alive, but that there is nobody left that understands how they work or could repair them if they broke.
1 reply →
Sounds like a disassembler.
because the tools can't? Lol. That's not how it works. Am I in the twilight zone?
All this anthropomorphism of literal statistical text generators.
Yes they exhibit generated sentences of text that describe coherent responses about a topic when there's an inordinate amount of research material in the training data from which they are distilling sentences of sound and rational thought. That's the ONLY way it can possibly work. There are so many scenarios where the training data isn't setup like that and low and behold the generated responses are just literal garbage.
4 replies →
Fable is the "gadget" of language ELI5.
Honestly it is not that much different from the divine inspiration if you have ever experienced it.
I do not know how you view the world or walk through it but language in general is simply subject to interpretation to me, the arrangement of words for the sentence is inspiration in and of itself - though the majority of time it amounts to minimum jumps.
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 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 a conundrum I hadn’t seen anyone predict. We will reach a time when machines push math and physics farther than a human mind ever could. But we won’t be able to know if it is correct for that same reason!
Math suddenly becomes biology
1 reply →
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 who ideate their afterlife as "pursuing hobbies".
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.
> The new result does not directly imply new complexity bounds for polynomial multiplication over a fixed finite field, say multiplication in F2[x]. The state of the art for this problem is an algorithm that multiplies polynomials of degree n in time O(n log n 4^log*(n)) [HvdH19].
@platypii and I obtained a Lean proof of the same improvement for DFT over prime-order finite fields (yielding polynomial multiplication via the convolution theorem): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...
> 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.
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.
Does the model get things wrong? Or does it just give up in trying to completely understand some very messy codebases?
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.
1 reply →
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?
if you understood only small part of the paper, how do you know that fable answers are correct and not just sound reasonable?
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.
He knows whether the explanations are coherent with eachother.
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”…
Note in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.
Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.
For those of us uninformed, what’s the difference between O and o?
Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329
5 replies →
To complement on other comments that have already provided definitions.
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.
2 replies →
f(n) = O(g(n)) means as n increases, f(n)/g(n) must not grow beyond a constant
f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink
5 replies →
If f is O(g) and o(h) then
And
4 replies →
Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound.
https://stackoverflow.com/questions/1364444/difference-betwe...
Big O basically drops constants
O(2n+1) = O(2n) = O(n)
o(2n+1) > o(2n) > o(n)
Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"
4 replies →
ty, fixed. (ahh, copy paste.)
Awesome write up and intro by a fellow Sydney-sider, kept me hooked! As someone who's not a maths wizard, the technical details flew by my head but the prose allowing me to empathise deeply with those in the field was very enlightening. I never realised how big of a deal the maths dump was and how much it has shaken up the field. I guess we are all just trying to figure out this whole "intelligence on tap" thing together.
You don’t need to be a math wizard. Just upload the paper to an AI and ask, “Explain this like I’m five.” Then, with each follow-up prompt, increase the age and level of expertise you want it to assume.
That algorithm won't converge anytime soon. A pre-conditioner (i.e. at least some apprentice wizardy) helps.
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 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...
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 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?
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 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.
Your feeling of inevitability is their private islands, mega-yachts, jets, mansions and immunity from prosecution.
No expense was spared.
Yeah it's crazy. I wonder if the lesser-educated, under-privileged, working class deplorables feel much schadenfreude about their enlightened betters who just got done with decades belittling and bullying them with "Dey terk er jerbs" and "Just learn to code" getting a bit of the treatment. Interesting times, maybe we should quit whining about AI derkin der jerbs and 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."
3 replies →
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.
I realize this is 100% not the point, but is this an immediately practical breakthrough that will change computing?
My extremely limited understanding is “no” as I sorta assume that would be the headline. The main point being that while a MASSIVE improvement over any previous progress it’s still “small” from a practical standpoint.
This is not to downplay the very well conveyed problem this might be, but I just want to make sure I even got that right.
I do wonder if this will be a major issue for future development or if the math experts in diapers right now will grow up in this world and have tools and understanding to assist and we’re just in a rough transition, but unfortunately that’s about as much as I can contribute.
This is very much a theoretical result. The author quotes a redditor or who jokes that the previous bound was nice and round and that was of practical importance:
>The result is of extreme practical importance. Not for actually multiplying integers (as usual with these algorithms it’s probably not faster than existing algorithms for integers that can be stored in the observable universe), but for writing papers. It has always been a hassle to write down the complexity of integer multiplication or algorithms based on integer multiplication by introducing soft-O notation, little-o exponents, epsilons greater than 0, or iterated logarithms. From now on I can just write O(n log n) in my papers and be done with it!
This new result means painful typesetting again.
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.
[flagged]
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.
Or, the AI convincingly responds that it "understands."
I really enjoy the writing style here.
edit: I mean this seriously. This kind of thing
> Some of my colleagues believe that this is a nefarious Company, whose only goal is profit, if necessary at our community’s expense. Perhaps there is some truth to this, but I think it is missing the larger point. The fact is that there now exists an automated system that can perform mathematical research — at least the part that involves “solving hard problems” — far better than any human. Now that such a system has been demonstrated, it is clear that results like these were bound to start appearing soon anyway. I do not blame the Company for getting there first. Who got there first is an irrelevant detail, a historical footnote.
is very pleasantly honest and well-thought-out.
> 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.
Almost as much as a paycheck from the Company.
what point are you trying to make?
2 replies →
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?
Agreed! I only wish I understood anything after page 3.
>A certain American technology company (henceforth “the Company”) recently dumped a large pile of manuscripts on GitHub.
Treating OAI's name like Voldemort reads as emotionally immature to me
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
New here but how does this help in general? Most of the time we use GEMM over Strassen even though time complexity is lower. Just ask idk anything :)
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.
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.
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.
You're dramatically underestimating. You need something like 2^2^2^5000 digits or something crazy like that.
1 reply →
>> I have not checked most of the details, but I think that the claimed o(n log n) bound is plausible.
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?
Come on. Prof David Harvey is the leading expert on this exact topic (integer multiplication algorithms), and here he has spent a lot of effort and time to digest the main new idea(s), and write 30+ pages explaining exactly what he's understood and why he believes the result is plausible. About the main “gadget”, he writes “I have worked through all the steps pretty carefully, and I think it checks out.” All this is useful information, and is the best we have so far from a reliable human source. I think it deserves more than a flippant response to the first line.
> Executive summary (longer version) > The bottom line is that I think the claimed result is plausible. I have not actually read the paper.
Based on skimming the paper (finally a proper explanation that gives some hint at intuition), the path to openai's formulation if you're familiar with undergrad CS is (apparently):
* Start with the usual FFT convolution for polynomials, viewing integers as a polynomial in a given base evaluated at a certain point
* In undergrad you (hopefully) saw polynomial multiplication can be done in nlogn via convolution using FFT, but that assumes complex integer addition/multiplication is O(1). Here we need O(log x) bits to simply represent a number x on a real machine.
* If you use naive (n^2) multiplication for those butterfies, then you end up with O(n[(log n)^2]).
* If you recursively use FFT for the digit multiplication at those butterflies, then you get something like O(n[(log n)^(log log n)]).
* Schonhage-Strassen realized that instead of doing FFT in C where the butterfly involves multiplying by \omega (\omega being roots of unity), you can work in a different ring where 2 is a root of unity and so it's a cheap bitshift, but were constrained in how finely they could break subproblems (could only break an n-bit integer into sqrt-n subpproblems each of sqrt-n bits), resulting in an overall O(nlogn * loglogn).
* The 2019 O(nlogn) version (supposedly, this is out of my depth) found a way to use some technique of "Gaussian Resampling" to do the matrix convolution via _multidimensional FFT_ in a ring where multiplying by root of unity became cheap _and_ subproblems could be finer. The bottleneck was thus only the addition/subtraction in the O(log n) butterfly layers, each of which does O(n) work for total of O(n logn)
* OpenAI's paper uses a fact that it's apparently easier to compute multiple butterfly layers "simultaneously" than doing them one at a time independently (page 10). There is some sort of implicit reuse because the later layers mix the outputs of earlier layers, and they take advantage of this to avoid having to write out layer 1 outputs separately from layer 2 outputs, and instead work in some coordinate system where they can intermingle them. This apparently amortizes to some tiny fractional epsilon shaved off of a layer, and since the whole FFT is recursive they can apparently save a factor of (1 - epislon)^(log log n) overall across "log log n" recursion depth, which is apparently where that ridiculously small overall exponent comes from.
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.
2 replies →
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.
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?
No. The realm mathematicians operate in here are integers so massively large it doesn't even make sense to consider computation.
> 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.
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.
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.
That made me chuckle...
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.
> I have not checked most of the details, but I think that the claimed o(n log n) bound is plausible.
Stopped reading right after that. Why is this so high up on HN? It's literally nothing.
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)
1 reply →
Because the author is one of the only humans who fully understands the O(n log n) algorithm that this o(n log n) result claims to improve on - he is a co-author of the 2019 O(n log n) breakthrough result.
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”).
> Stopped reading right after that. > Why is this so high up on HN?
Your question would have been answered if you'd just read a little more
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?
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.
Yeah I took a look later and am still mystified as to why specifically he would find a site like that to be addictive writing and helpful to him.
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...
this isn't the first time I see "I have not actually read the paper" take.
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
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'
Nice domain, UNSW!
web.maths.unsw.edu.au fills the whole address bar on mobile