Gröbner Bases Tutorial Part II Geometric Theorem Discovery

Geometric Theorem Discovery Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Our next topic involves an application of comprehensive Gröbner systems to the problem of discovering the correct hypotheses that give an interesting theorem in geometry. Our discussion was inspired by a preprint of Montes and Recio (2007). We begin with an example of Sato and Suzuki (2006) that illustrates specialization of Gröbner bases. Example 1 Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants The ideal I := h(u − 1)x + y 2 , uy + ui ⊆ k[x, y, u]. A lex Gröbner basis for x > y > u is {ux − x + y 2 , uy + u, xy + x − y 3 − y 2 } We think of u as a parameter. Set V := V(I) ⊆ A3 . Let’s apply our theorems: Elimination Theorem ⇒ I2 = {0}. Closure Theorem ⇒ the projection of V onto the last coordinate has Zariski dense image in A1 . A more careful analysis reveals that π2 (V ) = A1 \ {1}. This raises two questions. First Question Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Does G = {ux − x + y 2 , uy + u, xy + x − y 3 − y 2 } remain a Gröbner basis (for lex with x > y) when the parameter u is given a specific numerical value b? Two observations: Setting u = 1 gives G1 = {y 2 , y + 1, xy + x − y 3 − y 2 }, which generates h1i = k[x, y]. Since 1 ∈ / hy 2 , y, xyi, G is not a Gröbner basis. Write G as {(u − 1) · x + y 2 , u · y + u, 1 · xy + x − y 3 − y 2 }. If u = b 6= 0, 1, the Special Case considered in the proof of the Closure Theorem implies that Gb is a Gröbner basis. General Question: How do Gröbner bases specialize? Second Question Gröbner Bases Tutorial Since π2 (V ) = A1 \ {1}, the equations Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants (u − 1)x + y 2 = uy + u = 0 have a solution when u = b 6= 1. How many solutions? u = b 6= 0, 1 ⇒ (b − 1)x + y 2 = y + 1 = 0 has a unique solution. u = 0 ⇒ −x + y 2 = 0 has infinitely many solutions. General Question: How do we describe the number of solutions? Answers for the Example Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Consider the following pairs:
(S1 , G1 ) := A \ {0, 1}, {(u − 1)x + y , uy + u}
2 (S2 , G2 ) := {0}, {x − y }
(S3 , G3 ) := {1}, {1} . 2 Note that: Si is constructible, S1 ∪ S2 ∪ S3 = A1 is a partition. For b ∈ Si , Gi b is a reduced Gröbner basis (almost). For b ∈ Si , hLT(Gi b )i is independent of b. hLT(G1 b )i = hx, yi, hLT(G2 b )i = hxi, hLT(G3 b )i = h1i gives the number of solutions. This is a minimal canonical comprehensive Gröbner system. MCCGS Gröbner Bases Tutorial Let I ⊆ k[x, u] be an ideal with variables x = (x1 , . . . , xn ) and parameters u = (u1 , . . . , um ). Fix an order > on k[x]. Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Definition A minimal canonical comprehensive Gröbner system for I and > consists of pairs (Si , Gi ) satisfying: The Si give a constructible partition of Am . For b ∈ Si , setting u = b gives a reduced Gröbner basis Gi b (up to constants). For b ∈ Si , hLT(Gi b )i is independent of b. No smaller partition exists with these properties. This definition is due to Manubens and Montes (2006). A False Theorem Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Let CD be the diameter of a circle of radius 1. Fix A. Then: ← → • The line AE is tangent to the circle at E. ← → ←→ • The lines AC and E D meet at F . False Theorem AE = AF . Challenge: Discover reasonable hypotheses on A to make the theorem true. F A E C O D Hypotheses Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants Set A = (u1 , u2 ) E = (x1 , x2 ) F = (x3 , x4 ). F Then: ← → ←→ • AE ⊥ OE gives A E h1 := (x1 − u1 )(x1 − 1) + (x2 − u2 )x2 . • OE = 1 gives (x1 − 1)2 + x22 − 1. h2 := ← → T ←→ • F = AC ED gives h3 := u1 x4 − u2 x3 . h4 := x4 (x1 − 2) − x2 (x3 − 2). C O D More Hypotheses Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants F We also need to assume: A • A 6= C, so E u1 6= 0 or u2 6= 0. • E 6= D, so x2 6= 2. C O Conclusion: The ideal that describes this problem is the saturation I := hh1 , h2 , h3 , h4 i : h(x2 − 2)u1 , (x2 − 2)u2i∞ in the ring k[x1 , x2 , x3 , x4 , u1 , u2 ]. D Strategy Gröbner Bases Tutorial Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Our false theorem asserts AE = AF . This gives g := (u1 − x1 )2 + (u2 − x2 )2 − (u1 − x3 )2 − (u2 − x4 )2 . Strategy Compute a MCCGS for the ideal Phylogenetic Invariants I + hgi ⊆ k[x1 , x2 , x3 , x4 , u1 , u2 ], u1 , u2 parameters. Intuition The false theorem is true for those u = b ∈ A2 for which 0/ 6= V(Īb + hḡb i) ⊆ A4 . The MCCGS Gröbner Bases Tutorial The MCCGS for I + hgi ⊆ k[x1 , x2 , x3 , x4 , u1 , u2 ] under lex order with x1 > x2 > x3 > x4 is (S1 , G1 ) ∪ · · · ∪ (S6 , G6 ) Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants The Si and Leading Terms i Si
2 V(u12 + u22 − 2u1 ) ∪ V(u1 ) V(u12 + u22 − 2u1) \ {(0, 0), (2, 0)} x1 , x2 , x3 , x42 3 V(u1 ) \ {(0, 0), (0, ±i)} x1 , x2 , x3 , x42 4 {(0, ±i)} x1 , x2 , x3 , x4 5 {(2, 0)} x1 , x22 , x3 , x42 6 {(0, 0)} x1 , x2 , x32 , x42 1 A2 \ LT(Gi b ) 1 Consequences of the MCCGS Gröbner Bases Tutorial We can ignore Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants S4 = {(0, ±i)}, S5 = {(2, 0)}, S6 = {(0, 0)}. The first is not real, and the second and third are impossible since E 6= D and A 6= C.
2 2 2 G1 = {1} on S1 = A \ V(u1 + u2 − 2u1 ) ∪ V(u1 ) ⇒ V(I + hgi) = 0/ if u = b ∈ / V(u12 + u22 − 2u1 ) ∪ V(u1 ). Hence the “false theorem” AE = AF (i.e., g = 0) cannot follow from our hypotheses (i.e., the ideal I) unless the point A comes from V(u12 + u22 − 2u1) ∪ V(u1 ). This holds ⇔ A is on the circle or the tangent at C. Consequences and Expectations Gröbner Bases Tutorial Consequence Graph Theory “A is on the circle or the tangent at C” is a necessary condition for AE = AF . Geometric Theorem Discovery The Generic Gröbner Walk Before we investigate sufficiency, note that when a solution exists, we expect two solutions: Given A, there are two choices for E: A Phylogenetic Invariants E E C O D S2 and S3 Gröbner Bases Tutorial To study whether the condition: “A is on the circle or the tangent at C” Graph Theory Geometric Theorem Discovery is sufficient, we use: S2 = V(u12 + u22 − 2u1) \ {(0, 0), (2, 0)} The Generic Gröbner Walk S3 = V(u1 ) \ {(0, 0), (0, ±i)}. Phylogenetic Invariants Both have LT(Gi b ) = hx1 , x2 , x3 , x42 i, so there are two solutions (counting multiplicity). Notice that: S2 corresponds to “A is on the circle”. S3 corresponds to “A is on the tangent at C”. We study each case separately. On the Circle Gröbner Bases Tutorial When A is on the circle, we get: Graph Theory Geometric Theorem Discovery A=E=F The Generic Gröbner Walk Phylogenetic Invariants C O D Here, AE = AF is true – both sides are zero! The unique solution has multiplicity two (the tangents from A coincide). Hence the “false theorem” is true but not interesting. On the Tangent Gröbner Bases Tutorial When A is on the tangent, we get the picture to the right. F2 Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants There are two choices for E: • For E1 , we get F1 = E1 , so AE = AF is true but uninteresting. A • For E2 , we get an interesting theorem! E2 F1 = E1 = C This is automatic theorem discovery using MCCGS. O D References Gröbner Bases Tutorial D. Lazard, F. Rouillier, Solving parametric polynomial systems, J. Symbolic Comput. 42 (2007), 636–667. Graph Theory Geometric Theorem Discovery The Generic Gröbner Walk Phylogenetic Invariants M. Manubens, A. Montes, Minimal canonical comprehensive Groebner systems, arXiv:0611948 [math.AC]. A. Montes, T. Recio, Automatic discovery of geometric theorems using minimal canonical comprehensive Groebner systems, arXiv:0703483 [math.AG]. A. Suzuki, Y. Sato, A simple algorithm to compute comprehensive Gröbner bases, Proceedings ISSAC 2006, ACM, 326–331. M. Wibmer, Gröbner bases for families of affine or projective schemes, arXiv:0608019 [math.AC].