The recently proposed o(n log n) integer multiplication algorithm [pdf]

Posted by craigcitro 8 hours ago

Counter217Comment148OpenOriginal

Comments

Comment by jdb1729 7 hours ago

> 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!

Comment by marwahaha 2 hours ago

I help run a website that crowdsources formalized mathematics. We have a version of this result in Lean: https://prove2.me/campaigns/integer-multiplication-kappa

Comment by mariofdistrust 7 minutes ago

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?

Comment by ironborn123 1 hour ago

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!!

Comment by sebzim4500 1 hour ago

You forgot to specify that f(n) approaches 1 so that is an easy challenge

Comment by ironborn123 57 minutes ago

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.

Comment by 6 hours ago

Comment by Kapura 7 hours ago

> 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

Comment by flockonus 5 hours ago

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.

Comment by bamb008 4 hours ago

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...

Comment by miksuko 4 hours ago

> Were they fake, mathematicians would not consider this release important enough to comment upon[1,2], as vixra always provided a steady supply of such writings.

Few articles on vixra are made by companies with ~$1T valuations.

Comment by 3 hours ago

Comment by p-e-w 5 hours ago

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.

Comment by soVeryTired 5 hours ago

Or maybe the PhD impersonator discovered a soundness bug in a component of Lean and was able to exploit it.

With no humans able to understand the proofs the impersonator has produced, there's no way of knowing.

Comment by mrob 2 hours ago

There are many independent implementations of Lean's proof checker:

https://arena.lean-lang.org/

It's highly implausible that the same bug is present in all of them.

Comment by pera 35 minutes ago

Is that true? I'm actually asking because all the ones that I have seen mentioned from the arena were generated with Claude and I just checked a few random ones and they all have commits by Claude.

I don't know how much was created by LLMs but can you still call these independent implementations?

Comment by stouset 4 hours ago

This is true of literally any proof of sufficient complexity, human-authored or otherwise.

It takes time to convey the core ideas. It takes time for other mathematicians to come up to speed on the new techniques and approaches or the novel combinations of existing ones.

The actual experts in this field have asked for the argument to be explained to them, and are now at the point where they believe this is plausible. Another person in this thread has produced a Lean proof and presumably is not trying to pull a fast one on us by exploiting a bug in the solver.

TL;DR chill bro.

Comment by OxO4 3 hours ago

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.

Comment by CrimsonRain 3 hours ago

that's a hard cope. You think humans don't make thousands of mistakes to come up with something good?

Comment by david-gpu 3 hours ago

Good luck writing a Lean proof of a nontrivial theorem by giving a keyboard to a thousand coke-fueled monkeys. If only it was that easy.

Comment by TheOtherHobbes 2 hours ago

Strange to be against this when it works so well in other industries.

Comment by FeepingCreature 19 minutes ago

1. Well, mathematics isn't other industries

2. It really doesn't work well in other industries either.

Comment by aljgz 4 hours ago

More realistically, that impersonator has created lots of output, and the correct ones are selectively publicized (and few particularly interesting bad answers).

Comment by varjag 4 hours ago

Do you really believe Open AI made more progress in math than any of the human predecessors? Come on.

Galois had built modern algebra before dying at 20. What agents did so far is flash in a pan.

Comment by ithkuil 2 hours ago

Wait and see when _they_ are 20 years old!

Comment by varjag 2 hours ago

[dead]

Comment by abricq 2 hours ago

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...

Comment by jrflo 7 hours ago

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.

Comment by chowells 5 hours ago

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?

Comment by badlibrarian 5 hours ago

> Math is about clear communication between people first and foremost.

I can't imagine I'm the first one to point out that this is perhaps the greatest unsolved problem in mathematics.

> Where's the clear communication explaining it to the satisfaction of other mathematicians?

Coming in about a year for $20/month, sure seems like.

Comment by calf 2 hours ago

I mean it's just patently absurd. It is trendy to use this hubristic, and frankly bureaucratic, definition or requirement on math.

People can do math alone. They don't have to share it with others. Mochizuki was doing math (with errors). The aliens from Arrival could do math and we wouldn't necessarily be entitled to that. It doesn't make these things not valid math.

