Coverage for /usr/lib/python3/dist-packages/sympy/polys/sqfreetools.py: 13%

1"""Square-free decomposition algorithms and related tools. """ 

2 

3 

4from sympy.polys.densearith import ( 

5 dup_neg, dmp_neg, 

6 dup_sub, dmp_sub, 

7 dup_mul, 

8 dup_quo, dmp_quo, 

9 dup_mul_ground, dmp_mul_ground) 

10from sympy.polys.densebasic import ( 

11 dup_strip, 

12 dup_LC, dmp_ground_LC, 

13 dmp_zero_p, 

14 dmp_ground, 

15 dup_degree, dmp_degree, 

16 dmp_raise, dmp_inject, 

17 dup_convert) 

18from sympy.polys.densetools import ( 

19 dup_diff, dmp_diff, dmp_diff_in, 

20 dup_shift, dmp_compose, 

21 dup_monic, dmp_ground_monic, 

22 dup_primitive, dmp_ground_primitive) 

23from sympy.polys.euclidtools import ( 

24 dup_inner_gcd, dmp_inner_gcd, 

25 dup_gcd, dmp_gcd, 

26 dmp_resultant) 

27from sympy.polys.galoistools import ( 

28 gf_sqf_list, gf_sqf_part) 

29from sympy.polys.polyerrors import ( 

30 MultivariatePolynomialError, 

31 DomainError) 

32 

33def dup_sqf_p(f, K): 

34 """ 

35 Return ``True`` if ``f`` is a square-free polynomial in ``K[x]``. 

36 

37 Examples 

38 ======== 

39 

40 >>> from sympy.polys import ring, ZZ 

41 >>> R, x = ring("x", ZZ) 

42 

43 >>> R.dup_sqf_p(x**2 - 2*x + 1) 

44 False 

45 >>> R.dup_sqf_p(x**2 - 1) 

46 True 

47 

48 """ 

49 if not f: 

50 return True 

51 else: 

52 return not dup_degree(dup_gcd(f, dup_diff(f, 1, K), K)) 

53 

54 

55def dmp_sqf_p(f, u, K): 

56 """ 

57 Return ``True`` if ``f`` is a square-free polynomial in ``K[X]``. 

58 

59 Examples 

60 ======== 

61 

62 >>> from sympy.polys import ring, ZZ 

63 >>> R, x,y = ring("x,y", ZZ) 

64 

65 >>> R.dmp_sqf_p(x**2 + 2*x*y + y**2) 

66 False 

67 >>> R.dmp_sqf_p(x**2 + y**2) 

68 True 

69 

70 """ 

71 if dmp_zero_p(f, u): 

72 return True 

73 else: 

74 return not dmp_degree(dmp_gcd(f, dmp_diff(f, 1, u, K), u, K), u) 

75 

76 

77def dup_sqf_norm(f, K): 

78 """ 

79 Square-free norm of ``f`` in ``K[x]``, useful over algebraic domains. 

80 

81 Returns ``s``, ``f``, ``r``, such that ``g(x) = f(x-sa)`` and ``r(x) = Norm(g(x))`` 

82 is a square-free polynomial over K, where ``a`` is the algebraic extension of ``K``. 

83 

84 Examples 

85 ======== 

86 

87 >>> from sympy.polys import ring, QQ 

88 >>> from sympy import sqrt 

89 

90 >>> K = QQ.algebraic_field(sqrt(3)) 

91 >>> R, x = ring("x", K) 

92 >>> _, X = ring("x", QQ) 

93 

94 >>> s, f, r = R.dup_sqf_norm(x**2 - 2) 

95 

96 >>> s == 1 

97 True 

98 >>> f == x**2 + K([QQ(-2), QQ(0)])*x + 1 

99 True 

100 >>> r == X**4 - 10*X**2 + 1 

101 True 

102 

103 """ 

104 if not K.is_Algebraic: 

105 raise DomainError("ground domain must be algebraic") 

106 

107 s, g = 0, dmp_raise(K.mod.rep, 1, 0, K.dom) 

108 

109 while True: 

110 h, _ = dmp_inject(f, 0, K, front=True) 

111 r = dmp_resultant(g, h, 1, K.dom) 

112 

113 if dup_sqf_p(r, K.dom): 

114 break 

115 else: 

116 f, s = dup_shift(f, -K.unit, K), s + 1 

117 

118 return s, f, r 

119 

120 

121def dmp_sqf_norm(f, u, K): 

