Opened 12 years ago

Closed 12 years ago

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

Reported by: Owned by: cremona was major sage-4.0.2 number theory number field height 4.0.2.alpha0 John Cremona Francis Clarke, Nick Alexander

### 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.

applies to 3.4.2

### Changed 12 years ago by cremona

Apply after previous patch

### comment:1 Changed 12 years ago by fwclarke

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 ﬁ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.

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: ↓ 3 ↓ 4 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: ↓ 5 Changed 12 years ago by fwclarke

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: ↓ 6 Changed 12 years ago by fwclarke

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

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

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.