simplification of radicals

[Ralf Hemmecke]

Dear Wakdek,

your recent contribution of rsimp is not totally satisfactory to me,
since it applies only to expressions that start with an 'nthRoot
operator. It's a good service function, but I wanted something that also
applies to combinations of such expression. So I wrote the following
function to apply rsimp recursively.

ZZ ==> Integer
EXZ ==> Expression ZZ
recursiveRootSimplification(x: EXZ): EXZ ==
liu: Union(List EXZ, "failed") := isTimes x
liu case List EXZ =>
reduce(_*, [recursiveRootSimplification(z) for z in liu], 1)
liu := isPlus x
liu case List EXZ =>
reduce(_+, [recursiveRootSimplification(z) for z in liu], 0)
is?(x, 'nthRoot) =>
r: Kernel EXZ := retract(x)@Kernel(EXZ)
a: List EXZ := argument retract x
ra: EXZ := recursiveRootSimplification(a.1)
ex := if #a < 2 then sqrt(ra) else ra^(1/a.2)
u: Union(EXZ, "failed") := rsimp(ex)$RootSimplification
u case "failed" => ex
u :: EXZ
x

Do you think that it makes sense to include that somewhere (where?) in
FriCAS?

I do not care much about the name except that it should have no
abbreviation.

The specification of rsimp does not say much about validity of the
transformation, i.e. whether x and rsimp(x) are actually the same root
(over complex numbers). Or do we have a statement in FriCAS about which
of the n possible values of an nthRoot expression, the nthRoot
expression actually represents.

With recursive application that could lead to a completely different
root value. Maybe that must be either said in the documentation or some
numerical code must be added to ensure that not suddenly a different
branch is chosen.

Ralf

[Ralf Hemmecke]

Just some more observations...

That the following expression

r :=
(884*sqrt(5)-1975)*sqrt((-sqrt(-16808278856375992320000000*sqrt(5)-37584454108531654656000000)-2239742361600*sqrt(5)-5008250880000)/2)

I get for

s := recursiveRootSimplification(r)

the value shown after the = sign, but

(s=(884*sqrt(5)-1975)*sqrt(((-19599*sqrt(-3758419364587713331200000)-43896710544998400)*sqrt(5)-43825*sqrt(-3758419364587713331200000)-98156708997120000)/39198))@Boolean

returns false.

I do not complain about the "false", but would rather like to ask how I
can convince recursiveRootSimplification to apply this kind of
simplification that obviously the interpreter is applying when I enter
the actual expression that I get back from recursiveRootSimplification(r)?

There is another interesting thing about r and s.

Obviously, FriCAS tries to make the denominator rational.
While developing recursiveRootSimplification I kept the value of r
without recreating the kernels and later hat problems to compute
1/(r+1). That did not finish. Unfortunately, I cannot reproduce it
anymore, but what actually happens to expressions that have kernels that
where once in the kernel cache but are not anymore after the )compile
command cleared that cache?

Thank you
Ralf

[Waldek Hebisch]

Concerning specification: 'rsimp' is working with _fields_, not
numbers. More precisely, 'rsimp' works with generators and
"field descriptors". "Field descriptor" tells you how to
build a field starting from base field (that is field of rational
numbers or field or rational functions). 'rsimp' works with
algebraic extentions of base field. Such extention is built
adding successive generators and descriptor tells you minimal
polynomial of new generator in terms of previously added
generators. 'rsimp' is supposed to produce field that is
izomorphic to input field, but has lower nesting depth.

Taking about field descriptors may be intimidating for users
and also we need an easy way to specify field descriptor.
Those two problems are solved by using expressions as field
descriptors. More presicly, 'nthRoot' specifies apropriate
field extention and simultaneously serves as generator of
this extention. There is a catch here: not all expressions
actually define fields. To define a field roots appearing in
the expression must be independent. By extention, roots
created by 'rsimp' should be independent.

Concerning exact specification, 'rsimp' tries to find
izomorphic field with description of lower nesting depth.
AFAIK there are open theoretical questions about what
exacly is possible. In particular, it seems that there
are fields which can not have description with lower nesting
depth, but which can be embedded in bigger field of lower
nesting depth. However, here detailed problem statement
matters a lot. AFAIK using my definitions problem is open.
'rsimp' is using approach which is usually called "Zippel
denesting". Again, characterizing cases when this approach
works is an open problem. I mean, one can write condtions
which must be satisfied at each step, but since 'rsimp'
transforms field descriptors in each step it is not clear
how to simply formulate needed condition in terms of input
data.

Concerning extentions: I plan to substantially extend 'rsimp'.
Some extentions look quite easy, but there is question of
specification and efficiency. Namely, "well specified"
"easy" extentions heavily use factorization which may
lead to quite long execution time. In some cases it is
possible to use cheaper methods, but that needs more code.
Having said that, as long as you do not require much
removing restriction on having single kernel looks
easy.

I consider recursive apprach like you used as completely
inappropriate. First, recursive approach tends to repeat
similar calculations, so it make efficiency problems
worse. Second, trying to handle parts of expression like
you do is likely to introduce dependent roots, which means
that we no longer have a field and leads to various
troubles.

Concerning branches: from algebraic point of view all branches
are equivalent (as long as kernels are independent). In other
words, choice of branches is extenal to 'rsimp', 'rsimp' simply
must be careful to avoid creating dependent roots. Of course,
users may use some "established" convention like principal
branch. In the future I will probably add some code to
make behaviour with such conventions better. For numbers
in principle it is possible to use numerical computations
to track branches. This may need rather large accuracy,
but other computations in 'rsimp' may be quite costly, so
probably numerical computations have acceptable cost. Still,
tracking needed accuracy requires appropriate code. Also,
from my point of view important advantage of 'rsimp' is that
it can deal with functions. But for functions principal
branch convention usually leads to troubles: one have to
spend large effort to get principal branch and frequently
this is wrong branch, so this effort is wasted.

--
Waldek Hebisch