Computing GR Obner Bases - A Short Overview

Computing Gröbner Bases – a short overview
Christian Eder, Jean-Charles Faugère,

Fayssal Martani, John Perry and Bjarke Hammersholt Roune
Seminar of the CARAMEL Team in Nancy, France
September 11, 2014
1 / 57
Preliminaries
Conventions
I R = K [x1 , . . . , xn ], K field, < well-ordering on Mon(x1 , . . . , xn )
I f ∈ R can be represented in a unique way by <.

⇒ Definitions as lc (f ), lm(f ), and lt(f ) make sense.
I An ideal I in R is an additive subgroup of R such that for f ∈ I,

g ∈ R it holds that fg ∈ I.
I G = {g1 , . . . , gs } ⊂ R is a Gröbner basis for I = hf1 , . . . , fm i

w.r.t. <
:⇐⇒
G ⊂ I and L< (G) = L< (I )
2 / 57
Buchberger’s criterion
S-polynomials
Let f 6= 0, g 6= 0 ∈ R and let λ = lcm (lt (f ) , lt (g )) be the least common
multiple of lt (f ) and lt (g ). The S-polynomial between f and g is given
by
λ λ
spol (f , g ) ..= f− g.
lt (f ) lt (g )
3 / 57
Buchberger’s criterion
S-polynomials
Let f 6= 0, g 6= 0 ∈ R and let λ = lcm (lt (f ) , lt (g )) be the least common
multiple of lt (f ) and lt (g ). The S-polynomial between f and g is given
by
λ λ
spol (f , g ) ..= f− g.
lt (f ) lt (g )
Buchberger’s criterion [5]

Let I = hf1 , . . . , fm i be an ideal in R . A finite subset G ⊂ R is a
G
Gröbner basis for I if G ⊂ I and for all f , g ∈ G : spol (f , g ) −
→ 0.
3 / 57
Buchberger’s algorithm
Input: Ideal I = hf1 , . . . , fm i

Output: Gröbner basis G for I
1. G ← 0/
2. G ← G ∪ {fi } for all i ∈ {1, . . . , m}
3. Set P ← {spol (fi , fj ) | fi , fj ∈ G, i > j }
4 / 57

1. G ← 0/
2. G ← G ∪ {fi } for all i ∈ {1, . . . , m}
4. Choose p ∈ P, P ← P \ {p}
4 / 57

1. G ← 0/
2. G ← G ∪ {fi } for all i ∈ {1, . . . , m}
4. Choose p ∈ P, P ← P \ {p}
G
(a) If p −
→ 0 II no new information
Go on with the next element in P.
G
(b) If p −
→ q 6= 0 II new information
Build new S-pair with q and add them to P.
Add q to G.
5. When P = 0/ we are done and G is a Gröbner basis for I.
4 / 57
How to improve computations?
I Modular computations (modStd et al.)
I Predict zero reductions (Buchberger, Gebauer-Möller,

Möller-Mora-Traverso, Faugère.)
I Sort pair set (Buchberger, Giovini et al., Möller et al.)
I Homogenize: d-Gröbner bases
I Change of ordering (FGLM, Gröbner Walk)
I Linear Algebra: Gaussian Elimination (Lazard, Faugère)
I Sparse Gröbner Bases: Use sparsity and exploit Newton polygons

(Faugère, Spaenlehauer, Svartz)
I ...
5 / 57
How to improve computations?
I Predict zero reductions (Buchberger, Gebauer-Möller,

Möller-Mora-Traverso, Faugère.)
I Linear Algebra: Gaussian Elimination (Lazard, Faugère)
5 / 57
1 Predicting zero reductions
2 Fast linear algebra for computing Gröbner bases
6 / 57
How to detect zero reductions in advance?
Let I = hg1 , g2 i ∈ Q[x , y , z ] and let < denote the reverse lexicographical
ordering. Let
g1 = xy − z2 , g2 = y2 − z2
7 / 57
ordering. Let
g1 = xy − z2 , g2 = y2 − z2
spol(g2 , g1 ) = xg2 − yg1 = xy2 − xz 2 − xy2 + yz 2

= −xz 2 + yz 2 .
=⇒ g3 = xz2 − yz2 .
7 / 57
ordering. Let
g1 = xy − z2 , g2 = y2 − z2

= −xz 2 + yz 2 .
=⇒ g3 = xz2 − yz2 .
spol(g3 , g1 ) = xyz2 − y 2 z 2 − xyz2 + z 4 = −y 2 z 2 + z 4 .
7 / 57
ordering. Let
g1 = xy − z2 , g2 = y2 − z2

= −xz 2 + yz 2 .
=⇒ g3 = xz2 − yz2 .
spol(g3 , g1 ) = xyz2 − y 2 z 2 − xyz2 + z 4 = −y 2 z 2 + z 4 .
We can reduce further using z 2 g2 :
−y 2 z 2 + z 4 + y 2 z 2 − z 4 = 0.
7 / 57
Can we see something? How are the generators of the S-polynomials related
to each other?
8 / 57
to each other?
spol(g3 , g2 ) = y2 xz 2 − yz 2 − xz2 y 2 − z 2

= lt (g2 )g3 − lt (g3 )g2

= lt (g2 )lot (g3 ) − lt (g3 )lot (g2 )
8 / 57
to each other?

= lt (g2 )g3 − lt (g3 )g2

= lt (g2 )lot (g3 ) − lt (g3 )lot (g2 )
For all u ∈ support (lot (g3 )) we can reduce with ug2 :
=⇒ lt (g2 ) lot (g3 ) − g2 lot (g3 ) − lt (g3 ) lot (g2 )

= − lot (g2 ) lot (g3 ) − lt (g3 ) lot (g2 )
= − g3 lot (g2 ) .
8 / 57
to each other?

= lt (g2 )g3 − lt (g3 )g2

= lt (g2 )lot (g3 ) − lt (g3 )lot (g2 )
For all u ∈ support (lot (g3 )) we can reduce with ug2 :
=⇒ lt (g2 ) lot (g3 ) − g2 lot (g3 ) − lt (g3 ) lot (g2 )

= − lot (g2 ) lot (g3 ) − lt (g3 ) lot (g2 )
= − g3 lot (g2 ) .
So we can reduce this to zero by vg3 for all v ∈ support (lot (g2 )).
8 / 57
Buchberger’s criteria
Product criterion [6, 7]

{f ,g }
If lcm (lt (f ) , lt (g )) = lt (f ) lt (g ) then spol (f , g ) −
−−→ 0.
9 / 57

{f ,g }
−−→ 0.
Couldn’t we remove spol (g3 , g2 ) in a different way?
9 / 57

