Episode 81 · The Machine's Theorems
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.
Listen to the show on your preferred podcast platform.
Inside this episode
- Cold open: the pocket calculator and the barrier
- Schoolbook multiplication, counted
- Karatsuba's trick: three instead of four
- Splitting into more pieces: Toom-Cook
- The fast Fourier transform: n work per level, log n levels
- From Schönhage–Strassen to n log n
- Why n log n felt like a law of nature
- What family 109 claims
- Inside the multiplication manuscript: the cost of moving data
- Jeřábek: shocking, and unverified
- The DFT below n log n: family 130
- Did they change the model?
- Chow: the n log n intuition was already cracked
- Halfway: the speed limits so far
- Matrix multiplication and the exponent omega
- Tensors and the laser method, in words
- What family 107 claims: nine fourths
- Checking the Lean statement for omega
- Subset Sum: breaking the half
- How a referee would test Subset Sum
- Deterministic factoring over prime fields
- Why it matters to an engineer
- Closing: fifty-four zeros
Production credits & AI disclosure
Scripts generated with Claude Opus. Synthetic narration generated with Edge TTS. Reviewed, listened to, and approved by Sankalp Thakur.