Opened 3 years ago

Closed 3 years ago

# Implement polynomial factorization over universal cyclotomic field

Reported by: Owned by: Sebastian Oehms major sage-9.0 number fields universal cyclotomic field, factorization Travis Scrimshaw Sebastian Oehms Travis Scrimshaw N/A a3c9a81

### 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
```

### 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 new → needs_review

I add an implementation of `_factor_univariate_polynomial`.

New commits:

 ​a3c9a81 `28631: inital version`

### comment:3 Changed 3 years ago by Travis Scrimshaw

Reviewers: → Travis Scrimshaw needs_review → positive_review

LGTM.

Thanks!

### comment:5 Changed 3 years ago by Volker Braun

Branch: u/soehms/factorization_universal_cycl_field_28631 → a3c9a81a7ae393a66002153e4303b253c0eec478 → fixed positive_review → closed

### comment:6 follow-up:  7 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

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

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.