Mitch harris2009-11-16 10:19:04

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 documentation 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

Israel2009-11-16 10:19:15

|>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 harris2009-11-16 10:19:33

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 murphy2009-11-16 10:19:39

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 harris2009-11-17 02:41:41

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 murphy2009-11-17 02:42:16

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 harris2009-11-18 04:31:46

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 harris2009-11-19 08:54:15

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

## Leave a Reply

You must be logged in to post a comment.