Opened 12 years ago

Closed 12 years ago

#6046 closed enhancement (fixed)

[with new patch, positive review] Implement local and global heights for number field elements

Reported by: cremona Owned by: was
Priority: major Milestone: sage-4.0.2
Component: number theory Keywords: number field height
Cc: Merged in: 4.0.2.alpha0
Authors: John Cremona Reviewers: Francis Clarke, Nick Alexander
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

This patch implements local (archimedean non) and global heights for elements of number fields, and also rationals.

This will be used in an eventual implementation of #360 (which must be one of the oldest outstanding tickets, mea culpa).

It's all in rings/rational.pyx and rings/number_field/number_field_element.pyx and no other files should be affected.

The second patch was added after 64-bit testing.

Attachments (4)

heights.patch (23.5 KB) - added by cremona 12 years ago.
applies to 3.4.2
heights2.patch (1.4 KB) - added by cremona 12 years ago.
Apply after previous patch
heights3.patch (5.8 KB) - added by fwclarke 12 years ago.
Apply after the other two
trac_6046.patch (30.2 KB) - added by cremona 12 years ago.
Replaces all earlier patches; based on 4.0.alpha0

Download all attachments as: .zip

Change History (13)

Changed 12 years ago by cremona

applies to 3.4.2

Changed 12 years ago by cremona

Apply after previous patch

comment:1 Changed 12 years ago by fwclarke

Four Comments

  1. I had a doctest failure (after applying both patches to 3.4.2 on OS X 10.5.7).
    File "/Users/mafwc/sage-3.4.2/devel/sage-cremona/sage/rings/number_field/number_field_element.pyx", line 2138:
        sage: [a.local_height_arch(i, weighted=True) for i in range(4)]
    Expected:
        [0.530192454572, 1.77282843491, 1.77282843491, 1.06038490914]
    Got:
        [1.06038490914, 1.77282843491, 1.77282843491, 0.530192454572]
    

But I get the "right" answer when doing the same interactively. No doubt this is down to pari's unpredictability.

  1. Your test in local_height_arch for whether embeddings are real can easily fail:
    sage: K.<a> = NumberField(x^4+3*x^2-17)
    sage: [f(a).imag().is_zero() for f in K.complex_embeddings()]
    [False, False, False, True]
    

would be telling us that there are 3 complex embeddings and 1 real one! In fact

sage: K.signature()
(2, 1)

It's a rounding problem, of course,

sage: [f(a).imag() for f in K.complex_embeddings()]
[4.33954243808e-16, 2.42641344245, -2.42641344245, 0.0]

It would be possible to use something corresponding to Mathematica's Chop, but this would have to be done carefully.

On the other hand the following from the pari manual entry for nfint could be helpful:

"nf [6] is the vector containing the r1 + r2 roots (nf .roots) of nf [1] corresponding to the r1 + r2 embeddings of the number field into C (the first r1 components are real, the next r2 have positive imaginary part)."

But this approach wouldn't allow the precision to be varied.

  1. Trying your new functions on elements in relative number fields has exposed

a problem with x.valuation() when x is such an element. It's easily solved by a change to is_prime for relative ideals. I've attached a new patch which makes this change, as well as a few tweaks, and some doctests, so that all your functions (with the exception of local_height_arch and those that depend on it) work in the relative case.

  1. denominator_ideal and numerator_ideal are surely better defined using

the denominator and numerator of the ideal generated by the element, as already defined in number_field_ideal.py. I've incorporated the changes in the patch.

Changed 12 years ago by fwclarke

Apply after the other two

comment:2 follow-ups: Changed 12 years ago by cremona

Thanks for your comments, Francis, and for fixing this up to work with relative extensions.

Your comments and fixes for numerator/denominator ideals are *wrong*! number field elements have numerators and denominators which are dependent on the basis used to represent them, and are not what I meant or need -- as I thought my doctest made clear!

We must sort out this mess with the embeddings. Your first doctest failure (with different behaviour in different runs) must mean that the ordering of the embeddings is not deterministic. That must be fixed, say by ordering the roots when the embeddings are found. Secondly we must have a fool-proof way of determining which embeddings are real when you do K.complex_embeddings(). What I would prefer is to have a function called (perhaps) K.archimedean_completions() which returns a list of r+s embeddings, the first r into a RealField? and the last s into a ComplexField? (or even a list of two lists of embeddings, of lengths r and s respectively). That way the codomain of a real embedding would be a RealField? which could easily be tested for. While we are at it the complex list would only contain one of each pair.

