###### 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.

title = On Cap Sets and the Group-theoretic Approach to Matrix Multiplication,
author = Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric
Naslund, William F. Sawin, and Chris Umans, plaintextauthor = Jonah Blasiak,
Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin,
Chris Umans, runningauthor = J. Blasiak, T. Church, H. Cohn, J. A. Grochow, E.
Naslund, W. F. Sawin, and C. Umans, year=2017, number=3, received=17 August
2016, revised=5 January 2017, published=16 January 2017, doi=10.19086/da.1245,

[classification=text]

##  1 Introduction

A _cap set_ is a subset of ${\mathbb{F}}_{3}^{n}$ containing no lines;
equivalently, if $u$, $v$, and $w$ belong to the set, then $u+v+w=0$ if and
only if $u=v=w$. In a remarkable pair of recent papers [9, 11], Croot, Lev,
and Pach [9] introduced a powerful new technique, which Ellenberg and Gijswijt
[11] used to prove that cap sets in ${\mathbb{F}}_{3}^{n}$ are bounded in size
by $O(c^{n})$ with $c<3$, thus settling a long-standing open question. The
results of Ellenberg and Gijswijt similarly bound the size of subsets of
${\mathbb{F}}_{p}^{n}$ that contain no three-term arithmetic progressions, as
well as certain more general sum-free sets.

Via the connections established earlier by Alon, Shpilka, and Umans [1], the
cap set bounds prove the Erdős–Szemerédi sunflower conjecture [12] and
disprove the Coppersmith–Winograd “no three disjoint equivoluminous subsets”
conjecture [7], which was proposed as a means to show that the exponent
$\omega$ of matrix multiplication is $2$. Alon _et al_. also showed that a
_tricolored_ version of the cap set bounds would disprove the “strong Uniquely
Solvable Puzzle (USP)” conjecture of Cohn, Kleinberg, Szegedy, and Umans [4],
which was another proposed approach to prove $\omega=2$ in the group-theoretic
framework of Cohn and Umans [5]. The strong USP conjecture is situated in the
context of a broader family of conjectures from [4], which are all potential
means to prove $\omega=2$. These conjectures all assert the existence of
certain large “simultaneous triple product property” (STPP) constructions. An
STPP construction is a collection of triples of subsets
$A_{i},B_{i},C_{i}\subseteq H$ inside a group $H$, satisfying certain
conditions (see Definition 2.2). The approach of [4] shows that when $H$ is
abelian, any STPP construction implies the inequality

$\sum_{i}(\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\left\lvert C_{i}\right\rvert)^{\omega/3}\leq\left\lvert
H\right\rvert.$ (1.1)

If the sets involved are large enough, this yields a nontrivial bound on
$\omega$, and [4] showed how a family of sufficiently large STPP constructions
would imply $\omega=2$.

This paper contains two main results. The first is a bound on the size of
tricolored sum-free sets in abelian groups of bounded exponent. A tricolored
sum-free set is a generalization of a three-term progression-free set (a set
whose elements satisfy $u+v=2w\iff u=v=w$) in which the elements $u$, $v$, and
$w$ range over three _different_ subsets (see Definition 3.1). The _exponent_
of a finite group is the least common multiple of the orders of all its
elements; if a finite abelian group is generated by elements of order at most
$m$, then its exponent is at most
$\operatorname{lcm}(1,2,\dots,m)=e^{m(1+o(1))}$. (This asymptotic formula for
$\operatorname{lcm}(1,2,\dots,m)$ is a variant of the prime number theorem.
See, for example, Theorem 11 in [23] for a stronger bound on
$\psi(m)=\log\operatorname{lcm}(1,2,\dots,m)$.)

######  Theorem A.

There exists an absolute constant
$\varepsilon=\frac{1}{2}\log((2/3)2^{2/3})=0.02831\ldots$ such that if $H$ is
an abelian group generated by elements of order at most $m$, then every
tricolored sum-free set in $H$ has size at most $3\cdot\left\lvert
H\right\rvert^{1-\frac{\varepsilon}{m}}$.

In the case when $H$ is a power of a single cyclic group
${\mathbb{Z}}/p^{k}{\mathbb{Z}}$, we obtain a sharper bound.

######  Theorem A′.

There exists an absolute constant $\delta=2\varepsilon=0.05663\ldots$ such
that if $H\cong({\mathbb{Z}}/q{\mathbb{Z}})^{n}$ for some prime power $q$,
then every tricolored sum-free set in $H$ has size at most $3\cdot\left\lvert
H\right\rvert^{1-\frac{\delta}{\log q}}$.

These theorems extend the Ellenberg–Gijswijt [11] result in two directions:
from progression-free sets to tricolored sum-free sets111Noga Alon
independently observed that the Ellenberg–Gijswijt result extends to
tricolored sum-free sets in ${\mathbb{F}}_{p}^{n}$. and from abelian groups of
prime exponent to abelian groups of bounded exponent. In particular, Theorem A
disproves the strong USP conjecture via [1]. Note that when $H$ has prime
exponent $p$, the bound in Theorem A′ of $3\cdot\left\lvert
H\right\rvert^{1-\frac{\delta}{\log p}}$ agrees with the bound for
progression-free sets obtained in [11], but with a slightly worse exponent as
we have stated it uniformly in $p$. It remains to be seen whether
$\frac{\varepsilon}{m}$ can be improved to $\frac{c}{\log m}$ for general
abelian groups of bounded exponent. A generalization of the Ellenberg–Gijswijt
result that handles progression-free sets in abelian $p$-groups of bounded
exponent was also obtained by Petrov in [20].

In the proof of Theorem A, we study a variant of tensor rank due to Tao [22],
which we call slice rank, and we show how slice rank is related to a
quantitative version of the notion of instability from geometric invariant
theory. We show that functions with low slice rank are unstable, and
conversely prove that a quantitative bound on instability yields a bound on
slice rank of tensor powers (see Section 4.2).

Our second main result generalizes [1] by showing that every STPP construction
yields a large tricolored sum-free set. Together these two facts show that it
is impossible to prove $\omega=2$ using sets satisfying the simultaneous
triple product property in abelian groups of bounded exponent:

######  Theorem B.

For every $\ell\in{\mathbb{N}}$, there is an $\varepsilon_{\ell}>0$ such that
no STPP construction in any abelian group of exponent at most $\ell$ is large
enough to yield a bound better than $\omega\leq 2+\varepsilon_{\ell}$ via the
inequality (1.1).

Note that all of the current best bounds on $\omega$ via the group-theoretic
approach (in [4]), as well as the current best bounds on $\omega$ which use
the Coppersmith–Winograd approach [7, 10, 24, 15], yield STPP constructions
whose underlying group is $({\mathbb{Z}}/m{\mathbb{Z}})^{n}$ for $m$ fixed.

However, our results _do not_ rule out achieving $\omega=2$ by using STPP
constructions over abelian groups. Specifically, when the group has a large
cyclic factor, it indeed contains a large sum-free subset and thus the
constraints analyzed here are irrelevant. Furthermore, one can use non-abelian
groups or even more general objects such as association schemes [6]. Thus, our
results serve to focus the search for group-theoretic constructions, and
certainly do _not_ rule them out as an approach to achieving $\omega=2$.

##  2 The simultaneous triple product property

Recall that the _exponent of matrix multiplication_ is defined as

$\omega=\inf\\{c:\text{the tensor rank of $n\times n$ matrix multiplication is
at most }O(n^{c})\text{ as }n\to\infty\\}.$

In 2003, Cohn and Umans [5] described a framework for proving upper bounds on
$\omega$ by reducing matrix multiplication to group algebra multiplication.
This reduction is carried out by means of a triple of subsets satisfying the
_triple product property_ :

######  Definition 2.1 ([5, Definition 2.1]).

Subsets $A,B,C$ of a group $G$ satisfy the _triple product property_ if

$abc=1\iff a=b=c=1$

for all $a\in A^{-1}A$, $b\in B^{-1}B$, and $c\in C^{-1}C$, where $S^{-1}S$
denotes $\\{s^{-1}s^{\prime}:s,s^{\prime}\in S\\}$ for $S\subseteq G$.

Such a triple of subsets realizes $\langle\left\lvert
A\right\rvert,\left\lvert B\right\rvert,\left\lvert C\right\rvert\rangle$
inside the group algebra of $G$. (Here $\langle m,n,p\rangle$ denotes the
matrix multiplication tensor for multiplying an $m\times n$ matrix by an
$n\times p$ matrix.) From this, letting $d_{1},d_{2},\dots$ be the character
degrees of $G$ (i.e., the dimensions of its irreducible representations), we
obtain the inequality

$(\left\lvert A\right\rvert\left\lvert B\right\rvert\left\lvert
C\right\rvert)^{\omega/3}\leq\sum_{i}d_{i}^{\omega}$

by bounding the rank of group algebra multiplication [5, Theorem 4.1]. This
inequality yields an upper bound for $\omega$ when $G$ and $A,B,C$ are chosen
appropriately.

In the later paper [4] several concrete routes to proving $\omega=2$ were
proposed. These proposals seemingly go beyond the framework of the triple
product property in various different ways; however as described in [4, §7],
all of these constructions can be uniformly described using the triple product
property as follows. Several independent matrix multiplications are realized
via the triple product property in the group algebra of a wreath product $H\wr
S_{m}=H^{m}\rtimes S_{m}$ using certain well-chosen subsets of a group $H$.
This general formulation is captured by the simultaneous triple product
property:

######  Definition 2.2 ([4, Definition 5.1]).

An _STPP construction_ is a collection of triples of subsets
$A_{i},B_{i},C_{i}$ of a group $H$ satisfying the _simultaneous triple product
property_ (STPP), which states that

  1. 1.

for each $i$ the sets $A_{i},B_{i},C_{i}$ satisfy the triple product property,
and

  2. 2.

setting $S_{i}=A_{i}B_{i}^{-1}$, $T_{j}=B_{j}C_{j}^{-1}$, and
$U_{k}=C_{k}A_{k}^{-1}$,

$s_{i}t_{j}u_{k}=1\quad\Rightarrow\quad i=j=k$

for all $s_{i}\in S_{i}$, $t_{j}\in T_{j}$, and $u_{k}\in U_{k}$.

Equivalently, $A_{i},B_{i},C_{i}\subseteq H$ satisfy the STPP if for all
$i,j,k$ and $s\in A_{k}$, $s^{\prime}\in A_{i}$, $t\in B_{i}$, $t^{\prime}\in
B_{j}$, $u\in C_{j}$, and $u^{\prime}\in C_{k}$, we have

$s^{-1}s^{\prime}t^{-1}t^{\prime}u^{-1}u^{\prime}=1\quad\iff\quad i=j=k,\ \
s=s^{\prime},\ \ t=t^{\prime},\ \ u=u^{\prime}.$

An STPP construction in $H$ realizes the tensor
$\bigoplus_{i}\langle\left\lvert A_{i}\right\rvert,\left\lvert
B_{i}\right\rvert,\left\lvert C_{i}\right\rvert\rangle$ and, via the
asymptotic sum inequality [21] or the use of a wreath product [4, §7], yields
the fundamental inequality

$\sum_{i}(\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\left\lvert
C_{i}\right\rvert)^{\omega/3}\leq\sum_{i}d_{i}^{\omega},$ (2.1)

where $d_{1},d_{2},\dots$ are the character degrees of $H$. For the rest of
this paper we will take $H$ to be abelian (with additive notation), in which
case this bound becomes the inequality (1.1) of the introduction:

$\sum_{i}(\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\left\lvert C_{i}\right\rvert)^{\omega/3}\leq\left\lvert
H\right\rvert.$

All of the analysis of STPP constructions in the framework of [4] is based on
this inequality.

No single STPP construction can achieve $\omega=2$ via (2.1) (more generally,
see [8]), so we must consider families of constructions in groups of growing
size. To simplify the notation we typically do not index such families
explicitly (i.e., we refer to a group $H$ rather than, say,
$\\{H_{\alpha}\\}_{\alpha\in A}$).

Any STPP construction satisfies some simple “packing bound” inequalities,
which reflect the fact that the sets $S_{i}$ must be disjoint from each other,
as must $T_{i}$ and $U_{i}$. This disjointness follows immediately from the
second condition in the definition of the simultaneous triple product
property. Furthermore, since the sets $A_{i},B_{i},C_{i}$ satisfy the triple
product property we must have $\left\lvert S_{i}\right\rvert=\left\lvert
A_{i}\right\rvert\left\lvert B_{i}\right\rvert$, $\left\lvert
T_{i}\right\rvert=\left\lvert B_{i}\right\rvert\left\lvert C_{i}\right\rvert$,
and $\left\lvert U_{i}\right\rvert=\left\lvert C_{i}\right\rvert\left\lvert
A_{i}\right\rvert$. Together these give the packing bounds:

$\sum_{i}\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\leq\left\lvert H\right\rvert,\qquad\sum_{i}\left\lvert
B_{i}\right\rvert\left\lvert C_{i}\right\rvert\leq\left\lvert
H\right\rvert,\quad\text{and}\quad\sum_{i}\left\lvert
C_{i}\right\rvert\left\lvert A_{i}\right\rvert\leq\left\lvert H\right\rvert.$

######  Definition 2.3.

We say that a family of STPP constructions with $\left\lvert
H\right\rvert\to\infty$ _meets the packing bound_ if

$\sum_{i}\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\geq\left\lvert
H\right\rvert^{1-o(1)},\qquad\sum_{i}\left\lvert B_{i}\right\rvert\left\lvert
C_{i}\right\rvert\geq\left\lvert
H\right\rvert^{1-o(1)},\quad\text{and}\quad\sum_{i}\left\lvert
C_{i}\right\rvert\left\lvert A_{i}\right\rvert\geq\left\lvert
H\right\rvert^{1-o(1)}.$

A key observation is that meeting the packing bound is necessary for achieving
$\omega=2$:

######  Lemma 2.4.

Any family of STPP constructions that does _not_ meet the packing bound cannot
imply $\omega=2$ via the inequality (1.1).

###### Proof.

In our usual notation, if $\sum_{i}\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\leq\left\lvert H\right\rvert^{1-3\varepsilon}$ for some
fixed $\varepsilon>0$, then

