# Small sunflowers and the structure of slice rank decompositions

Thomas Karam111Mathematical Institute, University of Oxford. Email:
<EMAIL_ADDRESS>
###### Abstract

Let $d\geq 3$ be an integer. We show that whenever an order-$d$ tensor admits
$d+1$ decompositions according to Tao’s slice rank, if the linear subspaces
spanned by their one-variable functions constitute a sunflower for each choice
of special coordinate, then the tensor admits a decomposition where these
linear subspaces are contained in the centers of these respective sunflowers.
As an application, we deduce that for every nonnegative integer $k$ and every
finite field $\mathbb{F}$ there exists an integer $C(d,k,|\mathbb{F}|)$ such
that every order-$d$ tensor with slice rank $k$ over $\mathbb{F}$ admits at
most $C(d,k,|\mathbb{F}|)$ decompositions with length $k$, up to a class of
transformations that can be easily described.

###### Contents

  1. 1 Introduction
  2. 2 Constructions of different minimal-length slice rank decompositions
  3. 3 Statements of main results
  4. 4 Deduction of the structure theorem on slice rank decompositions
  5. 5 Simpler analogue for tensor rank decompositions
  6. 6 Proof of the theorem on sunflowers for order-$3$ tensors
  7. 7 Proof of the theorem on sunflowers in the general case
  8. 8 Open questions

##  1 Introduction

Throughout we will use the following notations. If $k$ is a positive integer,
then $[k]$ will denote the set $\\{1,\dots,k\\}$ of positive integers up to
$k$. The letter $\mathbb{F}$ will denote a field. All our statements will be
uniform with respect to the choice of the field $\mathbb{F}$, unless we
explicitly write the assumption that the field $\mathbb{F}$ is finite. Even in
that latter case, the dependence will only be on the size of the field
$\mathbb{F}$ and not involve its structure.

We will prove various statements involving order-$d$ tensors, with $d\geq 2$
some integer. Order-$d$ tensors will be taken to be functions
$[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$ for some positive integers
$n_{1},\dots,n_{d}$. All our statements will be uniform in the integers
$n_{1},\dots,n_{d}$ once all other parameters are fixed, and we will use the
integers $n_{1},\dots,n_{d}$ without defining them again in our statements.

Let $k$ be a positive integer, and let $\mathbb{F}$ be a field. If
$M:[n_{1}]\times[n_{2}]\to\mathbb{F}$ is a matrix with rank $k$, then all
decompositions of $M$ as a sum of $k$ rank-$1$ matrices can be obtained from
one another up to changes of bases. In particular, there exist some linear
subspaces $A_{1}\subset\mathbb{F}^{n_{1}},A_{2}\subset\mathbb{F}^{n_{2}}$ such
that if

$M(x,y)=\sum_{i=1}^{k}f_{i}(x)g_{i}(y)$

is a decomposition of $M$, then $\langle f_{1},\dots,f_{k}\rangle=A_{1}$ and
$\langle g_{1},\dots,g_{k}\rangle=A_{2}$. If $\mathbb{F}$ is a finite field,
then it is well-known that the number of decompositions of $M$, where two
decompositions are viewed as the same if their $2k$-tuples
$(f_{1},\dots,f_{k},g_{1},\dots,g_{k})$ are the same, is equal to the number

$(|\mathbb{F}|^{k}-1)(|\mathbb{F}|^{k}-|\mathbb{F}|)\dots(|\mathbb{F}|^{k}-|\mathbb{F}|^{k-1})=|\mathbb{F}|^{k^{2}}\prod_{i=1}^{k}(1-|\mathbb{F}|^{-i})$
(1)

of bases of $\langle f_{1},\dots,f_{k}\rangle$. This number is between
$\omega|\mathbb{F}|^{k^{2}}$ and $|\mathbb{F}|^{k^{2}}$, where $\omega$ is
taken to be the absolute constant

$\prod_{i=1}^{\infty}(1-2^{-i})>0.$

We note that even from a purely qualitative perspective, the analogous
boundedness statement becomes false in general for decompositions of length
even one greater than the rank of $M$. For instance, if $M(x,y)=f(x)g(y)$,
then for any functions $f_{1},f_{2}:[n]\to\mathbb{F}$ satisfying
$f_{2}-f_{1}=f$, we have

$M(x,y)=f_{2}(x)g(y)-f_{1}(x)g(y),$

so as long as the function $f_{2}$ is not fixed, the function $f_{1}$ can be
completely arbitrary.

Our main aim in the present paper is to obtain a comparable statement for the
notion of slice rank on higher-order tensors. We have found the task of
formulating an appropriate corresponding statement to already be challenging,
which is why we shall state it precisely only in Section 3, after going
through several constructions guiding us towards its formulation and ruling
out stronger ones in Section 2. Informally speaking, we will prove that up to
a natural class of transformations, the number of minimal-length slice rank
decompositions of a tensor over a finite field is bounded above in a way that
depends only on the order of the tensor, on its slice rank, and on the size of
the field. As we will also discuss, the bound that we obtain cannot be too far
from the optimal bound. Let us recall the definition of the slice rank and
even before this, the definition of the tensor rank.

######  Definition 1.1.

Let $d\geq 2$ be an integer, and let
$T:[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$ be an order-$d$ tensor. We
say that the _tensor rank_ of $T$, denoted by $\operatorname{tr}T$, is the
smallest nonnegative integer $k$ such that there exist functions
$a_{j,i}:[n_{j}]\to\mathbb{F}$ for each $j\in[d]$ and $i\in[k]$ satisfying

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k}a_{1,i}(x_{1})a_{2,i}(x_{2})\dots
a_{d,i}(x_{d})$ (2)

is satisfied for all $(x_{1},\dots,x_{d})\in[n_{1}]\times\dots\times[n_{d}]$.

We say that an expression such as (2) is a _tensor rank decomposition_ of $T$,
say that the _length_ of the decomposition is the integer $k$, and say that
the decomposition has _minimal length_ if its length is equal to the tensor
rank of $T$.

For every $x\in[n_{1}]\times\dots\times[n_{d}]$ and every $j\in[d]$, we write
$\overline{x_{j}}$ for $(x_{j’})_{j’\in[d]\setminus\\{j\\}}$.

######  Definition 1.2.

Let $d\geq 2$ be an integer, and let
$T:[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$ be an order-$d$ tensor. We
say that the _slice rank_ of $T$, denoted by $\operatorname{sr}T$, is the
smallest nonnegative integer $k$ such that there exist nonnegative integers
$r_{1},\dots,r_{d}$ with $r_{1}+\dots+r_{d}=k$ satisfying one of the following
two equivalent properties.

  1. 1.

There exist matrices $M_{j}:[n_{j}]\times(\prod_{j^{\prime}\neq
j}[n_{j^{\prime}}])\to\mathbb{F}$ with rank at most $r_{j}$ for each $j\in[d]$
such that

$T(x_{1},\dots,x_{d})=\sum_{j=1}^{d}M_{j}(x_{j},\overline{x_{j}})$

is satisfied for all $(x_{1},\dots,x_{d})\in[n_{1}]\times\dots\times[n_{d}]$.

  2. 2.

For each $j\in[d]$ and $i\in[r_{j}]$ there exist some functions
$a_{j,i}:[n_{j}]\to\mathbb{F}$ and $b_{j,i}:\prod_{j^{\prime}\neq
j}[n_{j^{\prime}}]\to\mathbb{F}$ such that

$T(x_{1},\dots,x_{d})=\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})$
(3)

is satisfied for all $(x_{1},\dots,x_{d})\in[n_{1}]\times\dots\times[n_{d}]$.

We say that an expression such as (3) is a _slice rank decomposition_ of $T$,
say that the _length_ of the decomposition is the integer $r_{1}+\dots+r_{d}$,
and say that the decomposition has _minimal length_ if its length is equal to
the slice rank of $T$.

Before going further, let us recall the history of the slice rank and some of
the ways in which it has been studied.

The slice rank was originally introduced by Tao [20] in 2016 as a
reformulation of a central idea from the breakthrough of Croot, Lev and Pach
[6], which led to the solution to the cap-set problem by Ellenberg and
Gijswijt [7]. Since then, the slice rank has been used successfully several
times as a tool to solve combinatorial problems. For instance, it was also
shown by Naslund and Sawin [17] that subsets of the cube $\\{0,1\\}^{n}$
containing no $3$-sunflower are exponentially sparse, and further properties
on the slice rank from Sawin and Tao [19] were later used by Sauermann [18] to
obtain properties guaranteeing the existence of solutions with pairwise
distinct variables to systems of equations in subsets of vector spaces over
finite prime fields which are not exponentially sparse. In another direction,
a variant of the slice rank, the partition rank, was defined by Naslund in
[16], originally to obtain polynomial upper bounds on problems on $k$-right
corners, and was more recently used again by Naslund [15], this time to obtain
exponential lower bounds on the chromatic number of $\mathbb{R}^{n}$ with
multiple forbidden distances.

Although all these works have primarily used the slice rank and the partition
rank as tools, interest in studying them and their basic properties for their
own sake has recently been building up. In the post of Sawin and Tao [19], a
characterisation of the slice rank in terms of coverings in the case of
tensors supported inside an antichain had already been discussed, and this
characterisation later played an important role in the work of Sauermann [18]
that we previously mentioned. Later, it was proved by Gowers [8] that the
slice rank of a direct sum of two tensors is the sum of their slice ranks.

As another example in this direction, the facts that a high-rank matrix must
contain a high-rank submatrix of not too large size and that a matrix with
high rank after every modification of the diagonal must have a high rank
submatrix for which the sets of rows and columns are disjoint were extended by
the author in [11] to a class of notions of rank containing the slice and
partition ranks. Still on the topic of subtensors, it was shown by Briët and
Castro-Silva [4], again for a wide class of notions of rank, that a random
subtensor of a high-rank subtensor must have high rank for some natural way of
choosing the restriction at random, together with some analogous results on
random restrictions of polynomials.

These three results found applications. The first, conditionally on better
bounds, was discussed in [4] as a way to provide an alternate proof of some of
the main results of that paper. The second was used by Gowers and the author
[9] as a key stepping stone to extend to distributions inside $\\{0,1\\}^{n}$
the result of Green and Tao [10] on the equidistribution of high-rank
polynomials over finite prime fields. The third was applied (primarily in the
case of polynomials, although the case of tensors was involved as well) by
Briët, Buhrman, Castro-Silva, and Neumann [5] to prove limitations on the
decoding of corrupted classical and quantum error-correcting codes with
$\mathrm{NC}^{0}[\oplus]$ circuits.

The slice and partition ranks have also been studied using more algebraic
methods. For instance, a “universal” role that the partition rank plays among
notions of rank has been explored by Bik, Draisma and Eggermont [3]. Another
universality result was proved by Kazhdan and Ziegler [12] on the strength of
polynomials (an analogue of the partition rank of tensors), and later led to
an extension by Bik, Danelon, Draisma, and Eggermont [2] to the more abstract
setting of arbitrary polynomial functors.

Let us finally mention that in the case of the tensor rank, much effort has
gone into understanding the notion of identifiability of a tensor, which is
much stronger than the mere boundedness of its set of minimal-length
decompositions that we focus on (primarily in the case of the slice rank) in
the present paper: if $k$ is a nonnegative integer, then a tensor $T$ with
tensor rank $k$ is said to be identifiable if there is only one way of writing
it as a sum

$T_{1}+\dots+T_{k},$

up to permutations of the $k$ tensors $T_{1},\dots,T_{k}$. This area of
research, perhaps started by Kruskal [13] in 1977, is still very active. A
recent paper [1] of Ballico, Bernardi and Santarsiero contains, among other
interesting things, a wealth of references on identifiability.

We now define some more notations which we shall use throughout the paper. Let
$d\geq 2$ be an integer. If $x$ is an element of
$[n_{1}]\times\dots\times[n_{d}]$ and $J$ is a subset of $[d]$, then we shall
write $x(J)$ for the restriction of $x$ to its coordinates in $J$, that is,
for the element of $\prod_{j\in J}[n_{j}]$ defined by $x(J)_{j}=x_{j}$ for
every $j\in J$. If $a,a^{\prime}:[n_{j}]\to\mathbb{F}$ are functions for some
$j\in[d]$, then we write $a.a^{\prime}$ for the element of $\mathbb{F}$
defined by

$\sum_{x_{j}\in[n_{j}]}a(x_{j})a^{\prime}(x_{j}).$

More generally, if $J^{\prime}\subset J$ are non-empty subsets of $[d]$, and
$U:\prod_{j\in J}[n_{j}]\to\mathbb{F}$, $U^{\prime}:\prod_{j\in
J^{\prime}}[n_{j}]\to\mathbb{F}$ are functions, then $U^{\prime}.U:\prod_{j\in
J\setminus J^{\prime}}[n_{j}]\to\mathbb{F}$ will denote the function (or
rather element of $\mathbb{F}$ if $J^{\prime}=J$) defined by

$(U^{\prime}.U)(x(J\setminus J^{\prime}))=\sum_{x(J^{\prime})\in\prod_{j\in
J^{\prime}}[n_{j}]}U^{\prime}(x(J^{\prime}))U(x(J))$

for all $x(J\setminus J^{\prime})$. If $s$ is a positive integer, and
$j_{1},\dots,j_{s}$ are pairwise distinct elements of $[d]$, then we write
$\overline{x_{j_{1}},\dots,x_{j_{s}}}$ for
$x([d]\setminus\\{j_{1},\dots,j_{s}\\})$.

We will repeatedly use the following observations. If a decomposition (3) has
minimal length, then for every $j\in[d]$ its functions $a_{j,i}$ with
$i\in[r_{j}]$ are linearly independent. Even if the decomposition does not
have minimal length, each of the $d$ parts of the decomposition and hence the
whole decomposition can always be written such that these functions are
linearly independent, and we will always assume this to be the case whenever
we write any slice rank decomposition of any tensor.

It follows from Gaussian elimination that if for some $j\in[d]$ and some
integer $r\geq 1$ the functions $a_{1},\dots,a_{r}:[n_{j}]\to\mathbb{F}$ are
linearly independent, then there exist functions
$a_{1}^{*},\dots,a_{r}^{*}:[n_{j}]\to\mathbb{F}$ satisfying
$a_{i}^{*}.a_{i^{\prime}}=1_{i=i^{\prime}}$ for any $i,i^{\prime}\in[r]$. We
will refer to the family $(a_{1}^{*},\dots,a_{r}^{*})$ as a family of _dual
functions_ to the family of functions $(a_{1},\dots,a_{r})$. More generally,
if for some non-empty subset $J$ of $[d]$ and some integers $r_{j}\geq 1$ for
each $j\in J$ the functions $a_{j,1},\dots,a_{j,r_{j}}$ are linearly
independent for every $j\in J$, then the tensor products

$\otimes_{j\in J}a_{j,i_{j}}:\prod_{j\in J}[n_{j}]\to\mathbb{F}$

with $(i_{j})_{j\in J}$ are linearly independent, and furthermore

$(\otimes_{j\in J}a_{j,i_{j}}^{*}).(\otimes_{j\in
J}a_{j,i_{j}^{\prime}})=\prod_{j\in J}1_{i_{j}=i_{j}’}$

is equal to $1$ if $i_{j}=i_{j}’$ for every $j\in J$, and to $0$ otherwise.

The remainder of the paper is organised as follows. In Section 2 we describe
several rather systematic ways in which we may construct several slice rank
decompositions of the same tensor. Against these constructions we then
formulate in Section 3 our result on the structure of slice rank
decompositions, Theorem 3.5, together with two other results on slice rank
decompositions, Proposition 3.2 and Theorem 3.3, from which Theorem 3.5 can be
deduced and which also appear to be of intrinsic interest. This deduction is
then performed in Section 4. In Section 5, which is independent from the other
sections, we give a simple proof of a statement showing that in the case of
the tensor rank, the result on decompositions of matrices extends in a rather
optimistic way. In Section 6 we then prove Proposition 3.2 and Theorem 3.3 in
the case of order-$3$ tensors, and in Section 7 we prove them in the general
case of order-$d$ tensors for every $d\geq 3$. Finally, in Section 8 we
conclude by mentioning some questions which remain open.

Most of the underlying basic ideas involved in our proofs of the general $d$
case already arise for $d=3$, and these are discussed in more detail in the
$d=3$ case, which is why Section 6 is slightly lengthier than Section 7
despite proving a less general result.

## Acknowledgements

The author thanks Timothy Gowers for discussions around Gowers’s paper [8]
that attracted the author’s attention to the idea of slice rank decompositions
of the zero tensor, which was involved there and plays a role in the present
paper as well. The author also thanks Jordan Ellenberg for encouraging him to
prove results stating that even if the analogue of a “perfect” property which
holds for the matrix rank does not hold for other notions of rank on tensors,
some appropriate weakening of it does.

##  2 Constructions of different minimal-length slice rank decompositions

We next go over five ways in which several minimal-length slice rank
decompositions can arise for the same tensor.

######  Construction 1.

_Since it is possible to obtain new decompositions of matrices using a change
of basis, it is possible to obtain new decompositions of $T$ from an existing
decomposition by rewriting the decompositions of any of the individual
matrices $M_{1},\dots,M_{d}$ while leaving the $d$-tuple $(M_{1},\dots,M_{d})$
unchanged._

However, this $d$-tuple is not unique in general, and there are other ways of
obtaining new decompositions, which brings us to the remaining four
constructions.

######  Construction 2.

_To see that the matrices $M_{1},\dots,M_{d}$ are not individually determined,
consider any tensor $T$ for which the slice rank and tensor rank are equal to
some common positive integer $k$. Let_

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k}a_{1,1}(x_{1})\dots a_{d,1}(x_{d})$

_be a tensor rank decomposition of $T$ with length $k$. Then for every
partition $\\{I_{1},\dots,I_{d}\\}$ of $[k]$ into $d$ sets $I_{1},\dots,I_{d}$
that are possibly empty, the decomposition_

$T(x_{1},\dots,x_{d})=\sum_{j=1}^{d}\sum_{i\in
I_{j}}a_{j,i}(x_{i})(\prod_{j’\neq j}a_{j’,i}(x_{j’}))$

_is a slice-rank decomposition of $T$ with length $k$._

_These tensors exist, since for instance the “identity” tensor
$I_{d,k}:[k]^{d}\to\mathbb{F}$ defined by_

$I_{d,k}(x_{1},\dots,x_{d})=\sum_{i=1}^{k}1_{x_{1}=i}\dots 1_{x_{d}=i}$

_was shown by Tao ([20], Lemma 1) to have slice rank $k$. Since the tensor
rank of this tensor is at most $k$ by definition, and since the slice rank is
always at most the tensor rank, it follows that both ranks are equal for this
tensor._

_For instance, in the case $d=3$, we obtain a slice rank decomposition_

$I_{3,k}(x,y,z)=\sum_{i\in I_{1}}1_{x=i}1_{y=z=i}+\sum_{i\in
I_{2}}1_{y=i}1_{x=z=i}+\sum_{i\in I_{3}}1_{z=i}1_{x=y=i}$

_for every tripartition $\\{I_{1},I_{2},I_{3}\\}$ of $[k]$ (again, with
$I_{1},I_{2},I_{3}$ allowed to be empty)._

As we can see from Construction 2 not even the sizes of the three parts of the
decomposition are determined in general. One comment that can nonetheless be
made about Construction 2 is that although the matrices $M_{1},\dots,M_{d}$
are not always the same, the set of all summands is always the same set

$\\{1_{x_{1}=i}\dots 1_{x_{d}=i}:i\in[k]\\}.$

However, there is another class of examples where this usually does not hold,
even up to changes of bases in the matrices $M_{1},\dots,M_{d}$, and which
even encompasses typical tensors.

