## `Dom::MultivariatePolynomial` -- the domains of multivariate polynomials

#### Introduction

`Dom::MultivariatePolynomial``(Vars, R, ..)` creates the domain of multivariate polynomials in the variable list `Vars` over the commutative ring `R` in distributed representation.

#### Domain

`Dom::MultivariatePolynomial( <Vars <, R <, Order>>>)`

#### Parameters

`Vars` | - | a list of indeterminates. Default: `[x,y,z]`.
`R` | - | a commutative ring, i.e., a domain of category `Cat::CommutativeRing`. Default: `Dom::ExpressionField(normal)`.
`Order` | - | a monomial ordering, i.e., one of the predefined orderings `LexOrder`, `DegreeOrder`, or `DegInvLexOrder` or any object of type `Dom::MonomOrdering`. Default: `LexOrder`.

#### Details

- `Dom::MultivariatePolynomial` represents multivariate polynomials over arbitrary commutative rings.

  All usual algebraic and arithmetical polynomial operations are implemented, including Gröbner basis computation and some classical construction tools used in invariant theory.

- It is highly recommend to use only coefficient rings with unique zero representation. Otherwise it may happen that, e.g., a polynomial division will not terminate or a wrong degree will be returned.

- `Dom::MultivariatePolynomial``(Vars, R, Order)` creates a domain of multivariate polynomials in the variable list `Vars` over a domain `R` of category `Cat::CommutativeRing` in sparse distributed representation with respect to the monomial ordering `Order`.
- `Dom::MultivariatePolynomial``()` creates a polynomial domain in the variable list `[x,y,z]` over the domain `Dom::ExpressionField``(normal)` with respect to the lexicographic monomial ordering.
- `Dom::MultivariatePolynomial``(Vars)` generates the polynomial domain in the variable list `Vars` over the domain `Dom::ExpressionField(normal)` with respect to the lexicographic monomial ordering is created.

- Only commutative coefficient rings of type `DOM_DOMAIN` which inherit from `Dom::BaseDomain` are allowed. If `R` is of type `DOM_DOMAIN` but does not inherit from `Dom::BaseDomain`, the domain `Dom::ExpressionField``(normal)` will be used instead.

- In contrast to the domain `Dom::DistributedPolynomial`, `Dom::MultivariatePolynomial` accepts only identifiers (`DOM_IDENT`) as indeterminates. This restriction enables some further methods described below.
- Please note: For reasons of efficiency not all methods check their arguments, not even at the interactive level. In particular this is true for many access methods, converting methods and technical methods. This may cause strange error messages.

#### Creating Elements

``Dom::MultivariatePolynomial`(Vars, R, Order)(p)`
``Dom::MultivariatePolynomial`(Vars, R, Order)(lm)`

#### Parameters

`p` | - | a polynomial or a polynomial expression.
`lm` | - | list of monomials, which are represented as lists containing the coefficients together with the exponents or exponent vectors.

#### Categories

if `Vars` has a single variable, then
`Cat::UnivariatePolynomial(R)`
else
`Cat::Polynomial(R)`

#### Related Domains

`Dom::DistributedPolynomial`, `Dom::Polynomial`, `Dom::UnivariatePolynomial`

#### Entries

characteristic

  The characteristic of this domain.

coeffRing

  The coefficient ring of this domain as defined by the parameter `R`.

key

  The name of the domain created.

one

  The neutral element w.r.t. `"_mult"`.

ordering

  The monomial ordering defined by the parameter `Order`.

variables

  The list of variables defined by the parameter `Vars`.

zero

  The neutral element w.r.t. `"_plus"`.

#### Method borderedHessianDet: bordered Hessian determinant of a polynomial

- `borderedHessianDet(dom a, dom b <, list of indeterminates v>)`
- - Returns the determinant of the Hessian matrix of `a` bordered by `b` with respect to `v`, which is

        borderedHessianDet(a,b,v)

    as an element of this domain. If `v` is not given, `Vars` will be used instead.

#### Method borderedHessianMat: bordered Hessian matrix of a polynomial

