mjo/polynomial.py

   1 from sage.all import *
   2
   3 def multidiv(f, gs):
   4     r"""
   5     Divide the multivariate polynomial ``f`` by the ordered list of
   6     polynomials ``gs`` from the same ring.
   7
   8     INPUT:
   9
  10     - ``f`` -- A multivariate polynomial, the "numerator," that we try
  11       to express as a combination of the ``gs``.
  12
  13     - ``gs`` -- An ordered list of multipolynomials, the "denominators,"
  14       in the same ring as ``f``.
  15
  16     OUTPUT:
  17
  18     A pair, the first component of which is the list of "quotients," and
  19     the second of which is the remainder. All quotients and the
  20     remainder will live in the same ring as ``f`` and the ``gs``. If the
  21     ordered list of "quotients" is ``qs``, then ``f`` is the remainder
  22     plus the sum of all ``qs[i]*gs[i]``.
  23
  24     The remainder is either zero, or a linear combination of monomials
  25     none of which are divisible by any of the leading terms of the ``gs``.
  26     Moreover if ``qs[i]*gs[i]`` is nonzero, then the multidegree of ``f``
  27     is greater than or equal to the multidegree of ``qs[i]*gs[i]``.
  28
  29     SETUP::
  30
  31         sage: from mjo.polynomial import multidiv
  32
  33     ALGORITHM:
  34
  35     The algorithm from Theorem 3 in  Section 2.3 of Cox, Little, and O'Shea
  36     is used almost verbatim.
  37
  38     REFERENCES:
  39
  40     - David A. Cox, John Little, Donal O'Shea. Ideals, Varieties, and
  41       Algorithms: An Introduction to Computational Algebraic Geometry
  42       and Commutative Algebra (Fourth Edition). Springer Undergraduate
  43       Texts in Mathematics. Springer International Publishing, Switzerland,
  44       2015. :doi:`10.1007/978-3-319-16721-3`.
  45
  46     EXAMPLES:
  47
  48     Example 1 in Section 2.3 of Cox, Little, and O'Shea::
  49
  50         sage: R = PolynomialRing(QQ, 'x,y', order='lex')
  51         sage: x,y = R.gens()
  52         sage: f = x*y^2 + 1
  53         sage: gs = [ x*y + 1, y + 1 ]
  54         sage: (qs, r) = multidiv(f, gs)
  55         sage: (qs, r)
  56         ([y, -1], 2)
  57         sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
  58         True
  59         sage: not any( g.lt().divides(m) for m in r.monomials()
  60         ....:          for g in gs )
  61         True
  62
  63     Example 2 in Section 2.3 of Cox, Little, and O'Shea::
  64
  65         sage: R = PolynomialRing(QQ, 'x,y', order='lex')
  66         sage: x,y = R.gens()
  67         sage: f = x^2*y + x*y^2 + y^2
  68         sage: gs = [ x*y - 1, y^2 - 1 ]
  69         sage: (qs, r) = multidiv(f, gs)
  70         sage: (qs, r)
  71         ([x + y, 1], x + y + 1)
  72         sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
  73         True
  74         sage: not any( g.lt().divides(m) for m in r.monomials()
  75         ....:          for g in gs )
  76         True
  77
  78     A solution ``g`` to Exercise 6 in Section 2.3 of Cox, Little, and
  79     O'Shea that lives in the ideal generated by ``f1`` and ``f2`` but
  80     which has nonzero remainder after division::
  81
  82         sage: R = PolynomialRing(QQ, 'x,y', order='deglex')
  83         sage: x,y = R.gens()
  84         sage: f1 = 2*x*y^2 - x
  85         sage: f2 = 3*x^2*y - y - 1
  86         sage: I = R.ideal(f1,f2)
  87         sage: g = 2*y*f2
  88         sage: g in I
  89         True
  90         sage: (qs,r) = multidiv(g,[f1,f2])
  91         sage: r.is_zero()
  92         False
  93
  94     Two solutions ``g`` to Exercise 7 in Section 2.3 of Cox, Little, and
  95     O'Shea that live in the ideal generated by ``f1``, ``f2``, and ``f3``
  96     but which have nonzero remainders after division::
  97
  98         sage: R = PolynomialRing(QQ, 'x,y,z', order='deglex')
  99         sage: x,y,z = R.gens()
 100         sage: f1 = x^4*y^2 - z
 101         sage: f2 = x^3*y^3 - 1
 102         sage: f3 = x^2*y^4 - 2*z
 103         sage: I = R.ideal(f1,f2,f3)
 104         sage: g = x^2*f3
 105         sage: g in I
 106         True
 107         sage: (qs, r) = multidiv(g, [f1,f2,f3])
 108         sage: r.is_zero()
 109         False
 110         sage: g = x*f2
 111         sage: g in I
 112         True
 113         sage: (qs, r) = multidiv(g, [f1,f2,f3])
 114         sage: r.is_zero()
 115         False
 116
 117     Example 4 in Section 2.3 of Cox, Little, and O'Shea. This is the
 118     same as Example 2, except with the order of ``gs`` reversed::
 119
 120         sage: R = PolynomialRing(QQ, 'x,y', order='lex')
 121         sage: x,y = R.gens()
 122         sage: f = x^2*y + x*y^2 + y^2
 123         sage: gs = [ y^2 - 1, x*y - 1 ]
 124         sage: (qs, r) = multidiv(f, gs)
 125         sage: (qs, r)
 126         ([x + 1, x], 2*x + 1)
 127         sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
 128         True
 129         sage: not any( g.lt().divides(m) for m in r.monomials()
 130         ....:          for g in gs )
 131         True
 132
 133     TESTS:
 134
 135     If we get a zero remainder, then the numerator should belong to
 136     the ideal generated by the denominators::
 137
 138         sage: R = PolynomialRing(QQ, 'x,y,z')
 139         sage: x,y,z = R.gens()
 140         sage: s = ZZ.random_element(1,5).abs()
 141         sage: gs = [ R.random_element() for idx in range(s) ]
 142         sage: # hack for SageMath Trac #28855
 143         sage: f = R(R.random_element(ZZ.random_element(10).abs()))
 144         sage: (qs, r) = multidiv(f,gs)
 145         sage: r != 0 or f in R.ideal(gs)
 146         True
 147
 148     The numerator is always the sum of the remainder and the quotients
 149     times the denominators, and the remainder's monomials aren't divisible
 150     by the leading term of any denominator::
 151
 152         sage: R = PolynomialRing(QQ, 'x,y,z')
 153         sage: s = ZZ.random_element(1,5).abs()
 154         sage: gs = [ R.random_element() for idx in range(s) ]
 155         sage: # hack for SageMath Trac #28855
 156         sage: f = R(R.random_element(ZZ.random_element(10).abs()))
 157         sage: (qs, r) = multidiv(f,gs)
 158         sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
 159         True
 160         sage: r == 0 or (not any( g.lt().divides(m) for m in r.monomials()
 161         ....:                     for g in gs ))
 162         True
 163
 164     Exercise 8 in Section 2.4 of Cox, Little, and O'Shea says that we
 165     should always get a zero remainder if we divide an element of a
 166     monomial ideal by its generators::
 167
 168         sage: R = PolynomialRing(QQ,'x,y,z')
 169         sage: gs = R.random_element().monomials()
 170         sage: I = R.ideal(gs)
 171         sage: # hack for SageMath Trac #28855
 172         sage: f = R(I.random_element(ZZ.random_element(5).abs()))
 173         sage: (qs, r) = multidiv(f, gs)
 174         sage: r.is_zero()
 175         True
 176
 177     """
 178     R = f.parent()
 179     s = len(gs)
 180
 181     p = f
 182     r = R.zero()
 183     qs = [R.zero()]*s
 184
 185     while p != R.zero():
 186         for i in range(0,s):
 187             division_occurred = false
 188             # If gs[i].lt() divides p.lt(), then this remainder will
 189             # be zero and the quotient will be in R (and not the
 190             # fraction ring, which is important).
 191             (factor, lt_r) = p.lt().quo_rem(gs[i].lt())
 192             if lt_r.is_zero():
 193                 qs[i] += factor
 194                 p -= factor*gs[i]
 195                 division_occurred = true
 196                 break
 197
 198         if not division_occurred:
 199             r += p.lt()
 200             p -= p.lt()
 201
 202     return (qs,r)