School of Computing, National University of Singapore (NUS), Singapore and
https://sites.google.com/view/pduttashomepagepranjal@nus.edu.sghttps://orcid.org/0000-0001-9137-9025Funded
under the project “Foundation of Lattice-based Cryptography”, by NUS-NCS Joint
Laboratory for Cyber Security. Institut de Mathématiques de Toulouse,
Université Paul Sabatier, Toulouse, France and
<EMAIL_ADDRESS>toulouse.frhttps://orcid.org/0000-0001-6402-021X University of Warwick,
Warwick, UK and
https://www.dcs.warwick.ac.uk/~u2270030/christian.ikenmeyer@warwick.ac.ukhttps://orcid.org/0000-0003-4654-177XSupported
by EPSRC grant EP/W014882/1. Max Planck Institute for Software Systems,
Saarbrücken, Germany and https://goravjindal.github.io/gjindal@mpi-
sws.orghttps://orcid.org/0000-0002-9749-5032 Ruhr-Universität Bochum, Bochum,
Germany and https://qi.rub.de/lysikovVladimir.Lysikov@ruhr-uni-
bochum.dehttps://orcid.org/0000-0002-7816-6524Part of the work was done while
V.L. was affiliated with the QMATH Centre, University of Copenhagen. V.L.
acknowledges financial support from VILLUM FONDEN via the QMATH Centre of
Excellence (Grant No. 10059) and the European Union (ERC Grant Agreements
818761 and 101040907). Views and opinions expressed are however those of the
author(s) only and do not necessarily reflect those of the European Union or
the European Research Council Executive Agency. Neither the European Union nor
the granting authority can be held responsible for them. Pranjal Dutta, Fulvio
Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov [500]Theory
of computation Algebraic complexity theory

###### Acknowledgements.

# Fixed-parameter debordering of Waring rank

Pranjal Dutta  Fulvio Gesmundo  Christian Ikenmeyer  Gorav Jindal  Vladimir
Lysikov

###### Abstract

Border complexity measures are defined via limits (or topological closures),
so that any function which can approximated arbitrarily closely by low
complexity functions itself has low border complexity. Debordering is the task
of proving an upper bound on some non-border complexity measure in terms of a
border complexity measure, thus getting rid of limits.

Debordering is at the heart of understanding the difference between Valiant’s
determinant vs permanent conjecture, and Mulmuley and Sohoni’s variation which
uses border determinantal complexity. The debordering of matrix multiplication
tensors by Bini played a pivotal role in the development of efficient matrix
multiplication algorithms. Consequently, debordering finds applications in
both establishing computational complexity lower bounds and facilitating
algorithm design. Currently, very few debordering results are known.

In this work, we study the question of debordering the border Waring rank of
polynomials. Waring and border Waring rank are very well studied measures in
the context of invariant theory, algebraic geometry, and matrix multiplication
algorithms. For the first time, we obtain a Waring rank upper bound that is
exponential in the border Waring rank and only linear in the degree. All
previous known results were exponential in the degree. For polynomials with
constant border Waring rank, our results imply an upper bound on the Waring
rank linear in degree, which previously was only known for polynomials with
border Waring rank at most 5.

###### keywords:

border complexity, Waring rank, debordering, apolarity

###### category:

##  1 Introduction

Given a homogeneous polynomial $f$ of degree $d$ over $\mathbb{C}$, its
_Waring rank_ $\mathsf{WR}(f)$ is defined as the smallest number $r$ such that
there exist homogeneous linear forms $\ell_{1},\dots,\ell_{r}$ with

$f=\sum_{i=1}^{r}\ell_{i}^{d}.$

Equivalently, $\mathsf{WR}(f)$ is the minimal top fanin of a homogeneous
$\Sigma\wedge\Sigma$ circuit computing $f$. In the case of quadratic forms
(polynomials of degree $2$), this notion is equivalent to the rank of the
symmetric matrix associated with a quadratic form; hence Waring rank can be
regarded as a generalization of the rank of a symmetric matrix. Unlike the
case of matrices, when $d\geq 3$, Waring rank is in general not lower
semicontinuous 111A function $f$ is lower semicontinuous at $a$ if
$\underset{x\rightarrow a}{\lim\inf}\leavevmode\nobreak\ f(x)\geq f(a)$., that
is, a limit of a family of polynomials with low Waring rank can have higher
Waring rank. The simplest example is given by the polynomial $x^{d-1}y$, which
has Waring rank $d$ (this is a classical result [50]), but can be presented as
a limit

$x^{d-1}y=\lim_{\epsilon\to 0}\frac{1}{d\epsilon}\left[(x+\epsilon
y)^{d}-x^{d}\right]$

of a family of Waring rank $2$ polynomials (note that we work over
$\mathbb{C}$, so this expression can be rearranged into a sum of two powers by
moving constants inside the parentheses). The _border Waring rank_ is a
semicontinuous variation of Waring rank defined as follows: the border Waring
rank of $f$, denoted $\underline{\mathsf{WR}}(f)$, is the smallest $r$ such
that $f$ can be written as a limit of a sequence of polynomials of Waring rank
at most $r$. We have $\underline{\mathsf{WR}}(x^{d-1}y)=2$.

Waring rank was studied already in the eighteenth century [24, 53, 26] in the
context of invariant theory, with the aim to determine normal forms for
homogeneous polynomials. We mention the famous Sylvester Pentahedral Theorem,
stating that a generic cubic form in four variables can be written uniquely as
a sum of five cubes. At the beginning of the twentieth century, the early work
on secant varieties in classical algebraic geometry [51, 54] implicitly
commenced the study of border Waring rank. The notion of border rank for
tensors was introduced in [12] to construct faster-than-Strassen matrix
multiplication algorithms. In [11], Bini proved that tensor border rank and
tensor rank define the same matrix multiplication exponent. Today this theory
is deeply related to the study of Gorenstein algebras [38, 16], the Hilbert
scheme of points [41], and deformation theory [19, 42].

In the context of algebraic complexity theory, Waring rank defines a model of
computation known as the homogeneous diagonal depth 3 circuits or homogeneous
$\Sigma\wedge\Sigma$ circuits, see e.g. [52]. This is a very weak
computational model (determinants have provably exponential Waring rank [34]).
Nevertheless, it is important as one of the simplest nontrivial computational
models and has many unresolved open problems associated with it. The Waring
rank of a generic homogeneous polynomial of degree $d\geq 3$ in $n$ variables
is $\lceil\frac{1}{n}\cdot\binom{n+d-1}{d}\rceil=\Omega(\frac{n^{d-1}}{d!})$
with finite number of exceptional values of $(n,d)$ [2], but the best lower
bounds obtained are of order $2n^{\lfloor d/2\rfloor}$ (from tensor rank lower
bounds in [3]). For a large class of lower bound methods, so called rank
methods, there are barrier results showing that cannot give bounds
significantly larger than $n^{\lfloor d/2\rfloor}$ [28, 31, 30]. Waring rank
can be useful when the degree of the polynomials considered is constant. For
example, the results of [25] guarantee that the matrix multiplication exponent
is controlled by the Waring rank or border Waring rank of the polynomial
$\operatorname{Tr}(X^{3})$ with $X\in\mathbb{C}^{n\times n}$, which is a
symmetrized version of the matrix multiplication tensor.

The lack of semicontinuity is a common phenomenon in algebraic complexity not
specific to Waring rank. Most complexity measures defined in terms of discrete
structures (such as circuits or formulas) or in terms of decompositions (such
as Waring rank or tensor rank) are not lower semicontinuous. To any algebraic
complexity measure one can define the corresponding _border complexity
measure_ in the same way as border Waring rank arises from Waring rank: the
border complexity of $f$ is the smallest number $s$ such that $f$ can be
approximated arbitrarily closely by polynomials of complexity at most $s$.
Border tensor rank appears in the study of the computational complexity of
matrix multiplication [12, 11], border complexity for algebraic circuits was
first discussed in [48] and [21].

Replacing a complexity measure by its border measure in a complexity class, we
obtain the _closure_ of this class. For example, $\overline{\mathsf{VP}}$ is
the class of all polynomial sequences with polynomially bounded degree and
border circuit size, and $\overline{\mathsf{VF}}$ is defined analogously using
formula size. Formally, the closure $\overline{\mathcal{C}}$ of a complexity
class $\mathcal{C}$ consists of all polynomial sequences
$(f_{n})_{n\in\mathbb{N}}$ such that there exists a bivariate sequence
$(g_{n,m})_{n,m\in\mathbb{N}}$ with the property that
$(g_{n,m})_{n\in\mathbb{N}}$ lies in $\mathcal{C}$ for every fixed $m$, and
$f_{n}=\lim_{m\to\infty}g_{n,m}$. The operation of going to the closure is
indeed a closure operator in the sense of topology, see [39].

The relationship between border and non-border complexity is far from
straightforward. In some contexts taking a limit can be a very strong
operation, which sometimes turns non-universal computational models into
universal ones. For example, there are polynomials which cannot be computed by
width $2$ algebraic branching programs [4], but the corresponding border
measure is related to border formula size [15], so every polynomial is a limit
of width $2$ ABPs. Kumar [45] gives an even easier example: every polynomial
can be presented as a limit of a sum of $2$ products of affine linear forms.
On the other hand, there are examples of complexity measures which are lower
semicontinuous, so that there is no difference between border and non-border
complexity measures. A simplest example is the number of monomials in a
polynomial (equivalently, top fanin of a $\Sigma\Pi$ circuit). Other examples
are noncommutative ABP width (implicit in [49]) and read-once ABP width [27].

Semicontinuous complexity measures and closed complexity classes are easier to
work with using geometric methods. Because of this, the geometric complexity
theory program [48] proposes to study conjectures
$\mathsf{VNP}\not\subseteq\overline{\mathsf{VBP}}$ and
$\mathsf{VNP}\not\subseteq\overline{\mathsf{VP}}$ instead of Valiant’s
conjectures $\mathsf{VNP}\neq\mathsf{VBP}$ and $\mathsf{VNP}\neq\mathsf{VP}$.
The $\mathsf{VNP}\not\subseteq\overline{\mathsf{VP}}$ conjecture was also
proposed in [21]. These border variants of Valiant’s conjecture are now
usually referred to as the Mulmuley–Sohoni conjectures. Mulmuley–Sohoni
conjectures are stronger that Valiant’s conjectures, but it is not clear how
much stronger, as most questions about the relations between complexity
classes and their closures are wide open. It is unknown even whether or not
$\overline{\mathsf{VF}}\subseteq\mathsf{VNP}$. Theorems of the form
$\overline{\mathcal{C}}\subseteq\mathcal{D}$ for algebraic complexity classes
$\mathcal{C}$ and $\mathcal{D}$ are called _debordering_ results. These kind
of results can also be proven directly on the complexity measures, by giving
an upper bound on a non-border complexity in terms of border complexity. For
example, $\textup{{abpw}}(f)\leq\underline{\mathsf{WR}}(f)$, where
$\textup{{abpw}}(f)$ is the algebraic branching program width of $f$. This is
proven using semicontinuity of noncommutative ABP width, see [13, Thm 4.2] and
[29]. In terms of complexity classes, this means
$\overline{\mathsf{VWaring}}\subseteq\mathsf{VBP}$, where $\mathsf{VWaring}$
is the class of $p$-families that have polynomially bounded Waring rank.

Forbes [55] conjectures that $\overline{\mathsf{VWaring}}=\mathsf{VWaring}$.
Since this puts $\overline{\mathsf{VWaring}}$ in $\mathsf{VF}$, a proof of
this conjecture will also improve the results of Dutta, Dwivedi and Saxena
[27] from $\overline{\Sigma^{[r]}\Pi\Sigma}\subset\mathsf{VBP}$ to
$\overline{\Sigma^{[r]}\Pi\Sigma}\subset\mathsf{VF}$. Ballico and Bernardi [7]
propose an even stronger conjecture stating that
$\mathsf{WR}(f)\leq(\underline{\mathsf{WR}}(f)-1)\cdot\deg f$. This was proven
by case analysis for small values of border Waring rank: for
$\underline{\mathsf{WR}}(f)\leq 3$ in [46], for $\underline{\mathsf{WR}}(f)=4$
in [6], and for $\underline{\mathsf{WR}}(f)=5$ and $\deg f\geq 9$ in [5].

### Main result

We prove the following improved debordering theorem for border Waring rank.

######  Theorem 1.1 (Fixed-parameter debordering).

Let $f$ be a homogeneous polynomial with $\deg f=d$ and
$\underline{\mathsf{WR}}(f)=r$. Then $\mathsf{WR}(f)\leq 4^{r}\cdot d.$

Note that the example of the polynomial $x^{d-1}y$ with
$\underline{\mathsf{WR}}(x^{d-1}y)=2$ and $\mathsf{WR}(x^{d-1}y)=d$ shows that
any debordering bound must necessarily depend on both border Waring rank $r$
and the degree $d$. We call our result a _fixed-parameter debordering_ because
the bound is polynomial (in this case even linear) in $d$, but exponential in
the complexity parameter $r$. In the case of a fixed border Waring rank this
gives a bound linear in the degree. This was previously known only for
$\underline{\mathsf{WR}}(f)\leq 5$. Even for $r=O(\log d)$ we obtain an upper
bound polynomial in $d$.

To the best of our knowledge, this is the first fixed-parameter debordering
result. Previous methods applied to border Waring rank only allow upper bounds
of the order $d^{r}$ or $r^{d}$. To get $\mathsf{WR}(f)\leq O(d^{r})$, note
that a polynomial with border Waring rank $r$ can be transformed into a
polynomial in only $r$ variables using a linear change of variables (see Lemma
2.3), and then take the maximal possible Waring rank of an $r$-variate
polynomial of degree $d$ as an upper bound. Alternatively, an upper bound
$\mathsf{WR}(f)\leq 2^{d-1}r^{d}$ can be obtained by using the previously
mentioned debordering into an ABP
($\textup{{abpw}}(f)\leq\underline{\mathsf{WR}}(f)$) and writing the ABP as a
sum of at most $r^{d}$ products, one for each path. Other known debordering
techniques, such as the interpolation technique using the bound on the degree
of $\epsilon$ in the approximation from the work of Lehmkuhl and Lickteig [47]
(which is exponential in the degree of the polynomial), or the DiDIL technique
from [27] can be applied in the border Waring rank setting, but do not improve
over the simpler results discussed above.

### Proof ideas

The main ideas for the proof come from _apolarity theory_ and the study of
$0$-dimensional schemes in projective space (see Appendix A), but we managed
to simplify the proof so that it is elementary and does not use the language
of algebraic geometry and is based on partial derivative techniques (see
Section 2.3).

To prove the debordering, we transform a border Waring rank decomposition for
$f$ into a _generalized additive decomposition_ [37, 8, 10] of the form
$f=\sum_{k=1}^{m}\ell_{k}^{d-r_{k}+1}g_{k},$ where $\ell_{k}$ are linear
forms, and $g_{k}$ are homogeneous polynomials of degrees $r_{k}-1$. We then
obtain an upper bound on the Waring rank, by first decomposing each $g_{k}$
with respect to a basis consisting of powers of linear forms, and then using
the classical fact (see also [20]) that
$\mathsf{WR}(\ell_{1}^{a}\ell_{2}^{b})\leq\max(a+1,b+1)$.

To construct a generalized additive decomposition, we divide the summands of a
border rank decomposition into several parts such that cancellations happen
_only_ between summands belonging to the same part; see Lemma 2.13. The key
insight is that if the degree of polynomials involved is high enough, namely
when $\deg f\geq\underline{\mathsf{WR}}(f)-1$, then all parts of the
decomposition are “local” in the sense that the lowest order term in each
summand is a multiple of the same linear form. Each local part gives one term
of the form $\ell^{d-r+1}g$, where $r$ is the number of rank one summands in
the part and $\ell$ is the common lowest order linear form; see Lemma 2.8.

For example, consider the family of polynomials
$f_{d}=x_{0}^{d-1}y_{0}+x_{1}^{d-1}y_{1}+2(x_{0}+x_{1})^{d-1}y_{2}$, adapted
from [17]. If $d>3$, then the border Waring rank of $f$ is at most $6$, as
evidenced by the decomposition

$f_{d}=\lim_{\epsilon\to 0}\frac{1}{d\epsilon}\left[(x_{0}+\epsilon
y_{0})^{d}-x_{0}^{d}+(x_{1}+\epsilon
y_{1})^{d}-x_{1}^{d}+2(x_{0}+x_{1}+\epsilon
y_{2})^{d}-2(x_{0}+x_{1})^{d}\right],$ (1)

and a matching lower bound is obtained by considering the dimension of the
space of second order partial derivatives. The summands of the decomposition
(1) can be divided into three pairs. The lowest order term of the first pair
is $x_{0}^{d}$, the one of the second pair is $x_{1}^{d}$ and the one of the
third pair is $(x_{0}+x_{1})^{d}$. For each pair, the sum of the two powers
individually converges to a limit as $\epsilon\to 0$; these three limits are,
respectively, $x_{0}^{d-1}y_{0}$, $x_{1}^{d-1}y_{1}$, and
$2(x_{0}+x_{1})^{d-1}y_{2}$, which are the summands of a generalized additive
decomposition for $f_{d}$.

When $d=3$, the polynomial $f_{d}$ is an example of a “wild form” [17]. It has
border Waring rank $5$ given for example by the decomposition

$f_{3}=\lim_{\epsilon\to 0}\frac{1}{9\epsilon}\left[3(x_{0}+\epsilon
y_{0})^{3}+3(x_{1}+\epsilon y_{1})^{3}+\right.\\\ \left.6(x_{0}+x_{1}+\epsilon
y_{2})^{3}-(x_{0}+2x_{1})^{3}-(2x_{0}+x_{3})^{3}\right].$ (2)

Unlike the previous decomposition, this one cannot be divided into parts that
have limits individually, and is not local — all summands have different
lowest order terms. This is only possible if the degree is low.

The condition on the degree is related to algebro-geometric questions about
regularity of $0$-dimensional schemes [38, Thm. 1.69], but for the schemes
arising from border rank decompositions, this is ultimately a consequence of
the fact that $r$ distinct linear forms have linearly independent $d$-th
powers when $d\geq r-1$.

##  2 Debordering border Waring rank

The goal of this section is to prove Theorem 1.1. Given a homogeneous degree
$d$ polynomial $f$, we provide upper bounds for $\mathsf{WR}(f)$ in terms of
$\underline{\mathsf{WR}}(f)$ and $d$.

###  2.1 Definitions

In this section we introduce some notation and give a formal definition of
Waring rank and border Waring rank. We work over the field $\mathbb{C}$ of
complex numbers. The space of homogeneous polynomials of degree $d$ in
variables $\boldsymbol{x}=(x_{1},\dots,x_{n})$ is denoted by
$\mathbb{C}[\boldsymbol{x}]_{d}$. We write $f\simeq g$ for
$f,g\in\mathbb{C}(\epsilon)[\boldsymbol{x}]$ if $\lim_{\epsilon\to
0}f=\lim_{\epsilon\to 0}g$ (in particular, both limits must exist). Recall
that the projective space $\mathbb{P}V$ is defined as the set of lines through
the origin in $V$, that is, for each nonzero $v\in V$ we have a corresponding
line $[v]\in\mathbb{P}V$, and $[v]=[w]$ if and only if $v=\alpha w$ for some
$\alpha$.

######  Definition 2.1.

A _Waring rank decomposition_ of a homogeneous polynomial
$f\in\mathbb{C}[\boldsymbol{x}]_{d}$ is a decomposition of the form

$f=\sum_{k=1}^{r}\ell_{k}^{d}$

for some linear forms
$\ell_{1},\dots,\ell_{r}\in\mathbb{C}[\boldsymbol{x}]_{1}$. The minimal number
of summands in a Waring rank decomposition is called the _Waring rank_ of $f$
and is denoted by $\mathsf{WR}(f)$.

It is known that every homogeneous polynomial over $\mathbb{C}$ has finite
Waring rank [50].

######  Definition 2.2.

A _border Waring rank decomposition_ of a homogeneous polynomial
$f\in\mathbb{C}[\boldsymbol{x}]_{d}$ is an expression of the form

$f=\lim_{\epsilon\to 0}\sum_{k=1}^{r}\ell_{k}^{d}$

where $\ell_{1},\dots,\ell_{r}\in\mathbb{C}(\epsilon)[\boldsymbol{x}]_{1}$,
that is, $\ell_{i}$ are linear forms in $\boldsymbol{x}$ with coefficients
rationally dependent on $\epsilon$. The _border Waring rank_
$\underline{\mathsf{WR}}(f)$ is the minimal number of summands in a border
Waring rank decomposition.

Equivalently, the border Waring rank of $f\in\mathbb{C}[\boldsymbol{x}]_{d}$
can be defined as the minimal number $r$ such that $f$ lies in the closure of
the set $W_{d,r}=\\{g\in\mathbb{C}[\boldsymbol{x}]_{d}\mid\mathsf{WR}(g)\leq
r\\}$ of all polynomials with Waring rank at most $r$. The set $W_{d,r}$ is
constructible, so its Zariski and Euclidean closures coincide, see e.g. [44,
Anh.I.7.2 Folgerung]. The equivalence to the definition given above was
established by Alder [1] (cited by [22, Ch.20]) for a similar notion of tensor
rank, the proof remains essentially the same for Waring rank of polynomials.

###  2.2 Orbit closure and essential variables

The number of essential variables of a homogeneous polynomial $f$ is the
minimum integer $m$ such that there is a linear change of coordinates after
which $f$ can be written as a polynomial in $m$ variables. Denote the number
of essential variables of $f$ by $\mathrm{N}_{\mathrm{ess}}(f)$. It is a
classical fact, which already appears in [53], that the number of essential
variables of $f$ equals the dimension of the linear span of its first order
partial derivatives, or equivalently the rank of the first partial derivative
map. In particular $\mathrm{N}_{\mathrm{ess}}(-)$ is a lower semicontinuous
function. We refer to [23] and [43, Lemma B.1] for modern proofs of this
result.

An immediate consequence of the semicontinuity of the number of essential
variables is the following result.

######  Lemma 2.3.

For a homogeneous polynomial $f\in\mathbb{C}[\boldsymbol{x}]_{d}$ we have
$\mathrm{N}_{\mathrm{ess}}(f)\leq\underline{\mathsf{WR}}(f)$.

######  Proof 2.4.

We first prove $\mathrm{N}_{\mathrm{ess}}(f)\leq\mathsf{WR}(f)$. Let $p$ be
the dimension of the linear space spanned by the linear forms $\ell_{k}$ in
the decomposition $f=\sum_{k=1}^{r}\ell_{k}^{d}$. Without loss of generality
the linear forms $\ell_{1},\dots,\ell_{p}$ are linearly independent, and
$\ell_{p+1},\dots,\ell_{r}$ are linear combinations of
$\ell_{1},\dots,\ell_{p}$. After applying a change of variables such that
$y_{k}=\ell_{k}(\boldsymbol{x})$ for $k=1,\dots,p$ we see that
$\mathrm{N}_{\mathrm{ess}}(f)\leq p\leq r$.

The inequality $\mathrm{N}_{\mathrm{ess}}(f)\leq\underline{\mathsf{WR}}(f)$
now follows from the semicontinuity of $\mathrm{N}_{\mathrm{ess}}$: if

$f=\lim_{\epsilon\to 0}\sum_{k=1}^{r}\ell_{k}^{d}\;,$

with $\ell_{k}\in\mathbb{C}(\epsilon)[\boldsymbol{x}]$, then
$\mathrm{N}_{\mathrm{ess}}(f)\leq\lim_{\epsilon\to
0}\mathrm{N}_{\mathrm{ess}}(\sum_{k=1}^{r}\ell_{k}^{d}(\epsilon))\leq r$.

###  2.3 Fixed-parameter debordering

The proof of Theorem 1.1 is based on generalized additive decompositions of
polynomials, in the sense of [37]. These decompositions were studied in
algebraic geometry, usually in connection to $0$-dimensional schemes and the
notion of cactus rank. We defer the discussion of connections to algebraic
geometry to the next section. Here we provide elementary proofs of some
statements on generalized additive decompositions based on partial derivatives
techniques, without using the language of $0$-dimensional schemes. We bring
from geometry a key insight: a border rank decomposition can be separated into
_local_ parts if the degree of the polynomial is large enough.

