Opened 13 years ago

Closed 13 years ago

composite_fields does not play nice with QuadraticFields

Reported by: Owned by: Robert Miller David Loeffler major sage-4.4.1 number fields ncalexan sage-4.4.1.alpha2 Francis Clarke John Cremona N/A

Description

```sage: K.<a> = QuadraticField(-5)
sage: K.composite_fields(L, names='c')
[]
sage: K.<a> = NumberField(x^2 + 5)
sage: L.<b> = NumberField(x^2 + 47)
sage: K.composite_fields(L, names='c')
[Number Field in c0 with defining polynomial x^4 + 104*x^2 + 1764]
```

comment:1 Changed 13 years ago by Francis Clarke

Authors: → Francis Clarke ncalexan added new → needs_review

When fields are constructed using `QuadraticField` they come with a specified real or complex embedding. Then the problem is caused by the following lines of `number_field.py` (which are only encountered when the fields are both equipped with an embedding):

```                if r(embedding) > 1e-30: # XXX how to do this more generally?
continue
```

In the case of the two quadratic fields, `r` is the polynomial `x^4 + 104*x^2 + 1764`, `embedding` is the element `4.619586622901255?*I` of `Complex Lazy Field`, and `r(embedding)` is `0.?e-11`. Since this is bigger than `1e-30`, the only compositum given by pari's `polcompositum` is skipped and an empty list returned.

Worse still is the following example:

```sage: C1.<a> = NumberField(x^3 - 2, embedding = CC(2^(1/3)))
sage: C2.<b> = NumberField(x^3 - 2, embedding = CC(2^(1/3)*exp(2*pi*I/3)))
sage: C1.composite_fields(C2)
[Number Field in ab0 with defining polynomial x^3 + 2]
```

Here `polcompositum` (which is independent of the embeddings) returns

```[x^3 + 2, x^6 + 40*x^3 + 1372]
```

In the first case (which ought to be rejected since it is incompatible with the given embeddings), `r(embedding)` is `-18.0000000000000? + 31.1769145362398?*I` and `r(embedding) > 1e-30` is `False` (sic!), so this field passes the test. In the second case (which should be accepted), `r(embedding)` is `0.?e-11 + 0.?e-11*I` and `r(embedding) > 1e-30` is `True`, so this field fails the test.

Clearly this test is not up to the job.

There is a simple way to rewrite the code, because when embeddings of both fields are specified there is always only one compositum. Thus we can simply pick the field for which `r(embedding)`takes a minimum value.

The patch implements this idea.

Another change is to only compute the maps into the composite when they are required. In additiion various checks have been omitted, since pari should have already done the necessary work.

I have also allowed the fields into which the two fields are embedded to be different as long as they have a common ambient field, so that, for example, the following now works:

```sage: C1.<a> = NumberField(x^3 - 2, embedding = RR(2^(1/3)))
sage: C2.<b> = NumberField(x^3 - 2, embedding = CC(2^(1/3)*exp(2*pi*I/3)))
sage: C1.composite_fields(C2)
[Number Field in ab with defining polynomial x^6 + 40*x^3 + 1372]
```

Another problem with the present code is that when no embeddings are specified it yields, in general, too many fields (because there are duplicates). The following fields provide a good example: at present

```sage: Q1.<a> = NumberField(x^4 + 10*x^2 + 1)
sage: Q2.<b> = NumberField(x^4 + 16*x^2 + 4)
sage: Q1.composite_fields(Q2)
[Number Field in ab0 with defining polynomial x^8 + 64*x^6 + 904*x^4 + 3840*x^2 + 3600,
Number Field in ab1 with defining polynomial x^8 + 160*x^6 + 6472*x^4 + 74880*x^2 + 1296]
```

