Add interface to PARI's rnfisnorm()

[craigcitro]

This patch adds support to solve norm equations via PARI.

Quick summary: given an element x of any number field (even QQ), x.is_norm(L) will return True if and only if x is a norm from L. It is also able to return an element of L whose norm is x.

The data used by PARI to compute whether or not an element is a norm can be computed once for each extension L/K. The function pari_rnfnorm_data computes exactly this, and hopefully in a later version its result can be passed to is_norm to avoid recomputing it each time in the case that K != QQ. If K is QQ, there is no need to save any such data -- the only data needed is that of K.pari_bnf(), which is used instead, and is already cached by K.

Dependencies: #10677

Apply:

1. attachment: trac_2329_rnfisnorm5.patch (positive_review)
2. attachment: 2329_reviewer.patch (positive_review)
3. attachment: 2329_selmer.patch (needs_review)

CC: @ncalexan @mstreng @jdemeyer

Component: number fields

Keywords: editor_craigcitro pari

Author: Craig Citro, Marco Streng, Francis Clarke, Jeroen Demeyer

Reviewer: Nick Alexander, David Loeffler, Jeroen Demeyer, David Kirkby

Merged: sage-4.7.alpha2

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

[craigcitro]

Attachment: trac-2329.patch.gz

[ncalexan]

comment:1

I have some questions.

There seems to be two things in this patch: changes to pari/gen, and access to stuff to do with norms. Is the latter independent of the former? I'd be a lot happier with the latter if that's true, because I'm not expert in the Pari interface.

Also, what relation does this have to "elements_of_norm"? There needs to be some unification, I think. Also, having is_norm() not always return a boolean is not good, IMO. I say is_norm -> Boolean and element_of_norm raises an exception if is_norm is not True.

I will gladly referee and have cc'ed myself.

[ncalexan]

comment:4

Craig, what's the status on this patch? I need it as we speak :) Are you interested in completing this or should I implement the changes I think are necessary and kick it back to you for refereeing?

[craigcitro]

comment:5

Nick, I'd be more than happy to have you finish this guy off. I think all the code is there, it just needs to be cleaned up and unified here and there. I just haven't had time to get back to it since you posted the referee report -- but if you want to clean this up, I'll review it for you lickety-split.

[craigcitro]

comment:6

Added a second patch that addresses all of the above issues.

[craigcitro]

comment:7

Attachment: trac-2329-pt2.patch.gz

[ncalexan]

comment:8

Attachment: 2329-ccitro-pari-indexing-fixes-1.patch.gz

The last patch separates out very useful fixes to the pari/gen.pyx that should be applied now.

The remainder of the functionality requires some more substantial changes and is a work in progress.

[craigcitro]

Changed keywords from none to editor_craigcitro

[sagetrac-mabshoff]

comment:10

This has been sitting around forever. Any movement here?

Cheers,

Michael

[mstreng]

comment:12

Same question as mabshoff 22 months ago...

[mstreng]

Author: Craig Citro, Marco Streng

[mstreng]

comment:13

As nobody replied here any more, I attacked the ticket myself by changing Craig's patch.

I've addressed Nick's concerns and replaced the documentation to reflect better what is in the Pari documentation (which weakens some claims considerably unfortunately).

x.is_norm() now decides whether an element x is a norm (proven output), while x.rnfisnorm() gives exactly the output that Pari's rnfisnorm would give.

The output of is_norm is True or False. With element=True, it also gives an element of norm x (or None if it doesn't exist). The function element_of_norm is removed, to avoid confusion with elements_of_norm.

[mstreng]

Reviewer: Nick Alexander

[mstreng]

Attachment: trac_2329_rnfisnorm.patch.gz

apply only this latest file

[jdemeyer]

comment:50

I have a new patch to change the Selmer group test, since the signs can change randomly. Needs review.

[kiwifb]

comment:52

Probably related, I got this on x86 with 4.7.alpha2

sage -t -long  -force_lib devel/sage-main/sage/rings/rational.pyx
**********************************************************************
File  
"/storage/strogdon/gentoo/usr/share/sage/devel/sage-main/sage/rings/rational.pyx",  
line 1222:
     sage: (1/5).is_norm(QuadraticField(5/4, 'a'), element=True)
Expected:
     (True, -1/5*a + 1/2)
Got:
     (True, 1/5*a - 1/2)

The log is from a friend of mine who has it as well on x86 but it doesn't show up on his amd64 hardware. I cannot test on amd64 or OSX at the present time.

[jdemeyer]

Work Issues: fix on 32-bit

[jdemeyer]

comment:53

Replying to @kiwifb:

Probably related, I got this on x86 with 4.7.alpha2

Good to know this. But keep in mind that sage-4.7.alpha2 has not been released (not even sage-4.7.alpha0). In the future it would be better to test released versions with patches applied instead of unreleased versions.

I will test this patch on a 32-bit system and see what needs to be fixed.

[jdemeyer]

Attachment: 2329_selmer.patch.gz

Additional patch

[jdemeyer]

Changed work issues from fix on 32-bit to none

[sagetrac-drkirkby]

comment:56

I can confirm that the doctest now passes on a 32-bit build of sage-4.7.alpha1 on OpenSolaris 06/2009 (Intel Xeon chip)

sage -t -long -force_lib "devel/sage/sage/rings/number_field/number_field.py"
	 [48.8 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 48.8 seconds

Prior to adding the 3 patches to sage-4.7.alpha1, I got.

File "/export/home/drkirkby/sage-4.7.alpha1/devel/sage-main/sage/rings/number_field/number_field.py", line 3035:
    sage: K.selmer_group([K.ideal(2, -a+1), K.ideal(3, a+1), K.ideal(a)], 3)
Expected:
    [2, a + 1, a]
Got:
    [2, a + 1, -a] 

I don't know enough about the maths to understand what the patch does, so whilst it appears to fix the problems I see in sage-4.7.alpha1, I don't feel I should give this a positive review - it needs a mathematician to check it too.

Dave

[sagetrac-drkirkby]

Changed reviewer from Nick Alexander, David Loeffler, Jeroen Demeyer to Nick Alexander, David Loeffler, Jeroen Demeyer, David Kirkby

[jdemeyer]

comment:57

David, could you please test both with and without -long.

[sagetrac-drkirkby]

comment:58

Replying to @jdemeyer:

David, could you please test both with and without -long.

With the patch applied, it is taking about 22 seconds without -long, and 46 seconds with -long.

If the patch is not applied, it fails with or without -long.

[loefflerd]

comment:59

it needs a mathematician to check it too.

Looks OK to me.

[jdemeyer]

Merged: sage-4.7.alpha2