Talk:Buchberger's algorithm

- "Problem"

I understand you want to keep this simple, but you should say the polynomials are in R = K[x_1...x_n], and that the linear combinations have coefficients in R

- "Why is this problem difficult?"

Another indication for the difficulty of constructing Gröbner bases is that the question of (????) has remained ....

I do not consider it as surprising that solving algebraic equations over the integers is more difficult than solving over the complex numbers. Hence this is not really a good argument. In my opinion, the main difficulty lies in the computational complexity. One can also argue about the "historic" argument, as in the field of differential equations people like Janet and Riquier computed already in the 1910s, 1920s routinely and algorithmically Gröbner bases (of course without using this name). Essentially, they were only missing a rigorous notion of normal form and reduction.

- "Complexity"

It might be useful to emphasize more strongly that you are speaking here about the complexity of the *problem* and not of the *algorithm* itself - meaning that no other algorithm could achieve a better worst-case complexity. Furthermore, it should be said more clearly that in many practical instances one obtains the Gröbner basis in a reasonable time. The way you speak currently about the complexity, nobody without previous experiences would actually think that the bases are practically obtainable.

If one wants to go a little a bit deeper into this topic, one could mention that the crucial quantity is the Castelnuovo-Mumford regularity of the ideal and that it has usually reasonable values for examples of a more geometric origin whereas all the worst-case examples are of a more combinatorial origin (and specifically designed to be "bad").

- "Variations"

One should mention here the involutive algorithm of Gerdt/Blinkov (originally due to Janet/Riquier) representing a highly competitive alternative to Buchberger's algorithm (well, upon closer inspection it is really a variation and not a completely new algorithm).

- "Syzygies"

You should add a short paragraph that via the Schreyer theorem one can also use Buchberger's algorithm to determine a Gröbner basis of the first syzygy module by simply keeping track of the performed reductions. In commutative algebra, this represents a crucial application, as it allows to compute resolutions.

- "non-commutative Gröbner bases"

I am a bit surprised that neither in the article on Gröbner bases nor in this article it is mentioned that the theory and the algorithm remain valid without any changes in a large class of non-commutative polynomial rings (polynomial rings of solvable type, PBW algebras or G-algebras are just a few common names for this class).

- "Implementations"

When describing an algorithm one should say a few words about existing implementations - in particular in specialized systems like Singular, Macaulay or CoCoA.

- "Literature"

It would be interesting to add the lists of all the text books (you know of) describing the algorithm and of all the CAS implementing it.

Main of the books cited in the article on Gröbner bases should also be cited here (or it should at least be mentioned that these books are also useful for understanding Buchberger's algorithm).