By the Fundamental Theory of Symmetric Polynomials every symmetric polynomial in $K[x_1, \dots, x_n]$ can be written uniquely in the elementary symmetric functions $s_1, \dots, s_n$.

I know there are algorithms (like the one of the image I add at the end) that compute the reduction respect with the elementary functions. But for big polynomials this can be unwieldly.

I was wondering if one could do it faster when the polynomial is in certain regular form. For instance, consider the computation of a resolvent. This is, given a polynomial $\phi \in K[x_1, \dots, x_n]$ let $H$ be the $Stab_{S_n}(\phi)$ and let $S_n // H$ stand for a complete system of representatives of left cosets of $S_n$ respect to $H$. It is useful to compute the symmetric form of the resolvent defined by:

$$\prod_{\sigma \in S_n//H} \left( y - \phi(x_{\sigma(1)},\dots, x_{\sigma(n)})\right) \in K[y, s_1, \dots, s_n] $$

This is symmetric but computing the product and then reducing can be unwieldly sometimes. Is there any way to compute the reduction without computing the product for regular polynomials like those?

Consider for example $\phi := x_1+x_2 \in K[x_1, \dots, x_4]$. Then the resolvent is:


Multiplying takes a lot of operations but the polynomial is very regular, symmetric. How could one take advantage of this?

The algorithm I mentioned:


(Chapter 7 of Cox, Little, O'Shea: Ideals, Varieties and Algorithms)


I solved the problem for the linear resolvent (this is when $\phi$ is a linear polynomial) which was what I really needed. The trick to compute efficiently a linear resolvent is combining three well known algorithms. One of them computes the polynomial whose roots are the sums of roots of two polynomials (using resultants). Other computes a polynomial whose roots are the roots of another polynomial multiplied by a number. And the last is an algorithm to find a polynomial $r(x)$ given by the equation $r(x)^k = u(x)$ with $k \in \mathbb{N}^+$ and $u(x) \in K[x]$ known.

Combining these three methods one can compute a linear resolvent efficiently.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.