Speed Limits I: Multiplying, Transforming, Factoring

Part 13 of "The Machine's Theorems". Farah and Augustin walk from long multiplication through Karatsuba, Toom-Cook, Schönhage–Strassen, Fürer and Harvey–van der Hoeven's n log n, then the fast Fourier transform's "n work per level times log n levels", and the matrix multiplication exponent omega. We read OpenAI's manuscripts on integer multiplication below n log n (family 109, not Lean-listed), an explicit power saving for the exact DFT (130, Lean-listed), omega at most nine fourths (107, Lean-listed), Subset Sum in two to the 0.49 n (138) and deterministic polynomial factorization over prime fields (142). We weigh the computational-model concern raised on MathOverflow, Timothy Chow's Alman–Rao precedent, Emil Jeřábek's reaction, and Scott Aaronson's remark about all those nines. Chapters 00:00:00 Cold open: the pocket calculator and the barrier 00:02:07 Schoolbook multiplication, counted 00:03:33 Karatsuba's trick: three instead of four 00:05:35 Splitting into more pieces: Toom-Cook 00:06:56 The fast Fourier transform: n work per level, log n levels 00:09:21 From Schönhage–Strassen to n log n 00:11:21 Why n log n felt like a law of nature 00:13:18 What family 109 claims 00:15:56 Inside the multiplication manuscript: the cost of moving data 00:18:59 Jeřábek: shocking, and unverified 00:20:33 The DFT below n log n: family 130 00:22:29 Did they change the model? 00:25:51 Chow: the n log n intuition was already cracked 00:27:44 Halfway: the speed limits so far 00:29:06 Matrix multiplication and the exponent omega 00:31:48 Tensors and the laser method, in words 00:34:53 What family 107 claims: nine fourths 00:38:23 Checking the Lean statement for omega 00:40:22 Subset Sum: breaking the half 00:44:10 How a referee would test Subset Sum 00:45:54 Deterministic factoring over prime fields 00:48:30 Why it matters to an engineer 00:50:45 Closing: fifty-four zeros Created by Sankalp Thakur. A Transient Labs production. Website: https://transientlabs.ai GitHub: https://github.com/sankalpsthakur X / Twitter: https://x.com/sankalpsthakur LinkedIn:   / sankalpthakur   Hugging Face: https://huggingface.co/sankalpsthakur Scripts generated with Claude Opus. Synthetic narration generated with Edge TTS. Reviewed, listened to, and approved by Sankalp Thakur.