Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#11891 closed enhancement (fixed)

NumberField(...).pari_polynomial() should return an integral polynomial

Reported by: jdemeyer Owned by: davidloeffler
Priority: major Milestone: sage-4.8
Component: number fields Keywords:
Cc: cremona Merged in: sage-4.8.alpha0
Authors: Jeroen Demeyer Reviewers: Luis Felipe Tabera Alonso
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

Mostly, PARI only works with number fields defined by monic integral polynomials. A few functions (like factornf()) also work for non-monic polynomials. In these cases, PARI always requires the polynomial to have integer coefficients. So, PARI prefers 2*x^2 - 1 over x^2 - 1/2 for defining a number field. The NumberField method pari_polynomial should reflect this.

This change allows one to define number field towers with non-integral polynomials. Example from vanilla sage-4.7.1:

sage: k.<a, c> = NumberField([x^2 + 1/3, x^2 + 1/4])
---------------------------------------------------------------------------
PariError                                 Traceback (most recent call last)

/home/jdemeyer/<ipython console> in <module>()

/usr/local/src/sage-4.7.1/local/lib/python2.6/site-packages/sage/rings/number_field/number_field.pyc in NumberField(polynomial, name, check, names, cache, embedding, latex_name, assume_disc_small, maximize_at_primes)
    435
    436     if isinstance(polynomial, (list, tuple)):
--> 437         return NumberFieldTower(polynomial, name, embeddings=embedding)
    438
    439     name = sage.structure.parent_gens.normalize_names(1, name)

/usr/local/src/sage-4.7.1/local/lib/python2.6/site-packages/sage/rings/number_field/number_field.pyc in NumberFieldTower(v, names, check, embeddings)
    622     #    return z
    623     #else:
--> 624     return w.extension(f, name, check=check, embedding=embeddings[0])
    625
    626

/usr/local/src/sage-4.7.1/local/lib/python2.6/site-packages/sage/rings/number_field/number_field.pyc in extension(self, poly, name, names, check, embedding)
   3570             raise TypeError, "the variable name must be specified."
   3571         from sage.rings.number_field.number_field_rel import NumberField_relative
-> 3572         return NumberField_relative(self, poly, str(name), check=check, embedding=embedding)
   3573
   3574     def factor(self, n):

/usr/local/src/sage-4.7.1/local/lib/python2.6/site-packages/sage/rings/number_field/number_field_rel.pyc in __init__(self, base, polynomial, name, latex_name, names, check, embedding)
    293
    294         if check:
--> 295             if not self.pari_relative_polynomial().polisirreducible():
    296                 # this is *much* faster than
    297                 # polynomial.is_irreducible() at some point in the

/usr/local/src/sage-4.7.1/local/lib/python2.6/site-packages/sage/libs/pari/gen.so in sage.libs.pari.gen._pari_trap (sage/libs/pari/gen.c:47834)()

PariError: inconsistent data (12)

With the patch, this works.

This patch also fixes

sage: K.<I> = NumberField(x^2+1)
sage: K.pari_polynomial('I')
0

by raising PariError instead.

By chance, it also fixes _division_field() for elliptic curves which now always returns an absolute field.

Attachments (1)

11891.patch (21.9 KB) - added by jdemeyer 8 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 8 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Description modified (diff)

comment:2 Changed 8 years ago by jdemeyer

  • Description modified (diff)
  • Milestone changed from sage-4.7.2 to sage-4.7.3
  • Status changed from new to needs_review

comment:3 follow-up: Changed 8 years ago by was

The code looks good, and passes tests, and it means we can at least compute discriminants.

The first and second things I try still don't work though, and I'm curious what you think about this:

sage: k.<a, c> = NumberField([x^2 + 1/3, x^2 + 1/4])
sage: k
Number Field in a with defining polynomial x^2 + 1/3 over its base field
sage: a+c
  ***   Warning: non-monic polynomial. Result of the form [nf,c].
