Pascal Koiran
email: pascal.koiran@ens-lyon.fr

Orbits of monomials and factorization into products of linear forms *

This paper is devoted to the factorization of multivariate polynomials into products of linear forms, a problem which has applications to differential algebra, to the resolution of systems of polynomial equations and to Waring decomposition (i.e., decomposition in sums of d-th powers of linear forms; this problem is also known as symmetric tensor decomposition). We provide three black box algorithms for this problem.

Our main contribution is an algorithm motivated by the application to Waring decomposition. This algorithm reduces the corresponding factorization problem to simultaenous matrix diagonalization, a standard task in linear algebra. The algorithm relies on ideas from invariant theory, and more specifically on Lie algebras.

Our second algorithm reconstructs a factorization from several bivariate projections. Our third algorithm reconstructs it from the determination of the zero set of the input polynomial, which is a union of hyperplanes.

Introduction

The main contribution of this paper is a simple algorithm which determines whether an input polynomial f (x 1 , . . . , x n ) has a factorization of the form

f (x) = l 1 (x) α 1 • • • l n (x) αn (1)
where the linear forms l i are linearly independent. The algorithm outputs such a factorization if there is one. Our algorithm works in the black box model: we assume that we have access to the input polynomial f only through a "black box" which on input (x 1 , . . . , x n ) outputs f (x 1 , . . . , x n ).

We therefore deal with a very special case of the polynomial factorization problem. As explained in Section 1.2 below, this special case already has an interesting application to Waring decomposition. The algorithm is based on (elementary) ideas of invariant theory, but is nonetheless quite simple: it essentially boils down to the simultaneous diagonalization of commuting matrices, a standard task in linear algebra. For the general problem of factorization in the black box model there is a rather involved algorithm by Kaltofen and Trager [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF], see Section 1.3 for more details. Our factorization algorithm seems to be the first to rely on ideas from invariant theory, and to reduce a multivariate polynomial factorization problem to matrix diagonalization. Let us now explain why it is natural to use invariant theory in this context.

Connection with invariant theory

Consider a field K of characteristic 0 and a polynomial f ∈ K[x 1 , . . . , x n ]. By definition, the orbit Orb(f ) of f under the action of the general linear group is the set of polynomials of the form f (A.x) where A ∈ GL n (K) is an arbitrary invertible matrix. In their Geometric Complexity Theory program [START_REF] Mulmuley | Geometric complexity theory I: An approach to the P vs. NP and related problems[END_REF][START_REF] Mulmuley | Geometric complexity theory II: Towards explicit obstructions for embeddings among class varieties[END_REF], Mulmuley and Sohoni have proposed the following approach to lower bounds in algebraic complexity: in order to prove a lower bound for a polynomial g, show that it does not belong to a suitable orbit closure Orb(f ). The case where f is the determinant polynomial is of particular interest as it allows to address the infamous "permanent versus determinant" problem. Mulmuley and Sohoni have also proposed a specific representation-theoretic approach to deal with this orbit closure problem. As it turns out, the representationtheoretic approach provably does not work [START_REF] Bürgisser | No occurrence obstructions in geometric complexity theory[END_REF]. The general approach based on orbit closure remains plausible, but has so far not produced any major lower bound result because the orbit closure of the determinant is difficult to describe. By contrast, the renewed interest in invariant theory has led to new positive results, i.e., to new polynomial time algorithms: see for instance [START_REF] Bürgisser | Deciding positivity of Littlewood-Richardson coefficients[END_REF][START_REF] Bürgisser | Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory[END_REF][START_REF] Garg | A deterministic polynomial time algorithm for non-commutative rational identity testing[END_REF][START_REF] Mulmuley | Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient[END_REF] and especially [START_REF] Kayal | Affine projections of polynomials[END_REF], which is a main inspiration for this paper.

We deal here with the simplest of all orbits, namely, the orbit of a single monomial x α 1 1 . . . x αn n , and we derive a new factorization algorithm. It is immediate from the definition that this orbit is the set of polynomials that can be factorized as in [START_REF] Baur | The complexity of partial derivatives[END_REF] with linearly independent forms. Note that the orbit closure of the monomial x 1 x 2 . . . x n is the set of polynomials that can be written as products of n linear forms (without any assumption of linear independence). This is well known in algebraic geometry, see example [START_REF] Bürgisser | Condition: The geometry of numerical algorithms[END_REF] in Section 3.1.2 of [START_REF] Landsberg | Geometry and complexity theory[END_REF] and exercise 3.1.4.2 in the same book. Moreover, equations for this orbit closure are known, see chapter 9 of [START_REF] Landsberg | Geometry and complexity theory[END_REF] for a derivation of the equations and the history of this subject. However, no factorization algorithm relying on ideas from invariant theory is currently known for arbitrary products of linear forms. We suggest this problem as a natural step before considering more complicated orbit closure problems.

Application to Waring decomposition

The factorization problem studied here is motivated mainly by an algorithm due to Neeraj Kayal (see Section 5 of [START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF]). Factorization in products of linear forms is also useful for algorithmic differential algebra [START_REF] Michael | Linear differential equations and products of linear forms[END_REF][START_REF] Mark Van Hoeij | Liouvillian solutions of linear differential equations of order three and higher[END_REF] and for the resolution of systems of algebraic equations by factorization of the U -resultant [START_REF] Cox | Using algebraic geometry[END_REF][START_REF] Kobayashi | Solving systems of algebraic equations by a general elimination method[END_REF].

Kayal's algorithm determines whether a homogeneous polynomial f of degree d in n variables can be written as the sum of n d-th powers of linearly independent forms. This algorithm is based on the fact that such a polynomial has a Hessian determinant which factors as a product of (d -2)-th powers of linearly independent forms. In [START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF] the Hessian is factorized with Kaltofen's algorithm for the factorization of polynomials given by straightline programs [START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF]. The decomposition of f as a sum of d-th powers can be recovered from this information. The algorithm presented in this note can therefore be used instead of Kaltofen's algorithm to solve the same decomposition problem.

Building on these ideas from [START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF], it was recently shown in [START_REF] García-Marco | Polynomial equivalence problems for sums of affine powers[END_REF] how to recover up to O(n 2 ) terms in a Waring decomposition 1 (and more generally in a sum of powers of affine forms with possibly different exponents in each power). The algorithm works for polynomials of degree d ≥ 5 and is based on the factorization of a "generalized Hessian" into products of linear forms. There are now up to order n 2 distinct linear forms in the factorization, and that many linear forms must of course be linearly dependent. This provides further motivation for the problem suggested at the end of Section 1.1 (namely, the extension of our algorithm to the case of linearly dependent forms). Factorization in products of dependent forms is discussed at the end of Section 1.3.

Comparison with previous factorization algorithms

As mentioned above, the algorithm for Waring decomposition in [START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF] relies on Kaltofen's factorization algorithm [START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF] which works in the arithmetic circuit (or "straight-line program") model: the input polynomial f is described by an arithmetic circuit, and the output is a list of arithmetic circuits for the irreducible factors of f together with their multiplicities.

One could instead appeal to the black-box factorization algorithm by Kaltofen and Trager [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF]. In this case, instead of factorizing a circuit for the determinant of a Hessian matrix one would use a black box for the determinant of this matrix. The algorithm from [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF] produces a black box for the irreducible factors of f given a black-box for evaluating f .

Compared to [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF][START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF] our algorithm works in a hybrid model: we use the most general of the two for the input polynomial (black box representation) but we explicitly determine the linear forms l i in (1) when they exist. 2 For the general polynomial factorization problem, it is apparently not known how to efficiently produce "small" arithmetic circuits for the irreducible factors of a polynomial f given a black-box for f . Due to the black box algorithm of [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF], this would be equivalent to producing a small arithmetic circuit for a polynomial given a black box for this polynomial.

The algorithms from [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF][START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF] project the original n-variate factorization problem to a bivariate factorization problem, solve the bivariate problem using a factorization algorithm for polynomials in dense representation, and then lift the result to a factorization of the n-variate input polynomial. It will be clear that our algorithm is based on a very different principle: instead of projecting we do linear algebra computations directly in n-dimensional space.

There is an intringuing connection between our algorithm and Gao's algorithm for the absolute factorization of bivariate polynomials [START_REF] Gao | Factoring multivariate polynomials via partial differential equations[END_REF]: they are both based on the study of certains partial differential equations. For the connection of our approach to PDEs see Lemma 5 in Section 2.3.

As explained in Section 1.2, for the application to Waring decomposition following [START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF] we can assume that the linear forms l i are independent. This assumption does not seem so natural in other applications such as differential algebra [START_REF] Michael | Linear differential equations and products of linear forms[END_REF][START_REF] Mark Van Hoeij | Liouvillian solutions of linear differential equations of order three and higher[END_REF] or the resolution of systems of polynomial equations [START_REF] Cox | Using algebraic geometry[END_REF][START_REF] Kobayashi | Solving systems of algebraic equations by a general elimination method[END_REF]. For this reason, we present in Section 5 another algorithm for factorization into products of linear forms based like [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF][START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF] on bivariate projections. Our goal in that section is to give a simpler algorithm which takes advantage of the fact that we are considering only a special case of the polynomial factorization problem. We present another simple algorithm in Section 6. This algorithm requires a univariate factorization algorithm, and the projectionbased algorithm requires a bivariate factorization algorithm (see Sections 5 and 6 for more details).

For these last two algorithms, no assumption of linear independence is needed. This is also the case for the algorithms in [START_REF] Kobayashi | Solving systems of algebraic equations by a general elimination method[END_REF][START_REF] Mark Van Hoeij | Liouvillian solutions of linear differential equations of order three and higher[END_REF]. In these two papers no complexity analysis is provided, and it is assumed in the second one that the polynomial to be factorized is squarefree. We note that the algorithm from [START_REF] Kobayashi | Solving systems of algebraic equations by a general elimination method[END_REF] bears some similarity to the algorithm that we present in Section 6: both are based on the determination of the zero set of the input polynomial, which is a union of hyperplanes.

On the choice of fields

Polynomial factorization problems come with many variations. In particular, the following choices need to be made:

(i) The input is a polynomial f ∈ K[x 1 , . . . , x n ]. What field K do we
choose as field of coefficients for f ?

