Coverage for /usr/lib/python3/dist-packages/sympy/polys/agca/ideals.py: 39%

1"""Computations with ideals of polynomial rings.""" 

2 

3from sympy.polys.polyerrors import CoercionFailed 

4from sympy.polys.polyutils import IntegerPowerable 

5 

6 

7class Ideal(IntegerPowerable): 

8 """ 

9 Abstract base class for ideals. 

10 

11 Do not instantiate - use explicit constructors in the ring class instead: 

12 

13 >>> from sympy import QQ 

14 >>> from sympy.abc import x 

15 >>> QQ.old_poly_ring(x).ideal(x+1) 

16 <x + 1> 

17 

18 Attributes 

19 

20 - ring - the ring this ideal belongs to 

21 

22 Non-implemented methods: 

23 

24 - _contains_elem 

25 - _contains_ideal 

26 - _quotient 

27 - _intersect 

28 - _union 

29 - _product 

30 - is_whole_ring 

31 - is_zero 

32 - is_prime, is_maximal, is_primary, is_radical 

33 - is_principal 

34 - height, depth 

35 - radical 

36 

37 Methods that likely should be overridden in subclasses: 

38 

39 - reduce_element 

40 """ 

41 

42 def _contains_elem(self, x): 

43 """Implementation of element containment.""" 

44 raise NotImplementedError 

45 

46 def _contains_ideal(self, I): 

47 """Implementation of ideal containment.""" 

48 raise NotImplementedError 

49 

50 def _quotient(self, J): 

51 """Implementation of ideal quotient.""" 

52 raise NotImplementedError 

53 

54 def _intersect(self, J): 

55 """Implementation of ideal intersection.""" 

56 raise NotImplementedError 

57 

58 def is_whole_ring(self): 

59 """Return True if ``self`` is the whole ring.""" 

60 raise NotImplementedError 

61 

62 def is_zero(self): 

63 """Return True if ``self`` is the zero ideal.""" 

64 raise NotImplementedError 

65 

66 def _equals(self, J): 

67 """Implementation of ideal equality.""" 

68 return self._contains_ideal(J) and J._contains_ideal(self) 

69 

70 def is_prime(self): 

71 """Return True if ``self`` is a prime ideal.""" 

72 raise NotImplementedError 

73 

74 def is_maximal(self): 

75 """Return True if ``self`` is a maximal ideal.""" 

76 raise NotImplementedError 

77 

78 def is_radical(self): 

79 """Return True if ``self`` is a radical ideal.""" 

80 raise NotImplementedError 

81 

82 def is_primary(self): 

83 """Return True if ``self`` is a primary ideal.""" 

84 raise NotImplementedError 

85 

86 def is_principal(self): 

87 """Return True if ``self`` is a principal ideal.""" 

88 raise NotImplementedError 

89 

90 def radical(self): 

91 """Compute the radical of ``self``.""" 

92 raise NotImplementedError 

93 

94 def depth(self): 

95 """Compute the depth of ``self``.""" 

96 raise NotImplementedError 

97 

98 def height(self): 

99 """Compute the height of ``self``.""" 

100 raise NotImplementedError 

101 

102 # TODO more 

103 

104 # non-implemented methods end here 

105 

106 def __init__(self, ring): 

107 self.ring = ring 

108 

109 def _check_ideal(self, J): 

110 """Helper to check ``J`` is an ideal of our ring.""" 

111 if not isinstance(J, Ideal) or J.ring != self.ring: 

112 raise ValueError( 

113 'J must be an ideal of %s, got %s' % (self.ring, J)) 

114 

115 def contains(self, elem): 

116 """ 

117 Return True if ``elem`` is an element of this ideal. 

118 

119 Examples 

120 ======== 

121 

122 >>> from sympy.abc import x 

123 >>> from sympy import QQ 

124 >>> QQ.old_poly_ring(x).ideal(x+1, x-1).contains(3) 

125 True 

126 >>> QQ.old_poly_ring(x).ideal(x**2, x**3).contains(x) 

127 False 

128 """ 

129 return self._contains_elem(self.ring.convert(elem)) 

130 

131 def subset(self, other): 