ERROR: An unexpected error occurred while tokenizing input
... 
BOOM!
sage: k.relative_discriminant()
  ***   Warning: non-monic polynomial. Result of the form [nf,c].
BOOM!

Side Remarks: 1. I've always intended to just rewrite number fields to completely use

sage.schemes.elliptic_curves.heegner.make_monic

behind the scenes, and do *everything* that involves PARI in all cases using a monic integral polynomial, and only convert to the user's representation for input and output. I wish I had done that when I was first writing number fields.

  1. This is disturbing:
    sage: K.<I> = NumberField(x^2+1)
    sage: K.pari_polynomial()
    x^2 + 1
    sage: K.pari_polynomial('I')
    0
    

I would rather get an error message in the latter case. What do you think? If you agree, could you open a ticket?

Anyway, I'll wait for your comments...

comment:4 in reply to: ↑ 3 Changed 8 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Replying to was:

The code looks good, and passes tests, and it means we can at least compute discriminants.

The first and second things I try still don't work though, and I'm curious what you think about this:

sage: k.<a, c> = NumberField([x^2 + 1/3, x^2 + 1/4])
sage: k
Number Field in a with defining polynomial x^2 + 1/3 over its base field
sage: a+c
  ***   Warning: non-monic polynomial. Result of the form [nf,c].
ERROR: An unexpected error occurred while tokenizing input
... 
BOOM!
sage: k.relative_discriminant()
  ***   Warning: non-monic polynomial. Result of the form [nf,c].
BOOM!

Side Remarks: 1. I've always intended to just rewrite number fields to completely use

sage.schemes.elliptic_curves.heegner.make_monic

behind the scenes, and do *everything* that involves PARI in all cases using a monic integral polynomial, and only convert to the user's representation for input and output. I wish I had done that when I was first writing number fields.

I never intended this ticket to completely fix non-integral/non-monic number fields. I can have a look at the error messages above and try to fix them, but I also do not want to put too much effort. The main motivation for this ticket was to support #11890, for which it seems to work.

  1. This is disturbing:
    sage: K.<I> = NumberField(x^2+1)
    sage: K.pari_polynomial()
    x^2 + 1
    sage: K.pari_polynomial('I')
    0
    

I would rather get an error message in the latter case.

Okay, that should be fixable (currently, we simply substitute instead of creating a polynomial with a given variable).

comment:5 Changed 8 years ago by jdemeyer

This seems to cause a doctest failure in elliptic curves. Given the severity of the failure, it is surprising that there is only one failure:

sage -t -long "devel/sage/sage/schemes/elliptic_curves/gal_reps.py"
**********************************************************************
File "/usr/local/src/sage-4.7.2.alpha2/devel/sage/sage/schemes/elliptic_curves/gal_reps.py", line 257:
    sage: L = _division_field(E,5); L   # long time (4s on sage.math, 2011)
Expected:
    Number Field in a with defining polynomial Y^2 + Y - 7544/9663480699587560272216796875*b^18 - 922862/10473721227685546875*b^12 - 2459197/170278453125*b^6 - 859421/1661 over its base field
