De-bordering is the task of proving that a border complexity measure is bounded from
below, by a non-border complexity measure. This task is at the heart of understanding the
difference between Valiant’s determinant vs permanent conjecture, and Mulmuley and Sohoni’s
Geometric Complexity Theory (GCT) approach to settle the P!= NP conjecture. Currently, very
few de-bordering results are known.
In this work, we study the question of de-bordering 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 results were known to be exponential in the degree.
According to Kumar’s recent surprising result (ToCT’20), a small border Waring rank
implies that the polynomial can be approximated as a sum of a constant and a small product
of linear polynomials. We prove the converse of Kumar’s result, and in this way we de-border
Kumar’s complexity, and obtain a new formulation of border Waring rank, up to a factor of the
degree. We phrase this new formulation as the orbit closure problem of the product-plus-power
polynomial, and we successfully de-border this orbit closure. We fully implement the GCT
approach against the power sum, and we generalize the ideas of Ikenmeyer-Kandasamy
(STOC’20) to this new orbit closure. In this way, we obtain new multiplicity obstructions that
are constructed from just the symmetries of the points and representation theoretic branching
rules, rather than explicit multilinear computations.
Furthermore, we realize that the generalization of our converse of Kumar’s theorem to
square matrices gives a homogeneous formulation of Ben-Or and Cleve (SICOMP’92). This
results for the first time in a VF-complete family under homogeneous projections. We study
this approach further and obtain that a homogeneous variant of the continuant polynomial,
which was studied by Bringmann, Ikenmeyer, Zuiddam (JACM’18), is VQP-complete under
homogeneous border qp-projections. Such results are required to set up the GCT approach in
a way that avoids the no-go theorems of Bürgisser, Ikenmeyer, Panova (JAMS’19).
Added new multiplicity obstructions;
De-bordering proofs are unified;
New expository introduction and flow of the results
In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this work, we prove the converse of Kumar's result which ramifies in a surprising new formulation of Waring rank and border Waring rank. From this conclusion, we branch out into two different directions, and implement the geometric complexity theory (GCT) approach in two different settings.
In the first direction, we study the orbit closure of the product-plus-power polynomial, determine its stabilizer, and determine the properties of its boundary points. We also connect its fundamental invariant to the Alon-Tarsi conjecture on Latin squares, and prove several exponential separations between related polynomials contained in the affine closure of product-plus-product polynomials. We fully implement the GCT approach and obtain several equations for the product-plus-power polynomial from its symmetries via representation theoretic multiplicity obstructions.
In the second direction, we demonstrate that the non-commutative variant of Kumar's result is intimately connected to the constructions of Ben-Or and Cleve (SICOMP'92), and Bringmann, Ikenmeyer, Zuiddam (JACM'18), which describe algebraic formulas in terms of iterated matrix multiplication. From this we obtain that a variant of the elementary symmetric polynomial is complete for V3F, a large subclass of VF, under homogeneous border projections. In the regime of quasipolynomial complexity, our polynomial has the same power as the determinant or as arbitrary circuits, i.e., VQP. This is the first completeness result under homogeneous projections for a subclass of VBP. Such results are required to set up the GCT approach in a way that avoids the no-go theorems of B\"urgisser, Ikenmeyer, Panova (JAMS'19).
Finally, using general geometric considerations, we significantly improve the relationship between the Waring rank and the border Waring rank of polynomials. In particular, if the border Waring rank of a homogeneous polynomial $f$ is $k$, then, the Waring rank of $f$ can be at most $\exp(k) \cdot d$, while previously it was known to be $O(d^k)$.