132 """ 

133 Returns True if ``other`` is is a subset of ``self``. 

134 

135 Here ``other`` may be an ideal. 

136 

137 Examples 

138 ======== 

139 

140 >>> from sympy.abc import x 

141 >>> from sympy import QQ 

142 >>> I = QQ.old_poly_ring(x).ideal(x+1) 

143 >>> I.subset([x**2 - 1, x**2 + 2*x + 1]) 

144 True 

145 >>> I.subset([x**2 + 1, x + 1]) 

146 False 

147 >>> I.subset(QQ.old_poly_ring(x).ideal(x**2 - 1)) 

148 True 

149 """ 

150 if isinstance(other, Ideal): 

151 return self._contains_ideal(other) 

152 return all(self._contains_elem(x) for x in other) 

153 

154 def quotient(self, J, **opts): 

155 r""" 

156 Compute the ideal quotient of ``self`` by ``J``. 

157 

158 That is, if ``self`` is the ideal `I`, compute the set 

159 `I : J = \{x \in R | xJ \subset I \}`. 

160 

161 Examples 

162 ======== 

163 

164 >>> from sympy.abc import x, y 

165 >>> from sympy import QQ 

166 >>> R = QQ.old_poly_ring(x, y) 

167 >>> R.ideal(x*y).quotient(R.ideal(x)) 

168 <y> 

169 """ 

170 self._check_ideal(J) 

171 return self._quotient(J, **opts) 

172 

173 def intersect(self, J): 

174 """ 

175 Compute the intersection of self with ideal J. 

176 

177 Examples 

178 ======== 

179 

180 >>> from sympy.abc import x, y 

181 >>> from sympy import QQ 

182 >>> R = QQ.old_poly_ring(x, y) 

183 >>> R.ideal(x).intersect(R.ideal(y)) 

184 <x*y> 

185 """ 

186 self._check_ideal(J) 

187 return self._intersect(J) 

188 

189 def saturate(self, J): 

190 r""" 

191 Compute the ideal saturation of ``self`` by ``J``. 

192 

193 That is, if ``self`` is the ideal `I`, compute the set 

194 `I : J^\infty = \{x \in R | xJ^n \subset I \text{ for some } n\}`. 

195 """ 

196 raise NotImplementedError 

197 # Note this can be implemented using repeated quotient 

198 

199 def union(self, J): 

200 """ 

201 Compute the ideal generated by the union of ``self`` and ``J``. 

202 

203 Examples 

204 ======== 

205 

206 >>> from sympy.abc import x 

207 >>> from sympy import QQ 

208 >>> 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) 

209 True 

210 """ 

211 self._check_ideal(J) 

212 return self._union(J) 

213 

214 def product(self, J): 

215 r""" 

216 Compute the ideal product of ``self`` and ``J``. 

217 

218 That is, compute the ideal generated by products `xy`, for `x` an element 

219 of ``self`` and `y \in J`. 

220 

221 Examples 

222 ======== 

223 

224 >>> from sympy.abc import x, y 

225 >>> from sympy import QQ 

226 >>> QQ.old_poly_ring(x, y).ideal(x).product(QQ.old_poly_ring(x, y).ideal(y)) 

227 <x*y> 

228 """ 

229 self._check_ideal(J) 

230 return self._product(J) 

231 

232 def reduce_element(self, x): 

233 """ 

234 Reduce the element ``x`` of our ring modulo the ideal ``self``. 

235 

236 Here "reduce" has no specific meaning: it could return a unique normal 

237 form, simplify the expression a bit, or just do nothing. 

238 """ 

239 return x 

240 

241 def __add__(self, e): 

242 if not isinstance(e, Ideal): 

243 R = self.ring.quotient_ring(self) 

244 if isinstance(e, R.dtype): 

245 return e 

246 if isinstance(e, R.ring.dtype): 

247 return R(e) 

248 return R.convert(e) 

249 self._check_ideal(e) 

250 return self.union(e) 

251 

252 __radd__ = __add__ 

253 

254 def __mul__(self, e): 

255 if not isinstance(e, Ideal): 

256 try: 

257 e = self.ring.ideal(e) 

258 except CoercionFailed: 

259 return NotImplemented 

260 self._check_ideal(e) 

261 return self.product(e) 

262 

263 __rmul__ = __mul__ 

264 

265 def _zeroth_power(self): 

266 return self.ring.ideal(1) 

267 

268 def _first_power(self): 