The only benefit of defining math through this vulgar social reductivism is to benefit the status quo. So you see some experts and expert-adjacent commentators using these math slogans but never critically justifying those words. Case in point, the above commenter asserts "...math is foremost about communication.", but the very next sentence does not explain why it is foremost, it just uses the sentence as a premise for the following sentence. Guess what, that is exactly how ideologues argue, by question begging fallacy. Ironic that STEM people who ought know better fail to catch this simple rational mistake.

Comment by TheOtherHobbes 2 hours ago

Math that isn't communicated is valueless - by definition.

Applies to STEM generally, because the foundation of STEM is peer review and independent testing and confirmation.

Even if the practice never quite lives up to the theory (true) that's no excuse to hand-wave away the requirement as if it doesn't matter.

Proofs that can't be confirmed are valueless because no one learns anything from them. The value of a proof isn't just in proving something but in inventing new techniques and insights that can be reused for other applications.

Brute force searches are fundamentally less valuable, because the creative foundation of math is discovering leaps of logic that solve problems with insightful shortcuts that can be generalised and reused for other applications.

Comment by asaddhamani 5 hours ago

I mean, I could not understand 95% of all the math out there due to skill issue, and it’s still valid. If machines can understand the math and humans can’t, we can’t validate it, but that doesn’t make the math itself invalid.

Comment by darepublic 5 hours ago

It could be logically valid but irrelevant? Allowing for the atrophying of all our skills is dangerous? While simultaneously building ever more complicated edifices that control our lives? Not a doomer but you really just want to shrug and say it ain't no thing?

Comment by wvenable 5 hours ago

Perhaps humans have peaked due to the fundamental biological nature of our brains and AI will eventually surpass us in mathematical intelligence.

That has been the ultimate goal of creating AI -- not to simply match human intelligence but to surpass it. If it surpasses us, does that make it irrelevant? Everything around us is powered by mathematics, most of it I don't understand, and soon perhaps everything will be powered by mathematics that everybody doesn't understand.

Comment by bonitochips 3 hours ago

To what end?

“Hey guys, the human condition can be experienced by these machines more efficiently than we are able to! Now we can finally die off!”

Why are we enabling a world that outpaces us? Is this going to lead to anything other than displacement in the long term?

Do you ever stop and ask why we’re building the world we’re building?

To what end does a world we cannot comprehend or rebuild from first principles serve us?

Comment by wartywhoa23 3 hours ago

@bonitochips

They killed your comment, but you should know that you've posted it on the world's #1 AI propaganda site, where literally trillions of dollars are at stake and ROI depends on the correctness of the discourse running among the meat LLMs foraging or lurking here.

Comment by shaky-carrousel 2 hours ago

No one here likes to hear their AI girlfriend isn't real.

Comment by indigo945 2 hours ago

It's not that their argument is wrong or not worth discussing, it's that it is utterly irrelevant when the question at stake is whether the math is valid and useful or not. It's effectively whataboutism.

Comment by ImHereToVote 2 minutes ago

I think sometimes it's worth being concerned about something else. What about "this" is valid if the "this" is important to us.

Everything is potentially interconnected.

What separates things is course-graining, not ontological separation per se.

Comment by mlsu 5 hours ago

Does math already exist and is discovered? Or is it a thing invented by people?

Comment by marcianx 5 hours ago

The underlying tautologies always existed. Making them accessible to us as truth and usable for one or more functions is what's invented by people (and potentially by AI) via insightful proofs and narratives.

Comment by pavas 3 hours ago

I think the nuance they are pointing towards is that we cannot with any certainty say one way or another, as this is an unsolved problem in mathematics, and may possibly remain unsolved forever.

Your opinion is a possibility but it is not grounded by any proof, as such it is nothing more than an assumption. I think the more intellectually healthy approach is to list out the possibilities and figure out what they entail, rather than to throw all your eggs in one basket blindly, which amounts to a leap of faith or a retreat to commitment.

But that's just my two cents, take it or leave it.

Comment by don_esteban 3 hours ago

Can you be more explicit?

I absolutely do not understand what are you talking about.

The question whether the tautologies exists regardless of whether we know about them or not is absolutely not a problem that is studied by mathematics and can be proven by mathematics.

Comment by alhirzel 2 hours ago

Does math exist without humans?

Comment by fwlr 4 hours ago

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.

Comment by don_esteban 3 hours ago

