LAUSR

We show that two important quantities from two disparate areas of complexity theory --- Strassen's exponent of matrix multiplication $\omega$ and Grothendieck's constant $K_G$ --- are intimately related. They are different measures of size for the same underlying object --- the matrix multiplication tensor, i.e., the $3$-tensor or bilinear operator $\mu_{l,m,n} : \mathbb{F}^{l \times m} \times \mathbb{F}^{m \times n} \to \mathbb{F}^{l \times n}$, $(A,B) \mapsto AB$ defined by matrix-matrix product over $\mathbb{F} = \mathbb{R}$ or $\mathbb{C}$. It is well-known that Strassen's exponent of matrix multiplication is the greatest lower bound on (the log of) a tensor rank of $\mu_{l,m,n}$. We will show that Grothendieck's constant is the least upper bound on a tensor norm of $\mu_{l,m,n}$, taken over all $l, m, n \in \mathbb{N}$. Aside from relating the two celebrated quantities, this insight allows us to rewrite Grothendieck's inequality as a norm inequality \[ \lVert\mu_{l,m,n}\rVert_{1,2,\infty} =\max_{X,Y,M\neq0}\frac{|\operatorname{tr}(XMY)|}{\lVert X\rVert_{1,2}\lVert Y\rVert_{2,\infty}\lVert M\rVert_{\infty,1}}\leq K_G, \] and thereby allows a natural generalization to arbitrary $p,q, r$, $1\le p,q,r\le \infty$. We show that the following generalization is locally sharp: \[ \lVert\mu_{l,m,n}\rVert_{p,q,r}=\max_{X,Y,M\neq0}\frac{|\operatorname{tr}(XMY)|}{\|X\|_{p,q}\|Y\|_{q,r}\|M\|_{r,p}}\leq K_G \cdot l^{|1/q-1/2|} \cdot m^{1-1/p} \cdot n^{1/r}, \] and conjecture that Grothendieck's inequality is unique: $(p,q,r )=(1,2,\infty)$ is the only choice for which $\lVert\mu_{l,m,n}\rVert_{p,q,r}$ is uniformly bounded by a constant. We establish two-thirds of this conjecture: uniform boundedness of $\lVert\mu_{l,m,n}\rVert_{p,q,r}$ over all $l,m,n$ necessarily implies that $\min \{p,q,r\}=1$ and $\max \{p,q,r\}=\infty$.