Basic Examples
Basic Examples
Create a set of polynomials:
In[]:=
polys={x^2+3*y-2*z^4+7,5*x^2*y*z-4*y^2*z^2+3,x^2+y^2+z^3-6};
First compute its Groebner basis:
In[]:=
gb1=GroebnerBasis[polys,{x,y,z}]
Out[]=
{9-1890z+1205+14820+2794-2756+6198-4256-607-130-2324+304+64+100+200,-174568722857469+32134376477706y+174412495017740z+1978174579982874+338799254181097-360676216949111+836357857920969-584758935888737-68963401625500-20615441826364-309573453014396+42730628534164+7055457141820+13177425497200+26562952946000,249548934638783+10711458825902-174412495017740z-1978174579982874-338799254181097+339253299297307-836357857920969+584758935888737+68963401625500+20615441826364+309573453014396-42730628534164-7055457141820-13177425497200-26562952946000}
2
z
3
z
4
z
5
z
6
z
7
z
8
z
9
z
10
z
11
z
12
z
13
z
14
z
2
z
3
z
4
z
5
z
6
z
7
z
8
z
9
z
10
z
11
z
12
z
13
z
2
x
2
z
3
z
4
z
5
z
6
z
7
z
8
z
9
z
10
z
11
z
12
z
13
z
Compute the extended Groebner basis:
In[]:=
{gb2,cmat}=[polys,{x,y,z}]
Out[]=
{{9-1890z+1205+14820+2794-2756+6198-4256-607-130-2324+304+64+100+200,-174568722857469+32134376477706y+174412495017740z+1978174579982874+338799254181097-360676216949111+836357857920969-584758935888737-68963401625500-20615441826364-309573453014396+42730628534164+7055457141820+13177425497200+26562952946000,249548934638783+10711458825902-174412495017740z-1978174579982874-338799254181097+339253299297307-836357857920969+584758935888737+68963401625500+20615441826364+309573453014396-42730628534164-7055457141820-13177425497200-26562952946000},{{-45z-15yz+113+975y-400+1140-60y-60+208-48y-225-75y+580-170y+50-136-32-100,3-435z+80yz-88+12y+15+64-10y+8,45z-113+1200y-1140+500y-208+48y+225-580-150y+136-40y+32+100},{15926908215185z+130275989040585yz-53557294129510z+152243446089993-10043547678483y-7197744002550+25622276783275-5152326625065y-348165578250-28479789034230-9872664025320y-26012743950+78251351237524-22578510004100y+6640738236500-19588443609652-3553741314860+52025487900-13281476473000,-58189574285823+10711458825902y-10879103926555z+1439548800510yz-330073062345+69633115650y+1903218666174+5202548790y+8495982903688-1328147647300y+1062518117840,-15926908215185z+160671882388530yz-152243446089993+64439067311258y-25622276783275+6802691936790y+28479789034230+356570694450y-78251351237524-19901404514340y+19588443609652-5312590589200y+3553741314860-52025487900+13281476473000},{10711458825902-15926908215185z-130275989040585yz+53557294129510z-152243446089993+10043547678483y+7197744002550-25622276783275+5152326625065y+348165578250+28479789034230+9872664025320y+26012743950-78251351237524+22578510004100y-6640738236500+19588443609652+3553741314860-52025487900+13281476473000,58189574285823-10711458825902y+10879103926555z-1439548800510yz+330073062345-69633115650y-1903218666174-5202548790y-8495982903688+1328147647300y-1062518117840,15926908215185z-160671882388530yz+152243446089993-64439067311258y+25622276783275-6802691936790y-28479789034230-356570694450y+78251351237524+19901404514340y-19588443609652+5312590589200y-3553741314860+52025487900-13281476473000}}}
2
z
3
z
4
z
5
z
6
z
7
z
8
z
9
z
10
z
11
z
12
z
13
z
14
z
2
z
3
z
4
z
5
z
6
z
7
z
8
z
9
z
10
z
11
z
12
z
13
z
2
x
2
z
3
z
4
z
5
z
6
z
7
z
8
z
9
z
10
z
11
z
12
z
13
z
2
z
2
z
2
y
2
z
3
z
3
z
2
y
3
z
4
z
4
z
5
z
5
z
6
z
6
z
2
y
6
z
7
z
8
z
10
z
2
z
2
z
4
z
5
z
5
z
6
z
2
z
2
z
3
z
3
z
4
z
4
z
5
z
6
z
6
z
7
z
7
z
8
z
10
z
2
y
2
z
2
z
2
y
2
z
3
z
3
z
2
y
3
z
4
z
4
z
2
y
4
z
5
z
5
z
2
y
5
z
6
z
7
z
8
z
9
z
2
z
2
z
3
z
3
z
4
z
4
z
5
z
2
z
2
z
3
z
3
z
4
z
4
z
5
z
5
z
6
z
6
z
7
z
8
z
9
z
2
y
2
z
2
z
2
y
2
z
3
z
3
z
2
y
3
z
4
z
4
z
2
y
4
z
5
z
5
z
2
y
5
z
6
z
7
z
8
z
9
z
2
z
2
z
3
z
3
z
4
z
4
z
5
z
2
z
2
z
3
z
3
z
4
z
4
z
5
z
5
z
6
z
6
z
7
z
8
z
9
z
Check that the bases agree up to a constant factor:
In[]:=
Together[gb1/gb2]
Out[]=
{1,1,1}
Check the conversion matrix identity:
In[]:=
Expand[cmat.polys-gb2]
Out[]=
{0,0,0}
Scope
Scope
Here is a larger example:
In[]:=
polys={x^2+3*y-2*z^4+7,-x^3*z+5*x^2*y^2*z-4*y^2*z^3+3,x^3+y^3+2*z^3-6};gb1=GroebnerBasis[polys,{x,y,z},MonomialOrderDegreeReverseLexicographic]
Out[]=
{-6+++2,-7--3y+2,10++3y-6z+5z+z-4,-6-10x-3xy+35+5+16+6xz-30z-xz+5z+2+4x,210+30+90y+56-150x-167-11-80-15+25x-40z-4z-12yz+24+140+56-100-10-30y+50x,35670-3200x-240+31830y+300xy+150y+25752-31189-7077+750x-27005-5065-6025-8700+625+1070z-600xz+1032z-304yz+260yz-120z-7000xz-2900xz-192+3250x-600+240y+750xy+14630+17502+4760-16900+830-13010y-50y-2400-800x+250x}
3
x
3
y
3
z
2
x
4
z
2
x
2
x
2
y
3
y
2
y
3
z
2
y
2
x
2
y
3
y
2
y
3
y
5
y
3
z
2
y
3
z
2
x
2
y
2
y
2
x
2
y
3
y
2
x
3
y
4
y
5
y
2
x
2
z
2
y
2
z
3
y
2
z
3
z
2
x
3
z
3
z
2
y
3
z
2
x
2
x
2
y
2
x
2
y
3
y
3
y
2
x
3
y
4
y
2
x
4
y
5
y
8
y
2
x
2
x
2
y
2
y
3
y
2
z
2
z
2
x
2
z
2
z
2
z
2
y
2
z
3
y
2
z
4
y
2
z
3
z
2
x
3
z
3
z
2
x
3
z
2
y
3
z
2
y
3
z
3
y
3
z
In[]:=
{gb2,cmat}=[polys,{x,y,z},MonomialOrderDegreeReverseLexicographic]
Out[]=
{{-6+++2,-7--3y+2,10++3y-6z+5z+z-4,-6-10x-3xy+35+5+16+6xz-30z-xz+5z+2+4x,210+30+90y+56-150x-167-11-80-15+25x-40z-4z-12yz+24+140+56-100-10-30y+50x,71340-6400x-480+63660y+600xy+300y+51504-62378-14154+1500x-54010-10130-12050-17400+1250+2140z-1200xz+2064z-608yz+520yz-240z-14000xz-5800xz-384+6500x-1200+480y+1500xy+29260+35004+9520-33800+1660-26020y-100y-4800-1600x+500x},{{0,0,1},{-1,0,0},{1,1,z},{-x+5,-x,1-xz+5z},{30+8-25-5-4z+20-10,-4z-10,25x-4-10},{13770+200x-1500-625+4800y-1128-8750+1250-2135-3750-800+64z+200z-80yz-2000xz+500x+4180-1000+3200-4590+500-1600y,3750+400x-625-625+564z+200z-80yz+1000x-4590+500-1600y,6050+1500x+625+1875y-7500-1250+1250+200xz-625z+3125z+64+200-80y+500x-5000-4590+500-1600y}}}
3
x
3
y
3
z
2
x
4
z
2
x
2
x
2
y
3
y
2
y
3
z
2
y
2
x
2
y
3
y
2
y
3
y
5
y
3
z
2
y
3
z
2
x
2
y
2
y
2
x
2
y
3
y
2
x
3
y
4
y
5
y
2
x
2
z
2
y
2
z
3
y
2
z
3
z
2
x
3
z
3
z
2
y
3
z
2
x
2
x
2
y
2
x
2
y
3
y
3
y
2
x
3
y
4
y
2
x
4
y
5
y
8
y
2
x
2
x
2
y
2
y
3
y
2
z
2
z
2
x
2
z
2
z
2
z
2
y
2
z
3
y
2
z
4
y
2
z
3
z
2
x
3
z
3
z
2
x
3
z
2
y
3
z
2
y
3
z
3
y
3
z
2
y
2
y
2
y
2
x
2
y
3
y
2
y
2
z
3
z
3
z
2
y
2
z
4
z
2
x
3
x
2
y
2
x
2
y
4
x
2
y
3
y
2
x
3
y
4
y
2
x
2
y
2
z
2
y
2
z
2
x
2
y
2
z
3
y
2
z
3
z
2
x
3
z
3
z
3
x
3
y
2
x
2
z
3
z
2
x
3
z
3
z
2
x
2
y
3
x
2
y
5
y
3
x
2
x
2
y
2
z
2
x
2
z
2
z
3
z
2
y
3
z
4
z
2
x
4
z
4
z
Check that the bases agree up to constant factors (they are not identical in this instance):
In[]:=
Together[gb1/gb2]
Out[]=
1,1,1,1,1,
1
2
Check the conversion matrix identity:
In[]:=
Expand[cmat.polys-gb2]
Out[]=
{0,0,0,0,0,0}
Properties and Relations
Properties and Relations
The Groebner basis of a pair of univariate polynomials is their greatest common divisor, and similarly the extended Groebner basis gives the extended GCD. Create a pair of polynomials with a known common divisor :
poly1
In[]:=
randomPoly[deg_,x_,cmax_]:=x^deg+RandomInteger[{-cmax,cmax},deg].x^Range[0,deg-1]SeedRandom[1234]poly1=randomPoly[4,x,9];poly2=randomPoly[4,x,9];poly3=randomPoly[4,x,9];poly12=Expand[poly1*poly2];poly13=Expand[poly1*poly3];polys={poly12,poly13};
Compute the extended GCD:
In[]:=
{gcd,mat}=[polys]
Out[]=
{{-2046672-2046672x-2302506+1790838+255834},{{33605+2090x+10913-3969,-1858+19757x+28777+3969}}}
2
x
3
x
4
x
2
x
3
x
2
x
3
x
Check that the single polynomial in the Groebner basis is a GCD (a constant multiple of ):
poly1
In[]:=
Together[gcd[[1]]/poly1]
Out[]=
255834
Check the Bezout relation for the extended GCD:
In[]:=
Expand[mat.polys-gcd]
Out[]=
{0}
Compare to :
In[]:=
{gcd2,vec}=PolynomialExtendedGCD[poly12,poly13,x]
Out[]=
-8-8x-9+7+,,
2
x
3
x
4
x
302445+18810x+98217-35721
2
x
3
x
2302506
-16722+177813x+258993+35721
2
x
3
x
2302506
Again check the Bezout relation:
In[]:=
Expand[vec.polys-gcd2]
Out[]=
0
Now check that these two computations agree up to a constant factor:
In[]:=
Together[{gcd,mat[[1]]}/{gcd2,vec}]
Out[]=
{{255834},{255834,255834}}
Possible Issues
Possible Issues