__RECURSIVELY.__

- If
*n*= 1 we can use a univariate representation - otherwise we can view
*R*[*X*] as a univariate polynomial ring with a multivariate polynomial ring as coefficient ring, say for instance*R*[*x*_{1},...,*x*_{n-1}][*x*_{n}].

__AS LINEAR COMBINATIONS OF MONOMIALS.__

- By
*monomial*we mean any product of variables. - The product of variable is assumed to be commutative and induces a commutative multiplication for monomials.
- Each polynomial can be viewed as a linear combination
of monomials (with coefficients in
*R*). - Then the polynomial
*p*=*a*_{1}*m*_{1}+^{ ... }+*a*_{p}*m*_{p}.(35)

where the*m*_{i}are pairwise different monomials and the*a*_{i}are nonzero coefficients, can be represented as an aggregate of terms [*a*_{i},*m*_{i}]. - This provides us with a canonical representation.
- To have a fast equality-test, the aggregate of terms
must be
*linear*. In other words, there should be a*first*term, a*second*term, ... Thus this aggregate should better be a*list*or an*array*and the monomials should be totally ordered. - Two types of monomial orderings are frequently used.
- The lexicographical ordering. With
*X*= {*x*>*y*>*z*} we have1 < *z*<^{ ... }<*z*^{n ... }<*y*<*yz*<^{ ... }<*yz*^{n ... }<*y*^{2}<*y*^{2}*z*<^{ ... }<*y*^{2}*z*^{n ... }(36)

- The degree-lexicographical ordering. With
*X*= {*x*>*y*>*z*} we have1 < *z*<*y*<*x*<*z*^{2}<*zy*<*y*^{2}<*zx*<*xy*<*x*^{2}<^{ ... }<(37)

- The lexicographical ordering. With

2003-06-06