{f ,g }
−−→ 0.
lt (g1 ) = xy | xy 2 z 2 = lcm (lt (g3 ) , lt (g2 ))
9 / 57

{f ,g }
−−→ 0.
=⇒ We can rewrite spol (g3 , g2 ):

spol (g3 , g2 ) = y spol (g3 , g1 ) −z 2 spol (g2 , g1 ) = y yg3 − z 2 g1 − z 2 (xg2 − yg1 )

| {z } | {z }
G G
−
→0 −
→−g3
9 / 57

{f ,g }
−−→ 0.
=⇒ We can rewrite spol (g3 , g2 ):

spol (g3 , g2 ) = y spol (g3 , g1 ) −z 2 spol (g2 , g1 ) = y yg3 − z 2 g1 − z 2 (xg2 − yg1 )

| {z } | {z }
G G
−
→0 −
→−g3
Standard representations of spol (g2 , g1 ) and spol (g3 , g1 )

=⇒ Standard representation of spol (g3 , g2 ).
9 / 57
Chain criterion [8]

Let f , g , h ∈ R , G ⊂ R finite. If
1. lt (h) | lcm (lt (f ) , lt (g )), and
2. spol (f , h) and spol (h, g ) have a standard representation w.r.t. G
respectively,
then spol (f , g ) has a standard representation w.r.t. G.
10 / 57
Chain criterion [8]

respectively,
Note
Do not remove too much information! If λ = 1 and
spol (f , g ) = λ spol (f , h) + σ spol (h, g ) ,
then we can remove spol (f , g ) or spol (f , h) but not both!
10 / 57
Chain criterion [8]

respectively,
Note
Do not remove too much information! If λ = 1 and
spol (f , g ) = λ spol (f , h) + σ spol (h, g ) ,
then we can remove spol (f , g ) or spol (f , h) but not both!
How to combine Product and Chain criterion?
10 / 57
Gebauer-Möller installation [32]
We add a new element h to G and generate new pairs P 0 := {(f , h) | f ∈ G}.
11 / 57
We update the pairs in 4 steps:
11 / 57
1. If (f , g ) ∈ P s.t.
. lt (h) | lcm (lt (f ) , lt (g )),
. lcm (lt (f ) , lt (h)) 6= lcm (lt (f ) , lt (g )),
. lcm (lt (g ) , lt (h)) 6= lcm (lt (f ) , lt (g ))
=⇒ Remove (f , g ) from P. [P done]
11 / 57
1. If (f , g ) ∈ P s.t.
. lt (h) | lcm (lt (f ) , lt (g )),
2. Fix (f , h) ∈ P 0 . If (g , h) ∈ P 0 \ {(f , h)} s.t.
. ∃ λ > 1 and lcm (lt (f ) , lt (h)) = λ lcm (lt (g ) , lt (h))
=⇒ Remove (g , h) from P 0 .
11 / 57
1. If (f , g ) ∈ P s.t.
. lt (h) | lcm (lt (f ) , lt (g )),
. lcm (lt (f ) , lt (h)) = lcm (lt (g ) , lt (h))
=⇒ Remove (g , h) from P 0 . [Chain criterion done]
11 / 57
1. If (f , g ) ∈ P s.t.
. lt (h) | lcm (lt (f ) , lt (g )),
. lcm (lt (f ) , lt (h)) = lcm (lt (g ) , lt (h))
=⇒ Remove (g , h) from P 0 . [Chain criterion done]
4. If (f , h) ∈ P 0 s.t. lcm (lt (f ) , lt (h)) = lt (f ) lt (h)

=⇒ Remove (f , h) from P 0 . [Product criterion done]
11 / 57
Can we do even better?
In our example we still need to consider
G
spol (g3 , g1 ) −
→ 0.
12 / 57
G
spol (g3 , g1 ) −
→ 0.
How to get rid of this useless computation?
12 / 57
G
spol (g3 , g1 ) −
→ 0.
How to get rid of this useless computation?
Use more structure of I =⇒ Signatures
12 / 57
Signatures
Let I = hf1 , . . . , fm i ⊂ R .
Idea: Give each f ∈ I a bit more structure:
13 / 57
Signatures
Let I = hf1 , . . . , fm i ⊂ R .
1. Let R m be generated by e1 , . . . , em and let ≺ be a compatible monomial
order on the monomials of R m .
13 / 57
Signatures
Let I = hf1 , . . . , fm i ⊂ R .
2. Let α 7→ α : R m → R such that ei = fi for all i.
13 / 57
Signatures
Let I = hf1 , . . . , fm i ⊂ R .
3. Each f ∈ I can be represented via some α ∈ R m : f = α
13 / 57
Signatures
Let I = hf1 , . . . , fm i ⊂ R .
4. A signature of f is given by s(f ) = lt≺ (α) where f = α .
13 / 57
Signatures
Let I = hf1 , . . . , fm i ⊂ R .
4. A signature of f is given by s(f ) = lt≺ (α) where f = α .
5. An element α ∈ R m such that α = 0 is called a syzygy.
13 / 57
Our example again – with signatures and ≺pot
g1 = xy − z 2 , s(g1 ) = e1 ,
g2 = y 2 − z 2 , s(g2 ) = e2 .
14 / 57
g1 = xy − z 2 , s(g1 ) = e1 ,
g2 = y 2 − z 2 , s(g2 ) = e2 .
g3 = spol(g2 , g1 ) = xg2 − yg1

⇒ s(g3 ) = x s(g2 ) = xe2 .
14 / 57
g1 = xy − z 2 , s(g1 ) = e1 ,
g2 = y 2 − z 2 , s(g2 ) = e2 .
g3 = spol(g2 , g1 ) = xg2 − yg1

⇒ s(g3 ) = x s(g2 ) = xe2 .
spol(g3 , g1 ) = yg3 − z 2 g1
⇒ s (spol(g3 , g1 )) = y s(g3 ) = xye2 .
14 / 57
g1 = xy − z 2 , s(g1 ) = e1 ,
g2 = y 2 − z 2 , s(g2 ) = e2 .
g3 = spol(g2 , g1 ) = xg2 − yg1

⇒ s(g3 ) = x s(g2 ) = xe2 .
spol(g3 , g1 ) = yg3 − z 2 g1
⇒ s (spol(g3 , g1 )) = y s(g3 ) = xye2 .
Note that s (spol(g3 , g1 )) = xye2 and lm(g1 ) = xy .
14 / 57
Think in the module
α ∈ R m =⇒ polynomial α with lt (α), signature s(α) = lt (α)
15 / 57
Think in the module
S-pairs/S-polynomials:

