Magma incorporates an implementation of the Hilbert-driven Buchberger Algorithm [Tra96]. This algorithm constructs the Gröbner basis of an homogeneous ideal I whose Hilbert series is known. The algorithm is often much more efficient than the conventional Buchberger algorithm since knowledge of the Hilbert series eliminates many unnecessary reductions of S-polynomials. The algorithm can also be used as an alternative to the Gröbner Walk algorithm for changing order since one can compute the Hilbert series of the ideal with respect to an easy monomial order, and then start again with the Hilbert-driven algorithm to compute the Gröbner basis with respect to the desired final order. Furthermore, the algorithm can sometimes be used to test whether an ideal has a particular Hilbert series and abort early if this is proven to be false. The algorithm is also used extensively internally in the Invariant Theory algorithms of Magma.
Let S be a set or sequence of homogeneous polynomials from the multivariate polynomial ring P=K[x1, ..., xn], where K is a field, and let I be the ideal of P generated by S. Let either H be the Hilbert series HP/I(t) of I (as a rational function in Z(t)) or let N∈Z[t] be a univariate integer polynomial such that the weighted numerator of the Hilbert series of I is N. This function attempts to construct the (reduced) Gröbner basis of I using the given Hilbert series. The weighted numerator of the Hilbert series of I is the Hilbert series HP/I(t) of I, multiplied by the denominator ∏i=1n 1 - tdi, where di is the weighted degree of the i-th variable xi (this denominator is thus (1 - t)n if P has the default grading).If the function returns false, then H (or N) cannot be the correct Hilbert series (or weighted numerator of the Hilbert series) of I. Otherwise, the function returns true and a sequence B of polynomials which generates the same ideal as S; if H or N is correct, B will be the (reduced) Gröbner basis of I.
In more detail, let fH be the power series corresponding to the true Hilbert series of I and let fN be the power series corresponding to N/(∏i=1n 1 - tdi). If fH = fN, then the function returns true and the correct (reduced) Gröbner basis of I. Otherwise, consider the first term at which fN and fH differ: if the coefficient of fN is greater than that of fH, then the function returns false (since it will not be able to construct the extra Gröbner basis polynomials needed), otherwise the function will return true with a partial Gröbner basis (since it concludes that it has enough Gröbner basis polynomials when it hasn't). Consequently, the algorithm is usually used when the correct Hilbert series or weighted numerator of the Hilbert series is known, or when there is a weighted numerator which is known to be greater than or equal to the correct weighted numerator of the Hilbert series.
Change verbose printing for the Hilbert-driven Buchberger algorithm to be v. Currently the legal values for v are true, false, 0, or 1.
Let R be the invariant ring of the (permutation) cyclic group G of order 4 over the field K = GF(2). Suppose we have a sequence L of 4 homogeneous invariants of degrees 1, 2, 2, and 4 respectively. We wish to determine efficiently whether the polynomials of L constitute primary invariants for R. To check this, the ideal generated by L must be zero-dimensional and the elements of L must be algebraically independent. This is equivalent to the condition that the weighted numerator of the Hilbert series of the ideal is the product (1 - t)(1 - t2)2(1 - t4). If that is not the correct weighted numerator, it will be less than the correct weighted numerator so the algorithm will return whether the polynomials L do constitute primary invariants for R.
> K := GF(2);
> P<a,b,c,d> := PolynomialRing(K, 4);
> L := [
> a + b + c + d,
> a*b + a*d + b*c + c*d,
> a*c + b*d,
> a*b*c*d
> ];
> // Form potential Hilbert series weighted numerator
> T<t> := PolynomialRing(IntegerRing());
> N := &*[1 - t^Degree(f): f in L];
> N;
t^9 - t^8 - 2*t^7 + 2*t^6 + 2*t^3 - 2*t^2 - t + 1
> time l, B := HilbertGroebnerBasis(L, N);
Time: 0.000
> l;
true
> // Examine Groebner basis B of L:
> B;
[
a + b + c + d,
b^2 + d^2,
b*c + b*d + c^2 + c*d,
c^3 + c^2*d + c*d^2 + d^3,
d^4
]