######  Construction 3.

_A tensor $T:[k]^{d}\to\mathbb{F}$ can in particular be written in $d$
different ways as a sum of its $(d-1)$-variable slices of each type, i.e. be
decomposed as_

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k}1_{x_{j}=i}T(x_{1},\dots,x_{j-1},i,x_{j+1},\dots,x_{d}).$

_If $T$ has slice rank $k$, then these $d$ decompositions are each minimal-
length decompositions. If the field $\mathbb{F}$ is finite, then the number of
tensors $[k]^{d}\to\mathbb{F}$ with slice rank at most $k-1$ is at most_

$k^{d}|\mathbb{F}|^{(k-1)(k^{d-1}+k)}=k^{d}|\mathbb{F}|^{k^{d}-k^{d-1}+k^{2}-k}.$

_Provided that $d\geq 3$, we can crudely bound this number above by_

$(k^{d}/|\mathbb{F}|^{k})|\mathbb{F}|^{k^{d}}.$

_The ratio is less than $1$ for $k$ large enough, and tends to $0$ as $k$
tends to infinity, which shows that random tensors have slice rank $k$. Unlike
in the $I_{d,k}$ example, the sets of $k$ summands involved in each of the $d$
decompositions are in particular usually very different._

######  Construction 4.

_Provided that a tensor $T$ with slice rank $k$ does have a decomposition with
length $k$ that does not have all its terms of the same of the three types,
there is a systematic way of changing some of the components of the
decomposition and obtain another decomposition with length $k$. In the $d=3$
case, for instance, if_

$T(x,y,z)=a(x)b(y,z)+c(y)d(x,z),$

_then for any function $e:[n_{3}]\to\mathbb{F}$, the functions
$b^{\prime}=b+c\otimes e$ and $d^{\prime}=d-a\otimes e$ satisfy_

$T(x,y,z)=a(x)b^{\prime}(y,z)+c(y)d^{\prime}(x,z).$

_Because the function $e$ is arbitrary, and in particular there are
unboundedly many such functions as $n$ tends to infinity, it is never true,
for any integers $d\geq 3$, $k\geq 2$ and any field $\mathbb{F}$, that every
order-$d$ tensor with slice rank $k$ has a number of minimal-length
decompositions which is bounded above by some function of $d,k,\mathbb{F}$. A
boundedness statement of this kind may only hold up to this type of
transformation._

_If $T$ is an order-$3$ tensor with a more general slice rank decomposition_

$T(x,y,z)=\sum_{i=1}^{r}a_{i}(x)b_{i}(y,z)+\sum_{j=1}^{s}c_{j}(x)d_{j}(y,z)+\sum_{k=1}^{t}e_{k}(z)f_{k}(x,y)$
(4)

_is a decomposition of $T$, then whenever $(i,j)\in[r]\times[s]$ and
$e:[n_{3}]\to\mathbb{F}$ is a function, replacing $b_{i}$ and $d_{j}$ by
respectively_

$b_{i}+c_{j}\otimes e\text{ and }d_{j}-a_{i}\otimes e$

_leads to a new decomposition of $T$._

_Returning to the case of general $d\geq 3$, if_

$T(x_{1},\dots,x_{d})=a_{1}(x_{1})b_{1}(\overline{x_{1}})+\dots+a_{d}(x_{d})b_{d}(\overline{x_{d}})$

_is a slice rank decomposition of $T$, then for any function
$c:[n_{3}]\times\dots\times[n_{d}]$, replacing $b_{1}$ and $b_{2}$ by
respectively_

$b_{1}+a_{2}\otimes c\text{ and }b_{2}-a_{1}\otimes c$

_leads to a new decomposition of $T$._

_Combining both axes of generality, if_

$T(x_{1},\dots,x_{d})=\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})$

_is a slice rank decomposition of $T$, $c:[n_{3}]\times\dots\times[n_{d}]$ is
a function, and $i_{1}\in[r_{1}]$, $i_{2}\in[r_{2}]$ are two indices, then
replacing $b_{1,i_{1}}$ and $b_{2,i_{2}}$ by respectively_

$b_{1,i_{1}}+a_{2,i_{2}}\otimes c\text{ and }b_{2,i_{2}}-a_{1,i_{1}}\otimes c$

_leads to a new decomposition of $T$. The roles of either of the first two
coordinates may of course be exchanged with those of the other coordinates._

######  Construction 5.

_We can generalise Construction 4 further. Let us begin by describing a
variant of Construction 4, in the simplest setting. If we have the
decomposition_

$T(x,y,z)=a(x)b(y,z)+c(y)d(x,z)+e(z)f(x,y),$

_then the functions_

$\displaystyle b’$ $\displaystyle=b+\lambda_{1}c\otimes e$ $\displaystyle d’$
$\displaystyle=d+\lambda_{2}a\otimes e$ $\displaystyle f’$
$\displaystyle=f+\lambda_{3}a\otimes c$

_for some $\lambda_{1},\lambda_{2},\lambda_{3}\in\mathbb{F}$ adding up to $0$
satisfy_

$T(x,y,z)=a(x)b’(y,z)+c(y)d’(x,z)+e(z)f’(x,y).$

_We note that this transformation reduces to successively applying three of
the transformations from Construction 4, since we can always find
$\mu_{12,1}$, $\mu_{12,2}$, $\mu_{13,1}$, $\mu_{13,3}$, $\mu_{23,2}$,
$\mu_{23,3}\in\mathbb{F}$ satisfying_

$\displaystyle\mu_{12,1}+\mu_{12,2}=0$ $\displaystyle\text{
}\lambda_{1}=\mu_{12,1}+\mu_{13,1}$ $\displaystyle\mu_{13,1}+\mu_{13,3}=0$
$\displaystyle\text{ }\lambda_{2}=\mu_{12,2}+\mu_{23,2}$
$\displaystyle\mu_{23,2}+\mu_{23,3}=0$ $\displaystyle\text{
}\lambda_{3}=\mu_{13,3}+\mu_{23,3}.$

_We may for instance choose $\mu_{13,1}$ and $\mu_{13,3}$ to be zero, and
$\mu_{12,1},\mu_{12,2},\mu_{23,2},\mu_{23,3}$ are then uniquely determined._

_If ( 4) is a more general decomposition of an order-$3$ tensor $T$, then
whenever $(i,j,k)\in[r]\times[s]\times[t]$ and
$\lambda_{1},\lambda_{2},\lambda_{3}\in\mathbb{F}$ satisfy_

$\lambda_{1}+\lambda_{2}+\lambda_{3}=0,$

_replacing $b_{i},d_{j},f_{k}$ by respectively_

$\displaystyle b_{i}$ $\displaystyle+\lambda_{1}c_{j}\otimes e_{k}$
$\displaystyle d_{j}$ $\displaystyle+\lambda_{2}a_{i}\otimes e_{k}$
$\displaystyle f_{k}$ $\displaystyle+\lambda_{3}a_{i}\otimes c_{j}$

_leads to a new decomposition of $T$._

_In the case of general $d\geq 3$, if (3) is a decomposition of $T$, then we
can choose some index $i_{j}$ for each $j\in[d]$, and choose some
$\lambda_{1},\dots\lambda_{d}\in\mathbb{F}$ satisfying_

$\lambda_{1}+\dots+\lambda_{d}=0.$

_Replacing the functions $b_{j,i_{j}}$ for each $j\in[d]$ by the functions_

$b_{j,i_{j}}^{\prime}(\overline{x_{j}})=b_{j,i_{j}}(\overline{x_{j}})+\lambda_{j}a_{1,i_{1}}(x_{1})\dots
a_{j-1,i_{j-1}}(x_{j-1})a_{j+1,i_{j+1}}(x_{j+1})\dots a_{d,i_{d}}(x_{d})$

_then provides a new decomposition of $T$._

_However, we can extend this class of transformations yet further: we can
choose successively a subset $J$ of $[d]$ with size at least $2$, some indices
$i_{j}\in[r_{j}]$ for each $j\in J$, some functions
$c_{j}:\prod_{j\in[d]\setminus J}[n_{j}]\to\mathbb{F}$ for each $j\in J$
(instead taken to be a elements of $\mathbb{F}$ if $J=[d]$) satisfying_

$\sum_{j\in J}c_{j}=0,$

_and replace for each $j\in J$ the function $b_{j,i_{j}}$ by the function
$b_{j,i_{j}}^{\prime}$ defined by_

$b_{j,i_{j}}^{\prime}(\overline{x_{j}})=b_{j,i_{j}}(\overline{x_{j}})+(\prod_{j^{\prime}\in
J\setminus\\{j\\}}a_{j^{\prime},i_{j^{\prime}}}(x_{j^{\prime}}))c_{j}(x([d]\setminus
J)).$

_This yet again provides a new decomposition of $T$._

_Just as in the case of order- $3$ tensors, for general $d\geq 3$ and
$2\leq|J|\leq d$ doing this transformation ultimately reduces to successively
applying transformations from Construction 4 several times. For instance,
writing $J=\\{j_{1},\dots,j_{s}\\}$, there is a unique way of performing them
while only using the $s-1$ pairs of indices
$\\{j_{1},j_{2}\\},\dots,\\{j_{s-1},j_{s}\\}$. Nonetheless, we single out
Construction 5 separately, as in our proofs we will think of the corresponding
transformation as a single transformation rather than as a succession of
several transformations from Construction 4._

Any of the five constructions that we have just described may be combined
together: as shown by Gowers in [8], the slice rank of a block diagonal tensor
is equal to the sum of the slice ranks of the diagonal blocks, so putting
together minimal-length decompositions of the five examples each respectively
corresponding to a tensor $T_{1},\dots,T_{5}$ leads to a minimal-length
decomposition of the diagonal sum

$T_{1}\oplus\dots\oplus T_{5},$

and this is still the case after modifying any of the decompositions of
$T_{1},\dots,T_{5}$ using Constructions 1 to 5 respectively.

##  3 Statements of main results

The previous section was devoted to constructions illustrating how a variety
of different slice rank decompositions may arise for the same tensor. In the
present section we describe our main results, which will be in the converse
direction and show that to some extent, the set of minimal-length slice rank
decompositions of the same tensor cannot be too rich. We will do so separately
for the $(d-1)$-variable functions and for the one-variable functions of
minimal-length decompositions. We will go through the following three steps,
corresponding respectively to the proofs of the three main results of this
paper, Proposition 3.2, Theorem 3.3, and Theorem 3.5.

  1. 1.

We will begin by showing that if two decompositions have the same one-variable
functions, then any differences between the two decompositions arise from
Construction 4 and Construction 5.

  2. 2.

After this, we will show a statement which in particular implies that no more
than $d$ decompositions can have their sets of one-variable functions in the
$j$th coordinate be jointly linearly independent for every $j\in[d]$
simultaneously.

  3. 3.

This result will allow us to deduce that, in the finite field case, there are
only a bounded number of possibilities for the one-variable functions, with a
bound depending only on the order of the tensor, on its slice rank, and on the
size of the finite field.

In summary, we can partition the decompositions according to their one-
variable functions in a bounded number of sets, and inside each of these sets
we can then completely describe the possibilities for the $(d-1)$-variable
functions once we know what these are for one of the decompositions from the
set.

It may seem slightly surprising that we begin with and use fewer steps to
obtain a satisfactory result with the $(d-1)$-variable functions than we do
with the one-variable functions. That this is the case is due to the fact that
whenever we compare two decompositions in the part of our argument studying
the former, we always assume that the one-variable functions are the same,
whereas while studying the latter we do not make any assumption on the
$(d-1)$-variable functions.

Let us now go through these steps more formally. Although the following
definition is a bit long, all that it describes is differences between the
original and the new $(d-1)$-variable functions before and after successively
applying Construction 4 and Construction 5 as much as can be done. If $J$ is a
subset of $[d]$, then for simplicity of notation we will denote a sequence
$(i_{j})_{j\in J}$ by $i_{J}$.

######  Definition 3.1.

Let $d\geq 3$ be an integer, and let $r_{1},\dots,r_{d}$ be nonnegative
integers. We say that a decomposition

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{i}(x_{j})b_{i}(\overline{x_{j}})$

is in _zero form_ if there exist functions

$c_{J,j,i,i_{J\setminus\\{j\\}}}:\prod_{j^{\prime\prime}\in[d]\setminus
J}[n_{j^{\prime\prime}}]\to\mathbb{F}$

(instead taken to be elements of $\mathbb{F}$ if $J=[d]$) for every subset
$J\subset[d]$ with $2\leq|J|\leq d$, every $j\in[d]$, every $i\in[r_{j}]$ and
every $i_{J\setminus\\{j\\}}$ satisfying the following two properties.

  1. 1.

For every $j\in[d]$ and every $i\in[r_{j}]$ we can write

$b_{j,i}(\overline{x_{j}})=\sum_{J\subset[d]:j\in
J}\sum_{i_{J\setminus\\{j\\}}}\left(\prod_{j^{\prime}\in
J\setminus\\{j\\}}a_{j^{\prime},i_{j^{\prime}}}(x_{j^{\prime}})\right)c_{J,j,i,i_{J\setminus\\{j\\}}}(x([d]\setminus
J)).$

  2. 2.

For every $J\subset[d]$ with $2\leq|J|\leq d$ and every
$(i_{j^{\prime}})_{j^{\prime}\in J}$, we obtain a sum of $0$ whenever we take
the sum over all functions $c_{J,j,i,i_{J\setminus\\{j\\}}}$ where the
sequence $i_{J\setminus\\{j\\}}$ completed to a sequence indexed by $J$ by
introducing the additional term $i_{j}=i$ is equal to
$(i_{j^{\prime}})_{j^{\prime}\in J}$.

Given this definition, the first component of our results can be easily
formulated. It can be checked that any decomposition that is in zero form adds
up to the zero tensor, and our first result is a converse of that. We assume
as usual that the functions $a_{j,i}$ of decompositions are linearly
independent for each $j\in[d]$.

######  Proposition 3.2.

Let $d\geq 3$ be an integer, and let $r_{1},\dots,r_{d}$ be nonnegative
integers. If a decomposition

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})$

is equal to the zero tensor, then it is in zero form.

The next theorem corresponds to the second step of the argument that we
described at the beginning of this section. The key structure that we will use
is that of sunflowers in a linear algebra sense: if $A^{0},A^{1},\dots,A^{h}$
are linear subspaces which are all jointly in direct sum for some positive
integer $h$, then we say that the linear subspaces

$A^{0}\oplus A^{1},\dots,A^{0}\oplus A^{h}$

constitute a _sunflower_ with _center_ $A^{0}$ and _petals_
$A^{1},\dots,A^{h}$. Given bases of the linear subspaces
$A^{0},A^{1},\dots,A^{h}$, we will refer to a basis of $A^{0}$ as a _basis of
center functions_ and to bases of $A^{1},\dots,A^{h}$ as _bases of petal
functions_.

What we will show is that if we can find $d+1$ decompositions $\theta$ of the
same tensor (not necessarily with minimal length) where for each $j\in[d]$ the
linear subspaces spanned by the one-variable functions $a_{j,i}$ coming from
the respective decompositions constitute a sunflower in the sense that we have
just described, then the tensor has a slice rank decomposition where for every
$j\in[d]$ the one-variable functions $a_{j,i}$ all belong to the center of the
sunflower, and hence in particular the tensor has slice rank at most

$\dim A_{1}^{0}+\dots+\dim A_{d}^{0}.$

We state this result for any $d\geq 2$: the $d=2$ case is relevant since as we
shall discuss later in Section 6, it will be used in the proof of the $d=3$
case.

######  Theorem 3.3.

Let $d\geq 2$ be an integer, let $\mathbb{F}$ be a field, and let $T$ be an
order-$d$ tensor over $\mathbb{F}$. Let $r_{1}^{0},\dots,r_{d}^{0}$ be
nonnegative integers, and let $a_{j,i}^{0}:[n_{j}]\to\mathbb{F}$ be one-
variable functions for every $j\in[d]$ and every $i\in[r_{j}^{0}]$. Let $h>d$
be an integer, and assume that the following two conditions are satisfied.

  1. 1.

For every $\theta\in[h]$ there exist nonnegative integers
$r_{1}^{\theta},\dots,r_{d}^{\theta}$ and a decomposition of $T$ of the type

$\sum_{j=1}^{d}\left(\sum_{i=1}^{r_{j}^{0}}a_{j,i}^{0}(x_{j})b_{j,i}^{0,\theta}(\overline{x_{j}})+\sum_{i=1}^{r_{j}^{\theta}}a_{j,i}^{\theta}(x_{j})b_{j,i}^{\theta}(\overline{x_{j}})\right)$

for some one-variable functions $a_{j,i}^{\theta},[n_{j}]\to\mathbb{F}$ and
for some $(d-1)$-variable functions
$b_{j,i}^{0,\theta},b_{j,i}^{\theta}:\prod_{j^{\prime}\neq
j}[n_{j^{\prime}}]\to\mathbb{F}$.

  2. 2.

For each $j\in[d]$ the one-variable functions

$a_{j,1}^{0},\dots,a_{j,r_{j}^{0}}^{0},a_{j,1}^{1},\dots,a_{j,r_{j}^{1}}^{1},\dots,a_{j,1}^{h},\dots,a_{j,r_{j}^{h}}^{h}:[n_{j}]\to\mathbb{F}$

are linearly independent.

Then there exist $(d-1)$-variable functions $b_{j,i}^{0}:\prod_{j^{\prime}\neq
j}[n_{j^{\prime}}]\to\mathbb{F}$ such that

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}^{0}}a_{j,i}^{0}(x_{j})b_{j,i}^{0}(\overline{x_{j}})$

is a decomposition of $T$ and in particular

$\operatorname{sr}T\leq r_{1}^{0}+\dots+r_{d}^{0}.$

We stress that in the assumptions of Theorem 3.3 the decompositions are not
required to have minimal length. The inequality $h>d$ is optimal, as can be
seen from either Construction 2 or Construction 3.

We note that there is a large class of examples where the subspaces
$A_{1}^{\theta},\dots,A_{d}^{\theta}$ are respectively the same for every
minimal-length decomposition of $T$. Informally, this is the class of
order-$d$ tensors which admit a minimal-length slice rank decomposition where
the $(d-1)$-variable functions of each kind are sufficiently separated with
respect to the slice rank of order-$(d-1)$ tensors.

######  Proposition 3.4.

Let $d\geq 3$, $k\geq 1$ be integers, and let $T$ be an order-$d$ tensor with
slice rank $k$. Assume that there exist nonnegative integers
$r_{1},\dots,r_{d}$ satisfying

$r_{1}+\dots+r_{d}=k,$

and a decomposition

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})$

of $T$ such that for every $j\in[d]$ the order-$(d-1)$ tensors
$b_{j,1},\dots,b_{j,r_{j}}:\prod_{j’\neq j}[n_{j}]\to\mathbb{F}$ satisfy

$\operatorname{sr}\left(\sum_{i=1}^{r_{j}}\lambda_{i}b_{j,i}\right)\geq 2k$
(5)

for every
$(\lambda_{1},\dots,\lambda_{r_{j}})\in\mathbb{F}^{r_{j}}\setminus\\{0\\}$ and
for every $j\in[d]$. Then the linear subspaces

$A_{j}=\langle a_{j,i}:i\in[r_{j}]\rangle$

with $j\in[d]$ are such that whenever

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}’}a_{j,i}’(x_{j})b_{j,i}’(\overline{x_{j}})$

is a slice rank decomposition of $T$ satisfying $r_{1}’+\dots+r_{d}’=k$, we
have $r_{j}’=r_{j}$ and

$A_{j}=\langle a_{j,i}^{\prime}:i\in[r_{j}]\rangle$

for every $j\in[d]$.

###### Proof.

