Doug Colkitt: conditional improvement of OpenAI problem #109 (integer multiplication), κ from 2^-182 to 5.8×10^-33
Doug Colkitt @0xdougX
Why it matters
First announcement (02:24 UTC, ~105k views) of a conditional tightening of the exponent in OpenAI’s claimed sub-n log n integer multiplication algorithm.
Summary
First of three posts on 7 Oct. Conditional on OpenAI’s algorithmic interfaces, parameter and network refinements raise the exponent saving from κ = 2^-182 to κ = 5.8×10^-33 (between 2^-108 and 2^-107); he also states a ceiling κ < 5.838×10^-33 for that network family and cost inequalities. Quotes his own 00:35 UTC thread post calling integer multiplication “probably the most shocking result” of the OpenAI release (https://x.com/0xdoug/status/2107630826636648494).
Archived text
We’re publishing a result demonstrating a substantial tightening to the results from OpenAI Problem #109 (integer multiplication).
Conditional on OpenAI’s algorithmic interfaces, our parameter and network refinements improve the exponent saving in:
T(n)=O(n(\log n)^{1-\kappa})
from κ=2⁻¹⁸² to κ=5.8×10⁻³³ (between 2⁻¹⁰⁸ and 2⁻¹⁰⁷).
This represents a nearly 2⁷⁵ fold increase in the algorithm’s exponent saving parameter.
We also establish a ceiling of κ<5.838×10⁻³³ for the stated network-counting family and cost inequalities. Our result exceeds 99% of that ceiling. Surpassing this ceiling would require improving the network bounds or cost analysis from the original result.
Quoting @0xdoug: 3/ Integer multiplication is probably the most shocking result. Similar to matrix multiplication it’s a “asymptotic reduction”. Also like the matrix result, it’s not practical.