We are publishing an update to OpenAI Problem #109 (integer multiplication) with a substantial further tightening:
T(n) = O(n (log n)^(1 − κ)),
With κ = 2⁻⁷⁸ (tightened from κ = 2⁻¹⁸²)
Approximately 570 million fold improvement over our previous result and a 2¹⁰⁴ fold improvement over original OAI result.
Our earlier ceiling applied to a cubic bottleneck in the network. The new witness scales quadratically; we haven't established a new ceiling.
The key was using nonadjacent axis swaps to route around the cubic bottleneck. The original manuscript already supported nonadjacent axis swaps. Using them directly reduces layout routing from O(d²) to O(d) swaps.
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.