For every $j\in[d]$ we write $A_{j}$ and $A_{j}^{\prime}$ for the linear
subspaces

$\langle a_{j,1},\dots,a_{j,r_{j}}\rangle\text{ and }\langle
a_{j,1},\dots,a_{j,r_{j}}\rangle$

respectively. If for some $j_{0}\in[d]$ the subspace $A_{j_{0}}^{\prime}$ does
not contain $A_{j_{0}}$, then there exists a function
$u:[n_{j_{0}}]\to\mathbb{F}$ such that $u.a=0$ for every $a\in
A_{j_{0}}^{\prime}$ but such that $u.a\neq 0$ for some $a\in A_{j_{0}}$.
Applying $u$ to both sides of the equality

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})=\sum_{j=1}^{d}\sum_{i=1}^{r_{j}^{\prime}}a_{j,i}^{\prime}(x_{j})b_{j,i}^{\prime}(\overline{x_{j}})$

we obtain

$\sum_{i=1}^{r_{j_{0}}}(u.a_{j_{0},i})b_{j_{0},i}(\overline{x_{j_{0}}})+\sum_{j\neq
j_{0}}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})(u.b_{j,i})(\overline{x_{j_{0}},x_{j}})=\sum_{j\neq
j_{0}}\sum_{i=1}^{r_{j}^{\prime}}a_{j,i}^{\prime}(x_{j})(u.b_{j,i}^{\prime})(\overline{x_{j_{0}},x_{j}}).$

Our assumption (5) shows that

$(u.a_{j_{0},1},\dots,u.a_{j_{0},r_{j_{0}}})\neq 0$

and hence that the first sum of the left-hand side has slice rank at least
$2k$. All inner summands of all other sums each have slice rank at most $1$,
and there are at most $2k-1$ such summands, which is a contradiction.
Therefore, $A_{j}^{\prime}$ contains $A_{j}$ for every $j\in[d]$. Since

$r_{1}+\dots+r_{d}=k=r_{1}^{\prime}+\dots+r_{d}^{\prime},$

we have $A_{j}^{\prime}=A_{j}$ for every $j\in[d]$. ∎

From Proposition 3.2 and Theorem 3.3 we then deduce our theorem on the
structure of minimal-length slice rank decompositions of tensors, which we now
state.

######  Theorem 3.5.

Let $d\geq 3$, $k\geq 1$ be integers, let $\mathbb{F}$ be a field, and let $T$
be an order-$d$ tensor over $\mathbb{F}$ and with slice rank equal to $k$.
Then we have the following.

  1. 1.

If the field $\mathbb{F}$ is finite, then there exists a set $\mathcal{A}$ of
$d$-tuples $(W_{1},\dots,W_{d})$ of linear subspaces of
$\mathbb{F}^{n_{1}},\dots,\mathbb{F}^{n_{d}}$ respectively, with size
$|\mathcal{A}|\leq d^{k}|\mathbb{F}|^{dk^{2}}$, such that if
$r_{1},\dots,r_{d}$ are nonnegative integers satisfying

$r_{1}+\dots+r_{d}=k$

and $a_{j,i}:[n_{j}]\to\mathbb{F}$ with $j\in[d]$ and $i\in[r_{j}]$ are
functions satisfying

$T(x_{1},\dots,x_{d})=\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})$

for some $(d-1)$-variable functions $b_{j,i}:\prod_{j^{\prime}\neq
j}[n_{j^{\prime}}]\to\mathbb{F}$, then

$(\langle a_{1,1},\dots,a_{1,r_{1}}\rangle,\dots,\langle
a_{d,1},\dots,a_{d,r_{d}}\rangle)\in\mathcal{A}.$

In particular, there are at most $d^{k}|\mathbb{F}|^{2dk^{2}}$ possibilities
in total for

$((r_{1},\dots,r_{d}),(a_{1,1},\dots,a_{1,r_{1}}),\dots,(a_{d,1},\dots,a_{d,r_{d}})).$

  2. 2.

For any field $\mathbb{F}$, if two decompositions

$T(x_{1},\dots,x_{d})=\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}^{1}(\overline{x_{j}})=\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}^{2}(\overline{x_{j}})$
(6)

of $T$ have the same one-variable functions $a_{j,i}$, then the decomposition

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})(b_{j,i}^{2}-b_{j,i}^{1})(\overline{x_{j}})$
(7)

is in zero form.

In the second item of Theorem 3.5, the decompositions need not be assumed to
have minimal length, even if like the first item it was conceived primarily
with this case in mind. The following example shows that the exponents in the
two bounds from the first item of Theorem 3.5 can only be away from the
optimal bounds by factors which are linear in $d$, uniformly in $k$ and
$\mathbb{F}$.

######  Example 3.6.

_Let $d\geq 4$ be an integer, let $r$ be a positive integer, let
$n_{1},\dots,n_{d}$ be large integers compared to $r$, let
$M:[n_{1}]\times[n_{2}]\to\mathbb{F}$ be a rank-$2r$ matrix with a
decomposition_

$M(x_{1},x_{2})=\sum_{i=1}^{2r}a_{i}^{1}(x)a_{i}^{2}(y),$

_let $c:[n_{3}]\times\dots\times[n_{d}]\to\mathbb{F}$ be a function, and let
$T$ be the order-$d$ tensor defined by_

$T(x_{1},\dots,x_{d})=M(x_{1},x_{2})c(x_{3},\dots,x_{d}).$

_If the function $c$ has slice rank at least 2r as an order-(d-2) tensor then
the tensor $T$ has slice rank $2r$ (if instead $d=3$, then $T$ always has
slice rank at most $1$). Then there are at least $\omega|\mathbb{F}|^{r^{2}}$
possibilities for the linear subspace $\langle
a_{1}^{1},\dots,a_{r}^{1}\rangle$._

###### Proof.

The decompositions

$\sum_{i=1}^{r}a_{i}^{1}(x_{1})(a_{i}^{2}c)(x_{2},x_{3},\dots,x_{d})+\sum_{i=r+1}^{2r}a_{i}^{2}(x_{2})(a_{i}^{1}c)(x_{1},x_{3},\dots,x_{d})$

are decompositions of $T$ with length $2r$, and the linear subspace $\langle
a_{1}^{1},\dots,a_{r}^{1}\rangle$ can be any dimension-$r$ linear subspace of
$\langle a_{1}^{1},\dots,a_{2r}^{1}\rangle$. In turn, there are at least at
least

$\omega|\mathbb{F}|^{(2r)^{2}}/|\mathbb{F}|^{2r^{2}}|\mathbb{F}|^{r^{2}}$

possibilities for this linear subspace, which provides the desired bound. It
hence suffices to check that these decompositions indeed have minimal length,
in other words that T has slice rank no less than 2r. Assume for contradiction
that

$\sum_{i=1}^{r_{1}}a_{1,i}(x_{1})b_{1,i}(\overline{x_{1}})+\sum_{i=1}^{r_{2}}a_{2,i}(x_{2})b_{2,i}(\overline{x_{2}})+\sum_{j=3}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})$

is a slice rank decomposition of $T$ satisfying

$r_{1}+r_{2}+r_{3}+\dots+r_{d}<2r.$

The linear subspace

$U=\\{a_{1}^{*}\in\mathbb{F}^{n_{1}}:a_{1}^{*}.a_{1,1}=0,\dots,a_{1}^{*}.a_{1,r_{1}}=0\\}$

has dimension $n-r_{1}$, so since $M$ has rank $2r$, the linear subspace

$\\{a_{1}^{*}.M:a_{1}^{*}\in U\\}$

has dimension at least $2r-r_{1}$, so is not contained inside the linear
subspace $\langle a_{2,1},\dots,a_{2,r_{2}}\rangle$. Therefore, we can find
$a_{1}^{*}\in U$ and an element $a_{2}^{*}$ of

$\\{a_{2}^{*}\in\mathbb{F}^{n_{2}}:a_{2}^{*}.a_{2,1}=0,\dots,a_{2}^{*}.a_{2,r_{2}}=0\\}$

which furthermore satisfies

$(a_{1}^{*}\otimes a_{2}^{*}).M=a_{2}^{*}.(a_{1}^{*}.M)\neq 0.$

Applying $a_{1}^{*}\otimes a_{2}^{*}$ to the original decomposition of $T$
then provides a slice rank decomposition

$\lambda
c(x_{3},\dots,x_{d})=\sum_{j=3}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})((a_{1}^{*}\otimes
a_{2}^{*}).b_{j,i})(\overline{x_{1},x_{2},x_{j}})$

for some $\lambda\neq 0$, which contradicts that $\operatorname{sr}c\geq 2r$.∎

##  4 Deduction of the structure theorem on slice rank decompositions

In this section we deduce Theorem 3.5 from Proposition 3.2 and Theorem 3.3.

###### Proof of Theorem 3.5.

Let us begin by proving the second item. Because the two decompositions (6)
are decompositions of the same tensor, their difference (7) is equal to the
zero tensor, so it follows from Proposition 3.2 that the decomposition (7) is
in zero form.

There remains to prove the first item. Let $k$ be the slice rank of $T$. If
$k=0$ then we are done, so let us assume $k\geq 1$. We consider an arbitrary
set of minimal-length decompositions

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}^{\theta}}a_{j,i}^{\theta}(x_{j})b_{j,i}^{\theta}(\overline{x_{j}})$

of $T$ indexed by $\theta\in[h]$ for some positive integer $h$. For every
$\theta\in[h]$ we write $A_{1}^{\theta},\dots,A_{d}^{\theta}$ for the linear
subspaces spanned by the functions $a_{1,i}^{\theta},\dots,a_{d,i}^{\theta}$
respectively. We assume that whenever $\theta,\theta^{\prime}$ are distinct
elements of $[h]$, the equality $A_{j}^{\theta}=A_{j}^{\theta^{\prime}}$ fails
for at least one $j\in[d]$.

Let $M_{1}$ be a maximal subset of $[h]$ such that for each $j\in[d]$ the
linear subspaces $A_{j}^{\theta}$ with $\theta\in M_{1}$ are all in direct
sum. By Theorem 3.3 the set $M_{1}$ must have size at most $d$, as otherwise
we would have $T=0$. We can hence write

$[h]=\bigcup_{1\leq j_{1}\leq d}\bigcup_{w_{1}}\Theta_{(j_{1},w_{1})}$

where the union over $w_{1}$ is taken over all non-zero vectors of
$\oplus_{\theta\in M_{1}}A_{j_{1}}^{\theta}$, and where for every
$(j_{1},w_{1})$ and every $\theta\in M_{1}$ the line containing $w_{1}$ is
contained in $A_{j_{1}}^{\theta}$.

We now fix $(j_{1},w_{1})$, and let $M_{2}$ be a maximal subset of
$\Theta_{(j_{1},w_{1})}$ such that the linear subspaces $A_{j_{1}}^{\theta}$
with $\theta\in M_{2}$ have pairwise intersection $\langle w_{1}\rangle$, and
such that for every $j\neq j_{1}$ the linear subspaces $A_{j}^{\theta}$ with
$\theta\in M_{2}$ are in direct sum. Again, by applying Theorem 3.3 the set
$M_{2}$ has size at most $d$, as otherwise we would have
$\operatorname{sr}T\leq 1$, and we can further write

$\Theta_{(j_{1},w_{1})}=\bigcup_{1\leq j_{2}\leq
d}\bigcup_{w_{2}}\Theta_{(j_{1},w_{1}),(j_{2},w_{2})}$

where the union over $w_{2}$ is taken over all non-zero vectors of
$\oplus_{\theta\in M_{1}}A_{j_{2}}^{\theta}$ if $j_{2}\neq j_{1}$ (resp. taken
over all vectors linearly independent from $w$ if $j_{2}=j_{1}$), and where
for every $\theta\in\Theta_{(j_{2},w_{2})}$ the line containing $w_{2}$ is
contained in $A_{j_{2}}^{\theta}$ (resp. the plane containing $w_{1},w_{2}$ is
contained in $A_{j_{1}}^{\theta}$).

Iterating further we obtain a tree structure with depth $k$, and with root
$[h]$. Let us describe the inductive step of the process. Once the tree is
constructed up to some depth $\kappa\leq k$, a (depth-$\kappa$) leaf of the
tree constructed at this point is a subset

$\Theta_{(j_{1},w_{1}),(j_{2},w_{2}),\dots,(j_{\kappa},w_{\kappa})}$

of $[h]$ such that there exist linear subspaces
$W_{1}\subset\mathbb{F}^{n_{1}}\dots,W_{d}\subset\mathbb{F}^{n_{d}}$ with

$\dim W_{1}+\dots+\dim W_{d}=\kappa$

and such that $W_{j}\subset A_{j}^{\theta}$ for every $j\in[d]$ and every
$\theta\in\Theta_{(j_{1},w_{1}),(j_{2},w_{2}),\dots,(j_{\kappa},w_{\kappa})}$.
If $\kappa<k$, then let $M_{\kappa+1}$ be a maximal subset of
$\Theta_{(j_{1},w_{1}),(j_{2},w_{2}),\dots,(j_{\kappa},w_{\kappa})}$ such that
the linear subspaces $A_{j}^{\theta}$ with $\theta\in M_{\kappa+1}$ have
pairwise intersection $W_{j}$ for every $j\in[d]$. Theorem 3.3 then shows that
$M_{\kappa+1}$ has size at most $d$ (as otherwise we would have
$\operatorname{sr}T\leq\kappa)$, and we can hence write

$\Theta_{(j_{1},w_{1}),(j_{2},w_{2}),\dots,(j_{\kappa},w_{\kappa})}=\bigcup_{1\leq
j_{\kappa+1}\leq
d}\bigcup_{w_{\kappa+1}}\Theta_{(j_{1},w_{1}),(j_{2},w_{2}),\dots,(j_{\kappa},w_{\kappa}),(j_{\kappa+1},w_{\kappa+1})},$
(8)

where the union over $w_{\kappa+1}$ is over all vectors of

$(+_{\theta\in M_{\kappa+1}}A_{j_{\kappa+1}}^{\theta})\setminus
W_{j_{\kappa+1}}.$

We then take the sets
$\Theta_{(j_{1},w_{1}),(j_{2},w_{2}),\dots,(j_{\kappa},w_{\kappa}),(j_{\kappa+1},w_{\kappa+1})}$
to be the immediate descendants of the set
$\Theta_{(j_{1},w_{1}),(j_{2},w_{2}),\dots,(j_{\kappa},w_{\kappa})}$ in the
tree.

If instead $\kappa=k$ then $\dim W_{1}+\dots+\dim W_{d}$ and $\dim
A_{1}^{\theta}+\dots+\dim A_{d}^{\theta}$ are both equal to $k$, so are equal
to one another. Hence, once we reach depth $k$ the linear subspaces
$A_{1}^{\theta},\dots,A_{d}^{\theta}$ are all completely determined by
$W_{1},\dots,W_{d}$. By our initial assumption that for any distinct
$\theta,\theta^{\prime}\in[h]$ we have $A_{j}^{\theta}\neq
A_{j}^{\theta^{\prime}}$ for some $j\in[d]$, the sets
$\Theta_{(j_{1},w_{1}),(j_{2},w_{2}),\dots,(j_{\kappa},w_{\kappa})}$ each have
size at most $1$.

We have obtained a tree with depth $k$, and each node of the tree has at most
$d|\mathbb{F}|^{dk}$ immediate descendants, so the number of leaves, and hence
of $d$-tuples of linear subspaces $(A_{1}^{\theta},\dots,A_{d}^{\theta})$ is
at most $(d|\mathbb{F}|^{dk})^{k}=d^{k}|\mathbb{F}|^{dk^{2}}$. Furthermore,
for each choice of a $d$-tuple of subspaces
$(A_{1}^{\theta},\dots,A_{d}^{\theta})$ with respective dimensions
$r_{1},\dots,r_{d}$, by the number (1) of decompositions of matrices there are
at most

$|\mathbb{F}|^{dr_{1}^{2}}\dots|\mathbb{F}|^{dr_{d}^{2}}\leq|\mathbb{F}|^{dk^{2}}$

choices for

$((a_{1,1},\dots,a_{1,r_{1}}),\dots,(a_{d,1},\dots,a_{d,r_{d}})).$

This finishes the proof of the first item of Theorem 3.5. ∎

##  5 Simpler analogue for tensor rank decompositions

In this section we prove a simpler analogue of Theorem 3.5 in the case of the
tensor rank, which is much more similar to the statement for matrices that we
discussed in the introduction.

######  Proposition 5.1.

Let $d\geq 2$ be an integer, let $k$ be a nonnegative integer, and let
$\mathbb{F}$ be a field. If $T:[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$
is an order-$d$ tensor with tensor rank $k$, then there exist linear subspaces
$A_{1}\subset\mathbb{F}^{n_{1}},\dots,A_{d}\subset\mathbb{F}^{n_{d}}$ such
that if

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k}a_{1,i}(x_{1})\dots a_{d,i}(x_{d})$ (9)

is a tensor rank decomposition of $T$ with length $k$, then we have

$A_{1}=\langle a_{1,1},\dots,a_{1,k}\rangle,\dots,A_{d}=\langle
a_{d,1},\dots,a_{d,k}\rangle.$

In particular, if the field $\mathbb{F}$ is finite, then the number of
possible tensor rank decompositions of $T$ with length $k$ is at most
$|\mathbb{F}|^{(d-1)k^{2}}$.

###### Proof.

Assume that

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k}a_{1,i}(x_{1})\dots
a_{d,i}(x_{d})=\sum_{i=1}^{k}a_{1,i}^{\prime}(x_{1})\dots
a_{d,i}^{\prime}(x_{d})$

are two decompositions of $T$ with length $k$. To prove the first conclusion,
it suffices to show that for each $j\in[d]$ the linear subspaces $\langle
a_{j,1},\dots,a_{j,k}\rangle$ and $\langle
a_{j,1}^{\prime},\dots,a_{j,k}^{\prime}\rangle$ are the same. Assume for
contradiction that they are not. Then without loss of generality the linear
subspace $\langle a_{1,1},\dots,a_{1,k}\rangle$ is not contained in the linear
subspace $\langle a_{1,1}^{\prime},\dots,a_{1,k}^{\prime}\rangle$, so there
exists $u:[n_{1}]\to\mathbb{F}$ such that
$(u.a_{1,1}^{\prime},\dots,u.a_{1,k}^{\prime})=0$ but
$(u.a_{1,1},\dots,u.a_{1,k})\neq 0$. Applying $u$ to both decompositions of
$T$ we obtain

$\sum_{i=1}^{k}(u.a_{1,i})a_{2,i}(x_{2})\dots a_{d,i}(x_{d})=0,$

so the products $a_{2,i}\otimes\dots\otimes a_{d,i}$ with $i\in[k]$ are
linearly dependent. Assuming without loss of generality that the product
$a_{2,k}\otimes\dots\otimes a_{d,k}$ is a linear combination of the products
$a_{2,i}\otimes\dots\otimes a_{d,i}$ with $i\in[k-1]$, we can hence write

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k-1}\alpha_{1,i}(x_{1})a_{2,i}(x_{2})\dots
a_{d,i}(x_{d})$

for some new functions
$\alpha_{1,1},\dots,\alpha_{1,k-1}:[n_{1}]\to\mathbb{F}$. This is a tensor
rank decomposition of $T$ with length $k-1$, which contradicts that $T$ has
tensor rank $k$.

If the field $\mathbb{F}$ is finite, then for each of the $k(d-1)$ functions
$a_{j,i}$ with $j\in\\{2,\dots,d\\}$ and $i\in[k]$ involved in a given
decomposition of $T$, there are at most $|A_{j}|\leq|\mathbb{F}|^{k}$
possibilities. Once these functions are fixed, the linear independence of the
products

$a_{2,i}\otimes\dots\otimes a_{d,i}$