Leaving aside the (much more important) issue of monopolizing intelligence, and assuming the claimed result is indeed correct, the question is whether a) the correctness proof is indeed too complex to be understood by humans, or b) the creator (the LLM) is not able to write it down in a form digestible by humans.

Observing the LLM output on problems that have clear solutions invented by humans, I tend to believe that too many people are jumping to conclusions too soon and interpreting b) as a).

If the LLMs are truly so great, we should see (in a short time, i.e. in order of months) a transformation of the math proofs generated by LLMs from the current state of indigestible mess to something that indeed looks like written by human for humans.

Only then would one be able to claim that we got into situation a).

Comment by fwlr 1 hour ago

Why should we expect this? Does it help the corporation’s bottom line? How much? Is that worth the R&D spend and compute budget it would need? What advantage do they stand to gain by demystifying their product, that they don’t already get from e.g. Lean verification? Do they gain more if the same research and compute spend on their inscrutable intelligence is directed into making it more intelligent, instead of less inscrutable?

Comment by RetroTechie 1 hour ago

A more practical approach:

If a paper/proof is impossible to understand by humans, it could be considered useless (irrelevant) for most intents & purposes.

Regardless how interesting or valid looking, might as well be gibberish pulled from /dev/random. Until:

a) Written down in a form that humans can understand. And/or

b) Turned into practical applications that are demonstrated to work.

In other words: safe to ignore, until a) and/or b) occurs.

Comment by jeezfrk 6 hours ago

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.

Comment by prodigycorp 5 hours ago

There's nothing that makes this paper the be and and end all opinion pieces of the paper. The community will review his review, and people who wish to understand more will read more and more of the paper. I see nothing wrong with this process of progressive understanding.

Comment by nico 6 hours ago

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

Comment by sysguest 6 hours ago

well math has always been about "understanding things" -- hence proofs and etc is the main tool in the field

(and why math differentiates between conjectures (maybe true) and theorems)

so that "oh some 3rd party person/machine understood it for me" can feel... a bit icky

Comment by metanonsense 5 hours ago

Even pre-AI, there have been proofs that took years to be verified, understood and some were disputed forever and still are (like the Mochizuki / IUT drama). So, even without AI, maths has reached a point of specialization, where only a few people in the world know the areas used in a proof well enough to check it. When „new math“ is invented for a proof, people may even be more disincentivied to put in the effort. So, I‘d argue, AI makes understanding new proofs easier, not more difficult.

Comment by rzz3 6 hours ago

And yet for someone like me who is not a math expert, it has (all) always felt unapproachably foreign.

Comment by ziiinq 4 hours ago

[dead]

Comment by Madmallard 6 hours ago

IDK why this is relevant to the topic at hand.

Everyone in advanced math research understands the topics they are reading about deeply.

This person is just literally being victimized by the AI incompetence apocalypse.

Information overload + trained laziness.

Comment by dimator 5 hours ago

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.

Comment by CrimsonRain 2 hours ago

One day AI might use all these complex math to build a ftl rocket and you will still be what's the point if we can't understand it?

Comment by rtpg 6 hours ago

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

Comment by jonhohle 5 hours ago

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?

Comment by locknitpicker 6 hours ago

> Why not? If mathematicians in the field cannot understand the papers, but tools at our disposal can (...)

How can you tell?

Comment by techpression 4 hours ago

Especially for tools built to tell us we’re right and happily pretend to solve problems they didn’t. I think the OpenAI “revert” of their math problems speaks volumes of how volatile this can be.

Comment by 20k 6 hours ago

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

Comment by aenis 5 hours ago

So, just like humans then?

But where they do differ is they do have an infinite stamina, and can work on problems in loops, self-correcting their own mistakes if a formal way of checking the correctness of the solution exists. Which does happen to be the case with math.

Comment by 20k 5 hours ago

Humans can be wrong, but luckily we have an entire process for dealing with this, which is broadly called this new fangled 'science' thing

Comment by aenis 2 hours ago

I dunno. There is a flavour of a physicist who is only ever dabbling in theory, and relies on others to experiment and verify their ideas. I don't see why that can't be usurped by LLMs. Its just match, data and Gedankenexperimente.

Comment by BetterThanSober 4 hours ago

> but luckily we have an entire process for dealing with this

and why does this "peer-review" new-age thing cannot be used to scrutinize AI-writted/AI-assisted papers?

Comment by don_esteban 3 hours ago