$\displaystyle\sum_{i}(\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\left\lvert C_{i}\right\rvert)^{\omega/3}$
$\displaystyle\leq\Big{(}\sum_{i}(\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\left\lvert C_{i}\right\rvert)^{2/3}\Big{)}^{\omega/2}$
$\displaystyle=\bigg{(}\sum_{i}\left(\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\left\lvert H\right\rvert^{2\varepsilon}\cdot\left\lvert
B_{i}\right\rvert\left\lvert C_{i}\right\rvert\left\lvert
H\right\rvert^{-\varepsilon}\cdot\left\lvert C_{i}\right\rvert\left\lvert
A_{i}\right\rvert\left\lvert
H\right\rvert^{-\varepsilon}\right)^{1/3}\bigg{)}^{\omega/2}$
$\displaystyle\leq\bigg{(}\frac{\sum_{i}\left\lvert
A_{i}\right\rvert\left\lvert B_{i}\right\rvert\left\lvert
H\right\rvert^{2\varepsilon}+\sum_{i}\left\lvert B_{i}\right\rvert\left\lvert
C_{i}\right\rvert\left\lvert H\right\rvert^{-\varepsilon}+\sum_{i}\left\lvert
C_{i}\right\rvert\left\lvert A_{i}\right\rvert\left\lvert
H\right\rvert^{-\varepsilon}}{3}\bigg{)}^{\omega/2}$
$\displaystyle\leq\big{(}\left\lvert
H\right\rvert^{1-\varepsilon}\big{)}^{\omega/2},$

and so the strongest bound that can be obtained from (1.1) is $\omega\leq
2\cdot\frac{1}{1-\varepsilon}$, which is bounded strictly away from the hoped-
for $\omega=2$. The same holds if either $\sum_{i}\left\lvert
B_{i}\right\rvert\left\lvert C_{i}\right\rvert\leq\left\lvert
H\right\rvert^{1-3\varepsilon}$ or $\sum_{i}\left\lvert
C_{i}\right\rvert\left\lvert A_{i}\right\rvert\leq\left\lvert
H\right\rvert^{1-3\varepsilon}$. ∎

Both the strong USP conjecture [4, Conjecture 3.4] and the “two families”
conjecture [4, Conjecture 4.7] would, if true, yield STPP constructions that
meet the packing bound and moreover prove $\omega=2$. However, the STPP
constructions produced by the strong USP conjecture have underlying group
$H={\mathbb{F}}_{3}^{n}$, while the groups in the two families conjecture need
not have bounded exponent. Thus although Theorem B disproves the strong USP
conjecture, it addresses only very special cases of the two families
conjecture.

##  3 STPP constructions and tricolored sum-free sets

######  Definition 3.1.

A _tricolored sum-free set_ in an abelian group $H$ is a 3-dimensional perfect
matching $M\subseteq S\times T\times U$ on a triple of sets $S,T,U\subseteq
H$, such that

$s+t+u=0\text{ for all }(s,t,u)\in M$

and

$s+t+u\neq 0\text{ for all }(s,t,u)\in(S\times T\times U)\setminus M.$

The _cardinality_ of a tricolored sum-free set is the cardinality of $M$.

By a perfect matching $M\subseteq S\times T\times U$ we mean a subset whose
projection onto each of the three factors is a bijection. In other words,
given $s\in S$ there exist unique $t\in T$ and $u\in U$ such that $(s,t,u)\in
M$, and similarly for the other factors. The cardinality of the matching $M$
is therefore equal to $\left\lvert S\right\rvert$, $\left\lvert
T\right\rvert$, and $\left\lvert U\right\rvert$. Note that any 3-dimensional
matching $M\subseteq H^{3}$ (not necessarily perfect, i.e., replacing
“bijection” above with “injection”) uniquely determines three sets
$S,T,U\subseteq H$ such that $M$ is a 3-dimensional perfect matching on
$S\times T\times U$.

If $S\subseteq{\mathbb{F}}_{p}^{n}$ contains no three-term arithmetic
progressions, then $M=\\{(s,s,-2s):s\in S\\}$ is a tricolored sum-free set.
Similarly, for any nonzero $\alpha,\beta,\gamma\in{\mathbb{F}}_{p}$ with
$\alpha+\beta+\gamma=0$, we obtain a tricolored sum-free set $M=\\{(\alpha
s,\beta s,\gamma s):s\in S\\}$ whenever $S$ avoids nontrivial solutions to
$\alpha s+\beta t+\gamma u=0$.

In this section, we show how to obtain a tricolored sum-free set from any STPP
construction in an abelian group. This allows us to prove that Theorem A
implies Theorem B; we then prove Theorem A in Section 4.

###  3.1 STPP constructions imply tricolored sum-free sets

We will first construct slightly weaker objects we call border tricolored sum-
free sets, which are motivated by the notion of combinatorial degeneration in
the theory of border rank (see Definition 15.29 in [2]). We will then use
border tricolored sum-free sets to construct genuine tricolored sum-free sets.

######  Definition 3.2.

A _border tricolored sum-free set_ in an abelian group $H$ is a 3-dimensional
perfect matching $M\subseteq S\times T\times U$ on a triple of sets
$S,T,U\subseteq H$ together with functions $\alpha\colon S\to{\mathbb{Z}}$,
$\beta\colon T\to{\mathbb{Z}}$, and $\gamma\colon U\to{\mathbb{Z}}$ such that

$s+t+u=0\quad\text{and}\quad\alpha(s)+\beta(t)+\gamma(u)=0$

for all $(s,t,u)\in M$, while

$s+t+u\neq 0\quad\text{or}\quad\alpha(s)+\beta(t)+\gamma(u)>0$

for all $(s,t,u)\in(S\times T\times U)\setminus M$. The _cardinality_ of a
border tricolored sum-free set is the cardinality of $M$, and its _range_ is
the maximum of $|\alpha(s)|$, $|\beta(t)|$, and $|\gamma(u)|$ over $s\in S$,
$t\in T$, and $u\in U$.

One can reformulate the definition as follows: the sets $\\{(s,\alpha(s)):s\in
S\\}$, $\\{(t,\beta(t)):t\in T\\}$, and $\\{(u,\gamma(u)):u\in U\\}$ form a
tricolored sum-free set in $H\times{\mathbb{Z}}$ (under the obvious
$3$-dimensional matching extending $M$), and they satisfy the positivity
condition that $\alpha(s)+\beta(t)+\gamma(u)\geq 0$ whenever $s+t+u=0$.

One of our main new contributions in this paper is the following construction:

######  Theorem 3.3.

Let $A_{i},B_{i},C_{i}\subseteq H$ be an STPP construction in an abelian group
$H$. Then there is a border tricolored sum-free set in $H$ of cardinality at
least

$\sum_{i}\frac{\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\left\lvert C_{i}\right\rvert}{\left\lvert
A_{i}\right\rvert+\left\lvert B_{i}\right\rvert+\left\lvert
C_{i}\right\rvert}.$

###### Proof.

As in Definition 2.2 (but using additive notation), we will set
$S_{i}=A_{i}-B_{i}=\\{a-b:a\in A_{i},b\in B_{i}\\}$, and similarly
$T_{i}=B_{i}-C_{i}$ and $U_{i}=C_{i}-A_{i}$.

We will first construct a matching $M$ out of smaller matchings $M_{i}$ on
subsets of $S_{i}$, $T_{i}$, and $U_{i}$. This matching will not quite be a
tricolored sum-free set in general, but we will define functions $\alpha$,
$\beta$, and $\gamma$ that repair any problems with it, so that it becomes a
border tricolored sum-free set.

To begin, let $n_{i}=\left\lvert A_{i}\right\rvert$, $m_{i}=\left\lvert
B_{i}\right\rvert$, and $p_{i}=\left\lvert C_{i}\right\rvert$, and identify
$A_{i},B_{i},C_{i}$ with $[n_{i}],[m_{i}],[p_{i}]$, respectively, via
bijections $\alpha_{i},\beta_{i},\gamma_{i}$. Let $r_{i}$ be the most
frequently occurring value in the multiset

$\\{x+y+z:(x,y,z)\in[n_{i}]\times[m_{i}]\times[p_{i}]\\}.$

Define $M_{i}\subseteq H^{3}$ as

$M_{i}=\\{(a-b,b-c,c-a):\mbox{$a\in A_{i}$, $b\in B_{i}$, $c\in C_{i}$ such
that $\alpha_{i}(a)+\beta_{i}(b)+\gamma_{i}(c)=r_{i}$}\\}.$

The size of $M_{i}$ is the number of times $r_{i}$ occurs in the multiset
above. The number of distinct elements of the multiset is
$n_{i}+m_{i}+p_{i}-2$; we can ignore the 2 and bound this by $\left\lvert
A_{i}\right\rvert+\left\lvert B_{i}\right\rvert+\left\lvert
C_{i}\right\rvert$. Since $r_{i}$ was chosen to be the most frequent value,

$\left\lvert M_{i}\right\rvert\geq\frac{\left\lvert
A_{i}\right\rvert\left\lvert B_{i}\right\rvert\left\lvert
C_{i}\right\rvert}{\left\lvert A_{i}\right\rvert+\left\lvert
B_{i}\right\rvert+\left\lvert C_{i}\right\rvert}.$

Each $M_{i}$ is a $3$-dimensional perfect matching: given the first coordinate
$a-b$, the triple product property determines $a$ and $b$ from $a-b$, and then
$\alpha_{i}(a)+\beta_{i}(b)+\gamma_{i}(c)=r_{i}$ determines $c$, and the same
is true for the other two coordinates. We combine these matchings by setting
$M=\bigcup_{i}M_{i}$. Note that the sets $M_{i}$ are disjoint from each other
(since the sets $S_{i}$ are, for example), so $\left\lvert
M\right\rvert=\sum_{i}\left\lvert M_{i}\right\rvert$. All that remains is to
define the functions $\alpha,\beta,\gamma$ so as to obtain a border tricolored
sum-free set.

Let $S^{\prime}_{i}$, $T^{\prime}_{i}$, $U^{\prime}_{i}$ be the projections of
$M_{i}$ onto the three factors of $H^{3}$. In other words,

$S^{\prime}_{i}=\\{a-b:\mbox{$a\in A_{i}$, $b\in B_{i}$, and there exists
$c\in C_{i}$ such that
$\alpha_{i}(a)+\beta_{i}(b)+\gamma_{i}(c)=r_{i}$}\\}\subseteq S_{i},$

and $T^{\prime}_{i}$ and $U^{\prime}_{i}$ can be expressed similarly. Let
$S=\bigcup_{i}S^{\prime}_{i}$, $T=\bigcup_{i}T^{\prime}_{i}$, and
$U=\bigcup_{i}U^{\prime}_{i}$, so that $M$ is a perfect matching between $S$,
$T$, and $U$.

To complete the proof, we must analyze when $s+t+u=0$ with $s\in S$, $t\in T$,
and $u\in U$. First, note that the simultaneous triple product property
implies that if $s_{i}+t_{j}+u_{k}=0$ with $s_{i}\in S_{i}$, $t_{j}\in T_{j}$,
and $u_{k}\in U_{k}$, then $i=j=k$. Thus, we cannot obtain a sum of zero from
$S^{\prime}_{i}$, $T^{\prime}_{j}$, and $U^{\prime}_{k}$ unless $i=j=k$, so we
can analyze each matching $M_{i}$ individually, without worrying about how
they might interact with each other. More specifically, if for each $i$ we can
find functions on $S^{\prime}_{i}$, $T^{\prime}_{i}$, and $U^{\prime}_{i}$
that make $M_{i}$ into a border tricolored sum-free set, then this yields
functions on $S$, $T$, and $U$ that make $M$ into a border tricolored sum-free
set.

Now consider $(s,t,u)\in S_{i}^{\prime}\times T_{i}^{\prime}\times
U_{i}^{\prime}$, with $s=a-b^{\prime}\in A_{i}-B_{i}$, $t=b-c^{\prime}\in
B_{i}-C_{i}$, and $u=c-a^{\prime}\in C_{i}-A_{i}$. Note that $s$ determines
$a$ and $b^{\prime}$, $t$ determines $b$ and $c^{\prime}$, and $u$ determines
$c$ and $a^{\prime}$ since $A_{i},B_{i},C_{i}$ satisfy the triple product
property. Furthermore, the triple product property tells us that

$s+t+u=0\quad\text{implies}\quad a=a^{\prime},\ b=b^{\prime},\ c=c^{\prime}.$

However, that is not enough to conclude that $(s,t,u)\in M_{i}$, because it is
not necessarily the case that
$\alpha_{i}(a)+\beta_{i}(b)+\gamma_{i}(c)=r_{i}$. To address this issue, we
will define functions $\alpha$, $\beta$, and $\gamma$ on $S^{\prime}_{i}$,
$T^{\prime}_{i}$, and $U^{\prime}_{i}$, respectively, so that

$\alpha(s)+\beta(t)+\gamma(u)=\big{(}\alpha_{i}(a)+\beta_{i}(b)+\gamma_{i}(c)-r_{i}\big{)}^{2}$

whenever $s+t+u=0$. Specifically, we can take

$\displaystyle\alpha(s)$
$\displaystyle=\alpha_{i}(a)^{2}+2\alpha_{i}(a)\beta_{i}(b^{\prime})-2\alpha_{i}(a)r_{i}+r_{i}^{2},$
$\displaystyle\beta(t)$
$\displaystyle=\beta_{i}(b)^{2}+2\beta_{i}(b)\gamma_{i}(c^{\prime})-2\beta_{i}(b)r_{i},\quad\text{and}$
$\displaystyle\gamma(u)$
$\displaystyle=\gamma_{i}(c)^{2}+2\gamma_{i}(c)\alpha_{i}(a^{\prime})-2\gamma_{i}(c)r_{i}.$

(We simply expand the square and assign each term to one of
$\alpha(s),\beta(t),\gamma(u)$ so that $\alpha(s)$ depends only on $a$ and
$b^{\prime}$, $\beta(t)$ depends only on $b$ and $c^{\prime}$, and $\gamma(u)$
depends only on $c$ and $a^{\prime}$.)

By construction, $\alpha(s)+\beta(t)+\gamma(u)\geq 0$ whenever $s+t+u=0$, and
$\alpha(s)+\beta(t)+\gamma(u)=0$ exactly when $(s,t,u)\in M_{i}$. Thus, we
have constructed a border tricolored sum-free set, as desired. ∎

######  Lemma 3.4.

