Opened 16 years ago

Closed 7 years ago

# Make number fields work when polynomial not integral or not monic.

Reported by: Owned by: William Stein David Loeffler major sage-6.4 number fields Kate Stange, Charles Bouillaguet Peter Bruin Kartik Venkatram N/A 8b86c52 8b86c525a43dcfbab01224e3416722a1b29a9880 #18740

The goal of this ticket is to make number fields work when the defining polynomial is not integral or not monic.

If the user specifies a non-integral or non-monic polynomial to define an absolute or relative number field, we define the corresponding PARI number field by a monic integral polynomial obtained from the PARI functions `polredbest` and `rnfpolredbest`, respectively.

The new methods `NumberField_generic._pari_absolute_structure()` and `NumberField_relative._pari_relative_structure()` return the data needed to convert elements between the Sage `NumberField` and the PARI `nf` structure.

### comment:1 Changed 15 years ago by Michael Abshoff

Milestone: → Sage-2.10

### comment:2 Changed 15 years ago by Carl Witty

You may find sage.rings.algebraic_real.clear_denominators() useful here. (If so, the function should probably be moved to a more sensible place, and perhaps renamed.)

### comment:3 Changed 15 years ago by William Stein

Milestone: Sage-2.10 → sage-2.9.1

The example above works. But other things don't:

```sage: R.<x> = QQ[]
sage: sage: L.<b> = NumberField(x^2-1/2)
sage: sage: L.discriminant()
8
sage: L.ring_of_integers()
boom
```

### comment:4 Changed 14 years ago by Michael Abshoff

Notice that #4041 is a duplicate of this ticket.

Cheers,

Michael

### comment:5 Changed 14 years ago by David Loeffler

Component: number theory → number fields changed from William Stein to David Loeffler

### comment:6 Changed 13 years ago by Luis Felipe Tabera Alonso

Report Upstream: → N/A

Another example from #9408

```sage: L.<a,b> = QQ[i].relativize(1) #Ok
sage: L.<a,b> = QQ[i].relativize(1/2) #PariError
```

### comment:7 Changed 12 years ago by Kate Stange

At least the pari errors could be changed to "not implemented" messages in the meantime? This is an error a new user may encounter. It would help them to know immediately that the problem is all non-integral coefficients, so they can program around it, and to know that it is known to the developers.

### comment:9 follow-up:  11 Changed 11 years ago by Jeroen Demeyer

I agree that fixing this would be very nice, but also would require completely reworking the number field code. I think it is feasible, but do we really want to put that much effort into this?

### comment:10 Changed 11 years ago by Luis Felipe Tabera Alonso

I, for myself would like to see this fixed. I would fix this myself if I had time...

In any case, current situation in Sage is not admissible. If we decide not to fix this then, should we allow to define number fields with nonintegral generators? This would also mean a lot of effort.

### comment:11 in reply to:  9 Changed 11 years ago by William Stein

I agree that fixing this would be very nice, but also would require completely reworking the number field code. I think it is feasible, but do we really want to put that much effort into this?

I don't know about "we", but it is a total no brainer that this has to get done eventually. It is certainly easier than writing the number field code in the first place, which was hard, but not that hard.

### comment:12 Changed 10 years ago by Charles Bouillaguet

Cc: Charles Bouillaguet added sage-5.7 → sage-5.8 minor → major

I just ran into this issue

### comment:13 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11 → sage-5.12

### comment:14 Changed 9 years ago by For batch modifications

Milestone: sage-6.1 → sage-6.2

### comment:15 Changed 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:16 Changed 8 years ago by For batch modifications

Milestone: sage-6.3 → sage-6.4

### comment:17 Changed 8 years ago by Peter Bruin

In SageMath 6.7.beta1:

```sage: R.<x> = QQ[]
sage: L.<b> = NumberField(x^2-1/2)
sage: L.discriminant()
8
sage: L.ring_of_integers()
Maximal Order in Number Field in b with defining polynomial x^2 - 1/2
```

