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:

• It contains a ring declaration, and after this a list of polynomials called ideal.
• Most PolyBoRi standard importants are done by default.
• The second parameter for the ring declaration (the globals() dictionary) can be omitted.
• The polynomial system ideal is supposed to be the main data. Usually we calculate a Gröbner basis of it.

The data file can be loaded using the following commands.

3.2 Reinterpretation of Boolean sets as subsets of the vector space ℤ2ⁿ

Let S be a Boolean set. For example:

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

Another interpretation is to map a set of variables m to a vector v in ℤ2ⁿ. 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 {x₀} with (1,0,0) and {x₁,x₂} with (0,1,1) in ℤ2³. 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 ℤ2ⁿ 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.

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

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

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 x₃.

3.3 Lexicographical normal form of a polynomial against a variety

Let V be a set of points in ℤ2ⁿ, 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 .

We take V = {e₀,e₁,e₂,e₃,0}, where e_i describes the i-th unit vector. For our considerations it does not play any role, if we suppose V to be embedded in ℤ2⁴ or a vector space of higher dimension.

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.

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.

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

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

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:

• adding a generator
• iterating over the system and accessing generators via indices
• accessing generators via their leading term (heavily used inside our internal routines)
• calculation of normal form via the method nf

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:

• critical pairs (managed automatically)
• leading terms
• minimal leading terms

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.

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

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

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

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).

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:

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:

• 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 monotonously 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.