A gap in the slice rank of k-tensors

DOI10.1016/J.JCTA.2020.105335MaRDI QIDQ2005208zbMATH OpenOpenAlexWikidataFDO

Authors Simone Costa, Marco Dalai

Publication date 7 October 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.07355

zbMATH Keywords

polynomial methodslice ranktrifference

Mathematics Subject Classification ID

Extremal set theory (05D05) Other combinatorial number theory (11B75) Multilinear algebra, tensor calculus (15A69)

Abstract: The slice-rank method, introduced by Tao as a symmetrized version of the polynomial method of Croot, Lev and Pach and Ellenberg and Gijswijt, has proved to be a useful tool in a variety of combinatorial problems. Explicit tensors have been introduced in different contexts but little is known about the limitations of the method. In this paper, building upon a method presented by Tao and Sawin, it is proved that the asymptotic slice rank of any $k$-tensor in any field is either $1$ or at least $k/(k-1{)}^{(k-1)/k}$. This provides evidence that straight-forward application of the method cannot give useful results in certain problems for which non-trivial exponential bounds are already known. An example, actually a motivation for starting this work, is the problem of bounding the size of trifferent sets of sequences, which constitutes a long-standing open problem in information theory and in theoretical computer science.

Recommendations

• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
• The analytic rank of tensors and its applications
• Tensor slice rank and Cayley's first hyperdeterminant
• Weighted slice rank and a minimax correspondence to Strassen's spectra
• The G-stable rank for tensors and the cap set problem

Cites work

• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 881164 (Why is no real title available?)
• Information theory. Coding theorems for discrete memoryless systems
• On cap sets and the group-theoretic approach to matrix multiplication
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
• Universal points in the asymptotic spectrum of tensors
• UPPER BOUNDS FOR SUNFLOWER-FREE SETS

Cited in

(12)

• Tensor slice rank and Cayley's first hyperdeterminant
• The G-stable rank for tensors and the cap set problem
• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
• New bounds for perfect \(k\)-hashing
• The analytic rank of tensors and its applications
• A Gap in the Subrank of Tensors
• Bounds on the higher degree Erdős-Ginzburg-Ziv constants over \({\mathbb{F}}_q^n\)
• Small sunflowers and the structure of slice rank decompositions
• Discreteness of asymptotic tensor ranks (extended abstract)
• The maximum cardinality of trifferent codes with lengths 5 and 6
• The next gap in the subrank of 3-tensors
• Improved upper bound for the size of a trifferent code

This page was built for publication: A gap in the slice rank of \(k\)-tensors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2005208)