実際の計算

ブール環の直積構造がわかっている場合、グレブナー基底の計算は、定理 2.4 によってGF(2) 上の多項式環に おけるグレブナー基底の計算に還元される. 各成分 Gi の計算は全く独立におこなわれるので、 並列計算が容易に実現可能になる. 以下に、実際の計算がどのようにされるかについて述べる.

ブール環 B として、A を 加算無限集合として、
B = { P|P ⊆ A and P is a finite set or a complement of a finite set } で定義されるブール環を用いた. これは有限ブール環ではないが、実際のグレブナー基底の計算では、これの有限部分環のみを用い、 直積構造も自明である. 対象領域がブール環であるので、多項式環 B[ X1 ,X2 ....,Xn] ではなく、剰余環 B [ X1 , X2 ,...., Xn ] / ( X²1 + X1, X²2 + X2 , .... ,X²n + Xn ) における 正規グレブナー基底(われわれはこれを Boolean Gröbner Basis とよんでいる[S 95].) の計算をおこなう.
定理 2.4を用いてどのような計算をするのか、次の例で説明する. a,b ∈ A として、

((~{a,b}) * x * y + {a} * x + y + {b}, x * y + {a} * y + x + {a,b})

の B [ x , y ] / ( x² + x,y² + y ) におけるグレブナー基底の計算には B の有限部分環
{ 0 , 1 , {a} , {b} , {a,b} , ~{a,b} , ~{a} , ~{b} } の要素のみが現れるので、この部分環における計算を考えればよい. この有限ブール環のアトミックな要素は {a} , {b} , ~{a,b} の３つ なので、この部分環は GF( 2 )³ と同型になる. この同型写像を Φ とおく. ただし Φ( {a} ) = ( 1 , 0 , 0 ) , Φ( {b} ) = ( 0 , 1 , 0 ) , Φ( ~{a,b} ) = ( 0 , 0 , 1 ) とする. このとき、多項式 (~{a,b} ) * x * y + {a} * x + y + {b} , x * y + {a} * y + x + {a,b} の Φ による像は GF( 2 )³ 上の多項式 ( 0 , 0 , 1 ) * x * y + ( 1 , 0 , 0 ) * x + ( 1 , 1 , 1 ) * y + ( 0 , 1 , 0 ),( 1 , 1 , 1 ) * x * y +( 1 , 0 , 0 ) * y + ( 1 , 1 , 1 ) * x + ( 1 , 1 , 0 ) となる. G を GF( 2 )³ [ x , y ] / ( x² + x ,y² + y ) における、これの既約グレブナー基底とすると、 定理 2.4 によれば、
G1 は GF( 2 ) [ x , y ] / ( x² + x , y² + y ) における x + y , x * y + y + x + 1 の既約グレブナー基底、
G2 は GF( 2 ) [ x , y ] / ( x² + x , y² + y ) における y +1 , x * y + x + 1 の既約グレブナー基底、
G3 は GF( 2 ) [ x , y ] / ( x² + x , y² + y ) における x * y + y , x * y + x の既約グレブナー基底
である. これを計算すると、それぞれ { y + 1 , x + 1 }、{ 1 }、{ y + x } になる. よって G = { ( 1 , 0 , 0 ) * ( y + 1 ) , ( 1 , 0 , 0 ) * ( x + 1 ) , ( 0 , 1 , 0 ) , ( 0 , 0 , 1 ) * ( y + x ) } とおくと、 G は求める既約グレブナー基底になる. このままでは G は正規ではないので、最大単項の同じものを１つに足し合わせて 正規グレブナー基底 { ( 1 , 0 , 1 ) * y + ( 0 , 0 , 1 ) * x + ( 1 , 0 , 0 ) , ( 1 , 0 , 0 ) * ( x + 1 ) , ( 0 , 1 , 0 ) } を得る. これの Φ による逆像 { ~{b} * y + ~{ a , b } * x + { a } , { a } * ( x + 1 ) , { b } } が最終的に求める 正規グレブナー基底である.