- `borderedHessianMat(dom a, dom b <, list of indeterminates v>)`
- - Returns the Hessian matrix of `a` bordered by `b` with respect to `v` as an element of `Dom::Matrix(dom)`. For the definition of that matrix see method `"borderedHessianDet"`. If `v` is not given, `Vars` will be used instead.

#### Method degLex: compares two polynomials w.r.t. the graded lexicographical order

- `degLex(dom a, dom b)`
- - Returns `-1` if `a` < `b`, `0` if `a` = `b`, `1` if `a` > `b` with respect to the graded lexicographical order, which first uses the degree order and then the lexicographical order for tie-break.

#### Method degRevLex: compares two polynomials w.r.t. the graded reverse lexicographical order

- `degRevLex(dom a, dom b)`
- - Returns `-1` if `a` < `b`, `0` if `a` = `b`, `1` if `a` > `b` with respect to the graded reverse lexicographical order, which first uses the degree order and then the reverse lexicographical order for tie-break.

#### Method hessianDet: Hessian determinant of a polynomial

- `hessianDet(dom a <, list of indeterminates v>)`
- - Returns the determinant of the Hessian matrix of `a` with respect to `v`, which is

        hessianDet(a,v)

    as an element of this domain. If `v` is not given, `Vars` will be used instead.

#### Method hessianMat: Hessian matrix of a polynomial

- `hessianMat(dom a <, list of indeterminates v>)`
- - Returns the Hessian matrix of `a` with respect to `v`, which is

        hessianMat(a,v)

    as an element of `Dom::Matrix(dom)`. If `v` is not given, `Vars` will be used instead.

#### Method homogeneousComponents: list of homogeneous components of a polynomial

- `homogeneousComponents(dom a)`
- - Returns an ordered list of the homogeneous components of `a`, i.e., a list of sums of monomials with the same total degree. The list is sorted in descending total degree order.

#### Method isHomogeneous: tests if a polynomial is homogeneous

- `isHomogeneous(dom a)`
- - Returns `TRUE` if `a` is a homogeneous polynomial and `FALSE` otherwise.

#### Method jacobianDet: Jacobian determinant of a polynomial

- `jacobianDet(list of dom ais <, list of indeterminates v>)`
- - Returns the determinant of the Jacobian matrix of `ais`, with respect to `v` which is

        jacobianDet(ais,v)

    as an element of this domain. If `v` is not given, `Vars` will be used instead.

#### Method jacobianMat: Jacobian matrix of a polynomial

- `jacobianMat(list of dom ais <, list of indeterminates v>)`
- - Returns the Jacobian matrix of `ais`, with respect to `v` which is

        jacobianMat(ais,v)

    as an element of `Dom::Matrix(dom)`. If `v` is not given, `Vars` will be used instead.

#### Method rewriteHomPoly: rewrites a polynomial in terms of other polynomials

- `rewriteHomPoly(dom a, list of dom ais, list of indeterminates v)`
- - Computes a polynomial `g` over the ring `R` in the variable list `v`, such that `g(op(ais)) = a`, i.e., it returns the homogeneous polynomial `a` expressed in terms of the new variable list `v`, which represents the list of homogeneous polynomials `ais` respectively. For this, the sequence (order) of `ais` is used in the algorithm.
  - All the polynomials `a` and `ais` must be homogeneous.
  - The variables of `v` should be new variables.

#### Method rewritePoly: rewrites a polynomial in terms of other polynomials

- `rewritePoly(dom a, list of equations [ai=vi] <, Unsorted>)`
- - computes a polynomial `g` over the ring `R` in the variables `vi` such that `g(...,ai,...)=a`, where the `ai`'s are homogeneous polynomials of this domain, and returns the polynomial `a` expressed in terms of the new variables `vi`, or `FAIL` if this is not possible.
  - This method can be used for representing a polynomial with respect to a given polynomial basis.
  - When option `Unsorted` is given, the list `[ai=vi]` is not sorted. Otherwise, in a precomputation step this list will be sorted in the `ai`'s w.r.t. the graded lexicographical order (`"degLex"`).
  - Please note: the algorithm depends on the order of `Vars` and `ais`.
  - All the polynomials `ai` must be homogeneous.
  - The variables of `vi` should be new variables.