122 """ 

123 Square-free norm of ``f`` in ``K[X]``, useful over algebraic domains. 

124 

125 Returns ``s``, ``f``, ``r``, such that ``g(x) = f(x-sa)`` and ``r(x) = Norm(g(x))`` 

126 is a square-free polynomial over K, where ``a`` is the algebraic extension of ``K``. 

127 

128 Examples 

129 ======== 

130 

131 >>> from sympy.polys import ring, QQ 

132 >>> from sympy import I 

133 

134 >>> K = QQ.algebraic_field(I) 

135 >>> R, x, y = ring("x,y", K) 

136 >>> _, X, Y = ring("x,y", QQ) 

137 

138 >>> s, f, r = R.dmp_sqf_norm(x*y + y**2) 

139 

140 >>> s == 1 

141 True 

142 >>> f == x*y + y**2 + K([QQ(-1), QQ(0)])*y 

143 True 

144 >>> r == X**2*Y**2 + 2*X*Y**3 + Y**4 + Y**2 

145 True 

146 

147 """ 

148 if not u: 

149 return dup_sqf_norm(f, K) 

150 

151 if not K.is_Algebraic: 

152 raise DomainError("ground domain must be algebraic") 

153 

154 g = dmp_raise(K.mod.rep, u + 1, 0, K.dom) 

155 F = dmp_raise([K.one, -K.unit], u, 0, K) 

156 

157 s = 0 

158 

159 while True: 

160 h, _ = dmp_inject(f, u, K, front=True) 

161 r = dmp_resultant(g, h, u + 1, K.dom) 

162 

163 if dmp_sqf_p(r, u, K.dom): 

164 break 

165 else: 

166 f, s = dmp_compose(f, F, u, K), s + 1 

167 

168 return s, f, r 

169 

170 

171def dmp_norm(f, u, K): 

172 """ 

173 Norm of ``f`` in ``K[X1, ..., Xn]``, often not square-free. 

174 """ 

175 if not K.is_Algebraic: 

176 raise DomainError("ground domain must be algebraic") 

177 

178 g = dmp_raise(K.mod.rep, u + 1, 0, K.dom) 

179 h, _ = dmp_inject(f, u, K, front=True) 

180 

181 return dmp_resultant(g, h, u + 1, K.dom) 

182 

183 

184def dup_gf_sqf_part(f, K): 

185 """Compute square-free part of ``f`` in ``GF(p)[x]``. """ 

186 f = dup_convert(f, K, K.dom) 

187 g = gf_sqf_part(f, K.mod, K.dom) 

188 return dup_convert(g, K.dom, K) 

189 

190 

191def dmp_gf_sqf_part(f, u, K): 

192 """Compute square-free part of ``f`` in ``GF(p)[X]``. """ 

193 raise NotImplementedError('multivariate polynomials over finite fields') 

194 

195 

196def dup_sqf_part(f, K): 

197 """ 

198 Returns square-free part of a polynomial in ``K[x]``. 

199 

200 Examples 

201 ======== 

202 

203 >>> from sympy.polys import ring, ZZ 

204 >>> R, x = ring("x", ZZ) 

205 

206 >>> R.dup_sqf_part(x**3 - 3*x - 2) 

207 x**2 - x - 2 

208 

209 """ 

210 if K.is_FiniteField: 

211 return dup_gf_sqf_part(f, K) 

212 

213 if not f: 

214 return f 

215 

216 if K.is_negative(dup_LC(f, K)): 

217 f = dup_neg(f, K) 

218 

219 gcd = dup_gcd(f, dup_diff(f, 1, K), K) 

220 sqf = dup_quo(f, gcd, K) 

221 

222 if K.is_Field: 

223 return dup_monic(sqf, K) 

224 else: 

225 return dup_primitive(sqf, K)[1] 

226 

227 

228def dmp_sqf_part(f, u, K): 

229 """ 

230 Returns square-free part of a polynomial in ``K[X]``. 

231 

232 Examples 

233 ======== 

234 

235 >>> from sympy.polys import ring, ZZ 

236 >>> R, x,y = ring("x,y", ZZ) 

237 

238 >>> R.dmp_sqf_part(x**3 + 2*x**2*y + x*y**2) 

239 x**2 + x*y 

240 

241 """ 

242 if not u: 

243 return dup_sqf_part(f, K) 

244 

245 if K.is_FiniteField: 

246 return dmp_gf_sqf_part(f, u, K) 

247 

248 if dmp_zero_p(f, u): 

249 return f 

