Dear Forum, > On May 10, 2015, at 5:30 AM, Anvita <anvit...@gmail.com> wrote: > > Dear Forum, > > Suppose that f1,...fn are polynomials in x1,...,xk > and suppose that f is another such polynomial that > can be represented in the form > > f = g(f1,...,fn) > > where g(y1,...,yn) is a new polynomial. Can I use GAP > to find the polynomial g?
In the generic case, algorithms for this have been proposed (e.g. http://link.springer.com/article/10.1007%2Fs00200-003-0122-8 http://www.sciencedirect.com/science/article/pii/S0747717108001818 ) which reduce to Gröbner basis calculations. However, to the best of my knowledge, such algorithms have not been implemented in GAP. > For example, expressing a > symmetric polynomial as a polynomial in the elementary > symmetric polynomials is a particular case of this problem. If you want only this, I append a toy implementation of the basic algorithm. Regards Alexander Hulpke # basic decomposition in elementary symmetric polynomials. ElementarySymmetricDecomposition:=function(pol) local v,r,vars,n,G,e,s,i,m,l,t,j,d,b; v:=OccuringVariableIndices(pol); r:=LeftActingDomain(DefaultRing([pol])); vars:=List(v,x->X(r,x)); n:=Length(v); G:=SymmetricGroup(v); if not ForAll(GeneratorsOfGroup(G),x->OnIndeterminates(pol,x)=pol) then Error("polynomial is not symmetric"); fi; e:=[]; s:=[]; for i in [1..n] do Add(s,X(r,Concatenation("e",String(i)):old)); b:=Product(vars{[1..i]}); Add(e,Sum(Orbit(G,b,OnIndeterminates))); od; r:=rec(basis:=e, symbols:=s); d:=Zero(pol); m:=LeadingMonomial(pol); while Length(m)>0 do; l:=Length(m); t:=LeadingCoefficient(pol)*s[m[l-1]]^m[l]; for j in [l-3,l-5..1] do t:=t*s[m[j]]^(m[j+1]-m[j+3]); od; #Print("Found ",m,"->",t,"\n"); d:=d+t; pol:=pol-Value(t,s,e); m:=LeadingMonomial(pol); od; d:=d+pol; # constant term r.decomposition:=d; return r; end; Example: r:=PolynomialRing(Rationals,["x","y","z","w"]); v:=IndeterminatesOfPolynomialRing(r); c:=Combinations(v,2); p:=Product(List(c,x->(x[1]-x[2])^2)); then ElementarySymmetricDecomposition(p); returns: rec( basis := [ x+y+z+w, x*y+x*z+x*w+y*z+y*w+z*w, x*y*z+x*y*w+x*z*w+y*z*w, x*y*z*w ], decomposition := -27*e1^4*e4^2+18*e1^3*e2*e3*e4-4*e1^3*e3^3-4*e1^2*e2^3*e4+e\ 1^2*e2^2*e3^2+144*e1^2*e2*e4^2-6*e1^2*e3^2*e4-80*e1*e2^2*e3*e4+18*e1*e2*e3^3+1\ 6*e2^4*e4-4*e2^3*e3^2-192*e1*e3*e4^2-128*e2^2*e4^2+144*e2*e3^2*e4-27*e3^4+256*\ e4^3, symbols := [ e1, e2, e3, e4 ] ) _______________________________________________ Forum mailing list Forum@mail.gap-system.org http://mail.gap-system.org/mailman/listinfo/forum
