Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#7643 closed defect (fixed)

composite_fields does not play nice with QuadraticFields

Reported by: Robert Miller Owned by: David Loeffler
Priority: major Milestone: sage-4.4.1
Component: number fields Keywords:
Cc: ncalexan Merged in: sage-4.4.1.alpha2
Authors: Francis Clarke Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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]

Attachments (2)

trac_7643.patch (23.4 KB) - added by Francis Clarke 13 years ago.
based on 4.3.rc0
trac_7643_revised.patch (31.9 KB) - added by Francis Clarke 13 years ago.
replaces earlier patch, based on 4.3

Download all attachments as: .zip

Change History (9)

comment:1 Changed 13 years ago by Francis Clarke

Authors: Francis Clarke
Cc: ncalexan added
Status: newneeds_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,

Changed 13 years ago by Francis Clarke

Attachment: trac_7643.patch added

based on 4.3.rc0

comment:2 Changed 13 years ago by John Cremona

Reviewers: John Cremona
Status: needs_reviewneeds_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_infoneeds_review

Replying to cremona:

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

Attachment: trac_7643_revised.patch added

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_reviewpositive_review

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.

comment:6 Changed 13 years ago by William Stein

Merged in: 4.4.1.alpha2
Resolution: fixed
Status: positive_reviewclosed

comment:7 Changed 13 years ago by Minh Van Nguyen

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