(ii) What field K do we choose as field of coefficients for the output? More precisely, the output is a factorization f = g 1 . . . g k where the polynomials g i belong to K[x 1 , . . . , x n ] for some field extension K of K, and are irreducible over K. In the literature it is often (but not always) assumed that K = K.

(iii) How do we represent the field elements? Assume for instance that K = Q and that we are interested in absolute factorization, i.e., factorization over K = Q (the algebraic closure of Q). Do we insist on a symbolic representation for the coefficients of the g i 's (in this case, the coefficients would be represented as elements of an extension of Q of finite degree) or, using an embedding Q ⊆ C, are we happy to compute only numerical approximations of these coefficients?

Absolute factorization seems to be the most natural choice for this paper because of the application to Waring decomposition (this problem has been studied mostly in algebraically closed fields3 ). Moreover, for any field K if a decomposition of f of the form (1) with the l i in K[x 1 , . . . , x n ] is possible then this decomposition clearly is an absolute factorization of f . Nevertheless, we do not commit to any specific choice for (i), (ii) and (iii) except that K must be of characteristic zero. This is possible because our main algorithm is a reduction (to matrix diagonalization). Any (efficient) algorithm for this standard linear algebra task for a specific choice of (i), (ii) and (iii) will therefore yield an (efficient) factorization algorithm. We elaborate on the complexity of our reduction in Section 1.5.

Complexity of our invariant-theoretic algorithm

The black box algorithm in [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF] applies to polynomials with coefficients in a field K of characteristic 0. The only assumption on K if that a factorization algorithm for univariate polynomials in K[x] is available. This black box algorithm can therefore be thought of as a reduction from multivariate to univariate polynomial factorization. In order to evaluate precisely the complexity of this algorithm for a specific field K, one must of course take into account the complexity of the univariate factorization problem for this particular field.

Likewise, our main algorithm can be thought of as a reduction to (simultaneous) matrix diagonalization. 4 When we write that the algorithms of Section 4 run in polynomial time, we mean polynomial in n (the number of variables of the input polynomial) and d (its degree). In particular, the algorithm makes poly(n, d) calls to the black box for f . It also performs simultaneous diagonalization on n (commuting) matrices, and makes a few other auxiliary computations. The main one is the determination of the Lie algebra of f , which as explained in Section 2.3 is a linear algebra problem; a polynomial black box algorithm for it can be found in [START_REF] Kayal | Affine projections of polynomials[END_REF]. A more precise analysis of our algorithm can be found in the appendix. It suggests that the computation of the Lie algebra of f is a particularly expensive step. Improving the algorithm from [START_REF] Kayal | Affine projections of polynomials[END_REF] (or its analysis in the appendix) seems to be an interesting open problem.

If we just want to decide the existence of a suitable factorization (rather than compute it) our algorithm becomes purely algebraic, i.e., it just performs arithmetic operations (additions, multiplications and tests to zero) on the function values given by the black box for f . In particular, we do not need to factor univariate polynomials or diagonalize matrices.

Like in [START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF][START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF] our algorithm is randomized and can return a wrong answer with a small probability ǫ. This is unavoidable because homogeneous polynomials of degree d in n variables have n+d-1 d coefficients and this is bigger than any fixed polynomial in n and d if these two parameters are nonconstant. As a result, for a polynomial f of form (1) there will always be another polynomial g which agrees with f on all points queried on input f . The algorithm will therefore erroneously 5 output the same answer on these two inputs. The probability of error ǫ can be thought of as a small fixed constant, and as usual it can be made as small as desired by repeating the algorithm (or by changing the parameters in the algorithm from [START_REF] Kayal | Affine projections of polynomials[END_REF] for the computation of the Lie algebra; this is the main source of randomness in our algorithm6 ).

Organization of the paper

In Section 2 we recall some background on matrix diagonalization, simultaenous diagonalization and invariant theory. In Section 3 we give a characterization of the polynomials in the orbit of a monomial. We use this characterization in Section 4 to derive our main algorithm for factorization into products of (independent) linear forms. An algorithm based on the older idea of bivariate projections is presented in Section 5. In contrast to [START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF][START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF] this algorithm recovers a factorization of the input polynomial from several bivariate projections. Another simple algorithm is presented in Section 6. As mentioned earlier, this algorithm relies on the determination of the zero set of f . Our last two algorithms do not rely on any invariant theory and do not require any independence property for the linear forms. As pointed out at the end of Section 1.1, for factorization into products of arbitrary linear forms no algorithm that would rely on ideas from invariant theory is known at this time.

The paper ends with two appendices where we analyze the complexity of our three algorithms in more detail than in the main body. In particular, we point out in Appendix A an optimization of our invariant-theoretic algorithm for the "white box" model, in which the black box for f is implemented by an arithmetic circuit.

Background

We first recall the Schwarz-Zippel lemma [START_REF] Schwarz | Fast probabilistic algorithms for verification of polynomials identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF], a ubiquitous tool in the analysis of randomized algorithms. Lemma 1. Let f ∈ K[x 1 , . . . , x n ] be a nonzero polynomial. If a 1 , . . . , a n are drawn independently and uniformly at random from a finite set S ⊆ K then

Pr[f (a 1 , . . . , a n ) = 0] ≤ deg(f )/|S|.
A similar result with a slightly worse bound was obtained a little earlier by DeMillo and Lipton [START_REF] Demillo | A probabilistic remark on algebraic program testing[END_REF]. In the remainder of this section we recall some background on matrix diagonalization, on simultaenous diagonalization, on invariant theory and Lie algebras.

Background on matrix diagonalization

Since our main algorithm is a reduction to matrix diagonalization, it is appropriate to provide some brief background on the algorithmic solutions to this classical problem. After a first course on linear algebra, this might look like a simple task: to diagonalize a matrix M , first compute its eigenvalues. Then, for each eigenvalue λ compute a basis of Ker(M -λ.I). But this problem is more subtle than it seems at first sight.

Let us begin with numerical algorithms.

There is a vast literature on numerical methods for eigenvalue problems (see for instance [START_REF] Björck | Numerical methods in matrix computations[END_REF] and the references there). Naively, one might want to compute the eigenvalues of M by computing the roots of its characteristic polynomial χ M (λ) = det(M -λI). This approach is hardly ever used in practice for large matrices because the roots of a polynomial can be very sensitive to perturbations of its coefficients [START_REF] Wilkinson | The perfidious polynomial[END_REF]. A theoretical analysis explaining why such a bad behaviour is rather prevalent can be found in [START_REF] Bürgisser | On the condition of the zeros of characteristic polynomials[END_REF]. The QR algorithm is now considered to be the standard algorithm for computing all eigenvalues and eigenvectors of a dense matrix [START_REF] Björck | Numerical methods in matrix computations[END_REF]. It works well in practice, but a thorough understanding of this algorithm (or of any efficient and stable numerical algorithm for the computation of eigenvalue -eigenvector pairs) is still lacking, see Open Problem 2 in [START_REF] Bürgisser | Condition: The geometry of numerical algorithms[END_REF].

Let us now turn to symbolic methods. In the absence of roundoff errors, an approach based on the computation of the characteristic polynomial becomes feasible (see [START_REF] Pernet | Faster algorithms for the characteristic polynomial[END_REF] for the state of the art on the computation of this polynomial). From the knowledge of χ M we can decide whether M is diagonalizable using the following classical result from linear algebra. Proposition 2. Let K be a field of characteristic 0 and let χ M be the characteristic polynomial of a matrix M ∈ M n (K). Let P M = χ M /gcd(χ M , χ ′ M ) be the squarefree part of χ M . The matrix M is diagonalizable over K iff P M (M ) = 0.7 Moreover, in this case M is diagonalizable over K iff all the roots of P M lie in K.

Once we know that M is diagonalizable, computing the diagonal form of M symbolically requires the factorization of P M . We note that for K = Q, finding the roots of P M in Q is cheaper than the general problem of factorization in irreducible factors over Q[X] ([3], Proposition 21.22). This faster algorithm should therefore be used to diagonalize over Q. For the purpose of this paper, this is relevant for factorisation into a product of linear forms with rational coefficients.

Once we know the eigenvalues of M and their multiplicities, the last step is the computation of a transition matrix T such that T -1 M T is diagonal. For this step we refer to [START_REF] Giesbrecht | Fast algorithms for rational forms of integer matrices[END_REF][START_REF] Giesbrecht | Nearly optimal algorithms for canonical matrix forms[END_REF][START_REF] Villard | Fast parallel algorithms for matrix reduction to normal forms[END_REF]. These papers consider the more general problem of computing symbolic representations of the Jordan normal form.

The knowledge of T is particularly important for the application to factorization into product of linear forms because (as shown in Section 4) these forms can be read off directly from the transition matrix. If we just want to know whether such a factorization is possible over K or K, Proposition 2 is sufficient.

Simultaneous diagonalization

It is a well known fact of linear algebra that a family of diagonalizable matrices is simultaneously diagonalizable if and only if they pairwise commute. We will use this criterion to test whether a family of matrices A 1 , . . . , A k is simultaneously diagonalizable. If the test succeeds, we will then need to diagonalize them. Note that a transition matrix which diagonalizes A 1 may not necessarily diagonalize the other matrices (this may happen if A 1 has an eigenvalue of multiplicity larger than 1). We can nonetheless perform a simultaneous diagonalization by diagonalizing a single matrix. Indeed, as suggested in Section 6.1.1 of [START_REF] Kayal | Affine projections of polynomials[END_REF] we can diagonalize a random linear combination of the A i 's. We sketch a proof of this simple fact below. For notational simplicity we consider only the case of two matrices. The general case can be treated in a similar way. Lemma 3. Assume that M, N ∈ M n (k) are two simultaneously diagonalizable matrices. There is a set B ⊆ K of size at most n(n -1)/2 such that for any t ∈ K \ B any eigenvector of M + tN is also an eigenvector of M and N .

