X-Git-Url: http://gitweb.michael.orlitzky.com/?a=blobdiff_plain;f=mjo%2Fpolynomial.py;h=55ada9a2f5d5ed259277fb8bceeb53f43a1b30e1;hb=1bbade9f41ffbfe366b15d0db657f666bc1f025d;hp=3e90ba5bf3cf3862360ed5d5e5e3ccdcd9c17647;hpb=44f02b184d9a8907ab92e268193f6a1f0a3eaaa7;p=sage.d.git

diff --git a/mjo/polynomial.py b/mjo/polynomial.py
index 3e90ba5..55ada9a 100644
--- a/mjo/polynomial.py
+++ b/mjo/polynomial.py
@@ -51,8 +51,14 @@ def multidiv(f, gs):
         sage: x,y = R.gens()
         sage: f = x*y^2 + 1
         sage: gs = [ x*y + 1, y + 1 ]
-        sage: multidiv(f, gs)
+        sage: (qs, r) = multidiv(f, gs)
+        sage: (qs, r)
         ([y, -1], 2)
+        sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
+        True
+        sage: not any( g.lt().divides(m) for m in r.monomials()
+        ....:          for g in gs )
+        True
 
     Example 2 in Section 2.3 of Cox, Little, and O'Shea::
 
@@ -60,12 +66,116 @@ def multidiv(f, gs):
         sage: x,y = R.gens()
         sage: f = x^2*y + x*y^2 + y^2
         sage: gs = [ x*y - 1, y^2 - 1 ]
-        sage: multidiv(f, gs)
+        sage: (qs, r) = multidiv(f, gs)
+        sage: (qs, r)
         ([x + y, 1], x + y + 1)
+        sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
+        True
+        sage: not any( g.lt().divides(m) for m in r.monomials()
+        ....:          for g in gs )
+        True
+
+    A solution ``g`` to Exercise 6 in Section 2.3 of Cox, Little, and
+    O'Shea that lives in the ideal generated by ``f1`` and ``f2`` but
+    which has nonzero remainder after division::
+
+        sage: R = PolynomialRing(QQ, 'x,y', order='deglex')
+        sage: x,y = R.gens()
+        sage: f1 = 2*x*y^2 - x
+        sage: f2 = 3*x^2*y - y - 1
+        sage: I = R.ideal(f1,f2)
+        sage: g = 2*y*f2
+        sage: g in I
+        True
+        sage: (qs,r) = multidiv(g,[f1,f2])
+        sage: r.is_zero()
+        False
+
+    Two solutions ``g`` to Exercise 7 in Section 2.3 of Cox, Little, and
+    O'Shea that live in the ideal generated by ``f1``, ``f2``, and ``f3``
+    but which have nonzero remainders after division::
+
+        sage: R = PolynomialRing(QQ, 'x,y,z', order='deglex')
+        sage: x,y,z = R.gens()
+        sage: f1 = x^4*y^2 - z
+        sage: f2 = x^3*y^3 - 1
+        sage: f3 = x^2*y^4 - 2*z
+        sage: I = R.ideal(f1,f2,f3)
+        sage: g = x^2*f3
+        sage: g in I
+        True
+        sage: (qs, r) = multidiv(g, [f1,f2,f3])
+        sage: r.is_zero()
+        False
+        sage: g = x*f2
+        sage: g in I
+        True
+        sage: (qs, r) = multidiv(g, [f1,f2,f3])
+        sage: r.is_zero()
+        False
+
+    Example 4 in Section 2.3 of Cox, Little, and O'Shea. This is the
+    same as Example 2, except with the order of ``gs`` reversed::
+
+        sage: R = PolynomialRing(QQ, 'x,y', order='lex')
+        sage: x,y = R.gens()
+        sage: f = x^2*y + x*y^2 + y^2
+        sage: gs = [ y^2 - 1, x*y - 1 ]
+        sage: (qs, r) = multidiv(f, gs)
+        sage: (qs, r)
+        ([x + 1, x], 2*x + 1)
+        sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
+        True
+        sage: not any( g.lt().divides(m) for m in r.monomials()
+        ....:          for g in gs )
+        True
 
     TESTS:
 
-    Derp.
+    If we get a zero remainder, then the numerator should belong to
+    the ideal generated by the denominators::
+
+        sage: set_random_seed()
+        sage: R = PolynomialRing(QQ, 'x,y,z')
+        sage: x,y,z = R.gens()
+        sage: s = ZZ.random_element(1,5).abs()
+        sage: gs = [ R.random_element() for idx in range(s) ]
+        sage: # hack for SageMath Trac #28855
+        sage: f = R(R.random_element(ZZ.random_element(10).abs()))
+        sage: (qs, r) = multidiv(f,gs)
+        sage: r != 0 or f in R.ideal(gs)
+        True
+
+    The numerator is always the sum of the remainder and the quotients
+    times the denominators, and the remainder's monomials aren't divisible
+    by the leading term of any denominator::
+
+        sage: set_random_seed()
+        sage: R = PolynomialRing(QQ, 'x,y,z')
+        sage: s = ZZ.random_element(1,5).abs()
+        sage: gs = [ R.random_element() for idx in range(s) ]
+        sage: # hack for SageMath Trac #28855
+        sage: f = R(R.random_element(ZZ.random_element(10).abs()))
+        sage: (qs, r) = multidiv(f,gs)
+        sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
+        True
+        sage: r == 0 or (not any( g.lt().divides(m) for m in r.monomials()
+        ....:                     for g in gs ))
+        True
+
+    Exercise 8 in Section 2.4 of Cox, Little, and O'Shea says that we
+    should always get a zero remainder if we divide an element of a
+    monomial ideal by its generators::
+
+        sage: set_random_seed()
+        sage: R = PolynomialRing(QQ,'x,y,z')
+        sage: gs = R.random_element().monomials()
+        sage: I = R.ideal(gs)
+        sage: # hack for SageMath Trac #28855
+        sage: f = R(I.random_element(ZZ.random_element(5).abs()))
+        sage: (qs, r) = multidiv(f, gs)
+        sage: r.is_zero()
+        True
 
     """
     R = f.parent()