New lower bounds for matrix multiplication and $\operatorname {det}_3$

Austin Conner ; Alicia Harper ; J.M. Landsberg

Forum of Mathematics, Pi, Tome 11 (2023)

Résumé

Let $M_{\langle \mathbf {u},\mathbf {v},\mathbf {w}\rangle }\in \mathbb C^{\mathbf {u}\mathbf {v}}{\mathord { \otimes } } \mathbb C^{\mathbf {v}\mathbf {w}}{\mathord { \otimes } } \mathbb C^{\mathbf {w}\mathbf {u}}$ denote the matrix multiplication tensor (and write $M_{\langle \mathbf {n} \rangle }=M_{\langle \mathbf {n},\mathbf {n},\mathbf {n}\rangle }$), and let $\operatorname {det}_3\in (\mathbb C^9)^{{\mathord { \otimes } } 3}$ denote the determinant polynomial considered as a tensor. For a tensor T, let $\underline {\mathbf {R}}(T)$ denote its border rank. We (i) give the first hand-checkable algebraic proof that $\underline {\mathbf {R}}(M_{\langle 2\rangle })=7$, (ii) prove $\underline {\mathbf {R}}(M_{\langle 223\rangle })=10$ and $\underline {\mathbf {R}}(M_{\langle 233\rangle })=14$, where previously the only nontrivial matrix multiplication tensor whose border rank had been determined was $M_{\langle 2\rangle }$, (iii) prove $\underline {\mathbf {R}}( M_{\langle 3\rangle })\geq 17$, (iv) prove $\underline {\mathbf {R}}(\operatorname {det}_3)=17$, improving the previous lower bound of $12$, (v) prove $\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.32\mathbf {n}$ for all $\mathbf {n}\geq 25$, where previously only $\underline {\mathbf {R}}(M_{\langle 2\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1$ was known, as well as lower bounds for $4\leq \mathbf {n}\leq 25$, and (vi) prove $\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+1.6\mathbf {n}$ for all $\mathbf {n} \ge 18$, where previously only $\underline {\mathbf {R}}(M_{\langle 3\mathbf {n}\mathbf {n}\rangle })\geq \mathbf {n}^2+2$ 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.

Détail

DOI : 10.1017/fmp.2023.14

Bibliographie

[1] Alman, J., Limits on the Universal Method for Matrix Multiplication, 34th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 137 (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019), Art. No. 12, 24. MR 3984617Google Scholar

[2] Alman, J. and Vassilevska Williams, V., Further Limitations of the Known Approaches for Matrix Multiplication, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11–14, 2018 (Cambridge, MA, 2018), 25:1–25:15.Google Scholar

[3] Alman, J. and Vassilevska Williams, V., Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication, 59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018 (IEEE Computer Soc., Los Alamitos, CA, 2018), 580–591. MR 3899623Google Scholar | DOI

[4] Ambainis, A., Filmus, Y. and Le Gall, F., Fast Matrix Multiplication: Limitations of the Coppersmith–Winograd Method (Extended Abstract), STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing (ACM, New York, 2015), 585–593. MR 3388238Google Scholar | DOI

[5] Arora, S. and Barak, B., Computational Complexity. A Modern Approach. (Cambridge University Press, Cambridge, 2009). MR 2500087 (2010i,68001)Google Scholar | DOI

[6] Bini, D., ‘Relations between exact and approximate bilinear algorithms’, Applications , Calcolo 17(1) (1980), 87–97. MR 605920 (83f,68043b)Google Scholar | DOI

[7] Bini, D., Lotti, G. and Romani, F., ‘Approximate solutions for the bilinear form computational problem’, SIAM J. Comput. 9(4) (1980), 692–697. MR MR592760 (82a:68065)Google Scholar | DOI

[8] Bläser, M., Fast Matrix Multiplication, Graduate Surveys, no. 5, Theory of Computing Library, 2013.Google Scholar

[9] Boij, M. and Teitler, Z., ‘A bound for the Waring rank of the determinant via syzygies’, Linear Algebra and its Applications 587 (2020), 195 – 214.Google Scholar | DOI

[10] Bourbaki, N., Lie Groups and Lie Algebras, Chapters 4–6, Elements of Mathematics (Berlin) (Springer-Verlag, Berlin, 2002). Translated from the 1968 French original by Andrew Pressley. MR MR1890629 (2003a:17001)Google Scholar | DOI

[11] Buczyńska, W. and Buczyński, J., ‘Apolarity, border rank, and multigraded Hilbert scheme’, Duke Math. J. 170(16) (2021), 3659–3702. MR 4332674Google Scholar | DOI

[12] Bürgisser, P., Clausen, M. and Shokrollahi, M. A., Algebraic Complexity Theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315 (Springer-Verlag, Berlin, 1997). With the collaboration of Thomas Lickteig. MR 99c:68002Google Scholar | DOI

[13] Christandl, M., Vrana, P. and Zuiddam, J., Barriers for Fast Matrix Multiplication from Irreversibility, 34th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 137 (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019), Art. No. 26, 17. MR 3984631Google Scholar

[14] Conner, A., Gesmundo, F., Landsberg, J. M. and Ventura, E., ‘Tensors with maximal symmetries’, Preprint, 2019, .Google Scholar | arXiv

[15] Conner, A., Gesmundo, F., Landsberg, J. M. and Ventura, E., ‘Rank and border rank of Kronecker powers of tensors and Strassen’s laser method’, Comput. Complexity 31(1) (2022), Paper No. 1, 40. MR 4356227Google Scholar | DOI

[16] Conner, A., Huang, H. and Landsberg, J. M., ‘Bad and good news for Strassen’s laser method: Border rank of and strict submultiplicativity’, Foundations of Computational Mathematics (2022).Google Scholar | DOI

[17] Derksen, H., ‘On the nuclear norm and the singular value decomposition of tensors’, Found. Comput. Math. 16(3) (2016), 779–811. MR 3494510Google Scholar | DOI

[18] Efremenko, K., Garg, A., Oliveira, R. and Wigderson, A., Barriers for Rank Methods in Arithmetic Complexity, 9th Innovations in Theoretical Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 94 (Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018), Art. No. 1, 19. MR 3761737Google Scholar

[19] Farnsworth, C., ‘Koszul–Young flattenings and symmetric border rank of the determinant’, J. Algebra 447 (2016), 664–676. MR 3427655Google Scholar | DOI

[20] Fulton, W. and Harris, J., Representation Theory , Graduate Texts in Mathematics, vol. 129 (Springer-Verlag, New York, 1991), A first course, Readings in Mathematics. MR 1153249 (93a,20069)Google Scholar

[21] Gałązka, M., ‘Vector bundles give equations of cactus varieties’, Linear Algebra Appl. 521 (2017), 254–262. MR 3611482Google Scholar | DOI

[22] Gałązka, M., ‘Multigraded apolarity’, Math. Nachr. 296(1) (2023), 286–313. MR 4553599Google Scholar | DOI

[23] Gallet, M., Ranestad, K. and Villamizar, N., ‘Varieties of apolar subschemes of toric surfaces’, Ark. Mat. 56(1) (2018), 73–99. MR 3800460Google Scholar | DOI

[24] Haiman, M. and Sturmfels, B., ‘Multigraded Hilbert schemes’, J. Algebraic Geom. 13(4) (2004), 725–769. MR 2073194Google Scholar | DOI

[25] Hartshorne, R., Deformation Theory, Graduate Texts in Mathematics, vol. 257 (Springer, New York, 2010). MR 2583634Google Scholar | DOI

[26] Humphreys, J. E., Introduction to Lie Algebras and Representation Theory, Graduate Texts in Mathematics, vol. 9 (Springer-Verlag, New York, 1978), Second printing, revised. MR MR499562 (81b:17007)Google Scholar

[27] Iarrobino, A. and Kanev, V., Power Sums, Gorenstein Algebras, and Determinantal Loci, Lecture Notes in Mathematics, vol. 1721 (Springer-Verlag, Berlin, 1999), Appendix C by Iarrobino and S. L. Kleiman. MR MR1735271 (2001d:14056)Google Scholar | DOI

[28] Knapp, A. W., Lie Groups Beyond an Introduction, second edn., Progress in Mathematics, vol. 140 (Birkhäuser Boston, Inc., Boston, MA, 2002). MR MR1920389 (2003c:22001)Google Scholar

[29] Landsberg, J. M., ‘The border rank of the multiplication of matrices is seven’, J. Amer. Math. Soc. 19(2) (2006), 447–459. MR 2188132 (2006j:68034)Google Scholar | DOI

[30] Landsberg, J. M., Tensors: Geometry and Applications, Graduate Studies in Mathematics, vol. 128 (American Mathematical Society, Providence, RI, 2012). MR 2865915Google Scholar

[31] Landsberg, J. M., Geometry and complexity theory, Cambridge Studies in Advanced Mathematics, vol. 169 (Cambridge University Press, Cambridge, 2017). MR 3729273Google Scholar | DOI

[32] Landsberg, J. M., Tensors: Asymptotic Geometry and Developments 2016–2018, CBMS Regional Conference Series in Mathematics, vol. 132 (AMS, 2019).Google Scholar | DOI

[33] Landsberg, J. M. and Michałek, M., ‘Abelian tensors’, J. Math. Pures Appl. (9) 108(3) (2017), 333–371. MR 3682743Google Scholar | DOI

[34] Landsberg, J. M. and Michałek, M., ‘On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry’, SIAM J. Appl. Algebra Geom. 1(1) (2017), 2–19. MR 3633766Google Scholar | DOI

[35] Landsberg, J. M. and Ottaviani, G., ‘Equations for secant varieties of Veronese and other varieties’, Ann. Mat. Pura Appl. (4) 192(4) (2013), 569–606. MR 3081636Google Scholar | DOI

[36] Landsberg, J. M. and Ottaviani, G., ‘ New lower bounds for the border rank of matrix multiplication’, Theory Comput. 11 (2015), 285–298. MR 3376667Google Scholar | DOI

[37] Lickteig, T., ‘A note on border rank’, Inform. Process. Lett. 18(3) (1984), 173–178. MR 86c:68040Google Scholar | DOI

[38] Smirnov, A. V., ‘The bilinear complexity and practical algorithms for matrix multiplication’, Comput. Math. Math. Phys. 53(12) (2013), 1781–1795. MR 3146566Google Scholar | DOI

[39] Strassen, V., ‘Relative bilinear complexity and matrix multiplication’, J. Reine Angew. Math. 375 376 (1987), 406–443. MR MR882307 (88h:11026)Google Scholar

[40] Strassen, V., ‘Gaussian elimination is not optimal’, Numer. Math. 13 (1969), 354–356. MR 248973Google Scholar | DOI

[41] Strassen, V., ‘Rank and optimal computation of generic tensors’, Linear Algebra Appl. 52/53 (1983), 645–685. MR 85b:15039Google Scholar | DOI