Efficient reduction to elementary symmetric polynomials

edit

I wasn't asking how to reduce the expression in elementary symmetric polynomials, but rather how to speed up the computation of SymmetricFunctions.from_polynomial given the special conditions I have. That is my input is some polynomial in the roots (which I know is symmetric) and I want to express it in $e_i$. But I guess there really isn't a way other than writing the reduction algorithm myself.

It's unclear what is your set up. If you work with symmetric expressions of 5 roots only, how do you get $e_i$ with $i>5$ in the result of from_polynomial? In general you can reduce your polynomial in the ideal generated by polynomials like $e_1$ (known to be zero) before converting to a symmetric one.

If you work with symmetric expressions of 5 roots only, how do you get ei with i>5 in the result of from_polynomial

The same as in your question you linked: My polynomial is of higher degree than the number of variables (which in my case is the hypothetical roots of a (different) polynomial to be solved)

you can reduce your polynomial in the ideal generated by polynomials like e1 (known to be zero) before converting to a symmetric one.

Yeah, that's what I tried at first but the reduce operation breaks the symmetry (quite naturally). E.g. (a^2 + b^2 + c^2 + d^2).reduce([a+b+c+d]) is no longer symmetric because the a is eliminated by the division algorithm,

I do not follow. (a^2 + b^2 + c^2 + d^2).reduce([a+b+c+d])is symmetric in the remaining three variables. E.g. see https://sagecell.sagemath.org/?q=jxrjub

Ok. It is symmetric but is there any relation between this new polynomial in 3 variables to the original one? In particular, can the original $e_i$ be recovered from the new $e_i$? To repeat my goal, given a symmetric polynomial I would like to express it in elementary symmetric polynomials while somehow utilizing the fact that $e_1$ is zero during the computation. I.e. my goal is to speed up the computation given the special properties.

If $e_i, e'_i$ are "old" and "new" polynomials, respectively, then $e_i = e'_i - e'_1e'_{i-1}$. So, you can work with new polynomials and then switch back to old one when needed.

Now I don't follow :-) To recover $e_i$ you surely need some original (non-primed) $e$ on the right hand side. Otherwise you are missing a. Perhaps just a typo? But anyway, looking at the simple cases https://sagecell.sagemath.org/?q=mxzabp I don't see any simple recovering relation.

No. Here are a bit ugly but working (back and force) conversion functions: https://sagecell.sagemath.org/?q=khljrd

Thank you for your time and effort but I still don't see what you mean. I must be missing some piece of theory you could perhaps point me to.

Anyway, just to restate my goal on a concrete example, I want to express f = a^3 + b^3 + c^3 in ESym, i.e. e[1, 1, 1] - 3*e[2, 1] + 3*e[3]. I also know beforehand that e[1] = a + b + c is zero, therefore the result I'm after is 3*e[3]. The whole question is whether there's a way to get this result without converting f to ESym first.

One of the possible options I tried was to first reduce by e[1]: e.from_polynomial(f).reduce([a+b+c]).specialization({a:0}). As you pointed out, this gives a symmetric polynomial in b, c although that's not at all clear why this should be the case. Is it a special property of the Grobner basis algorithm that is (probably) used here? Because another valid value of course would also be 3*e[3] = 3*a*b*c which is what I originally hoped I would get after the reduction.

Anyway, when I plug in this reduced polynomial to your to_old function I get 9*e[3], i.e. not the correct result.

My point is that you can perform computations with symmetric ("primed") functions of one fewer variables, which will take care of $e_1=0$ automatically. Then you can get the result transformed back to a symmetric ("non-primed") function of original variables. I've provided conversion functions in the last link to Sagecell.

This way, you first eliminate one variable from f and then convert it into a symmetric polynomial of the remaining variables to get the ball running.

Can you provide a complete example? Also, it should be e.from_polynomial( f.reduce([a+b+c]).specialization({a:0}) ), not e.from_polynomial(f).reduce([a+b+c]).specialization({a:0}).

Sorry, I made a copy&paste error probably but my computations were correct, i.e. this to_old( e.from_polynomial( (a^3 + b^3 + c^3).reduce([a+b+c]).specialization({a:0}) ) ) gives (using your conversion function) 9*e[3] which is not 3*e[3] (the only e[1]-less term of e.from_polynomial(a^3 + b^3 + c^3)

Anyway, I realize now that this whole exercise (while interesting in itself) is probably pointless since it seems that calling from_polynomial on the reduced input isn't significantly faster after all :-( I start doubting that there actually is a useful optimization for the e[1] == 0 case.