spol α, β = aα − bβ =⇒ spair (α, β ) = aα − bβ
15 / 57
Think in the module

s-reductions:
γ − d δ =⇒ γ − d δ
15 / 57
Think in the module

s-reductions:
γ − d δ =⇒ γ − d δ
Remark
In the following we need one detail from signature-based Gröbner Ba-
sis computations:
We pick from P by increasing signature.
15 / 57
Signature-based criteria
s(α) = s(β ) =⇒ Compute 1, remove 1.
16 / 57
s(α) = s(β ) =⇒ Compute 1, remove 1.
Sketch of proof
1. s(α − β ) ≺ s(α), s(β ).

2. All S-pairs are handled by increasing signature.
⇒ All relatons ≺ s(α) are known:
α = β + elements of smaller signature
16 / 57
S-pairs in signature T
17 / 57
What are all possible

configurations to reach
signature T ?
17 / 57
n o
RT = aα | α handled by the algorithm and s(aα) = T
What are all possible

configurations to reach
signature T ?
17 / 57
n o
What are all possible Define an order on RT

configurations to reach and choose the maximal
signature T ? element.
17 / 57
Special cases
n o
18 / 57
Special cases
n o
Choose bβ to be an element of RT maximal w.r.t. an order E.
18 / 57
Special cases
n o
1. If bβ is a syzygy =⇒ Go on to next signature.
18 / 57
Special cases
n o

2. If bβ is not part of an S-pair =⇒ Go on to next signature.
18 / 57
Special cases
n o

2. If bβ is not part of an S-pair =⇒ Go on to next signature.
Revisiting our example with ≺pot
) s (spol(g3 , g1 )) = xye2
g1 = xy − z 2
⇒ psyz(g2 , g1 ) = g1 e2 − g2 e1 = xye2 + . . .
g2 = y 2 − z 2
18 / 57
Modifications not specific to
signature-based Gröbner ba- involutive bases
sis algorithms [33, 34] TRB
(2013)
F5GEN [35]
[37, 38] (2010)
quasi- (2013)
homogeneous
case Extended GBGC
[20] F5 Criteria
(2013) [4] [41]
(2010) (2011)
SSG
bihomogeneous
F5” [25]
case
[17] (2012)
[19] SBA
(2002)
(2010) [16]
AP SB
(2013)
[2] [39]
MatrixF5
(2009) (2012)
[18]
(2003)
GVW(v1) GVW(HS)
F4/5
[1]
F5 [27] [28, 43]
(2010) (2011)
(2010) [17] on
solvable
(2002) alge-
SAGBI Gröbner
bras
bases
globally iG2V [42]
[24] G2V (2012)
invariant [10]
(2009) [26] (2012)
(group
(2010)
action)
[22]
(2012)
F5t iF5A
F5’ F5A iF5C
[30, 31] [10]
F5B [17] [15] (2012) [10]
(2009) (2011) (2012)
[3] (2002)
(2005) F5/2
[18]
invariant
(2003)
(group
action) F5R F5C
[23] F5+ [40] [14]
(2013) (2005) (2009)
[13]
(2011)
Variants covered by
the survey
19 / 57
# zero reductions (Singular-4-0-0, F32003 )
Benchmark STD SBA ≺pot SBA ≺d-pot SBA ≺lt

cyclic-8 4,284 243 243 671
cyclic-8-h 5,843 243 243 671
eco-11 3,476 0 749 749
eco-11-h 5,429 502 502 749
katsura-11 3,933 0 0 348
katsura-11-h 3,933 0 0 348
noon-9 25,508 0 0 682
noon-9-h 25,508 0 0 682
Random(11, 2, 2) 6,292 0 0 590
HRandom(11, 2, 2) 6,292 0 0 590
Random(12, 2, 2) 13,576 0 0 1,083
HRandom(12, 2, 2) 13,576 0 0 1,083
20 / 57
Time in seconds (Singular-4-0-0, F32003 )
Benchmark STD SBA ≺pot SBA ≺d-pot SBA ≺lt

cyclic-8 32.480 44.310 100.780 38.120
cyclic-8-h 38.300 35.770 98.440 32.640
eco-11 28.450 3.450 27.360 13.270
eco-11-h 20.630 11.600 14.840 7.960
katsura-11 54.780 35.720 31.010 11.790
katsura-11-h 51.260 34.080 32.590 17.230
noon-9 29.730 12.940 14.620 15.220
noon-9-h 34.410 17.850 20.090 20.510
Random(11, 2, 2) 267.810 77.430 130.400 28.640
HRandom(11, 2, 2) 22.970 14.060 39.320 3.540
Random(12, 2, 2) 2,069.890 537.340 1,062.390 176.920
HRandom(12, 2, 2) 172.910 112.420 331.680 22.060
21 / 57
Can we combine both attempts?
Buchberger’s Product and Chain criterion can be combined with the Rewrite
criterion [29, 33, 11]:
22 / 57
criterion [29, 33, 11]:
Chain criterion is a special case of the Rewrite criterion

⇒ already included.
22 / 57
criterion [29, 33, 11]:

Product criterion is not always (but mostly) included.
22 / 57
criterion [29, 33, 11]:

α added to G
H
Generate all possible
principal syzygies with α .
(e.g. GVW)
22 / 57
criterion [29, 33, 11]:

α added to G S-pair fulfilling Product criterion

H not detected by Rewrite criterion
Generate all possible H
principal syzygies with α . Add one corresponding syzygy.
(e.g. GVW) (e.g. SBA in Singular)
22 / 57
Experimental results
Implementation done in Singular [9]
STD SBA ≺pot SBA ≺lt
Benchmark
ZR ZR ZR ZR / PC
cyclic-8 4284 243 671 671 / 0
cyclic-8-h 5843 243 671 671 / 0
eco-11 3476 0 749 749 / 0
eco-11-h 5429 502 749 718 / 0
katsura-11 3933 0 348 304 / 0
katsura-11-h 3933 0 348 304 / 0
noon-9 25508 0 682 646 / 0
noon-9-h 25508 0 682 646 / 0
binomial-6-2 21 6 15 8/7
binomial-6-3 20 13 15 9/6
binomial-7-3 27 24 21 21 / 0
binomial-7-4 41 16 19 16 / 3
binomial-8-3 53 23 27 27 / 0
binomial-8-4 40 31 26 26 / 0
23 / 57
And what’s about SBA using ≺pot ?
Conjecture [11]
Every S-polynomial fulfilling the Product criterion is also detected by
the Rewrite criterion in SBA using ≺pot .
24 / 57
Conjecture [11]
I We checked several million examples, all fulfilling the conjecture.

