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

[was]

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.

[cwitty]

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.)

[was]

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

[mabshoff]

Notice that #4041 is a duplicate of this ticket.

Cheers,

Michael

[lftabera]

Another example from #9408

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

[katestange]

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.

[jdemeyer]

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?

[lftabera]

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.

[was]

Replying to jdemeyer:

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.

[Bouillaguet]

I just ran into this issue

[pbruin]

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.

[pbruin]

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.

[git]

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

[pbruin]

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.

[git]

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

[git]

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

[git]

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

[pbruin]

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

[git]

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

​d122714

Merge branch 'develop' into ticket/252-number_fields

[kartikv]

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...

[pbruin]

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)

[pbruin]

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.

[git]

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

​fd2743f

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

[kartikv]

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.

[git]

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

​d4660f1

Trac 252: additional examples

[git]

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

​8b86c52

Trac 252: additional examples

[pbruin]

Replying to kartikv:

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).

[kartikv]

Perfect.