Proof. Since M and N are simultaneously diagonalizable we may as well work in a basis where these matrices become diagonal. We therefore assume without loss of generality that M = diag(λ 1 , . . . , λ n ) and N = diag(µ 1 , . . . , µ n ). We then have M + tN = diag(λ 1 + tµ 1 , . . . , λ n + tµ n ) for any t ∈ K. We may take for B the set of t's such that λ i + tµ i = λ j + tµ j for some pair {i, j} such that (λ i , µ i ) = (λ j , µ j ). This is indeed a set of size at most n(n -1)/2, and for t ∈B the eigenspace of M + tN associated to the eigenvalue λ i + tµ i is the intersection of the eigenspace of M associated to λ i and of the eigenspace of N associated to µ i . In particular, any eigenvector of M + tN is also an eigenvector of M and N . Proposition 4. Assume that M, N ∈ M n (k) are two simultaneously diagonalizable matrices and that t is drawn from the uniform distribution on a finite set S ⊂ K. With probability at least 1 -n(n-1)

2|S| , all the transition matrices which diagonalize M + tN also diagonalize M and N .

Proof. We show that the required property holds true for any t that does not belong to the "bad set" of Lemma 3.

For an invertible matrix T , T -1 (M + tN )T is diagonal iff all the column vectors of T are eigenvectors of M + tN . But for t ∈ B, any eigenvector of M + tN is also an eigenvector of M and N . As a result, if T -1 (M + tN )T is diagonal then T -1 M T and T -1 N T are diagonal as well.

Background on invariants and Lie algebras

In this section and in the remainder of the paper, K denotes a field of characteristic 0. The general linear group GL n acts on the polynomial ring K[x 1 , . . . , x n ] by linear change of variables: an invertible matrix A ∈ GL n sends a polynomial P (x) ∈ K[x 1 , . . . , x n ] to P (A.x). The group of invariant of P is the group of matrices A such that P (A.x) = P (x). We recall that this is a Lie group. Its Lie algebra g is a linear subspace of M n (K) defined as the tangent space of G at identity. More precisely, g is the "linear part" of the tangent space; the (affine) tangent space is I + g.

The Lie algebra associated to the group of invariants of P will be called simply "Lie algebra of P ", and we will denote it by g P . It can be explicitly computed as follows.

Lemma 5 (Claim 59 in [START_REF] Kayal | Affine projections of polynomials[END_REF]).

A matrix A = (a ij ) ∈ M n (K) belongs to the Lie algebra of P if and only if i,j∈[n] a ij x j ∂P ∂x i = 0 (2)
The elements of the Lie algebra therefore correspond to linear dependence relations between the polynomials x j ∂P ∂x i .

As an example we determine the group of invariants of monomials. Lemma 6. The group of invariants of a monomial m = x α 1 1 ....x αn n with α i ≥ 1 for all i is generated by: (i) The diagonal matrices diag(λ 1 , . . . , λ n ) with n i=1 λ α i i = 1. We denote this subgroup of GL n by T α , where α is the tuple (α 1 , . . . , α n ).

(ii) The permutation matrices which map any variable x i to a variable x π(i)

with same exponent in m (i.e., with

α i = α π(i) ).
Proof. The monomial is obviously invariant under the actions of matrices from (i) and (ii). Conversely, assume that m is invariant under the action of an invertible matrix A. By uniqueness of factorization, A must send every variable x i to the multiple of another variable, i.e., to λ i x π(i) . Moreover we must have α i = α π(i) and n i=1 λ α i i = 1, so A is in the group generated by (i) and (ii).

The Lie algebras of monomials is determined in Proposition 8. In this paper we will follow the Lie-algebraic approach from [START_REF] Kayal | Affine projections of polynomials[END_REF]. As a result we will not work directly with groups of invariants.

If two polynomials are equivalent under the action of GL n , their Lie algebras are conjugate. More precisely: Proposition 7 (Proposition 58 in [START_REF] Kayal | Affine projections of polynomials[END_REF]).

If P (x) = Q(A.x) then g P = A -1 .g Q .A
3 The orbit of a monomial Throughout the paper, m denotes a monomial x α 1 1 ....x αn n with all exponents α i ≥ 1.

Proposition 8. The Lie algebra g m of a monomial m = x α 1 1 • • • x αn n with all exponents α i ≥ 1 is the space of diagonal matrices diag(λ 1 , . . . , λ n ) such that n i=1 α i λ i = 0.
Proof. By Lemma 5, all these matrices are in g m since m satisfies the equation x i ∂m ∂x i = α i m. Conversely, if A ∈ g all off-diagonal entries a ij must vanish since the monomial x j ∂m ∂x i could not cancel with any other monomial in (2).

Remark 9. The above characterization of g m is no longer true if some exponents α i may vanish. Indeed, in this case there is no constraint on the entries in row i of a matrix in g m . However, we note for later use that in all cases, the space of diagonal matrices diag(λ 1 , . . . , λ n ) which lie in g m is defined by n i=1 α i λ i = 0.

It is easy to check by a direct computation that the Lie algebra determined in Proposition 8 is (as expected) equal to the tangent space at identity of the group T α from Lemma 6. The next result turns Proposition 8 into an equivalence.

Proposition 10. Let f ∈ K[x 1 , . . . , x n ] be a homogeneous polynomial of degree d. The two following properties are equivalent:

(i) f is a monomial which depends on all of its n variables.

(ii) The Lie algebra of f is an (n -1)-dimensional subspace of the space of diagonal matrices.

Proof. We have seen in Proposition 8 that (i) implies (ii). Conversely, for any polynomial P let us denote by d P the subspace of its Lie algebra made of diagonal matrices. By Lemma 5,

d f is the space of of matrices diag(λ 1 , . . . , λ n ) such that n i=1 λ i x i ∂f ∂x i = 0 (3)
For any monomial m, x i ∂m ∂x i is proportional to m. This implies that d f is the intersection of the d m 's for the various monomials m appearing in f since the contributions to (3) coming from different monomials cannot cancel. By Remark 9, for two distinct monomials m 1 and m 2 appearing in f the subspaces d m 1 and d m 2 are distinct since they are defined by linear forms that are not proportional (here we use the homogeneity of f ). It follows that their intersection is of dimension n -2 in contradiction with (ii). Therefore, only one monomial can appear in f . Finally, by Remark 9 all of the n variables must appear in this monomial; otherwise, g f would contain some nondiagonal matrices.

We can now characterize the Lie algebras of polynomials in the orbit of a monomial. (ii) The Lie algebras of f and m are conjugate by A, i.e., g f = A -1 .g m .A.

Theorem 11. Consider a monomial m = x α 1 1 • • • x αn n with α i ≥ 1 for all i, a homogeneous polynomial f ∈ K[x 1 , . . . , x n ] of degree d = α 1 + • • • + α
Proof. Proposition 7 shows that (i) implies (ii). For the converse, assume that g f = A -1 .g m .A and define g(x) = f (A -1 .x). By Proposition 7 we have g g = g m . It follows from Propositions 8 and 10 that g = λ.m for some nonzero constant λ. We therefore have m

(Ax) = f (x)/λ.
This characterization takes a particularly simple form in the case of equal exponents. (i) Some multiple of f belongs to the orbit of m, i.e., m(A.x) = c.f (x) for some invertible matrix A and some constant c.

(ii) The Lie algebra of f has a basis made of n -1 diagonalizable matrices of trace zero which pairwise commute.

Moreover, f is a constant multiple of m if and only its Lie algebra is the space of diagonal matrices of trace zero.

Proof. Let f be in the orbit of m. By Proposition 7, in order to establish (ii) for f we just need to check that this property is true for m. This is the case since (by Proposition 8) the Lie algebra of m is the space of diagonal matrices of trace 0. Conversely, assume that (ii) holds for f . It is a well known fact of linear algebra that a family of diagonalizable matrices is simultaneously diagonalizable if and only if they pairwise commute. By simultaneously diagonalizing the n -1 matrices in the basis of g f we find that this Lie algebra is conjugate to g m (which as we just saw is the space of diagonal matrices of trace 0). Hence some constant multiple of f is in the orbit of m by Theorem 11.

As to the second part of the theorem, we have already seen that g m is the space of diagonal matrices of trace zero. Conversely, if g f = g m we can apply Theorem 11 with A = Id and it follows that f is a constant multiple of m.

Note that if (ii) holds for some basis of g f this property holds for all bases. Also, if K is algebraically closed we can always take c = 1 in Theorems 11 and 12.

Factorization into products of independent forms

By definition, the orbit of a monomial m αn where the linear forms l i are linearly independent. We will exploit the characterization of orbits obtained in Section 3 to factor such polynomials. We assume that we have access to a black-box for f . We begin with the simpler case of equal exponents. Note that this is exactly what is needed in Section 5 of [START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF].

= x α 1 1 • • • x αn n contains the polyno- mial f if an only if f can be written as f (x) = l 1 (x) α 1 • • • l n (x)

Equal exponents

In this section we describe an algorithm which takes as input a homogeneous polynomial

f ∈ K[x 1 , . . . , x n ] of degree d = nα, determines if it can be expressed as f = (l 1 • • • l n ) α
where the l i 's are linearly independent forms and finds such a factorization if it exists. In the first three steps of the following algorithm we decide whether such a factorization exists over K, and in the last two we actually compute the factorization.

1. Compute a basis B 1 , . . . , B k of the Lie algebra of f . 2. Reject if k = n -1, i.e., if the Lie algebra is not of dimension n -1.

3. Check that the matrices B 1 , . . . , B n-1 commute, are all diagonalizable over K and of trace zero. If this is the case, declare that f can be factored as f = (l 1 • • • l n ) α where the l i 's are linearly independent forms. Otherwise, reject.

4. Perform a simultaneous diagonalization of the B i 's, i.e., find an invertible matrix A such that the n -1 matrices AB i A -1 are diagonal.

At the previous step we have found a matrix

A such that f (A -1 x) = λ.m(x) where m is the monomial (x 1 • • • x n ) α .
We therefore have f (x) = λ.m(Ax) and we output this factorization.

Note that this algorithm outputs a factorization of the form

f = λ.(l 1 • • • l n ) α .
We can of course obtain λ = 1 by an appropriate scaling of the l i 's if desired.

Theorem 13. The above algorithm runs in polynomial time and determines whether f can be written as f = (l 1 • • • l n ) α where the forms l i are linearly independent. It ouputs such a factorization if there is one.

