Polynomial Equivalence Problems for Sum of Affine Powers

A sum of affine powers is an expression of the form [f(x 1 ,...,x n ) = ∑ i =1 s α i l i (x 1 ,...,x n ) e i ] where l i is an affine form. We propose polynomial time black-box algorithms that find the decomposition with the smallest value of s for an input polynomial f . Our algorithms work in situations where s is small enough compared to the number of variables or to the exponents e i . Although quite simple, this model is a generalization of Waring decomposition. This paper extends previous work on Waring decomposition as well as our work on univariate sums of affine powers (ISSAC'17).