The functions described in this file were written to alleviate the
deficiency of GAP3 in manipulating multi-variate polynomials. In GAP3 one
can only define one-variable polynomials over a given ring; this allows
multi-variate polynomials by taking this ring to be a polynomial ring; but,
in addition to providing little flexibility in the choice of coefficients,
this "full" representation makes for somewhat inefficient computation.
The use of the Mvp (MultiVariate Polynomials) described here is faster
than GAP3 polynomials as soon as there are two variables or more. What is
implemented here is actually "Puiseux polynomials", i.e. linear
combinations of monomials of the type x1a1... xnan where
xi are variables and ai are exponents which can be arbitrary rational
numbers. Some functions described below need their argument to involve only
variables to integral powers; we will refer to such objects as "Laurent
polynomials"; some functions require further that variables are raised
only to positive powers: we refer then to "true polynomials". Rational
fractions (RatFrac) have been added, thanks to work of Gwenaëlle Genet (the main difficulty there was to write an algorithm for the
Gcd of multivariate polynomials, a non-trivial task). The coefficients of
our polynomials can in principle be elements of any ring, but some
algorithms like division or Gcd require the coefficients of their arguments
to be invertible.
Mvp( string s [, coeffs v] )
Defines an indeterminate with name s suitable to build multivariate polynomials.
gap> x:=Mvp("x");y:=Mvp("y");(x+y)^3;
x
y
3xy^2+3x^2y+x^3+y^3
If a second argument (a vector of coefficients v) is given, returns
Sum([1..Length(v)],i->Mvp(s)^(i-1)*v[i]).
gap> Mvp("a",[1,2,0,4]);
1+2a+4a^3
Mvp( polynomial x)
Converts the GAP3 polynomial x to an Mvp. It is an error if
x.baseRing.indeterminate.name is not bound; otherwise this is taken as
the name of the Mvp variable.
gap> q:=Indeterminate(Rationals);
X(Rationals)
gap> Mvp(q^2+q);
Error, X(Rationals) should have .name bound in
Mvp( q ^ 2 + q ) called from
main loop
brk>
gap> q.name:="q";;
gap> Mvp(q^2+q);
q+q^2
Mvp( FracRat x)
Returns false if the argument rational fraction is not in fact a Laurent
polynomial. Otherwise returns that polynomial.
gap> Mvp(x/y);
xy^-1
gap> Mvp(x/(y+1));
false
Mvp( elm, coeff)
Build efficiently an Mvp from the given list of coefficients and the list
elm describing the corresponding monomials. A monomial is itself
described by a record with a field .elm containing the list of involved
variable names and a field .coeff containing the list of corresponding
exponents.
gap> Mvp([rec(elm:=["y","x"],coeff:=[1,-1])],[1]);
x^-1y
Mvp( scalar x)
A scalar is anything which is not one of the previous types (like a cyclotomic, or a finite-field-element, etc). Returns the constant multivariate polynomial whose constant term is x.
gap> Degree(Mvp(1));
0
The arithmetic operations +, -, *, / and ^ work for Mvps.
They also have Print and String methods. The operations +, -,
* work for any inputs. / works only for Laurent polynomials, and
may return a rational fraction (see below); if one is sure that the
division is exact, one should call MvpOps.ExactDiv (see below).
gap> x:=Mvp("x");y:=Mvp("y");
x
y
gap> a:=x^(-1/2);
x^(-1/2)
gap> (a+y)^4;
x^-2+4x^(-3/2)y+6x^-1y^2+4x^(-1/2)y^3+y^4
gap> (x^2-y^2)/(x-y);
x+y
gap> (x-y^2)/(x-y);
(x-y^2)/(x-y)
gap> (x-y^2)/(x^(1/2)-y);
Error, x^(1/2)-y is not a polynomial with respect to x
in
V.operations.Coefficients( V, v ) called from
Coefficients( q, var ) called from
MvpOps.ExactDiv( x, q ) called from
fun( arg[1][i] ) called from
List( p, function ( x ) ... end ) called from
...
brk>
Only monomials can be raised to a non-integral power; they can be raised
to a fractional power of denominator b only if GetRoot(x,b) is
defined where x is their leading coefficient. For an Mvp m,
the function GetRoot(m,n) is equivalent to m^(1/n). Raising a
non-monomial Laurent polynomial to a negative power returns a rational
fraction.
gap> (2*x)^(1/2);
ER(2)x^(1/2)
gap> (evalf(2)*x)^(1/2);
1.4142135624x^(1/2)
gap> GetRoot(evalf(2)*x,2);
1.4142135624x^(1/2)
The Degree of a monomial is the sum of the exponent of the variables.
The Degree of an Mvp is the largest degree of a monomial.
gap> a;
x^(-1/2)
gap> Degree(a);
-1/2
gap> Degree(a+x);
1
gap> Degree(Mvp(0));
-1
There exists also a form of Degree taking as second argument a variable
name, which returns the degree of the polynomial in that variable.
gap> p:=x/y;
xy^-1
gap> Degree(p,"x");
1
gap> Degree(p,"y");
-1
gap> Degree(p);
0
The Valuation of an Mvp is the minimal degree of a monomial.
gap> a;
x^(-1/2)
gap> Valuation(a);
-1/2
gap> Valuation(a+x);
-1/2
gap> Valuation(Mvp(0));
-1
There exists also a form of Valuation taking as second argument a
variable name, which returns the valuation of the polynomial in that
variable.
gap> Valuation(x^2+y^2);
2
gap> Valuation(x^2+y^2,"x");
0
gap> Valuation(x^2+y^2,"y");
0
The Format routine formats Mvps in such a way that they can be read
back in by GAP3 or by some other systems, by giving an appropriate option
as a second argument, or using the functions FormatGAP, FormatMaple or
FormatTeX. The String method is equivalent to Format, and gives a
compact display.
gap> p:=7*x^5*y^-1-2;
-2+7x^5y^-1
gap> Format(p);
"-2+7x^5y^-1"
gap> FormatGAP(p);
"-2+7*x^5*y^-1"
gap> FormatMaple(p);
"-2+7*x^5*y^(-1)"
gap> FormatTeX(p);
"-2+7x^5y^{-1}"
The Value method evaluates an Mvp by fixing simultaneously the value
of several variables. The syntax is Value(x, [ string1, value1,
string2, value2, ... ]).
gap> p;
-2+7x^5y^-1
gap> Value(p,["x",2]);
-2+224y^-1
gap> Value(p,["y",3]);
-2+7/3x^5
gap> Value(p,["x",2,"y",3]);
218/3
One should pay attention to the fact that the last value is not a
rational number, but a constant Mvp (for consistency). See the
function ScalMvp below for how to convert such constants to their base
ring.
gap> Value(p,["x",y]);
-2+7y^4
gap> Value(p,["x",y,"y",x]);
-2+7x^-1y^5
Evaluating an Mvp which is a Puiseux polynomial may cause calls to
GetRoot
gap> p:=x^(1/2)*y^(1/3);
x^(1/2)y^(1/3)
gap> Value(p,["x",y]);
y^(5/6)
gap> Value(p,["x",2]);
ER(2)y^(1/3)
gap> Value(p,["y",2]);
Error, : unable to compute 3-th root of 2
in
GetRoot( values[i], d[i] ) called from
f.operations.Value( f, x ) called from
Value( p, [ "y", 2 ] ) called from
main loop
brk>
The function Derivative(p,v) returns the derivative of p with respect
to the variable given by the string v; if v is not given, with respect
to the first variable in alphabetical order.
gap> p:=7*x^5*y^-1-2;
-2+7x^5y^-1
gap> Derivative(p,"x");
35x^4y^-1
gap> Derivative(p,"y");
-7x^5y^-2
gap> Derivative(p);
35x^4y^-1
gap> p:=x^(1/2)*y^(1/3);
x^(1/2)y^(1/3)
gap> Derivative(p,"x");
1/2x^(-1/2)y^(1/3)
gap> Derivative(p,"y");
1/3x^(1/2)y^(-2/3)
gap> Derivative(p,"z");
0
The function Coefficients(p, var) is defined only for Mvps which
are polynomials in the variable var . It returns as a list the list of
coefficients of p with respect to var.
gap> p:=x+y^-1;
y^-1+x
gap> Coefficients(p,"x");
[ y^-1, 1 ]
gap> Coefficients(p,"y");
Error, y^-1+x is not a polynomial with respect to y
in
V.operations.Coefficients( V, v ) called from
Coefficients( p, "y" ) called from
main loop
brk>
The same caveat is applicable to Coefficients as to Value: the
result is always a list of Mvps. To get a list of scalars for
univariate polynomials represented as Mvps, one should use ScalMvp.
Finally we mention the functions ComplexConjugate and evalf which
are defined using for coefficients the Complex and Decimal numbers
of the CHEVIE package.
gap> p:=E(3)*x+E(5);
E5+E3x
gap> evalf(p);
0.3090169944+0.9510565163I+(-0.5+0.8660254038I)x
gap> p:=E(3)*x+E(5);
E5+E3x
gap> ComplexConjugate(p);
E5^4+E3^2x
gap> evalf(p);
0.3090169944+0.9510565163I+(-0.5+0.8660254038I)x
gap> ComplexConjugate(last);
0.3090169944-0.9510565163I+(-0.5-0.8660254038I)x
IsMvp( p )
Returns true if p is an Mvp and false otherwise.
gap> IsMvp(1+Mvp("x"));
true
gap> IsMvp(1);
false
ScalMvp( p )
If p is an Mvp then if p is a scalar, return that scalar,
otherwise return false. Or if p is a list, then apply ScalMvp
recursively to it (but return false if it contains any Mvp which is
not a scalar). Else assume p is already a scalar and thus return p.
gap> v:=[Mvp("x"),Mvp("y")];
[ x, y ]
gap> ScalMvp(v);
false
gap> w:=List(v,p->Value(p,["x",2,"y",3]));
[ 2, 3 ]
gap> Gcd(w);
Error, sorry, the elements of <arg> lie in no common ring domain in
Domain( arg[1] ) called from
DefaultRing( ns ) called from
Gcd( w ) called from
main loop
brk>
gap> Gcd(ScalMvp(w));
1
Variables for Mvp( p )
Returns the list of variables of the Mvp p as a sorted list of strings.
gap> Variables(x+x^4+y);
[ "x", "y" ]
LaurentDenominator( p1, p2, ... )
Returns the unique monomial m of minimal degree such that for all the
Laurent polynomial arguments p1, p2, etc... the product m* pi is
a true polynomial.
gap> LaurentDenominator(x^-1,y^-2+x^4);
xy^2
OnPolynomials( m, p [,vars] )
Implements the action of a matrix on Mvps. vars should be a list of
strings representing variables. If v=List(vars,Mvp), the polynomial p
is changed by replacing in it vi by (v× m)i. If vars is
omitted, it is taken to be Variables(p).
gap> OnPolynomials([[1,2],[3,1]],x+y);
3x+4y
FactorizeQuadraticForm( p)
p should be an Mvp of degree 2 which represents a quadratic form. The
function returns a list of two linear forms of which p is the product if
such forms exist, otherwise it returns false (it returns [Mvp(1),p] if
p is of degree 1).
gap> FactorizeQuadraticForm(x^2-y^2+x+3*y-2);
[ -1+x+y, 2+x-y ]
gap> FactorizeQuadraticForm(x^2+x+1);
[ -E3+x, -E3^2+x ]
gap> FactorizeQuadraticForm(x*y+1);
false
MvpGcd( p1, p2, ...)
Returns the Gcd of the Mvp arguments. The arguments must be true
polynomials.
gap> MvpGcd(x^2-y^2,(x+y)^2);
x+y
MvpLcm( p1, p2, ...)
Returns the Lcm of the Mvp arguments. The arguments must be true
polynomials.
gap> MvpLcm(x^2-y^2,(x+y)^2);
xy^2-x^2y-x^3+y^3
RatFrac( num [,den] )
Build the rational fraction (RatFrac) with numerator num and denominator
den (when den is omitted it is taken to be 1).
gap> RatFrac(x,y);
x/y
gap> RatFrac(x*y^-1);
x/y
The arithmetic operations +, -, *, / and ^ work for RatFracs.
They also have Print and String methods.
gap> 1/(x+1)+y^-1;
(1+x+y)/(y+xy)
gap> 1/(x+1)*y^-1;
1/(y+xy)
gap> 1/(x+1)/y;
1/(y+xy)
gap> 1/(x+1)^-2;
1+2x+x^2
Mvps, RatFracs hav Format and Value methods:
gap> Format(1/(x*y+1));
"1/(1+xy)"
gap> FormatGAP(1/(x*y+1));
"1/(1+x*y)"
gap> Value(1/(x*y+1),["x",2]);
1/(1+2y)
IsRatFrac( p )
Returns true if p is an Mvp and false otherwise.
gap> IsRatFrac(1+RatFrac(x));
true
gap> IsRatFrac(x);
false
gap3-jm