To define formally what it means for a border rank decomposition to be local,
note that a rational family of linear forms
$\ell\in\mathbb{C}(\epsilon)[\boldsymbol{x}]_{1}$ always has a limit when
viewed projectively. Specifically, expanding $\ell(\epsilon)$ as a Laurent
series $\ell(\epsilon)=\sum_{i=q}^{\infty}\epsilon^{i}\ell_{i}$ with
$\ell_{q}\neq 0$, we have $\lim_{\epsilon\to
0}[\ell(\epsilon)]=\lim_{\epsilon\to
0}[\sum_{i=0}^{\infty}\epsilon^{i}\ell_{q+i}]=[\ell_{q}]$. A border Waring
rank decomposition is called local if for all summands in the decomposition
this limit is the same. More precisely, we give the following definition.

######  Definition 2.5.

Let $f\in\mathbb{C}[\boldsymbol{x}]_{d}$ be a homogeneous polynomial. A border
Waring rank decomposition

$f=\lim_{\epsilon\to 0}\sum_{k=1}^{r}\ell_{k}^{d}\;,$

with $\ell_{k}\in\mathbb{C}(\epsilon)[\boldsymbol{x}]_{1}$ is called a _local
border decomposition_ if there exists a linear form
$\ell\in\mathbb{C}[\boldsymbol{x}]_{1}$ such that $\lim_{\epsilon\to
0}[\ell_{k}(\epsilon)]=[\ell]$ for all $k\in\\{1,\dots,r\\}$. We call the
point $[\ell]\in\mathbb{P}\mathbb{C}[\boldsymbol{x}]_{1}$ the _base_ of the
decomposition. A local decomposition is called _standard_ if
$\ell_{1}=\epsilon^{q}\gamma\ell$ for some $q\in\mathbb{Z}$ and
$\gamma\in\mathbb{C}$.

######  Lemma 2.6.

If $f$ has a local border decomposition, then it has a standard local border
decomposition with the same base and the same number of summands.

######  Proof 2.7.

After applying a linear change of variables, we may assume that the base of
the local decomposition for $f$ is $[x_{1}]$. This means

$f=\lim_{\epsilon\to 0}\sum_{k=1}^{r}\ell_{k}^{d}$

with
$\ell_{k}=\epsilon^{q_{k}}\cdot\gamma_{k}x_{1}+\sum_{j=q_{k}+1}^{\infty}\epsilon^{j}\ell_{k,j}$.

Write $\ell_{1}=\epsilon^{q_{1}}\left(\sum_{i=1}^{n}\alpha_{i}x_{i}\right)$
where $\alpha_{i}\in\mathbb{C}(\epsilon)$. Let
$\widehat{x}_{1}=\frac{\gamma_{1}}{\alpha_{1}}x_{1}-\sum_{i=2}^{n}\frac{\alpha_{n}}{\alpha_{1}}x_{i}$.
Note that $\alpha_{1}\simeq\gamma_{1}$ and $\alpha_{i}\simeq 0$ for $i>1$,
hence $\widehat{x}_{1}\simeq x_{1}$ and

$f\simeq
f(\widehat{x}_{1},\dots,x_{n})\simeq\ell_{1}(\widehat{x}_{1},x_{2},\dots,x_{n})^{d}+\sum_{k=2}^{r}\ell_{k}(\widehat{x}_{1},x_{2},\dots,x_{n})^{d}=(\epsilon^{q_{1}}\gamma_{1}x_{1})^{d}+\sum_{k=2}^{r}\widehat{\ell}_{k}^{d}.$

where
$\widehat{\ell}_{k}(x_{1},\dots,x_{n})=\ell_{k}(\widehat{x}_{1},x_{2},\dots,x_{n})$.
This defines a new border rank decomposition of $f$. Moreover, notice that
$\lim_{\epsilon\to 0}[\widehat{\ell}_{k}]=[x_{1}]$ for every $k$, so the new
decomposition is again local with base $[x_{1}]$. Since the first summand is
$\epsilon^{q_{1}}\gamma_{1}x_{1}$, this is the desired standard local border
decomposition.

######  Lemma 2.8.

Suppose $f\in\mathbb{C}[\boldsymbol{x}]_{d}$ has a local border decomposition
with $r$ summands based at $[\ell]$. If $d\geq r-1$, then $f=\ell^{d-r+1}g$
for some homogeneous polynomial $g$ of degree $r-1$.

######  Proof 2.9.

After applying a linear change of variables we may assume $\ell=x_{1}$. We
prove the statement by induction on $r$ and the difference $d-(r-1)$.

The cases $r=1$ and $d=r-1$ are trivial.

If $d>r-1$, then by the previous Lemma there exists a standard local border
decomposition

$f=\lim_{\epsilon\to 0}\sum_{k=1}^{r}\ell_{k}(\epsilon)^{d}.$

Write $\ell_{k}=\sum_{i=1}^{n}\alpha_{ki}x_{i}$ for some
$\alpha_{ki}\in\mathbb{C}(\epsilon)$. Since the decomposition is standard,
$\alpha_{1i}=0$ for $i>1$. For the derivatives of $f$ we have the following
border decompositions

$\frac{\partial f}{\partial x_{1}}=\lim_{\epsilon\to
0}\sum_{k=1}^{r}d\cdot\alpha_{k1}(\epsilon)\ell_{k}(\epsilon)^{d-1},$

and

$\frac{\partial f}{\partial x_{i}}=\lim_{\epsilon\to
0}\sum_{k=2}^{r}d\cdot\alpha_{ki}(\epsilon)\ell_{k}(\epsilon)^{d-1}.$

for $i\neq 1$. These decompositions involve the same linear forms $\ell_{k}$
with multiplicative coefficients, so they are local with the same base
$[x_{1}]$. By inductive hypothesis $\frac{\partial f}{\partial
x_{1}}=x_{1}^{d-r}g_{1}$ and $\frac{\partial f}{\partial
x_{i}}=x_{1}^{d-r+1}g_{i}$ for some homogeneous polynomials
$g_{1},\dots,g_{n}$ of appropriate degrees. To get an analogous expression for
$f$, combine these expressions using Euler’s formula for homogeneous
polynomials as follows

$f=\frac{1}{d}\sum_{i=1}^{n}x_{i}\frac{\partial f}{\partial
x_{i}}=\frac{1}{d}\left(x_{1}\cdot
x_{1}^{d-r}g_{1}+\sum_{i=2}^{n}x_{i}x_{1}^{d-r+1}g_{i}\right)=\frac{1}{d}x_{1}^{d-r+1}\left(g_{1}+\sum_{i=2}^{n}x_{i}g_{i}\right)\;.$

We will now extend this result to non-local border Waring rank decompositions.
As long as the degree of the approximated polynomial is high enough, every
border rank decomposition can be divided into local parts and transformed into
a sum of terms of the form $\ell^{d-r+1}g$.

######  Definition 2.10.

A _generalized additive decomposition_ of $f$ is a decomposition of the form

$f=\sum_{k=1}^{m}\ell_{k}^{d-r_{k}+1}g_{k}\;,$

where $\ell_{k}$ are linear forms such that $\ell_{i}$ is not proportional to
$\ell_{j}$ when $i\neq j$, and $g_{k}$ are homogeneous polynomials of degrees
$\deg g_{k}=r_{k}-1$.

To show that there are no cancellations between different local parts, we need
the following lemma, which in the case of $2$ variables goes back to Jordan
[38, Lem. 1.35]. This lemma can be seen as a generalization of a well-known
fact that $m$ pairwise non-proportional linear forms $\ell_{1},\dots,\ell_{m}$
have linearly independent powers $\ell_{1}^{d},\dots,\ell_{m}^{d}$ for $d\geq
m-1$.

######  Lemma 2.11.

Let $\ell_{1},\dots,\ell_{m}\in\mathbb{C}[\boldsymbol{x}]_{1}$ be linear forms
such that $\ell_{i}$ is not proportional to $\ell_{j}$ when $i\neq j$. Let
$g_{1},\dots,g_{m}$ be homogeneous polynomials of degrees
$r_{1}-1,\dots,r_{m}-1$ respectively. If

$\sum_{k=1}^{m}\ell_{k}^{d-r_{k}+1}g_{k}\;=\;0\;,$

and $d\geq\sum_{k=1}^{m}r_{i}-1$, then all $g_{k}$ are zero.

######  Proof 2.12.

We first prove the statement for polynomials in $2$ variables $y_{1},y_{2}$ by
induction on the number of summands $m$; this part of the proof closely
follows [32, Appx.III].

The case $m=1$ with one summand is clear. Consider the case $m>2$. We can
assume $\ell_{1}=y_{1}$ by applying a linear change of variables if required.
Note two simple facts about partial derivatives. First, for a homogeneous
polynomial $f\in\mathbb{C}[y_{1},y_{2}]_{d}$ we have $\partial_{2}^{r}f=0$ if
and only if $f=y_{1}^{d-r+1}g$ (here $\partial_{2}:=\frac{\partial}{\partial
y_{2}}$). Second, differentiating $r$ times a homogeneous polynomial of the
form $\ell^{d-s+1}g$, we obtain a polynomial of the form $\ell^{d-r-s+1}h$.

Suppose

$y_{1}^{d-r_{1}+1}g_{1}+\sum_{k=2}^{m}\ell_{k}^{d-r_{k}+1}g_{k}=0.$

Differentiating $r_{1}$ times with respect to $y_{2}$, we obtain

$\sum_{k=2}^{m}\ell_{k}^{d-r_{1}-r_{k}+1}h_{k}=0,$

where
$\ell_{k}^{d-r_{1}-r_{k}+1}h_{k}=\partial_{2}^{r_{1}}(\ell_{k}^{d-r_{k}+1}g_{k})$.
The degree condition $d-r_{1}\geq\sum_{k=2}^{m}r_{k}-1$ holds for this new
expression. Therefore, by induction hypothesis we have $h_{k}=0$ and thus
$\partial_{2}^{r_{1}}(\ell_{k}^{d-r_{k}+1}g_{k})=0$. It follows that
$\ell_{k}^{d-r_{k}+1}g_{k}=y_{1}^{d-r_{1}+1}\widehat{g}_{k}$ for some
homogeneous polynomial $\widehat{g}_{k}$. This implies that
$y_{1}^{d-r_{1}+1}$ divides $g_{k}$, which is impossible since
$d-r_{1}+1\geq\sum_{k=2}^{m}r_{k}\geq r_{k}>\deg g_{k}$.

Consider now the general case where the number of variables $n\geq 2$ (the
case $n=1$ is trivial). Suppose $\sum_{k=1}^{m}\ell_{k}^{d-r_{k}+1}g_{k}=0$.
The set of linear maps $A\colon(y_{1},y_{2})\mapsto(x_{1},\dots,x_{n})$ such
that $\ell_{i}\circ A$ and $\ell_{j}\circ A$ are not proportional to each
other is a nonempty Zariski open set given by the condition
$\mathrm{rank}(\ell_{i}\circ A,\ell_{j}\circ A)>1$. Hence for a nonempty
Zariski open (and therefore dense) set of linear maps $A$ the linear forms
$\ell_{k}\circ A$ are pairwise non-proportional. From the binary case above we
have $g_{k}\circ A=0$ if $A$ lies in this open set. By continuity this implies
$g_{k}\circ A=0$ for all $A$. Since every point lies in the image of some
linear map $A$ we have $g_{k}=0$.

######  Lemma 2.13.

Let $f\in\mathbb{C}[\boldsymbol{x}]_{d}$ be such that
$\underline{\mathsf{WR}}(f)=r$. If $d\geq r-1$, then there exists a partition
$r=r_{1}+\dots+r_{m}$ such that $f$ has a generalized additive decomposition

$f=\sum_{k=1}^{m}\ell_{k}^{d-r_{k}+1}g_{k},$

and moreover $\underline{\mathsf{WR}}(\ell_{k}^{d-r_{k}+1}g_{k})\leq r_{k}$.

######  Proof 2.14.

Consider a border Waring rank decomposition

$f=\lim_{\epsilon\to 0}\sum_{k=1}^{r}\ell_{k}^{d}$

Divide the summands between several local decompositions as follows. Define an
equivalence relation $\sim$ on the set of indices $\\{1,2,\dots,r\\}$ as
$i\sim j\Leftrightarrow\lim_{\epsilon\to 0}[\ell_{i}]=\lim_{\epsilon\to
0}[\ell_{j}]$ and let $I_{1},\dots,I_{m}$ be the equivalence classes with
respect to this relation. Further, let $r_{k}=|I_{k}|$ and let
$[L_{k}]=\lim_{\epsilon\to 0}[\ell_{i}]$ for $i\in I_{k}$.