Let $H$ be an abelian group in which there is a border tricolored sum-free set
of cardinality $|M|$ and range $t$. Then for each natural number $N$, there
exists a tricolored sum-free set in $H^{N}$ of cardinality at least
$|M|^{N}/(2Nt+1)^{3}$.

In particular, as $N\to\infty$ there are tricolored sum-free sets in $H^{N}$
of cardinality $|M|^{(1-o(1))N}$.

###### Proof.

We will use the notation from Definition 3.2 for the border tricolored sum-
free set in $H$: let $M$ be the perfect matching on sets $S,T,U\subseteq H$,
with functions $\alpha\colon S\to{\mathbb{Z}}$, $\beta\colon
T\to{\mathbb{Z}}$, and $\gamma\colon U\to{\mathbb{Z}}$.

Define $M^{\prime}\subseteq(S^{N}\times T^{N}\times U^{N})$ in the natural
way, so that $((s_{1},\dots,s_{N}),(t_{1},\dots,t_{N}),(u_{1},\dots,u_{N}))\in
M^{\prime}$ if and only if $(s_{i},t_{i},u_{i})\in M$ for all $i$, and define
$\alpha(s_{1},\dots,s_{N})=\alpha(s_{1})+\dots+\alpha(s_{N})$ and similarly
for $\beta$ and $\gamma$. This construction yields a border tricolored sum-
free set of cardinality $|M|^{N}$ and range $Nt$ in $H^{N}$.

To obtain a genuine tricolored sum-free set, we will shrink $M^{\prime}$ by a
small amount. Because the functions $\alpha,\beta,\gamma$ for $M^{\prime}$
have range $Nt$ (and thus each take on at most $2Nt+1$ values), there exist
integers $\alpha^{*},\beta^{*},\gamma^{*}$ such that for at least a
$1/(2Nt+1)^{3}$ fraction of the triples $(s^{\prime},t^{\prime},u^{\prime})\in
M^{\prime}$, we have $\alpha(s^{\prime})=\alpha^{*}$,
$\beta(t^{\prime})=\beta^{*}$, and $\gamma(u^{\prime})=\gamma^{*}$.
Furthermore, $\alpha^{*}+\beta^{*}+\gamma^{*}=0$ because
$\alpha(s^{\prime})+\beta(t^{\prime})+\gamma(u^{\prime})=0$ whenever
$(s^{\prime},t^{\prime},u^{\prime})\in M^{\prime}$.

Let $M^{\prime\prime}$ be the subset of $M^{\prime}$ consisting of these
triples with $\alpha(s^{\prime})=\alpha^{*}$, $\beta(t^{\prime})=\beta^{*}$,
and $\gamma(u^{\prime})=\gamma^{*}$, and let
$S^{\prime\prime},T^{\prime\prime},U^{\prime\prime}$ be the sets on which
$M^{\prime\prime}$ is a perfect matching. Then
$|M^{\prime\prime}|\geq|M^{\prime}|/(2Nt+1)^{3}=$ $|M|^{N}/(2Nt+1)^{3}$, and
$M^{\prime\prime}$ is trivially a border tricolored sum-free set. Furthermore,

$\alpha(s^{\prime\prime})+\beta(t^{\prime\prime})+\gamma(u^{\prime\prime})=\alpha^{*}+\beta^{*}+\gamma^{*}=0$

whenever $s^{\prime\prime}\in S^{\prime\prime}$, $t^{\prime\prime}\in
T^{\prime\prime}$, and $u^{\prime\prime}\in U^{\prime\prime}$, by
construction. Because
$\alpha(s^{\prime\prime})+\beta(t^{\prime\prime})+\gamma(u^{\prime\prime})$
vanishes identically, the functions $\alpha$, $\beta$, and $\gamma$ serve no
purpose in the definition of a border tricolored sum-free set. Thus,
$M^{\prime\prime}$ reduces to an actual tricolored sum-free set, as desired. ∎

To control the size of the tricolored sum-free sets resulting from Theorem 3.3
and Lemma 3.4, we will need the following notion. We say that an STPP
construction is _uniform_ if $\left\lvert A_{i}\right\rvert$ is independent of
$i$, as are $\left\lvert B_{i}\right\rvert$ and $\left\lvert
C_{i}\right\rvert$ (note that we do not require $\left\lvert
A_{i}\right\rvert=\left\lvert B_{i}\right\rvert=\left\lvert
C_{i}\right\rvert$).

######  Lemma 3.5.

If there is a family of STPP constructions in abelian groups $H$ meeting the
packing bound, then there is a family of _uniform_ STPP constructions in
powers of $H$ meeting the packing bound.

###### Proof.

Let the original STPP construction consist of $n$ triples $A_{i},B_{i},C_{i}$
of subsets of $H$ indexed by $i\in[n]$. Our new STPP construction will consist
of subsets of $H^{3N}$, where $N$ is a large number to be chosen later; these
subsets are indexed by triples $(u,v,w)\in[n]^{N}\times[n]^{N}\times[n]^{N}$
and defined by

$\displaystyle\widehat{A}_{u,v,w}$
$\displaystyle=\prod_{\ell}A_{u_{\ell}}\times\prod_{\ell}B_{v_{\ell}}\times\prod_{\ell}C_{w_{\ell}},$
$\displaystyle\widehat{B}_{u,v,w}$
$\displaystyle=\prod_{\ell}B_{u_{\ell}}\times\prod_{\ell}C_{v_{\ell}}\times\prod_{\ell}A_{w_{\ell}},$
$\displaystyle\widehat{C}_{u,v,w}$
$\displaystyle=\prod_{\ell}C_{u_{\ell}}\times\prod_{\ell}A_{v_{\ell}}\times\prod_{\ell}B_{w_{\ell}}.$

(The products here are cartesian products of sets.) It is not hard to verify
that these sets satisfy the STPP in $H^{3N}$ (see [4, Lemma 5.4]). The
resulting STPP construction is not yet uniform, but will become so below when
we restrict the choices of $u$, $v$, and $w$. We first argue that the STPP
construction $\widehat{A}_{u,v,w},\widehat{B}_{u,v,w},\widehat{C}_{u,v,w}$
meets the packing bound if the original sets $A_{i},B_{i},C_{i}$ did.

To check that this construction meets the packing bound, we observe that

$\Big{(}\sum_{i}\left\lvert A_{i}\right\rvert\left\lvert
B_{i}\right\rvert\Big{)}^{N}\cdot\Big{(}\sum_{i}\left\lvert
B_{i}\right\rvert\left\lvert
C_{i}\right\rvert\Big{)}^{N}\cdot\Big{(}\sum_{i}\left\lvert
C_{i}\right\rvert\left\lvert A_{i}\right\rvert\Big{)}^{N}\geq\left\lvert
H\right\rvert^{3N(1-o(1))}$

because the original STPP construction meets the packing bound. Expanding the
left side gives

$\sum_{u}\prod_{\ell}\left\lvert A_{u_{\ell}}\right\rvert\left\lvert
B_{u_{\ell}}\right\rvert\cdot\sum_{v}\prod_{\ell}\left\lvert
B_{v_{\ell}}\right\rvert\left\lvert
C_{v_{\ell}}\right\rvert\cdot\sum_{w}\prod_{\ell}\left\lvert
C_{w_{\ell}}\right\rvert\left\lvert
A_{w_{\ell}}\right\rvert=\sum_{u,v,w}\prod_{\ell}\left\lvert
A_{u_{\ell}}\right\rvert\left\lvert B_{v_{\ell}}\right\rvert\left\lvert
C_{w_{\ell}}\right\rvert\left\lvert B_{u_{\ell}}\right\rvert\left\lvert
C_{v_{\ell}}\right\rvert\left\lvert A_{w_{\ell}}\right\rvert.$

We have

$\big{\lvert}\widehat{A}_{u,v,w}\big{\rvert}\big{\lvert}\widehat{B}_{u,v,w}\big{\rvert}=\prod_{\ell}\left\lvert
A_{u_{\ell}}\right\rvert\left\lvert B_{v_{\ell}}\right\rvert\left\lvert
C_{w_{\ell}}\right\rvert\left\lvert B_{u_{\ell}}\right\rvert\left\lvert
C_{v_{\ell}}\right\rvert\left\lvert A_{w_{\ell}}\right\rvert$ (3.1)

and hence

$\sum_{u,v,w}\big{\lvert}\widehat{A}_{u,v,w}\big{\rvert}\big{\lvert}\widehat{B}_{u,v,w}\big{\rvert}\geq\left\lvert
H\right\rvert^{3N(1-o(1))},$

as desired; the same also holds for
$\sum_{u,v,w}\big{\lvert}\widehat{B}_{u,v,w}\big{\rvert}\big{\lvert}\widehat{C}_{u,v,w}\big{\rvert}$
and
$\sum_{u,v,w}\big{\lvert}\widehat{A}_{u,v,w}\big{\rvert}\big{\lvert}\widehat{C}_{u,v,w}\big{\rvert}$.

To enforce uniformity, we restrict our attention to only certain choices of
$u$, $v$, and $w$ by observing that the cardinality

$\big{\lvert}\widehat{A}_{u,v,w}\big{\rvert}=\prod_{\ell}\left\lvert
A_{u_{\ell}}\right\rvert\left\lvert B_{v_{\ell}}\right\rvert\left\lvert
C_{w_{\ell}}\right\rvert$

depends only on the _distributions_ of $u,v,w$ (where the distribution of $u$
is the vector specifying the number of times each element of $[n]$ occurs in
$u$). The same is true for $\lvert\widehat{B}_{u,v,w}\rvert$ and
$\lvert\widehat{C}_{u,v,w}\rvert$. There are $\binom{N+n-1}{n-1}$ possible
distributions, but all we need is the crude upper bound $(N+1)^{n}$ from the
fact that each element of $[n]$ occurs between $0$ and $N$ times. It follows
that there is at least one triple $\mu_{1},\mu_{2},\mu_{3}$ of distributions
for which

$\sum_{u\sim\mu_{1}}\prod_{\ell}\left\lvert
A_{u_{\ell}}\right\rvert\left\lvert
B_{u_{\ell}}\right\rvert\cdot\sum_{v\sim\mu_{2}}\prod_{\ell}\left\lvert
B_{v_{\ell}}\right\rvert\left\lvert
C_{v_{\ell}}\right\rvert\cdot\sum_{w\sim\mu_{3}}\prod_{\ell}\left\lvert
C_{w_{\ell}}\right\rvert\left\lvert
A_{w_{\ell}}\right\rvert\geq\frac{1}{(N+1)^{3n}}\left\lvert
H\right\rvert^{3N(1-o(1))},$ (3.2)

where $u\sim\mu_{1}$ means $u$ has distribution $\mu_{1}$.

Restricting to only those sets $\widehat{A}_{u,v,w}$, $\widehat{B}_{u,v,w}$,
and $\widehat{C}_{u,v,w}$ with $u\sim\mu_{1}$, $v\sim\mu_{2}$, and
$w\sim\mu_{3}$ thus gives a uniform STPP construction. Combining (3.1) and
(3.2) we obtain

$\sum_{u\sim\mu_{1},v\sim\mu_{2},w\sim\mu_{3}}\big{\lvert}\widehat{A}_{u,v,w}\big{\rvert}\big{\lvert}\widehat{B}_{u,v,w}\big{\rvert}\geq\frac{1}{(N+1)^{3n}}\left\lvert
H\right\rvert^{3N(1-o(1))},$

which is again $\left\lvert H\right\rvert^{3N(1-o(1))}$ as long as $N$ is
chosen sufficiently large relative to $n$ and $\left\lvert H\right\rvert$. The
same holds for the other two conditions in the packing bound.

Choosing $N$ and $\mu_{1},\mu_{2},\mu_{3}$ in this way thus yields a family of
uniform STPP constructions meeting the packing bound in powers of $H$, as
desired. ∎

###  3.2 Theorem A implies Theorem B

We conclude this section by proving that Theorem A implies Theorem B; we will
then prove Theorem A in Section 4.

Fix $\ell\in{\mathbb{N}}$, and suppose that for each $\delta>0$ there is an
STPP construction in a group of exponent at most $\ell$ that proves
$\omega\leq 2+\delta$. Choosing a sequence with $\delta$ tending to zero, we
obtain a family of STPP constructions that meets the packing bound by Lemma
2.4. Furthermore Lemma 3.5 lets us inflate these constructions to make them
uniform, while still meeting the packing bound, in powers of the original
groups; in particular, the exponent of all our groups is still at most $\ell$.

Consider one of these uniform STPP constructions in a group $H$ of exponent at
most $\ell$, thus generated by elements of order at most $\ell$. By Theorem
3.3 there exists a border tricolored sum-free set in $H$ of cardinality
$\left\lvert M\right\rvert=\sum_{i}\frac{\left\lvert
A_{i}\right\rvert\left\lvert B_{i}\right\rvert\left\lvert
C_{i}\right\rvert}{\left\lvert A_{i}\right\rvert+\left\lvert
B_{i}\right\rvert+\left\lvert C_{i}\right\rvert}$. Since $\left\lvert
A_{i}\right\rvert$, $\left\lvert B_{i}\right\rvert$, and $\left\lvert
C_{i}\right\rvert$ are each independent of $i$, without loss of generality we
may assume that $\left\lvert C_{i}\right\rvert$ is the largest of these, in
which case

$\left\lvert M\right\rvert=\sum_{i}\frac{\left\lvert
A_{i}\right\rvert\left\lvert B_{i}\right\rvert\left\lvert
C_{i}\right\rvert}{\left\lvert A_{i}\right\rvert+\left\lvert
B_{i}\right\rvert+\left\lvert
C_{i}\right\rvert}\geq\frac{1}{3}\sum_{i}\left\lvert
A_{i}\right\rvert\left\lvert B_{i}\right\rvert\geq\left\lvert
H\right\rvert^{1-o(1)}.$

Finally, Lemma 3.4 converts the border tricolored sum-free set to a genuine
tricolored sum-free set, at the cost of raising $H$ to a high power (which of
course does not change the exponent of this group). This contradicts Theorem
A, which states that the cardinality of any tricolored sum-free set in $H^{N}$
is at most $3\left\lvert H\right\rvert^{N(1-\frac{\varepsilon}{\ell})}$, and
thus completes the proof of Theorem B.

##  4 Tricolored sum-free sets in abelian groups of bounded exponent via rank
and instability of tensors

