Gröbner Bases Tutorial Part II The Generic Gröbner Walk

Changing Gröbner Bases Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Sometimes one Gröbner basis (say grevlex) is easy to find while another Gröbner basis (say lex) is harder. In the 0-dimensional case, one can use the FGLM algorithm of Faugère, Gianni, Lazard and Mora (1993). For arbitrary ideals, one can use the Gröbner walk of Collart, Kalkbrener and Mall (1997). Avoiding “bad walks” sometimes requires perturbations and large integer arithmetic. The generic Gröbner walk of Fukada, Jensen, Lauritzen and Thomas (2007) avoids this problem. The Gröbner Cone Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Definition Let (G, >) be the reduced Gröbner basis of I ⊆ k[x]. The Gröbner cone C> (I) ⊆ Rn+ consists of all w ∈ Rn+ such that w ·u ≥ w ·v i.e., w ·(u − v) ≥ 0, where xu = LM(g), g ∈ G, and xv 6= xu appears in g. Example {y 3 − x 2 , x 3 − y 2 + x} is a reduced Gröbner basis for I = hx 2 − y 3 , x 3 − y 2 + xi using grlex with x > y. Then C> (I) ⊆ R2+ is defined by w ·(−2, 3) ≥ 0, w ·(3, −2) ≥ 0, w ·(2, 0) ≥ 0. The Gröbner Fan Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Theorem Fix an ideal I ⊆ k[x]. 1 As we vary over all monomial orders on k[x], I has only finitely many distinct reduced Gröbner bases. 2 Two distinct Gröbner cones of I intersect in a common face of each. Corollary The finitely many distinct Gröbner cones form a fan, called the (restricted) Gröbner fan, whose support is the first orthant Rn+ of Rn . Example Gröbner Bases Tutorial The Gröbner fan of hx 2 − y 3 , x 3 − y 2 + xi has seven cones: 6 4 Graph Theory Geometric Theorem Discovery 12 3 3/2 4 The Generic Gröbner Walk 2/3 5 1/4 Phylogenetic Invariants 6 7 1/7 1: lex with y > x {x 8 − 3x 6 + 3x 4 − x 3 − x 2 , xy − x 7 + 2x 5 − x 3 + x 2 , y 2 − x 3 − x} 4: grlex or grevlex with y > x or x > y {y 3 − x 2 , x 3 − y 2 + x} 7: lex with x > y {y 9 − 2y 6 − y 4 + y 3 , x − y 7 + y 4 − y 2 } The Gröbner Walk Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Let (G, >) be a reduced Gröbner basis of I. Definition If g = ∑v av xv ∈ G and w ∈ Rn+ , then inw (g) := ∑ w ·v =max av xv . Lemma w is in the interior of C> (I) ⇐⇒ inw (g) = LT(g) ∀g ∈ G. Intuition for the Gröbner Walk If w lies on the boundary of C> (I), then: hinw (G)i is “close” to a monomial ideal. Finding the Gröbner basis on the other side is “easy”. Example Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants I = hx 2 − y 3 , x 3 − y 2 + xi has reduced Gröbner basis G = {y 3 − x 2 , x 3 − y 2 + x} for grevlex with x > y. We will “walk” to the reduced Gröbner basis for lex with x > y. Note: (1, 1) is in the interior of the initial Gröbner cone. (1, 0) is in the target Gröbner cone. 3/2 2/3 (1,1) ← walk (1,0) Example Gröbner Bases Tutorial • Compute that we leave the initial cone at w = (1, 2/3). 3/2 Graph Theory Geometric Theorem Discovery 2/3 (1,1) The Generic Gröbner Walk ← w = (1,2/3) ← walk Phylogenetic Invariants (1,0) • Compute inw (G) = {y 3 − x 2 , x 3 } and compute a lex Gröbner basis H = {x 2 − y 3 , xy 3 , y 6 } of hinw (G)i. Lifting Lemma A Gröbner basis (possibly non-reduced) for >w ,lex is {h − hG | h ∈ H}. Example Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants • The lemma gives the Gröbner basis: {x 2 − y 3 , xy 3 − y 2 − x, y 6 − xy 2 − x 2 }. Reducing gives the new reduced Gröbner basis: {x 2 − y 3 , xy 3 − y 2 − x, y 6 − xy 2 − y 3 } and new Gröbner cone: 3/2 2/3 (1,1) ← new cone 1/4 ← walk (1,0) • Repeat, starting with the new cone! Problems Gröbner Bases Tutorial A walk can be: good when it crosses only walls. Graph Theory bad when it meets an intersection of walls. Geometric Theorem Discovery z z The Generic Gröbner Walk y Phylogenetic Invariants bad → good → x ← x y (This is a 2-dimensional slice of a Gröbner fan in R3+ .) Perturbations are used to ensure that the walk is good, but this causes problems with w (large integers). The Generic Gröbner Walk Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Goal Convert a reduced Gröbner basis (G1 , >1 ) to (G2 , >2 ). The generic Gröbner walk picks wi ∈ C>i (I) that are sufficiently generic and computes consequences of wi without knowing wi explicitly. Key Question When does w = (1 − t)w1 + t w2 leave C>1 (I)? C>1 (I) consists of those w ∈ Rn+ satisfying w ·u ≥ w ·v, g = a u x u + · · · + a v x v + · · · ∈ G1 Set ∆(G1 ) = {u − v as above}, so that C>1 (I) is w ·γ ≥ 0 ∀γ ∈ ∆(G1 ), w ∈ Rn+ . Elements of ∆(G1 ) are called facet normals. Normals Instead of Weights Gröbner Bases Tutorial The generic Gröbner walk replaces weight vectors with facet normals to keep track of the walk. Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Classic Generic 3/2 Phylogenetic Invariants 3/2 2/3 ←γ ←w 1/4 w 1/7 ← ←w use weight vectors 2/3 ←γ ←γ 1/4 1/7 use facet normals Facet Normals Tell Us Everything Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Suppose the classic Gröbner walk crosses cones at a generic point w of the facet defined by γ . If g = au xu + · · · + av xv + · · · ∈ G, then: inw (g) equals au xu plus those terms av xv with w ·u = w ·v, i.e., w ·(u − v) = 0. By genericity, this happens ⇔ u − v is parallel to γ . Thus, writing inγ (g) instead of inw (g), we have inγ (g) = au xu + ∑u−v ||γ av xv . Furthermore: H is the Gröbner basis of hinγ (G)i for >2 . The new Gröbner basis is {f − f G | f ∈ H}, where f G is the remainder of f on division by G under >1 . Find the Facet Normal Gröbner Bases Tutorial Lemma w = (1 − t)w1 + t w2 leaves the Gröbner cone of G when Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants where t = min{tγ | γ ∈ ∆(G), w1 ·γ > 0, w2 ·γ < 0}, | {z } w1 ,w2 on opposite sides 1 tγ := w2 ·γ . 1− w1 ·γ Any γ with minimal tγ is the desired facet normal! Let’s compare tγ and tδ . Since w2 is generic for >2 , tγ ≤ tδ ⇔ w2 ·(w1 ·δ )γ ≤ w2 ·(w1 ·γ )δ ⇔ (w1 ·δ )γ ≤2 (w1 ·γ )δ . This removes w2 from the picture. Find the Facet Normal Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants To remove w1 , represent >2 using τ1 , . . . , τn . This means u <2 v ⇔ τ1 ·u < τ1 ·v, or τ1 ·u = τ1 ·v and τ2 ·u < τ2 ·v, or . . . Then testing (w1 ·δ )γ ≤2 (w1 ·γ )δ requires checking