Consider the sum of all summands with indices in $I_{k}$. Let $q_{k}$ be the
power of $\epsilon$ in the lowest order term, that is,

$\sum_{i\in
I_{k}}\ell_{i}^{d}\;=\;\epsilon^{q_{k}}f_{k}+\sum_{j=q_{k}+1}^{\infty}\epsilon^{j}f_{k,j}\;,$

with $f_{k}\in\mathbb{C}[\mathbf{x}]_{d}$ nonzero. This expression can be
transformed into a local border decomposition

$f_{k}=\lim_{\epsilon\to 0}\sum_{i\in
I_{k}}\left(\frac{\ell_{i}(\epsilon^{d})}{\epsilon^{q_{k}}}\right)^{d}.$

based at $[L_{k}]$. By Lemma 2.8 we have $f_{k}=L_{k}^{d-r_{k}+1}g_{k}$ for
some homogeneous polynomial $g_{k}$ of degree $r_{k}-1$. The decomposition
also gives $\underline{\mathsf{WR}}(f_{k})\leq r_{k}$.

Note that $q_{k}\leq 0$ since otherwise the summands $\ell_{i}$ with $i\in
I_{k}$ can be removed from the original border rank decomposition of $f$
without changing the limit. Let $q=\min\\{q_{1},\dots,q_{m}\\}$. Note that if
$q<0$, then, comparing the terms before $\epsilon^{q}$ in the left and right
hand sides of the equality

$f+O(\epsilon)=\sum_{k=1}^{m}\sum_{i\in I_{k}}\ell_{i}^{d}$

we get

$0=\sum_{k\colon q_{k}=q}f_{k}=\sum_{k\colon q_{k}=q}L_{k}^{d-r_{k}+1}g_{k}.$

From Lemma 2.11 we obtain $g_{k}=0$ and $f_{k}=0$, in contradiction with the
definition of $f_{k}$.

We conclude that $q=0$ and

$f=\sum_{k=1}^{m}f_{k}=\sum_{k=1}^{m}L_{k}^{d-r_{k}+1}g_{k},$

obtaining the required generalized additive decomposition.

We will now take a brief detour to define a function $M(r)$ which we use to
upper bound the Waring rank of generalized additive decomposition.

######  Definition 2.15.

Let $\mathsf{maxR}(n,d)$ denote the _maximum Waring rank_ of a degree $d$
homogeneous polynomial in $n$ variables, that is
$\mathsf{maxR}(n,d)=\max\\{\mathsf{WR}(f)\mid
f\in\mathbb{C}[x_{1},\dots,x_{n}]_{d}\\}$. Define the _partition-maxrank
function_ as

$M(r)=\max_{r_{1}+\dots+r_{m}=r}\sum_{k=1}^{m}\mathsf{maxR}(r_{k},r_{k}-1).$

Since every homogeneous polynomial has finite Waring rank, the space
$\mathbb{C}[x_{1},\dots,x_{n}]_{d}$ is spanned by powers of linear forms. This
implies a trivial upper bound on the maximum Waring rank:
$\mathsf{maxR}(n,d)\leq\dim\mathbb{C}[x_{1},\dots,x_{n}]_{d}=\binom{n+d-1}{d}$.
Improved upper bounds were proven in [14, 40].

######  Proposition 2.16.

$\mathsf{maxR}(n,d_{1})\leq\mathsf{maxR}(n,d_{2})$ when $d_{1}\leq d_{2}$.

######  Proof 2.17.

Every form $f$ of degree $d_{1}$ can be represented as a partial derivative of
some form $g$ of degree $d_{2}$. By differentiating a Waring rank
decomposition of $g$ we obtain a Waring rank decomposition of $f$, thus
$\mathsf{WR}(f)\leq\mathsf{WR}(g)\leq\mathsf{maxR}(n,d_{2})$. Since $f$ is
arbitrary, $\mathsf{maxR}(n,d_{1})\leq\mathsf{maxR}(n,d_{2})$.

We are now ready to prove a debordering theorem for Waring rank.

######  Theorem 2.18.

Let $f\in\mathbb{C}[\boldsymbol{x}]_{d}$ be such that
$\underline{\mathsf{WR}}(f)=r$. Then

$\mathsf{WR}(f)\leq M(r)\cdot d.$

######  Proof 2.19.

We consider two cases depending on relation of degree $d$ and border Waring
rank $r$.

_Case_ $d<r-1$. Since $\underline{\mathsf{WR}}(f)=r$, the number of essential
variables of $f$ is at most $r$. Taking the maximum Waring rank as an upper
bound, we obtain

$\mathsf{WR}(f)\leq\mathsf{maxR}(r,d)<\mathsf{maxR}(r,r-1)\leq M(r)\leq
M(r)\cdot d.$

_Case_ $d\geq r-1$. By Lemma 2.13 $f$ has a generalized additive decomposition

$f=\sum_{k=1}^{m}\ell_{k}^{d-r_{k}+1}g_{k}$

with $r_{1}+\dots+r_{m}=r$, $\deg g_{k}=r_{k}-1$ and
$\underline{\mathsf{WR}}(\ell_{k}^{d-r_{k}+1}g_{k})\leq r_{k}$. Since
$\underline{\mathsf{WR}}(\ell_{k}^{d-r_{k}+1}g_{k})\leq r_{k}$, the number of
essential variables $\mathrm{N}_{\mathrm{ess}}(g_{k})\leq r_{k}$. If
$r_{k}=1$, then

$\mathsf{WR}(\ell_{k}^{d-r_{k}+1}g_{k})=\mathsf{WR}(\ell_{k}^{d})=1\leq d.$

If $r_{k}\geq 2$, then we upper bound $\mathsf{WR}(g_{k})$ by
$\mathsf{maxR}(\mathrm{N}_{\mathrm{ess}}(g_{k}),\deg
g_{k})=\mathsf{maxR}(r_{k},r_{k}-1)$. Taking a Waring rank decomposition
$g_{k}=\sum_{i=1}^{\mathsf{WR}(g_{k})}L_{i}^{r_{k}-1}$ and multiplying it by
$\ell_{k}^{d-r_{k}+1}$, we obtain a decomposition

$\ell_{k}^{d-r_{k}+1}g_{k}=\sum_{i=1}^{\mathsf{WR}(g_{k})}\ell_{k}^{d-r_{k}+1}\cdot
L_{i}^{r_{k}-1}.$

It is known that $\mathsf{WR}(y_{1}^{a}y_{2}^{b})=\max\\{a,b\\}+1$ (this is a
classical fact known at least to Oldenburger [50], see also [20])222it is easy
to see that for $a\geq b$ the monomial $y_{1}^{a}y_{2}^{b}$ is proportional to
$\sum_{k=0}^{a}\zeta^{k}(\zeta^{k}y_{1}+y_{2})^{a+b}$ where $\zeta$ is a
primitive root of unity of order $a+1$.. It follows that

$\mathsf{WR}(\ell_{k}^{d-r_{k}+1}L_{i}^{r_{k}-1})\leq\mathsf{WR}(y_{1}^{d-r_{k}+1}y_{2}^{r_{k}-1})=\max\\{d-r_{k}+2,r_{k}\\}\leq
d.$

Hence we have $\mathsf{WR}(\ell_{k}^{d-r_{k}+1}g_{k})\leq
d\cdot\mathsf{WR}(g_{k})\leq d\cdot\mathsf{maxR}(r_{k}-1,r_{k})$.

Combining all parts of the decomposition together, we get

$\mathsf{WR}(f)\leq d\sum_{k=1}^{m}\mathsf{maxR}(r-k-1,r_{k})\leq M(r)\cdot
d.$

A more explicit upper bound is provided by the following immediate corollary.

######  Theorem 2.20.

Let $f\in\mathbb{C}[x_{1},\dots,x_{n}]_{d}$ and let
$\underline{\mathsf{WR}}(f)=r$. Then

$\mathsf{WR}(f)\leq\binom{2r-2}{r-1}\cdot d.$

######  Proof 2.21.

The space of homogeneous polynomials of degree $r-1$ in $r$ variables has
dimension $\binom{2r-2}{r-1}$ and is spanned by powers of linear forms.
Therefore, $\mathsf{maxR}(r-1,r)\leq\binom{2r-2}{r-1}$. Note that if $r=p+q$
with $p,q\neq 0$, then the space $\mathbb{C}[x_{1},\dots,x_{r}]_{r-1}$
contains a direct sum of $x_{1}^{q}\cdot\mathbb{C}[x_{1},\dots,x_{p}]_{p-1}$
and $x_{1}^{p+1}\cdot\mathbb{C}[x_{p+1},\dots,x_{r}]_{q-1}$. Taking the
dimensions of these spaces, we obtain
$\binom{2r-2}{r-1}\geq\binom{2p-2}{p-1}+\binom{2q-2}{q-1}$. It follows that
$M(r)\leq\binom{2r-2}{r-1}$.

Using the Blekherman–Teitler bound on the maximum rank [14], we can get a
slightly better bound. The proof is essentially the same as for the previous
theorem.

######  Corollary 2.22.

Let $f\in\mathbb{C}[x_{1},\dots,x_{n}]_{d}$ and let
$\underline{\mathsf{WR}}(f)=r$. Then

$\mathsf{WR}(f)\leq 2\left\lceil\frac{1}{r}\binom{2r-2}{r-1}\right\rceil\cdot
d.$

###  2.4 Scheme-theoretic proof

In this section we give a proof of Lemma 2.13 based on the theory of
$0$-dimensional schemes and apolarity. This short section assumes familiarity
with these topics, we review them in more details in Appendix A.

See 2.13

######  Proof 2.23 (Alternative proof).

Denote by $V$ the space of linear forms $\mathbb{C}[\boldsymbol{x}]_{1}$.

Since $d\geq r-1$, the border Waring rank of $f$ is equal to its _smoothable
rank_ $\mathsf{SR}(f)$ [17], that is, there exists a $0$-dimensional scheme
$Z\subset\mathbb{P}V$ of degree $r$ which is smoothable (obtained as a flat
limit of the family of $r$-point subsets of $\mathbb{P}V$) and $f$ is apolar
to $Z$. Let $I$ be the ideal of $Z$ and let $I=I^{(1)}\cap\dots\cap I^{(m)}$
be the primary decomposition of this ideal. The primary ideals $I^{(j)}$
correspond to irreducible components $Z_{j}$ of the scheme $Z$.

Since $f$ is apolar to $I$, we have $f\in
I_{d}^{\perp}=(I^{(1)}_{d})^{\perp}+\dots+(I^{(m)}_{d})^{\perp}$. In
particular, there exist $f_{j}\in(I^{(j)}_{d})^{\perp}$ such that
$f=f_{1}+\cdots+f_{m}$. Let $r_{j}$ be the degree of $Z_{j}$. By the
definition of degree, $r=r_{1}+\cdots+r_{m}$. If $Z_{j}$ is supported at the
point $[\ell_{j}]\in\mathbb{P}V$, then for the ideal $I^{(j)}$ we have
$(\ell_{j}^{\perp})^{r_{j}}\subset I^{(j)}\subset\ell_{j}^{\perp}$ and
$(I^{(j)}_{d})^{\perp}\subset\ell_{j}^{d-r_{j}+1}\cdot\mathbb{C}[\boldsymbol{x}]_{r_{j}-1}$.
Therefore the polynomials $f_{j}$ have the form $\ell_{j}^{d-r_{j}+1}g_{j}$
for some $g_{j}$ of degree $\deg g_{j}=r_{j}-1$.

Additionally, all irreducible components of a smoothable scheme $Z$ are
smoothable [18, Thm. 1.1], and since $f_{j}$ is apolar to $Z_{j}$, we have
$\underline{\mathsf{WR}}(f_{j})\leq\mathsf{SR}(f_{j})\leq r_{j}$.