with $i\in[k]$, shows that the functions $a_{1,1},\dots,a_{1,k}$ are
determined. The bound follows. ∎

Although the upper bound that we obtain specialises in the case $d=2$ to the
upper bound obtained at the start of the introduction, the number of tensor
rank decompositions can be much less than that for general $d$. Indeed if an
order-$d$ tensor $T$ with tensor rank $k$ is identifiable in the sense that we
mentioned in the introduction, then it can be written in at most $k!$ ways as
a sum of $k$ tensors with tensor rank $1$ (those being the same, up to
permutation); as in turn there are $(|\mathbb{F}|-1)^{d-1}$ ways of rewriting
a tensor with tensor rank $1$ as a product of $d$ functions, such as tensor
has at most $k!(|\mathbb{F}|-1)^{d-1}$ choices for the number of possible
tensor rank decompositions in our sense. Nonetheless, the following example
shows that the behaviour from the $d=2$ case for $k$ large can carry over to
tensors of higher order, and that the exponent in the bound from Proposition
5.1 cannot be improved by a factor greater than $d$ in general. We recall the
absolute constant $\omega=\prod_{i=1}^{\infty}(1-2^{-i})>0$ defined at the
start of the introduction.

######  Example 5.2.

_Let $d\geq 2$ be an integer, and let $k$ be a nonnegative integer. Let $T$ be
the order-$d$ tensor defined by_

$T(x_{1},\dots,x_{d})=M(x_{1},x_{2})a_{3}(x_{3})\dots a_{d}(x_{d})$ (10)

_for some matrix $M:[n_{1}]\times[n_{2}]\to\mathbb{F}$ with rank $k$ and some
non-zero functions
$a_{3}:[n_{3}]\to\mathbb{F},\dots,a_{d}:[n_{d}]\to\mathbb{F}$. Then $T$ has
tensor rank equal to $k$, and the number of tensor rank decompositions of
length $k$ of $T$ is exactly_

$(|\mathbb{F}|-1)^{(d-2)k}|\mathbb{F}|^{k^{2}}\prod_{i=1}^{k}(1-|\mathbb{F}|^{-i}),$

_which is between $\omega|\mathbb{F}|^{k^{2}}$ and
$|\mathbb{F}|^{k^{2}+(d-2)k}$._

###### Proof.

In one direction, writing a rank decomposition of the matrix $M$ with length
$k$ and plugging it in (10) shows $\operatorname{tr}T\leq k$. In the other
direction, if

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k^{\prime}}a_{1,i}(x_{1})a_{2,i}(x_{2})a_{3,i}(x_{3})\dots
a_{d,i}(x_{d})$ (11)

is a tensor rank decomposition of $T$ for some integer $k^{\prime}$, then
letting $a_{3}^{*}:[n_{3}]\to\mathbb{F},\dots,a_{d}^{*}:[n_{d}]\to\mathbb{F}$
such that $a_{j}^{*}.a_{j}=1$ for each $j\in\\{3,\dots,d\\}$ and applying
$a_{3}^{*},\dots,a_{d}^{*}$ to both decompositions (10) and (11) leads to

$M(x_{1},x_{2})=\sum_{i=1}^{k^{\prime}}C_{i}a_{1,i}(x_{1})a_{2,i}(x_{2})$

for some coefficients $C_{i}\in\mathbb{F}$, so
$k^{\prime}\geq\operatorname{rk}M$ and hence $\operatorname{tr}T\geq k$.

The decomposition (10) shows that the linear subspaces $A_{3},\dots,A_{d}$ of
Proposition 5.1 each have dimension $1$, and there are hence at most
$(|\mathbb{F}|-1)^{(d-2)k}$ choices for

$((a_{3,1},\dots,a_{3,k}),\dots,(a_{d,1},\dots,a_{d,k}))$ (12)

since if one of these functions were zero, then this would contradict
$\operatorname{tr}T=k$. Once this choice is made, there are

$|\mathbb{F}|^{k^{2}}\prod_{i=1}^{k}(1-|\mathbb{F}|^{-i})$

choices for $(a_{2,1},\dots,a_{2,k})$, and then $(a_{1,1},\dots,a_{1,k})$ is
completely determined. Conversely, for any given choice of (12) such that
$a_{j,i}\in A_{j}\setminus\\{0\\}$ for every $j\in\\{3,\dots,d\\}$ and
$i\in[k]$, the decomposition (9) becomes

$\sum_{i=1}^{k}D_{i}a_{1,i}(x_{1})a_{2,i}(x_{2})a_{3}(x_{3})\dots
a_{d}(x_{d})$

for some $D_{1},\dots,D_{k}\in\mathbb{F}\setminus\\{0\\}$, so whenever
$f_{1},\dots,f_{k}:[n_{1}]\to\mathbb{F}$,
$g_{1},\dots,g_{k}:[n_{2}]\to\mathbb{F}$ provide a decomposition

$M(x_{1},x_{2})=\sum_{i=1}^{k}f_{i}(x_{1})g_{i}(x_{2})$

of $M$ with length $k$, taking $a_{1,i}=f_{i}$ and $a_{2,i}=g_{i}/D_{i}$ for
every $i\in[k]$ provides a decomposition of $T$ with length $k$. ∎

##  6 Proof of the theorem on sunflowers for order-$3$ tensors

The main goal of this section is to prove Proposition 3.2 and Theorem 3.3 in
the case of order-$3$ tensors, and discuss the main ideas behind the proofs as
well as how they were discovered.

The statement of the next lemma is similar to Lemma 9 from [8]. The proof that
we give is slightly different from the proof in that paper, but they are based
on the same idea.

######  Lemma 6.1.

Let $F_{A}\subset\mathbb{F}^{n_{1}},F_{C}\subset\mathbb{F}^{n_{2}}$ both be
families of linearly independent vectors, and let $E$ be a linear subspace of
$\mathbb{F}^{n_{3}}$. For each $(a,c)\in F_{A}\times F_{C}$, let $p_{a,c}$ be
an element of $\mathbb{F}^{n_{3}}$. Assume that the linear combination

$\sum_{a\in F_{A},c\in F_{C}}a\otimes c\otimes p_{a,c}$

belongs to $\mathbb{F}^{n_{1}}\otimes\mathbb{F}^{n_{2}}\otimes E$. Then
$p_{a,c}\in E$ for every $(a,c)\in F_{A}\times F_{C}$.

###### Proof.

We define dual families $F_{A}^{*}$, $F_{C}^{*}$ to the families $F_{A}$,
$F_{C}$ respectively. The assumption states that we can write

$\sum_{a\in A,c\in C}a\otimes c\otimes
p_{a,c}=\sum_{i\in[n_{1}]}\sum_{j\in[n_{2}]}\tau_{i,1}\otimes\tau_{j,2}\otimes
e_{i,j}$

where the vectors $\tau_{i,1},\tau_{j,2}$ are respectively the canonical basis
vectors of $\mathbb{F}^{n_{1}}$ and $\mathbb{F}^{n_{2}}$ respectively, and
$e_{i,j}\in E$ for every $(i,j)\in[n_{1}]\times[n_{2}]$. For any given pair
$(a,c)\in F_{A}\times F_{C}$, applying $a^{*}\otimes c^{*}$ provides

$p_{a,c}=\sum_{i=1}^{n_{1}}\sum_{j=1}^{n_{2}}a^{*}(i)c^{*}(j)e_{i,j}.$

This establishes the lemma. ∎

We first prove Proposition 3.2 in the $d=3$ case. It can be restated as
follows, in a way that highlights the successive functions that will appear in
the proof. As much of the proof is similar to that of Lemma 10 from [8] and to
the discussion between that lemma and Corollary 11 there, we have decided to
re-use the same notations as those of that paper.

######  Proposition 6.2.

Let $r,s,t$ be nonnegative integers. Assume that we have the decomposition

$\sum_{i=1}^{r}a_{i}(x)b_{i}(y,z)+\sum_{j=1}^{s}c_{j}(y)d_{j}(x,z)+\sum_{k=1}^{t}e_{k}(z)f_{k}(x,y)$
(13)

of the order-$3$ zero tensor $[n_{1}]\times[n_{2}]\times[n_{3}]\to\mathbb{F}$
and that the families

$(a_{i}:i\in[r]),(c_{j}:j\in[s]),(e_{k}:k\in[t])$

are each linearly independent. Then we may write

$\displaystyle b_{i}$ $\displaystyle=\sum_{j=1}^{s}c_{j}\otimes
p_{i,j}+\sum_{k=1}^{t}q_{i,k}\otimes e_{k}$ (14) $\displaystyle d_{j}$
$\displaystyle=\sum_{i=1}^{r}a_{i}\otimes g_{i,j}+\sum_{k=1}^{t}h_{j,k}\otimes
e_{k}$ (15) $\displaystyle f_{k}$ $\displaystyle=\sum_{i=1}^{r}a_{i}\otimes
u_{i,k}+\sum_{j=1}^{s}v_{j,k}\otimes c_{j}$ (16)

for each $i\in[r],j\in[s],k\in[t]$ respectively, where
$h_{j,k},v_{j,k}:[n_{1}]\to\mathbb{F}$,
$q_{i,k},u_{i,k}:[n_{2}]\to\mathbb{F}$, $p_{i,j},g_{i,j}:[n_{3}]\to\mathbb{F}$
are some functions satisfying

$\displaystyle p_{i,j}+g_{i,j}$
$\displaystyle=\sum_{k=1}^{t}\lambda_{i,j,k}e_{k}$ (17) $\displaystyle
q_{i,k}+u_{i,k}$ $\displaystyle=\sum_{j=1}^{s}\mu_{i,j,k}c_{j}$ (18)
$\displaystyle h_{j,k}+v_{j,k}$ $\displaystyle=\sum_{i=1}^{r}\nu_{i,j,k}a_{i}$
(19)

for each $(i,j)\in[r]\times[s]$, for each $(i,k)\in[r]\times[t]$, and for each
$(j,k)\in[s]\times[t]$ respectively, with
$\lambda_{i,j,k},\mu_{i,j,k},\nu_{i,j,k}\in\mathbb{F}$ such that

$\lambda_{i,j,k}+\mu_{i,j,k}+\nu_{i,j,k}=0$ (20)

for each $(i,j,k)\in[r]\times[s]\times[t]$.

###### Proof.

Applying dual functions $a_{i}^{*},c_{j}^{*},e_{k}^{*}$ we get the expressions
(14), (15), (16). Substituting in (13) and applying Lemma 6.1 shows that

$\displaystyle p_{i,j}+g_{i,j}$ $\displaystyle\in\langle e_{k}:k\in[t]\rangle$
$\displaystyle q_{i,k}+u_{i,k}$ $\displaystyle\in\langle c_{j}:j\in[s]\rangle$
$\displaystyle h_{j,k}+v_{j,k}$ $\displaystyle\in\langle a_{i}:i\in[r]\rangle$

respectively for each $(i,j)\in[r]\times[s]$, for each $(i,k)\in[r]\times[t]$,
and for each $(j,k)\in[s]\times[t]$, so can write these functions as in (17),
(18), (19). Substituting in (13) we obtain

$\sum_{i=1}^{r}\sum_{j=1}^{s}\sum_{k=1}^{t}(\lambda_{i,j,k}+\mu_{i,j,k}+\nu_{i,j,k})a_{i}\otimes
c_{j}\otimes e_{k}=0.$

Because the products $a_{i}\otimes c_{j}\otimes e_{k}$ with
$(i,j,k)\in[r]\times[s]\times[t]$ are linearly independent, we conclude (20).
∎

Now turning to the one-variable functions, we can begin by asking for the
weakest possible property asserting some lack of independence between the one-
variable functions involved in several decompositions. As the strongest form
of independence is to have, for every fixed $j\in[d]$, the linear subspaces
$A_{j}^{\theta}$ spanned by the functions $a_{j,i}^{\theta}$ of the
decompositions (indexed by $\theta$) all be in direct sum, we aim to show that
this can only occur for a bounded number of decompositions.

As formulated this last goal is not yet completely reasonable, as shown by the
fact that the zero tensor can be decomposed as

$a(x)(bc)(y,z)-b(y)(ac)(x,z)$

for all $a:[n_{1}]\to\mathbb{F}$, $b:[n_{2}]\to\mathbb{F}$,
$c:[n_{3}]\to\mathbb{F}$ (or even more simply, by repeating the length-$0$
decomposition of the zero tensor arbitrarily many times). What we will rather
show is that the zero tensor is the only order-$3$ tensor for which there
exist four decompositions where for each of the three choices of special
coordinate the one-variable functions may all be in direct sum.

######  Proposition 6.3.

Let $T:[n_{1}]\times[n_{2}]\times[n_{3}]\to\mathbb{F}$ be an order-3 tensor.
Assume that for every $\theta\in[4]$ we have a decomposition

$T(x,y,z)=\sum_{i=1}^{r_{\theta}}a_{i}^{\theta}(x)b_{i}^{\theta}(y,z)+\sum_{j=1}^{s_{\theta}}c_{j}^{\theta}(y)d_{j}^{\theta}(x,z)+\sum_{k=1}^{t_{\theta}}e_{k}^{\theta}(z)f_{k}^{\theta}(x,y)$
(21)

for some nonnegative integers $r_{\theta},s_{\theta},t_{\theta}$. Assume that
the families

$(a_{i}^{\theta}:\theta\in[4],i\in[r_{\theta}])\text{,
}(c_{j}^{\theta}:\theta\in[4],j\in[s_{\theta}])\text{,
}(e_{k}^{\theta}:\theta\in[4],k\in[t_{\theta}])$ (22)

are each linearly independent. Then $T=0$.

Let us briefly outline the proof before writing it formally. Writing an
equality between two decompositions of $T$ (indexed by, say, $1$ and $2$) and
applying the dual functions then allows us to write any given two-variable
function of the first decomposition (such as, say, $b_{1}^{1}$) as a sum of
products of two one-variable functions, one of which, of one of the types
$c_{j}^{1}$, $c_{j}^{2}$, $e_{k}^{1}$, $e_{k}^{2}$, is specified and may come
from either of the two decompositions, and the other of which is unspecified.
We can write similar expressions of $b_{1}^{1}$ where the third and fourth
decompositions supply the one-variable functions that the second decomposition
previously supplied, which provides two other decompositions of $b_{1}^{1}$,
after which it is only moderately difficult to show that $b_{1}^{1}$ has a
decomposition of the kind that we have just described, where all specified
one-variable functions are of the types $c_{j}^{1}$ and $e_{k}^{1}$. In other
words we show that for every $\theta\in[4]$ the two-variable functions
$b_{i}^{\theta},d_{j}^{\theta},f_{k}^{\theta}$ have decompositions as sums of
products of two functions where at least one function of each product is of
the type $a_{i}^{\theta},c_{j}^{\theta},e_{k}^{\theta}$ for that same value of
$\theta$. This is the statement of Lemma 6.4, and is a property which is
strong enough to allow us to conclude that $T=0$ once we apply it to two
different values of $\theta$.

For every decomposition $\theta$ we respectively write
$A^{\theta},C^{\theta},E^{\theta}$ for the linear subspaces

$\langle a_{i}^{\theta}:i\in[r_{\theta}]\rangle\text{, }\langle
c_{j}^{\theta}:j\in[s_{\theta}]\rangle\text{, }\langle
e_{k}^{\theta}:k\in[t_{\theta}]\rangle.$

We begin with a lemma which informally says that under the assumptions of
Proposition 6.3, the two-variable functions of every decomposition $\theta$
can themselves be further decomposed as sums of products of two one-variable
functions, where in every product one of the functions is a one-variable
function from that same decomposition $\theta$ of the original tensor. So far
for we have used notations such as $a_{i}^{\theta}$, $b_{i}^{\theta}$ for
functions arising from a decomposition $\theta$. As will now write equalities
between decompositions, and use them to obtain expressions for the functions
$b_{i}^{\theta}$, our calculations will involve terms that may depend either
only on one decomposition or simultaneously on both of the decompositions
between which we wrote the original equality. In the first case these terms
will be denoted for instance by $p_{i,j}^{\theta}$ to indicate that they only
depend on the decomposition $\theta$, and the second case they will instead be
written for instance as $p_{i,j}^{\theta\theta^{\prime}}$ to indicate that
they depend on both decompositions $\theta$,$\theta^{\prime}$.

######  Lemma 6.4.

Let $T:[n_{1}]\times[n_{2}]\times[n_{3}]\to\mathbb{F}$ be an order-$3$ tensor.
Under the assumptions of Proposition 6.3, for each $\theta\in[4]$ we can write
decompositions of the type

$\displaystyle b_{i}^{\theta}(y,z)$
$\displaystyle=\sum_{j=1}^{s_{\theta}}c_{j}^{\theta}(y)p_{i,j}^{\theta}(z)+\sum_{k=1}^{t_{\theta}}q_{i,k}^{\theta}(y)e_{k}^{\theta}(z)$
(23) $\displaystyle d_{j}^{\theta}(x,z)$
$\displaystyle=\sum_{i=1}^{r_{\theta}}a_{i}^{\theta}(x)g_{i,j}^{\theta}(z)+\sum_{k=1}^{t_{\theta}}h_{j,k}^{\theta}(x)e_{k}^{\theta}(z)$
(24) $\displaystyle f_{k}^{\theta}(x,y)$
$\displaystyle=\sum_{i=1}^{r_{\theta}}a_{i}^{\theta}(x)u_{i,k}^{\theta}(y)+\sum_{j=1}^{s_{\theta}}v_{j,k}^{\theta}(x)c_{j}^{\theta}(y).$
(25)

###### Proof.

We choose dual families $(a_{i}^{\theta*})$, $(c_{j}^{\theta*})$,
$(e_{k}^{\theta*})$ to the respective (linearly independent) families (22). We
begin with the equality

$\displaystyle\sum_{i=1}^{r_{1}}a_{i}^{1}(x)b_{i}^{1}(y,z)+\sum_{j=1}^{s_{1}}c_{j}^{1}(y)d_{j}^{1}(x,z)+\sum_{k=1}^{t_{1}}e_{k}^{1}(z)f_{j}^{1}(x,y)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{r_{2}}a_{i}^{2}(x)b_{i}^{2}(y,z)+\sum_{j=1}^{s_{2}}c_{j}^{2}(y)d_{j}^{2}(x,z)+\sum_{k=1}^{t_{2}}e_{k}^{2}(z)f_{j}^{2}(x,y).$

Applying the function $a_{i}^{1*}$ we get a decomposition of the type

$b_{i}^{1}(y,z)=\sum_{j=1}^{s_{1}}c_{j}^{1}(y)p_{i,j}^{1}(z)-\sum_{j=1}^{s_{2}}c_{j}^{2}(y)p_{i,j}^{12}(z)+\sum_{k=1}^{t_{1}}q_{i,k}^{1}(y)e_{k}^{1}(z)-\sum_{k=1}^{t_{2}}q_{i,k}^{12}(y)e_{k}^{2}(z).$
(26)

Here $2$ could instead have been taken to be an arbitrary element of
$\\{2,3,4\\}$, so if we write the previous identity for the pair $(1,3)$
rather than for the pair $(1,2)$, and then subtract it from the identity for
the pair $(1,2)$ then we get

$\sum_{j=1}^{s_{3}}c_{j}^{3}(y)p_{i,j}^{13}(z)-\sum_{j=1}^{s_{2}}c_{j}^{2}(y)p_{i,j}^{12}(z)+\sum_{k=1}^{t_{3}}q_{i,k}^{13}(y)e_{k}^{3}(z)-\sum_{k=1}^{t_{2}}q_{i,k}^{12}(y)e_{k}^{2}(z)=0.$

Applying the dual functions $c_{j}^{2*}$ then shows that

