3.2 Monomial orderings and division algorithm

Monomial orderings are crucial for comparing and manipulating polynomials. They provide a systematic way to arrange terms, which is essential for algorithms like polynomial division. Understanding these orderings helps us work with complex polynomials and solve equations.

The division algorithm for polynomials extends the familiar process of dividing numbers to the world of polynomials. It allows us to break down complicated polynomials into simpler parts, making it easier to solve equations and study algebraic structures.

Monomial Orderings

Definition and Properties

• A monomial ordering is a total order on the set of monomials in a polynomial ring, which is compatible with the multiplication of monomials
• Compatibility with multiplication means that if $m_1 \leq m_2$, then $m_1 \cdot m \leq m_2 \cdot m$ for any monomial $m$
• A monomial ordering is called a well-ordering if every strictly decreasing sequence of monomials eventually terminates
  • This is a necessary condition for the division algorithm to work

Types of Monomial Orderings

• The three main types of monomial orderings are lexicographic order (lex), graded lexicographic order (grlex), and graded reverse lexicographic order (grevlex)
• Lexicographic order (lex) compares monomials by comparing their exponents from left to right, similar to how words are ordered in a dictionary
  • Example: $x^2y \leq xy^3$ in lex order because $2 < 3$
• Graded lexicographic order (grlex) first compares the total degree of the monomials, and if the degrees are equal, it then uses lexicographic order to break ties
  • Example: $x^2y^2 \leq xy^3$ in grlex order because $2+2 = 4 < 1+3 = 4$
• Graded reverse lexicographic order (grevlex) also compares the total degree of monomials first, but if the degrees are equal, it uses reverse lexicographic order to break ties
  • Example: $x^2y^2 \leq x^3y$ in grevlex order because $2+2 = 4 = 3+1$ and $2 < 3$

Applying Orderings to Polynomials

Leading Terms, Coefficients, and Monomials

• Given a monomial ordering, the leading term of a polynomial is the term with the highest monomial according to the chosen ordering
• The leading coefficient of a polynomial is the coefficient of the leading term
• The leading monomial of a polynomial is the monomial part of the leading term
  • Example: For $f = 3x^2y + 2xy^2 - y^3$, under lex order, the leading term is $3x^2y$, the leading coefficient is $3$, and the leading monomial is $x^2y$

Comparing Polynomials

• To compare two multivariate polynomials using a monomial ordering, compare their leading terms according to the chosen ordering
  • Example: Let $f = 3x^2y + 2xy^2 - y^3$ and $g = x^3 - 2x^2y + xy$. Under lex order, $f \leq g$ because $x^2y \leq x^3$
• The choice of monomial ordering can affect the leading term, leading coefficient, and leading monomial of a multivariate polynomial
  • Example: For $f = 3x^2y + 2xy^2 - y^3$, under grlex order, the leading term is $-y^3$, the leading coefficient is $-1$, and the leading monomial is $y^3$

Polynomial Division Algorithm

Algorithm Description

• The polynomial division algorithm is a generalization of the univariate polynomial division algorithm to multivariate polynomials using a chosen monomial ordering
• The algorithm divides a polynomial $f$ by a set of polynomials $\{g_1, \ldots, g_s\}$ and returns a remainder $r$ and quotients $\{q_1, \ldots, q_s\}$ such that $f = q_1g_1 + \ldots + q_sg_s + r$, where $r$ is reduced with respect to $\{g_1, \ldots, g_s\}$
• A polynomial $r$ is reduced with respect to a set of polynomials $\{g_1, \ldots, g_s\}$ if no term of $r$ is divisible by any of the leading terms of $\{g_1, \ldots, g_s\}$

Algorithm Steps

• The division algorithm proceeds by iteratively canceling the leading term of $f$ by the leading term of one of the divisor polynomials until no further reduction is possible
  1. Initialize the remainder $r$ to $f$ and the quotients $\{q_1, \ldots, q_s\}$ to zero
  2. While $r \neq 0$ and $r$ is not reduced with respect to $\{g_1, \ldots, g_s\}$:
     • Choose a polynomial $g_i$ whose leading term divides the leading term of $r$
     • Update $q_i := q_i + \frac{LT(r)}{LT(g_i)}$ and $r := r - \frac{LT(r)}{LT(g_i)} \cdot g_i$
  3. Return the remainder $r$ and quotients $\{q_1, \ldots, q_s\}$

Monomial Ordering Choice

• The choice of monomial ordering determines the leading terms of the polynomials and thus affects the outcome of the division algorithm
  • Example: Dividing $f = x^2y + xy^2 + y^3$ by $g = xy - 1$ yields different results under lex and grlex orders:
    • Under lex order: $f = (xy + y^2) \cdot g + y$
    • Under grlex order: $f = (x + y) \cdot g + y$

Orderings Impact on Division

Remainder and Quotient Dependence

• Different monomial orderings can lead to different remainders and quotients in the polynomial division algorithm
  • Example: Dividing $f = x^2y + xy^2 + y^3$ by $g_1 = xy - 1$ and $g_2 = y^2 - 1$ yields different results under lex and grlex orders:
    • Under lex order: $f = (x + y) \cdot g_1 + (1) \cdot g_2 + 2$
    • Under grlex order: $f = (x) \cdot g_1 + (y) \cdot g_2 + x + y$

Computational Efficiency

• The choice of monomial ordering can affect the efficiency of the division algorithm, as some orderings may lead to fewer reduction steps than others
• Graded reverse lexicographic order (grevlex) is often used in practice due to its computational efficiency and desirable properties for Gröbner basis computations

Gröbner Bases

• Gröbner bases, which are a key concept in computational algebraic geometry, depend on the choice of monomial ordering used in the division algorithm
• The division algorithm with respect to a Gröbner basis always yields a unique remainder, regardless of the order in which the divisor polynomials are used
  • Example: If $\{g_1, \ldots, g_s\}$ is a Gröbner basis under a given monomial ordering, then dividing any polynomial $f$ by $\{g_1, \ldots, g_s\}$ will always result in the same remainder $r$, regardless of the order in which the $g_i$ are used in the division algorithm