a) because the AI is not able to write papers in a manner digestible by humans? b) perhaps because AI generates papers whose complexity is beyond what a human brain can grasp?

Aaaa, you mean 'peer-review' by AI?

Then the answer is: What is the use of a paper no human understands? Then no human can see that the techniques from the paper can be used to build something useful for real human life.

OK, ok, AI can decide to use those techniques to do something in real life it considers useful.

Are you now getting scared? Why not?

Comment by orlp 3 hours ago

Math isn't a science. The scientific method is irrelevant for it.

Comment by root_axis 5 hours ago

The trope of superficially likening every aspect of LLMs to humans is specious and lazy.

Comment by 2 hours ago

Comment by Madmallard 6 hours ago

Yes you're replying to astroturfers or AI psychosis victims.

Comment by nextaccountic 5 hours ago

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.

Comment by jonathanstrange 2 hours ago

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".)

Comment by KingOfCoders 6 hours ago

Sounds like a disassembler.

Comment by Madmallard 6 hours ago

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.

Comment by Sharlin 5 hours ago

Honestly this is starting to feel like a "God in the gaps" argument.

Comment by Madmallard 5 hours ago

how so?

Comment by reichstein 3 hours ago

We can't explain how human thinking works, and how they produce their (verbal or written) output.

We can explain how LLMs generates this output.

Humans can't be that simple, there must be some ~~divine~~ unique human touch to what we do.

Every day LLMs, running in frameworks that add earlier "thoughts" to the context and iterate, reflecting on their own thought process, gets better and better at doing something even less distinguishable from human output.

The gap gets smaller. The "unique human touch" will always be in the gap.

Comment by Madmallard 2 hours ago

except LLM generated writing and art is basically instantaneously distinguishable because of the nature of how it works? even LLM code is as well?

You just fly in from astroturfer kookoo town or what?

Comment by krackers 7 hours ago

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.

Comment by estetlinus 5 hours ago

> this does not feel like a healthy place to be

I believe you just captured the zeitgeist, friend.

Comment by 6879346626 7 hours ago

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.

Comment by yodsanklai 1 hour ago

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...

Comment by khazhoux 5 hours ago

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!

Comment by wartywhoa23 2 hours ago

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".

Comment by ludvigk 5 hours ago

Math suddenly becomes biology

Comment by jdb1729 8 hours ago

> 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...

Comment by kenferry 3 hours ago

> 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.

Comment by bjornsing 39 minutes ago

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?

Comment by reasonableklout 2 hours ago

Does the model get things wrong? Or does it just give up in trying to completely understand some very messy codebases?

Comment by black_knight 1 hour ago

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.

Comment by throwaway63467 2 hours ago

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”…

Comment by flebron 8 hours ago

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.

Comment by ComplexSystems 8 hours ago

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.

Comment by onionisafruit 8 hours ago

For those of us uninformed, what’s the difference between O and o?

Comment by kuboble 1 hour ago

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.

Comment by m-chrzan 1 hour ago

Pedantic correction: big O is more like <=, little o like strict <. Big theta, Θ, is like =. There's also omegas, big and small, for >= and >.

Comment by bobmarleybiceps 7 hours ago

Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329

Comment by morsch 5 hours ago

That sounds like Knuth came up with them, but the notation is much older than 1976

Comment by weinzierl 3 hours ago

I learned them as Landau notation which would put its invention around the turn of the twentieth century.

Comment by bobmarleybiceps 4 hours ago

yeah you're right. I wrote that poorly and seems I can't edit it now.. In the link I shared, he does propose the similar theta and omega notations and provides the existing definition for big O.

Comment by globular-toast 4 hours ago

Best explanation of big-O I've read, in a single opening sentence, no less!

Comment by ruined 8 hours ago

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

Comment by jhanschoo 7 hours ago

Nitpick:

s/must shrink/must eventually shrink, after finitely many n/

Equivalently, must go to zero in the limit.

Comment by Davidzheng 7 hours ago

depends on what you think shrink means. If you mean decreasing, that's false even eventually.

Comment by mebrainmush 6 hours ago

[dead]

Comment by dandanua 2 hours ago

Those are complexity classes. It makes more sense to use '∈' instead of abused '='.

Comment by theokrueger 8 hours ago

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 _____"

Comment by contravariant 1 hour ago

> o(2n+1) > o(2n) > o(n)

