Let R be a commutative ring-with-one. We call a free associative algebra A over R a polynomial ring over R. The free generators of A are called indeterminates (to avoid naming conflicts with the word variables which will be used to denote GAP variables only) , they are usually denoted by x_1, x_2, .... The number of indeterminates is called the rank of A. The elements of A are called polynomials. Products of indeterminates are called monomials, every polynomial can be expressed as a finite sum of products of monomials with ring elements in a form like r_{1,0} x_1 + r_{1,1} x_1 x_2 + r_{0,1} x_2 + ⋯ with r_{i,j} ∈ R.
A polynomial ring of rank 1 is called an univariate polynomial ring, its elements are univariate polynomials.
Polynomial rings of smaller rank naturally embed in rings of higher rank; if S is a subring of R then a polynomial ring over S naturally embeds in a polynomial ring over R of the same rank. Note however that GAP does not consider R as a subset of a polynomial ring over R; for example the zero of R (0) and the zero of the polynomial ring (0x^0) are different objects.
Internally, indeterminates are represented by positive integers, but it is possible to give names to them to have them printed in a nicer way. Beware, however that there is not necessarily any relation between the way an indeterminate is called and the way it is printed. See section 66.1 for details.
If R is an integral domain, the polynomial ring A over R is an integral domain as well and one can therefore form its quotient field Q. This field is called a field of rational functions. Again A embeds naturally into Q and GAP will perform this embedding implicitly. (In fact it implements the ring of rational functions over R.) To avoid problems with leading coefficients, however, R must be a unique factorization domain.
Internally, indeterminates are created for a family of objects (for example all elements of finite fields in characteristic 3 are in one family). Thus a variable "x" over the rationals is also an "x" over the integers, while an "x" over GF(3) is different.
Within one family, every indeterminate has a number nr and as long as no other names have been assigned, this indeterminate will be displayed as "x_nr". Indeterminate numbers can be arbitrary nonnegative integers.
It is possible to assign names to indeterminates; these names are strings and only provide a means for printing the indeterminates in a nice way. Indeterminates that have not been assigned a name will be printed as "x_nr".
(Because of this printing convention, the name x_nr is interpreted specially to always denote the variable with internal number nr.)
The indeterminate names have not necessarily any relations to variable names: this means that an indeterminate whose name is, say, "x" cannot be accessed using the variable x, unless x was defined to be that indeterminate.
When asking for indeterminates with certain names, GAP usually will take the first (with respect to the internal numbering) indeterminates that are not yet named, name these accordingly and return them. Thus when asking for named indeterminates, no relation between names and indeterminate numbers can be guaranteed. The attribute IndeterminateNumberOfLaurentPolynomial(indet) will return the number of the indeterminate indet.
When asked to create an indeterminate with a name that exists already for the family, GAP will by default return this existing indeterminate. If you explicitly want a new indeterminate, distinct from the already existing one with the same name, you can add the new option to the function call. (This is in most cases not a good idea.)
gap> R:=PolynomialRing(GF(3),["x","y","z"]); GF(3)[x,y,z] gap> List(IndeterminatesOfPolynomialRing(R), > IndeterminateNumberOfLaurentPolynomial); [ 1, 2, 3 ] gap> R:=PolynomialRing(GF(3),["z"]); GF(3)[z] gap> List(IndeterminatesOfPolynomialRing(R), > IndeterminateNumberOfLaurentPolynomial); [ 3 ] gap> R:=PolynomialRing(GF(3),["x","y","z"]:new); GF(3)[x,y,z] gap> List(IndeterminatesOfPolynomialRing(R), > IndeterminateNumberOfLaurentPolynomial); [ 4, 5, 6 ] gap> R:=PolynomialRing(GF(3),["z"]); GF(3)[z] gap> List(IndeterminatesOfPolynomialRing(R), > IndeterminateNumberOfLaurentPolynomial); [ 3 ]
‣ Indeterminate( R[, nr] ) | ( operation ) |
‣ Indeterminate( R[, name][, avoid] ) | ( operation ) |
‣ Indeterminate( fam, nr ) | ( operation ) |
‣ X( R[, nr] ) | ( operation ) |
‣ X( R[, name][, avoid] ) | ( operation ) |
‣ X( fam, nr ) | ( operation ) |
returns the indeterminate number nr over the ring R. If nr is not given it defaults to 1. If the number is not specified a list avoid of indeterminates may be given. The function will return an indeterminate that is guaranteed to be different from all the indeterminates in the list avoid. The third usage returns an indeterminate called name (also avoiding the indeterminates in avoid if given).
X is simply a synonym for Indeterminate.
gap> x:=Indeterminate(GF(3),"x"); x gap> y:=X(GF(3),"y");z:=X(GF(3),"X"); y X gap> X(GF(3),2); y gap> X(GF(3),"x_3"); X gap> X(GF(3),[y,z]); x
‣ IndeterminateNumberOfUnivariateRationalFunction( rfun ) | ( attribute ) |
returns the number of the indeterminate in which the univariate rational function rfun is expressed. (This also provides a way to obtain the number of a given indeterminate.)
A constant rational function might not possess an indeterminate number. In this case IndeterminateNumberOfUnivariateRationalFunction will default to a value of 1. Therefore two univariate polynomials may be considered to be in the same univariate polynomial ring if their indeterminates have the same number or one if of them is constant. (see also CIUnivPols (66.1-5) and IsLaurentPolynomialDefaultRep (66.21-7)).
‣ IndeterminateOfUnivariateRationalFunction( rfun ) | ( attribute ) |
returns the indeterminate in which the univariate rational function rfun is expressed. (cf. IndeterminateNumberOfUnivariateRationalFunction (66.1-2).)
gap> IndeterminateNumberOfUnivariateRationalFunction(z); 3 gap> IndeterminateOfUnivariateRationalFunction(z^5+z); X
‣ IndeterminateName( fam, nr ) | ( operation ) |
‣ HasIndeterminateName( fam, nr ) | ( operation ) |
‣ SetIndeterminateName( fam, nr, name ) | ( operation ) |
SetIndeterminateName assigns the name name to indeterminate nr in the rational functions family fam. It issues an error if the indeterminate was already named.
IndeterminateName returns the name of the nr-th indeterminate (and returns fail if no name has been assigned).
HasIndeterminateName tests whether indeterminate nr has already been assigned a name.
gap> IndeterminateName(FamilyObj(x),2); "y" gap> HasIndeterminateName(FamilyObj(x),4); false gap> SetIndeterminateName(FamilyObj(x),10,"bla"); gap> Indeterminate(GF(3),10); bla
As a convenience there is a special method installed for SetName that will assign a name to an indeterminate.
gap> a:=Indeterminate(GF(3),5); x_5 gap> SetName(a,"ah"); gap> a^5+a; ah^5+ah
‣ CIUnivPols( upol1, upol2 ) | ( function ) |
This function (whose name stands for "common indeterminate of univariate polynomials") takes two univariate polynomials as arguments. If both polynomials are given in the same indeterminate number indnum (in this case they are "compatible" as univariate polynomials) it returns indnum. In all other cases it returns fail. CIUnivPols also accepts if either polynomial is constant but formally expressed in another indeterminate, in this situation the indeterminate of the other polynomial is selected.
The rational functions form a field, therefore all arithmetic operations are applicable to rational functions.
f + g
f - g
f * g
f / g
gap> x:=Indeterminate(Rationals,1);;y:=Indeterminate(Rationals,2);; gap> f:=3+x*y+x^5;;g:=5+x^2*y+x*y^2;; gap> a:=g/f; (x_1^2*x_2+x_1*x_2^2+5)/(x_1^5+x_1*x_2+3)
Note that the quotient f/g of two polynomials might be represented as a rational function again. If g is known to divide f the call Quotient(f,g) (see Quotient (56.1-9)) should be used instead.
f mod g
For two Laurent polynomials f and g, f mod g is the Euclidean remainder (see EuclideanRemainder (56.6-4)) of f modulo g.
As calculating a multivariate Gcd can be expensive, it is not guaranteed that rational functions will always be represented as a quotient of coprime polynomials. In certain unfortunate situations this might lead to a degree explosion. To ensure cancellation you can use Gcd (56.7-1) on the NumeratorOfRationalFunction (66.4-2) and DenominatorOfRationalFunction (66.4-3) values of a given rational function.
All polynomials as well as all the univariate polynomials in the same indeterminate form subrings of this field. If two rational functions are known to be in the same subring, the result will be expressed as element in this subring.
f = g
Two rational functions f and g are equal if the product Numerator(f) * Denominator(g) equals Numerator(g) * Denominator(f).
gap> x:=Indeterminate(Rationals,"x");;y:=Indeterminate(Rationals,"y");; gap> f:=3+x*y+x^5;;g:=5+x^2*y+x*y^2;; gap> a:=g/f; (x^2*y+x*y^2+5)/(x^5+x*y+3) gap> b:=(g*f)/(f^2); (x^7*y+x^6*y^2+5*x^5+x^3*y^2+x^2*y^3+3*x^2*y+3*x*y^2+5*x*y+15)/(x^10+2\ *x^6*y+6*x^5+x^2*y^2+6*x*y+9) gap> a=b; true
f < g
The ordering of rational functions is defined in several steps. Monomials (products of indeterminates) are sorted first by degree, then lexicographically (with x_1>x_2) (see MonomialGrlexOrdering (66.17-8)). Products of monomials with ring elements ("terms") are compared first by their monomials and then by their coefficients.
gap> x>y; true gap> x^2*y<x*y^2; false gap> x*y<x^2*y; true gap> x^2*y < 5* y*x^2; true
Polynomials are compared by comparing the largest terms in turn until they differ.
gap> x+y<y; false gap> x<x+1; true
Rational functions are compared by comparing the polynomial Numerator(f) * Denominator(g) with the polynomial Numerator(g) * Denominator(f). (As the ordering of monomials used by GAP is invariant under multiplication this is independent of common factors in numerator and denominator.)
gap> f/g<g/f; false gap> f/g<(g*g)/(f*g); false
For univariate polynomials this reduces to an ordering first by total degree and then lexicographically on the coefficients.
All these tests are applicable to every rational function. Depending on the internal representation of the rational function, however some of these tests (in particular, univariateness) might be expensive in some cases.
For reasons of performance within algorithms it can be useful to use other attributes, which give a slightly more technical representation. See section 66.20 for details.
‣ IsPolynomialFunction( obj ) | ( category ) |
‣ IsRationalFunction( obj ) | ( category ) |
A rational function is an element of the quotient field of a polynomial ring over an UFD. It is represented as a quotient of two polynomials, its numerator (see NumeratorOfRationalFunction (66.4-2)) and its denominator (see DenominatorOfRationalFunction (66.4-3))
A polynomial function is an element of a polynomial ring (not necessarily an UFD), or a rational function.
GAP considers IsRationalFunction as a subcategory of IsPolynomialFunction.
‣ NumeratorOfRationalFunction( ratfun ) | ( attribute ) |
returns the numerator of the rational function ratfun.
As no proper multivariate gcd has been implemented yet, numerators and denominators are not guaranteed to be reduced!
‣ DenominatorOfRationalFunction( ratfun ) | ( attribute ) |
returns the denominator of the rational function ratfun.
As no proper multivariate gcd has been implemented yet, numerators and denominators are not guaranteed to be reduced!
gap> x:=Indeterminate(Rationals,1);;y:=Indeterminate(Rationals,2);; gap> DenominatorOfRationalFunction((x*y+x^2)/y); y gap> NumeratorOfRationalFunction((x*y+x^2)/y); x^2+x*y
‣ IsPolynomial( ratfun ) | ( property ) |
A polynomial is a rational function whose denominator is one. (If the coefficients family forms a field this is equivalent to the denominator being constant.)
If the base family is not a field, it may be impossible to represent the quotient of a polynomial by a ring element as a polynomial again, but it will have to be represented as a rational function.
gap> IsPolynomial((x*y+x^2*y^3)/y); true gap> IsPolynomial((x*y+x^2)/y); false
‣ AsPolynomial( poly ) | ( attribute ) |
If poly is a rational function that is a polynomial this attribute returns an equal rational function p such that p is equal to its numerator and the denominator of p is one.
gap> AsPolynomial((x*y+x^2*y^3)/y); x^2*y^2+x
‣ IsUnivariateRationalFunction( ratfun ) | ( property ) |
A rational function is univariate if its numerator and its denominator are both polynomials in the same one indeterminate. The attribute IndeterminateNumberOfUnivariateRationalFunction (66.1-2) can be used to obtain the number of this common indeterminate.
‣ CoefficientsOfUnivariateRationalFunction( rfun ) | ( attribute ) |
if rfun is a univariate rational function, this attribute returns a list [ ncof, dcof, val ] where ncof and dcof are coefficient lists of univariate polynomials n and d and a valuation val such that rfun = x^val ⋅ n / d where x is the variable with the number given by IndeterminateNumberOfUnivariateRationalFunction (66.1-2). Numerator and denominator are guaranteed to be cancelled.
‣ IsUnivariatePolynomial( ratfun ) | ( property ) |
A univariate polynomial is a polynomial in only one indeterminate.
‣ CoefficientsOfUnivariatePolynomial( pol ) | ( attribute ) |
CoefficientsOfUnivariatePolynomial returns the coefficient list of the polynomial pol, sorted in ascending order. (It returns the empty list if pol is 0.)
‣ IsLaurentPolynomial( ratfun ) | ( property ) |
A Laurent polynomial is a univariate rational function whose denominator is a monomial. Therefore every univariate polynomial is a Laurent polynomial.
The attribute CoefficientsOfLaurentPolynomial (66.13-2) gives a compact representation as Laurent polynomial.
‣ IsConstantRationalFunction( ratfun ) | ( property ) |
A constant rational function is a function whose numerator and denominator are polynomials of degree 0.
‣ IsPrimitivePolynomial( F, pol ) | ( operation ) |
For a univariate polynomial pol of degree d in the indeterminate X, with coefficients in a finite field F with q elements, say, IsPrimitivePolynomial returns true if
pol divides X^{q^d-1} - 1, and
for each prime divisor p of q^d - 1, pol does not divide X^{(q^d-1)/p} - 1,
and false otherwise.