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:  sage4.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: 
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 64bit testing.
Attachments (4)
Change History (13)
Changed 12 years ago by
comment:1 Changed 12 years ago by
Four Comments
 I had a doctest failure (after applying both patches to 3.4.2 on OS X 10.5.7).
File "/Users/mafwc/sage3.4.2/devel/sagecremona/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.
 Your test in
local_height_arch
for whether embeddings are real can easily fail:sage: K.<a> = NumberField(x^4+3*x^217) 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.33954243808e16, 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 ﬁeld into C
(the ﬁrst r1
components are real, the next r2
have positive imaginary part)."
But this approach wouldn't allow the precision to be varied.
 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.

denominator_ideal
andnumerator_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.
comment:2 followups: ↓ 3 ↓ 4 Changed 12 years ago by
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 foolproof 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 nonreal 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 (nr)/2 where n is the degree and r the number of real embeddings).
Does that sould workable?
comment:3 in reply to: ↑ 2 ; followup: ↓ 5 Changed 12 years ago by
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 basisdependent.
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 nonzero 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 ; followup: ↓ 6 Changed 12 years ago by
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 foolproof 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 nonreal 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 (nr)/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^217) 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
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 basisdependent. 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 nonzero check) you doK = 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
thedenominator
function returnstry: return self._denom_ideal except AttributeError: pass self._denom_ideal = (self + self.number_field().unit_ideal())**(1) return self._denom_idealThe case for using the ideal
denominator
andnumerator
functions is, I think, (i) the general preference for not implementing the same thing twice; (ii) the fact that the functions innumber_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
Replying to fwclarke:
Yes; no time to experiment more with this, but I note that
places
innumber_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^217) 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
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 sagent since as far as can see this function has not yet been used anywhere!
comment:8 Changed 12 years ago by
 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 32bit and 64bit machines.
comment:9 Changed 12 years ago by
 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
applies to 3.4.2