Polynomial Division

Definition nw. Let \(h = \sum c_\alpha x^\alpha \in \mathbb{F}[\mathbf{x}] \setminus \{0\}\) be a nonzero polynomial, \(F\) a subset of \(\mathbb{F}[\mathbf{x}] \setminus \{0\}\), and let \(\succeq\) be a monomial order on \(\mathcal{M}\).

  1. The multidegree of \(h\) is \(\mathrm{multideg}(h) = \max(\alpha \in \mathbb{N}_0^n \mid c_\alpha \neq 0)\). The maximum is taken with respect to \(\succeq\).
  2. The leading coefficient of \(h\) is \(\mathrm{LC}(h) = c_{\mathrm{multideg}(h)} \in \mathbb{F}\).
  3. \(\mathrm{LC}(F) = \{\mathrm{LC}(f) \mid f \in F\}\).
  4. The leading monomial of \(h\) is \(\mathrm{LM}(h) = x^{\mathrm{multideg}(h)}\).
  5. \(\mathrm{LM}(F) = \{\mathrm{LM}(f) \mid f \in F\}\).
  6. The leading term of \(h\) is \(\mathrm{LT}(h) = \mathrm{LC}(h) \cdot \mathrm{LM}(h)\).
  7. \(\mathrm{LT}(F) = \{\mathrm{LT}(f) \mid f \in F\}\).
  8. \(M(f)\) denotes the set of all monomials in \(f\), and \(M(F) = \bigcup_{f \in F} M(f)\).

Example ni. Let \(f = xy^2z^3 + xy^3 \in \mathbb{F}[x, y, z]\) be a polynomial under the lexicographic order. Then \(\mathrm{multideg}(f) = (1, 3, 0)\), \(\mathrm{LC}(f) = 1\), \(\mathrm{LM}(f) = xy^3\), \(\mathrm{LT}(f) = xy^3\), and \(M(f) = \{xy^2z^3, xy^3\}\).

Univariate division provides an introduction to multivariate division and is used in the construction of finite fields.

Theorem ns. (Univariate Division.) Let \(g(x) \in \mathbb{F}[x]\) be a univariate polynomial. Then every \(f(x) \in \mathbb{F}[x]\) can be written as \(f(x) = q(x) g(x) + r(x)\), where \(q(x), r(x) \in \mathbb{F}[x]\) are unique and either \(r(x) = 0\) or \(\deg(r(x)) < \deg(g(x))\) (Cox 2015).

We can use the following algorithm for finding the polynomials \(q\) and \(r\).

Algorithm d1. Univariate polynomial division.

Input: univariate polynomials \(g, f\).
Output: univariate polynomials \(q, r\).

  1. \(q \gets 0\), \(r \gets f\).
  2. while \(r \neq 0\) and \(\mathrm{LT}(g)\) divides \(\mathrm{LT}( r)\):
    • \(q \gets q + \mathrm{LT}( r) / \mathrm{LT}(g)\).
    • \(r \gets r - (\mathrm{LT}( r) / \mathrm{LT}(g)) \cdot g\).
  3. return \(q, r\).

Example du. Let \(f(x) \in \mathbb{F}[x]\) be a univariate polynomial of degree \(d = \deg(f(x))\) and \(\langle f(x) \rangle\)the ideal generated by \(f(x)\). The elements of the quotient ring \(\mathbb{F}[x] / \langle f(x) \rangle\)can be written as univariate polynomials \(c_{d-1} x^{d-1} + \ldots + c_1 x + c_0\) in \(\mathbb{F}[x]\) of degree less than \(d\). In this quotient ring, we use standard addition. However, we define multiplication by applying Theorem ns: given two univariate polynomials \(g(x), h(x)\), there exist \(q(x), r(x)\) such that \(g(x) h(x) = q(x) f(x) + r(x)\), where \(\deg(r(x)) < \deg(f(x)) = d\). We take \(r(x)\) as the product of \(g(x)\) and \(h(x)\).

Proposition nz. Let \(\mathbb{F}\) be a finite field of order \(q = p^n\) and \(f(x) \in \mathbb{F}[x]\) a univariate polynomial of degree \(d\). The elements of the quotient ring \(\mathbb{F}[x] / \langle f(x) \rangle\)can be written as polynomials of degree less than \(d\), with multiplication defined via the remainder on division by \(f(x)\). This quotient ring is a finite field of order \(q^d = p^{nd}\) if and only if \(f(x)\) is irreducible over \(\mathbb{F}[x]\) (Lidl and Niederreiter 1994).

