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 sets of trifferent sequences, which constitutes a long-standing open problem in information theory and in theoretical computer science.
A gap in the slice rank of k-tensors
Costa S.
;Dalai M.
2021-01-01
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 sets of trifferent sequences, which constitutes a long-standing open problem in information theory and in theoretical computer science.File | Dimensione | Formato | |
---|---|---|---|
CostaDalaiGapSliceRank.pdf
gestori archivio
Descrizione: Articolo principale
Tipologia:
Full Text
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
287.64 kB
Formato
Adobe PDF
|
287.64 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
GapSliceRank-accepted_preprint.pdf
accesso aperto
Descrizione: Author’s Accepted Manuscript
Tipologia:
Documento in Pre-print
Licenza:
Creative commons
Dimensione
336.64 kB
Formato
Adobe PDF
|
336.64 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.