Source-linked AI summary
On cap sets and the group-theoretic approach to matrix multiplication
Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, Chris Umans
TL;DR
The paper asks whether the group-theoretic approach to matrix multiplication can reach ω = 2 through STPP constructions. It bounds tricolored sum-free sets in bounded-exponent abelian groups and uses that bound to rule out this route within that scope.
Problem
The group-theoretic approach proposes sufficiently large STPP constructions as a way to obtain ω = 2, so the size of such constructions is central to that route.
Source: §1 · p. 2Method
The paper bounds tricolored sum-free sets in bounded-exponent abelian groups and shows every STPP construction in an abelian group yields such a set.
Source: §1 · pp. 2–3Results
No STPP construction in an abelian group of exponent at most ℓ is large enough to yield ω ≤ 2 + ε_ℓ via inequality (1.1), for any ℓ ∈ N.
Source: §1 · p. 3Takeaways & Limitations
The result rules out obtaining ω = 2 through bounded-exponent abelian STPP constructions, but leaves other group-theoretic possibilities open.
Source: §1 · p. 3The results do not rule out ω = 2 via STPP constructions over abelian groups generally, particularly when groups have large cyclic factors.
Source: §1 · p. 3
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends cap-set bounds to tricolored sum-free sets in bounded-exponent abelian groups, then uses those bounds to rule out sufficiently strong STPP constructions as a route to ω = 2. It also relates slice rank to quantitative instability.
1 Introduction
- Every tricolored sum-free set in an abelian group generated by elements of order at most m has size at most 3·|H|^(1−ε), for an absolute ε > 0.This extends the cap-set framework to abelian groups of bounded exponent.Source: §1 · p. 2
- For H ≅ (Z/qZ)^n with prime-power q, every tricolored sum-free set has size at most 3·|H|^(1−δ/log q), where δ = 0.05663… .For prime exponent p, this agrees with the progression-free bound's form, with a slightly worse exponent when stated uniformly in p.Source: §1 · pp. 2–3
- The tricolored-set bounds extend Ellenberg–Gijswijt from progression-free sets to tricolored sum-free sets and from prime-exponent to bounded-exponent abelian groups [11].In particular, Theorem A disproves the strong USP conjecture via.Source: §1 · p. 2
- Low slice rank implies instability, while a quantitative bound on instability bounds the slice rank of tensor powers.The paper studies slice rank, a variant of tensor rank due to Tao, and relates it to quantitative instability from geometric invariant theory.Source: §1 · p. 3
- For every ℓ∈N, some εℓ>0 ensures that no STPP construction in any abelian group of exponent at most ℓ is large enough to yield, via inequality (1.1), a bound better than ω≤2+εℓ.Every STPP construction yields a large tricolored sum-free set.Source: §1 · p. 3
- The results do not rule out ω = 2 via STPP constructions over all abelian groups; large cyclic factors, non-abelian groups, and association schemes remain outside the obstruction.Groups with a large cyclic factor can contain a large sum-free subset.Source: §1 · p. 3
2 The simultaneous triple product property
The simultaneous triple product property (STPP) organizes collections of subset triples that realize matrix multiplications in group algebras. The framework’s inequality makes meeting the packing bound necessary for an STPP family to imply ω = 2.
2 The simultaneous triple product property
- The 2003 framework reduces matrix multiplication to group algebra multiplication using subset triples satisfying the triple product property.Such a triple realizes a matrix multiplication tensor in the group algebra, yielding an inequality that can bound ω when the group and subsets are chosen appropriately.Source: §2 · pp. 3–4
- The STPP captures multiple independent matrix multiplications through triples of subsets of H and constructions in the wreath product H ≀ S_m.The STPP requires the simultaneous triple product property across the indexed triples.Source: §2 · p. 4
- An STPP construction realizes its matrix multiplication tensor, and the resulting group-algebra inequality underlies the framework’s analysis of these constructions.For abelian H, the character-degree bound specializes to the introduction’s inequality (1.1).Source: §2 · p. 4
- Meeting the packing bound is necessary for a family of STPP constructions to imply ω = 2 through inequality (1.1).If any one of the three pairwise size sums is at most |H|^(1−3ε) for fixed ε > 0, the inequality yields an upper bound on ω strictly above 2.Source: §2 · p. 5
- The strong USP and two families conjectures would yield STPP constructions meeting the packing bound, but their group settings differ in scope.The strong USP constructions use groups F_3^n, while the two families conjecture does not require bounded exponent; Theorem B therefore addresses only special cases of the latter.Source: §2 · p. 5
3 STPP constructions and tricolored sum-free sets
This section connects STPP constructions in abelian groups to tricolored sum-free sets, using border versions as an intermediate step. It then uses uniform STPP constructions and Theorem A to show that bounded-exponent groups cannot yield ω = 2 through this route.
3.1 STPP constructions imply tricolored sum-free sets
- Every STPP construction in an abelian group yields a border tricolored sum-free set of size at least the sum of |Ai||Bi||Ci|/(|Ai|+|Bi|+|Ci|).The construction builds matchings from the difference sets and uses auxiliary functions to repair failures of the sum-free condition.Source: §3.1 · pp. 6–8
- Given a border tricolored sum-free set of cardinality |M| and range t in an abelian group H, for every natural N there is a tricolored sum-free set in H^N of cardinality at least |M|^N/(2Nt+1)^3; asymptotically, the cardinality is |M|^{(1−o(1))N}.Source: §3.1 · p. 8
- Any STPP family meeting the packing bound can be transformed into a uniform family in powers of its original abelian group that still meets the packing bound.The construction restricts product-set choices to fixed distributions; sufficiently large N preserves the packing bound up to a 1−o(1) factor.Source: §3.1 · pp. 8–10
3.2 Theorem A implies Theorem B
- Assuming bounded-exponent STPP constructions imply ω ≤ 2+δ for every δ > 0 would produce uniform families meeting the packing bound in groups of the same bounded exponent.Theorem 3.3 and the border-to-genuine conversion then contradict Theorem A’s bound, proving Theorem A implies Theorem B.Source: §3.2 · p. 10
4 Tricolored sum-free sets in abelian groups of bounded exponent via rank and instability of tensors
The section develops slice rank as a tool for bounding tricolored sum-free sets in abelian groups of bounded exponent, relating it to tensor instability and group-structure tensors. It then uses triangle-rank bounds to obtain exponential upper bounds for these groups.
4 Tricolored sum-free sets in abelian groups of bounded exponent via rank and instability of tensors
- For every bounded-exponent abelian group H, the argument bounds the size of any tricolored sum-free set by |H|^(1−α′) for some constant α′ > 0.It reduces to groups G = (Z/p^kZ)^n and uses a slice-rank bound for the tensor product of the G- and complementary-group multiplication tensors.Source: §4 · p. 11
4.1 Tensor rank and its variants
- Building on Tao, the paper develops slice rank and proves that slice-rank(F ⊗ G) is at most slice-rank(F) times either tensor-rank(G) or the largest side length of G.For the base case F_p^n, the proof uses polynomial degree to bound slice rank by the number of vectors in [p]^n whose coordinate sum is at most pn/3, yielding an exponential bound (p−ε_p)^n.Source: §4 · p. 11, §4.1 · p. 12
4.2 Unstable tensors and slice rank
- Low slice rank implies tensor instability, while quantitative instability bounds slice rank of tensor powers when the three side lengths are equal.Specifically, slice-rank(F) < min(|X|,|Y|,|Z|) implies F is unstable.Source: §4.2 · pp. 13, 15
- Every diagonal tensor with nonzero entries has slice rank equal to its side length.The section gives Tao’s proof and a second proof using the geometric invariant theory perspective.Source: §4.2 · pp. 15–16
- A tricolored sum-free set in H is bounded by the slice rank of its group-structure tensor, while matrix-multiplication tensors are nonunstable and have slice rank n² [3, Theorem 5.2].The set corresponds to a diagonal restriction of the tensor encoding multiplication in the group algebra.Source: §4.2 · p. 18
4.3 Upper bounds on slice rank
- The decomposition gives slice-rank(F^⊗n) ≤ (|X|^n + |Y|^n + |Z|^n)e^(−2nε²).This bound is nontrivial for sufficiently large n when |X| = |Y| = |Z|; for unequal sizes, instability must be sufficiently large.Source: §4.3 · pp. 18–19
- If |X| = |Y| = |Z| = k and triangle-rank(F) ≤ k, then instability(F) ≥ 1/6 and slice-rank(F^⊗n) ≤ 3(kJ(k))^n.The triangle-rank bound enables a sharper slice-rank estimate for tensor powers.Source: §4.3 · p. 20
4.4 Tricolored sum-free sets in abelian groups of bounded exponent
- Every tricolored sum-free set in H ≅ (Z/qZ)^n × G, for prime-power q, has size at most 3·|H|·J(q)^n.The proof uses triangle-rank(D_Z/qZ) ≤ q over F_p to bound the slice rank of tensor powers.Source: §4.4 · pp. 22–23
- For H ≅ (Z/qZ)^n, every tricolored sum-free set has size at most 3·|H|^(1−δ/log q).For groups of exponent at most m, the bound is 3·|H|^(1−ε/m).Source: §4.4 · p. 23