The recently proposed o(n log n) integer multiplication algorithm [pdf]
A new AI-generated result claiming an integer multiplication algorithm that runs in strictly sub‑O(n log n) time is prompting both excitement and unease among mathematicians and technologists. Commenters unpack the technical nuance between big-O and little-o notation, note that the algorithm is likely only of theoretical interest for astronomically large integers, and debate whether such “galactic” improvements matter in practice. Much of the conversation centers on what it means for AI systems to produce complex proofs that even top human experts struggle to fully understand, raising questions about verification, dependence on corporate-controlled models, and the future of mathematical research as a human-centered activity.
Asymptotic notation and the meaning of o(n log n)
- Multiple comments clarify the difference between big-O and little-o.
- Big-O is described as “≤” (upper bound up to a constant), little-o as strict “<” (grows strictly slower than any constant multiple).
- Several posters correct imprecise explanations (e.g., mistaken chains like o(2n+1) > o(2n) > o(n)).
- There’s some discussion of limit-based definitions (f/g bounded vs f/g → 0) and of Θ, Ω, and their “inequality” analogies.
Nature and practicality of the new integer multiplication result
- The significance is that this is o(n log n), strictly faster asymptotically than the classical FFT-based O(n log n).
- Multiple commenters stress it is a “galactic algorithm”: asymptotic improvement that only matters for astronomically large integers, far beyond any practical use.
- Existing O(n log n) and related FFT-based methods already aren’t used for most real-world integer sizes.
- A Lean formalization of an o(n log n) bound (with a concrete exponent slightly below 1) is mentioned; contributions are invited.
AI-generated proofs and mathematical understanding
- A central theme is that the new result (from “the Company”) is hard even for top experts to read, who instead interrogate an LLM to understand the paper.
- Some see this as a natural and useful new workflow: if humans can’t parse an exposition but tools can, use the tools.
- Others call this “unhealthy,” arguing that math is fundamentally about human understanding and clear communication, not just correctness.
- There is skepticism about LLM “understanding,” citing hallucinations, lack of self-assessment, and the danger of using AI to check AI.
- Formal proof assistants (e.g., Lean) are viewed as more trustworthy, though still limited by potential implementation bugs.
Philosophical and societal concerns
- Debate over whether math must be human-comprehensible to be valuable; some say unintelligible proofs are effectively useless until simplified or applied.
- Worry that frontier-level “intelligence” is becoming the property of a few corporations, with scenarios where states or firms could gate key mathematical capabilities.
- Several comments frame this as a loss of human control and agency, likening powerful AIs to genies whose workings we can’t fully grasp.
Reactions to exposition and tone
- Many praise the writeup’s prose, candor, and ability to convey emotional impact on the math community.
- Others criticize the “I have not actually read the paper” stance, seeing it as problematic even when meant self-deprecatingly.