3 Other techniques

3.1 Storing polynomial data in a file

In PolyBoRi we have default file format and tools, which read the files and generate references for our test suite.

The format is a normal Python-file with a few exceptions:

 
declare_ring([Block("x",4, reverse=False)]) 
ideal=[ 
x(1)+x(3), 
x(0)+x(1)*x(2)]

The data file can be loaded using the following commands.

 
In [1]: from polybori.gbrefs import load_file 
 
In [2]: data=load_file("data-sample.py") 
 
In [3]: data.ideal 
Out[3]: [x(1) + x(3), x(0) + x(1)*x(2)]

3.2 Reinterpretation of Boolean sets as subsets of the vector space 2n

Let S be a Boolean set. For example:

 
In [1]: S=BooleSet([x(0),x(1)*x(2)]) 
 
In [2]: S 
Out[2]: {{x(1),x(2)}, {x(0)}}

S is a set of sets of variables. Our usual interpretation is to identify it with a polynomial with corresponding terms:

 
In [3]: Polynomial(S) 
Out[3]: x(1)*x(2) + x(0)

Another interpretation is to map a set of variables m to a vector v in 2n. The i-th entry of v is set to 1, if and only if the i-th variable occurs in m. So we can identify {x0} with (1,0,0) and {x1,x2} with (0,1,1) in 23. Extending this identification from sets of variables to sets of set of variables we can identify S with {(1,0,0),(0,1,1)}. Note, that the choice of n as 3 was not determined by S. In fact every bigger n would have also been a candidate. For this reason, some procedures interpreting Boolean sets as subsets of 2n taking the monomial ambient space as an additional parameter. The full vector space can be constructed by multiplying all needed variables and the set of divisors of the product.

 
In [4]: (x(1)*x(2)*x(3)).divisors() 
Out[4]: {{x(1),x(2),x(3)}, {x(1),x(2)}, 
        {x(1),x(3)}, {x(1)}, {x(2),x(3)}, {x(2)}, {x(3)}, {}}

We distinguish between procedures, which use subsets of the ambient space (like finding zeros of a polynomial), and such procedures, where only the dimension/involved unit vectors/variables matter. The first kind of procedures usually gets the ambient space itself, the second kind gets the monomial consisting of all involved variables.

3.2.1 Examples
 
In [1]: f=x(0)+x(1)+x(2) 
 
In [2]: ambient_space=(x(0)*x(1)*x(2)).divisors() 
 
In [3]: ambient_space 
Out[3]: {{x(0),x(1),x(2)}, {x(0),x(1)}, 
        {x(0),x(2)}, {x(0)}, {x(1),x(2)}, {x(1)}, {x(2)}, {}} 
 
In [4]: f.zeros_in(ambient_space) 
Out[4]: {{x(0),x(1)}, {x(0),x(2)}, {x(1),x(2)}, {}} 
 
In [5]: S=BooleSet([x(0),x(1)*x(2)]) 
 
In [6]: f.zeros_in(S) 
Out[6]: {{x(1),x(2)}}

A example of the second kind, where only the full ambient space can be considered count
lex_groebner_basis_points

 
In [1]: S=BooleSet([x(0),x(1)*x(2)]) 
 
In [2]: from polybori.interpolate import * 
 
In [3]: lex_groebner_basis_points(S,x(0)*x(1)*x(2)) 
Out[3]: [x(0) + x(2) + 1, x(1) + x(2)] 
 
In [4]: lex_groebner_basis_points(S,x(0)*x(1)*x(2)*x(3)) 
Out[4]: [x(0) + x(2) + 1, x(1) + x(2), x(3)]

This function calculates the reduced lexicographical Gröbner basis of the vanishing ideal of S. Here the ambient space matters, as an additional component would mean, that the corresponding entries are zero, so we would get an additional generator for the ideal x3.

3.3 Lexicographical normal form of a polynomial against a variety

Let V be a set of points in 2n, f a Boolean polynomial. V can be encoded as a BooleSet as described in 3.2. Then we are interested in the normal form of f against the vanishing ideal of V : I(V ). It turns out, that the computation of the normal form can be done by the computation of a minimal interpolation polynomial, which takes the same values as f on V .

 
In [1]: from polybori.interpolate import * 
 