However, there are still problems; see e.g. #18243. We should make use of the fact that when one feeds a non-monic or non-integral polynomial `f` to PARI's `nfinit()`, it returns a pair `[nf, c]` where `nf` is an number field isomorphic to Q[x]/(f) and defined by a monic integral polynomial, and `c` is a root of `f` in `nf`.

### comment:18 Changed 8 years ago by Peter Bruin

Authors: → Peter Bruin → #18740

### comment:19 Changed 8 years ago by Peter Bruin

Branch: → u/pbruin/252-number_fields → 8d0e9cc46a967d0aa2c020365732fbaab84b996f

This branch is work in progress; it does not solve #18243 yet, and there are probably other places where it should be checked that non-integral and/or non-monic polynomials are supported.

### comment:20 Changed 8 years ago by git

Commit: 8d0e9cc46a967d0aa2c020365732fbaab84b996f → 78408430db0bd43a0cd1e886c0d6b42184bd6dd6

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​7840843 `Trac 252: allow non-monic and non-integral polynomials in number fields`

### comment:21 Changed 8 years ago by Peter Bruin

The examples in #14164 and #18243 now work. This is mostly finished, but it needs more doctests to show that number fields defined by non-monic and non-integral polynomials are supported.

### comment:22 Changed 8 years ago by git

Commit: 78408430db0bd43a0cd1e886c0d6b42184bd6dd6 → fce3c709dbeb1b7073b432527fe31a53eb7b8124

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​fce3c70 `Trac 252: allow non-monic and non-integral polynomials in number fields`

### comment:23 Changed 8 years ago by Peter Bruin

Description: modified (diff) new → needs_review

### comment:24 Changed 8 years ago by git

Commit: fce3c709dbeb1b7073b432527fe31a53eb7b8124 → 75756863cfd4ded5796d83696cf13f5ebb1670d2

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​566770a `Merge branch 'u/pbruin/18739-pari_rnf_conversion' into 6.8.b5` ​88fbd3d `trac #18379 doc typo in pari/gen` ​d27251d `trac #18739 raise into py3 syntax` ​5373b8e `Trac 18739: reviewer comments` ​bf87651 `Merge branch 'ticket/18739-pari_rnf_conversion' into ticket/18740-relative_number_fields` ​c661096 `Trac 18740: reduce overhead for relative number field elements` ​7575686 `Trac 252: allow non-monic and non-integral polynomials in number fields`

### comment:25 Changed 8 years ago by git

Commit: 75756863cfd4ded5796d83696cf13f5ebb1670d2 → b8fdeda84073d4c72e042cd64e68678e099d292e

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​b8fdeda `Trac 252: allow non-monic and non-integral polynomials in number fields`

### comment:26 Changed 8 years ago by Peter Bruin

The above version fixes `composite_fields()` to correctly solve #14164 and #18243.

### comment:27 Changed 7 years ago by git

Commit: b8fdeda84073d4c72e042cd64e68678e099d292e → d1227146064d0e4ebcaf313f6eeec5c70713dde3

Branch pushed to git repo; I updated commit sha1. New commits:

 ​d122714 `Merge branch 'develop' into ticket/252-number_fields`

### comment:28 Changed 7 years ago by Kartik Venkatram

Status: needs_review → needs_work

Something weird seems to be going on with factoring. This is "normal" behavior for a number field.

```sage: F.<a> = NumberField(x^3+x+1)
sage: F(2).factor()
2
sage: F(3).factor()
(a^2 + a + 2) * (-a + 1)
sage: (a^2 + a + 2).factor()
a^2 + a + 2
sage: F.factor(3)
(Fractional ideal (a^2 + a + 2)) * (Fractional ideal (-a + 1))
sage: (-a+1).factor()
-a + 1
```

This is not.