I Until now we cannot prove this.
24 / 57
Conjecture [11]
I We checked several million examples, all fulfilling the conjecture.

I Until now we cannot prove this.
Ongoing work:
1. Describe in detail the connection between our conjecture
and Moreno-Socı́as conjecture [36].
2. Try to exploit even more algebraic structures for predicting
zero reductions.
24 / 57
1 Predicting zero reductions
2 Fast linear algebra for computing Gröbner bases
25 / 57
Buchberger’s algorithm - revisited

1. G ← 0/
2. G ← G ∪ {fi } for all i ∈ {1, . . . , m}
4. Choose p ∈ P, P ← P \ {p}
G
(a) If p −
→ 0 II no new information
G
(b) If p −
→ q 6= 0 II new information
Build new S-pair with q and add them to P.
Add q to G.
5. When P = 0/ we are done and G is a Gröbner basis for I.
26 / 57
Faugère’s F4 algorithm
1. G ← 0/
2. G ← G ∪ {fi } for all i ∈ {1, . . . , m}
3. Set P ← {(af , bg ) | f , g ∈ G}
4. d ← 0
5. while P 6= 0/ :
27 / 57
Faugère’s F4 algorithm
1. G ← 0/
2. G ← G ∪ {fi } for all i ∈ {1, . . . , m}
3. Set P ← {(af , bg ) | f , g ∈ G}
4. d ← 0
5. while P 6= 0/ :
(a) d ← d + 1
(b) Pd ← Select (P ), P ← P \ Pd
(c) Ld ← {af , bg | (af , bg ) ∈ Pd }
(d) Ld ← Symbolic Preprocessing(Ld , G)
(e) Fd ← Reduction(Ld , G)
(f) for h ∈ Fd :
I If lt (h) ∈
/ L(G) (all other h are “useless”):
. P ← P ∪ {new pairs with h}
. G ← G ∪ {h}
6. Return G
27 / 57
Differences to Buchberger
1. Select a subset Pd of P, not only one element.

2. Do a symbolic preprocessing:
Search and store reducers, but do not reduce.
3. Do a full reduction of Pd at once:
Reduce a subset of R by a subset of R
28 / 57
Differences to Buchberger
1. Select a subset Pd of P, not only one element.

2. Do a symbolic preprocessing:
Search and store reducers, but do not reduce.
3. Do a full reduction of Pd at once:
Reduce a subset of R by a subset of R
If Select (P ) selects only 1 pair F4 is just Buchberger’s algorithm.

Usually one chooses the normal selection strategy,
i.e. all pairs of lowest degree.
28 / 57
Symbolic preprocessing
Input: L, G finite subsets of R

Output: a finite subset of R
1. F ← L
2. D ← L(F ) (S-pairs already reduce lead terms)
3. while T (F ) 6= D:
(a) Choose m ∈ T (F ) \ D, D ← D ∪ {m}.
(b) If m ∈ L(G) ⇒ ∃ g ∈ G and λ ∈ R such that λ lt (g ) = m
. F ← F ∪ {λ g }
4. Return F
29 / 57
Symbolic preprocessing

1. F ← L
2. D ← L(F ) (S-pairs already reduce lead terms)
3. while T (F ) 6= D:
(a) Choose m ∈ T (F ) \ D, D ← D ∪ {m}.
(b) If m ∈ L(G) ⇒ ∃ g ∈ G and λ ∈ R such that λ lt (g ) = m
. F ← F ∪ {λ g }
4. Return F
We optimize this soon!
29 / 57
Reduction

1. M ← Macaulay matrix of L
2. M ← Gaussian Elimination of M (Linear algebra)
3. F ← polynomials from rows of M
4. Return F
30 / 57
Reduction

1. M ← Macaulay matrix of L
2. M ← Gaussian Elimination of M (Linear algebra)
3. F ← polynomials from rows of M
4. Return F
Macaulay matrix
columns =ˆ monomials (sorted by monomial order <)
rows =
ˆ coeffs of polynomials in L
30 / 57
Example: Cyclic-4
R = Q[a, b, c , d ], < denotes DRL and we use the normal selection strategy
for Select (P ). I = hf1 , . . . , f4 i, where
f1 = abcd − 1,
f2 = abc + abd + acd + bcd ,
f3 = ab + bc + ad + cd ,
f4 = a + b + c + d .
31 / 57
Example: Cyclic-4
f1 = abcd − 1,
f3 = ab + bc + ad + cd ,
f4 = a + b + c + d .
We start with G = {f4 } and P1 = {(f3 , bf4 )}, thus L1 = {f3 , bf4 }.
31 / 57
Example: Cyclic-4
f1 = abcd − 1,
f3 = ab + bc + ad + cd ,
f4 = a + b + c + d .
Let us do symbolic preprocessing:
T (L1 ) = {ab, b2 , bc , ad , bd , cd }
L1 = {f3 , bf4 }
31 / 57
Example: Cyclic-4
f1 = abcd − 1,
f3 = ab + bc + ad + cd ,
f4 = a + b + c + d .
T (L1 ) = {ab, b2 , bc , ad , bd , cd }
L1 = {f3 , bf4 }
b2 ∈
/ L(G),
31 / 57
Example: Cyclic-4
f1 = abcd − 1,
f3 = ab + bc + ad + cd ,
f4 = a + b + c + d .
T (L1 ) = {ab, b2 , bc , ad , bd , cd }
L1 = {f3 , bf4 }
b2 ∈
/ L(G), bc ∈
/ L(G),
31 / 57
Example: Cyclic-4
f1 = abcd − 1,
f3 = ab + bc + ad + cd ,
f4 = a + b + c + d .
T (L1 ) = {ab, b2 , bc , ad , bd , cd , d 2 }
L1 = {f3 , bf4 , df4 }
b2 ∈
/ L(G), bc ∈
/ L(G), d lt (f4 ) = ad,
31 / 57
Example: Cyclic-4
f1 = abcd − 1,
f3 = ab + bc + ad + cd ,
f4 = a + b + c + d .
T (L1 ) = {ab, b2 , bc , ad , bd , cd , d 2 }
L1 = {f3 , bf4 , df4 }
b2 ∈
/ L(G), bc ∈
/ L(G), d lt (f4 ) = ad, all others also ∈
/ L(G),
31 / 57
Example: Cyclic-4
Now reduction:
Convert polynomial data L1 to Macaulay Matrix M1
ab b2 bc ad bd cd d 2
 
df4 0 0 0 1 1 1 1
 
 1
f3  0 1 1 0 1 0 

bf4 1 1 1 0 1 0 0
32 / 57
Example: Cyclic-4
Now reduction:
Convert polynomial data L1 to Macaulay Matrix M1
ab b2 bc ad bd cd d 2
 
