Opened 8 years ago

Closed 6 years ago

#14239 closed enhancement (fixed)

symbolic radical expression for algebraic number

Reported by: gagern Owned by: davidloeffler
Priority: major Milestone: sage-6.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:

Status badges

Description (last modified by jdemeyer)

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*b-4*a*c))/(2*a)
    if x == AA(y):
        return y
    y = (-b-sqrt(b*b-4*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 spin-off from my question on Ask Sage.

Follow-up tickets: #17516, #17517

Attachments (1)

trac_14239_algebraic_to_radicals.patch (2.4 KB) - added by gagern 8 years ago.

Download all attachments as: .zip

Change History (108)

Changed 8 years ago by gagern

comment:1 Changed 8 years ago by gagern

  • Status changed from new to needs_review

I wrapped my code into two methods radical_expression for the AlgebraicNumber and AlgebraicReal 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.

comment:2 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 follow-up: Changed 7 years ago by mmezzarobba

  • Reviewers set to Marc Mezzarobba
  • Status changed from needs_review to 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]

Last edited 7 years ago by mmezzarobba (previous) (diff)

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 in reply to: ↑ 3 ; follow-up: Changed 7 years ago by gagern

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 in reply to: ↑ 5 Changed 7 years ago by mmezzarobba

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 7 years ago by gagern

  • Branch set to u/gagern/ticket/14239
  • Created changed from 03/06/13 21:43:41 to 03/06/13 21:43:41
  • Modified changed from 01/31/14 07:50:11 to 01/31/14 07:50:11

comment:8 Changed 7 years ago by gagern

  • Commit set to 1ddc68cbd8cd536b3775a6c1bcba0e68511e7775
  • Status changed from needs_work to needs_review

New commits:

1ddc68cImplement method radical_expression for QQbar and AA elements.

comment:9 Changed 7 years ago by git

  • Commit changed from 1ddc68cbd8cd536b3775a6c1bcba0e68511e7775 to 30f71099332d11f775dda3f78ae0f33eef1a5623

Branch pushed to git repo; I updated commit sha1. New commits:

30f7109Check radical expression using QQbar even for AA elements.

comment:10 Changed 7 years ago by git

  • Commit changed from 30f71099332d11f775dda3f78ae0f33eef1a5623 to 039f4bf3bff139ce2630fe2fb8fd8f542096a498

Branch pushed to git repo; I updated commit sha1. New commits:

039f4bfFix radical expression for rational numbers.

comment:11 Changed 7 years ago by gagern

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 follow-up: Changed 7 years ago by nbruin

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^2-443,y^2-3,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 well-understood 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.?e-16*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.

Last edited 7 years ago by nbruin (previous) (diff)

comment:13 in reply to: ↑ 12 ; follow-up: Changed 7 years ago by gagern

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 read-only 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 its exactify method to take the additional information into account.
  • Are there cases where a symbolic minpoly would take significantly more time than the corresponding recursive exactify? If so, can we somehow detect these cases before we start the symbolic minpoly 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 some ANDescr 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 for ANDescr.

Does this approach make sense?

comment:14 in reply to: ↑ 13 Changed 7 years ago by gagern

Replying to gagern:

Makes me wonder whether the exactification should be somehow based on the minimal polynomial of the symbolic expression.

Created spinn-off ticket:16222 for this.

For this one here, I have another solution in mind which I'll push shortly.

comment:15 Changed 7 years ago by git

  • Commit changed from 039f4bf3bff139ce2630fe2fb8fd8f542096a498 to a65fa2b7be9560837ffb80ebcc6779a8d47bad42

Branch pushed to git repo; I updated commit sha1. New commits:

b0cc0b1Test parent of returned radical expression.
70f8311Merge tag '6.2.rc0' into ticket/14239
a65fa2bDetect exact conversion without comparing algebraic numbers.

comment:16 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:17 Changed 7 years ago by gagern

  • Authors set to Marc Mezzarobba, Martin von Gagern

comment:18 Changed 7 years ago by gagern

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 7 years ago by git

  • Commit changed from a65fa2b7be9560837ffb80ebcc6779a8d47bad42 to 16269faa29708fad205889d3063008772c036df5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

16269faTrac #14239: Implement method radical_expression for QQbar and AA elements.

comment:20 Changed 7 years ago by gagern

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:

  1. Some number where to_poly_solve=False won't find the solution but to_poly_solve=True will yield an exact solution.
  2. Some number where solve will not find all roots, or only some of these are exact.
  3. 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 7 years ago by git

  • Commit changed from 16269faa29708fad205889d3063008772c036df5 to e416116556a29c0b9304a5b7d5026f67b0e6ce3f

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

e416116Trac #14239: Implement method radical_expression for QQbar and AA elements.

comment:22 Changed 7 years ago by gagern

  • Authors changed from Marc Mezzarobba, Martin von Gagern to Martin von Gagern

comment:23 Changed 7 years ago by gagern

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 two-tuple by a one-tuple 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 7 years ago by git

  • Commit changed from e416116556a29c0b9304a5b7d5026f67b0e6ce3f to 006fa24b1199b44a2963ee0c14896f5e4d9003b0

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

006fa24Trac #14239: Implement method radical_expression for QQbar and AA elements.

comment:25 follow-up: Changed 7 years ago by vbraun

IMHO #16651 should be fixed instead of adding workarounds for #16651 elsewhere.

comment:26 in reply to: ↑ 25 Changed 7 years ago by gagern

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.

  1. 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 in NumberFieldElement 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.
  1. 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.
  1. 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 of to_poly_solve=True I consider both likely.
  1. 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 7 years ago by vbraun

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 floating-point approximate solution.

comment:28 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 7 years ago by git

  • Commit changed from 006fa24b1199b44a2963ee0c14896f5e4d9003b0 to d2f72c655cc22f18c9029da5feff12f35eb0dbf8

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d2f72c6Trac #14239: Implement method radical_expression for QQbar and AA elements.

comment:30 Changed 7 years ago by gagern

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 follow-up: Changed 6 years ago by jdemeyer

  • Status changed from needs_review to needs_work

I dislike

# Adapted from NumberFieldElement._symbolic_()

If two implementations do the same thing, there should be a common function...

comment:32 in reply to: ↑ 31 ; follow-up: Changed 6 years ago by gagern

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 in reply to: ↑ 32 Changed 6 years ago by jdemeyer

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 6 years ago by jdemeyer

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 6 years ago by jdemeyer

  • Reviewers changed from Marc Mezzarobba to Marc Mezzarobba, Jeroen Demeyer

comment:36 follow-up: Changed 6 years ago by jdemeyer

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 in reply to: ↑ 36 ; follow-up: Changed 6 years ago by gagern

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

  1. NumberFieldElement only converts the field generator to symbolic, everything else is accomplished by plugging that into a polynomial.
  2. The image of the generator comes from the embedding, and as such will be either from an exact field or from a lazy field.
  3. If it comes from an exact field, it is likely already from QQbar or AA 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 of NumberFieldElement and an analogous function for QQbar?

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 non-generator 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 follow-up: Changed 6 years ago by 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 from AA/QQbar.

Last edited 6 years ago by jdemeyer (previous) (diff)

comment:39 in reply to: ↑ 37 ; follow-up: Changed 6 years ago by jdemeyer

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 in reply to: ↑ 39 ; follow-up: Changed 6 years ago by gagern

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 in reply to: ↑ 38 ; follow-ups: Changed 6 years ago by gagern

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 from AA/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 non-cyaclotomic 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 in reply to: ↑ 41 Changed 6 years ago by jdemeyer

Replying to gagern:

For NumberFieldElement the computation is only performed for the generator, and only for non-cyclotomic 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.

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 non-broken wheel.

comment:43 in reply to: ↑ 40 Changed 6 years ago by jdemeyer

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 in reply to: ↑ 41 Changed 6 years ago by jdemeyer

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 6 years ago by jdemeyer

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 follow-up: Changed 6 years ago by gagern

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 6 years ago by git

  • Commit changed from d2f72c655cc22f18c9029da5feff12f35eb0dbf8 to 8ff313d2ea936471a4dda3989f9da440e8afe6b2

Branch pushed to git repo; I updated commit sha1. New commits:

a12a118Increase precision when converting to radical expression.
43d19daAvoid code duplication between qqbar and nfe.
8ff313dMerge tag '6.5.beta2' into ticket/14239

comment:48 Changed 6 years ago by gagern

  • Status changed from needs_work to needs_review

a12a118 does the interval-only 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 in reply to: ↑ 46 Changed 6 years ago by jdemeyer

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 floating-point 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 6 years ago by jdemeyer

I think you're still leaving way too much code in NumberFieldElement._symbolic_, for example the special case for cyclotomics...

comment:51 follow-up: Changed 6 years ago by jdemeyer

I really insist that you put all the code to do this in one place.

comment:52 Changed 6 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:53 in reply to: ↑ 51 Changed 6 years ago by gagern

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. Special-casing 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 follow-up ticket for AlgebraicNumber_base.symbolic_expression(), where the best approach to implement that might still be subject to discussion.

comment:54 Changed 6 years ago by jdemeyer

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 6 years ago by jdemeyer

  • Branch changed from u/gagern/ticket/14239 to u/jdemeyer/ticket/14239
  • Modified changed from 12/13/14 11:17:30 to 12/13/14 11:17:30

comment:56 Changed 6 years ago by jdemeyer

  • Commit changed from 8ff313d2ea936471a4dda3989f9da440e8afe6b2 to 06da2a3a251be8498e3ab3d1718e37d287a0e1c6

I was thinking along the lines of this commit here...


New commits:

06da2a3Simplify NumberFieldElement._symbolic_

comment:57 Changed 6 years ago by git

  • Commit changed from 06da2a3a251be8498e3ab3d1718e37d287a0e1c6 to 01b7e9e4aaa15a34d1d19788c36f47df1741bfe6

Branch pushed to git repo; I updated commit sha1. New commits:

01b7e9eUse refine_embedding to convert to AA/QQbar

comment:58 Changed 6 years ago by jdemeyer

  • Dependencies set to #17495

comment:59 follow-ups: Changed 6 years ago by gagern

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 in reply to: ↑ 59 Changed 6 years ago by jdemeyer

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 in reply to: ↑ 59 ; follow-up: Changed 6 years ago by jdemeyer

Replying to gagern:

And what is your rationale for moving the application of self.polynomial() to QQbar instead of SR?

  1. Plugging symbolic expressions into polynomials tend to give more complicated expressions. So the conversion to symbolic should be done as very last thing.
  2. 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.
  3. My code works in cases where the generator of the field doesn't have a radical expression, but the element does.
Last edited 6 years ago by jdemeyer (previous) (diff)

comment:62 Changed 6 years ago by jdemeyer

  • Dependencies changed from #17495 to #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 6 years ago by git

  • Commit changed from 01b7e9e4aaa15a34d1d19788c36f47df1741bfe6 to 24b00c640ccc096afa24da92e29cf2c1372628e2

Branch pushed to git repo; I updated commit sha1. New commits:

24b00c6Add an example in degree 10 with degree 2 subfield

comment:64 follow-up: Changed 6 years ago by gagern

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 in reply to: ↑ 64 Changed 6 years ago by jdemeyer

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 6 years ago by gagern

OK, so far I haven't been able to demonstrate a significant performance impact due to the removal of generator formula caching. So with #16964 and #17495 merged, and test cases added as requested, I think this should be ready. Will you add those test cases?

comment:67 in reply to: ↑ 61 ; follow-ups: Changed 6 years ago by gagern

Replying to jdemeyer:

  1. 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 non-generator 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 6 years ago by gagern

  • Branch changed from u/jdemeyer/ticket/14239 to u/gagern/ticket/14239
  • Modified changed from 12/15/14 13:55:40 to 12/15/14 13:55:40

comment:69 Changed 6 years ago by gagern

  • Commit changed from 24b00c640ccc096afa24da92e29cf2c1372628e2 to 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:

f30d693Only consider real embeddings if old embedding is into real lazy field.
cbe823aWhen determining embeddings, leave coefficients rational.
e689bc4Merge branch 'ticket/17495' into ticket/14239
2c4ac1bFaster qqbar comparison for case with equal minpoly.
bfa2338Merge branch 'ticket/16964' into ticket/14239
df03633Fall back to convertig generator to symbolic.

comment:70 Changed 6 years ago by git

  • Commit changed from df036339e25fcac24a3497b0cd74f4bf34d5816c to a5983f73b2acdbdd197f25d07c1fcf14bf1109e5

Branch pushed to git repo; I updated commit sha1. New commits:

a5983f7Drop __symbolic member from NumberFieldElement.

comment:71 follow-up: Changed 6 years ago by gagern

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 6 years ago by git

  • Commit changed from a5983f73b2acdbdd197f25d07c1fcf14bf1109e5 to a4fa89444e8f8d8da082c4b91849cade8aca5f79

Branch pushed to git repo; I updated commit sha1. New commits:

a4fa894Convert qqbar to radicals via number field.

comment:73 Changed 6 years ago by git

  • Commit changed from a4fa89444e8f8d8da082c4b91849cade8aca5f79 to 09683145989c437b59e02c02409d1dac05ac379d

Branch pushed to git repo; I updated commit sha1. New commits:

0968314Extend doctest for via_nf distinction.

comment:74 Changed 6 years ago by gagern

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 in reply to: ↑ 67 ; follow-up: Changed 6 years ago by 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. 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 non-generator 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 in reply to: ↑ 71 ; follow-up: Changed 6 years ago by jdemeyer

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) + 10

