Opened 10 years ago
Closed 7 years ago
#14239 closed enhancement (fixed)
symbolic radical expression for algebraic number
Reported by:  Martin von Gagern  Owned by:  David Loeffler 

Priority:  major  Milestone:  sage6.5 
Component:  number fields  Keywords:  
Cc:  Merged in:  
Authors:  Martin von Gagern, Jeroen Demeyer  Reviewers:  Marc Mezzarobba, Jeroen Demeyer, Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  4626286 (Commits, GitHub, GitLab)  Commit:  4626286463c734f931ecc7405285dc7bc1b58772 
Dependencies:  #17495, #16964  Stopgaps: 
Description (last modified by )
It would be nice to have a function which converts algebraic numbers to symbolic expressions using radicals, at least for those cases where this is possible (i.e. the cases where the minimal polynomial of the algebraic number has a degree less than 5). For the quadratic case, I have a code snippet to illustrate what I'm asking for:
def AA2SR(x): x = AA(x) p = x.minpoly() if p.degree() < 2: return SR(QQ(x)) if p.degree() > 2: raise TypeError("Cannot handle degrees > 2") c, b, a = p.coeffs() y = (b+sqrt(b*b4*a*c))/(2*a) if x == AA(y): return y y = (bsqrt(b*b4*a*c))/(2*a) assert x == AA(y) return y def QQbar2SR(x): x = QQbar(x) return AA2SR(x.real()) + I*AA2SR(x.imag())
These functions could then be applied to vectors or matrices over algebraic real or complex numbers in order to obtain an exact description of the relevant values using radicals.
This request is a spinoff from my question on Ask Sage.
Attachments (1)
Change History (108)
Changed 9 years ago by
Attachment:  trac_14239_algebraic_to_radicals.patch added 

comment:1 Changed 9 years ago by
Status:  new → needs_review 

comment:2 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:3 followup: 5 Changed 9 years ago by
Reviewers:  → Marc Mezzarobba 

Status:  needs_review → needs_work 
I think the feature you are looking for sort of exists. But it is available for elements of number fields, not algebraic numbers. And it is pretty inconvenient to use with algebraic numbers because alg.as_number_field_element()
returns alg
as an element of an abstract number field (plus an embedding of that number field into QQbar
or AA
), while conversion to symbolic expressions expects a number field with a registered embedding into CC
or RR
.
Yet, with the example from your question on AskSage?, one can do:
sage: a = N[0][0] sage: nf, val, nf2alg = a.as_number_field_element() sage: approx = CC(nf2alg(nf.gen())) sage: embedded_nf = NumberField(nf.polynomial(), 'a', embedding=approx) sage: nf2nf = sage.rings.number_field.number_field_morphisms.NumberFieldEmbedding(nf, embedded_nf, embedded_nf.gen()) sage: SR(nf2nf(val)) 1/5*sqrt(5)
So I disagree with the approach you take in your patch: IMO, we should make something like the above example work automatically and share the actual conversion code between algebraic numbers and number fields instead of implementing essentially the same feature twice.
[edit: add missing word]
comment:4 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:5 followup: 6 Changed 9 years ago by
Replying to mmezzarobba:
Yet, with the example from your question on AskSage, one can do:
I just gave that code a try, and on sage 5.12 it failed in the assignment of embedded_nf
with
embedded_nf = NumberField(nf.polynomial(), 'a', embedding=approx) File "parent.pyx", line 761, in sage.structure.parent.Parent.__getattr__ (sage/structure/parent.c:6823) File "misc.pyx", line 251, in sage.structure.misc.getattr_from_other_class (sage/structure/misc.c:1606) AttributeError: 'RationalField_with_category' object has no attribute 'polynomial'
Probably due to an outdated sage, so feel free to ignore this if that's the case. Can't update this system just now.
comment:6 Changed 9 years ago by
Replying to gagern:
Probably due to an outdated sage
Yes, I think so. (I tried again on develop
from a few days ago, and it works.)
comment:7 Changed 9 years ago by
Branch:  → u/gagern/ticket/14239 

Created:  Mar 6, 2013, 9:43:41 PM → Mar 6, 2013, 9:43:41 PM 
Modified:  Jan 31, 2014, 7:50:11 AM → Jan 31, 2014, 7:50:11 AM 
comment:8 Changed 9 years ago by
Commit:  → 1ddc68cbd8cd536b3775a6c1bcba0e68511e7775 

Status:  needs_work → needs_review 
New commits:
1ddc68c  Implement method radical_expression for QQbar and AA elements.

comment:9 Changed 9 years ago by
Commit:  1ddc68cbd8cd536b3775a6c1bcba0e68511e7775 → 30f71099332d11f775dda3f78ae0f33eef1a5623 

Branch pushed to git repo; I updated commit sha1. New commits:
30f7109  Check radical expression using QQbar even for AA elements.

comment:10 Changed 9 years ago by
Commit:  30f71099332d11f775dda3f78ae0f33eef1a5623 → 039f4bf3bff139ce2630fe2fb8fd8f542096a498 

Branch pushed to git repo; I updated commit sha1. New commits:
039f4bf  Fix radical expression for rational numbers.

