Border subrank of higher order tensors and algebras
This work addresses fundamental problems in algebraic complexity theory, providing exact border subrank values that are incremental extensions of Strassen's asymptotic results.
The paper determines the border subrank of higher-order structure tensors for various algebra families, including tight bounds for matrix multiplication and results for truncated polynomial, null, apolar, and Lie algebras, while extending prior asymptotic results to exact values and higher orders.
We determine the border subrank of higher order structure tensors of several families of algebras, and in particular obtain the following results. (1) We determine tight bounds on the border subrank of $k$-fold matrix multiplication and $k$-fold upper triangular matrix multiplication for all $k$. (2) We determine the border subrank of the higher order structure tensors of truncated polynomial algebras, null algebras, and apolar algebras of a quadric. (3) We determine the border subrank of the higher order structure tensors of the Lie algebra $\mathfrak{sl}_2$ for all orders. (4) We prove that degeneration of structure tensors of algebras propagates from higher to lower order. Along the way, we investigate which upper bound methods (geometric rank, $G$-stable rank, socle degree) are effective in which settings, and how they relate. Our work extends the results of Strassen (J.~Reine Angew.~Math., 1987, 1991), who determined the asymptotic subrank of these algebras for tensors of order three, in two directions: we determine the border subrank itself rather than its asymptotic version, and we consider higher order structure tensors.