Symmetric polynomial in terms of elementary symmetric polynomials

[Federico Lebrón]

Hi.

I've written a small pair of functions which could be useful:

1) A function is_symmetric which, given a polynomial, returns whether or not the polynomial is a symmetric polynomial.
2) A function symmetrize which, given a symmetric polynomial, returns an equivalent expression in terms of the elementary symmetric polynomials.

The code, which likely needs some cleanup (and modifications to do things "the Sage way", whatever it may be), is here: http://codepad.org/gJpNRfHH

Would there be interest in adding these to Sage perhaps? I tried searching for similar functionality but couldn't find it.

Cheers,

- Fede

[Dima Pasechnik]

Hi,

I tried your code, and got an error.

Could you please post an example of usage of your functions, and also tell us which version of Sage it is known to run on.

(Sage has a doctest facility, so for your code to be incorporated into Sage one will stil need to include such examples in the code).

Dmitrii

[Nicolas M. Thiery]

Please have a look at SymmetricFunctions and
http://combinat.sagemath.org/doc/thematic_tutorials/demo-symmetric-functions.html

and get back to us for more information if needed!

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Federico Lebrón]

Hi Dmitri,

I had forgotten to include the imports at the top :) Adding the imports it looks like this: https://gist.github.com/1427311

I'm using Sage 4.7.2 on OS X, an example code would be, if the code was at sym.py:

sage: import sym
sage: R.<x, y, z> = PolynomialRing(ZZ)
sage: f = x^2 + y^2 + z^2 + x^2*y*z + x*y^2*z + x*y*z^2
sage: sym.is_symmetric(f)
True
sage: sym.symmetrize(f)
sigma_1^2 + sigma_1*sigma_3 - 2*sigma_2

On 2011/12/03, at 05:37, Nicolas M. Thiery wrote:

>
> Please have a look at SymmetricFunctions and
> http://combinat.sagemath.org/doc/thematic_tutorials/demo-symmetric-functions.html
>
> and get back to us for more information if needed!
>
> Cheers,
> Nicolas

Hi Nicolas,

I looked at it but didn't find something like this, perhaps I missed it? I am using the symmetric function algebra mentioned there to generate the elementary symmetric polynomials. Did you mean that the functionality is already in that file?

Thanks,

- Fede

[Dima Pasechnik]

Hi Nicolas, 

unless I missed something,

your http://combinat.sagemath.org/doc/thematic_tutorials/demo-symmetric-functions.html

lacks any information as to how to take any symmetric polynomial, and expand it  in some basis of symmetric functions.

Is it even possible with the combinat functionality?

It's often suggested that in practice Groebner-basis based methods are more efficient...

Dmitrii

[Nicolas M. Thiery]

On Sun, Dec 04, 2011 at 03:56:39AM -0800, Dima Pasechnik wrote:
> unless I missed something,
> your http://combinat.sagemath.org/doc/thematic_tutorials/demo-symmetric-functions.html
> lacks any information as to how to take any symmetric polynomial, and
> expand it in some basis of symmetric functions.

Indeed: this tutorial is very incomplete. Someone should stand up and
take the time to gather all the bits of docs from here and there, and
merge a nice and clean tutorial on Symmetric functions into Sage.

> Is it even possible with the combinat functionality?

It definitely is. Here is a story without subtitles (please ask for
those if needed:

sage: S = SymmetricFunctions(QQ)
sage: m = S.m()
sage: e = S.e()
sage: f = e[3,2,1]
sage: f_as_poly = f.expand(3); f_as_poly
x0^3*x1^2*x2 + x0^2*x1^3*x2 + x0^3*x1*x2^2 + 3*x0^2*x1^2*x2^2 + x0*x1^3*x2^2 + x0^2*x1*x2^3 + x0*x1^2*x2^3
sage: f_as_poly.parent()
Multivariate Polynomial Ring in x0, x1, x2 over Rational Field

sage: f_in_m = m.from_polynomial(f_as_poly); f_in_m
3*m[2, 2, 2] + m[3, 2, 1]

sage: f_in_e = e(f_in_m)
sage: f_in_e
e[3, 2, 1] - 3*e[4, 1, 1] - 2*e[4, 2] + 13*e[5, 1] - 18*e[6]

Oops, but we don't get the original symmetric function f! Actually
this is perfectly correct since we lost information by only expanding
in 3 variables:

sage: f_in_e.expand(3) == f.expand(3)

If one kills all terms with parts larger than 3 (since
e_4=e_5=e_6=...=0 in three variables).

> It's often suggested that in practice Groebner-basis based
> methods are more efficient...

Really? A proof by benchmark is welcome :-)

