polredabs

[AurelPage]

This is meant to be more of a discussion ticket, and then we can open other tickets for the various things that may need to be done.

I have added a knowl with the precise definition of polredabs: http://beta.lmfdb.org/knowledge/show/nf.polredabs, which will probably need improvement but at least contains the definition.

There are still two problems with polredabs:
1/ until I reported the problem to Karim Belabas, the pari function was actually not guaranteed to return a canonical polynomial: there were potentially several polynomials that it could return, even though it is very unlikely that it actually happened. The problem was that at the last step (cf knowl), the polynomials were ordered by absolute value of the coefficients with no tie-breaker.
2/ the T_2 quadratic form that appears in the specification of polredabs is usually not defined over Q (it is for totally real and CM fields, which are therefore immune to this problem). pari only computes an approximation of it, and does not compute the polredabs polynomial rigorously. It is conceivable, although very unlikely, that for some number field one polynomial has T_2 norm slightly larger (but undistinguishable at the precision pari uses) than the mathematical polredabs polynomial, but gets selected because of smaller discriminant or coefficients.

Therefore:
1/ We may have to run the new polredabs on the database of number fields to check that the polynomial is the correct one (most likely, no polynomial will have to be changed).
2/ It would probably be very painful to implement a rigorous version of polredabs. Do we want to insist on certifying that the polynomial provided is the one satisfying the mathematical definition? I have no idea how many fields could potentially lead to difficult cases. The main problem is: given two polynomials defining the same number field, to decide whether they have exactly the same T_2 norm (if the answer is NO it is easy to certify it by computing the norm with enough precision; the problem is when the answer is YES).

(should be tagged at least nf and dq)

[AndrewVSutherland]

So just to clarify, what is the current status of polredabs in the version of pari we are using (verison 2.9.1 included in SageMath 7.6)? Is it guaranteed to always return the same polynomial? Might the polynomial it returns change in the future (e.g. if the precision used by pari is increased or if the tie-breaker is changed).

[AurelPage]

Currently only the development version of pari has the fixed polredabs (the commit fixing polredabs is b5b1ad73e769c1180009cb2598). [For future reference/check if one does not have the list of commits: polredabs is fixed iff the file pari/src/basemath/base1.c contains the string myabscmpii]
It is not guaranteed to always return the same polynomial because of the precision issue, but in practice it will always return the same polynomial. If it returns two different polynomials, that would mean that
1/ there are vectors with T_2 norm extremely close to the minimum,
2/ there are two LLL-reduced bases for the ring of integers which, when the T_2 norm is approximated using these bases, some extra vectors are included in one case and not in the other, and
3/ there is an extra coincidence on the discriminant and the coefficients of the corresponding minimal polynomials.
The definition will not change (for instance the tie-breaker). It could happen that one polynomial changes if someone implements a rigorous algorithm and it turns out that one output was incorrect (very unlikely but we cannot rule it out).

[JohnCremona]

I think that the set of number fields in LMFDB would be a great set of test data for the newly improved polredabs function in pari, and would like to encourage pari developers to run the algorithm on all of them -- possibly with the help of someone who is also an LMFDB developer, taking advantage of their current participation at a pari/gp development workshop. If there was such a person!

[AurelPage]

I am not currently at the pari/gp workshop, I am at AGC^2T in Marseille ! But ok, I can do it :-) (or maybe you were thinking about Nicolas, who is at the pari/gp workshop?)

[JohnCremona]

I had forgotten that you were in Luminy not C-F. Either is good -- I have no idea at all how much work it would be though.

[jwj61]

It sounds like there is no big hurry. I can run the new version on the number field database if you like.

[AurelPage]

@jwj61 that would be nice! You would have to use the development version of pari/gp, but I am sure you are used to doing that.
I also want to think a little more about this approximation problem. If there is a simple solution that does not take a month to implement, I might give it a shot.

[jwj61]

I started and have found some differences, such as
old gp: x^4 - 386x^2 - 37249
new gp: x^4 + 386x^2 - 37249
Clearly the same T2 and poldisc, but a different choice being made to break the tie.

[JohnCremona]

That's an example of what we were afraid could happen given that the old version sorted by absolute values of coefficients without a tie-break. It's possible that for this case at least the switch from x to -x is an automorphism of the field which may mean that it is relatively harmless. For example anything like an elliptic curve with coefficients expressed on the old generator will still have all the same properties.

[AurelPage]

It cannot be an automorphism of the field since the minimal polynomial would be the same if it were. It is really a different primitive element of the same field, even up to automorphisms.

[JohnCremona]

@AurelPage Of course, sorry. I was wrongly seeing the change of sign of x^2 as indicating x -> -x. It's too hot!

[jwj61]

The script I wrote to find differences got part way through degree 18 when it got cut off. So far, there are over 29000 examples where the new polredabs is producing a different polynomial.