The remainder of the paper is devoted to the proof of Theorems A and A′. Our
approach builds on the symmetric formulation presented by Tao [22], although
an earlier version of this paper contained a more direct application of the
original methods [9, 11] to the ${\mathbb{F}}_{p}^{n}$ case.

We begin here by outlining the main ideas of the proof, giving a road map for
the remaining sections. In order to formulate the symmetric version, we
develop the notion of _slice rank_ (in Section 4.1), which is a weakening of
tensor rank. For tricolored sum-free sets in ${\mathbb{F}}_{p}^{n}$, the upper
bound is then a consequence of the following three facts about slice rank:

  1. 1.

Just as the ordinary matrix rank of an $m\times m$ diagonal matrix is equal to
$m$ if all the diagonal entries are nonzero, the same holds for the slice rank
of an $m\times m\times m$ diagonal tensor (over any field; see Lemma 4.7 or
[22, Lemma 1]).

  2. 2.

A tricolored sum-free set of cardinality $m$ in a group $G$ implies that the
multiplication tensor of the group algebra ${\mathbb{F}}G$ restricts to an
$m\times m\times m$ diagonal tensor with nonzero diagonal entries. It follows
that the slice rank of the multiplication tensor of ${\mathbb{F}}G$ is at
least the size of any tricolored sum-free set in $G$ (see Proposition 4.8).

  3. 3.

Over a field of characteristic $p$, the slice rank of the
${\mathbb{F}}_{p}^{n}$-multiplication tensor is at most the number of vectors
in $[p]^{n}$ with coordinate sum at most $pn/3$, which is at most
$(p-\varepsilon_{p})^{n}$ for some $\varepsilon_{p}>0$. By a remarkable
observation [9, 11, 22], this upper bound on the slice rank follows almost
immediately from the fact that the $(x,y,z)$ entry of the tensor in question
equals $\delta_{0}(x+y+z)$, and the delta function $\delta_{0}(x+y+z)$ (indeed
_every_ function of $x+y+z$) is expressible as an $n$-variate polynomial of
degree $(p-1)n$; see Observation 4.11.

These three statements give an upper bound of $(p-\varepsilon_{p})^{n}$ on the
cardinality of a tricolored sum-free set in ${\mathbb{F}}_{p}^{n}$. Expressed
a different way, the upper bound for $H={\mathbb{F}}_{p}^{n}$ is $\left\lvert
H\right\rvert^{1-\alpha_{p}}$ for some constant $\alpha_{p}>0$. In Section
4.4, we prove an upper bound of the same form for tricolored sum-free sets in
any group of the form $G=({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$ with $p$ prime,
using a similar argument but using binomial coefficients instead of
polynomials to describe the delta function.

We then extend this bound to _any_ abelian group $H$ of bounded exponent by
arguing that such a group must decompose as $H\cong G\times K$ where
$G\cong({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$ and $\left\lvert
G\right\rvert\geq\left\lvert H\right\rvert^{c}$ for a constant $c>0$. Such a
decomposition expresses the $H$-multiplication tensor $D_{H}$ as a tensor
product $D_{G}\otimes D_{K}$. We establish a simple but powerful property of
slice rank: the slice rank of $T\otimes T^{\prime}$ is at most the slice rank
of $T$ times the side length of $T^{\prime}$ (Proposition 4.2). This allows us
to reduce to the $({\mathbb{Z}}/p^{k}{\mathbb{Z}})^{n}$ case, because the
slice rank of $D_{H}$ is at most $\left\lvert
G\right\rvert^{1-\alpha}\left\lvert K\right\rvert=\left\lvert
H\right\rvert^{1-\alpha^{\prime}}$ for some constant $\alpha^{\prime}>0$. As
before, this bound on slice rank also bounds the cardinality of tricolored
sum-free sets in $G$.

In the presentation below, we draw connections to _(in)stability_ of tensors,
a notion coming from geometric invariant theory (GIT). This broader context
seems powerful, and potentially useful beyond the results in this paper.
However, the reader who is interested only in the proofs of Theorems A and B
can skip all of Section 4.2 except Lemma 4.7 and Proposition 4.8 and skip
Theorem 4.10 since we only need the shaper bound on slice rank stated in
Proposition 4.13, coming from triangle rank.

###  4.1 Tensor rank and its variants

Throughout this section, $X$, $Y$, and $Z$ will denote finite sets. A function
$F\colon X\times Y\to{\mathbb{F}}$ with values in a field ${\mathbb{F}}$ has
an unambiguous _rank_ ; $\operatorname{rank}(F)$ is the smallest $k$ for which
we can write $F(x,y)=\sum_{i=1}^{k}f_{i}(x)g_{i}(y)$, and this coincides with
the rank of the $\left\lvert X\right\rvert\times\left\lvert Y\right\rvert$
matrix described by $F$.

A common way to define the rank of a function $F\colon X\times Y\times
Z\to{\mathbb{F}}$ is _tensor rank_ : $\operatorname{tensor-rank}(F)$ is the
smallest $k$ for which we can write

$F(x,y,z)=\sum_{i=1}^{k}f_{i}(x)g_{i}(y)h_{i}(z).$

In this paper, we make use of another notion of rank which we call _slice
rank_ : $\operatorname{slice-rank}(F)$ is the smallest $k$ for which we can
write

$F(x,y,z)=\sum_{i=1}^{a}f_{i}(x,y)g_{i}(z)+\sum_{i=a+1}^{b}f_{i}(x,z)g_{i}(y)+\sum_{i=b+1}^{k}f_{i}(y,z)g_{i}(x).$
(4.1)

As far as we know, this notion of rank was first used by Tao in [22]; here we
take this study a bit further by establishing some basic properties of slice
rank (Section 4.1) and connections to GIT (Section 4.2).

Since any sum $\sum_{i}f_{i}(x)g_{i}(y)h_{i}(z)$ automatically fits the form
(4.1), we always have

$\operatorname{slice-rank}(F)\leq\operatorname{tensor-
rank}(F)\leq\left\lvert\operatorname{support}(F)\right\rvert.$

Similarly, directly from the definition (4.1) we immediately conclude that

$\operatorname{slice-rank}(F)\leq\min(\left\lvert X\right\rvert,\left\lvert
Y\right\rvert,\left\lvert Z\right\rvert)$ (4.2)

and

$\operatorname{tensor-rank}(F)\leq\operatorname{slice-
rank}(F)\cdot\max(\left\lvert X\right\rvert,\left\lvert
Y\right\rvert,\left\lvert Z\right\rvert).$ (4.3)

######  Remark 4.1.

Slice rank and tensor rank can be quite different. For example, if
$\left\lvert X\right\rvert=N$ the function $F\colon X\times X\times
X\to{\mathbb{F}}$ given by $F(x,y,z)=\delta_{x,y}$ has $\operatorname{slice-
rank}(F)=1$ while $\operatorname{tensor-rank}(F)=N$. (Note that this is the
largest possible separation by (4.3).)

As another example of the difference between slice and tensor rank, every
function $F\colon X\times X\times X\to{\mathbb{F}}$ has slice rank at most $N$
(and this bound is sharp; see Lemma 4.7 or [22, Lemma 1]). However, tensor
rank can be much larger: the tensor rank of a generic222That is, the set of
functions $F$ with this tensor rank is non-empty and Zariski-open. $F$ is
$\lceil\frac{N^{3}}{3N-2}\rceil\approx N^{2}/3$ if $N\neq 3$ and
${\mathbb{F}}$ is algebraically closed [16].

Given functions $F\colon X^{\prime}\times Y^{\prime}\times
Z^{\prime}\to{\mathbb{F}}$ and $G\colon X^{\prime\prime}\times
Y^{\prime\prime}\times Z^{\prime\prime}\to{\mathbb{F}}$, set
$X=X^{\prime}\times X^{\prime\prime}$, $Y=Y^{\prime}\times Y^{\prime\prime}$,
and $Z=Z^{\prime}\times Z^{\prime\prime}$, and let $F\otimes G$ denote the
function $F\otimes G\colon X\times Y\times Z\to{\mathbb{F}}$ given by

$\big{(}(x^{\prime},x^{\prime\prime}),(y^{\prime},y^{\prime\prime}),(z^{\prime},z^{\prime\prime})\big{)}\mapsto
F(x^{\prime},y^{\prime},z^{\prime})G(x^{\prime\prime},y^{\prime\prime},z^{\prime\prime}).$

The inequality $\operatorname{tensor-rank}(F\otimes
G)\leq\operatorname{tensor-rank}(F)\cdot\operatorname{tensor-rank}(G)$ is
well-known; it has the following two variants, which bound the slice rank of a
tensor product:

######  Proposition 4.2.

For any $F,G$ as above, $\operatorname{slice-rank}(F\otimes
G)\leq\operatorname{slice-rank}(F)\cdot\operatorname{tensor-rank}(G)$ and
$\operatorname{slice-rank}(F\otimes G)\leq\operatorname{slice-
rank}(F)\cdot\max(\left\lvert X^{\prime\prime}\right\rvert,\left\lvert
Y^{\prime\prime}\right\rvert,\left\lvert Z^{\prime\prime}\right\rvert)$.

###### Proof.

Set $k=\operatorname{slice-rank}(F)$ and choose functions $f^{\prime}_{i}$ and
$g^{\prime}_{i}$ for $1\leq i\leq k$ as in (4.1). Similarly, set
$\ell=\operatorname{tensor-rank}(G)$ and write
$G(x^{\prime\prime},y^{\prime\prime},z^{\prime\prime})=\sum_{j=1}^{\ell}\alpha_{j}(x^{\prime\prime})\beta_{j}(y^{\prime\prime})\gamma_{j}(z^{\prime\prime})$.
If we then define

$\displaystyle f_{ij}(x,y)$ $\displaystyle\coloneq
f^{\prime}_{i}(x^{\prime},y^{\prime})\alpha_{j}(x^{\prime\prime})\beta_{j}(y^{\prime\prime}),\qquad
g_{ij}(z)\coloneq g_{i}(z^{\prime})\gamma_{j}(z^{\prime\prime})$
$\displaystyle\text{for }1\leq i\leq a,$ $\displaystyle\ 1\leq j\leq\ell,$
$\displaystyle f_{ij}(x,z)$ $\displaystyle\coloneq
f^{\prime}_{i}(x^{\prime},z^{\prime})\alpha_{j}(x^{\prime\prime})\gamma_{j}(z^{\prime\prime}),\qquad
g_{ij}(y)\coloneq g_{i}(y^{\prime})\beta_{j}(y^{\prime\prime})$
$\displaystyle\text{for }a<i\leq b,$ $\displaystyle\ 1\leq j\leq\ell,\text{
and}$ $\displaystyle f_{ij}(y,z)$ $\displaystyle\coloneq
f^{\prime}_{i}(y^{\prime},z^{\prime})\beta_{j}(y^{\prime\prime})\gamma_{j}(z^{\prime\prime}),\qquad
g_{ij}(x)\coloneq g_{i}(x^{\prime})\alpha_{j}(x^{\prime\prime})$
$\displaystyle\text{for }b<i\leq k,$ $\displaystyle\ 1\leq j\leq\ell,$

then

$(F\otimes G)(x,y,z)=\sum_{\begin{subarray}{c}1\leq i\leq a\\\ 1\leq
j\leq\ell\end{subarray}}f_{ij}(x,y)g_{ij}(z)+\sum_{\begin{subarray}{c}a<i\leq
b\\\ 1\leq
j\leq\ell\end{subarray}}f_{ij}(x,z)g_{ij}(y)+\sum_{\begin{subarray}{c}b<i\leq
k\\\ 1\leq j\leq\ell\end{subarray}}f_{ij}(y,z)g_{ij}(x).$

This demonstrates that $\operatorname{slice-rank}(F\otimes G)\leq k\cdot\ell$,
which verifies the first claim. For the second claim, we instead define

$\displaystyle f_{i\zeta}(x,y)$ $\displaystyle\coloneq
f^{\prime}_{i}(x^{\prime},y^{\prime})G(x^{\prime\prime},y^{\prime\prime},\zeta),\qquad\,\,g_{i\zeta}(z)\coloneq
g_{i}(z^{\prime})\delta_{\zeta}(z^{\prime\prime})$ $\displaystyle\text{for
}1\leq i\leq a,$ $\displaystyle\ \zeta\in Z^{\prime\prime},$ $\displaystyle
f_{i\psi}(x,z)$ $\displaystyle\coloneq
f^{\prime}_{i}(x^{\prime},z^{\prime})G(x^{\prime\prime},\psi,z^{\prime\prime}),\qquad
g_{i\psi}(y)\coloneq g_{i}(y^{\prime})\delta_{\psi}(y^{\prime\prime})$
$\displaystyle\text{for }a<i\leq b,$ $\displaystyle\ \psi\in
Y^{\prime\prime},\text{ and}$ $\displaystyle f_{i\xi}(y,z)$
$\displaystyle\coloneq
f^{\prime}_{i}(y^{\prime},z^{\prime})G(\xi,y^{\prime\prime},z^{\prime\prime}),\qquad\
g_{i\xi}(x)\coloneq g_{i}(x^{\prime})\delta_{\xi}(x^{\prime\prime})$
$\displaystyle\text{for }b<i\leq k,$ $\displaystyle\ \xi\in X^{\prime\prime},$

so that

$(F\otimes G)(x,y,z)=\sum_{\begin{subarray}{c}1\leq i\leq a\\\ \zeta\in
Z^{\prime\prime}\end{subarray}}f_{i\zeta}(x,y)g_{i\zeta}(z)+\sum_{\begin{subarray}{c}a<i\leq
b\\\ \psi\in
Y^{\prime\prime}\end{subarray}}f_{i\psi}(x,z)g_{i\psi}(y)+\sum_{\begin{subarray}{c}b<i\leq
k\\\ \xi\in X^{\prime\prime}\end{subarray}}f_{i\xi}(y,z)g_{i\xi}(x).$

This shows that $\operatorname{slice-rank}(F\otimes G)\leq
k\cdot\max(\left\lvert X^{\prime\prime}\right\rvert,\left\lvert
Y^{\prime\prime}\right\rvert,\left\lvert Z^{\prime\prime}\right\rvert)$, which
verifies the second claim. ∎

###  4.2 Unstable tensors and slice rank

In this section we relate slice rank to the notion of an unstable tensor from
geometric invariant theory. We show that functions with low slice rank are
unstable and prove that a quantitative bound on instability yields a bound on
slice rank of tensor powers.

######  Definition 4.3.

A function $F\colon X\times Y\times Z\to{\mathbb{F}}$ is _unstable_ if there
exist

  1. 1.

a basis $\\{f_{a}\\}$ for the functions $X\to{\mathbb{F}}$, and similarly
bases $\\{g_{b}\colon Y\to{\mathbb{F}}\\}$ and $\\{h_{c}\colon
Z\to{\mathbb{F}}\\}$,

  2. 2.

weights $u_{a},v_{b},w_{c}\in{\mathbb{R}}$ with arithmetic means
$u_{\operatorname{avg}},v_{\operatorname{avg}},w_{\operatorname{avg}}$, and

  3. 3.

coefficients $r_{a,b,c}\in{\mathbb{F}}$ such that

$F(x,y,z)=\sum_{\begin{subarray}{c}u_{a}+v_{b}+w_{c}<\\\
u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}\end{subarray}}r_{a,b,c}f_{a}(x)g_{b}(y)h_{c}(z).$

This terminology comes from geometric invariant theory (when ${\mathbb{F}}$ is
algebraically closed). Consider the action of the group
$G=\operatorname{SL}_{\left\lvert
X\right\rvert}\times\operatorname{SL}_{\left\lvert
Y\right\rvert}\times\operatorname{SL}_{\left\lvert Z\right\rvert}$ on the
vector space of functions $F\colon X\times Y\times Z\to{\mathbb{F}}$. A
function $F$ is said to be unstable in the sense of GIT if the zero function
is contained in the Zariski closure of the $G$-orbit of $F$, or equivalently
if every $G$-invariant homogeneous polynomial of positive degree vanishes on
$F$. The Hilbert–Mumford criterion [17, §1] is a concrete condition for a
function to be unstable: it says that a function $F$ is unstable in the sense
of GIT if and only if there exist functions and weights making $F$ unstable
according to Definition 4.3.

However, geometric invariant theory only deals with algebraically closed
fields ${\mathbb{F}}$, which is why for general ${\mathbb{F}}$ we take
Definition 4.3 as the _definition_ of unstable. To make our bounds explicit we
will also need to introduce a _quantitative_ version of this condition.

######  Definition 4.4.

The _instability_ of a function $F\colon X\times Y\times Z\to{\mathbb{F}}$ is
the supremum of all $\varepsilon\geq 0$ such that there exist bases
$f_{a},g_{b},h_{c}$, nontrivial weights $u_{a},v_{b},w_{c}\in{\mathbb{R}}$,
and coefficients $r_{a,b,c}\in{\mathbb{F}}$ such that

$F(x,y,z)=\sum_{u_{a}+v_{b}+w_{c}\leq R}r_{a,b,c}f_{a}(x)g_{b}(y)h_{c}(z)$
(4.4)

where

$R=(u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}})-\varepsilon(u_{\max}-u_{\min}+v_{\max}-v_{\min}+w_{\max}-w_{\min}).$
(4.5)

By “nontrivial weights” we mean that the weights $u_{a}$, $v_{b}$, and $w_{c}$
should not all be constant (since in that case our definition of $R$ becomes
degenerate). Note that a function $F$ is unstable if and only if
$\operatorname{instability}(F)>0$. By convention, if for some $F$ there is no
nonnegative $\varepsilon$ satisfying the hypotheses of the definition, we
define $\operatorname{instability}(F)=-\infty$. For readers familiar with the
terminology of GIT, we remark that (assuming ${\mathbb{F}}$ is algebraically
closed) the function $F$ is _semi-stable_ if and only if
$\operatorname{instability}(F)\in\\{-\infty,0\\}$, and $F$ is _stable_ if and
only if $\operatorname{instability}(F)=-\infty$. For consistency with this
terminology, we are careful to use the term “not unstable” where appropriate
(which is not the same, in GIT, as “stable”).

######  Remark 4.5 (Notes on the definition of instability).

x x

  1. 1.

Translating all the weights $u_{a}$ (or all the $v_{b}$, or all the $w_{c}$)
by a constant translates the quantity $R$ of (4.5) by the same amount, so the
condition $u_{a}+v_{b}+w_{c}\leq R$ is invariant under translation. Therefore
if we like we may assume that
$u_{\operatorname{avg}}=v_{\operatorname{avg}}=w_{\operatorname{avg}}=0$, or
that $u_{\min}=v_{\min}=w_{\min}=0$, without loss of generality. Similarly,
scaling all of the weights $u_{a}$, $v_{b}$, $w_{c}$ by the same constant does
not change the definition of instability nor the value of
$\operatorname{instability}(F)$.

  2. 2.

It does not matter whether we require the weights to lie in ${\mathbb{R}}$,
${\mathbb{Q}}$, or ${\mathbb{Z}}$. Indeed, the supremum defining instability
could be taken over rational $\varepsilon\geq 0$ without affecting the
definition. For any given rational $\varepsilon$, the inequalities relating
the $u_{a}$, $v_{b}$, and $w_{c}$ are a system of homogeneous linear
inequalities with rational coefficients, so they have rational solutions if
and only if they have real solutions. We can then transform rational weights
to integer weights by scaling. (In particular, this justifies our earlier
claim that the Hilbert–Mumford criterion is equivalent to Definition 4.3 when
over an algebraically closed field; the usual statement of the Hilbert–Mumford
criterion would require integer weights with
$u_{\operatorname{avg}}=v_{\operatorname{avg}}=w_{\operatorname{avg}}=0$.)

  3. 3.

The definition of instability would be the same if the $f_{a}$, $g_{b}$, and
$h_{c}$ were arbitrary functions not required to form bases, as long as
$\left\lvert A\right\rvert\leq\left\lvert X\right\rvert$, $\left\lvert
B\right\rvert\leq\left\lvert Y\right\rvert$, and $\left\lvert
C\right\rvert\leq\left\lvert Z\right\rvert$, where $A$, $B$, $C$ denote index
sets for the $f_{a}$, $g_{b}$, $h_{c}$, respectively. Indeed, if one function
$f_{a}$ is a linear combination of previous functions $f_{a^{\prime}}$ with
$u_{a^{\prime}}\leq u_{a}$, then the terms $f_{a}\otimes g_{b}\otimes h_{c}$
appearing in (4.4) can be replaced with a linear combination of terms
$f_{a^{\prime}}\otimes g_{b}\otimes h_{c}$, still satisfying
$u_{a^{\prime}}+v_{b}+w_{c}\leq u_{a}+v_{b}+w_{c}\leq R$. Repeating this, we
may assume that the set of functions $\\{f_{a}\\}_{a\in A^{\prime}}$ (with
$A^{\prime}\subseteq A$) appearing is linearly independent. Then extend this
set to a basis arbitrarily, giving $\left\lvert X\right\rvert-\left\lvert
A\right\rvert$ of these new functions the weight $u_{\operatorname{avg}}$ and
giving $\left\lvert A\right\rvert-\left\lvert A^{\prime}\right\rvert$ of them
the weights $\\{u_{a}\\}_{a\in A\setminus A^{\prime}}$. The other tensor
factors are handled similarly.

Recall from (4.2) that any function $F\colon X\times Y\times Z\to{\mathbb{F}}$
has $\operatorname{slice-rank}(F)\leq\min(\left\lvert
X\right\rvert,\left\lvert Y\right\rvert,\left\lvert Z\right\rvert)$. It turns
out that there is a close relationship between $F$ being unstable and this
inequality being _strict_. More precisely, the latter implies the former
(Theorem 4.6), and the former implies that the latter holds for sufficiently
large tensor powers when $\left\lvert X\right\rvert=\left\lvert
Y\right\rvert=\left\lvert Z\right\rvert$ (Theorem 4.10).

######  Theorem 4.6.

If $\operatorname{slice-rank}(F)<\min(\left\lvert X\right\rvert,\left\lvert
Y\right\rvert,\left\lvert Z\right\rvert)$, then $F$ is unstable.

###### Proof.

Given an arbitrary $F$, choose a decomposition

$F(x,y,z)=\sum_{i=1}^{p}\alpha_{i}(y,z)f_{i}(x)+\sum_{j=1}^{q}\beta_{j}(x,z)g_{j}(y)+\sum_{k=1}^{r}\gamma_{k}(x,y)h_{k}(z)$
(4.6)

with $p+q+r=\operatorname{slice-rank}(F)$. Note that this implies that the $p$
functions $f_{1},\dots,f_{p}$ are linearly independent (otherwise we could
find a smaller decomposition of $F$), so extend them to a basis
$f_{1},\dots,f_{\left\lvert X\right\rvert}$ for the functions
$X\to{\mathbb{F}}$. Do the same for the other factors, and define weights by

$u_{i}=\begin{cases}-1&\text{for }1\leq i\leq p,\\\ 0&\text{for
}p<i\leq\left\lvert X\right\rvert,\end{cases}\quad
v_{j}=\begin{cases}-1&\text{for }1\leq j\leq q,\\\ 0&\text{for
}q<j\leq\left\lvert Y\right\rvert,\end{cases}\quad
w_{k}=\begin{cases}-1&\text{for }1\leq k\leq r,\\\ 0&\text{for
}r<k\leq\left\lvert Z\right\rvert.\end{cases}$

Expanding $\alpha_{i}(y,z)$ as a linear combination of $g_{j}(y)h_{k}(z)$ and
so on, the decomposition (4.6) says that $F$ is a linear combination of
functions $f_{i}\cdot g_{j}\cdot h_{k}$ where at least _one_ of $1\leq i\leq
p$, $1\leq j\leq q$, or $1\leq k\leq r$ holds. From the definition of our
weight functions, these are precisely the cases when
$u_{i}+v_{j}+w_{k}\leq-1$.

On the other hand $u_{\operatorname{avg}}=-\frac{p}{\left\lvert
X\right\rvert}$, $v_{\operatorname{avg}}=-\frac{q}{\left\lvert
Y\right\rvert}$, and $w_{\operatorname{avg}}=-\frac{r}{\left\lvert
Z\right\rvert}$, from which it follows that

$u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}=-\frac{p}{\left\lvert
X\right\rvert}-\frac{q}{\left\lvert Y\right\rvert}-\frac{r}{\left\lvert
Z\right\rvert}\geq-\frac{p+q+r}{\min(\left\lvert X\right\rvert,\left\lvert
Y\right\rvert,\left\lvert Z\right\rvert)}=-\frac{\operatorname{slice-
rank}(F)}{\min(\left\lvert X\right\rvert,\left\lvert Y\right\rvert,\left\lvert
Z\right\rvert)}.$

