On cap sets and the group-theoretic approach to matrix multiplication

Abstract

In 2003, Cohn and Umans described a framework for proving upper bounds on the exponent $\omega$ of matrix multiplication by reducing matrix multiplication to group algebra multiplication, and in 2005 Cohn, Kleinberg, Szegedy, and Umans proposed specific conjectures for how to obtain $\omega =2$. In this paper we rule out obtaining $\omega =2$ in this framework from abelian groups of bounded exponent. To do this we bound the size of tricolored sum-free sets in such groups, extending the breakthrough results of Croot, Lev, Pach, Ellenberg, and Gijswijt on cap sets. As a byproduct of our proof, we show that a variant of tensor rank due to Tao gives a quantitative understanding of the notion of unstable tensor from geometric invariant theory.

27 pages

References in corpus (7)

• Progression-free sets in Z_4^n are exponentially small
• The Growth Rate of Tri-Colored Sum-Free Sets
• A distribution on triples with maximum entropy marginal
• On large subsets of $F_q^n$ with no three-term arithmetic progression
• Geometric Complexity Theory and Tensor Rank
• Proof of a Conjecture of Kleinberg-Sawin-Speyer
• Asymptotic upper bounds on progression-free sets in ${\mathbb{Z}}_p^n$

Cited by in corpus (37)

• A Refined Laser Method and Faster Matrix Multiplication
• Upper bounds for sunflower-free sets
• The Partition Rank of a Tensor and $k$-Right Corners in ${\mathbb{F}}_q^n$
• The Growth Rate of Tri-Colored Sum-Free Sets
• A distribution on triples with maximum entropy marginal
• Fast Feasible and Unfeasible Matrix Multiplication
• Barriers for fast matrix multiplication from irreversibility
• Monochromatic Equilateral Triangles in the Unit Distance Graph
• A lower bound for the $k$-multicolored sum-free problem in ${\mathbb{Z}}_m^n$
• Towards a Geometric Approach to Strassen's Asymptotic Rank Conjecture
• Proof of a Conjecture of Kleinberg-Sawin-Speyer
• Fast Matrix Multiplication and Symbolic Computation
• Exponential Bounds for the Erdős-Ginzburg-Ziv Constant
• The G-stable rank for tensors
• Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
• Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
• A nearly tight upper bound on tri-colored sum-free sets in characteristic 2
• Universal points in the asymptotic spectrum of tensors
• Weighted slice rank and a minimax correspondence to Strassen's spectra
• On the strength of general polynomials
• Strength conditions, small subalgebras, and Stillman bounds in degree $\le 4$
• Limits on the Universal Method for Matrix Multiplication
• A connection between matchings and removal in abelian groups
• Bounds for Matchings in Nonabelian Groups
• Barriers for rectangular matrix multiplication
• Recent progress on scaling algorithms and applications
• The slice rank of a direct sum
• Exponentially Larger Affine and Projective Caps
• Maximum subsets of ${\mathbb{F}}_q^n$ containing no right angles
• On Matrix Multiplication and Polynomial Identity Testing
• Saturation of Rota's basis conjecture
• A generalization of Croot-Lev-Pach's Lemma and a new upper bound for the size of difference sets in polynomial rings
• A new upper bound for the size of a sunflower-free family
• Sets avoiding $p$-term arithmetic progressions in ${\mathbb{Z}}_q^n$ are exponentially small
• The stability of finite sets in dyadic groups
• Removal lemmas and approximate homomorphisms
• Larger Corner-Free Sets from Combinatorial Degenerations