AlgebraicNumber to RealClosure

[Ralf Hemmecke]

I have given x: AlgebraicNumber and know already that the value is real.

1) Is there a function that given x and an eps:Fraction(Integer) returns
two rational bounds l,u such that l<=x<=u and u-l<eps without going
via Float?

2) Is there an a function to convert x to
RealClosure(Fraction(Integer))?

I am actually interested only in (1), but while looking for it, I came
across RealClosure und found that quite interesting and maybe the
function approximate [1] is close to what I want.

[1]
https://fricas.github.io/api/RealClosedField.html#l5265616c436c6f7365644669656c64-617070726f78696d617465

Ralf

[Waldek Hebisch]

On Fri, Mar 07, 2025 at 01:39:53PM +0100, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> I have given x: AlgebraicNumber and know already that the value is real.

But how do you "know" this? We discussed several times the problem:
algebraically conjugates of an algebraic number are indistinguishable.

So your "know" may mean on of several things:

- you look for real conjugate
- you know that all conjugates are real
- there is exactly one real conjugate
- you have some rules that choose real conjugate

As an example consider

p6 := legendre(6)$PolynomialNumberTheoryFunctions
a := rootOf(p6)

Which of the real roots of p6 do you want (all conjugates are real)?

Similarly

b := sqrt(a)

Do you "know" that b is real (6 conjugates are imaginary, 6 are
real).

Or consider

c := rootOf(x^3 - x + 4)

Do you "know" that c is real (there is exactly one real root).

> 1) Is there a function that given x and an eps:Fraction(Integer) returns
> two rational bounds l,u such that l<=x<=u and u-l<eps without going
> via Float?
>
> 2) Is there an a function to convert x to
> RealClosure(Fraction(Integer))?
>
> I am actually interested only in (1), but while looking for it, I came
> across RealClosure und found that quite interesting and maybe the function
> approximate [1] is close to what I want.

Answer really depends on what you mean by "know". And the most
efficient way to get resulut is likely to use floating point
approximations. For example, if you are statisfied with "random"
real conjugate one way to go is to find minimal polynomial, then
use Sturm sequences or rule of signs and bisection to find bounds
on a real root. Using some numeric root finding method is likely
to be more efficient (but mostly symbolic approach may be easier
to program).

Currently it seems that we do not have a function to compute
minimal polynomial. For kernels this could be done based on
definingPolynomial, in general we would need some extra linear
algebra.

Actually, if you want easy coding simplest way could go via setting
a _system_ of equations for your number and using 'solve'.

All this in general will give you a list of values (possible
solutions) and you will need to use your "know" to decide
which one you want.

--
Waldek Hebisch

[Dima Pasechnik]

On Fri, Mar 7, 2025 at 7:30 AM Waldek Hebisch <de...@fricas.org> wrote:
>
> On Fri, Mar 07, 2025 at 01:39:53PM +0100, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> > I have given x: AlgebraicNumber and know already that the value is real.
>
> But how do you "know" this? We discussed several times the problem:
> algebraically conjugates of an algebraic number are indistinguishable.

One way to "know" a real algebraic number t without knowing the
interval with rational endpoints is to know its Thom encoding, that
is, the signs of the derivatives of the
minimal polynomial of t at t. This determines t uniquely. Thom
encoding is very convenient in algorithmic settings, as it can be
parametrised.

Dima

> --
> You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fricas-devel...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/fricas-devel/Z8r03PddOvZG8-iF%40fricas.org.

[Ralf Hemmecke]

Dear Waldek,

thanks for the reply and apologies for being imprecise.

Actually the algebraic numbers I talk about are rational expression of
nested radicals. In fact, I get all roots of a polynomial via
radicalRoots $ RadicalSolvePackage(ZZ). Degree is <= 4 (mostly 2).
These roots undergo some rational operation and multiplication with
other roots. But let's forget about the latter. I am actually talking
about all roots.

I know that I can find rational intervals for all real roots as tight as
I want them.
I basically need a matching of these intervals with the respective
radical expressions that I get from radicalRoots.

Additionally, given an algebraic number z, it would be great if FriCAS
had a way to find a p \in Z[x] such that p(z)=0 (minimal poly for z).
I looked at definingPolynomial and it is not so helpful, as I would have
to construct the minimal polynomial over QQ myself.