Our hypothesis that $\operatorname{slice-rank}(F)<\min(\left\lvert
X\right\rvert,\left\lvert Y\right\rvert,\left\lvert Z\right\rvert)$ thus
guarantees that these weights satisfy
$u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}>-1$. In
this case, $F$ is a linear combination of functions $f_{i}\cdot g_{j}\cdot
h_{k}$ where
$u_{i}+v_{j}+w_{k}\leq-1<u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}$,
so $F$ is unstable. ∎

Theorem 4.6 implies that any tensor $F$ that is not unstable has

$\operatorname{slice-rank}(F)=\min(\left\lvert X\right\rvert,\left\lvert
Y\right\rvert,\left\lvert Z\right\rvert).$

This lets us compute the slice rank of any diagonal. Say that a function
$F\colon X\times Y\times Z\to{\mathbb{F}}$ is a _diagonal_ if its support
$\\{(x,y,z):F(x,y,z)\neq 0\\}$ is a perfect matching on $X$, $Y$, and $Z$.
Note that this implies $\left\lvert X\right\rvert=\left\lvert
Y\right\rvert=\left\lvert
Z\right\rvert=\left\lvert\operatorname{support}(F)\right\rvert$, and that we
require all the diagonal entries in $F$ (i.e., those corresponding to the
perfect matching) to be nonzero.

The following lemma was introduced to great effect by Tao [22, Lemma 1]. We
first reproduce Tao’s elementary proof for completeness, and then include a
second proof inspired by the GIT perspective.

######  Lemma 4.7.

If $F\colon X\times Y\times Z\to{\mathbb{F}}$ is a diagonal, then

$\operatorname{slice-rank}(F)=\operatorname{tensor-rank}(F)=\left\lvert
X\right\rvert.$

###### Tao’s proof from [22].

Suppose that $\operatorname{slice-rank}(F)<|X|$. Then there exist $k<|X|$ and
functions $f_{i},g_{i}$ such that

$F(x,y,z)=\sum_{i=1}^{j}f_{i}(x)g_{i}(y,z)+\sum_{i=j+1}^{\ell}f_{i}(y)g_{i}(z,x)+\sum_{i=\ell+1}^{k}f_{i}(z)g_{i}(x,y).$
(4.7)

Without loss of generality suppose that $j>0$, and let

$V=\left\\{h\colon X\rightarrow\mathbb{F}:\ \sum_{x\in X}f_{i}(x)h(x)=0\text{
for all }1\leq i\leq j\right\\}.$

This vector space has dimension at least $|X|-j$. Let $u\in V$ have maximal
support, and set $\Sigma=\left\\{x\in X:\ u(x)\neq 0\right\\}$. Then
$|\Sigma|\geq\dim V\geq|X|-j,$ since otherwise there exists nonzero $r\in V$
vanishing on $\Sigma,$ and the function $u+r$ would have a larger support than
$u.$ Multiply both sides of (4.7) by $u(x)$ and sum over $x$ to reduce from a
tensor to a matrix. As $u\in V$ is orthogonal to $f_{i}$ for $i=1,\dots,j$,
the right side of (4.7) becomes

$\sum_{i=j+1}^{\ell}f_{i}(y)\left(\sum_{x\in
X}u(x)g_{i}(z,x)\right)+\sum_{i=\ell+1}^{k}f_{i}(z)\left(\sum_{x\in
X}u(x)g_{i}(x,y)\right),$

which is a function of rank at most $k-j<|X|-j.$ Since the support of
$F(x,y,z)$ is precisely given by a perfect matching, $\sum_{x\in
X}u(x)F(x,y,z)$ will be a function with rank equal to
$|\operatorname{support}(u)|\geq|X|-j.$ Thus we have a contradiction, and it
follows that $\operatorname{slice-rank}(F)=|X|.$ ∎

We remark that Tao’s proof is inductive, and extends to higher-order tensors
as well [22]. The next proof of Lemma 4.7 uses the geometric invariant theory
perspective on slice rank.