Proposition na. Let \(f \in \mathbb{F}[\mathbf{x}]\) be irreducible over the field \(\mathbb{F}\). Then there exists an extension of \(\mathbb{F}\) containing a root of \(f\).

Proof. Consider the finite field \(\mathbb{E} = \mathbb{F}[\mathbf{x}] / \langle f \rangle\). The elements of \(\mathbb{E}\) are the cosets \([r] = r + \langle f \rangle\)with \(r \in \mathbb{F}[\mathbf{x}]\). For any \(a \in \mathbb{F}\), we can obtain a coset \([a]\) determined by the constant polynomial \(a\). The mapping \(a \mapsto [a]\) gives an isomorphism from \(\mathbb{F}\) onto a subfield \(\mathbb{F}’\) of \(\mathbb{E}\), so that \(\mathbb{F}’\) may be identified with \(\mathbb{F}\). Particularly, \(\mathbb{E}\) can be seen as an extension of \(\mathbb{F}\). Now, for every \(r(x) = a_0 + a_1 x + \cdots + a_m x^m \in \mathbb{F}[\mathbf{x}]\) we have \([r] = [a_0] + [a_1][x] + \cdots + [a_m][x]^m = a_0 + a_1[x] + \cdots + a_m[x]^m\) by the rules for operating with cosets and the identification \([a_i] = a_i\). Hence, every element of \(\mathbb{E}\) can be written as a polynomial expression in \([x]\) with coefficients in \(\mathbb{F}\). We say that the extension field \(\mathbb{E}\) is obtained by adjoining \([x]\) and denote it \(\mathbb{F}([x])\). Note that if \(f(x) = b_0 + b_1 x + \cdots + b_n x^n\), then \(f([x]) = b_0 + b_1[x] + \cdots + b_n[x]^n = [f] = [0]\), so that \([x]\) is a root of \(f\).

We use multivariate division in the description of algorithms for computing Gröbner bases.

Theorem n3. (Multivariate Division.) Let \(\succeq\) be a monomial order on \(\mathcal{M}\) and let \(F = (f_1, \ldots, f_m)\) be an ordered \(m\)-tuple of polynomials in \(\mathbb{F}[\mathbf{x}]\). Then every \(f \in \mathbb{F}[\mathbf{x}]\) can be written as \[f = q_1 f_1 + \cdots + q_m f_m + r,\] where \(q_i, r \in \mathbb{F}[\mathbf{x}]\), and either \(r = 0\) or \(r\) is a linear combination, with coefficients in \(\mathbb{F}\), of monomials, none of which is divisible by any of \(\mathrm{LT}(f_1), \ldots, \mathrm{LT}(f_m)\). We call \(r\) a remainder of \(f\) on division by \(F\) and denote it \(\overline{f}^F\). Furthermore, if \(q_i f_i \neq 0\), then \(\mathrm{LM}(f) \succeq \mathrm{LM}(q_i f_i)\) (Cox 2015).

We can use the following algorithm for finding the polynomials \(q_i\) and \(r\).

Algorithm dw. Multivariate polynomial division.

Input: polynomials \(f_1, \ldots, f_m, f\).
Output: polynomials \(q_1, \ldots, q_m, r\).

  1. \(q_i \gets 0\) for all \(i\), \(r \gets 0\), \(p \gets f\).
  2. while \(p \neq 0\):
    • \(i \gets 1\), \(\mathit{divisionoccured} \gets \mathit{False}\).
    • while \(i \le m\) and \(\mathit{divisionoccured} = \mathit{False}\):
      • if \(\mathrm{LT}(f_i)\) divides \(\mathrm{LT}(p)\):
        • \(q_i \gets q_i + \mathrm{LT}(p) / \mathrm{LT}(f_i)\).
        • \(p \gets p - (\mathrm{LT}(p) / \mathrm{LT}(f_i)) \cdot f_i\).
        • \(\mathit{divisionoccured} \gets \mathit{True}\).
      • else \(i \gets i + 1\).
    • if \(\mathit{divisionoccured} = \mathit{False}\):
      • \(r \gets r + \mathrm{LT}(p)\), \(p \gets p - \mathrm{LT}(p)\).
  3. return \(q_1, \ldots, q_m, r\).

References

Cox, David. 2015. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Cham: Springer.
Lidl, Rudolf, and Harald Niederreiter. 1994. Introduction to Finite Fields and Their Applications. Cambridge university press.
math
Dec 11, 2020