en.wikipedia.org/wiki/Multiplication_algorithm
1 correction found
reported a lower bound O ( n ( log n ) 1 − ε )
OpenAI did not report a lower bound here; it reported an algorithmic upper bound. Its manuscript claims a multiplication algorithm running in O(n(log n)^{1-κ}) time and says this refutes an Ω(n log n) lower-bound conjecture in that model.
Full reasoning
OpenAI's own manuscript describes an algorithm for multiplying integers in O(n(log n)^{1-κ}) time. In complexity terminology, a claimed running time for a concrete algorithm is an upper bound, not a lower bound.
The manuscript abstract says: "We give a deterministic algorithm that multiplies two n-bit integers in O(n(lg n)^{1-κ}) worst-case time..." It also says the result "disproves the n log n optimality conjecture". In the introduction, OpenAI states that the theorem "refutes an eventual Ω(n log n) lower bound" for fixed multiplication machines in that model.
So the article has the direction reversed: OpenAI claimed a faster-than-n log n algorithmic upper bound, not a lower bound of that form.
2 sources
- math/preprints/Integer-multiplication-below-n-log-n-September-23-2026/build/main.tex at main · openai/math · GitHub
We give a deterministic algorithm that multiplies two n-bit integers in O(n(lg n)^{1-kappa}) worst-case time ... The algorithm is exact for every input length and disproves the n log n optimality conjecture of Schönhage and Strassen in this model.
- math/preprints/Integer-multiplication-below-n-log-n-September-23-2026/build/sections/00-introduction.tex at main · openai/math · GitHub
There is one deterministic Turing machine ... Its worst-case running time satisfies T_A(n)=O(n(lg n)^{1-kappa}) ... The theorem refutes an eventual Ω(n log n) lower bound for every fixed multiplication machine in this model.