Elements of the quotient ring
are called boolean polynomials. Boolean polynomials arise naturally in cryptography, coding theory, formal logic, chip design and other areas. This implementation is a thin wrapper around the PolyBoRi library by Michael Brickenstein and Alexander Dreyer.
“Boolean polynomials can be modelled in a rather simple way, with
both coefficients and degree per variable lying in
{0, 1}. The ring of Boolean polynomials is, however,
not a polynomial ring, but rather the quotient ring of the
polynomial ring over the field with two elements modulo the field
equations for each variable
. Therefore,
the usual polynomial data structures seem not to be appropriate for
fast Groebner basis computations. We introduce a specialised data
structure for Boolean polynomials based on zero-suppressed binary
decision diagrams (ZDDs), which is capable of handling these
polynomials more efficiently with respect to memory consumption and
also computational speed. Furthermore, we concentrate on high-level
algorithmic aspects, taking into account the new data structures as
well as structural properties of Boolean polynomials.” - [BD07]
AUTHORS:
EXAMPLES:
Consider the ideal
First, we compute the lexicographical Groebner basis in the polynomial ring
sage: P.<a,b,c,d,e> = PolynomialRing(GF(2), 5, order='lex')
sage: I1 = ideal([a*b + c*d + 1, a*c*e + d*e, a*b*e + c*e, b*c + c*d*e + 1])
sage: for f in I1.groebner_basis():
... f
a + c^2*d + c + d^2*e
b*c + d^3*e^2 + d^3*e + d^2*e^2 + d*e + e + 1
b*e + d*e^2 + d*e + e
c*e + d^3*e^2 + d^3*e + d^2*e^2 + d*e
d^4*e^2 + d^4*e + d^3*e + d^2*e^2 + d^2*e + d*e + e
If one wants to solve this system over the algebraic closure of
then this Groebner basis was the one to consider. If one
wants solutions over
only then one adds the field polynomials
to the ideal to force the solutions in
.
sage: J = I1 + sage.rings.ideal.FieldIdeal(P)
sage: for f in J.groebner_basis():
... f
a + d + 1
b + 1
c + 1
d^2 + d
e
So the solutions over are
and
.
We can express the restriction to by considering the quotient
ring. If
is an ideal in
then the
ideals in the quotient ring
are in
one-to-one correspondence with the ideals of
containing
(that is, the ideals
satisfying
).
sage: Q = P.quotient( sage.rings.ideal.FieldIdeal(P) )
sage: I2 = ideal([Q(f) for f in I1.gens()])
sage: for f in I2.groebner_basis():
... f
abar + dbar + 1
bbar + 1
cbar + 1
ebar
This quotient ring is exactly what PolyBoRi handles well:
sage: B.<a,b,c,d,e> = BooleanPolynomialRing(5, order='lex')
sage: I2 = ideal([B(f) for f in I1.gens()])
sage: for f in I2.groebner_basis():
... f
a + d + 1
b + 1
c + 1
e
Note that is not representable in
. Also note, that
PolyBoRi cannot play out its strength in such small examples,
i.e. working in the polynomial ring might be faster for small examples
like this.
PolyBoRi comes with a Python wrapper. However this wrapper does not match Sage’s style and is written using Boost. Thus Sage’s wrapper is a reimplementation of Python bindings to PolyBoRi’s C++ library. This interface is written in Cython like all of Sage’s C/C++ library interfaces. An interface in PolyBoRi style is also provided which is effectively a reimplementation of the official Boost wrapper in Cython. This means that some functionality of the official wrapper might be missing from this wrapper and this wrapper might have bugs not present in the official Python interface.
The re-implementation PolyBoRi’s native wrapper is available to the user too:
sage: from polybori import *
sage: declare_ring([Block('x',2),Block('y',3)],globals())
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: r
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: [Variable(i) for i in xrange(r.ngens())]
[x(0), x(1), y(0), y(1), y(2)]
For details on this interface see:
http://polybori.sourceforge.net/doc/tutorial/tutorial.html.
Note that due to this duality of this interface some functions do not obey Sage’s naming convention. For instance, f.zerosIn should be called f.zeros_in by Sage’s standards. However, PolyBoRi expects the function f.zerosIn.
Also, the interface provides functions for compatibility with Sage accepting convenient Sage data types which are slower than their native PolyBoRi counterparts. For instance, sets of points can be represented as tuples of tuples (Sage) or as BooleSets (PolyBoRi) and naturally the second option is faster.
REFERENCES:
[BD07] | Michael Brickenstein, Alexander Dreyer; PolyBoRi: A Groebner basis framework for Boolean polynomials; pre-print available at http://www.itwm.fraunhofer.de/zentral/download/berichte/bericht122.pdf |
Return a new set of boolean monomials. This data type is also implemented on the top of ZDDs and allows to see polynomials from a different angle. Also, it makes high-level set operations possible, which are in most cases faster than operations handling individual terms, because the complexity of the algorithms depends only on the structure of the diagrams.
BooleanPolynomials can easily be converted to BooleSets by using the member function set().
INPUT:
EXAMPLE:
sage: from polybori import BooleSet
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = BooleSet(B)
sage: BS
{}
Note
BooleSet prints as ‘{}’ but are not Python dictionaries.
Create an iterator over elements of self.
EXAMPLES:
sage: P.<x, y> = BooleanPolynomialRing(2)
sage: f = x*y+x+y+1; s = f.set()
sage: list(s)
[x*y, x, y, 1]
EXAMPLE:
sage: from polybori import BooleSet
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = BooleSet(B)
sage: repr(BS) # indirect doctest
'{}'
Return the Cartesian product of this set and the set rhs.
The Cartesian product of two sets X and Y is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y.
EXAMPLE:
sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: g = x4 + 1
sage: t = g.set(); t
{{x4}, {}}
sage: s.cartesianProduct(t)
{{x1,x2,x4}, {x1,x2}, {x2,x3,x4}, {x2,x3}}
Return the set theoretic difference of this set and the set rhs.
The difference of two sets and
is defined
as:
EXAMPLE:
sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: g = x2*x3 + 1
sage: t = g.set(); t
{{x2,x3}, {}}
sage: s.diff(t)
{{x1,x2}}
Return True if this set is empty.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = (a*b + c).set()
sage: BS.empty()
False
sage: BS = B(0).set()
sage: BS.empty()
True
Return the number of nodes in the ZDD.
EXAMPLE:
sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: s.nNodes()
4
Navigators provide an interface to diagram nodes, accessing their index as well as the corresponding then- and else-branches.
You should be very careful and always keep a reference to the original object, when dealing with navigators, as navigators contain only a raw pointer as data. For the same reason, it is necessary to supply the ring as argument, when constructing a set out of a navigator.
EXAMPLE:
sage: from polybori import BooleSet
sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3*x4+x2*x4+x3+x4+1
sage: s = f.set(); s
{{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}
sage: nav = s.navigation()
sage: BooleSet(nav,s.ring())
{{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}
sage: nav.value()
1
sage: nav_else = nav.elseBranch()
sage: BooleSet(nav_else,s.ring())
{{x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}
sage: nav_else.value()
2
Return the parent ring.
EXAMPLE:
sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3*x4+x2*x4+x3+x4+1
sage: f.set().ring() is B
True
Return self.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = (a*b + c).set()
sage: BS.set() is BS
True
Return the set theoretic union of this set and the set rhs.
The union of two sets and
is defined as:
EXAMPLE:
sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: g = x2*x3 + 1
sage: t = g.set(); t
{{x2,x3}, {}}
sage: s.diff(t)
{{x1,x2}}
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: f = B.random_element()
sage: f
a*c + a*d + a + b*d + 1
sage: it = iter(f.set())
sage: it.next()
a*c
Construct a boolean monomial object.
INPUT:
EXAMPLE:
sage: from polybori import BooleanMonomialMonoid, BooleanMonomial
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: BooleanMonomial(M)
1
Note
Use the __call__ method of BooleanMonomialMonoid and not this constructor to construct these objects.
Addition operator. Returns a boolean polynomial.
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: x = M(x); xy = M(x*y)
sage: x + xy
x*y + x
sage: x+0
x
sage: 0+x # todo: not implemented
x
sage: x+1
x + 1
sage: 1 + x # todo: not implemented
x + 1
Evaluate this monomial.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m(B(0),B(1))
0
sage: m(x=B(1))
y
Return an iterator over the variables in this monomial.
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: list(M(x*z)) # indirect doctest
[x, z]
Evaluate this monomial.
INPUT:
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: m = P._monom_monoid(x*y)
sage: m._eval({0:y,1:z})
y*z
Multiply self with another boolean monomial.
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: x = M(x); xy = M(x*y); z=M(z)
sage: x*x
x
sage: xy*y
x*y
sage: xy*z
x*y*z
Return a string representing self.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: M = sage.rings.polynomial.pbori.BooleanMonomialMonoid(P)
sage: M(x*y) # indirect doctest
x*y
sage: R.<t,u> = BooleanPolynomialRing(2)
sage: M(x*y)
x*y
Return degree of this monomial.
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M(x*y).deg()
2
sage: M(x*x*y*z).deg()
3
Return degree of this monomial.
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M(x*y).degree()
2
Return a set of boolean monomials with all divisors of this monomial.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.divisors()
{{x,y}, {x}, {y}, {}}
Return the variable index of the first variable in this monomial.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.index()
0
Return an iterator over the indicies of the variables in self.
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: list(M(x*z).iterindex())
[0, 2]
Return a set of boolean monomials with all multiples of this monomial up the bound rhs.
INPUT:
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x
sage: m = f.lm()
sage: g = x*y*z
sage: n = g.lm()
sage: m.multiples(n)
{{x,y,z}, {x,y}, {x,z}, {x}}
sage: n.multiples(m)
{{x,y,z}}
Note
The returned set always contains self even if the bound rhs is smaller than self.
Return True if self is reducible by rhs.
INPUT:
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.reducibleBy((x*y).lm())
True
sage: m.reducibleBy((x*z).lm())
False
Return a boolean set of variables in this monomials.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.set()
{{x,y}}
Return a list of the variables in this monomial.
EXAMPLE:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M(x*z).variables() # indirect doctest
[x, z]
An iterator over the variable indices of a monomial.
EXAMPLE:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: for m in f: list(m.iterindex())# indirect doctest
[0, 1]
[2]
[]
EXAMPLE:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: m = f.lm()
sage: m.iterindex().next()
0
Construct a boolean monomial monoid given a boolean polynomial ring.
This object provides a parent for boolean monomials.
INPUT:
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: M = BooleanMonomialMonoid(P)
sage: M
MonomialMonoid of Boolean PolynomialRing in x, y
sage: M.gens()
(x, y)
sage: type(M.gen(0))
<type 'sage.rings.polynomial.pbori.BooleanMonomial'>
Convert elements of other objects to elements of this monoid.
INPUT:
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: x_monom = M(x); x_monom
x
sage: M(x*y)
x*y
sage: M(x+y)
...
TypeError: cannot convert to BooleanMonomialMonoid
Convert elements of self.
sage: M(x_monom)
x
Convert from other BooleanPolynomialRings.
sage: R.<z,x> = BooleanPolynomialRing(2)
sage: t = M(z); t
z
sage: t.parent() is M
True
Convert BooleanMonomials over other BooleanPolynomialRings.
sage: N = BooleanMonomialMonoid(R)
sage: t = M(N(x*z)); t
x*z
sage: t.parent() is M
True
Return a hash for this monoid.
EXAMPLE:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: M = BooleanMonomialMonoid(P)
sage: {M:1} # indirect doctest
{MonomialMonoid of Boolean PolynomialRing in x, y: 1}
Canonical conversion of elements from other objects to this monoid.
EXAMPLES:
Coerce elements of self.
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: x_monom = M(x); x_monom
x
sage: M._coerce_(x_monom) # indirect doctest
x
Coerce elements from BooleanMonomialMonoids where the generators of self include the generators of the other monoid.
sage: from polybori import BooleanMonomialMonoid
sage: R.<z,y> = BooleanPolynomialRing(2)
sage: N = BooleanMonomialMonoid(R)
sage: m = M._coerce_(N(y*z)); m
y*z
sage: m.parent() is M
True
TESTS:
sage: from polybori import BooleanMonomialMonoid
sage: R.<t,y> = BooleanPolynomialRing(2)
sage: N = BooleanMonomialMonoid(R)
sage: m = M._coerce_(N(y)); m
...
ValueError: cannot coerce monomial y to MonomialMonoid of Boolean PolynomialRing in x, y, z: name t not defined
sage: from polybori import BooleanMonomialMonoid
sage: R.<t,x,y,z> = BooleanPolynomialRing(4)
sage: N = BooleanMonomialMonoid(R)
sage: m = M._coerce_(N(x*y*z)); m
...
TypeError: coercion from <type 'sage.rings.polynomial.pbori.BooleanMonomial'> to MonomialMonoid of Boolean PolynomialRing in x, y, z not implemented
Monomials support multiplication by 0 and 1 in GF(2).
EXAMPLE:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: M = BooleanMonomialMonoid(P)
sage: M # indirect doctest
MonomialMonoid of Boolean PolynomialRing in x, y
Return the i-th generator of self.
INPUT:
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M.gen(0)
x
sage: M.gen(2)
z
sage: P = BooleanPolynomialRing(1000, 'x')
sage: M = BooleanMonomialMonoid(P)
sage: M.gen(50)
x50
Return the tuple of generators of this monoid.
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M.gens()
(x, y, z)
Returns the number of variables in this monoid.
EXAMPLES:
sage: from polybori import BooleanMonomialMonoid
sage: P = BooleanPolynomialRing(100, 'x')
sage: M = BooleanMonomialMonoid(P)
sage: M.ngens()
100
Return an iterator over the variables of a boolean monomial.
EXAMPLE:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: for m in f: list(m)# indirect doctest
[x, y]
[z]
[]
EXAMPLE:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: m = f.lm()
sage: iter(m).next()
x
Construct a boolean polynomial object in the given boolean polynomial ring.
INPUT:
TEST:
sage: from polybori import BooleanPolynomial
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: BooleanPolynomial(B)
0
Note
Do not use this method to construct boolean polynomials, but use the appropriate __call__ method in the parent.
Evaluate this boolean polynomials.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + 1
sage: f(0,1,1)
0
sage: f(z,y,x)
x + y*z + 1
sage: f(x=z)
y*z + z + 1
sage: P.<a,b,c> = PolynomialRing(QQ)
sage: f(a,b,c)
a*b + c + 1
sage: f(x=a,y=b,z=1)
a*b + 2
Evaluation of polynomials can be used fully symbolic:
sage: f(x=var('a'),y=var('b'),z=var('c'))
a*b + c + 1
sage: f(var('a'),var('b'),1)
a*b
Return an iterator over the monomials of self, in the order of the parent ring.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: p = x + z + x*y + y*z + x*y*z
sage: list(iter(p))
[x*y*z, x*y, x, y*z, z]
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: p = x + z + x*y + y*z + x*y*z
sage: list(iter(p))
[x*y*z, x*y, y*z, x, z]
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='degrevlex')
sage: p = x + z + x*y + y*z + x*y*z
sage: list(iter(p))
[z*y*x, y*x, z*y, x, z]
TESTS:
sage: R = BooleanPolynomialRing(1,'y')
sage: list(iter(y))
[y]
sage: R
Boolean PolynomialRing in y
Return -self.
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*z + b + 1
sage: -f
a*z + b + 1
EXAMPLE:
sage: P.<a,b> = BooleanPolynomialRing(2)
sage: loads(dumps(a)) == a
True
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*z + b + 1
sage: g = b + z
sage: f + g
a*z + z + 1
Return a LaTeX representation of this boolean polynomial.
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: latex(a+b+a*z^2+1) # indirect doctest
a z + a + b + 1
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: k = B.base_ring()
sage: f = a*z + b + 1
sage: k(0)*f
0
Returns the Magma representation of self.
EXAMPLES:
sage: R.<x,y> = BooleanPolynomialRing()
sage: f = y*x + x +1
sage: f._magma_init_(magma) # optional - magma
'_sage_[...]*_sage_[...] + _sage_[...] + 1'
sage: magma(f) # optional - magma
x*y + x + 1
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*z + b + 1
sage: g = b + z
sage: f * g
a*b*z + a*z + b*z + z
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: repr(a+b+z^2+1) # indirect doctest
'a + b + z + 1'
Return string representing this boolean polynomial but change the variable names to varnames.
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: a._repr_with_changed_varnames(['x','y','z'])
'x'
TESTS:
sage: a._repr_with_changed_varnames([1,'y','z'])
...
TypeError: varnames has entries with wrong type.
sage: a
a
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: k = B.base_ring()
sage: f = a*z + b + 1
sage: f*k(1)
a*z + b + 1
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*z + b + 1
sage: g = b + z
sage: f - g
a*z + z + 1
Return True if this element is constant.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: x.constant()
False
sage: B(1).constant()
True
Returns the constant coefficient of this boolean polynomial.
Return the degree of self. This is usually equivalent to the total degree except for weighted term orderings which are not implemented yet.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).degree()
1
sage: P(1).degree()
0
sage: (x*y + x + y + 1).degree()
2
Return the total degree of self.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).degree()
1
sage: P(1).degree()
0
sage: (x*y + x + y + 1).degree()
2
Return elimination length as used in the SlimGB algorithm.
EXAMPLE:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: x.elength()
1
sage: f = x*y + 1
sage: f.elength()
2
REFERENCES:
Return the first term with respect to the lexicographical term ordering.
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3,order='lex')
sage: f = b*z + a + 1
sage: f.firstTerm()
a
Return graded part of this boolean polynomial of degree deg.
INPUT:
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + c*d + a*b + 1
sage: f.gradedPart(2)
a*b + c*d
sage: f.gradedPart(0)
1
TESTS:
sage: f.gradedPart(-1)
0
Return True if this boolean polynomial has a
constant part, i.e. if is a term.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + c*d + a*b + 1
sage: f.hasConstantPart()
True
sage: f = a*b*c + c*d + a*b
sage: f.hasConstantPart()
False
Return True if this element is one.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: x.isOne()
False
sage: B(0).isOne()
False
sage: B(1).isOne()
True
Return True if this element is zero.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: x.isZero()
False
sage: B(0).isZero()
True
sage: B(1).isZero()
False
Check if self is constant.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(1).is_constant()
True
sage: P(0).is_constant()
True
sage: x.is_constant()
False
sage: (x*y).is_constant()
False
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*z + b + 1
sage: g = b + z
sage: f.is_equal(g)
False
sage: f.is_equal( (f + 1) - 1 )
True
Return True if this element is a homogeneous polynomial.
EXAMPLES:
sage: P.<x, y> = BooleanPolynomialRing()
sage: (x+y).is_homogeneous()
True
sage: P(0).is_homogeneous()
True
sage: (x+1).is_homogeneous()
False
Check if self is 1.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(1).is_one()
True
sage: P.one_element().is_one()
True
sage: x.is_one()
False
sage: P(0).is_one()
False
Check if self is invertible in the parent ring.
Note that this condition is equivalent to being 1 for boolean polynomials.
EXAMPLE:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P.one_element().is_unit()
True
sage: x.is_unit()
False
Check if self is zero.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(0).is_zero()
True
sage: x.is_zero()
False
sage: P(1).is_zero()
False
Return the leading monomial of boolean polynomial, with respect to to the order of parent ring.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lead()
x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lead()
y*z
Return the leading monomial of boolean polynomial, with respect to the lexicographical term ordering.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lexLead()
x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lexLead()
x
Return degree of leading monomial with respect to the lexicographical ordering.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='lex')
sage: f = x + y*z
sage: f
x + y*z
sage: f.lexLmDeg()
1
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: f = x + y*z
sage: f
y*z + x
sage: f.lexLmDeg()
1
Return the leading monomial of this boolean polynomial, with respect to the order of parent ring.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lm()
x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lm()
y*z
Return the degree of the leading monomial with respect to the lexicographical orderings.
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='lex')
sage: f = x + y*z
sage: f
x + y*z
sage: f.lmDeg()
1
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: f = x + y*z
sage: f
y*z + x
sage: f.lmDeg()
2
Return a BooleSet of all divisors of the leading monomial.
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*b + z + 1
sage: f.lmDivisors()
{{a,b}, {a}, {b}, {}}
Returns the total degree of the leading monomial of self.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: p = x + y*z
sage: p.lm_degree()
1
sage: P.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: p = x + y*z
sage: p.lm_degree()
2
sage: P(0).lm_degree()
0
Return the leading term of this boolean polynomial, with respect to the order of the parent ring.
Note that for boolean polynomials this is equivalent to returning leading monomials.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lt()
x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lt()
y*z
Map every variable x_i in this polynomial to
.
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*b + z + 1; f
a*b + z + 1
sage: f.mapEveryXToXPlusOne()
a*b + a + b + z + 1
sage: f(a+1,b+1,z+1)
a*b + a + b + z + 1
Return the coefficient of the monomial mon in self, where mon must have the same parent as self.
INPUT:
EXAMPLE:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: x.monomial_coefficient(x)
1
sage: x.monomial_coefficient(y)
0
sage: R.<x,y,z,a,b,c>=BooleanPolynomialRing(6)
sage: f=(1-x)*(1+y); f
x*y + x + y + 1
sage: f.monomial_coefficient(1)
1
sage: f.monomial_coefficient(0)
0
Return a list of monomials appearing in self ordered largest to smallest.
EXAMPLE:
sage: P.<a,b,c> = BooleanPolynomialRing(3,order='lex')
sage: f = a + c*b
sage: f.monomials()
[a, b*c]
sage: P.<a,b,c> = BooleanPolynomialRing(3,order='degrevlex')
sage: f = a + c*b
sage: f.monomials()
[c*b, a]
Return the number of variables used to form this boolean polynomial.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + 1
sage: f.nVars()
3
Return the number of variables used to form this boolean polynomial.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + 1
sage: f.nvariables()
3
Return the normal form of self w.r.t. I, i.e. return the remainder of self with respect to the polynomials in I. If the polynomial set/list I is not a Groebner basis the result is not canonical.
INPUT:
EXAMPLE:
sage: B.<x0,x1,x2,x3> = BooleanPolynomialRing(4)
sage: I = B.ideal((x0 + x1 + x2 + x3, \
x0*x1 + x1*x2 + x0*x3 + x2*x3, \
x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x1*x2*x3, \
x0*x1*x2*x3 + 1))
sage: gb = I.groebner_basis()
sage: f,g,h,i = I.gens()
sage: f.reduce(gb)
0
sage: p = f*g + x0*h + x2*i
sage: p.reduce(gb)
0
sage: p.reduce(I)
x1*x2*x3 + x2
Note
If this function is called repeatedly with the same I then it is advised to use PolyBoRi’s GroebnerStrategy object directly, since that will be faster. See the source code of this function for details.
Return True if this boolean polynomial is reducible by the polynomial rhs.
INPUT:
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4,order='degrevlex')
sage: f = (a*b + 1)*(c + 1)
sage: f.reducibleBy(d)
False
sage: f.reducibleBy(c)
True
sage: f.reducibleBy(c + 1)
True
Return the parent of this boolean polynomial.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: a.ring() is B
True
Return a BooleSet with all monomials appearing in this polynomial.
EXAMPLE:
sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: (a*b+z+1).set()
{{a,b}, {z}, {}}
Return the S-Polynomial of this boolean polynomial and the other boolean polynomial rhs.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + c*d + a*b + 1
sage: g = c*d + b
sage: f.spoly(g)
a*b + a*c*d + c*d + 1
Fixes some given variables in a given boolean polynomial and returns the changed boolean polynomials. The polynomial itself is not affected. The variable,value pairs for fixing are to be provided as dictionary of the form {variable:value} or named parameters (see examples below).
INPUT:
EXAMPLE:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y + z + y*z + 1
sage: f.subs(x=1)
y*z + y + z + 1
sage: f.subs(x=0)
y*z + z + 1
sage: f.subs(x=y)
y*z + y + z + 1
sage: f.subs({x:1},y=1)
0
sage: f.subs(y=1)
x + 1
sage: f.subs(y=1,z=1)
x + 1
sage: f.subs(z=1)
x*y + y
sage: f.subs({'x':1},y=1)
0
This method can work fully symbolic:
sage: f.subs(x=var('a'),y=var('b'),z=var('c'))
a*b + b*c + c + 1
sage: f.subs({'x':var('a'),'y':var('b'),'z':var('c')})
a*b + b*c + c + 1
Return total degree of this boolean polynomial.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + 1
sage: f.totalDegree()
3
Return the total degree of self.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).total_degree()
1
sage: P(1).total_degree()
0
sage: (x*y + x + y + 1).total_degree()
2
Return a list of all variables appearing in self.
EXAMPLE:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x + y).variables()
[x, y]
sage: (x*y + z).variables()
[x, y, z]
sage: P.zero_element().variables()
[]
sage: P.one_element().variables()
[1]
Return a boolean monomial with all the variables appearing in self.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x + y).varsAsMonomial()
x*y
sage: (x*y + z).varsAsMonomial()
x*y*z
sage: P.zero_element().varsAsMonomial()
1
sage: P.one_element().varsAsMonomial()
1
TESTS:
sage: R = BooleanPolynomialRing(1, 'y')
sage: y.varsAsMonomial()
y
sage: R
Boolean PolynomialRing in y
Return a set containing all elements of s where this boolean polynomial evaluates to zero.
If s is given as a BooleSet, then the return type is also a BooleSet. If s is a set/list/tuple of tuple this function returns a tuple of tuples.
INPUT:
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b + c + d + 1
Now we create a set of points:
sage: s = a*b + a*b*c + c*d + 1
sage: s = s.set(); s
{{a,b,c}, {a,b}, {c,d}, {}}
This encodes the points (1,1,1,0), (1,1,0,0), (0,0,1,1) and (0,0,0,0). But of these only (1,1,0,0) evaluates to zero.
sage: f.zerosIn(s)
{{a,b}}
sage: f.zerosIn([(1,1,1,0), (1,1,0,0), (0,0,1,1), (0,0,0,0)])
((1, 1, 0, 0),)
Construct an ideal in the boolean polynomial ring.
INPUT:
ring - the ring this ideal is defined in
gens - a list of generators
(default: True)
EXAMPLES:
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4)
sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0)
sage: I
Ideal (x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) of Boolean PolynomialRing in x0, x1, x2, x3
Return a Groebner basis of this ideal.
INPUT:
this options affects mainly heuristics. The reducedness of the output polynomials can only be guaranteed by the option redsb (default: True)
minsb - return a minimal Groebner basis (default: True)
redsb - return a minimal Groebner basis and all tails are reduced (default: True)
deg_bound - only compute Groebner basis up to a given degree bound (default: False)
faugere - turn off or on the linear algebra (default: False)
linear_algebra_in_last_block - this affects the last block of block orderings and degree orderings. If it is set to True linear algebra takes affect in this block. (default: True)
selection_size - maximum number of polynomials for parallel reductions (default: 1000)
heuristic - Turn off heuristic by setting heuristic=False (default: True)
lazy - (default: True)
invert - setting invert=True input and output get a transformation x+1 for each variable x, which shouldn’t effect the calculated GB, but the algorithm.
other_ordering_first - possible values are False or an ordering code. In practice, many Boolean examples have very few solutions and a very easy Groebner basis. So, a complex walk algorithm (which cannot be implemented using the data structures) seems unnecessary, as such Groebner bases can be converted quite fast by the normal Buchberger algorithm from one ordering into another ordering. (default: False)
prot - show protocol (default: False)
full_prot - show full protocol (default: False)
EXAMPLES:
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4)
sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0)
sage: I.groebner_basis()
[x0*x1 + x0*x2 + x0, x0*x2*x3 + x0*x3]
If this ideal is spanned by (f_1, ..., f_n) this method returns (g_1, ..., g_s) such that:
EXAMPLE:
sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True)
sage: F,s = sr.polynomial_system()
sage: I = F.ideal()
sage: I.interreduced_basis()
[k000*s000 + k002*s000 + k002*s001 + k002*s003 + k003*s001 + k003*s002 + k003*s003 + s001 + k001 + k003,
k000*s001 + k001*s003 + k002*s000 + k002*s001 + k002*s003 + k003*s000 + s001,
k000*s002 + k001*s000 + k001*s001 + k001*s003 + k002*s001 + k003*s000 + k003*s002 + s001,
k000*s003 + k001*s001 + k001*s002 + k001*s003 + k002*s001 + k003*s000 + k003*s001 + s001 + k001,
k001*s000 + k001*s003 + k002*s000 + k002*s001 + k003*s000 + k003*s002 + k003*s003 + s001 + 1,
k001*s001 + k001*s003 + k002*s000 + k002*s001 + k002*s003 + k003*s002 + k003*s003 + k003,
k001*s002 + k002*s000 + k002*s003 + k003*s001 + k003*s002 + s003 + 1,
k001*s003 + k002*s000 + k002*s001 + k002*s002 + s001 + k001 + k003 + 1,
k001*k000 + k002*k000 + k003*s002 + k003,
k002*s000 + k002*s002 + k003*s001 + k003*s002 + s001 + k000 + k001 + k002,
k002*s001 + k002*s003 + k003*s000 + k003*s001 + s003 + k000 + k001 + k003,
k002*s002 + k003*s003 + s000 + s001 + k000 + k001 + 1,
k002*s003 + k003*s000 + k003*s001 + k003*s002 + k003*s003 + s002 + s003 + k001,
k002*k000 + k000 + k002 + 1,
k002*k001 + k003*s002 + k003*k002 + k002 + k003,
k003*s001 + k003*s002 + k003*s003 + k001,
k003*k000 + s001 + 1,
k003*k001 + s001 + k000 + k003,
k003*k002 + s001 + k002 + 1,
k100 + x103 + s001 + s002 + 1,
k101 + x102 + x103 + s002,
k102 + x100 + x103 + s001 + s002 + s003,
k103 + x101 + x102 + x103,
x100 + x103 + s001 + s003 + 1,
x101 + x102 + x103 + s001 + s002 + s003 + 1,
x102 + x103 + s002 + s003 + 1,
x103 + s003 + 1,
w100 + k000 + 1,
w101,
w102 + k002 + 1,
w103 + k003 + 1,
s000 + s001,
s001 + k002 + k003 + 1,
s002 + k002 + k003 + 1,
s003 + k002 + 1,
k001]
Reduce an element modulo the reduced Groebner basis for this ideal. This returns 0 if and only if the element is in this ideal. In any case, this reduction is unique up to monomial orders.
EXAMPLE:
sage: P = PolynomialRing(GF(2),10, 'x')
sage: B = BooleanPolynomialRing(10,'x')
sage: I = sage.rings.ideal.Cyclic(P)
sage: I = B.ideal([B(f) for f in I.gens()])
sage: gb = I.groebner_basis()
sage: I.reduce(gb[0])
0
sage: I.reduce(gb[0] + 1)
1
sage: I.reduce(gb[0]*gb[1])
0
sage: I.reduce(gb[0]*B.gen(1))
0
Iterator over the monomials of a boolean polynomial.
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: list(B.random_element()) # indirect doctest
[a*c, a*d, a, b*d, 1]
EXAMPLE:
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: it = iter(B.random_element())
sage: it.next() # indirect doctest
a*c
Construct a boolean polynomial ring with the following parameters:
INPUT:
n - number of variables (an integer > 1)
list/tuple
order - term order (default: lex)
EXAMPLES:
sage: R.<x, y, z> = BooleanPolynomialRing()
sage: R
Boolean PolynomialRing in x, y, z
sage: p = x*y + x*z + y*z
sage: x*p
x*y*z + x*y + x*z
sage: R.term_order()
Lexicographic term order
sage: R = BooleanPolynomialRing(5,'x',order='deglex(3),deglex(2)')
sage: R.term_order()
deglex(3),deglex(2) term order
sage: R = BooleanPolynomialRing(3,'x',order='degrevlex')
sage: R.term_order()
Degree reverse lexicographic term order
TESTS:
sage: P.<x,y> = BooleanPolynomialRing(2,order='degrevlex')
sage: x > y
True
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4,order='degrevlex(2),degrevlex(2)')
sage: x0 > x1
True
sage: x2 > x3
True
Convert elements of other objects to this boolean polynomial ring.
EXAMPLE:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(5)
1
sage: P(x+y)
x + y
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: R = BooleanPolynomialRing(1,'y')
sage: p = R(y); p
y
sage: p.parent()
Boolean PolynomialRing in y
sage: P = BooleanPolynomialRing(2,'x,y')
sage: R.<z,x,y> = ZZ['z,x,y']
sage: t = x^2*y + 5*y^3
sage: p = P(t); p
x*y + y
sage: p.parent()
Boolean PolynomialRing in x, y
TESTS:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: R = BooleanPolynomialRing(1,'y')
sage: p = R(x+y+x*y+1)
...
ValueError: cannot convert polynomial x*y + x + y + 1 to Boolean PolynomialRing in y: name x not defined
sage: P = BooleanPolynomialRing(2,'x,y')
sage: R.<z,x,y> = ZZ['z,x,y']
sage: t = x^2*z+5*y^3
sage: p = P(t)
...
ValueError: cannot convert polynomial z*x^2 + 5*y^3 to Boolean PolynomialRing in x, y: name z not defined
EXAMPLE:
sage: P.<a,b> = BooleanPolynomialRing(2)
sage: loads(dumps(P)) == P # indirect doctest
True
Change the ordering of this boolean polynomial ring. Do NOT call this method, unless you know very well what you are doing.
INPUT:
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: y*z > x
True
Now we call the internal method and change the ordering to ‘lex’:
sage: B._change_ordering(0)
sage: y*z > x
False
However, this change is not - and should not be - picked up by the public interface.
sage: B.term_order()
Degree lexicographic term order
Warning
Do not use this method. It is provided for compatibility reasons with PolyBoRi but parents are supposed to be immutable in Sage.
Return a string which when evaluated with Magma returns a Magma representation of this boolean polynomial ring.
INPUT:
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: magma(B) # indirect doctest; optional - magma
Affine Algebra of rank 3 over GF(2)
Lexicographical Order
Variables: x, y, z
Quotient relations:
[
x^2 + x,
y^2 + y,
z^2 + z
]
Choose a random monomial using variables indexed in
vars_set up to given degree. The
degree of the monomial, , is chosen uniformly in the
interval [0,degree] first, then the monomial is generated by
selecting a random sample of size
from
vars_set.
INPUT:
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: [P._random_monomial_dfirst(3, (0,1,2)) for _ in range(10)]
[x*y*z, x*y*z, x*y*z, y*z, x*z, z, z, y*z, x*y*z, 1]
Choose a random monomial uniformly from set of monomials in the variables indexed by vars_set in self.
INPUT:
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: [P._random_monomial_uniform([1, 3, 4], (0,1)) for _ in range(10)]
[x*y, x*y, x, x, x, x*y, x, y, x*y, 1]
Recursively generate a random polynomial in in this ring, using the variables from vars_set.
INPUT:
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P._random_uniform_rec(2, [1, 3, 4], (0,1), True, 2)
x + y
sage: P._random_uniform_rec(2, [1, 3, 4], (0,1), True, 2)
0
EXAMPLE:
sage: P.<x, y> = BooleanPolynomialRing(2)
sage: P # indirect doctest
Boolean PolynomialRing in x, y
Set variable name of i-th variable to s.
This function is used by PolyBoRi python functions.
INPUT:
EXAMPLES:
sage: P.<x0,x1> = BooleanPolynomialRing(2)
sage: P
Boolean PolynomialRing in x0, x1
sage: P._set_variable_name(0, 't')
sage: P
Boolean PolynomialRing in t, x1
Warning
Do not use this method. It is provided for compatibility reasons with PolyBoRi but parents are supposed to be immutable in Sage.
Return a newly created Singular quotient ring matching this boolean polynomial ring.
Note
TODO: This method does not only return a string but actually calls Singular.
EXAMPLE:
sage: B.<x,y> = BooleanPolynomialRing(2)
sage: B._singular_()
// characteristic : 2
// number of vars : 2
// block 1 : ordering lp
// : names x y
// block 2 : ordering C
// quotient ring from ideal
_[1]=x2+x
_[2]=y2+y
Return if
is the
ordered list of variable names of this ring.
also has
the same term ordering as this ring.
EXAMPLE:
sage: B.<x,y> = BooleanPolynomialRing(2)
sage: R = B.cover_ring(); R
Multivariate Polynomial Ring in x, y over Finite Field of size 2
sage: B.term_order() == R.term_order()
True
The cover ring is cached:
sage: B.cover_ring() is B.cover_ring()
True
Return where
,
the ordered list
of variables/variable names of this ring and
any
element in
.
EXAMPLE:
sage: B.<x,y> = BooleanPolynomialRing(2)
sage: I = B.defining_ideal(); I
Ideal (x^2 + x, y^2 + y) of Multivariate Polynomial Ring
in x, y over Finite Field of size 2
Returns the i-th generator of this boolean polynomial ring.
INPUT:
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.gen()
x
sage: P.gen(2)
z
sage: m = x.monomials()[0]
sage: P.gen(m)
x
TESTS:
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='dp')
sage: P.gen(0)
x
Return the tuple of variables in this ring.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.gens()
(x, y, z)
sage: P = BooleanPolynomialRing(10,'x')
sage: P.gens()
(x0, x1, x2, x3, x4, x5, x6, x7, x8, x9)
TESTS:
sage: P.<x,y,z> = BooleanPolynomialRing(3,order='degrevlex')
sage: P.gens()
(x, y, z)
Create an ideal in this ring.
INPUT:
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.ideal(x+y)
Ideal (x + y) of Boolean PolynomialRing in x, y, z
sage: P.ideal(x*y, y*z)
Ideal (x*y, y*z) of Boolean PolynomialRing in x, y, z
sage: P.ideal([x+y, z])
Ideal (x + y, z) of Boolean PolynomialRing in x, y, z
Return the lexicographically minimal boolean polynomial for the given sets of points.
Given two sets of points zeros - evaluating to zero - and ones - evaluating to one -, compute the lexicographically minimal boolean polynomial satisfying these points.
INPUT:
EXAMPLE:
First we create a random-ish boolean polynomial.
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing(6)
sage: f = a*b*c*e + a*d*e + a*f + b + c + e + f + 1
Now we find interpolation points mapping to zero and to one.
sage: zeros = set([(1, 0, 1, 0, 0, 0), (1, 0, 0, 0, 1, 0), \
(0, 0, 1, 1, 1, 1), (1, 0, 1, 1, 1, 1), \
(0, 0, 0, 0, 1, 0), (0, 1, 1, 1, 1, 0), \
(1, 1, 0, 0, 0, 1), (1, 1, 0, 1, 0, 1)])
sage: ones = set([(0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 1, 0), \
(0, 0, 0, 1, 1, 1), (1, 0, 0, 1, 0, 1), \
(0, 0, 0, 0, 1, 1), (0, 1, 1, 0, 1, 1), \
(0, 1, 1, 1, 1, 1), (1, 1, 1, 0, 1, 0)])
sage: [f(*p) for p in zeros]
[0, 0, 0, 0, 0, 0, 0, 0]
sage: [f(*p) for p in ones]
[1, 1, 1, 1, 1, 1, 1, 1]
Finally, we find the lexicographically smallest interpolation polynomial using PolyBoRi .
sage: g = B.interpolation_polynomial(zeros, ones); g
b*f + c + d*f + d + e*f + e + 1
sage: [g(*p) for p in zeros]
[0, 0, 0, 0, 0, 0, 0, 0]
sage: [g(*p) for p in ones]
[1, 1, 1, 1, 1, 1, 1, 1]
Alternatively, we can work with PolyBoRi’s native BooleSet‘s. This example is from the PolyBoRi tutorial:
sage: B = BooleanPolynomialRing(4,"x0,x1,x2,x3")
sage: x = B.gen
sage: V=(x(0)+x(1)+x(2)+x(3)+1).set(); V
{{x0}, {x1}, {x2}, {x3}, {}}
sage: f=x(0)*x(1)+x(1)+x(2)+1
sage: z = f.zerosIn(V); z
{{x1}, {x2}}
sage: o = V.diff(z); o
{{x0}, {x3}, {}}
sage: B.interpolation_polynomial(z,o)
x1 + x2 + 1
ALGORITHM: Calls interpolate_smallest_lex as described in the PolyBoRi tutorial.
Returns the number of variables in this boolean polynomial ring.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P.ngens()
2
sage: P = BooleanPolynomialRing(1000, 'x')
sage: P.ngens()
1000
Return a random boolean polynomial. Generated polynomial has the given number of terms, and at most given degree.
INPUT:
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.random_element(degree=3, terms=4)
x*y*z + x*z + y*z + z
sage: P.random_element(degree=1, terms=2)
z + 1
TESTS:
sage: P.random_element(degree=4)
...
ValueError: Given degree should be less than or equal to number of variables (3)
sage: t = P.random_element(degree=1, terms=5)
...
ValueError: Cannot generate random polynomial with 5 terms and maximum degree 1 using 3 variables
sage: t = P.random_element(degree=2,terms=5,vars_set=(0,1))
...
ValueError: Cannot generate random polynomial with 5 terms using 2 variables
Return the currently active global ring, this is only relevant for the native PolyBoRi interface.
sage: from polybori import declare_ring, get_cring, Block
sage: R = declare_ring([Block('x',2),Block('y',3)],globals())
sage: Q = get_cring(); Q
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: R is Q
True
Return a variable mapping between variables of other and ring. When other is a parent object, the mapping defines images for all variables of other. If it is an element, only variables occurring in other are mapped.
Raises NameError if no such mapping is possible.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: R.<z,y> = QQ[]
sage: sage.rings.polynomial.pbori.get_var_mapping(P,R)
[z, y]
sage: sage.rings.polynomial.pbori.get_var_mapping(P, z^2)
[z, None]
sage: R.<z,x> = BooleanPolynomialRing(2)
sage: sage.rings.polynomial.pbori.get_var_mapping(P,R)
[z, x]
sage: sage.rings.polynomial.pbori.get_var_mapping(P, x^2)
[None, x]
The opposite of navigating down a ZDD using navigators is to construct new ZDDs in the same way, namely giving their else- and then-branch as well as the index value of the new node.
INPUT:
EXAMPLE:
sage: from polybori import if_then_else
sage: B = BooleanPolynomialRing(6,'x')
sage: x0,x1,x2,x3,x4,x5 = B.gens()
sage: f0 = x2*x3+x3
sage: f1 = x4
sage: if_then_else(x1, f0, f1)
{{x1,x2,x3}, {x1,x3}, {x4}}
sage: if_then_else(x1.lm().index(),f0,f1)
{{x1,x2,x3}, {x1,x3}, {x4}}
sage: if_then_else(x5, f0, f1)
...
IndexError: index of root must be less than the values of roots of the branches.
Set the currently active global ring, this is only relevant for the native PolyBoRi interface.
sage: from polybori import *
sage: declare_ring([Block('x',2),Block('y',3)],globals())
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: R = get_cring(); R
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
sage: declare_ring([Block('x',2),Block('y',2)],globals())
Boolean PolynomialRing in x(0), x(1), y(0), y(1)
sage: get_cring()
Boolean PolynomialRing in x(0), x(1), y(0), y(1)
sage: set_cring(R)
sage: get_cring()
Boolean PolynomialRing in x(0), x(1), y(0), y(1), y(2)
Return the highest index in the parameter s.
INPUT:
EXAMPLE:
sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: from polybori import top_index
sage: top_index(x.lm())
0
sage: top_index(y*z)
1
sage: top_index(x + 1)
0
Unpickle boolean polynomials
EXAMPLE:
sage: T = TermOrder('deglex',2)+TermOrder('deglex',2)
sage: P.<a,b,c,d> = BooleanPolynomialRing(4,order=T)
sage: loads(dumps(a+b)) == a+b # indirect doctest
True
Unpickle boolean polynomial rings.
EXAMPLE:
sage: T = TermOrder('deglex',2)+TermOrder('deglex',2)
sage: P.<a,b,c,d> = BooleanPolynomialRing(4,order=T)
sage: loads(dumps(P)) == P # indirect doctest
True