Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#28631 closed enhancement (fixed)

Implement polynomial factorization over universal cyclotomic field

Reported by: Sebastian Oehms Owned by:
Priority: major Milestone: sage-9.0
Component: number fields Keywords: universal cyclotomic field, factorization
Cc: Travis Scrimshaw 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 3 years ago by Sebastian Oehms

Branch: u/soehms/factorization_universal_cycl_field_28631

comment:2 Changed 3 years ago by Sebastian Oehms

Commit: a3c9a81a7ae393a66002153e4303b253c0eec478
Status: newneeds_review

I add an implementation of _factor_univariate_polynomial.


New commits:

a3c9a8128631: inital version

comment:3 Changed 3 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

LGTM.

comment:4 Changed 3 years ago by Sebastian Oehms

Thanks!

comment:5 Changed 3 years ago by Volker Braun

Branch: u/soehms/factorization_universal_cycl_field_28631a3c9a81a7ae393a66002153e4303b253c0eec478
Resolution: fixed
Status: positive_reviewclosed

comment:6 Changed 3 years ago by Vincent Delecroix

Commit: a3c9a81a7ae393a66002153e4303b253c0eec478

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 3 years ago by Vincent Delecroix (previous) (diff)

comment:7 in reply to:  6 Changed 3 years ago by Sebastian Oehms

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.