I guess it depends a lot on what kind of polynomials are being fed in
(degree, number of variables), and in particular if one is interested
in symmetric functions (on an infinite number of variables) or
symmetric polynomials (on a, typically small, finite number of
variables).

Best,

[Nicolas M. Thiery]

On Sat, Dec 03, 2011 at 11:58:16AM -0300, Federico Lebr�n wrote:

> I looked at it but didn't find something like this, perhaps I missed
> it? I am using the symmetric function algebra mentioned there to
> generate the elementary symmetric polynomials. Did you mean that the
> functionality is already in that file?

Indeed. I was in a rush, and hoping you would find it indirectly (a
non trivial task). See the details in my other e-mail!

Cheers,

[Dima Pasechnik]

Thanks, it's really useful, and really must make its way into the docs ASAP...

 

>    It's often suggested that in practice Groebner-basis based
>    methods are more efficient...

Really? A proof by benchmark is welcome :-)

I probably meant a (rather naive?) algorithm implemented in Symmetrica, which is known to be unable to 

expand (x+y+z)^3.

So this one is easy to beat with anything, I guess.

 

I guess it depends a lot on what kind of polynomials are being fed in
(degree, number of variables), and in particular if one is interested
in symmetric functions (on an infinite number of variables) or
symmetric polynomials (on a, typically small, finite number of
variables).

by the way, how about settings when more than one bunch of symmetric polynomials (or functions).

E.g. I have a polynomial expression P in roots of a polynomial f(x), and in roots of the complex conjugate of f(x), 

and it is symmetric (via the natural bijection between the roots of f and the roots its conjugate).

(Example: take a general quadratic polynomial, then the distance between its roots in the complex plane is such an expression.)

And I would like to express P in some symmetric functions of the coefficients of f and its conjugate.

Is it easy to do?

Or here one would need a Groebner basis anyway?

Thanks,

Dima

  

Best,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Jeroen Demeyer]

So I think this illustrates exactly Dima's sentiment that Sage doesn't
have functionality to write a given symmetric polynomial in terms of
elementary symmetric polynomials. Maybe it's technically possible, but
surely not easy!

Also, it's not clear to me even what e[3,2,1] means. How do Sage's
elementary symmetric functions relate to
http://en.wikipedia.org/wiki/Elementary_symmetric_polynomial#Examples

[Florent Hivert]

This is a notation for the product e3e2e1.

Cheers,

Florent

[Mike Hansen]

You can get the symmetric polynomials on that page by expanding Sage's
elementary symmetric functions out in a finite number of variables.

sage: e = SymmetricFunctions(QQ).e()
sage: e[1].expand(4)
x0 + x1 + x2 + x3
sage: e[2].expand(4)
x0*x1 + x0*x2 + x1*x2 + x0*x3 + x1*x3 + x2*x3
sage: e[3].expand(4)
x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x1*x2*x3
sage: e[4].expand(4)
x0*x1*x2*x3

e[3,2,1] represents the product e[3]*e[2]*[1]:

sage: e[3]*e[2]*e[1]
e[3, 2, 1]

To get a symmetric function from a polynomial, you use the
"from_polynomial" method as Nicolas mentioned. The only awkward part
is that this method only exists for the the monomial basis. (It would
be easy to add a method to the other bases which converted the
polynomial to the monomial basis and then to itself, but that doesn't
exist yet.)

