Opened 2 years ago

Closed 2 years ago

Last modified 2 years ago

#28631 closed enhancement (fixed)

Implement polynomial factorization over universal cyclotomic field

Reported by: soehms Owned by:
Priority: major Milestone: sage-9.0
Component: number fields Keywords: universal cyclotomic field, factorization
Cc: tscrim Merged in:
Authors: Sebastian Oehms Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: a3c9a81 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

Indeed, that hasn't been done so far:

sage: UCF = UniversalCyclotomicField()
sage: P.<x> = UCF[]
sage: p = x**5-1
sage: p.roots()
Traceback (most recent call last):
...
NotImplementedError: root finding for this polynomial not implemented

Change History (7)

comment:1 Changed 2 years ago by soehms

  • Branch set to u/soehms/factorization_universal_cycl_field_28631

comment:2 Changed 2 years ago by soehms

  • Commit set to a3c9a81a7ae393a66002153e4303b253c0eec478
  • Status changed from new to needs_review

I add an implementation of _factor_univariate_polynomial.


New commits:

a3c9a8128631: inital version

comment:3 Changed 2 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:4 Changed 2 years ago by soehms

Thanks!

comment:5 Changed 2 years ago by vbraun

  • Branch changed from u/soehms/factorization_universal_cycl_field_28631 to a3c9a81a7ae393a66002153e4303b253c0eec478
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:6 follow-up: Changed 2 years ago by vdelecroix

  • Commit a3c9a81a7ae393a66002153e4303b253c0eec478 deleted

What is your code supposed to do!?

sage: x = polygen(UCF)
sage: (x**2 - 3).factor()
x^2 - 3

But there is a square root

sage: UCF(3).sqrt()
E(12)^7 - E(12)^11
sage: UCF(3).sqrt()**2
3

I propose to simply revert all of what this ticket did in #28659.

Note that the sqrt used above is implemented for integers only since this is more or less trivial. But it fails for general UCF elements. Implementing more is definitely welcome

  • factorization of rational polynomials over UCF
  • square root for any UCF element

(these are non-trivial tasks)

Please be more careful with your code submissions and reviews. Code discussion is very welcome on sage-devel and sage-nt.

Last edited 2 years ago by vdelecroix (previous) (diff)

comment:7 in reply to: ↑ 6 Changed 2 years ago by soehms

Replying to vdelecroix:

Please be more careful with your code submissions and reviews. Code discussion is very welcome on sage-devel and sage-nt.

I'm sorry for that, Vincent, and will be more careful in future! I didn't become aware, that there was a serious reason that this was not implemented.

On the other hand, I think there are reasons, that Sage should be able to find roots of unity over the UCF. At least the following two:

1) Code which needs a root of unity over an unspecified ring should not need an separate implementation for UCF.

2) Sage is not only a tool for experts, but satisfies educational requirements, as well. But, what I've displayed in the ticket-description would at least cause irritations.

My code can be easily improved (adding two lines), in order to be not vastly any more. I will explain this in the new ticket.

Note: See TracTickets for help on using tickets.