×

A new method for solving algebraic systems of positive dimension. (English) Zbl 0753.13013

Let \(R_ 0\) be a domain with the field of fractions \(K_ 0\) and let \(S_ 0\) be a multiplicative set of \(R_ 0\). For a natural number \(n\), let \(R_ n=R_ 0[X_ 1,\ldots,X_ n]\) and \(P_ n=K_ 0[X_ 1,\ldots,X_ n]\). An algebraic system is a finite set \(E=\{e_ 1,\ldots,e_ k\}\) of \(R_ n\). To each prime ideal \(I\) in \(P_ n\), let \(I_ i=I\cap R_ i\), \(A_ i=R_ i/I_ i\) and \(K_ i\) the field of fractions of \(A_ i\). Then the set of fields \(K_ 0,\ldots,K_ n\) is called the tower associated with the prime ideal \(I\). If \(f\in R_ i\backslash R_{i-1}\), the main variable of \(f\) is defined to be \(X_ i\) and its index to be \(i\). Further, the degree of \(f\) means its degree in \(X_ i\) and the leading coefficient is its coefficient in \(R_{i-1}\) of the highest power of \(X_ i\). The corresponding functions are denoted respectively by main(\(f\)), index(\(f\)), \(\deg(f)\), lc(\(f\)). Using this terminology, the author defines:
Definition 3.2. A triangular set in \(R_ n\) is a list of non-constant polynomials \((f_ 1,\ldots,f_ k)\) in \(R_ n\) satisfying the following for \(i=1,\ldots,k\):
(1) [weak triangular] \(\text{index}(f_ j)<\text{index}(f_ i)\) for \(j<i\); then inductively, let \(K_ j=K_{j-1}[X_ j]/(f_ i)\) if \(\text{index}(f_ i)=j\) and \(qf(K_{j-1}[X_ j])\) (the total quotient ring) otherwise:
(2) [reduced] the degree of \(f_ i\) in main\((f_ j)\) is strictly less than \(\deg(f_ j)\) for \(j=1,\ldots,i-1\);
(3) [normalized] \(\text{index(lc}^ h(f_ i))\notin \{\text{index}(f_ 1),\ldots,\text{index}(f_{i-1})\}\) for any \(h>0\);
(4) [\(R_ 0\)-normalized] if \(\text{lc}^ h(f_ i))\in R_ 0\), then \(\text{lc}^ h(f_ i))\in S_ 0\);
(5) [square-free] the resultant of \(f_ i\) and its derivative with respect to \(\text{main}(f_ i)\) is invertible in \(K_{j-1}\), where \(j=\text{index}(f_ i)\);
(6) [primitive] the coefficients of \(f_ i\) viewed as a multivariate polynomial over \(K_{j-1}[X_ j]\) generate the unit ideal of \(K_{j- 1}[X_ j]\) for all \(j<\text{index}(f_ i)\).
And, the author remarks:
Proposition 3.3. Let \(I\) be a prime ideal, and \(K_ 0,\ldots,K_ n\) the associated tower; if \(K_ i\) is algebraic over \(K_{i-1}\), the minimal polynomial of \(x_ i\) over \(K_{i-1}\) may be chosen in \(R_ i\) such that the set of these polynomials forms a triangular set. There is exactly one such choice.
Proposition 3.4. Let \(f_ 1,\ldots,f_ k\) be a triangular set, \(h=\text{lc}(f_ 1)\cdots\text{lc}(f_ k)\) and let \(I=\{p\in P_ n\mid h^ ep\in(f_ 1,\ldots,f_ k)\}\). Then if the triangular system is associated with a prime ideal \(J\), we have \(I=J\).
Corollary 3.5. The set of generators of the ideal \(I\) above is computable from the triangular set.
Then the author shows how to compute numerically the common zeros of a given prime ideal, using the associated triangular set.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
65H10 Numerical computation of solutions to systems of equations
Full Text: DOI

References:

[1] Buchberger, B., Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleischunssystem, Aequationes Math., 4, 374-383 (1970) · Zbl 0212.06401
[2] Buchberger, B., Gröbner bases: an algorithmic method in polynomial ideal theory, (Bose, Recent Trends in Multidimensional System Theory (1985), Reidel: Reidel Dordrecht) · Zbl 0587.13009
[3] Chistov, A. L.; Grigoriev, D. Yu., Subexponential-time solving systems of algebraic equations, (LOMI Preprints E-9-83 and E-10-83 (1983), Steklov Mathematical Institute: Steklov Mathematical Institute Leningrad) · Zbl 1206.16050
[4] Della Dora, J.; Dicrescenzo, C.; Duval, D., About a new method for computing in algebraic number fields, (Lecture Notes in Computer Science 204. Lecture Notes in Computer Science 204, Proceedings EUROCAL 85, Vol. 2 (1985), Springer: Springer Berlin), 289-290
[5] Dicrescenzo, C.; Duval, D., Algebraic computations on algebraic numbers, (Chenin; etal., Computers and Computing (1985), Masson and Wiley: Masson and Wiley Paris), 54-61 · Zbl 0683.12002
[6] Dicrescenzo, C.; Duval, D., Algebraic extensions and algebraic closure in SCRATCHPAD II, (Proceedings of ISSAC 88. Proceedings of ISSAC 88, Roma. Proceedings of ISSAC 88. Proceedings of ISSAC 88, Roma, Lecture Notes in Computer Science, 258 (1989), Springer: Springer Berlin), 440-446, Symbolic and Algebraic Computation
[7] Duval, D., Diverses questions relatives au calcul formel avec des nombres algebriques, Thèse d’Etat (1987), Grenoble
[8] Huynh, D. T., A superexponential lower bound for Gröbner bases and Church Rosser commutative Thue systems, Inform. and Control, 68, 196-206 (1986) · Zbl 0612.68033
[9] D. Lazard, Solving zero-dimensional algebraic systems, J. Symbolic Comput., to appear.; D. Lazard, Solving zero-dimensional algebraic systems, J. Symbolic Comput., to appear. · Zbl 0753.13012
[10] Trinks, W.; Buchbergers Verfahren, Über B., Systeme algebraischer Gleichungen zu lösen, J. Number Theory, 10, 475-488 (1978) · Zbl 0404.13004
[11] Wen-Tsün, Wu, A zero structure theorem for polynomial equation solving, (Math. Mechanization Research Preprints, 1 (1987), Academica Sinica: Academica Sinica Beijing), 2-12
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.