#### Method order: compares two polynomials w.r.t. a given order

- `order(dom a, dom b, `Dom::MonomOrdering` o)`
- - Compares `a` and `b` with respect to the monomial order `o`: If `a` > `b` then 1 is returned, if `a` = `b` then 0 is returned and if `a` < `b` then -1 is returned.

#### Method sortList: sorts a list of polynomials w.r.t. a given order

- `sortList(list of dom ais, `Dom::MonomOrdering` o )`
- - Sorts the polynomials `ais` with respect to the monomial order `o` in descending order.
  - This sorting method may be not stable if `o` is not a total order.

#### Method stableSort: sorts a list of polynomials w.r.t. a given order

- `stableSort(list of dom ais, `Dom::MonomOrdering` o )`
- - Sorts the polynomials `ais` with respect to the monomial order `o` in descending order.
  - This sorting method is stable, even if `o` is not a total order.

#### Example 1

To create the ring of multivariate polynomials in `x`, `y` and `z` over the rationals one may define

    >> MP := Dom::MultivariatePolynomial([x, y, z], Dom::Rational)

          Dom::MultivariatePolynomial([x, y, z], Dom::Rational, LexOrder)

The elementary symmetric polynomials of this domain are

    >> s1 := MP(x + y + z)

                                     x + y + z

    >> s2 := MP(x*y + x*z + y*z)

                                  x y + x z + y z

    >> s3:=MP(x*y*z)

                                       x y z

A polynomial is called symmetric if it remains unchanged under every possible permutation of variables as, e.g.:

    >> s3=s3(MP(y), MP(z), MP(x))

                                   x y z = x y z

These polynomials arise naturally in studying the roots of a polynomial. To show this, we first have to create an univariate polynomial, e.g., in `U` over `MP`, and generate a polynomial in `U` with roots in `x`, `y` and `z`.

    >> UP:=Dom::UnivariatePolynomial(U, MP)

          Dom::UnivariatePolynomial(U, Dom::MultivariatePolynomial(

             [x, y, z], Dom::Rational, LexOrder), LexOrder)

    >> f := UP((U - x)*(U - y)*(U - z))

                 3                  2
                U  + (- x - y - z) U  + (x y + x z + y z) U - x y z

    >> UP(U^3)-s1*UP(U^2)+s2*UP(U)+(-1)^3*s3

                 3                  2
                U  + (- x - y - z) U  + (x y + x z + y z) U - x y z

This exemplifies that the coefficients of `f` are (elementary) symmetric polynomials in its roots.

From the fundamental theorem of symmetric polynomials we know that every symmetric polynomial can be written uniquely as a polynomial in the elementary symmetric polynomials. Thus we can rewrite the following symmetric polynomial `s` in the elementary symmetric polynomials `s1`, `s2` and `s3`,

    >> s:=MP(x^3*y+x^3*z+x*y^3+x*z^3+y^3*z+y*z^3)

                       3      3        3      3    3        3
                      x  y + x  z + x y  + x z  + y  z + y z

    >> S:=MP::rewritePoly(s,[s1=S1,s2=S2,s3=S3])

                                2                  2
                              S1  S2 - S1 S3 - 2 S2

where these polynomials are represented by the three new variables `S1`, `S2` and `S3` respectively. To see that this new polynomial `S` in the new variables indeed represents the old original polynomial `s`, we simply have to plug in the three elementary symmetric polynomials into `S`:

    >> S(s1,s2,s3,Expr)

                       3      3        3      3    3        3
                      x  y + x  z + x y  + x z  + y  z + y z

When one has a given list of polynomials, e.g., like:

    >> l:=[3*s1,2*s1,s1,s3]

               [3 x + 3 y + 3 z, 2 x + 2 y + 2 z, x + y + z, x y z]

and one wants to sort them in an appropriate order, one may use one of the following two methods.

    >> MP::sortList(l,Dom::MonomOrdering(DegLex(3)))

               [x y z, 2 x + 2 y + 2 z, x + y + z, 3 x + 3 y + 3 z]

    >> MP::stableSort(l,Dom::MonomOrdering(DegLex(3)))

               [x y z, 3 x + 3 y + 3 z, 2 x + 2 y + 2 z, x + y + z]