I don't think any of those are right. The latter two are trivially equivalent, the former also is since it differs by a factor of at most 3 for all n >= 1.

I still think the simplest definition for o(f) is 'g in o(g) iff O(g) is a proper subset of O(f)'. Or you can just say g is dominated by f in the sense that lim sup g/f = 0.

I'm fairly sure those two are equivalent, but it's a good little exercise.

Comment by bobmarleybiceps 8 hours ago

that's not the convention I know... (from CLRS algorithms book).

Big O is sort of like <=. little o is sort of like <.

https://dl.acm.org/doi/10.1145/1008328.1008329

Comment by npinsker 7 hours ago

yes, GP is slightly off, but the idea of <= and < is accurate.

O(n) is: "there exists a K such that, for sufficiently large n, K*n is always larger".

o(n) is: "for every K, for sufficiently large n, K*n is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.)

Comment by contravariant 1 hour ago

> "there exists a K such that, for sufficiently large n, K*n is always larger".

For what it's worth you can leave out the 'sufficiently large n' part, assuming we're talking about positive integers (or continuous functions on the nonnegative reals). I like to leave it in though because it makes the jump to defining both o, O and Theta in terms of lim sup f/g a little easier.

Comment by boothby 8 hours ago

If f is O(g) and o(h) then

  Lim f/g -> C a constant
And

  Lim f/h -> 0

Comment by adgjlsfhk1 7 hours ago

> Lim f/g -> C a constant.

This isn't quite correct. O(g) doesn't require the limit to exist.

Comment by boothby 6 hours ago

Ah, true, I was being sloppy. Thanks

Comment by appplication 8 hours ago

Lmao! If someone is asking the difference between big and little o notation this is absolutely not the right way to clarify it.

If you were joking then maybe you got me

Comment by boothby 7 hours ago

I do hope you can find and reattach your ass; that does sound painful.

Comment by Ygg2 8 hours ago

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...

Comment by craigcitro 8 hours ago

ty, fixed. (ahh, copy paste.)

Comment by yaoke259 7 hours ago

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.

Comment by m00dy 7 hours ago

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.

Comment by trostaft 7 hours ago

That algorithm won't converge anytime soon. A pre-conditioner (i.e. at least some apprentice wizardy) helps.

Comment by jonhohle 5 hours ago

> 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.

Comment by wartywhoa23 2 hours ago

Your feeling of inevitability is their private islands, mega-yachts, jets, mansions and immunity from prosecution.

Comment by stinkbeetle 5 hours ago

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).

Comment by 10111001 3 hours ago

> 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."

Comment by stinkbeetle 2 hours ago

> 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.

Comment by bonitochips 2 hours ago

[dead]

Comment by Eji1700 5 hours ago

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.

Comment by atzeus 5 hours ago

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.

Comment by kleiba2 4 hours ago

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.

Comment by oersted 3 hours ago

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.

Comment by DannyBee 4 hours ago

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...

Comment by CH-Abhinav 3 hours ago

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 :)

Comment by ajkjk 7 hours ago

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.

Comment by wartywhoa23 2 hours ago

> 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.

Comment by GMoromisato 6 hours ago

Agreed! I only wish I understood anything after page 3.

Comment by WindyTree 6 hours ago

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.

Comment by MiroslavPokorny 7 hours ago

> Executive summary (longer version) > The bottom line is that I think the claimed result is plausible. I have not actually read the paper.

Comment by krackers 5 hours ago

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.

Comment by briansm 3 hours ago

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.

Comment by adrian_b 36 minutes ago

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.

Comment by Surac 4 hours ago

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?

Comment by hoten 4 hours ago

No. The realm mathematicians operate in here are integers so massively large it doesn't even make sense to consider computation.

Comment by autuni 3 hours ago

> 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.

Comment by reasonableklout 2 hours ago

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.

Comment by autuni 2 hours ago

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)

Comment by fwlr 19 minutes ago

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.

Comment by tiara_girl 2 hours ago

[dead]

Comment by kypro 45 minutes ago

> 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.

Comment by calf 3 hours ago

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?

Comment by reasonableklout 2 hours ago

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...

Comment by joe_the_user 4 hours ago

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...

Comment by cachius 6 hours ago

Nice domain, UNSW!

web.maths.unsw.edu.au fills the whole address bar on mobile