mitch harris

OK, it's easy to see that this is unique. (aren't algebraic -integers-
such things with the extra restriction that the leading coeff is 1?)

However, I have trouble figuring out how to compute with this, that is:

1) given an algebraic number, say

sqrt(1+sqrt(17+cuberoot(19)))- cuberoot(5)

Oh. OK, that's not necessarily algebraic according to my definition.
So...uh... how about I change the set on you but keep the same question.
For -forms- involving arbitrary roots, etc, no vars, is there a unique
normal form? I simplemindedly can't see an obvious way to convert the
above form to a poly of which it is a root. (for some forms yes, but not
all (e.g. like the one above)).
Likewise is there a way (algorithm) to get a such a form from a polynomial?

and

2) I realize there exists a way to index (totally order) the roots, but
I wonder what is computationally "acceptable". That is, I can do it
numerically (Sturm sequence/binary search), but is there a better way?
more symbolic? an implicit who cares?

Mathematica, too. But MMA do***entation is not very expressive about its
methods.


--
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://tcs.inf.tu-dresden.de/~harris

israel

|>OK, it's easy to see that this is unique. (aren't algebraic -integers-
|>such things with the extra restriction that the leading coeff is 1?)
|>However, I have trouble figuring out how to compute with this, that is:
|>1) given an algebraic number, say
|> sqrt(1+sqrt(17+cuberoot(19)))- cuberoot(5)
|>Oh. OK, that's not necessarily algebraic according to my definition.
|>So...uh... how about I change the set on you but keep the same question.
|>For -forms- involving arbitrary roots, etc, no vars, is there a unique
|>normal form? I simplemindedly can't see an obvious way to convert the
|>above form to a poly of which it is a root. (for some forms yes, but not
|>all (e.g. like the one above)).
|>Likewise is there a way (algorithm) to get a such a form from a
polynomial?

Yes, there is. In Maple:

P:=sort(evala(Norm(convert((q-x),RootOf))));

36 34 33 31 30 29
P := x - 18 x + 60 x - 720 x + 3282 x + 9720 x

28 27 26 25
- 16146 x - 78820 x + 295956 x - 287820 x

24 23 22 21
- 1792506 x + 13743360 x + 40209912 x - 14096280 x

20 19 18
- 279700236 x + 387516960 x - 523775078 x

17 16 15
+ 730492920 x + 11686352778 x + 85080734460 x

14 13 12
+ 9488713392 x - 254456753220 x - 616299273531 x

11 10 9
+ 857922985800 x + 1211443482834 x + 277908076980 x

8 7 6
- 5266258028172 x + 3345011588160 x + 1484108332884 x

5 4 3
+ 4356940483080 x - 14804808163020 x + 15364752902640 x

2
- 7922401473600 x + 2087405575200 x - 225309308400

Of course, then you have to figure out which of the 36 roots of P this is,
which might not be so simple (requiring high-precision numerical
calculation).

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2

mitch harris

so to get the polynomial P(x) from the form q, there -seems- to be some
kind of elimination going on (take a reasonably high power of q,
subtract off a smaller power of q which removes the leading term with
respect to the radicals, continue with smaller and smaller powers).
But I don't see the actual details of the process. Is it obvious? Is
this just basic algebra?

And I don't see how to go the other direction, that is, get some root
based form from the polynomial.

OK, with just a rereading of that, it seems really naive. Slapping
myself in the forehead, that would be equivalent to solving an arbitrary
polynomial in radicals which is known to be undecidable. So finding a
polynomial, one of whose solutions is a given algebraic, is quite a bit
easier than finding the algebraic itself. Sounds like a one-way function
to me!!

--
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://tcs.inf.tu-dresden.de/~harris

timothy murphy

It's not undecidable -- it's impossible.


--
Timothy Murphy
e-mail: tim@birdsnest.maths.tcd.ie
tel: +353-86-233 6090
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland

mitch harris

Poor usage/memory on my part. so some of what I said is then
meaningless..

Then what is known here?:

1) Is it decidable whether or not a particular polynomial has solutions
in radicals? (compute the galois group of a poly, check for being
solvable; that is are those two procedures decidable) If so, what is the
complexity?

2) given a formula in +,-,*,/, and radicals, and its computed minimal
polynomial (for which the formula is a solution), are the other real
solutions expressible similarly (as formulas in +,-,+,/,radicals)?

--
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://tcs.inf.tu-dresden.de/~harris

timothy murphy

It is decidable.
There is an algorithm for determining the galois group of a polynomial
(ie of the splitting field of the polynomial).
IIRC, such an algorithm is given in van der Waerden, Modern Algebra.
(I'm not certain of that, as both my volumes have been stolen.
However, I am certain there is such an algorithm.)

Since the galois group is finite, any question about it is decidable --
eg to determine if it is simple one goes through all subsets,
and decides if each one is a normal subgroup.
[I'm not suggesting that is a sensible thing to do;
just that it is a possible procedure.]

I don't know the complexity of the algorithm,
but I would be slightly surprised if it were not polynomial time
in the degree of the polynomial.


Yes, the other roots (ie the conjugates of the given root)
are obtained by replacing each nth root by the other nth roots,
eg replacing a^{1/n} by wa^{1/n} where w is an nth root of 1.

--
Timothy Murphy
e-mail: tim@birdsnest.maths.tcd.ie
tel: +353-86-233 6090
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland

mitch harris

Of course, reading a book would help me here


!! Any? Integers are all finite.
But anyway I know what you mean.

from the web that sounds right: the following, though not exactly the
same problem (it doesn't necessarily compute the galois group, just
pieces of it) from mathscinet:

Landau, Susan(1-MIT); Miller, Gary Lee(1-MIT)
Solvability by radicals is in polynomial time.
J. Comput. System Sci. 30 (1985), no. 2, 179--208.
The authors give an algorithm to decide in polynomial time\break whether
a monic irreducible polynomial over the rationals is solvable by
radicals. The algorithm depends on the attempted construction of certain
intermediate primitive groups. Such groups, if solvable, have order at
most a polynomial of their degree. While the algorithm runs in
polynomial time, it is not necessarily short.


but is that really in the given syntax? "w" (=e^(2pi i/n) )
isn't really allowed here. none of e, i, or pi are definable (I also
left out the restriction that powers can only be rationals).


--
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://tcs.inf.tu-dresden.de/~harris

mitch harris

OK, maybe this is allowable symbolically. But my thoughts about it are
not clear enough really to say yes or no.

Maybe not perfectly. I was under the impression that, by definition,
algebraics were a subset of the reals. but looking around the web it
seems that sometimes it is specified as such but mostly not. And maaybe
now I realize I don't care (i.e. algebraics that are not reals are OK).

If any "spirituality" is involved, it is in my desire to have only
symbolic operations involved, no numerical ones (yes, I realize that is
problematic distinction, let's say no bit counting?).

I think my problem may have been better stated in other threads ("What
is an algebraic integer?" and "Computational algebraic integers").

--
Mitch Harris
Lehrstuhl fuer Automatentheorie, Fakultaet Informatik
Technische Universitaet Dresden, Deutschland
http://tcs.inf.tu-dresden.de/~harris