Boolean Polynomials

Elements of the quotient ring

\[\GF{2}[x_1,...,x_n]/<x_1^2+x_1,...,x_n^2+x_n>.\]

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 \(x^2=x\) for each variable \(x\). 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.” - [BD2007]

For details on the internal representation of polynomials see

http://polybori.sourceforge.net/zdd.html

AUTHORS:

• Michael Brickenstein: PolyBoRi author

• Alexander Dreyer: PolyBoRi author

• Burcin Erocal <burcin@erocal.org>: main Sage wrapper author

• Martin Albrecht <malb@informatik.uni-bremen.de>: some contributions to the Sage wrapper

• Simon King <simon.king@uni-jena.de>: Adopt the new coercion model. Fix conversion from univariate polynomial rings. Pickling of BooleanMonomialMonoid (via UniqueRepresentation) and BooleanMonomial.

• Charles Bouillaguet <charles.bouillaguet@gmail.com>: minor changes to improve compatibility with MPolynomial and make the variety() function work on ideals of BooleanPolynomial’s.

EXAMPLES:

Consider the ideal

\[<ab + cd + 1, ace + de, abe + ce, bc + cde + 1>.\]

First, we compute the lexicographical Groebner basis in the polynomial ring

\[R = \GF{2}[a,b,c,d,e].\]

Sage

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

Python

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(2)), Integer(5), order='lex', names=('a', 'b', 'c', 'd', 'e',)); (a, b, c, d, e,) = P._first_ngens(5)
>>> I1 = ideal([a*b + c*d + Integer(1), a*c*e + d*e, a*b*e + c*e, b*c + c*d*e + Integer(1)])
>>> 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 \(\GF{2}\) then this Groebner basis was the one to consider. If one wants solutions over \(\GF{2}\) only then one adds the field polynomials to the ideal to force the solutions in \(\GF{2}\).

Sage

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

Python

>>> from sage.all import *
>>> J = I1 + sage.rings.ideal.FieldIdeal(P)
>>> for f in J.groebner_basis():
...   f
a + d + 1
b + 1
c + 1
d^2 + d
e

So the solutions over \(\GF{2}\) are \(\{e=0, d=1, c=1, b=1, a=0\}\) and \(\{e=0, d=0, c=1, b=1, a=1\}\).

We can express the restriction to \(\GF{2}\) by considering the quotient ring. If \(I\) is an ideal in \(\Bold{F}[x_1, ..., x_n]\) then the ideals in the quotient ring \(\Bold{F}[x_1, ..., x_n]/I\) are in one-to-one correspondence with the ideals of \(\Bold{F}[x_0, ..., x_n]\) containing \(I\) (that is, the ideals \(J\) satisfying \(I \subset J \subset P\)).

Sage

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

Python

>>> from sage.all import *
>>> Q = P.quotient( sage.rings.ideal.FieldIdeal(P) )
>>> I2 = ideal([Q(f) for f in I1.gens()])
>>> 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

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

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5), order='lex', names=('a', 'b', 'c', 'd', 'e',)); (a, b, c, d, e,) = B._first_ngens(5)
>>> I2 = ideal([B(f) for f in I1.gens()])
>>> for f in I2.groebner_basis():
...   f
a + d + 1
b + 1
c + 1
e

Note that d^2 + d is not representable in B == Q. 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.

Implementation specific notes

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.

Access to the original PolyBoRi interface

The re-implementation PolyBoRi’s native wrapper is available to the user too:

Sage

sage: from sage.rings.polynomial.pbori import *
sage: declare_ring([Block('x',2),Block('y',3)],globals())
Boolean PolynomialRing in x0, x1, y0, y1, y2
sage: r
Boolean PolynomialRing in x0, x1, y0, y1, y2

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori import *
>>> declare_ring([Block('x',Integer(2)),Block('y',Integer(3))],globals())
Boolean PolynomialRing in x0, x1, y0, y1, y2
>>> r
Boolean PolynomialRing in x0, x1, y0, y1, y2

Sage

sage: [Variable(i, r) for i in range(r.ngens())]
[x(0), x(1), y(0), y(1), y(2)]

Python

