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

## Synopsis

• Function: gbBoolean
• Usage:
gbBoolean I
• Inputs:
• 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.