Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Boolean Polynomials
Elements of the quotient ring
.. MATH::
\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." - [BD07]_
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 :class:`BooleanMonomialMonoid` (via :class:`~sage.structure.unique_representation.UniqueRepresentation`) and :class:`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
.. MATH::
<ab + cd + 1, ace + de, abe + ce, bc + cde + 1>.
First, we compute the lexicographical Groebner basis in the polynomial ring
.. MATH::
R = \GF{2}[a,b,c,d,e].
::
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 `\mathbb{F}[x_1, ..., x_n]` then the ideals in the quotient ring `\mathbb{F}[x_1, ..., x_n]/I` are in one-to-one correspondence with the ideals of `\mathbb{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:
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.
REFERENCES:
.. [BD07] Michael Brickenstein, Alexander Dreyer\; *PolyBoRi: A Groebner basis framework for Boolean polynomials*; pre-print available at http://www.itwm.fraunhofer.de/fileadmin/ITWM-Media/Zentral/Pdf/Berichte_ITWM/2007/bericht122.pdf """ from __future__ import print_function, absolute_import
from cpython.object cimport Py_EQ, Py_NE from cython.operator cimport dereference as deref from cysignals.memory cimport sig_malloc, sig_free from cysignals.signals cimport sig_on, sig_off from sage.ext.cplusplus cimport ccrepr
import operator
from sage.cpython.string cimport str_to_bytes
from sage.misc.cachefunc import cached_method
from sage.misc.randstate import current_randstate from sage.arith.long cimport pyobject_to_long import sage.misc.weak_dict from sage.rings.integer import Integer from sage.rings.finite_rings.finite_field_constructor import FiniteField as GF
from sage.rings.polynomial.polynomial_element cimport Polynomial from sage.rings.polynomial.multi_polynomial_ideal import MPolynomialIdeal from sage.rings.polynomial.term_order import TermOrder from sage.rings.polynomial.polynomial_ring import PolynomialRing_general
from sage.rings.ideal import FieldIdeal
from sage.structure.element cimport (Element, RingElement, have_same_parent, coercion_model)
from sage.structure.parent cimport Parent from sage.structure.sequence import Sequence from sage.structure.element import coerce_binop from sage.structure.unique_representation import UniqueRepresentation from sage.structure.richcmp cimport richcmp, richcmp_not_equal
from sage.categories.action cimport Action
from sage.monoids.monoid import Monoid_class
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing from sage.interfaces.all import singular as singular_default from sage.interfaces.singular import SingularElement
order_dict= {"lp": pblp, "dlex": pbdlex, "dp_asc": pbdp_asc, "dp": pbdp, "block_dlex": pbblock_dlex, "block_dp_asc": pbblock_dp_asc, "block_dp": pbblock_dp, }
inv_order_dict= {pblp: "lex", pbdlex: "deglex", pbdp_asc: "degneglex", pbdp: "degrevlex", }
order_mapping = {'lp': pblp, 'lex': pblp, 'Dp': pbdlex, 'deglex': pbdlex, 'dlex': pbdlex, 'dp_asc': pbdp_asc, 'degneglex': pbdp_asc, 'dp': pbdp, 'degrevlex': pbdp, }
lp = int(pblp) dlex = int(pbdlex) dp = int(pbdp) dp_asc = int(pbdp_asc) block_dlex = int(pbblock_dlex) block_dp_asc = int(pbblock_dp_asc)
rings = sage.misc.weak_dict.WeakValueDictionary()
cdef class BooleanPolynomialRing(MPolynomialRing_generic): """ 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/tuple
- ``order`` - term order (default: lex)
EXAMPLES::
sage: R.<x, y, z> = BooleanPolynomialRing() sage: R Boolean PolynomialRing in x, y, z
::
sage: p = x*y + x*z + y*z sage: x*p x*y*z + x*y + x*z
::
sage: R.term_order() Lexicographic term order
::
sage: R = BooleanPolynomialRing(5,'x',order='deglex(3),deglex(2)') sage: R.term_order() 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
TESTS::
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4,order='deglex(2),deglex(2)') sage: x0 > x1 True sage: x2 > x3 True sage: TestSuite(P).run()
Boolean polynomial rings are unique parent structures. We thus have::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: R.<x,y> = BooleanPolynomialRing(2) sage: P is R True
::
sage: Q.<x,z> = BooleanPolynomialRing(2) sage: P == Q False
::
sage: S.<x,y> = BooleanPolynomialRing(2, order='deglex') sage: P == S False
""" def __init__(self, n=None, names=None, order='lex'): """ Create a new boolean polynomial ring.
EXAMPLES::
sage: R.<x, y, z> = BooleanPolynomialRing() sage: R Boolean PolynomialRing in x, y, z
.. NOTE::
See class documentation for parameters. """ cdef Py_ssize_t i, j, bstart, bsize
raise TypeError("You must specify the names of the variables.")
except TypeError as msg: raise TypeError("Number of variables must be an integer")
raise ValueError("Number of variables must be greater than 1.")
except KeyError: raise ValueError("Only order keys " + ', '.join(order_mapping.keys()) + " are supported.")
from sage.misc.superseded import deprecation deprecation(13849, "using 'degrevlex' in Boolean polynomial rings is deprecated. If needed, reverse the order of variables manually and use 'degneglex'")
raise ValueError("Only deglex and degneglex are supported for block orders.") elif pb_order_code is pbdp_asc: pb_order_code = pbblock_dp_asc elif pb_order_code is pbdp: pb_order_code = pbblock_dp raise ValueError("Each block must have the same order type " "(deglex and degneglex) for block orders.")
for i from 0 <= i < n: self.pbind[i] = n - i -1 pb_order_code = pbdp_asc bstart = 0 for i from 0 <= i < len(order.blocks()): bsize = len(order[i]) for j from 0 <= j < bsize: self.pbind[bstart + j] = bstart + bsize - j -1 bstart += bsize pb_order_code = pbblock_dp_asc else: # native PolyBoRi ordering
else:
PBBoolePolynomial(0, self._pbring) PBBoolePolynomial(1, self._pbring)
def __dealloc__(self):
def __reduce__(self): """ EXAMPLES::
sage: P.<a,b> = BooleanPolynomialRing(2) sage: loads(dumps(P)) == P # indirect doctest True """
def ngens(self): """ 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 """
def gen(self, 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
TESTS::
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: P.gen(0) x """ else: raise TypeError("Boolean monomials must be in one variable only.") raise ValueError("Generator not defined.")
def gens(self): """ 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)
"""
def change_ring(self, 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: 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 """
else:
def _repr_(self): """ EXAMPLES::
sage: P.<x, y> = BooleanPolynomialRing(2) sage: P # indirect doctest Boolean PolynomialRing in x, y """ # we use this function when we throw exceptions, thus we want # it to be fast.
# Coercion cpdef _coerce_map_from_(self,S): """ There is coercion from the base ring, from any boolean polynomial ring with compatible variable names, any boolean monomial monoid with compatible variable names, and any polynomial ring with compatible variable names and base ring.
Before :trac:`9138`, boolean polynomial rings had a custom containment test, but that is not needed now since it now uses Sage's new coercion model. So, we move the tests from the old ``__contains__`` to here.
TESTS::
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: a in B True
Any boolean monomial is contained in the ring::
sage: e = B.random_element(); e a*b + a*c + a + b*d + 1 sage: e.lt() a*b sage: e.lt().parent() MonomialMonoid of Boolean PolynomialRing in a, b, c, d sage: e.lt() in B # indirect doctest True
Note that all integers are considered to be in the boolean polynomial ring::
sage: 0 in B True sage: 1 in B True sage: 7 in B True sage: 7 in GF(2) True
We test that :trac:`10173` is fixed::
sage: R = BooleanPolynomialRing(256,'x') sage: S = PolynomialRing(GF(2),256,'y') sage: S.gen(8) in R False
Of course, coercion is also responsible for arithmetics involving different rings. There is coercion from uni- and multivariate polynomial rings whose base rings coerce into ``GF(2)``::
sage: ZZ['a','b'].gen() + c a + c sage: ZZ['a'].gen() + c a + c
Check that :trac:`13284` is fixed::
sage: from sage.rings.ideal import Cyclic sage: R = BooleanPolynomialRing(10, 'x') sage: I = Cyclic(R) sage: len(I.groebner_basis()) 10 """
cdef _convert(self, other): r""" Canonical conversion of elements from other domains to this boolean polynomial ring.
EXAMPLES:
Convert elements of ``self``.
::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: p = x*y + x sage: P(p) x*y + x
Convert from monomials over the same ring.
::
sage: P(p.lm()) # indirect doctest x*y
Convert from a different BooleanPolynomialRing.
::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: R = BooleanPolynomialRing(2,'y,x') sage: p = R(x+y+x*y+1) sage: p.parent() Boolean PolynomialRing in y, x sage: p y*x + y + x + 1
Convert from polynomials over the integers.
::
sage: P = BooleanPolynomialRing(3,'x,y,z') sage: R.<z,x,y> = ZZ['z,x,y'] sage: t = x^2*z+5*y^3 sage: p = P(t) sage: p.parent() Boolean PolynomialRing in x, y, z sage: p x*z + y
Convert from integers.
::
sage: P = BooleanPolynomialRing(3,'x,y,z') sage: p = P(1) sage: p.is_one() True sage: p = P(6) sage: p.is_zero() True
Conversion from GF(2).
::
sage: P = BooleanPolynomialRing(3,'x,y,z') sage: F = GF(2) sage: p = P(F.zero()) sage: p.is_zero() True sage: p = P(F.one()) sage: p.is_one() True
Conversion from boolean monomials over a different boolean polynomial ring.
::
sage: R.<y,x> = BooleanPolynomialRing(2) sage: M = R._monom_monoid sage: P = BooleanPolynomialRing(3,'x,y,z') sage: t = P(M(x*y)) sage: t x*y sage: t.parent() Boolean PolynomialRing in x, y, z
TESTS::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: R = BooleanPolynomialRing(1,'y') sage: p = R(x+y+x*y+1) Traceback (most recent call last): ... TypeError: cannot convert polynomial x*y + x + y + 1 to Boolean PolynomialRing in y: name x not defined
::
sage: P = BooleanPolynomialRing(2,'x,y') sage: R.<z,x,y> = ZZ['z,x,y'] sage: t = x^2*z+5*y^3 sage: p = P(t) Traceback (most recent call last): ... TypeError: cannot convert polynomial z*x^2 + 5*y^3 to Boolean PolynomialRing in x, y: name z not defined
Test conversion from a ring that compares equal.
::
sage: P = BooleanPolynomialRing(2,'x,y') sage: R.<x,y> = BooleanPolynomialRing(2) sage: P == R True sage: P(x) x
Test that :trac:`10797` is really fixed::
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: I = ideal(a*b + a + b*e + c*e + 1, a + b + c*d + c + 1, a*c + c + d*f + d + 1, a*c + c*f + c + d*f + 1, c*f + c + d + e + 1, a + b*c + b*d + e*f + 1) sage: I.groebner_basis() [1] """ cdef BooleanPolynomial p # we check for other PolyBoRi types first since this conversion # is used by the PolyBoRi python code often
else: except NameError as msg: raise TypeError("cannot coerce monomial %s to %s: %s" % (other, self, msg)) else: raise TypeError("cannot coerce monomial %s to %s" % (other, self))
((<BooleanPolynomialRing>(<BooleanPolynomial>other)\ # try PolyBoRi's built-in coercions (<BooleanPolynomialRing>(<BooleanPolynomial>other)._parent)._pbring.hash(): except NameError as msg: raise TypeError("cannot coerce polynomial %s to %s: %s" % (other, self, msg))
else: else:
def _element_constructor_(self, other): """ Convert ``other`` to this Boolean polynomial ring.
EXAMPLES::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P(5) # indirect doctest 1
sage: P(x+y) x + y
sage: P.<x,y> = BooleanPolynomialRing(2) sage: R = BooleanPolynomialRing(1,'y') sage: p = R(y); p y sage: p.parent() Boolean PolynomialRing in y
sage: P = BooleanPolynomialRing(2,'x,y') sage: R.<z,x,y> = ZZ['z,x,y'] sage: t = x^2*y + 5*y^3 sage: p = P(t); p x*y + y sage: p.parent() Boolean PolynomialRing in x, y
TESTS::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: R = BooleanPolynomialRing(1,'y') sage: p = R(x+y+x*y+1) Traceback (most recent call last): ... TypeError: cannot convert polynomial x*y + x + y + 1 to Boolean PolynomialRing in y: name x not defined
sage: P = BooleanPolynomialRing(2,'x,y') sage: R.<z,x,y> = ZZ[] sage: t = x^2*z+5*y^3 sage: p = P(t) Traceback (most recent call last): ... TypeError: cannot convert polynomial z*x^2 + 5*y^3 to Boolean PolynomialRing in x, y: name z not defined
We test that univariate polynomials convert into the boolean polynomial ring (:trac:`9138`)::
sage: R.<x> = ZZ[] sage: p = x^3+2*x^2+x+1 sage: P(p) x """ cdef int i
pass
(<BooleanMonomial>other)._pbmonom.deg() <= <Py_ssize_t>self._pbring.nVariables()): try: var_mapping = get_var_mapping(self, other) except NameError as msg: raise TypeError("cannot convert monomial %s to %s: %s" % (other, self, msg)) p = self._one_element for i in other.iterindex(): p *= var_mapping[i] return p self._pbring.nVariables()): except NameError as msg: raise TypeError("cannot convert polynomial %s to %s: %s" % (other, self, msg)) # we have a univariate polynomial. # That case had only been implemented # in trac ticket #9138:
i = i % 2 if i == 1: return self._one_element else: return self._zero_element
def __hash__(self): """ Return a hash of this boolean polynomial ring.
EXAMPLES::
sage: P.<a,b,c,d> = BooleanPolynomialRing(4, order='lex') sage: P Boolean PolynomialRing in a, b, c, d sage: {P:1} # indirect doctest {Boolean PolynomialRing in a, b, c, d: 1} """
def remove_var(self, *var, order=None): """ 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
""" else:
def ideal(self, *gens, **kwds): """ Create an ideal in this ring.
INPUT:
- ``gens`` - list or tuple of generators
- ``coerce`` - 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 """
def random_element(self, 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: 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
TESTS::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P.random_element(degree=4) Traceback (most recent call last): ... ValueError: Given degree should be less than or equal to number of variables (3)
sage: P.random_element(degree=1, terms=5) y + 1
sage: P.random_element(degree=2, terms=5, vars_set=(0,1)) x*y + y
We test that :trac:`13845` is fixed::
sage: n = 10 sage: B = BooleanPolynomialRing(n, 'x') sage: r = B.random_element(terms=(n/2)**2) """
else: else:
else:
def _random_uniform_rec(self, degree, monom_counts, vars_set, dfirst, l): r""" Recursively generate a random polynomial in this ring, using the variables from ``vars_set``.
INPUT:
- ``degree`` - maximum degree
- ``monom_counts`` - a list containing total number of monomials up to given degree
- ``vars_set`` - list of variable indices to use in the generated polynomial
- ``dfirst`` - if ``True`` choose degree first, otherwise choose the monomial uniformly
- ``l`` - number of monomials to generate
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: P._random_uniform_rec(2, [1, 3, 4], (0,1), True, 2) x + y sage: P._random_uniform_rec(2, [1, 3, 4], (0,1), True, 2) 0 """ return self._zero_element else:
def _random_monomial_uniform(self, monom_counts, vars_set): r""" Choose a random monomial uniformly from set of monomials in the variables indexed by ``vars_set`` in self.
INPUT:
- ``monom_counts`` - list of number of monomials up to given degree
- ``vars_set`` - list of variable indices to use in the generated monomial
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: [P._random_monomial_uniform([1, 3, 4], (0,1)) for _ in range(10)] [x*y, x*y, x, x, x, x*y, x, y, x*y, 1] """
def _random_monomial_dfirst(self, degree, vars_set): r""" Choose a random monomial using variables indexed in ``vars_set`` up to given ``degree``. The degree of the monomial, `d`, is chosen uniformly in the interval [0,degree] first, then the monomial is generated by selecting a random sample of size `d` from ``vars_set``.
INPUT:
- ``degree`` - maximum degree
- ``vars_set`` - list of variable indices of self
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: [P._random_monomial_dfirst(3, (0,1,2)) for _ in range(10)] [x*y*z, x*y*z, x*y*z, y*z, x*z, z, z, y*z, x*y*z, 1] """
def cover_ring(self): r""" 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 """
def defining_ideal(self): """ 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 """
def _singular_init_(self, singular=singular_default): r""" Return a newly created Singular quotient ring matching this boolean polynomial ring.
.. NOTE::
TODO: This method does not only return a string but actually calls Singular.
EXAMPLES::
sage: B.<x,y> = BooleanPolynomialRing(2) sage: B._singular_() # indirect doctest polynomial ring, over a field, global ordering // coefficients: ZZ/2 // number of vars : 2 // block 1 : ordering lp // : names x y // block 2 : ordering C // quotient ring from ideal _[1]=x2+x _[2]=y2+y """
def _magma_init_(self, magma): """ Return a string which when evaluated with Magma returns a Magma representation of this boolean polynomial ring.
INPUT:
- ``magma`` - a magma instance
EXAMPLES::
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: magma(B) # indirect doctest; optional - magma Boolean polynomial ring of rank 3 over GF(2) Order: Lexicographical (bit vector word) Variables: x, y, z """ #R = magma(self.cover_ring()) #v = [z.name() for z in R.gens()] # important to use this because it caches the generators #w = [f._repr_with_changed_varnames(v) for f in self.defining_ideal().gens()] #return "quo<%s | %s>"%(R.name(), ",".join(w)) s = 'BooleanPolynomialRing(%s,%s)'%(self.ngens(), self.term_order().magma_str()) return magma._with_names(s, self.variable_names())
def interpolation_polynomial(self, zeros, ones): r""" 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: 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. """ #from brial.interpolate import interpolate_smallest_lex else: else:
### # # Methods for compatibility with PolyBoRi # ###
def id(self): """ 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 """
def variable(self, 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
TESTS::
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: P.variable(0) x """ else: raise TypeError("Boolean monomials must be in one variable only.") raise ValueError("Generator not defined.")
def get_order_code(self): """
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. """
def get_base_order_code(self): """
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. """
def has_degree_order(self): """ Return checks whether the order code corresponds to a degree ordering.
EXAMPLES::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: P.has_degree_order() False """
def _settings(self, names, blocks): for (idx, elt) in enumerate(names): self._pbring.setVariableName(self.pbind[idx], elt)
for elt in blocks: self._pbring.ordering().appendBlock(elt)
def one(self): """ EXAMPLES::
sage: P.<x0,x1> = BooleanPolynomialRing(2) sage: P.one() 1 """
def zero(self): """ EXAMPLES::
sage: P.<x0,x1> = BooleanPolynomialRing(2) sage: P.zero() 0 """
def clone(self, 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. """
def n_variables(self): """ 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. """
def get_var_mapping(ring, other): r""" Return a variable mapping between variables of ``other`` and ``ring``. When other is a parent object, the mapping defines images for all variables of other. If it is an element, only variables occurring in other are mapped.
Raises ``NameError`` if no such mapping is possible.
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: R.<z,y> = QQ[] sage: sage.rings.polynomial.pbori.get_var_mapping(P,R) [z, y] sage: sage.rings.polynomial.pbori.get_var_mapping(P, z^2) [z, None]
::
sage: R.<z,x> = BooleanPolynomialRing(2) sage: sage.rings.polynomial.pbori.get_var_mapping(P,R) [z, x] sage: sage.rings.polynomial.pbori.get_var_mapping(P, x^2) [None, x] """ else: else:
# variable name not found in list of our variables # raise an exception and bail out
class BooleanMonomialMonoid(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: 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:`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()
""" def __init__(self, BooleanPolynomialRing polring): """ Create a new boolean polynomial ring.
TESTS::
sage: from brial import BooleanMonomialMonoid sage: B.<a,b,c> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(B) sage: M MonomialMonoid of Boolean PolynomialRing in a, b, c
.. NOTE::
See class documentation for parameters. """ cdef BooleanMonomial m
def _repr_(self): """ EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y> = BooleanPolynomialRing(2) sage: M = BooleanMonomialMonoid(P) sage: M # indirect doctest MonomialMonoid of Boolean PolynomialRing in x, y """
def __hash__(self): """ Return a hash for this monoid.
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y> = BooleanPolynomialRing(2) sage: M = BooleanMonomialMonoid(P) sage: {M:1} # indirect doctest {MonomialMonoid of Boolean PolynomialRing in x, y: 1} """
def ngens(self): """ 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 """
def gen(self, Py_ssize_t 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 """ raise ValueError("Generator not defined.")
cdef PBVar newvar
def gens(self): """ 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) """
def _get_action_(self, S, op, bint self_on_left): """ Monomials support multiplication by 0 and 1 in GF(2).
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: M.get_action(ZZ) # indirect doctest Right action by Integer Ring on MonomialMonoid of Boolean PolynomialRing in x, y, z sage: M.get_action(GF(2)) Right action by Finite Field of size 2 on MonomialMonoid of Boolean PolynomialRing in x, y, z sage: M.get_action(QQ) is None True """
def _coerce_impl(self, other): """ Canonical conversion of elements from other objects to this monoid.
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x_monom = M(x); x_monom x sage: M(x_monom) # indirect doctest x
Convert elements from :class:`BooleanMonomialMonoid` where the generators of self include the generators of the other monoid::
sage: from brial import BooleanMonomialMonoid sage: R.<z,y> = BooleanPolynomialRing(2) sage: N = BooleanMonomialMonoid(R) sage: m = M(N(y*z)); m y*z sage: m.parent() is M True
TESTS::
sage: from brial import BooleanMonomialMonoid sage: R.<t,y> = BooleanPolynomialRing(2) sage: N = BooleanMonomialMonoid(R) sage: m = M(N(y)); m Traceback (most recent call last): ... TypeError: list indices must be integers, not sage.rings.polynomial.pbori.BooleanMonomial
sage: from brial import BooleanMonomialMonoid sage: R.<t,x,y,z> = BooleanPolynomialRing(4) sage: N = BooleanMonomialMonoid(R) sage: m = M(N(x*y*z)); m Traceback (most recent call last): ... TypeError: list indices must be integers, not sage.rings.polynomial.pbori.BooleanMonomial """
def _element_constructor_(self, other=None): """ Convert elements of other objects to elements of this monoid.
INPUT:
- ``other`` - element to convert, if ``None`` a :class:`BooleanMonomial` representing 1 is returned only :class:`BooleanPolynomial`s with the same parent ring as ``self`` which have a single monomial is converted
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x_monom = M(x); x_monom x
sage: M(x*y) x*y
sage: M(x+y) Traceback (most recent call last): ... TypeError: cannot convert to BooleanMonomialMonoid
Convert elements of self::
sage: M(x_monom) x
Convert from other :class:`BooleanPolynomialRing`s::
sage: R.<z,x> = BooleanPolynomialRing(2) sage: t = M(z); t z sage: t.parent() is M True
Convert :class:`BooleanMonomial`s over other :class:`BooleanPolynomialRing`s::
sage: N = BooleanMonomialMonoid(R) sage: t = M(N(x*z)); t x*z sage: t.parent() is M True
Convert :class:`BooleSet`s::
sage: t = M.an_element(); t x sage: M(t.set()) == t True
Convert a tuple of integers::
sage: M((0,2,0)) x*z
""" cdef BooleanMonomial m cdef PBMonom t
# this is needed for the PolyBoRi python code return self._one_element
# We must not call this explicitly in an element constructor. # It used to be ok, when there was a custom __call__ # try: # return self._coerce_(other) # except ValueError: # pass # except TypeError: # pass
pass
(<BooleanPolynomial>other)._pbpoly.lead()) except NameError as msg: raise ValueError("cannot convert polynomial %s to %s: %s" % (other, self, msg))
else: raise ValueError("cannot convert polynomial %s to %s" % (other, self))
except NameError as msg: raise ValueError("cannot convert monomial %s to %s: %s" % (other, self, msg)) return m self.base_ring()(other).is_one(): return self._one_element
result = self._one_element for elt in other: result = result * elt return result # S.K.: Tuples of integers have not been converted # into monomials before. I think that would be very # natural (namely the integers providing the index # of generators). It is also useful for pickling.
cdef class BooleanMonomial(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 :meth:`BooleanMonomialMonoid__call__` method and not this constructor to construct these objects. """ def __init__(self, parent): """ EXAMPLES::
sage: from brial import BooleanMonomialMonoid, BooleanMonomial sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: BooleanMonomial(M) 1
.. NOTE::
See class documentation for parameters. """
def __reduce__(self): """ Pickling
TESTS::
sage: from brial import BooleanMonomialMonoid sage: R.<z,x> = BooleanPolynomialRing(2) sage: M = BooleanMonomialMonoid(R) sage: t = M.0*M.1 sage: loads(dumps(t)) == t # indirect doctest True """
cpdef int _cmp_(left, right) except -2: """ Compare BooleanMonomial objects.
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: M(x) < M(y) False
sage: M(x) > M(y) True
sage: M(x) == M(x) True
sage: M(x) <= M(x) True
sage: M(x) >= M(x) True """ cdef int res
def _repr_(self): """ Return a string representing this boolean monomial.
EXAMPLES::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: M = sage.rings.polynomial.pbori.BooleanMonomialMonoid(P) sage: M(x*y) # indirect doctest x*y
sage: R.<t,u> = BooleanPolynomialRing(2) sage: M(x*y) x*y """
def _eval(self, d): """ Evaluate this monomial.
INPUT:
- ``d`` -- dictionary with integer indices
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: m = P._monom_monoid(x*y) sage: m._eval({0:y,1:z}) y*z """ else:
def __call__(self, *args, **kwds): """ Evaluate this monomial.
EXAMPLES::
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: m(B(0),B(1)) 0 sage: m(x=B(1)) y """ raise ValueError("Using keywords and regular arguments not supported.") raise ValueError("Number of arguments is greater than the number of variables of parent ring.")
def __hash__(self): """ Return a hash of this monomial.
EXAMPLES::
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y sage: m = f.lm() sage: {m:1} #indirect doctest {x*y: 1} """
def stable_hash(self): """ A hash value which is stable across processes.
EXAMPLES::
sage: B.<x,y> = BooleanPolynomialRing() sage: m = x.lm() sage: m.stable_hash() -845955105 # 32-bit 173100285919 # 64-bit
.. NOTE::
This function is part of the upstream PolyBoRi interface. In Sage all hashes are stable. """
def ring(self): """ Return the corresponding boolean ring.
EXAMPLES::
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: a.lm().ring() is B True """
def index(self): """ 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
TESTS:
Check that :trac:`13133` is resolved::
sage: B(1).lm().index() Traceback (most recent call last): ... ValueError: no variables in constant monomial ; cannot take index()
.. NOTE::
This function is part of the upstream PolyBoRi interface. """
def deg(BooleanMonomial self): """ 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. """
def degree(BooleanMonomial self, BooleanPolynomial 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: 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 """
raise ValueError("x must be one of the generators of the parent.")
else:
def divisors(self): """ 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}, {}} """
def multiples(self, BooleanMonomial 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 bound ``rhs`` is smaller than ``self``. """
def reducible_by(self, BooleanMonomial rhs): """ Return ``True`` if ``self`` is reducible by ``rhs``.
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 """
def set(self): """ 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}} """
def __len__(BooleanMonomial self): """ Return 1.
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: len(M(x*y)) 1 """
def __iter__(self): """ Return an iterator over the variables in this monomial.
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: list(M(x*z)) # indirect doctest [x, z] """
def variables(self): """ 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) """
def iterindex(self): """ 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] """
cpdef _mul_(left, right): """ Multiply this boolean monomial with another boolean monomial.
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x = M(x); xy = M(x*y); z=M(z) sage: x*x # indirect doctest x
sage: xy*y x*y
sage: xy*z x*y*z """ (<BooleanMonomial>left)._pbmonom)
def __add__(left, right): """ Addition operator. Return a boolean polynomial.
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x = M(x); xy = M(x*y) sage: x + xy x*y + x
sage: x+0 x sage: 0+x # todo: not implemented x
sage: x+1 x + 1 sage: 1 + x # todo: not implemented x + 1 """ # Using canonical coercion is not possible for this case. # The coercion model cannot find the common parent # BooleanPolynomialRing for argument types BooleanMonomial and Integer. # This is a common case we should handle as in the examples above. # Since we know the result will be a BooleanPolynomial, we let # BooleanPolynomial handle the coercion. cdef BooleanPolynomial res cdef BooleanMonomial monom else: raise TypeError("BooleanMonomial.__add__ called with not supported types %s and %s" % (type(right), type(left)))
def __floordiv__(BooleanMonomial left, right): """ Floordiv operator.
EXAMPLES::
sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x = M(x); xy = M(x*y) sage: xy//x y sage: x//xy 0
sage: x//0 Traceback (most recent call last): ... ZeroDivisionError
sage: x//1 x """ cdef BooleanMonomial other cdef BooleanMonomial m
other = left._parent(right) else:
(<BooleanMonomial>left)._pbmonom) else:
def navigation(self): """ 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 """
@coerce_binop def gcd(self, BooleanMonomial 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 """
### # # Various internal constructors for boolean polynomials from various # other formats. # ###
cdef inline BooleanMonomial new_BM(parent, BooleanPolynomialRing ring): cdef BooleanMonomial m
cdef inline BooleanMonomial new_BM_from_PBMonom(parent, BooleanPolynomialRing ring, PBMonom juice):
cdef inline BooleanMonomial new_BM_from_PBVar(parent, BooleanPolynomialRing ring, PBVar juice):
cdef class BooleanMonomialVariableIterator: def __iter__(self): """ Return an iterator over the variables of a boolean monomial.
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: for m in f: list(m)# indirect doctest [x, y] [z] [] """ return self
def __next__(self): """ EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: m = f.lm() sage: next(iter(m)) x """ cdef PBVar value
cdef inline BooleanMonomialVariableIterator new_BMVI_from_BooleanMonomial( BooleanMonomial monom): """ Construct a new iterator over the variable indices of a boolean monomial. """ cdef BooleanMonomialVariableIterator m
cdef class BooleanMonomialIterator: """ An iterator over the variable indices of a monomial. """ def __iter__(self): """ EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: for m in f: list(m.iterindex())# indirect doctest [0, 1] [2] [] """
def __next__(self): """ EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: m = f.lm() sage: next(m.iterindex()) 0 """ cdef int value
cdef inline BooleanMonomialIterator new_BMI_from_BooleanMonomial(BooleanMonomial monom): """ Construct a new BooleanMonomialIterator """ cdef BooleanMonomialIterator m
cdef class BooleanPolynomial(MPolynomial): """ Construct a boolean polynomial object in the given boolean polynomial ring.
INPUT:
- ``parent`` - a boolean polynomial ring
TESTS::
sage: from brial import BooleanPolynomial sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: BooleanPolynomial(B) 0
.. NOTE::
Do not use this method to construct boolean polynomials, but use the appropriate ``__call__`` method in the parent. """ def __init__(self, parent):
def _repr_(self): """ EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: repr(a+b+z^2+1) # indirect doctest 'a + b + z + 1' """
def _repr_with_changed_varnames(self, varnames): r""" Return string representing this boolean polynomial but change the variable names to ``varnames``.
EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: a._repr_with_changed_varnames(['x','y','z']) 'x'
TESTS::
sage: a._repr_with_changed_varnames([1,'y','z']) Traceback (most recent call last): ... TypeError: varnames has entries with wrong type.
::
sage: a a """ cdef int i
raise TypeError("len(varnames) doesn't equal self.parent().ngens()")
def _latex_(self): r""" Return a LaTeX representation of this boolean polynomial.
EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: latex(a+b+a*z^2+1) # indirect doctest a z + a + b + 1 """
cpdef _add_(left, right): """ EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*z + b + 1 sage: g = b + z sage: f + g # indirect doctest a*z + z + 1 """
cpdef _sub_(left, right): """ EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*z + b + 1 sage: g = b + z sage: f - g # indirect doctest a*z + z + 1 """
cpdef _lmul_(self, Element left): """ EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: k = B.base_ring() sage: f = a*z + b + 1 sage: f*k(1) # indirect doctest a*z + b + 1
::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: k = B.base_ring() sage: f = a*z + b + 1 sage: k(0)*f # indirect doctest 0 """ else:
cpdef _mul_(left, right): """ EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*z + b + 1 sage: g = b + z sage: f * g # indirect doctest a*b*z + a*z + b*z + z """
cpdef _div_(left, right): """ EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*z + b + 1 sage: f / a z sage: f = z + b + 1 sage: f / a 0 """
def is_equal(self, BooleanPolynomial 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. """
cpdef _richcmp_(left, right, int op): """ Compare left and right.
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: x < x+y True
sage: y*z < x True
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: y*z < x False sage: P(True) == True True sage: P(0) == 0 True
TESTS::
sage: P.<x> = BooleanPolynomialRing() sage: P(True) == True True sage: P.zero() == True False sage: P(0) != True True sage: P(False) == False True sage: P() != False False sage: x == True False sage: x != True True sage: x == False False sage: x != False True """
def __iter__(self): r""" Return an iterator over the monomials of ``self``, in the order of the parent ring.
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: p = x + z + x*y + y*z + x*y*z sage: list(iter(p)) [x*y*z, x*y, x, y*z, z]
::
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: p = x + z + x*y + y*z + x*y*z sage: list(iter(p)) [x*y*z, x*y, y*z, x, z]
::
sage: P.<x,y,z> = BooleanPolynomialRing(3, order='deglex') sage: p = x + z + x*y + y*z + x*y*z sage: list(iter(p)) [x*y*z, x*y, y*z, x, z]
TESTS::
sage: R = BooleanPolynomialRing(1,'y') sage: list(iter(y)) [y] sage: R Boolean PolynomialRing in y """
def __pow__(BooleanPolynomial self, int exp, ignored): r""" Return ``self^(exp)``.
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: p = x + y sage: p^0 1
::
sage: p^1 x + y
::
sage: p^5 x + y
::
sage: p^-1 Traceback (most recent call last): ... NotImplementedError: Negative exponents for non constant boolean polynomials not implemented.
::
sage: z = P(0) sage: z^0 1
::
sage: z^1 0 """ return self raise ZeroDivisionError else:
def __neg__(BooleanPolynomial self): r""" Return -``self``.
EXAMPLES::
sage: B.<a,b,z> = BooleanPolynomialRing(3) sage: f = a*z + b + 1 sage: -f a*z + b + 1 """
def total_degree(BooleanPolynomial self): r""" 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 """
def degree(self, BooleanPolynomial x=None): r""" 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: 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 """ return 0 else:
def lm(BooleanPolynomial self): r""" 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 """
def lt(BooleanPolynomial self): """ 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 """
def is_singleton(BooleanPolynomial self): r""" 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
"""
def is_singleton_or_pair(BooleanPolynomial self): r""" 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
"""
def is_pair(BooleanPolynomial self): r""" 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
""" return self._pbpoly.isPair()
def is_zero(BooleanPolynomial self): r""" 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 """
def __nonzero__(self): r""" Check if ``self`` is zero.
EXAMPLES::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: bool(P(0)) False
::
sage: bool(x) True
::
sage: bool(P(1)) True """
def is_one(BooleanPolynomial self): """ 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 """
def is_unit(BooleanPolynomial self): r""" 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 """
def is_constant(BooleanPolynomial self): r""" 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 """
def lead_deg(BooleanPolynomial self): r""" 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. """
def vars_as_monomial(self): r""" 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
TESTS::
sage: R = BooleanPolynomialRing(1, 'y') sage: y.vars_as_monomial() y sage: R Boolean PolynomialRing in y
.. NOTE::
This function is part of the upstream PolyBoRi interface. """
def variables(self): r""" 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() () """
def nvariables(self): """ 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 """
def is_univariate(self): """ 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 """
def univariate_polynomial(self, 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 :meth:`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: 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) """
#construct ring if none else:
def monomials(self): r""" 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() [] """
def variable(self, 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 """
def terms(self): """ 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] """
def monomial_coefficient(self, mon): r""" Return the coefficient of the monomial ``mon`` in ``self``, where ``mon`` must have the same parent as ``self``.
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 """ else:
def constant_coefficient(self): """ 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 """ else:
def __hash__(self): r""" Return hash for ``self``.
EXAMPLES::
sage: P.<x,y> = BooleanPolynomialRing(2) sage: {x:1} # indirect doctest {x: 1} """
def __len__(self): r""" Return number of monomials in ``self``.
EXAMPLES::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: len(x + y) 2
::
sage: len(P.one()) 1
::
sage: len(x*y + y + z + x*z) 4
::
sage: len(P.zero()) 0 """
def __call__(self, *args, **kwds): """ Evaluate this boolean polynomials.
EXAMPLES::
sage: B.<x,y,z> = BooleanPolynomialRing(3) sage: f = x*y + z + 1 sage: f(0,1,1) 0 sage: f(z,y,x) x + y*z + 1 sage: f(x=z) y*z + z + 1
::
sage: P.<a,b,c> = PolynomialRing(QQ) sage: f(a,b,c) a*b + c + 1 sage: f(x=a,y=b,z=1) a*b + 2
Evaluation of polynomials can be used fully symbolic::
sage: f(x=var('a'),y=var('b'),z=var('c')) a*b + c + 1 sage: f(var('a'),var('b'),1) a*b """ raise ValueError("Using keywords and regular arguments not supported.") raise ValueError("Number of arguments is different from the number of variables of parent ring.") # TODO: We should collect those and reduce once only else:
def subs(self, in_dict=None, **kwds): r""" 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 """
else: fixed[var.lm().index()] = val
else:
def __reduce__(self): """ EXAMPLES::
sage: P.<a,b> = BooleanPolynomialRing(2) sage: loads(dumps(a)) == a True """
def _magma_init_(self, magma): r""" Return the Magma representation of self.
EXAMPLES::
sage: R.<x,y> = BooleanPolynomialRing() sage: f = y*x + x +1 sage: f._magma_init_(magma) # optional - magma '_sage_[...]*_sage_[...] + _sage_[...] + 1' sage: magma(f) # optional - magma x*y + x + 1 """ magma_gens = [e.name() for e in magma(self.parent()).gens()] return self._repr_with_changed_varnames(magma_gens)
def is_homogeneous(self): r""" 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 """
def set(self): r""" 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}, {}} """
def deg(self): r""" 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. """
def elength(self): r""" 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. """
def lead(self): r""" 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. """
def lex_lead(self): r""" 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. """
def lex_lead_deg(self): """ 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. """
def constant(self): r""" 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. """
def navigation(self): """ 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. """
def map_every_x_to_x_plus_one(self): """ Map every variable ``x_i`` in this polynomial to ``x_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
"""
def lead_divisors(self): r""" 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. """
def first_term(self): r""" 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. """
def reducible_by(self, BooleanPolynomial rhs): r""" Return ``True`` if this boolean polynomial is reducible by the polynomial ``rhs``.
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. """
def n_nodes(self): """ 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. """
def n_vars(self): """ 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. """
def graded_part(self, int deg): r""" 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
TESTS::
sage: f.graded_part(-1) 0 """
def has_constant_part(self): r""" Return ``True`` if this boolean polynomial has a constant part, i.e. if ``1`` 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 """
def zeros_in(self, s): r""" 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: 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),) """ else: raise TypeError("Type '%s' of s not supported." % type(s))
def spoly(self, BooleanPolynomial rhs): r""" 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. """
def stable_hash(self): """ A hash value which is stable across processes.
EXAMPLES::
sage: B.<x,y> = BooleanPolynomialRing() sage: x.stable_hash() -845955105 # 32-bit 173100285919 # 64-bit
.. NOTE::
This function is part of the upstream PolyBoRi interface. In Sage all hashes are stable. """
def ring(self): """ Return the parent of this boolean polynomial.
EXAMPLES::
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: a.ring() is B True """
def reduce(self, I): r""" 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`` - 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 :class:`GroebnerStrategy` object directly, since that will be faster. See the source code of this function for details.
TESTS::
sage: R=BooleanPolynomialRing(20,'x','lex') sage: a=R.random_element() sage: a.reduce([None,None]) Traceback (most recent call last): ... TypeError: argument must be a BooleanPolynomial. """
cdef class PolynomialConstruct: """ Implements PolyBoRi's ``Polynomial()`` constructor. """ def lead(self, 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 """
def __call__(self, x, ring=None): """ Construct a new :class:`BooleanPolynomial` or return ``x`` if it is a :class:`BooleanPolynomial` already.
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: PolynomialConstruct()(1, B) 1 sage: PolynomialConstruct()(a) a """ return (<BooleSet>x)._ring._element_constructor_(x) return (<BooleanMonomial>x)._ring(x) # It is a wrong use of the notion of "coercion" # to say that the boolean set is "coerced" into # a boolean polynomial ring: Boolean sets have # no parent, and thus there is no coercion map # from that parent to the ring. # So, it is just a conversion. [Simon King]
raise TypeError("Cannot generate Boolean polynomial from %s , %s%" % (type(x), type(ring)))
cdef class MonomialConstruct: """ Implements PolyBoRi's ``Monomial()`` constructor. """ def __call__(self, x): """ Construct a new :class:`BooleanMonomial` or return ``x`` if it is a :class:`BooleanMonomial` already.
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: MonomialConstruct()(B) 1 sage: MonomialConstruct()(a.lm()) a sage: MonomialConstruct()(a) a """ else: try: result = x[-1] for elt in reversed(x[:-1]): result = result * elt if isinstance(x, BooleanPolynomial): return result.lm() return result except Exception: raise TypeError("Cannot convert to Boolean Monomial %s" % type(x))
cdef class VariableConstruct: """ Implements PolyBoRi's ``Variable()`` constructor. """ def __call__(self, arg, ring=None): """ Return a Variable for ``x``.
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: VariableConstruct()(B) a sage: VariableConstruct()(0, B) a """ else: raise TypeError("todo polynomial factory %s%s" % (str(type(arg)),str(type(ring))))
cdef class BooleanPolynomialIterator: """ Iterator over the monomials of a boolean polynomial. """ def __dealloc__(self):
def __iter__(self): """ EXAMPLES::
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: list(B.random_element()) # indirect doctest [a*b, a*c, a, b*d, 1] """
def __next__(self): """ EXAMPLES::
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: it = iter(B.random_element()) sage: next(it) # indirect doctest a*b """ cdef PBMonom value
cdef inline BooleanPolynomialIterator new_BPI_from_BooleanPolynomial(BooleanPolynomial f): """ Construct a new BooleanMonomialIterator """ cdef BooleanPolynomialIterator m
class BooleanPolynomialIdeal(MPolynomialIdeal): def __init__(self, ring, gens=[], coerce=True): """ Construct an ideal in the boolean polynomial ring.
INPUT:
- ``ring`` - the ring this ideal is defined in
- ``gens`` - a list of generators
- ``coerce`` - coerce all elements to the ring ``ring`` (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
"""
def dimension(self): """ Return the dimension of ``self``, which is always zero.
TESTS:
Check that :trac:`13155` is solved::
sage: R = BooleanPolynomialRing(11, 'x') sage: R2 = PolynomialRing(GF(2), 11, 'x') sage: I = ideal([ R(f) for f in sage.rings.ideal.Cyclic(R2, 11).gens() ]) sage: I.dimension() 0 """
def groebner_basis(self, 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 shouldn't effect the calculated GB, but the algorithm.
- ``other_ordering_first`` - possible values are ``False`` or an ordering code. In practice, many Boolean examples have very few solutions and a very easy Groebner basis. So, a complex walk algorithm (which cannot be implemented using the data structures) seems unnecessary, as such Groebner bases can be converted quite fast by the normal Buchberger algorithm from one ordering into another ordering. (default: ``False``)
- ``prot`` - show protocol (default: ``False``)
- ``full_prot`` - show full protocol (default: ``False``)
EXAMPLES::
sage: P.<x0, x1, x2, x3> = BooleanPolynomialRing(4) sage: I = P.ideal(x0*x1*x2*x3 + x0*x1*x3 + x0*x1 + x0*x2 + x0) sage: I.groebner_basis() [x0*x1 + x0*x2 + x0, x0*x2*x3 + x0*x3]
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). <BLANKLINE> Highest degree reached during computation: 3. Polynomial Sequence with 35 Polynomials in 36 Variables
TESTS:
This example shows, that a bug in our variable indices was indeed fixed::
sage: R.<a111,a112,a121,a122,b111,b112,b211,b212,c111,c112> = BooleanPolynomialRing(order='lex') sage: I = (a111 * b111 * c111 + a112 * b112 * c112 - 1, a111 * b211 * c111 + a112 * b212 * c112 - 0, ....: a121 * b111 * c111 + a122 * b112 * c112, a121 * b211 * c111 + a122 * b212 * c112 - 1)*R sage: I.groebner_basis() [a111 + b212, a112 + b211, a121 + b112, a122 + b111, b111*b112 + b111 + b112 + 1, b111*b211 + b111 + b211 + 1, b111*b212 + b112*b211 + 1, b112*b212 + b112 + b212 + 1, b211*b212 + b211 + b212 + 1, c111 + 1, c112 + 1]
The following example shows whether boolean constants are handled correctly::
sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: I = Ideal([x*z + y*z + z, x*y + x*z + x + y*z + y + z]) sage: I.groebner_basis() [x, y, z]
Check that this no longer crash (:trac:`12792`)::
sage: names = [ "s{0}s{1}".format(i,j) for i in range(4) for j in range(8)] sage: R = BooleanPolynomialRing(32, names) sage: R.inject_variables() Defining s0s0, ... sage: problem = [s1s0*s1s1, s0s0*s0s1 + s0s0 + s0s1 + s2s0 + s3s0*s3s1 + s3s0 + s3s1, ....: s1s1 + s2s0 + s3s0 + s3s1 + 1, s0s0*s0s1 + s1s1 + s3s0*s3s1 + s3s0, ....: s0s1 + s1s0 + s1s1 + s3s0, s0s0*s0s1 + s0s0 + s0s1 + s1s1 + s2s0 + s3s1, ....: s0s1 + s1s0, s0s0*s0s1 + s0s0 + s0s1 + s1s0 + s2s0 + s3s1, ....: s0s0 + s2s0 + s3s0*s3s1 + s3s0 + 1, s0s0 + s1s1] sage: ideal(problem).groebner_basis() [1]
""" pass
from sage.rings.polynomial.multi_polynomial_ideal import MPolynomialIdeal_magma_repr gb = MPolynomialIdeal_magma_repr._groebner_basis_magma(self, **kwds) else:
def _groebner_basis(self, **kwds): r""" Calls PolyBoRi's groebner_basis function. It takes care of the import and suitable wrapping (if necessary)
EXAMPLES::
sage: B.<x,y,z> = BooleanPolynomialRing(order='deglex') sage: id = B.ideal((x + y)*(y + z), x*y*z) sage: id._groebner_basis() [x*z, x*y + y*z + y]
sage: B.<x,y,z> = BooleanPolynomialRing(order='deglex') sage: id = B.ideal((x + y)*(y + z), x*y*z) sage: id._groebner_basis() [x*z, x*y + y*z + y] """
# PolyBoRi's groebner_basis assumes increasing indices # so undone degneglex (dp_asc) wrapping for now tmp = BooleanPolynomialRing_from_PBRing((<BooleanPolynomialRing>self.ring())._pbring) gb = groebner_basis([new_BP_from_PBPoly(tmp, (<BooleanPolynomial>elt)._pbpoly) \ for elt in self.gens()], **kwds) return [new_BP_from_PBPoly(self.ring(), (<BooleanPolynomial>elt)._pbpoly) for elt in gb]
def variety(self, **kwds): r""" 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}]
TESTS:
BooleanIdeal and regular (quotient) Ideal should coincide::
sage: R = BooleanPolynomialRing(6, ['x%d'%(i+1) for i in range(6)], order='lex') sage: R.inject_variables() Defining... sage: polys = [ ....: x1*x2 + x1*x4 + x1*x5 + x1*x6 + x1 + x2 + x3*x4 + x3*x5 + x3 + x4*x5 + x4*x6 + x4 + x5 + x6, ....: x1*x2 + x1*x3 + x1*x4 + x1*x6 + x2*x3 + x2*x6 + x2 + x3*x4 + x5*x6, ....: x1*x3 + x1*x4 + x1*x6 + x1 + x2*x5 + x2*x6 + x3*x4 + x3 + x4*x6 + x4 + x5*x6 + x5 + x6, ....: x1*x2 + x1*x3 + x1*x4 + x1*x5 + x2 + x3*x5 + x3*x6 + x3 + x5 + x6, ....: x1*x2 + x1*x4 + x1*x5 + x1*x6 + x2*x3 + x2*x4 + x2*x5 + x3*x5 + x5*x6 + x5 + x6, ....: x1*x2 + x1*x6 + x2*x4 + x2*x5 + x2*x6 + x3*x6 + x4*x6 + x5*x6 + x5] sage: I = R.ideal( polys ) sage: print(reproducible_repr(I.variety())) [{x1: 0, x2: 0, x3: 0, x4: 0, x5: 0, x6: 0}, {x1: 1, x2: 1, x3: 1, x4: 0, x5: 0, x6: 1}]
sage: R = PolynomialRing(GF(2), 6, ['x%d'%(i+1) for i in range(6)], order='lex') sage: I = R.ideal( polys ) sage: v = (I + sage.rings.ideal.FieldIdeal(R)).variety() sage: print(reproducible_repr(v)) [{x1: 0, x2: 0, x3: 0, x4: 0, x5: 0, x6: 0}, {x1: 1, x2: 1, x3: 1, x4: 0, x5: 0, x6: 1}]
Check that :trac:`13976` is fixed::
sage: R.<x,y,z> = BooleanPolynomialRing() sage: I = ideal( [ x*y*z + x*z + y + 1, x+y+z+1 ] ) sage: sols = I.variety() sage: sols[0][y] 1
Make sure the result is a key converting dict, as discussed in :trac:`9788` and consistent with :meth:`sage.rings.polynomial.multi_polynomial_ideal.MPolynomialIdeal_singular_repr.variety`::
sage: sols[0]["y"] 1
"""
def reduce(self, 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 """ except AttributeError: self.groebner_basis() g = self.__gb
def interreduced_basis(self): """ 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: 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] """
def __eq__(self, other): """ EXAMPLES:: sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True) sage: F,s = sr.polynomial_system() sage: I = F.ideal() sage: J = Ideal(I.interreduced_basis()) sage: I == J True sage: J = Ideal(I.gens()[1:] + [I.gens()[0] + 1]) sage: I == J False """ return False return False else:
def __ne__(self, other): """ EXAMPLES:: sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True) sage: F,s = sr.polynomial_system() sage: I = F.ideal() sage: J = Ideal(I.interreduced_basis()) sage: I != J False sage: J = Ideal(I.gens()[1:] + [I.gens()[0] + 1]) sage: I != J True """
## # # Various internal constructors for boolean polynomials from various # other formats. # ##
cdef inline BooleanPolynomial new_BP(BooleanPolynomialRing parent): cdef BooleanPolynomial p
cdef inline BooleanPolynomial new_BP_from_PBVar(BooleanPolynomialRing parent, PBVar juice):
cdef inline BooleanPolynomial new_BP_from_PBPoly(BooleanPolynomialRing parent, PBPoly juice):
cdef inline BooleanPolynomial new_BP_from_PBMonom(BooleanPolynomialRing parent, PBMonom juice):
cdef inline BooleanPolynomial new_BP_from_PBSet(BooleanPolynomialRing parent, PBSet juice):
cdef inline BooleanPolynomial new_BP_from_int(BooleanPolynomialRing parent, int juice): cdef BooleanPolynomial p = new_BP(parent) p._pbpoly = PBBoolePolynomial(juice, parent._pbring) return p
cdef class BooleSet: """ 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 :class:`BooleanPolynomial` can easily be converted to the type :class:`BooleSet` by using the member function :meth:`BooleanPolynomial.set()`.
INPUT:
- ``param`` - either a :class:`CCuddNavigator`, a :class:`BooleSet` or ``None``. - ``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::
:class:`BooleSet` prints as ``{}`` but are not Python dictionaries. """ def __init__(self, param=None, ring=None): cdef BooleanPolynomial p raise TypeError("BooleSet constructor requires parent ring argument") (<BooleanPolynomialRing>ring)._pbring) else:
elif isinstance(ring, BooleanPolynomialRing): detected_ring = ring
raise TypeError( "BooleSet: could not extract ring from %s, %s" % (type(param), str(type(ring))))
def __repr__(self): """ EXAMPLES::
sage: from brial import BooleSet sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: BS = BooleSet(B) sage: repr(BS) # indirect doctest '{}' """
def set(self): """ Return ``self``.
EXAMPLES::
sage: B.<a,b,c,d> = BooleanPolynomialRing(4) sage: BS = (a*b + c).set() sage: BS.set() is BS True """
def empty(self): """ 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 """
def navigation(self): """ 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 """
def ring(self): """ 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 """
def cartesian_product(self, rhs): r""" 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.
.. MATH::
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}} """
def diff(self, rhs): r""" Return the set theoretic difference of this set and the set ``rhs``.
The difference of two sets `X` and `Y` is defined as:
.. MATH::
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}} """ cdef PBSet s else: raise TypeError("Argument 'rhs' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(rhs))
def union(self, rhs): r""" Return the set theoretic union of this set and the set ``rhs``.
The union of two sets `X` and `Y` is defined as:
.. MATH::
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}, {}} """ cdef PBSet s else: raise TypeError("Argument 'rhs' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(rhs))
def change(self, 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}} """
def vars(self): """ 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 """
def n_nodes(self): """ 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 """
def __iter__(self): """ Create an iterator over elements of self.
EXAMPLES::
sage: P.<x, y> = BooleanPolynomialRing(2) sage: f = x*y+x+y+1; s = f.set() sage: list(s) [x*y, x, y, 1] """
def __len__(self): """ 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: len(s) 2 """
def __hash__(self): """ 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:1} {{{x1,x2}, {x2,x3}}: 1} """
def __mod__(self, BooleSet vs): """ Return a set of all monomials which are not divisible by monomials in ``vs``.
INPUT:
- ``vs`` - a boolean set
EXAMPLES::
sage: B.<a,b,c> = BooleanPolynomialRing() sage: f = a*b + b + 1 sage: s = f.set(); s {{a,b}, {b}, {}} sage: s % a.set() {{b}, {}} sage: s % b.set() {{}} """
def __contains__(self, BooleanMonomial m): """ Return ``True`` if ``m`` is in this set.
INPUT:
- ``m`` - a monomial
EXAMPLES::
sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: f = a*b sage: s = f.set() sage: a.lm() in s False
TESTS::
sage: B.<a,b,c> = BooleanPolynomialRing() sage: f = a*b sage: s = f.set() sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: a.lm() in s Traceback (most recent call last): ... AssertionError """
def stable_hash(self): """ A hash value which is stable across processes.
EXAMPLES::
sage: B.<x,y> = BooleanPolynomialRing() sage: s = x.set() sage: s.stable_hash() -845955105 # 32-bit 173100285919 # 64-bit
.. NOTE::
This function is part of the upstream PolyBoRi interface. In Sage all hashes are stable. """
def divide(self, BooleanMonomial 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}, {}} """
def subset0(self, int 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}} """
def subset1(self, int 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: 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}} """
def include_divisors(self): """ 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}, {}} """
def minimal_elements(self): """ 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}} """
def intersect(self, BooleSet other): r""" Return the set theoretic intersection of this set and the set ``rhs``.
The union of two sets `X` and `Y` is defined as:
.. MATH::
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}} """
def divisors_of(self, BooleanMonomial 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}} """
def multiples_of(self, BooleanMonomial 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}} """
def size_double(self): """ 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 """
cdef inline BooleSet new_BS_from_PBSet(PBSet juice, BooleanPolynomialRing ring): """ Construct a new BooleSet """ cdef BooleSet s
cdef class BooleSetIterator: """ Helper class to iterate over boolean sets. """ def __dealloc__(self):
def __iter__(self): """ EXAMPLES::
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: f = B.random_element() sage: it = iter(f.set()) # indirect doctesrt """ return self
def __next__(self): """ EXAMPLES::
sage: B.<a,b,c,d> = BooleanPolynomialRing() sage: f = B.random_element() sage: f a*b + a*c + a + b*d + 1 sage: it = iter(f.set()) sage: next(it) a*b """ cdef PBMonom value
cdef inline BooleSetIterator new_BSI_from_PBSetIter(BooleSet s): """ Construct a new BooleSetIterator """ cdef BooleSetIterator m
cdef class CCuddNavigator: def __call__(self): return self
def value(self):
def else_branch(self):
def then_branch(self):
def constant(self):
def terminal_one(self):
def __richcmp__(CCuddNavigator self, CCuddNavigator other, int op): """ ::
sage: R.<x,y>=BooleanPolynomialRing(2) sage: p = R(0) sage: p.navigation() == p.navigation() True sage: p.navigation() != p.navigation() False sage: p.navigation() == x.navigation() False """
else: return NotImplemented
def __hash__(self):
cdef class BooleanPolynomialVector: """ 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] """ def __init__(self, I=None): """ Create a new :class:`BooleanPolynomialVector`.
INPUT:
- ``I`` - a list 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] """ # This is used by PolyBoRi python code
def __iter__(self): """ 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: list(iter(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] """
def __len__(self): """ 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() sage: len(v) 0 sage: v = BooleanPolynomialVector(l) sage: len(v) 3 """
def __getitem__(self, Py_ssize_t i): """ 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: v[-1] a*c + a*e + b*c + c*f + f sage: v[3] Traceback (most recent call last): ... IndexError: index out of range sage: v['a'] Traceback (most recent call last): ... TypeError: 'str' object cannot be interpreted as an index """
def __setitem__(self, Py_ssize_t i, p): """ 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; v[0] a sage: v[-1] = b; v[-1] b sage: v[3] = c Traceback (most recent call last): ... IndexError """ self._parent = p.ring()
def append(self, 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] """ cdef PBPoly p else: raise TypeError("Argument 'el' has incorrect type (expected BooleanPolynomial or BooleanMonomial, got %s)" % type(el))
cdef inline BooleanPolynomialVector new_BPV_from_PBPolyVector( BooleanPolynomialRing parent, PBPolyVector juice): cdef BooleanPolynomialVector m
cdef class BooleanPolynomialVectorIterator: def __iter__(self):
def __next__(self):
cdef inline BooleanPolynomialVectorIterator new_BPVI_from_PBPolyVectorIter( BooleanPolynomialVector vec): """ Construct a new BooleanPolynomialVectorIterator """ cdef BooleanPolynomialVectorIterator m
cdef class ReductionStrategy: """ Functions and options for boolean polynomial reduction. """ def __init__(self, ring): """ EXAMPLES::
sage: from brial import * sage: B.<x,y> = BooleanPolynomialRing() sage: red = ReductionStrategy(B) sage: del red """
def add_generator(self, BooleanPolynomial 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]
TESTS:
Check if :trac:`8966` is fixed::
sage: red = ReductionStrategy(B) sage: red.add_generator(None) Traceback (most recent call last): ... TypeError: argument must be a BooleanPolynomial. """ raise ValueError("zero generators not allowed.")
def nf(self, BooleanPolynomial 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 """
def reduced_normal_form(self, BooleanPolynomial 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 """
def head_normal_form(self, BooleanPolynomial 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 """
def can_rewrite(self, BooleanPolynomial p): """ Return ``True`` if ``p`` 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 """
def cheap_reductions(self, BooleanPolynomial p): """ Peform '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 """
def __getattr__(self, name): """ Get attributes of this reduction strategy object.
SUPPORTED OPTIONS:
- ``opt_ll`` - use linear algebra (default: ``False``)
- ``opt_red_tail`` - perform tail reductions (default: ``True``)
- ``opt_red_tail_deg_growth`` - (default: ``True``)
- ``opt_brutal_reductions`` - (default: ``True``)
OTHER ATTRIBUTES:
- ``leading_terms`` - all leading terms of generators
- ``minimal_leading_terms`` - the reduced set of leading terms
- ``monomials`` -
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(x*y + y) sage: red.add_generator(y*z + z)
sage: red.opt_ll False
sage: red.opt_red_tail True
sage: red.opt_brutal_reductions True
sage: red.opt_red_tail_deg_growth True
sage: red.leading_terms {{x,y}, {x}, {y,z}} sage: red.minimal_leading_terms {{x}, {y,z}} """
raise AttributeError(name)
def __setattr__(self, name, val): strat.optBrutalReductions = val else: raise AttributeError(name)
def __len__(self): """ 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(x*y + y) sage: red.add_generator(y*z + z) sage: len(red) 3 """
def __getitem__(self, Py_ssize_t i): cdef PBPoly t
cdef class BooleanPolynomialEntry: def __init__(self, p):
cdef class FGLMStrategy: """ 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. """ def __init__(self, from_ring, to_ring, BooleanPolynomialVector vec): """ Execute the FGLM algorithm.
EXAMPLES::
sage: from brial import * sage: B.<x,y,z> = BooleanPolynomialRing() sage: x > y > z True sage: old_ring = B sage: new_ring = B.clone(ordering=lp) sage: new_ring.gen(0) > new_ring.gen(1) > new_ring.gen(2) True sage: new_ring.gen(2) > new_ring.gen(1) > new_ring.gen(0) False sage: ideal = BooleanPolynomialVector([x+z, y+z]) sage: FGLMStrategy(old_ring, new_ring, ideal) <sage.rings.polynomial.pbori.FGLMStrategy object at 0x...>
Check that :trac:`13883` is fixed::
sage: nonreduced = BooleanPolynomialVector([x+z, x+y]) sage: FGLMStrategy(old_ring, new_ring, nonreduced) # optional - debug Traceback (most recent call last): ... RuntimeError...
""" cdef BooleanPolynomialRing _from_ring, _to_ring
elif isinstance(from_ring.ring, BooleanPolynomialRing): _from_ring = <BooleanPolynomialRing>from_ring.ring else: raise TypeError("from_ring has wrong type %s"%(type(from_ring),))
elif isinstance(to_ring.ring, BooleanPolynomialRing): _to_ring = <BooleanPolynomialRing>to_ring.ring else: raise TypeError("to_ring has wrong type %s"%(type(to_ring),))
def main(self): """ 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] """
cdef class GroebnerStrategy: """ A Groebner strategy is the main object to control the strategy for computing Groebner bases.
.. NOTE::
This class is mainly used internally. """ def __init__(self, param): """
INPUT:
- ``param`` - either ``None`` or a :class:`GroebnerStrategy` object.
EXAMPLES::
sage: from brial import GroebnerStrategy sage: B.<a,b,c,d,e,f> = BooleanPolynomialRing() sage: G = GroebnerStrategy(B) sage: H = GroebnerStrategy(G) sage: del G sage: del H """ else: raise ValueError("Cannot generate GroebnerStrategy from %s." % type(param))
def add_generator_delayed(self, BooleanPolynomial 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] """ raise ValueError("zero generators not allowed.")
def add_generator(self, BooleanPolynomial 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 """ raise ValueError("zero generators not allowed.")
def add_as_you_wish(self, BooleanPolynomial 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] """ raise ValueError("zero generators not allowed.")
def implications(self, i): """ Compute "useful" implied polynomials of ``i``-th generator, and add them to the strategy, if it finds any.
INPUT:
- ``i`` - an index """ cdef PBGBStrategy* strat = self._strat.get() strat.addNonTrivialImplicationsDelayed(strat.generators[i])
def clean_top_by_chain_criterion(self):
def symmGB_F2(self): """ 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. """
def contains_one(self): """ 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] """
def faugere_step_dense(self, BooleanPolynomialVector 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] """
def minimalize(self): """ Return a vector of all polynomials with minimal leading terms.
.. NOTE::
Use this function if strat contains a GB. """ return new_BPV_from_PBPolyVector(self._parent, deref(self._strat).minimalize())
def minimalize_and_tail_reduce(self): """ 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. """
def npairs(self):
def top_sugar(self):
def some_spolys_in_next_degree(self, n):
def all_spolys_in_next_degree(self): return new_BPV_from_PBPolyVector(self._parent, nextDegreeSpolys(deref(self._strat)))
def small_spolys_in_next_degree(self, double f, int n): return new_BPV_from_PBPolyVector(self._parent, small_next_degree_spolys(deref(self._strat), f, n))
def ll_reduce_all(self): """ Use the built-in ll-encoded :class:`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. """ deref(self._strat).llReduceAll()
def next_spoly(self): return new_BP_from_PBPoly(self._parent, deref(self._strat).nextSpoly())
def all_generators(self): """ 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] """
def suggest_plugin_variable(self): return deref(self._strat).suggestPluginVariable()
def variable_has_value(self, int 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 """
def nf(self, BooleanPolynomial 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.
"""
def select(self, BooleanMonomial m): """ Return the index of the generator which can reduce the monomial ``m``.
INPUT:
- ``m`` - a :class:`BooleanMonomial`
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 """
def __len__(self): """ Return the number of generators.
EXAMPLES::
sage: B.<a,b,c> = BooleanPolynomialRing() sage: from brial import GroebnerStrategy
sage: G = GroebnerStrategy(B) sage: G.add_as_you_wish(a) sage: len(G) 1 sage: G.add_as_you_wish(b) sage: len(G) 2 sage: G.add_as_you_wish(b + 1) sage: len(G) 2 """
def __getitem__(self, Py_ssize_t i): cdef PBPoly t
def __getattr__(self, name): cdef PBGBStrategy* strat = self._strat.get() if name == 'enabled_log': return strat.enabledLog elif name == 'opt_lazy': return strat.optLazy elif name == 'opt_exchange': return strat.optExchange elif name == 'opt_allow_recursion': return strat.optAllowRecursion elif name == 'opt_linear_algebra_in_last_block': return strat.optLinearAlgebraInLastBlock elif name == 'opt_modified_linear_algebra': return strat.optModifiedLinearAlgebra elif name == 'opt_draw_matrices': return strat.optDrawMatrices elif name == '"opt_red_by_reduced': return strat.reduceByTailReduced elif name == 'chain_criterions': return strat.chainCriterions elif name == 'variable_chain_criterions': return strat.variableChainCriterions elif name == 'easy_product_criterions': return strat.easyProductCriterions elif name == 'extended_product_criterions': return strat.extendedProductCriterions elif name == 'matrix_prefix': return strat.matrixPrefix.c_str()
raise AttributeError(name)
def __setattr__(self, name, val): cdef char* _tmp elif name == 'redByReduced': # working around a bug in PolyBoRi 0.6 strat.reduceByTailReduced = val else: raise AttributeError(name)
class BooleanMulAction(Action): def _call_(self, left, right): """ EXAMPLES: sage: from brial import BooleanMonomialMonoid sage: P.<x,y,z> = BooleanPolynomialRing(3) sage: M = BooleanMonomialMonoid(P) sage: x = M(x); xy = M(x*y); z=M(z) sage: x*1 # indirect doctest x sage: 1*x x sage: x*int(1) x sage: int(1)*x x sage: 0*x 0 sage: x*2 0 """ else:
cdef inline CCuddNavigator new_CN_from_PBNavigator(PBNavigator juice, Py_ssize_t* pbind): """ Construct a new CCuddNavigator """ cdef CCuddNavigator n
cdef class VariableBlock: def __init__(self, int size, int start_index, int offset, bint reverse, BooleanPolynomialRing ring): ring._pbring)
def __dealloc__(self): self._ring = None del self._block
def __call__(self, int i): return new_BM_from_PBVar(self._ring._monom_monoid, self._ring, deref(self._block)(i))
def add_up_polynomials(BooleanPolynomialVector v, BooleanPolynomial 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 """
def nf3(ReductionStrategy s, BooleanPolynomial p, BooleanMonomial m): return new_BP_from_PBPoly(s._parent, pb_nf3(deref(s._strat), p._pbpoly, m._pbmonom))
def red_tail(ReductionStrategy s, BooleanPolynomial p): """ Perform tail reduction on ``p`` using the generators of ``s``.
INPUT:
- ``s`` - a reduction strategy - ``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_tail(red,x) x sage: red_tail(red,x*y + x) x*y + y + 1 """
def map_every_x_to_x_plus_one(BooleanPolynomial p): """ Map every variable ``x_i`` in this polynomial to ``x_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 """
def zeros(pol, BooleSet s): """ Return a ``BooleSet`` encoding on which points from ``s`` the polynomial ``pol`` evaluates to zero.
INPUT:
- ``pol`` - a boolean polynomial
- ``s`` - a set of points encoded as a ``BooleSet``
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),)
""" cdef PBPoly p elif isinstance(pol, BooleanMonomial): p = PBBoolePolynomial((<BooleanMonomial>pol)._pbmonom) else: raise TypeError("Argument 'p' has incorrect type (expected BooleanPolynomial or BooleanMonomial, got %s)" % type(pol))
def interpolate(zero, one): r""" 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: 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 """ cdef PBSet z, o cdef BooleanPolynomialRing ring elif isinstance(zero, BooleanPolynomial): z = (<BooleanPolynomial>zero)._pbpoly.set() ring = (<BooleanPolynomial>zero)._parent else: raise TypeError("Argument 'zero' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(zero)) elif isinstance(one, BooleanPolynomial): o = (<BooleanPolynomial>one)._pbpoly.set() else: raise TypeError("Argument 'one' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(one))
def interpolate_smallest_lex(zero, one): r""" 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: 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 """ cdef PBSet z, o elif isinstance(zero, BooleanPolynomial): z = (<BooleanPolynomial>zero)._pbpoly.set() else: raise TypeError("Argument 'zero' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(zero)) else: raise TypeError("Argument 'one' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(one))
def contained_vars(BooleSet m): return new_BS_from_PBSet(pb_contained_variables_cudd_style(m._pbset), m._ring)
def mod_var_set(BooleSet a, BooleSet v): return new_BS_from_PBSet(pb_mod_var_set(a._pbset, v._pbset), a._ring)
def mult_fact_sim_C(BooleanPolynomialVector v, BooleanPolynomialRing ring): return new_BP_from_PBPoly(v._parent, pb_mult_fast_sim(v._vec, ring._pbring))
def recursively_insert(CCuddNavigator n, int ind, BooleSet m): cdef PBSet b cdef BooleanPolynomialRing ring = m.ring() b = pb_recursively_insert(n._pbnav, ring.pbind[ind], m._pbset) return new_BS_from_PBSet(b, m._ring)
def ll_red_nf_redsb(p, BooleSet 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`` - a boolean polynomial
- ``reductors`` - 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 """ cdef PBPoly t cdef PBPoly res cdef BooleanPolynomialRing parent elif isinstance(p, BooleanMonomial): t = PBBoolePolynomial((<BooleanMonomial>p)._pbmonom) parent = (<BooleanMonomial>p)._ring else: raise TypeError("Argument 'p' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(p))
def ll_red_nf_noredsb(BooleanPolynomial p, BooleSet reductors): """ Redude the polynomial ``p`` by the set of ``reductors`` with linear leading terms.
INPUT:
- ``p`` - a boolean polynomial
- ``reductors`` - 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 """ cdef PBPoly t
def ll_red_nf_noredsb_single_recursive_call(BooleanPolynomial p, BooleSet reductors): """ Redude the polynomial ``p`` by the set of ``reductors`` with linear leading terms.
:func:`ll_red_nf_noredsb_single_recursive` call has the same specification as :func:`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`` - a boolean polynomial
- ``reductors`` - 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 """ cdef PBPoly t
def mod_mon_set(BooleSet a_s, BooleSet v_s): cdef PBSet b
def parallel_reduce(BooleanPolynomialVector inp, GroebnerStrategy strat, int average_steps, double delay_f):
def 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: 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. """ cdef PBSet a_set, b_set cdef PBSet res cdef BooleanPolynomialRing ring else: raise TypeError("Argument 'b' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(b))
else: raise TypeError("Argument 'a' has incorrect type (expected BooleSet or BooleanPolynomial, got %s)" % type(a))
else: raise TypeError("Only variables are acceptable as root.") else: raise TypeError("Only variables are acceptable as root.")
raise TypeError("Only variables are acceptable as root.")
"the values of roots of the branches.")
def 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 """ idx = (<BooleSet>s)._pbset.navigation().value() else: raise TypeError("Argument 's' has incorrect type (expected BooleSet, BooleanMonomial or BooleanPolynomial, got %s)" % type(s))
cdef long PBRing_identifier(PBRing pbring):
cdef long _hash = pbring.hash() ^ hash(pbring.ordering().getOrderCode())
cdef PBBlockIter start = pbring.ordering().blockBegin() cdef PBBlockIter finish = pbring.ordering().blockEnd() while start != finish: _hash ^= start.dereference() start.increment()
return _hash
cdef object TermOrder_from_PBRing(PBRing _ring):
cdef BooleanPolynomialRing BooleanPolynomialRing_from_PBRing(PBRing _ring): """ Get BooleanPolynomialRing from C++-implementation """ cdef int i,j
# pbdp and pbblock_dp cannot occur here
def 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]
"""
def substitute_variables(BooleanPolynomialRing parent, vec, BooleanPolynomial poly): """ ``var(i)`` is replaced by ``vec[i]`` in ``poly``.
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
""" cdef BooleanPolynomialVector _vec
else:
def 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}} """
def random_set(BooleanMonomial variables, length): """ Return a random set of monomials with ``length`` elements with each element in the variables ``variables``.
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}} """ cdef PBSet r
def easy_linear_factors(BooleanPolynomial p):
# todo: merge with pickling from brial.parallel def 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 """ return ring(eval(string,ring.gens_dict()))
# todo: merge with pickling from brial.parallel def 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 """
# todo: merge with pickling from brial.parallel def 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 """
cdef class BooleConstant: def __init__(self, int value): """ 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] """
def __repr__(self): """ EXAMPLES::
sage: from brial import BooleConstant sage: repr((BooleConstant(0),BooleConstant(1))) # indirect doctest '(0, 1)'
"""
def deg(self): """ Get degree of boolean constant.
EXAMPLES::
sage: from brial import BooleConstant sage: BooleConstant(0).deg() -1 sage: BooleConstant(1).deg() 0 """
def variables(self): """ Get variables (return always and empty tuple).
EXAMPLES::
sage: from brial import BooleConstant sage: BooleConstant(0).variables() () sage: BooleConstant(1).variables() () """
def is_one(self): """ Check whether boolean constant is one.
EXAMPLES::
sage: from brial import BooleConstant sage: BooleConstant(0).is_one() False sage: BooleConstant(1).is_one() True """
def is_zero(self): """ Check whether boolean constant is zero.
EXAMPLES::
sage: from brial import BooleConstant sage: BooleConstant(1).is_zero() False sage: BooleConstant(0).is_zero() True """
def is_constant(self): """ 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 """
def has_constant_part(self): """ 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 """
cdef object pb_block_order(n, order_str,blocks): T = [TermOrder(order_str, blockend-blockstart, force=True) for (blockstart, blockend) in zip([0] + blocks, blocks + [n])]
if T: result = T[0] for elt in T[1:]: result += elt return result else: return order_str
cpdef object TermOrder_from_pb_order(int n, order, blocks): if order == pbblock_dlex: order_str = pb_block_order(n, "deglex", blocks) elif order == pbblock_dp: order_str = pb_block_order(n, "degrevlex", blocks) elif order == pbblock_dp_asc: order_str = pb_block_order(n, "degneglex", blocks) else: order_str = inv_order_dict[order] else:
cdef class VariableFactory: """Implements PolyBoRi's ``Variable()`` constructor and a variable factory for given ring """
def __init__(self, BooleanPolynomialRing ring=None): """ Initialize variable factory, if ring is given. Otherwise it initializes a plain constructor
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: fac = VariableFactory() sage: fac = VariableFactory(B)
"""
def __call__(self, arg=0, ring=None): """ Return a Variable for ``x``.
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: VariableFactory()(B) a sage: VariableFactory()(0, B) a sage: VariableFactory(B)() a sage: VariableFactory(B)(0) a
""" else: raise TypeError( "Cannot convert (%s, %s) to Boolean Variable" % (type(arg), type(ring)))
cdef class MonomialFactory: """ 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)
""" def __init__(self, BooleanPolynomialRing ring=None): """ Initialized a polynomial factory of ring is given. Otherwise it initializes a plain constructor.
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: MonomialFactory()(B) 1 sage: MonomialFactory()(a.lm()) a sage: MonomialFactory()(a) a sage: MonomialFactory(B)() 1 """
def __call__(self, arg=None): """ Generates a Boolean monomial from argument.
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: MonomialFactory()(B) 1 sage: MonomialFactory()(a.lm()) a sage: MonomialFactory()(a) a sage: MonomialFactory(B)() 1 """ else: try: result = arg[-1] for elt in reversed(arg[:-1]): result = result * elt if isinstance(arg, BooleanPolynomial): return result.lm() return result except Exception: raise TypeError( "Cannot %s convert to Boolean Monomial" % type(arg))
cdef class PolynomialFactory: """ Implements PolyBoRi's ``Polynomial()`` constructor and a polynomial factory for given rings. """ def __init__(self, BooleanPolynomialRing ring=None): """ Constructs a polynomial factory if ring is given, or plain constructor otherwise.
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: fac = PolynomialFactory()
"""
def lead(self, 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 """
def __call__(self, arg, ring=None): """ Construct a new :class:`BooleanPolynomial` or return ``arg`` if it is a :class:`BooleanPolynomial` already.
EXAMPLES::
sage: from brial import * sage: B.<a,b,c> = BooleanPolynomialRing() sage: PolynomialFactory()(1, B) 1 sage: PolynomialFactory()(a) a sage: PolynomialFactory(B)(1) 1
""" else:
elif isinstance(arg, BooleanPolynomial): return new_BP_from_PBPoly(self._ring, self._factory((<BooleanPolynomial>arg)._pbpoly))
elif isinstance(arg, BooleanMonomial): return new_BP_from_PBPoly(self._ring, self._factory((<BooleanMonomial>arg)._pbmonom))
raise TypeError("Cannot convert %s to BooleanPolynomial" % type(arg)) |