In [2]: V=(x(0)+x(1)+x(2)+x(3)+1).set()

We take V = {e0,e1,e2,e3,0}, where ei describes the i-th unit vector. For our considerations it does not play any role, if we suppose V to be embedded in 24 or a vector space of higher dimension.

 
In [3]: V 
Out[3]: {{x(0)}, {x(1)}, {x(2)}, {x(3)}, {}} 
 
In [4]: f=x(0)*x(1)+x(1)+x(2)+1 
 
In [5]: nf_lex_points(f,V) 
Out[5]: x(1) + x(2) + 1

In this case, the normal form of f w. r. t. the vanishing ideal of V consists of all terms of f with degree smaller or equal to 1.

It can be easily seen, that this polynomial forms the same function on V as f. In fact, our computation is equivalent to the direct call of the interpolation function interpolate_smallest_lex, which has two arguments: the set of interpolation points mapped to zero and the set of interpolation points mapped to one.

 
In [6]: z=f.zeros_in(V) 
 
In [7]: z 
Out[7]: {{x(1)}, {x(2)}} 
 
In [8]: o=V.diff(z) 
 
In [9]: o 
Out[9]: {{x(0)}, {x(3)}, {}} 
 
In [11]: interpolate_smallest_lex(z,o) 
Out[11]: x(1) + x(2) + 1

3.4 Partial Boolean functions

A partial Boolean function f is given by two disjoint set of points O, Z. f is defined to have value 1 on O, 0 on Z and is undefined elsewhere. For encoding sets of Boolean vectors we use the encoding defined in 3.2.

If we identify 1 with the Boolean value True and 0 with False, operations from propositional logic get a meaning for Boolean functions.

We can apply operations like xor, and, or to partial Boolean functions, defined everywhere where the result is uniquely determined on extensions of these functions.

 
In [1]: from polybori.partial import PartialFunction 
 
In [2]: O=BooleSet([Monomial(r),x(0)*x(1)]) 
 
In [3]: Z=BooleSet([x(2),x(0)*x(2)]) 
 
In [4]: f=PartialFunction(zeros=Z,ones=O) 
 
In [5]: f 
Out[5]: PartialFunction( 
    zeros={{x(0),x(2)}, {x(2)}}, 
    ones={{x(0),x(1)}, {}}) 
In [6]: O2=BooleSet([x(1),x(2)]) 
 
In [7]: Z2=BooleSet([x(0)*x(1),x(1)*x(2),x(0)*x(2)]) 
 
In [8]: g=PartialFunction(zeros=Z2,ones=O2) 
 
In [9]: f&g 
Out[9]: PartialFunction( 
          zeros={{x(0),x(1)}, {x(0),x(2)}, {x(1),x(2)}, {x(2)}}, 
          ones={}) 
 
In [10]: f|g 
Out[10]: PartialFunction( 
            zeros={{x(0),x(2)}}, 
            ones={{x(0),x(1)}, {x(1)}, {x(2)}, {}}) 
 
In [11]: f^g 
Out[11]: PartialFunction(zeros={{x(0),x(2)}}, 
    ones={{x(0),x(1)}, {x(2)}})

Since addition of in 2 is equivalent to xor (using this identification with Boolean logic), the operators & and + coincide.

 
In [12]: f+g 
Out[12]: PartialFunction(zeros={{x(0),x(2)}}, 
    ones={{x(0),x(1)}, {x(2)}})

We have also build our interpolation functions as method for our PartialFunction class, which is a more convenient way to use it.

 
In [13]: f.interpolate_smallest_lex() 
Out[13]: x(2) + 1 
 
In [14]: g.interpolate_smallest_lex() 
Out[14]: x(0) + x(1) + x(2)

3.5 Building your own Gröbner basis algorithm

The central class for writing your own Gröbner bases algorithm is called
GroebnerStrategy It represents a system of generators (Boolean polynomials) and contains information about critical pairs as well as some extra information like the set of leading terms belonging to these generators.

The most important operations are:

After construction several options can be set, e. g. opt_red_tail for tail reductions (affects also the nf method). The GroebnerStrategy keeps track not only of the single generators, but also of properties of the whole system:

3.5.1 Adding a Generator

There are several methods for adding a generator to a GroebnerStrategy. It may not contain two generators with the same leading monomial. In this way generators can be accessed with both their index and their leading term.

 
In [1]: g=GroebnerStrategy(r) 
 