>>> from sage.all import *
>>> [Variable(i, r) for i in range(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.

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 BooleSet (PolyBoRi) and naturally the second option is faster.

class sage.rings.polynomial.pbori.pbori.BooleConstant

Bases: object

Construct a boolean constant (modulo 2) from integer value:

INPUT:

• i – integer

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleConstant
sage: [BooleConstant(i) for i in range(5)]
[0, 1, 0, 1, 0]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleConstant
>>> [BooleConstant(i) for i in range(Integer(5))]
[0, 1, 0, 1, 0]

deg()

Get degree of boolean constant.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleConstant
sage: BooleConstant(0).deg()
-1
sage: BooleConstant(1).deg()
0

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleConstant
>>> BooleConstant(Integer(0)).deg()
-1
>>> BooleConstant(Integer(1)).deg()
0

has_constant_part()

This is true for \(BooleConstant(1)\).

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleConstant
sage: BooleConstant(1).has_constant_part()
True
sage: BooleConstant(0).has_constant_part()
False

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleConstant
>>> BooleConstant(Integer(1)).has_constant_part()
True
>>> BooleConstant(Integer(0)).has_constant_part()
False

is_constant()

This is always true for in this case.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleConstant
sage: BooleConstant(1).is_constant()
True
sage: BooleConstant(0).is_constant()
True

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleConstant
>>> BooleConstant(Integer(1)).is_constant()
True
>>> BooleConstant(Integer(0)).is_constant()
True

is_one()

Check whether boolean constant is one.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleConstant
sage: BooleConstant(0).is_one()
False
sage: BooleConstant(1).is_one()
True

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleConstant
>>> BooleConstant(Integer(0)).is_one()
False
>>> BooleConstant(Integer(1)).is_one()
True

is_zero()

Check whether boolean constant is zero.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleConstant
sage: BooleConstant(1).is_zero()
False
sage: BooleConstant(0).is_zero()
True

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleConstant
>>> BooleConstant(Integer(1)).is_zero()
False
>>> BooleConstant(Integer(0)).is_zero()
True

variables()

Get variables (return always and empty tuple).

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleConstant
sage: BooleConstant(0).variables()
()
sage: BooleConstant(1).variables()
()

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleConstant
>>> BooleConstant(Integer(0)).variables()
()
>>> BooleConstant(Integer(1)).variables()
()

class sage.rings.polynomial.pbori.pbori.BooleSet

Bases: object

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.

Objects of type BooleanPolynomial can easily be converted to the type BooleSet by using the member function BooleanPolynomial.set().

INPUT:

• param – either a CCuddNavigator, a BooleSet or None

• ring – boolean polynomial ring

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleSet
sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = BooleSet(a.set())
sage: BS
{{a}}

sage: BS = BooleSet((a*b + c + 1).set())
sage: BS
{{a,b}, {c}, {}}

sage: from sage.rings.polynomial.pbori.pbori import *
sage: from sage.rings.polynomial.pbori.PyPolyBoRi import Monomial
sage: BooleSet([Monomial(B)])
{{}}

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleSet
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> BS = BooleSet(a.set())
>>> BS
{{a}}

>>> BS = BooleSet((a*b + c + Integer(1)).set())
>>> BS
{{a,b}, {c}, {}}

>>> from sage.rings.polynomial.pbori.pbori import *
>>> from sage.rings.polynomial.pbori.PyPolyBoRi import Monomial
>>> BooleSet([Monomial(B)])
{{}}

Note

BooleSet prints as {} but are not Python dictionaries.

cartesian_product(rhs)

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.

\[X\times Y = \{(x,y) | x\in X\;\mathrm{and}\;y\in Y\}.\]

EXAMPLES:

Sage

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.cartesian_product(t)
{{x1,x2,x4}, {x1,x2}, {x2,x3,x4}, {x2,x3}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3
>>> s = f.set(); s
{{x1,x2}, {x2,x3}}
>>> g = x4 + Integer(1)
>>> t = g.set(); t
{{x4}, {}}
>>> s.cartesian_product(t)
{{x1,x2,x4}, {x1,x2}, {x2,x3,x4}, {x2,x3}}

change(ind)

Swaps the presence of x_i in each entry of the set.

EXAMPLES:

Sage

sage: P.<a,b,c> = BooleanPolynomialRing()
sage: f = a+b
sage: s = f.set(); s
{{a}, {b}}
sage: s.change(0)
{{a,b}, {}}
sage: s.change(1)
{{a,b}, {}}
sage: s.change(2)
{{a,c}, {b,c}}

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(names=('a', 'b', 'c',)); (a, b, c,) = P._first_ngens(3)
>>> f = a+b
>>> s = f.set(); s
{{a}, {b}}
>>> s.change(Integer(0))
{{a,b}, {}}
>>> s.change(Integer(1))
{{a,b}, {}}
>>> s.change(Integer(2))
{{a,c}, {b,c}}

diff(rhs)

Return the set theoretic difference of this set and the set rhs.

The difference of two sets \(X\) and \(Y\) is defined as:

\[X \ Y = \{x | x\in X\;\mathrm{and}\;x\not\in Y\}.\]

EXAMPLES:

Sage

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}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3
>>> s = f.set(); s
{{x1,x2}, {x2,x3}}
>>> g = x2*x3 + Integer(1)
>>> t = g.set(); t
{{x2,x3}, {}}
>>> s.diff(t)
{{x1,x2}}

divide(rhs)

Divide each element of this set by the monomial rhs and return a new set containing the result.

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing(order='lex')
sage: f = b*e + b*c*d + b
sage: s = f.set(); s
{{b,c,d}, {b,e}, {b}}
sage: s.divide(b.lm())
{{c,d}, {e}, {}}

sage: f = b*e + b*c*d + b + c
sage: s = f.set()
sage: s.divide(b.lm())
{{c,d}, {e}, {}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(order='lex', names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> f = b*e + b*c*d + b
>>> s = f.set(); s
{{b,c,d}, {b,e}, {b}}
>>> s.divide(b.lm())
{{c,d}, {e}, {}}

>>> f = b*e + b*c*d + b + c
>>> s = f.set()
>>> s.divide(b.lm())
{{c,d}, {e}, {}}

divisors_of(m)

Return those members which are divisors of m.

INPUT:

• m – boolean monomial

EXAMPLES:

Sage

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set()
sage: s.divisors_of((x1*x2*x4).lead())
{{x1,x2}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3
>>> s = f.set()
>>> s.divisors_of((x1*x2*x4).lead())
{{x1,x2}}

empty()

Return True if this set is empty.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> BS = (a*b + c).set()
>>> BS.empty()
False

>>> BS = B(Integer(0)).set()
>>> BS.empty()
True

include_divisors()

Extend this set to include all divisors of the elements already in this set and return the result as a new set.

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: f = a*d*e + a*f + b*d*e + c*d*e + 1
sage: s = f.set(); s
{{a,d,e}, {a,f}, {b,d,e}, {c,d,e}, {}}

sage: s.include_divisors()
{{a,d,e}, {a,d}, {a,e}, {a,f}, {a}, {b,d,e}, {b,d}, {b,e},
 {b}, {c,d,e}, {c,d}, {c,e}, {c}, {d,e}, {d}, {e}, {f}, {}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> f = a*d*e + a*f + b*d*e + c*d*e + Integer(1)
>>> s = f.set(); s
{{a,d,e}, {a,f}, {b,d,e}, {c,d,e}, {}}

>>> s.include_divisors()
{{a,d,e}, {a,d}, {a,e}, {a,f}, {a}, {b,d,e}, {b,d}, {b,e},
 {b}, {c,d,e}, {c,d}, {c,e}, {c}, {d,e}, {d}, {e}, {f}, {}}

intersect(other)

Return the set theoretic intersection of this set and the set rhs.

The union of two sets \(X\) and \(Y\) is defined as:

\[X \cap Y = \{x | x\in X\;\mathrm{and}\;x\in Y\}.\]

EXAMPLES:

Sage

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.intersect(t)
{{x2,x3}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3
>>> s = f.set(); s
{{x1,x2}, {x2,x3}}
>>> g = x2*x3 + Integer(1)
>>> t = g.set(); t
{{x2,x3}, {}}
>>> s.intersect(t)
{{x2,x3}}

minimal_elements()

Return a new set containing a divisor of all elements of this set.

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: f = a*d*e + a*f + a*b*d*e + a*c*d*e + a
sage: s = f.set(); s
{{a,b,d,e}, {a,c,d,e}, {a,d,e}, {a,f}, {a}}
sage: s.minimal_elements()
{{a}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> f = a*d*e + a*f + a*b*d*e + a*c*d*e + a
>>> s = f.set(); s
{{a,b,d,e}, {a,c,d,e}, {a,d,e}, {a,f}, {a}}
>>> s.minimal_elements()
{{a}}

multiples_of(m)

Return those members which are multiples of m.

INPUT:

• m – boolean monomial

EXAMPLES:

Sage

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set()
sage: s.multiples_of(x1.lm())
{{x1,x2}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3
>>> s = f.set()
>>> s.multiples_of(x1.lm())
{{x1,x2}}

n_nodes()

Return the number of nodes in the ZDD.

EXAMPLES:

Sage

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.n_nodes()
4

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3
>>> s = f.set(); s
{{x1,x2}, {x2,x3}}
>>> s.n_nodes()
4

navigation()

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.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori 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.else_branch()

sage: BooleSet(nav_else, s.ring())
{{x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

sage: nav_else.value()
2

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleSet
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3*x4+x2*x4+x3+x4+Integer(1)
>>> s = f.set(); s
{{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

>>> nav = s.navigation()
>>> BooleSet(nav, s.ring())
{{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

>>> nav.value()
1

>>> nav_else = nav.else_branch()

>>> BooleSet(nav_else, s.ring())
{{x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

>>> nav_else.value()
2

ring()

Return the parent ring.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3*x4+x2*x4+x3+x4+Integer(1)
>>> f.set().ring() is B
True

set()

Return self.

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: BS = (a*b + c).set()
sage: BS.set() is BS
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> BS = (a*b + c).set()
>>> BS.set() is BS
True

size_double()

Return the size of this set as a floating point number.

EXAMPLES:

Sage

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2+x2*x3
sage: s = f.set()
sage: s.size_double()
2.0

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3
>>> s = f.set()
>>> s.size_double()
2.0

stable_hash()

A hash value which is stable across processes.

EXAMPLES:

Sage

sage: B.<x,y> = BooleanPolynomialRing()
sage: x.set() is x.set()
False
sage: x.set().stable_hash() == x.set().stable_hash()
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('x', 'y',)); (x, y,) = B._first_ngens(2)
>>> x.set() is x.set()
False
>>> x.set().stable_hash() == x.set().stable_hash()
True

Note

This function is part of the upstream PolyBoRi interface. In Sage all hashes are stable.

subset0(i)

Return a set of those elements in this set which do not contain the variable indexed by i.

INPUT:

• i – an index

EXAMPLES:

Sage

sage: BooleanPolynomialRing(5,'x')
Boolean PolynomialRing in x0, x1, x2, x3, x4
sage: B = BooleanPolynomialRing(5,'x')
sage: B.inject_variables()
Defining x0, x1, x2, x3, x4
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: s.subset0(1)
{{x2,x3}}

Python

>>> from sage.all import *
>>> BooleanPolynomialRing(Integer(5),'x')
Boolean PolynomialRing in x0, x1, x2, x3, x4
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> B.inject_variables()
Defining x0, x1, x2, x3, x4
>>> f = x1*x2+x2*x3
>>> s = f.set(); s
{{x1,x2}, {x2,x3}}
>>> s.subset0(Integer(1))
{{x2,x3}}

subset1(i)

Return a set of those elements in this set which do contain the variable indexed by i and evaluate the variable indexed by i to 1.

INPUT:

• i – an index

EXAMPLES:

Sage

sage: BooleanPolynomialRing(5,'x')
Boolean PolynomialRing in x0, x1, x2, x3, x4
sage: B = BooleanPolynomialRing(5,'x')
sage: B.inject_variables()
Defining x0, x1, x2, x3, x4
sage: f = x1*x2+x2*x3
sage: s = f.set(); s
{{x1,x2}, {x2,x3}}
sage: s.subset1(1)
{{x2}}

Python

>>> from sage.all import *
>>> BooleanPolynomialRing(Integer(5),'x')
Boolean PolynomialRing in x0, x1, x2, x3, x4
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> B.inject_variables()
Defining x0, x1, x2, x3, x4
>>> f = x1*x2+x2*x3
>>> s = f.set(); s
{{x1,x2}, {x2,x3}}
>>> s.subset1(Integer(1))
{{x2}}

union(rhs)

Return the set theoretic union of this set and the set rhs.

The union of two sets \(X\) and \(Y\) is defined as:

\[X \cup Y = \{x | x\in X\;\mathrm{or}\;x\in Y\}.\]

EXAMPLES:

Sage

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.union(t)
{{x1,x2}, {x2,x3}, {}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3
>>> s = f.set(); s
{{x1,x2}, {x2,x3}}
>>> g = x2*x3 + Integer(1)
>>> t = g.set(); t
{{x2,x3}, {}}
>>> s.union(t)
{{x1,x2}, {x2,x3}, {}}

vars()

Return the variables in this set as a monomial.

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing(order='lex')
sage: f = a + b*e + d*f + e + 1
sage: s = f.set()
sage: s
{{a}, {b,e}, {d,f}, {e}, {}}
sage: s.vars()
a*b*d*e*f

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(order='lex', names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> f = a + b*e + d*f + e + Integer(1)
>>> s = f.set()
>>> s
{{a}, {b,e}, {d,f}, {e}, {}}
>>> s.vars()
a*b*d*e*f

class sage.rings.polynomial.pbori.pbori.BooleSetIterator

Bases: object

Helper class to iterate over boolean sets.

class sage.rings.polynomial.pbori.pbori.BooleanMonomial

Bases: MonoidElement

Construct a boolean monomial.

INPUT:

• parent – parent monoid this element lives in

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid, BooleanMonomial
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: BooleanMonomial(M)
1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid, BooleanMonomial
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> M = BooleanMonomialMonoid(P)
>>> BooleanMonomial(M)
1

Note

Use the BooleanMonomialMonoid__call__() method and not this constructor to construct these objects.

deg()

Return degree of this monomial.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori 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

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> M = BooleanMonomialMonoid(P)
>>> M(x*y).deg()
2

>>> M(x*x*y*z).deg()
3

Note

This function is part of the upstream PolyBoRi interface.

degree(x=None)

Return the degree of this monomial in x, where x must be one of the generators of the polynomial ring.

INPUT:

• x – boolean multivariate polynomial (a generator of the polynomial ring). If x is not specified (or is None), return the total degree of this monomial.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M(x*y).degree()
2
sage: M(x*y).degree(x)
1
sage: M(x*y).degree(z)
0

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> M = BooleanMonomialMonoid(P)
>>> M(x*y).degree()
2
>>> M(x*y).degree(x)
1
>>> M(x*y).degree(z)
0

divisors()

Return a set of boolean monomials with all divisors of this monomial.

EXAMPLES:

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.divisors()
{{x,y}, {x}, {y}, {}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> f = x*y
>>> m = f.lm()
>>> m.divisors()
{{x,y}, {x}, {y}, {}}

gcd(rhs)

Return the greatest common divisor of this boolean monomial and rhs.

INPUT:

• rhs – boolean monomial

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: a,b,c,d = a.lm(), b.lm(), c.lm(), d.lm()
sage: (a*b).gcd(b*c)
b
sage: (a*b*c).gcd(d)
1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> a,b,c,d = a.lm(), b.lm(), c.lm(), d.lm()
>>> (a*b).gcd(b*c)
b
>>> (a*b*c).gcd(d)
1

index()

Return the variable index of the first variable in this monomial.

EXAMPLES:

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.index()
0

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> f = x*y
>>> m = f.lm()
>>> m.index()
0

Note

This function is part of the upstream PolyBoRi interface.

iterindex()

Return an iterator over the indices of the variables in self.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: list(M(x*z).iterindex())
[0, 2]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> M = BooleanMonomialMonoid(P)
>>> list(M(x*z).iterindex())
[0, 2]

multiples(rhs)

Return a set of boolean monomials with all multiples of this monomial up to the bound rhs.

INPUT:

• rhs – boolean monomial

EXAMPLES:

Sage

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}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> f = x
>>> m = f.lm()
>>> g = x*y*z
>>> n = g.lm()
>>> m.multiples(n)
{{x,y,z}, {x,y}, {x,z}, {x}}
>>> n.multiples(m)
{{x,y,z}}

Note

The returned set always contains self even if the bound rhs is smaller than self.

navigation()

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.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori 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: m = f.lm(); m
x1*x2

sage: nav = m.navigation()
sage: BooleSet(nav, B)
{{x1,x2}}

sage: nav.value()
1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleSet
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3*x4+x2*x4+x3+x4+Integer(1)
>>> m = f.lm(); m
x1*x2

>>> nav = m.navigation()
>>> BooleSet(nav, B)
{{x1,x2}}

>>> nav.value()
1

reducible_by(rhs)

Return True if self is reducible by rhs.

INPUT:

• rhs – boolean monomial

EXAMPLES:

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.reducible_by((x*y).lm())
True
sage: m.reducible_by((x*z).lm())
False

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> f = x*y
>>> m = f.lm()
>>> m.reducible_by((x*y).lm())
True
>>> m.reducible_by((x*z).lm())
False

ring()

Return the corresponding boolean ring.

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: a.lm().ring() is B
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> a.lm().ring() is B
True

set()

Return a boolean set of variables in this monomials.

EXAMPLES:

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*y
sage: m = f.lm()
sage: m.set()
{{x,y}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> f = x*y
>>> m = f.lm()
>>> m.set()
{{x,y}}

stable_hash()

A hash value which is stable across processes.

EXAMPLES:

Sage

sage: B.<x,y> = BooleanPolynomialRing()
sage: x.lm() is x.lm()
False
sage: x.lm().stable_hash() == x.lm().stable_hash()
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('x', 'y',)); (x, y,) = B._first_ngens(2)
>>> x.lm() is x.lm()
False
>>> x.lm().stable_hash() == x.lm().stable_hash()
True

Note

This function is part of the upstream PolyBoRi interface. In Sage all hashes are stable.

variables()

Return a tuple of the variables in this monomial.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M(x*z).variables() # indirect doctest
(x, z)

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> M = BooleanMonomialMonoid(P)
>>> M(x*z).variables() # indirect doctest
(x, z)

class sage.rings.polynomial.pbori.pbori.BooleanMonomialIterator

Bases: object

An iterator over the variable indices of a monomial.

class sage.rings.polynomial.pbori.pbori.BooleanMonomialMonoid(polring)

Bases: UniqueRepresentation, Monoid_class

Construct a boolean monomial monoid given a boolean polynomial ring.

This object provides a parent for boolean monomials.

INPUT:

• polring – the polynomial ring our monomials lie in

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori 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))
<class 'sage.rings.polynomial.pbori.pbori.BooleanMonomial'>

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> M = BooleanMonomialMonoid(P)
>>> M
MonomialMonoid of Boolean PolynomialRing in x, y

>>> M.gens()
(x, y)
>>> type(M.gen(Integer(0)))
<class 'sage.rings.polynomial.pbori.pbori.BooleanMonomial'>

Since Issue #9138, boolean monomial monoids are unique parents and are fit into the category framework:

Sage

sage: loads(dumps(M)) is M
True
sage: TestSuite(M).run()

Python

>>> from sage.all import *
>>> loads(dumps(M)) is M
True
>>> TestSuite(M).run()

gen(i=0)

Return the \(i\)-th generator of self.

INPUT:

• i – integer

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori 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

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> M = BooleanMonomialMonoid(P)
>>> M.gen(Integer(0))
x
>>> M.gen(Integer(2))
z

>>> P = BooleanPolynomialRing(Integer(1000), 'x')
>>> M = BooleanMonomialMonoid(P)
>>> M.gen(Integer(50))
x50

gens()

Return the tuple of generators of this monoid.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: M = BooleanMonomialMonoid(P)
sage: M.gens()
(x, y, z)

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> M = BooleanMonomialMonoid(P)
>>> M.gens()
(x, y, z)

ngens()

Return the number of variables in this monoid.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
sage: P = BooleanPolynomialRing(100, 'x')
sage: M = BooleanMonomialMonoid(P)
sage: M.ngens()
100

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleanMonomialMonoid
>>> P = BooleanPolynomialRing(Integer(100), 'x')
>>> M = BooleanMonomialMonoid(P)
>>> M.ngens()
100

class sage.rings.polynomial.pbori.pbori.BooleanMonomialVariableIterator

Bases: object

class sage.rings.polynomial.pbori.pbori.BooleanMulAction

Bases: Action

class sage.rings.polynomial.pbori.pbori.BooleanPolynomial

Bases: MPolynomial

Construct a boolean polynomial object in the given boolean polynomial ring.

INPUT:

• parent – boolean polynomial ring

Note

Do not use this method to construct boolean polynomials, but use the appropriate __call__ method in the parent.

constant()

Return True if this element is constant.

EXAMPLES:

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: x.constant()
False

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> x.constant()
False

Sage

sage: B(1).constant()
True

Python

>>> from sage.all import *
>>> B(Integer(1)).constant()
True

Note

This function is part of the upstream PolyBoRi interface.

constant_coefficient()

Return the constant coefficient of this boolean polynomial.

EXAMPLES:

Sage

sage: B.<a,b> = BooleanPolynomialRing()
sage: a.constant_coefficient()
0
sage: (a+1).constant_coefficient()
1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b',)); (a, b,) = B._first_ngens(2)
>>> a.constant_coefficient()
0
>>> (a+Integer(1)).constant_coefficient()
1

deg()

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

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).degree()
1

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> (x+y).degree()
1

Sage

sage: P(1).degree()
0

Python

>>> from sage.all import *
>>> P(Integer(1)).degree()
0

Sage

sage: (x*y + x + y + 1).degree()
2

Python

>>> from sage.all import *
>>> (x*y + x + y + Integer(1)).degree()
2

Note

This function is part of the upstream PolyBoRi interface.

degree(x=None)

Return the maximal degree of this polynomial in x, where x must be one of the generators for the parent of this polynomial.

If x is not specified (or is None), return the total degree, which is the maximum degree of any monomial.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).degree()
1

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> (x+y).degree()
1

Sage

sage: P(1).degree()
0

Python

>>> from sage.all import *
>>> P(Integer(1)).degree()
0

Sage

sage: (x*y + x + y + 1).degree()
2

sage: (x*y + x + y + 1).degree(x)
1

Python

>>> from sage.all import *
>>> (x*y + x + y + Integer(1)).degree()
2

>>> (x*y + x + y + Integer(1)).degree(x)
1

elength()

Return elimination length as used in the SlimGB algorithm.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: x.elength()
1
sage: f = x*y + 1
sage: f.elength()
2

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> x.elength()
1
>>> f = x*y + Integer(1)
>>> f.elength()
2

REFERENCES:

• Michael Brickenstein; SlimGB: Groebner Bases with Slim Polynomials http://www.mathematik.uni-kl.de/~zca/Reports_on_ca/35/paper_35_full.ps.gz

Note

This function is part of the upstream PolyBoRi interface.

first_term()

Return the first term with respect to the lexicographical term ordering.

EXAMPLES:

Sage

sage: B.<a,b,z> = BooleanPolynomialRing(3,order='lex')
sage: f = b*z + a + 1
sage: f.first_term()
a

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3),order='lex', names=('a', 'b', 'z',)); (a, b, z,) = B._first_ngens(3)
>>> f = b*z + a + Integer(1)
>>> f.first_term()
a

Note

This function is part of the upstream PolyBoRi interface.

graded_part(deg)

Return graded part of this boolean polynomial of degree deg.

INPUT:

• deg – a degree

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + c*d + a*b + 1
sage: f.graded_part(2)
a*b + c*d

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> f = a*b*c + c*d + a*b + Integer(1)
>>> f.graded_part(Integer(2))
a*b + c*d

Sage

sage: f.graded_part(0)
1

Python

>>> from sage.all import *
>>> f.graded_part(Integer(0))
1

has_constant_part()

Return True if this boolean polynomial has a constant part, i.e. if 1 is a term.

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + c*d + a*b + 1
sage: f.has_constant_part()
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> f = a*b*c + c*d + a*b + Integer(1)
>>> f.has_constant_part()
True

Sage

sage: f = a*b*c + c*d + a*b
sage: f.has_constant_part()
False

Python

>>> from sage.all import *
>>> f = a*b*c + c*d + a*b
>>> f.has_constant_part()
False

is_constant()

Check if self is constant.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P(Integer(1)).is_constant()
True

>>> P(Integer(0)).is_constant()
True

>>> x.is_constant()
False

>>> (x*y).is_constant()
False

is_equal(right)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('a', 'b', 'z',)); (a, b, z,) = B._first_ngens(3)
>>> f = a*z + b + Integer(1)
>>> g = b + z
>>> f.is_equal(g)
False

>>> f.is_equal((f + Integer(1)) - Integer(1))
True

Note

This function is part of the upstream PolyBoRi interface.

is_homogeneous()

Return True if this element is a homogeneous polynomial.

EXAMPLES:

Sage

sage: P.<x, y> = BooleanPolynomialRing()
sage: (x+y).is_homogeneous()
True
sage: P(0).is_homogeneous()
True
sage: (x+1).is_homogeneous()
False

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> (x+y).is_homogeneous()
True
>>> P(Integer(0)).is_homogeneous()
True
>>> (x+Integer(1)).is_homogeneous()
False

is_one()

Check if self is 1.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(1).is_one()
True

sage: P.one().is_one()
True

sage: x.is_one()
False

sage: P(0).is_one()
False

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P(Integer(1)).is_one()
True

>>> P.one().is_one()
True

>>> x.is_one()
False

>>> P(Integer(0)).is_one()
False

is_pair()

Check if self has exactly two terms.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(0).is_pair()
False

sage: x.is_pair()
False

sage: P(1).is_pair()
False

sage: (x*y).is_pair()
False

sage: (x + y).is_pair()
True

sage: (x + 1).is_pair()
True

sage: (x*y + 1).is_pair()
True

sage: (x + y + 1).is_pair()
False

sage: ((x + 1)*(y + 1)).is_pair()
False

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P(Integer(0)).is_pair()
False

>>> x.is_pair()
False

>>> P(Integer(1)).is_pair()
False

>>> (x*y).is_pair()
False

>>> (x + y).is_pair()
True

>>> (x + Integer(1)).is_pair()
True

>>> (x*y + Integer(1)).is_pair()
True

>>> (x + y + Integer(1)).is_pair()
False

>>> ((x + Integer(1))*(y + Integer(1))).is_pair()
False

is_singleton()

Check if self has at most one term.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(0).is_singleton()
True

sage: x.is_singleton()
True

sage: P(1).is_singleton()
True

sage: (x*y).is_singleton()
True

sage: (x + y).is_singleton()
False

sage: (x + 1).is_singleton()
False

sage: (x*y + 1).is_singleton()
False

sage: (x + y + 1).is_singleton()
False

sage: ((x + 1)*(y + 1)).is_singleton()
False

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P(Integer(0)).is_singleton()
True

>>> x.is_singleton()
True

>>> P(Integer(1)).is_singleton()
True

>>> (x*y).is_singleton()
True

>>> (x + y).is_singleton()
False

>>> (x + Integer(1)).is_singleton()
False

>>> (x*y + Integer(1)).is_singleton()
False

>>> (x + y + Integer(1)).is_singleton()
False

>>> ((x + Integer(1))*(y + Integer(1))).is_singleton()
False

is_singleton_or_pair()

Check if self has at most two terms.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(0).is_singleton_or_pair()
True

sage: x.is_singleton_or_pair()
True

sage: P(1).is_singleton_or_pair()
True

sage: (x*y).is_singleton_or_pair()
True

sage: (x + y).is_singleton_or_pair()
True

sage: (x + 1).is_singleton_or_pair()
True

sage: (x*y + 1).is_singleton_or_pair()
True

sage: (x + y + 1).is_singleton_or_pair()
False

sage: ((x + 1)*(y + 1)).is_singleton_or_pair()
False

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P(Integer(0)).is_singleton_or_pair()
True

>>> x.is_singleton_or_pair()
True

>>> P(Integer(1)).is_singleton_or_pair()
True

>>> (x*y).is_singleton_or_pair()
True

>>> (x + y).is_singleton_or_pair()
True

>>> (x + Integer(1)).is_singleton_or_pair()
True

>>> (x*y + Integer(1)).is_singleton_or_pair()
True

>>> (x + y + Integer(1)).is_singleton_or_pair()
False

>>> ((x + Integer(1))*(y + Integer(1))).is_singleton_or_pair()
False

is_unit()

Check if self is invertible in the parent ring.

Note that this condition is equivalent to being 1 for boolean polynomials.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P.one().is_unit()
True

sage: x.is_unit()
False

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P.one().is_unit()
True

>>> x.is_unit()
False

is_univariate()

Return True if self is a univariate polynomial.

This means that self contains at most one variable.

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing()
sage: f = x + 1
sage: f.is_univariate()
True
sage: f = y*x + 1
sage: f.is_univariate()
False
sage: f = P(0)
sage: f.is_univariate()
True

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> f = x + Integer(1)
>>> f.is_univariate()
True
>>> f = y*x + Integer(1)
>>> f.is_univariate()
False
>>> f = P(Integer(0))
>>> f.is_univariate()
True

is_zero()

Check if self is zero.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P(0).is_zero()
True

sage: x.is_zero()
False

sage: P(1).is_zero()
False

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P(Integer(0)).is_zero()
True

>>> x.is_zero()
False

>>> P(Integer(1)).is_zero()
False

lead()

Return the leading monomial of boolean polynomial, with respect to to the order of parent ring.

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lead()
x

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x+y+y*z).lead()
x

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lead()
y*z

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), order='deglex', names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x+y+y*z).lead()
y*z

Note

This function is part of the upstream PolyBoRi interface.

lead_deg()

Return the total degree of the leading monomial of self.

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: p = x + y*z
sage: p.lead_deg()
1

sage: P.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: p = x + y*z
sage: p.lead_deg()
2

sage: P(0).lead_deg()
0

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> p = x + y*z
>>> p.lead_deg()
1

>>> P = BooleanPolynomialRing(Integer(3),order='deglex', names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> p = x + y*z
>>> p.lead_deg()
2

>>> P(Integer(0)).lead_deg()
0

Note

This function is part of the upstream PolyBoRi interface.

lead_divisors()

Return a BooleSet of all divisors of the leading monomial.

EXAMPLES:

Sage

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*b + z + 1
sage: f.lead_divisors()
{{a,b}, {a}, {b}, {}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('a', 'b', 'z',)); (a, b, z,) = B._first_ngens(3)
>>> f = a*b + z + Integer(1)
>>> f.lead_divisors()
{{a,b}, {a}, {b}, {}}

Note

This function is part of the upstream PolyBoRi interface.

lex_lead()

Return the leading monomial of boolean polynomial, with respect to the lexicographical term ordering.

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lex_lead()
x

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lex_lead()
x

sage: P(0).lex_lead()
0

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x+y+y*z).lex_lead()
x

>>> P = BooleanPolynomialRing(Integer(3), order='deglex', names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x+y+y*z).lex_lead()
x

>>> P(Integer(0)).lex_lead()
0

Note

This function is part of the upstream PolyBoRi interface.

lex_lead_deg()

Return degree of leading monomial with respect to the lexicographical ordering.

EXAMPLES:

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3,order='lex')
sage: f = x + y*z
sage: f
x + y*z
sage: f.lex_lead_deg()
1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3),order='lex', names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> f = x + y*z
>>> f
x + y*z
>>> f.lex_lead_deg()
1

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: f = x + y*z
sage: f
y*z + x
sage: f.lex_lead_deg()
1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3),order='deglex', names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> f = x + y*z
>>> f
y*z + x
>>> f.lex_lead_deg()
1

Note

This function is part of the upstream PolyBoRi interface.

lm()

Return the leading monomial of this boolean polynomial, with respect to the order of parent ring.

EXAMPLES:

Sage

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

sage: P(0).lm()
0

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x+y+y*z).lm()
x

>>> P = BooleanPolynomialRing(Integer(3), order='deglex', names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x+y+y*z).lm()
y*z

>>> P(Integer(0)).lm()
0

lt()

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

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x+y+y*z).lt()
x

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x+y+y*z).lt()
x

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex')
sage: (x+y+y*z).lt()
y*z

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), order='deglex', names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x+y+y*z).lt()
y*z

