Speed Limits I: Multiplying, Transforming, Factoring

Deep End Era. Engineering with Sankalp · Oct 12, 2026 · 52m

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…