New lower bounds for matrix multiplication and
New lower bounds for matrix multiplication and
复制标题
矩阵乘法的新下界和
DOI：
10.1017/fmp.2023.14
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Landsberg, J.M.
中科院分区：
文献类型：
--
作者：
Conner, Austin;Harper, Alicia;Landsberg, J.M.
设表示矩阵乘法张量(和写)，设表示被视为张量的行列式多项式。对于张量T，让我们表示它的边界秩.我们(I)给出了第一个可手工检查的代数证明，(Ii)证明，(Iii)证明，(Iv)证明，改进了以前的下界，(V)证明(V)证明给所有人，以及(Vi)证明，以前只知道的所有人的证明，和(Vi)证明，其中以前只知道的非平凡矩阵乘法张量是，(Iii)证明，(Iv)证明，改进了以前只知道的所有证明的下界，以及(Vi)证明所有以前只知道的证明。后两个结果之所以重要，有两个原因：(I)它们本质上是张量在“不平衡”环境空间中的第一个非平凡下界；(Ii)它们证明了我们所使用的方法(边界去极化)可以应用于张量序列。用来获得结果的方法是Razborov和Rudich意义上的新的和非自然的，因为结果是通过一种不能有效地应用于一般张量的算法获得的。我们利用了Buczyńska和Buczyński在环簇的一般上下文中发展的一种新的技术，称为边界非极化。我们应用这一技术来开发一种算法，在给定张量T和整数r的情况下，在有限个步骤中，要么输出T不存在边界秩r分解，要么产生可能由边界秩分解得到的所有归一化理想的列表。当T具有较大的对称群时，该算法是有效实现的，在这种情况下，它以自然范式输出潜在的分解。该算法以代数几何和表示论为基础。
Let denote the matrix multiplication tensor (and write ), and let denote the determinant polynomial considered as a tensor. For a tensor T, let denote its border rank. We (i) give the first hand-checkable algebraic proof that , (ii) prove and , where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was , (iii) prove , (iv) prove , improving the previous lower bound of , (v) prove for all , where previously only was known, as well as lower bounds for , and (vi) prove for all , where previously only was known. The last two results are significant for two reasons: (i) they are essentially the first nontrivial lower bounds for tensors in an “unbalanced” ambient space and (ii) they demonstrate that the methods we use (border apolarity) may be applied to sequences of tensors. The methods used to obtain the results are new and “nonnatural” in the sense of Razborov and Rudich, in that the results are obtained via an algorithm that cannot be effectively applied to generic tensors. We utilize a new technique, called border apolarity developed by Buczyńska and Buczyński in the general context of toric varieties. We apply this technique to develop an algorithm that, given a tensor T and an integer r, in a finite number of steps, either outputs that there is no border rank r decomposition for T or produces a list of all normalized ideals which could potentially result from a border rank decomposition. The algorithm is effectively implementable when T has a large symmetry group, in which case it outputs potential decompositions in a natural normal form. The algorithm is based on algebraic geometry and representation theory.