map_every_x_to_x_plus_one()

Map every variable x_i in this polynomial to x_i + 1.

EXAMPLES:

Sage

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*b + z + 1; f
a*b + z + 1
sage: f.map_every_x_to_x_plus_one()
a*b + a + b + z + 1
sage: f(a+1,b+1,z+1)
a*b + a + b + z + 1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('a', 'b', 'z',)); (a, b, z,) = B._first_ngens(3)
>>> f = a*b + z + Integer(1); f
a*b + z + 1
>>> f.map_every_x_to_x_plus_one()
a*b + a + b + z + 1
>>> f(a+Integer(1),b+Integer(1),z+Integer(1))
a*b + a + b + z + 1

monomial_coefficient(mon)

Return the coefficient of the monomial mon in self, where mon must have the same parent as self.

INPUT:

• mon – a monomial

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> x.monomial_coefficient(x)
1
>>> x.monomial_coefficient(y)
0
>>> R = BooleanPolynomialRing(Integer(6), names=('x', 'y', 'z', 'a', 'b', 'c',)); (x, y, z, a, b, c,) = R._first_ngens(6)
>>> f=(Integer(1)-x)*(Integer(1)+y); f
x*y + x + y + 1

Sage

sage: f.monomial_coefficient(1)
1

Python

>>> from sage.all import *
>>> f.monomial_coefficient(Integer(1))
1

Sage

sage: f.monomial_coefficient(0)
0

Python

>>> from sage.all import *
>>> f.monomial_coefficient(Integer(0))
0

monomials()

Return a list of monomials appearing in self ordered largest to smallest.

EXAMPLES:

Sage

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='deglex')
sage: f = a + c*b
sage: f.monomials()
[b*c, a]
sage: P.zero().monomials()
[]

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3),order='lex', names=('a', 'b', 'c',)); (a, b, c,) = P._first_ngens(3)
>>> f = a + c*b
>>> f.monomials()
[a, b*c]

>>> P = BooleanPolynomialRing(Integer(3),order='deglex', names=('a', 'b', 'c',)); (a, b, c,) = P._first_ngens(3)
>>> f = a + c*b
>>> f.monomials()
[b*c, a]
>>> P.zero().monomials()
[]

n_nodes()

Return the number of nodes in the ZDD implementing this polynomial.

EXAMPLES:

Sage

sage: B = BooleanPolynomialRing(5,'x')
sage: x0,x1,x2,x3,x4 = B.gens()
sage: f = x1*x2 + x2*x3 + 1
sage: f.n_nodes()
4

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2 + x2*x3 + Integer(1)
>>> f.n_nodes()
4

Note

This function is part of the upstream PolyBoRi interface.

n_vars()

Return the number of variables used to form this boolean polynomial.

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + 1
sage: f.n_vars()
3

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> f = a*b*c + Integer(1)
>>> f.n_vars()
3

Note

This function is part of the upstream PolyBoRi interface.

navigation()

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.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori 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: nav = f.navigation()
sage: BooleSet(nav, B)
{{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

sage: nav.value()
1

sage: nav_else = nav.else_branch()

sage: BooleSet(nav_else, B)
{{x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

sage: nav_else.value()
2

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import BooleSet
>>> B = BooleanPolynomialRing(Integer(5),'x')
>>> x0,x1,x2,x3,x4 = B.gens()
>>> f = x1*x2+x2*x3*x4+x2*x4+x3+x4+Integer(1)

>>> nav = f.navigation()
>>> BooleSet(nav, B)
{{x1,x2}, {x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

>>> nav.value()
1

>>> nav_else = nav.else_branch()

>>> BooleSet(nav_else, B)
{{x2,x3,x4}, {x2,x4}, {x3}, {x4}, {}}

>>> nav_else.value()
2

Note

This function is part of the upstream PolyBoRi interface.

nvariables()

Return the number of variables used to form this boolean polynomial.

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b*c + 1
sage: f.nvariables()
3

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> f = a*b*c + Integer(1)
>>> f.nvariables()
3

reduce(I)

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:

• I – list/set of polynomials in self.parent(); if I is an ideal, the generators are used

EXAMPLES:

Sage

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
sage: p.reduce([])
x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x2

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('x0', 'x1', 'x2', 'x3',)); (x0, x1, x2, x3,) = B._first_ngens(4)
>>> 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 + Integer(1)))
>>> gb = I.groebner_basis()
>>> f,g,h,i = I.gens()
>>> f.reduce(gb)
0
>>> p = f*g + x0*h + x2*i
>>> p.reduce(gb)
0
>>> p.reduce(I)
x1*x2*x3 + x2
>>> p.reduce([])
x0*x1*x2 + x0*x1*x3 + x0*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.

reducible_by(rhs)

Return True if this boolean polynomial is reducible by the polynomial rhs.

INPUT:

• rhs – boolean polynomial

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4,order='deglex')
sage: f = (a*b + 1)*(c + 1)
sage: f.reducible_by(d)
False
sage: f.reducible_by(c)
True
sage: f.reducible_by(c + 1)
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4),order='deglex', names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> f = (a*b + Integer(1))*(c + Integer(1))
>>> f.reducible_by(d)
False
>>> f.reducible_by(c)
True
>>> f.reducible_by(c + Integer(1))
True

Note

This function is part of the upstream PolyBoRi interface.

ring()

Return the parent of this boolean polynomial.

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: a.ring() is B
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> a.ring() is B
True

set()

Return a BooleSet with all monomials appearing in this polynomial.

EXAMPLES:

Sage

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: (a*b+z+1).set()
{{a,b}, {z}, {}}

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('a', 'b', 'z',)); (a, b, z,) = B._first_ngens(3)
>>> (a*b+z+Integer(1)).set()
{{a,b}, {z}, {}}

spoly(rhs)

Return the S-Polynomial of this boolean polynomial and the other boolean polynomial rhs.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> f = a*b*c + c*d + a*b + Integer(1)
>>> g = c*d + b
>>> f.spoly(g)
a*b + a*c*d + c*d + 1

Note

This function is part of the upstream PolyBoRi interface.

stable_hash()

A hash value which is stable across processes.

EXAMPLES:

Sage

sage: B.<x,y> = BooleanPolynomialRing()
sage: x is B.gen(0)
False
sage: x.stable_hash() == B.gen(0).stable_hash()
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('x', 'y',)); (x, y,) = B._first_ngens(2)
>>> x is B.gen(Integer(0))
False
>>> x.stable_hash() == B.gen(Integer(0)).stable_hash()
True

Note

This function is part of the upstream PolyBoRi interface. In Sage all hashes are stable.

subs(in_dict=None, **kwds)

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:

• in_dict – (optional) dict with variable:value pairs

• **kwds – names parameters

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> f = x*y + z + y*z + Integer(1)
>>> f.subs(x=Integer(1))
y*z + y + z + 1
>>> f.subs(x=Integer(0))
y*z + z + 1

Sage

sage: f.subs(x=y)
y*z + y + z + 1

Python

>>> from sage.all import *
>>> f.subs(x=y)
y*z + y + z + 1

Sage

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

Python

>>> from sage.all import *
>>> f.subs({x:Integer(1)},y=Integer(1))
0
>>> f.subs(y=Integer(1))
x + 1
>>> f.subs(y=Integer(1),z=Integer(1))
x + 1
>>> f.subs(z=Integer(1))
x*y + y
>>> f.subs({'x':Integer(1)},y=Integer(1))
0

