Sage: Ticket #6046: [with new patch, positive review] Implement local and global heights for number field elements
https://trac.sagemath.org/ticket/6046
<p>
This patch implements local (archimedean non) and global heights for elements of number fields, and also rationals.
</p>
<p>
This will be used in an eventual implementation of <a class="closed ticket" href="https://trac.sagemath.org/ticket/360" title="enhancement: Implementation of elliptic curve height bounds in Sage (closed: wontfix)">#360</a> (which must be one of the oldest outstanding tickets, mea culpa).
</p>
<p>
It's all in rings/rational.pyx and rings/number_field/number_field_element.pyx and no other files should be affected.
</p>
<p>
The second patch was added after 64-bit testing.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/6046
Trac 1.1.6cremonaFri, 15 May 2009 16:16:26 GMTattachment set
https://trac.sagemath.org/ticket/6046
https://trac.sagemath.org/ticket/6046
<ul>
<li><strong>attachment</strong>
set to <em>heights.patch</em>
</li>
</ul>
<p>
applies to 3.4.2
</p>
TicketcremonaFri, 15 May 2009 16:16:40 GMTattachment set
https://trac.sagemath.org/ticket/6046
https://trac.sagemath.org/ticket/6046
<ul>
<li><strong>attachment</strong>
set to <em>heights2.patch</em>
</li>
</ul>
<p>
Apply after previous patch
</p>
TicketfwclarkeSat, 16 May 2009 12:24:48 GMT
https://trac.sagemath.org/ticket/6046#comment:1
https://trac.sagemath.org/ticket/6046#comment:1
<h2 id="FourComments">Four Comments</h2>
<ol><li>I had a doctest failure (after applying both patches to 3.4.2 on OS X 10.5.7).
<pre class="wiki">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]
</pre></li></ol><p>
But I get the "right" answer when doing the same interactively. No doubt this is down
to pari's unpredictability.
</p>
<ol start="2"><li> Your test in <code>local_height_arch</code> for whether embeddings are real can easily fail:
<pre class="wiki">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]
</pre></li></ol><p>
would be telling us that there are 3 complex embeddings and 1 real one! In fact
</p>
<pre class="wiki">sage: K.signature()
(2, 1)
</pre><p>
It's a rounding problem, of course,
</p>
<pre class="wiki">sage: [f(a).imag() for f in K.complex_embeddings()]
[4.33954243808e-16, 2.42641344245, -2.42641344245, 0.0]
</pre><p>
It would be possible to use something corresponding to Mathematica's <code>Chop</code>,
but this would have to be done carefully.
</p>
<p>
On the other hand the following from the pari manual entry for <code>nfint</code> could
be helpful:
</p>
<p>
"<code>nf [6]</code> is the vector containing the <code>r1 + r2</code> roots (<code>nf .roots</code>) of <code>nf [1]</code>
corresponding to the <code>r1 + r2</code> embeddings of the number ﬁeld into <code>C</code>
(the ﬁrst <code>r1</code> components are real, the next <code>r2</code> have positive imaginary part)."
</p>
<p>
But this approach wouldn't allow the precision to be varied.
</p>
<ol start="3"><li>Trying your new functions on elements in relative number fields has exposed
</li></ol><p>
a problem with <code>x.valuation()</code> when <code>x</code> is such an element. It's easily solved by
a change to <code>is_prime</code> 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 <code>local_height_arch</code> and those that depend on it) work in
the relative case.
</p>
<ol start="4"><li> <code>denominator_ideal</code> and <code>numerator_ideal</code> are surely better defined using
</li></ol><p>
the <code>denominator</code> and <code>numerator</code> of the ideal generated by the element, as
already defined in <code>number_field_ideal.py</code>. I've incorporated the changes in the
patch.
</p>
TicketfwclarkeSat, 16 May 2009 12:25:31 GMTattachment set
https://trac.sagemath.org/ticket/6046
https://trac.sagemath.org/ticket/6046
<ul>
<li><strong>attachment</strong>
set to <em>heights3.patch</em>
</li>
</ul>
<p>
Apply after the other two
</p>
TicketcremonaSat, 16 May 2009 12:58:55 GMT
https://trac.sagemath.org/ticket/6046#comment:2
https://trac.sagemath.org/ticket/6046#comment:2
<p>
Thanks for your comments, Francis, and for fixing this up to work with relative extensions.
</p>
<p>
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!
</p>
<p>
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 <a class="missing wiki">RealField?</a> and the last s into a <a class="missing wiki">ComplexField?</a> (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 <a class="missing wiki">RealField?</a> which could easily be tested for. While we are at it the complex list would only contain one of each pair.
</p>
<p>
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).
</p>
<p>
Does that sould workable?
</p>
TicketfwclarkeSat, 16 May 2009 14:25:25 GMT
https://trac.sagemath.org/ticket/6046#comment:3
https://trac.sagemath.org/ticket/6046#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6046#comment:2" title="Comment 2">cremona</a>:
</p>
<blockquote class="citation">
<p>
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!
</p>
</blockquote>
<p>
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 <code>denominator_ideal(self)</code> (leaving aside the non-zero check) you do
</p>
<pre class="wiki"> K = self.number_field()
one = K.ideal(1)
return one / (one + K.ideal(self))
</pre><p>
while I've suggested
</p>
<pre class="wiki"> return self.number_field().ideal(self).denominator()
</pre><p>
and for a fractional ideal <code>self</code> the <code>denominator</code> function returns
</p>
<pre class="wiki"> try:
return self._denom_ideal
except AttributeError:
pass
self._denom_ideal = (self + self.number_field().unit_ideal())**(-1)
return self._denom_ideal
</pre><p>
The case for using the ideal <code>denominator</code> and <code>numerator</code> functions is, I think,
(i) the general preference for not implementing the same thing twice;
(ii) the fact that the functions in <code>number_field_ideal.py</code> cache their output.
</p>
TicketfwclarkeSat, 16 May 2009 14:35:43 GMT
https://trac.sagemath.org/ticket/6046#comment:4
https://trac.sagemath.org/ticket/6046#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6046#comment:2" title="Comment 2">cremona</a>:
</p>
<blockquote class="citation">
<p>
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 <a class="missing wiki">RealField?</a> and the last s into a <a class="missing wiki">ComplexField?</a> (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 <a class="missing wiki">RealField?</a> which could easily be tested for. While we are at it the complex list would only contain one of each pair.
</p>
<p>
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).
</p>
<p>
Does that sound workable?
</p>
</blockquote>
<p>
Yes; no time to experiment more with this, but I note that <code>places</code> in <code>number_field.py</code> seems to do what's needed:
</p>
<pre class="wiki"> 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).
...
</pre><p>
so that
</p>
<pre class="wiki">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]
</pre><p>
Not defined (yet!) for relative number fields.
</p>
TicketcremonaSat, 16 May 2009 14:56:40 GMT
https://trac.sagemath.org/ticket/6046#comment:5
https://trac.sagemath.org/ticket/6046#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6046#comment:3" title="Comment 3">fwclarke</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6046#comment:2" title="Comment 2">cremona</a>:
</p>
<blockquote class="citation">
<p>
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!
</p>
</blockquote>
<p>
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 <code>denominator_ideal(self)</code> (leaving aside the non-zero check) you do
</p>
<pre class="wiki"> K = self.number_field()
one = K.ideal(1)
return one / (one + K.ideal(self))
</pre><p>
while I've suggested
</p>
<pre class="wiki"> return self.number_field().ideal(self).denominator()
</pre><p>
and for a fractional ideal <code>self</code> the <code>denominator</code> function returns
</p>
<pre class="wiki"> try:
return self._denom_ideal
except AttributeError:
pass
self._denom_ideal = (self + self.number_field().unit_ideal())**(-1)
return self._denom_ideal
</pre><p>
The case for using the ideal <code>denominator</code> and <code>numerator</code> functions is, I think,
(i) the general preference for not implementing the same thing twice;
(ii) the fact that the functions in <code>number_field_ideal.py</code> cache their output.
</p>
</blockquote>
<p>
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.
</p>
<p>
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.
</p>
TicketcremonaSat, 16 May 2009 14:59:12 GMT
https://trac.sagemath.org/ticket/6046#comment:6
https://trac.sagemath.org/ticket/6046#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/6046#comment:4" title="Comment 4">fwclarke</a>:
</p>
<blockquote class="citation">
<p>
Yes; no time to experiment more with this, but I note that <code>places</code> in <code>number_field.py</code> seems to do what's needed:
</p>
<pre class="wiki"> 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).
...
</pre><p>
so that
</p>
<pre class="wiki">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]
</pre><p>
Not defined (yet!) for relative number fields.
</p>
</blockquote>
<p>
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!
</p>
TicketcremonaSun, 17 May 2009 11:17:18 GMT
https://trac.sagemath.org/ticket/6046#comment:7
https://trac.sagemath.org/ticket/6046#comment:7
<p>
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 <a class="missing wiki">Real/ComplexFields?</a>. 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.
</p>
<p>
I'll ask on sage-nt since as far as can see this function has not yet been used anywhere!
</p>
TicketcremonaSun, 17 May 2009 15:18:00 GMTattachment set
https://trac.sagemath.org/ticket/6046
https://trac.sagemath.org/ticket/6046
<ul>
<li><strong>attachment</strong>
set to <em>trac_6046.patch</em>
</li>
</ul>
<p>
Replaces all earlier patches; based on 4.0.alpha0
</p>
TicketcremonaSun, 17 May 2009 15:22:35 GMTsummary changed
https://trac.sagemath.org/ticket/6046#comment:8
https://trac.sagemath.org/ticket/6046#comment:8
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Implement local and global heights for number field elements</em> to <em>[with new patch, needs review] Implement local and global heights for number field elements</em>
</li>
</ul>
<p>
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.
</p>
<p>
I have tested this on both 32-bit and 64-bit machines.
</p>
TicketncalexanMon, 15 Jun 2009 06:30:52 GMTstatus, summary changed; author, reviewer, resolution, merged set
https://trac.sagemath.org/ticket/6046#comment:9
https://trac.sagemath.org/ticket/6046#comment:9
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>author</strong>
set to <em>John Cremona</em>
</li>
<li><strong>summary</strong>
changed from <em>[with new patch, needs review] Implement local and global heights for number field elements</em> to <em>[with new patch, positive review] Implement local and global heights for number field elements</em>
</li>
<li><strong>reviewer</strong>
set to <em>Francis Clarke, Nick Alexander</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>4.0.2.alpha0</em>
</li>
</ul>
Ticket