###### Proof of Lemma 4.7.

By Theorem 4.6, it suffices to prove that a diagonal is not unstable. It will
be convenient to use dual bases to compute coefficients. Given bases
$f_{a},g_{b},h_{c}$ as in Definition 4.3, consider the dual bases
$f_{a}^{\prime},g_{b}^{\prime},h_{c}^{\prime}$; in other words,

$\sum_{x\in X}f_{a}(x)f^{\prime}_{a^{\prime}}(x)=\begin{cases}1&\text{if
$a=a^{\prime}$, and}\\\ 0&\text{otherwise,}\end{cases}$

and the same holds for $g_{b},g_{b}^{\prime}$ (summing over $Y$) and
$h_{c},h_{c}^{\prime}$ (summing over $Z$). Our proof will depend on the
following two observations.

First, the condition that

$F(x,y,z)=\sum_{\begin{subarray}{c}u_{a}+v_{b}+w_{c}<\\\
u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}\end{subarray}}r_{a,b,c}f_{a}(x)g_{b}(y)h_{c}(z)$

is equivalent to the condition that

$\sum_{x,y,z}F(x,y,z)f_{a}^{\prime}(x)g_{b}^{\prime}(y)h_{c}^{\prime}(z)\neq
0\quad\implies\quad
u_{a}+v_{b}+w_{c}<u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}},$
(4.8)

since that sum is precisely the coefficient $r_{a,b,c}$.

Second, the condition (4.8) is invariant under the change of basis that
replaces $f_{a_{2}}^{\prime}$ by $\alpha
f_{a_{1}}^{\prime}+f_{a_{2}}^{\prime}$ as long as $u_{a_{1}}\geq u_{a_{2}}$.
For if

$\sum_{x,y,z}F(x,y,z)\big{(}\alpha
f_{a_{1}}^{\prime}(x)+f_{a_{2}}^{\prime}(x)\big{)}g_{b}^{\prime}(y)h_{c}^{\prime}(z)\neq
0,$

then either
$\sum_{x,y,z}F(x,y,z)f_{a_{1}}^{\prime}(x)g_{b}^{\prime}(y)h_{c}^{\prime}(z)\neq
0$ or
$\sum_{x,y,z}F(x,y,z)f_{a_{2}}^{\prime}(x)g_{b}^{\prime}(y)h_{c}^{\prime}(z)\neq
0$, so either $u_{a_{1}}+v_{b}+w_{c}$ or $u_{a_{2}}+v_{b}+w_{c}$ is less than
$u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}$. Thus
in either case $u_{a_{2}}+v_{b}+w_{c}$ is less than
$u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}$ as it
is at most $u_{a_{1}}+v_{b}+w_{c}$. The same is true for the $g_{b}$ and
$h_{c}$.

We can now proceed to the proof. For the sake of contradiction, assume that
$F$ is a diagonal and unstable. Without loss of generality, assume that
$X=Y=Z=[n]$ and that the support of $F$ is $\\{(i,i,i):i\in[n]\\}$.

View the functions $f_{a}^{\prime}\colon[n]\to{\mathbb{F}}$ as $n$-dimensional
vectors. Using changes of variables of the aforementioned form, we may perform
Gaussian elimination until no two $f_{a}^{\prime}$ have their first nonzero
entries in the same position. In that case, each element of $[n]$ is the
position of the first nonzero entry of some $f_{a}^{\prime}$, so we may index
the $f_{a}^{\prime}$ by these positions. Do the same for the $g_{b}^{\prime}$,
but for the $h_{c}^{\prime}$, perform Gaussian elimination so that the _last_
nonzero entries have distinct positions, and index the $h_{c}^{\prime}$ by
these positions.

Because $F$ is diagonal,

$\sum_{x,y,z}F(x,y,z)f_{a}^{\prime}(x)g_{b}^{\prime}(y)h_{c}^{\prime}(z)=\sum_{x}F(x,x,x)f_{a}^{\prime}(x)g_{b}^{\prime}(x)h_{c}^{\prime}(x)$

and $F(x,x,x)\neq 0$. Now for each index $i\in[n]$, since $i$ is the position
of the first nonzero entry of $f_{i}^{\prime}$ and $g_{i}^{\prime}$ and the
last nonzero entry of $h_{i}^{\prime}$,

$f_{i}^{\prime}(x)g_{i}^{\prime}(x)h_{i}^{\prime}(x)=\begin{cases}f_{i}^{\prime}(i)g_{i}^{\prime}(i)h_{i}^{\prime}(i)\neq
0&\text{if }x=i,\text{ and }\\\ 0&\text{otherwise.}\end{cases}$

This means

$\sum_{x}F(x,x,x)f_{i}^{\prime}(x)g_{i}^{\prime}(x)h_{i}^{\prime}(x)=F(i,i,i)f_{i}^{\prime}(i)g_{i}^{\prime}(i)h_{i}^{\prime}(i)\neq
0,$

which implies
$u_{i}+v_{i}+w_{i}<u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}$.
Summing over $i$, we have

$\sum_{i=1}^{n}u_{i}+\sum_{i=1}^{n}v_{i}+\sum_{i=1}^{n}w_{i}<nu_{\operatorname{avg}}+nv_{\operatorname{avg}}+nw_{\operatorname{avg}}=\sum_{i=1}^{n}u_{i}+\sum_{i=1}^{n}v_{i}+\sum_{i=1}^{n}w_{i},$

which is a contradiction, so $F$ is not unstable. ∎

Lemma 4.7 has the following important consequence. If $H$ is any abelian group
and ${\mathbb{F}}$ is any field, let $D_{H}\colon H\times H\times
H\to{\mathbb{F}}$ be the tensor encoding the group structure (corresponding to
multiplication in the group algebra ${\mathbb{F}}H$), defined by

$D_{H}(x,y,z)=\begin{cases}1&\text{if }x+y+z=0,\text{ and}\\\ 0&\text{if
}x+y+z\neq 0.\end{cases}$

######  Proposition 4.8.

If $M$ is a tricolored sum-free set in an abelian group $H$, then

${\left\lvert M\right\rvert\leq\operatorname{slice-rank}(D_{H})}.$

###### Proof.

When we restrict a function $F\colon X\times Y\times Z\to{\mathbb{F}}$ to
subsets $X_{0},Y_{0},Z_{0}$, we can also restrict any decomposition as in
(4.1), showing that

$\operatorname{slice-rank}(F|_{X_{0}\times Y_{0}\times
Z_{0}})\leq\operatorname{slice-rank}(F).$

A set $M\subseteq S\times T\times U$ on subsets $S,T,U\subseteq H$ is a
tricolored sum-free set if and only if the restriction $D_{H}|_{S\times
T\times U}$ is a diagonal; if it is, Lemma 4.7 implies that

$\left\lvert M\right\rvert=\operatorname{slice-rank}(D_{H}|_{S\times T\times
U})\leq\operatorname{slice-rank}(D_{H}).\qed$

This means we can bound the size of tricolored sum-free sets in an abelian
group $H$ by bounding the slice rank of $D_{H}$ from above.

######  Remark 4.9.

With the notion of slice rank in hand, it is natural to wonder whether upper
bounds on slice rank could be applied directly to matrix multiplication to get
upper bounds on its tensor rank. Indeed, since $\operatorname{tensor-
rank}(\langle n,n,n\rangle)\leq n^{2}\cdot\operatorname{slice-rank}(\langle
n,n,n\rangle)$ by (4.3), upper bounds of $O(n^{\delta})$ on the slice rank of
$n\times n$ matrix multiplication would imply $\omega\leq 2+\delta$. However,
no nontrivial upper bounds on $\omega$ can be achieved this way: it is known
that the matrix multiplication tensor is not unstable [3, Theorem 5.2], so
Theorem 4.6 implies that $\operatorname{slice-rank}(\langle
n,n,n\rangle)=n^{2}$. (However, the topic of the slice rank of matrix
multiplication itself is orthogonal to the main results of this paper.)

###  4.3 Upper bounds on slice rank

The following result gives us upper bounds on slice rank.

######  Theorem 4.10.

If $F$ is unstable, then for any $n\geq 1$,

$\operatorname{slice-rank}(F^{\otimes n})\leq(\left\lvert
X\right\rvert^{n}+\left\lvert Y\right\rvert^{n}+\left\lvert
Z\right\rvert^{n})e^{-2n\operatorname{instability}(F)^{2}}.$

We remark that in the most common case when $\left\lvert
X\right\rvert=\left\lvert Y\right\rvert=\left\lvert Z\right\rvert$, this bound
is always nontrivial for sufficiently large $n$. However if the sets have
unequal sizes, this only improves on the trivial bound $\operatorname{slice-
rank}(F^{\otimes n})\leq\min(\left\lvert X\right\rvert^{n},\left\lvert
Y\right\rvert^{n},\left\lvert Z\right\rvert^{n})$ if
$\operatorname{instability}(F)$ is sufficiently large.

###### Proof.

It suffices to prove for all $\varepsilon<\operatorname{instability}(F)$ that

$\operatorname{slice-rank}(F^{\otimes n})\leq(\left\lvert
X\right\rvert^{n}+\left\lvert Y\right\rvert^{n}+\left\lvert
Z\right\rvert^{n})e^{-2n\varepsilon^{2}}.$

Given such an $\varepsilon$, we can choose functions $f_{a},g_{b},h_{c}$,
weights $u_{a},v_{b},w_{c}$, and coefficients $r_{a,b,c}$ as in Definition 4.4
indexed by $a\in A$, $b\in B$, and $c\in C$ such that

$F(x,y,z)=\sum_{u_{a}+v_{b}+w_{c}\leq R}r_{a,b,c}f_{a}(x)g_{b}(y)h_{c}(z)$

with $R$ as in (4.5). Assume without loss of generality that
$u_{\min}=v_{\min}=w_{\min}=0$, and let us define bounds
$u_{\operatorname{bd}}=u_{\operatorname{avg}}-\varepsilon u_{\max}$, and
similarly for $v_{\operatorname{bd}}$ and $w_{\operatorname{bd}}$, so that

$R=u_{\operatorname{avg}}+v_{\operatorname{avg}}+w_{\operatorname{avg}}-\varepsilon(u_{\max}+v_{\max}+w_{\max})=u_{\operatorname{bd}}+v_{\operatorname{bd}}+w_{\operatorname{bd}}.$

For $\mathbf{a}\in A^{n}$ and $\mathbf{x}\in X^{n}$, define
$f_{\mathbf{a}}(\mathbf{x})=\prod_{i=1}^{n}f_{a_{i}}(x_{i})$ and
$u_{\mathbf{a}}=u_{a_{1}}+\cdots+u_{a_{n}}\in{\mathbb{R}}$; similarly define
$g_{\mathbf{b}}(\mathbf{y})$, $v_{\mathbf{b}}$, $h_{\mathbf{c}}(\mathbf{z})$,
$w_{\mathbf{c}}$, and
$r_{\mathbf{a},\mathbf{b},\mathbf{c}}=\prod_{i=1}^{n}r_{a_{i},b_{i},c_{i}}$.
Then

$F^{\otimes
n}(\mathbf{x},\mathbf{y},\mathbf{z})=\sum_{(\mathbf{a},\mathbf{b},\mathbf{c})}\prod_{i=1}^{n}r_{a_{i},b_{i},c_{i}}f_{a_{i}}(x_{i})g_{b_{i}}(y_{i})h_{c_{i}}(z_{i})=\sum_{(\mathbf{a},\mathbf{b},\mathbf{c})}r_{\mathbf{a},\mathbf{b},\mathbf{c}}f_{\mathbf{a}}(\mathbf{x})g_{\mathbf{b}}(\mathbf{y})h_{\mathbf{c}}(\mathbf{z}),$

where the sum is over triples $(\mathbf{a},\mathbf{b},\mathbf{c})$ of tuples
$\mathbf{a}\in A^{n},\mathbf{b}\in B^{n},\mathbf{c}\in C^{n}$ satisfying the
condition $u_{a_{i}}+v_{b_{i}}+w_{c_{i}}\leq
R=u_{\operatorname{bd}}+v_{\operatorname{bd}}+w_{\operatorname{bd}}$ for each
$i=1,\dots,n$. This condition implies
$u_{\mathbf{a}}+v_{\mathbf{b}}+w_{\mathbf{c}}\leq
nR=n(u_{\operatorname{bd}}+v_{\operatorname{bd}}+w_{\operatorname{bd}})$, so
each such triple must satisfy at least one of the inequalities
$u_{\mathbf{a}}\leq nu_{\operatorname{bd}}$, $v_{\mathbf{b}}\leq
nv_{\operatorname{bd}}$, or $w_{\mathbf{c}}\leq nw_{\operatorname{bd}}$.
Therefore we can collect terms above to write

$F^{\otimes n}(\mathbf{x},\mathbf{y},\mathbf{z})=\sum_{u_{\mathbf{a}}\leq
nu_{\operatorname{bd}}}f_{\mathbf{a}}(\mathbf{x})E_{\mathbf{a}}(\mathbf{y},\mathbf{z})+\sum_{v_{\mathbf{b}}\leq
nv_{\operatorname{bd}}}g_{\mathbf{b}}(\mathbf{y})E_{\mathbf{b}}(\mathbf{x},\mathbf{z})+\sum_{w_{\mathbf{c}}\leq
nw_{\operatorname{bd}}}h_{\mathbf{c}}(\mathbf{z})E_{\mathbf{c}}(\mathbf{x},\mathbf{y}).$

This decomposition exhibits a bound on the slice rank of $F^{\otimes n}$, so
all we need to do is estimate how many terms appear in these sums. The number
of tuples $\mathbf{a}\in A^{n}$ satisfying $u_{\mathbf{a}}\leq
nu_{\operatorname{bd}}=n(u_{\operatorname{avg}}-\varepsilon u_{\max})$ is a
classical large deviation estimate: $u_{\mathbf{a}}$ is the sum of i.i.d.
variables $u_{a_{i}}$ taking values in $[0,u_{\max}]$, and we are asking how
often this deviates on one side from the mean $nu_{\operatorname{avg}}$ by at
least $\varepsilon nu_{\max}$. Even without knowing anything about the
distribution of $u_{a}$, Hoeffding’s inequality [13, Theorem 1] states that
this proportion is bounded by $e^{-2n\varepsilon^{2}}$, so the number of such
tuples $\mathbf{a}\in A^{n}$ appearing in the first sum is at most
$\left\lvert A^{n}\right\rvert e^{-2n\varepsilon^{2}}=\left\lvert
X\right\rvert^{n}e^{-2n\varepsilon^{2}}$. The same bound applies to the other
two sums, so we conclude that $\operatorname{slice-rank}(F^{\otimes
n})\leq(\left\lvert X\right\rvert^{n}+\left\lvert
Y\right\rvert^{n}+\left\lvert Z\right\rvert^{n})e^{-2n\varepsilon^{2}}$. ∎