In the first sorted list the order of the three polynomials of the same degree has changed, while with the second method this order remains stable.

#### Example 2

Let G⊆GL(n,k) be a finite (matrix) subgroup of the general linear group. Then a polynomial f∈k[x1,...,xn] is called invariant under G, if for all A∈G f(x)=f(A·x) where x=(x1,...,xn).
The symmetric polynomials `s1`, `s2` and `s3` from the previous example are invariants under the symmetric group S3. In fact, these three fundamental invariants yet generate the whole ring of invariants of S3.

Now let us examine the invariants of the famous icosahedral group. One may find a representation of this group in H. F. Blichfeldt: Finite collineation groups, University of Chicago Press, 1917. on page 73. S'= ε^3 0
0 ε^2 , U'= 0 1
-1 0 , T'= α β
β -α, ε^5=1, α=(ε^4-ε)/(√5), β=(ε^2-ε^3)/(√5) The group is generated from these three matrices, has 120 elements and is thus a finite subgroup, even of the special linear group SL(2,Q(ε)). It is also well known that I_1= x 1 x 2 11 -11 x 1 6 x 2 6 -x 1 11 x 2 is a fundamental invariant of degree 12 of this group. To declare I1 in MuPAD one has first to define the polynomial domain.

    >> MP:=Dom::MultivariatePolynomial([x1,x2],Dom::Rational)

          Dom::MultivariatePolynomial([x1, x2], Dom::Rational, LexOrder)

    >> i1:=MP(x1*x2^(11)-11*x1^6*x2^6-x1^(11)*x2)

                             11           6   6        11
                         - x1   x2 - 11 x1  x2  + x1 x2

From the invariant I1 one can compute a further fundamental invariant I2 with

    >> i2:=MP::hessianDet(i1)

                  20           15   5           10   10
          - 121 x1   + 27588 x1   x2  - 59774 x1   x2   -

                     5   15         20
             27588 x1  x2   - 121 x2

But to get more simple coefficients we choose I2 as

    >> i2:=-1/121*MP::hessianDet(i1)

               20         15   5         10   10         5   15     20
             x1   - 228 x1   x2  + 494 x1   x2   + 228 x1  x2   + x2

instead. Similar we obtain a third fundamental invariant I3 with

    >> i3:=1/20*MP::jacobianDet([i1,i2])

            30         25   5           20   10           10   20
          x1   + 522 x1   x2  - 10005 x1   x2   - 10005 x1   x2   -

                   5   25     30
             522 x1  x2   + x2

In contrast to the symmetric groups, where all invariants can be uniquely represented by the fundamental invariants, the fundamental invariants of this group have an algebraic relation, a so-called syzygy between them. It is possible to represent I32 in two ways:

    >> MP::rewritePoly(i3^2,[i1=I1,i2=I2,i3=I3])

                                          5     3
                                 - 1728 I1  + I2

    >> MP::rewritePoly(i3^2,[i1=I1,i2=I2,i3=I3],Unsorted)

                                          2
                                        I3

And hence we get the syzygy:

    >> MP::rewritePoly(i3^2,[i1=I1,i2=I2,i3=I3],Unsorted)-
       MP::rewritePoly(i3^2,[i1=I1,i2=I2,i3=I3]) = 0

                                    5     3     2
                             1728 I1  - I2  + I3  = 0

#### Super-Domain

`Dom::DistributedPolynomial`

#### Axioms

if `R` has `Ax::normalRep`, then
`Ax::normalRep`
if `R` has `Ax::canonicalRep`, then
`Ax::canonicalRep`

#### Background

- The algorithms used for rewriting polynomials, i.e., for expressing polynomials in terms of some other homogeneous polynomials stem from
  - Winfried Fakler. Algorithmen zur symbolischen Lösung homogener linearer Differentialgleichungen. Diplomarbeit, Universität Karlsruhe (1994).

#### Changes

- `Dom::MultivariatePolynomial` is a new domain.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000