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

On the recently proposed o(n log n) integer multiplication algorithm David Harvey, UNSW Sydney 20th October 2026 Abstract I offer some thoughts about the recently proposed integer multiplication algorithm whose complexity is claimed to be o(n log n) bit operations. 1 Executive summary I have not checked most of the details, but I think that the claimed o(n log n) bound is plausible. 2 Declaration This note was written without AI assistance, except for (a) typesetting (i.e., TeX wizardry), (b) proofreading, and most importantly (c) extensive discussions to help me understand the new algo- rithms. The main system used throughout was Claude Fable 5.1. 3 Introduction and background A certain American technology company (henceforth “the Company”) recently dumped a large pile of manuscripts on GitHub. This “math(s) dump” contains many remarkable claims and results. I have struggled to find the words to convey the stupendousness of these discoveries to my non- mathematical associates. One paper in particular caught my attention [TC26a]. It proposes a new algorithm for multiplying n-bit integers, claiming that it runs in o(n log n) bit operations, in either the multitape Turing model or the Boolean circuit model. The small “o” is not a typo. More precisely, the paper claims a complexity bound of the form O(n(log n)1−ε) for some small positive constant ε. This bound is of course utterly ridiculous. Previously the best bound was O(n log n) (big “O”), and this was widely believed to be optimal. The dump contains many other ludicrous results, but most of them were at least supposed to be true. This one was not. Nevertheless, this is a serious Company with a track record of doing serious things, so we should make an effort to take the claim seriously. 1 I would like to congratulate the Company, or more precisely its employees, for creating a Model with these astonishing capabilities. My understanding is that none of these people actually know how the Model works. Nor do they, for the most part, understand the content of the papers that they just publicly released. I would also like to congratulate the unnamed Model itself. Both for its brilliant ideas, and also for its perseverance against unfathomable odds. 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 believe that they are decent and hard- working people, whose efforts are sincerely aimed at making the world a better place. I hope and pray that they succeed. Some of my colleagues believe that this is a nefarious Company, whose only goal is profit, if necessary at our community’s expense. Perhaps there is some truth to this, but I think it is missing the larger point. The fact is that there now exists an automated system that can perform mathematical research — at least the part that involves “solving hard problems” — far better than any human. Now that such a system has been demonstrated, it is clear that results like these were bound to start appearing soon anyway. I do not blame the Company for getting there first. Who got there first is an irrelevant detail, a historical footnote. I am confident that this is not a one-off. At some point soon, the Model, or one of equivalent capability, possibly developed by a different Company, will be released publicly. At first it will be expensive, but then it will become cheap, and perhaps even free. Its capabilities will continue to improve. More mathematical results will appear, with increasing frequency, produced not only by the Company and its peers, but by ordinary people with access to these Models. Everyone in my community must grapple with the consequences. For instance, I doubt that it is possible for humans to be taken seriously as authors of mathematics research papers for much longer, for the same reason that we no longer accept written assignments from our undergraduates. It is possible that we have already reached this point; we will soon find out. This is not the place to dig into my views on the wider impacts of AI, but I can recommend the excellent blog by Zvi Mowshowitz (https://thezvi.substack.com/), whose perspective on AI is broadly similar to my own. I learn a huge amount from his voluminous and highly addictive writing. Zvi, if you are reading this, many thanks for your efforts, they are greatly appreciated. Returning now to the o(n log n) integer multiplication result. The new work builds directly on top of the O(n log n) algorithm described by myself and Joris van der Hoeven [HvdH21] (henceforth “the 2021 algorithm”). Much commentary on the interweb has focused on how insanely small the (log n)ε improvement is over the previous O(n log n) record, harping especially on the tiny numerical value of ε. In the initial writeup ε is 2−182, meaning that the exponent of log n is roughly 0.99999999999999999999999999999999999999999999999999999984. But from where I stand, this is actually a gobsmackingly enormous improvement. To put the gap in perspective, recall that when F¨urer established his O(n log n · Klog∗ n) bound in 2007, the improvement that he had achieved over the previous state of the art, namely the epochal Sch¨onhage– Strassen O(n log n log log n) bound from 1971, was smaller than log log n. And the subsequent 2 improvement made by my work with van der Hoeven (and several other papers along the way) was much, much, much smaller than this. The claimed (log n)ε improvement in the new work is exponentially larger than any of these. The actual value of ε is irrelevant. This is a huge gap. English has many synonyms for “big” but not enough for what I am trying to say. I suspect that very few people (i.e., humans) worldwide understand all the details of the 2021 algorithm, but I happen to be one of them. This puts me in the rare position of having the background to be able to comment immediately on the new work. 4 Executive summary (longer version) The bottom line is that I think the claimed result is plausible. 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. 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. 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 (notice that I choose my words very carefully), and that the bound O(n(log n)α) has the right shape. I stress that I have not checked the proof in any serious level of detail, and there are many parts that I do not yet understand properly. 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. Incidentally, when I say that the math(s) dump “does not appear to be strong on exposition”, all I mean is that I, as an human expert in this field, have difficulty understanding it (specifically [TC26a]). I have heard similar comments from other human experts regarding other papers in the dump. But as far as Fable seems to be concerned, the exposition in [TC26a] is perfectly clear. So perhaps the problem is not with the exposition, but with us humans. Before the advent of AI, it was already the case that different styles or levels of exposition were appropriate for different audiences. Perhaps we need to ask the LLMs to “explain it to me like I’m human” (ELIH). 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. 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. Such a formalisation seems to be achievable by current technology, but it is still not easy. If the result is correct, I expect a formalisation to be available fairly soon. My confidence in the result would be increased greatly if such a formalisation existed, assuming 3 that the initial definitions and statement of the main theorem had been checked by a (human?) Lean expert. I apologise that in this note I have not maintained my usual level of care and scholarship. Everything is happening so fast. In particular I apologise to those people whose work is used in this note without adequate attribution, due to my ignorance and/or negligence. Maybe one day I will make a more careful attempt, though I suspect that an LLM will beat me to it. Before getting to the explanations, I want to mention some consequences of the main result, as- suming that it is correct: There is a now a quantity that I would suggest calling the “exponent of integer multiplication”. It is the infimum of real numbers α ⩾ 0 such that there exists an integer multiplication running in time O(n(log n)α). We previously believed that α = 1, but the Model’s claim is that α < 1. Already some people have