Proof. The correctness of the algorithm follows from Theorem 12. In particular, the equivalence of properties (i) and (ii) in Theorem 12 shows that the algorithm will make a correct decision on the existence of a suitable factorization at step 3. If this step succeeds, the simultaneous diagonalization at step 4 is possible since (as already pointed out Section 2.2 and in the proof of Theorem 12) simultaneous diagonalization is always possible for a family of matrices which are diagonalizable and pairwise commute. By Proposition 7, the Lie algebra of f (A -1 x) is the space of diagonal matrices of trace 0. This implies that f (A -1 x) is a constant multiple of m by the last part of Theorem 12, and justifies the last step of the algorithm.

Let us now explain how to implement the 5 steps. A randomized8 black box algorithm for Step 1 based on Lemma 5 can be found in Lemma 22 of [START_REF] Kayal | Affine projections of polynomials[END_REF]. Steps 2 and 3 are mostly routine (use Proposition 2 to check that the B i 's are diagonalizable). Step 4 (simultaenous diagonalization of commuting matrices) is also a standard linear alegbra computation. One suggestion from Section 6.1.1 of [START_REF] Kayal | Affine projections of polynomials[END_REF] is to diagonalize a random linear combination of the B i 's (see Section 2.2 for more details). That matrix can be diagonalized as explained in Section 2.1. Finally, the scaling factor λ at step 5 can be computed by one call to the black box for f . Remark 14. We have presented the above algorithm with a view towards factorisation over K, but it is readily adapted to factorization over some intermediate field K ⊆ K ⊆ K. Note in particular that to decide the existence of a factorization at step 3, we would need to check that the matrices B i are diagonalizable over K. As recalled in Proposition 2, this requires an algorithm that decides whether the characteristic polynomial of a matrix has all its roots in K. In the case K = K, if we stop at step 3 we obtain a purely algebraic algorithm for deciding the existence of a suitable factorization (in particular, we do not need to factorize univariate polynomials or diagonalize matrices).

General case

In this section we describe an algorithm which takes as input a homogeneous polynomial f of degree αn where the l i 's are linearly independent forms, and finds such a factorization if it exists. Note that the values of the exponents α i are determined by the algorithm (they are not given as input). We assume that α i ≥ 1 for all i. The number of distinct factors is therefore equal to the number of variables of f . The case where there are more factors than variables is related to orbit closure and we do not treat it in this section. Let us explain briefly explain how to handle the case where some exponents α i may be 0, i.e., the case where the number r of distinct factors is smaller than the number of variables. In this case, f has only r "essential variables", i.e., it is possible to make a linear (invertible) change of variables after which f depends only on r variables. This puts us therefore in the situation where the number of distinct factors is equal to the number of variables. The number of essential variables and the corresponding change of variables can be computed with Kayal's algorithm9 [START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF], see also [START_REF] Carlini | Reducing the number of variables of a polynomial[END_REF].

d = α 1 +• • •+α n in n variables, determines if it can be expressed as f (x) = l 1 (x) α 1 • • • l n (x)
We can now present our factorization algorithm. Like in the case of equal exponents, the existence of a suitable factorization is decided in the first three steps.

1. Compute a basis B 1 , . . . , B k of the Lie algebra of f . 2. Reject if k = n -1, i.e., if the Lie algebra is not of dimension n -1.

3. Check that the matrices B 1 , . . . , B n-1 commute and are all diagonalizable over K. If this is not the case, reject. Otherwise, declare the existence of a factorization

f (x) = l 1 (x) α 1 • • • l n (x)
αn where the linear forms l i are linearly independent and α i ≥ 1 (the l i and α i will be determined in the last 3 steps of the algorithm).

4. Perform a simultaneous diagonalization of the B i 's, i.e., find an invertible matrix A such that the n -1 matrices AB i A -1 are diagonal.

5. At the previous step we have found a matrix A such that g(x) = f (A -1 x) has a Lie algebra g g which is an (n -1)-dimensional subspace of the space of diagonal matrices. Then we compute the orthogonal of g g , i.e., we find a vector α = (α 1 , . . . , α n ) such g g is the space of matrices diag(λ 1 , . . . , λ n ) satisfying n i=1 α i λ i = 0. We normalize α so that n i=1 α i = d.

6. We must have g(x) = λ.m where λ ∈ K * and m is the monomial

x α 1 1 • • • x αn n (
in particular, α must be a vector with integral entries). We therefore have f (x) = λ.m(Ax) and we output this factorization.

Again, this algorithm outputs a factorization of the form f αn and we can obtain λ = 1 by an appropriate scaling of the l i 's.

(x) = λ.l 1 (x) α 1 • • • l n (x)
Theorem 15. The above algorithm runs in polynomial time and determines whether f can be written as αn where the forms l i are linearly independent and α i ≥ 1 for all i. It ouputs such a factorization if there is one.

f (x) = l 1 (x) α 1 • • • l n (x)
Proof. The two main steps (finding a basis of g f and simultaneous diagonalization) can be implemented efficiently as in the case of equal exponents, so we'll focus on the correctness of the algorithm.

Assume first that f can be written as βn where the L i 's are linearly independent forms and β i ≥ 1 for all i. Then f is in the orbit of the monomial M = x β 1 1 • • • x βn n , so g f and g M are conjugate by Proposition 7. By Proposition 8, g M is the space of diagonal matrices diag(λ 1 , . . . , λ n ) such that n i=1 β i λ i = 0. These two facts imply that the first 4 steps of the algorithm will succeed. The polynomial g(x) = f (A -1 x) defined at step 5 has a Lie algebra which is an (n -1)-dimensional subspace of the space of diagonal matrices. By Proposition 10, g must therefore be a monomial. Proposition 8 implies that the tuple of exponents of g is correctly determined at step 5, so that we indeed have g = λ.m at step 6. Note that m may differ from M by a permutation of indices, and likewise the factorization output by the algorithm may differ from f

f (x) = L 1 (x) β 1 • • • L n (x)
(x) = L 1 (x) β 1 • • • L n (x)
βn by a permutation of indices and the scaling of linear forms.

Conversely, if the 3 first steps of the algorithm succeed the B i must be simultaneously diagonalizable and it follows again from Proposition 10 that the polynomial g defined at step 5 satisfies g = λ.m where λ ∈ K * and m is some monomial

x α 1 1 • • • x αn n .
In particular, Proposition 10 guarantees that the exponents α i are all positive. The algorithm will then output at step 6 a correct factorization of f . Like in Section 4.1 we have presented our algorithm with a view towards factorisation over K, but it is readily adapted to factorization over some intermediate field K ⊆ K ⊆ K as explained in Remark 14.

In the above algorithm we need to perform the simultaneous diagonalization at step 4 before computing the exponents α i . In the remainder of this section we show that the exponents can be computed without step 4. The corresponding algorithm relies on Proposition 16 below. First, we recall that for any set of matrices S ⊆ M n (K) the centralizer of S is the set of matrices that commute with all matrices of S. It is a linear subspace of M n (K) and we denote it by C(S).

Proposition 16. Consider a monomial m = x α 1 1 • • • x αn n with α i ≥ 1
for all i, and a polynomial f in the orbit of m.

The centralizer C(g f ) of the Lie algebra of f is of dimension n. Moreover, there is a unique H in C(g f ) such that Tr H = d and Tr(HM ) = 0 for all M ∈ g f . The matrix H is diagonalizable, its eigenvalues are (α 1 , . . . , α n ) and C(g f ) = g f ⊕ Span(H).

Note that the case α 1 = . . . = α n = 1 corresponds to H = Id. The condition Tr(HM ) = 0 for all M ∈ g f is an analogue of the trace zero condition in property (ii) of Theorem 12.

Proof. We first consider the case f = m. By Proposition 8, g m is the set of diagonal matrices diag(λ 1 , . . . , λ n ) such that i α i λ i = 0.

For 1 ≤ i = j ≤ n, let H ij denote the set of matrices diag(λ 1 , . . . , λ n ) such that λ i = λ j . Consider the set h of diagonal matrices. The hyperplane g m of h is equal to no hyperplane of the form H ij . Since the field is infinite, g m is not contained in the union of the hyperplanes H ij . Then g m contains a matrix M 0 with pairwise distinct eigenvalues. Then

h ⊆ C(g m ) ⊆ C(M 0 ) ⊆ h, and C(g m ) = h. Set H 0 = diag(α 1 , . . . , α n ) ∈ h. It is clear that Tr(H 0 ) = d and Tr(H 0 M ) = 0 for any M ∈ g m . Conversely, let H = diag(β 1 , . . . , β n ) ∈ h and M = diag(λ 1 , . . . , λ n ) ∈ g m . Then Tr(HM ) = i β i λ i .
Since g m is the hyperplane of h defined by i α i λ i = 0, Tr(HM ) = 0, for any M ∈ g m if and only if (β 1 , . . . , β n ) is proportional to (α 1 , . . . , α n ). If moreover Tr(H) = d, we get H = H 0 . This proves the unicity. Morever, Tr(H 2 0 ) = i α 2 i = 0 and H 0 ∈ g m , since the field has characteristic zero. Then, since g m is an hyperplane of h, g m ⊕ KH 0 = C(g m ) = h.

Consider now a point f in the orbit of m. Let A be an invertible matrix such that f = A.m = m • A -1 . Then, by Proposition 7, g f = Ag m A -1 and C(g f ) = AC(g m )A -1 . One easily checks that H satisfies the proposition for f if and only if A -1 HA satisfies it for m. With the first part, this proves the existence and unicity of H. This proposition yields the following algorithm for the computation of the exponents α 1 , . . . , α n . We assume that the first three steps of the algorithm of Theorem 15 have executed successfully. Note that the system constructed at step (a) is overdetermined: it has Θ(n 3 ) equations but only n 2 unknowns. Proposition 16 guarantees that the system has a unique solution H, and that the eigenvalues of H are the exponents α 1 , . . . , α n . We refer to Section 2.1 for the computation of eigenvalues at step (b).

Bivariate projections

In this section we present a probabilistic black box algorithm that finds a factorization into products of linear forms whenever this is possible, without any assumption of linear independence of the linear forms. As explained before this can be done with the algorithm by Kaltofen and Trager [START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF].

We assume that the input polynomial is in K[x 1 , . . . , x n ] where K is infinite. In contrast to Section 4, we do not need to assume that K is of characteristic 0. The hypothesis that K is infinite is needed because the algorithm draws random elements from "large enough" but finite subsets S ⊆ K. The algorithm also applies to a finite field if K is large enough for this, or if we can draw points from a large enough field extension.

As in [START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF][START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF] we rely on bivariate projections but we present a simplified algorithm which takes advantage of the fact that we are trying to factor polynomials of a special form (another simple algorithm based on a different idea is presented in the next section). In these two papers, a factorization of the input polynomial is recovered from a single bivariate projection (see Step R in [START_REF] Kaltofen | Factorization of polynomials given by straight-line programs[END_REF] and Step 1 in [21]10 ). By contrast, we will recover the solution to our problem from several projections as in e.g. [START_REF] García-Marco | Polynomial equivalence problems for sums of affine powers[END_REF][START_REF] Kayal | Affine projections of polynomials[END_REF]. A recurring difficulty with projection-based algorithms is that when we try to "lift" the solutions of problems on a lower-dimensional space to a solution of the original problem, the lift may not be unique. We first present in Section 5.1 a solution under an additional assumption which guarantees uniqueness of the lift. We then lift (as it were) this assumption in Section 5.2.

We assume that a polynomial time factorization algorithm for polynomials in K[x, y] is available. It is explained in [START_REF] Kaltofen | Polynomial-time reductions from multivariate to bi-and univariate integral polynomial factorization[END_REF] how to obtain such an algorithm from a univariate factorization algorithm for the field of rational numbers, and more generally for number fields and finite fields. In the case of absolute factorization, polynomial time algoritms were first given by Gao [START_REF] Gao | Factoring multivariate polynomials via partial differential equations[END_REF] and by Chèze and Lecerf [START_REF] Chèze | Lifting and recombination techniques for absolute factorization[END_REF]. The complexity of the latter algorithm was analyzed in [START_REF] Chèze | Lifting and recombination techniques for absolute factorization[END_REF] for the algebraic (unit cost) model of computation. The complexity of the former algorithm was analyzed in [START_REF] Gao | Factoring multivariate polynomials via partial differential equations[END_REF] for an input polynomial with coefficients in a finite field F q . 11Without loss of generality, we'll assume that our input f is in K[x 1 , . . . , x n ] with n ≥ 4. Indeed, if there are only 3 variables we can set g(x 1 , x 2 ) = f (x 1 , x 2 , 1), use the bivariate algorithm to factor g as a product of affine forms, and homogonenize the result to obtain a factorization of f . Note that the homogenization step includes a multiplication by x deg(f )-deg(g) 3 .

A uniqueness condition

In this section we assume that our input f (x 1 , . . . , x n ) can be factorized as

f (x) = λ.l 1 (x) α 1 • • • l k (x) α k (4)
where the linear form l i is not proportional to l j if i = j, and λ is a nonzero constant. We would like to recover λ, the exponents α i 's and the l i 's (note that each linear forms is defined only up to a constant). Write l i (x) = n j=1 l ij x j . In order to guarantee "uniqueness of the lift" we make the following temporary assumption:

(*) The k coefficients l i1 are distinct and nonzero and l in = 1 for all i.

The algorithm is as follows.

1. For j = 2, . . . , n -1 define g j (x 1 , x j ) = f • π j where the projection π j sends variable x n to the constant 1, leaves x 1 and x j unchanged and sets all other variables to 0. Compute the dense representation of the g j 's by interpolation.

2. Using the bivariate factorization algorithm, write each g j as

g j (x 1 , x j ) = λ. k i=1 (a ij x 1 + b ij x j + 1) β ij .
3. At the beginning of this step, each of the n -2 tuples (a 1j , . . . , a kj ) is a permutation of the tuple (l 11 , . . . , l k1 ). We reorder the factors in the factorizations of the g j from step 2 to make sure that the n -2 tuples are identical (i.e., its elements always appear in the same order).

After reordering, the n -2 tuples of exponents (β 1j , . . . , β kj ) will also become identical. We therefore obtain factorizations of the form:

g j (x 1 , x j ) = λ. k i=1 (a i x 1 + c ij x j + 1) γ i .
4. We output the factorization:

f (x 1 , . . . , x n ) = λ. k i=1 (a i x 1 + c i2 x 2 + • • • + c i,n-1 x n-1 + x n ) γ i .
The main issue regarding the correctness of this algorithm is to make sure that we have correctly combined the factors of the g j 's to obtain the factors of f . This is established in the next proposition. For an example of what can go wrong without assumption (*) consider the following two polynomials:

f 1 = (x 1 + x 2 + x 3 + x 4 )(x 1 + 2x 2 + 2x 3 + x 4 )
and

f 2 = (x 1 + x 2 + 2x 3 + x 4 )(x 1 + 2x 2 + x 3 + x 4 ).
At step 1 of the algorithm, these two polynomials are mapped to the same pair of bivariate polynomials:

g 2 = (x 1 + x 2 + 1)(x 1 + 2x 2 + 1), g 3 = (x 1 + x 3 + 1)(x 1 + 2x 3 + 1)
and there is no unique way of lifting {g 2 , g 3 } to an input polynomial. Another difficulty is that the factorization pattern of f (i.e., the set of exponents {α 1 , . . . , α k }) could change after projection, for instance

f = (x 1 + x 2 + x 3 + x 4 )(x 1 + 2x 2 + x 3 + x 4 )
is mapped to

g 2 = (x 1 + x 2 + 1)(x 1 + 2x 2 + 1), g 3 = (x 1 + x 3 + 1) 2 .
Proposition 17. The above algorithm correctly factorizes the polynomials of form ( 4) that satisfy assumption (*).

Proof. Since l in = 1 for all i we have λ = f (0, • • • , 0, 1) = g j (0, • • • , 0) for all j = 2, . . . , n -1. Each g j admits the factorization:

g j (x 1 , x j ) = λ. k i=1 (l i1 x 1 + l ij x j + 1) α j (5)
All these polynomials therefore have same factorization pattern as f (note in particular that the affine forms l i1 x 1 + l ij x j + 1 are nonconstant since l i1 = 0; and two of these forms cannot be proportional since the l i1 are distinct). It follows that the factorization of g j discovered by the algorithm at step 2 is identical to (5) up to a permutation, i.e., we have a ij = l σ j (i)1 , b ij = l σ j (i)j and β ij = α σ j (i) for some permutation σ j ∈ S k . Since the l i1 are distinct, after reordering at step 3 these n -2 permutations become identical, i.e., we have a i = l σ(i)1 , c ij = l σ(i)j and γ i = α σ(i) for some permutation σ. Finally, at step 4 the algorithm outputs the correct factorization

f (x) = λ. k i=1 l σ(i) (x) α σ(i) .

General case

In this section we present a black box algorithm that factors a homogeneous polynomial f ∈ K[x 1 , . . . , x n ] of degree d into a product of d linear forms whenever this is possible, thereby lifting assumption (*) from Section 5.1. The algorithm is as follows.

1. Set g(x) = f (A.x) where A ∈ M n (K) is a random matrix.

2. Attempt to factor g with the algorithm of Section 5.1. If this fails, reject f . In case of success, let g ′ (x) = λ.l 1 (x) α 1 • • • l k (x) α k be the factorization output by this algorithm.

3. Check that f (x) = g ′ (A -1 .x) and output the corresponding factorization.

The random matrix at step 1 is constructed by drawing its entries independently at random from some large enough finite set S ⊆ K. The point of this random change of variables is that g will satisfy assumption (*) of Section 5.1 with high probability if f can be factored as a product of linear forms. The (quite standard) arguments needed to estimate the probability of success are presented in the proof of Theorem 18. Note also that by the Schwarz-Zippel lemma, A will be invertible with high probability.

At step 2 we need a black-box for g. Such a black box is easily obtained by composing the black box for f with the map x → A.x.

At step 3, we check the polynomial identity f (x) = g ′ (A -1 .x) by evaluating the left and right-hand sides at one random point.

Theorem 18. The above algorithm runs in polynomial time and determines whether f can be written as a product of linear forms. It outputs such a factorization if there is one.

Proof. By the Schwarz-Zippel lemma, any factorization of f output at step 3 will be correct with high probability. So we only need to prove the converse: if f can be factored as a product of linear forms, the algorithm finds a correct factorization with high probability. Suppose therefore that

f (x) = L 1 (x) α 1 • • • L k (x) α k
where no two linear forms L i , L j in this expression are proportional. Then g(x) = f (A.x) can be written as

g(x) = ℓ 1 (x) α 1 • • • ℓ k (x) α k
where ℓ i (x) = L i (A.x). If A is invertible, the linear forms in this expression will not be proportional. The coefficients of these linear forms are given by the expression:

ℓ ij = n p=1 L ip A pj . ( 6
)
If the entries A pj of A are drawn from a set S ⊂ K, ℓ in = 0 with probability at most 1/|S| since L i ≡0. These n coefficients will all be nonzero with probability at least 1 -n/|S|; in this case we can factor out λ = k i=1 ℓ α i in to make sure that the coefficient of x n in each linear form is equal to 1 as required by assumption (*). This gives the factorization

g(x) = λ.l 1 (x) α 1 • • • l k (x) α k
where l i (x) = ℓ i (x)/ℓ in . The same argument as for ℓ in shows that ℓ i1 and therefore l i1 will be nonzero with high probability. To take care of assumption (*), it remains to check that the l i1 will be distinct with high probability.

The condition l i1 = l j1 is equivalent to ℓ i1 ℓ jn -ℓ j1 ℓ in = 0. By ( 6) this expression can be viewed as a quadratic form in the entries of A. From unique factorization and the hypothesis that the linear forms L i , L j are not proportional it follows that this quadratic form is not identically 0. We conclude again that it will be nonzero with high probability by the Schwarz-Zippel lemma.

We have established that g(x) = f (A.x) satisfies (*) with high probability. In this case, by Proposition 17 the factorization of g at step 2 of the algorithm and the verification of the polynomial identity at step 3 will also succeed.

Identifying the hyperplanes and their multiplicities

If a polynomial f can be factored as a product of linear forms, its zero set Z(f ) is a union of (homogeneous) hyperplanes. In this section we present an algorithm based on this simple geometric fact. We can identify each hyperplane in Z(f ) by finding n -1 nonzero points that lie on it. Assume that f can be written as

f (x) = λ.l 1 (x) α 1 • • • l k (x) α k
where the linear forms l i are not proportional. We will need a total of k(n-1) points on Z(f ) to identify the k hyperplanes. Our algorithm begins with the determination of these k(n -1) points.

1. Pick a random point a ∈ K n and n -1 random vectors v 1 , . . . , v n-1 in K n (or representatives of points in P(K n ) to be more precise).

Let ∆ i be the line of direction v i going through a. Compute the intersection ∆ i ∩ Z(f ) for i = 1, . . . , n -1.

2. Output the k(n -1) intersection points a 1 , . . . , a k(n-1) found at step 1.

In the sequel, we assume that f (a) = 0. This holds with high probability by the Schwarz-Zippel lemma.

At step 1 we compute ∆ i ∩ Z(f ) by finding the roots of the univariate polynomial g(t) = f (a + tv i ). We obtain one point on each hyperplane Z(l 1 ), . . . , Z(l k ) except if v i belongs to one of these hyperplanes. This can happen only with negligible probability. Moreover, these k points are distinct except if ∆ i goes through the intersection of two of these hyperplanes. Again, this happens with negligible probability (we explain in the proof of Theorem 19 how to obtain explicit bounds on the probabilities of these bad events). Since a ∈ Z(f ), with high probability we find a total of k(n -1) distinct points as claimed at step 2. Moreover, each hyperplane Z(l i ) contains exactly n -1 points. Note that at step 1 we have also determined k if this parameter was not already known in advance.

At the next stage of our algorithm we determine the k hyperplanes. We first determine the hyperplane going through a 1 as follows:

3. Find n -2 points b 2 , . . . , b n-1 in the set {a 2 , . . . , a k(n-1) } such that each line (a 1 b j ) is included in Z(f ).

Output the linear subspace

H 1 = Span(a 1 , b 2 , . . . , b n-1 )
.

At step 3 we can find out whether a line (a 1 a j ) is included in Z(f ) by checking that the univariate polynomial g(t) = f (ta 1 + (1 -t)a j ) is identically 0. This can be done deterministically with k -1 calls to the black box for f (indeed, if g ≡0 this polynomial has at most k roots, and we already know that g(0) = g(1) = 0). Alternatively, we can perform a single call to the black box by evaluating g at a random point. Assume for instance that Z(l 1 ) is the hyperplane going through a 1 . In the analysis of the first two steps we saw that (with high probability) a 1 does not lie on any other Z(l j ), and that exactly n -2 points b 2 , . . . , b n-1 in {a 2 , . . . , a k(n-1) } lie on Z(l 1 ). The algorithm identifies these points at step 3 (we will find exactly one point on each line ∆ i ). It follows that the subspace H 1 output at step 4 is included in Z(l 1 ). To conclude that H 1 = Z(l 1 ), it remains to show that H 1 is of dimension n -1. Assume without loss of generality that {a 1 } = ∆ 1 ∩ Z(l 1 ) and {b j } = ∆ j ∩ Z(l 1 ) for j = 2, . . . , n -1.

Then a 1 = a + t 1 v 1 and b j = a + t j v j for j = 2, . . . , n -1. Here v 1 , . . . , v n-1 are the directions chosen at step 1, and t 1 , . . . , t n-1 are appropriate nonzero scalars. With high probability, the n vectors a, v 1 , . . . , v n-1 are linearly independent. In this case, the family a + t 1 v 1 , . . . , a + t n-1 v n-1 is of rank n -1 as desired.

The above analysis shows that steps 3 and 4 identify H 1 = Z(l 1 ) with high probability. The k -1 remaining hyperplanes can be identified by repeating this procedure. For instance, to determine the second hyperplane H 2 we will remove the points a 1 , b 2 , . . . , b n-1 (which lie on H 1 ) from the set {a 1 , . . . , a k(n-1) } and we will determine the hyperplane going through the first of the (k -1)(n -1) remaining points.

In the next stage of the algorithm we determine the multiplicities α i of the linear forms l i . This is done as follows:

5. Consider again the random point a and the random vector v 1 drawn at step 1. We have already computed the intersection points with H 1 = Z(l 1 ), . . . , H k = Z(l k ) of the line ∆ 1 of direction v 1 going through a.

Recall that this was done by computing the roots t 1 , . . . , t k of the univariate polynomial g(t) = f (a + tv 1 ).

Let us assume without loss of generality that these roots are ordered so that {a

+ t 1 v 1 } = H 1 ∩ ∆ 1 , . . . , {a + t k v 1 } = H k ∩ ∆ 1 . Now we
compute the multiplicities α 1 , . . . , α k of t 1 , . . . , t k as roots of g and we output these multiplicities.

If f (x) = l 1 (x) α 1 • • • l k (x) α k
, the multiplicities of the roots of g are indeed equal to α 1 , . . . , α k except if ∆ 1 goes through the intersection of two of the hyperplanes H 1 , . . . , H k . As already pointed out in the analysis of the first two steps, this happens only with negligible probability. Note that there is nothing special about ∆ 1 at step 5: we could have used a new random line ∆ instead.

The final stage of the algorithm is a normalization step.

6. At the beginning of this step we have determined linear forms l i and multiplicities

α i so that f (x) = λ.l 1 (x) α 1 • • • l k (x) α k for some con- stant λ.
We determine λ by one call to the black box for f at a point where the l i do not vanish (for instance, at a random point).

We have obtained the following result.

Theorem 19. Let f ∈ K[x 1 , . . . , x n ] be a polynomial of degree d that ad- mits a factorization f (x) = λ.l 1 (x) α 1 • • • l k (x) α k over K,
where no two linear forms l i are proportional. The above algorithm determines such a factorization with high probability, and the number of calls to the black box for f is polynomial in n and d. Assume moreover that K = Q and that a factorization of f where l i ∈ Q[x 1 , . . . , x n ] is possible. If the coefficients of these linear forms are of bit size at most s then all calls to the black box are made at rational points of bit size polynomial in n, d and s.

Proof. The correctness of the algorithm follows from the above analysis. Let us focus therefore on the case K = Q of the theorem. This result relies on a standard application of the Schwarz-Zippel lemma. More precisely, as explained in the analysis of the first two steps, we want to pick a random point a such that f (a) = 0 and random vectors v 1 , . . . , v n-1 that do not belong to any of the hyperplanes. Moreover, the line ∆ i defined at step 1 should not go through the intersection of two hyperplanes. Let us pick the coordinates of a and of the v i independently at random from a finite set S ⊆ Q. By the Schwarz-Zippel lemma, Pr[f (a) = 0] ≤ k/|S| ≤ d/|S|; and for any linear form l j we have Pr[l j (v i ) = 0] ≤ 1/|S|. As to ∆ i , let us bound for instance the probability of going through the intersection of the first two hyperplanes. Since ∆ i is the line of direction v i going through a, it suffices to make sure that l 2 (a)l 1 (v i )-l 1 (a)l 2 (v i ) = 0. By the Schwarz-Zippel lemma this happens with probability at least 1 -2/|S|.

Another constraint arising in the analysis of steps 3 and 4 is that a, v 1 , . . . , v n-1 should be linearly independent. By the Schwarz-Zippel lemma, the corresponding determinant vanishes with probability at most n/|S|. Note that the bounds obtained so far are independent of s. This parameter comes into play when we compute the intersections ∆ i ∩ Z(f ) at step 1. Recall that we do this by finding the roots of the univariate polynomial g(t) = f (a + tv i ). The roots are:

t 1 = -l 1 (a)/l 1 (v i ), . . . , t k = -l k (a)/l k (v i ).
Then at step 3 we call the black box at points belonging to lines going through two of the k(n -1) intersections points found at step 1.

The algorithm presented in this section relies on a simple and appealing geometric picture, but it suffers from a drawback compared to the algorithms of sections 4 and 5:

Remark 20. Assume that K = Q. The above algorithm may need to call the black box for f at algebraic (non rational) points in the case where the linear forms l i do not have rational coefficients. This is due to the fact that we call the black box at points that lie on the hyperplanes l i = 0.

By contrast, the algorithms of sections 4 and 5 always call the black box at integer points even when f has algebraic (non rational) coefficients. To see why this is true for the algorithm of Section 5, note that the main use of the black box is for performing bivariate interpolation. In Section 4, the black box is used only for the computation of the Lie algebra of f following Lemma 22 of [START_REF] Kayal | Affine projections of polynomials[END_REF]. More details on the black box calls performed by our three algorithms can be found in the appendix.

A Appendix: Cost of calls to the black box

In this section we compare the number of calls to the black box made by our three algorithms (for the cost of other operations, see Appendix B). A more thorough analysis would also take into account the size of points at which the black box is queried (for this, Remark 20 would become especially relevant).

It turns out that the hyperplane algorithm of Section 6 makes fewer calls to the black box than the other two. We also analyze these algorithms in the "white box" model, where we have access to an arithmetic circuit computing the input polynomial f . In that model, the cost of function evaluations becomes smallest for the Lie-theoretic algorithm of Section 4.

A.1 Lie-theoretic algorithm

In Section 4, the black box is used only for the computation of the Lie algebra of f . By Lemma 5, this boils down to the determination of linear dependence relations between the n 2 polynomials x j ∂f ∂x i . The general problem of finding linear dependence relations between polynomials given by black box access is solved by the following lemma (see appendix A1 of [START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF] for a proof).

Lemma 21 (Lemma 14 in [START_REF] Kayal | Affine projections of polynomials[END_REF]). Let (f 1 (x), f 2 (x), . . . , f m (x)) be an m-tuple of n-variate polynomials. Let P = {a i ; 1 ≤ i ≤ m} be a set of m points in K n . Consider the m × m matrix M = (f j (a i )) 1≤i,j≤m .

With high probability over a random choice of P, the nullspace of M consists precisely of all the vectors (α 1 , . . . , α m ) ∈ K m such that

m i=1 α i f i (x) ≡ 0.
We therefore need to evaluate the n polynomials ∂f /∂x i at n 2 random points. Note however that we have only access to a black box for f rather than for its partial derivatives. As is well known, it is easy to take care of this issue by polynomial interpolation. Suppose indeed that we wish to evaluate ∂f /∂x i at a point a. Then we evaluate f at d + 1 = deg(f ) + 1 points on the line ∆ which goes through a and is parallel to the i-th basis vector. From these d + 1 values we can recover f and ∂f /∂x i on ∆. We conclude that the Lie-theoretic algorithm performs O(dn 3 ) calls to the black box for f . These n 3 polynomial interpolations also have a cost in terms of arithmetic operations, but it is relatively small. Suppose indeed that we wish to compute ∂f /∂x 1 at a point a = (a 1 , . . . , a n ) with a 1 = 0. Consider the univariate polynomial g(x) = f (a 1 x, a 2 , . . . , a n ). It suffices to compute g ′ (1) = a 1 ∂f /∂x 1 (a). We can obtain g ′ (1) as a fixed linear combination of g(0), g(1), . . . , g(d). One polynomial interpolation therefore requires one linear combination of values of f and one division (by a 1 ). We conclude for use in Appendix B.1 that the arithmetic cost of these n 3 interpolations is O(n 3 d).

The Lie-theoretic algorithm admits an interesting optimization when the black box is implemented by an arithmetic circuit. Suppose indeed that we have access to an arithmetic circuit of size s computing f (this is the socalled "white box" model). The above analysis translates immediately into an arithmetic cost of order sdn 3 for the evaluation of the partial derivatives of f at our n 2 random points. But one can do much better thanks to the classical result by Baur and Strassen [START_REF] Baur | The complexity of partial derivatives[END_REF] (see also [START_REF] Morgenstern | How to compute fast a function and all its derivatives: A variation on the theorem of Baur-Strassen[END_REF]), which shows that the n partial derivatives of an arithmetic circuit of size s can be evaluated by a single arithmetic circuit of size O(s). This reduces the cost of evaluations from O(sdn 3 ) to O(sn 2 ). Moreover, the arithmetic cost of interpolations drops from O(n 3 d) to 0 since we do not perform any interpolation in the white box model.

A.2 Bivariate projections

The algorithm of Section 5 recovers a factorization of the input polynomial f from the factorization of n -2 bivariate projections g 1 , . . . , g n-2 . The black box is used only to obtain each g j in dense form by interpolation. 12 This can be done deterministically by evaluating g j on any set of the form S × S where |S| = d + 1. We therefore need a total of O(nd 2 ) function evaluations. Note that this is only O(n 3 ) for d = n, i.e., smaller than the number of black box call performed by the Lie-theoretic algorithm. In general the bounds dn 3 and nd 2 obtained for our first two algorithms are not comparable since d could be much larger than n (this can happen when the exponents α i in (1) are large enough).

There is no obvious improvement to this analysis of our second algorithm in the "white box" model described in Section A.1: the O(nd 2 ) function evaluations translate into an arithmetic cost of order snd 2 . Now the white box version of the Lie-theoretic algorithm becomes more interesting from the point of view of the cost of function evaluations: as explained above, this cost is only O(sn 2 ). By contrast, this cost is Ω(sn 3 ) for the algorithm of Section 5 since d ≥ n.

A.3 The hyperplane algorithm

In order to factor an input polynomial f

(x) = λ.l 1 (x) α 1 • • • l k (x) α k ,
this algorithm determines the hyperplanes H i = Z(l i ) together with their multiplicities α i . The black box calls are performed at steps 1, 3 and 6 of the algorithm. We'll focus on steps 1 and 3 since Step 6 performs only one call to the black box.

At Step 1 we compute the intersection of n -1 lines ∆ 1 , . . . , ∆ n-1 with Z(f ), the zero set of f . For this we need to interpolate f on each line; this requires a total of (n -1)(d + 1) calls to the black box.

The determination of a single hyperplane of Z(f ) is explained at step 3 of the algorithm, which we repeat here for convenience ({a 2 , . . . , a k(n-1) } are the intersection points found at Step 1):

3. Find n -2 points b 2 , . . . , b n-1 in the set {a 2 , . . . , a k(n-1) } such that each line (a 1 b j ) is included in Z(f ).
As explained in Section 6, the test (a 1 b j ) ⊆ Z(f ) can be implemented with one call to the black box at a random point on the line (a 1 b j ). This test is repeated at most k(n -1) times. We therefore need O(kn) calls to determine a single hyperplane. There are k hyperplanes to determine, for a total cost of order k 2 n. We conclude that this algorithm makes O(dn + k In order to compare with the Lie-theoretic algorithm we whould set k = n since that algorithm applies only in this situation. The cost of the hyperplane algorithm becomes O(dn + n 3 ); this is smaller than the O(dn 3 ) bound obtained for the Lie-theoretic algorithm. Note however that the latter algorithm becomes cheaper in the white box model: as explained in Section A.1 the arithmetic cost of function evaluations is only O(sn 2 ) when f is given by an arithmetic circuit of size s. This should be compared to a cost of order s(dn + n 3 ) for the hyperplane algorithm (like the bivariate algorithm, it does not seem to admit any interesting optimization in the white box model).

Finally, the hyperplane algorithm should be compared to bivariate projections. In number of calls to the black box, the latter algorithm is always as expensive or more expensive than the former (compare dn + k 2 n to d 2 n).

B Appendix: Cost of other operations

In this section we continue the analysis of our three algorithms. Appendix A dealt with the number of calls to the black box. Here we estimate the cost of "other operations", which consist mostly of:

• arithmetic operations, in K or in an extension of K.

• certain non-algebraic steps such as eigenvalue computations or the factorization of univariate polynomials.

The bounds that we give should only be viewed as very rough estimates of the algorithms' complexity since we do not perform a full analysis at the level of bit operations. 13

B.1 Lie-theoretic algorithm

In this section we analyze more precisely the algorithm of Section 4.2. We'll focus first on the complexity of deciding the existence of a suitable factorization over K. This is done in the first three steps of the algorithm. Note that the corresponding steps for the case of equal exponents (Section 4.1) only differ by the presence of n -1 trace computations. The cost of trace computations turns out to be negligible, so this analysis applies to the two versions of our algorithm. At Step 1 of the algorithm we compute a basis of the Lie algebra of f . The Lie algebra is the nullspace of a certain matrix M of size m = n 2 which we have already computed as explained in Appendix A.1. A basis of the nullspace can be computed with O(m 3 ) arithmetic operations by Gaussian elimination, and with O(m θ ) operations using fast linear algebra [START_REF] Bürgisser | Algebraic Complexity Theory[END_REF].

Here θ denotes any exponent strictly larger than ω, the exponent of matrix multiplication.

At Step 3 we first check that the matrices B 1 , . . . , B n-1 commute, where B 1 , . . . , B n-1 is the basis of the Lie algebra found at Step 1. This can be done in O(n 2+ω ) arithmetic operations. This is negligible compared to the cost O(n 2θ ) of the first step since θ > ω ≥ 2.

Then we check that the B i are all diagonalizable. Recall from Section 2.1 that B i is diagonalizable over K iff its minimal polynomial m i has only simple roots. The minimal polynomial can be computed in O(n θ ) arithmetic operations [START_REF] Giesbrecht | Nearly optimal algorithms for canonical matrix forms[END_REF][START_REF] Storjohann | Deterministic computation of the Frobenius form[END_REF]. Then we need to check that gcd(m i , m ′ i ) = 1. The cost of computing the gcd is negligible compared to n θ . The cost of the n -1 diagonalizability tests is O(n 1+θ ), which is again negligible compared to Step 1. We conclude that the existence of a suitable factorization of f can be decided in O(n 2θ ) arithmetic operations.

At Step 4 we perform a simultaneous diagonalization of the B i . As suggested in Section 2.2 and in Section 4, this can be done by diagonalizing a random combination R of the B i 's. For this, as recalled in Section 2.1 we can first compute the eigenvalues λ 1 , . . . , λ n of R (a non algebraic step). Then we compute a basis of ker(R-λ i I) for all i. One basis can computed in O(n θ ) arithmetic operations, so O(n 1+θ ) is a rough estimate on the number of arithmetic operations needed to compute a transition matrix T (we will not try to improve it since it is dominated by the cost of Step 1). Note that these arithmetic operations take place in K[λ 1 , . . . , λ n ], so counting such an operation as "one step" is probably most appropriate when the λ i lie in K, or when we work with approximations of the λ i .

Once T is known, the n -1 diagonal matrices D i = T -1 B i T can be computed at a cost of O(n 1+θ ) arithmetic operations. Then, as explained at

Step 5, we obtain the exponents α i as the orthogonal of the space spanned by the D i in the space of diagonal matrices. Alternatively, the α i can be obtained without knowledge of T as explained after Proposition 16: the n exponents are the eigenvalues of matrix H which is obtained as the unique solution of a system of Θ(n 3 ) equations in n 2 unknowns. This approach looks rather expensive since solving a square system in n 2 unknowns would already take O(n 2θ ) arithmetic operations.

The above analysis can be summarized as follows.

Proposition 22. The algorithm of Section 4.2 decides in O(n 2θ + n 3 d) arithmetic operations whether the input polynomial f admits a factorization of the form (1) over K. If such a factorization exists, it can be computed within the same number of arithmetic operations and the additional computation of the eigenvalues of a matrix R ∈ M n (K).

In the white box model of Appendix A.1, the number of arithmetic operations drops from O(n 2θ + n 3 d) to O(n 2θ ).

The term n 3 d in Proposition 22 is due to the arithmetic cost of inter-of arithmetic operations is barely higher: Õ(d 3 ) instead of O(d 3 ), where the Õ notation hides logarithmic terms. We refer to [START_REF] Chèze | Lifting and recombination techniques for absolute factorization[END_REF] for a more precise statement of their result and a description of the output representation. One advantage of their algorithm is that all arithmetic operations take place in the coefficient field K of the input polynomial, even if the factors only exist in a field extension K. Finally, we note that algorithm only applies to squarefree bivariate polynomials. For a reduction from the general case to the squarefree case we refer to Section 4.2 of [START_REF] Lecerf | New recombination algorithms for bivariate polynomial factorization based on Hensel lifting[END_REF].

So far, we have not addressed the arithmetic cost of converting from black box representation to dense bivariate representation. As pointed out in Section A.2, this can be done by interpolating each of the n -2 bivariate polynomials on a set of size (d + 1) 2 . There are several ways of doing this at negligible cost compared to dense bivariate factorization.

First, recall that a univariate polynomial of degree d can be interpolated from its values at roots of unity in O(d log d) arithmetic operations using the Fast Fourier Transform. The cost of univariate interpolation at an arbitrary set of d + 1 points is a little higher but remains Õ(d), see Section 10 of [START_REF] Von | Modern computer algebra[END_REF] for details.

Returning to bivariate polynomials, one option is to use the twodimensional FFT. Its cost remains O(N log N ), where N is the number of interpolation points. Here, N = (d + 1) 2 and we interpolate on S × S where S is the set of (1 + d)-th roots of unity. Another option is to perform the Kronecker substitution y = x d+1 and interpolate the polynomial g(x) = f (x, x d+1 ) using one of the aforementioned univariate methods. The coefficients of f can be recovered uniquely from those of g.

B.3 The hyperplane algorithm

Recall that the algorithm proposed in Section 6 factors an input polynomial f (x) = λ.l 1 (x) α 1 • • • l k (x) α k from n -1 univariate polynomial factorizations. Each univariate polynomial is of the form g(t) = f (a + tv i ) and its coefficients must be determined by interpolation at Step 1. As already mentioned in Section B.2, this can be done in O(d log d) arithmetic operations by FFT from d + 1 values of g. In order to obtain one value of g we must compute the coordinates of a + tv i before calling the black box for f , at a cost of n arithmetic operations. Interpolating g therefore takes O(d log d + dn) arithmetic operations. Since we have n -1 such polynomials to interpolate, the arithmtic cost of interpolations is O(dn(n + log d)).

The roots a 1 , . . . , a k(n-1) of the n -1 univariate polynomials are used at steps 3 and 4 to determine the zero sets of the l i . At step 5, the multiplicities of the roots of the first polynomial yield the exponents α i .

At step 3 we test whether the line (a 1 b) is included in Z(f ), where b is one the k(n -1) roots. This is done by evaluating the black box at a random linear combination ta 1 + (1 -t)b. The coordinates of this point can be computed in O(n) arithmetic operations. Repeating this for all the k(n -1) roots takes O(kn 2 ) operations.

At step 4 we determine H 1 = Span(a 1 , b 2 , . . . , b n-1 ), where the b i have been found at Step 3. Finding an equation for H 1 amounts to solving a linear system, and can be done in O(n θ ) arithmetic operations recalled in Appendix B.1. The combined cost of the determination of H 1 at steps 3 and 4 is therefore O(kn 2 + n θ ). This is repeated for all the hyperplanes, at a total cost of O(k(kn 2 + n θ )) operations. We recall that these arithmetic operations may take place in a field extension.

Finally, at Step 6 we evaluate the product k i=1 l i (x) α i at some point x and divide f (x) by this product to determine the normalization factor λ. If we use repeated squaring to evaluate the powers l i (x) α i , we can complete Step 6 in O(k(n + log d)) arithmetic operations. Since k ≤ d this is negligible compared to the cost of the univariate interpolations at Step 1. The above analysis can be therefore be summarized as follows.

Proposition 24. The algorithm of Section 6 obtains a factorization of the form f (x) = λ.l 1 (x) α 1 • • • l k (x) α k using O(k(kn 2 + n θ ) + dn(n + log d)) arithmetic operations. The algorithm also needs to compute the roots of n -1 univariate polynomials of degree d, and for one of these polynomials it needs to determine the multiplicities of roots.

For comparison with the Lie-theoretic algorithm, setting k = n in Proposition 24 yields a count of O(n 4 + dn(n + log d)) arithmetic operations. If d remains polynomially bounded in n, this is always smaller than the corresponding O(n 2θ + n 3 d) bound for the black box version of the Lie-theoretic algorithm. 14 In the white box model, the arithmetic cost of that algorithm drops to O(n 2θ ). The Lie-theoretic algorithm therefore becomes preferable from the point of view of the arithmetic cost when d exceeds n 2θ-2 .

  n and an invertible matrix A. The two following properties are equivalent.(i) The action of A sends m to a multiple of f , i.e., m(A.x) = c.f (x) for some constant c.

Theorem 12 .

 12 Consider a monomial m = (x 1 • • • x n ) α and a homogeneous polynomial f ∈ K[x 1 , . . . , x n ] of degree d = nα. The two following properties are equivalent.

  (a) Set up and solve the linear system which expresses that Tr[H] = d, Tr[HB i ] = 0 and HB i = B i H for all i = 1, . . . , n -1. Here (B 1 , . . . , B n-1 ) is the basis of g f computed at step 1 of the algorithm of Theorem 15. The system's unknowns are the n 2 entries of H. (b) Compute the eigenvalues α 1 , . . . , α n of H.

  2 n) calls to the black box. The two terms dn and k 2 n in this bound are in general incomparable since d ≥ k is the only relation between d = deg(f ) and the number k of distinct factors.

This algorithm works when the linear forms to be recovered are sufficiently generic; efficient reconstruction in the worst case is still open.

It would anyway be easy to explicitly determine the li by interpolation from a black box for these linear forms.

Some results are also known for the field of real numbers[START_REF] Carlini | The solution to the Waring problem for monomials and the sum of coprime monomials[END_REF][START_REF] Comon | On the typical rank of real binary forms[END_REF]

Note that diagonalizing a matrix is clearly related to the factorization of its characteristic polynomial.

[START_REF] Bürgisser | Condition: The geometry of numerical algorithms[END_REF] Indeed, the algorithm should report failure if g is not of form[START_REF] Baur | The complexity of partial derivatives[END_REF], or if it is should return a different factorization than for f

.[START_REF] Bürgisser | Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory[END_REF] If f is given explicitly as a sum of monomials, the Lie algebra can be computed deterministically in polynomial time; this is clear from the characterization of the Lie algebra in Lemma 5.

An equivalent characterization is that the minimal polynomial of M has only simple roots.

There is no need for randomization if f is given explicitly as a sum of monomials rather than by a black box (in this case we can directly solve the linear system from Lemma 5).

The algorithm in[START_REF] Kayal | Efficient algorithms for some special cases of the polynomial equivalence problem[END_REF] works in the circuit model, i.e., it is assumed that the input polynomial is given by an arithmetic circuit. Kayal later showed how to perform the same task in the black box model, see Section 3 of[START_REF] Kayal | Affine projections of polynomials[END_REF].

More precisely, the construction of the black boxes for the irreducible factors of f requires a single projection. Evaluating these black boxes at an input point requires another bivariate projection, see Step A in[START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF]

The algorithm also works for fields of characteristic 0, but a precise analysis of its complexity was left for future work.

There is also an additional call to the black box for verification of the final result, see Step 3 in Section 5.2.

Note that a complexity analysis at the level of bit operations is also omitted from the paper by Kalftofen and Trager[START_REF] Kaltofen | Computing with polynomials given by black boxes for their evaluations: Greatest common divisors, factorization, separation of numerators and denominators[END_REF] on black box factorization.

We recall that the term n 2θ comes from the computation of the Lie algebra of f , and the term n 3 d from the arithmetic cost of polynomial interpolation. The arithmetic computations for these two tasks take place in the coefficient field K of f rather than in a field extension.

Acknowledgements P.K. would like to thank Gilles Villard for useful pointers to the literature on computational linear algebra.

The authors are supported by ANR project CompA (code ANR-13-BS02-0001-01).

polations as explained in Appendix A.1. Towards a more thorough analysis of this algorithm one could attempt to estimate its bit complexity, assuming for instance for simplicity that f admits a factorization with the l i in Z[x 1 , . . . , x n ].

B.2 Bivariate projections

The algorithm from Section 5 recovers a factorization of f from n -2 bivariate factorization. A state of the art algorithm for the latter task can be found in [START_REF] Lecerf | New recombination algorithms for bivariate polynomial factorization based on Hensel lifting[END_REF], where the following reduction from bivariate to univariate factorization is provided. Theorem 23. Let K be a field of characteristic 0, and F ∈ K[x, y] a bivariate polynomial of degree d x in the variable x and d y in the variable y. There is a probabilistic algorithm that factors F in O((d x d y ) 1.5 ) arithmetic operations. Moreover, the algorithm performs irreducible factorizations polynomials in K[y] whose degree sum is at most d x + d y .

We have omitted the cost of generating random field elements from the statement of the theorem. A deterministic version of this result is also provided in [START_REF] Lecerf | New recombination algorithms for bivariate polynomial factorization based on Hensel lifting[END_REF], with a slightly higher arithmetic cost: O((d x d y ) (θ+1)/2 ) instead of O((d x d y ) 1.5 ). The univariate factorizations in Theorem 23 can be viewed as an analogue of the eigenvalue computations in Proposition 22.

For an input polynomial f with coefficients in K, it may be the case that a factorization into products of linear forms exists only in an extension K of K. We will therefore need to apply Theorem 23 to such a field extension, and the arithmetic operations in Theorem 23 will also take place in this field extension. We have already made a similar remark for the algorithm of Section 4 in Section B.1.

If the input f has degree d, we can take d x = d y = d and we conclude that the algorithm of Section 5 will make O(nd 3 ) arithmetic operations. For d = n this is smaller than the arithmetic cost O(n 2θ ) in Proposition 22, but the latter bound becomes smaller if d significantly larger than n.

A complete analysis should also take the cost of univariate factorizations into account. Assume for instance that K = K = Q. A polynomial time algorithm for this task was first by given Lenstra, Lenstra and Lovasz [START_REF] Lenstra | Factoring polynomials with rational coefficients[END_REF]. This remains a relatively expensive task despite several improvements (see [START_REF] Bostan | Algorithmes efficaces en calcul formel[END_REF] for an exposition and more references). However, we only need to find the linear factors of F (together with their multiplicities). This boils down to finding the rational roots of a univariate polynomial, a task which (as already pointed out in Section 2.1) has an essential quadratic binary cost ([3], Proposition 21.22).

As an alternative to Theorem 23 one may use the absolute factorization algorithm by Chèze and Lecerf [START_REF] Chèze | Lifting and recombination techniques for absolute factorization[END_REF]. This algorithm only performs arithmetic operations (no univariate factorization is involved). Moreover, the number