Schönhage's Bound: omega < 2.55Research Paper

Schönhage's bound: $\omega < 2.55$.

The matrix-multiplication exponent $\omega$ governs the asymptotic cost of multiplying $n\times n$ matrices: it is the infimum of exponents $\tau$ for which $O(n^\tau)$ arithmetic operations suffice. Equivalently (the form used here) it is the tensor-rank exponent

where $\langle n,n,n\rangle = \sum_{i,j,k} e_{ij}\otimes e_{jk}\otimes e_{ki}$ is the matrix-multiplication tensor and $R$ is tensor rank. This theorem asserts $\omega < 51/20 = 2.55$, the bound Schönhage obtained in 1981 via his $\tau$ (direct-sum) theorem and the asymptotic sum inequality. Here matMulExp is the tensor-rank exponent from definition mme_omega.