In [2]: g.add_generator(x(1)) 
 
In [3]: g[x(1)] 
Out[3]: x(1) 
 
In [4]: g.add_generator(x(1)+1) 
------------------------------------------------ 
ValueError     Traceback (most recent call last) 
 
/Users/michael/sing/PolyBoRi/<ipython console> in <module>() 
 
ValueError: strategy contains already 
    a polynomial with same lead

An alternative is to push the generator to the (generalized) set of critical pairs instead of adding it directly

 
In [5]: g.add_generator_delayed(x(1)+1)

Due to the absence of other pairs, in this example the polynomial is on top of the pair queue

 
In [6]: g.next_spoly() 
Out[6]: x(1) + 1

A alternative approach is to let PolyBoRi decide, if an generator is added to the system directly or not.

 
In [1]: g=GroebnerStrategy(r) 
 
In [2]: g.add_as_you_wish(x(1))

3.5.2 Interreduction

The interred-function gives back a system generating the same ideal, where no two leading terms coincide. Also, using the parameter completely ensures that no leading term divides the terms in the tails of the other generators. Even more, it is easier than the Buchberger algorithm, because no critical pairs have to be handled (actually the GroebnerStrategy applies some criteria, when adding a generator, which produces some overhead). The algorithm works by passing the generators sorted to the strategy. If a generator is (lead) rewriteable, it is rewriteable by generators with smaller leading terms. So it will be rewritten by this procedure. The algorithm stops, when no generator is lead rewriteable any more (completely = False) or rewriteable (completely = True).

 
def interred(l,completely=False): 
    """computes a new generating system (g1, ...,gn), 
    spanning the same ideal modulo field equations. 
    The system is interreduced: For i!=j: 
    gi.lead() does not divide any term of gj 
    """ 
    l=[Polynomial(p) for p in l if not p==0] 
    l_old=None 
    l=tuple(l) 
    while l_old!=l: 
        l_old=l 
        l=sorted(l,key=Polynomial.lead) 
        g=ReductionStrategy() 
        if completely: 
            g.opt_red_tail=True 
        for p in l: 
            p=g.nf(p) 
            if not p.is_zero(): 
                g.add_generator(p) 
        l=tuple([e.p for e in g]) 
    return list(l)

3.5.3 A minimal Buchberger algorithm

In this section the buchberger function from the module simplebb is presented. Unlike PolyBoRi’s more sophisticated routines this procedure was developed for educational purposes only:

 
def buchberger(l): 
    "calculates a (non minimal) Groebner basis" 
    l=interred(l) 
    #for making sure, that every polynomial has a 
        different leading term 
    #needed for add_generator 
    if not l: 
        return l 
    g=GroebnerStrategy(l[0].ring()) 
    for p in l: 
        g.add_generator(p) 
    while g.npairs()>0: 
        g.clean_top_by_chain_criterion() 
        p=g.next_spoly() 
        p=g.nf(p) 
        if not p.is_zero(): 
            g.add_generator(p) 
    return list(g)

The criteria are handled by the add_generator-method for immediately applicable criteria and by the function clean_top_by_chain_criterion for the chain criterion.

3.5.4 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:

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) 
    if not l: 
        return l 
    ring = l[0].ring() 
    g=GroebnerStrategy(ring) 
    all_monomials=Monomial([Variable(i, ring) for i 
        in xrange(number_of_variables())]).divisors() 
    monomials_not_in_leading_ideal=all_monomials 
    for p in l: 
        g.add_generator(p) 
    while g.npairs()>0: 
        monomials_not_in_leading_ideal =\ 
            monomials_not_in_leading_ideal\ 
            % g.reduction_strategy.minimal_leading_terms 
        if len(monomials_not_in_leading_ideal)<n: 
            return True 
        g.clean_top_by_chain_criterion() 
        p=g.next_spoly() 
        p=g.nf(p) 
        if not p.is_zero(): 
            g.add_generator(p) 
    monomials_not_in_leading_ideal =\ 
        monomials_not_in_leading_ideal\ 
        % g.reduction_strategy.minimal_leading_terms 
    if len(monomials_not_in_leading_ideal)<n: 
        return True 
    else: 
        return False