Estimating the number of solutions

In this section, it is presented, how to use the building blocks for Buchberger algorithms for other tasks like estimating the number of solutions.

First, we observe the following:

• By implicit use of the field equations, the number of solutions is always finite.
• We consider finitely many monomials (as we have a degree bound of one per variable).
• The number of standard monomials (monomials not present in the leading ideal) is equal to the number of solutions.
• The leading ideal (w.r.t. to the increasing set of generators) growths monotonely in each step.

This gives a break condition for the number Buchberger algorithm. It becomes clear at a certain point of the computations, that no more than $n$ solutions exist. However, if there are more than $n$ solutions, the full Gröbner basis is computed by this presented algorithm.

def less_than_n_solutions(ideal,n):
    l=interred(ideal)
    g=GroebnerStrategy()
    all_monomials=Monomial([Variable(i) for i in xrange(number_of_variables())]).divisors()
    monomials_not_in_leading_ideal=all_monomials
    for p in l:
        g.addGenerator(p)
    while g.npairs()>0:
        monomials_not_in_leading_ideal=monomials_not_in_leading_ideal%g.minimalLeadingTerms
        if len(monomials_not_in_leading_ideal)<n:
            return True
        g.cleanTopByChainCriterion()
        p=g.nextSpoly()
        p=g.nf(p)
        if not p.isZero():
            g.addGenerator(p)
    monomials_not_in_leading_ideal=monomials_not_in_leading_ideal%g.minimalLeadingTerms
    if len(monomials_not_in_leading_ideal)<n:
        return True
    else:
        return False