Integer Multiplication Breaks the n log n Barrier, with AI Leading the Way
Starting October 7, researchers on social media reported that integer multiplication has for the first time been pushed below the long-assumed O(n log n) lower bound—faster than Schönhage–Strassen–type algorithms—with AI credited as the main contributor. Together with recent results such as 3-sum at n^1.999, the news triggered widespread discussion and debate in the algorithms and complexity-theory community, flooding timelines to the point that some bloggers joked about buying a Texas Instruments calculator instead.
Confirmed
- New work indicates integer multiplication can beat n log n; the news, relayed by @QuintinPope5 from @mgostIH, was described as "cursed."
- @IgorCarron relayed commentary that AI (AlphaEvolve–style work) found a method faster than n log n while AES encryption remains unaffected—"just because it hasn't been announced?"—though this remains commentary and algorithm details are unpublished.
- Technical approach (per a tweet cited by @deanwball): recast multiplication as a convolution network, run FFT, and exploit butterfly-network symmetries; asymptotically faster, but Dean Ball noted the speedup only shows up around the 37th decimal place.
- The research process itself is being rewritten by AI: @arannayebi relayed Christian Szegedy's remark that such results once took years of scattered, peer-reviewed papers, but AI plus formal tools can compress the process to hours; Aurelien Prot built a live tracker streaming the community's AI-driven assault on the problem.
- The main contribution comes from AI—a dramatic contrast with LLMs failing at multiplication five years ago (discussion relayed by @CatAstroPiyush).
- @bzogrammer (relayed by @snikolov) offered a lay explanation: these are typical fractal-style complexity bounds, not bizarre results—naive O(n²) multiplication was long deemed optimal until Karatsuba's log2(3)≈1.58 algorithm; history is repeating.
- Related "shaving" results: 3-sum down to n^1.999 and multiplication to n(log n)^0.999.
- @chrisalbon noted timelines flooded with talk of "sub n log n" and "kappa constants."
Unconfirmed
- Most claims come via second-hand relays; the original paper has not been formally released, and the algorithm details and exact role of AI are not given in the posts.
Why it matters
- If the lower bound is truly broken, long-trusted complexity bounds may merely be "weak approximations" reflecting human cognitive limits.
- The research paradigm shift matters: per Szegedy, AI plus formal tools could compress multi-year peer-review cycles into hours, with a public live tracker enabling community collaboration—potentially reshaping mathematical research itself.
- Aesthetic debate: @thomasahle worried such results make deep mathematics "ugly" (square-packing-style bounds), yet sees beauty from another angle; @deanwball marveled that in 2026 we can still discover new things about "multiplication."
- Practicality debate: @srchvrs questioned whether shaving small constants off known exponents is a fundamental breakthrough or a hack—many asymptotic improvements historically carry "galactic" constants with no practical impact; responses exist in @thomasahle's discussion threads.
2026-10-07 ~ 2026-10-09 · 11 related posts
- Episode 1: Truly Subquadratic 3SUM and Subcubic APSP Break Decades-Old Barriers, Reportedly with Claude's Help(2026-10-06, 13 posts)
- Episode 2: Integer Multiplication Breaks the n log n Barrier, with AI Leading the Way(2026-10-07, 11 posts)
- Episode 3: OpenAI's 'Below n log n' Claim Called Out as Wordplay(2026-10-07, 2 posts)
- Episode 4: AI Agents Chase Integer Multiplication Complexity Records in Viral Livestream(2026-10-08, 4 posts)
Primary sources
- Integer multiplication faster than N log N? Algorithm fans call it "cursed" — QuintinPope5 ·
- In 2026 We're Still Discovering Faster Multiplication — 37 Decimal Places Faster — deanwball ·
- AI plus formal tools compress years of research into hours as community live-tracks integer multiplication breakthrough — aran_nayebi ·
- [source] Integer multiplication faster than N log N? Algorithm fans call it "cursed" — QuintinPope5 · 2026-10-07
- From flubbing 3-digit multiplication to beating n log n: AI cracks integer multiplication in 5 years — CatAstro_Piyush · 2026-10-07
- After 3-sum hits n^1.999, complexity theorists debate whether math is 'all square packing' — thomasahle · 2026-10-07
- Integer multiplication can beat n log n, shaking faith in 'lower bounds', researchers react — deanwball · 2026-10-07
- [source] In 2026 We're Still Discovering Faster Multiplication — 37 Decimal Places Faster — deanwball · 2026-10-07
- Is shaving small constants off exponents a breakthrough? Algorithm theorists debate n^1.999 results — srchvrs · 2026-10-07
- Researchers debate whether sub-n-log-n multiplication is breakthrough or hack — thomasahle · 2026-10-07
- Karatsuba explained: why integer multiplication's O(n^1.58) bound is just fractal complexity — snikolov · 2026-10-08
- Faster-than-n log n integer multiplication claim sparks skepticism online — IgorCarron · 2026-10-08
- Timeline flooded with integer multiplication talk? Just buy a TI calculator — chrisalbon · 2026-10-09
- [source] AI plus formal tools compress years of research into hours as community live-tracks integer multiplication breakthrough — aran_nayebi · 2026-10-09