Is this all due to situations where the previous version was picking something without following some normalization, or were there some nomalizations in the choice before (inadequate as they were) which have been changed?

[AurelPage]

I noticed that the definition of polredabs did not define a single polynomial and reported it to Karim, who fixed the problem. The only difference is that in the old polredabs, the remaining polynomials in the last step were sorted by lexicographic order of the absolute value of the coefficients, without tie-breakers when the coefficients are the same up to sign. In all the examples that you see, the two polynomials should have the same T2 norm, same discriminant and same absolute value of the coefficients.

[JohnCremona]

I'm sure there is a lesson to be learned here, and one which some of us should have learned years ago. The Cremona labels for curves in an isogeny class (over Q) start with 1 for the "optimal" curve and then there is a deterministic way to order them from there, based on ordering isogenies of prime degree by degree and then by something else. For degree 2 isogenies this "something else" was to sort the x-coordinates of the 2-torsion point generating the kernel (when there was more than one). Except that I sorted by absolute value of the x-coordinate for several years, until I noticed. There's a prize for working out when I noticed... You can see why I had a sense of deja vu this morning!

[jwj61]

Is there a chance polredabs can be tweaked to be more consistent with the previous version? I realize the answer is probably no, but I thought it would be worth checking.

When I start switching polynomials, doing all of the cross-references inside the number field database is not so bad, and I know the implications to the Artin representation database (which will be sticky to change), but presumably there are changes in several other places. In particular, if ideals have labels based on the integral basis in the number field database, those may need recomputation as well. Also, I suppose defining polynomials for other things (like base fields for elliptic curves over number fields) may need some adjustment.

[JohnCremona]

It is crucial that we fix these for good before people start using the new labelling system for ideals.
I think I am a world expert on the perils of changing labels on things. Right now ecnf's over totally real fields borrow the labels from their hmfs, and we will want to relabel all of those. Luckily for me though, we don't need polredabs to get the canonical polynomial for quadratic fields!

[AurelPage]

@jwj61 No, I am pretty sure this is the best we can do. The old choice depends on the specific pari implementation of the algorithm that enumerates short vectors, and possibly on the sort algorithm of pari (for instance whether it is stable or not). The previous choice among the polynomials that were equal up to coefficient signs was essentially random, but in a consistent way.
I do not think we will have to change any ideal labels since we are only using the new labeling scheme for quadratic fields so far.

[pascalmolin]

Well, there should really be a discussion with Karim. He is not really happy with the new sorting (with + taking precedence over -) and maybe the large number of changes was unexpected so that other orders could actually be considered, and details of the implementation really settled if needed. If things can be improved for the LMFDB, this is really the time to do it (if I understand correctly Karim somehow considers that polredabs exists only for the lmfdb). Pascal 2017-06-21 21:26 GMT+02:00 AurelPage <notifications@github.com>:

…

@jwj61 <https://github.com/jwj61> No, I am pretty sure this is the best we can do. The old choice depends on the specific pari implementation of the algorithm that enumerates short vectors, and possibly on the sort algorithm of pari (for instance whether it is stable or not). The previous choice among the polynomials that were equal up to coefficient signs was essentially random, but in a consistent way. I do not think we will have to change any ideal labels since we are only using the new labeling scheme for quadratic fields so far. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2135 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ADL0jZNZqos-g6_aqAccEOaGqYd5vWWyks5sGW50gaJpZM4N_iWb> .

[jwj61]

OK, I will do more prep work, but will hold off on doing substitutions for now.

[AurelPage]

(if I understand correctly Karim somehow considers that polredabs exists only for the lmfdb).

