Opened 13 years ago
Closed 5 years ago
#252 closed defect (fixed)
Make number fields work when polynomial not integral or not monic.
Reported by:  was  Owned by:  davidloeffler 

Priority:  major  Milestone:  sage6.4 
Component:  number fields  Keywords:  
Cc:  katestange, Bouillaguet  Merged in:  
Authors:  Peter Bruin  Reviewers:  Kartik Venkatram 
Report Upstream:  N/A  Work issues:  
Branch:  8b86c52 (Commits)  Commit:  8b86c525a43dcfbab01224e3416722a1b29a9880 
Dependencies:  #18740  Stopgaps: 
Description (last modified by )
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 nonintegral or nonmonic 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.
Change History (38)
comment:1 Changed 12 years ago by
 Milestone set to Sage2.10
comment:2 Changed 12 years ago by
comment:3 Changed 12 years ago by
 Milestone changed from Sage2.10 to sage2.9.1
The example above works. But other things don't:
sage: R.<x> = QQ[] sage: sage: L.<b> = NumberField(x^21/2) sage: sage: L.discriminant() 8 sage: L.ring_of_integers() boom
comment:4 Changed 11 years ago by
comment:5 Changed 11 years ago by
 Component changed from number theory to number fields
 Owner changed from was to davidloeffler
comment:6 Changed 10 years ago by
 Report Upstream set to 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 9 years ago by
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 nonintegral coefficients, so they can program around it, and to know that it is known to the developers.
comment:8 Changed 9 years ago by
 Cc katestange added
comment:9 followup: ↓ 11 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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.
comment:12 Changed 7 years ago by
 Cc Bouillaguet added
 Milestone changed from sage5.7 to sage5.8
 Priority changed from minor to major
I just ran into this issue
comment:13 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:14 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:15 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:16 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:17 Changed 5 years ago by
In SageMath 6.7.beta1:
sage: R.<x> = QQ[] sage: L.<b> = NumberField(x^21/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 nonmonic or nonintegral 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 5 years ago by
 Dependencies set to #18740
comment:19 Changed 5 years ago by
 Branch set to u/pbruin/252number_fields
 Commit set to 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 nonintegral and/or nonmonic polynomials are supported.
comment:20 Changed 5 years ago by
 Commit changed from 8d0e9cc46a967d0aa2c020365732fbaab84b996f to 78408430db0bd43a0cd1e886c0d6b42184bd6dd6
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
7840843  Trac 252: allow nonmonic and nonintegral polynomials in number fields

comment:21 Changed 5 years ago by
comment:22 Changed 5 years ago by
 Commit changed from 78408430db0bd43a0cd1e886c0d6b42184bd6dd6 to fce3c709dbeb1b7073b432527fe31a53eb7b8124
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
fce3c70  Trac 252: allow nonmonic and nonintegral polynomials in number fields

comment:23 Changed 5 years ago by
 Description modified (diff)
 Status changed from new to needs_review
comment:24 Changed 5 years ago by
 Commit changed from fce3c709dbeb1b7073b432527fe31a53eb7b8124 to 75756863cfd4ded5796d83696cf13f5ebb1670d2
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
566770a  Merge branch 'u/pbruin/18739pari_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/18739pari_rnf_conversion' into ticket/18740relative_number_fields

c661096  Trac 18740: reduce overhead for relative number field elements

7575686  Trac 252: allow nonmonic and nonintegral polynomials in number fields

comment:25 Changed 5 years ago by
 Commit changed from 75756863cfd4ded5796d83696cf13f5ebb1670d2 to b8fdeda84073d4c72e042cd64e68678e099d292e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
b8fdeda  Trac 252: allow nonmonic and nonintegral polynomials in number fields

comment:26 Changed 5 years ago by
comment:27 Changed 5 years ago by
 Commit changed from b8fdeda84073d4c72e042cd64e68678e099d292e to d1227146064d0e4ebcaf313f6eeec5c70713dde3
Branch pushed to git repo; I updated commit sha1. New commits:
d122714  Merge branch 'develop' into ticket/252number_fields

comment:28 Changed 5 years ago by
 Status changed from needs_review to 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 5 years ago by
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 5 years ago by
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 5 years ago by
 Commit changed from d1227146064d0e4ebcaf313f6eeec5c70713dde3 to 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 5 years ago by
 Status changed from needs_work to needs_review
comment:33 followup: ↓ 36 Changed 5 years ago by
 Status changed from needs_review to 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 5 years ago by
 Commit changed from fd2743f092ecbffd79f49dc6cd18552631c407db to d4660f119eb45da3d9520b5f3b598ca5a6753906
Branch pushed to git repo; I updated commit sha1. New commits:
d4660f1  Trac 252: additional examples

comment:35 Changed 5 years ago by
 Commit changed from d4660f119eb45da3d9520b5f3b598ca5a6753906 to 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 5 years ago by
 Status changed from needs_work to needs_review
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).
comment:37 Changed 5 years ago by
 Reviewers set to Kartik Venkatram
 Status changed from needs_review to positive_review
Perfect.
comment:38 Changed 5 years ago by
 Branch changed from u/pbruin/252number_fields to 8b86c525a43dcfbab01224e3416722a1b29a9880
 Resolution set to fixed
 Status changed from positive_review to closed
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.)