comment:11 Changed 8 years ago by
I notice that in real world applications, the check for self == QQbar(res)
takes excessively long. Example:
QQ[x](16*x^6  392*x^4 + 133*x^2 + 900).roots(AA, False)[1].radical_expression()
It gets stuck in several layers of exactify
, but eventually the keyboard interrupt ends up here:
File "sage/rings/qqbar.py", line 6798, in exactify red_elt, red_back, red_pol = do_polred(newpol_sage_y) File "sage/rings/qqbar.py", line 1645, in do_polred new_poly, elt_back = poly._pari_().polredbest(flag=1) File "gen.pyx", line 8048, in sage.libs.pari.gen.gen.polredbest (sage/libs/pari/gen.c:42279) File "c_lib.pyx", line 73, in sage.ext.c_lib.sig_raise_exception (sage/ext/c_lib.c:872)
On the one hand, I wonder whether there is some better way to detect an inexact conversion. I haven't looked enough at the internal structure of a symbolic expression to know how to handle this.
On the other hand, I wonder why this comparison is taking so long. Or even whether it is simply taking excessively long, or perhaps even got stuck completely. Perhaps this is an indication of some more fundamental problem. If you want to invastigate this, you can do so without checking out this branch. Simply using the example above, the relevant operation is the following:
a = QQ[x](16*x^6  392*x^4 + 133*x^2 + 900).roots(AA, False)[1] b = 1/1296*((9*I*sqrt(3)*(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3) + 9*(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3)  37*I*sqrt(3)/(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3) + 37/(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3) + 18)*(9*I*sqrt(3)*(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3) + 9*(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3)  37*I*sqrt(3)/(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3) + 37/(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3)  12)  3456)*sqrt(9/2*I*sqrt(3)*(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3)  9/2*(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3) + 37/2*I*sqrt(3)/(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3)  37/2/(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3) + 6) a == b
Even as it stands, having the as_radical_expression
method is better than not having it. So this comment here should be no reason not to merge the branch, in my opinion. On the other hand, I would very much welcome input to make things work faster for complicated expressions like those described above.
Barring any good ideas, I might eventually end up adding an optional argument exact
with a default value of True
. Setting that to False
would skip this check, and therefore possibly return an approximate symbolic ring element.
comment:12 followup: 13 Changed 8 years ago by
The problem is, an expression like this:
(2/9*I*sqrt(443)*sqrt(3) + 53/27)^(1/3)
has (at least) 3 possible values. You need to specify branch cuts to single out a particular value in, say, CC. Algebraically, sqrt(443)
, sqrt(3)
, and I
have the same problem. So when you first construct this element you are making essentially the ring
QQ[x,y,z,w]/(x^2443,y^23,z^2+1,w^3(2/9*z*x*y + 53/27))
which is of rather high degree.
The other elements you add to this will just add to the degree, since the next time a sqrt(443)
is encountered, it is not algebraically clear that this is supposed to be the same as the one designated by x
. The complex embedding that comes with AA or Qbar specifies some of the ambiguity (e.g., the branch cut of sqrt(443)
will ensure the "positive" root always), but once you start taking roots of complex numbers, the cuts might not even do what they algebraically are supposed to (e.g., (z)^(1/3) != (z)^(1/3)
).
While in the expression for b
that you give, it is exactly the same expression that you are taking the cube root of repeatedly, one can only see this after careful inspection. For a human it's clear you're meaning the "same" cube root every time, but the computer has no immediate way of finding that out. A priori, all the choices made by sqrt...
and (...)^(1/3)
are considered as algebraically unrelated and only with laborious computations using the embedding in CC
does one rediscover those relations. If instead you do
u=Qbar(sqrt(3)) v=Qbar(sqrt(443))*u w=Qbar( (2/9*v+53/27)^(1/3))
and then construct b from that, you should already get a little faster results.
The problems you are running into are fairly wellunderstood and real. Symbolic notation as you use it fails to express the full algebraic relations once you start repeating related expressions.
EDIT: apologies. The fact that the value didn't match was due to a missubstitution on my part. I've corrected the result below. The value b
computed does match what it's supposed to be:
sage: u=QQbar(sqrt(3)) sage: v=QQbar(sqrt(443))*u sage: w=(2/9*v + 53/27)^(1/3) sage: b = 1/1296*((9*u*w + 9*w  37*u/w + 37/w + 18)*(9*u*w + 9*w  37*u/w + 37/w  12)  3456)*sqrt(9/2*u*w  9/2*w + 37/2*u/w  37/2/w + 6) sage: b 4.904821984561304? + 0.?e16*I sage: 16*b.minpoly() #still takes a long time 16*x^6  392*x^4 + 133*x^2 + 900
The fundamental problem remains, though: the symbolic version doesn't quite carry the same information. In addition, some of the slowness might be due to QQbar` itself, since:
sage: t=(9/2*u*w  9/2*w + 37/2*u/w  37/2/w + 6) sage: t.minpoly() # this is fast x^3  18*x^2  891*x + 2916 sage: r=sqrt(t) sage: r.minpoly() # this is quite slow x^6  18*x^4  891*x^2 + 2916 sage: b = 1/1296*((9*u*w + 9*w  37*u/w + 37/w + 18)*(9*u*w + 9*w  37*u/w + 37/w  12)  3456)*r sage: b.minpoly() #this is now pretty quick x^6  49/2*x^4 + 133/16*x^2 + 225/4
so QQbar is slow exactifying an element r
for which it has all relevant algebraic information (it's the square root of t
, which has a known minimal polynomial)
Computer algebra systems such as maple have their own symbolic ways of dealing with the ambiguity introduced by defining elements as "roots" of polynomials:
> lprint(solve(x^5+4*x+1)); RootOf(_Z^5+4*_Z+1,index = 1), RootOf(_Z^5+4*_Z+1,index = 2), RootOf(_Z^5+4*_Z +1,index = 3), RootOf(_Z^5+4*_Z+1,index = 4), RootOf(_Z^5+4*_Z+1,index = 5)
which allows it to simplify RootOf(_Z^5+4*_Z+1,index = 1)RootOf(_Z^5+4*_Z+1,index = 1)
to 0 but leave RootOf(_Z^5+4*_Z+1,index = 1)RootOf(_Z^5+4*_Z+1,index = 2)
alone. This doesn't capture the algebraic dependencies between the roots, but at least allows identification of each root individually.
comment:13 followup: 14 Changed 8 years ago by
Thanks for explaining a bit of what's going on here to cause such delays. Alternate ways to compute things more efficiently are all very well, but won't be of use unless I can make this automatic somehow. After all, on the high level all I do is compare two numbers, without wanting to think about implementation details.
While investigating this problem, I noticed that for my original length expression b
the call b.minpoly()
works really fast, whereas QQbar(b).minpoly()
takes ages. Makes me wonder whether the exactification should be somehow based on the minimal polynomial of the symbolic expression. Or at least leverage some of the machinery which makes that so fast. That should speed up the kind of comparison I'm using. Or is that computation somehow inexact?
Let me try to think this through. Naively I'd rewrite sage.symbolic.expression_conversions.algebraic
to first compute the minpoly of the expression in question. I fear that this might take long, which is a problem in those cases where we don't need the exact representation. So it would probably be better to only do this on demand. Which raises several related questions.
 Can we store a reference to a symbolic expression without having to worry that it will get modified? Are symbolic expressions readonly after construction?
 Can we afford the cost of storing whole symbolic expressions in addition to their AA or QQbar converted forms? Or should we try to reconstruct the symbolic expression from the descriptor DAG when needed?
 How do we link the symbolic expression with the algebraic number? We could invent a descriptor which is layered around the one returned from the current conversion approach, but whose
exactify
method will compute the minimal polynomial of the whole expression instead of recursing.  On the other hand, we might need access to the current interval, so an alternative would be storing such information in
AlgebraicNumber_base
and modify itsexactify
method to take the additional information into account.  Are there cases where a symbolic
minpoly
would take significantly more time than the corresponding recursiveexactify
? If so, can we somehow detect these cases before we start the symbolicminpoly
computation?  We need to find roots for that polynomial, which I'd so via a simple
p.roots(self.parent(), False)
unless someone suggests otherwise.  Wen need to compare them to the approximation returned by the nested descriptor. Which is probably the main reason to have this in
AlgebraicNumber_base
instead of someANDescr
descendant.  We might have to increase precision until the interval contains no more than a single solution. Simple with
AlgebraicNumber_base._more_precision
but difficult or wasteful forANDescr
.
Does this approach make sense?
comment:14 Changed 8 years ago by
Replying to gagern:
Makes me wonder whether the exactification should be somehow based on the minimal polynomial of the symbolic expression.
Created spinnoff ticket:16222 for this.
For this one here, I have another solution in mind which I'll push shortly.
comment:15 Changed 8 years ago by
Commit:  039f4bf3bff139ce2630fe2fb8fd8f542096a498 → a65fa2b7be9560837ffb80ebcc6779a8d47bad42 

comment:16 Changed 8 years ago by
Milestone:  sage6.2 → sage6.3 

comment:17 Changed 8 years ago by
Authors:  → Marc Mezzarobba, Martin von Gagern 

comment:18 Changed 8 years ago by
I found that my branch still has some problem. In particular, in the following situation Sage will do the conversion even though it is inexact.
sage: sorted(QQ[x](x^7  x  1).roots(QQbar, False), key=imag)[0].radical_expression() 3775/3963*I  2573/7076
So my assumption that an inexact solution will always leas to floats embedded into SR appears to be wrong. Is there some other way to check whether a given result is exact? Or perhaps even to not try any inexact conversion at all? I found no such thing, but it seems to me I haven't found the core of this conversion either.
comment:19 Changed 8 years ago by
Commit:  a65fa2b7be9560837ffb80ebcc6779a8d47bad42 → 16269faa29708fad205889d3063008772c036df5 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
16269fa  Trac #14239: Implement method radical_expression for QQbar and AA elements.

comment:20 Changed 8 years ago by
OK, I completly rewrite my approach. Due to #16651 I don't trust the conversion from NumberField to SymbolicRing. So I read the essence of what they are doing, and adapted it to my use. It works excellent in all the test cases I have gathered so far.
However, I still have some trouble finding good test cases to cover all my code paths. I'm not sure whether you'd be willing to accept my patch without that kind of coverage. Here is what's missing:
 Some number where
