1

Buchberger's algorithm requires computing S-pairs (more on page 83 of Ideals, Varities and Algorithm by Cox et all 2008, 3rd edition)

S(f,g)=LCM(LT(f),LT(g))/LT(f) *f - LCM(LT(f),LT(g))/LT(g) * g

where LCM is the least common multiple (equivalent to x^\gamma in the book notation) and LT is the leading term.

How can you compute S-pairs in Macaulay2 or otherwise programmatically?

Example: S-pair in Graded Lexicographic order with g1=x^2-y and g2=x^3-z where S(g1,g2)=xz-xy.

enter image description here

hhh
  • 50,788
  • 62
  • 179
  • 282

1 Answers1

2

S-pair command for Macaulay2 as a function by the definition

enter image description here

and also the code in text for easy copying

Spair = (g1,g2) -> lcm(leadTerm(g1),leadTerm(g2))/leadTerm(g1)*g1-lcm(leadTerm(g1),leadTerm(g2))/leadTerm(g2)*g2;

that works such that Spair(polynomial1, polynomial2) computes the S-pair polynomial for polynomial1 and polynomial2.

In contrast, alternative method for Spairs can apparently be deduced in terms of syzygies and generators by the Theorem 9 of the book (1)

S * G = \sum_{i=1}^t h_i g_i \rightarrow_G 0

where the mapping is modulo G, S-pairs are somehow related to the expression in terms of syzygies and generators, some examples the below. Perhaps syz and gb are useful to compute S-pairs.

Relationship of S-pairs to generating sets in terms of Gröbner basis and syzygies

  • "Let us now take a look at the first syzygies (or minimal S-pairs [1, §2.9]) among the sixteen minimal generators. " (Ideals, Varieties and Macaulay 2, p9)

  • "The matrix spairs contains all the S-pairs between generators of J corresponding to the minimal first syzygies of M" (p.195 here)

References

(1) Ideals, Varities, and Algorithms by Cox et all (2008, 3rd ed)

hhh
  • 50,788
  • 62
  • 179
  • 282