Roots of unity

[Richard B. Kreckel]

Hi,

On Sun, 20 Jan 2002, Hans Peter Würmli wrote:
> I have written a 
> 
> lst RootOf(const lst & l) returning a list of the three zeros plus the
> lead coefficient
> 
> program for degree 3 polynomials, where the input list contains the
> polynomial and the indeterminate. In the sample output of the main
> program you will see the effect of precision with Digits=yyy that
> "zero" is represented by some long digit sequence times E-xxx that you
> felt some time ago was a bug of GiNaC, but isn't.
> 
> I don't know how one can force GiNaC to simplify expressions. Say, I
> used the programm to find symbolically the three roots x1, x2, x3 and
> reassembled the polynomonial by expanding
> leadcoefficient*(x-x1)*(x-x2)*(x-x3). To take an example: 
> 
> p(x) = 1 + x + x^3
> 
> Reassembling p from the roots and expanding produces:
> 
> p(x) = 1/2+x+x^3+(-27/2+3/2*sqrt(93))^(-1)-1/18*sqrt(93)
> 
> which is correct, if one simplifies 1/2+(-27/2+3/2*sqrt(93))^(-1)-1/18*sqrt(93) to 1

This is already way cool, isn't it?  But, to "simplify" is not
well-defined.  Such computations should not be done automatically at the
level of the anonymous avaluator (i.e. classwhatever::eval()).

This does not mean that it doesn't fit into the library, per se.  In
Maple, you may have noticed that `simplify' gets the job done, but what
really is being called is the function `radsimp'.  We simply haven't
looked at this yet because we don't need it in our computations so I see
little hope that Cebix or me is going to do this.  If somebody else wants
to, patches that implement such a method/function would be welcome.

The general cases can AFAIK not be algorithmically handled.  However, if
you are only interested in square roots and the degree of nesting of
radicals is not larger than two, there is a wealth of literature.  The
book by James Davenport, Yvon Siret and Evelyne Tournier "Systems and
Algorithms for algebraic Computation" talks about this, IIRC (don't have
the copy here).  H. Cohen's "A Course in Computational Algebraic Number
Theory" is another must.  Two classic papers are R. Zippel's
"Simplification of expressions involving radicals", in J. Symb. Comput.
1:189-210, 1985 and "Decreasing the nesting depth of expressions involving
square roots" by J. Hopcroft, A. Borodina, R. Fagin and M. Tompa in J.
Symb. Comput. 1:169-188, 1985.

There might also be some problems of representation involved because not
all solutions of polynomials are expressible as radicals.  Just consider
the classic x^5-x+1==0.  One could still symbolically represent the roots
inside a new class called `root' and even do interesting things to them,
like root(x^5-x+1)^5 => root(x^5-x+1)-1.  But this is now getting quite
far...

Regards
    -richy.
-- 
Richard B. Kreckel
<Richard.Kreckel at Uni-Mainz.DE>
<http://wwwthep.physik.uni-mainz.de/~kreckel/>