The bound in Theorem 4.10 can be improved if we have more information about
the distribution of the weights, by sharpening the large deviation estimate in
the last paragraph of the proof. (If $F$ is not symmetric between $x$, $y$,
and $z$, it may also be helpful to use different cutoffs for the different
variables.) One case is very common, so we single it out: we define the
_triangle rank_ $\operatorname{triangle-rank}(F)$ to be the smallest $k$ for
which there exist functions $f_{a}$, $g_{b}$, $h_{c}$ for
$a,b,c\in\\{0,\dots,k-1\\}$ such that

$F(x,y,z)=\sum_{a+b+c<k}r_{a,b,c}f_{a}(x)g_{b}(y)h_{c}(z).$ (4.9)

We remark that in contrast with the definition of instability, here we do not
require that the functions $f_{i}$ are linearly independent or form a basis.
However, it turns out we can assume this without affecting the triangle rank
by the same argument as Remark 4.5(3).

We will not use the following observation directly, but it provides a
representative example and was central to Ellenberg–Gijswijt’s results in
[11].

######  Observation 4.11.

For any function $P\colon{\mathbb{F}}_{p}\to{\mathbb{F}}_{p}$ with $p$ prime,
the function $F(x,y,z)=P(x+y+z)$ has triangle rank at most $p$.

###### Proof.

We can represent $P$ as a polynomial of degree less than $p$. Expanding
$P(x+y+z)$ and collecting terms expresses $F(x,y,z)=P(x+y+z)$ as a linear
combination of monomials $x^{a}y^{b}z^{c}$. Since $\deg P<p$, each monomial
that occurs satisfies $a+b+c<p$. ∎

To analyze the bounds on slice rank resulting from triangle rank, we will need
to bound the proportion of tuples $\mathbf{a}\in\\{0,\dots,m\\}^{n}$ with
$\sum_{i}a_{i}\leq\frac{1}{3}mn$. The bounds used in the proof of Theorem 4.10
would bound this proportion by $e^{-n/18}$, but in this case the rate function
can be analyzed more carefully, leading to the following definition. For $m>0$
and $\alpha\in(0,\frac{1}{2})$, let

$I(m,\alpha)\coloneq\sup_{\theta<0}\left(\alpha\theta-\log\left(\frac{1-e^{(1+1/m)\theta}}{(m+1)(1-e^{\theta/m})}\right)\right).$

######  Proposition 4.12.

The proportion of tuples $\mathbf{a}\in\\{0,\dots,m\\}^{n}$ satisfying
$\sum_{i}a_{i}\leq\alpha mn$ is at most $e^{-I(m,\alpha)n}$. Moreover, for
fixed $\alpha\in(0,\frac{1}{2})$ the function $I(m,\alpha)$ is positive, is
increasing in $m$, and converges to
$\sup_{\theta<0}\big{(}\alpha\theta-\log\big{(}\frac{e^{\theta-1}}{\theta}\big{)}\big{)}$
as $m\to\infty$.

We will prove this proposition below; although the first assertion in this
proposition is standard, we include the proof for completeness. Before moving
to the proof of the proposition, we show that bounds on the triangle rank lead
to bounds on the slice rank of tensor powers. In this case the relevant
proportion will be $\alpha=\frac{1}{3}$, so for $s>1$ let us define

$J(s)\coloneq
e^{-I(s-1,\frac{1}{3})}=\frac{1}{s}\inf_{0<x<1}\frac{1-x^{s}}{1-x}x^{-\frac{s-1}{3}}.$
(4.10)

(The latter expression is obtained from the definition of $I(s-1,\alpha)$ by
setting $x=e^{\theta/(s-1)}$.) We point out as a consequence of Proposition
4.12 that for all $s>1$ the function $J(s)$ is decreasing, satisfies $J(s)<1$,
and (with $z=e^{-\theta/3}$)

$\lim_{s\to\infty}J(s)=\inf_{z>1}\frac{z-z^{-2}}{3\log z}=0.8414\ldots.$
(4.11)

######  Proposition 4.13.

If $\left\lvert X\right\rvert=\left\lvert Y\right\rvert=\left\lvert
Z\right\rvert=k$ and $\operatorname{triangle-rank}(F)\leq k$, then not only is
$\operatorname{instability}(F)\geq\frac{1}{6}$, but moreover the slice rank of
$F^{\otimes n}$ is at most $3(kJ(k))^{n}$.

###### Proof.

We first check the first claim. Express $F$ as in (4.9) with the $f_{a}$,
$g_{b}$, and $h_{c}$ linearly independent. Set $u_{a}=a$ for all
$a=0,1,\dots,k-1$; if the $f_{a}$ are not a basis, extend them arbitrarily to
a basis and set $u_{a}=\frac{k-1}{2}=u_{\operatorname{avg}}$ for all $a\geq k$
(these terms will not play any role in the decomposition). Doing the same for
the other factors exhibits $F$ as a sum as in (4.4) with $R=k-1$. Since
$u_{\max}=v_{\max}=w_{\max}=R$ and
$u_{\operatorname{avg}}=v_{\operatorname{avg}}=w_{\operatorname{avg}}=\frac{R}{2}$,
solving for $\varepsilon$ gives $\varepsilon=\frac{1}{6}$.

To bound the slice rank of $F^{\otimes n}$, simply follow the proof of Theorem
4.10 up until the last paragraph. The relevant estimate in this case is the
number of tuples $\mathbf{a}\in\\{0,\dots,k-1\\}^{n}$ with
$\sum_{i}a_{i}\leq\frac{1}{3}(k-1)n$. In place of the general bound of
$k^{n}e^{-n/18}$ obtained there, substitute the bound of
$k^{n}e^{-I(k-1,\frac{1}{3})n}=k^{n}J(k)^{n}$ from Proposition 4.12 to
conclude that $\operatorname{slice-rank}(F^{\otimes n})\leq 3(kJ(k))^{n}$. ∎

###### Proof of Proposition 4.12.

After dividing everything by $m$, the first claim in the proposition states
that if $X_{1},\dots,X_{n}$ are independent copies of a random variable $X$
uniformly distributed on the $m+1$ values
$\\{\frac{0}{m},\frac{1}{m},\dots,\frac{m}{m}\\}$, then
$\Pr\big{(}\sum_{i}X_{i}\leq\alpha n\big{)}\leq e^{-I(m,\alpha)n}$. For any
$\theta<0$, applying the order-reversing transformation $x\mapsto e^{\theta
x}$ shows that $\Pr\big{(}\sum_{i}X_{i}\leq\alpha
n\big{)}=\Pr\big{(}e^{\theta\sum_{i}X_{i}}\geq e^{\alpha n\theta}\big{)}$. By
Markov’s inequality, the latter is at most $e^{-\alpha
n\theta}\mathbb{E}\big{(}e^{\theta\sum_{i}X_{i}}\big{)}=\big{(}e^{-\alpha\theta}\mathbb{E}\big{(}e^{\theta
X}\big{)}\big{)}^{n}$. Setting $q=e^{\theta/m}$, we have
$\mathbb{E}\big{(}e^{\theta
X}\big{)}=(1+q+\cdots+q^{m})/(m+1)=\frac{1-q^{m+1}}{1-q}\cdot\frac{1}{m+1}$,
and this concludes the proof of the first claim.

For the remaining claims, set
$G(t,x)=\frac{1-e^{t}e^{tx}}{(1+1/x)(1-e^{tx})}$, and set $G(0,x)=1$ so that
$G$ is continuous at $0$. By definition $I(m,\alpha)$ is the supremum over
$\theta<0$ of $\gamma(\theta,m)=\alpha\theta-\log G(\theta,\frac{1}{m})$. Note
that $\gamma(0,m)=0$; moreover, as $t\to 0$,

$\begin{split}G(t,x)&=\frac{1-e^{t(1+x)}}{(1+1/x)(1-e^{tx})}\\\
&=\frac{1}{1+1/x}\left(\frac{-t(1+x)-t^{2}(1+x)^{2}/2+O(t^{3})}{-tx-t^{2}x^{2}/2+O(t^{3})}\right)\\\
&=\frac{1+t(1+x)/2+O(t^{2})}{1+tx/2+O(t^{2})}\\\ &=1+t/2+O(t^{2}),\end{split}$

and hence $\frac{\partial\log G}{\partial t}(0,x)=\frac{\frac{\partial
G}{\partial t}(0,x)}{G(0,x)}=\frac{\partial G}{\partial t}(0,x)=\frac{1}{2}$.
Thus, the derivative
$\frac{\partial\gamma}{\partial\theta}(0,m)=\alpha-\frac{1}{2}<0$ is negative
for all $\alpha\in(0,\frac{1}{2})$. This guarantees that there exists some
$\theta<0$ where $\gamma(\theta,m)$ is positive, proving the second claim.

Furthermore, the supremum of $\gamma(\theta,m)$ is attained at some
$\theta<0$, because $\gamma(\theta,m)$ tends to $0$ as $\theta\to 0$ and
$-\infty$ as $\theta\to-\infty$, while the supremum is positive. This means
that to prove that $I(m,\alpha)$ is increasing in $m$, it suffices to prove
for each _fixed_ $\theta<0$ that $\gamma(\theta,m)$ is increasing in $m$.
Equivalently, we must prove that $G(t,x)$ is increasing in $x$ when $t<0$ and
$x>0$; we do this by proving that $\frac{\partial G}{\partial x}>0$ in this
region.

Set $h(x)=(1-e^{tx})/x$. Note that
$\frac{h(x+1)}{h(x)}=\frac{(1-e^{t(x+1)})/(x+1)}{(1-e^{tx})/x}=G(t,x)$.
Therefore $\frac{\partial G}{\partial x}>0$ if and only if
$h^{\prime}(x+1)h(x)\geq h^{\prime}(x)h(x+1)$. Since $t<0$ and $x>0$ we have
$h(x)>0$, so this holds if and only if
$\frac{h^{\prime}(x+1)}{h(x+1)}>\frac{h^{\prime}(x)}{h(x)}$. Hence it suffices
to show that $\frac{d^{2}}{dx^{2}}\log h(x)>0$, since then $\frac{d}{dx}\log
h(x)=\frac{h^{\prime}(x)}{h(x)}$ is increasing. We have that
$\frac{d^{2}}{dx^{2}}\log
h(x)=\frac{d}{dx}\left(-\frac{1}{x}-\frac{te^{tx}}{1-e^{tx}}\right)=\frac{1}{x^{2}}-\frac{(1-e^{tx})t^{2}e^{tx}-te^{tx}(-te^{tx})}{(1-e^{tx})^{2}}=\frac{1}{x^{2}}-\frac{t^{2}e^{tx}}{(1-e^{tx})^{2}}$,
and so the proposition follows from the inequality
$(1-e^{tx})^{2}>t^{2}x^{2}e^{tx}$, which we can prove as follows.

To verify this inequality, note that $n!\leq 2^{n-1}(n-1)!$ for all
$n\in{\mathbb{N}}$ with strict inequality for all $n>2$. Hence
$\sum_{n=1}^{\infty}\frac{z^{n}}{n!}>\sum_{n=1}^{\infty}\frac{z^{n}}{2^{n-1}(n-1)!}$
for $z>0$. Evaluating those power series shows that $e^{z}-1>ze^{z/2}$.
Dividing by $e^{z}$, we obtain $1-e^{-z}>ze^{-z/2}$. Squaring yields
$(1-e^{-z})^{2}>z^{2}e^{-z}$; setting $z=-tx$, this becomes the desired
inequality.

Finally, as $m\to\infty$ we have

$\lim_{m\rightarrow\infty}I(m,\alpha)=\lim_{m\rightarrow\infty}\sup_{\theta<0}\left(\alpha\theta-\log
G\left(\theta,{\textstyle\frac{1}{m}}\right)\right).$

Since $-\log G(\theta,x)$ is monotonically decreasing in $x$,
$\alpha\theta-\log G\left(\theta,{\textstyle\frac{1}{m}}\right)$ is
monotonically increasing in $m$, so the limit in $m$ is the same as the
supremum in $m$ and hence commutes with the supremum in $\theta$. Thus we may
switch the order of the limit and the supremum to obtain

$\lim_{m\rightarrow\infty}I(m,\alpha)=\sup_{\theta<0}\big{(}\alpha\theta-\lim_{m\rightarrow\infty}\log
G\left(\theta,{\textstyle\frac{1}{m}}\right)\big{)}.$

By the continuity of the logarithm and the variable change $\frac{1}{m}=x$
this equals

$\sup_{\theta<0}\left(\alpha\theta-\log\Big{(}\lim_{x\rightarrow
0}{\textstyle\frac{h(x+1)}{h(x)}}\Big{)}\right),$

where $h(x)=\left(1-e^{\theta x}\right)/x$. Since $\lim_{x\rightarrow
0}h(x)=-\theta$, it follows that

$\lim_{m\rightarrow\infty}I(m,\alpha)=\sup_{\theta<0}\alpha\theta-\log\big{(}{\textstyle\frac{e^{\theta}-1}{\theta}}\big{)}.\qed$

###  4.4 Tricolored sum-free sets in abelian groups of bounded exponent

In this section, we prove Theorems A and A′, by way of the following sharper
bound.

######  Theorem 4.14.

If $H$ is an abelian group $H\cong({\mathbb{Z}}/q{\mathbb{Z}})^{n}\times G$
where $q$ is a prime power, then every tricolored sum-free set in $H$ has
cardinality at most $3\cdot\left\lvert H\right\rvert\cdot J(q)^{n}$.

The upper bound in Theorem 4.14 is known to be sharp up to a subexponential
factor by [14, Theorem 2], conditional on a conjecture, namely [14, Conjecture
3], that was later proved independently in [18] and [19].

The proofs of these theorems depend on the following proposition.

######  Proposition 4.15.

