Magma incorporates an implementation of the Hilbert-driven
Buchberger Algorithm. 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.
HilbertGroebnerBasis(S, H) : [ RngMPolElt ], FldFunRatUElt -> BoolElt, [ RngMPolElt ]
Let S be a set or sequence of homogeneous polynomials from the multivariate polynomial ring P=K[x_1, ..., x_n] and let I be the the ideal of P generated by S. Let either H be the Hilbert series H_(P/I)(t) of I (as a rational function in Z(t)) or let N in 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 H_(P/I)(t) of I, multiplied by the denominator prod_(i=1)^(n) 1 - t^(d_i), where d_i is the weighted degree of the i-th variable x_i (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 f_H be the power series corresponding to the true Hilbert series of I and let f_N be the power series corresponding to N/(prod_(i=1)^(n) 1 - t^(d_i)). If f_H = f_N, then the function returns true and the correct (reduced) Gröbner basis of I. Otherwise, consider the first term at which f_N and f_H differ: if the coefficient of f_N is greater than that of f_H, 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.
> 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^TotalDegree(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);
> 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
]