[with patch, needs review] move number fields to new coercion, implement embeddings

I'll actually upload the patches when I'm on a stable enough connection to do so...

To help possible reviewers of what looks like very useful and good stuff, would it be possible to write a few words about what is going on here?

By the way, the second patch does not view properly whan I click on it. I don't know why.

Yes, I explained this to some people at Sage Days 10, but it certainly could use some explanation here.

These patches move coercion over to the new api, which is (hopefully) easier to understand and use as well as being faster. As part of this move, we also get the benefit of being able to specify embeddings at creation time, into RR or CC being the most common. (The embeddings into RR and CC are by default into "lazy" fields so the path can be followed to a field of any precision.) Cyclotomic fields and fields created with the "QuadraticField?" command come with their standard embeddings.

A field with an embedding can do arithmetic with its ambient field, and if two number fields have an embedding into a common field than elements can be moved from one to the other as well. Here is a brief example (though more can be found in the documentation):

sage: L.<a> = QuadraticField(-3)
sage: a + 1.5
1.50000000000000 + 1.73205080756888*I
sage: a + 1.50000000000000000000000000000000000000
1.50000000000000000000000000000000000000 + 1.73205080756887729352744634150587236694*I
sage: K.<zeta> = CyclotomicField(12)
sage: K(a)
2*zeta^7 + 1

sage: L.<b> = NumberField(x^5-x+1, embedding=-1.1)
sage: b in RR
True
sage: RR(b)
-1.16730397826142
sage: RealField(200)(b)
-1.1673039782614186842560458998548421807205603715254890391401
sage: RealField(200)(b^2-5)
-3.6374014223350653758204435726195439793325331732024834332371
sage: RealField(200)(b^5-b+1)
0.00000000000000000000000000000000000000000000000000000000000

This also paves the path for more sophisticated arithmetic, like automatic compositums.

I downloaded these patches not so much in order to review them but because I wanted to see if they would conflict with any changes I might make in order to fix #4193.

Anyway, they apply and build fine (eventually) under 3.1.4. Testing number_field/ passes except for a minor numerical noise issue:

**************************************************
File "/home/david/sage-current/tmp/number_field_morphisms.py", line 223:
    sage: closest_root(x^3-1, CDF.0)
Expected:
    -0.500000000000000 + 0.866025403784439*I
Got:
    -0.500000000000000 + 0.866025403784438*I
**********************************************************************

But I can't really do much to test the new functionality, since I'm not sure what it's supposed to do. You say above "here is a brief example (though more can be found in the documentation)" but I can't see any; all of the various number field constructors now accept an embedding parameter but there's no explanation or tests in the docstrings. Can we have a bit of demystification?

Thank you for taking a look at this. I really don't want these patches to bitrot. I will try to post another patch with more docstrings.

Essentially, the embedding is a specified coercion into another field (typically RR or CC, though embeddings to any other field can be specified). This should make what you're trying to do at #4193 trivial (or at least very easy). The embedding parameter specifies where the generator of the number field should land (the closest root being taken if the root is not exact). So by doing

sage: L.<b> = NumberField(x^5-x+1, embedding=-1.1)

I am saying I want the number filed defined by x^5-x+1 *with* the embedding into RR defined by sending the generator to the root (closest to) -1.1. You can test this by calling RR(b) or RR(some other element of K) and doing stuff like b+1.5 whose result should be about 0.4. Given two number fields K and L with embedding into (say) CC, one now gets for free morphisms between (subsets of) K and L.

OK, I've attached some more documentation on embeddings. Also, since this is a coercion ticket, one of the main points of testing it is to make sure things still work like they used to.

Thanks for clarifying things there. Your new docstrings assert that cyclotomic fields all have their usual embeddings so coercion between them should work, but I'm slightly concerned by the following non-associativity of addition:

sage: K5.<zeta5> = CyclotomicField(5)
sage: K7.<zeta7> = CyclotomicField(7)
sage: K35.<zeta35> = CyclotomicField(35)
sage: (-zeta35 + zeta7) + (zeta5 + zeta35)
zeta35^7 + zeta35^5
sage: -zeta35 + (zeta7 + zeta5) + zeta35
TypeError: unsupported operand parent(s) for '+': 'Cyclotomic Field of order 5 and degree 4' and 'Cyclotomic Field of order 7 and degree 6'