df4 0 0 0 1 1 1 1
 
 1
f3  0 1 1 0 1 0 

bf4 1 1 1 0 1 0 0
Gaussian Elimination of M1 :
2
 ab b bc ad bd cd d2 
df4 0 0 0 1 1 1 1
 
f3  1 0 1 0 −1 0 −1 
 
 
bf4 0 1 0 0 2 0 1
32 / 57
Example: Cyclic-4
Convert matrix data back to polynomial structure F1 :
2
df4 0 0 0 1 1 1 1
 
f3  1 0 1 0 −1 0 −1 
 
 
bf4 0 1 0 0 2 0 1
 
 
F1 = ad + bd + cd + d 2 , ab + bc − bd − d 2 , b2 + 2bd + d 2
| {z }| {z }| {z }
f5 f6 f7
33 / 57
Example: Cyclic-4
Convert matrix data back to polynomial structure F1 :
2
df4 0 0 0 1 1 1 1
 
f3  1 0 1 0 −1 0 −1 
 
 
bf4 0 1 0 0 2 0 1
 
 
F1 = ad + bd + cd + d 2 , ab + bc − bd − d 2 , b2 + 2bd + d 2
| {z }| {z }| {z }
f5 f6 f7
lt (f5 ) , lt (f6 ) ∈ L(G), so
G ← G ∪ {f7 }.
33 / 57
Example: Cyclic-4
Next round:
G = {f4 , f7 }, P2 = {(f2 , bcf4 )} , L2 = {f2 , bcf4 } .
34 / 57
Example: Cyclic-4
Next round:
G = {f4 , f7 }, P2 = {(f2 , bcf4 )} , L2 = {f2 , bcf4 } .

We can simplify the computations:
lt (bcf4 ) = abc = lt (cf6 ) .
f6 possibly better reduced than f4 .(f6 is not in G!)
=⇒ L2 = {f2 , cf6 }
34 / 57
Example: Cyclic-4
Next round:
G = {f4 , f7 }, P2 = {(f2 , bcf4 )} , L2 = {f2 , bcf4 } .

=⇒ L2 = {f2 , cf6 }
Symbolic preprocessing:
T (L2 ) = {abc , bc 2 , abd , acd , bcd , cd 2 }

L2 = {f2 , cf6 , }
34 / 57
Example: Cyclic-4
Next round:
G = {f4 , f7 }, P2 = {(f2 , bcf4 )} , L2 = {f2 , bcf4 } .

=⇒ L2 = {f2 , cf6 }

L2 = {f2 , cf6 , }
bc 2 ∈
/ L(G),
34 / 57
Example: Cyclic-4
Next round:
G = {f4 , f7 }, P2 = {(f2 , bcf4 )} , L2 = {f2 , bcf4 } .

=⇒ L2 = {f2 , cf6 }

L2 = {f2 , cf6 , }
bc 2 ∈
/ L(G), abd = lt (bdf4 ), but also abd = lt (bf5 )!
34 / 57
Example: Cyclic-4
Next round:
G = {f4 , f7 }, P2 = {(f2 , bcf4 )} , L2 = {f2 , bcf4 } .

=⇒ L2 = {f2 , cf6 }

L2 = {f2 , cf6 , }
bc 2 ∈
/ L(G), abd = lt (bdf4 ), but also abd = lt (bf5 )!
Let us investigate this in more detail.
34 / 57
Interlude – Simplify
Idea
Try to replace u · f by a product (wv ) · g where vg corresponds to an
already computed row in the Gauss. Elim. of a previous matrix Mi .
⇒ Reuse rows that are reduced but not “in” G.
35 / 57
Idea
Input: monomial u, polynomial f , list F of old Fi (from Mi after Gauss. Elim.)

Output: product v · g replacing u · f
35 / 57
Idea
Input: monomial u, polynomial f , list F of old Fi (from Mi after Gauss. Elim.)

Output: product v · g replacing u · f
1. d ← current index in the F4 algorithm
2. D (u ) ← {list of divisors of u }
3. for w ∈ D (u )
(a) if ∃ j ∈ {1, . . . , d − 1} such that w · f corresponds to row in Mj
. ∃1 g ∈ Fj such that lt (g ) = lt (w · f )
. if w 6= u: Return Simplify wu , g , F (recursive call)
. else: Return 1 · g
4. else: Return u · f
35 / 57
Note
I Tries to reuse all rows from old matrices.

⇒ We need to keep them in memory.
I We also simplify generators of S-pairs, as we have done
in our example: (f2 , bcf4 ) =⇒ (f2 , cf6 ).
I One can also choose “better” reducers by other properties, not
only “last reduced one”.
I Without Simplify the F4 algorithm is rather slow.
36 / 57
Note
I Tries to reuse all rows from old matrices.

⇒ We need to keep them in memory.
I We also simplify generators of S-pairs, as we have done
in our example: (f2 , bcf4 ) =⇒ (f2 , cf6 ).
I One can also choose “better” reducers by other properties, not
only “last reduced one”.
I Without Simplify the F4 algorithm is rather slow.
In our example:
Choose bf5 as reducer, not bdf4 .
36 / 57
Example: Cyclic-4
Symbolic preprocessing - now with simplify:

L2 = {f2 , cf6 }
bc 2 ∈
/ L(G),
37 / 57
Example: Cyclic-4

L2 = {f2 , cf6 }
bc 2 ∈
/ L(G), abd = lt (bf5 ),
37 / 57
Example: Cyclic-4
T (L2 ) = {abc , bc 2 , abd , acd , bcd , cd 2 , b2 d , c 2 d }

L2 = {f2 , cf6 , bf5 }
bc 2 ∈
/ L(G), abd = lt (bf5 ),
37 / 57
Example: Cyclic-4
T (L2 ) = {abc , bc 2 , abd , acd , bcd , cd 2 , b2 d , c 2 d , . . . }

L2 = {f2 , cf6 , bf5 , cf5 , df7 }
bc 2 ∈
/ L(G), abd = lt (bf5 ), and so on.
37 / 57
Example: Cyclic-4
T (L2 ) = {abc , bc 2 , abd , acd , bcd , cd 2 , b2 d , c 2 d , . . . }