## References

  * [1] Alexander Alder.  Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht.  PhD thesis, Universität Zürich, 1984.
  * [2] J. Alexander and A. Hirschowitz.  Polynomial interpolation in several variables.  J. Alg. Geom., 4(2):201–222, 1995.
  * [3] Boris Alexeev, Michael A. Forbes, and Jacob Tsimerman.  Tensor rank: Some lower and upper bounds.  In CCC 2011, pages 283–291. IEEE Computer Society, 2011.  doi:10.1109/CCC.2011.28.
  * [4] Eric Allender and Fengming Wang.  On the power of algebraic branching programs of width two.  Comput. Complex., 25(1):217–253, 2016.  doi:10.1007/s00037-015-0114-7.
  * [5] Edoardo Ballico.  On the ranks of homogeneous polynomials of degree at least 9 and border rank 5.  Note di Matematica, 38(2):55–92, 2019.  doi:10.1285/i15900932v38n2p55.
  * [6] Edoardo Ballico and Alessandra Bernardi.  Stratification of the fourth secant variety of Veronese varieties via the symmetric rank.  Adv. Pure Appl. Math., 4(2):215–250, 2013.  doi:10.1515/apam-2013-0015.
  * [7] Edoardo Ballico and Alessandra Bernardi.  Curvilinear schemes and maximum rank of forms.  Le Matematiche, 72(1):137–144, 2017.  doi:10.4418/2017.72.1.10.
  * [8] Alessandra Bernardi, Jérôme Brachat, and Bernard Mourrain.  A comparison of different notions of ranks of symmetric tensors.  Linear Algebra Appl., 460:205–230, 2014.  doi:10.1016/j.laa.2014.07.036.
  * [9] Alessandra Bernardi, Joachim Jelisiejew, Pedro Macias Marques, and Kristian Ranestad.  On polynomials with given Hilbert function and applications.  Collect. Math., 69(1):39–64, 2018.  doi:10.1007/s13348-016-0190-2.
  * [10] Alessandra Bernardi, Alessandro Oneto, and Daniele Taufer.  On schemes evinced by generalized additive decompositions and their regularity, 2023.  arXiv:2309.12961.
  * [11] Dario Bini.  Relations between exact and approximate bilinear algorithms. Applications.  Calcolo, 17(1):87–97, 1980.  doi:10.1007/BF02575865.
  * [12] Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti.  $O(n^{2.7799})$ complexity for $n\times n$ approximate matrix multiplication.  Inf. Process. Lett., 8(5):234–235, 1979.  doi:10.1016/0020-0190(79)90113-3.
  * [13] Markus Bläser, Julian Dörfler, and Christian Ikenmeyer.  On the complexity of evaluating highest weight vectors.  In 36th Computational Complexity Conference (CCC 2021), volume 200 of LIPIcs, pages 29:1–29:36. Dagstuhl, 2021.  doi:10.4230/LIPIcs.CCC.2021.29.
  * [14] Grigoriy Blekherman and Zach Teitler.  On maximum, typical and generic ranks.  Math. Ann., 362(3-4):1021–1031, 2015.  doi:10.1007/s00208-014-1150-3.
  * [15] Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam.  On algebraic branching programs of small width.  J. ACM, 65(5):32:1–32:29, 2018.  doi:10.1145/3209663.
  * [16] Weronika Buczyńska and Jarosław Buczyński.  Secant varieties to high degree Veronese reembeddings, catalecticant matrices and smoothable Gorenstein schemes.  J. Algebraic Geom., 23(1):63–90, 2014.  doi:10.1090/S1056-3911-2013-00595-0.
  * [17] Weronika Buczyńska and Jarosław Buczyński.  On differences between the border rank and the smoothable rank of a polynomial.  Glasg. Math. J., 57(2):401–413, 2015.  doi:10.1017/S0017089514000378.
  * [18] Jarosł aw Buczyński and Joachim Jelisiejew.  Finite schemes and secant varieties over arbitrary characteristic.  Differential Geom. Appl., 55:13–67, 2017.  doi:10.1016/j.difgeo.2017.08.004.
  * [19] Weronika Buczyńska and Jarosław Buczyński.  Apolarity, border rank, and multigraded Hilbert scheme.  Duke Math. J., 170(16):3659–3702, 2021.  doi:10.1215/00127094-2021-0048.
  * [20] Weronika Buczyńska, Jarosław Buczyński, and Zach Teitler.  Waring decompositions of monomials.  Journal of Algebra, 378:45–57, 2013.  doi:10.1016/j.jalgebra.2012.12.011.
  * [21] Peter Bürgisser.  The complexity of factors of multivariate polynomials.  Found. Comput. Math., 4(4):369–396, 2004.  doi:10.1007/s10208-002-0059-5.
  * [22] Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi.  Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften.  Springer-Verlag, 1997.  doi:10.1007/978-3-662-03338-8.
  * [23] Enrico Carlini.  Reducing the number of variables of a polynomial.  In Algebraic geometry and geometric modeling, pages 237–247. Springer, Berlin, 2006.  doi:10.1007/978-3-540-33275-6_15.
  * [24] Arthur Cayley.  On the theory of linear transformations.  Cambridge Math. J., IV:193–209, 1845.  Reprinted in A. Cayley, _The Collected Mathematical Papers I_ , 80–94, Cambridge University Press, 1889.  doi:10.1017/CBO9780511703676.014.
  * [25] Luca Chiantini, Jonathan D. Hauenstein, Christian Ikenmeyer, Joseph M. Landsberg, and Giorgio Ottaviani.  Polynomials and the exponent of matrix multiplication.  Bull. LMS, 50(3):369–389, 2018.  doi:10.1112/blms.12147.
  * [26] Alfred Clebsch.  Zur Theorie der algebraischen Flächen.  J. Reine Angew. Math., 58:93–108, 1861.  doi:10.1515/crll.1861.58.93.
  * [27] Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena.  Demystifying the border of depth-3 algebraic circuits.  In FOCS 2021, pages 92–103. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00018.
  * [28] Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, and Avi Wigderson.  Barriers for rank methods in arithmetic complexity.  In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of LIPIcs, pages 1:1–1:19. Dagstuhl, 2018.  doi:10.4230/LIPIcs.ITCS.2018.1.
  * [29] Michael Forbes.  Some concrete questions on the border complexity of polynomials.  Presentation given at the Workshop on Algebraic Complexity Theory (WACT 2016) in Tel Aviv, 2016.  URL: https://www.youtube.com/watch?v=1HMogQIHT6Q.
  * [30] Maciej Gałązka.  Vector bundles give equations of cactus varieties.  Lin. Alg. Appl., 521:254–262, 2017.  doi:10.1016/j.laa.2016.12.005.
  * [31] Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, and Avi Wigderson.  More barriers for rank methods, via a "numeric to symbolic" transfer.  In FOCS 2019, pages 824–844. IEEE, 2019.  doi:10.1109/FOCS.2019.00054.
  * [32] John Hilton Grace and Alfred Young.  The Algebra of Invariants.  Cambridge Library Collection — Mathematics. Cambridge University Press, 2010.  doi:10.1017/CBO9780511708534.
  * [33] Alexander Grothendieck.  Techniques de construction et théorèmes d’existence en géométrie algébrique IV : les schémas de Hilbert.  In Séminaire Bourbaki : années 1960/61, exposés 205-222, number 6 in Séminaire Bourbaki. Société mathématique de France, 1961.  URL: http://www.numdam.org/item/SB_1960-1961__6__249_0/.
  * [34] Leonid Gurvits.  Ryser (or polarization) formula for the permanent is essentially optimal: the Waring rank approach.  Technical Report LA-UR08-06583, Los Alamos National Laboratory, 2008.
  * [35] Mark Haiman and Bernd Sturmfels.  Multigraded Hilbert schemes.  Journal of Algebraic Geometry, 13(4):725–769, 2004.  doi:10.1090/S1056-3911-04-00373-X.
  * [36] Robin Hartshorne.  Algebraic geometry.  Springer, New York, 1977.  Graduate Texts in Mathematics, No. 52.  doi:10.1007/978-1-4757-3849-0.
  * [37] Anthony Iarrobino.  Inverse system of a symbolic power II. the Waring problem for forms.  Journal of Algebra, 174(3):1091–1110, 1995.  doi:10.1006/jabr.1995.1169.
  * [38] Anthony Iarrobino and Vassil Kanev.  Power sums, Gorenstein algebras, and determinantal loci, volume 1721 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 1999.  doi:10.1007/BFb0093426.
  * [39] Christian Ikenmeyer and Abhiroop Sanyal.  A note on VNP-completeness and border complexity.  Inf. Process. Lett., 176:106243, 2022.  doi:10.1016/j.ipl.2021.106243.
  * [40] Joachim Jelisiejew.  An upper bound for the Waring rank of a form.  Arch. Math. (Basel), 102(4):329–336, 2014.  doi:10.1007/s00013-014-0632-6.
  * [41] Joachim Jelisiejew.  Pathologies on the Hilbert scheme of points.  Inventiones mathematicae, 220(2):581–610, 2020.  doi:10.1007/s00222-019-00939-5.
  * [42] Joachim Jelisiejew and Tomasz Mańdziuk.  Limits of saturated ideals, 2022.  arXiv:2210.13579.
  * [43] Neeraj Kayal and Nitin Saxena.  Polynomial identity testing for depth 3 circuits.  comput. complex., 16(2):115–138, 2007.  doi:10.1007/s00037-007-0226-9.
  * [44] Hanspeter Kraft.  Geometrische Methoden in der Invariantentheorie.  Springer, Berlin, 2 edition, 1985.  doi:10.1007/978-3-663-10143-7.
  * [45] Mrinal Kumar.  On the power of border of depth-3 arithmetic circuits.  ACM Trans. Comput. Theory, 12(1):5:1–5:8, 2020.  doi:10.1145/3371506.
  * [46] Joseph M. Landsberg and Zach Teitler.  On the ranks and border ranks of symmetric tensors.  Found. Comput. Math., 10(3):339–366, 2010.  doi:10.1007/s10208-009-9055-3.
  * [47] Thomas Lehmkuhl and Thomas Lickteig.  On the order of approximation in approximative triadic decompositions of tensors.  Theor. Comput. Sci., 66(1):1–14, 1989.  doi:10.1016/0304-3975(89)90141-2.
  * [48] Ketan Mulmuley and Milind A. Sohoni.  Geometric complexity theory I: an approach to the P vs. NP and related problems.  SIAM J. Comput., 31(2):496–526, 2001.  doi:10.1137/S009753970038715X.
  * [49] Noam Nisan.  Lower bounds for non-commutative computation (extended abstract).  In STOC’91: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 410–418. ACM, 1991.  doi:10.1145/103418.103462.
  * [50] Rufus Oldenburger.  Polynomials in several variables.  Annals of Mathematics, 41(3):694–710, 1940.  doi:10.2307/1968741.
  * [51] Francesco Palatini.  Sulle superficie algebriche i cui $S_{h}$ $(h+1)$-seganti non riempiono lo spazio ambiente.  Atti della R. Acc. delle Scienze di Torino, 41:634–640, 1906.  URL: https://archive.org/details/attidellarealeac41real/page/634.
  * [52] Nitin Saxena.  Diagonal circuit identity testing and lower bounds.  In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Part I, volume 5125 of Lecture Notes in Computer Science, pages 60–71. Springer, 2008.  doi:10.1007/978-3-540-70575-8_6.
  * [53] James Joseph Sylvester.  On the principles of the calculus of forms.  J. Cambridge and Dublin Math., 7:52–97, 1852.  Reprinted in J. J. Sylvester, _The Collected Mathematical Papers I_ , 284–327, Cambridge University Press, 1904.
  * [54] Alessandro Terracini.  Sulle $V_{k}$ per cui la varietà degli $S_{h}$ $(h+1)$-seganti ha dimensione minore dell’ordinario.  Rend. Circ. Mat., 31:392–396, 1911.  doi:10.1007/BF03018812.
  * [55] WACT 2016.  Some accessible open problems.  URL: https://www.cs.tau.ac.il/~shpilka/wact2016/concreteOpenProblems/openprobs.pdf.

##  Appendix A Behind the scenes: generalized additive decompositions and
schemes

We will now discuss how the results similar to these of the Section 2 can be
obtained from apolarity theory and the study of $0$-dimensional schemes in
projective space. The connection between variations of Waring rank, apolar
schemes and generalized additive decompositions is explored in detail by
Bernardi, Brachat and Mourrain in [8] (they use a subtly different notion of
generalized affine decomposition). In particular, there exists a much stronger
version of Lemma 2.13 (although with a slightly worse restriction on degree),
which tightly relates generalized additive decompositions of a homogeneous
polynomial $f$ to its _cactus rank_ $\mathsf{CR}(f)$, a variation of Waring
rank arising in apolarity theory defined in terms of $0$-dimensional schemes
in the space of linear forms in place of finite sets of linear forms. We will
formally define the notions of cactus rank and size of a generalized additive
decomposition later, for not let us state the theorem, which is based on [8,
Thm. 3.5].

