next | previous | forward | backward | up | top | index | toc | Macaulay2 website
BooleanGB :: gbBoolean(Ideal)

gbBoolean(Ideal) -- Compute Groebner Basis for Ideals in Boolean Polynomial Quotient Ring

Synopsis

Description

gbBoolean computes $J$, a reduced Groebner basis in lexicographic order for the ideal $I$ in the Boolean quotient ring, i.e., $\mathbb F_2[x_1, \ldots, x_n] / <x_1^2-x_1, \ldots, x_n^2-x_n >$. The algorithm is implemented bitwise rather than symbolic, which reduces the computational complexity.

i1 : n = 3

o1 = 3
i2 : R = ZZ/2[vars(0)..vars(n-1)]

o2 = R

o2 : PolynomialRing
i3 : J = apply( gens R, x -> x^2 + x)

       2       2       2
o3 = {a  + a, b  + b, c  + c}

o3 : List
i4 : QR = R/J

o4 = QR

o4 : QuotientRing
i5 : I = ideal(a+b,b)

o5 = ideal (a + b, b)

o5 : Ideal of QR
i6 : gbBoolean I

o6 = ideal (b, a)

o6 : Ideal of QR
i7 : gens gb I

o7 = | b a |

              1        2
o7 : Matrix QR  <--- QR

Caveat

gbBoolean always assumes that the ideal is in the Boolean quotient ring, i.e., $\mathbb F_2[x_1, \ldots, x_n] / <x_1^2-x_1, \ldots, x_n^2-x_n >$, regardless of the ring in which the ideal was generated. Thus, gbBoolean promotes an ideal in the base ring to the quotient ring automatically, even if the quotient ring has not been defined.

See also