Implement Hilbert symbols over number fields

[adeines]

PARI has Hilbert symbols for number fields. Hilbert symbols can be implemented by wrapping PARI's function nfhilbert.

Apply attachment: trac_9334_nfhilbert.patch and attachment: 9334_review_jdemeyer.patch.

Depends on #11304
Depends on #11540
Depends on #11130

Upstream: Fixed upstream, in a later stable release.

CC: @mstreng @jdemeyer

Component: number fields

Keywords: hilbert symbol

Author: Aly Deines, Marco Streng, Jeroen Demeyer

Reviewer: David Loeffler, John Cremona, Marco Streng, Jeroen Demeyer

Merged: sage-4.8.alpha1

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

[adeines]

comment:1

Here all the functions are better placed. I still need to fix the code so that generalized_hilbert_symbol(a,b,P) doesn't assume a.valuation(P) and b.valuation(P) are 0 or 1.

[adeines]

comment:2

I changed the code as Tim (correctly) suggested so as it doesn't assume reduced input.

[adeines]

comment:3

This has better uniformizer code.

[loefflerd]

comment:4

This doesn't seem to apply to 4.4.4. Does it require some other patch as a prerequisite? Also, the docstrings don't seem to be correctly ReST formatted (you should always run sage -docbuild reference html and check that there are no warnings before submitting a patch).

[loefflerd]

Work Issues: patch does not apply

[loefflerd]

Changed work issues from patch does not apply to ReST formatting issues

[loefflerd]

comment:5

I see. So it's supposed to be applied on top of the patches at #9317. That's fine, but you should explain this in your trac upload messages. Don't repost random patches from other tickets on this ticket -- that's just unnecessary duplication, and it's confusing for the release maintainer when s/he has to merge stuff later.

Anyway: with the #9317 patches in place these four patches apply fine, and all doctests pass. But they're quite hard to review, since you seem to have added code in one place in the first patch and then removed it and added it again somewhere else in the second. Could I suggest that you use the Mercurial "qfold" command to combine the four patches into one single patch? That would make the reviewer's job vastly easier. And don't forget those docstring formatting problems; the two that stand out most at a quick glance are that the LaTeX formulae should be in backticks not dollar signs (`x^2 + 2` etc), and the LaTeX fraction command is \frac not \frak.

[adeines]

comment:6

Here is one single patch. It does not depend on ticket #9317. This should have all the documentation fixed. Thank you for your patience, I've learned a lot about Mercurial and ReST formatting recently.

I also applied this on a clean clone of 4.4.2 to check that it would build, all the doctest pass, and the -docbuild looks correct.

[loefflerd]

comment:7

Most of this looks fine, and the docstring formatting is much better; but there are some technical issues.

• The code in solver_mod_p is obviously wrong for n > 1: it calculates the inverse modulo Pⁿ but then takes the square root of this modulo P. You need some kind of Hensel lifting or suchlike to get an answer that's right modulo Pⁿ.

