1"""Computations with ideals of polynomial rings.""" 2 3from functools import reduce 4 5from sympy.polys.polyerrors import CoercionFailed 6 7 8class Ideal: 9 """ 10 Abstract base class for ideals. 11 12 Do not instantiate - use explicit constructors in the ring class instead: 13 14 >>> from sympy import QQ 15 >>> from sympy.abc import x 16 >>> QQ.old_poly_ring(x).ideal(x+1) 17 <x + 1> 18 19 Attributes 20 21 - ring - the ring this ideal belongs to 22 23 Non-implemented methods: 24 25 - _contains_elem 26 - _contains_ideal 27 - _quotient 28 - _intersect 29 - _union 30 - _product 31 - is_whole_ring 32 - is_zero 33 - is_prime, is_maximal, is_primary, is_radical 34 - is_principal 35 - height, depth 36 - radical 37 38 Methods that likely should be overridden in subclasses: 39 40 - reduce_element 41 """ 42 43 def _contains_elem(self, x): 44 """Implementation of element containment.""" 45 raise NotImplementedError 46 47 def _contains_ideal(self, I): 48 """Implementation of ideal containment.""" 49 raise NotImplementedError 50 51 def _quotient(self, J): 52 """Implementation of ideal quotient.""" 53 raise NotImplementedError 54 55 def _intersect(self, J): 56 """Implementation of ideal intersection.""" 57 raise NotImplementedError 58 59 def is_whole_ring(self): 60 """Return True if ``self`` is the whole ring.""" 61 raise NotImplementedError 62 63 def is_zero(self): 64 """Return True if ``self`` is the zero ideal.""" 65 raise NotImplementedError 66 67 def _equals(self, J): 68 """Implementation of ideal equality.""" 69 return self._contains_ideal(J) and J._contains_ideal(self) 70 71 def is_prime(self): 72 """Return True if ``self`` is a prime ideal.""" 73 raise NotImplementedError 74 75 def is_maximal(self): 76 """Return True if ``self`` is a maximal ideal.""" 77 raise NotImplementedError 78 79 def is_radical(self): 80 """Return True if ``self`` is a radical ideal.""" 81 raise NotImplementedError 82 83 def is_primary(self): 84 """Return True if ``self`` is a primary ideal.""" 85 raise NotImplementedError 86 87 def is_principal(self): 88 """Return True if ``self`` is a principal ideal.""" 89 raise NotImplementedError 90 91 def radical(self): 92 """Compute the radical of ``self``.""" 93 raise NotImplementedError 94 95 def depth(self): 96 """Compute the depth of ``self``.""" 97 raise NotImplementedError 98 99 def height(self): 100 """Compute the height of ``self``.""" 101 raise NotImplementedError 102 103 # TODO more 104 105 # non-implemented methods end here 106 107 def __init__(self, ring): 108 self.ring = ring 109 110 def _check_ideal(self, J): 111 """Helper to check ``J`` is an ideal of our ring.""" 112 if not isinstance(J, Ideal) or J.ring != self.ring: 113 raise ValueError( 114 'J must be an ideal of %s, got %s' % (self.ring, J)) 115 116 def contains(self, elem): 117 """ 118 Return True if ``elem`` is an element of this ideal. 119 120 Examples 121 ======== 122 123 >>> from sympy.abc import x 124 >>> from sympy import QQ 125 >>> QQ.old_poly_ring(x).ideal(x+1, x-1).contains(3) 126 True 127 >>> QQ.old_poly_ring(x).ideal(x**2, x**3).contains(x) 128 False 129 """ 130 return self._contains_elem(self.ring.convert(elem)) 131 132 def subset(self, other): 133 """ 134 Returns True if ``other`` is is a subset of ``self``. 135 136 Here ``other`` may be an ideal. 137 138 Examples 139 ======== 140 141 >>> from sympy.abc import x 142 >>> from sympy import QQ 143 >>> I = QQ.old_poly_ring(x).ideal(x+1) 144 >>> I.subset([x**2 - 1, x**2 + 2*x + 1]) 145 True 146 >>> I.subset([x**2 + 1, x + 1]) 147 False 148 >>> I.subset(QQ.old_poly_ring(x).ideal(x**2 - 1)) 149 True 150 """ 151 if isinstance(other, Ideal): 152 return self._contains_ideal(other) 153 return all(self._contains_elem(x) for x in other) 154 155 def quotient(self, J, **opts): 156 r""" 157 Compute the ideal quotient of ``self`` by ``J``. 158 159 That is, if ``self`` is the ideal `I`, compute the set 160 `I : J = \{x \in R | xJ \subset I \}`. 161 162 Examples 163 ======== 164 165 >>> from sympy.abc import x, y 166 >>> from sympy import QQ 167 >>> R = QQ.old_poly_ring(x, y) 168 >>> R.ideal(x*y).quotient(R.ideal(x)) 169 <y> 170 """ 171 self._check_ideal(J) 172 return self._quotient(J, **opts) 173 174 def intersect(self, J): 175 """ 176 Compute the intersection of self with ideal J. 177 178 Examples 179 ======== 180 181 >>> from sympy.abc import x, y 182 >>> from sympy import QQ 183 >>> R = QQ.old_poly_ring(x, y) 184 >>> R.ideal(x).intersect(R.ideal(y)) 185 <x*y> 186 """ 187 self._check_ideal(J) 188 return self._intersect(J) 189 190 def saturate(self, J): 191 r""" 192 Compute the ideal saturation of ``self`` by ``J``. 193 194 That is, if ``self`` is the ideal `I`, compute the set 195 `I : J^\infty = \{x \in R | xJ^n \subset I \text{ for some } n\}`. 196 """ 197 raise NotImplementedError 198 # Note this can be implemented using repeated quotient 199 200 def union(self, J): 201 """ 202 Compute the ideal generated by the union of ``self`` and ``J``. 203 204 Examples 205 ======== 206 207 >>> from sympy.abc import x 208 >>> from sympy import QQ 209 >>> QQ.old_poly_ring(x).ideal(x**2 - 1).union(QQ.old_poly_ring(x).ideal((x+1)**2)) == QQ.old_poly_ring(x).ideal(x+1) 210 True 211 """ 212 self._check_ideal(J) 213 return self._union(J) 214 215 def product(self, J): 216 r""" 217 Compute the ideal product of ``self`` and ``J``. 218 219 That is, compute the ideal generated by products `xy`, for `x` an element 220 of ``self`` and `y \in J`. 221 222 Examples 223 ======== 224 225 >>> from sympy.abc import x, y 226 >>> from sympy import QQ 227 >>> QQ.old_poly_ring(x, y).ideal(x).product(QQ.old_poly_ring(x, y).ideal(y)) 228 <x*y> 229 """ 230 self._check_ideal(J) 231 return self._product(J) 232 233 def reduce_element(self, x): 234 """ 235 Reduce the element ``x`` of our ring modulo the ideal ``self``. 236 237 Here "reduce" has no specific meaning: it could return a unique normal 238 form, simplify the expression a bit, or just do nothing. 239 """ 240 return x 241 242 def __add__(self, e): 243 if not isinstance(e, Ideal): 244 R = self.ring.quotient_ring(self) 245 if isinstance(e, R.dtype): 246 return e 247 if isinstance(e, R.ring.dtype): 248 return R(e) 249 return R.convert(e) 250 self._check_ideal(e) 251 return self.union(e) 252 253 __radd__ = __add__ 254 255 def __mul__(self, e): 256 if not isinstance(e, Ideal): 257 try: 258 e = self.ring.ideal(e) 259 except CoercionFailed: 260 return NotImplemented 261 self._check_ideal(e) 262 return self.product(e) 263 264 __rmul__ = __mul__ 265 266 def __pow__(self, exp): 267 if exp < 0: 268 raise NotImplementedError 269 # TODO exponentiate by squaring 270 return reduce(lambda x, y: x*y, [self]*exp, self.ring.ideal(1)) 271 272 def __eq__(self, e): 273 if not isinstance(e, Ideal) or e.ring != self.ring: 274 return False 275 return self._equals(e) 276 277 def __ne__(self, e): 278 return not (self == e) 279 280 281class ModuleImplementedIdeal(Ideal): 282 """ 283 Ideal implementation relying on the modules code. 284 285 Attributes: 286 287 - _module - the underlying module 288 """ 289 290 def __init__(self, ring, module): 291 Ideal.__init__(self, ring) 292 self._module = module 293 294 def _contains_elem(self, x): 295 return self._module.contains([x]) 296 297 def _contains_ideal(self, J): 298 if not isinstance(J, ModuleImplementedIdeal): 299 raise NotImplementedError 300 return self._module.is_submodule(J._module) 301 302 def _intersect(self, J): 303 if not isinstance(J, ModuleImplementedIdeal): 304 raise NotImplementedError 305 return self.__class__(self.ring, self._module.intersect(J._module)) 306 307 def _quotient(self, J, **opts): 308 if not isinstance(J, ModuleImplementedIdeal): 309 raise NotImplementedError 310 return self._module.module_quotient(J._module, **opts) 311 312 def _union(self, J): 313 if not isinstance(J, ModuleImplementedIdeal): 314 raise NotImplementedError 315 return self.__class__(self.ring, self._module.union(J._module)) 316 317 @property 318 def gens(self): 319 """ 320 Return generators for ``self``. 321 322 Examples 323 ======== 324 325 >>> from sympy import QQ 326 >>> from sympy.abc import x, y 327 >>> list(QQ.old_poly_ring(x, y).ideal(x, y, x**2 + y).gens) 328 [x, y, x**2 + y] 329 """ 330 return (x[0] for x in self._module.gens) 331 332 def is_zero(self): 333 """ 334 Return True if ``self`` is the zero ideal. 335 336 Examples 337 ======== 338 339 >>> from sympy.abc import x 340 >>> from sympy import QQ 341 >>> QQ.old_poly_ring(x).ideal(x).is_zero() 342 False 343 >>> QQ.old_poly_ring(x).ideal().is_zero() 344 True 345 """ 346 return self._module.is_zero() 347 348 def is_whole_ring(self): 349 """ 350 Return True if ``self`` is the whole ring, i.e. one generator is a unit. 351 352 Examples 353 ======== 354 355 >>> from sympy.abc import x 356 >>> from sympy import QQ, ilex 357 >>> QQ.old_poly_ring(x).ideal(x).is_whole_ring() 358 False 359 >>> QQ.old_poly_ring(x).ideal(3).is_whole_ring() 360 True 361 >>> QQ.old_poly_ring(x, order=ilex).ideal(2 + x).is_whole_ring() 362 True 363 """ 364 return self._module.is_full_module() 365 366 def __repr__(self): 367 from sympy import sstr 368 return '<' + ','.join(sstr(x) for [x] in self._module.gens) + '>' 369 370 # NOTE this is the only method using the fact that the module is a SubModule 371 def _product(self, J): 372 if not isinstance(J, ModuleImplementedIdeal): 373 raise NotImplementedError 374 return self.__class__(self.ring, self._module.submodule( 375 *[[x*y] for [x] in self._module.gens for [y] in J._module.gens])) 376 377 def in_terms_of_generators(self, e): 378 """ 379 Express ``e`` in terms of the generators of ``self``. 380 381 Examples 382 ======== 383 384 >>> from sympy.abc import x 385 >>> from sympy import QQ 386 >>> I = QQ.old_poly_ring(x).ideal(x**2 + 1, x) 387 >>> I.in_terms_of_generators(1) 388 [1, -x] 389 """ 390 return self._module.in_terms_of_generators([e]) 391 392 def reduce_element(self, x, **options): 393 return self._module.reduce_element([x], **options)[0] 394