to_poly_solve=False
won't find the solution butto_poly_solve=True
will yield an exact solution.  Some number where solve will not find all roots, or only some of these are exact.
 Some situation where we can demonstrate that multiple symbolic roots overlap the current value interval.
For the third use case, the one where len(candidates) == 1
fails, I just found an example: AA(sqrt(2)*10^(25)+3)
. I'll have to write some more code to ensure that it will in fact use the code path for which I designed it. Working on that.
comment:21 Changed 8 years ago by
Commit:  16269faa29708fad205889d3063008772c036df5 → e416116556a29c0b9304a5b7d5026f67b0e6ce3f 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e416116  Trac #14239: Implement method radical_expression for QQbar and AA elements.

comment:22 Changed 8 years ago by
Authors:  Marc Mezzarobba, Martin von Gagern → Martin von Gagern 

comment:23 Changed 8 years ago by
If there are any objections to the lack of tests for the to_poly_solve=True
code path, then I'd be willing to take that out until someone can come up with an example to actually test that. If I simply replace the twotuple by a onetuple in the loop, that would be simple enough to restore later on. If I should remove all the code which is specific to to_poly_solve=True
, then I'd like to back that up somewhere so it may be reactivated later on. Perhaps I'd do the removal as a separate commit which can be reverted if someone comes up with a case.
By the way, the Maxima manual for to_poly_solve didn't suggest some useful case either. Since the main benefit of to_poly_solve
appears to be its ability to turn the equations into polynomials, it probably has little benefit over the standard solver. 3278794 from #6642 which introduced the use of to_poly_solve=True
for NumberFieldElement
doesn't contain any example of why it might be needed.
comment:24 Changed 8 years ago by
Commit:  e416116556a29c0b9304a5b7d5026f67b0e6ce3f → 006fa24b1199b44a2963ee0c14896f5e4d9003b0 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
006fa24  Trac #14239: Implement method radical_expression for QQbar and AA elements.

comment:25 followup: 26 Changed 8 years ago by
comment:26 Changed 8 years ago by
Replying to vbraun:
IMHO #16651 should be fixed instead of adding workarounds for #16651 elsewhere.
Even with #16651 fixed, there are several reasons why I'd consider the detour via NumberFieldElement
to be inferior to my approach here.
 In case of no exact solution,
NumberFieldElement
will use an approximation, while my idea here is to never loose precision. So you'd have to either declare all uses of approximation inNumberFieldElement
to be undesired as well, or add some flag to suppress approximate solutions. Or detect them after the fact, and hope I get it right this time around.
 In some cases, the degree used for the conversion to a number field element is much bigger than that of the minimal polynomial. In one case I've seen the number field to have a dense defining polynomial of degree 24, while the minpoly only had even degrees up to 6. This might of course well be considered a bug in its own right.
 My code can deal with a situation where the number of distinct roots found by the symbolic solver does not equal the degree of the polynomial.
NumberFieldElement
will give up in that situation. I don't know yet whether we might encounter polynomials with multiple roots, and I don't know how likely it is for the solver to find only a subset of all roots. But with a too high degree and the use ofto_poly_solve=True
I consider both likely.
 I'm not sure I trust the root matching in
ambient_field=ComplexField(53)
. There are cases where the different roots cannot be distinguished in this field, and I believe that in these cases the approach of “taking the closest root” is unreliable at best.
If you are confident that most of the issues raised above should be fixed for NumberFieldElement
as well, then I'll investigate options to share code between both implementations.
comment:27 Changed 8 years ago by
I don't know the NumberFieldElement
implementation well enough to have an opinion on whether the code should be shared. I was only commenting on this ticket trying out different to_poly_solve
options and checking exact answers from solve. Also, you should use to_poly_solve='force'
since you definitely want to use the algebraic system solver from maxima. With my patch from #16651 this should always either return an exact solution or a floatingpoint approximate solution.
comment:28 Changed 8 years ago by
Milestone:  sage6.3 → sage6.4 

comment:29 Changed 8 years ago by
Commit:  006fa24b1199b44a2963ee0c14896f5e4d9003b0 → d2f72c655cc22f18c9029da5feff12f35eb0dbf8 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
d2f72c6  Trac #14239: Implement method radical_expression for QQbar and AA elements.

comment:30 Changed 8 years ago by
Rebased onto 6.4.beta2, and dropped the to_poly_solve=True
code since comment:15:ticket:16651 suggests that we can't expect to gain anything from this, and dropping it means we can avoid dealing with approximate solutions altogether.
comment:31 followup: 32 Changed 8 years ago by
Status:  needs_review → needs_work 