• The code in uniformizer is a mess (e.g. it trivially fails for any non-principal ideal in a number field of degree > 2, because you've assumed self.integral_basis() has length 2). But there's already a method sage.rings.number_field.number_field.NumberField_generic.uniformizer (taking a prime as an argument). I agree that it is worth having uniformizers accessible via a method of ideals as well, but it should just be a thin wrapper around the existing code.

[JohnCremona]

Reviewer: David Loeffler, John Cremona

[JohnCremona]

Changed work issues from ReST formatting issues to ReST formatting issues, and more

[JohnCremona]

comment:8

I generally agree with David's points. This code will be very useful for a topic begin done at SD23 (solving conics over various fields) so I am keen to get this in (suitably modified).

In generalized_legendre_symbol: (1) test P for primality first, before trying to construct its residue field. (2) instead of K(2).valuation(P) just test that n is odd. (3) don't raise run-time errors, make them ValueErrors?. (4) make the return types consistent: you return either +1 in k or -1 as a python int. I would return a Sage integer in either case. (5) you do not test if P divides self. If so, return 0 (as a Sage integer)>

Why are generalized_hilbert_symbol and _legendre_symbol in sage/rings/arith.py? I would put them both in number_fields -- where you put the even one in fact.

In generalized_even_hilbert_symbol you define but do not use iprime, so delete it. And do the simple calculation to get the coefficients of jprime**2 so you don't need to construct the quaternion algebra. (You can leave in a comment about that).

_voight_alg_6_2 has some ^ symbols which should be **. Check for others.

Do what David said about uniformizer -- just call the existing function.

Sort out the solve function.

[mstreng]

comment:9

Great, I could use this.

While you are still at it, I have a small wish list as well. Could you

• Let the generalized even Hilbert symbol accept fractions (as the odd one and the QQ one do)?

  sage: hilbert_symbol(1/3, 1, 2)
  1
  sage: K.<i> = QuadraticField(-1)
  sage: O = K.maximal_order()
  sage: generalized_hilbert_symbol(K(1/2), K(1), 3*O)
  1
  sage: generalized_hilbert_symbol(K(1/3), K(1), (1+i)*O)
  NotImplementedError: inverse_mod is not implemented for non-integral elements
  

• Also add the Hilbert symbol for infinite places? See e.g.

  sage: hilbert_symbol(-1, -1, -1)
  -1
  

  This is almost trivial compared to what you've already done. I have code, contact me if you have questions.

• Correct the doc text. The doc of generalized_even_hilbert_symbol should say that P must divide 2, while generalized_hilbert_symbol should not say that P must be odd

[mstreng]

comment:10

In addition to the first part of my precious comment: generalized_even_hilbert_symbol should accept a and b to both be divisible by p.

sage: hilbert_symbol(2,2,2)
1
sage: K.<i>=QuadraticField(-1)
sage: O=K.maximal_order()
sage: generalized_hilbert_symbol(3,3,3*O)
1
sage: generalized_hilbert_symbol(2,2,2*O)
ValueError: P must be a prime

[mstreng]

comment:11

Oops, the last two lines of my previous comment should of course read

sage: p = 1+i
sage: generalized_hilbert_symbol(p,p,p*O)
RuntimeError: ord_P(a) or ord_P(b) must be zero

[jdemeyer]

comment:52

Replying to @mstreng:

There is still a duplicate example, and a lot of examples that return 1 now that they are corrected. I think we should remove some of these, and add some -1's such as the ones in my comment 2 days ago.

Please do it!

Also, what is the output type now? In my patch, I converted it to Integer. Jeroen removed that conversion, but what does cdef long give us?

It will be Python int. I see no reason to return a Sage Integer.

Finally, in my patch, I had self(a), but Jeroen turned this into a. How carefully does Pari check whether stuff is in the right field?

I only moved a = self(a) up in the code.

[JohnCremona]

comment:53

Replying to @mstreng:

----------------------------------------------------------------------
| Sage Version 4.7.1, Release Date: 2011-08-11                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: K.<a> = NumberField(x^3+x+1)
sage: L.<b> = NumberField(x^3+2*x+2)
sage: K(b)
a

I think this is a horrible bug. There is no embedding from L to K! A very generic __call__ method is used, and is definitely not doing the right thing here.

[loefflerd]

comment:54

Replying to @JohnCremona:

Replying to @mstreng:

----------------------------------------------------------------------
| Sage Version 4.7.1, Release Date: 2011-08-11                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: K.<a> = NumberField(x^3+x+1)
sage: L.<b> = NumberField(x^3+2*x+2)
sage: K(b)
a

I think this is a horrible bug. There is no embedding from L to K! A very generic __call__ method is used, and is definitely not doing the right thing here.

I agree -- that's horrible! It's not so generic actually: the offending code is the method NumberField_absolute._coerce_from_other_number_field which just converts to a polynomial and back:

f = self.polynomial_ring()(x.polynomial())
return self._element_class(self, f)

This is mathematically meaningless unless either the other field is isomorphic to self, or x is actually in Q. I suggest we raise this on sage-nt, and maybe open a ticket to fix it ASAP.

[mstreng]

comment:55

Replying to @jdemeyer:

It will be Python int. I see no reason to return a Sage Integer.

Python ints are fine with me, I was afraid it would be a pari object. I would have liked some uniformity, but that's missing already.

sage: type(legendre_symbol(3,5))
<type 'int'>
sage: type(hilbert_symbol(3,5,7))
<type 'sage.rings.integer.Integer'>
sage: type(jacobi_symbol(3,5))
<type 'sage.rings.integer.Integer'>

I want all symbols to behave nicely with division by Sage integers, but that's fine with int

sage: int(1)/ZZ(2)
1/2

[mstreng]

comment:56

Replying to @JohnCremona:

I think this is a horrible bug. There is no embedding from L to K! A very generic __call__ method is used, and is definitely not doing the right thing here.

Is there a ticket for this yet?

[loefflerd]

comment:57

Sage-nt thread here: http://groups.google.com/group/sage-nt/browse_thread/thread/9108218411e7f0a6

[jdemeyer]

comment:58

Replying to @mstreng:

Replying to @JohnCremona:

I think this is a horrible bug. There is no embedding from L to K! A very generic __call__ method is used, and is definitely not doing the right thing here.

Is there a ticket for this yet?

Just made one: #11869.

[mstreng]

comment:59

Replying to @jdemeyer:

Replying to @mstreng:

There is still a duplicate example, and a lot of examples that return 1 now that they are corrected. I think we should remove some of these, and add some -1's such as the ones in my comment 2 days ago.

Please do it!

I could, but I wouldn't be able to test it, and it may need to be rebased afterwards: I failed to install #11130.

[mstreng]

comment:60

Positive review for the reviewer patch. I noticed that it included extra -1 examples and removed the duplicate example, and I did not find removing examples worth the trouble.

I also managed to build #11130 and found that all tests pass. I'm assuming Jeroen gives a positive review to what he didn't change, and that his reviewer patch was ready for review, so I'm setting the whole ticket to positive review.

[jdemeyer]

Changed work issues from add/remove some doctests to none

[jdemeyer]

Milestone sage-4.7.3 deleted

[jdemeyer]

Merged: sage-4.8.alpha1