#14239: symbolic radical expression for algebraic number
-------------------------------------+-------------------------------------
Reporter: gagern | Owner: davidloeffler
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: Martin von Gagern | Reviewers: Marc Mezzarobba,
Report Upstream: N/A | Jeroen Demeyer
Branch: | Work issues:
u/gagern/ticket/14239 | Commit:
Dependencies: | d2f72c655cc22f18c9029da5feff12f35eb0dbf8
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by gagern):
Replying to [comment:36 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
[http://git.sagemath.org/sage.git/tree/src/sage/rings/number_field/number_field_element.pyx?id=4e629501a164188d17dfce651d9854f3d91f25da#n2200
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
[http://git.sagemath.org/sage.git/tree/src/sage/rings/number_field/number_field_morphisms.pyx?id=4e629501a164188d17dfce651d9854f3d91f25da#n494
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,
[http://git.sagemath.org/sage.git/tree/src/sage/rings/number_field/number_field_morphisms.pyx?id=4e629501a164188d17dfce651d9854f3d91f25da#n64
it's a LazyAlgebraic] and as such
[http://git.sagemath.org/sage.git/tree/src/sage/rings/real_lazy.pyx?id=4e629501a164188d17dfce651d9854f3d91f25da#n1626
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/14239#comment:37>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
