[GAP Forum] Composition of polynomials

[Alexander Hulpke]

Dear Forum,

> On May 10, 2015, at 5:30 AM, Anvita <anvita21 at 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 ] )