This method can work fully symbolic:

Sage

sage: f.subs(x=var('a'), y=var('b'), z=var('c'))                            # needs sage.symbolic
a*b + b*c + c + 1
sage: f.subs({'x': var('a'), 'y': var('b'), 'z': var('c')})                 # needs sage.symbolic
a*b + b*c + c + 1

Python

>>> from sage.all import *
>>> f.subs(x=var('a'), y=var('b'), z=var('c'))                            # needs sage.symbolic
a*b + b*c + c + 1
>>> f.subs({'x': var('a'), 'y': var('b'), 'z': var('c')})                 # needs sage.symbolic
a*b + b*c + c + 1

terms()

Return a list of monomials appearing in self ordered largest to smallest.

EXAMPLES:

Sage

sage: P.<a,b,c> = BooleanPolynomialRing(3,order='lex')
sage: f = a + c*b
sage: f.terms()
[a, b*c]

sage: P.<a,b,c> = BooleanPolynomialRing(3,order='deglex')
sage: f = a + c*b
sage: f.terms()
[b*c, a]

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3),order='lex', names=('a', 'b', 'c',)); (a, b, c,) = P._first_ngens(3)
>>> f = a + c*b
>>> f.terms()
[a, b*c]

>>> P = BooleanPolynomialRing(Integer(3),order='deglex', names=('a', 'b', 'c',)); (a, b, c,) = P._first_ngens(3)
>>> f = a + c*b
>>> f.terms()
[b*c, a]

total_degree()

Return the total degree of self.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: (x+y).total_degree()
1

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> (x+y).total_degree()
1

Sage

sage: P(1).total_degree()
0

Python

>>> from sage.all import *
>>> P(Integer(1)).total_degree()
0

Sage

sage: (x*y + x + y + 1).total_degree()
2

Python

>>> from sage.all import *
>>> (x*y + x + y + Integer(1)).total_degree()
2

univariate_polynomial(R=None)

Return a univariate polynomial associated to this multivariate polynomial.

If this polynomial is not in at most one variable, then a ValueError exception is raised. This is checked using the is_univariate() method. The new Polynomial is over GF(2) and in the variable x if no ring R is provided.

sage: R.<x, y> = BooleanPolynomialRing() sage: f = x - y + x*y + 1 sage: f.univariate_polynomial() Traceback (most recent call last): … ValueError: polynomial must involve at most one variable sage: g = f.subs({x:0}); g y + 1 sage: g.univariate_polynomial () y + 1 sage: g.univariate_polynomial(GF(2)[‘foo’]) foo + 1

Here’s an example with a constant multivariate polynomial:

Sage

sage: g = R(1)
sage: h = g.univariate_polynomial(); h
1
sage: h.parent()                                                            # needs sage.libs.ntl
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)

Python

>>> from sage.all import *
>>> g = R(Integer(1))
>>> h = g.univariate_polynomial(); h
1
>>> h.parent()                                                            # needs sage.libs.ntl
Univariate Polynomial Ring in x over Finite Field of size 2 (using GF2X)

variable(i=0)

Return the i-th variable occurring in self. The index i is the index in self.variables()

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = x*z + z + 1
sage: f.variables()
(x, z)
sage: f.variable(1)
z

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> f = x*z + z + Integer(1)
>>> f.variables()
(x, z)
>>> f.variable(Integer(1))
z

variables()

Return a tuple of all variables appearing in self.

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x + y).variables()
(x, y)

sage: (x*y + z).variables()
(x, y, z)

sage: P.zero().variables()
()

sage: P.one().variables()
()

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x + y).variables()
(x, y)

>>> (x*y + z).variables()
(x, y, z)

>>> P.zero().variables()
()

>>> P.one().variables()
()

vars_as_monomial()

Return a boolean monomial with all variables appearing in self.

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: (x + y).vars_as_monomial()
x*y

sage: (x*y + z).vars_as_monomial()
x*y*z

sage: P.zero().vars_as_monomial()
1

sage: P.one().vars_as_monomial()
1

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> (x + y).vars_as_monomial()
x*y

>>> (x*y + z).vars_as_monomial()
x*y*z

>>> P.zero().vars_as_monomial()
1

>>> P.one().vars_as_monomial()
1

Note

This function is part of the upstream PolyBoRi interface.

zeros_in(s)

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:

• s – candidate points for evaluation to zero

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b + c + d + 1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> f = a*b + c + d + Integer(1)

Now we create a set of points:

Sage

sage: s = a*b + a*b*c + c*d + 1
sage: s = s.set(); s
{{a,b,c}, {a,b}, {c,d}, {}}

Python

>>> from sage.all import *
>>> s = a*b + a*b*c + c*d + Integer(1)
>>> 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

sage: f.zeros_in(s)
{{a,b}}

Python

>>> from sage.all import *
>>> f.zeros_in(s)
{{a,b}}

Sage

sage: f.zeros_in([(1,1,1,0), (1,1,0,0), (0,0,1,1), (0,0,0,0)])
((1, 1, 0, 0),)

Python

>>> from sage.all import *
>>> f.zeros_in([(Integer(1),Integer(1),Integer(1),Integer(0)), (Integer(1),Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(1)), (Integer(0),Integer(0),Integer(0),Integer(0))])
((1, 1, 0, 0),)

class sage.rings.polynomial.pbori.pbori.BooleanPolynomialEntry

Bases: object

p

class sage.rings.polynomial.pbori.pbori.BooleanPolynomialIdeal(ring, gens=[], coerce=True)

Bases: MPolynomialIdeal

Construct an ideal in the boolean polynomial ring.

INPUT:

• ring – the ring this ideal is defined in

• gens – list of generators

• coerce – coerce all elements to the ring ring (default: True)

EXAMPLES:

Sage

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
sage: loads(dumps(I)) == I
True

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(4), names=('x0', 'x1', 'x2', 'x3',)); (x0, x1, x2, x3,) = P._first_ngens(4)
>>> I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0)
>>> I
Ideal (x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) of Boolean PolynomialRing in x0, x1, x2, x3
>>> loads(dumps(I)) == I
True

dimension()

Return the dimension of self, which is always zero.

groebner_basis(algorithm='polybori', **kwds)

Return a Groebner basis of this ideal.

INPUT:

• algorithm – either 'polybori' (built-in default) or 'magma' (requires Magma)

• red_tail – tail reductions in intermediate polynomials, 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)

• gauss_on_linear – perform Gaussian elimination on linear polynomials (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 should not 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

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]

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(4), names=('x0', 'x1', 'x2', 'x3',)); (x0, x1, x2, x3,) = P._first_ngens(4)
>>> I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0)
>>> I.groebner_basis()
[x0*x1 + x0*x2 + x0, x0*x2*x3 + x0*x3]

Another somewhat bigger example:

Sage

sage: sr = mq.SR(2,1,1,4,gf2=True, polybori=True)
sage: while True:  # workaround (see :issue:`31891`)
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass
sage: I = F.ideal()
sage: I.groebner_basis()  # not tested, known bug, unstable (see :issue:`32083`)
Polynomial Sequence with 36 Polynomials in 36 Variables

Python

>>> from sage.all import *
>>> sr = mq.SR(Integer(2),Integer(1),Integer(1),Integer(4),gf2=True, polybori=True)
>>> while True:  # workaround (see :issue:`31891`)
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass
>>> I = F.ideal()
>>> I.groebner_basis()  # not tested, known bug, unstable (see :issue:`32083`)
Polynomial Sequence with 36 Polynomials in 36 Variables

We compute the same example with Magma:

Sage

sage: sr = mq.SR(2,1,1,4,gf2=True, polybori=True)
sage: while True:  # workaround (see :issue:`31891`)
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass
sage: I = F.ideal()
sage: I.groebner_basis(algorithm='magma', prot='sage') # optional - magma
Leading term degree:  1. Critical pairs: 148.
Leading term degree:  2. Critical pairs: 144.
Leading term degree:  3. Critical pairs: 462.
Leading term degree:  1. Critical pairs: 167.
Leading term degree:  2. Critical pairs: 147.
Leading term degree:  3. Critical pairs: 101 (all pairs of current degree eliminated by criteria).

Highest degree reached during computation:  3.
Polynomial Sequence with 35 Polynomials in 36 Variables

Python

>>> from sage.all import *
>>> sr = mq.SR(Integer(2),Integer(1),Integer(1),Integer(4),gf2=True, polybori=True)
>>> while True:  # workaround (see :issue:`31891`)
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass
>>> I = F.ideal()
>>> I.groebner_basis(algorithm='magma', prot='sage') # optional - magma
Leading term degree:  1. Critical pairs: 148.
Leading term degree:  2. Critical pairs: 144.
Leading term degree:  3. Critical pairs: 462.
Leading term degree:  1. Critical pairs: 167.
Leading term degree:  2. Critical pairs: 147.
Leading term degree:  3. Critical pairs: 101 (all pairs of current degree eliminated by criteria).
<BLANKLINE>
Highest degree reached during computation:  3.
Polynomial Sequence with 35 Polynomials in 36 Variables

interreduced_basis()

If this ideal is spanned by (f_1, ..., f_n) this method returns (g_1, ..., g_s) such that:

• <f_1,...,f_n> = <g_1,...,g_s>

• LT(g_i) != LT(g_j) for all i != j

• LT(g_i) does not divide m for all monomials m of {g_1,...,g_{i-1},g_{i+1},...,g_s}

EXAMPLES:

Sage

sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True)
sage: while True:  # workaround (see :issue:`31891`)
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass
sage: I = F.ideal()
sage: g = I.interreduced_basis()
sage: len(g) == len(set(gi.lt() for gi in g))
True
sage: for i in range(len(g)):
....:     lt = g[i].lt()
....:     for j in range(len(g)):
....:         if i == j:
....:             continue
....:         for t in iter(g[j]):
....:             assert lt not in t.divisors()

Python

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), gf2=True, polybori=True)
>>> while True:  # workaround (see :issue:`31891`)
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass
>>> I = F.ideal()
>>> g = I.interreduced_basis()
>>> len(g) == len(set(gi.lt() for gi in g))
True
>>> for i in range(len(g)):
...     lt = g[i].lt()
...     for j in range(len(g)):
...         if i == j:
...             continue
...         for t in iter(g[j]):
...             assert lt not in t.divisors()

reduce(f)

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.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(2)),Integer(10), 'x')
>>> B = BooleanPolynomialRing(Integer(10),'x')
>>> I = sage.rings.ideal.Cyclic(P)
>>> I = B.ideal([B(f) for f in I.gens()])
>>> gb = I.groebner_basis()
>>> I.reduce(gb[Integer(0)])
0
>>> I.reduce(gb[Integer(0)] + Integer(1))
1
>>> I.reduce(gb[Integer(0)]*gb[Integer(1)])
0
>>> I.reduce(gb[Integer(0)]*B.gen(Integer(1)))
0

variety(**kwds)

Return the variety associated to this boolean ideal.

EXAMPLES:

A simple example:

Sage

sage: from sage.doctest.fixtures import reproducible_repr
sage: R.<x,y,z> = BooleanPolynomialRing()
sage: I = ideal( [ x*y*z + x*z + y + 1, x+y+z+1 ] )
sage: print(reproducible_repr(I.variety()))
[{x: 0, y: 1, z: 0}, {x: 1, y: 1, z: 1}]

Python

>>> from sage.all import *
>>> from sage.doctest.fixtures import reproducible_repr
>>> R = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> I = ideal( [ x*y*z + x*z + y + Integer(1), x+y+z+Integer(1) ] )
>>> print(reproducible_repr(I.variety()))
[{x: 0, y: 1, z: 0}, {x: 1, y: 1, z: 1}]

class sage.rings.polynomial.pbori.pbori.BooleanPolynomialIterator

Bases: object

Iterator over the monomials of a boolean polynomial.

class sage.rings.polynomial.pbori.pbori.BooleanPolynomialRing

Bases: BooleanPolynomialRing_base

Construct a boolean polynomial ring with the following parameters:

INPUT:

• n – integer > 1; number of variables

• names – names of ring variables; may be a string or list/tuple

• order – term order (default: lex)

EXAMPLES:

Sage

sage: R.<x, y, z> = BooleanPolynomialRing()
sage: R
Boolean PolynomialRing in x, y, z

Python

>>> from sage.all import *
>>> R = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> R
Boolean PolynomialRing in x, y, z

Sage

sage: p = x*y + x*z + y*z
sage: x*p
x*y*z + x*y + x*z

Python

>>> from sage.all import *
>>> p = x*y + x*z + y*z
>>> x*p
x*y*z + x*y + x*z

Sage

sage: R.term_order()
Lexicographic term order

Python

>>> from sage.all import *
>>> R.term_order()
Lexicographic term order

Sage

sage: R = BooleanPolynomialRing(5,'x',order='deglex(3),deglex(2)')
sage: R.term_order()
Block term order with blocks:
(Degree lexicographic term order of length 3,
 Degree lexicographic term order of length 2)

Python

>>> from sage.all import *
>>> R = BooleanPolynomialRing(Integer(5),'x',order='deglex(3),deglex(2)')
>>> R.term_order()
Block term order with blocks:
(Degree lexicographic term order of length 3,
 Degree lexicographic term order of length 2)

Sage

sage: R = BooleanPolynomialRing(3,'x',order='deglex')
sage: R.term_order()
Degree lexicographic term order

Python

>>> from sage.all import *
>>> R = BooleanPolynomialRing(Integer(3),'x',order='deglex')
>>> R.term_order()
Degree lexicographic term order

change_ring(base_ring=None, names=None, order=None)

Return a new multivariate polynomial ring with base ring base_ring, variable names set to names, and term ordering given by order.

When base_ring is not specified, this function returns a BooleanPolynomialRing isomorphic to self. Otherwise, this returns a MPolynomialRing. Each argument above is optional.

INPUT:

• base_ring – a base ring

• names – variable names

• order – a term order

EXAMPLES:

Sage

sage: P.<x, y, z> = BooleanPolynomialRing()
sage: P.term_order()
Lexicographic term order
sage: R = P.change_ring(names=('a', 'b', 'c'), order='deglex')
sage: R
Boolean PolynomialRing in a, b, c
sage: R.term_order()
Degree lexicographic term order
sage: T = P.change_ring(base_ring=GF(3))
sage: T
Multivariate Polynomial Ring in x, y, z over Finite Field of size 3
sage: T.term_order()
Lexicographic term order

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> P.term_order()
Lexicographic term order
>>> R = P.change_ring(names=('a', 'b', 'c'), order='deglex')
>>> R
Boolean PolynomialRing in a, b, c
>>> R.term_order()
Degree lexicographic term order
>>> T = P.change_ring(base_ring=GF(Integer(3)))
>>> T
Multivariate Polynomial Ring in x, y, z over Finite Field of size 3
>>> T.term_order()
Lexicographic term order

clone(ordering=None, names=[], blocks=[])

Shallow copy this boolean polynomial ring, but with different ordering, names or blocks if given.

ring.clone(ordering=…, names=…, block=…) generates a shallow copy of ring, but with different ordering, names or blocks if given.

EXAMPLES:

Sage

sage: B.<a,b,c> = BooleanPolynomialRing()
sage: B.clone()
Boolean PolynomialRing in a, b, c

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c',)); (a, b, c,) = B._first_ngens(3)
>>> B.clone()
Boolean PolynomialRing in a, b, c

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex')
sage: y*z > x
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3),order='deglex', names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> y*z > x
True

Now we call the clone method and generate a compatible, but ‘lex’ ordered, ring:

Sage

sage: C = B.clone(ordering=0)
sage: C(y*z) > C(x)
False

Python

>>> from sage.all import *
>>> C = B.clone(ordering=Integer(0))
>>> C(y*z) > C(x)
False

Now we change variable names:

Sage

sage: P.<x0,x1> = BooleanPolynomialRing(2)
sage: P
Boolean PolynomialRing in x0, x1

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x0', 'x1',)); (x0, x1,) = P._first_ngens(2)
>>> P
Boolean PolynomialRing in x0, x1

Sage

sage: Q = P.clone(names=['t'])
sage: Q
Boolean PolynomialRing in t, x1

Python

>>> from sage.all import *
>>> Q = P.clone(names=['t'])
>>> Q
Boolean PolynomialRing in t, x1

We can also append blocks to block orderings this way:

Sage

sage: R.<x1,x2,x3,x4> = BooleanPolynomialRing(order='deglex(1),deglex(3)')
sage: x2 > x3*x4
False

Python

>>> from sage.all import *
>>> R = BooleanPolynomialRing(order='deglex(1),deglex(3)', names=('x1', 'x2', 'x3', 'x4',)); (x1, x2, x3, x4,) = R._first_ngens(4)
>>> x2 > x3*x4
False

Now we call the internal method and change the blocks:

Sage

sage: S = R.clone(blocks=[3])
sage: S(x2) > S(x3*x4)
True

Python

>>> from sage.all import *
>>> S = R.clone(blocks=[Integer(3)])
>>> S(x2) > S(x3*x4)
True

Note

This is part of PolyBoRi’s native interface.

construction()

A boolean polynomial ring is the quotient of a polynomial ring, in a special implementation.

Before Issue #15223, the boolean polynomial rings returned the construction of a polynomial ring, which was of course wrong.

Now, a QuotientFunctor is returned that knows about the \("pbori"\) implementation.

EXAMPLES:

Sage

sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4,order='degneglex(2),degneglex(2)')
sage: F,O = P.construction()
sage: O
Multivariate Polynomial Ring in x0, x1, x2, x3 over Finite Field of size 2
sage: F
QuotientFunctor
sage: F(O) is P
True

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(4),order='degneglex(2),degneglex(2)', names=('x0', 'x1', 'x2', 'x3',)); (x0, x1, x2, x3,) = P._first_ngens(4)
>>> F,O = P.construction()
>>> O
Multivariate Polynomial Ring in x0, x1, x2, x3 over Finite Field of size 2
>>> F
QuotientFunctor
>>> F(O) is P
True

cover_ring()

Return \(R = \GF{2}[x_1,x_2,...,x_n]\) if x_1,x_2,...,x_n is the ordered list of variable names of this ring. R also has the same term ordering as this ring.

EXAMPLES:

Sage

sage: B.<x,y> = BooleanPolynomialRing(2)
sage: R = B.cover_ring(); R
Multivariate Polynomial Ring in x, y over Finite Field of size 2

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = B._first_ngens(2)
>>> R = B.cover_ring(); R
Multivariate Polynomial Ring in x, y over Finite Field of size 2

Sage

sage: B.term_order() == R.term_order()
True

Python

>>> from sage.all import *
>>> B.term_order() == R.term_order()
True

The cover ring is cached:

Sage

sage: B.cover_ring() is B.cover_ring()
True

Python

>>> from sage.all import *
>>> B.cover_ring() is B.cover_ring()
True

defining_ideal()

Return \(I = <x_i^2 + x_i> \subset R\) where R = self.cover_ring(), and \(x_i\) any element in the set of variables of this ring.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = B._first_ngens(2)
>>> 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

gen(i=0)

Return the \(i\)-th generator of this boolean polynomial ring.

INPUT:

• i – integer or a boolean monomial in one variable

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> P.gen()
x
>>> P.gen(Integer(2))
z
>>> m = x.monomials()[Integer(0)]
>>> P.gen(m)
x

gens()

Return the tuple of variables in this ring.

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.gens()
(x, y, z)

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> P.gens()
(x, y, z)

Sage

sage: P = BooleanPolynomialRing(10,'x')
sage: P.gens()
(x0, x1, x2, x3, x4, x5, x6, x7, x8, x9)

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(10),'x')
>>> P.gens()
(x0, x1, x2, x3, x4, x5, x6, x7, x8, x9)

get_base_order_code()

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: B.get_base_order_code()
0

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing(order='deglex')
sage: B.get_base_order_code()
1
sage: T = TermOrder('deglex',2) + TermOrder('deglex',2)
sage: B.<a,b,c,d> = BooleanPolynomialRing(4, order=T)
sage: B.get_base_order_code()
1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> B.get_base_order_code()
0

>>> B = BooleanPolynomialRing(order='deglex', names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> B.get_base_order_code()
1
>>> T = TermOrder('deglex',Integer(2)) + TermOrder('deglex',Integer(2))
>>> B = BooleanPolynomialRing(Integer(4), order=T, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> B.get_base_order_code()
1

Note

This function which is part of the PolyBoRi upstream API works with a current global ring. This notion is avoided in Sage.

get_order_code()

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: B.get_order_code()
0

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing(order='deglex')
sage: B.get_order_code()
1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> B.get_order_code()
0

>>> B = BooleanPolynomialRing(order='deglex', names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> B.get_order_code()
1

Note

This function which is part of the PolyBoRi upstream API works with a current global ring. This notion is avoided in Sage.

has_degree_order()

Return checks whether the order code corresponds to a degree ordering.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P.has_degree_order()
False

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P.has_degree_order()
False

id()

Return a unique identifier for this boolean polynomial ring.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: print("id: {}".format(P.id()))
id: ...

sage: P = BooleanPolynomialRing(10, 'x')
sage: Q = BooleanPolynomialRing(20, 'x')

sage: P.id() != Q.id()
True

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> print("id: {}".format(P.id()))
id: ...

>>> P = BooleanPolynomialRing(Integer(10), 'x')
>>> Q = BooleanPolynomialRing(Integer(20), 'x')

>>> P.id() != Q.id()
True

ideal(*gens, **kwds)

Create an ideal in this ring.

INPUT:

• gens – list or tuple of generators

• coerce – boolean (default: True); automatically coerce the given polynomials to this ring to form the ideal

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.ideal(x+y)
Ideal (x + y) of Boolean PolynomialRing in x, y, z

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> P.ideal(x+y)
Ideal (x + y) of Boolean PolynomialRing in x, y, z

Sage

sage: P.ideal(x*y, y*z)
Ideal (x*y, y*z) of Boolean PolynomialRing in x, y, z

Python

>>> from sage.all import *
>>> P.ideal(x*y, y*z)
Ideal (x*y, y*z) of Boolean PolynomialRing in x, y, z

Sage

sage: P.ideal([x+y, z])
Ideal (x + y, z) of Boolean PolynomialRing in x, y, z

Python

>>> from sage.all import *
>>> P.ideal([x+y, z])
Ideal (x + y, z) of Boolean PolynomialRing in x, y, z

interpolation_polynomial(zeros, ones)

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:

• zeros – the set of interpolation points mapped to zero

• ones – the set of interpolation points mapped to one

EXAMPLES:

First we create a random-ish boolean polynomial.

Sage

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

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(6), names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> f = a*b*c*e + a*d*e + a*f + b + c + e + f + Integer(1)

Now we find interpolation points mapping to zero and to one.

Sage

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]

Python

>>> from sage.all import *
>>> zeros = set([(Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0)), (Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)),
...              (Integer(0), Integer(0), Integer(1), Integer(1), Integer(1), Integer(1)), (Integer(1), Integer(0), Integer(1), Integer(1), Integer(1), Integer(1)),
...              (Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)), (Integer(0), Integer(1), Integer(1), Integer(1), Integer(1), Integer(0)),
...              (Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(1)), (Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(1))])
>>> ones = set([(Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0)), (Integer(1), Integer(0), Integer(1), Integer(0), Integer(1), Integer(0)),
...             (Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(1)), (Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1)),
...             (Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1)), (Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(1)),
...             (Integer(0), Integer(1), Integer(1), Integer(1), Integer(1), Integer(1)), (Integer(1), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0))])
>>> [f(*p) for p in zeros]
[0, 0, 0, 0, 0, 0, 0, 0]
>>> [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

sage: g = B.interpolation_polynomial(zeros, ones); g
b*f + c + d*f + d + e*f + e + 1

Python

>>> from sage.all import *
>>> g = B.interpolation_polynomial(zeros, ones); g
b*f + c + d*f + d + e*f + e + 1

Sage

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]

Python

>>> from sage.all import *
>>> [g(*p) for p in zeros]
[0, 0, 0, 0, 0, 0, 0, 0]
>>> [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

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.zeros_in(V); z
{{x1}, {x2}}
sage: o = V.diff(z); o
{{x0}, {x3}, {}}
sage: B.interpolation_polynomial(z,o)
x1 + x2 + 1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4),"x0,x1,x2,x3")
>>> x = B.gen
>>> V=(x(Integer(0))+x(Integer(1))+x(Integer(2))+x(Integer(3))+Integer(1)).set(); V
{{x0}, {x1}, {x2}, {x3}, {}}
>>> f=x(Integer(0))*x(Integer(1))+x(Integer(1))+x(Integer(2))+Integer(1)
>>> z = f.zeros_in(V); z
{{x1}, {x2}}
>>> o = V.diff(z); o
{{x0}, {x3}, {}}
>>> B.interpolation_polynomial(z,o)
x1 + x2 + 1

ALGORITHM: Calls interpolate_smallest_lex as described in the PolyBoRi tutorial.

n_variables()

Return the number of variables in this boolean polynomial ring.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P.n_variables()
2

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P.n_variables()
2

Sage

sage: P = BooleanPolynomialRing(1000, 'x')
sage: P.n_variables()
1000

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(1000), 'x')
>>> P.n_variables()
1000

Note

This is part of PolyBoRi’s native interface.

ngens()

Return the number of variables in this boolean polynomial ring.

EXAMPLES:

Sage

sage: P.<x,y> = BooleanPolynomialRing(2)
sage: P.ngens()
2

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x', 'y',)); (x, y,) = P._first_ngens(2)
>>> P.ngens()
2

Sage

sage: P = BooleanPolynomialRing(1000, 'x')
sage: P.ngens()
1000

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(1000), 'x')
>>> P.ngens()
1000

one()

EXAMPLES:

Sage

sage: P.<x0,x1> = BooleanPolynomialRing(2)
sage: P.one()
1

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x0', 'x1',)); (x0, x1,) = P._first_ngens(2)
>>> P.one()
1

random_element(degree=None, terms=None, choose_degree=False, vars_set=None)

Return a random boolean polynomial. Generated polynomial has the given number of terms, and at most given degree.

INPUT:

• degree – maximum degree (default: 2 for len(var_set) > 1, 1 otherwise)

• terms – number of terms requested (default: 5). If more terms are requested than exist, then this parameter is silently reduced to the maximum number of available terms.

• choose_degree – choose degree of monomials randomly first, rather than monomials uniformly random

• vars_set – list of integer indices of generators of self to use in the generated polynomial

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: f = P.random_element(degree=3, terms=4)
sage: f.degree() <= 3
True
sage: len(f.terms())
4

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> f = P.random_element(degree=Integer(3), terms=Integer(4))
>>> f.degree() <= Integer(3)
True
>>> len(f.terms())
4

Sage

sage: f = P.random_element(degree=1, terms=2)
sage: f.degree() <= 1
True
sage: len(f.terms())
2

Python

>>> from sage.all import *
>>> f = P.random_element(degree=Integer(1), terms=Integer(2))
>>> f.degree() <= Integer(1)
True
>>> len(f.terms())
2

In corner cases this function will return fewer terms by default:

Sage

sage: P = BooleanPolynomialRing(2,'y')
sage: f = P.random_element()
sage: len(f.terms())
2

sage: P = BooleanPolynomialRing(1,'y')
sage: f = P.random_element()
sage: len(f.terms())
1

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2),'y')
>>> f = P.random_element()
>>> len(f.terms())
2

>>> P = BooleanPolynomialRing(Integer(1),'y')
>>> f = P.random_element()
>>> len(f.terms())
1

We return uniformly random polynomials up to degree 2:

Sage

sage: from collections import defaultdict
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: counter = 0.0
sage: dic = defaultdict(Integer)
sage: def more_terms():
....:     global counter, dic
....:     for t in B.random_element(terms=Infinity).terms():
....:         counter += 1.0
....:         dic[t] += 1

sage: more_terms()
sage: while any(abs(dic[t]/counter - 1.0/11) > 0.01 for t in dic):
....:     more_terms()

Python

>>> from sage.all import *
>>> from collections import defaultdict
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> counter = RealNumber('0.0')
>>> dic = defaultdict(Integer)
>>> def more_terms():
...     global counter, dic
...     for t in B.random_element(terms=Infinity).terms():
...         counter += RealNumber('1.0')
...         dic[t] += Integer(1)

>>> more_terms()
>>> while any(abs(dic[t]/counter - RealNumber('1.0')/Integer(11)) > RealNumber('0.01') for t in dic):
...     more_terms()

remove_var(order=None, *var)

Remove a variable or sequence of variables from this ring.

If order is not specified, then the subring inherits the term order of the original ring, if possible.

EXAMPLES:

Sage

sage: R.<x,y,z,w> = BooleanPolynomialRing()
sage: R.remove_var(z)
Boolean PolynomialRing in x, y, w
sage: R.remove_var(z,x)
Boolean PolynomialRing in y, w
sage: R.remove_var(y,z,x)
Boolean PolynomialRing in w

Python

>>> from sage.all import *
>>> R = BooleanPolynomialRing(names=('x', 'y', 'z', 'w',)); (x, y, z, w,) = R._first_ngens(4)
>>> R.remove_var(z)
Boolean PolynomialRing in x, y, w
>>> R.remove_var(z,x)
Boolean PolynomialRing in y, w
>>> R.remove_var(y,z,x)
Boolean PolynomialRing in w

