Math 2.0

Commutative algebra Definition

Buchberger's algorithm

Builds on FieldPolynomial ringMonomial orderLeast common multipleMultivariate division algorithmGröbner basisMonomial idealHilbert's basis theorem

Definition

Let kk be a field, let S=k[x1,…,xn]S = k[x_1, \ldots, x_n] be the polynomial ring, and fix a monomial order. For nonzero f∈Sf \in S, let LT⁡(f)\operatorname{LT}(f) be its leading term and LM⁡(f)\operatorname{LM}(f) its leading monomial. For nonzero f,g∈Sf, g \in S, let xγx^\gamma be the least common multiple of LM⁡(f)\operatorname{LM}(f) and LM⁡(g)\operatorname{LM}(g); the S-polynomial of ff and gg is S(f,g)=xγLT⁡(f) f−xγLT⁡(g) g.S(f, g) = \frac{x^\gamma}{\operatorname{LT}(f)} \, f - \frac{x^\gamma}{\operatorname{LT}(g)} \, g. Buchberger's algorithm takes a finite set FF of nonzero elements of SS and proceeds as follows.

  1. Set G=FG = F.
  2. For each pair f≠gf \ne g in GG, compute the remainder rr of S(f,g)S(f, g) under the multivariate division algorithm by GG, listed in a fixed order.
  3. If some such rr is nonzero, add all the nonzero remainders to GG and go back to step 2.
  4. If all such remainders are zero, return GG.

Remarks

The algorithm rests on Buchberger's criterion. Let GG be a finite set of generators of an ideal II. Then GG is a Gröbner basis of II if and only if each S(f,g)S(f, g) with f,g∈Gf, g \in G has remainder zero on division by GG. The algorithm stops for the following reason. Each pass with a nonzero remainder makes the monomial ideal generated by the leading terms of GG strictly larger. An ascending chain of ideals of SS is stationary by Hilbert's basis theorem. The output is a Gröbner basis of the ideal generated by FF.

Example: in k[x,y]k[x, y] with the lexicographic order x>yx > y, let F={x+y,  x}F = \set{x + y, \; x}. Then S(x+y,x)=(x+y)−x=yS(x + y, x) = (x + y) - x = y, which has remainder y≠0y \ne 0 on division by FF, so yy is added. For G={x+y,x,y}G = \set{x + y, x, y}, one finds S(x+y,y)=y(x+y)−xy=y2S(x + y, y) = y(x + y) - x y = y^2, with remainder 00, and S(x,y)=0S(x, y) = 0, and S(x+y,x)=yS(x + y, x) = y now has remainder 00. So GG is a Gröbner basis of (x,y)(x, y).

Non-example: the set FF above fails the test in step 4, since S(x+y,x)S(x + y, x) has nonzero remainder; this is why FF is not a Gröbner basis.

Reading path

To understand this page from the ground up, read these 18 pages in order. The foundations come first.

Show the path as a graph
Ascending chain condition, definition, no evidence levelAscending chain condi…definitionField, concept, no evidence levelFieldconceptGroup, concept, no evidence levelGroupconceptGröbner basis, concept, no evidence levelGröbner basisconceptLeast common multiple, concept, no evidence levelLeast common multipleconceptMonomial ideal, concept, no evidence levelMonomial idealconceptMonomial order, concept, no evidence levelMonomial orderconceptMultivariate division algorithm, concept, no evidence levelMultivariate division…conceptPolynomial ring, concept, no evidence levelPolynomial ringconceptRing, definition, no evidence levelRingdefinitionCommutative ring, definition, no evidence levelCommutative ringdefinitionPolynomial ring, definition, no evidence levelPolynomial ringdefinitionIdeal, definition, no evidence levelIdealdefinitionPolynomials in several variables, definition, no evidence levelPolynomials in severa…definitionIdeal generated by a subset, definition, no evidence levelIdeal generated by a …definitionNoetherian ring, definition, no evidence levelNoetherian ringdefinitionHilbert's basis theorem, statement, no evidence levelHilbert's basis theor…statementBuchberger's algorithm, definition, no evidence levelBuchberger's algorithmdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Ascending chain condition definition
  2. Field concept
  3. Group concept
  4. Gröbner basis concept
  5. Least common multiple concept
  6. Monomial ideal concept
  7. Monomial order concept
  8. Multivariate division algorithm concept
  9. Polynomial ring concept
  10. Ring definition
  11. Commutative ring definition
  12. Polynomial ring definition
  13. Ideal definition
  14. Polynomials in several variables definition
  15. Ideal generated by a subset definition
  16. Noetherian ring definition
  17. Hilbert's basis theorem statement
  18. Buchberger's algorithm definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Buchberger's_algorithm
About this page
TagYC90FXM4SA
URIm2://YC90FXM4SA
Kinddefinition
WritingW0 stub
MSC13P10, 68W30
DefinesBuchberger's algorithm
UsesField, Polynomial ring, Monomial order, Least common multiple, Multivariate division algorithm, Gröbner basis, Monomial ideal, Hilbert's basis theorem
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.