composite_fields does not play nice with QuadraticFields

[rlmill]

sage: K.<a> = QuadraticField(-5)
sage: L.<b> = QuadraticField(-47)
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]

CC: @ncalexan

Component: number fields

Author: Francis Clarke

Reviewer: John Cremona

Merged: sage-4.4.1.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/7643

[sagetrac-fwclarke]

Author: Francis Clarke

[sagetrac-fwclarke]

comment:1

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,

[sagetrac-fwclarke]

Attachment: trac_7643.patch.gz

based on 4.3.rc0

[JohnCremona]

comment:2

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.

[JohnCremona]

Reviewer: John Cremona

[sagetrac-fwclarke]

comment:3

Replying to @JohnCremona:

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.

[sagetrac-fwclarke]

replaces earlier patch, based on 4.3

[JohnCremona]

comment:4

Attachment: trac_7643_revised.patch.gz

Sorry to have given your more work to do ;)

I'll take a look!

[JohnCremona]

comment:5

Many apologies for having totally forgotten about this: you should have reminded me!

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.

[williamstein]

Merged: 4.4.1.alpha2

[sagetrac-mvngu]

Changed merged from 4.4.1.alpha2 to sage-4.4.1.alpha2