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

flebron

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.

jdb1729

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

ajkjk

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.

yaoke259

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.

Kapura

> 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

jdb1729

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

MiroslavPokorny

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

cachius

Nice domain, UNSW! web.maths.unsw.edu.au fills the whole address bar on mobile

WindyTree

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.

jonhohle

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