---
tag: 4RH1D40WG1
kind: concept
name: Buchberger's algorithm
msc: [13P10, 68W30]
sources:
  - url: https://en.wikipedia.org/wiki/Buchberger's_algorithm
same_as:
  wikidata: Q997962
  wikipedia: Buchberger's algorithm
---

## Summary

Buchberger's algorithm turns a finite set of generators of an ideal of a polynomial ring into a [[Gröbner basis|C83KPT47R0]] of the same ideal.
It repeatedly forms S-polynomials of pairs of elements, divides them by the current set with the [[multivariate division algorithm|T8EN3CAEQF]], and adds the nonzero remainders.
It was introduced by Bruno Buchberger, who also named Gröbner bases after his advisor Wolfgang Gröbner.
It plays the role for polynomial systems that Gaussian elimination plays for linear systems and the Euclidean algorithm plays for polynomials in one variable.

## Explanations

### L1 human

Two polynomials can combine so that their leading terms cancel, and what is left may have a new leading term that the generators do not see.
The S-polynomial of two generators is the simplest such combination.
Buchberger's algorithm computes all these combinations, reduces them by the current generators, and adds whatever does not reduce to zero.
Each addition makes the ideal of leading terms bigger, and this cannot go on forever, so the algorithm stops.
At the end, all S-polynomials reduce to zero, and this is exactly the test for a Gröbner basis.