250 

251 if K.is_negative(dmp_ground_LC(f, u, K)): 

252 f = dmp_neg(f, u, K) 

253 

254 gcd = f 

255 for i in range(u+1): 

256 gcd = dmp_gcd(gcd, dmp_diff_in(f, 1, i, u, K), u, K) 

257 sqf = dmp_quo(f, gcd, u, K) 

258 

259 if K.is_Field: 

260 return dmp_ground_monic(sqf, u, K) 

261 else: 

262 return dmp_ground_primitive(sqf, u, K)[1] 

263 

264 

265def dup_gf_sqf_list(f, K, all=False): 

266 """Compute square-free decomposition of ``f`` in ``GF(p)[x]``. """ 

267 f = dup_convert(f, K, K.dom) 

268 

269 coeff, factors = gf_sqf_list(f, K.mod, K.dom, all=all) 

270 

271 for i, (f, k) in enumerate(factors): 

272 factors[i] = (dup_convert(f, K.dom, K), k) 

273 

274 return K.convert(coeff, K.dom), factors 

275 

276 

277def dmp_gf_sqf_list(f, u, K, all=False): 

278 """Compute square-free decomposition of ``f`` in ``GF(p)[X]``. """ 

279 raise NotImplementedError('multivariate polynomials over finite fields') 

280 

281 

282def dup_sqf_list(f, K, all=False): 

283 """ 

284 Return square-free decomposition of a polynomial in ``K[x]``. 

285 

286 Examples 

287 ======== 

288 

289 >>> from sympy.polys import ring, ZZ 

290 >>> R, x = ring("x", ZZ) 

291 

292 >>> f = 2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16 

293 

294 >>> R.dup_sqf_list(f) 

295 (2, [(x + 1, 2), (x + 2, 3)]) 

296 >>> R.dup_sqf_list(f, all=True) 

297 (2, [(1, 1), (x + 1, 2), (x + 2, 3)]) 

298 

299 """ 

300 if K.is_FiniteField: 

301 return dup_gf_sqf_list(f, K, all=all) 

302 

303 if K.is_Field: 

304 coeff = dup_LC(f, K) 

305 f = dup_monic(f, K) 

306 else: 

307 coeff, f = dup_primitive(f, K) 

308 

309 if K.is_negative(dup_LC(f, K)): 

310 f = dup_neg(f, K) 

311 coeff = -coeff 

312 

313 if dup_degree(f) <= 0: 

314 return coeff, [] 

315 

316 result, i = [], 1 

317 

318 h = dup_diff(f, 1, K) 

319 g, p, q = dup_inner_gcd(f, h, K) 

320 

321 while True: 

322 d = dup_diff(p, 1, K) 

323 h = dup_sub(q, d, K) 

324 

325 if not h: 

326 result.append((p, i)) 

327 break 

328 

329 g, p, q = dup_inner_gcd(p, h, K) 

330 

331 if all or dup_degree(g) > 0: 

332 result.append((g, i)) 

333 

334 i += 1 

335 

336 return coeff, result 

337 

338 

339def dup_sqf_list_include(f, K, all=False): 

340 """ 

341 Return square-free decomposition of a polynomial in ``K[x]``. 

342 

343 Examples 

344 ======== 

345 

346 >>> from sympy.polys import ring, ZZ 

347 >>> R, x = ring("x", ZZ) 

348 

349 >>> f = 2*x**5 + 16*x**4 + 50*x**3 + 76*x**2 + 56*x + 16 

350 

351 >>> R.dup_sqf_list_include(f) 

352 [(2, 1), (x + 1, 2), (x + 2, 3)] 

353 >>> R.dup_sqf_list_include(f, all=True) 

354 [(2, 1), (x + 1, 2), (x + 2, 3)] 

355 

356 """ 

357 coeff, factors = dup_sqf_list(f, K, all=all) 

358 

359 if factors and factors[0][1] == 1: 

360 g = dup_mul_ground(factors[0][0], coeff, K) 

361 return [(g, 1)] + factors[1:] 

362 else: 

363 g = dup_strip([coeff]) 

364 return [(g, 1)] + factors 

365 

366 

367def dmp_sqf_list(f, u, K, all=False): 

