Algorithms for the universal decomposition algebra

Algorithms for the universal decomposition algebra

Let k be a field and let f ∈ k[T] be a polynomial of degree n. The universal decomposition algebra A is the quotient of k[X1, , Xn] by the ideal of symmetric relations (those polynomials that vanish on all permutations of the roots of f). We show how to obtain efficient algorithms to compute in A. We use a univariate representation of A, i.e. an isomorphism of the form A ≃ k[T]/Q(T), since in this representation, arithmetic operations in A are known to be quasi-optimal. We give details for two related algorithms, to find the isomorphism above, and to compute the characteristic polynomial of any element of A.

 Introduction 

Let k be a field and let f = Xn+ P i=1 n (−1)i fi Xn−i in k[X] be a degree n separable polynomial. We let R 7 {α1, , αn} be the set of roots of f in an algebraic closure of k. The ideal of symmetric relations Is is the ideal {P ∈ k[X1, , Xn]|∀σ ∈ Sn, P(ασ(1), , ασ(n)) = 0}. It is is generated by (Ei − fi)i=1, ,n, where Ei is the ith elementary symmetric function on X1, , Xn. Finally, the universal decomposition algebra is the quotient algebra A 7 k[X1, , Xn]/Is, of dimension δ 7 n!. For all P ∈ A, we denote by X P ,A its characteristic polynomial in A, that is, the characteristic polynomial of the multiplication-by-P endomorphism of A. Stickelberger’s theorem shows that X P ,A(T) = Y σ∈Sn (T − P(ασ(1), , ασ(n))) ∈ k[T]. (7.1) This polynomial is related to the absolute Lagrange resolvent LP(T) 7 Y Stab(P)\\Sn (T − P(ασ(1), , ασ(n)))∈ k[T], where Stab(P)\\Sn are the left cosets of the stabilizer of P in the symmetric group Sn; indeed, these polynomials satisfy the relation X P ,A = LP #Stab(P) . Computing Lagrange resolvents is a fundamental question, motivated for instance by applications to Galois theory or effective invariant theory. There exists an abundant literature on this question [Lag70, Soi81, Val89, AV94, AV97, Leh97, Yok97, RV99, AV00]; known symbolic methods rely on techniques involving resultants, symmetric functions, standard bases or invariants (we will make use of some of these ingredients as well). However, little is known about the complexity of these methods. As it turns out, almost all algorithms have at least a quadratic cost δ 2 in the general case. 145 Algorithms for the universal decomposition algebra In some particular cases, though, it is known that resolvents can be computed in quasi-linear time [CM94]. Our goal in this article is thus to shed some light on these questions, from the complexity viewpoint: is it possible to give fast algorithms (as close to quasi-linear time as possible) for general P? What are some particular cases for which better solutions exist? To answer these questions, we measure the cost of our algorithms by the number of arithmetic operations in k they perform. Practically, this is well adapted to cases where k is a finite field; over k = Q, a combination of our results and modular techniques, such as in [Ren04] for resolvents, should be used. The heart of the article, and the key to obtain better algorithms, is the question of which representation should be used for A. A commonly used representation is triangular . The divided differences, also known as Cauchy modules [Che50, RV99], are defined by C1(X1) 7 f(X1) and Ci+1 7 Ci(X1, , Xi) − Ci(X1, , Xi−1, Xi+1) Xi − Xi+1 (7.2) for 16i n in time O(M(n ′ )). The Newton representation is useful to speed up certain polynomial operations, such as multiplication and exact division, since Si(g h) = Si(g) + Si(h) for all i ∈ N. Other improved operations include the composed sum and composed product of g and another polynomial h, with roots γ1, , γm; they are defined by g ⊕ h 7 Y i=1 n,j=1 m (X − (βi + γj)), g ⊗ h 7 Y i=1 n,j=1 m (X − (βi γj)). Lemma 7.3. ([Bos03, section 7.3]) Let g, h be monic polynomials in k[X], and suppose that S(g, r) and S(h, r) are known. Then one can compute S (g ⊗ h, r) in time O(r); if the characteristic of k is either zero or greater than r, one can compute S (g ⊕ h, r) in time O(M(r)). We write ⊗NS(S(g, r), S(h, r), r) and ⊕NS(S(g, r), S(h, r), r) for these algorithms; the subscript NS shows that the inputs and outputs are in the Newton representation. 

Preliminaries 

Univariate representations

 We recall a few facts on univariate representations. Let us fix m 6n. Then, a linear form Λ is primitive for Am if and only if it takes distinct values on the points of the variety defined by Is∩k[X1, , Xm]. This is the case if and only if the minimal polynomial of Λ coincides with its characteristic polynomial X Λ,Am, if and only if X Λ,Am is squarefree. For instance when m =n, Λ is primitive in An if and only if the values Λ(ασ(1), , ασ(n)) are all distinct for σ ∈ Sn. By Zippel-Schwartz lemma [Zip79, Sch80], for K ∈ N>0, a random linear form Λ will be primitive for Am with probability greater than 1 − 1/(2 K) if its coefficients are taken in a set of cardinality K δm 2 ; this still holds if we set λ1 7 1. One can find primitive linear forms for Am in a (non-uniform) deterministic manner, but with a cost polynomial in δm [CG10]. When Λ is primitive, in the univariate representation P = (Q, S1, , Sn) corresponding to Λ, we obtain Q as Q = X Λ,Am. The polynomials Si are called parametrizations because they are the images of the variables Xi by the isomorphism Am ≃ k[T]/(Q). We will now argue that any “reasonable” algorithm that computes Q will also give us the parametrizations for a moderate overhead. Let us extend the base field k to k ′ 7 k(L1, , Lm), where Li are new indeterminates. Let Am ′ 7 Am ⊗k k ′ be obtained by adding L1, , Lm to the ground field in Am, and let finally X L,Am ′ ∈ k ′ [T] be the characteristic polynomial of L 7 L1 X1 + + Ln Xm. Then, the following holds: Si = − ∂ X L,Am ′ ∂Li / ∂ X L,Am ′ ∂T mod X L,Am ′     L1, ,Lm=λ1, ,λm ; see for instance [Kro82, Kön03, Mac16, HKP+00, GLS01, DL08]. We can avoid working with m-variate rational function coefficients, as the formula above implies that we can obtain Si as follows. Let kε 7 k[ε]/(ε 2 ). For a given Λ, and for i 6 m, let X Λi be the characteristic polynomial of Λi 7 Λ + ε Xi , computed over kε. Then, X Λi takes the form X Λi = X Λ,Am + ε Ri , and we obtain Si as Si = Ri/X Λ,Am ′ mod XΛ,Am. We will require that the algorithm computing X Λ,Am performs no zero-test or division (other than by constants in k, since those can be seen as multiplications by constants). Since any ring operation (+, ×) in kε costs at most 3 operations in k, given such an algorithm that computes the characteristic polynomial of any linear form in Am in time C, we can deduce an algorithm that computes each Si in time O(C), and S1, , Sm in time O(m C).