Well, in almost every use case of polredabs (= every time you don't need a canonical polynomial, which is essentially always), polredbest is better and much faster...

[pascalmolin]

Notice: Karim and Aurel have agreed on a complete definition + documentation of polredabs (with stronger mathematical meaningfullness). It is now commited in pari master. Launching a new labelling process is now necessary, but this should be the final one and other blocks can safely build on it. Pascal 2017-06-21 23:21 GMT+02:00 John Jones <notifications@github.com>:

…

OK, I will do more prep work, but will hold off on doing substitutions for now. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2135 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ADL0jaTayEyD8mTEP_9dzpu9NpMLm6Waks5sGYlHgaJpZM4N_iWb> .

[jwj61]

Quick update. I have a version of the number field database where defining polynomials and subfields are updated. I am still applying polredabs to resolvents (which can be of moderately high degree, which take longer).

Some of the Artin representations need to be redone. I ran into a bug in magma while trying to do that, so it is on hold for the moment. If we bring the new number field database on line, it would not cause serious issues with the Artin representations. It would break the cross-links between the two areas.

Also, we have a feature in the number field database where one can enter a polynomial and it will search for it by applying polredabs. If someone gives a polynomial where the field is isomorphic to one of the 30,000 fields which changed polynomials, it won't find it (until the new polredabs makes it into the gp used by sage). Odds of this happening to someone is low.

It looks to me like there may be changes needed in Hilbert modular forms and elliptic curves over number fields.

[JohnCremona]

I presume that for any number field where the polynomial will change, we will keep the old polynomial? That might be helpful in a change-over period since we could search for a polynomial using either the old or the new versions.

Over quadratic fields there will be no changes since the standard polynomial will not change (if I am wrong in that please tell me!). For HMFs there is a plan to do a large-scale relabelling of primes and levels using the new standard, but we can just wait and do that after these polynomials have settled down.
I don't know when this new pari version will get into Sage. Not for version 8.0 which will be released quite soon. We could build Sage with a new pari version but I would like to avoid if at all possible requiring LMFDB developers having to do some customization like that.

[jwj61]

I was not planning on keeping the old polynomials. Its a possibility, but that would involve changes to the code and data instead of just data. Admittedly, it would not be a very big change. On the other hand, it only helps with cross-linking and searching. Do people think it is worth making the code change?

I have seen no changes to fields of degree < 4. My guess is that most involve fields which contain $\sqrt{-1}$, the polynomial has all even powers, and the alternate comes from $x\mapsto i x$.

Once we make the change, would could wait and see if anyone notices the gp-version in Sage problem. I doubt people use the search by polynomial feature much, and if they do, odds are strongly in favor of them missing the changed fields.

[jwj61]

If people want to look at changes to other areas, I would have python output to a file all polynomials you use to define fields (including if you don't store the polynomial but store a number field label), load them into the new gp (available on atkin/lehner at ~jj/data/bin/ngp), and filter to see which ones have pol != polredabs(pol). Unless you have polynomials of degree > 15, it should be a quick check.

[jwj61]

The pari manual has a different description of how polredabs will pick the final polynomial when compared with the knowl Aurel wrote (referenced above). @AurelPage which is right?

[AurelPage]

This is what @pascalmolin was refering to: after further discussion with Karim Belabas, we adopted a different definition of polredabs from the one I wrote in the knowl (mathematically more meaningful). The correct one is the one from the pari documentation, and I will fix the knowl.

[jwj61]

I see. I thought I had things ready to go when I noticed a problem yesterday. I reported it, and it has been fixed in pari. This means the current number field database needs to be redone again. So far I have checked quadratic fields and 912,352 will change their defining polynomials (e.g.,
x^2 - x + 55
to
x^2 + x + 55

[jwj61]

@pascalmolin @JohnCremona

In a previous comment, @pascalmolin said that Karim was not happy with + taking precedence over -, but that is what is in the current version. This is what changes the defining polynomials for all quadratic fields Q(sqrt(d)) with d\equiv 1 (mod 4). Should we be seeking another change?

[JohnCremona]

I would not have strong feelings about x^2-x+n versus x^2+x+n in the abstract but if the former choice involves changing all quadratic fields with odd discriminant then that seems to me to be a good case for keeping the original -- even if that means changing the definition of polredabs.

Also, as far as I can tell this change would mean that for all these quadratic fields, the ordering of all split primes would change. In turn, that means that the ordering of elliptic curves (isogeny classes of given conductor) and modular forms (of given level) would change since these are sorted by lex. ordering of the a_P with the P in sequence. That would mean relabelling all Bianchi modular forms and elliptic curves over imaginary quadratic fields, which would have been fairly painless a couple of months ago but very painful now!

Can someone confirm my claim about the sorting of primes in a quadratic field (of odd discriminant)?

[jwj61]

If we want to propose a normalization which keeps more of the polynomials the same (including all of the quadratic ones), two relatively simple choices are:

(1) favor negative coefficients over positive ones
(2) mimic the ordering used to break ties for Conway polynomials (preferred sign alternates with + for x^n, - for x^{n-1}, etc.

Either way, this is for the final breaking of ties. Thoughts?

[AndrewVSutherland]

@JohnCremona I agree with you: the defining polynomials x^2-x+n and x^2+x+n lead to different labels for split primes (the ordering will be reversed). This will also impact the labels of non-prime ideals (e.g. that might show up as conductors).

[JohnCremona]

@jwj61 I prefer (1) to (2) as being simpler but am open to persuasion.

[jwj61]

I just e-mailed Karim asking for (1). It has the advantage that he would have to change only a few characters in the code, and a few in the manual.

[AurelPage]

I think Karim is on holidays for a week. (1) sounds like a good solution. I agree that changing the quadratic polynomials is not nice; I had not realised this when we discussed the new definition of polredabs.

[jwj61]

Karim did implement (1), so quadratic fields will remain unchanged. Work starting now on patching higher degree fields.

[jwj61]

This is finally complete.