######  Theorem A.1.

If $\deg f\geq 2\cdot\mathsf{CR}(f)-1$, then the cactus rank of a homogeneous
polynomial $f$ is equal to the minimal possible size of a generalized additive
decomposition for $f$.

To connect cactus rank to border rank we need and intermediate notion of
_smoothable rank_ $\mathsf{SR}(f)$. Smoothable rank is an upper bound on
cactus rank, and it coincides with border rank for polynomials of high enough
degree.

######  Theorem A.2 ([17]).

If $\deg f\geq\underline{\mathsf{WR}}(f)-1$, then
$\underline{\mathsf{WR}}(f)=\mathsf{SR}(f)$.

The goal of this section is to review the basic notions of apolarity theory,
define cactus rank, smoothable rank and size of a generalized additive
decomposition, and explain the ideas behind the proof of Theorem A.1 stated
above.

###  A.1 Some notation

Let us fix the notation. Let $S=\mathbb{C}[x_{1},\dots,x_{n}]$ be the algebra
of polynomials and $T=\mathbb{C}[\partial_{1},\dots,\partial_{n}]$ be the
algebra of polynomial differential operators with constant coefficients
(referred to as _diffoperators_ in what follows), which acts on $S$ in the
standard way.

Denote by $V$ the space of linear forms $S_{1}$. We identify $T_{1}$ with the
dual space $V^{*}$. More generally, the action of $T$ on $S$ gives rise to a
nondegenerate pairing between the homogeneous parts $S_{d}$ and $T_{d}$ for
every $d$. We use orthogonality with respect to this pairing, that is, for a
subset $F\subset S_{d}$ we denote $F^{\perp}=\\{\alpha\in T_{d}\mid\alpha\cdot
f=0\text{ for all $f\in F$}\\}$, and vice versa, for a subset $D\subset T_{d}$
we let $D^{\perp}=\\{f\in S_{d}\mid\alpha\cdot f=0\text{ for all $\alpha\in
D$}\\}$

###  A.2 Projective geometry

The algebra $T$ is isomorphic to $\mathbb{C}[V]$, the algebra of polynomials
in the coefficients of linear forms. The isomorphism maps a homogeneous
element $\alpha\in T_{d}$ to $\overline{\alpha}\in\mathbb{C}[V]_{d}$ defined
as $\overline{\alpha}(\ell)=\alpha\cdot\frac{\ell^{d}}{d!}$.

Recall that a homogeneous ideals in $T\cong\mathbb{C}[V]$ are in
correspondence with subsets of the projective space $\mathbb{P}V$. More
specifically, projective varieties are subsets of $\mathbb{P}V$ defined by
vanishing of some set of polynomials. The set of all polynomials vanishing on
a projective variety $Z$ is a homogeneous ideal $I$, which is saturated
($\alpha T_{1}\subset I\Rightarrow\alpha\in I$) and radical ($\alpha^{n}\in
I\Rightarrow\alpha\in I$). If we consider an ideal $I$ which is saturated but
not radical, it defines a projective scheme, which coincides with the variety
defined by $I$ as a topological space, but has additional structure which
distinguishes it from this variety.

If $I\subset T$ is a homogeneous ideal, then the function
$h_{I}(p)=\dim(T_{p}/I_{p})$ is called the _Hilbert function_ of $I$. The
Hilbert function of a homogeneous ideal $I$ always coincides with some
polynomial $H_{I}(p)$ for $p$ large enough. This polynomial is called the
_Hilbert polynomial_ of $I$. Many topological and geometric properties of a
projective variety or a scheme can be deduced from its Hilbert polynomial, in
particular, its dimension and degree [36, §I.7]. We are specifically
interested in ideals with constant Hilbert polynomials. These ideals
corresponds to schemes of dimension $0$. This means that a variety with
Hilbert polynomial $r$ is a set of $r$ distinct points in $\mathbb{P}V$. In
algebra, ideals with constant Hilbert polynomial $H_{I}=r$ are referred to as
_ideals of Krull dimension 1_ (the mismatch with the dimension of a scheme is
because in algebra dimension is counted in affine space). The number $r$ is
referred to as the _length_ of the ideal or the _degree_ of the corresponding
$0$-dimensional scheme.

###  A.3 Apolarity theory

The connection between Waring rank and algebraic geometry is provided by the
apolarity theory, which has its source in the works of Sylvester and Macaulay.

######  Definition A.3.

The _apolar ideal_ of a polynomial $f\in S$ is an ideal in $T$ defined as
$\operatorname{Ann}(f)=\\{\alpha\in T\mid\alpha\cdot f=0\\}$. The _apolar
algebra_ of $f$ is $A(f)=T/\operatorname{Ann}(f)$. An ideal $I\subset T$ is
said to be _apolar_ to $f$ if it lies in $\operatorname{Ann}(f)$. A scheme
$Z\subset\mathbb{P}V$ is _apolar_ to $f$ if its defining ideal is.

Note that as a vector space, $A(f)$ is isomorphic to the space of all partial
derivatives $T\cdot f$ via $(\alpha+\operatorname{Ann}(f))\mapsto\alpha\cdot
f$.

To relate apolarity to Waring rank, we also define an ideal associated with a
set of linear forms. Given $r$ linear forms $\ell_{1},\dots,\ell_{r}$,
consider the sequences of subspaces
$E_{p}=\operatorname{Span}(\\{\ell_{1}^{p},\dots,\ell_{r}^{p}\\})\subset
S_{p}$ and $I_{p}=E_{p}^{\perp}\subset T_{p}$. An important fact is that
$I=\bigoplus_{p=0}^{\infty}I_{p}$ is a homogeneous ideal in $T$. From the
geometric point of view it can be described as the vanishing ideal of the set
$Z=\\{[\ell_{1}],\dots,[\ell_{r}]\\}$ in the projective space $\mathbb{P}V$.
Algebraically, the fact that $I$ is a homogeneous ideal follows from the
following useful proposition.

######  Proposition A.4.

A sequence of subspaces $E_{p}\subset S_{p}$ satisfies the property
$T_{1}\cdot E_{p+1}\subset E_{p}$ if and only if
$I=\bigoplus_{p=0}^{\infty}E_{p}^{\perp}$ is a homogeneous ideal. If this is
the case, then $h_{I}(p)=\dim E_{p}$.

######  Proof A.5.

Let $I_{p}=E_{p}^{\perp}$. The fact that $I$ is a homogeneous ideal can be
written as $I_{p+1}\supset T_{1}\cdot I_{p}$, which is equivalent to
$T_{1}\cdot E_{p+1}\subset E_{p}$, as both of these statements reduce to

$(\alpha\partial)\cdot f=\alpha\cdot(\partial f)=0\text{ for all $\alpha\in
I_{p},\partial\in T_{1},f\in E_{p+1}$.}$

For the Hilbert function, note that $\dim(T_{p}/I_{p})=\dim T_{p}-\dim
I_{p}=\dim I_{p}^{\perp}=\dim E_{p}$.

######  Lemma A.6 (Apolarity lemma).

$f\in S_{d}$ is apolar to a homogeneous ideal
$I=\bigoplus_{p=0}^{\infty}E_{p}^{\perp}$ if and only if $f\in E_{d}$.

######  Proof A.7.

If $I$ is apolar to $f$, then $I_{d}\subset\operatorname{Ann}(f)_{d}$ and
therefore $E_{d}\supset(\operatorname{Ann}(f)_{d})^{\perp}=f^{\perp\perp}\ni
f$.

For the other direction, let $f\in E_{d}$. Note that
$\operatorname{Ann}(f)_{p}=T_{p}$ for $p>d$, so we only need to check
$I_{p}\subset\operatorname{Ann}(f)$ for $p\leq d$. Note that if we have
$\alpha\cdot f\neq 0$ for $\alpha\in T_{p}$ with $p<d$, then there exists
$\partial\in T_{1}$ such that $\partial\alpha\cdot f=\partial\cdot(\alpha\cdot
f)\neq 0$. This can be restated as
$T_{1}\alpha\subset\operatorname{Ann}(f)\Rightarrow\alpha\in\operatorname{Ann}(f)$
for all $\alpha\in T_{p}$ with $p<d$.

For $p\leq d$ we have $\alpha\in I_{p}\Rightarrow T_{1}^{d-p}\alpha\subset
I_{d}=E_{d}^{\perp}\Rightarrow T_{1}^{d-p}\alpha\cdot
f=0\Rightarrow\alpha\in\operatorname{Ann}(f)$, which proves
$I_{p}\subset\operatorname{Ann}(f)$.

######  Corollary A.8 (Apolarity for Waring rank).

$f\in S_{d}$ has $\mathsf{WR}(f)\leq r$ if and only if $f$ is apolar to the
vanishing ideal of $r$ points in $\mathbb{P}V$.

######  Proof A.9.

By definition, $\mathsf{WR}(f)\leq r$ if and only if there exists linear forms
$\ell_{1},\dots,\ell_{r}$ such that
$f\in\operatorname{Span}(\\{\ell_{1}^{d},\dots,\ell_{r}^{d}\\})$. As was
discussed before, the vanishing ideal $I$ of the set
$Z=\\{[\ell_{1}],\dots,[\ell_{r}]\\}$ has
$E_{d}=I_{d}^{\perp}=\operatorname{Span}(\\{\ell_{1}^{d},\dots,\ell_{r}^{d}\\})$,
and by apolarity lemma $f\in E_{d}$ is equivalent to $f$ being apolar to $I$.

###  A.4 Families of subspaces, ideals and their limits

Before considering border Waring rank, we need to define limits of families of
subspaces and families of ideals.

Let $W$ be a vector space. We consider two types of families of subspaces in
$W$. First is a family of subspaces of the form
$E(\epsilon)=\operatorname{Span}(\\{w_{1}(\epsilon),\dots,w_{r}(\epsilon)\\})$
where $w_{k}(\epsilon)$ are families of vectors in $W$ with coordinates given
by rational functions of $\epsilon$. We write $w_{k}\in W(\epsilon)$ in this
case. The second type is a family $E(\epsilon)=\\{w\mid
y_{1}(\epsilon;w)=\dots=y_{q}(\epsilon;w)=0\\}$ of vector spaces defined by
linear forms $y_{1},\dots,y_{q}\in W^{*}(\epsilon)$ which again depend
rationally on the parameter $\epsilon$.

In both cases we define the limit $\widehat{E}=\lim_{\epsilon\to
0}E(\epsilon)$ as the subspace containing the limits of all families $w\in
W(\epsilon)$ such that $w(\epsilon)\in E(\epsilon)$ for $\epsilon\neq 0$
(whenever $E(\epsilon)$ and $w(\epsilon)$ are defined).

For
$E(\epsilon)=\operatorname{Span}(\\{w_{1}(\epsilon),\dots,w_{r}(\epsilon)\\})$
from semicontinuity of rank we have that the maximal possible value of $\dim
E(\epsilon)$ is attained on an open set of values of $\epsilon$. The situation
is opposite for the family of the second type
$E(\epsilon)=\operatorname{Span}(\\{y_{1}(\epsilon),\dots,y_{q}(\epsilon)\\})^{\perp}$.
In both cases the dimension of $\widehat{E}$ cannot be higher then the generic
dimension. Indeed, if $\widehat{E}$ contains linearly indeoendent vectors
$v_{1},\dots,v_{m}$, then there are families
$v_{1}(\epsilon),\dots,v_{m}(\epsilon)$ which have them as limits, and these
families will be linearly independent for an open subset of values of
$\epsilon$. Considering two families $E(\epsilon)\subset W$ and
$E(\epsilon)^{\perp}\subset W^{*}$ together, we see that $\dim\widehat{E}$ is
actually equal to the generic dimension of $E(\epsilon)$ (maximal dimension
for the families of the first type, and minimal — for the families of the
second type).