$p_{i,j}^{12}\in E^{2}\oplus E^{3}$

for each $j\in[s_{2}]$. This argument also shows (by replacing $3$ by $4$)
that

$p_{i,j}^{12}\in E^{2}\oplus E^{4}$

for each $j\in[s_{2}]$. Because the linear subspaces $E^{2},E^{3},E^{4}$ are
all in direct sum, we obtain

$p_{i,j}^{12}\in E^{2}$

for each $j\in[s_{2}]$. A similar argument shows that

$q_{i,k}^{12}\in C^{2}$

for each $k\in[t_{2}]$. Substituting in (26) we obtain

$b_{i}^{1}(y,z)=\sum_{j=1}^{s_{1}}c_{j}^{1}(y)p_{i,j}^{1}(z)+\sum_{k=1}^{t_{1}}q_{i,k}^{1}(y)e_{k}^{1}(z)+\sum_{j=1}^{s_{2}}\sum_{k=1}^{t_{2}}\lambda_{i,j,k}^{12}c_{j}^{2}(y)e_{k}^{2}(z)$

for some coefficients $\lambda_{i,j,k}^{12}\in\mathbb{F}$. Writing a similar
equality with $3$ instead of $2$, subtracting it from the equality above, and
using that the products $c_{j}^{2}\otimes e_{k}^{2}$ and $c_{j}^{3}\otimes
e_{k}^{3}$ are all jointly independent we obtain that all coefficients
$\lambda_{i,j,k}^{12}$ are equal to $0$, and hence the desired expression
(23). We conclude (24) and (25) similarly. ∎

Given Lemma 6.4, Proposition 6.3 is now within reach.

###### Proof of Proposition 6.3.

Plugging in (23), (24), (25) into (21) and gathering terms, we obtain

$\displaystyle T$
$\displaystyle=\sum_{i=1}^{r_{1}}\sum_{j=1}^{s_{1}}a_{i}^{1}\otimes
c_{j}^{1}\otimes(p_{i,j}^{1}+g_{i,j}^{1})$
$\displaystyle+\sum_{i=1}^{r_{1}}\sum_{k=1}^{t_{1}}a_{i}^{1}\otimes(q_{i,k}^{1}+u_{i,k}^{1})\otimes
e_{k}^{1}$
$\displaystyle+\sum_{j=1}^{s_{1}}\sum_{k=1}^{t_{1}}(h_{j,k}^{1}+v_{j,k}^{1})\otimes
c_{j}^{1}\otimes e_{k}^{1}$ (27)

and a similar decomposition with $2$ instead of $1$. Writing the equality
between the two decompositions shows in particular that

$\sum_{i=1}^{r_{1}}\sum_{j=1}^{s_{1}}a_{i}^{1}\otimes
c_{j}^{1}\otimes(p_{i,j}^{1}+g_{i,j}^{1})-\sum_{i=1}^{r_{2}}\sum_{j=1}^{s_{2}}a_{i}^{2}\otimes
c_{j}^{2}\otimes(p_{i,j}^{2}+g_{i,j}^{2})$

belongs to the linear subspace

$\mathbb{F}^{n_{1}}\otimes\mathbb{F}^{n_{2}}\otimes(E^{1}\oplus E^{2}).$

Because the products $a_{i}^{1}\otimes c_{j}^{1}$ and $a_{i}^{2}\otimes
c_{j}^{2}$ are all linearly independent, Lemma 6.1 shows that

$p_{i,j}^{1}+g_{i,j}^{1}\in E^{1}\oplus E^{2}$

for each $(i,j)\in[r_{1}]\times[s_{1}]$. We obtain analogous statements for
the sums

$q_{i,k}^{1}+u_{i,k}^{1}\text{, }h_{j,k}^{1}+v_{j,k}^{1}\text{,
}p_{i,j}^{2}+g_{i,j}^{2}\text{, }q_{i,k}^{2}+u_{i,k}^{2}\text{,
}h_{j,k}^{2}+v_{j,k}^{2}.$

Substituting in the decomposition (27) we obtain that $T$ belongs to the
linear subspace

$(A^{1}\otimes C^{1}\otimes E^{1})\oplus(A^{2}\otimes C^{1}\otimes
E^{1})\oplus(A^{1}\otimes C^{2}\otimes E^{1})\oplus(A^{1}\otimes C^{1}\otimes
E^{2}),$

and similarly with the roles of $1$ and $2$ exchanged. The intersection of
these two linear subspaces is $\\{0\\}$, so $T=0$. ∎

The statement of Proposition 6.3 does not appear to be strong enough to deduce
Theorem 3.5 for order-$3$ tensors. In particular, an unsuccessful attempt at a
deduction runs as follows. Given any set of minimal-length decompositions of a
tensor with slice rank $k$ (indexed by $\theta\in[h]$) with size $h\geq 4$,
Proposition 6.3 shows that without loss of generality, every $\theta\in[h]$ is
such that at least one of the intersections

$A^{\theta}\cap(A^{1}+A^{2}+A^{3})\text{,
}C^{\theta}\cap(C^{1}+C^{2}+C^{3})\text{, }E^{\theta}\cap(E^{1}+E^{2}+E^{3})$
(28)

is non-empty. Because the field $|\mathbb{F}|$ is assumed to be finite, we can
write $[h]$ as a union of at most $3|\mathbb{F}|^{3k}$ sets, indexed by an
element of [3] indicating one of the intersections (28) which is non-empty
(chosen arbitrarily among the possibilities if more than one intersection is
non-empty), and by a non-zero vector in this intersection. Restricting our
attention to one of these sets, without loss of generality there exists
$a:[n_{1}]\to\mathbb{F}$ such that all decompositions of $T$ are, after a
change of basis in the first of the three parts of the decomposition, of the
type

$a(x)b^{\theta}(y,z)+\sum_{i=1}^{r_{\theta}-1}a_{i}^{\theta}(x)b_{i}^{\theta}(y,z)+\sum_{j=1}^{s_{\theta}}c_{j}^{\theta}(y)d_{j}^{\theta}(x,z)+\sum_{k=1}^{t_{\theta}}e_{k}^{\theta}(z)f_{k}^{\theta}(x,y)$

with $r_{\theta}+s_{\theta}+t_{\theta}=k$. The tensor $T^{\theta}$ defined by

$T^{\theta}(x,y,z)=T(x,y,z)-a(x)b^{\theta}(y,z)$

must then have slice rank $k-1$ (if it were strictly less than that, then the
subadditivity of the slice rank would show that $\operatorname{sr}T<k$). We
could then aim to induct on the slice rank of $k$ by applying on each
$T^{\theta}$ the inductive hypothesis stating that the number of possibilities
for the one-variable functions in minimal-length decompositions is bounded by
some function of $d,k,\mathbb{F}$ only. The inductive step however does not
work, because although the one-variable function $a$ is the same for every
$\theta$, the number of possibilities for the two-variable function
$b^{\theta}$ (and hence for the tensor $T^{\theta}$) could potentially be
unbounded.

To transform this attempt into the proof from Section 4, we want to prove a
strengthening of Proposition 6.3 which does not require us to use the
auxiliary tensors $T^{\theta}$ and instead allows us to work with
decompositions of $T$ directly. A suitable formulation is given by the
following statement, which is the special case $d=3$ of Theorem 3.5.

######  Proposition 6.5.

Let $T:[n_{1}]\times[n_{2}]\times[n_{3}]\to\mathbb{F}$ be an order-3 tensor.
Assume that for each $\theta\in[4]$ we have a decomposition

$\displaystyle T(x,y,z)$
$\displaystyle=\sum_{i=1}^{r_{0}}a_{i}^{0}(x)b_{i}^{0,\theta}(y,z)+\sum_{j=1}^{s_{0}}c_{j}^{0}(y)d_{j}^{0,\theta}(x,z)+\sum_{k=1}^{t_{0}}e_{k}^{0}(z)f_{k}^{0,\theta}(x,y)$
$\displaystyle+\sum_{i=1}^{r_{\theta}}a_{i}^{\theta}(x)b_{i}^{\theta}(y,z)+\sum_{j=1}^{s_{\theta}}c_{j}^{\theta}(y)d_{j}^{\theta}(x,z)+\sum_{k=1}^{t_{\theta}}e_{k}^{\theta}(z)f_{k}^{\theta}(x,y)$
(29)

for some nonnegative integers $r_{\theta},s_{\theta},t_{\theta}$. Assume that
the families

$(a_{i}^{\beta}:\beta\in\\{0\\}\cup[4],i\in[r_{\beta}])\text{,
}(c_{j}^{\beta}:\beta\in\\{0\\}\cup[4],j\in[s_{\beta}])\text{,
}(e_{k}^{\beta}:\beta\in\\{0\\}\cup[4],k\in[t_{\beta}])$ (30)

are each linearly independent. Then $T$ has a decomposition of the type

$\sum_{i=1}^{r_{0}}a_{i}^{0}(x)b_{i}(y,z)+\sum_{j=1}^{s_{0}}c_{j}^{0}(y)d_{j}(x,z)+\sum_{k=1}^{t_{0}}e_{k}^{0}(z)f_{k}(x,y)$

and in particular has slice rank at most $r_{0}+s_{0}+t_{0}$.

The bound of $r_{0}+s_{0}+t_{0}$ is sharp: if $T$ is a tensor with slice rank
$k$, then it suffices to take the part with one-variable functions
$a_{i}^{0},c_{j}^{0},e_{k}^{0}$ to be the same slice rank decomposition of $T$
with length $k$ for each $\theta$, and to take
$r_{\theta},s_{\theta},t_{\theta}$ equal to $0$ for each $\theta$.

Although the proof of Proposition 6.5 will in a way be slightly more
complicated than the proof of Proposition 6.3, it will also in another way be
more conceptually appealing: indeed, looking back at the argument about
decompositions of two-variable functions which we had used in the proof of
Proposition 6.3, we see that we had implicitly used and proved an analogue of
Proposition 6.5 for $d=2$. This analogue, Proposition 6.6, is the $d=2$ case
of Theorem 3.3 and furthermore lays the groundwork for the inductive argument
on the order $d$ of the tensor that we will later use in Section 7 when
dealing with the general case. Because the proof of Proposition 6.6 is
contained in that of Proposition 6.3, now appears to be a good moment to pass
to a slightly more abstract but more concise notation which we will use
repeatedly in the remainder of the paper.

######  Proposition 6.6.

Let $M:[n_{1}]\times[n_{2}]\to\mathbb{F}$ be a matrix. Assume that for each
$\theta\in[3]$ we have a decomposition

$\displaystyle M(x,y)$
$\displaystyle=\sum_{i=1}^{r_{0}}a_{i}^{0}(x)b_{i}^{0,\theta}(y)+\sum_{j=1}^{s_{0}}d_{j}^{0,\theta}(x)c_{j}^{0}(y)$
$\displaystyle+\sum_{i=1}^{r_{\theta}}a_{i}^{\theta}(x)b_{i}^{\theta}(y)+\sum_{j=1}^{s_{\theta}}d_{j}^{\theta}(x)c_{j}^{\theta}(y)$
(31)

for some nonnegative integers $r_{\theta},s_{\theta}$. Assume that the
families

$(a_{i}^{\beta}:\beta\in\\{0\\}\cup[3],i\in[r_{\beta}])\text{,
}(c_{j}^{\beta}:\beta\in\\{0\\}\cup[3],j\in[s_{\beta}])$ (32)

are both linearly independent. Then $M$ has a decomposition of the type

$\sum_{i=1}^{r_{0}}a_{i}^{0}(x)b_{i}(y)+\sum_{j=1}^{s_{0}}d_{j}(x)c_{j}^{0}(y)$

and in particular has rank at most $r_{0}+s_{0}$.

###### Proof.

For every $\beta\in\\{0\\}\cup[3]$ we respectively write $A^{\beta}$ and
$C^{\beta}$ for the linear subspaces $\langle
a_{i}^{\beta}:i\in[r_{\beta}]\rangle$ and $\langle
c_{j}^{\beta}:j\in[s_{\beta}]\rangle$. We define
$(a_{i}^{\beta}),(c_{j}^{\beta})$ to be dual families to the families (32).
Writing the equality between the decompositions $1$ and $2$ and applying the
dual functions $a_{i}^{1*}$ we obtain $b_{i}^{1}\in C^{0}\oplus C^{1}\oplus
C^{2}$. Similarly, $b_{i}^{1}\in C^{0}\oplus C^{1}\oplus C^{3}$. Because the
subspaces $C^{0}\oplus C^{1}$, $C^{2}$ and $C^{3}$ are in direct sum, we have
$b_{i}^{1}\in C^{0}\oplus C^{1}$. Similarly using the dual functions
$c_{j}^{1*}$ we show $d_{j}^{1}\in A^{0}\oplus A^{1}$. Using the decomposition
$1$ of $M$ we obtain that

$M\in A^{0}\otimes\mathbb{F}^{n_{2}}+\mathbb{F}^{n_{1}}\otimes
C^{0}+A^{1}\otimes(C^{0}\oplus C^{1})+(A^{0}\oplus A^{1})\otimes C^{1},$

which simplifies to

$M\in(A^{0}\otimes\mathbb{F}^{n_{2}}+\mathbb{F}^{n_{1}}\otimes C^{0})\oplus
A^{1}\otimes C^{1}.$

Similarly the decomposition $2$ provides

$M\in(A^{0}\otimes\mathbb{F}^{n_{2}}+\mathbb{F}^{n_{1}}\otimes C^{0})\oplus
A^{2}\otimes C^{2}.$

The linear subspaces

$A^{0}\otimes\mathbb{F}^{n_{2}}+\mathbb{F}^{n_{1}}\otimes C^{0},A^{1}\otimes
C^{1},A^{2}\otimes C^{2}$

are all in direct sum, so

$M\in A^{0}\otimes\mathbb{F}^{n_{2}}+\mathbb{F}^{n_{1}}\otimes C^{0}$

and the decomposition (31) follows. ∎

Using Proposition 6.6 we are now able to obtain a generalisation of Lemma 6.4
in rather short order. Throughout the remainder of this section, for every
$\beta\in\\{0\\}\cup[4]$ we respectively write $A^{\beta},C^{\beta},E^{\beta}$
for the linear subspaces

$\langle a_{i}^{\beta}:i\in[r_{\beta}]\rangle\text{, }\langle
c_{j}^{\beta}:j\in[s_{\beta}]\rangle\text{, }\langle
e_{k}^{\beta}:k\in[t_{\beta}]\rangle,$

and define dual families $(a_{i}^{\beta*})$,$(c_{j}^{\beta*})$,
$(e_{k}^{\beta*})$ to the respective families (30).

######  Lemma 6.7.

Let $T:[n_{1}]\times[n_{2}]\times[n_{3}]\to\mathbb{F}$ be an order-$3$ tensor.
Under the assumptions of Proposition 6.5, for each $\theta\in[4]$ we can write
decompositions of the type

$\displaystyle b_{i}^{\theta}(y,z)$
$\displaystyle=\sum_{j=1}^{s_{0}}c_{j}^{0}(y)p_{i,j}^{0,\theta}(z)+\sum_{k=1}^{t_{0}}q_{i,k}^{0,\theta}(y)e_{k}^{0}(z)+\sum_{j=1}^{s_{\theta}}c_{j}^{\theta}(y)p_{i,j}^{\theta}(z)+\sum_{k=1}^{t_{\theta}}q_{i,k}^{\theta}(y)e_{k}^{\theta}(z)$
(33) $\displaystyle d_{j}^{\theta}(x,z)$
$\displaystyle=\sum_{i=1}^{r_{0}}a_{i}^{0}(x)g_{i,j}^{0,\theta}(z)+\sum_{k=1}^{t_{0}}h_{j,k}^{0,\theta}(x)e_{k}^{0}(z)+\sum_{i=1}^{r_{\theta}}a_{i}^{\theta}(x)g_{i,j}^{\theta}(z)+\sum_{k=1}^{t_{\theta}}h_{j,k}^{\theta}(x)e_{k}^{\theta}(z)$
(34) $\displaystyle f_{k}^{\theta}(x,y)$
$\displaystyle=\sum_{i=1}^{r_{0}}a_{i}^{0}(x)u_{i,k}^{0,\theta}(y)+\sum_{j=1}^{s_{0}}v_{j,k}^{0,\theta}(x)c_{j}^{0}(y)+\sum_{i=1}^{r_{\theta}}a_{i}^{\theta}(x)u_{i,k}^{\theta}(y)+\sum_{j=1}^{s_{\theta}}v_{j,k}^{\theta}(x)c_{j}^{\theta}(y).$
(35)

###### Proof.

Writing an equality between the decompositions $1,2$ of $T$ and applying the
dual functions $a_{i}^{1*}$ we get a decomposition of the type

$\displaystyle b_{i}^{1}(y,z)$
$\displaystyle=\sum_{j=1}^{s_{0}}c_{j}^{0}(y)(p_{i,j}^{0,1}-p_{i,j}^{0,12})(z)+\sum_{j=1}^{s_{1}}c_{j}^{1}(y)p_{i,j}^{1}(z)-\sum_{j=1}^{s_{2}}c_{j}^{2}(y)p_{i,j}^{12}(z)$
$\displaystyle+\sum_{k=1}^{t_{0}}(q_{i,k}^{0,1}-q_{i,k}^{0,12})(y)e_{k}^{0}(z)+\sum_{k=1}^{t_{1}}q_{i,k}^{1}(y)e_{k}^{1}(z)-\sum_{k=1}^{t_{2}}q_{i,k}^{12}(y)e_{k}^{2}(z).$

We can write similar decompositions by replacing $2$ by $3$ or by $4$. We then
apply Proposition 6.6, with the pair of coordinates $(y,z)$ instead of
$(x,y)$, with

$(c_{j}^{\beta}:\beta\in\\{0,1\\},j\in[s_{\beta}])$

forming a basis of center functions,

$(c_{j}^{2}:j\in[s_{2}]),(c_{j}^{3}:j\in[s_{3}]),(c_{j}^{4}:j\in[s_{4}])$

forming bases of petal functions, and similarly for the remaining coordinate.
The desired expressions (33), (34), (35) then follow. ∎

There again, having established Lemma 6.7 we are ready to finish the proof of
Proposition 6.5.

###### Proof of Proposition 6.5.

Writing the equality between the two decompositions (29) of $T$ for $\theta=1$
and $\theta=2$ and applying the dual functions $a_{i}^{0*}$ we obtain

$b_{i}^{0,1}-b_{i}^{0,2}\in(C^{0}\oplus C^{1}\oplus
C^{2})\otimes\mathbb{F}^{n_{3}}+\mathbb{F}^{n_{2}}\otimes(E^{0}\oplus
E^{1}\oplus E^{2}).$ (36)

We obtain similar statements for the differences $d_{j}^{0,1}-d_{j}^{0,2}$ and
$f_{k}^{0,1}-f_{k}^{0,2}$.

We define linear subspaces of
$\mathbb{F}^{n_{1}}\otimes\mathbb{F}^{n_{2}}\otimes\mathbb{F}^{n_{3}}$, by

$\displaystyle R_{\mathrm{target}}$
$\displaystyle=A^{0}\otimes\mathbb{F}^{n_{2}}\otimes\mathbb{F}^{n_{3}}+\mathbb{F}^{n_{1}}\otimes
C^{0}\otimes\mathbb{F}^{n_{3}}+\mathbb{F}^{n_{1}}\otimes\mathbb{F}^{n_{2}}\otimes
E^{0}$ $\displaystyle R_{1}$ $\displaystyle=(A^{1}\otimes
C^{1}\otimes\mathbb{F}^{n_{3}})+(A^{1}\otimes\mathbb{F}^{n_{2}}\otimes
E^{1})+(\mathbb{F}^{n_{1}}\otimes C^{1}\otimes E^{1})$ $\displaystyle R_{2}$
$\displaystyle=(A^{2}\otimes
C^{2}\otimes\mathbb{F}^{n_{3}})+(A^{2}\otimes\mathbb{F}^{n_{2}}\otimes
E^{2})+(\mathbb{F}^{n_{1}}\otimes C^{2}\otimes E^{2})$