sage: m = SymmetricFunctions(QQ).m()
sage: f = e[2].expand(4); f
x0*x1 + x0*x2 + x1*x2 + x0*x3 + x1*x3 + x2*x3
sage: f_in_e = e(m.from_polynomial(f)); f_in_e
e[2]
sage: f_in_e.expand(4)
x0*x1 + x0*x2 + x1*x2 + x0*x3 + x1*x3 + x2*x3

--Mike

[Jeroen Demeyer]

On 2011-12-08 20:16, Mike Hansen wrote:
> e[3,2,1] represents the product e[3]*e[2]*[1]:

As far as I can tell, this is nowhere mentioned in the documentation.
Certainly not in the obvious places.

> sage: e[3]*e[2]*e[1]
> e[3, 2, 1]

It would be nice to be able to expand e[3,2,1] into a polynomial
e3*e2*e1, for example for expressing symmetric functions of the roots of
a polynomial in terms of the coefficients of that polynomial.

[Dima Pasechnik]

On Friday, 9 December 2011 04:25:23 UTC+8, Jeroen Demeyer wrote:

On 2011-12-08 20:16, Mike Hansen wrote:
> e[3,2,1] represents the product e[3]*e[2]*[1]:
As far as I can tell, this is nowhere mentioned in the documentation.

well, this is standard in the symmetric functions business.

e_\lambda is defined for any partition \lambda in this way.

 

Certainly not in the obvious places.

> sage: e[3]*e[2]*e[1]
> e[3, 2, 1]
It would be nice to be able to expand e[3,2,1] into a polynomial
e3*e2*e1, for example for expressing symmetric functions of the roots of
a polynomial in terms of the coefficients of that polynomial.

Hmm, not sure I understand what you are asking for.

sage: e[3,2,1]==e[3]*e[2]*e[1]

True

Dima 

[Jeroen Demeyer]

On 2011-12-09 07:39, Dima Pasechnik wrote:
> Hmm, not sure I understand what you are asking for.

I am asking for:

sage: e = SymmetricFunctions(QQ).e()
sage: R.<e1,e2,e3> = PolynomialRing(QQ)
sage: e[3,1,1].express_as_polynomial([1,e1,e2,e3])
e1^2*e3

or something like:

sage: e = SymmetricFunctions(QQ).e()
sage: R.<E> = InfinitePolynomialRing(QQ)
sage: R(e[3,1,1])
E_3*E_1^2

[Nicolas M. Thiery]

On Fri, Dec 09, 2011 at 10:19:22AM +0100, Jeroen Demeyer wrote:
> I am asking for:
>
> sage: e = SymmetricFunctions(QQ).e()
> sage: R.<e1,e2,e3> = PolynomialRing(QQ)
> sage: e[3,1,1].express_as_polynomial([1,e1,e2,e3])
> e1^2*e3

Ah, you want the result expressed as a plain polynomial. Then it's
just a one-liner change of representation:

sage: e = SymmetricFunctions(QQ).e()
sage: x = e.an_element()
sage: x
1/2*e[] + 3*e[1, 1, 1] + 2*e[2, 1, 1]
sage: sum( c*prod( Re[i-1] if i<=3 else R.zero for i in part ) for (part,c) in x )
3*e1^3 + 2*e1^2*e2 + 1/2

However I agree this one-liner deserves to be wrapped for the user,
especially since this one-liner won't handle properly corner cases (in
particular x=0). So ...

Free commutative algebras represented using a multiplicative basis
(like this one) should have:

- An "algebra_morphism" method
- A morphism and its inverse, built using algebra_morphism,
implementing the isomorphism with some plain Sage polynomial ring

Any good suggestion of name? the obvious to_polynomial is ambiguous
since we don't know if we want a polynomial in the x's or in the
e's.
- Functionalities like factor and such, implemented through the
those isomorphisms

Note: in MuPAD, had the algebra_morphism functionality, and we could
also write expr(x) which returned x as an expression in (the analogue
of) SR, and then we could just do poly(expr(x)). We also. That's
probably why we had not come up with an appropriate interface for this
functionality.

Cheers,