368 """ 

369 Return square-free decomposition of a polynomial in ``K[X]``. 

370 

371 Examples 

372 ======== 

373 

374 >>> from sympy.polys import ring, ZZ 

375 >>> R, x,y = ring("x,y", ZZ) 

376 

377 >>> f = x**5 + 2*x**4*y + x**3*y**2 

378 

379 >>> R.dmp_sqf_list(f) 

380 (1, [(x + y, 2), (x, 3)]) 

381 >>> R.dmp_sqf_list(f, all=True) 

382 (1, [(1, 1), (x + y, 2), (x, 3)]) 

383 

384 """ 

385 if not u: 

386 return dup_sqf_list(f, K, all=all) 

387 

388 if K.is_FiniteField: 

389 return dmp_gf_sqf_list(f, u, K, all=all) 

390 

391 if K.is_Field: 

392 coeff = dmp_ground_LC(f, u, K) 

393 f = dmp_ground_monic(f, u, K) 

394 else: 

395 coeff, f = dmp_ground_primitive(f, u, K) 

396 

397 if K.is_negative(dmp_ground_LC(f, u, K)): 

398 f = dmp_neg(f, u, K) 

399 coeff = -coeff 

400 

401 if dmp_degree(f, u) <= 0: 

402 return coeff, [] 

403 

404 result, i = [], 1 

405 

406 h = dmp_diff(f, 1, u, K) 

407 g, p, q = dmp_inner_gcd(f, h, u, K) 

408 

409 while True: 

410 d = dmp_diff(p, 1, u, K) 

411 h = dmp_sub(q, d, u, K) 

412 

413 if dmp_zero_p(h, u): 

414 result.append((p, i)) 

415 break 

416 

417 g, p, q = dmp_inner_gcd(p, h, u, K) 

418 

419 if all or dmp_degree(g, u) > 0: 

420 result.append((g, i)) 

421 

422 i += 1 

423 

424 return coeff, result 

425 

426 

427def dmp_sqf_list_include(f, u, K, all=False): 

428 """ 

429 Return square-free decomposition of a polynomial in ``K[x]``. 

430 

431 Examples 

432 ======== 

433 

434 >>> from sympy.polys import ring, ZZ 

435 >>> R, x,y = ring("x,y", ZZ) 

436 

437 >>> f = x**5 + 2*x**4*y + x**3*y**2 

438 

439 >>> R.dmp_sqf_list_include(f) 

440 [(1, 1), (x + y, 2), (x, 3)] 

441 >>> R.dmp_sqf_list_include(f, all=True) 

442 [(1, 1), (x + y, 2), (x, 3)] 

443 

444 """ 

445 if not u: 

446 return dup_sqf_list_include(f, K, all=all) 

447 

448 coeff, factors = dmp_sqf_list(f, u, K, all=all) 

449 

450 if factors and factors[0][1] == 1: 

451 g = dmp_mul_ground(factors[0][0], coeff, u, K) 

452 return [(g, 1)] + factors[1:] 

453 else: 

454 g = dmp_ground(coeff, u) 

455 return [(g, 1)] + factors 

456 

457 

458def dup_gff_list(f, K): 

459 """ 

460 Compute greatest factorial factorization of ``f`` in ``K[x]``. 

461 

462 Examples 

463 ======== 

464 

465 >>> from sympy.polys import ring, ZZ 

466 >>> R, x = ring("x", ZZ) 

467 

468 >>> R.dup_gff_list(x**5 + 2*x**4 - x**3 - 2*x**2) 

469 [(x, 1), (x + 2, 4)] 

470 

471 """ 

472 if not f: 

473 raise ValueError("greatest factorial factorization doesn't exist for a zero polynomial") 

474 

475 f = dup_monic(f, K) 

476 

477 if not dup_degree(f): 

478 return [] 

479 else: 

480 g = dup_gcd(f, dup_shift(f, K.one, K), K) 

481 H = dup_gff_list(g, K) 

482 

483 for i, (h, k) in enumerate(H): 

484 g = dup_mul(g, dup_shift(h, -K(k), K), K) 

485 H[i] = (h, k + 1) 

486 

487 f = dup_quo(f, g, K) 

488 

489 if not dup_degree(f): 

490 return H 

491 else: 

492 return [(f, 1)] + H 

493 

494 

495def dmp_gff_list(f, u, K): 

496 """ 

497 Compute greatest factorial factorization of ``f`` in ``K[X]``. 

498 

499 Examples 

500 ======== 

501 

502 >>> from sympy.polys import ring, ZZ 

503 >>> R, x,y = ring("x,y", ZZ) 

504 

505 """ 

506 if not u: 

507 return dup_gff_list(f, K) 

508 else: 

509 raise MultivariatePolynomialError(f)