of 27
D
ISCRETE
A
NALYSIS
, 2017:3, 27 pp.
www.discreteanalysisjournal.com
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
Received 17 August 2016; Revised 5 January 2017; Published 16 January 2017
Abstract:
In 2003, Cohn and Umans described a framework for proving upper bounds
on the exponent
ω
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
ω
=
2
. In this paper we rule out obtaining
ω
=
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
A
cap set
is a subset of
F
n
3
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
Supported by NSF grant DMS-14071174.
Supported by NSF grant DMS-1350138, the Alfred P. Sloan Foundation, and the Frederick E. Terman Fellowship.
Supported by a Santa Fe Institute Omidyar Fellowship.
§
Supported by Ben Green’s ERC Starting Grant 279438, Approximate Algebraic Structure and Applications.
Supported by NSF grant DGE-1148900, Dr. Max Rössler, the Walter Haefner Foundation, and the ETH Zürich Foundation.
Supported by NSF grant CCF-1423544 and a Simons Foundation Investigator grant.
c
©
2017 Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans
cb
Licensed under a Creative Commons Attribution License (CC-BY)
DOI: 10.19086/da.1245
arXiv:1605.06702v4 [math.CO] 14 Jan 2017
J. B
LASIAK
, T. C
HURCH
, H. C
OHN
, J. A. G
ROCHOW
, E. N
ASLUND
, W. F. S
AWIN
,
AND
C. U
MANS
Pach [
9
] introduced a powerful new technique, which Ellenberg and Gijswijt [
11
] used to prove that cap
sets in
F
n
3
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
F
n
p
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
̋
os–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
ω
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
ω
=
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
ω
=
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
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
i
(
|
A
i
||
B
i
||
C
i
|
)
ω
/
3
|
H
|
.
(1.1)
If the sets involved are large enough, this yields a nontrivial bound on
ω
, and [
4
] showed how a family of
sufficiently large STPP constructions would imply
ω
=
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
=
2
w
⇐⇒
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
lcm
(
1
,
2
,...,
m
) =
e
m
(
1
+
o
(
1
))
. (This asymptotic formula for
lcm
(
1
,
2
,...,
m
)
is a variant of the prime number theorem. See, for example, Theorem 11 in [
23
] for a
stronger bound on
ψ
(
m
) =
log lcm
(
1
,
2
,...,
m
)
.)
Theorem A.
There exists an absolute constant
ε
=
1
2
log
((
2
/
3
)
2
2
/
3
) =
0
.
02831
...
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
·
|
H
|
1
ε
m
.
In the case when
H
is a power of a single cyclic group
Z
/
p
k
Z
, we obtain a sharper bound.
Theorem A
.
There exists an absolute constant
δ
=
2
ε
=
0
.
05663
...
such that if
H
=
(
Z
/
q
Z
)
n
for some
prime power q, then every tricolored sum-free set in H has size at most
3
·
|
H
|
1
δ
log
q
.
These theorems extend the Ellenberg–Gijswijt [
11
] result in two directions: from progression-free
sets to tricolored sum-free sets
1
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
·
|
H
|
1
δ
log
p
agrees with the bound for progression-free
1
Noga Alon independently observed that the Ellenberg–Gijswijt result extends to tricolored sum-free sets in
F
n
p
.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
2
O
N
C
AP
S
ETS AND THE
G
ROUP
-
THEORETIC
A
PPROACH TO
M
ATRIX
M
ULTIPLICATION
sets obtained in [
11
], but with a slightly worse exponent as we have stated it uniformly in
p
. It remains
to be seen whether
ε
m
can be improved to
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
ω
=
2
using sets
satisfying the simultaneous triple product property in abelian groups of bounded exponent:
Theorem B.
For every
`
N
, there is an
ε
`
>
0
such that no STPP construction in any abelian group of
exponent at most
`
is large enough to yield a bound better than
ω
2
+
ε
`
via the inequality
(1.1)
.
Note that all of the current best bounds on
ω
via the group-theoretic approach (in [
4
]), as well as the
current best bounds on
ω
which use the Coppersmith–Winograd approach [
7
,
10
,
24
,
15
], yield STPP
constructions whose underlying group is
(
Z
/
m
Z
)
n
for
m
fixed.
However, our results
do not
rule out achieving
ω
=
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
ω
=
2.
2 The simultaneous triple product property
Recall that the
exponent of matrix multiplication
is defined as
ω
=
inf
{
c
: the tensor rank of
n
×
n
matrix multiplication is at most
O
(
n
c
)
as
n
}
.
In 2003, Cohn and Umans [
5
] described a framework for proving upper bounds on
ω
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
⇐⇒
a
=
b
=
c
=
1
for all a
A
1
A, b
B
1
B, and c
C
1
C, where S
1
S denotes
{
s
1
s
:
s
,
s
S
}
for S
G.
Such a triple of subsets realizes
|
A
|
,
|
B
|
,
|
C
|
inside the group algebra of
G
. (Here
m
,
n
,
p
denotes
the matrix multiplication tensor for multiplying an
m
×
n
matrix by an
n
×
p
matrix.) From this, letting
d
1
,
d
2
,...
be the character degrees of
G
(i.e., the dimensions of its irreducible representations), we obtain
the inequality
(
|
A
||
B
||
C
|
)
ω
/
3
i
d
ω
i
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
3
J. B
LASIAK
, T. C
HURCH
, H. C
OHN
, J. A. G
ROCHOW
, E. N
ASLUND
, W. F. S
AWIN
,
AND
C. U
MANS
by bounding the rank of group algebra multiplication [
5
, Theorem 4.1]. This inequality yields an upper
bound for
ω
when
G
and
A
,
B
,
C
are chosen appropriately.
In the later paper [
4
] several concrete routes to proving
ω
=
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
o
S
m
=
H
m
o
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. for each i the sets A
i
,
B
i
,
C
i
satisfy the triple product property, and
2. setting S
i
=
A
i
B
1
i
, T
j
=
B
j
C
1
j
, and U
k
=
C
k
A
1
k
,
s
i
t
j
u
k
=
1
i
=
j
=
k
for all s
i
S
i
, t
j
T
j
, and u
k
U
k
.
Equivalently,
A
i
,
B
i
,
C
i
H
satisfy the STPP if for all
i
,
j
,
k
and
s
A
k
,
s
A
i
,
t
B
i
,
t
B
j
,
u
C
j
,
and
u
C
k
, we have
s
1
s
t
1
t
u
1
u
=
1
⇐⇒
i
=
j
=
k
,
s
=
s
,
t
=
t
,
u
=
u
.
An STPP construction in
H
realizes the tensor
i
|
A
i
|
,
|
B
i
|
,
|
C
i
|
and, via the asymptotic sum
inequality [21] or the use of a wreath product [4, §7], yields the fundamental inequality
i
(
|
A
i
||
B
i
||
C
i
|
)
ω
/
3
i
d
ω
i
,
(2.1)
where
d
1
,
d
2
,...
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:
i
(
|
A
i
||
B
i
||
C
i
|
)
ω
/
3
|
H
|
.
All of the analysis of STPP constructions in the framework of [4] is based on this inequality.
No single STPP construction can achieve
ω
=
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
α
}
α
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
|
S
i
|
=
|
A
i
||
B
i
|
,
|
T
i
|
=
|
B
i
||
C
i
|
, and
|
U
i
|
=
|
C
i
||
A
i
|
. Together these give the packing bounds:
i
|
A
i
||
B
i
|
|
H
|
,
i
|
B
i
||
C
i
|
|
H
|
,
and
i
|
C
i
||
A
i
|
|
H
|
.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
4
O
N
C
AP
S
ETS AND THE
G
ROUP
-
THEORETIC
A
PPROACH TO
M
ATRIX
M
ULTIPLICATION
Definition 2.3.
We say that a family of STPP constructions with
|
H
|
meets the packing bound
if
i
|
A
i
||
B
i
|
|
H
|
1
o
(
1
)
,
i
|
B
i
||
C
i
|
|
H
|
1
o
(
1
)
,
and
i
|
C
i
||
A
i
|
|
H
|
1
o
(
1
)
.
A key observation is that meeting the packing bound is necessary for achieving
ω
=
2:
Lemma 2.4.
Any family of STPP constructions that does
not
meet the packing bound cannot imply
ω
=
2
via the inequality
(1.1)
.
Proof.
In our usual notation, if
i
|
A
i
||
B
i
|
|
H
|
1
3
ε
for some fixed
ε
>
0, then
i
(
|
A
i
||
B
i
||
C
i
|
)
ω
/
3
(
i
(
|
A
i
||
B
i
||
C
i
|
)
2
/
3
)
ω
/
2
=
(
i
(
|
A
i
||
B
i
||
H
|
2
ε
·
|
B
i
||
C
i
||
H
|
ε
·
|
C
i
||
A
i
||
H
|
ε
)
1
/
3
)
ω
/
2
(
i
|
A
i
||
B
i
||
H
|
2
ε
+
i
|
B
i
||
C
i
||
H
|
ε
+
i
|
C
i
||
A
i
||
H
|
ε
3
)
ω
/
2
(
|
H
|
1
ε
)
ω
/
2
,
and so the strongest bound that can be obtained from
(1.1)
is
ω
2
·
1
1
ε
, which is bounded strictly away
from the hoped-for
ω
=
2. The same holds if either
i
|
B
i
||
C
i
|
|
H
|
1
3
ε
or
i
|
C
i
||
A
i
|
|
H
|
1
3
ε
.
Both the strong USP conjecture [
4
, Conjecture 3.4] and the “two families” conjecture [
4
, Conjec-
ture 4.7] would, if true, yield STPP constructions that meet the packing bound and moreover prove
ω
=
2
. However, the STPP constructions produced by the strong USP conjecture have underlying group
H
=
F
n
3
, 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
S
×
T
×
U on a triple of sets S
,
T
,
U
H, such that
s
+
t
+
u
=
0
for all
(
s
,
t
,
u
)
M
and
s
+
t
+
u
6
=
0
for all
(
s
,
t
,
u
)
(
S
×
T
×
U
)
\
M
.
The
cardinality
of a tricolored sum-free set is the cardinality of M.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
5
J. B
LASIAK
, T. C
HURCH
, H. C
OHN
, J. A. G
ROCHOW
, E. N
ASLUND
, W. F. S
AWIN
,
AND
C. U
MANS
By a perfect matching
M
S
×
T
×
U
we mean a subset whose projection onto each of the three
factors is a bijection. In other words, given
s
S
there exist unique
t
T
and
u
U
such that
(
s
,
t
,
u
)
M
,
and similarly for the other factors. The cardinality of the matching
M
is therefore equal to
|
S
|
,
|
T
|
, and
|
U
|
. Note that any 3-dimensional matching
M
H
3
(not necessarily perfect, i.e., replacing “bijection”
above with “injection”) uniquely determines three sets
S
,
T
,
U
H
such that
M
is a 3-dimensional perfect
matching on
S
×
T
×
U
.
If
S
F
n
p
contains no three-term arithmetic progressions, then
M
=
{
(
s
,
s
,
2
s
)
:
s
S
}
is a tricolored
sum-free set. Similarly, for any nonzero
α
,
β
,
γ
F
p
with
α
+
β
+
γ
=
0
, we obtain a tricolored sum-free
set
M
=
{
(
α
s
,
β
s
,
γ
s
)
:
s
S
}
whenever
S
avoids nontrivial solutions to
α
s
+
β
t
+
γ
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
S
×
T
×
U
on a triple of sets
S
,
T
,
U
H
together with functions
α
:
S
Z
,
β
:
T
Z
,
and
γ
:
U
Z
such that
s
+
t
+
u
=
0
and
α
(
s
)+
β
(
t
)+
γ
(
u
) =
0
for all
(
s
,
t
,
u
)
M, while
s
+
t
+
u
6
=
0
or
α
(
s
)+
β
(
t
)+
γ
(
u
)
>
0
for all
(
s
,
t
,
u
)
(
S
×
T
×
U
)
\
M
. The
cardinality
of a border tricolored sum-free set is the cardinality of
M, and its
range
is the maximum of
|
α
(
s
)
|
,
|
β
(
t
)
|
, and
|
γ
(
u
)
|
over s
S, t
T , and u
U .
One can reformulate the definition as follows: the sets
{
(
s
,
α
(
s
))
:
s
S
}
,
{
(
t
,
β
(
t
))
:
t
T
}
, and
{
(
u
,
γ
(
u
))
:
u
U
}
form a tricolored sum-free set in
H
×
Z
(under the obvious
3
-dimensional matching
extending
M
), and they satisfy the positivity condition that
α
(
s
)+
β
(
t
)+
γ
(
u
)
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
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
i
|
A
i
||
B
i
||
C
i
|
|
A
i
|
+
|
B
i
|
+
|
C
i
|
.
Proof.
As in Definition 2.2 (but using additive notation), we will set
S
i
=
A
i
B
i
=
{
a
b
:
a
A
i
,
b
B
i
}
,
and similarly
T
i
=
B
i
C
i
and
U
i
=
C
i
A
i
.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
6
O
N
C
AP
S
ETS AND THE
G
ROUP
-
THEORETIC
A
PPROACH TO
M
ATRIX
M
ULTIPLICATION
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
α
,
β
, and
γ
that repair any problems with it, so that it becomes a border tricolored sum-free set.
To begin, let
n
i
=
|
A
i
|
,
m
i
=
|
B
i
|
, and
p
i
=
|
C
i
|
, and identify
A
i
,
B
i
,
C
i
with
[
n
i
]
,
[
m
i
]
,
[
p
i
]
, respectively,
via bijections
α
i
,
β
i
,
γ
i
. Let
r
i
be the most frequently occurring value in the multiset
{
x
+
y
+
z
:
(
x
,
y
,
z
)
[
n
i
]
×
[
m
i
]
×
[
p
i
]
}
.
Define
M
i
H
3
as
M
i
=
{
(
a
b
,
b
c
,
c
a
)
:
a
A
i
,
b
B
i
,
c
C
i
such that
α
i
(
a
)+
β
i
(
b
)+
γ
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
|
A
i
|
+
|
B
i
|
+
|
C
i
|
. Since
r
i
was
chosen to be the most frequent value,
|
M
i
|
|
A
i
||
B
i
||
C
i
|
|
A
i
|
+
|
B
i
|
+
|
C
i
|
.
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
α
i
(
a
)+
β
i
(
b
)+
γ
i
(
c
) =
r
i
determines
c
, and the same is
true for the other two coordinates. We combine these matchings by setting
M
=
i
M
i
. Note that the sets
M
i
are disjoint from each other (since the sets
S
i
are, for example), so
|
M
|
=
i
|
M
i
|
. All that remains is
to define the functions
α
,
β
,
γ
so as to obtain a border tricolored sum-free set.
Let
S
i
,
T
i
,
U
i
be the projections of
M
i
onto the three factors of
H
3
. In other words,
S
i
=
{
a
b
:
a
A
i
,
b
B
i
, and there exists
c
C
i
such that
α
i
(
a
)+
β
i
(
b
)+
γ
i
(
c
) =
r
i
}⊆
S
i
,
and
T
i
and
U
i
can be expressed similarly. Let
S
=
i
S
i
,
T
=
i
T
i
, and
U
=
i
U
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
S
,
t
T
, and
u
U
. First, note
that the simultaneous triple product property implies that if
s
i
+
t
j
+
u
k
=
0
with
s
i
S
i
,
t
j
T
j
, and
u
k
U
k
, then
i
=
j
=
k
. Thus, we cannot obtain a sum of zero from
S
i
,
T
j
, and
U
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
i
,
T
i
, and
U
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
)
S
i
×
T
i
×
U
i
, with
s
=
a
b
A
i
B
i
,
t
=
b
c
B
i
C
i
, and
u
=
c
a
C
i
A
i
. Note that
s
determines
a
and
b
,
t
determines
b
and
c
, and
u
determines
c
and
a
since
A
i
,
B
i
,
C
i
satisfy the triple product property. Furthermore, the triple product property tells us that
s
+
t
+
u
=
0 implies
a
=
a
,
b
=
b
,
c
=
c
.
However, that is not enough to conclude that
(
s
,
t
,
u
)
M
i
, because it is not necessarily the case that
α
i
(
a
)+
β
i
(
b
)+
γ
i
(
c
) =
r
i
. To address this issue, we will define functions
α
,
β
, and
γ
on
S
i
,
T
i
, and
U
i
,
respectively, so that
α
(
s
)+
β
(
t
)+
γ
(
u
) =
(
α
i
(
a
)+
β
i
(
b
)+
γ
i
(
c
)
r
i
)
2
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
7
J. B
LASIAK
, T. C
HURCH
, H. C
OHN
, J. A. G
ROCHOW
, E. N
ASLUND
, W. F. S
AWIN
,
AND
C. U
MANS
whenever
s
+
t
+
u
=
0. Specifically, we can take
α
(
s
) =
α
i
(
a
)
2
+
2
α
i
(
a
)
β
i
(
b
)
2
α
i
(
a
)
r
i
+
r
2
i
,
β
(
t
) =
β
i
(
b
)
2
+
2
β
i
(
b
)
γ
i
(
c
)
2
β
i
(
b
)
r
i
,
and
γ
(
u
) =
γ
i
(
c
)
2
+
2
γ
i
(
c
)
α
i
(
a
)
2
γ
i
(
c
)
r
i
.
(We simply expand the square and assign each term to one of
α
(
s
)
,
β
(
t
)
,
γ
(
u
)
so that
α
(
s
)
depends only
on
a
and
b
,
β
(
t
)
depends only on
b
and
c
, and
γ
(
u
)
depends only on
c
and
a
.)
By construction,
α
(
s
)+
β
(
t
)+
γ
(
u
)
0
whenever
s
+
t
+
u
=
0
, and
α
(
s
)+
β
(
t
)+
γ
(
u
) =
0
exactly
when
(
s
,
t
,
u
)
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
/
(
2
Nt
+
1
)
3
.
In particular, as
N
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
H
, with functions
α
:
S
Z
,
β
:
T
Z
, and
γ
:
U
Z
.
Define
M
(
S
N
×
T
N
×
U
N
)
in the natural way, so that
((
s
1
,...,
s
N
)
,
(
t
1
,...,
t
N
)
,
(
u
1
,...,
u
N
))
M
if and only if
(
s
i
,
t
i
,
u
i
)
M
for all
i
, and define
α
(
s
1
,...,
s
N
) =
α
(
s
1
)+
···
+
α
(
s
N
)
and similarly for
β
and
γ
. 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
by a small amount. Because the
functions
α
,
β
,
γ
for
M
have range
Nt
(and thus each take on at most
2
Nt
+
1
values), there exist integers
α
,
β
,
γ
such that for at least a
1
/
(
2
Nt
+
1
)
3
fraction of the triples
(
s
,
t
,
u
)
M
, we have
α
(
s
) =
α
,
β
(
t
) =
β
, and
γ
(
u
) =
γ
. Furthermore,
α
+
β
+
γ
=
0
because
α
(
s
)+
β
(
t
)+
γ
(
u
) =
0
whenever
(
s
,
t
,
u
)
M
.
Let
M
′′
be the subset of
M
consisting of these triples with
α
(
s
) =
α
,
β
(
t
) =
β
, and
γ
(
u
) =
γ
,
and let
S
′′
,
T
′′
,
U
′′
be the sets on which
M
′′
is a perfect matching. Then
|
M
′′
|≥|
M
|
/
(
2
Nt
+
1
)
3
=
|
M
|
N
/
(
2
Nt
+
1
)
3
, and
M
′′
is trivially a border tricolored sum-free set. Furthermore,
α
(
s
′′
)+
β
(
t
′′
)+
γ
(
u
′′
) =
α
+
β
+
γ
=
0
whenever
s
′′
S
′′
,
t
′′
T
′′
, and
u
′′
U
′′
, by construction. Because
α
(
s
′′
) +
β
(
t
′′
) +
γ
(
u
′′
)
vanishes
identically, the functions
α
,
β
, and
γ
serve no purpose in the definition of a border tricolored sum-free
set. Thus,
M
′′
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
|
A
i
|
is independent of
i
, as
are
|
B
i
|
and
|
C
i
|
(note that we do not require
|
A
i
|
=
|
B
i
|
=
|
C
i
|
).
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.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
8
O
N
C
AP
S
ETS AND THE
G
ROUP
-
THEORETIC
A
PPROACH TO
M
ATRIX
M
ULTIPLICATION
Proof.
Let the original STPP construction consist of
n
triples
A
i
,
B
i
,
C
i
of subsets of
H
indexed by
i
[
n
]
.
Our new STPP construction will consist of subsets of
H
3
N
, where
N
is a large number to be chosen later;
these subsets are indexed by triples
(
u
,
v
,
w
)
[
n
]
N
×
[
n
]
N
×
[
n
]
N
and defined by
̂
A
u
,
v
,
w
=
`
A
u
`
×
`
B
v
`
×
`
C
w
`
,
̂
B
u
,
v
,
w
=
`
B
u
`
×
`
C
v
`
×
`
A
w
`
,
̂
C
u
,
v
,
w
=
`
C
u
`
×
`
A
v
`
×
`
B
w
`
.
(The products here are cartesian products of sets.) It is not hard to verify that these sets satisfy the STPP in
H
3
N
(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
̂
A
u
,
v
,
w
,
̂
B
u
,
v
,
w
,
̂
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
(
i
|
A
i
||
B
i
|
)
N
·
(
i
|
B
i
||
C
i
|
)
N
·
(
i
|
C
i
||
A
i
|
)
N
|
H
|
3
N
(
1
o
(
1
))
because the original STPP construction meets the packing bound. Expanding the left side gives
u
`
|
A
u
`
||
B
u
`
|
·
v
`
|
B
v
`
||
C
v
`
|
·
w
`
|
C
w
`
||
A
w
`
|
=
u
,
v
,
w
`
|
A
u
`
||
B
v
`
||
C
w
`
||
B
u
`
||
C
v
`
||
A
w
`
|
.
We have
̂
A
u
,
v
,
w
̂
B
u
,
v
,
w
=
`
|
A
u
`
||
B
v
`
||
C
w
`
||
B
u
`
||
C
v
`
||
A
w
`
|
(3.1)
and hence
u
,
v
,
w
̂
A
u
,
v
,
w
̂
B
u
,
v
,
w
|
H
|
3
N
(
1
o
(
1
))
,
as desired; the same also holds for
u
,
v
,
w
̂
B
u
,
v
,
w
̂
C
u
,
v
,
w
and
u
,
v
,
w
̂
A
u
,
v
,
w
̂
C
u
,
v
,
w
.
To enforce uniformity, we restrict our attention to only certain choices of
u
,
v
, and
w
by observing
that the cardinality
̂
A
u
,
v
,
w
=
`
|
A
u
`
||
B
v
`
||
C
w
`
|
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
|
̂
B
u
,
v
,
w
|
and
|
̂
C
u
,
v
,
w
|
. There are
(
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
μ
1
,
μ
2
,
μ
3
of distributions
for which
u
μ
1
`
|
A
u
`
||
B
u
`
|
·
v
μ
2
`
|
B
v
`
||
C
v
`
|
·
w
μ
3
`
|
C
w
`
||
A
w
`
|
1
(
N
+
1
)
3
n
|
H
|
3
N
(
1
o
(
1
))
,
(3.2)
where
u
μ
1
means
u
has distribution
μ
1
.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
9
J. B
LASIAK
, T. C
HURCH
, H. C
OHN
, J. A. G
ROCHOW
, E. N
ASLUND
, W. F. S
AWIN
,
AND
C. U
MANS
Restricting to only those sets
̂
A
u
,
v
,
w
,
̂
B
u
,
v
,
w
, and
̂
C
u
,
v
,
w
with
u
μ
1
,
v
μ
2
, and
w
μ
3
thus gives a
uniform STPP construction. Combining (3.1) and (3.2) we obtain
u
μ
1
,
v
μ
2
,
w
μ
3
̂
A
u
,
v
,
w
̂
B
u
,
v
,
w
1
(
N
+
1
)
3
n
|
H
|
3
N
(
1
o
(
1
))
,
which is again
|
H
|
3
N
(
1
o
(
1
))
as long as
N
is chosen sufficiently large relative to
n
and
|
H
|
. The same holds
for the other two conditions in the packing bound.
Choosing
N
and
μ
1
,
μ
2
,
μ
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
`
N
, and suppose that for each
δ
>
0
there is an STPP construction in a group of exponent at
most
`
that proves
ω
2
+
δ
. Choosing a sequence with
δ
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
`
.
Consider one of these uniform STPP constructions in a group
H
of exponent at most
`
, thus generated
by elements of order at most
`
. By Theorem 3.3 there exists a border tricolored sum-free set in
H
of
cardinality
|
M
|
=
i
|
A
i
||
B
i
||
C
i
|
|
A
i
|
+
|
B
i
|
+
|
C
i
|
. Since
|
A
i
|
,
|
B
i
|
, and
|
C
i
|
are each independent of
i
, without loss of
generality we may assume that
|
C
i
|
is the largest of these, in which case
|
M
|
=
i
|
A
i
||
B
i
||
C
i
|
|
A
i
|
+
|
B
i
|
+
|
C
i
|
1
3
i
|
A
i
||
B
i
|
|
H
|
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
|
H
|
N
(
1
ε
`
)
, 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
F
n
p
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
F
n
p
, the upper bound is then a consequence
of the following three facts about slice rank:
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
10
O
N
C
AP
S
ETS AND THE
G
ROUP
-
THEORETIC
A
PPROACH TO
M
ATRIX
M
ULTIPLICATION
1.
Just as the ordinary matrix rank of an
m
×
m
diagonal matrix is equal to
m
if all the diagonal entries
are nonzero, the same holds for the slice rank of an
m
×
m
×
m
diagonal tensor (over any field; see
Lemma 4.7 or [22, Lemma 1]).
2.
A tricolored sum-free set of cardinality
m
in a group
G
implies that the multiplication tensor of
the group algebra
F
G
restricts to an
m
×
m
×
m
diagonal tensor with nonzero diagonal entries. It
follows that the slice rank of the multiplication tensor of
F
G
is at least the size of any tricolored
sum-free set in
G
(see Proposition 4.8).
3.
Over a field of characteristic
p
, the slice rank of the
F
n
p
-multiplication tensor is at most the number
of vectors in
[
p
]
n
with coordinate sum at most
pn
/
3
, which is at most
(
p
ε
p
)
n
for some
ε
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
δ
0
(
x
+
y
+
z
)
, and the delta
function
δ
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
ε
p
)
n
on the cardinality of a tricolored sum-free set
in
F
n
p
. Expressed a different way, the upper bound for
H
=
F
n
p
is
|
H
|
1
α
p
for some constant
α
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
= (
Z
/
p
k
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
=
G
×
K
where
G
=
(
Z
/
p
k
Z
)
n
and
|
G
|
|
H
|
c
for a constant
c
>
0
. Such a
decomposition expresses the
H
-multiplication tensor
D
H
as a tensor product
D
G
D
K
. We establish a
simple but powerful property of slice rank: the slice rank of
T
T
is at most the slice rank of
T
times
the side length of
T
(Proposition 4.2). This allows us to reduce to the
(
Z
/
p
k
Z
)
n
case, because the slice
rank of
D
H
is at most
|
G
|
1
α
|
K
|
=
|
H
|
1
α
for some constant
α
>
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
:
X
×
Y
F
with values in a field
F
has an unambiguous
rank
;
rank
(
F
)
is the smallest
k
for which we can write
F
(
x
,
y
) =
k
i
=
1
f
i
(
x
)
g
i
(
y
)
,
and this coincides with the rank of the
|
X
|
×
|
Y
|
matrix described by
F
.
A common way to define the rank of a function
F
:
X
×
Y
×
Z
F
is
tensor rank
:
tensor-rank
(
F
)
is
the smallest
k
for which we can write
F
(
x
,
y
,
z
) =
k
i
=
1
f
i
(
x
)
g
i
(
y
)
h
i
(
z
)
.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
11
J. B
LASIAK
, T. C
HURCH
, H. C
OHN
, J. A. G
ROCHOW
, E. N
ASLUND
, W. F. S
AWIN
,
AND
C. U
MANS
In this paper, we make use of another notion of rank which we call
slice rank
:
slice-rank
(
F
)
is the
smallest
k
for which we can write
F
(
x
,
y
,
z
) =
a
i
=
1
f
i
(
x
,
y
)
g
i
(
z
)+
b
i
=
a
+
1
f
i
(
x
,
z
)
g
i
(
y
)+
k
i
=
b
+
1
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
i
f
i
(
x
)
g
i
(
y
)
h
i
(
z
)
automatically fits the form (4.1), we always have
slice-rank
(
F
)
tensor-rank
(
F
)
|
support
(
F
)
|
.
Similarly, directly from the definition (4.1) we immediately conclude that
slice-rank
(
F
)
min
(
|
X
|
,
|
Y
|
,
|
Z
|
)
(4.2)
and
tensor-rank
(
F
)
slice-rank
(
F
)
·
max
(
|
X
|
,
|
Y
|
,
|
Z
|
)
.
(4.3)
Remark 4.1.
Slice rank and tensor rank can be quite different. For example, if
|
X
|
=
N
the function
F
:
X
×
X
×
X
F
given by
F
(
x
,
y
,
z
) =
δ
x
,
y
has
slice-rank
(
F
) =
1
while
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
:
X
×
X
×
X
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 generic
2
F
is
d
N
3
3
N
2
e≈
N
2
/
3
if
N
6
=
3
and
F
is algebraically
closed [16].
Given functions
F
:
X
×
Y
×
Z
F
and
G
:
X
′′
×
Y
′′
×
Z
′′
F
, set
X
=
X
×
X
′′
,
Y
=
Y
×
Y
′′
, and
Z
=
Z
×
Z
′′
, and let
F
G
denote the function
F
G
:
X
×
Y
×
Z
F
given by
(
(
x
,
x
′′
)
,
(
y
,
y
′′
)
,
(
z
,
z
′′
)
)
7→
F
(
x
,
y
,
z
)
G
(
x
′′
,
y
′′
,
z
′′
)
.
The inequality
tensor-rank
(
F
G
)
tensor-rank
(
F
)
·
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,
slice-rank
(
F
G
)
slice-rank
(
F
)
·
tensor-rank
(
G
)
and
slice-rank
(
F
G
)
slice-rank
(
F
)
·
max
(
|
X
′′
|
,
|
Y
′′
|
,
|
Z
′′
|
)
.
Proof.
Set
k
=
slice-rank
(
F
)
and choose functions
f
i
and
g
i
for
1
i
k
as in
(4.1)
. Similarly, set
`
=
tensor-rank
(
G
)
and write
G
(
x
′′
,
y
′′
,
z
′′
) =
`
j
=
1
α
j
(
x
′′
)
β
j
(
y
′′
)
γ
j
(
z
′′
)
. If we then define
f
i j
(
x
,
y
)
:
=
f
i
(
x
,
y
)
α
j
(
x
′′
)
β
j
(
y
′′
)
,
g
i j
(
z
)
:
=
g
i
(
z
)
γ
j
(
z
′′
)
for 1
i
a
,
1
j
`,
f
i j
(
x
,
z
)
:
=
f
i
(
x
,
z
)
α
j
(
x
′′
)
γ
j
(
z
′′
)
,
g
i j
(
y
)
:
=
g
i
(
y
)
β
j
(
y
′′
)
for
a
<
i
b
,
1
j
`,
and
f
i j
(
y
,
z
)
:
=
f
i
(
y
,
z
)
β
j
(
y
′′
)
γ
j
(
z
′′
)
,
g
i j
(
x
)
:
=
g
i
(
x
)
α
j
(
x
′′
)
for
b
<
i
k
,
1
j
`,
2
That is, the set of functions
F
with this tensor rank is non-empty and Zariski-open.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
12
O
N
C
AP
S
ETS AND THE
G
ROUP
-
THEORETIC
A
PPROACH TO
M
ATRIX
M
ULTIPLICATION
then
(
F
G
)(
x
,
y
,
z
) =
1
i
a
1
j
`
f
i j
(
x
,
y
)
g
i j
(
z
)+
a
<
i
b
1
j
`
f
i j
(
x
,
z
)
g
i j
(
y
)+
b
<
i
k
1
j
`
f
i j
(
y
,
z
)
g
i j
(
x
)
.
This demonstrates that
slice-rank
(
F
G
)
k
·
`
, which verifies the first claim. For the second claim, we
instead define
f
i
ζ
(
x
,
y
)
:
=
f
i
(
x
,
y
)
G
(
x
′′
,
y
′′
,
ζ
)
,
g
i
ζ
(
z
)
:
=
g
i
(
z
)
δ
ζ
(
z
′′
)
for 1
i
a
,
ζ
Z
′′
,
f
i
ψ
(
x
,
z
)
:
=
f
i
(
x
,
z
)
G
(
x
′′
,
ψ
,
z
′′
)
,
g
i
ψ
(
y
)
:
=
g
i
(
y
)
δ
ψ
(
y
′′
)
for
a
<
i
b
,
ψ
Y
′′
,
and
f
i
ξ
(
y
,
z
)
:
=
f
i
(
y
,
z
)
G
(
ξ
,
y
′′
,
z
′′
)
,
g
i
ξ
(
x
)
:
=
g
i
(
x
)
δ
ξ
(
x
′′
)
for
b
<
i
k
,
ξ
X
′′
,
so that
(
F
G
)(
x
,
y
,
z
) =
1
i
a
ζ
Z
′′
f
i
ζ
(
x
,
y
)
g
i
ζ
(
z
)+
a
<
i
b
ψ
Y
′′
f
i
ψ
(
x
,
z
)
g
i
ψ
(
y
)+
b
<
i
k
ξ
X
′′
f
i
ξ
(
y
,
z
)
g
i
ξ
(
x
)
.
This shows that slice-rank
(
F
G
)
k
·
max
(
|
X
′′
|
,
|
Y
′′
|
,
|
Z
′′
|
)
, 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
:
X
×
Y
×
Z
F
is
unstable
if there exist
1. a basis
{
f
a
}
for the functions X
F
, and similarly bases
{
g
b
:
Y
F
}
and
{
h
c
:
Z
F
}
,
2. weights u
a
,
v
b
,
w
c
R
with arithmetic means u
avg
,
v
avg
,
w
avg
, and
3. coefficients r
a
,
b
,
c
F
such that
F
(
x
,
y
,
z
) =
u
a
+
v
b
+
w
c
<
u
avg
+
v
avg
+
w
avg
r
a
,
b
,
c
f
a
(
x
)
g
b
(
y
)
h
c
(
z
)
.
This terminology comes from geometric invariant theory (when
F
is algebraically closed). Consider
the action of the group
G
=
SL
|
X
|
×
SL
|
Y
|
×
SL
|
Z
|
on the vector space of functions
F
:
X
×
Y
×
Z
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
F
, which is why for
general
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.
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
13
J. B
LASIAK
, T. C
HURCH
, H. C
OHN
, J. A. G
ROCHOW
, E. N
ASLUND
, W. F. S
AWIN
,
AND
C. U
MANS
Definition 4.4.
The
instability
of a function
F
:
X
×
Y
×
Z
F
is the supremum of all
ε
0
such that
there exist bases f
a
,
g
b
,
h
c
, nontrivial weights u
a
,
v
b
,
w
c
R
, and coefficients r
a
,
b
,
c
F
such that
F
(
x
,
y
,
z
) =
u
a
+
v
b
+
w
c
R
r
a
,
b
,
c
f
a
(
x
)
g
b
(
y
)
h
c
(
z
)
(4.4)
where
R
= (
u
avg
+
v
avg
+
w
avg
)
ε
(
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
instability
(
F
)
>
0
. By convention, if for some
F
there is no nonnegative
ε
satisfying the hypotheses of the
definition, we define
instability
(
F
) =
. For readers familiar with the terminology of GIT, we remark
that (assuming
F
is algebraically closed) the function
F
is
semi-stable
if and only if
instability
(
F
)
{−
,
0
}
, and
F
is
stable
if and only if
instability
(
F
) =
. 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)
.
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
R
is invariant under translation. Therefore
if we like we may assume that
u
avg
=
v
avg
=
w
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 instability
(
F
)
.
2.
It does not matter whether we require the weights to lie in
R
,
Q
, or
Z
. Indeed, the supremum
defining instability could be taken over rational
ε
0
without affecting the definition. For any given
rational
ε
, 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
avg
=
v
avg
=
w
avg
=
0.)
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
|
A
|
|
X
|
,
|
B
|
|
Y
|
, and
|
C
|
|
Z
|
, 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
with
u
a
u
a
, then the terms
f
a
g
b
h
c
appearing in
(4.4)
can be replaced with a linear combination of
terms
f
a
g
b
h
c
, still satisfying
u
a
+
v
b
+
w
c
u
a
+
v
b
+
w
c
R
. Repeating this, we may assume that
the set of functions
{
f
a
}
a
A
(with
A
A
) appearing is linearly independent. Then extend this set to a
basis arbitrarily, giving
|
X
|
|
A
|
of these new functions the weight
u
avg
and giving
|
A
|
|
A
|
of them the
weights
{
u
a
}
a
A
\
A
. The other tensor factors are handled similarly.
Recall from
(4.2)
that any function
F
:
X
×
Y
×
Z
F
has
slice-rank
(
F
)
min
(
|
X
|
,
|
Y
|
,
|
Z
|
)
. It turns
out that there is a close relationship between
F
being unstable and this inequality being
strict
. More
D
ISCRETE
A
NALYSIS
, 2017:3, 27pp.
14