If $q=p^{r}$ is a prime power, the triangle rank of
$D_{{\mathbb{Z}}/q{\mathbb{Z}}}$ over ${\mathbb{F}}_{p}$ is at most $q$.

###### Proof.

The triangle rank is invariant under any permutation of the sets $X,Y,Z$, so
it suffices to bound the triangle rank of the function

$D_{{\mathbb{Z}}/q{\mathbb{Z}}}(x,y,z+1)=\begin{cases}1\in{\mathbb{F}}_{p}&\text{if
}x+y+z=q-1\in{\mathbb{Z}}/q{\mathbb{Z}},\text{ and}\\\
0\in{\mathbb{F}}_{p}&\text{if }x+y+z\neq
q-1\in{\mathbb{Z}}/q{\mathbb{Z}}.\end{cases}$

As a consequence of Lucas’ theorem, for any $0\leq k<q$ and
$m,m^{\prime}\in{\mathbb{N}}$,

$m\equiv
m^{\prime}\pmod{q}\quad\implies\quad\binom{m}{k}\equiv\binom{m^{\prime}}{k}\pmod{p}.$

In other words, $m\mapsto\binom{m}{k}$ descends to a well-defined function
${\mathbb{Z}}/q{\mathbb{Z}}\to{\mathbb{F}}_{p}$. We claim that

$D_{{\mathbb{Z}}/q{\mathbb{Z}}}(x,y,z+1)=\sum_{a+b+c=q-1}\binom{x}{a}\binom{y}{b}\binom{z}{c}.$

Indeed, the identity
$\binom{X+Y+Z}{i}=\sum_{a+b+c=i}\binom{X}{a}\binom{Y}{b}\binom{Z}{c}\in{\mathbb{N}}$
for $X,Y,Z\in{\mathbb{N}}$ descends to an identity
$\binom{x+y+z}{i}=\sum_{a+b+c=i}\binom{x}{a}\binom{y}{b}\binom{z}{c}\in{\mathbb{F}}_{p}$
for $x,y,z\in{\mathbb{Z}}/q{\mathbb{Z}}$. But for any
$w\in{\mathbb{Z}}/q{\mathbb{Z}}$, choosing a lift in $\\{0,\dots,q-1\\}$ shows
that

$\binom{w}{q-1}=\begin{cases}1\in{\mathbb{F}}_{p}&\text{if
}w=q-1\in{\mathbb{Z}}/q{\mathbb{Z}},\text{ and}\\\
0\in{\mathbb{F}}_{p}&\text{if }w\neq
q-1\in{\mathbb{Z}}/q{\mathbb{Z}}.\end{cases}$

This decomposition of $D_{{\mathbb{Z}}/q{\mathbb{Z}}}(x,y,z+1)$ shows that its
triangle rank is at most $q$. ∎

###### Proof of Theorem 4.14.

Let $q=p^{r}$, and consider the tensor $D_{H}$ over ${\mathbb{F}}_{p}$. The
decomposition $H\cong({\mathbb{Z}}/q{\mathbb{Z}})^{n}\times G$ induces a
decomposition $D_{H}=D_{({\mathbb{Z}}/q{\mathbb{Z}})^{n}}\otimes D_{G}$.
Proposition 4.2 thus implies

$\operatorname{slice-rank}(D_{H})\leq\operatorname{slice-
rank}(D_{({\mathbb{Z}}/q{\mathbb{Z}})^{n}})\cdot\left\lvert G\right\rvert.$

We proved in Proposition 4.15 that $\operatorname{triangle-
rank}(D_{{\mathbb{Z}}/q{\mathbb{Z}}})\leq q$. By Proposition 4.13, this
implies that $\operatorname{slice-
rank}(D_{({\mathbb{Z}}/q{\mathbb{Z}})^{n}})\leq 3(qJ(q))^{n}$. We conclude

$\operatorname{slice-rank}(D_{H})\leq 3(qJ(q))^{n}\cdot\left\lvert
G\right\rvert=3\cdot\left\lvert H\right\rvert\cdot J(q)^{n}.$

The bound on tricolored sum-free sets in $H$ then follows from Proposition
4.8. ∎

###### Proof of Theorem A′.

If $q$ is a prime power, Theorem 4.14 states that the size of any tricolored
sum-free set in $H\cong({\mathbb{Z}}/q{\mathbb{Z}})^{n}$ is at most
$3\cdot\left\lvert H\right\rvert\cdot J(q)^{n}$. To get a uniform bound we
recall that $J(q)$ is decreasing by Proposition 4.12, so the worst case for
this bound occurs when the prime power $q$ is $2$. Therefore if we set

$\delta=I(1,{\textstyle\frac{1}{3}})=\sup_{\theta<0}\left({\textstyle\frac{\theta}{3}}-\log\left(\frac{e^{2\theta}-1}{2e^{\theta}-2}\right)\right)=\log\big{(}(2/3)2^{2/3}\big{)}=0.05663\ldots,$

then $J(q)\leq J(2)=e^{-\delta}=q^{-\frac{\delta}{\log q}}$. The size of any
tricolored sum-free set in $H\cong({\mathbb{Z}}/q{\mathbb{Z}})^{n}$ is thus at
most

$3\cdot\left\lvert H\right\rvert\cdot J(q)^{n}\leq 3\cdot\left\lvert
H\right\rvert\cdot J(2)^{n}=3q^{n}e^{-\delta n}=3\cdot\left\lvert
H\right\rvert^{1-\frac{\delta}{\log q}}.\qed$

###### Proof of Theorem A.

Let $q_{1},\dots,q_{r}$ denote all the prime powers less than or equal to $m$.
By the Chinese remainder theorem, we can write
$H\cong\prod_{i=1}^{r}({\mathbb{Z}}/q_{i}{\mathbb{Z}})^{n_{i}}$. Let $\ell$ be
the index for which $n_{\ell}$ is largest. Writing $\sum_{i}n_{i}=N$, we know
that $n_{\ell}\geq N/r$. Since $\sum_{i}n_{i}\log q_{i}=\log\left\lvert
H\right\rvert$ and $q_{i}\leq m$ we have $N\geq\frac{\log\left\lvert
H\right\rvert}{\log m}$.

Next, we claim that $r<\frac{2m}{\log m}$ for all $m>1$. By [23, (3.2) and
(3.36)] we have that $r<\frac{m}{\log m}+\frac{3m}{2(\log
m)^{2}}+\frac{1.4260m^{1/2}}{\log 2}$. This bound is at most $\frac{2m}{\log
m}$ as long as $m\geq 242$. For the remaining $1<m<242$, one can simply check
directly that the number of prime powers less than $m$ is less than
$\frac{2m}{\log m}$.

Combining these bounds on $N$ and $r$ shows that
$n_{\ell}\geq\frac{N}{r}\geq\frac{\log\left\lvert H\right\rvert}{2m}$. By
Theorem 4.14, this implies the size of any tricolored sum-free set in
$H\cong({\mathbb{Z}}/q_{\ell}{\mathbb{Z}})^{n_{\ell}}\times G$ is at most

$3\cdot\left\lvert H\right\rvert\cdot J(q_{\ell})^{n_{\ell}}\leq
3\cdot\left\lvert H\right\rvert\cdot J(q_{\ell})^{\log\left\lvert
H\right\rvert/(2m)}=3\cdot\left\lvert H\right\rvert^{1+\log
J(q_{\ell})/(2m)}.$

As in the proof of Theorem A′ above, the worst case for this bound is when the
prime power $q_{\ell}$ is $2$; since $J(s)$ is decreasing, we can bound $\log
J(q_{\ell})\leq\log J(2)=-\delta$. Setting

$\varepsilon=\delta/2=\log\big{(}(2/3)2^{2/3}\big{)}/2=0.02831\ldots,$

the bound from Theorem 4.14 then implies the size of any tricolored sum-free
set in $H$ is at most $3\cdot\left\lvert H\right\rvert^{1+\log
J(q_{\ell})/(2m)}\leq 3\cdot\left\lvert H\right\rvert^{1-\varepsilon/m}$. ∎

## Acknowledgements

We thank the AIM SQuaRE program, the Santa Fe Institute, and Microsoft
Research for hosting visits.

## References

  * [1] N. Alon, A. Shpilka, and C. Umans, _On sunflowers and matrix multiplication_ , Computational Complexity 22 (2013), 219–243, 10.1007/s00037-013-0060-1.
  * [2] P. Bürgisser, M. Clausen, and M. A. Shokrollahi, _Algebraic complexity theory_ , Grundlehren der Mathematischen Wissenschaften 315, Springer-Verlag, Berlin, 1997, 10.1007/978-3-662-03338-8.
  * [3] P. Bürgisser and C. Ikenmeyer, _Geometric complexity theory and tensor rank_ , Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 6–8 June 2011, San Jose, CA, Association for Computing Machinery, pp. 509–518, arXiv:1011.1350, 10.1145/1993636.1993704.
  * [4] H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans, _Group-theoretic algorithms for matrix multiplication_ , Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp. 379–388, arXiv:math.GR/0511460, 10.1109/sfcs.2005.39.
  * [5] H. Cohn and C. Umans, _A group-theoretic approach to fast matrix multiplication_ , Proceedings of the 44th Annual Symposium on Foundations of Computer Science, 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp. 438–449, arXiv:math.GR/0307321, 10.1109/sfcs.2003.1238217.
  * [6] H. Cohn and C. Umans, _Fast matrix multiplication using coherent configurations_ , Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 6–8 January 2013, New Orleans, LA, Society for Industrial and Applied Mathematics, pp. 1074–1087, arXiv:1207.6528, 10.1137/1.9781611973105.77.
  * [7] D. Coppersmith and S. Winograd, _Matrix multiplication via arithmetic progressions_ , J. Symbolic Computation 9 (1990), 251–280, 10.1016/s0747-7171(08)80013-2.
  * [8] D. Coppersmith and S. Winograd, _On the asymptotic complexity of matrix multiplication_ , SIAM J. Comput. 11 (1982), 472–492, 10.1137/0211038.
  * [9] E. Croot, V. Lev, and P. Pach, _Progression-free sets in ${\mathbb{Z}}_{4}^{n}$ are exponentially small_, Ann. of Math. (2) 185 (2017), 331–337, arXiv:1605.01506, 10.4007/annals.2017.185.1.7.
  * [10] A. M. Davie and A. J. Stothers, _Improved bound for complexity of matrix multiplication_ , Proc. Roy. Soc. Edinburgh Sect. A 143 (2013), 351–369, 10.1017/S0308210511001648.
  * [11] J. S. Ellenberg and D. Gijswijt, _On large subsets of ${\mathbb{F}}_{q}^{n}$ with no three-term arithmetic progression_, Ann. of Math. (2) 185 (2017), 339–343, arXiv:1605.09223, 10.4007/annals.2017.185.1.8.
  * [12] P. Erdős and E. Szemerédi, _Combinatorial properties of systems of sets_ , J. Combinatorial Theory Ser. A 24 (1978), 308–313, 10.1016/0097-3165(78)90060-2.
  * [13] W. Hoeffding, _Probability inequalities for sums of bounded random variables_ , J. Amer. Statist. Assoc. 58 (1963), 13–30, 10.1080/01621459.1963.10500830.
  * [14] R. Kleinberg, W. F. Sawin, and D. E. Speyer, _The growth rate of tri-colored sum-free sets_ , preprint, 2016, arXiv:1607.00047.
  * [15] F. Le Gall, _Powers of tensors and fast matrix multiplication_ , Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, 23–25 July 2014, Kobe, Japan, Association for Computing Machinery, pp. 296–303, full version at arXiv:1401.7714, 10.1145/2608628.2608664.
  * [16] T. Lickteig, _Typical tensorial rank_ , Linear Algebra Appl. 69 (1985), 95–120, 10.1016/0024-3795(85)90070-9
  * [17] D. Mumford, _Stability of projective varieties_ , Enseignement Math. (2) 23 (1977), 39–110, 10.5169/seals-48919.
  * [18] S. Norin, _A distribution on triples with maximum entropy marginal_ , preprint, 2016, arXiv:1608.00243.
  * [19] L. Pebody, _Proof of a conjecture of Kleinberg-Sawin-Speyer_ , preprint, 2016, arXiv:1608.05740.
  * [20] F. Petrov, _Many zero divisors in a group ring imply bounds on progression-free subsets_ , preprint, 2016, arXiv:1606.03256.
  * [21] A. Schönhage, _Partial and total matrix multiplication_ , SIAM J. Comp. 10 (1981), 434–455, 10.1137/0210032
  * [22] T. Tao, A symmetric formulation of the Croot–Lev–Pach–Ellenberg–Gijswijt capset bound, blog post, 2016, http://terrytao.wordpress.com/2016/05/18/a.
  * [23] J. B. Rosser and L. Schoenfeld, _Approximate formulas for some functions of prime numbers_ , Illinois J. Math. 6 (1962), 64–94, http://projecteuclid.org/euclid.ijm/1255631807.
  * [24] V. Vassilevska Williams, _Multiplying matrices faster than Coppersmith–Winograd_ , Proceedings of the 44th ACM Symposium on Theory of Computing, 19–22 May 2012, New York, NY, Association for Computing Machinery, pp. 887–898, 10.1145/2213977.2214056.

[Blasiak] Jonah Blasiak
Department of Mathematics
Drexel University
Philadelphia, PA 19104
<EMAIL_ADDRESS>[Church] Thomas Church
Department of Mathematics
Stanford University
450 Serra Mall
Stanford, CA 94305
<EMAIL_ADDRESS>[Cohn] Henry Cohn
Microsoft Research New England
One Memorial Drive
Cambridge, MA 02142
<EMAIL_ADDRESS>[Grochow] Joshua A. Grochow
University of Colorado at Boulder
Department of Computer Science
1111 Engineering Drive
Boulder, CO 80309
and
Santa Fe Institute
1399 Hyde Park Rd.
Santa Fe, NM 87501
<EMAIL_ADDRESS>[Naslund] Eric Naslund
Mathematics Department
Princeton University
Fine Hall, Washington Road
Princeton, NJ 08544
<EMAIL_ADDRESS>[Sawin] William F. Sawin
ETH Institute for Theoretical Studies
ETH Zürich
8092 Zürich
<EMAIL_ADDRESS>[Umans] Chris Umans
Computing and Mathematical Sciences
Caltech
1200 E. California Blvd.
Pasadena, CA 91125
<EMAIL_ADDRESS>