BooleanGB -- Groebner Bases for Ideals in Boolean Polynomial Quotient Ring

Description

BooleanGB is a package to compute Groebner Bases in lexicographic order for polynomial ideals in the quotient ring $\mathbb F_2[x_1, \ldots, x_n]/J$, where J is the ideal generated by field polynomials $x_i^2 - x_i $ for $i \in \{ 1, \ldots, n\}$. The algorithm is implemented bitwise rather than symbolically, which reduces the computational complexity.

i1 : n = 3;

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

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

i4 : QR = R/J;

i5 : I = 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

BooleanGB 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, any ideal in the base ring is promoted to the quotient ring automatically, even if the quotient ring has not been defined.

Authors

Franziska Hinkelmann <[email protected]>
Mike Stillman
Elizabeth Arnold

Version

This documentation describes version 1.0 of BooleanGB.

Citation

If you have used this package in your research, please cite it as follows:

@misc{BooleanGBSource,
  title = {{BooleanGB: Groebner bases for ideals in Boolean polynomial quotient rings. Version~1.0}},
  author = {Franziska Hinkelmann and Mike Stillman and Elizabeth Arnold},
  howpublished = {A \emph{Macaulay2} package available at
    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages}}
}

Exports

Functions and commands
- gbBoolean -- see gbBoolean(Ideal) -- Compute Groebner Basis for Ideals in Boolean Polynomial Quotient Ring
Methods
- gbBoolean(Ideal) -- Compute Groebner Basis for Ideals in Boolean Polynomial Quotient Ring

For the programmer

The object BooleanGB is a package, defined in BooleanGB.m2.

The source of this document is in BooleanGB.m2:50:0.