Boolean Polynomials¶
Elements of the quotient ring
are called boolean polynomials. Boolean polynomials arise naturally in cryptography, coding theory, formal logic, chip design and other areas. This implementation is a thin wrapper around the PolyBoRi library by Michael Brickenstein and Alexander Dreyer.
“Boolean polynomials can be modelled in a rather simple way, with
both coefficients and degree per variable lying in
{0, 1}
. The ring of Boolean polynomials is, however,
not a polynomial ring, but rather the quotient ring of the
polynomial ring over the field with two elements modulo the field
equations \(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
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
(viaUniqueRepresentation
) andBooleanMonomial
. - 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
First, we compute the lexicographical Groebner basis in the polynomial ring
sage: P.<a,b,c,d,e> = PolynomialRing(GF(2), 5, order='lex')
sage: I1 = ideal([a*b + c*d + 1, a*c*e + d*e, a*b*e + c*e, b*c + c*d*e + 1])
sage: for f in I1.groebner_basis():
....: f
a + c^2*d + c + d^2*e
b*c + d^3*e^2 + d^3*e + d^2*e^2 + d*e + e + 1
b*e + d*e^2 + d*e + e
c*e + d^3*e^2 + d^3*e + d^2*e^2 + d*e
d^4*e^2 + d^4*e + d^3*e + d^2*e^2 + d^2*e + d*e + e
If one wants to solve this system over the algebraic closure of \(\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: J = I1 + sage.rings.ideal.FieldIdeal(P)
sage: for f in J.groebner_basis():
....: f
a + d + 1
b + 1
c + 1
d^2 + d
e
So the solutions over \(\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: Q = P.quotient( sage.rings.ideal.FieldIdeal(P) )
sage: I2 = ideal([Q(f) for f in I1.gens()])
sage: for f in I2.groebner_basis():
....: f
abar + dbar + 1
bbar + 1
cbar + 1
ebar
This quotient ring is exactly what PolyBoRi handles well:
sage: B.<a,b,c,d,e> = BooleanPolynomialRing(5, order='lex')
sage: I2 = ideal([B(f) for f in I1.gens()])
sage: for f in I2.groebner_basis():
....: f
a + d + 1
b + 1
c + 1
e
Note that 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: from brial 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
sage: [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:
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.
BooleConstant
¶ Bases:
object
Construct a boolean constant (modulo 2) from integer value:
INPUT:
i
- an integer
EXAMPLES:
sage: from brial import BooleConstant sage: [BooleConstant(i) for i in range(5)] [0, 1, 0, 1, 0]
-
deg
()¶ Get degree of boolean constant.
EXAMPLES:
sage: from brial import BooleConstant sage: BooleConstant(0).deg() -1 sage: BooleConstant(1).deg() 0
-
has_constant_part
()¶ This is true for \(BooleConstant(1)\).
EXAMPLES:
sage: from brial import BooleConstant sage: BooleConstant(1).has_constant_part() True sage: BooleConstant(0).has_constant_part() False
-
is_constant
()¶ This is always true for in this case.
EXAMPLES:
sage: from brial import BooleConstant sage: BooleConstant(1).is_constant() True sage: BooleConstant(0).is_constant() True
-
is_one
()¶ Check whether boolean constant is one.
EXAMPLES:
sage: from brial import BooleConstant sage: BooleConstant(0).is_one() False sage: BooleConstant(1).is_one() True
-
is_zero
()¶ Check whether boolean constant is zero.
EXAMPLES:
sage: from brial import BooleConstant sage: BooleConstant(1).is_zero() False sage: BooleConstant(0).is_zero() True
-
variables
()¶ Get variables (return always and empty tuple).
EXAMPLES:
sage: from brial import BooleConstant sage: BooleConstant(0).variables() () sage: BooleConstant(1).variables() ()
-
class
sage.rings.polynomial.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 typeBooleSet
by using the member functionBooleanPolynomial.set()
.INPUT:
param
- either aCCuddNavigator
, aBooleSet
orNone
.ring
- a boolean polynomial ring.
EXAMPLES:
sage: from brial 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 brial import * sage: 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: 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}}
-
change
(ind)¶ Swaps the presence of
x_i
in each entry of the set.EXAMPLES:
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}}
-
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: 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}}
-
divide
(rhs)¶ Divide each element of this set by the monomial
rhs
and return a new set containing the result.EXAMPLES:
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}, {}}
-
divisors_of
(m)¶ Return those members which are divisors of
m
.INPUT:
m
- a boolean monomial
EXAMPLES:
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}}
-
empty
()¶ Return
True
if this set is empty.EXAMPLES:
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
-
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: 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}, {}}
-
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: 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}}
-
minimal_elements
()¶ Return a new set containing a divisor of all elements of this set.
EXAMPLES:
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}}
-
multiples_of
(m)¶ Return those members which are multiples of
m
.INPUT:
m
- a boolean monomial
EXAMPLES:
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}}
-
n_nodes
()¶ Return the number of nodes in the ZDD.
EXAMPLES:
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
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: from brial 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
-
ring
()¶ Return the parent ring.
EXAMPLES:
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
-
set
()¶ Return
self
.EXAMPLES:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: BS = (a*b + c).set() sage: BS.set() is BS True
-
size_double
()¶ Return the size of this set as a floating point number.
EXAMPLES:
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
-
stable_hash
()¶ A hash value which is stable across processes.
EXAMPLES:
sage: B.<x,y> = BooleanPolynomialRing() sage: x.set() is x.set() False sage: 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: 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}}
-
subset1
(i)¶ Return a set of those elements in this set which do contain the variable indexed by
i
and evaluate the variable indexed byi
to 1.INPUT:
i
- an index
EXAMPLES:
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}}
-
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: 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}, {}}
-
vars
()¶ Return the variables in this set as a monomial.
EXAMPLES:
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
-
class
sage.rings.polynomial.pbori.
BooleSetIterator
¶ Bases:
object
Helper class to iterate over boolean sets.
-
next
()¶ x.next() -> the next value, or raise StopIteration
-
-
class
sage.rings.polynomial.pbori.
BooleanMonomial
¶ Bases:
sage.structure.element.MonoidElement
Construct a boolean monomial.
INPUT:
parent
- parent monoid this element lives in
EXAMPLES:
sage: from brial import BooleanMonomialMonoid, BooleanMonomial sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: 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: from brial 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
Note
This function is part of the upstream PolyBoRi interface.
-
degree
(x=None)¶ Return the degree of this monomial in
x
, wherex
must be one of the generators of the polynomial ring.INPUT:
x
- boolean multivariate polynomial (a generator of the polynomial ring). Ifx
is not specified (or isNone
), return the total degree of this monomial.
EXAMPLES:
sage: from brial 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
-
divisors
()¶ Return a set of boolean monomials with all divisors of this monomial.
EXAMPLES:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: m.divisors() {{x,y}, {x}, {y}, {}}
-
gcd
(rhs)¶ Return the greatest common divisor of this boolean monomial and
rhs
.INPUT:
rhs
- a boolean monomial
EXAMPLES:
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
-
index
()¶ Return the variable index of the first variable in this monomial.
EXAMPLES:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: 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: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: 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
- a boolean monomial
EXAMPLES:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x sage: m = f.lm() sage: g = x*y*z sage: n = g.lm() sage: m.multiples(n) {{x,y,z}, {x,y}, {x,z}, {x}} sage: n.multiples(m) {{x,y,z}}
Note
The returned set always contains
self
even if the boundrhs
is smaller thanself
.
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: from brial 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
-
reducible_by
(rhs)¶ Return
True
ifself
is reducible byrhs
.INPUT:
rhs
- a boolean monomial
EXAMPLES:
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
-
ring
()¶ Return the corresponding boolean ring.
EXAMPLES:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: a.lm().ring() is B True
-
set
()¶ Return a boolean set of variables in this monomials.
EXAMPLES:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: m.set() {{x,y}}
-
stable_hash
()¶ A hash value which is stable across processes.
EXAMPLES:
sage: B.<x,y> = BooleanPolynomialRing() sage: x.lm() is x.lm() False sage: 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: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: M(x*z).variables() # indirect doctest (x, z)
-
class
sage.rings.polynomial.pbori.
BooleanMonomialIterator
¶ Bases:
object
An iterator over the variable indices of a monomial.
-
next
()¶ x.next() -> the next value, or raise StopIteration
-
-
class
sage.rings.polynomial.pbori.
BooleanMonomialMonoid
(polring)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.monoids.monoid.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: from brial import BooleanMonomialMonoid sage: P.<x,y> = BooleanPolynomialRing(2) sage: M = BooleanMonomialMonoid(P) sage: M MonomialMonoid of Boolean PolynomialRing in x, y sage: M.gens() (x, y) sage: type(M.gen(0)) <type 'sage.rings.polynomial.pbori.BooleanMonomial'>
Since trac ticket #9138, boolean monomial monoids are unique parents and are fit into the category framework:
sage: loads(dumps(M)) is M True sage: TestSuite(M).run()
-
gen
(i=0)¶ Return the i-th generator of
self
.INPUT:
i
- an integer
EXAMPLES:
sage: from brial 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
-
gens
()¶ Return the tuple of generators of this monoid.
EXAMPLES:
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: M.gens() (x, y, z)
-
ngens
()¶ Return the number of variables in this monoid.
EXAMPLES:
sage: from brial import BooleanMonomialMonoid sage: P = BooleanPolynomialRing(100, 'x') sage: M = BooleanMonomialMonoid(P) sage: M.ngens() 100
-
class
sage.rings.polynomial.pbori.
BooleanMonomialVariableIterator
¶ Bases:
object
-
next
()¶ x.next() -> the next value, or raise StopIteration
-
-
class
sage.rings.polynomial.pbori.
BooleanMulAction
¶
-
class
sage.rings.polynomial.pbori.
BooleanPolynomial
¶ Bases:
sage.rings.polynomial.multi_polynomial.MPolynomial
Construct a boolean polynomial object in the given boolean polynomial ring.
INPUT:
parent
- a 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: B.<x,y,z> = BooleanPolynomialRing(3) sage: x.constant() False
sage: B(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: B.<a,b> = BooleanPolynomialRing() sage: a.constant_coefficient() 0 sage: (a+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: P.<x,y> = BooleanPolynomialRing(2) sage: (x+y).degree() 1
sage: P(1).degree() 0
sage: (x*y + x + y + 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
, wherex
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: P.<x,y> = BooleanPolynomialRing(2) sage: (x+y).degree() 1
sage: P(1).degree() 0
sage: (x*y + x + y + 1).degree() 2 sage: (x*y + x + y + 1).degree(x) 1
-
elength
()¶ Return elimination length as used in the SlimGB algorithm.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2) sage: x.elength() 1 sage: f = x*y + 1 sage: 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: B.<a,b,z> = BooleanPolynomialRing(3,order='lex') sage: f = b*z + a + 1 sage: 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: 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
sage: f.graded_part(0) 1
-
has_constant_part
()¶ Return
True
if this boolean polynomial has a constant part, i.e. if1
is a term.EXAMPLES:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + c*d + a*b + 1 sage: f.has_constant_part() True
sage: f = a*b*c + c*d + a*b sage: f.has_constant_part() False
-
is_constant
()¶ Check if
self
is constant.EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P(1).is_constant() True
sage: P(0).is_constant() True
sage: x.is_constant() False
sage: (x*y).is_constant() False
-
is_equal
(right)¶ EXAMPLES:
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
Note
This function is part of the upstream PolyBoRi interface.
-
is_homogeneous
()¶ Return
True
if this element is a homogeneous polynomial.EXAMPLES:
sage: P.<x, y> = BooleanPolynomialRing() sage: (x+y).is_homogeneous() True sage: P(0).is_homogeneous() True sage: (x+1).is_homogeneous() False
-
is_one
()¶ Check if self is 1.
EXAMPLES:
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
-
is_pair
()¶ Check if
self
has exactly two terms.EXAMPLES:
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
-
is_singleton
()¶ Check if
self
has at most one term.EXAMPLES:
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
-
is_singleton_or_pair
()¶ Check if
self
has at most two terms.EXAMPLES:
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
-
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: P.<x,y> = BooleanPolynomialRing(2) sage: P.one().is_unit() True
sage: x.is_unit() False
-
is_univariate
()¶ Return
True
if self is a univariate polynomial, that is if self contains only one variable.EXAMPLES:
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
-
is_zero
()¶ Check if
self
is zero.EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P(0).is_zero() True
sage: x.is_zero() False
sage: P(1).is_zero() False
-
lead
()¶ Return the leading monomial of boolean polynomial, with respect to to the order of parent ring.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: (x+y+y*z).lead() x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: (x+y+y*z).lead() y*z
Note
This function is part of the upstream PolyBoRi interface.
-
lead_deg
()¶ Return the total degree of the leading monomial of
self
.EXAMPLES:
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
Note
This function is part of the upstream PolyBoRi interface.
-
lead_divisors
()¶ Return a
BooleSet
of all divisors of the leading monomial.EXAMPLES:
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*b + z + 1 sage: 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: 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
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: B.<x,y,z> = BooleanPolynomialRing(3,order='lex') sage: f = x + y*z sage: f x + y*z sage: f.lex_lead_deg() 1
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
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: 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
-
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: P.<x,y,z> = BooleanPolynomialRing(3) sage: (x+y+y*z).lt() x
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: (x+y+y*z).lt() y*z
-
map_every_x_to_x_plus_one
()¶ Map every variable
x_i
in this polynomial tox_i + 1
.EXAMPLES:
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
-
monomial_coefficient
(mon)¶ Return the coefficient of the monomial
mon
inself
, wheremon
must have the same parent asself
.INPUT:
mon
- a monomial
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2) sage: x.monomial_coefficient(x) 1 sage: x.monomial_coefficient(y) 0 sage: R.<x,y,z,a,b,c>=BooleanPolynomialRing(6) sage: f=(1-x)*(1+y); f x*y + x + y + 1
sage: f.monomial_coefficient(1) 1
sage: f.monomial_coefficient(0) 0
-
monomials
()¶ Return a list of monomials appearing in
self
ordered largest to smallest.EXAMPLES:
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() []
-
n_nodes
()¶ Return the number of nodes in the ZDD implementing this polynomial.
EXAMPLES:
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
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: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + 1 sage: f.n_vars() 3
Note
This function is part of the upstream PolyBoRi interface.
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: from brial 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
Note
This function is part of the upstream PolyBoRi interface.
-
nvariables
()¶ Return the number of variables used to form this boolean polynomial.
EXAMPLES:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b*c + 1 sage: f.nvariables() 3
-
reduce
(I)¶ Return the normal form of
self
w.r.t.I
, i.e. return the remainder ofself
with respect to the polynomials inI
. If the polynomial set/listI
is not a Groebner basis the result is not canonical.INPUT:
I
- a list/set of polynomials in self.parent(). If I is an ideal, the generators are used.
EXAMPLES:
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
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 polynomialrhs
.INPUT:
rhs
- a boolean polynomial
EXAMPLES:
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
Note
This function is part of the upstream PolyBoRi interface.
-
ring
()¶ Return the parent of this boolean polynomial.
EXAMPLES:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: a.ring() is B True
-
set
()¶ Return a
BooleSet
with all monomials appearing in this polynomial.EXAMPLES:
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: (a*b+z+1).set() {{a,b}, {z}, {}}
-
spoly
(rhs)¶ Return the S-Polynomial of this boolean polynomial and the other boolean polynomial
rhs
.EXAMPLES:
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
Note
This function is part of the upstream PolyBoRi interface.
-
stable_hash
()¶ A hash value which is stable across processes.
EXAMPLES:
sage: B.<x,y> = BooleanPolynomialRing() sage: x is B.gen(0) False sage: x.stable_hash() == B.gen(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: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + y*z + 1 sage: f.subs(x=1) y*z + y + z + 1 sage: f.subs(x=0) y*z + z + 1
sage: f.subs(x=y) y*z + y + z + 1
sage: f.subs({x:1},y=1) 0 sage: f.subs(y=1) x + 1 sage: f.subs(y=1,z=1) x + 1 sage: f.subs(z=1) x*y + y sage: f.subs({'x':1},y=1) 0
This method can work fully symbolic:
sage: f.subs(x=var('a'),y=var('b'),z=var('c')) a*b + b*c + c + 1 sage: f.subs({'x':var('a'),'y':var('b'),'z':var('c')}) a*b + b*c + c + 1
-
terms
()¶ Return a list of monomials appearing in
self
ordered largest to smallest.EXAMPLES:
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]
-
total_degree
()¶ Return the total degree of
self
.EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2) sage: (x+y).total_degree() 1
sage: P(1).total_degree() 0
sage: (x*y + x + y + 1).total_degree() 2
-
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 theis_univariate()
method. The new Polynomial is over GF(2) and in the variablex
if no ringR
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 + 1Here’s an example with a constant multivariate polynomial:
sage: g = R(1) sage: h = g.univariate_polynomial(); h 1 sage: h.parent() 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: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*z + z + 1 sage: f.variables() (x, z) sage: f.variable(1) z
-
variables
()¶ Return a tuple of all variables appearing in
self
.EXAMPLES:
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() ()
-
vars_as_monomial
()¶ Return a boolean monomial with all the variables appearing in
self
.EXAMPLES:
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
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 aBooleSet
, then the return type is also aBooleSet
. Ifs
is a set/list/tuple of tuple this function returns a tuple of tuples.INPUT:
s
- candidate points for evaluation to zero
EXAMPLES:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b + c + d + 1
Now we create a set of points:
sage: s = a*b + a*b*c + c*d + 1 sage: s = s.set(); s {{a,b,c}, {a,b}, {c,d}, {}}
This encodes the points (1,1,1,0), (1,1,0,0), (0,0,1,1) and (0,0,0,0). But of these only (1,1,0,0) evaluates to zero.
sage: f.zeros_in(s) {{a,b}}
sage: f.zeros_in([(1,1,1,0), (1,1,0,0), (0,0,1,1), (0,0,0,0)]) ((1, 1, 0, 0),)
-
class
sage.rings.polynomial.pbori.
BooleanPolynomialIdeal
(ring, gens=[], coerce=True)¶ Bases:
sage.rings.polynomial.multi_polynomial_ideal.MPolynomialIdeal
Construct an ideal in the boolean polynomial ring.
INPUT:
ring
- the ring this ideal is defined ingens
- a list of generatorscoerce
- coerce all elements to the ringring
(default:True
)
EXAMPLES:
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4) sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) sage: I Ideal (x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) of Boolean PolynomialRing in x0, x1, x2, x3 sage: 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 toTrue
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 settingheuristic=False
(default:True
)lazy
- (default:True
)invert
- settinginvert=True
input and output get a transformationx+1
for each variablex
, which shouldn’t effect the calculated GB, but the algorithm.other_ordering_first
- possible values areFalse
or an ordering code. In practice, many Boolean examples have very few solutions and a very easy Groebner basis. So, a complex walk algorithm (which cannot be implemented using the data structures) seems unnecessary, as such Groebner bases can be converted quite fast by the normal Buchberger algorithm from one ordering into another ordering. (default:False
)prot
- show protocol (default:False
)full_prot
- show full protocol (default:False
)
EXAMPLES:
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4) sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) sage: I.groebner_basis() [x0*x1 + x0*x2 + x0, x0*x2*x3 + x0*x3]
Another somewhat bigger example:
sage: sr = mq.SR(2,1,1,4,gf2=True, polybori=True) sage: F,s = sr.polynomial_system() sage: I = F.ideal() sage: I.groebner_basis() Polynomial Sequence with 36 Polynomials in 36 Variables
We compute the same example with Magma:
sage: sr = mq.SR(2,1,1,4,gf2=True, polybori=True) sage: F,s = sr.polynomial_system() 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
-
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 alli != j`
LT(g_i)
does not dividem
for all monomialsm
of{g_1,...,g_{i-1},g_{i+1},...,g_s}
EXAMPLES:
sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True) sage: F,s = sr.polynomial_system() sage: I = F.ideal() sage: I.interreduced_basis() [k100 + 1, k101 + k001 + 1, k102, k103 + 1, x100 + k001 + 1, x101 + k001, x102, x103 + k001, w100 + 1, w101 + k001 + 1, w102 + 1, w103 + 1, s000 + k001, s001 + k001 + 1, s002, s003 + k001 + 1, k000 + 1, k002 + 1, k003 + 1]
-
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: 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
-
variety
(**kwds)¶ Return the variety associated to this boolean ideal.
EXAMPLES:
A simple example:
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}]
-
class
sage.rings.polynomial.pbori.
BooleanPolynomialIterator
¶ Bases:
object
Iterator over the monomials of a boolean polynomial.
-
next
()¶ x.next() -> the next value, or raise StopIteration
-
-
class
sage.rings.polynomial.pbori.
BooleanPolynomialRing
¶ Bases:
sage.rings.polynomial.multi_polynomial_ring_base.MPolynomialRing_base
Construct a boolean polynomial ring with the following parameters:
INPUT:
n
- number of variables (an integer > 1)names
- names of ring variables, may be a string or list/tupleorder
- term order (default: lex)
EXAMPLES:
sage: R.<x, y, z> = BooleanPolynomialRing() sage: R Boolean PolynomialRing in x, y, z
sage: p = x*y + x*z + y*z sage: x*p x*y*z + x*y + x*z
sage: R.term_order() Lexicographic term order
sage: R = BooleanPolynomialRing(5,'x',order='deglex(3),deglex(2)') sage: R.term_order() Block term order with blocks: (Degree lexicographic term order of length 3, Degree lexicographic term order of length 2)
sage: R = BooleanPolynomialRing(3,'x',order='deglex') sage: 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 tonames
, and term ordering given byorder
.When
base_ring
is not specified, this function returns aBooleanPolynomialRing
isomorphic toself
. Otherwise, this returns aMPolynomialRing
. Each argument above is optional.INPUT:
base_ring
– a base ringnames
– variable namesorder
– a term order
EXAMPLES:
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
-
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: B.<a,b,c> = BooleanPolynomialRing() sage: B.clone() Boolean PolynomialRing in a, b, c
sage: B.<x,y,z> = BooleanPolynomialRing(3,order='deglex') sage: y*z > x True
Now we call the clone method and generate a compatible, but ‘lex’ ordered, ring:
sage: C = B.clone(ordering=0) sage: C(y*z) > C(x) False
Now we change variable names:
sage: P.<x0,x1> = BooleanPolynomialRing(2) sage: P Boolean PolynomialRing in x0, x1
sage: Q = P.clone(names=['t']) sage: Q Boolean PolynomialRing in t, x1
We can also append blocks to block orderings this way:
sage: R.<x1,x2,x3,x4> = BooleanPolynomialRing(order='deglex(1),deglex(3)') sage: x2 > x3*x4 False
Now we call the internal method and change the blocks:
sage: S = R.clone(blocks=[3]) sage: S(x2) > S(x3*x4) True
Note
This is part of PolyBoRi’s native interface.
-
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: B.<x,y> = BooleanPolynomialRing(2) sage: R = B.cover_ring(); R Multivariate Polynomial Ring in x, y over Finite Field of size 2
sage: B.term_order() == R.term_order() True
The cover ring is cached:
sage: B.cover_ring() is B.cover_ring() True
-
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: 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
-
gen
(i=0)¶ Return the i-th generator of this boolean polynomial ring.
INPUT:
i
- an integer or a boolean monomial in one variable
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.gen() x sage: P.gen(2) z sage: m = x.monomials()[0] sage: P.gen(m) x
-
gens
()¶ Return the tuple of variables in this ring.
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.gens() (x, y, z)
sage: P = BooleanPolynomialRing(10,'x') sage: P.gens() (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9)
-
get_base_order_code
()¶ EXAMPLES:
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
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: 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
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: P.<x,y> = BooleanPolynomialRing(2) sage: P.has_degree_order() False
-
id
()¶ Return a unique identifier for this boolean polynomial ring.
EXAMPLES:
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
-
ideal
(*gens, **kwds)¶ Create an ideal in this ring.
INPUT:
gens
- list or tuple of generatorscoerce
- bool (default: True) automatically coerce the given polynomials to this ring to form the ideal
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.ideal(x+y) Ideal (x + y) of Boolean PolynomialRing in x, y, z
sage: P.ideal(x*y, y*z) Ideal (x*y, y*z) of Boolean PolynomialRing in x, y, z
sage: P.ideal([x+y, z]) Ideal (x + y, z) of Boolean PolynomialRing in x, y, z
-
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 - andones
- evaluating to one -, compute the lexicographically minimal boolean polynomial satisfying these points.INPUT:
zeros
- the set of interpolation points mapped to zeroones
- the set of interpolation points mapped to one
EXAMPLES:
First we create a random-ish boolean polynomial.
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing(6) sage: f = a*b*c*e + a*d*e + a*f + b + c + e + f + 1
Now we find interpolation points mapping to zero and to one.
sage: zeros = set([(1, 0, 1, 0, 0, 0), (1, 0, 0, 0, 1, 0), ....: (0, 0, 1, 1, 1, 1), (1, 0, 1, 1, 1, 1), ....: (0, 0, 0, 0, 1, 0), (0, 1, 1, 1, 1, 0), ....: (1, 1, 0, 0, 0, 1), (1, 1, 0, 1, 0, 1)]) sage: ones = set([(0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 1, 0), ....: (0, 0, 0, 1, 1, 1), (1, 0, 0, 1, 0, 1), ....: (0, 0, 0, 0, 1, 1), (0, 1, 1, 0, 1, 1), ....: (0, 1, 1, 1, 1, 1), (1, 1, 1, 0, 1, 0)]) sage: [f(*p) for p in zeros] [0, 0, 0, 0, 0, 0, 0, 0] sage: [f(*p) for p in ones] [1, 1, 1, 1, 1, 1, 1, 1]
Finally, we find the lexicographically smallest interpolation polynomial using PolyBoRi .
sage: g = B.interpolation_polynomial(zeros, ones); g b*f + c + d*f + d + e*f + e + 1
sage: [g(*p) for p in zeros] [0, 0, 0, 0, 0, 0, 0, 0] sage: [g(*p) for p in ones] [1, 1, 1, 1, 1, 1, 1, 1]
Alternatively, we can work with PolyBoRi’s native
BooleSet
’s. This example is from the PolyBoRi tutorial:sage: B = BooleanPolynomialRing(4,"x0,x1,x2,x3") sage: x = B.gen sage: V=(x(0)+x(1)+x(2)+x(3)+1).set(); V {{x0}, {x1}, {x2}, {x3}, {}} sage: f=x(0)*x(1)+x(1)+x(2)+1 sage: z = f.zeros_in(V); z {{x1}, {x2}} sage: o = V.diff(z); o {{x0}, {x3}, {}} sage: B.interpolation_polynomial(z,o) x1 + x2 + 1
ALGORITHM: Calls
interpolate_smallest_lex
as described in the PolyBoRi tutorial.
-
n_variables
()¶ Return the number of variables in this boolean polynomial ring.
EXAMPLES:
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P.n_variables() 2
sage: P = BooleanPolynomialRing(1000, 'x') sage: 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: P.<x,y> = BooleanPolynomialRing(2) sage: P.ngens() 2
sage: P = BooleanPolynomialRing(1000, 'x') sage: P.ngens() 1000
-
one
()¶ EXAMPLES:
sage: P.<x0,x1> = BooleanPolynomialRing(2) sage: 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 randomvars_set
- list of integer indices of generators of self to use in the generated polynomial
EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.random_element(degree=3, terms=4) x*y*z + x*z + x + y*z
sage: P.random_element(degree=1, terms=2) z + 1
In corner cases this function will return fewer terms by default:
sage: P = BooleanPolynomialRing(2,'y') sage: P.random_element() y0*y1 + y0 sage: P = BooleanPolynomialRing(1,'y') sage: P.random_element() y
We return uniformly random polynomials up to degree 2:
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: B.random_element(terms=Infinity) a*b + a*c + a*d + b*c + b*d + d
-
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: 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
Removing all variables results in the base ring:
sage: 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: 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
-
variable
(i=0)¶ Return the i-th generator of this boolean polynomial ring.
INPUT:
i
- an integer or a boolean monomial in one variable
EXAMPLES:
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
-
zero
()¶ EXAMPLES:
sage: P.<x0,x1> = BooleanPolynomialRing(2) sage: P.zero() 0
-
class
sage.rings.polynomial.pbori.
BooleanPolynomialVector
¶ Bases:
object
A vector of boolean polynomials.
EXAMPLES:
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: from brial import BooleanPolynomialVector sage: l = [B.random_element() for _ in range(3)] sage: v = BooleanPolynomialVector(l) sage: len(v) 3 sage: v[0] a*b + a + b*e + c*d + e*f sage: list(v) [a*b + a + b*e + c*d + e*f, a*d + c*d + d*f + e + f, a*c + a*e + b*c + c*f + f]
-
append
(el)¶ Append the element
el
to this vector.EXAMPLES:
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: from brial import BooleanPolynomialVector sage: v = BooleanPolynomialVector() sage: for i in range(5): ....: v.append(B.random_element()) sage: list(v) [a*b + a + b*e + c*d + e*f, a*d + c*d + d*f + e + f, a*c + a*e + b*c + c*f + f, a*c + a*d + a*e + a*f + b*e, b*c + b*d + c*d + c + 1]
-
-
class
sage.rings.polynomial.pbori.
BooleanPolynomialVectorIterator
¶ Bases:
object
-
next
()¶ x.next() -> the next value, or raise StopIteration
-
Bases:
object
-
class
sage.rings.polynomial.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: from brial 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]
-
-
class
sage.rings.polynomial.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: from brial 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)
Note that nothing happened immediatly but that the generator was indeed added:
sage: list(gbs) [a + b] sage: gbs.symmGB_F2() sage: list(gbs) [a + c, b + c]
-
add_generator
(p)¶ Add a new generator.
INPUT:
p
- a polynomial
EXAMPLES:
sage: from brial 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
-
add_generator_delayed
(p)¶ Add a new generator but do not perform interreduction immediatly.
INPUT:
p
- a polynomial
EXAMPLES:
sage: from brial 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]
-
all_generators
()¶ EXAMPLES:
sage: from brial 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]
-
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: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: from brial 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
Still, we have that:
sage: from brial import groebner_basis sage: groebner_basis(gb) [1]
-
faugere_step_dense
(v)¶ Reduces a vector of polynomials using linear algebra.
INPUT:
v
- a boolean polynomial vector
EXAMPLES:
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: from brial 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 brial 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]
-
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
- a boolean polynomial
EXAMPLES:
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 brial 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
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
- aBooleanMonomial
EXAMPLES:
sage: B.<a,b,c,d,e> = BooleanPolynomialRing() sage: f = B.random_element() sage: g = B.random_element() sage: from brial 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
-
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)¶ Computes, 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: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: from brial 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 brial 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
-
-
class
sage.rings.polynomial.pbori.
MonomialConstruct
¶ Bases:
object
Implements PolyBoRi’s
Monomial()
constructor.
-
class
sage.rings.polynomial.pbori.
MonomialFactory
¶ Bases:
object
Implements PolyBoRi’s
Monomial()
constructor. If a ring is given is can be used as a Monomial factory for the given ring.EXAMPLES:
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: fac = MonomialFactory() sage: fac = MonomialFactory(B)
-
class
sage.rings.polynomial.pbori.
PolynomialConstruct
¶ Bases:
object
Implements PolyBoRi’s
Polynomial()
constructor.-
lead
(x)¶ Return the leading monomial of boolean polynomial
x
, with respect to the order of parent ring.EXAMPLES:
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: PolynomialConstruct().lead(a) a
-
-
class
sage.rings.polynomial.pbori.
PolynomialFactory
¶ Bases:
object
Implements 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: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: PolynomialFactory().lead(a) a
-
-
class
sage.rings.polynomial.pbori.
ReductionStrategy
¶ Bases:
object
Functions and options for boolean polynomial reduction.
-
add_generator
(p)¶ Add the new generator
p
to this strategy.INPUT:
p
- a boolean polynomial.
EXAMPLES:
sage: from brial import * sage: B.<x,y,z> = BooleanPolynomialRing() sage: red = ReductionStrategy(B) sage: red.add_generator(x) sage: list([f.p for f in red]) [x]
-
can_rewrite
(p)¶ Return
True
ifp
can be reduced by the generators of this strategy.EXAMPLES:
sage: from brial 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
-
cheap_reductions
(p)¶ Perform ‘cheap’ reductions on
p
.INPUT:
p
- a boolean polynomial
EXAMPLES:
sage: from brial 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
-
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: from brial 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
-
nf
(p)¶ Compute the normal form of
p
w.r.t. to the generators of this reduction strategy object.EXAMPLES:
sage: from brial 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
-
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: from brial 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
-
-
sage.rings.polynomial.pbori.
TermOrder_from_pb_order
(n, order, blocks)¶
-
class
sage.rings.polynomial.pbori.
VariableBlock
¶ Bases:
object
-
class
sage.rings.polynomial.pbori.
VariableConstruct
¶ Bases:
object
Implements PolyBoRi’s
Variable()
constructor.
-
class
sage.rings.polynomial.pbori.
VariableFactory
¶ Bases:
object
Implements PolyBoRi’s
Variable()
constructor and a variable factory for given ring
-
sage.rings.polynomial.pbori.
add_up_polynomials
(v, init)¶ Add up all entries in the vector
v
.INPUT:
v
- a vector of boolean polynomials
EXAMPLES:
sage: from brial 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()) a*d + b*c + b*d + c + 1 sage: sum(l) a*d + b*c + b*d + c + 1
-
sage.rings.polynomial.pbori.
contained_vars
(m)¶
-
sage.rings.polynomial.pbori.
easy_linear_factors
(p)¶
-
sage.rings.polynomial.pbori.
gauss_on_polys
(inp)¶ Perform Gaussian elimination on the input list of polynomials.
INPUT:
inp
- an iterable
EXAMPLES:
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: from brial import * sage: l = [B.random_element() for _ in range(B.ngens())] sage: A,v = Sequence(l,B).coefficient_matrix() sage: A [1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0] [0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0] [0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0] [0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1] [0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1] sage: e = gauss_on_polys(l) sage: E,v = Sequence(e,B).coefficient_matrix() sage: E [1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0 1] [0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0] [0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0] [0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 1] [0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1] sage: A.echelon_form() [1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0] [0 1 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0 1] [0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0] [0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0] [0 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 1] [0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 1]
-
sage.rings.polynomial.pbori.
get_var_mapping
(ring, other)¶ Return a variable mapping between variables of
other
andring
. When other is a parent object, the mapping defines images for all variables of other. If it is an element, only variables occurring in other are mapped.Raises
NameError
if no such mapping is possible.EXAMPLES:
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: R.<z,y> = QQ[] sage: sage.rings.polynomial.pbori.get_var_mapping(P,R) [z, y] sage: sage.rings.polynomial.pbori.get_var_mapping(P, z^2) [z, None]
sage: R.<z,x> = BooleanPolynomialRing(2) sage: sage.rings.polynomial.pbori.get_var_mapping(P,R) [z, x] sage: sage.rings.polynomial.pbori.get_var_mapping(P, x^2) [None, x]
-
sage.rings.polynomial.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 variablea
- the if branch, aBooleSet
or aBoolePolynomial
b
- the else branch, aBooleSet
or aBoolePolynomial
EXAMPLES:
sage: from brial import if_then_else sage: B = BooleanPolynomialRing(6,'x') sage: x0,x1,x2,x3,x4,x5 = B.gens() sage: f0 = x2*x3+x3 sage: f1 = x4 sage: if_then_else(x1, f0, f1) {{x1,x2,x3}, {x1,x3}, {x4}}
sage: if_then_else(x1.lm().index(),f0,f1) {{x1,x2,x3}, {x1,x3}, {x4}}
sage: if_then_else(x5, f0, f1) Traceback (most recent call last): ... IndexError: index of root must be less than the values of roots of the branches.
-
sage.rings.polynomial.pbori.
interpolate
(zero, one)¶ Interpolate a polynomial evaluating to zero on
zero
and to one onones
.INPUT:
zero
- the set of zeroone
- the set of ones
EXAMPLES:
sage: B = BooleanPolynomialRing(4,"x0,x1,x2,x3") sage: x = B.gen sage: from brial.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
-
sage.rings.polynomial.pbori.
interpolate_smallest_lex
(zero, one)¶ Interpolate the lexicographical smallest polynomial evaluating to zero on
zero
and to one onones
.INPUT:
zero
- the set of zerosone
- 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: B = BooleanPolynomialRing(4,"x0,x1,x2,x3") sage: x = B.gen sage: from brial.interpolate import * sage: V=(x(0)+x(1)+x(2)+x(3)+1).set()
We take V = {e0,e1,e2,e3,0}, where ei describes the i-th unit vector. For our considerations it does not play any role, if we suppose V to be embedded in \(\GF{2}^4\) or a vector space of higher dimension:
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
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: 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
-
sage.rings.polynomial.pbori.
ll_red_nf_noredsb
(p, reductors)¶ Redude the polynomial
p
by the set ofreductors
with linear leading terms.INPUT:
p
- a boolean polynomialreductors
- a boolean set encoding a Groebner basis with linear leading terms.
EXAMPLES:
sage: from brial 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
-
sage.rings.polynomial.pbori.
ll_red_nf_noredsb_single_recursive_call
(p, reductors)¶ Redude the polynomial
p
by the set ofreductors
with linear leading terms.ll_red_nf_noredsb_single_recursive()
call has the same specification asll_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
- a boolean polynomialreductors
- a boolean set encoding a Groebner basis with linear leading terms.
EXAMPLES:
sage: from brial 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
-
sage.rings.polynomial.pbori.
ll_red_nf_redsb
(p, reductors)¶ Redude the polynomial
p
by the set ofreductors
with linear leading terms. It is assumed that the setreductors
is a reduced Groebner basis.INPUT:
p
- a boolean polynomialreductors
- a boolean set encoding a reduced Groebner basis with linear leading terms.
EXAMPLES:
sage: from brial 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
-
sage.rings.polynomial.pbori.
map_every_x_to_x_plus_one
(p)¶ Map every variable
x_i
in this polynomial tox_i + 1
.EXAMPLES:
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*b + z + 1; f a*b + z + 1 sage: from brial 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
-
sage.rings.polynomial.pbori.
mod_mon_set
(a_s, v_s)¶
-
sage.rings.polynomial.pbori.
mod_var_set
(a, v)¶
-
sage.rings.polynomial.pbori.
mult_fact_sim_C
(v, ring)¶
-
sage.rings.polynomial.pbori.
nf3
(s, p, m)¶
-
sage.rings.polynomial.pbori.
parallel_reduce
(inp, strat, average_steps, delay_f)¶
-
sage.rings.polynomial.pbori.
random_set
(variables, length)¶ Return a random set of monomials with
length
elements with each element in the variablesvariables
.EXAMPLES:
sage: from brial 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}}
-
sage.rings.polynomial.pbori.
recursively_insert
(n, ind, m)¶
-
sage.rings.polynomial.pbori.
red_tail
(s, p)¶ Perform tail reduction on
p
using the generators ofs
.INPUT:
s
- a reduction strategyp
- a polynomial
EXAMPLES:
sage: from brial 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
-
sage.rings.polynomial.pbori.
set_random_seed
(seed)¶ The the PolyBoRi random seed to
seed
EXAMPLES:
sage: from brial 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}}
-
sage.rings.polynomial.pbori.
substitute_variables
(parent, vec, poly)¶ var(i)
is replaced byvec[i]
inpoly
.EXAMPLES:
sage: B.<a,b,c> = BooleanPolynomialRing() sage: f = a*b + c + 1 sage: from brial 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
Substitution is also allowed with different rings:
sage: B.<a,b,c> = BooleanPolynomialRing() sage: f = a*b + c + 1 sage: B.<w,x,y,z> = BooleanPolynomialRing(order='deglex') sage: from brial import substitute_variables sage: substitute_variables(B, [x,y,z], f) * w w*x*y + w*z + w
-
sage.rings.polynomial.pbori.
top_index
(s)¶ Return the highest index in the parameter
s
.INPUT:
s
-BooleSet
,BooleMonomial
,BoolePolynomial
EXAMPLES:
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: from brial import top_index sage: top_index(x.lm()) 0 sage: top_index(y*z) 1 sage: top_index(x + 1) 0
-
sage.rings.polynomial.pbori.
unpickle_BooleanPolynomial
(ring, string)¶ Unpickle boolean polynomials
EXAMPLES:
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
-
sage.rings.polynomial.pbori.
unpickle_BooleanPolynomial0
(ring, l)¶ Unpickle boolean polynomials
EXAMPLES:
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
-
sage.rings.polynomial.pbori.
unpickle_BooleanPolynomialRing
(n, names, order)¶ Unpickle boolean polynomial rings.
EXAMPLES:
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
-
sage.rings.polynomial.pbori.
zeros
(pol, s)¶ Return a
BooleSet
encoding on which points froms
the polynomialpol
evaluates to zero.INPUT:
pol
- a boolean polynomials
- a set of points encoded as aBooleSet
EXAMPLES:
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: f = a*b + a*c + d + b
Now we create a set of points:
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}}
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: from brial import zeros sage: zeros(f,s) {{a,b}}
For comparison we work with tuples:
sage: f.zeros_in([(1,1,1,0), (1,1,0,0), (0,0,1,1), (0,1,1,0)]) ((1, 1, 0, 0),)