symbolic radical expression for algebraic number

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

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

Depends on #17495 Depends on #16964

Component: number fields

Author: Martin von Gagern, Jeroen Demeyer

Branch/Commit: 4626286

Reviewer: Marc Mezzarobba, Jeroen Demeyer, Vincent Delecroix

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

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

Attachment: trac_14239_algebraic_to_radicals.patch.gz

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:1

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.

[mezzarobba]

Reviewer: Marc Mezzarobba

[mezzarobba]

comment:3

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]

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:5

Replying to @mezzarobba:

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.

[mezzarobba]

comment:6

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

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

Branch: u/gagern/ticket/14239

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

Commit: 1ddc68c

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

New commits:

1ddc68c

Implement method radical_expression for QQbar and AA elements.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

30f7109

Check radical expression using QQbar even for AA elements.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1ddc68c to 30f7109

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 30f7109 to 039f4bf

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

039f4bf

Fix radical expression for rational numbers.

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:11

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.

[nbruin]

comment:12

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.

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:13

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?

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:14

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b0cc0b1	Test parent of returned radical expression.
70f8311	Merge tag '6.2.rc0' into ticket/14239
a65fa2b	Detect exact conversion without comparing algebraic numbers.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 039f4bf to a65fa2b

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

Author: Marc Mezzarobba, Martin von Gagern

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:18

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a65fa2b to 16269fa

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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.

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:20

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 16269fa to e416116

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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.

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

Changed author from Marc Mezzarobba, Martin von Gagern to Martin von Gagern

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:23

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e416116 to 006fa24

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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.

[vbraun]

comment:25

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

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:26

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.

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

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

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

[vbraun]

comment:27

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 006fa24 to d2f72c6

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:30

Rebased onto 6.4.beta2, and dropped the to_poly_solve=True code since #16651 comment:15 suggests that we can't expect to gain anything from this, and dropping it means we can avoid dealing with approximate solutions altogether.

[jdemeyer]

comment:31

I dislike

# Adapted from NumberFieldElement._symbolic_()

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

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:32

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?

[jdemeyer]

comment:33

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.

[jdemeyer]

comment:34

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.

[jdemeyer]

Changed reviewer from Marc Mezzarobba to Marc Mezzarobba, Jeroen Demeyer

[jdemeyer]

comment:36

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.

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:37

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.

[jdemeyer]

comment:38

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.

[jdemeyer]

comment:39

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!

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:40

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.

[8d15854a-f726-4f6b-88e7-82ec1970fbba]

comment:41

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.

[jdemeyer]

comment:42

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.

[jdemeyer]

comment:43

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.

[jdemeyer]

comment:44

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