and by letting $R$ be the sum of all linear subspaces of
$\mathbb{F}^{n_{1}}\otimes\mathbb{F}^{n_{2}}\otimes\mathbb{F}^{n_{3}}$ of the
type $Y_{1}\otimes Y_{2}\otimes Y_{3}$ satisfying at least one of the
equalities

$Y_{1}=A^{0},Y_{2}=C^{0},Y_{3}=C^{0},$

and at least two of the properties

$Y_{1}\in\\{A^{0},A^{1},A^{2}\\}\text{,
}Y_{2}\in\\{C^{0},C^{1},C^{2}\\}\text{, }Y_{3}\in\\{E^{0},E^{1},E^{2}\\}.$

The tensor $S$ defined by

$S(x,y,z)=\sum_{i=1}^{r_{0}}a_{i}^{0}(x)b_{i}^{0,2}(y,z)+\sum_{j=1}^{s_{0}}c_{j}^{0}(y)d_{j}^{0,2}(x,z)+\sum_{k=1}^{t_{0}}e_{k}^{0}(z)f_{k}^{0,2}(x,y)$

belongs to $R_{\mathrm{target}}$. Subtracting this decomposition of $S$ from
both sides of (29) we obtain an equality between two decompositions of $T-S$,
which we can write as

$T_{1}+T_{\Delta}=T_{2},$ (37)

where

$\displaystyle T_{\Delta}$
$\displaystyle=\sum_{i=1}^{r_{0}}a_{i}^{0}(x)(b_{i}^{0,1}-b_{i}^{0,2})(y,z)+\sum_{j=1}^{s_{0}}c_{j}^{0}(y)(d_{j}^{0,1}-d_{j}^{0,2})(x,z)+\sum_{k=1}^{t_{0}}e_{k}^{0}(z)(f_{k}^{0,1}-f_{k}^{0,2})(x,y)$
$\displaystyle T_{1}$
$\displaystyle=\sum_{i=1}^{r_{1}}a_{i}^{1}(x)b_{i}^{1}(y,z)+\sum_{j=1}^{s_{1}}c_{j}^{1}(y)d_{j}^{1}(x,z)+\sum_{k=1}^{t_{1}}e_{k}^{1}(z)f_{k}^{1}(x,y)$
$\displaystyle T_{2}$
$\displaystyle=\sum_{i=1}^{r_{2}}a_{i}^{2}(x)b_{i}^{2}(y,z)+\sum_{j=1}^{s_{2}}c_{j}^{2}(y)d_{j}^{2}(x,z)+\sum_{k=1}^{t_{2}}e_{k}^{2}(z)f_{k}^{2}(x,y).$

From (36) and the two other analogous identities for $d_{j}^{0,1}-d_{j}^{0,2}$
and $f_{k}^{0,1}-f_{k}^{0,2}$, the tensor $T_{\Delta}$ belongs to $R$. From
Lemma 6.7 we know that

$T_{1}\in R+R_{1}\text{ and }T_{2}\in R+R_{2}.$

In the equality (37) we gather terms of $T_{\Delta},T_{1},T_{2}$ which are of
the same type, meaning that for instance if we have two terms

$a_{i}^{1}\otimes c_{j}^{0}\otimes p^{\prime}\text{ and }a_{i}^{1}\otimes
c_{j}^{0}\otimes p^{\prime\prime},$

and $p^{\prime}$,$p^{\prime\prime}$ are unspecified elements of
$\mathbb{F}^{n_{3}}$, then we replace them by a single term

$a_{i}^{1}\otimes c_{j}^{0}\otimes(p^{\prime}+p^{\prime\prime})\text{ or
}a_{i}^{1}\otimes c_{j}^{0}\otimes(p^{\prime}-p^{\prime\prime})$

as appropriate. We allow terms to change sides of the equation, and because we
do so, the resulting equality is no longer between two decompositions of
$T-S$, but between two decompositions of $T-S^{\prime}$, for some new tensor
$S^{\prime}$. Any terms which appear on both sides of (37) must necessarily
have as a factor an element of one of the types $a_{i}^{0}$, $c_{j}^{0}$,
$e_{k}^{0}$: indeed, if they do not, then their product of specified one-
variable functions is necessarily of one of the types

$a_{i}^{1}\otimes c_{j}^{1},a_{i}^{1}\otimes e_{k}^{1},c_{j}^{1}\otimes
e_{k}^{1},a_{i}^{2}\otimes c_{j}^{2},a_{i}^{2}\otimes
e_{k}^{2},c_{j}^{2}\otimes e_{k}^{2},$

and in the case of the first three and last three the term can respectively
only arise in the left-hand side and in the right-hand side. The difference
$S^{\prime}-S$ hence belongs to $R_{\mathrm{target}}$. Since $T-S$ also
belongs to $R_{\mathrm{target}}$, we obtain that $T-S^{\prime}$ belongs to
$R_{\mathrm{target}}$.

Using Lemma 6.1 and the linear independence of the families (30) we obtain
that the terms involved in the resulting equality all belong to

$(A^{0}\oplus A^{1}\oplus A^{2})\otimes(C^{0}\oplus C^{1}\oplus
C^{2})\otimes(E^{0}\oplus E^{1}\oplus E^{2}),$

and we can hence write both sides of the equality as linear combinations of
terms of the type

$a_{i}^{\beta_{1}}\otimes c_{j}^{\beta_{2}}\otimes e_{k}^{\beta_{3}}.$ (38)

The terms that have none of the indices $\beta_{1},\beta_{2},\beta_{3}$ equal
to $0$ can only come from a single side: the left-hand side if at least two
indices $1$ are involved, the right-hand if at most one is. The linear
independence of the families (30) (and hence of the products (38)) shows that
the contribution of these terms is zero. We are left with an equality between
terms which each have a factor of one of the types $a_{i}^{0}$, $c_{j}^{0}$,
$e_{k}^{0}$, so either side belongs to $R_{\mathrm{target}}$. These sides are
equal to $T-S^{\prime}$, so $T-S^{\prime}$ belongs to $R_{\mathrm{target}}$.
Since $S^{\prime}$ also does, we conclude that $T$ belongs to
$R_{\mathrm{target}}$, and $T$ therefore has slice rank at most
$r_{0}+s_{0}+t_{0}$, as desired. ∎

##  7 Proof of the theorem on sunflowers in the general case

In this section we show Proposition 3.2 and Theorem 3.3 for general $d$, the
proofs of which are based on and extend those of Proposition 6.2 and
Proposition 6.5 respectively. Whenever $X$ is a finite set and $m$ is a
nonnegative integer, we write $\mathcal{T}_{m}(X)$ for the set of $m$-tuples
$(j_{1},\dots,j_{m})$ where $j_{1},\dots,j_{m}$ are pairwise distinct elements
of $X$.

In order to avoid excessively heavy notation we will for instance for a linear
subspace $A_{j}$ of $\mathbb{F}^{n_{j}}$ write
$A_{j}\otimes(\otimes_{j^{\prime}\neq j}\mathbb{F}^{n_{j^{\prime}}})$ for the
tensor product that would more usually be written as

$(\otimes_{1\leq j^{\prime}<j}\mathbb{F}^{n_{j^{\prime}}})\otimes
A_{j}\otimes(\otimes_{j<j^{\prime}\leq d}\mathbb{F}^{n_{j^{\prime}}}).$

However, this should not cause any confusion to the reader, because the
dimension (in $[d]$) from which any term of any such product comes from will
always be clearly identified.

We begin by proving Proposition 3.2. The key additional idea for this proof,
compared to the $d=3$ case, is to gradually split terms of a slice rank
decomposition, which originally are products of one specified one-variable
function and one unspecified $(d-1)$-variable function, into products of $m$
specified one-variable functions and of one unspecified $(d-m)$-variable
function, for $m=1,2,\dots,d-1$ before finally writing the decomposition as a
product of $d$ specified one-variable functions. This process had been used in
relation to the slice rank in the proof of Lemma 9 from the _first_ version of
the manuscript [8]. Throughout the process, we collect terms together whenever
they are of the same type, which may involve cancellations, but as these are
all of the kind allowed in Definition 3.1, the definition of a tensor in zero
form, we conclude that the original decomposition was in zero form.

###### Proof of Proposition 3.2.

For every $j\in[d]$ let $(a_{j,1}^{*},\dots,a_{j,r_{j}}^{*})$ be a dual family
to the family $(a_{j,1},\dots,a_{j,r_{j}})$. For any fixed $j\in[d]$ and
$i\in[r_{j}]$, applying the function $a_{j,i}^{*}$ to the original
decomposition

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})$ (39)

of the zero tensor provides a decomposition of $b_{j,i}$ of the type

$b_{j,i}(\overline{x_{j}})=\sum_{j^{\prime}\neq
j}\sum_{i^{\prime}=1}^{r_{j^{\prime}}}a_{j^{\prime},i^{\prime}}(x_{j^{\prime}})p_{((j,i),(j^{\prime},i^{\prime}))}(\overline{x_{j},x_{j^{\prime}}}).$

Substituting for every $j\in[d]$ and every $i\in[r_{j}]$ these expressions in
the decomposition (39) we obtain

$\sum_{(j_{1},j_{2})\in\mathcal{T}_{2}([d])}\sum_{i_{1}\in[r_{j_{1}}],i_{2}\in[r_{j_{2}}]}a_{j_{1},i_{1}}(x_{j_{1}})a_{j_{2},i_{2}}(x_{j_{2}})p_{((j_{1},i_{1}),(j_{2},i_{2}))}(\overline{x_{j_{1}},x_{j_{2}}}).$

Gathering terms together whenever their sets
$\\{(j_{1},i_{1}),(j_{2},i_{2})\\}$ are the same, this decomposition of the
zero tensor can be rearranged as

$\sum_{1\leq j_{1}<j_{2}\leq
d}\sum_{i_{1}\in[r_{j_{1}}],i_{2}\in[r_{j_{2}}]}a_{j_{1},i_{1}}(x_{j_{1}})a_{j_{2},i_{2}}(x_{j_{2}})p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}(\overline{x_{j_{1}},x_{j_{2}}}).$
(40)

While doing this rearrangement we have potentially cancelled terms
corresponding to $|J|=2$ in Definition 3.1.

After that, for any fixed $(j_{1},j_{2})\in\mathcal{T}_{2}([d])$ and
$(i_{1},i_{2})\in[r_{j_{1}}]\times[r_{j_{2}}]$, applying
$a_{j_{1},i_{1}}^{*}\otimes a_{j_{2},i_{2}}^{*}$ leads to a decomposition

$\displaystyle
p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}(\overline{x_{j_{1}},x_{j_{2}}})=\sum_{j_{3}\in[d]\setminus\\{j_{1},j_{2}\\}}\sum_{i_{3}=1}^{r_{j_{3}}}a_{j_{3},i_{j_{3}}}(x_{j_{3}})p_{((j_{1},i_{1}),(j_{2},i_{2}),(i_{3},j_{3}))}^{|J|=3,\mathrm{main}}(\overline{x_{j_{1}},x_{j_{2}},x_{j_{3}}})+$
$\displaystyle\sum_{(j_{3},j_{4})\in\mathcal{T}_{2}([d]\setminus\\{j_{1},j_{2}\\})}\sum_{i_{3}\in[r_{j_{3}}],i_{4}\in[r_{j_{4}}]}a_{j_{3},i_{j_{3}}}(x_{j_{3}})a_{j_{4},i_{j_{4}}}(x_{j_{4}})p_{((j_{1},i_{1}),(j_{2},i_{2}),(i_{3},j_{3}),(i_{4},j_{4}))}^{|J|=3,\mathrm{secondary}}(\overline{x_{j_{1}},x_{j_{2}},x_{j_{3}},x_{j_{4}}}).$

The terms of the second type can in particular also be viewed as terms of the
first type, so we may write the simpler expression

$p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}(\overline{x_{j_{1}},x_{j_{2}}})=\sum_{j_{3}\in[d]\setminus\\{j_{1},j_{2}\\}}a_{j_{3},i_{j_{3}}}(x_{j_{3}})p_{((j_{1},i_{1}),(j_{2},i_{2}),(i_{3},j_{3}))}(\overline{x_{j_{1}},x_{j_{2}},x_{j_{3}}}).$

Substituting in (40) leads to the decomposition

$\sum_{(j_{1},j_{2},j_{3})\in\mathcal{T}_{3}([d])}\sum_{i_{1}\in[r_{j_{1}}],i_{2}\in[r_{j_{2}}],i_{3}\in[r_{j_{3}}]}a_{j_{1},i_{1}}(x_{j_{1}})a_{j_{2},i_{2}}(x_{j_{2}})a_{j_{3},i_{3}}(x_{j_{3}})p_{((j_{1},i_{1}),(j_{2},i_{2}),(j_{3},i_{3}))}(\overline{x_{j_{1}},x_{j_{2}},x_{j_{3}}}).$

We then gather terms together, this time whenever their sets
$\\{(j_{1},i_{1}),(j_{2},i_{2}),(j_{3},i_{3})\\}$ are the same. Our
decomposition of the zero tensor now becomes

$\sum_{1\leq j_{1}<j_{2}<j_{3}\leq
d}\sum_{i_{1}\in[r_{j_{1}}],i_{2}\in[r_{j_{2}}],i_{3}\in[r_{j_{3}}]}a_{j_{1},i_{1}}(x_{j_{1}})a_{j_{2},i_{2}}(x_{j_{2}})a_{j_{3},i_{3}}(x_{j_{3}})p_{\\{(j_{1},i_{1}),(j_{2},i_{2}),(j_{3},i_{3})\\}}(\overline{x_{j_{1}},x_{j_{2}},x_{j_{3}}}).$

Again, while doing this rearrangement we may have cancelled terms
corresponding to $|J|=3$ in Definition 3.1.

We then continue the process until our decomposition of the zero tensor has
become of the type

$\sum_{1\leq j_{1}<\dots<j_{d-1}\leq
d}\sum_{i_{j_{1}}\in[r_{j_{1}}],\dots,i_{j_{d-1}}\in[r_{j_{d-1}}]}\left(\prod_{1\leq
t\leq
d-1}a_{j_{t},i_{j_{t}}}(x_{j_{t}})\right)p_{\\{(j_{1},i_{1}),\dots,(j_{d-1},i_{d-1})\\}}(x_{j})$

where we write $j$ for the remaining element of $[d]$ aside from
$j_{1},\dots,j_{d-1}$. Until this point we may have cancelled terms
corresponding to $2\leq|J|\leq d-1$ in Definition 3.1. Applying products of
the type

$a_{j_{1},i_{1}}^{*}\otimes\dots\otimes a_{j_{d-1},i_{d-1}}^{*}$

we obtain that the functions

$p_{\\{(j_{1},i_{1}),\dots,(j_{d-1},i_{d-1})\\}}$

are linear combinations of the functions $a_{j,t_{j}}$. After cancelling terms
corresponding to $|J|=d$ in Definition 3.1, our decomposition of the zero
tensor becomes

$\sum_{i_{1}\in[r_{1}],\dots,i_{d}\in[r_{d}]}\lambda_{i_{1},\dots,i_{d}}a_{1,i_{1}}\otimes\dots\otimes
a_{d,i_{d}}$

for some $\lambda_{i_{1},\dots,i_{d}}\in\mathbb{F}$. These are necessarily all
zero since the tensor products

$a_{1,i_{1}}\otimes\dots\otimes a_{d,i_{d}}$

are linearly independent. The result follows. ∎

We finally move to the proof of Theorem 3.3. There again, we gradually split
terms of decompositions as we did in the proof of Proposition 3.2, while
carefully tracking down the specified one-variable functions in the terms that
appear. The main guiding heuristic behind the computations that we will make
is that at any point throughout the process, terms which have at least one
specified one-variable function of the type $a_{j,i}^{0}$ as a factor are
acceptable, as they do not get in the way of the desired conclusion, whereas
for terms which have none of these we aim to ensure that all specified one-
variable functions arising in the same product come from the same
decomposition $\theta$, and to that end we will use Theorem 3.3 for tensors of
lower-order, which leads to an inductive argument on the order $d$ of the
tensor. As in Section 6, notations such as
$p_{(j,i),(j^{\prime},i^{\prime})}^{\theta}$ will refer to functions depending
only on a single decomposition $\theta$, whereas notations such as
$p_{(j,i),(j^{\prime},i^{\prime})}^{\theta\theta^{\prime}}$ will refer to
functions depending on both decompositions $\theta,\theta^{\prime}$.

###### Proof of Theorem 3.3.

We proceed by induction on $d$. The base case is the case $d=2$, in other
words Proposition 6.6. Let us now assume $d\geq 3$, and suppose that the
result has been shown for all $d^{\prime}\in[2,d]$. We begin with the
decompositions

$\sum_{j=1}^{d}\left(\sum_{i=1}^{r_{j}^{0}}a_{j,i}^{0}(x_{j})b_{j,i}^{0,\theta}(\overline{x_{j}})+\sum_{i=1}^{r_{j}^{\theta}}a_{j,i}^{\theta}(x_{j})b_{j,i}^{\theta}(\overline{x_{j}})\right)$
(41)

of $T$ for each $\theta\in[h]$ for some $h>d$. For $j\in[d]$ and every
$\beta\in\\{0\\}\cup[h]$ we define

$A_{j}^{\beta}=\langle a_{j,i}^{\beta}:i\in[r_{j}^{\beta}]\rangle$

and for every $j\in[d]$ we choose a family

$(a_{j,i}^{\beta*}:\beta\in\\{0\\}\cup[h],i\in[r_{j}^{\beta}])$

of dual functions to the family

$(a_{j,i}^{\beta}:\beta\in\\{0\\}\cup[h],i\in[r_{j}^{\beta}]).$

We start the first step of the splitting process. Let $j\in[d]$ and
$i\in[r_{j}^{1}]$ be fixed. We write the equality between the decompositions
$1$ and $2$ of $T$, and apply the function $a_{j,i}^{1*}$. This leads to an
expression of the type

$\displaystyle b_{j,i}^{1}(\overline{x_{j}})$
$\displaystyle=\sum_{j^{\prime}\neq
j}\sum_{i^{\prime}=1}^{r_{j^{\prime}}^{1}}a_{j^{\prime},i^{\prime}}^{1}(x_{j^{\prime}})p_{(j,i),(j^{\prime},i^{\prime})}^{1}(\overline{x_{j},x_{j^{\prime}}})$
$\displaystyle-\sum_{j^{\prime}\neq
j}\sum_{i^{\prime}=1}^{r_{j^{\prime}}^{2}}a_{j^{\prime},i^{\prime}}^{2}(x_{j^{\prime}})p_{(j,i),(j^{\prime},i^{\prime})}^{12}(\overline{x_{j},x_{j^{\prime}}})$
$\displaystyle+\sum_{j^{\prime}\neq
j}\sum_{i^{\prime}=1}^{r_{j^{\prime}}^{0}}a_{j^{\prime},i^{\prime}}^{0}(x_{j^{\prime}})(p_{(j,i),(j^{\prime},i^{\prime})}^{0,1}-p_{(j,i),(j^{\prime},i^{\prime})}^{0,12})(\overline{x_{j},x_{j^{\prime}}}).$