So 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 follow-ups: Changed 6 years ago by jdemeyer

General comment: the approach of using Maxima's solve() has its limitations. I think we should just accept that instead of implementing arbitrary work-arounds. 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 in reply to: ↑ 75 Changed 6 years ago by gagern

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 in reply to: ↑ 76 Changed 6 years ago by gagern

Replying to jdemeyer:

So 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...

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 in reply to: ↑ 77 Changed 6 years ago by gagern

Replying to jdemeyer:

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).

OK, I can understand that. At a glance I didn't find a ready-to-use 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 6 years ago by jdemeyer

In any case, the Galois stuff is surely not for this ticket. It's not a ready-to-use function, but the functions starting with galois should be able to do this.

comment:82 in reply to: ↑ 67 ; follow-up: Changed 6 years ago by jdemeyer

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 in reply to: ↑ 82 Changed 6 years ago by gagern

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 follow-up: Changed 6 years ago by jdemeyer

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 in reply to: ↑ 84 ; follow-up: Changed 6 years ago by gagern

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 in reply to: ↑ 85 ; follow-up: Changed 6 years ago by jdemeyer

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 in reply to: ↑ 86 Changed 6 years ago by gagern

Replying to jdemeyer:

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.

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 in reply to: ↑ 77 Changed 6 years ago by gagern

