Companion worksheet to the course Gröbner bases and convex polytopes: between algebra, geometry, and combinatorics by Sara Veneziale. Edit the code and click Run to experiment. Note that variables are not shared between cells.
In one variable, the division algorithm is unique: given $f, g \in k[x]$, there exist unique $q, r$ with $f = qg + r$ and $\deg(r) < \deg(g)$.
Every ideal in $k[x]$ is principal:
In multiple variables, we need to choose a monomial order. Different orders give different leading terms. Let's see the three standard orders on the same polynomial. Try to find a polynomial that has a different leading order for each and one that has the same leading order for all.
The multivariate division algorithm produces $f = h_1 f_1 + \cdots + h_s f_s + r$, but the remainder $r$ depends on the order in which we divide.
Sage's built-in reduce divides by all polynomials simultaneously, so the list order doesn't matter. To see the order-dependence, we need the textbook algorithm where the break restarts from the top of the divisor list:
Let's start by computing the leading terms with respect to some order.
Let's compute the Gröbner basis of a simple ideal and verify that the remainder is now unique regardless of division order.
One of the main uses of Gröbner bases: testing whether a polynomial belongs to an ideal.
This is a key point: the same ideal has different Gröbner bases under different monomial orders. Let's see this with an example.
Let's implement Buchberger's algorithm naively, with full logging so we can follow each step.
Given a polynomial $f \in k[x_1, \dots, x_n]$, its Newton polytope $\operatorname{Newt}(f)$ is the convex hull of the exponent vectors of the monomials appearing in $f$. The key fact is that only monomials corresponding to vertices of $\operatorname{Newt}(f)$ can ever be the leading term under some term order, since choosing a term order amounts to maximising a linear functional, and the maximum of a linear functional on a polytope is always attained at a vertex.
In three variables, Newton polytopes become genuine 3-dimensional objects. The $f$-vector $(V, E, F)$ counts vertices, edges, and facets, and satisfies the Euler relation $V - E + F = 2$.
The Minkowski sum of two polytopes $P$ and $Q$ is $P + Q = \{p + q \mid p \in P, q \in Q\}$. A fundamental fact is that $\operatorname{Newt}(f \cdot g) = \operatorname{Newt}(f) + \operatorname{Newt}(g)$: the Newton polytope of a product is the Minkowski sum of the Newton polytopes. Let's verify this for $h = x + y + z + 1$, where $\operatorname{Newt}(h)$ is a tetrahedron and $\operatorname{Newt}(h^2)$ should be the tetrahedron scaled by 2.