L2 = {f2 , cf6 , bf5 , cf5 , df7 }
bc 2 ∈
/ L(G), abd = lt (bf5 ), and so on.
Now try to exploit the special structure of the Macaulay matrices.
37 / 57
Improve Gaussian Elimination
Use Linear Algebra for reduction steps in GB computations.
38 / 57
1 3 0 0 7 1 0
1 0 4 1 0 0 5
0 1 6 0 8 0 1
0 5 0 0 0 2 0
0 0 0 0 1 3 1
38 / 57
1 3 0 0 7 1 0
1 0 4 1 0 0 5
0 1 6 0 8 0 1
0 5 0 0 0 2 0
0 0 0 0 1 3 1
Knowledge of underlying GB structure
38 / 57
1 3 0 0 7 1 0
S-pair
1 0 4 1 0 0 5
0 1 6 0 8 0 1
S-pair
0 5 0 0 0 2 0
reducer 0 0 0 0 1 3 1
38 / 57
1 3 0 0 7 1 0
S-pair
1 0 4 1 0 0 5
0 1 6 0 8 0 1
S-pair
0 5 0 0 0 2 0
reducer 0 0 0 0 1 3 1
38 / 57
1 3 0 0 7 1 0
S-pair
1 0 4 1 0 0 5
0 1 6 0 8 0 1
S-pair
0 5 0 0 0 2 0
reducer 0 0 0 0 1 3 1
Idea
Do a static reordering before the Gaussian Elimination to achieve a
better initial shape. Reorder afterwards.
38 / 57
Faugère-Lachartre Idea
1st step: Sort pivot and non-pivot columns
1 3 0 0 7 1 0
1 0 4 1 0 0 5
0 1 6 0 8 0 1
0 5 0 0 0 2 0
0 0 0 0 1 3 1
39 / 57
1 3 0 0 7 1 0
1 0 4 1 0 0 5
0 1 6 0 8 0 1
0 5 0 0 0 2 0
0 0 0 0 1 3 1
Pivot column
39 / 57
1 3 0 0 7 1 0
1 0 4 1 0 0 5
0 1 6 0 8 0 1
0 5 0 0 0 2 0
0 0 0 0 1 3 1
Pivot column
39 / 57
1 3 0 0 7 1 0
1 0 4 1 0 0 5
0 1 6 0 8 0 1
0 5 0 0 0 2 0
0 0 0 0 1 3 1
Pivot column Non-Pivot column
39 / 57
1 3 0 0 7 1 0
1 0 4 1 0 0 5
0 1 6 0 8 0 1
0 5 0 0 0 2 0
0 0 0 0 1 3 1
39 / 57
1 3 0 0 7 1 0 1 3 7 0 0 1 0
1 0 4 1 0 0 5 1 0 0 4 1 0 5
0 1 6 0 8 0 1 0 1 8 6 0 0 9
0 5 0 0 0 2 0 0 5 0 0 0 2 0
0 0 0 0 1 3 1 0 0 1 0 0 3 1
39 / 57
2nd step: Sort pivot and non-pivot rows
1 3 7 0 0 1 0
1 0 0 4 1 0 5
0 1 8 6 0 0 9
0 5 0 0 0 2 0
0 0 1 0 0 3 1
40 / 57
1 3 7 0 0 1 0
1 0 0 4 1 0 5
0 1 8 6 0 0 9
0 5 0 0 0 2 0
0 0 1 0 0 3 1
Pivot row
40 / 57
1 3 7 0 0 1 0
1 0 0 4 1 0 5
0 1 8 6 0 0 9
0 5 0 0 0 2 0
0 0 1 0 0 3 1
Pivot row Non-Pivot row
40 / 57
1 3 7 0 0 1 0
1 0 0 4 1 0 5
0 1 8 6 0 0 9
0 5 0 0 0 2 0
0 0 1 0 0 3 1
40 / 57
1 3 7 0 0 1 0 1 0 0 4 1 0 5
1 0 0 4 1 0 5 0 5 0 0 0 2 0
0 1 8 6 0 0 9 0 0 1 0 0 3 1
0 5 0 0 0 2 0 1 3 7 0 0 1 0
0 0 1 0 0 3 1 0 1 8 6 0 0 9
40 / 57
3rd step: Reduce lower left part to zero
1 0 0 4 1 0 5
0 5 0 0 0 2 0
0 0 1 0 0 3 1
1 3 7 0 0 1 0
0 1 8 6 0 0 9
41 / 57
3rd step: Reduce lower left part to zero
1 0 0 4 1 0 5 1 0 0 4 1 0 5
0 5 0 0 0 2 0 0 5 0 0 0 2 0
0 0 1 0 0 3 1 0 0 1 0 0 3 1
1 3 7 0 0 1 0 0 0 0 7 10 3 10
0 1 8 6 0 0 9 0 0 0 6 0 2 1
41 / 57
4th step: Reduce lower right part
1 0 0 4 1 0 5
0 5 0 0 0 2 0
0 0 1 0 0 3 1
0 0 0 7 10 3 10
0 0 0 6 0 2 1
42 / 57
1 0 0 4 1 0 5 1 0 0 4 1 0 5
0 5 0 0 0 2 0 0 5 0 0 0 2 0
0 0 1 0 0 3 1 0 0 1 0 0 3 1
0 0 0 7 10 3 10 0 0 0 7 10 3 10
0 0 0 6 0 2 1 0 0 0 0 4 1 5
42 / 57
1 0 0 4 1 0 5 1 0 0 4 1 0 5
0 5 0 0 0 2 0 0 5 0 0 0 2 0
0 0 1 0 0 3 1 0 0 1 0 0 3 1
0 0 0 7 10 3 10 0 0 0 7 10 3 10
0 0 0 6 0 2 1 0 0 0 0 4 1 5
5th step: Remap columns of lower right part
42 / 57
How our matrices look like
Some data about the matrix:

I F4 computation of homogeneous K ATSURA -12, degree 6 matrix
43 / 57

I Size 137MB
43 / 57

I Size 137MB
I 24, 006, 869 nonzero elements (density: 5%)
43 / 57

I Size 137MB
I 24, 006, 869 nonzero elements (density: 5%)
I Dimensions:
full matrix: 21, 182 × 22, 207
upper-left: 17, 915 × 17, 915
lower-left: 3, 267 × 17, 915
upper-right: 17, 915 × 4, 292
lower-right: 3, 267 × 4, 292
43 / 57
How our matrices look like (2)
44 / 57
How our matrices look like (3)
44 / 57
Hybrid Matrix Multiplication A−1 B
45 / 57
Hybrid Matrix Multiplication A−1 B
46 / 57
Reduce C to zero
47 / 57
Gaussian Elimination on D
48 / 57
New information
49 / 57
First attempts
2010 – UPMC Paris 6, INRIA PolSys Team
Jean-Charles Faugère & Sylvain Lachartre – FL
2011 – University of Kaiserslautern