I dislike
# Adapted from NumberFieldElement._symbolic_()
If two implementations do the same thing, there should be a common function...
comment:32 followup: 33 Changed 8 years ago by
Replying to jdemeyer:
I dislike
# Adapted from NumberFieldElement._symbolic_()If two implementations do the same thing, there should be a common function...
They don't do the same thing. Please read my comment:26. Looking at the code, the common functionality is essentially two and a half lines:
poly = self.minpoly() var = SR(poly.variable_name()) for soln in SR(poly).solve(var, …
Where I pass explicit_solutions=True
, number field elements pass to_poly_solve=True
. Where they collect all roots and do a closest root matching in a 53 bit ambient field, I only collect roots which fall into our separating interval and hope (but don't require) that only one of the roots found does that. Where they give up in cases where not all solutions were found, I try each found solution to check whether it's the one I need. I do the same verification if I got more than one root into my isolating interval, contrary to my hope stated above.
It could well be that although the two implementations don't do the same thing at the moment, they should do the same thing because what's right in one case is right in the other as well. In that case, I could adjust my code to encompass the number field case as well. The verification of roots in cases where more than one is found would have to happen in QQbar
but it shouldn't hurt to do that step in QQbar
in any case.
I haven't yet figured out how to obtain an isolating interval for a number field element. And where would you suggest to place such a function, if I were to write it? Which module is most suitable for this?
My main concern is that I put in this extra work and then eventually someone gives me a negative review because it modifies established behavior of the numeric element implementation. Or because there is a good reason for things to be done differently there which I hadn't thought of before.
Would you give the current commit a conditional positive review? Would you say that if combining the code turns out to be impossible for some reason, then we can go back to the current code and merge that?
comment:33 Changed 8 years ago by
Replying to gagern:
It could well be that although the two implementations don't do the same thing at the moment, they should do the same thing because what's right in one case is right in the other as well.
That's absolutely true.
comment:34 Changed 8 years ago by
Would you give the current commit a conditional positive review?
I haven't actually looked at the code, but I will never give an actual positive review for two implementations of the same thing.
comment:35 Changed 8 years ago by
Reviewers:  Marc Mezzarobba → Marc Mezzarobba, Jeroen Demeyer 

comment:36 followup: 37 Changed 8 years ago by
I haven't yet figured out how to obtain an isolating interval for a number field element.
Perhaps a def isolating_interval(self)
method of NumberFieldElement
and an analogous function for QQbar
?
Using such a function properly, you wouldn't need to consider the case of multiple candidates
, it's better to ensure a priori that you have only a single candidate.
comment:37 followup: 39 Changed 8 years ago by
Replying to jdemeyer:
I haven't yet figured out how to obtain an isolating interval for a number field element.
Digging for that myself, I found that
 NumberFieldElement only converts the field generator to symbolic, everything else is accomplished by plugging that into a polynomial.
 The image of the generator comes from the embedding, and as such will be either from an exact field or from a lazy field.
 If it comes from an exact field, it is likely already from
QQbar
orAA
or easily converted to those. If it comes from a lazy field, it's a LazyAlgebraic and as such essentially an element of AA or QQbar as well, at least if you want guaranteed isolation.
So I wonder whether instead of moving the common code to some common function, we should simply replace the relevant portion of NumberFieldElement._symbolic_
with a call to this newly provided AlgebraicNumber_base.radical_expression()
. That would leave my code where it currently is, would avoid code duplication and should have about the same kind of performance unless I overlooked something in my investigation above.
What do you think?
Perhaps a
def isolating_interval(self)
method ofNumberFieldElement
and an analogous function forQQbar
?
The latter would be easy: simply return the _value
of the descriptor. The former might be more tricky. As outlined above, the image of the generator can be different things, and the best way to avoid a million case distinctions is probably by casting it to AA
or QQbar
as appropriate. The isolating interval of a nongenerator would depend on the minimal polynomial of that element, and the best way I can think of to find an isolating interval for that as well would again be to cast it to AA
resp. QQbar
.
If we build NumberFieldElement._symbolic_()
on AlgebraicNumber_base.radical_expression()
as suggested above, then we have no need for such a method. If, on the other hand, we don't build on a cast to algebraic, then I don't see how one would implement this for number field elements. Of course, even if we don't need it just now, it might be nice to provide access to isolating intervals to our users, but that would be a separate issue and might best be done for AlgebraicNumber_base
only.
Using such a function properly, you wouldn't need to consider the case of multiple
candidates
, it's better to ensure a priori that you have only a single candidate.
I don't follow you. You have isolating intervals. So say you have two roots, then you have some interval around each root. Then you take that interval field with its precision, and evaluate the symbolic expression in that. Nothing I can think of will ever guarantee a priori that the resulting interval for the symbolic expression doesn't overlap the intervals of both your roots. After all, the symbolic expression might be fairly involved, leading to high errors in the final interval. The only reasonable way I can think of to rule out multiple overlap is to test for it, leading to my candidates. If there are more, then I have two options: either check for equality like I did, or increase the precision for the symbolic expression evaluation. But we don't want to increase the precision indefinitely, so we'll need the exact computation in the end in any case, as the final fallback. And since all of this should be pretty rare, I see no need to introduce additional code which would be hard to test and could therefore cause obscure errors every now and then. Let's keep the rare case as simple as possible, and the common case as efficient as possible.
comment:38 followup: 41 Changed 8 years ago by
I think it's much more natural to combine code the other way around: implement everything on the level of NumberFieldElement
and then call that code from AA
/QQbar
.
comment:39 followup: 40 Changed 8 years ago by
Replying to gagern:
either check for equality like I did, or increase the precision for the symbolic expression evaluation.
The problem is that I don't really know how this "checking for equality" works. If it works well, then why bother with intervals in the first place?
Let's keep the rare case as simple as possible
Agreed, increasing precision is surely simpler!
comment:40 followup: 43 Changed 8 years ago by
Replying to jdemeyer:
The problem is that I don't really know how this "checking for equality" works. If it works well, then why bother with intervals in the first place?
Checking for equality means turning the symbolic expression into an algebraic number. Which in turn means building a tree of algebraic number descriptors. Comparing them with the input number will work by the usual comparison of algebraic numbers, which starts by a few rounds of increasing precision but in the end boils down to finding a common number field to accomodate both values and doing the arithmetic there. Which can be really slow. So it works, it may be unavoidable as a last resort, but it comes with a severe performance penalty. In comment:12 Nils Bruin explained why that operation is so slow. #16222 (which resulted from comment:13) and #16964 might reduce that penalty somewhat, but it would still be better to avoid that.
comment:41 followups: 42 44 Changed 8 years ago by
Replying to jdemeyer:
I think it's much more natural to combine code the other way around: implement everything on the level of
NumberFieldElement
and then call that code fromAA
/QQbar
.
I disagree. With AA
resp. QQbar
the computation is available for any element of the field, and is always based on the minimal polynomial (for the sake of consistency), even for cyclotomic elements. For NumberFieldElement
the computation is only performed for the generator, and only for noncyaclotomic fields, so the code we're talking about is one of may possible cases in a larger control flow structure. What is more, the cast from NumberFieldElement
to AA
resp. QQbar
is easy and cheap. The converse has quite a bulky syntax, as you can see in comment:3, and can be quite costly, as I mentioned in comment:26 item 2.
Or, to put it differently, this is not about converting number field elements. This is about converting the generator of a number field, which itself is an algebraic number, into a symbolic expression. This involves finding solutions of a symbolic polynomial, comparing isolating intervals (which is a thing of algebraic numbers not number field elements), and if that fails, casting to an algebraic number and comparing the result for equality. Seems to me a lot closer to algebraic numbers than to number field elements.
comment:42 Changed 8 years ago by
Replying to gagern:
For
NumberFieldElement
the computation is only performed for the generator, and only for noncyclotomic fields, so the code we're talking about is one of may possible cases in a larger control flow structure. What is more, the cast fromNumberFieldElement
toAA
resp.QQbar
is easy and cheap. The converse has quite a bulky syntax, as you can see in comment:3, and can be quite costly, as I mentioned in comment:26 item 2.
All of this can be fixed. I understand that you're unhappy with the current situation and I'm not disagreeing. But instead of working around these problems, they should be fixed. If the wheel is broken, then fix it instead of reinventing the nonbroken wheel.
comment:43 Changed 8 years ago by
Replying to gagern:
Checking for equality means turning the symbolic expression into an algebraic number. Which in turn means building a tree of algebraic number descriptors. Comparing them with the input number will work by the usual comparison of algebraic numbers, which starts by a few rounds of increasing precision but in the end boils down to finding a common number field to accomodate both values and doing the arithmetic there. Which can be really slow.
Then stick to using intervals. I completely agree with your argument that the "rare" case should be as simple as possible. Which for me means to not have a completely different code path.
comment:44 Changed 8 years ago by
Replying to gagern:
Or, to put it differently, this is not about converting number field elements. This is about converting the generator of a number field, which itself is an algebraic number, into a symbolic expression. This involves finding solutions of a symbolic polynomial, comparing isolating intervals (which is a thing of algebraic numbers not number field elements), and if that fails, casting to an algebraic number and comparing the result for equality. Seems to me a lot closer to algebraic numbers than to number field elements.
I'd say it's about number field elements with a specified embedding...
comment:45 Changed 8 years ago by
Note that for me, the discussion about whether the code should go into QQbar
or NumberFieldElement
is the least of my worries. If you're really convinced that QQbar
is the better way, then so be it provided that the code also works equally well for NumberFieldElement
.
comment:46 followup: 49 Changed 8 years ago by
I have the gut feeling that we might be misunderstanding one another somewhere. So it it looks as if I'm unwilling to take good advice, it might be because I'm misunderstanding that advice and can't see that it's indeed good.
It seems as if in comment:42 you're suggesting that we should always convert to AA
resp. QQbar
and do the equality comparison there. I disagree for the following reason: deciding whether to algebraic numbers are equal is hard, since it involves exact computation. Deciding which of a given set of algebraic numbers is equal to a given number is a lot cheaper that exactly one of them must be equal, since in most cases that can be decided using interval arithmetic. Of course we could convert all found symbolic roots to AA
resp. QQbar
and do the candidate check there. But we'd convert from SR
to AA
/QQbar
for no practical reason at all, and still end up with a second code path to cater for the case of multiple candidates. To stretch your metaphor, if I want to drive in a nail I should choose a hammer, not a wheel, no matter whether the wheel is broken or not. Always use the appropriate tool.
If I understand you correctly, in comment:43 you suggest that I wrap the whole candidate collection process in a big loop which increments precision until there is exactly one candidate left. Doing so should be possible, but not trivial. One question we'd have to answer is which precision do we increase? The intervals of the symbolic expression evaluations might be huge, so we should be decreasing those always. The interval of the current algebraic number is known to be small enough to be isolating. But by sheer bad luck it might still be big enough that it almost touches a neighboring root, in which case increasing its precision once might lower the need for precision when evaluating the symbolic expressions. Suppose I got that wrapped up, I should hope that I'd only have to increase precision a finite number of times to reduce the number of candidates to one. But even then, I still haven't ruled out the case where I don't get symbolic expressions for all roots. That still has me worried, since I simply don't know what I can assume in that regard. Of course I could give up, like number field element symbolification does, and perhaps even ask users to report a bug indicating what scenario caused such problems.
In comment:44 I still disagree. When you convert number field elements, you do that by plugging the converted generator into some polynomial. That's code which is already in place, and which I'd leave as is. But as I just see, this is no show stopper for you, so I'll simply do that my way in the next commit and you see how that looks to you.
comment:47 Changed 8 years ago by
Commit:  d2f72c655cc22f18c9029da5feff12f35eb0dbf8 → 8ff313d2ea936471a4dda3989f9da440e8afe6b2 

comment:48 Changed 8 years ago by
Status:  needs_work → needs_review 

a12a118 does the intervalonly approach you requested in comment:43, without increasing the accuracy of self
. We should end up with a single overlap nonetheless.
43d19da removes the duplicate functionality, calling from number field element to qqbar. The casting of the generator image required a bit more code than anticipated, but still feels like the correct approach to me. As a benefit, we get exact algebraic numbers instead of floating point approximations if there is no radical expression for a given number field element generator, as seen in the doctests.
comment:49 Changed 8 years ago by
Replying to gagern:
It seems as if in comment:42 you're suggesting that we should always convert to
AA
resp.QQbar
and do the equality comparison there.
No, it was a very general comment of the form "don't work around bugs". If you say "I implemented this by doing B instead of the more obvious A, since A is broken", then that's a sign that you should fix A first and then use A.
deciding whether to algebraic numbers are equal is hard
Really, why? Isn't it just a matter of comparing the minimal polynomials first and then a floatingpoint interval approximation second? What's hard about that?
If I understand you correctly, in comment:43 you suggest that I wrap the whole candidate collection process in a big loop which increments precision until there is exactly one candidate left.
Exactly.
The interval of the current algebraic number is known to be small enough to be isolating. But by sheer bad luck it might still be big enough that it almost touches a neighboring root, in which case increasing its precision once might lower the need for precision when evaluating the symbolic expressions. Suppose I got that wrapped up, I should hope that I'd only have to increase precision a finite number of times to reduce the number of candidates to one.
Well yes. I think a large enough precision should always work.
But even then, I still haven't ruled out the case where I don't get symbolic expressions for all roots.
Can that actually happen? I wouldn't mind to just give up in this case and don't return a radical expression.
In comment:44 I still disagree. When you convert number field elements, you do that by plugging the converted generator into some polynomial.
You don't have to do that. You could just work with the minimal polynomial of the number field element (which is trivial to compute).
comment:50 Changed 8 years ago by
I think you're still leaving way too much code in NumberFieldElement._symbolic_
, for example the special case for cyclotomics...
comment:51 followup: 53 Changed 8 years ago by
I really insist that you put all the code to do this in one place.
comment:52 Changed 8 years ago by
Status:  needs_review → needs_work 

comment:53 Changed 8 years ago by
In my opinion it makes sense to have the special case for cyclotomics in number field element. Take the example from the doctest:
sage: K.<zeta> = CyclotomicField(19) sage: SR(zeta) # indirect doctest e^(2/19*I*pi)
Yes, this is a conversion of a number field generator to the symbolic ring, so it should be the output of a conversion from number field to symbolic. On the other hand, this is not a radical expression, therefore it would be unsuitable for AlgebraicNumber_base.radical_expression()
. That's the reason I didn't move that code.
Of course, you could argue that we should have AlgebraicNumber_base.symbolic_expression()
. But I'd still like to keep access to the radical expressions, for those cases where both make sense. Example:
sage: K.<z10> = CyclotomicField(10) sage: a = z10 + z10^9 sage: SR(a) (e^(1/5*I*pi)  1)*e^(2/5*I*pi) + 1 sage: AA(QQbar(SR(a))).radical_expression() 1/2*sqrt(5) + 1/2
The first thing makes sense if you are explicitely working in a cyclotomic field, where the symbolic expression for z10
is something you can reasonably expect in your output. If, on the other hand, you work with algebraic numbers, you shouldn't have to care about the internal representation. Hiding the different internal implementations behind a common interface therefore felt good. Every algebraic number has a minimal polynomial. So I'm using that as the basis for my conversion. Specialcasing the cyclotomics in qqbar would be a lot harder. It would depend on the actual descriptors, which in turn depend on the number fields used in their leafs, which in turn makes this conversion closer to number fields than what I did with the radical expressions.
So if I can convince you, I'd like to keep the current split as it is in my commits, and suggest a followup ticket for AlgebraicNumber_base.symbolic_expression()
, where the best approach to implement that might still be subject to discussion.
comment:54 Changed 8 years ago by
I get your point about cyclotomic elements.
Note that my comment 50 wasn't only talking about cyclotomics, there is still a lot of code left in NumberFieldElement._symbolic_
.
comment:55 Changed 8 years ago by
Branch:  u/gagern/ticket/14239 → u/jdemeyer/ticket/14239 

Modified:  Dec 13, 2014, 11:17:30 AM → Dec 13, 2014, 11:17:30 AM 
comment:56 Changed 8 years ago by
Commit:  8ff313d2ea936471a4dda3989f9da440e8afe6b2 → 06da2a3a251be8498e3ab3d1718e37d287a0e1c6 

I was thinking along the lines of this commit here...
New commits:
06da2a3  Simplify NumberFieldElement._symbolic_

comment:57 Changed 8 years ago by
Commit:  06da2a3a251be8498e3ab3d1718e37d287a0e1c6 → 01b7e9e4aaa15a34d1d19788c36f47df1741bfe6 

Branch pushed to git repo; I updated commit sha1. New commits:
01b7e9e  Use refine_embedding to convert to AA/QQbar

comment:58 Changed 8 years ago by
Dependencies:  → #17495 

comment:59 followups: 60 61 Changed 8 years ago by
I don't know about the internals of refine_embedding
, but 01b7e9e looks good to me at first glance. The fact that id adds a dependency feels bad, though, since that would mean further delay on this ticket here. Of course, failing doctests make development tricky here.
In 06da2a3 you drop the caching of the symbolic conversion of the generator, which might be bad for performance. What is your rationale behind this? And what is your rationale for moving the application of self.polynomial()
to QQbar
instead of SR
? On the whole, I can see your motivation for wanting further simplification there, but I don't see this related to this ticket here. This ticket here is in my opinion about a new method for algebraic numbers, without introducing duplicate code. That doesn't need your simplifications. Can we keep separate concerns separate? If you review my code, I'll be happy to review any simplifications you build on that in a separate ticket.
comment:60 Changed 8 years ago by
Replying to gagern:
Can we keep separate concerns separate?
I actually prefer to keep it together because of easier testing: if you two tickets doing closely related things, then you really need to test that changes in one ticket do not break the other ticket. To avoid this, I think it's better to just have one ticket.
comment:61 followup: 67 Changed 8 years ago by
Replying to gagern:
And what is your rationale for moving the application of
self.polynomial()
toQQbar
instead ofSR
?
 Plugging symbolic expressions into polynomials tend to give more complicated expressions. So the conversion to symbolic should be done as very last thing.
 With my code, the result doesn't depend on the choice of generator or number field: elements which are equal in
QQbar
yield equal symbolic expressions.  My code works in cases where the generator of the field doesn't have a radical expression, but the element does.
comment:62 Changed 8 years ago by
Dependencies:  #17495 → #17495, #16964 

Adding #16964 as dependency because it makes the computation of the embedding of the number field element into QQbar
horribly slow.
comment:63 Changed 8 years ago by
Commit:  01b7e9e4aaa15a34d1d19788c36f47df1741bfe6 → 24b00c640ccc096afa24da92e29cf2c1372628e2 

Branch pushed to git repo; I updated commit sha1. New commits:
24b00c6  Add an example in degree 10 with degree 2 subfield

comment:64 followup: 65 Changed 8 years ago by
Thanks for the rationale from comment:35. Can you add test cases for each of these benefits? I see you already wrote one for the case where the generator has no radical expression. So far none of the existing test cases covers the other two benefits, though, since none had to be changed.
Since you removed the caching of symbolic expressions in the __symbolic
member of the number field element, I think you should also remove said member from the number_field_element.pxd
since it is without use now.
I'm still not happy that now we'll have to fix two other issues before we can evaluate what you did here and see whether the (quite valid) gains are worth the performance penalty due to the removal of caching. Or, to be more precise, I'm unhappy that my own modifications are blocked together with this.
I also have some doubts about the refine_embedding
approach. As far as I can see, the refined embedding should get cached in the number field, but I'd prefer to see that verified by a test case. The choice which of these embeddings to use doesn't seem to be cached, so that matching would be repeated for every conversion. Not sure how costly that is, but I would prefer if we could cache the algebraic embedding which matches the specified complex embedding explicitely. Looking at embeddings
I also think that K['x'](self.defining_polynomial()).roots()
is probably bad, since singular can't deal with polynomials with algebraic coefficients. Shouldn't this be self.defining_polynomial().roots(K)
instead? The subsequent r.sort()
seems superfluous, since roots are to my knowledge always returned in sorted order.
comment:65 Changed 8 years ago by
Replying to gagern:
I'm still not happy that now we'll have to fix two other issues before we can evaluate what you did here
I understand your unhappiness, but consider that #17495 should be quite easy to fix and that #16964 is very much in need of a fix anyway (for various reasons, not just this ticket).
I also have some doubts about the
refine_embedding
approach.
Perhaps, but those comments really belong to #17495.
comment:66 Changed 8 years ago by
comment:67 followups: 75 82 Changed 8 years ago by
Replying to jdemeyer:
 My code works in cases where the generator of the field doesn't have a radical expression, but the element does.
However, it fails in cases where we are unable to find a radical expression for the element even though we would have been able to find one for the generator. Case in point:
sage: K.<a> = NumberField(QQ['x']([6, 65, 163, 185, 81, 15, 1]), embedding=4.9) sage: b = a + a^3 sage: SR(b) 120.55238677055798? sage: b.polynomial()(SR(a)) 1/8*((sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 5)^2 + 4)*(sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 5)
Not sure how to proceed here. One approach would be to try conversion of the nongenerator element first, and if that fails (as evidenced by x.radical_expression().parent() != SR
) try again for the generator and plug that into the polynomial.
comment:68 Changed 8 years ago by
Branch:  u/jdemeyer/ticket/14239 → u/gagern/ticket/14239 

Modified:  Dec 15, 2014, 1:55:40 PM → Dec 15, 2014, 1:55:40 PM 
comment:69 Changed 8 years ago by
Commit:  24b00c640ccc096afa24da92e29cf2c1372628e2 → df036339e25fcac24a3497b0cd74f4bf34d5816c 

I merged the dependencies into this, to facilitate testing of the changes here and to ensure this doesn't accidentially get merged without its dependencies. I also implemented the fallback discussed in comment:67.
New commits:
f30d693  Only consider real embeddings if old embedding is into real lazy field.

cbe823a  When determining embeddings, leave coefficients rational.

e689bc4  Merge branch 'ticket/17495' into ticket/14239

2c4ac1b  Faster qqbar comparison for case with equal minpoly.

bfa2338  Merge branch 'ticket/16964' into ticket/14239

df03633  Fall back to convertig generator to symbolic.

comment:70 Changed 8 years ago by
Commit:  df036339e25fcac24a3497b0cd74f4bf34d5816c → a5983f73b2acdbdd197f25d07c1fcf14bf1109e5 

Branch pushed to git repo; I updated commit sha1. New commits:
a5983f7  Drop __symbolic member from NumberFieldElement.

comment:71 followup: 76 Changed 8 years ago by
Looking back to comment:3 I find that for the example from comment:67 that approach is able to find a radical expression on the level of the algebraic numbers, without knowledge of the original number field:
sage: c = AA.polynomial_root(b.minpoly(), RIF(120,121)) sage: nf, val, nf2alg = c.as_number_field_element() sage: val.polynomial()(nf2alg(nf.gen()).radical_expression()) 1/8*((sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 13)*(sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 1) + 52)*(sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 1) + 10
So in a certain sense, as_number_field_element
makes it easier to find a symbolic expression for a given algebraic number, even though the expression found in this way may be more complicated. I wonder whether I should include that into my radical_expression
method. Probably with a switch to allow disabling it.
comment:72 Changed 8 years ago by
Commit:  a5983f73b2acdbdd197f25d07c1fcf14bf1109e5 → a4fa89444e8f8d8da082c4b91849cade8aca5f79 

Branch pushed to git repo; I updated commit sha1. New commits:
a4fa894  Convert qqbar to radicals via number field.

comment:73 Changed 8 years ago by
Commit:  a4fa89444e8f8d8da082c4b91849cade8aca5f79 → 09683145989c437b59e02c02409d1dac05ac379d 

Branch pushed to git repo; I updated commit sha1. New commits:
0968314  Extend doctest for via_nf distinction.

comment:74 Changed 8 years ago by
I considered using the simplified NumberFieldElement._symbolic_
method as a template for a matching NumberFieldElement._algebraic_
which would address #5355, #12715, #13041 and perhaps some others I hadn't found. Unfortunately, simply adding such a method results in a ton of failed coercions. Apparently such an approach would cause a lot of stuff to go via number fields which didn't take that route before. Nevertheless, those things might be worth fixing, and in the long run we should have a simple path from number field elements to algebraic numbers. And the two functions would likely look similar to one another.
I'd prefer to get this ticket here accepted first, then try to implement conversion to algebraic and see how best to avoid code duplication. While still keeping things readable, since factoring out stuff like the outer case distinction for cyclotomics would be possible but might cause very ugly code constructs if the code for each case is to be rather flexible. We'll see when we get there.
comment:75 followup: 78 Changed 8 years ago by
Replying to gagern:
However, it fails in cases where we are unable to find a radical expression for the element even though we would have been able to find one for the generator. Case in point:
sage: K.<a> = NumberField(QQ['x']([6, 65, 163, 185, 81, 15, 1]), embedding=4.9) sage: b = a + a^3 sage: SR(b) 120.55238677055798? sage: b.polynomial()(SR(a)) 1/8*((sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 5)^2 + 4)*(sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 5)Not sure how to proceed here.
I would just live with it for now.
One approach would be to try conversion of the nongenerator element first, and if that fails (as evidenced by
x.radical_expression().parent() != SR
) try again for the generator
I don't like it because it makes things depend again on the choice of generator...
comment:76 followup: 79 Changed 8 years ago by
Replying to gagern:
sage: c = AA.polynomial_root(b.minpoly(), RIF(120,121)) sage: nf, val, nf2alg = c.as_number_field_element() sage: val.polynomial()(nf2alg(nf.gen()).radical_expression()) 1/8*((sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 13)*(sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 1) + 52)*(sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 1) + 10So in a certain sense,
as_number_field_element
makes it easier to find a symbolic expression for a given algebraic number
I don't like it because it makes things depend again on the choice of generator...
comment:77 followups: 80 88 Changed 8 years ago by
General comment: the approach of using Maxima's solve()
has its limitations. I think we should just accept that instead of implementing arbitrary workarounds. The right way of implementing radical_expression()
would involve Galois theory anyway, so perhaps we can rid of solve()
completely in the future (it might be feasible to implement that in Sage using PARI).
comment:78 Changed 8 years ago by
Replying to jdemeyer:
Replying to gagern:
However, it fails in cases where we are unable to find a radical expression for the element even though we would have been able to find one for the generator.
I would just live with it for now.
That introduces regressions: stuff that used to convert to SR in the past will fail to do so once this gets merged. I'd prefer to avoid such breaks in backward compatibility, even if it means less elegant behavior.
I don't like it because it makes things depend again on the choice of generator...
That is true, but I can think of no way to maintain backwards compatibility and avoid that dependence.
comment:79 Changed 8 years ago by
Replying to jdemeyer:
So in a certain sense,
as_number_field_element
makes it easier to find a symbolic expression for a given algebraic numberI don't like it because it makes things depend again on the choice of generator...
I could make via_nf
default to false. But practically speaking, when I try to convert stuff to radical expressions, I care mostly about obtaining a radical expression, and only secondly about that expression not depending on too much other stuff (like the exact descriptor tree, the result of do_polred
, and whatever). So returning a value which only depends on the minimal polynomial is nice when that value is radical, but if that fails, I really think I'd want to try harder instead of giving up early.
comment:80 Changed 8 years ago by
Replying to jdemeyer:
The right way of implementing
radical_expression()
would involve Galois theory anyway, so perhaps we can rid ofsolve()
completely in the future (it might be feasible to implement that in Sage using PARI).
OK, I can understand that. At a glance I didn't find a readytouse function in the PARI/GP docs, but it's pretty late in the day and I haven't worked directly with PARI before. If you have some pointers, please share them.
Feel free to give a5983f7 a positive review and ignore the commits about via_nf
if you are not comfortable with those.
comment:81 Changed 8 years ago by
In any case, the Galois stuff is surely not for this ticket. It's not a readytouse function, but the functions starting with galois
should be able to do this.
comment:82 followup: 83 Changed 8 years ago by
Replying to gagern:
sage: K.<a> = NumberField(QQ['x']([6, 65, 163, 185, 81, 15, 1]), embedding=4.9) sage: b = a + a^3 sage: SR(b) 120.55238677055798? sage: b.polynomial()(SR(a)) 1/8*((sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 5)^2 + 4)*(sqrt(4*(1/9*sqrt(109)*sqrt(3) + 2)^(1/3)  4/3/(1/9*sqrt(109)*sqrt(3) + 2)^(1/3) + 17) + 5)
Can you please say where this example comes from? I am trying to understand if the behaviour above is typical or rare.
comment:83 Changed 8 years ago by
Replying to jdemeyer:
Can you please say where this example comes from?
I was looking for numbers with a minpoly of degree more than four which allow for radical expressions but where computing said expression might take some time. I intended to use this in a performance comparison. This particular one I found using
sage: R.<x,y>=QQ[] sage: (x^2  5*x + 2  y).resultant(y^3 + y  4, y) x^6 + 15*x^5  81*x^4 + 185*x^3  163*x^2 + 65*x  6 sage: _.univariate_polynomial().roots(QQbar, False) [0.1274914752251046?, 4.872508524774896?, 0.5703693585365878?  0.4035749775931049?*I, 0.5703693585365878? + 0.4035749775931049?*I, 4.429630641463412?  0.403574977593105?*I, 4.429630641463412? + 0.403574977593105?*I] sage: _[1].minpoly() x^6  15*x^5 + 81*x^4  185*x^3 + 163*x^2  65*x + 6 sage: K.<a> = NumberField(_, embedding=4.9)
I've essentially been toying with the original two polynomials until I got something real and with reasonable conversion to symbolic. There is no deeper meaning behind the actual values of the coefficients. The conversion to symbolic is possible because the polynomial in y
is cubic, so one can express y
using radicals, and once you know y
the polynomial in x
is quadratic so that, too, can be expressed using radicals. I was somewhat surprised that the symbolic expression could avoid complex numbers along the way, since usually solving cubic equations requires those.
I then did my performance test using SR(a + k)
for some integer k
. And at some point decided that I should try more complicated elements of that field as well, tried the a + a^3
and was really surprised by the result.
comment:84 followup: 85 Changed 8 years ago by
So, I would say that your example was quite artificial and so perhaps the regression isn't so bad...
At least that example could certainly work using Galois theory (the splitting field has degree 48 and the Galois group can easily be computed using PARI).
comment:85 followup: 86 Changed 8 years ago by
Replying to jdemeyer:
So, I would say that your example was quite artificial and so perhaps the regression isn't so bad...
But neither is the fallback really bad. I'd say keep that for now and aim for a proper solution to all of this using Galois theory (getting a book on that now). If you decide to drop that, please get review from someone else, since I don't feel comfortable sanctioning a deliverate breach of backwards compatibility just for the sake of elegance.
comment:86 followup: 87 Changed 8 years ago by
Replying to gagern:
But neither is the fallback really bad.
OK, here is a compromise: remove the via_nf
argument (just pretend that it's always True
), add fallback code only to qqbar.py
(i.e. undo df036339e25fcac24a3497b0cd74f4bf34d5816c) and clearly comment the fallback code as being a fallback in case that Maxima's solve
doesn't work.
comment:87 Changed 8 years ago by
Replying to jdemeyer:
OK, here is a compromise: remove the
via_nf
argument (just pretend that it's alwaysTrue
), add fallback code only toqqbar.py
(i.e. undo df036339e25fcac24a3497b0cd74f4bf34d5816c) and clearly comment the fallback code as being a fallback in case that Maxima'ssolve
doesn't work.
I'm not convinced. The regression is for the case where Maxima could solve the defining polynomial for the generator but not the minimal polynomial for the element. While it might be hoped that applying pol_reduce to the minimal polynomial of the element will lead to something Maxima can handle again, I don't have any guarantees for this. And even if it works, it will depend on the generator of some field used internally by qqbar, not the declared generator of the number field where we started. I consider that inferior. In addition to this, implementing via_nf=True
without the ability to pass via_nf=False
in the recursive call would make that code uglier as well.
So instead I'd drop the via_nf
argument, expect it's always false and only do the fallback to the generator for number field elements. Or in other words, keep df03633 but drop a4fa894. Which is why I suggested in comment:80 to review stuff up to a5983f7.
comment:88 Changed 8 years ago by
Replying to jdemeyer:
The right way of implementing
radical_expression()
would involve Galois theory anyway, so perhaps we can rid ofsolve()
completely in the future (it might be feasible to implement that in Sage using PARI).
Just filed #17516 for this. There we can discuss preliminary work in that direction, be sure things aren't forgotten, and even have a ticket number to mention in documentation and comments when explaining that we consider some code temporary until that got addressed.
comment:89 Changed 8 years ago by
Description:  modified (diff) 

Milestone:  sage6.4 → sage6.5 
comment:90 Changed 8 years ago by
What's the status here? We have a bunch of other tickets developing from this one here, but we shouldn't forget about this here. Could I convince you to keep the backwards compatible fallback with the generator conversion for number field elements? Do you have any doubts about the rest of the code? Should I push a forced update to my branch, dropping that via_nf
stuff and instead adding some comments about the fact that finding roots using maxima is preliminary until #17516 gets addressed? Anything else you need to give this your approval?
comment:92 Changed 8 years ago by
Commit:  09683145989c437b59e02c02409d1dac05ac379d → 8486d6c862053923139fcb796b7812d0b4d1451d 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
8486d6c  Indicate temporary nature of generatorbased conversion.

comment:93 Changed 8 years ago by
Status:  needs_work → needs_review 

comment:94 Changed 8 years ago by
Commit:  8486d6c862053923139fcb796b7812d0b4d1451d → cb09ec61cdcbf04ef63b8d90e894c1b0b05b46b8 

Branch pushed to git repo; I updated commit sha1. New commits:
cb09ec6  Fix formatting of doctest block.

comment:95 Changed 8 years ago by
Commit:  cb09ec61cdcbf04ef63b8d90e894c1b0b05b46b8 → 4ccb707ae41dd6b8e10a61f78734d2d955929925 

comment:96 Changed 8 years ago by
Commit:  4ccb707ae41dd6b8e10a61f78734d2d955929925 → 4626286463c734f931ecc7405285dc7bc1b58772 

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
890cf9b  Increase precision when converting to radical expression.

ee3823a  Avoid code duplication between qqbar and nfe.

52512cc  Simplify NumberFieldElement._symbolic_

229b1fb  Use refine_embedding to convert to AA/QQbar

981942b  Add an example in degree 10 with degree 2 subfield

3423450  Fall back to convertig generator to symbolic.

73df99f  Drop __symbolic member from NumberFieldElement.

da4aa6e  Indicate temporary nature of generatorbased conversion.

a5a9245  Fix formatting of doctest block.

4626286  Delegate computation of symbolic roots to the roots method of the polynomial.

comment:97 Changed 8 years ago by
comment:99 followup: 102 Changed 8 years ago by
Status:  needs_review → needs_work 

What is the point of
 Test :trac:`14895`::   sage: K.<sqrt2> = QuadraticField(2) + sage: K.<sqrt2> = QuadraticField(2) # :trac:`14895`
I really do not like the attribute symbolic. Why this result needs to be cached? You can possibly cache in the parent a symbolic version of the generator.
The fact that SR(a)
when a
is a number field element returns possibly a numerical approximation is a very bad regression. You switch from something exact to something approximative.
comment:100 Changed 8 years ago by
What is the point of looking for an approximation
k = ( K._n()*CC(K.gen()).log() / CC(two_pi_i) ).real().round() # n ln z / (2 pi i)
comment:101 followup: 105 Changed 8 years ago by
Instead of embedding.im_gens()[0]
you can use the clearer embedding.gen_image()
.
comment:102 followup: 103 Changed 8 years ago by
Authors:  Martin von Gagern → Martin von Gagern, Jeroen Demeyer 

Replying to vdelecroix:
What is the point of
 Test :trac:`14895`::   sage: K.<sqrt2> = QuadraticField(2) + sage: K.<sqrt2> = QuadraticField(2) # :trac:`14895`
That one is from 4626286 by Jeroen, but you have the patch reversed. I assume that :trac:`…`
work in plain text but not in doctest comments, so this made a lot of sense to me.
I really do not like the attribute symbolic. Why this result needs to be cached? You can possibly cache in the parent a symbolic version of the generator.
Could it be you are seeing the wrong patch direction here as well? We are dropping the __symbolic
member and its caching functionality, since we don't expect to need it except in rare cases as a temporary solution.
The fact that
SR(a)
whena
is a number field element returns possibly a numerical approximation is a very bad regression. You switch from something exact to something approximative.
Yes, you are definitely seeing the patch in the wrong direction. A good thing that you pasted the patch lines above, otherwise I would have ben thoroughly confused.
Replying to vdelecroix:
What is the point of looking for an approximation
k = ( K._n()*CC(K.gen()).log() / CC(two_pi_i) ).real().round() # n ln z / (2 pi i)
I must confess that I was a bit unhappy with that myself when I read it. But the code just changed place and location, it wasn't really changed. And I figure that if you ever have a cyclotomic field of such a great order that you are affected by rounding errors here, its dimension would be high enough that you'd not get any real work done with it in any case. So I decided not to complain or modify this, since it's not directly related to the issue at hand and I feard that discussing one more item might prevent stuff from getting accepted.
Are you sure you want this handled with this ticket here? If so I'll have to work out how to find the right k
using exact arithmetic. I guess the integers are all there somewhere, but I'll have to look closer. It's been a while.
Replying to vdelecroix:
Instead of
embedding.im_gens()[0]
you can use the clearerembedding.gen_image()
.
Thanks, that should be a quick and obvious improvement. Will push a commit to that effect once I know whether to address the approximation issue above as well.
comment:103 followup: 104 Changed 8 years ago by
Replying to gagern:
Yes, you are definitely seeing the patch in the wrong direction. A good thing that you pasted the patch lines above, otherwise I would have ben thoroughly confused.
Oups... sorry
Replying to vdelecroix:
What is the point of looking for an approximation
k = ( K._n()*CC(K.gen()).log() / CC(two_pi_i) ).real().round() # n ln z / (2 pi i)Are you sure you want this handled with this ticket here? If so I'll have to work out how to find the right
k
using exact arithmetic. I guess the integers are all there somewhere, but I'll have to look closer. It's been a while.
It should be easy, NumberField_cyclotomic
does have a method .zeta_order()
. But then, the exact root of unity depends on the embedding... and I do not see how to avoid going to QQbar
(or using in an ugly way interval approximations). It is really a pity that we use embedding into RLF/CLF
by default and not AA/QQbar
(see also #18103, #18104).
Vincent
comment:104 Changed 8 years ago by
Replying to vdelecroix:
It should be easy,
NumberField_cyclotomic
does have a method.zeta_order()
. But then, the exact root of unity depends on the embedding... and I do not see how to avoid going toQQbar
(or using in an ugly way interval approximations).It is really a pity that we use embedding into
RLF/CLF
by default and notAA/QQbar
(see also #18103, #18104).
Yes, using qqbar
for the generator would certainly make things better. How about we leave the approximation in place for now, and file a separate ticket to get rid of that once the generator comes from qqbar
?
comment:105 followup: 106 Changed 8 years ago by
Status:  needs_work → needs_review 

Replying to vdelecroix:
Instead of
embedding.im_gens()[0]
you can use the clearerembedding.gen_image()
.
That won't work: at that point (since the refine_embedding
line a bit above that), the object in question is a morphism.NumberFieldHomomorphism_im_gens
and not a number_field_morphisms.NumberFieldEmbedding
any more, so it doesn't have a gen_image
method. I have no idea whether that's how it should be, but I'm fairly certain that if this should change, some other ticket should take care of that.
So I'm back to asking for review, even though I changed nothing.
comment:106 Changed 8 years ago by
Reviewers:  Marc Mezzarobba, Jeroen Demeyer → Marc Mezzarobba, Jeroen Demeyer, Vincent Delecroix 

Status:  needs_review → positive_review 
Replying to gagern:
Replying to vdelecroix:
Instead of
embedding.im_gens()[0]
you can use the clearerembedding.gen_image()
.That won't work: at that point (since the
refine_embedding
line a bit above that), the object in question is amorphism.NumberFieldHomomorphism_im_gens
and not anumber_field_morphisms.NumberFieldEmbedding
any more, so it doesn't have agen_image
method. I have no idea whether that's how it should be, but I'm fairly certain that if this should change, some other ticket should take care of that.So I'm back to asking for review, even though I changed nothing.
That's good to me!
Vincent
comment:107 Changed 7 years ago by
Branch:  u/gagern/ticket/14239 → 4626286463c734f931ecc7405285dc7bc1b58772 

Resolution:  → fixed 
Status:  positive_review → closed 
I wrapped my code into two methods
radical_expression
for theAlgebraicNumber
andAlgebraicReal
classes.Only second degree polynomials supported so far. I guess this should cover the most useful use cases: third and fourth degree are certainly possible, but don't help very much with the readability of the result in most cases. Square roots, on the other hand, are everywhere, so being able to represent these is a huge win imho.
The code I wrote does rely little on the internal workings of algebraic numbers and their descriptions, mostly because I haven't dug into that code yet. I guess the check which solution of the quadratic equation to choose might benefit from a more direct comparison of separating intervals, but at the moment I see no urgent performance issue with most use cases of this function.