Lexicographical normal form of a polynomial against a variety

Let $ V$ be a set of points in $ \mathbb{Z}_2^n$ , $ f$ a Boolean polynomial. $ V$ can be encoded as a BooleSet as described in [*]. 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=\{e_0,e_1,e_2,e_3,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 $ \mathbb{Z}_2^4$ 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.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) + 1
2011-02-25