Derandomization and absolute reconstruction for sums of powers of linear forms (Q820536)

In this paper, given a homogeneous polynomial \(f (x_1,\dots, x_n)\) of degree 3, the problem to decide whether it can be written as a sum of cubes of linearly independent linear forms is studied. In other words, an algorithm is given to check if, modulo a linear change of coordinates, we can re-write \(f (A(x_1, \dots, x_n)) = f (y_1,\dots, y_n) = a_1y_1^3 + a_2y_2^3 +\dots+ a_ny_n^3\), where \(\mathbf{\underline{y}} = A\mathbf{\underline{x}}\) is a linear change of coordinates and each \(a_i\in \{0, 1\}\). The given algorithm works over \(\mathbb{C}\) and is algebraic, i.e., it performs only arithmetic operations and equality tests on the coefficients of the input polynomial \(f\) (also inequalities if working over \(\mathbb{R}\)); moreover the algorithm runs in polynomial time if \(f \in \mathbb{Q}[x_1, \dots, x_n]\) and it does not make any kind of polynomial factorization. The algorithm can run in polynomial time because it just answers the question whether \(f\) can or cannot be decomposed in a sum of \(r \leq n\) sum of powers of linearly independent linear forms; it may not give the linear forms in question, whose coefficients may not be hard computable with arithmetic operations from those of \(f\) (examples are given). The algorithms is obtained by viewing the input polynomial \(f\) as symmetric tensor \(T\) of size \(n\) and order 3 and considering the 3 ``slices'' of \(T\) (i.e. symmetric \(n\times n\) matrices) and to find a simultaneous diagonalization of them; this procedure uses the factorization properties of the Hessian determinant of \(f\).