When is it plausible that a result is optimal?

(Lance and Bill did a vidcast about the OpenAI Document Drop. See here. My spellcheck thinks that vidcast and OpenAI are not words.) 

 The Metric TSP problem is TSP where, for all vertices \(x,y,z\), 

                                    \(w(x,z) \le  w(x,y) + w(y,z) \).

In 1976 Christofides and Serdyukov (independently of each other) showed that there is a poly time algorithm for a 1.5-approx to Metric TSP.

Some people thought the 1.5 could be improved.

Some people thought that 1.5 is optimal. 

1.5 is a natural number. Hmm, that's not quite right. 1.5 is a  pretty number. It would not be a surprise if someone had proven 

                                   If there is a poly time (\(1.5-\epsilon\)) approx then P=NP.

Indeed, people tried to prove that. 

In 2020 Karlin, Klein, Gharan, and Oveis proved 

                                  there is a poly time (\(1.5-\frac{1}{10^{36}}\))  approximation algorithm. 

Darling thinks this result is hilarious. I tried to tell her that the result is important since 

a) We now know that 1.5 is NOT optimal.

b) One of the authors, Nathan Klein, had been in my REU program in 2015.

She was not impressed.

Nobody believes that \(1.5-\frac{1}{10^{36}}\) is optimal. 

Is there a current conjecture? Klein told me he thinks  4/3.  A pretty number. 

The recent results on Matrix Mult and  Int Mult give a contrast involving pretty runtime and ugly runtimes.

MATRIX MULT

Let \(\omega\) be the least \(a\) such that two \(n\times n\) matrices can be multiplied together with \(O(n^a)\) operations. This definition is not quite right for two reasons:

(i) It is possible (though I think unlikely) that there is no least \(a\), For example, if there is a sequence of algorithms with runtime \(O(n^{2.1})\), \(O(n^{2.01})\), \(O(n^{2.001})\), \(\ldots\), then there is no least \(a\),

(ii) It is possible (though I thought unlikely before Oct 6, 2026), that the runtime may be different over different fields. 

We keep the incorrect definition to prove that ChatGPT is not the boss of me.

Here are some known results. I may have missed some:

The traditional algorithm: \(\omega\le 3\).

Strassen's Algorithm (1969): \(\omega\le \log_2 7 = 2.807\ldots \).

Coppersmith-Winograd (1990): \(\omega \le 2.376\ldots \).

Stothers (2010): \(\omega \le 2.3736\ldots\).

V.V. Williams (2012): \(\omega \le 2.3728642\ldots \).  (Stothers and V.V. Williams were independent.)

Alman and V.V. Williams (2020): \(\omega < 2.3728596\).

Alman, Duan, V.V. Williams, Y. Xu, Z. Xu, and Zhou (2024):  \(\omega < 2.371339 \).  (The preprint was in 2024. The published paper was in 2025.)

Google DeepMind's AI-based optimizer (August 2026): \(\omega < 2.371177\).

The value 2.371177 was the best upper bound on \(\omega\) for about 2 months.

The Chrysler Building was the tallest building in the world for about 11 months: from May 27, 1930 until May 1, 1931. The Empire State Building was the new champion. After May 1, 1931, the Chrysler Building wasn't even the tallest building in Manhattan. Fame is fleeting in both mathematics and architecture.

Note:

a) I believe that all of the algorithms above work over any field.

Google AI agrees with that, but ChatGPT correctly reminded me that Google AI's opinion is not a proof and that I should seek a citation or a counterexample.  If you know of a citation to confirm the any-field statement, or a counterexample to the any-field statement, please leave a comment.

b) After 1990 the improvements are really small.

c) None of these bounds is a pretty candidate for the true exponent.

We need notation that makes the field explicit.

Let \(\mathbb{F}\) be a field.  Let \(\omega(\mathbb{F})\) be the least \(a\) such that two \(n\times n\) matrices over \(\mathbb{F}\) can be multiplied together with \(O(n^a)\) operations.  (ChatGPT is still not the boss of me.)

OpenAI showed the following:

a) \(\omega(\mathbb{C})\le 2.25\). 2.25 is a very pretty number. It makes my heart go pitter-patter.

b) For every field \(\mathbb{F}\) they have \(\omega(\mathbb{F}) < 2.371054886006746\).

Lean-formalized.

A separate GitHub project claims to extend the 2.25 bound to every field with a Lean-checked proof. I have not checked the extension (as opposed to all of the new results OpenAI has dropped, which I have checked line by line with a quill pen and inkwell by the light of an oil lamp). The project is here.

Back to the issue at hand.

The drop from \(\omega \le 2.37\) to \(2.25\) is a Bob Beamon moment. Recall that before the 1968 Summer Olympics in Mexico City, the world record for the long jump was 27 feet, 4.75 inches (8.35 meters). During those Olympics, Bob Beamon jumped 29 feet, 2.5 inches (8.9 meters). A massive improvement. His record stood until 1991, when Mike Powell jumped 29 feet, 4.5 inches (8.95 meters). Gee, only two inches more! Mike Powell's jump still holds the record. So Beamon had the record for 23 years, and Powell has the record for 35 years.  If matrix multiplication follows the same pattern, we may wait 23 years for the next improvement and 35 more years for the one after that. However, since we are dealing with silicon instead of carbon, it may be 23 days and 35 days.

I am happy that the new upper bound on \(\omega\) is a pretty number and hence a plausible candidate for optimal.  If no one improves the result within 23 days, I will think 2.25 is optimal.

INT MULT

 Improved Algorithms for Integer Multiplication of two \(n\)-bit numbers.

In 1971 Schonhage and Strassen conjectured that there is an algorithm for integer multiplication that takes \(O(n\log n)\) bit operations.  In 2019, Harvey and van der Hoeven proved this conjecture.  Is there an algorithm that takes less time? Or is \(O(n\log n)\) optimal?

OpenAI obtained an algorithm that takes \(O(n(\log n)^{1-\kappa})\) bit operations, where \(\kappa=2^{-82}\). Really? \(2^{-82}\)? I declined to tell Darling about this one.

Google tells me that OpenAI did not lean-verify this one but open-source contributors later completed an independent Lean verification of the algorithm and improved the bound. The link is here. The improvement first pushed the small term to \(2^{-34}\) and then to \(2^{-14.38}\). I won't tell Darling these results until its down to \(2^{-1}\). 

Note the contrast between matrix multiplication and integer multiplication.

Matrix multiplication went from a runtime too ugly to be optimal---(O(n^{2.371\ldots})\)---to one pretty enough to be optimal---\(O(n^{2.25})\).  

Integer multiplication went from a runtime pretty enough to be optimal---\(O(n\log n)\)---to one too ugly to be optimal---\(O(n(\log n)^{1-\kappa})\), where \(\kappa=2^{-14.38}\)