Replying to jdemeyer:

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).

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 6 years ago by jdemeyer

  • Description modified (diff)
  • Milestone changed from sage-6.4 to sage-6.5

comment:90 Changed 6 years ago by gagern

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:91 Changed 6 years ago by jdemeyer

Sure, go ahead with the modifications.

comment:92 Changed 6 years ago by git

  • Commit changed from 09683145989c437b59e02c02409d1dac05ac379d to 8486d6c862053923139fcb796b7812d0b4d1451d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

8486d6cIndicate temporary nature of generator-based conversion.

comment:93 Changed 6 years ago by gagern

  • Status changed from needs_work to needs_review

comment:94 Changed 6 years ago by git

  • Commit changed from 8486d6c862053923139fcb796b7812d0b4d1451d to cb09ec61cdcbf04ef63b8d90e894c1b0b05b46b8

Branch pushed to git repo; I updated commit sha1. New commits:

cb09ec6Fix formatting of doctest block.

comment:95 Changed 6 years ago by git

  • Commit changed from cb09ec61cdcbf04ef63b8d90e894c1b0b05b46b8 to 4ccb707ae41dd6b8e10a61f78734d2d955929925

Branch pushed to git repo; I updated commit sha1. New commits:

472c754Implement symbolic (radical) roots of polynomials.
989674dMerge branch ticket/17517 into ticket/14239.
4ccb707Delegate computation of symbolic roots to the roots method of the polynomial.

