Geometric complexity theory for product-plus-power

Abstract

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 establish a tight connection between border Waring rank and the model of computation in Kumar's result. In this way, we obtain a new formulation of border Waring rank, up to a factor of the degree. We connect this new formulation to the orbit closure problem of the product-plus-power polynomial. We study this orbit closure from two directions: 1. We deborder this orbit closure and some related orbit closures, i.e., prove all points in the orbit closure have small non-border algebraic branching programs. 2. We fully implement the geometric complexity theory approach against the power sum by generalizing 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 polynomials.

This version (v3) has been accepted for publication at the "special issue on the topics of MEGA 2024" of the Journal of Symbolic Computation. Parts of v1/v2 have been published independently as "Fixed-parameter debordering of Waring rank" (DOI: 10.4230/LIPIcs.STACS.2024.30) and "Homogeneous Algebraic Complexity Theory and Algebraic Formulas" (DOI: 10.4230/LIPIcs.ITCS.2024.43)