Gröbner bases

A Gröbner basis of an ideal I \subseteq \mathbb{F}_p[x_1, \ldots, x_m] with respect to a monomial ordering is a finite generating set G of I such that the leading monomial of every nonzero element of I is divisible by the leading monomial of some element of G; equivalently, division by G (fmpz_mod_mpoly_divrem_ideal) leaves remainder zero exactly on the elements of I. A Gröbner basis is reduced if its elements are monic and no term of an element is divisible by the leading monomial of another element; the reduced Gröbner basis of an ideal is unique [BW1993] [CLO2015].

fmpz_mod_mpoly_buchberger_naive computes a Gröbner basis of the ideal generated by a vector of polynomials by Buchberger's algorithm [Buc1965]: it starts from the monic generators and repeatedly reduces the S-polynomial of a pair of basis elements (fmpz_mod_mpoly_spoly) modulo the current basis, adding the remainder to the basis when it is nonzero, until all pairs reduce to zero. Pairs are selected and discarded as in the algorithm GROEBNERNEW2 of Becker and Weispfenning [BW1993], which applies the criteria of Gebauer and Möller [GM1988]. The result is a Gröbner basis but in general not a reduced one; fmpz_mod_mpoly_vec_autoreduction_groebner turns it into the reduced Gröbner basis. The modulus must be prime.

The implementation is meant for small systems. Its running time and the size of the basis can grow very quickly (doubly exponentially in the number of variables in the worst case); the version fmpz_mod_mpoly_buchberger_naive_with_limits gives up, returning 0, when the basis gets more than ideal_len_limit elements or a polynomial more than poly_len_limit terms. fmpz_mod_mpoly_vec_is_groebner checks the Buchberger criterion (all S-polynomials reduce to zero) and, if F is given, that the generators reduce to zero modulo G.

Example#

The intersection of a sphere, a paraboloid and a plane over \mathbb{F}_{101}; with the lexicographic ordering x > y > z, the reduced Gröbner basis is triangular and gives the solutions by successive substitution:

#include <flint/flint.h>
#include <flint/fmpz_mod_mpoly.h>

int main(void)
{
    fmpz_mod_mpoly_ctx_t ctx;
    fmpz_mod_mpoly_vec_t F, G, H;
    fmpz_mod_mpoly_t f;
    fmpz_t p;
    const char * vars[] = {"x", "y", "z"};
    slong i;

    fmpz_init_set_ui(p, 101);
    fmpz_mod_mpoly_ctx_init(ctx, 3, ORD_LEX, p);
    fmpz_mod_mpoly_vec_init(F, 0, ctx);
    fmpz_mod_mpoly_vec_init(G, 0, ctx);
    fmpz_mod_mpoly_vec_init(H, 0, ctx);
    fmpz_mod_mpoly_init(f, ctx);

    /* the intersection of a sphere, a paraboloid and a plane */
    fmpz_mod_mpoly_set_str_pretty(f, "x^2 + y^2 + z^2 - 4", vars, ctx);
    fmpz_mod_mpoly_vec_append(F, f, ctx);
    fmpz_mod_mpoly_set_str_pretty(f, "x^2 + y^2 - 2*z", vars, ctx);
    fmpz_mod_mpoly_vec_append(F, f, ctx);
    fmpz_mod_mpoly_set_str_pretty(f, "x - y", vars, ctx);
    fmpz_mod_mpoly_vec_append(F, f, ctx);

    fmpz_mod_mpoly_buchberger_naive(G, F, ctx);
    flint_printf("Groebner basis: %d, size %wd\n",
                 fmpz_mod_mpoly_vec_is_groebner(G, F, ctx), G->length);

    fmpz_mod_mpoly_vec_autoreduction_groebner(H, G, ctx);
    flint_printf("reduced basis (autoreduced: %d):\n",
                 fmpz_mod_mpoly_vec_is_autoreduced(H, ctx));
    for (i = 0; i < H->length; i++)
    {
        fmpz_mod_mpoly_print_pretty(fmpz_mod_mpoly_vec_entry(H, i), vars, ctx);
        flint_printf("\n");
    }

    fmpz_mod_mpoly_clear(f, ctx);
    fmpz_mod_mpoly_vec_clear(F, ctx);
    fmpz_mod_mpoly_vec_clear(G, ctx);
    fmpz_mod_mpoly_vec_clear(H, ctx);
    fmpz_mod_mpoly_ctx_clear(ctx);
    fmpz_clear(p);
    return 0;
}

Groebner basis: 1, size 5
reduced basis (autoreduced: 1):
x+100*y
y^2+100*z
z^2+2*z+97

The basis says x = y, y^2 = z and z^2 + 2z - 4 = 0. The unreduced basis returned by fmpz_mod_mpoly_buchberger_naive has five elements, two of which are redundant.