269 # Raising to any power but 1 returns a new instance. So we mult by 1 

270 # here so that the first power is no exception. 

271 return self * 1 

272 

273 def __eq__(self, e): 

274 if not isinstance(e, Ideal) or e.ring != self.ring: 

275 return False 

276 return self._equals(e) 

277 

278 def __ne__(self, e): 

279 return not (self == e) 

280 

281 

282class ModuleImplementedIdeal(Ideal): 

283 """ 

284 Ideal implementation relying on the modules code. 

285 

286 Attributes: 

287 

288 - _module - the underlying module 

289 """ 

290 

291 def __init__(self, ring, module): 

292 Ideal.__init__(self, ring) 

293 self._module = module 

294 

295 def _contains_elem(self, x): 

296 return self._module.contains([x]) 

297 

298 def _contains_ideal(self, J): 

299 if not isinstance(J, ModuleImplementedIdeal): 

300 raise NotImplementedError 

301 return self._module.is_submodule(J._module) 

302 

303 def _intersect(self, J): 

304 if not isinstance(J, ModuleImplementedIdeal): 

305 raise NotImplementedError 

306 return self.__class__(self.ring, self._module.intersect(J._module)) 

307 

308 def _quotient(self, J, **opts): 

309 if not isinstance(J, ModuleImplementedIdeal): 

310 raise NotImplementedError 

311 return self._module.module_quotient(J._module, **opts) 

312 

313 def _union(self, J): 

314 if not isinstance(J, ModuleImplementedIdeal): 

315 raise NotImplementedError 

316 return self.__class__(self.ring, self._module.union(J._module)) 

317 

318 @property 

319 def gens(self): 

320 """ 

321 Return generators for ``self``. 

322 

323 Examples 

324 ======== 

325 

326 >>> from sympy import QQ 

327 >>> from sympy.abc import x, y 

328 >>> list(QQ.old_poly_ring(x, y).ideal(x, y, x**2 + y).gens) 

329 [x, y, x**2 + y] 

330 """ 

331 return (x[0] for x in self._module.gens) 

332 

333 def is_zero(self): 

334 """ 

335 Return True if ``self`` is the zero ideal. 

336 

337 Examples 

338 ======== 

339 

340 >>> from sympy.abc import x 

341 >>> from sympy import QQ 

342 >>> QQ.old_poly_ring(x).ideal(x).is_zero() 

343 False 

344 >>> QQ.old_poly_ring(x).ideal().is_zero() 

345 True 

346 """ 

347 return self._module.is_zero() 

348 

349 def is_whole_ring(self): 

350 """ 

351 Return True if ``self`` is the whole ring, i.e. one generator is a unit. 

352 

353 Examples 

354 ======== 

355 

356 >>> from sympy.abc import x 

357 >>> from sympy import QQ, ilex 

358 >>> QQ.old_poly_ring(x).ideal(x).is_whole_ring() 

359 False 

360 >>> QQ.old_poly_ring(x).ideal(3).is_whole_ring() 

361 True 

362 >>> QQ.old_poly_ring(x, order=ilex).ideal(2 + x).is_whole_ring() 

363 True 

364 """ 

365 return self._module.is_full_module() 

366 

367 def __repr__(self): 

368 from sympy.printing.str import sstr 

369 return '<' + ','.join(sstr(x) for [x] in self._module.gens) + '>' 

370 

371 # NOTE this is the only method using the fact that the module is a SubModule 

372 def _product(self, J): 

373 if not isinstance(J, ModuleImplementedIdeal): 

374 raise NotImplementedError 

375 return self.__class__(self.ring, self._module.submodule( 

376 *[[x*y] for [x] in self._module.gens for [y] in J._module.gens])) 

377 

378 def in_terms_of_generators(self, e): 

379 """ 

380 Express ``e`` in terms of the generators of ``self``. 

381 

382 Examples 

383 ======== 

384 

385 >>> from sympy.abc import x 

386 >>> from sympy import QQ 

387 >>> I = QQ.old_poly_ring(x).ideal(x**2 + 1, x) 

388 >>> I.in_terms_of_generators(1) 

389 [1, -x] 

390 """ 

391 return self._module.in_terms_of_generators([e]) 

392 

393 def reduce_element(self, x, **options): 

394 return self._module.reduce_element([x], **options)[0]