Let
be a set of points in
,
a Boolean polynomial.
can be encoded as a BooleSet as described in
.
Then we are interested in the normal form of
against the vanishing ideal of
:
.
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
on
.
In [1]:from polybori.interpolate import * In [2]:V=(x(0)+x(1)+x(2)+x(3)+1).set()
We take
, where
describes the
-th unit vector. For our considerations it does not play any role, if we suppose
to be embedded in
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
w.r.t. the vanishing ideal of
consists of all terms of
with degree smaller or equal to
.
It can be easily seen, that this polynomial forms the same function on
as
.
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.zerosIn(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) + 12009-09-10