We had started with at least $d+1$ decompositions of $T$, so there are at
least $d$ of them that are distinct from $1$. Applying the inductive
hypothesis to the order-$(d-1)$ tensor $b_{j,i}^{1}$, with for every
$j^{\prime}\neq j$ the functions $a_{j^{\prime},i^{\prime}}^{0}$ and
$a_{j^{\prime},i^{\prime}}^{1}$ together forming a basis of center functions
and the functions $a_{j^{\prime},i^{\prime}}^{\theta}$ forming for each
$\theta\neq 1$ a basis of petal functions, we obtain

$b_{j,i}^{1}\in(A_{1}^{0}+A_{1}^{1})\otimes(\otimes_{j^{\prime}\notin\\{j,1\\}}\mathbb{F}^{n_{j^{\prime}}})+\dots+(\otimes_{j^{\prime}\notin\\{j,d\\}}\mathbb{F}^{n_{j^{\prime}}})\otimes(A_{d}^{0}+A_{d}^{1}).$

We likewise obtain such a description of the functions $b_{j,i}^{\theta}$ for
each $\theta\in[h]$. Writing the equality between the decompositions $1$ and
$2$ that we started with (41) and applying the functions $a_{j,i}^{0*}$ we
obtain

$b_{j,i}^{0,1}-b_{j,i}^{0,2}\in(A_{1}^{0}+A_{1}^{1}+A_{1}^{2})\otimes(\otimes_{j^{\prime}\notin\\{j,1\\}}\mathbb{F}^{n_{j^{\prime}}})+\dots+(\otimes_{j^{\prime}\notin\\{j,d\\}}\mathbb{F}^{n_{j^{\prime}}})\otimes(A_{d}^{0}+A_{d}^{1}+A_{d}^{2}).$

We write $S_{0}$ for the part

$\sum_{j=1}^{d}\sum_{i=1}^{r_{j}^{0}}a_{j,i}^{0}(x_{j})b_{j,i}^{0,1}(\overline{x_{j}})$

of the decomposition $1$ of $T$ with central one-variable functions. This
tensor belongs to the subspace

$R_{\mathrm{target}}=(A_{1}^{0}\otimes\mathbb{F}^{n_{2}}\otimes\dots\otimes\mathbb{F}^{n_{d}})+\dots+(\mathbb{F}^{n_{1}}\otimes\dots\otimes\mathbb{F}^{n_{d-1}}\otimes
A_{d}^{0}).$

We then consider decompositions of $T-S_{0}$. The equality between the
resulting decompositions $1$ and $2$ can be written as

$T_{1}+T_{\Delta}=T_{2},$ (42)

with

$\displaystyle T_{1}$
$\displaystyle\in+_{(j_{1},j_{2})\in\mathcal{T}_{2}([d])}(A_{j_{1}}^{1}\otimes(A_{j_{2}}^{0}\oplus
A_{j_{2}}^{1})\otimes(\otimes_{j\notin\\{j_{1},j_{2}\\}}\mathbb{F}^{n_{j}}))$
(43) $\displaystyle T_{2}$
$\displaystyle\in+_{(j_{1},j_{2})\in\mathcal{T}_{2}([d])}(A_{j_{1}}^{2}\otimes(A_{j_{2}}^{0}\oplus
A_{j_{2}}^{2})\otimes(\otimes_{j\notin\\{j_{1},j_{2}\\}}\mathbb{F}^{n_{j}}))$
(44) $\displaystyle T_{\Delta}$
$\displaystyle\in+_{(j_{1},j_{2})\in\mathcal{T}_{2}([d])}(A_{j_{1}}^{0}\otimes(A_{j_{2}}^{0}\oplus
A_{j_{2}}^{1}\oplus
A_{j_{2}}^{2})\otimes(\otimes_{j\notin\\{j_{1},j_{2}\\}}\mathbb{F}^{n_{j}}))$
(45)

where the unspecified $(d-2)$-variable functions in
$\otimes_{j\notin\\{j_{1},j_{2}\\}}\mathbb{F}^{n_{j}}$ from (43) and (44)
respectively depend on the decompositions $1$ only and $2$ only.

In any of these three tensors, any term of the decomposition that we have
obtained is split as a product of two specified one-variable functions and one
unspecified $(d-2)$-variable function. Whenever some of the resulting terms
have the same pair of specified one-variable functions, we gather them
together into a single term, even if the original two terms come from
different sides of the equality. For instance, the two terms

$\displaystyle
a_{1,i_{1}}^{1}(x_{1})a_{2,i_{2}}^{0}(x_{2})p^{\prime}(x_{3},\dots,x_{d})$
$\displaystyle
a_{1,i_{1}}^{1}(x_{1})a_{2,i_{2}}^{0}(x_{2})p^{\prime\prime}(x_{3},\dots,x_{d})$

for some unspecified functions $p^{\prime},p^{\prime\prime}$ would be replaced
by a single term

$a_{1,i_{1}}^{1}(x_{1})a_{2,i_{2}}^{0}(x_{2})p(x_{3},\dots,x_{d}).$

Because we gather terms even if they come from different sides of the original
equality, the resulting equality is in general no longer between two
decompositions of $T-S_{0}$, but between two decompositions of $T-S_{1}$ for
some new tensor $S_{1}$. However, since in the expressions of
$T_{1},T_{2},T_{\Delta}$ given by (43), (44), (45) there is no term with both
a function of the type $a_{j,i}^{1}$ and a function of the type $a_{j,i}^{2}$
as its specified two one-variable functions, any term which has neither of the
two specified one-variable functions of the type $a_{j,i}^{0}$ must
necessarily have both its specified one-variable functions of the type
$a_{j,i}^{1}$, or both its specified one-variable functions of the type
$a_{j,i}^{2}$, in which case the term may only arise in the left-hand side or
in the right-hand side of (42) respectively. The difference $S_{1}-S_{0}$
hence only involves terms which have some $a_{j,i}^{0}$ as a factor; in other
words $S_{1}-S_{0}$ belongs to $R_{\mathrm{target}}$. Since $S_{0}$ belongs to
$R_{\mathrm{target}}$, it follows that $S_{1}$ belongs to
$R_{\mathrm{target}}$. Without loss of generality this equality is of the type

$\displaystyle\sum_{1\leq j_{1}<j_{2}\leq
d}\sum_{i_{1}\in[r_{j_{1}}^{1}],i_{2}\in[r_{j_{2}}^{1}]}a_{j_{1},i_{1}}^{1}(x_{j_{1}})a_{j_{2},i_{2}}^{1}(x_{j_{2}})p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}^{1}(\overline{x_{j_{1}},x_{j_{2}}})$
$\displaystyle+$
$\displaystyle\sum_{(j_{1},j_{2})\in\mathcal{T}_{2}([d])}\sum_{\beta\in\\{0,1,2\\}}\sum_{i_{1}\in[r_{j_{1}}^{0}],i_{2}\in[r_{j_{2}}^{\beta}]}a_{j_{1},i_{1}}^{0}(x_{j_{1}})a_{j_{2},i_{2}}^{\beta}(x_{j_{2}})p_{((j_{1},i_{1}),(j_{2},i_{2})),\beta}^{12}(\overline{x_{j_{1}},x_{j_{2}}})$
$\displaystyle=$ $\displaystyle\sum_{1\leq j_{1}<j_{2}\leq
d}\sum_{i_{1}\in[r_{j_{1}}^{2}],i_{2}\in[r_{j_{2}}^{2}]}a_{j_{1},i_{1}}^{2}(x_{j_{1}})a_{j_{2},i_{2}}^{2}(x_{j_{2}})p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}^{2}(\overline{x_{j_{1}},x_{j_{2}}})$
(46)

since terms with a factor of the type $a_{j_{1},i_{1}}^{0}$ may be collected
on either side of the equality. This finishes the first step of the splitting
process.

We now start the second step. In the equality (46), we consider some distinct
elements $j_{1},j_{2}$ of $[d]$ and some $i_{1}\in[r_{j_{1}}^{1}]$,
$i_{2}\in[r_{j_{2}}^{1}]$, and apply $a_{j_{1},i_{1}}^{1*}\otimes
a_{j_{2},i_{2}}^{1*}$. This leads to

$p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}^{1}\in+_{j\notin\\{j_{1},j_{2}\\}}((A_{j}^{0}\oplus
A_{j}^{1}\oplus
A_{j}^{2})\otimes(\otimes_{j^{\prime}\notin\\{j_{1},j_{2},j\\}}\mathbb{F}^{n_{j^{\prime}}})).$

Applying Theorem 3.3 for order-$(d-2)$ tensors, with for every
$j\notin\\{j_{1},j_{2}\\}$ the functions $a_{j,i}^{0}$ and $a_{j,i}^{1}$
together forming a basis of center functions and the functions
$a_{j,i}^{\theta}$ forming for each $\theta\neq 1$ a basis of petal functions,
we obtain

$p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}^{1}\in+_{j\notin\\{j_{1},j_{2}\\}}((A_{j}^{0}\oplus
A_{j}^{1})\otimes(\otimes_{j^{\prime}\notin\\{j_{1},j_{2},j\\}}\mathbb{F}^{n_{j^{\prime}}}))$

where the unspecified $(d-3)$-variable functions in
$\otimes_{j^{\prime}\notin\\{j_{1},j_{2},j\\}}\mathbb{F}^{n_{j^{\prime}}}$
depend on the decomposition $1$ only. We obtain a similar statement for the
function $p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}^{2}$. Returning to the
equality (46) between two decompositions of $T-S_{1}$, we apply the other
products, that is, those of any of the types

$a_{j_{1},i_{1}}^{0*}\otimes a_{j_{2},i_{2}}^{0*}\text{,
}a_{j_{1},i_{1}}^{0*}\otimes a_{j_{2},i_{2}}^{1*}\text{,
}a_{j_{1},i_{1}}^{0*}\otimes a_{j_{2},i_{2}}^{2*}$

(as there are no terms where a product of the type $a_{j_{1},i_{1}}^{1}\otimes
a_{j_{2},i_{2}}^{2}$ appears, there is no need to apply any
$a_{j_{1},i_{1}}^{1*}\otimes a_{j_{2},i_{2}}^{2*})$. We obtain

$p_{((j_{1},i_{1}),(j_{2},i_{2})),\beta}^{12}\in+_{j\notin\\{j_{1},j_{2}\\}}((A_{j}^{0}\oplus
A_{j}^{1}\oplus
A_{j}^{2})\otimes(\otimes_{j^{\prime}\notin\\{j_{1},j_{2},j\\}}\mathbb{F}^{n_{j^{\prime}}}))$

for all $(j_{1},j_{2})\in\mathcal{T}_{2}([d])$, all $\beta\in\\{0,1,2\\}$ and
all $i_{1}\in[r_{j_{1}}^{0}]$ and $i_{2}\in[r_{j_{2}}^{\beta}]$.

We then substitute in the equality (46) between decompositions of $T-S_{1}$,
and are left with an equality between two sides which are each sums of
products of four functions, with each product containing three specified one-
variable functions and one unspecified function in the remaining $d-3$
variables. We factor together any terms which have the same three specified
one-variable functions, even if this requires changing which side of the
equality they are on. This leads to an equality between two decompositions of
$T-S_{2}$ for some new tensor $S_{2}$. We note that the triples of specified
one-variable functions are of one of two types: either they contain at least
one term of the type $a_{j,i}^{0}$, or they do not, in which case they are
necessarily of one of the types

$a_{j_{1},i_{1}}^{1}\otimes a_{j_{2},i_{2}}^{1}\otimes
a_{j_{3},i_{3}}^{1}\text{, }a_{j_{1},i_{1}}^{2}\otimes
a_{j_{2},i_{2}}^{2}\otimes a_{j_{3},i_{3}}^{2}.$ (47)

Furthermore, if a term has its product of specified one-variable functions of
these two latter types, then it may only arise in the left-hand side or in the
right-hand side respectively. All terms involved in the difference
$S_{2}-S_{1}$ hence have a function of the type $a_{j,i}^{0}$ as a factor, so
$S_{2}-S_{1}$ belongs to $R_{\mathrm{target}}$. Since $S_{1}$ also does, we
conclude that $S_{2}$ belongs to $R_{\mathrm{target}}$.

We emphasize that we have shown that for terms which have their product of
three specified one-variable functions as the first (resp. the second) of
(47), the unspecified $(d-3)$-variable function depends only on the
decomposition 1 (resp. 2). This guarantees that the next time that we apply
Theorem 3.3 to a lower-order tensor, we indeed apply it to several
decompositions of the same tensor. (Likewise, when applying Theorem 3.3 in the
step that we are now completing, we have used that the function
$p_{\\{(j_{1},i_{1}),(j_{2},i_{2})\\}}^{1}$ was the same whenever we wrote an
equality between decompositions from $\theta=1$ and from any other value of
$\theta$.) We have now obtained an equality of the type

$\displaystyle\sum_{1\leq j_{1}<j_{2}<j_{3}\leq
d}\sum_{i_{1}\in[r_{j_{1}}^{1}],i_{2}\in[r_{j_{2}}^{1}],i_{3}\in[r_{j_{3}}^{1}]}a_{j_{1},i_{1}}^{1}(x_{j_{1}})a_{j_{2},i_{2}}^{1}(x_{j_{2}})a_{j_{3},i_{3}}^{1}(x_{j_{3}})p_{\\{(j_{1},i_{1}),(j_{2},i_{2}),(j_{3},i_{3})\\}}^{1}(\overline{x_{j_{1}},x_{j_{2}},x_{j_{3}}})$
$\displaystyle+$ $\displaystyle\sum_{1\leq j_{1}<j_{2}<j_{3}\leq
d}\sum_{(\beta_{1},\beta_{2},\beta_{3})\in\\{0,1,2\\}^{3}\setminus\\{1,2\\}^{3}}\sum_{i_{1}\in[r_{j_{1}}^{\beta_{1}}],i_{2}\in[r_{j_{2}}^{\beta_{2}}],i_{3}\in[r_{j_{3}}^{\beta_{3}}]}a_{j_{1},i_{1}}^{\beta_{1}}(x_{j_{1}})a_{j_{2},i_{2}}^{\beta_{2}}(x_{j_{2}})a_{j_{3},i_{3}}^{\beta_{3}}(x_{j_{3}})$
$\displaystyle
p_{\\{(j_{1},i_{1},\beta_{1}),(j_{2},i_{2},\beta_{2}),(j_{3},i_{3},\beta_{3})\\}}^{12}(\overline{x_{j_{1}},x_{j_{2}},x_{j_{3}}})$
$\displaystyle=$ $\displaystyle\sum_{1\leq j_{1}<j_{2}<j_{3}\leq
d}\sum_{i_{1}\in[r_{j_{1}}^{2}],i_{2}\in[r_{j_{2}}^{2}],i_{3}\in[r_{j_{3}}^{2}]}a_{j_{1},i_{1}}^{2}(x_{j_{1}})a_{j_{2},i_{2}}^{2}(x_{j_{2}})a_{j_{3},i_{3}}^{2}(x_{j_{3}})p_{\\{(j_{1},i_{1}),(j_{2},i_{2}),(j_{3},i_{3})\\}}^{2}(\overline{x_{j_{1}},x_{j_{2}},x_{j_{3}}}).$

This finishes the second step of the splitting process. We then continue the
process in a similar way. For every $m\in[d-1]$, at the end of the $m-1$th
step we have obtained a tensor $S_{m-1}$ in $R_{\mathrm{target}}$, and an
equality between two decompositions of $T-S_{m-1}$ of the type

$\displaystyle\sum_{1\leq j_{1}<\dots<j_{m}\leq
d}\sum_{i_{1}\in[r_{j_{1}}^{1}],\dots,i_{m}\in[r_{j_{m}}^{1}]}a_{j_{1},i_{1}}^{1}(x_{j_{1}})\dots
a_{j_{m},i_{m}}^{1}(x_{j_{m}})p_{\\{(j_{1},i_{1}),\dots,(j_{m},i_{m})\\}}^{1}(\overline{x_{j_{1}},\dots,x_{j_{m}}})$
$\displaystyle+$ $\displaystyle\sum_{1\leq j_{1}<\dots<j_{m}\leq
d}\sum_{(b_{1},\dots,\beta_{m})\in\\{0,1,2\\}^{m}\setminus\\{1,2\\}^{m}}\sum_{i_{1}\in[r_{j_{1}}^{\beta_{1}}],\dots,i_{m}\in[r_{j_{m}}^{\beta_{m}}]}a_{j_{1},i_{1}}^{\beta_{1}}(x_{j_{1}})\dots
a_{j_{m},i_{m}}^{\beta_{m}}(x_{j_{m}})$ $\displaystyle
p_{\\{(j_{1},i_{1},\beta_{1}),\dots,(j_{m},i_{m},\beta_{m})\\}}^{12}(\overline{x_{j_{1}},\dots,x_{j_{m}}})$
$\displaystyle=$ $\displaystyle\sum_{1\leq j_{1}<\dots<j_{m}\leq
d}\sum_{i_{1}\in[r_{j_{1}}^{2}],\dots,i_{m}\in[r_{j_{m}}^{2}]}a_{j_{1},i_{1}}^{2}(x_{j_{1}})\dots
a_{j_{m},i_{m}}^{2}(x_{j_{m}})p_{\\{(j_{1},i_{1}),\dots,(j_{m},i_{m})\\}}^{2}(\overline{x_{j_{1}},\dots,x_{j_{m}}}).$

The important features of this equality are the following.

  1. (i)

All terms of both sides are products of $m+1$ functions, $m$ of which are
specified one-variable functions of the type $a_{j,i}^{\beta}$ and the
remaining one of which is an unspecified function in the other $d-m$
variables.

  2. (ii)

Whenever $j_{1},\dots,j_{m}$ are pairwise distinct indices in $[d]$,
$\beta_{1},\dots,\beta_{m}$ are in $\\{0,1,2\\}$, and
$i_{1}\in[r_{j_{1}}^{\beta_{1}}],\dots,i_{m}\in[r_{j_{m}}^{\beta_{m}}]$ are
indices, there is only at most one term in total (from both the left-hand and
right-hand sides) that has

$\otimes_{1\leq t\leq m}a_{j_{t},i_{t}}^{\beta_{t}}$

as the product of its $m$ specified one-variable functions.

  3. (iii)

Whenever a term does not have any function of the type $a_{j,i}^{0}$ as a
factor, its product of specified one-variable functions is of one of the types

$\otimes_{1\leq t\leq m}a_{j_{t},i_{t}}^{1}\text{, }\otimes_{1\leq t\leq
m}a_{j_{t},i_{t}}^{2},$

and it must come from the left-hand side and from the right-hand side
respectively in these cases.

  4. (iv)

In the situation of terms described in the previous item, the remaining
unspecified $(d-m)$-variable functions depend only on the decompositions $1$
and $2$ respectively.

In particular, after $d-2$ steps we have an equality between two
decompositions of $T-S_{d-2}$, that obeys the properties above for $m=d-1$.
This equality is of the type

$\displaystyle\sum_{j=1}^{d}\sum_{i_{[d]\setminus\\{j\\}}\in\prod_{j^{\prime}\neq
j}[r_{j^{\prime}}^{1}]}\left(\prod_{j^{\prime}\neq
j}a_{j^{\prime},i_{j^{\prime}}}^{1}(x_{j^{\prime}})\right)p_{j,i_{[d]\setminus\\{j\\}}}^{1}(x_{j})$
$\displaystyle+$
$\displaystyle\sum_{j=1}^{d}\sum_{\beta_{[d]\setminus\\{j\\}}\in\\{0,1,2\\}^{[d]\setminus\\{j\\}}\setminus\\{1,2\\}^{[d]\setminus\\{j\\}}}\sum_{i_{[d]\setminus\\{j\\}}\in\prod_{j^{\prime}\neq
j}[r_{j^{\prime}}^{\beta_{j^{\prime}}}]}\left(\prod_{j^{\prime}\neq
j}a_{j^{\prime},i_{j^{\prime}}}^{\beta_{j^{\prime}}}(x_{j^{\prime}})\right)p_{j,i_{[d]\setminus\\{j\\}},\beta_{[d]\setminus\\{j\\}}}^{12}(x_{j})$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{d}\sum_{i_{[d]\setminus\\{j\\}}\in\prod_{j^{\prime}\neq
j}[r_{j^{\prime}}^{2}]}\left(\prod_{j^{\prime}\neq
j}a_{j^{\prime},i_{j^{\prime}}}^{2}(x_{j^{\prime}})\right)p_{j,i_{[d]\setminus\\{j\\}}}^{2}(x_{j})$