Bradford Hovinen – LELA
https://github.com/Singular/LELA
2012 – UPMC Paris 6, INRIA PolSys Team

Fayssal Martani – new implementation in LELA
https://github.com/martani/LELA
2012-2013 – University of Kaiserslautern

Bjarke Hammersholt Roune – MathicGB
https://github.com/broune/mathicgb
2012-2014 – University of Passau

Severin Neumann – parallelGBC
https://github.com/svrnm/parallelGBC
50 / 57
References I
[1] Albrecht, M. and Perry, J. F4/5. http://arxiv.org/abs/1006.4933, 2010.
[2] Arri, A. and Perry, J. The F5 Criterion revised. Journal of Symbolic Computation,
46(2):1017–1029, June 2011. Preprint online at arxiv.org/abs/1012.3664.
[3] Ars, G. Applications des bases de Gröbner à la cryptographie. PhD thesis, Université de
Rennes I, 2005.
[4] Ars, G. and Hashemi, A. Extended F5 Criteria. Journal of Symbolic Computation, MEGA
2009 special issue, 45(12):1330–1340, 2010.
[5] Buchberger, B. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes
nach einem nulldimensionalen Polynomideal. PhD thesis, University of Innsbruck, 1965.
[6] Buchberger, B. Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen
Gleichungssystems. Aequ. Math., 4(3):374–383, 1970.
[7] Buchberger, B. A criterion for detecting unnecessary reductions in the construction of

Gröbner bases. In EUROSAM ’79, An International Symposium on Symbolic and Algebraic
Manipulation, volume 72 of Lecture Notes in Computer Science, pages 3–21. Springer,
1979.
[8] Buchberger, B. Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory. pages
184–232, 1985.
51 / 57
References II
[9] Decker, W., Greuel, G.-M., Pfister, G., and Schönemann, H. S INGULAR 4-0-0 — A
computer algebra system for polynomial computations, 2014.
http://www.singular.uni-kl.de.
[10] Eder, C. Improving incremental signature-based Groebner bases algorithms. ACM SIGSAM
Communications in Computer Algebra, 47(1):1–13, 2013.
http://arxiv.org/abs/1201.6472.
[11] Eder, C. Predicting zero reductions in Gröbner basis computations. submitted to Journal of
Symbolc Computation, preprint at http://arxiv.org/abs/1404.0161, 2014.
[12] Eder, C. and Faugère, J.-C. A survey on signature-based Groebner basis algorithms, 2014.
http://arxiv.org/abs/1404.1774
[13] Eder, C., Gash, J., and Perry, J. Modifying Faugère’s F5 Algorithm to ensure termination.
ACM SIGSAM Communications in Computer Algebra, 45(2):70–89, 2011.
http://arxiv.org/abs/1006.0318.
[14] Eder, C. and Perry, J. F5C: A Variant of Faugère’s F5 Algorithm with reduced Gröbner
bases. Journal of Symbolic Computation, MEGA 2009 special issue, 45(12):1442–1458,
2010. dx.doi.org/10.1016/j.jsc.2010.06.019.
[15] Eder, C. and Perry, J. Signature-based Algorithms to Compute Gröbner Bases. In ISSAC
2011: Proceedings of the 2011 international symposium on Symbolic and algebraic
computation, pages 99–106, 2011.
52 / 57
References III
[16] Eder, C. and Roune, B. H. Signature Rewriting in Gröbner Basis Computation. In ISSAC
[17] Faugère, J.-C. A new efficient algorithm for computing Gröbner bases without reduction to
zero F5. In ISSAC’02, Villeneuve d’Ascq, France, pages 75–82, July 2002. Revised version
from http://fgbrs.lip6.fr/jcf/Publications/index.html.
[18] Faugère, J.-C. and Joux, A. Algebraic Cryptanalysis of Hidden Field Equation (HFE)
Cryptosystems Using Gröbner Bases. 2729:44–60, 2003.
[19] Faugère, J.-C., Safey El Din, M., and Spaenlehauer, P.-J. Gröbner Bases of
Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and
Complexity. Journal of Symbolic Computation, 46(4):406–437, 2011. Available online 4
November 2010.
[20] Faugère, J.-C., Safey El Din, M., and Verron, T. On the complexity of Computing Gröbner
Bases for Quasi-homogeneous Systems. In Proceedings of the 38th international
symposium on International symposium on symbolic and algebraic computation, ISSAC
’13, pages 189–196, New York, NY, USA, 2013. ACM.
[21] Faugère, J.-C., Spaenlehauer, P.-J. and Svartz, J. Sparse Gröbner Bases: the unmixed
Case. In Proceedings of the 39th international symposium on International symposium on
symbolic and algebraic computation, ISSAC ’14, Kobe, Japan, 2014.
53 / 57
References IV
[22] Faugère, J.-C. and Svartz, J. Solving polynomial systems globally invariant under an action
of the symmetric group and application to the equilibria of n vertices in the plane. In
Proceedings of the 37th international symposium on International symposium on symbolic
and algebraic computation, ISSAC ’12, pages 170–178, New York, NY, USA, 2012. ACM.
[23] Faugère, J.-C. and Svartz, J. Gröbner Bases of ideals invariant under a Commutative group
: the Non-modular Case. In Proceedings of the 38th international symposium on
International symposium on symbolic and algebraic computation, ISSAC ’13, pages
347–354, New York, NY, USA, 2013. ACM.
[24] Faugère, J.-C. and Rahmany, S. Solving systems of polynomial equations with symmetries
using SAGBI-Gröbner bases. In ISSAC ’09: Proceedings of the 2009 international
symposium on Symbolic and algebraic computation, ISSAC ’09, pages 151–158, New York,
NY, USA, 2009. ACM.
[25] Galkin, V. Simple signature-based Groebner basis algorithm.

http://arxiv.org/abs/1205.6050, 2012.
[26] Gao, S., Guan, Y., and Volny IV, F. A new incremental algorithm for computing Gröbner
bases. In ISSAC ’10: Proceedings of the 2010 international symposium on Symbolic and
algebraic computation, pages 13–19. ACM, 2010.
[27] Gao, S., Volny IV, F., and Wang, D. A new algorithm for computing Groebner bases.
http://eprint.iacr.org/2010/641, 2010.
54 / 57
References V
[28] Gao, S., Volny IV, F., and Wang, D. A new algorithm for computing Groebner bases (rev.
2011). http://www.math.clemson.edu/˜sgao/papers/gvw.pdf, 2011.
[29] Gao, S., Volny IV, F., and Wang, D. A new algorithm for computing Groebner bases (rev.
2013).
http://www.math.clemson.edu/˜sgao/papers/gvw_R130704.pdf,
2013.
[30] Gash, J. M. On efficient computation of Gröbner bases. PhD thesis, University of Indiana,
Bloomington, IN, 2008.
[31] Gash, J. M. A provably terminating and speed-competitive variant of F5 – F5t. submitted to