Got:
    Number Field in b with defining polynomial x^48 + 24*x^47 - 2634*x^46 - 64906*x^45 + 2726775*x^44 + 70841232*x^43 + 224413842693*x^42 + 4701700599732*x^41 - 3592508072137596/5*x^40 - 15012293781179144*x^39 + 968283011174870355*x^38 + 20267256109653557724*x^37 + 12067484020318191883430*x^36 + 1074616923704149785005406/5*x^35 - 36733858365780941833244052*x^34 - 645743028366047451133249842*x^33 + 220969510763490262549458235143/5*x^32 + 3821508904338000023273602548048/5*x^31 - 116959091827892505647463476639056/5*x^30 - 410999736248972608356551138775366*x^29 - 14893829970063945547808915701339152/5*x^28 - 65364599206437988881942239704947194/5*x^27 + 67673426654602996794997806980859832818/5*x^26 + 881882930983056033772717698410508954006/5*x^25 - 222881687343119655077359346112642829420824/25*x^24 - 2895120823335191010101881263518064564214338/25*x^23 + 45001727573606034388747893503112487075055856/25*x^22 + 123791333776720160716501836669886842723129232/5*x^21 + 33784656476525285313173627304265791556761499182/25*x^20 + 315309937263412002519549766396743184287341740362/25*x^19 - 29809326189907478934703273836943134749630766073937/25*x^18 - 277139669604549129326940625213109992460300794466472/25*x^17 + 48267417458901196371693187503590931071511693353624403/125*x^16 + 417747951937480880271176634423393038757023573062901214/125*x^15 + 2007263826796309855277267487981686566625095650300775449/125*x^14 + 6629329384200142639862088631838847849519261327732912678/125*x^13 - 7890086815228540044028318696011082482007739165946890467526/125*x^12 - 47407282438244289856698339380010252170030182743016263979758/125*x^11 + 3298070588288796211686670268348031992948626610010905491413867/125*x^10 + 16925026780847521477088033404397720576309067225732939278573654/125*x^9 - 12606276975554600131707859641843171596158942063398834295739121081/3125*x^8 - 52976903401697668325123474606327892765221094244312074003749191524/3125*x^7 - 1938266538684772533113390852600216820719603074035866039130578333001/3125*x^6 - 5627590284654484129751875434157935192705922694236805197727447225544/3125*x^5 + 285380988605606088041604497638523394233117370690633546039125252974974/625*x^4 + 2863126544037648956156470697472798773649141080128520101958284622979502/3125*x^3 - 292971118345690446877843351574720458113286307337430973163488739432371577/3125*x^2 - 294403610592013769220290971977947932182340270515731034223504446414069348/3125*x + 128890191901531504726282929609520479109501654595823184011440588325811602871/15625
**********************************************************************

Changed 8 years ago by jdemeyer

comment:6 Changed 8 years ago by jdemeyer

  • Cc cremona added
  • Description modified (diff)
  • Status changed from needs_work to needs_review

New patch, not yet fully tested.

comment:7 Changed 8 years ago by jdemeyer

With the new patch, all long tests in sage/rings and sage/schemes/elliptic_curves pass. Needs review.

comment:8 follow-up: Changed 8 years ago by lftabera

Looks ok to me.

fully tested in sage-4.7.1. The code and the tests seem fine. It does not allow to operate in towers of numberfields with nonintegral generators, but neither worked in previous Sage versions.

I have a question regarding pari_relative_polynomial in number_field_rel

The output of this method will be a monic polynomial. So we may have non-trivial denominators. Is this OK?

comment:9 in reply to: ↑ 8 ; follow-up: Changed 8 years ago by jdemeyer

Replying to lftabera:

The output of this method will be a monic polynomial. So we may have non-trivial denominators. Is this OK?

It's the only way. There is no meaningful definition of the "denominator" of a polynomial over a number field. So in order to get something canonical, let's take the monic polynomial.

comment:10 in reply to: ↑ 9 Changed 8 years ago by cremona

  • Reviewers set to Luis Felipe Tabera Alonso

Replying to jdemeyer:

Replying to lftabera:

The output of this method will be a monic polynomial. So we may have non-trivial denominators. Is this OK?

It's the only way. There is no meaningful definition of the "denominator" of a polynomial over a number field.

Pedantic point: you can define a denominator ideal sensibly (exercise), just as for number field elements. But that's not really relevant!

Any reason why Luis did not give a positive review? I have added his name to the Reviewers field

comment:11 Changed 8 years ago by lftabera

I have not finish yet...

comment:12 Changed 8 years ago by lftabera

  • Status changed from needs_review to positive_review

Now I am done, positive review.

comment:13 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.7.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:14 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:15 Changed 8 years ago by jdemeyer

  • Merged in changed from sage-4.7.3.alpha0 to sage-4.8.alpha0
  • Milestone set to sage-4.8
Note: See TracTickets for help on using tickets.