Removing all variables results in the base ring:

Sage

sage: R.remove_var(y,z,x,w)
Finite Field of size 2

Python

>>> from sage.all import *
>>> R.remove_var(y,z,x,w)
Finite Field of size 2

If possible, the term order is kept:

sage: R.<x,y,z,w> = BooleanPolynomialRing(order=’deglex’) sage: R.remove_var(y).term_order() Degree lexicographic term order

sage: R.<x,y,z,w> = BooleanPolynomialRing(order=’lex’) sage: R.remove_var(y).term_order() Lexicographic term order

Be careful with block orders when removing variables:

Sage

sage: R.<x,y,z,u,v> = BooleanPolynomialRing(order='deglex(2),deglex(3)')
sage: R.remove_var(x,y,z)
Traceback (most recent call last):
...
ValueError: impossible to use the original term order (most likely because it was a block order); please specify the term order for the subring
sage: R.remove_var(x,y,z, order='deglex')
Boolean PolynomialRing in u, v

Python

>>> from sage.all import *
>>> R = BooleanPolynomialRing(order='deglex(2),deglex(3)', names=('x', 'y', 'z', 'u', 'v',)); (x, y, z, u, v,) = R._first_ngens(5)
>>> R.remove_var(x,y,z)
Traceback (most recent call last):
...
ValueError: impossible to use the original term order (most likely because it was a block order); please specify the term order for the subring
>>> R.remove_var(x,y,z, order='deglex')
Boolean PolynomialRing in u, v

variable(i=0)

Return the \(i\)-th generator of this boolean polynomial ring.

INPUT:

• i – integer or a boolean monomial in one variable

EXAMPLES:

Sage

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: P.variable()
x
sage: P.variable(2)
z
sage: m = x.monomials()[0]
sage: P.variable(m)
x

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> P.variable()
x
>>> P.variable(Integer(2))
z
>>> m = x.monomials()[Integer(0)]
>>> P.variable(m)
x

zero()

EXAMPLES:

Sage

sage: P.<x0,x1> = BooleanPolynomialRing(2)
sage: P.zero()
0

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(2), names=('x0', 'x1',)); (x0, x1,) = P._first_ngens(2)
>>> P.zero()
0

class sage.rings.polynomial.pbori.pbori.BooleanPolynomialVector

Bases: object

A vector of boolean polynomials.

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: from sage.rings.polynomial.pbori.pbori import BooleanPolynomialVector
sage: l = [B.random_element() for _ in range(3)]
sage: v = BooleanPolynomialVector(l)
sage: len(v)
3
sage: all(vi.parent() is B for vi in v)
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> from sage.rings.polynomial.pbori.pbori import BooleanPolynomialVector
>>> l = [B.random_element() for _ in range(Integer(3))]
>>> v = BooleanPolynomialVector(l)
>>> len(v)
3
>>> all(vi.parent() is B for vi in v)
True

append(el)

Append the element el to this vector.

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: from sage.rings.polynomial.pbori.pbori import BooleanPolynomialVector
sage: v = BooleanPolynomialVector()
sage: entries = []
sage: for i in range(5):
....:   entries.append(B.random_element())
....:   v.append(entries[-1])

sage: list(v) == entries
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> from sage.rings.polynomial.pbori.pbori import BooleanPolynomialVector
>>> v = BooleanPolynomialVector()
>>> entries = []
>>> for i in range(Integer(5)):
...   entries.append(B.random_element())
...   v.append(entries[-Integer(1)])

>>> list(v) == entries
True

class sage.rings.polynomial.pbori.pbori.BooleanPolynomialVectorIterator

Bases: object

class sage.rings.polynomial.pbori.pbori.CCuddNavigator

Bases: object

constant()

else_branch()

terminal_one()

then_branch()

value()

class sage.rings.polynomial.pbori.pbori.FGLMStrategy

Bases: object

Strategy object for the FGLM algorithm to translate from one Groebner basis with respect to a term ordering A to another Groebner basis with respect to a term ordering B.

main()

Execute the FGLM algorithm.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<x,y,z> = BooleanPolynomialRing()
sage: ideal = BooleanPolynomialVector([x+z, y+z])
sage: list(ideal)
[x + z, y + z]
sage: old_ring = B
sage: new_ring = B.clone(ordering=dp_asc)
sage: list(FGLMStrategy(old_ring, new_ring, ideal).main())
[y + x, z + x]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> ideal = BooleanPolynomialVector([x+z, y+z])
>>> list(ideal)
[x + z, y + z]
>>> old_ring = B
>>> new_ring = B.clone(ordering=dp_asc)
>>> list(FGLMStrategy(old_ring, new_ring, ideal).main())
[y + x, z + x]

class sage.rings.polynomial.pbori.pbori.GroebnerStrategy

Bases: object

A Groebner strategy is the main object to control the strategy for computing Groebner bases.

Note

This class is mainly used internally.

add_as_you_wish(p)

Add a new generator but let the strategy object decide whether to perform immediate interreduction.

INPUT:

• p – a polynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: gbs = GroebnerStrategy(B)
sage: gbs.add_as_you_wish(a + b)
sage: list(gbs)
[a + b]
sage: gbs.add_as_you_wish(a + c)

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> gbs = GroebnerStrategy(B)
>>> gbs.add_as_you_wish(a + b)
>>> list(gbs)
[a + b]
>>> gbs.add_as_you_wish(a + c)

Note that nothing happened immediately but that the generator was indeed added:

Sage

sage: list(gbs)
[a + b]

sage: gbs.symmGB_F2()
sage: list(gbs)
[a + c, b + c]

Python

>>> from sage.all import *
>>> list(gbs)
[a + b]

>>> gbs.symmGB_F2()
>>> list(gbs)
[a + c, b + c]

add_generator(p)

Add a new generator.

INPUT:

• p – a polynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: gbs = GroebnerStrategy(B)
sage: gbs.add_generator(a + b)
sage: list(gbs)
[a + b]
sage: gbs.add_generator(a + c)
Traceback (most recent call last):
...
ValueError: strategy already contains a polynomial with same lead

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> gbs = GroebnerStrategy(B)
>>> gbs.add_generator(a + b)
>>> list(gbs)
[a + b]
>>> gbs.add_generator(a + c)
Traceback (most recent call last):
...
ValueError: strategy already contains a polynomial with same lead

add_generator_delayed(p)

Add a new generator but do not perform interreduction immediately.

INPUT:

• p – a polynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: gbs = GroebnerStrategy(B)
sage: gbs.add_generator(a + b)
sage: list(gbs)
[a + b]
sage: gbs.add_generator_delayed(a + c)
sage: list(gbs)
[a + b]

sage: list(gbs.all_generators())
[a + b, a + c]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> gbs = GroebnerStrategy(B)
>>> gbs.add_generator(a + b)
>>> list(gbs)
[a + b]
>>> gbs.add_generator_delayed(a + c)
>>> list(gbs)
[a + b]

>>> list(gbs.all_generators())
[a + b, a + c]

all_generators()

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: gbs = GroebnerStrategy(B)
sage: gbs.add_as_you_wish(a + b)
sage: list(gbs)
[a + b]
sage: gbs.add_as_you_wish(a + c)

sage: list(gbs)
[a + b]

sage: list(gbs.all_generators())
[a + b, a + c]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> gbs = GroebnerStrategy(B)
>>> gbs.add_as_you_wish(a + b)
>>> list(gbs)
[a + b]
>>> gbs.add_as_you_wish(a + c)

>>> list(gbs)
[a + b]

>>> list(gbs.all_generators())
[a + b, a + c]

all_spolys_in_next_degree()

clean_top_by_chain_criterion()

contains_one()

Return True if 1 is in the generating system.

EXAMPLES:

We construct an example which contains 1 in the ideal spanned by the generators but not in the set of generators:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: from sage.rings.polynomial.pbori.pbori import GroebnerStrategy
sage: gb = GroebnerStrategy(B)
sage: gb.add_generator(a*c + a*f + d*f + d + f)
sage: gb.add_generator(b*c + b*e + c + d + 1)
sage: gb.add_generator(a*f + a + c + d + 1)
sage: gb.add_generator(a*d + a*e + b*e + c + f)
sage: gb.add_generator(b*d + c + d*f + e + f)
sage: gb.add_generator(a*b + b + c*e + e + 1)
sage: gb.add_generator(a + b + c*d + c*e + 1)
sage: gb.contains_one()
False

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> from sage.rings.polynomial.pbori.pbori import GroebnerStrategy
>>> gb = GroebnerStrategy(B)
>>> gb.add_generator(a*c + a*f + d*f + d + f)
>>> gb.add_generator(b*c + b*e + c + d + Integer(1))
>>> gb.add_generator(a*f + a + c + d + Integer(1))
>>> gb.add_generator(a*d + a*e + b*e + c + f)
>>> gb.add_generator(b*d + c + d*f + e + f)
>>> gb.add_generator(a*b + b + c*e + e + Integer(1))
>>> gb.add_generator(a + b + c*d + c*e + Integer(1))
>>> gb.contains_one()
False

Still, we have that:

Sage

sage: from sage.rings.polynomial.pbori import groebner_basis
sage: groebner_basis(gb)
[1]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori import groebner_basis
>>> groebner_basis(gb)
[1]

faugere_step_dense(v)

Reduces a vector of polynomials using linear algebra.

INPUT:

• v – boolean polynomial vector

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: from sage.rings.polynomial.pbori.pbori import GroebnerStrategy
sage: gb = GroebnerStrategy(B)
sage: gb.add_generator(a*c + a*f + d*f + d + f)
sage: gb.add_generator(b*c + b*e + c + d + 1)
sage: gb.add_generator(a*f + a + c + d + 1)
sage: gb.add_generator(a*d + a*e + b*e + c + f)
sage: gb.add_generator(b*d + c + d*f + e + f)
sage: gb.add_generator(a*b + b + c*e + e + 1)
sage: gb.add_generator(a + b + c*d + c*e + 1)

sage: from sage.rings.polynomial.pbori.pbori import BooleanPolynomialVector
sage: V= BooleanPolynomialVector([b*d, a*b])
sage: list(gb.faugere_step_dense(V))
[b + c*e + e + 1, c + d*f + e + f]

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> from sage.rings.polynomial.pbori.pbori import GroebnerStrategy
>>> gb = GroebnerStrategy(B)
>>> gb.add_generator(a*c + a*f + d*f + d + f)
>>> gb.add_generator(b*c + b*e + c + d + Integer(1))
>>> gb.add_generator(a*f + a + c + d + Integer(1))
>>> gb.add_generator(a*d + a*e + b*e + c + f)
>>> gb.add_generator(b*d + c + d*f + e + f)
>>> gb.add_generator(a*b + b + c*e + e + Integer(1))
>>> gb.add_generator(a + b + c*d + c*e + Integer(1))

>>> from sage.rings.polynomial.pbori.pbori import BooleanPolynomialVector
>>> V= BooleanPolynomialVector([b*d, a*b])
>>> list(gb.faugere_step_dense(V))
[b + c*e + e + 1, c + d*f + e + f]

implications(i)

Compute “useful” implied polynomials of i-th generator, and add them to the strategy, if it finds any.

INPUT:

• i – an index

ll_reduce_all()

Use the built-in ll-encoded BooleSet of polynomials with linear lexicographical leading term, which coincides with leading term in current ordering, to reduce the tails of all polynomials in the strategy.

minimalize()

Return a vector of all polynomials with minimal leading terms.

Note

Use this function if strat contains a GB.

minimalize_and_tail_reduce()

Return a vector of all polynomials with minimal leading terms and do tail reductions.

Note

Use that if strat contains a GB and you want a reduced GB.

next_spoly()

nf(p)

Compute the normal form of p with respect to the generating set.

INPUT:

• p – boolean polynomial

EXAMPLES:

Sage

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: from sage.rings.polynomial.pbori.pbori import GroebnerStrategy

sage: G = GroebnerStrategy(B)
sage: _ = [G.add_generator(f) for f in gb]
sage: G.nf(gb[0])
0
sage: G.nf(gb[0] + 1)
1
sage: G.nf(gb[0]*gb[1])
0
sage: G.nf(gb[0]*B.gen(1))
0

Python

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(2)),Integer(10), 'x')
>>> B = BooleanPolynomialRing(Integer(10),'x')
>>> I = sage.rings.ideal.Cyclic(P)
>>> I = B.ideal([B(f) for f in I.gens()])
>>> gb = I.groebner_basis()

>>> from sage.rings.polynomial.pbori.pbori import GroebnerStrategy

>>> G = GroebnerStrategy(B)
>>> _ = [G.add_generator(f) for f in gb]
>>> G.nf(gb[Integer(0)])
0
>>> G.nf(gb[Integer(0)] + Integer(1))
1
>>> G.nf(gb[Integer(0)]*gb[Integer(1)])
0
>>> G.nf(gb[Integer(0)]*B.gen(Integer(1)))
0

Note

The result is only canonical if the generating set is a Groebner basis.

npairs()

reduction_strategy

select(m)

Return the index of the generator which can reduce the monomial m.

INPUT:

• m – a BooleanMonomial

EXAMPLES:

Sage

sage: B.<a,b,c,d,e> = BooleanPolynomialRing()
sage: f = B.random_element()
sage: g = B.random_element()
sage: while g.lt() == f.lt():
....:     g = B.random_element()
sage: from sage.rings.polynomial.pbori.pbori import GroebnerStrategy
sage: strat = GroebnerStrategy(B)
sage: strat.add_generator(f)
sage: strat.add_generator(g)
sage: strat.select(f.lm())
0
sage: strat.select(g.lm())
1
sage: strat.select(e.lm())
-1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e',)); (a, b, c, d, e,) = B._first_ngens(5)
>>> f = B.random_element()
>>> g = B.random_element()
>>> while g.lt() == f.lt():
...     g = B.random_element()
>>> from sage.rings.polynomial.pbori.pbori import GroebnerStrategy
>>> strat = GroebnerStrategy(B)
>>> strat.add_generator(f)
>>> strat.add_generator(g)
>>> strat.select(f.lm())
0
>>> strat.select(g.lm())
1
>>> strat.select(e.lm())
-1

small_spolys_in_next_degree(f, n)

some_spolys_in_next_degree(n)

suggest_plugin_variable()

symmGB_F2()

Compute a Groebner basis for the generating system.

Note

This implementation is out of date, but it will revived at some point in time. Use the groebner_basis() function instead.

top_sugar()

variable_has_value(v)

Compute whether there exists some polynomial of the form \(v+c\) in the Strategy – where c is a constant – in the list of generators.

INPUT:

• v – the index of a variable

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: from sage.rings.polynomial.pbori.pbori import GroebnerStrategy
sage: gb = GroebnerStrategy(B)
sage: gb.add_generator(a*c + a*f + d*f + d + f)
sage: gb.add_generator(b*c + b*e + c + d + 1)
sage: gb.add_generator(a*f + a + c + d + 1)
sage: gb.add_generator(a*d + a*e + b*e + c + f)
sage: gb.add_generator(b*d + c + d*f + e + f)
sage: gb.add_generator(a*b + b + c*e + e + 1)
sage: gb.variable_has_value(0)
False

sage: from sage.rings.polynomial.pbori import groebner_basis
sage: g = groebner_basis(gb)
sage: list(g)
[a, b + 1, c + 1, d, e + 1, f]

sage: gb = GroebnerStrategy(B)
sage: _ = [gb.add_generator(f) for f in g]
sage: gb.variable_has_value(0)
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> from sage.rings.polynomial.pbori.pbori import GroebnerStrategy
>>> gb = GroebnerStrategy(B)
>>> gb.add_generator(a*c + a*f + d*f + d + f)
>>> gb.add_generator(b*c + b*e + c + d + Integer(1))
>>> gb.add_generator(a*f + a + c + d + Integer(1))
>>> gb.add_generator(a*d + a*e + b*e + c + f)
>>> gb.add_generator(b*d + c + d*f + e + f)
>>> gb.add_generator(a*b + b + c*e + e + Integer(1))
>>> gb.variable_has_value(Integer(0))
False

>>> from sage.rings.polynomial.pbori import groebner_basis
>>> g = groebner_basis(gb)
>>> list(g)
[a, b + 1, c + 1, d, e + 1, f]

>>> gb = GroebnerStrategy(B)
>>> _ = [gb.add_generator(f) for f in g]
>>> gb.variable_has_value(Integer(0))
True

class sage.rings.polynomial.pbori.pbori.MonomialConstruct

Bases: object

Implement PolyBoRi’s Monomial() constructor.

class sage.rings.polynomial.pbori.pbori.MonomialFactory

Bases: object

Implement PolyBoRi’s Monomial() constructor. If a ring is given is can be used as a Monomial factory for the given ring.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c> = BooleanPolynomialRing()
sage: fac = MonomialFactory()
sage: fac = MonomialFactory(B)

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c',)); (a, b, c,) = B._first_ngens(3)
>>> fac = MonomialFactory()
>>> fac = MonomialFactory(B)

class sage.rings.polynomial.pbori.pbori.PolynomialConstruct

Bases: object

Implement PolyBoRi’s Polynomial() constructor.

lead(x)

Return the leading monomial of boolean polynomial x, with respect to the order of parent ring.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c> = BooleanPolynomialRing()
sage: PolynomialConstruct().lead(a)
a

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c',)); (a, b, c,) = B._first_ngens(3)
>>> PolynomialConstruct().lead(a)
a

class sage.rings.polynomial.pbori.pbori.PolynomialFactory

Bases: object

Implement PolyBoRi’s Polynomial() constructor and a polynomial factory for given rings.

lead(x)

Return the leading monomial of boolean polynomial x, with respect to the order of parent ring.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c> = BooleanPolynomialRing()
sage: PolynomialFactory().lead(a)
a

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c',)); (a, b, c,) = B._first_ngens(3)
>>> PolynomialFactory().lead(a)
a

class sage.rings.polynomial.pbori.pbori.ReductionStrategy

Bases: object

Functions and options for boolean polynomial reduction.

add_generator(p)

Add the new generator p to this strategy.

INPUT:

• p – boolean polynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<x,y,z> = BooleanPolynomialRing()
sage: red = ReductionStrategy(B)
sage: red.add_generator(x)
sage: [f.p for f in red]
[x]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> red = ReductionStrategy(B)
>>> red.add_generator(x)
>>> [f.p for f in red]
[x]

can_rewrite(p)

Return True if p can be reduced by the generators of this strategy.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: red = ReductionStrategy(B)
sage: red.add_generator(a*b + c + 1)
sage: red.add_generator(b*c + d + 1)
sage: red.can_rewrite(a*b + a)
True
sage: red.can_rewrite(b + c)
False
sage: red.can_rewrite(a*d + b*c + d + 1)
True

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> red = ReductionStrategy(B)
>>> red.add_generator(a*b + c + Integer(1))
>>> red.add_generator(b*c + d + Integer(1))
>>> red.can_rewrite(a*b + a)
True
>>> red.can_rewrite(b + c)
False
>>> red.can_rewrite(a*d + b*c + d + Integer(1))
True

cheap_reductions(p)

Perform ‘cheap’ reductions on p.

INPUT:

• p – boolean polynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: red = ReductionStrategy(B)
sage: red.add_generator(a*b + c + 1)
sage: red.add_generator(b*c + d + 1)
sage: red.add_generator(a)
sage: red.cheap_reductions(a*b + a)
0
sage: red.cheap_reductions(b + c)
b + c
sage: red.cheap_reductions(a*d + b*c + d + 1)
b*c + d + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> red = ReductionStrategy(B)
>>> red.add_generator(a*b + c + Integer(1))
>>> red.add_generator(b*c + d + Integer(1))
>>> red.add_generator(a)
>>> red.cheap_reductions(a*b + a)
0
>>> red.cheap_reductions(b + c)
b + c
>>> red.cheap_reductions(a*d + b*c + d + Integer(1))
b*c + d + 1

head_normal_form(p)

Compute the normal form of p with respect to the generators of this strategy but do not perform tail any reductions.

INPUT:

• p – a polynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<x,y,z> = BooleanPolynomialRing()
sage: red = ReductionStrategy(B)
sage: red.opt_red_tail = True
sage: red.add_generator(x + y + 1)
sage: red.add_generator(y*z + z)

sage: red.head_normal_form(x + y*z)
y + z + 1

sage: red.nf(x + y*z)
y + z + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> red = ReductionStrategy(B)
>>> red.opt_red_tail = True
>>> red.add_generator(x + y + Integer(1))
>>> red.add_generator(y*z + z)

>>> red.head_normal_form(x + y*z)
y + z + 1

>>> red.nf(x + y*z)
y + z + 1

nf(p)

Compute the normal form of p w.r.t. to the generators of this reduction strategy object.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<x,y,z> = BooleanPolynomialRing()
sage: red = ReductionStrategy(B)
sage: red.add_generator(x + y + 1)
sage: red.add_generator(y*z + z)
sage: red.nf(x)
y + 1

sage: red.nf(y*z + x)
y + z + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> red = ReductionStrategy(B)
>>> red.add_generator(x + y + Integer(1))
>>> red.add_generator(y*z + z)
>>> red.nf(x)
y + 1

>>> red.nf(y*z + x)
y + z + 1

reduced_normal_form(p)

Compute the normal form of p with respect to the generators of this strategy and perform tail reductions.

INPUT:

• p – a polynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<x,y,z> = BooleanPolynomialRing()
sage: red = ReductionStrategy(B)
sage: red.add_generator(x + y + 1)
sage: red.add_generator(y*z + z)
sage: red.reduced_normal_form(x)
y + 1

sage: red.reduced_normal_form(y*z + x)
y + z + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> red = ReductionStrategy(B)
>>> red.add_generator(x + y + Integer(1))
>>> red.add_generator(y*z + z)
>>> red.reduced_normal_form(x)
y + 1

>>> red.reduced_normal_form(y*z + x)
y + z + 1

sage.rings.polynomial.pbori.pbori.TermOrder_from_pb_order(n, order, blocks)

class sage.rings.polynomial.pbori.pbori.VariableBlock

Bases: object

class sage.rings.polynomial.pbori.pbori.VariableConstruct

Bases: object

Implement PolyBoRi’s Variable() constructor.

class sage.rings.polynomial.pbori.pbori.VariableFactory

Bases: object

Implements PolyBoRi’s Variable() constructor and a variable factory for given ring

sage.rings.polynomial.pbori.pbori.add_up_polynomials(v, init)

Add up all entries in the vector v.

INPUT:

• v – a vector of boolean polynomials

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: v = BooleanPolynomialVector()
sage: l = [B.random_element() for _ in range(5)]
sage: _ = [v.append(e) for e in l]
sage: add_up_polynomials(v, B.zero()) == sum(l)
True

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> v = BooleanPolynomialVector()
>>> l = [B.random_element() for _ in range(Integer(5))]
>>> _ = [v.append(e) for e in l]
>>> add_up_polynomials(v, B.zero()) == sum(l)
True

sage.rings.polynomial.pbori.pbori.contained_vars(m)

sage.rings.polynomial.pbori.pbori.easy_linear_factors(p)

sage.rings.polynomial.pbori.pbori.gauss_on_polys(inp)

Perform Gaussian elimination on the input list of polynomials.

INPUT:

• inp – an iterable

EXAMPLES:

Sage

sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing()
sage: from sage.rings.polynomial.pbori.pbori import *
sage: l = [B.random_element() for _ in range(B.ngens())]
sage: A, _ = Sequence(l, B).coefficients_monomials()
sage: while A.rank() < 6:
....:     l = [B.random_element() for _ in range(B.ngens())]
....:     A, _ = Sequence(l, B).coefficients_monomials()

sage: e = gauss_on_polys(l)
sage: E, _ = Sequence(e, B).coefficients_monomials()
sage: E == A.echelon_form()
True

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e', 'f',)); (a, b, c, d, e, f,) = B._first_ngens(6)
>>> from sage.rings.polynomial.pbori.pbori import *
>>> l = [B.random_element() for _ in range(B.ngens())]
>>> A, _ = Sequence(l, B).coefficients_monomials()
>>> while A.rank() < Integer(6):
...     l = [B.random_element() for _ in range(B.ngens())]
...     A, _ = Sequence(l, B).coefficients_monomials()

>>> e = gauss_on_polys(l)
>>> E, _ = Sequence(e, B).coefficients_monomials()
>>> E == A.echelon_form()
True

sage.rings.polynomial.pbori.pbori.get_var_mapping(ring, other)

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

sage: P.<x,y,z> = BooleanPolynomialRing(3)
sage: R.<z,y> = QQ[]
sage: sage.rings.polynomial.pbori.pbori.get_var_mapping(P,R)
[z, y]
sage: sage.rings.polynomial.pbori.pbori.get_var_mapping(P, z^2)
[z, None]

Python

>>> from sage.all import *
>>> P = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = P._first_ngens(3)
>>> R = QQ['z, y']; (z, y,) = R._first_ngens(2)
>>> sage.rings.polynomial.pbori.pbori.get_var_mapping(P,R)
[z, y]
>>> sage.rings.polynomial.pbori.pbori.get_var_mapping(P, z**Integer(2))
[z, None]

Sage

sage: R.<z,x> = BooleanPolynomialRing(2)
sage: sage.rings.polynomial.pbori.pbori.get_var_mapping(P,R)
[z, x]
sage: sage.rings.polynomial.pbori.pbori.get_var_mapping(P, x^2)
[None, x]

Python

>>> from sage.all import *
>>> R = BooleanPolynomialRing(Integer(2), names=('z', 'x',)); (z, x,) = R._first_ngens(2)
>>> sage.rings.polynomial.pbori.pbori.get_var_mapping(P,R)
[z, x]
>>> sage.rings.polynomial.pbori.pbori.get_var_mapping(P, x**Integer(2))
[None, x]

sage.rings.polynomial.pbori.pbori.if_then_else(root, a, b)

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:

• root – a variable

• a – the if branch, a BooleSet or a BoolePolynomial

• b – the else branch, a BooleSet or a BoolePolynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori 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}}

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import if_then_else
>>> B = BooleanPolynomialRing(Integer(6),'x')
>>> x0,x1,x2,x3,x4,x5 = B.gens()
>>> f0 = x2*x3+x3
>>> f1 = x4
>>> if_then_else(x1, f0, f1)
{{x1,x2,x3}, {x1,x3}, {x4}}

Sage

sage: if_then_else(x1.lm().index(),f0,f1)
{{x1,x2,x3}, {x1,x3}, {x4}}

Python

>>> from sage.all import *
>>> if_then_else(x1.lm().index(),f0,f1)
{{x1,x2,x3}, {x1,x3}, {x4}}

Sage

sage: if_then_else(x5, f0, f1)
Traceback (most recent call last):
...
IndexError: index of root must be less than the values of roots of the branches

Python

>>> from sage.all import *
>>> if_then_else(x5, f0, f1)
Traceback (most recent call last):
...
IndexError: index of root must be less than the values of roots of the branches

sage.rings.polynomial.pbori.pbori.interpolate(zero, one)

Interpolate a polynomial evaluating to zero on zero and to one on ones.

INPUT:

• zero – the set of zero

• one – the set of ones

EXAMPLES:

Sage

sage: B = BooleanPolynomialRing(4,"x0,x1,x2,x3")
sage: x = B.gen
sage: from sage.rings.polynomial.pbori.interpolate import *
sage: V=(x(0)+x(1)+x(2)+x(3)+1).set()

sage: V
{{x0}, {x1}, {x2}, {x3}, {}}

sage: f=x(0)*x(1)+x(1)+x(2)+1
sage: nf_lex_points(f, V)
x1 + x2 + 1

sage: z=f.zeros_in(V)
sage: z
{{x1}, {x2}}

sage: o=V.diff(z)
sage: o
{{x0}, {x3}, {}}

sage: interpolate(z,o)
x0*x1*x2 + x0*x1 + x0*x2 + x1*x2 + x1 + x2 + 1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4),"x0,x1,x2,x3")
>>> x = B.gen
>>> from sage.rings.polynomial.pbori.interpolate import *
>>> V=(x(Integer(0))+x(Integer(1))+x(Integer(2))+x(Integer(3))+Integer(1)).set()

>>> V
{{x0}, {x1}, {x2}, {x3}, {}}

>>> f=x(Integer(0))*x(Integer(1))+x(Integer(1))+x(Integer(2))+Integer(1)
>>> nf_lex_points(f, V)
x1 + x2 + 1

>>> z=f.zeros_in(V)
>>> z
{{x1}, {x2}}

>>> o=V.diff(z)
>>> o
{{x0}, {x3}, {}}

>>> interpolate(z,o)
x0*x1*x2 + x0*x1 + x0*x2 + x1*x2 + x1 + x2 + 1

sage.rings.polynomial.pbori.pbori.interpolate_smallest_lex(zero, one)

Interpolate the lexicographical smallest polynomial evaluating to zero on zero and to one on ones.

INPUT:

• zero – the set of zeros

• one – the set of ones

EXAMPLES:

Let V be a set of points in \(\GF{2}^n\) and f a Boolean polynomial. V can be encoded as a BooleSet. 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:

Sage

