High-rank subtensors of high-rank tensors

EUROCOMB’23

Abstract
Let $d \ge 2$ be a positive integer. We show that for a class of notions $R$ of rank for order-$d$ tensors, which includes in particular the tensor rank, the slice rank and the partition rank, there exist functions $F_{d,R}$ and $G_{d,R}$ such that if an order-$d$ tensor has $R$-rank at least $G_{d,R}(l)$ then we can restrict its entries to a product of sets $X_1 \times \dots \times X_d$ such that the restriction has $R$-rank at least $l$ and the sets $X_1, \dots, X_d$ each have size at most $F_{d,R}(l)$. Furthermore, our proof methods allow us to show that under a very natural condition we can require the sets $X_1, \dots, X_d$ to be pairwise disjoint.

Pages:
647–652
References

E. Croot, V. Lev and P. Pach, Progression-free sets in Z_4^n are exponentially small, Ann of Math. 185 (2017), 331-337.
https://doi.org/10.4007/annals.2017.185.1.7

J. Ellenberg and D. Gijswijt, On large subsets of F_q^n with no three-term arithmetic progression, Ann of Math. 185 (2017), 339-343.
https://doi.org/10.4007/annals.2017.185.1.8

W. T. Gowers and T. Karam, Equidistribution of high rank polynomials with variables restricted to subsets of F_p, arXiv:2209.04932 (2022).

B. Green and T. Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math. 4 (2009), no. 2, 1-36.

T. Karam, High-rank subtensors of high-rank tensors, arXiv:2207.08030v2 (2022).
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-089

S. Lovett, The analytic rank of tensors and its applications, Discrete Anal. 7 (2019), 1-10.

E. Naslund, The Chromatic Number of R^n with Multiple Forbidden Distances, arxiv:2205.12312 (2022).

E. Naslund, The partition rank of a tensor and k-right corners in F_q^n, Jour. Combin. Th, A 174 (2020), 105190.
https://doi.org/10.1016/j.jcta.2019.105190

L. Sauermann, Finding solutions with distinct variables to systems of linear equations over F_p, Math. Ann (2022).
https://doi.org/10.1007/s00208-022-02391-y

W. Sawin and T. Tao, Notes on the "slice rank" of tensors, https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors.

T. Tao, A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound.

Metrics

0

Views

0

PDF views