Talk:Gröbner basis

From Wikipedia, the free encyclopedia

If I'm not mistaken, this algorithm generalizes not only Euclid's algorithm but also Gaussian elimination and the simplex algorithm. I don't know enough about it to incorporate those topics into the article. Can someone do that? 128.101.13.104 02:15, 6 Nov 2003 (UTC)

I think you're mistaken about the simplex algorithm. I'm pretty sure that it is wasteful to do Gauss-Jordan elimination this way. In fact it seems to be like doing numerous eliminations in parallel.

Charles Matthews 09:26, 6 Nov 2003 (UTC)

I think the rewrite of the article has made it less accessible. For example, trying to give an exact characterisation of a GB in the opening sentence means that the technical density is immediately at a maximum.

Charles Matthews 11:13, 9 Jun 2004 (UTC)

Contents

[edit] About polynomial systems

The text implies that a polynomial system with finitely many solutions can be "solved" using the Gröbner basis. But if the system has zero solutions, then this technique won't always demonstrate that fact, right? Perhaps the article should say "If the system has a finite nonzero number of solutions..." or some such. I'd change it myself, but I'm a bit new to Gröbner bases, and would like some assurance that I'm right. Staecker 17:46, 25 Jun 2005 (UTC)

In fact, if there is no solution, then by the Nullstellensatz the polynomial 1 belongs to the ideal, and since its leading monomial is 1 and is the smallest element in every term order, the reduced minimal GB will be exactly {1}, so You would know. For the other thing, look up lexikographic order, FGLM (Jean C. Faugere is the F), RUR by Fabrice Rouillier, also called "geometric solution" in other contexts. A first result on finite numbers of solutions is that for each variable there has to be a polynomial in the GB with a pure power of said variable as leading monomial.--LutzL 14:28, 29 August 2005 (UTC)

[edit] Gröbner basis and Hironaka

Copied from User talk:LutzL for possible use by others. --LambiamTalk 14:49, 5 May 2006 (UTC)
 (Lambiam adressing LutzL:) Hi. Concerning your recent edit of Gröbner basis, I am not sure that Hironaka's theory of "standard bases" is exactly the same. See for example Joachim Apel, Division of entire functions by polynomial ideals, in Proc. AAECC 11, LNCS 948 (1995), pp. 82-95. So if you agree but think the addition is nevertheless important, I propose that you change the text into something like: "In 1964, at almost the same time and independently, Heisuke Hironaka had developed a closely related theory, which he called standard bases." I'm not sure how close this is to your areas of expertise, but I you have interest, time and patience, perhaps you could also add some of this to the Hironaka article, putting it in context, and if possible cite the references as provided by Apel's paper. Cheerio. LambiamTalk 13:46, 3 May 2006 (UTC)

As I understand it now, the standard bases are defined for ideals in the ring of Puisseux series. Thus they contain Gröbner bases as a special case. The real contribution of Buchberger to the fundamentals is the proof that his algorithm stops in finite time. Perhaps it should be mentioned somewhere that the idea comes from the non-constructive proof by Hilbert of the Basissatz (Kronecker had a constructive proof, but only formulated for bivariate polynomials) -- No, I'm not an expert in the whole of the topic of Gröbner bases. They are interesting to me in the aspect of their inefficiency. I got most of my knowledge from Gethgen/vonzur Gathen: Modern Algebra, where they mention H. Hironaka in the second sentence of the introduction. And from M. Guisty: Bases standard, élimination et complexité, notes of a lecture given at X, where some propositions are attributed to Hironaka.--LutzL 07:29, 5 May 2006 (UTC)

I'm not an expert either and I don't have access to a library, so I wouldn't be comfortable making any changes of substance. I'll copy this exchange to the talk page of the article in the hope that a next reader can do something with it. --LambiamTalk 14:43, 5 May 2006 (UTC)

[edit] Definition of Reduced Gröbner Bases

The definition of reduced bases didn't make sense. As it was written, it referred to the "ideal generated by the leading coefficient", which is always all of R. Therefore, the condition for a reduced basis could never be satisfied.

I changed "coefficient" to "term". Now at least it at least makes sense, although I don't have a reference to be sure whether it is correct. If anyone would care to look it up and check it that would be good. When I find a reference I will do so. Heatkernel 10:58, 8 May 2006 (UTC)

[edit] Example of Groebner basis

Hello. I am aware that a Groebner basis, in general, may be tremendously verbose. Even so I wonder if we can give some kind of example. A set of examples which shows the increasingly verbose Groebner bases for a progression of simple problems would be terrific. 207.174.201.18 21:15, 23 June 2006 (UTC)

[edit] Solving equations

Solving equations is the elementary application which, from my point of view, motivates the theory. The formulas, { f1[x1, ..., xn] = a1, ..., fm[x1, ..., xn] = am} and g(xn) = b, can be simplified into {f1[x1, ..., xn] = 0, ..., fm[x1, ..., xn] = 0} and g(xn) = 0 . For example a circle cutting a straight line: x2+y2−4 = y−1 = 0. You do not need to understand ideals in order to understand the problem of solving systems of equations with several unknowns. Bo Jacoby 08:17, 8 August 2007 (UTC).

Hi Bo, nice to see You again. And now, what was the point? The main application of GB, as it is my experience, is to prove structural theorems in algebraic geometry. Such as estimates on the Hilbert polynomial, number of rational points etc. Your point is valid, but the number of solvable systems is rather small.--LutzL 06:45, 9 August 2007 (UTC)

Thanks LutzL! Regarding Gröbner bases I am a pupil and not a teacher. I may have got it wrong. I was looking for methods for solving algebraic equations in several unknowns. It is a practical and elementary problem. If the system of equations is fm[xn] = 0, where each fm is a polynomial in the variables xn, then any polynomial, p, in the ideal spanned by the fm makes an equation p[xn] = 0. Elimination of variables is construction of a system of algebraic equations, pn[xn] = 0, each in one unknown. Algebraic equations in one unknown can be solved numerically by the Durand-Kerner method, and so we are done. Am I on the track? Bo Jacoby 14:51, 9 August 2007 (UTC).

[edit] Earliest examples

An IP hinted at a paper "Les Invariants des formes binaires" in Jour. Des Mathematiques Pure and Applique'es, (1900), se'rie 5/ T 6, pp 141-156.", which is available from a digitisation project site (PDF). There exists an english translation at a Gröbner bibliography project (PDF) which claims it as an early example of a computed Gröbner basis. Perhaps someone might include in in the article.--LutzL (talk) 09:37, 6 December 2007 (UTC)