A Universal Sequence of Tensors for the Asymptotic Rank Conjecture
No Thumbnail Available
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2025-02-11
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
24
Series
16th Innovations in Theoretical Computer Science Conference, ITCS 2025, pp. 1-24, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 325
Abstract
The exponent σ(T) of a tensor T ∈ Fd ⊗ Fd ⊗ Fd over a field F captures the base of the exponential growth rate of the tensor rank of T under Kronecker powers. Tensor exponents are fundamental from the standpoint of algorithms and computational complexity theory; for example, the exponent ω of square matrix multiplication can be characterized as ω = 2σ(MM2), where MM2 ∈ F4 ⊗ F4 ⊗ F4 is the tensor that represents 2 × 2 matrix multiplication. Strassen [FOCS 1986] initiated a duality theory for spaces of tensors that enables one to characterize the exponent of a tensor via objects in a dual space, called the asymptotic spectrum of the primal (tensor) space. While Strassen’s theory has considerable generality beyond the setting of tensors – Wigderson and Zuiddam [Asymptotic Spectra: Theory, Applications, and Extensions, preprint, 2023] give a recent exposition – progress in characterizing the dual space in the tensor setting has been slow, with the first universal points in the dual identified by Christandl, Vrana, and Zuiddam [J. Amer. Math. Soc. 36 (2023)]. In parallel to Strassen’s theory, the algebraic geometry community has developed a geometric theory of tensors aimed at characterizing the structure of the primal space and tensor exponents therein; the latter study was motivated in particular by an observation of Strassen (implicit in [J. Reine Angew. Math. 384 (1988)]) that matrix-multiplication tensors have limited universality in the sense that σ(Fd ⊗ Fd ⊗ Fd) ≤23ω =43 σ(MM2) holds for all d ≥ 1. In particular, this limited universality of the tensor MM2 puts forth the question whether one could construct explicit universal tensors that exactly characterize the worst-case tensor exponent in the primal space. Such explicit universal objects would, among others, give means towards a proof or a disproof of Strassen’s asymptotic rank conjecture [Progr. Math. 120 (1994)]; the former would immediately imply ω = 2 and, among others, refute the Set Cover Conjecture (cf. Björklund and Kaski [STOC 2024] and Pratt [STOC 2024]). Our main result is an explicit construction of a sequence Ud of zero-one-valued tensors that is universal for the worst-case tensor exponent; more precisely, we show that σ(Ud) = σ(d) where σ(d) = supT∈Fd ⊗ Fd ⊗ Fd σ(T). We also supply an explicit universal sequence U∆ localised to capture the worst-case exponent σ(∆) of tensors with support contained in ∆ ⊆ [d] × [d] × [d]; by combining such sequences, we obtain a universal sequence Td such that σ(Td) = 1 holds if and only if Strassen’s asymptotic rank conjecture holds for d. Finally, we show that the limit limd→∞ σ(d) exists and can be captured as limd→∞ σ(Dd) for an explicit sequence (Dd)∞d=1 of tensors obtained by diagonalisation of the sequences Ud. As our second result we relate the absence of polynomials of fixed degree vanishing on tensors of low rank, or more generally asymptotic rank, with upper bounds on the exponent σ(d). Using this technique, one may bound asymptotic rank for all tensors of a given format, knowing enough specific tensors of low asymptotic rank.Description
Publisher Copyright: © Petteri Kaski and Mateusz Michałek.
Keywords
asymptotic rank conjecture, secant variety, Specht module, tensor exponent, tensor rank
Other note
Citation
Kaski, P & Michałek, M 2025, A Universal Sequence of Tensors for the Asymptotic Rank Conjecture . in R Meka (ed.), 16th Innovations in Theoretical Computer Science Conference, ITCS 2025 ., 64, Leibniz International Proceedings in Informatics, LIPIcs, vol. 325, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-24, Innovations in Theoretical Computer Science Conference, New York, New York, United States, 07/01/2025 . https://doi.org/10.4230/LIPIcs.ITCS.2025.64