So, how to implement this? Not problem with the list of real embeddings, though they should be sorted by the natural real ordering on the image og K.gen(); for the non-real ones we could first find all embeddings into CC, then sort them by their imaginary parts and then take the last s of these (where s could be defined to be (n-r)/2 where n is the degree and r the number of real embeddings).

Does that sould workable?

comment:3 in reply to: ↑ 2 ; follow-up: Changed 12 years ago by fwclarke

Replying to cremona:

Your comments and fixes for numerator/denominator ideals are *wrong*! number field elements have numerators and denominators which are dependent on the basis used to represent them, and are not what I meant or need -- as I thought my doctest made clear!

I don't see how this can be. The functions I'm calling are not basis-dependent. They are essentially the same as yours, but for ideals rather than elements, and the code is nearly identical. E.g., for denominator_ideal(self) (leaving aside the non-zero check) you do

        K = self.number_field() 
        one = K.ideal(1) 
        return one / (one + K.ideal(self)) 

while I've suggested

        return self.number_field().ideal(self).denominator() 

and for a fractional ideal self the denominator function returns

        try:
            return self._denom_ideal
        except AttributeError:
            pass
        self._denom_ideal = (self + self.number_field().unit_ideal())**(-1)
        return self._denom_ideal

The case for using the ideal denominator and numerator functions is, I think, (i) the general preference for not implementing the same thing twice; (ii) the fact that the functions in number_field_ideal.py cache their output.

comment:4 in reply to: ↑ 2 ; follow-up: Changed 12 years ago by fwclarke

Replying to cremona:

We must sort out this mess with the embeddings. Your first doctest failure (with different behaviour in different runs) must mean that the ordering of the embeddings is not deterministic. That must be fixed, say by ordering the roots when the embeddings are found. Secondly we must have a fool-proof way of determining which embeddings are real when you do K.complex_embeddings(). What I would prefer is to have a function called (perhaps) K.archimedean_completions() which returns a list of r+s embeddings, the first r into a RealField? and the last s into a ComplexField? (or even a list of two lists of embeddings, of lengths r and s respectively). That way the codomain of a real embedding would be a RealField? which could easily be tested for. While we are at it the complex list would only contain one of each pair.

So, how to implement this? Not problem with the list of real embeddings, though they should be sorted by the natural real ordering on the image og K.gen(); for the non-real ones we could first find all embeddings into CC, then sort them by their imaginary parts and then take the last s of these (where s could be defined to be (n-r)/2 where n is the degree and r the number of real embeddings).

Does that sound workable?