```sage: F.<a> = NumberField(2*x^3+x+1)
sage: F(2).factor()
(-47*a^2 + 21*a - 93/2) * (-1/2*a^2 + 1/2*a)^2 * (1/2*a^2 + 1/2*a)
sage: F.factor(2)
(Fractional ideal (-1/2*a^2 + 1/2*a))^2 * (Fractional ideal (1/2*a^2 + 1/2*a))
sage: (-47*a^2 + 21*a - 93/2).norm()
-8192
sage: (-47*a^2 + 21*a - 93/2).factor()
(3718815975/16384*a^2 - 1336872061/16384*a + 7884913157/32768) * (-1/2*a^2 + 1/2*a)^14 * (1/2*a^2 + 1/2*a)^-1
sage: (1/2*a^2 + 1/2*a).factor()
(13/512*a^2 - 11/512*a - 7/256) * (-1/2*a^2 + 1/2*a)^-4
```

Somehow, it's not controlling primes over the leading coefficient properly...

### comment:29 Changed 7 years ago by Peter Bruin

The underlying problem seems to be converting PARI ideals in Hilbert normal form to Sage ideals:

```sage: F.<a> = NumberField(2*x^3+x+1)
sage: Fp = F.pari_nf()
sage: I = F.ideal(2)
sage: Ip = I.pari_hnf()
sage: fact = Fp.idealfactor(Ip)
sage: Jp = fact[0, 0]
sage: Fp.idealnorm(Jp)
2
sage: J = F.ideal(Jp)
sage: J.norm()
1/2             # should be 2, like Fp.idealnorm(Jp)
```

### comment:30 Changed 7 years ago by Peter Bruin

Actually the bug is in the conversion from PARI elements expressed on the integral basis:

```sage: F.<a> = NumberField(2*x^3+x+1)
sage: b = F.random_element()
sage: F(F.pari_nf().nfalgtobasis(b)) == b
False  # should be True
```

I'm working on a patch.

### comment:31 Changed 7 years ago by git

Commit: d1227146064d0e4ebcaf313f6eeec5c70713dde3 → fd2743f092ecbffd79f49dc6cd18552631c407db

Branch pushed to git repo; I updated commit sha1. New commits:

 ​fd2743f `Trac 252: fix conversion from PARI elements expressed on the integral basis`

### comment:32 Changed 7 years ago by Peter Bruin

Status: needs_work → needs_review

### comment:33 follow-up:  36 Changed 7 years ago by Kartik Venkatram

Status: needs_review → needs_work

Positive review. I think there should probably be an example in the docstring to NumberField? that demonstrates/tests this functionality (since it has been missing for so long), but otherwise ready to submit. You're welcome to use my example or any of yours from deeper in the number field code.

### comment:34 Changed 7 years ago by git

Commit: fd2743f092ecbffd79f49dc6cd18552631c407db → d4660f119eb45da3d9520b5f3b598ca5a6753906

Branch pushed to git repo; I updated commit sha1. New commits:

 ​d4660f1 `Trac 252: additional examples`

### comment:35 Changed 7 years ago by git

Commit: d4660f119eb45da3d9520b5f3b598ca5a6753906 → 8b86c525a43dcfbab01224e3416722a1b29a9880

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​8b86c52 `Trac 252: additional examples`

### comment:36 in reply to:  33 Changed 7 years ago by Peter Bruin

Status: needs_work → needs_review

Positive review. I think there should probably be an example in the docstring to NumberField? that demonstrates/tests this functionality (since it has been missing for so long), but otherwise ready to submit. You're welcome to use my example or any of yours from deeper in the number field code.

Thanks for your comments. If you approve of the new examples you can set this to positive review (and remember to fill in your [real] name as reviewer).

### comment:37 Changed 7 years ago by Kartik Venkatram

Reviewers: → Kartik Venkatram needs_review → positive_review

Perfect.

### comment:38 Changed 7 years ago by Volker Braun

Branch: u/pbruin/252-number_fields → 8b86c525a43dcfbab01224e3416722a1b29a9880 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.