I guess, a function AlgebraicNumber -> RealClosure(QQ) is not reliable,
because AlgebraicNumber does not encode which of the roots of the
minimal polynomial is actually meant, i.e. I cannot even say whether
sqrt(2)@AN is positive. (Oh, yes, I know that AN does not export <.)

Ralf

[Waldek Hebisch]

On Fri, Mar 07, 2025 at 04:47:04PM +0100, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> Dear Waldek,
>
> thanks for the reply and apologies for being imprecise.
>
> Actually the algebraic numbers I talk about are rational expression of
> nested radicals. In fact, I get all roots of a polynomial via radicalRoots $
> RadicalSolvePackage(ZZ). Degree is <= 4 (mostly 2).
> These roots undergo some rational operation and multiplication with other
> roots. But let's forget about the latter. I am actually talking about all
> roots.
>
> I know that I can find rational intervals for all real roots as tight as I
> want them.
> I basically need a matching of these intervals with the respective radical
> expressions that I get from radicalRoots.

You should understand the in generic case there is a single multivalued
root: depending on branches of radicals you get all root of corresponding
polynomial. AFAIK the only _general_ method to track the roots is
evaluation via some local field. I do not think there is any regularity
in results from different local fiels, so practically one have to
choose one and stick to it. In a sense most typical local field
is that of complex numbers and practical methods of doing
evaluation are numeric.

AFAICS you are interested in _very_ special cases. It is quite
likely that you can do what you want by case analysis. For
example you can handle square roots of rationals by evaluating
exactly number under square root and looking at its sign.
In RootUtilities we handle bunch of cases of for equations of
degree 3 and 4. But already for degree 3 there is case of
3 real roots, each having complex expression.

> Additionally, given an algebraic number z, it would be great if FriCAS had a
> way to find a p \in Z[x] such that p(z)=0 (minimal poly for z).
> I looked at definingPolynomial and it is not so helpful, as I would have to
> construct the minimal polynomial over QQ myself.

Yes, it would be nice to have this, but it is currently unimplemented.

--
Waldek Hebisch

[Ralf Hemmecke]

Dear Waldek,

On 3/7/25 19:16, Waldek Hebisch wrote:
> AFAICS you are interested in _very_ special cases.

Yes, of course. But this discussion helped me to realize,
that I actually have a bit more freedom. I have to anyway investigate
all the conjugates where in the end I only care about real roots.

>> Additionally, given an algebraic number z, it would be great if
>> FriCAS had a way to find a p \in Z[x] such that p(z)=0 (minimal
>> poly for z).

> Yes, it would be nice to have this, but it is currently
> unimplemented.

