Primitive polynomial remainder sequences in elimination theory (Q1343108): Difference between revisions

The sequence of contents involved in the primitive polynomial remainder sequence (pprs) used to compute the gcd of two multivariate polynomials provides information about their common zeros. Let \(R:= K[x_1, \dots, x_n ]\) be a ring of polynomials over a field \(K\). If \[ f= \sum^m_{r=0} q_r (x_1, \dots, x_{n-1}) x^r_n\in \mathbb{R}, \qquad q_m\neq 0, \] then \(\text{lc} (f):= q_m\), \(\text{deg} (f):= m\), \(\text{cont} (f):= \text{gcd} (q_0, \dots, q_m)\) and \(\text{pp} (f):= f/\text{cont} (f)\). If \(\text{cont} (f)=1\) then \(f\) is called primitive. For non-zero \(f,g\in \mathbb{R}\) the pseudo-division relation is \[ (\text{lc} (g))^d f= \text{pquo} (f,g) g+\text{prem} (f,g), \qquad \text{deg(prem} (f,g))< \text{deg} (g), \] where \(d:= \max\{ \text{deg} (f)- \text{deg} (g)+ 1,0\}\) and \(\text{deg} (0) :=-1\). Let \(f_1, f_2\in \mathbb{R}\) be primitive non-zero polynomials with \(\text{deg} (f_1)\geq \text{deg} (f_2)\). The pprs of \(f_1\), \(f_2\) is the sequence of non-zero polynomials \(f_1, f_2, \dots, f_k\in \mathbb{R}\) such that \(\text{pp(prem} (f_{i-2}, f_{i-1}))= f_i\), \(i=3, \dots, k\), \(\text{prem} (f_{k-1}, f_k)=0\), and \(f_k= \text{gcd} (f_i, f_{i+1})\). Let \(c_i:= \text{cont(prem} (f_{i-1}, f_i))\), \(i=2, \dots, k-1\), \(l_i:= \text{lc} (f_i )^{\text{deg} (f_{i-1})- \text{deg} (f_i)+1}\), \(i=2, \dots, k\). Then the elimination sequence of \(f_1\), \(f_2\) is \(e_2, \dots, e_{k-1}\in K[x_1, \dots, x_{n-1} ]\) such that \[ e_2:= p_2, \quad e_i:= {{p_i} \over {\text{gcd} (p_i, \prod^{i-1}_{r=2} e_r)}}, \qquad i=3, \dots, k-1, \] where \[ p_i:= \text{squarefree } \Biggl( {{\prod^i_{r=2} c_r} \over {\text{gcd} (\prod^i_{r=2} c_r, \prod^i_{r=2} l_r)}} \Biggr), \qquad i=2, \dots, k-1, \] and \(\text{squarefree} (f)\) denotes the squarefree form of \(f\). Define \(\text{po} (h_1, h_2):= \max \{m\in \mathbb{N} \mid (h^m_1|h_2)\}\), \(h_1, h_2\in \mathbb{R}\). Then Lemma 1. Let \(p\in K[x_1, \dots, x_{n-1} ]\) be irreducible and \(i\in \{2, \dots, k-1\}\). Then \(p\mid e_i\) iff \(i= \min \{2, \dots, k-1\}\) such that \(\text{po} (p, \prod^i_{r=2} c_r)> \text{po} (p, \prod^i_{r=2} l_r)\). Examples and proofs are given in the paper. Lemma 2. Let \(i\in \{3, \dots, k\}\), \(a\in \overline {K}^n\) (where \(\overline {K}\) is the algebraic closure of \(K\)) such that \[ f_1 (a)= f_2 (a) =0 \quad \text{ and }\quad \prod^{i-1}_{r=2} e_r (a) \neq 0. \] Then \(f_i (a) =0\). -- From this follows: Theorem 2. Either \(f_k (a) =0\) or \(\exists i\in \{2, \dots, k-1\}\) such that \(e_i (a)=0\) and \((f_i/ f_k) (a)=0\). Only in the bivariate case \((n=2)\) is every common zero of \(e_i\) and \(f_i\) a common zero of \(f_1\) and \(f_2\). More generally, Theorem 3. Let \(i\in \{2, \dots, k-1\}\), \(a\in \overline {K}^n\). If \(e_i (a)= f_i (a) =0\) and \(f_i (a_1, \dots, a_{n-1}, x_n) \neq 0\) then \(f_1 (a)= f_2 (a) =0\). As a corollary, \(f_i\) can be replaced by \(f_i/ f_k\). The following connection exists between elimination sequences and resultants: Theorem 5. Let \(f_1\), \(f_2\) be relatively prime and \(E:= \prod^{k-1}_{j=2} e_j\). Then (1) \(\exists h_1, h_2\in \mathbb{R}\) and \(d\in \mathbb{N}\) such that \(h_1 f_1+ h_2 f_2= E^d\). (2) \(E\mid\text{squarefree Res} (f_1,f_2)\). (3) If \(\text{lc} (f_1)\) and \(\text{lc} (f_2)\) are relatively prime then \(E= \text{squarefree Res} (f_1, f_2)\). Examples of the use of theorem 2 to solve systems of polynomial equations are presented. This approach is found to be significantly faster than using Gröbner bases. The 3-variable case has been implemented in Maple [\textit{R. Gebauer}, \textit{M. Kalkbrener}, \textit{B. Wall} and \textit{F. Winkler}, CASA: a computer algebra package for constructive algebraic geometry. In: Proc. ISSAC'91, Bonn, Germany, pp. 403-410 (1991)], and is described further in [\textit{M. Kalkbrener}, An algorithm for solving systems of algebraic equations in three variables. In: Springer Texts Monogr. Symbol. Comput. 1995, 7-37 (1995)].