Yes; no time to experiment more with this, but I note that places in number_field.py seems to do what's needed:

    def places(self, all_complex=False, prec=None):
        """
        Return the collection of all places of self. By default, this
        returns the set of real places as homomorphisms into RIF first,
        followed by a choice of one of each pair of complex conjugate
        homomorphisms into CIF.
        
        On the other hand, if prec is not None, we simply return places
        into RealField(prec) and ComplexField(prec) (or RDF, CDF if
        prec=53).
       
        ...

so that

sage: K.<a> = NumberField(x^4+3*x^2-17)
sage: K.places()

[Ring morphism:
  From: Number Field in a with defining polynomial x^4 + 3*x^2 - 17
  To:   Real Field with 106 bits of precision
  Defn: a |--> -1.699259307373674805202512065354,
 Ring morphism:
  From: Number Field in a with defining polynomial x^4 + 3*x^2 - 17
  To:   Real Field with 106 bits of precision
  Defn: a |--> 1.699259307373674805202512065354,
 Ring morphism:
  From: Number Field in a with defining polynomial x^4 + 3*x^2 - 17
  To:   Complex Field with 53 bits of precision
  Defn: a |--> 2.42641344244876*I]

Not defined (yet!) for relative number fields.

comment:5 in reply to: ↑ 3 Changed 12 years ago by cremona

Replying to fwclarke:

Replying to cremona:

Your comments and fixes for numerator/denominator ideals are *wrong*! number field elements have numerators and denominators which are dependent on the basis used to represent them, and are not what I meant or need -- as I thought my doctest made clear!

I don't see how this can be. The functions I'm calling are not basis-dependent. They are essentially the same as yours, but for ideals rather than elements, and the code is nearly identical. E.g., for denominator_ideal(self) (leaving aside the non-zero check) you do

        K = self.number_field() 
        one = K.ideal(1) 
        return one / (one + K.ideal(self)) 

while I've suggested

        return self.number_field().ideal(self).denominator() 

and for a fractional ideal self the denominator function returns

        try:
            return self._denom_ideal
        except AttributeError:
            pass
        self._denom_ideal = (self + self.number_field().unit_ideal())**(-1)
        return self._denom_ideal

The case for using the ideal denominator and numerator functions is, I think, (i) the general preference for not implementing the same thing twice; (ii) the fact that the functions in number_field_ideal.py cache their output.

My mistake, apologies. I misread your patch and thought that you called denominator() before ideal(), while you did te opposite, which I do not argue with.

Now I am wondering how I did not notice that the functions existed already! It is almost not worth implementing the denominator_ideal() function, but as it is now there I guess we can keep it.

comment:6 in reply to: ↑ 4 Changed 12 years ago by cremona

Replying to fwclarke:

Yes; no time to experiment more with this, but I note that places in number_field.py seems to do what's needed:

    def places(self, all_complex=False, prec=None):
        """
        Return the collection of all places of self. By default, this
        returns the set of real places as homomorphisms into RIF first,
        followed by a choice of one of each pair of complex conjugate
        homomorphisms into CIF.
        
        On the other hand, if prec is not None, we simply return places
        into RealField(prec) and ComplexField(prec) (or RDF, CDF if
        prec=53).
       
        ...

so that

sage: K.<a> = NumberField(x^4+3*x^2-17)
sage: K.places()

[Ring morphism:
  From: Number Field in a with defining polynomial x^4 + 3*x^2 - 17
  To:   Real Field with 106 bits of precision
  Defn: a |--> -1.699259307373674805202512065354,
 Ring morphism:
  From: Number Field in a with defining polynomial x^4 + 3*x^2 - 17
  To:   Real Field with 106 bits of precision
  Defn: a |--> 1.699259307373674805202512065354,
 Ring morphism:
  From: Number Field in a with defining polynomial x^4 + 3*x^2 - 17
  To:   Complex Field with 53 bits of precision
  Defn: a |--> 2.42641344244876*I]

Not defined (yet!) for relative number fields.

This does exactly what I was suggesting. So I will amend my heights code to use places instead of embeddings. I note that places() does not work for QQ though, and that will have to change!

comment:7 Changed 12 years ago by cremona

Comment about places: If you look carefully at the docstring quoted above, you find the following inconsistency: with "prec=None" it says that the codomains are RIF or CIF. But in fact in this case they are not, they are plain Real/ComplexFields?. In the code, while CIF and RIF are used to compute the roots, when the hom's are defined the center() is taken of each root so they are not longer intervals.

I'll ask on sage-nt since as far as can see this function has not yet been used anywhere!

Changed 12 years ago by cremona

Replaces all earlier patches; based on 4.0.alpha0

comment:8 Changed 12 years ago by cremona

  • Summary changed from [with patch, needs review] Implement local and global heights for number field elements to [with new patch, needs review] Implement local and global heights for number field elements

The new patch trac_6046.patch replaces all earlier ones. I have taken Francis's advice and now use the places() function (notwithstanding the issue raised above). This meant implementing places() for relative extensions, which I did. I also made a slight refinement to K.primes_above() which used to sort on degree but now also sort on norm (thus avoiding one possible source of doctest failures due to randomness). It may well be that whoever wrote this only ever intended it to be used with prime arguments! Note however that where there are two primes in the list with the same degree and norm, the order is not necessarily canonical.

I have tested this on both 32-bit and 64-bit machines.

comment:9 Changed 12 years ago by ncalexan

  • Authors set to John Cremona
  • Merged in set to 4.0.2.alpha0
  • Resolution set to fixed
  • Reviewers set to Francis Clarke, Nick Alexander
  • Status changed from new to closed
  • Summary changed from [with new patch, needs review] Implement local and global heights for number field elements to [with new patch, positive review] Implement local and global heights for number field elements
Note: See TracTickets for help on using tickets.