comment:96 Changed 6 years ago by git

  • Commit changed from 4ccb707ae41dd6b8e10a61f78734d2d955929925 to 4626286463c734f931ecc7405285dc7bc1b58772

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

890cf9bIncrease precision when converting to radical expression.
ee3823aAvoid code duplication between qqbar and nfe.
52512ccSimplify NumberFieldElement._symbolic_
229b1fbUse refine_embedding to convert to AA/QQbar
981942bAdd an example in degree 10 with degree 2 subfield
3423450Fall back to convertig generator to symbolic.
73df99fDrop __symbolic member from NumberFieldElement.
da4aa6eIndicate temporary nature of generator-based conversion.
a5a9245Fix formatting of doctest block.
4626286Delegate computation of symbolic roots to the roots method of the polynomial.

comment:97 Changed 6 years ago by gagern

Rebased since we had a conflict with e216b6f from #16908.

Am I right that we are just waiting for Jeroen or someone else to give this a positive review? Or is there still something missing which I should address in order to let this proceed?

comment:98 Changed 6 years ago by rws

Passes make ptestlong. Can't comment on the code, sorry.

comment:99 follow-up: Changed 6 years ago by vdelecroix

  • Status changed from needs_review to 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 6 years ago by 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)

comment:101 follow-up: Changed 6 years ago by vdelecroix

Instead of embedding.im_gens()[0] you can use the clearer embedding.gen_image().

comment:102 in reply to: ↑ 99 ; follow-up: Changed 6 years ago by gagern

  • Authors changed from Martin von Gagern to 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) 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.

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 clearer embedding.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 in reply to: ↑ 102 ; follow-up: Changed 6 years ago by vdelecroix

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 in reply to: ↑ 103 Changed 6 years ago by gagern

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 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).

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 in reply to: ↑ 101 ; follow-up: Changed 6 years ago by gagern

  • Status changed from needs_work to needs_review

Replying to vdelecroix:

Instead of embedding.im_gens()[0] you can use the clearer embedding.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 in reply to: ↑ 105 Changed 6 years ago by vdelecroix

  • Reviewers changed from Marc Mezzarobba, Jeroen Demeyer to Marc Mezzarobba, Jeroen Demeyer, Vincent Delecroix
  • Status changed from needs_review to positive_review

Replying to gagern:

Replying to vdelecroix:

Instead of embedding.im_gens()[0] you can use the clearer embedding.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.

That's good to me!

Vincent

comment:107 Changed 6 years ago by vbraun

  • Branch changed from u/gagern/ticket/14239 to 4626286463c734f931ecc7405285dc7bc1b58772
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.