`Q1` is the field `QQ(sqrt(-2), sqrt(-3))` and `Q2` is `QQ(sqrt(-3), sqrt(-5))`. So there is only one compositum, i.e., `QQ(sqrt(-2), sqrt(-3), sqrt(-5))`. The fields generated by the two degree 8 polynomials provided by `polcompositum` are isomorphic, and without specifying the embeddings there is no way of distinguishing them. `Q1.composite_fields(Q2, both_maps=True)` will choose embeddings of `Q1` and `Q2` in the compositum, but there are four choices for each, none of which is preferred.

The patch includes code which removes duplicates.

As a result of these changes, many changes have had to be made to the doctests, which contained some misleading examples.

Also in the patch is code to deal with relative number fields, and, in the case where a single field is returned, a minor change to the way that its variable name is generated,

based on 4.3.rc0

comment:2 follow-up:  3 Changed 13 years ago by John Cremona

Reviewers: → John Cremona needs_review → needs_info

Review: The code looks excellent. It deals with the problem originally given and does a lot more besides, is well-written and very well documented. Applied fine to 4.3 and all tests pass (in the two files changed and also in totallyreal_rel.py where the function is used).

Quick question: in cases where we compute K.composite_fields(L) where there is an embedding of K into L or K into K, would it not be nice to return L (resp K) rather than some new field? Surely that would not be expensive to test for. For example:

```sage: K.<a> = QuadraticField(-3)
sage: L.<z> = CyclotomicField(21)
sage: K.composite_fields(L)
[Number Field in az with defining polynomial x^12 - x^11 + 21*x^10 - 20*x^9 + 188*x^8 - 168*x^7 + 925*x^6 - 756*x^5 + 2645*x^4 - 1952*x^3 + 4725*x^2 - 2458*x + 2269]
```

while we could have used one of these:

```sage: K.embeddings(L)
[
Ring morphism:
From: Number Field in a with defining polynomial x^2 + 3
To:   Cyclotomic Field of order 21 and degree 12
Defn: a |--> 2*z^7 + 1,
Ring morphism:
From: Number Field in a with defining polynomial x^2 + 3
To:   Cyclotomic Field of order 21 and degree 12
Defn: a |--> -2*z^7 - 1
]
```

If this can be done easily then I would vote for it, otherwise I'll give this a positive review.

comment:3 in reply to:  2 Changed 13 years ago by Francis Clarke

Status: needs_info → needs_review

Quick question: in cases where we compute K.composite_fields(L) where there is an embedding of K into L or K into K, would it not be nice to return L (resp K) rather than some new field? Surely that would not be expensive to test for.

This is an excellent idea. In principle it's easy to implement, because we only have to see if the degrees are equal. In practice it all becomes quite complicated when embeddings, maps and relative fields are taken into account, and I fear the the code in the replacement patch which I attach is even more convoluted than before.

One of the complications was that I needed to obtain the inverse of an isomorphism between distinct fields. At present one can only take the inverse of an automorphism of a field. So the patch includes some minor tweaks to `rings/number_field/morphism.py`, `categories/map.pyx` and `modules/matrix_morphism.py` in order to do this neatly. In particular, after the patch one can raise a map to the power -1, when the inverse is defined.

Changed 13 years ago by Francis Clarke

replaces earlier patch, based on 4.3

comment:4 Changed 13 years ago by John Cremona

Sorry to have given your more work to do ;)

I'll take a look!

comment:5 Changed 13 years ago by John Cremona

Status: needs_review → positive_review

The good news is that the new patch (we only apply the second one) applies absolutely fine to 4.4.rc0, and all tests in sage/rings/number_field pass, and the example I gave above now works perfectly as requested!

Positive review for the second patch.

comment:6 Changed 13 years ago by William Stein

Merged in: → 4.4.1.alpha2 → fixed positive_review → closed

comment:7 Changed 13 years ago by Minh Van Nguyen

Merged in: 4.4.1.alpha2 → sage-4.4.1.alpha2
Note: See TracTickets for help on using tickets.