See attachment. That is only a proof-of-concept approach.
I haven't thought very much about it, but I am mostly interested in
radical expressions (so, restriction to algebraic numbers.
Am I right with the assumption that the only operator in a kernel of
AlgebraicNumber is nthRoot?
Doesn't that say that the function (from AN)

minPoly: Kernel % -> SparseUnivariatePolynomial %

always return a polynomial of the form (x^n - t) where t is a rational
expression in "lower depth" kernels. In other words sorting the
variables as I did for the lex Groebner basis computation doesn't
actually waste time for the polynomials corresponding to the tower(q)
(where q is the algebraic number I want to find the minimal polynomial
for). So lexGroebner should be the optimal approach to find the minimal
polynomial.

If you think that would be a reasonable approach, I will prepare a patch
for

minimalPolynomial: % -> SparseUnivariatePolynomial Integer

in AlgebraicNumber.

Ralf

PS: As can be seen in the attachment, the approach via minimal
polynomial helped to "simplify" an unnecessarily complicated radical.

[Waldek Hebisch]

On Tue, Mar 11, 2025 at 11:22:23AM +0100, 'Ralf Hemmecke' via FriCAS - computer algebra system wrote:
> Dear Waldek,
>
> On 3/7/25 19:16, Waldek Hebisch wrote:
> > AFAICS you are interested in _very_ special cases.
>
> Yes, of course. But this discussion helped me to realize,
> that I actually have a bit more freedom. I have to anyway investigate
> all the conjugates where in the end I only care about real roots.
>
> > > Additionally, given an algebraic number z, it would be great if
> > > FriCAS had a way to find a p \in Z[x] such that p(z)=0 (minimal
> > > poly for z).
>
> > Yes, it would be nice to have this, but it is currently
> > unimplemented.
>
> See attachment. That is only a proof-of-concept approach.
> I haven't thought very much about it, but I am mostly interested in radical
> expressions (so, restriction to algebraic numbers.
> Am I right with the assumption that the only operator in a kernel of
> AlgebraicNumber is nthRoot?

No, there is also 'rootOf'.

> Doesn't that say that the function (from AN)
>
> minPoly: Kernel % -> SparseUnivariatePolynomial %
>
> always return a polynomial of the form (x^n - t) where t is a rational
> expression in "lower depth" kernels.

minPoly is in terms of lower oder kernels. For 'rootOf' minPoly
is not a binomial.

> In other words sorting the variables as
> I did for the lex Groebner basis computation doesn't actually waste time for
> the polynomials corresponding to the tower(q)
> (where q is the algebraic number I want to find the minimal polynomial for).
> So lexGroebner should be the optimal approach to find the minimal
> polynomial.
>
> If you think that would be a reasonable approach, I will prepare a patch for
>
> minimalPolynomial: % -> SparseUnivariatePolynomial Integer
>
> in AlgebraicNumber.

I tried your code replacing definition of 'q' by:

p4 := legendre(4)$PolynomialNumberTheoryFunctions
a := rootOf(p4)
q := sqrt(a - 1)

Clearly, minimal polynomial of 'q' is given by:

(14) -> pp := p4(z^2 + 1)

8 6 4 2
35 z + 140 z + 180 z + 80 z + 8
(14) -----------------------------------
8
Type: Fraction(Polynomial(Integer))

and it checks:

(15) -> eval(pp, z = q)

(15) 0
Type: Fraction(Polynomial(AlgebraicNumber))

The code fails in 'rootFactor' (which looks like a bug in
'rootFactor'). After commenting out line calling 'rootFactor'
we get

mp := last gb


8 6 4 2 11
(37) x + 4 x + 6 x + 4 x + --
8
Type: Polynomial(Fraction(Integer))
factor mp


8 6 4 2 11
(38) x + 4 x + 6 x + 4 x + --
8
Type: Factored(Polynomial(Fraction(Integer)))

which is not the minimal polynomial (plugging in 'q' does not
give 0). AFAICS this is because the code only handle radicals.

There is also question what to do with final 'factor'. If all
intermediate root are independent, and generic case we will
get irreducible polynomial. However, in non-generic case,
that is when 'q' generates proper subfield of the field
generated by roots (I think that such cases are extremally
rare, but possible) I am not sure what will come out from
Groebner basis computation.

--
Waldek Hebisch

[Ralf Hemmecke]

On 3/12/25 19:00, Waldek Hebisch wrote:

> No, there is also 'rootOf'.

Ah, OK, that makes sense. And as you noted my code only makes sense for
radical expressions. But that is currently exactly what I need.

> minPoly is in terms of lower oder kernels. For 'rootOf' minPoly is
> not a binomial.

Yes, clear, that is to consider for the general case, but radicals are
currently sufficient for me.

> The code fails in 'rootFactor' (which looks like a bug in
> 'rootFactor').

In fact, I was not sure whether I should actually use rootFactor, but it
was necessary for one case where I got from radicalRoots a tower with
kernels like sqrt(1+sqrt(7/5)), sqrt(7), sqrt(5). And for computing the
minimal polynomial application of rootFactor should not change the
minimal poly.

> There is also question what to do with final 'factor'.

Well, of course, I wouldn't include factor in the code, but for my
demonstrated input radical expression it basically showed that it can be
expressed by unnested roots, since the minpoly factors.
In fact, for me the game is also like rsimp. Some radicals that come out
of my computation cannot be simplified by rsimp, so I look for other
means to produce radicals with lower depth.

> If all intermediate root are independent, and generic case we will
> get irreducible polynomial. However, in non-generic case, that is
> when 'q' generates proper subfield of the field generated by roots
> (I think that such cases are extremally rare, but possible) I am not
> sure what will come out from Groebner basis computation.

Well... the only thing that would trouble me would be if there would be
no univariate polynomial in x over ZZ in the Groebner basis. But why
would that be? What might happen is that the polynomial is not minimal.
But then factorization would help and checking which factor evaluates to
0. (Oh, oh... plugging in the initial radical into a factor might not
simplify to 0 in our AN, although the expression represents 0. It would
need a function to produce a canonical representation for AN.)

Do you see that your argument can ever apply to radical numbers? If I
apply rootFactor, only primes survive under the radical.

Ralf