where we have written $i_{[d]\setminus\\{j\\}}$ for
$(i_{j^{\prime}})_{j^{\prime}\in[d]\setminus\\{j\\}}$ and
$\beta_{[d]\setminus\\{j\\}}$ for
$(\beta_{j^{\prime}})_{j^{\prime}\in[d]\setminus\\{j\\}}$.

Each term is now a product of $d$ one-variable functions, where $d-1$ of them
are specified functions of the type $a_{j,i}^{\beta}$ and the last one is an
unspecified function. Applying one last time the products of the $d-1$ one-
variable specified functions shows that the unspecified function is a linear
combination of functions of the type $a_{j,i}^{\beta}$ (for the relevant value
of $j$). After yet again gathering terms, we obtain some tensor $S_{d-1}\in
R_{\mathrm{target}}$ and an equality between two decompositions of $T-S_{d-1}$
of the type

$\displaystyle\sum_{i_{1}\in[r_{1}^{1}],\dots,i_{d}\in[r_{d}^{1}]}\lambda_{(1,i_{1},1),\dots,(d,i_{d},1)}a_{1,i_{1}}^{1}(x_{1})\dots
a_{d,i_{d}}^{1}(x_{d})$ $\displaystyle+$
$\displaystyle\sum_{j=1}^{d}\sum_{i_{[d]\setminus\\{j\\}}\in\prod_{j^{\prime}\neq
j}[r_{j^{\prime}}^{1}]}\lambda_{(1,i_{1},1),\dots,(j-1,i_{j-1},1),(j,i_{j},2),(j+1,i_{j+1},1),\dots,(d,i_{d},1)}\left(\prod_{j^{\prime}\neq
j}a_{j^{\prime},i_{j^{\prime}}}^{1}(x_{j^{\prime}})\right)a_{j,i_{j}}^{2}(x_{j})$
$\displaystyle+$
$\displaystyle\sum_{(\beta_{1},\dots,\beta_{d})\in\\{0,1,2\\}^{d}\setminus\\{1,2\\}^{d}}\sum_{i_{1}\in[r_{1}^{\beta_{1}}],\dots,i_{d}\in[r_{d}^{\beta_{d}}]}\lambda_{(1,i_{1},\beta_{1}),\dots,(d,i_{d},\beta_{d})}a_{1,i_{1}}^{\beta_{1}}(x_{1})\dots
a_{d,i_{d}}^{\beta_{d}}(x_{d})$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{d}\sum_{i_{[d]\setminus\\{j\\}}\in\prod_{j^{\prime}\neq
j}[r_{j^{\prime}}^{2}]}\lambda_{(1,i_{1},2),\dots,(j-1,i_{j-1},2),(j,i_{j},1),(j+1,i_{j+1},2),\dots,(d,i_{d},2)}\left(\prod_{j^{\prime}\neq
j}a_{j^{\prime},i_{j^{\prime}}}^{2}(x_{j^{\prime}})\right)a_{j,i_{j}}^{1}(x_{j})$
$\displaystyle+$
$\displaystyle\sum_{i_{1}\in[r_{1}^{2}],\dots,i_{d}\in[r_{d}^{2}]}\lambda_{(1,i_{1},2),\dots,(d,i_{d},2)}a_{1,i_{1}}^{2}(x_{1})\dots
a_{d,i_{d}}^{2}(x_{d})$ (48)

for some
$\lambda_{(1,i_{1},\beta_{1}),\dots,(d,i_{d},\beta_{d})}\in\mathbb{F}$. In
this equality, all terms on both sides are multiples of products of the type

$a_{1,i_{1}}^{\beta_{1}}\otimes\dots\otimes a_{d,i_{d}}^{\beta_{d}}.$ (49)

If a term has $\beta_{j}\neq 0$ for every $j\in[d]$, then it has either at
least $d-1$ or at most one index equal to $1$ (and the remaining ones are
equal to $2$), and in these two cases it necessarily must come from the left-
hand and right-hand side respectively, so the sets of values of
$(\beta_{1},\dots,\beta_{d})$ from the terms appearing in both sides are
disjoint. Because the products (49) are linearly independent, it follows that
either side of (48) is equal to $0$. These sides are equal to $T-S_{d-1}$, so
we have shown $T=S_{d-1}$. Therefore, $T$ belongs to $R_{\mathrm{target}}$. In
particular it has the desired decomposition and has slice rank at most

$r_{1}^{0}+\dots+r_{d}^{0}.\qed$

##  8 Open questions

Let us finish by discussing a few questions that are left open by our current
results and proofs. As we had explained in Section 5, in the tensor rank case
the exponent in the upper bound that we show on the number of minimal-length
tensor rank decompositions cannot be improved by more than a factor of $d$,
but this nonetheless does not give a complete answer to our first question.

######  Question 8.1.

What are the optimal bounds in Proposition 5.1, and for which tensors are they
attained ?

Returning to the slice rank, Example 3.6 shows that Theorem 3.5 is false for
infinite fields, that in the finite field case the bounds cannot be uniform
with respect to $\mathbb{F}$, and furthermore that even in the finite field
case they grow square-exponentially in the slice rank of the tensor. This
leads us instead to the following formulation, which we believe provides a
statement of a similar kind and which is uniform over all fields.

######  Conjecture 8.2.

Let $d\geq 3$, $k\geq 1$ be integers. Then there exists a positive integer
$C(d,k)$ such that the following holds. Let $T$ be an order-$d$ tensor over
some arbitrary field $\mathbb{F}$ and with slice rank equal to $k$. Then there
exist linear subspaces

$A_{1}\subset\mathbb{F}^{n_{1}},\dots,A_{d}\subset\mathbb{F}^{n_{d}}$

each with dimension at most $C(d,k)$ such that if $r_{1},\dots,r_{d}$ are
nonnegative integers satisfying

$r_{1}+\dots+r_{d}=k$

and $a_{j,i}:[n_{j}]\to\mathbb{F}$ with $j\in[d]$ and $i\in[r_{j}]$ are
functions satisfying

$T(x_{1},\dots,x_{d})=\sum_{j=1}^{d}\sum_{i=1}^{r_{j}}a_{j,i}(x_{j})b_{j,i}(\overline{x_{j}})$

for some $(d-1)$-variable functions $b_{j,i}:\prod_{j^{\prime}\neq
j}[n_{j^{\prime}}]\to\mathbb{F}$, then

$\langle a_{1,1},\dots,a_{1,r_{1}}\rangle\subset A_{1},\dots,\langle
a_{d,1},\dots,a_{d,r_{d}}\rangle\subset A_{d}.$

We would furthermore not be surprised if for any fixed $d\geq 3$ we could take
$C(k,d)$ to be linear in $k$, as we have not managed to build a counterexample
disproving this.

######  Question 8.3.

Is Conjecture 8.2 true with furthermore $C(k,d)=O(k)$ for every $d\geq 3$ ?

One further direction in which we believe that our results can be taken
further is that of formulating and proving suitable generalisations of Theorem
3.3 and Theorem 3.5 for other notions of rank. As described in the
introduction, one such notion that is of interest is the partition rank.

######  Question 8.4.

Can we prove an analogue of Theorem 3.5 for the partition rank ?

As was the case for the slice rank, formulating the property already appears
to be challenging, and it is useful to keep in mind that the five ways in
which various slice rank decompositions can arise all extend to the partition
rank. Let us finish by describing these extensions. For $d\geq 2$ an integer,
we write $\mathcal{B}_{2}([d])$ for the set of bipartitions $\\{J,J^{c}\\}$ of
$[d]$ with $J,J^{c}\neq\emptyset$. We recall that if $d\geq 2$ is an integer,
$J$ is a subset of $[d]$, then for every $x\in[n_{1}]\times\dots\times[n_{d}]$
we write $x(J)$ for the restriction of $x$ to its coordinates in $J$. Let us
also recall the definition of the partition rank.

######  Definition 8.5.

Let $d\geq 2$ be an integer, and let
$T:[n_{1}]\times\dots\times[n_{d}]\to\mathbb{F}$ be an order-$d$ tensor. We
say that the _partition rank_ of $T$, denoted by $\operatorname{pr}T$, is the
smallest nonnegative integer $k$ such that there exist nonnegative integers
$r_{\\{J,J^{c}\\}}$ for each bipartition
$\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])$, such that

$\sum_{\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])}r_{\\{J,J^{c}\\}}=k$

and satisfying one of the following two equivalent properties.

  1. 1.

There exist matrices $M_{\\{J,J^{c}\\}}:(\prod_{j\in
J}[n_{j}])\times(\prod_{j\in J^{c}}[n_{j}])\to\mathbb{F}$ with rank at most
$r_{\\{J,J^{c}\\}}$ for each $\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])$ such that

$T(x_{1},\dots,x_{d})=\sum_{\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])}M_{\\{J,J^{c}\\}}(x(J),x(J^{c}))$
(50)

is satisfied for all $(x_{1},\dots,x_{d})\in[n_{1}]\times\dots\times[n_{d}]$.

  2. 2.

For each $\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])$ and each
$i\in[r_{\\{J,J^{c}\\}}]$ there exist some functions $a_{J,i}:\prod_{j\in
J}[n_{j}]\to\mathbb{F}$ and $b_{J^{c},i}:\prod_{j\in
J^{c}}[n_{j}]\to\mathbb{F}$ such that

$T(x_{1},\dots,x_{d})=\sum_{\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])}\sum_{i=1}^{r_{\\{J,J^{c}\\}}}a_{J,i}(x(J))b_{J^{c},i}(x(J^{c}))$
(51)

is satisfied for all $(x_{1},\dots,x_{d})\in[n_{1}]\times\dots\times[n_{d}]$.

We say that an expression such as (51) is a _partition rank decomposition_ of
$T$, say that the _length_ of the decomposition is the integer

$\sum_{\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])}r_{\\{J,J^{c}\\}},$

and say that the decomposition has _minimal length_ if its length is equal to
the partition rank of $T$.

Constructions 1 to 5 respectively adapt to the following. Let $d\geq 3$,
$k\geq 1$ be integers, and let $T$ be an order-$d$ tensor with partition rank
$k$.

######  Construction 6.

_If $M_{\\{J,J^{c}\\}}:(\prod_{j\in J}[n_{j}])\times(\prod_{j\in
J^{c}}[n_{j}])\to\mathbb{F}$ with $\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])$ are
matrices satisfying (50) and_

$\sum_{\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])}\operatorname{rk}M_{\\{J,J^{c}\\}}=\operatorname{pr}T,$

_then rewriting any minimal-length matrix decomposition of any of the matrices
$M_{\\{J,J^{c}\\}}$ leads to a new minimal-length partition rank decomposition
of $T$._

######  Construction 7.

_If the tensor rank of $T$ is equal to the partition rank $k$ of $T$, and_

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k}a_{1,i}(x_{1})\dots a_{d,i}(x_{d})$

_is a length- $k$ tensor rank decomposition of $T$ then for any map
$\iota:[k]\to\mathcal{B}_{2}([d])$ the decomposition_

$T(x_{1},\dots,x_{d})=\sum_{\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])}\sum_{i\in\iota^{-1}(\\{J,J^{c}\\})}(\prod_{j\in
J}a_{j,i})(x(J))(\prod_{j\in J^{c}}a_{j,i})(x(J^{c}))$

_is a minimal-length partition rank decomposition of $T$. This is merely the
most extreme form that this construction can take, and tensors $T$ satisfying
much weaker assumptions than $\operatorname{pr}T=\operatorname{tr}T$ will lend
themselves to it. For instance if $T$ has partition rank $k$ and can merely be
written as_

$T(x_{1},\dots,x_{d})=\sum_{i=1}^{k}a_{i,J_{i,1}}(x(J_{i,1}))a_{i,J_{i,2}}(x(J_{i,2}))a_{i,J_{i,3}}(x(J_{i,3}))$

_where for every $i\in[k]$ the set $\\{J_{i,1},J_{i,2},J_{i,3}\\}$ is a
tripartition of $[d]$ with $J_{i,1},J_{i,2},J_{i,3}$ each non-empty and
$a_{i,J_{i,s}}:\prod_{j\in J_{i,s}}[n_{j}]\to\mathbb{F}$ is a function for
each $s=1,2,3$ then we already obtain different minimal-length decompositions
of $T$ depending on how we view each summand as a product of two terms._

######  Construction 8.

_A tensor $[k]^{d}\to\mathbb{F}$ usually has partition rank equal to $k$.
Indeed, for any $d\geq 3$, if the field $\mathbb{F}$ is finite then there are
at most_

$k^{2^{d}}|\mathbb{F}|^{(k-1)(k^{d-1}+k)}\leq(k^{2^{d}}/|\mathbb{F}|^{k})|\mathbb{F}|^{k^{d}}$

_tensors with partition rank at most $k-1$. So writing $T$ as the sum of its
$(d-1)$-variable slices as in Construction 3 again provides $d$ minimal-length
partition rank decomposition of $T$. We can also write $T$ as a sum of its
$d^{\prime}$-variable slices for $d^{\prime}<d-1$, but the resulting partition
rank decomposition then has length $k^{d-d^{\prime}}>k$, which is not minimal,
and we hence have less of a generalisation in this direction._

######  Construction 9.

_If the decomposition_

$T(x_{1},\dots,x_{d})=\sum_{\\{J,J^{c}\\}\in\mathcal{B}_{2}([d])}\sum_{i=1}^{r_{\\{J,J^{c}\\}}}a_{J,i}(x(J))a_{J^{c},i}(x(J^{c}))$

_is a minimal-length decomposition of $T$, $\\{J_{1},J_{2},J\\}$ is a
tripartition of $[d]$ with $J_{1},J_{2}$ each with size at least $1$,
$i_{1}\in[r_{\\{J_{1},J_{1}^{c}\\}}]$ and
$i_{2}\in[r_{\\{J_{2},J_{2}^{c}\\}}]$ are indices, and $c:\prod_{j\in
J}[n_{j}]\to\mathbb{F}$ is a function if $J$ is non-empty and an element of
$\mathbb{F}$ otherwise, then replacing $a_{J_{1}^{c},i_{1}}$ and
$a_{J_{2}^{c},i_{2}}$ by respectively_

$a_{J_{1}^{c},i_{1}}+a_{I_{2},i_{2}}\otimes c\text{ and
}a_{J_{2}^{c},i_{2}}-a_{J_{1},i_{1}}\otimes c$

_leads to a new minimal-length partition rank decomposition of $T$._

######  Construction 10.

_More generally, if $s\in[2,d]$ is an integer, $\\{J_{1},\dots,J_{s},J\\}$ is
a partition of $[d]$ with $J_{1},\dots,J_{s}$ each with size at least $1$,
$i_{1}\in[r_{\\{J_{1},J_{1}^{c}\\}}],\dots,i_{s}\in[r_{\\{J_{s},J_{s}^{c}\\}}]$
are indices, and $c_{1},\dots,c_{s}$ are functions $\prod_{j\in
J}[n_{j}]\to\mathbb{F}$ if $J$ is non-empty and elements of $\mathbb{F}$
otherwise, which satisfy_

$c_{1}+\dots+c_{s}=0,$

_then replacing $a_{J_{t}^{c},i_{t}}$ by_

$a_{J_{t}^{c},i_{t}}+(\otimes_{t’\in[s]\setminus\\{t\\}}a_{J_{t^{\prime}},i_{t^{\prime}}})\otimes
c_{t}$

_for each $t\in[s]$ leads to a new minimal-length partition rank decomposition
of $T$._

Construction 9 shows that whenever $|J|\geq 2$, it is never true (for any
integers $d\geq 3$, $k\geq 2$, and any field $\mathbb{F}$) that there exists a
linear subspace $A_{J}$ of $\otimes_{j\in J}\mathbb{F}^{n_{j}}$ with dimension
bounded above depending on $d,k,\mathbb{F}$ only such that any functions
$a_{J,i}$ from any minimal-length decomposition of $T$ are contained in
$A_{J}$.

Moreover, in the case of the partition rank there may be new constructions in
addition to the analogues above.

## References

  * [1] E. Ballico, A. Bernardi, and P. Santarsiero, Identifiability of rank-$3$ tensors, arXiv:2001.10497 (2020).
  * [2] A. Bik, A. Danelon, J. Draisma, R. H. Eggermont, Universality of high-strength tensors, Vietnam J. Math 50 (2022), 557-580.
  * [3] A. Bik, J. Draisma, R. H. Eggermont, Polynomials and tensors of bounded strength, Commun. Contemp. Math. 21 (7) (2019), 1850062.
  * [4] Jop Briët and Davi Castro-Silva, Random restrictions of high-rank tensors and polynomial maps, arXiv:2212.13728 (2022).
  * [5] Jop Briet, Harry Buhrman, Davi Castro-Silva, and Niels M.P. Neumann, Noisy decoding by shallow circuits with parities: classical and quantum, arXiv:2302.02870 (2023).
  * [6] E. Croot, V. Lev and P. Pach, Progression-free sets in $\mathbb{Z}_{4}^{n}$ are exponentially small, Ann of Math. 185 (2017), 331-337.
  * [7] J. Ellenberg and D. Gijswijt, On large subsets of $\mathbb{F}_{q}^{n}$ with no three-term arithmetic progression Ann of Math. 185 (2017), 339-343.
  * [8] W. T. Gowers, The slice rank of a direct sum, arXiv:2105.08394v2 (2022).
  * [9] W. T. Gowers and T. Karam, Equidistribution of high-rank polynomials with variables restricted to subsets of $\mathbb{F}_{p}$, arXiv:2209.04932 (2022).
  * [10] B. Green and T. Tao, The distribution of polynomials over finite fields, with applications to the Gowers norms. Contr. Discr. Math., 4 (2009), no. 2, 1-36.
  * [11] T. Karam, High-rank subtensors of high-rank tensors, arxiv:2207.08030 (2022).
  * [12] D. Kazhdan and T. Ziegler, Properties of high rank varieties of affine spaces, Geom. Funct. Anal., 30(4) (2020), 1063-1096.
  * [13] B. Kruskal, Three-way arrays: Rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics, Linear Algebra Appl. 18 (1977), 95-138.
  * [14] S. Lovett, The analytic rank of tensors and its applications, Discrete Anal. 7 (2019), 1-10.
  * [15] E. Naslund, The Chromatic Number of $\mathbb{R}^{n}$ with Multiple Forbidden Distances, arxiv:2205.12312 (2022).
  * [16] E. Naslund, The partition rank of a tensor and k-right corners in $\mathbb{F}_{q}^{n}$, Jour. Combin. Th, A 174 (2020), 105190.
  * [17] E. Naslund and W. Sawin, Upper bounds for sunflower-free sets, Forum of Mathematics, Sigma, vol. 5 (2017).
  * [18] L. Sauermann, Finding solutions with distinct variables to systems of linear equations over $\mathbb{F}_{p}$, Math. Ann. 386 (2023), 1-33.
  * [19] W. Sawin and T. Tao, Notes on the “slice rank” of tensors, https://terrytao.wordpress.com/2016/08/24/notes-on-the-slice-rank-of-tensors.
  * [20] T. Tao, A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound, https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound.