I would like to present an application of Gröbner bases. The audience is a class of first year graduate students who are taking first year algebra.

Does anyone have suggestions on a specific application that the audience would appreciate?


Solution 1:

Since Grobner basis algorithms may be considered as nonlinear generalizations of Gaussian elimination for systems of linear equations, they have very widespread applicability. Below is a random collection of applications of Grobner bases.

  • effective computation with (holonomic) special functions

  • solving Diophantine equations (Pell)

  • automated geometry theorem proving.

  • coding theory

  • signal and image processing

  • robotics

  • graph coloring problems e.g. Sudoku puzzles

  • extrapolating "missing links" in palaeontology, and phylogenetic tree construction

Solution 2:

  • find intersection points of a couple of conics (pick the right coefficients to make it not so tedious to do all the manipulation)

  • describing the motion of a constrained single hinged robot arm or planetary epicycles (make a cardioid from two equations)

  • colorability of a graph (see A Crash Course... ) (when presented with the construction, very easy to see that the algorithm produces a solution)

Solution 3:

Here are the things I use Grobner bases for, which I certainly find interesting:

  1. Extending the univariate division algorithm to multivariate polynomials (although not a true euclidean division algorithm, it is still useful).

  2. (related) Computing generators for $I_1 + I_2$ where $I_1,I_2$ are ideals in a multivariate polynomial ring (say $\mathbb{C}$), and using this to determine $I(V_1\cap V_2)$ where $V_1$ and $V_2$ are affine varieties in $\mathbb{A}^n$ for $n > 1$.

I'm not sure if these interest you or the students you are presenting to, but hopefully it's at least a start.