]>
gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/polynomial.py
2b8dc2aa4cb825c06c6e0e09dc8582da0533817b
5 Divide the multivariate polynomial ``f`` by the ordered list of
6 polynomials ``gs`` from the same ring.
10 - ``f`` -- A multivariate polynomial, the "numerator," that we try
11 to express as a combination of the ``gs``.
13 - ``gs`` -- An ordered list of multipolynomials, the "denominators,"
14 in the same ring as ``f``.
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]``.
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]``.
31 sage: from mjo.polynomial import multidiv
35 The algorithm from Theorem 3 in Section 2.3 of Cox, Little, and O'Shea
36 is used almost verbatim.
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`.
48 Example 1 in Section 2.3 of Cox, Little, and O'Shea::
50 sage: R = PolynomialRing(QQ, 'x,y', order='lex')
53 sage: gs = [ x*y + 1, y + 1 ]
54 sage: (qs, r) = multidiv(f, gs)
57 sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
59 sage: not any( g.lt().divides(m) for m in r.monomials()
63 Example 2 in Section 2.3 of Cox, Little, and O'Shea::
65 sage: R = PolynomialRing(QQ, 'x,y', order='lex')
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)
71 ([x + y, 1], x + y + 1)
72 sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
74 sage: not any( g.lt().divides(m) for m in r.monomials()
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::
82 sage: R = PolynomialRing(QQ, 'x,y', order='deglex')
84 sage: f1 = 2*x*y^2 - x
85 sage: f2 = 3*x^2*y - y - 1
86 sage: I = R.ideal(f1,f2)
90 sage: (qs,r) = multidiv(g,[f1,f2])
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::
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)
107 sage: (qs, r) = multidiv(g, [f1,f2,f3])
113 sage: (qs, r) = multidiv(g, [f1,f2,f3])
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::
120 sage: R = PolynomialRing(QQ, 'x,y', order='lex')
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)
126 ([x + 1, x], 2*x + 1)
127 sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
129 sage: not any( g.lt().divides(m) for m in r.monomials()
135 If we get a zero remainder, then the numerator should belong to
136 the ideal generated by the denominators::
138 sage: set_random_seed()
139 sage: R = PolynomialRing(QQ, 'x,y,z')
140 sage: x,y,z = R.gens()
141 sage: s = ZZ.random_element(1,5).abs()
142 sage: gs = [ R.random_element() for idx in range(s) ]
143 sage: f = 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)
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::
152 sage: set_random_seed()
153 sage: R = PolynomialRing(QQ, 'x,y,z')
154 sage: x,y,z = R.gens()
155 sage: s = ZZ.random_element(1,5).abs()
156 sage: gs = [ R.random_element() for idx in range(s) ]
157 sage: f = R.random_element(ZZ.random_element(10).abs())
158 sage: (qs, r) = multidiv(f,gs)
159 sage: r + sum( qs[i]*gs[i] for i in range(len(gs)) ) == f
161 sage: r == 0 or (not any( g.lt().divides(m) for m in r.monomials()
175 division_occurred
= false
176 # If gs[i].lt() divides p.lt(), then this remainder will
177 # be zero and the quotient will be in R (and not the
178 # fraction ring, which is important).
179 (factor
, lt_r
) = p
.lt().quo_rem(gs
[i
].lt())
183 division_occurred
= true
186 if not division_occurred
: