Primitive polynomial remainder sequences in elimination theory (Q1343108): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 14:39, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Primitive polynomial remainder sequences in elimination theory |
scientific article |
Statements
Primitive polynomial remainder sequences in elimination theory (English)
0 references
31 January 1995
0 references
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)].
0 references
multivariate polynomials
0 references
elimination sequence
0 references
polynomial equations
0 references