Singular

Additionally to what malex said, here is proc which also works
as a certificate whether the inout is symmetric.

The problem of expressing a symmetric polynomial in terms of
the elementary polynomials is just rewriting process.

See for instance
Cox, Little, O'Shea: Ideals, varieties and algorithms,
Ch. 7, especially p. 314

there you will also find the notice that [b]Gauss [/b] already has answered this question.

Now with the help of Groebner basis calculations, this rewriting
process is automatized by computing the normalform.

First we need a procedure to generate the elementary symmetric polynomials.
[code]proc elemsymp(list #)
"USAGE: elemsymp(); or elemsymp(k); k int, 0<=k<=nvars(basering)
RETURN: ideal I; containing the elementary symmetric polynomials
I[k] = s_k, 1<=k<=nvars, deg(s_k) = k
poly, the elementary symmetric polynomial s_k, 0<=k<=nvars(basering)
EXAMPLE: example elemsymp; shows an example
"
{
int n = nvars(basering);
int i,k;
if (size(#))
{
k=#[1];
if (k<0 or k>n) {ERROR("// -- proc elemsymp: argument outside range");}
if (k==0) {return(1);}
}
def d = basering;
list rl = ringlist(d);
rl[2]= insert(rl[2],"@Z@",n);
def rnew = ring(rl);
setring rnew;
poly f=1;
for (i=1;i<=n;i++)
{
f = f*(var(n+1)-var(i));
}
ideal I = coeffs(f,var(n+1));
for (i=1;i<=n;i++)
{
I[i] = (-1)^(n-i+1)*I[i];
}
I = I[n..1];
setring d;
ideal I = fetch(rnew,I);
if (k) {return(I[k]);}
else { return(I);}
}
[/code]
When called without any argument, this proc returns an ideal such
that slot i (1<=i<=nvars(basering)) contains the elementary polynomial of degree i. (So the constant polynomial is ommited.)

If this proc is called with an integer i , (0<=i<=nvars), then it returns the i-th symmetric polynomial.
[code]
> ring r=0,(x,y,z),dp;
> elemsymp();
_[1]=x+y+z
_[2]=xy+xz+yz
_[3]=xyz
> elemsymp(0);
1
> elemsymp(1);
x+y+z
> elemsymp(2);
xy+xz+yz
> elemsymp(3);
xyz[/code]
Now the rewriting process:

Proposition 4 p. 314 says:

[list=] Let e_1,...,e_n the elementary symmetric polynomials in the variables x_1,...,x_n.

Introduce new variables y_1,...,y_n, such the monomial in the old
variables x_1,...,x_n are greater h´than those in y_i

Form the ideal I = <e_1 - y_1,..., e_n - y_n>,

Compute a Grobener basis G of I,

and determine for the given polynomial f the normalform w.r.t. G.

Then f is symmetric if and only if g only depends on the variables y_1,...,y_n.
Moreover, in this case, g is the desired polynomial.

This is, substituting the variable y_i by the poylnomial e_i
gives f = g(e_1,...,g_n).
[/list=]

Here is the proc which does this, it uses the proc [b]substitute[/b] from [i]poly.lib[/i].

[code]proc reprsympoly(poly f)
"USAGE: reprsympoly(f); f poly
RETURN: poly 0, if f is not symmetric, otherwise
the polynomial which expresses f in the elementary polynomials,
ASSUME: global polynomial ordering of the basering
NOTE: the polynomial is considered symmetric w.r.t. to the variables
of the basering
EXAMPLE: example reprsympoly(f); shows an example
"
{
int n = nvars(basering);
def d = basering;
ideal Isym = elemsymp();
ideal maxid1 = maxideal(1);

list rl = ringlist(d);
for (int i=1;i<=n;i++)
{
rl[2]= insert(rl[2],"@"+string(var(i)),n+i-1);
}
def rnew = ring(rl);
setring rnew;

ideal I = fetch(d,Isym);
for (i=1;i<=n;i++)
{
I[i] = -var(n+i) +I[i];
}
ideal Istd = std(I);

poly f = fetch(d,f);
poly G = NF(f,Istd);
ideal maxid1 = maxideal(1);
ideal I1 = maxid1[1..n];
ideal I2 = maxid1[n+1..2*n];
ideal varG = variables(G);
if (substitute(G,I1,ideal(0:n))!=G) // poly.lib
{
return(0);
}
else
{
G = substitute(G,I2,I1);
}
setring d;
poly G = fetch(rnew,G);
return(G);
}[/code]

If the input polynomial is not symmetric, then 0 is return,

For the convenience of the user, the returned polynomial is in the original variables.
[code]
> LIB "poly.lib"; // for subsitute
> ideal I = elemsymp();
> I;
I[1]=x+y+z
I[2]=xy+xz+yz
I[3]=xyz
> poly f = -7*I[1]^3 +4*I[3] - 11 * I[2] + 1; // malex example
> reprsympoly(f); // leading coeff is the right one
-7x3-11y+4z+1

> reprsympoly(xy+z); // not symmetric
0

> reprsympoly(x3y+x3z+xy3+xz3+y3z+yz3);
x2y-2y2-xz
> substitute(_,maxideal(1),elemsymp());
x3y+xy3+x3z+y3z+xz3+yz3

> reprsympoly((x-y)^2*(x-z)^2*(y-z)^2);
x2y2-4x3z-4y3+18xyz-27z2
> factorize(substitute(_,maxideal(1),elemsymp()));
[1]:
_[1]=1
_[2]=x-z
_[3]=-x+y
_[4]=y-z
[2]:
1,2,2,2
[/code]

Further comments:

1.) As usuals, the certificat "symmetric" is w.r.t. the ambiant ring.

This means, in a ring with three variables the polynomial
x+y is not (considered as) symmetric.

Cleary, it is not invariant under the permutations involving z.

[code]> string(basering);
(0),(x,y,z),(dp(3),C)

> reprsympoly(x+y);
0[/code]

2.) The proc reprsympoly does not need a substitution

y_1 <- e_1,...,y_n <- e_n

to verify the correctness of the computation

You may do this afterward, as shown in the examples above,
but in general the substitution may take longer than computing
the representation itself.

The following timings are taken on a slow machine, to demonstrate the difference.
[code]> poly F = (((x-y)^2*(x-z)^2*(y-z)^2)^21);
> timer=0;
> timer = 1;
> poly H = reprsympoly(F); // find the representation
//used time: 37.99 sec
> timer;
38

> timer = 1;
> poly S = substitute(H,maxideal(1),elemsymp()); // go to check the result
//used time: 64.68 sec
> timer;
65
> F == S;
1
[/code]

//-------------------

Ch. Gorzel

Hi Octopus,

you simply eliminate initial variables as follows:

[code]ring R = (0), (x(1..3), s(1..3)), (dp);

poly s1 = x(1) + x(2) + x(3);
poly s2 = x(1)*x(2) + x(1)*x(3) + x(2)*x(3);
poly s3 = x(1) * x(2) * x(3);

// just any symmetric poly. in x,y,z (NOT in s(i)) !!!
poly f = -7*s1^3 +4*s3 - 11 * s2 + 1; // i used s_i just to make sure that it is symmetric

ideal S = s(1) - s1, s(2) - s2, s(3) - s3; // Relations between s(i) and symmetric polynomials
poly g = eliminate( S + f, s3)[1]; // ELIMINATE ALL THE INITIAL VARIABLES!
[/code]
the '''eliminate''' yealds:
_[1]=7*s(1)^3+11*s(2)-4*s(3)-1

note that it is a multiple of the needed expression... you can fix it as follows:

if f contained a constant:
[code]
g = g * jet(f, 0) / jet(g,0);
[/code]
otherwise:
[code]
poly ff = subst(g, s(1), s1, s(2), s2, s(3), s3); // may be expensive!
g = g * leadcoef(f) / leadcoef(ff);
[/code]


I hope that helps,
Oleksandr

Hi Octopus,

there is no such direct command. Of course you may construct an ideal consisting of the elementary symmetric polynomials and your candidate polynomial and then call 'syz' to discover the polynomial factors; see below for an example session.
Maybe also sagbi.lib (for working with finitely presented subalgebras of a polynomial ring) provides commands which may be useful for your purpose.

Regards,
Frank

==========================================

$ Singular
SINGULAR /
A Computer Algebra System for Polynomial Computations / version 3-1-2
0<
by: W. Decker, G.-M. Greuel, G. Pfister, H. Schoenemann \ Oct 2010
FB Mathematik der Universitaet, D-67653 Kaiserslautern \
// ** executing /cygdrive/c/Work/Code/SINGULAR/svn/Release/LIB/.singularrc
> ring R = integer, (x,y,z), dp;
// ** You are using coefficient rings which are not fields.
// ** Please note that only limited functionality is available
// ** for these coefficients.
// **
// ** The following commands are meant to work:
// ** - basic polynomial arithmetic
// ** - std
// ** - syz
// ** - lift
// ** - reduce
> poly p0 = 1;
> poly p1 = x+y+z;
> poly p2 = xy+xz+yz;
> poly p3 = xyz;
> poly f = p1*p3+p2*p2+7*p0;
> f;
x2y2+3x2yz+3xy2z+x2z2+3xyz2+y2z2+7
> ideal i = p0,p1,p2,p3,f;
> print(syz(i)); // only look for syzygies involving f
-x-y-z,y2+yz+z2,z3, 7,
1, -y-z, -z2,xy2+3xyz+y2z+xz2+yz2,
0, 1, z, -y2-yz-z2,
0, 0, -1, 0,
0, 0, 0, -1
> ideal i = p1,p2,p3,f-7*p0;
// ** redefining i **
> print(syz(i)); // only look for syzygies involving f
-xy-xz-yz,0, -xz2-yz2,y2z2,
x+y+z, -xy-xz-yz,xz+yz+z2,-y2z-yz2,
0, -x-y-z, -x-y-z, y2+yz+z2,
0, 1, 0, 0
>

Hi,

is there any function with the following feature?
input: a symmetric polynomial f with coefficients in Z.
output: f rewritten as a polynomial in the elementary symmetric polynomials.

Thanks a lot for help!

-Octopus