sage: B = BooleanPolynomialRing(4,"x0,x1,x2,x3")
sage: x = B.gen
sage: from sage.rings.polynomial.pbori.interpolate import *
sage: V=(x(0)+x(1)+x(2)+x(3)+1).set()

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4),"x0,x1,x2,x3")
>>> x = B.gen
>>> from sage.rings.polynomial.pbori.interpolate import *
>>> V=(x(Integer(0))+x(Integer(1))+x(Integer(2))+x(Integer(3))+Integer(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 \(\GF{2}^4\) or a vector space of higher dimension:

Sage

sage: V
{{x0}, {x1}, {x2}, {x3}, {}}

sage: f=x(0)*x(1)+x(1)+x(2)+1
sage: nf_lex_points(f, V)
x1 + x2 + 1

Python

>>> from sage.all import *
>>> V
{{x0}, {x1}, {x2}, {x3}, {}}

>>> f=x(Integer(0))*x(Integer(1))+x(Integer(1))+x(Integer(2))+Integer(1)
>>> nf_lex_points(f, V)
x1 + x2 + 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:

Sage

sage: z=f.zeros_in(V)
sage: z
{{x1}, {x2}}

sage: o=V.diff(z)
sage: o
{{x0}, {x3}, {}}

sage: interpolate_smallest_lex(z,o)
x1 + x2 + 1

Python

>>> from sage.all import *
>>> z=f.zeros_in(V)
>>> z
{{x1}, {x2}}

>>> o=V.diff(z)
>>> o
{{x0}, {x3}, {}}

>>> interpolate_smallest_lex(z,o)
x1 + x2 + 1

sage.rings.polynomial.pbori.pbori.ll_red_nf_noredsb(p, reductors)

Redude the polynomial p by the set of reductors with linear leading terms.

INPUT:

• p – boolean polynomial

• reductors – boolean set encoding a Groebner basis with linear leading terms

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import ll_red_nf_noredsb
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: p = a*b + c + d + 1
sage: f,g  = a + c + 1, b + d + 1
sage: reductors = f.set().union( g.set() )
sage: ll_red_nf_noredsb(p, reductors)
b*c + b*d + c + d + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import ll_red_nf_noredsb
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> p = a*b + c + d + Integer(1)
>>> f,g  = a + c + Integer(1), b + d + Integer(1)
>>> reductors = f.set().union( g.set() )
>>> ll_red_nf_noredsb(p, reductors)
b*c + b*d + c + d + 1

sage.rings.polynomial.pbori.pbori.ll_red_nf_noredsb_single_recursive_call(p, reductors)

Redude the polynomial p by the set of reductors with linear leading terms.

ll_red_nf_noredsb_single_recursive() call has the same specification as ll_red_nf_noredsb(), but a different implementation: It is very sensitive to the ordering of variables, however it has the property, that it needs just one recursive call.

INPUT:

• p – boolean polynomial

• reductors – boolean set encoding a Groebner basis with linear leading terms

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import ll_red_nf_noredsb_single_recursive_call
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: p = a*b + c + d + 1
sage: f,g  = a + c + 1, b + d + 1
sage: reductors = f.set().union( g.set() )
sage: ll_red_nf_noredsb_single_recursive_call(p, reductors)
b*c + b*d + c + d + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import ll_red_nf_noredsb_single_recursive_call
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> p = a*b + c + d + Integer(1)
>>> f,g  = a + c + Integer(1), b + d + Integer(1)
>>> reductors = f.set().union( g.set() )
>>> ll_red_nf_noredsb_single_recursive_call(p, reductors)
b*c + b*d + c + d + 1

sage.rings.polynomial.pbori.pbori.ll_red_nf_redsb(p, reductors)

Redude the polynomial p by the set of reductors with linear leading terms. It is assumed that the set reductors is a reduced Groebner basis.

INPUT:

• p – boolean polynomial

• reductors – boolean set encoding a reduced Groebner basis with linear leading terms

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import ll_red_nf_redsb
sage: B.<a,b,c,d> = BooleanPolynomialRing()
sage: p = a*b + c + d + 1
sage: f,g  = a + c + 1, b + d + 1
sage: reductors = f.set().union( g.set() )
sage: ll_red_nf_redsb(p, reductors)
b*c + b*d + c + d + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import ll_red_nf_redsb
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> p = a*b + c + d + Integer(1)
>>> f,g  = a + c + Integer(1), b + d + Integer(1)
>>> reductors = f.set().union( g.set() )
>>> ll_red_nf_redsb(p, reductors)
b*c + b*d + c + d + 1

sage.rings.polynomial.pbori.pbori.map_every_x_to_x_plus_one(p)

Map every variable x_i in this polynomial to x_i + 1.

EXAMPLES:

Sage

sage: B.<a,b,z> = BooleanPolynomialRing(3)
sage: f = a*b + z + 1; f
a*b + z + 1
sage: from sage.rings.polynomial.pbori.pbori import map_every_x_to_x_plus_one
sage: map_every_x_to_x_plus_one(f)
a*b + a + b + z + 1
sage: f(a+1,b+1,z+1)
a*b + a + b + z + 1

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('a', 'b', 'z',)); (a, b, z,) = B._first_ngens(3)
>>> f = a*b + z + Integer(1); f
a*b + z + 1
>>> from sage.rings.polynomial.pbori.pbori import map_every_x_to_x_plus_one
>>> map_every_x_to_x_plus_one(f)
a*b + a + b + z + 1
>>> f(a+Integer(1),b+Integer(1),z+Integer(1))
a*b + a + b + z + 1

sage.rings.polynomial.pbori.pbori.mod_mon_set(a_s, v_s)

sage.rings.polynomial.pbori.pbori.mod_var_set(a, v)

sage.rings.polynomial.pbori.pbori.mult_fact_sim_C(v, ring)

sage.rings.polynomial.pbori.pbori.nf3(s, p, m)

sage.rings.polynomial.pbori.pbori.parallel_reduce(inp, strat, average_steps, delay_f)

sage.rings.polynomial.pbori.pbori.random_set(variables, length)

Return a random set of monomials with length elements with each element in the variables variables.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import random_set, set_random_seed
sage: B.<a,b,c,d,e> = BooleanPolynomialRing()
sage: (a*b*c*d).lm()
a*b*c*d
sage: set_random_seed(1337)
sage: random_set((a*b*c*d).lm(),10)
{{a,b,c,d}, {a,b}, {a,c,d}, {a,c}, {b,c,d}, {b,d}, {b}, {c,d}, {c}, {d}}

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import random_set, set_random_seed
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e',)); (a, b, c, d, e,) = B._first_ngens(5)
>>> (a*b*c*d).lm()
a*b*c*d
>>> set_random_seed(Integer(1337))
>>> random_set((a*b*c*d).lm(),Integer(10))
{{a,b,c,d}, {a,b}, {a,c,d}, {a,c}, {b,c,d}, {b,d}, {b}, {c,d}, {c}, {d}}

sage.rings.polynomial.pbori.pbori.recursively_insert(n, ind, m)

sage.rings.polynomial.pbori.pbori.red_tail(s, p)

Perform tail reduction on p using the generators of s.

INPUT:

• s – a reduction strategy

• p – a polynomial

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import *
sage: B.<x,y,z> = BooleanPolynomialRing()
sage: red = ReductionStrategy(B)
sage: red.add_generator(x + y + 1)
sage: red.add_generator(y*z + z)
sage: red_tail(red,x)
x
sage: red_tail(red,x*y + x)
x*y + y + 1

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import *
>>> B = BooleanPolynomialRing(names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> red = ReductionStrategy(B)
>>> red.add_generator(x + y + Integer(1))
>>> red.add_generator(y*z + z)
>>> red_tail(red,x)
x
>>> red_tail(red,x*y + x)
x*y + y + 1

sage.rings.polynomial.pbori.pbori.set_random_seed(seed)

Set the PolyBoRi random seed to seed.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.pbori.pbori import random_set, set_random_seed
sage: B.<a,b,c,d,e> = BooleanPolynomialRing()
sage: (a*b*c*d).lm()
a*b*c*d
sage: set_random_seed(1337)
sage: random_set((a*b*c*d).lm(),2)
{{b}, {c}}
sage: random_set((a*b*c*d).lm(),2)
{{a,c,d}, {c}}

sage: set_random_seed(1337)
sage: random_set((a*b*c*d).lm(),2)
{{b}, {c}}
sage: random_set((a*b*c*d).lm(),2)
{{a,c,d}, {c}}

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import random_set, set_random_seed
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c', 'd', 'e',)); (a, b, c, d, e,) = B._first_ngens(5)
>>> (a*b*c*d).lm()
a*b*c*d
>>> set_random_seed(Integer(1337))
>>> random_set((a*b*c*d).lm(),Integer(2))
{{b}, {c}}
>>> random_set((a*b*c*d).lm(),Integer(2))
{{a,c,d}, {c}}

>>> set_random_seed(Integer(1337))
>>> random_set((a*b*c*d).lm(),Integer(2))
{{b}, {c}}
>>> random_set((a*b*c*d).lm(),Integer(2))
{{a,c,d}, {c}}

sage.rings.polynomial.pbori.pbori.substitute_variables(parent, vec, poly)

var(i) is replaced by vec[i] in poly.

EXAMPLES:

Sage

sage: B.<a,b,c> = BooleanPolynomialRing()
sage: f = a*b + c + 1
sage: from sage.rings.polynomial.pbori.pbori import substitute_variables
sage: substitute_variables(B, [a,b,c],f)
a*b + c + 1
sage: substitute_variables(B, [a+1,b,c],f)
a*b + b + c + 1
sage: substitute_variables(B, [a+1,b+1,c],f)
a*b + a + b + c
sage: substitute_variables(B, [a+1,b+1,B(0)],f)
a*b + a + b

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c',)); (a, b, c,) = B._first_ngens(3)
>>> f = a*b + c + Integer(1)
>>> from sage.rings.polynomial.pbori.pbori import substitute_variables
>>> substitute_variables(B, [a,b,c],f)
a*b + c + 1
>>> substitute_variables(B, [a+Integer(1),b,c],f)
a*b + b + c + 1
>>> substitute_variables(B, [a+Integer(1),b+Integer(1),c],f)
a*b + a + b + c
>>> substitute_variables(B, [a+Integer(1),b+Integer(1),B(Integer(0))],f)
a*b + a + b

Substitution is also allowed with different rings:

Sage

sage: B.<a,b,c> = BooleanPolynomialRing()
sage: f = a*b + c + 1
sage: B.<w,x,y,z> = BooleanPolynomialRing(order='deglex')

sage: from sage.rings.polynomial.pbori.pbori import substitute_variables
sage: substitute_variables(B, [x,y,z], f) * w
w*x*y + w*z + w

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(names=('a', 'b', 'c',)); (a, b, c,) = B._first_ngens(3)
>>> f = a*b + c + Integer(1)
>>> B = BooleanPolynomialRing(order='deglex', names=('w', 'x', 'y', 'z',)); (w, x, y, z,) = B._first_ngens(4)

>>> from sage.rings.polynomial.pbori.pbori import substitute_variables
>>> substitute_variables(B, [x,y,z], f) * w
w*x*y + w*z + w

sage.rings.polynomial.pbori.pbori.top_index(s)

Return the highest index in the parameter s.

INPUT:

• s – BooleSet, BooleMonomial, BoolePolynomial

EXAMPLES:

Sage

sage: B.<x,y,z> = BooleanPolynomialRing(3)
sage: from sage.rings.polynomial.pbori.pbori import top_index
sage: top_index(x.lm())
0
sage: top_index(y*z)
1
sage: top_index(x + 1)
0

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = B._first_ngens(3)
>>> from sage.rings.polynomial.pbori.pbori import top_index
>>> top_index(x.lm())
0
>>> top_index(y*z)
1
>>> top_index(x + Integer(1))
0

sage.rings.polynomial.pbori.pbori.unpickle_BooleanPolynomial(ring, string)

Unpickle boolean polynomials.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> T = TermOrder('deglex',Integer(2))+TermOrder('deglex',Integer(2))
>>> P = BooleanPolynomialRing(Integer(4),order=T, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = P._first_ngens(4)
>>> loads(dumps(a+b)) == a+b # indirect doctest
True

sage.rings.polynomial.pbori.pbori.unpickle_BooleanPolynomial0(ring, l)

Unpickle boolean polynomials.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> T = TermOrder('deglex',Integer(2))+TermOrder('deglex',Integer(2))
>>> P = BooleanPolynomialRing(Integer(4),order=T, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = P._first_ngens(4)
>>> loads(dumps(a+b)) == a+b # indirect doctest
True

sage.rings.polynomial.pbori.pbori.unpickle_BooleanPolynomialRing(n, names, order)

Unpickle boolean polynomial rings.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> T = TermOrder('deglex',Integer(2))+TermOrder('deglex',Integer(2))
>>> P = BooleanPolynomialRing(Integer(4),order=T, names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = P._first_ngens(4)
>>> loads(dumps(P)) == P  # indirect doctest
True

sage.rings.polynomial.pbori.pbori.zeros(pol, s)

Return a BooleSet encoding on which points from s the polynomial pol evaluates to zero.

INPUT:

• pol – boolean polynomial

• s – set of points encoded as a BooleSet

EXAMPLES:

Sage

sage: B.<a,b,c,d> = BooleanPolynomialRing(4)
sage: f = a*b + a*c + d + b

Python

>>> from sage.all import *
>>> B = BooleanPolynomialRing(Integer(4), names=('a', 'b', 'c', 'd',)); (a, b, c, d,) = B._first_ngens(4)
>>> f = a*b + a*c + d + b

Now we create a set of points:

Sage

sage: s = a*b + a*b*c + c*d + b*c
sage: s = s.set(); s
{{a,b,c}, {a,b}, {b,c}, {c,d}}

Python

>>> from sage.all import *
>>> s = a*b + a*b*c + c*d + b*c
>>> s = s.set(); s
{{a,b,c}, {a,b}, {b,c}, {c,d}}

This encodes the points (1,1,1,0), (1,1,0,0), (0,0,1,1) and (0,1,1,0). But of these only (1,1,0,0) evaluates to zero.:

Sage

sage: from sage.rings.polynomial.pbori.pbori import zeros
sage: zeros(f, s)
{{a,b}}

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.pbori.pbori import zeros
>>> zeros(f, s)
{{a,b}}

For comparison we work with tuples:

Sage

sage: f.zeros_in([(1,1,1,0), (1,1,0,0), (0,0,1,1), (0,1,1,0)])
((1, 1, 0, 0),)

Python

>>> from sage.all import *
>>> f.zeros_in([(Integer(1),Integer(1),Integer(1),Integer(0)), (Integer(1),Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(1)), (Integer(0),Integer(1),Integer(1),Integer(0))])
((1, 1, 0, 0),)