the Journal of Symbolic Computation, 2009.
[32] Gebauer, R. and Möller, H. M. On an installation of Buchberger’s algorithm. Journal of

Symbolic Computation, 6(2-3):275–286, October/December 1988.
[33] Gerdt, V. P. and Hashemi, A. On the use of Buchberger criteria in G2V algorithm for
calculating Gröbner bases. Program. Comput. Softw., 39(2):81–90, March 2013.
[34] Gerdt, V. P., Hashemi, A., and M.-Alizadeh, B. Involutive Bases Algorithm Incorporating F5
Criterion. J. Symb. Comput., 59:1–20, 2013.
[35] Huang, L. A new conception for computing Gröbner basis and its applications.
55 / 57
References VI
[36] Moreno-Socı́as, G. Degrevlex Gröbner bases of generic complete intersections. Journal of

Pure and Applied Algebra, 180(3):263 – 283, 2003.
[37] Pan, S., Hu, Y., and Wang, B. The Termination of Algorithms for Computing Gröbner Bases.
[38] Pan, S., Hu, Y., and Wang, B. The Termination of the F5 Algorithm Revisited. In ISSAC
[39] Roune, B. H. and Stillman, M. Practical Gröbner Basis Computation. In ISSAC 2012:
Proceedings of the 2012 international symposium on Symbolic and algebraic computation,
2012.
[40] Stegers, T. Faugère’s F5 Algorithm revisited. Master’s thesis, Technische Univerität
Darmstadt, revised version 2007.
[41] Sun, Y. and Wang, D. K. A generalized criterion for signature related Gröbner basis
algorithms. In ISSAC 2011: Proceedings of the 2011 international symposium on Symbolic
and algebraic computation, pages 337–344, 2011.
[42] Sun, Y., Wang, D. K., Ma, D. X., and Zhang, Y. A signature-based algorithm for computing
Gröbner bases in solvable polynomial algebras. In ISSAC 2012: Proceedings of the 2011
international symposium on Symbolic and algebraic computation, pages 351–358, 2012.
56 / 57
References VII
[43] Volny, F. New algorithms for computing Gröbner bases. PhD thesis, Clemson University,
2011.
57 / 57

Computing GR Obner Bases - A Short Overview

Uploaded by

Copyright:

Available Formats

Computing GR Obner Bases - A Short Overview

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Computing GR Obner Bases - A Short Overview

Uploaded by

Copyright:

Available Formats

Computing Gröbner Bases – a short overview

Christian Eder, Jean-Charles Faugère,

Seminar of the CARAMEL Team in Nancy, France

September 11, 2014

I R = K [x1 , . . . , xn ], K field, < well-ordering on Mon(x1 , . . . , xn )

I f ∈ R can be represented in a unique way by <.

I An ideal I in R is an additive subgroup of R such that for f ∈ I,

I G = {g1 , . . . , gs } ⊂ R is a Gröbner basis for I = hf1 , . . . , fm i

Buchberger’s criterion [5]

Input: Ideal I = hf1 , . . . , fm i

Input: Ideal I = hf1 , . . . , fm i

Input: Ideal I = hf1 , . . . , fm i

I Modular computations (modStd et al.)

I Predict zero reductions (Buchberger, Gebauer-Möller,

I Sort pair set (Buchberger, Giovini et al., Möller et al.)

I Homogenize: d-Gröbner bases

I Change of ordering (FGLM, Gröbner Walk)

I Linear Algebra: Gaussian Elimination (Lazard, Faugère)

I Sparse Gröbner Bases: Use sparsity and exploit Newton polygons

I Predict zero reductions (Buchberger, Gebauer-Möller,

I Linear Algebra: Gaussian Elimination (Lazard, Faugère)

2 Fast linear algebra for computing Gröbner bases

spol(g2 , g1 ) = xg2 − yg1 = xy2 − xz 2 − xy2 + yz 2

spol(g2 , g1 ) = xg2 − yg1 = xy2 − xz 2 − xy2 + yz 2

spol(g3 , g1 ) = xyz2 − y 2 z 2 − xyz2 + z 4 = −y 2 z 2 + z 4 .

spol(g2 , g1 ) = xg2 − yg1 = xy2 − xz 2 − xy2 + yz 2

spol(g3 , g1 ) = xyz2 − y 2 z 2 − xyz2 + z 4 = −y 2 z 2 + z 4 .

We can reduce further using z 2 g2 :

= lt (g2 )g3 − lt (g3 )g2

= lt (g2 )g3 − lt (g3 )g2

For all u ∈ support (lot (g3 )) we can reduce with ug2 :

=⇒ lt (g2 ) lot (g3 ) − g2 lot (g3 ) − lt (g3 ) lot (g2 )

= lt (g2 )g3 − lt (g3 )g2

For all u ∈ support (lot (g3 )) we can reduce with ug2 :

=⇒ lt (g2 ) lot (g3 ) − g2 lot (g3 ) − lt (g3 ) lot (g2 )

Product criterion [6, 7]

Product criterion [6, 7]

Couldn’t we remove spol (g3 , g2 ) in a different way?

Product criterion [6, 7]

Couldn’t we remove spol (g3 , g2 ) in a different way?

lt (g1 ) = xy | xy 2 z 2 = lcm (lt (g3 ) , lt (g2 ))

Product criterion [6, 7]

Couldn’t we remove spol (g3 , g2 ) in a different way?

lt (g1 ) = xy | xy 2 z 2 = lcm (lt (g3 ) , lt (g2 ))

=⇒ We can rewrite spol (g3 , g2 ):

Product criterion [6, 7]

Couldn’t we remove spol (g3 , g2 ) in a different way?

lt (g1 ) = xy | xy 2 z 2 = lcm (lt (g3 ) , lt (g2 ))

=⇒ We can rewrite spol (g3 , g2 ):

Standard representations of spol (g2 , g1 ) and spol (g3 , g1 )

Chain criterion [8]

Chain criterion [8]

spol (f , g ) = λ spol (f , h) + σ spol (h, g ) ,

then we can remove spol (f , g ) or spol (f , h) but not both!

Chain criterion [8]

spol (f , g ) = λ spol (f , h) + σ spol (h, g ) ,

then we can remove spol (f , g ) or spol (f , h) but not both!

How to combine Product and Chain criterion?

4. If (f , h) ∈ P 0 s.t. lcm (lt (f ) , lt (h)) = lt (f ) lt (h)