τi · (w1 ·δ )γ ≤ τi · (w1 ·γ )δ . Rewrite this as

w1 · (τi ·γ )δ ≤ w1 · (τi ·δ )γ . Since w1 is generic for >1 , this is equivalent to (τi ·γ )δ ≤1 (τi ·δ )γ . This removes w1 from the picture. Example Gröbner Bases Tutorial As before, we convert a reduced grevlex Gröbner basis with x > y for I = hx 2 − y 3 , x 3 − y 2 + xi to lex with x > y. Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants We assume we have done one step to obtain the first facet normal γ = (−2, 3) and the reduced Gröbner basis G = {x 2 − y 3 , xy 3 − y 2 − x, y 6 − xy 2 − y 3 } This gives ∆(G) = {(2, −3), (1, 1), (0, 3), (−1, 4)}. The second facet normal lies in {γ ∈ ∆(G) | γ >1 0, γ <2 0} = {(−1, 4), (0, 3)} | {z } | {z } | {z } γ separates >1 ,>2 γ δ Which do we use: γ or δ ? Example Gröbner Bases Tutorial Here is the picture: 3/2 first ←γ Graph Theory ← γ = (−1,4) Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants 2/3 ← δ = (0,3) Then: • >1 is grevlex with x > y and >2 is lex with x > y. • Represent >2 using: τ1 = (1, 0), τ2 = (0, 1). • Our previous analysis gives: tγ < tδ ⇔ (τ1 ·γ )δ <1 (τ1 ·δ )γ , or (τ1 ·γ )δ = (τ1 ·δ )γ and . . . ⇔ (0, −3) <1 (0, 0). Conclusion: The second γ is (−1, 4). Summary Gröbner Bases Tutorial The Generic Gröbner Walk Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Input: A reduced Gröbner basis (G1 , >1 ) of I. Output: A reduced Gröbner basis (G2 , >2 ) of I. 1: Use G1 to find the first γ using (τi ·γ )δ ≤1 (τi ·δ )γ . 2: Use γ to find inγ (G1 ). 3: Find a reduced Gröbner basis (H, >2 ) of hinγ (G1 )i. 4: Lift to H 0 = {f − f G | f ∈ H}. 5: Autoreduce to get the next reduced Gröbner basis. 6: Iterate! Final Comments Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Another interesting variation on the Gröbner walk has been proposed by Tran (2007). It uses the following definition. Definition Given I ⊆ k[x, y], a monomial order > is ideal-specific for I for eliminating x if the reduced Gröbner basis (G, >) has the property that for any g ∈ G, LT(g) ∈ k[y] ⇒ g ∈ k[y]. Lemma Given I ⊆ k[x, y] and (G, >) as in the definition, G ∩ k[y] is a Gröbner basis for the elimination ideal I ∩ k[y]. Final Comments Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Lemma Suppose a Gröbner cone C> (I) contains a weight vector w = (β1 , . . . , βs , 0, . . . , 0 ). | {z } | {z } x variables y variables Then > is ideal-specific for I for eliminating x. Tran has applied this to elimination theory via the classic Gröbner walk (with perturbations introduced in 2000). The target is an elimination order >2 , but the walk stops as soon as if finds an ideal-specific elimination order. In examples, the Gröbner walk traverses 92 cones, but finds an ideal-specific elimination order after 86. Since the later cones can require the most computation, this can cut the running time in half. References Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants S. Collart, M. KalkBrener, D. Mall, Converting bases with the Gröbner walk, J. Symbolic Comput. 24 (1997), 465–469. D. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, Second Edition, Graduate Texts in Mathematics, Springer, New York, 2005. K. Fukada, A. N. Jensen, N. Lauritzen, R. Thomas, The generic Gröbner walk, J. Symbolic Comput. 42 (2007), 298–312. Q.-N. Tran, A new class of term orders for elimination, J. Symbolic Comput. 42 (2007), 533–548.