This problem is not in any way new, and existed before your patches; but shouldn't your patches fix it?

No, my patch does not automatically compute compositums, just coercions one direction or the other. This should be done, is on my (long) todo list, and of course is especially easy for cyclotomic fields, but this ticket is big enough already...

Note that Sage does not guarantee associativity of addition. Consider

sage: ZZ['t,x'].0 + ZZ['x'].0 + ZZ['t'].0
2*t + x
sage: ZZ['t,x'].0 + (ZZ['x'].0 + ZZ['t'].0)
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '+': 'Univariate Polynomial Ring in x over Integer Ring' and 'Univariate Polynomial Ring in t over Integer Ring'

This is because there is an ambiguous ordering of the variables if the rightmost addition is performed first. What should be true, however, is if both operations succeed then they should give equal answers.

I am trying to referee this, but it's going to take some time. I'm going to put it into my tree and try to move some of my code that does this by hand to the embedding architecture. Email me in a month.

I have some questions and problems:

I really need to be able to specify embeddings after creation, because *tons* of functions create number fields (composite_fields, for example, or subfields) and I really don't want to specify all possible embeddings of the results...

First, why squarefree_part bounded? This could be a separate patch.

Second, I can specify non-embeddings that seem to be ignored:

sage: K.<a> = NumberField(x^3+2, embedding=CC(-10).nth_root(3))
sage: K.coerce_embedding()

Generic morphism:
  From: Number Field in a with defining polynomial x^3 + 2
  To:   Complex Lazy Field
  Defn: a -> 0.6299605249474365? + 1.091123635971722?*I
sage: K.gen_embedding()^3
-2.00000000000000? + 0.?e-14*I

Finally, I am having lots of trouble creating non-default embeddings:

sage: K2.<a> = NumberField(x^2 + 2, 'a', embedding=RR(-sqrt(2)))
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)

/Users/ncalexan/.sage/temp/mero.local/25160/_Users_ncalexan__sage_init_sage_0.py in <module>()
----> 1 
      2 
      3 
      4 
      5 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.pyc in NumberField(polynomial, name, check, names, cache, embedding)
    369 
    370     if polynomial.degree() == 2:
--> 371         K = NumberField_quadratic(polynomial, name, check, embedding)
    372     else:
    373         K = NumberField_absolute(polynomial, name, None, check, embedding)

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.pyc in __init__(self, polynomial, name, check, embedding)
   6470             Number Field in a with defining polynomial x^2 - 4
   6471         """
-> 6472         NumberField_absolute.__init__(self, polynomial, name=name, check=check, embedding=embedding)
   6473         self._element_class = number_field_element_quadratic.NumberFieldElement_quadratic
   6474         c, b, a = [rational.Rational(t) for t in self.defining_polynomial().list()]

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.pyc in __init__(self, polynomial, name, latex_name, check, embedding)
   3649         NumberField_generic.__init__(self, polynomial, name, latex_name, check, embedding)
   3650         self._element_class = number_field_element.NumberFieldElement_absolute
-> 3651         self._zero_element = self(0)
   3652         self._one_element =  self(1)
   3653 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:3665)()
    277 
    278 
--> 279 
    280 
    281 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.convert_map_from (sage/structure/parent.c:8640)()
   1000 
   1001 
-> 1002 
   1003 
   1004 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.discover_convert_map_from (sage/structure/parent.c:8771)()
   1007 
   1008 
-> 1009 
   1010 
   1011 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.coerce_map_from (sage/structure/parent.c:7653)()
    876 
    877 
--> 878 
    879 
    880 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.discover_coerce_map_from (sage/structure/parent.c:7956)()
    921 
    922 
--> 923 
    924 
    925 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent_old.so in sage.structure.parent_old.Parent._coerce_map_from_ (sage/structure/parent_old.c:6291)()
    576 
    577 
--> 578 
    579 
    580 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.pyc in _coerce_map_from_(self, K)
   6497             return number_field_element_quadratic.Q_to_quadratic_field_element(self)
   6498         else:
-> 6499             return NumberField_absolute._coerce_map_from_(self, K)
   6500 
   6501 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.pyc in _coerce_map_from_(self, R)
   1525         """
   1526         if R in [int, long, ZZ, QQ, self.base()]:
-> 1527             return self._generic_convert_map(R)
   1528         from sage.rings.number_field.order import is_NumberFieldOrder
   1529         if is_NumberFieldOrder(R) and R.number_field().has_coerce_map_from(self):

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent_old.so in sage.structure.parent_old.Parent._generic_convert_map (sage/structure/parent_old.c:6841)()
    594 
    595 
--> 596 
    597 
    598 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent_old.so in sage.structure.parent_old.Parent._generic_convert_map (sage/structure/parent_old.c:6806)()
    602 
    603 
--> 604 
    605 
    606 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/parent.so in sage.structure.parent.Parent._generic_convert_map (sage/structure/parent.c:6875)()
    747 
    748 
--> 749 
    750 
    751 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.DefaultConvertMap.__init__ (sage/structure/coerce_maps.c:1931)()
     22 
     23 
---> 24 
     25 
     26 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/categories/map.so in sage.categories.map.Map.__init__ (sage/categories/map.c:1768)()
     39 
     40 
---> 41 
     42 
     43 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/categories/homset.pyc in Hom(X, Y, cat)
    151             
    152     ##_cache[key] = weakref.ref(H)
--> 153     _cache[(X, Y, cat)] = weakref.ref(H)
    154     
    155     return H

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.pyc in __cmp__(self, other)
   1639         else:
   1640             return cmp(self.coerce_embedding()(self.gen()),
-> 1641                        other.coerce_embedding()(other.gen()))
   1642 
   1643     def _ideal_class_(self):

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyBinop.__richcmp__ (sage/rings/real_lazy.c:7858)()
    868 
    869 
--> 870 
    871 
    872 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/element.so in sage.structure.element.Element._richcmp (sage/structure/element.c:5169)()
    530 
    531 
--> 532 
    533 
    534 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/element.so in sage.structure.element.Element._richcmp_c_impl (sage/structure/element.c:5400)()
    577 
    578 
--> 579 
    580 
    581 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyFieldElement._cmp_c_impl (sage/rings/real_lazy.c:5445)()
    508 
    509 
--> 510 
    511 
    512 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyFieldElement.approx (sage/rings/real_lazy.c:5880)()
    567 
    568 
--> 569 
    570 
    571 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyBinop.eval (sage/rings/real_lazy.c:7427)()
    825 
    826 
--> 827 
    828 
    829 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyBinop.eval (sage/rings/real_lazy.c:7439)()
    826 
    827 
--> 828 
    829 
    830 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyAlgebraic.eval (sage/rings/real_lazy.c:10310)()
   1278 
   1279 
-> 1280 
   1281 
   1282 

IndexError: list index out of range
sage:

And even worse, non-embeddings. check the sign of sqrt(2) below)

sage: K1.<a> = NumberField(x^2 + 2, 'a', embedding=RR(sqrt(2)))
sage: K1.gen_embedding()
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)

/Users/ncalexan/.sage/temp/mero.local/25160/_Users_ncalexan__sage_init_sage_0.py in <module>()
----> 1 
      2 
      3 
      4 
      5 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/IPython/Prompts.pyc in __call__(self, arg)
    549 
    550             # and now call a possibly user-defined print mechanism
--> 551             manipulated_val = self.display(arg)
    552             
    553             # user display hooks can change the variable to be stored in

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/IPython/Prompts.pyc in _display(self, arg)
    575             return IPython.generics.result_display(arg)
    576         except TryNext:            
--> 577             return self.shell.hooks.result_display(arg)
    578 
    579     # Assign the default display method:

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/IPython/hooks.pyc in __call__(self, *args, **kw)
    133             #print "prio",prio,"cmd",cmd #dbg
    134             try:
--> 135                 ret = cmd(*args, **kw)
    136                 return ret
    137             except ipapi.TryNext, exc:

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/IPython/hooks.pyc in result_display(self, arg)
    163     
    164     if self.rc.pprint:
--> 165         out = pformat(arg)
    166         if '\n' in out:
    167             # So that multi-line strings line up with the left column of

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python/pprint.pyc in pformat(self, object)
    109     def pformat(self, object):
    110         sio = _StringIO()
--> 111         self._format(object, sio, 0, 0, {}, 0)
    112         return sio.getvalue()
    113 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python/pprint.pyc in _format(self, object, stream, indent, allowance, context, level)
    127             self._readable = False
    128             return
--> 129         rep = self._repr(object, context, level - 1)
    130         typ = _type(object)
    131         sepLines = _len(rep) > (self._width - 1 - indent - allowance)

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python/pprint.pyc in _repr(self, object, context, level)
    193     def _repr(self, object, context, level):
    194         repr, readable, recursive = self.format(object, context.copy(),
--> 195                                                 self._depth, level)
    196         if not readable:
    197             self._readable = False

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python/pprint.pyc in format(self, object, context, maxlevels, level)
    205         and whether the object represents a recursive construct.
    206         """
--> 207         return _safe_repr(object, context, maxlevels, level)
    208 
    209 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python/pprint.pyc in _safe_repr(object, context, maxlevels, level)
    290         return format % _commajoin(components), readable, recursive
    291 
--> 292     rep = repr(object)
    293     return rep, (rep and not rep.startswith('<')), False
    294 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/structure/sage_object.so in sage.structure.sage_object.SageObject.__repr__ (sage/structure/sage_object.c:1090)()
     90 
     91 
---> 92 
     93 
     94 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyFieldElement._repr_ (sage/rings/real_lazy.c:5833)()
    555 
    556 
--> 557 
    558 
    559 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyFieldElement.approx (sage/rings/real_lazy.c:5880)()
    567 
    568 
--> 569 
    570 
    571 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyBinop.eval (sage/rings/real_lazy.c:7427)()
    825 
    826 
--> 827 
    828 
    829 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyBinop.eval (sage/rings/real_lazy.c:7439)()
    826 
    827 
--> 828 
    829 
    830 

/Users/ncalexan/sage-3.2.1.alpha1/local/lib/python2.5/site-packages/sage/rings/real_lazy.so in sage.rings.real_lazy.LazyAlgebraic.eval (sage/rings/real_lazy.c:10310)()
   1278 
   1279 
-> 1280 
   1281 
   1282 

IndexError: list index out of range
sage: 

4276-ncalexan.patch applies to 3.2.1.alpha2 and aggregates all robertwb's patches.

Thanks very much, ncalexan, for taking over refereeing of this patch. I don't have the background to review something like this (my initial attempts above made me realise that) and I was worried that other more qualified people would now assume I had it under control.

First, why squarefree_part bounded? This could be a separate patch.

Yes, in retrospect it could be. I moved that code out of the number field file, and while doing so decided to optimize it.

Second, I can specify non-embeddings that seem to be ignored:

I'm not sure what you're trying to show with your example. It picks the closest root (so one doesn't need to specify the root to an arbitrary precision).

Finally, I am having lots of trouble creating non-default embeddings:

sage: K2.<a> = NumberField(x^2 + 2, 'a', embedding=RR(-sqrt(2)))

I agree these tracebacks are bad, but it's having trouble deciding which of I*sqrt(2) or -I*sqrt(2) is closest to sqrt(2). I'll have it throw a more sensible error instead.

Everything rebased against 3.2.1

I've rebased against 3.2.1. Still building, but I'm off to bed.

With this patch and the one from #3623 applied I am seeing two doctest failures in

sage -t -long devel/sage/sage/structure/coerce.pyx # 3 doctests failed
sage -t -long devel/sage/sage/schemes/elliptic_curves/ell_number_field.py

The details are at #3623.

Cheers,

Michael