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

Synopsis

Function: gbBoolean
Usage:

gbBoolean I
Inputs:
- I, an ideal,
Outputs:
- J, an ideal, the reduced Groebner basis of I

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.

Ways to use this method: