]> gitweb.michael.orlitzky.com - sage.d.git/blob - mjo/polynomial.py
eja: rename MatrixEJA to HermitianMatrixEJA.
[sage.d.git] / 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)