Change algorithm for K.uniformizer(P)

[jdemeyer]

As shown by #14476, it is annoying that the following depends on the hardware:

sage: K.<t> = NumberField(x^4 - x^3 - 3*x^2 - x + 1)
sage: [K.uniformizer(P) for P,e in factor(K.ideal(5))]

Moreover, the algorithm for K.uniformizer() seems inefficient: instead of calling idealappr(), we can simply use the second component of the pari_prime() structure. Experiments show that this yields equal results for 32-bit and 64-bit machines (but there is no guarantee).

Depends on #14476
Depends on #15124

Component: number fields

Author: Jeroen Demeyer

Reviewer: John Cremona

Merged: sage-5.13.beta0

Issue created by migration from https://trac.sagemath.org/ticket/15243

[jdemeyer]

Dependencies: #14476

[jdemeyer]

Attachment: 15243_uniformizer.patch.gz

[jdemeyer]

Author: Jeroen Demeyer

[JohnCremona]

comment:4

Could you explain the first two hunks of your patch?

[jdemeyer]

comment:5

The change to sage/libs/pari/decl.pxi is to remove a duplicate definition of stackdummy() (and is technically unrelated to this patch). The change to sage/libs/pari/gen.pyx is to use a version of idealappr() with an extra flag, see

gp> ?idealappr
idealappr(nf,x,{flag=0}): x being a fractional ideal, gives an element b such that v_p(b)=v_p(x) for all prime ideals p dividing x, and v_p(b)>=0 for all other p. If 
(optional) flag is non-null x must be a prime ideal factorization with possibly zero exponents.

[JohnCremona]

comment:6

Thanks. Patch looks good, testing now on 64-bit...32 will take longer....

[JohnCremona]

comment:7

..getting some 32-bit errors in number_field.py, full report when it finishes.

[JohnCremona]

comment:8

On 32-bit:

sage -t --long devel/sage/sage/rings/number_field/number_field.py  # 2 doctests failed
sage -t --long devel/sage/sage/schemes/elliptic_curves/ell_number_field.py  # 3 doctests failed
sage -t --long devel/sage/sage/rings/number_field/number_field_ideal.py  # 1 doctest failed
sage -t --long devel/sage/sage/rings/residue_field.pyx  # 1 doctest failed
sage -t --long devel/sage/sage/schemes/elliptic_curves/ell_local_data.py  # 1 doctest failed

I will give further details later but will not have access to the 32-bit machine again until the evening.

[jdemeyer]

comment:9

Strange, all tests pass for me on 32-bit. Are you sure you don't have any other patches applied (apart from #14476 and #15243)?

[JohnCremona]

comment:10

Replying to @jdemeyer:

Strange, all tests pass for me on 32-bit. Are you sure you don't have any other patches applied (apart from #14476 and #15243)?

I am pretty confident in that but will check. The machine is at home though, and I no longer have a 32-bit desktop in my office, so cannot do it before this evening.

It's certainly getting harder to test 32-bit builds these days!

[JohnCremona]

comment:11

To confirm: this was sage-5.12.beta4 and the only patches applied are

trac_14476_bugs_in_local_data.patch
trac_14476_trac_links.patch
15243_uniformizer.patch

Here are some details:

**********************************************************************
File "devel/sage/sage/rings/number_field/number_field.py", line 5205, in sage.rings.number_field.number_field.NumberField_generic.uniformizer
Failed example:
    K.ideal(pi).factor()
Expected:
    (Fractional ideal (2, a + 1))^-1 * (Fractional ideal (3, a + 1))
Got:
    (Fractional ideal (2, a + 1)) * (Fractional ideal (3, a + 1))
**********************************************************************

**********************************************************************
File "devel/sage/sage/schemes/elliptic_curves/ell_local_data.py", line 671, in sage.schemes.elliptic_curves.ell_local_data.EllipticCurveLocalData._tate
Failed example:
    E.conductor() # indirect doctest
Exception raised:
    Traceback (most recent call last):
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 479, in _run
        self.execute(example, compiled, test.globs)
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 838, in execute
        exec compiled in globs
      File "<doctest sage.schemes.elliptic_curves.ell_local_data.EllipticCurveLocalData._tate[11]>", line 1, in <module>
        E.conductor() # indirect doctest
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py", line 1321, in conductor
        for d in self.local_data()],\
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py", line 777, in local_data
        return [self._get_local_data(pr, proof) for pr in primes]
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_number_field.py", line 836, in _get_local_data
        self._local_data[P, proof, algorithm] = EllipticCurveLocalData(self, P, proof, algorithm)
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_local_data.py", line 270, in __init__
        self._Emin, ch, self._val_disc, self._fp, self._KS, self._cp, self._split = self._tate(proof)
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_local_data.py", line 1035, in _tate
        pi_neg = K.uniformizer(P, 'negative')
      File "/home/john/sage-5.12.beta4/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.py", line 5249, in uniformizer
        return ~self(nf.idealappr(F, 1))
      File "gen.pyx", line 10605, in sage.libs.pari.gen._pari_trap (sage/libs/pari/gen.c:56583)
    PariError:  (5)
**********************************************************************

and similar.

[jdemeyer]

comment:12

I don't know what to say, it works for me...

Just to be sure, can you remove all patches, re-download and apply them and do ./sage -b and test again?

[JohnCremona]

comment:13

Replying to @jdemeyer:

I don't know what to say, it works for me...

Just to be sure, can you remove all patches, re-download and apply them and do ./sage -b and test again?

OK, I did that. What happens is that the third patch, the one on this ticket, fails to apply properly (which I had not noticed before). I get sage/libs/pari/gen.pyx.rej:

--- gen.pyx
+++ gen.pyx
@@ -7012,7 +7012,7 @@
     def idealappr(self, x, long flag=0):
         t0GEN(x)
         pari_catch_sig_on()
-        return self.new_gen(idealappr(self.g, t0))
+        return self.new_gen(idealappr0(self.g, t0, flag))
 
     def idealcoprime(self, x, y):

-- could this be because I am using 5.12.beta4 and not beta5 or later? I am now in a position to build a newer version on this 32-bit machine if needed.

[jdemeyer]

comment:14

Replying to @JohnCremona:

could this be because I am using 5.12.beta4 and not beta5 or later?

Yes, indeed. Or just apply #15124.

[jdemeyer]

Changed dependencies from #14476 to #14476, #15124

[JohnCremona]

Reviewer: John Cremona

[JohnCremona]

comment:16

With the extra dependency satisfied all is well, and all tests pass on a 32-bit machine too. Positive review!

[jdemeyer]

Merged: sage-5.13.beta0