Alternatively, we may associate with a family of subspaces a family of points
in the _Grassmannian_ – the space of all $k$-dimensional subspaces in $W$. The
Grassmannian can be defined as the projective variety in
$\mathbb{P}\Lambda^{k}W$ consisting of all points of the form
$[w_{1}\wedge\dots\wedge w_{k}]$, which represent $k$-dimensional subspaces
spanned by $w_{1},\dots,w_{k}$ respectively. If $E(\epsilon)$ is a family with
generic dimension $k$ and $v_{1}(\epsilon),\dots,v_{k}(\epsilon)\in
E(\epsilon)$ are linearly independent for generic values of $\epsilon$, then
we can define a rational map $\epsilon\mapsto[v_{1}(\epsilon)\wedge\dots\wedge
v_{k}(\epsilon)]$ and take the limit of this map in the Grassmannian.

Suppose $I(\epsilon)$ is a family of homogeneous ideals in $T$, that is,
$I(\epsilon)=\bigoplus_{p=0}^{\infty}I_{p}(\epsilon)$ for the families of
subspaces $I_{p}(\epsilon)\subset T_{p}$ such that $I_{p+1}(\epsilon)\supset
I_{p}(\epsilon)\cdot T_{1}$. By continuity of multiplication for the limit
subspaces $\widehat{I}_{p}=\lim_{\epsilon\to 0}I_{p}(\epsilon)$ we still have
$\widehat{I}_{p+1}\supset\widehat{I}_{p}\cdot T_{1}$. Hence $\widehat{I}$ is
again a homogeneous ideal in $T$. This notion of limit of ideals corresponds
to taking limits in the _multigraded Hilbert scheme_ , which is a space of
ideals with given Hilbert function, see [35]. We refer to this limit as the
_multigraded limit of a family of ideals_. The problem is that the limit in
the multigraded Hilbert scheme can be non-saturated and thus not correspond to
a geometric object in projective space.

For example, consider three families of points
$(1:0:1),(-1:0:1),(0:\epsilon:1)$ in $\mathbb{P}^{2}$. The family of vanishing
ideals is $\left<x_{1}x_{2},x_{2}(x_{2}-\epsilon
x_{3}),\epsilon(x_{1}^{2}-x_{3}^{2})+x_{2}x_{3},x_{1}^{3}-x_{1}x_{3}^{2}\right>$.
Taking $\epsilon\to 0$ we obtain the ideal
$\left<x_{1}x_{2},x_{2}^{2},x_{2}x_{3},x_{1}^{3}-x_{1}x_{3}^{2}\right>$, which
is not saturated, since it contains $x_{1}x_{2},x_{2}^{2},x_{2}x_{3}$ but not
$x_{2}$. Taking the saturation, we obtain
$\left<x_{2},x_{1}^{3}-x_{1}x_{3}^{2}\right>$ which corresponds to three
points $(1:0:1),(-1:0:1),(0:0:1)$ as expected.

We can take saturation after obtaining the limit ideal. This notion of limit
corresponds to limits in the _Hilbert scheme_ , which is the space of ideals
with the fixed Hilbert polynomial. It was defined by Grothendieck [33], see
also [38, Appx.C].

###  A.5 Border apolarity

We will now describe the basic idea of the apolarity theory for border Waring
rank, which was developed by Buczyńska and Buczyński in [19].

Let $f=\lim_{\epsilon\to 0}\sum_{k=1}^{r}\ell_{k}^{d}$ be a border Waring rank
decomposition. Consider the families of subspaces
$E_{p}(\epsilon)=\operatorname{Span}(\\{\ell_{1}(\epsilon)^{p},\dots,\ell_{r}(\epsilon)^{p}\\})\subset
S_{p}$ and the family of homogeneous ideals
$I(\epsilon)=\bigoplus_{p=0}^{\infty}E_{p}(\epsilon)^{\perp}$ in $T$.

As $\epsilon\to 0$, we obtain a sequence of subspaces
$\widehat{E}_{p}=\lim_{\epsilon\to 0}E_{p}(\epsilon)\subset S_{p}$ and a
homogeneous ideal $\widehat{I}=\lim_{\epsilon\to 0}I(\epsilon)$ (taking the
limit in the multigraded Hilbert scheme). Let
$\overline{f}=\sum_{k=1}^{r}\ell_{k}^{d}\in S_{d}(\epsilon)$, so that
$f=\lim_{\epsilon\to 0}\overline{f}(\epsilon)$. By the Apolarity Lemma the
ideal $I(\epsilon)$ is apolar to $\overline{f}(\epsilon)$ for $\epsilon\neq
0$, which means that $\alpha(\epsilon)\cdot\overline{f}(\epsilon)=0$ for every
$\alpha(\epsilon)\in I(\epsilon)$. Since the action of $T$ on $S$ is
continuous, we obtain from this $(\lim_{\epsilon\to 0}\alpha(\epsilon))\cdot
f=0$, if the limit exists. Thus $\widehat{I}$ is apolar to $f$.

On the other hand, suppose that $f\in S_{d}$ is apolar to an ideal
$\widehat{I}$ which is a _limit of ideals of $r$ points_, that is, there
exists a family $I(\epsilon)$ such that $I(\epsilon)$ is the vanishing ideal
of a set of $r$ points in $\mathbb{P}V$. Define
$E_{d}(\epsilon)=I(\epsilon)_{d}^{\perp}\subset S_{d}$. For $\epsilon\neq 0$
the subspace $E_{d}(\epsilon)$ is a span of powers of $r$ linear forms, so it
consists of polynomials with Waring rank at most $r$. Since $f$ is orthogonal
to $\widehat{I}_{d}$, it lies in the limit $\lim_{\epsilon\to
0}E_{d}(\epsilon)$ and thus has border Waring rank at most $r$.

######  Theorem A.10 (Border apolarity, [19]).

$f\in S_{d}$ has $\underline{\mathsf{WR}}(f)\leq r$ if and only if $f$ is
apolar to an ideal $\widehat{I}$ which is a limit of ideals of $r$ points.

###  A.6 Various ranks via apolarity.

The apolarity lemma provides a template for defining different notions of rank
for homogeneous polynomials by varying the class of ideals apolar to $f$.

######  Definition A.11.

Let $\mathcal{C}$ be a class of ideals of Krull dimension $1$. If $f\in S_{d}$
is a homogeneous polynomial, we define the $\mathcal{C}$-rank of $f$ as the
minimal $r$ such that there exists an ideal $I\subset\mathcal{C}$ apolar to
$f$ with length $r$.

As we have seen, Waring rank and border Waring rank are special cases of this
definition corresponding to ideals of points and their limits.

We are now ready to define cactus rank and smoothable rank. The cactus rank
$\mathsf{CR}(f)$ is obtained from the template definition above if we consider
the class of all saturated ideals with constant Hilbert polynomial, that is,
ideals of $0$-dimensional schemes. The smoothable rank $\mathsf{SR}(f)$
corresponds to saturated limits of ideals of points. In addition, the border
cactus rank $\underline{\mathsf{CR}}(f)$ is defined by considering limits of
saturated ideals.

Class of ideals | Rank | Notation
---|---|---
Ideals of points (radical saturated ideals) | Waring rank | $\mathsf{WR}(f)$
Limits of ideals of points | Border Waring rank | $\underline{\mathsf{WR}}(f)$
Smoothable ideals (saturated limits of ideals of points) | Smoothable rank | $\mathsf{SR}(f)$
Saturated ideals | Cactus rank | $\mathsf{CR}(f)$
Saturable ideals (limits of saturated ideals) | Border cactus rank | $\underline{\mathsf{CR}}(f)$

The unified definition allows us to determine relations between these
different ranks.

######  Theorem A.12 ([8]).

The following inequalities hold:
$\underline{\mathsf{CR}}(f)\leq\mathsf{CR}(f)\leq\mathsf{SR}(f)\leq\mathsf{WR}(f)$
and
$\underline{\mathsf{CR}}(f)\leq\underline{\mathsf{WR}}(f)\leq\mathsf{SR}(f)\leq\mathsf{WR}(f)$.

######  Proof A.13.

The inequality $\underline{\mathsf{WR}}(f)\leq\mathsf{SR}(f)$ follows from the
fact that if the saturation $I^{\operatorname{sat}}\supset I$ is apolar to
$f$, then $I$ is also apolar to $f$. Other inequalities follow from the
containments between corresponding classes of ideals.

In addition, for high enough degree the border Waring rank coincides with
smoothable rank, and border cactus rank coincides with cactus rank. To prove
this, we will need the following property of ideals of Krull dimension $1$.

######  Theorem A.14 ([38, Thm. 1.69]).

If $I$ is a saturated ideal with $H_{I}=r$, then $h_{I}$ is nondecreasing and
$h_{I}(p)=r$ for $p\geq r-1$.

Note that this applying this to the ideal of $r$ points
$\\{[\ell_{1}],\dots,[\ell_{r}]\\}$ we get the well-known property that $p$-th
powers of pairwise non-proportional linear forms are linearly independent for
$p\geq r-1$.

######  Theorem A.15 ([16, Prop. 2.5]).

If $\deg f\geq\underline{\mathsf{WR}}(f)-1$, then
$\underline{\mathsf{WR}}(f)=\mathsf{SR}(f)$. Similarly, if $\deg
f\geq\underline{\mathsf{CR}}(f)-1$, then
$\underline{\mathsf{CR}}(f)=\mathsf{CR}(f)$.

######  Proof A.16.

Suppose $\underline{\mathsf{WR}}(f)=r$. Let $I$ be the ideal apolar to $f$
which is a limit of ideals of $r$ points, and let $J=I^{\operatorname{sat}}$
be its saturation. We have $h_{I}(p)=r$ for $p\geq r-1$, because this property
is true for ideals of points and $I$ is a limit of ideals of points. In
particular, $h_{I}(d)=r$ for $d=\deg f$. It is known that $J_{p}=I_{p}$ for
$p$ large enough, thus $H_{J}=H_{I}=r$. We have $r=h_{I}(d)\leq h_{J}(d)\leq
r$, where the first inequality follows from $I\subset
I^{\operatorname{sat}}=J$, and the second one from the monotonicity of
$h_{J}$. Therefore $I_{d}=J_{d}$, and thus $f\in J_{d}^{\perp}=I_{d}^{\perp}$,
that is, $f$ is apolar to $J$, the saturated limit of ideals of points. We
obtain $\mathsf{SR}(f)\leq r=\underline{\mathsf{WR}}(f)$. Together with the
opposite inequality from Theorem A.12, this gives us the required equality.

The proof of the second statement is the same, with ideal of $r$ points
replaces by saturated ideals of length $r$.

###  A.7 Size of generalized additive decompositions

We now describe how to measure the size of a generalized additive
decomposition in a way compatible with various notions of rank.

######  Definition A.17.

The _partial derivative space_ of a polynomial $f\in S$ (not necessarily
homogeneous) is the vector space $T\cdot f$ spanned by $f$ and all its partial
derivatives of all orders.

######  Definition A.18.

Let $\ell$ be a linear form and let $\partial\in T_{1}$ be a partial
derivative such that $\partial\ell=1$. Denote
$T^{\prime}=\mathbb{C}[\ell^{\perp}]\subset T$ and
$S^{\prime}=\mathbb{C}[\partial^{\perp}]\subset S$. We define the
_compression_ $f_{(\partial,\ell)}$ of a homogeneous polynomial $f\in S_{d}$
with respect to $\ell$ and $\partial$ as follows. Write

$f=\sum_{i=0}^{d}\frac{\ell^{i}}{i!}f_{i}.$

with $f_{i}\in S^{\prime}_{d-i}$. Then
$f_{(\partial,\ell)}=\sum_{i=0}^{d}f_{i}$. The _compressed size_ of $f$ with
respect to $(\partial,\ell)$ is the dimension of the partial derivative space
$T^{\prime}\cdot f_{(\partial,\ell)}$

One can check that the compressed does not depend on the choice of $\partial$
as long as $\partial\ell=1$; this can be proved by hand, and it is obtained in
[9] in a more intrinsic way.

######  Definition A.19.

The _size_ of a generalized additive decomposition

$f=\sum_{k=1}^{m}\ell_{k}^{d-r_{k}+1}g_{k}$

is defined as the sum of compressed sizes of the summands
$\ell_{k}^{d-r_{k}+1}g_{k}$ with respect to the corresponding linear forms
$\ell_{k}$.

###  A.8 Schemes and generalized additive decompositions

We will now prove several lemmas which connect generalized additive
decompositions and apolar ideals, finishing the proof of Theorem A.1.

######  Lemma A.20 ([9]).

