3j0hn's comments

Oh yeah, great point. Like plugging numbers into the master theorem, if 5x5 could be done in 25 multiplications, say, it would imply multiplication in O(n^2), and even 45 multiplications would give a new asymptotically fast multiplication. I would have to dig out a textbook to figure out what an Omega(n^2 log n) lowerbound would imply for n=5.

edit of course wikipedia links to a explicit lowerbound which is kind of useful for small cases. https://www.sciencedirect.com/science/article/pii/S0885064X0... has it as 2*n*m+2*n-m-2 which is 53 for m=n=5, which is not super tight, but tight enough to say that no 5x5 formula is ever going to lead to an asymptotically faster MM algorithm.

This is a little bit apples and oranges, however. An asymptotic bound on the complexity doesn't say a lot about the number of multiplications needed for a fixed value of n=5 say. A lot of those complexity proofs say "for large enough n".

I wouldn't exactly call it a teaser. The formulas they published stand on their own, and putting them out there in the wake of all the press of the AlphaTensor paper, is just a good idea.

Of course, these formulas are not super interesting on their own, and so the forthcoming paper on HOW they developed these formulas is in some sense the "real" paper.