[next] [prev] [prev-tail] [tail] [up]

### 3 Other techniques

#### 3.1 Storing polynomial data in a ﬁle

In Po l yBoRi we have default ﬁle format and tools, which read the ﬁles and generate references for our test suite.

The format is a normal Python-ﬁle with a few exceptions:

- It contains a ring declaration, and after this a list of polynomials called ideal.
- Most Po l yBoRi 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.

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

The data ﬁle 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 identiﬁcation 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 ﬁnding zeros of a polynomial), and such procedures, where only the dimension/involved unit vectors/variables matter. The ﬁrst 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 deﬁned to have value 1 on O, 0 on Z and is undeﬁned elsewhere. For encoding sets of Boolean vectors we use the encoding deﬁned 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, deﬁned 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 identiﬁcation 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:

- 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 (aﬀects 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.

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 Po l yBoRi’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:

- By implicit use of the ﬁeld equations, the number of solutions is always ﬁnite.
- We consider ﬁnitely 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.

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

[next] [prev] [prev-tail] [front] [up]