Let $\ell$ be a linear form and let $f\in S_{d}$ be a homogeneous polynomial.
There exists a homogeneous ideal $I$ apolar to $f$ with length equal to the
compressed size of $f$ with respect to $\ell$.

######  Proof A.21.

Let $\partial\in T_{1}$ be such that $\partial\ell=1$. Denote
$S^{\prime}=\mathbb{C}[\partial^{\perp}]$ and
$T^{\prime}=\mathbb{C}[\ell^{\perp}]$ as above. The rings $S^{\prime}$ and
$T^{\prime}$ are in the same dual relationship as $S$ and $T$, and $T$ is
generated by $T^{\prime}$ and $\partial$.

We start from the ideal $J=\operatorname{Ann}(f_{(\partial,\ell)})\subset
T^{\prime}$ and homogenize it using $\partial$. That is, define the
homogenization map from $T^{\prime}_{\leq
p}=\bigoplus_{j=0}^{p}T^{\prime}_{j}$ to $T_{p}$ sending
$\alpha=\sum_{j=0}^{p}\alpha_{j}$ to $\sum_{j=0}^{p}\partial^{p-j}\alpha_{j}$.
The homogeneous part $I_{p}$ of the ideal $I$ is then the image of $J_{\leq
p}$ under this homogenization map.

To show that the ideal $I$ is apolar to $f$, write
$f=\sum_{i=0}^{d}\frac{\ell^{i}}{i!}f_{d-i}$ with $f_{i}\in S^{\prime}_{i}$.
Then $f_{(\partial,\ell)}=\sum_{i=0}^{d}f_{i}$. If
$\alpha^{\prime}=\sum_{j=0}^{p}\alpha_{j}\in T^{\prime}$ and
$\alpha=\sum_{j=0}^{p}\partial^{p-j}\alpha_{j}$ is the $\alpha^{\prime}$
homogenized, then the statement $\alpha^{\prime}\cdot f_{(\partial,\ell)}=0$
is equivalent to $\alpha\cdot f=0$, since they are both equivalent to
$\sum_{j=0}^{p}\alpha_{j}f_{j+e}=0$ for all $e\geq 0$. Since $J$ is apolar to
$f_{(\partial,\ell)}$, $I$ is apolar to $f$.

Since $f_{(\partial,\ell)}$ has degree at most $d$, $J$ contains
$T^{\prime}_{p}$ for $p>d$. Hence

$T^{\prime}\cdot f_{(\partial,\ell)}\cong
A(f_{(\partial,\ell)})=T^{\prime}/J\cong T^{\prime}_{\leq d}/J_{\leq d}$

as vector spaces, and for $p>d$ we have $T_{p}/I_{p}\cong T^{\prime}_{\leq
p}/J_{\leq p}\cong T^{\prime}_{\leq d}/J_{\leq d}$. Therefore, for $p$ large
enough $\dim T_{p}/I_{p}=\dim T^{\prime}\cdot f_{(\partial,\ell)}$, and
$H_{I}=\dim T^{\prime}\cdot f_{(\partial,\ell)}$ as required.

######  Lemma A.22.

Suppose $f\in S_{d}$ is apolar to a saturated primary homogeneous ideal $I$
with length $r$. If $d\geq 2r-1$, then $f$ has a one-summand generalized
additive decomposition of size at most $r$.

######  Proof A.23.

If $I$ is an ideal of Krull dimension $1$, then it defines a $0$-dimensional
scheme, and if it is primary, then this scheme is supported at one point
$[\ell]\in\mathbb{P}V$. The ideal corresponding to this point is
$J=\operatorname{Ann}(\ell)=\left<\ell^{\perp}\right>$ and we have
$J^{m}\subset I\subset J$ for some $m\leq r$. For the corresponding dual space
$E_{p}$ with $p\geq m$ we have
$E_{p}\subset(J^{m})_{p}^{\perp}=\\{\ell^{p-m}g\mid g\in S_{\leq m}\\}$. Since
$f\in E_{d}$, it has a one-summand generalized additive decomposition
$f=\ell^{d-m}g$.

Choose $\partial\in T_{1}$ such that $\partial\ell=1$. Write
$f=\sum_{i=0}^{m}\frac{\ell^{d-i}}{(d-i)!}f_{i}$ with
$f_{i}\in\mathbb{C}[\partial^{\perp}]_{i}$. Then
$f_{(\partial,\ell)}=\sum_{i=0}^{m}f_{i}$ has degree at most $m$. For every
$\alpha^{\prime}=\sum_{j=0}^{m}\in\mathbb{C}[\ell^{\perp}]_{\leq m}$ and the
corresponding homogeneous $\alpha=\sum_{j=0}^{m}\partial^{m-j}\alpha_{j}$ we
have

$\alpha^{\prime}\cdot f_{(\partial,\ell)}=\sum_{j\geq i}\alpha_{j}\cdot f_{i}$

and

$\alpha\cdot f=\sum_{j\leq i}\frac{\ell^{d-m+j-i}}{(d-m+j-i)!}\alpha_{j}\cdot
f_{i}.$

Therefore, there is an isomorphism between $\partial^{*}f_{(\partial,\ell)}$
and $T^{m}\cdot f\subset E_{d-m}$. Note that $d-m\geq r$. By Theorem A.14 we
have $r=H_{I}=\dim E_{d-m}\geq\dim\partial^{*}f_{(\partial,\ell)}$.

######  Proof A.24 (Proof of Theorem A.1).

If $\mathsf{CR}(f)\leq r$, then there exists a saturated homogeneous ideal $I$
apolar to $f$ with Hilbert polynomial $r$. This ideal corresponds to a
$0$-dimensional scheme $Z$, which consists of several points. Each point
corresponds to a primary ideal in the primary decomposition
$I=I^{(1)}\cap\dots\cap I^{(m)}$, and for the Hilbert polynomials it is true
that $H_{I}=H_{I^{(1)}}+\dots+H_{I^{(m)}}$. Defining $E_{d}=I_{d}^{\perp}$ and
$E^{(k)}_{d}=(I^{(k)}_{d})^{\perp}$ we have
$E_{d}=E^{(1)}_{d}+\dots+E^{(m)}_{d}$. Therefore, $f=f^{(1)}+\dots+f^{(m)}$
where $f^{(k)}\in E^{(k)}_{d}$. By Lemma A.22 each $f^{(k)}$ contributes one
summand to the generalized additive decomposition. The sizes of these summands
are bounded by $H_{I^{(k)}}$, and the total size is bounded by $r$.

Conversely, if $f$ has a generalized additive decomposition of size $r$, then
from each summand we can construct an ideal using Lemma A.20 and take the
intersection of these ideals to get an ideal apolar to $f$ with Hilbert
function at most $r$.

##  Appendix B Characterizing small border Waring rank

The results on generalized additive decompositions from §2.3 can be used to
describe the polynomials of border rank $2$ and $3$, reproving the results of
Landsberg and Teitler [46, Sec. 10].

######  Theorem B.1.

A polynomial $f$ with $\underline{\mathsf{WR}}(f)=2$ must have the form
$\ell_{1}^{d}+\ell_{2}^{d}$ or $\ell_{1}^{d-1}\ell_{2}$ where $\ell_{1}$ and
$\ell_{2}$ are linear forms.

In the first case, every border rank decomposition for $f$ has the form

$f=(\ell_{1}+\epsilon\widehat{\ell}_{1})^{d}+(\ell_{2}+\epsilon\widehat{\ell}_{2})^{d}$

for some
$\widehat{\ell}_{1},\widehat{\ell}_{2}\in\mathbb{C}[[\epsilon]][\boldsymbol{x}]_{1}$.

In the second case, every border rank decomposition for $f$ has the form

$f=\frac{1}{\epsilon^{M}}\left(a\ell_{1}+\epsilon\widehat{\ell}_{1}+\epsilon^{M}(\frac{1}{a^{d-1}d}\ell_{2}+\ell_{3})\right)^{d}-\frac{1}{\epsilon^{M}}\left(a\ell_{1}+\epsilon\widehat{\ell}_{1}+\epsilon^{M}(\ell_{3}+\epsilon\widehat{\ell}_{2})\right)^{d}$

for some $a\in\mathbb{C}$, $\ell_{3}\in\mathbb{C}[\boldsymbol{x}]_{1}$ and
$\widehat{\ell}_{1},\widehat{\ell}_{2}\in\mathbb{C}[[\epsilon]][\boldsymbol{x}]_{1}$.

######  Proof B.2.

By Lemma 2.13 $f$ has a generalized additive decomposition

$f=\sum_{i=1}^{m}\ell_{i}^{d-r_{i}+1}g_{i}$

with $\sum_{i=1}^{m}r_{i}=\underline{\mathsf{WR}}(f)=2$, $\deg g_{i}=r_{i}-1$
There are only two possible partitions $\sum r_{i}=2$. In the case
$m=2,r_{1}=r_{2}=1$ the generalized additive decomposition is actually a
Waring rank decomposition $f=\ell_{1}^{d}+\ell_{2}^{d}$. In the case
$m=1,r_{1}=2$ the polynomial $g_{1}$ is a linear form, renaming it we have
$f=\ell_{1}^{d-1}\ell_{2}$.

From the proof of Lemma 2.13 it is clear that in the first case the
decomposition must be a sum of two local decompositions of rank $1$, and a
local decomposition of rank $1$ is just a power of
$\ell+\epsilon\widehat{\ell}$ for some
$\widehat{\ell}\in\mathbb{C}[[\epsilon]][\boldsymbol{x}]_{1}$.

In the second case the decomposition must be local, which means that both
summands in the decomposition have the form
$\epsilon^{-M}(a\ell_{1}+\epsilon\widehat{\ell})$. To obtain
$\ell_{1}^{d-1}\ell_{2}$ in the limit, the first $M$ terms in each summand
must cancel, and the terms in $\epsilon^{M}$ must differ by
$\frac{1}{a^{d-1}d}\ell_{2}$.

######  Theorem B.3.

A polynomial with $\underline{\mathsf{WR}}(f)=3$ must have one of the three
normal forms: $\ell_{1}^{d}+\ell_{2}^{d}+\ell_{3}^{d}$ or
$\ell_{1}^{d}+\ell_{2}^{d-1}\ell_{3}^{d}$ or
$\ell_{1}^{d-1}\ell_{2}+\ell_{1}^{d-2}\ell_{3}^{2}$ (with
$\ell_{1}^{d-2}\ell_{3}^{2}$ as a special case).

######  Proof B.4.

By Lemma 2.13 $f$ has a generalized additive decomposition

$f=\sum_{i=1}^{m}\ell_{i}^{d-r_{i}+1}g_{i}$

with $\sum_{i=1}^{m}r_{i}=\underline{\mathsf{WR}}(f)=3$, $\deg g_{i}=r_{i}-1$,
and $\underline{\mathsf{WR}}(\ell_{i}^{d-r_{i}+1}g_{i})\leq r_{i}$.

In the case $m=3$, $r_{1}=r_{2}=r_{3}=1$ this is a Waring rank decomposition
$f=\ell_{1}^{d}+\ell_{2}^{d}+\ell_{3}^{d}$.

In the case $m=2$, we can assume $r_{1}=1$, $r_{2}=2$. The generalized
additive decomposition becomes $\ell_{1}^{d}+\ell_{2}^{d-1}\ell_{3}$, where
$\ell_{3}=g_{2}$ is a linear form.

In the case $m=1$, $r_{1}=3$ we have $f=\ell_{1}^{d-2}g_{1}$ where $g_{1}$ is
a quadratic form, and $\ell_{1}^{d-2}g_{1}$ has at most three-dimensional
space of essential variables. The quadratic form $g_{1}$ can be presented in
one of the following forms: $a\ell_{1}^{2}$, $\ell_{2}^{2}$,
$\ell_{1}\ell_{2}$, $\ell_{1}\ell_{2}+\ell_{3}^{2}$, or
$a\ell_{1}^{2}+\ell_{2}\ell_{3}$ for some linear forms $\ell_{2},\ell_{3}$
linearly independent from $\ell_{1}$.

If $d>2$, then all cases except the last are covered by the given normal
forms, and in the last case the border rank of $\ell_{1}^{d-2}g_{1}$ is at
least $4$ if $d>2$, which can be seen by computing the dimension of the second
order partial derivative space, so it cannot appear. If $d=2$ then all forms
have rank $3$ and are covered by the case
$\ell_{1}^{d}+\ell_{2}^{d}+\ell_{3}^{d}$.