Multivariate polynomials.

Let $R$ be a ring and $X = \{ x_1, \ldots, x_n\}$ be a finite set of variables. The multivariate polynomial ring $R[X]$ can be implemented in different ways.

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, \ldots, x_{n-1}][x_n]$ .

This implies to choose an ordering on the variables and a representation for univariate polynomials.

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 + \cdots + a_p m_p.$$ (36)

  
  
  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 have

    $$1 < z < \cdots < z^n \cdots < y < y z < \cdots < y z^n \cdots < y^2 < y^2 z < \cdots < y^2 z^n \cdots$$ (37)

    
    

  • The degree-lexicographical ordering. With $X = \{ x > y > z\}$ we have

    $$1 < z < y < x < z^2 < zy < y^2 < zx < xy < x^2 < \cdots <$$ (38)