Unsolubility by radicals for n>4 and computer algebra
lemm...@my-deja.com
general polynomials of degree > 4 don't have solutions by the method of
radicals. This brings up two questions in my mind:
(1) Any algebraic number can still be _represented_ by starting with
the rationals and performing a finite number of adds, multiplies,
divisions, nth-root extractions, etc., right? I've intuitively proved
to my self that this is necessarily the case, but I am not sure. In
other words, if someone asks you for the roots of some monster
polynomial like ax^4007 + ... + qx + z , you in principle could guess
them all (if there is no algorithm, my next question below...) and give
them to the person in a nice form like
(nthroot(4007, 345)/sqrt(2)) / nthroot(2001, 326) + ...
you know, something that looks like that, instead of having to give the
root by a power series or some other "infinitary" or
"nonexplicit" representation or something because it doesn't have such a
nice representation. Is this all right?
(2) You can't solve polynomials of degree > 4, but this doesn't
necessarily imply that the problem is algorithmically unsolvable, in the
sense of the halting problem or Hilbert's 10th and diophantine
equations, right? Well, is it algorithmically unsolvable, or could a
computer algebra system in principle find all the roots of the biggest,
ugliest polynomial you can give it, and moreover give them to you in the
kind of representation I tried to define above (but it is sort of
difficult to precisely articulate). I hope I'm being clear enough so
that you all understand what I'm trying to ask.
Thank you.
Sent via Deja.com
http://www.deja.com/
Roni Choudhury
> Okay, I am aware that Abel (and later Galois, I guess) showed that
> general polynomials of degree > 4 don't have solutions by the method of
> radicals. This brings up two questions in my mind:
>
> (1) Any algebraic number can still be _represented_ by starting with
> the rationals and performing a finite number of adds, multiplies,
> divisions, nth-root extractions, etc., right? I've intuitively proved to
> my self that this is necessarily the case, but I am not sure. In other
> words, if someone asks you for the roots of some monster polynomial like
> ax^4007 + ... + qx + z , you in principle could guess them all (if
> there is no algorithm, my next question below...) and give them to the
> person in a nice form like
>
> (nthroot(4007, 345)/sqrt(2)) / nthroot(2001, 326) + ...
>
> you know, something that looks like that, instead of having to give the
> root by a power series or some other "infinitary" or
> "nonexplicit" representation or something because it doesn't have such a
> nice representation. Is this all right?
>
Yeah I suppose so. But these would be trivial examples. For example,
here's one: solve
((x - sqrt(2))^3)((x-sqrt(5))^7)=0.
Here you can "guess" that the solutions are sqrt(2) and sqrt(5), but
there is no general method to give radical roots to such an equation.
> (2) You can't solve polynomials of degree > 4, but this doesn't
> necessarily imply that the problem is algorithmically unsolvable, in the
> sense of the halting problem or Hilbert's 10th and diophantine
> equations, right? Well, is it algorithmically unsolvable, or could a
> computer algebra system in principle find all the roots of the biggest,
> ugliest polynomial you can give it, and moreover give them to you in the
> kind of representation I tried to define above (but it is sort of
> difficult to precisely articulate). I hope I'm being clear enough so
> that you all understand what I'm trying to ask.
>
Again, since there are no general methods for getting radical solutions
to large enough degree polynomials, you certainly couldn't program such a
function on a computer. A Turing complete language is at most as
powerful as first order predicate logic will allow it to be, which means
that while a program couldn't give you the exact solutions, you could
program a function to give approximate decimal values that are
sufficiently close to the exact value. In fact, I believe this is
exactly what "fixed-point iteration" does (Newton's method, for example).
Hope that helps, and I hope I didn't make any blatantly wrong
statements...
roni
Geoff Bailey
> general polynomials of degree > 4 don't have solutions by the method of
> radicals. This brings up two questions in my mind:
>
> (1) Any algebraic number can still be _represented_ by starting with
> the rationals and performing a finite number of adds, multiplies,
> divisions, nth-root extractions, etc., right?
No, this is not the case. In fact, this is what Galois' results show
us -- that there is no solution in radicals to a polynomial unless its
Galois group is soluble. To take a specific example, the quintic
x^5 - x - 1 has Galois group S_5, which is not soluble. This means not
just that one cannot find a solution in radicals, but that it actually
has no solution in radicals. So the operations you describe do not
suffice to find its roots.
I believe that it is true that for quintics (and possibly sextics as
well) all roots can be expressed by also allowing the operation theta(a)
which returns the roots of x^5 - x - a. For higher degree polynomials
one has to use more complicated expressions again.
Cheers,
Geoff.
-----------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ft...@cs.usyd.edu.au | Gameplayer by vocation.
-----------------------------------------------------------------------------
David L. Johnson
>
> Okay, I am aware that Abel (and later Galois, I guess) showed that
> general polynomials of degree > 4 don't have solutions by the method of
> radicals. This brings up two questions in my mind:
>
> (1) Any algebraic number can still be _represented_ by starting with
> the rationals and performing a finite number of adds, multiplies,
> divisions, nth-root extractions, etc., right?
That is more or less the definition of an algebraic number.
... something that looks like that, instead of having to give the
> root by a power series or some other "infinitary" or
> "nonexplicit" representation or something because it doesn't have such a
> nice representation. Is this all right?
I think you have the idea.
>
> (2) You can't solve polynomials of degree > 4, but this doesn't
> necessarily imply that the problem is algorithmically unsolvable, in the
> sense of the halting problem or Hilbert's 10th and diophantine
> equations, right? Well, is it algorithmically unsolvable, or could a
> computer algebra system in principle find all the roots of the biggest,
> ugliest polynomial you can give it, and moreover give them to you in the
> kind of representation I tried to define above (but it is sort of
> difficult to precisely articulate).
If a computer could turn the information about the polynomial (coefficients
and degree) into expressions for the roots, then that would contradict
unsolvability, wouldn't it? A computer can't do what cannot be done. The
point of solvability, by some algorithm, would be precisely this. That does
not contradict that all roots are algebraic, but that there is no algorithm
(there cannot be an algorithm) to extract them from the polynomial.
--
David L. Johnson
__o | Become MicroSoft-free forever. Ask me how.
_`\(,_ |
(_)/ (_) |
lemm...@my-deja.com
Since my two questions have not generated any answers, and since I am
sure that at least one reader could give a quick answer of "yes," "no,"
or "it is unknown" if they understood the two questions, I'll ask my
questions again, but this time with a precise mathematical formulation.
[I will also cross-post to sci.math, since it might not be bad
netiquette after all.]
QUESTION 1: Let us begin by defining the term "nicely represented."
We shall say that an algebraic number z is "nicely represented" if and
only if there exists a finite set of rational numbers F={q_1,...,q_n}
such that z is the result of applying the following finite collection of
functions to the elements of F a finite number of times. (C denotes the
set of complex numbers. CxC is the cartesian product of C with itself.)
+:CxC --> C
(a,b) |-> a+b
-:CxC --> C
(a,b) |-> a-b
*:CxC --> C
(a,b) |-> a*b
%:Cx(C\{0}) --> C
(a,b) |-> a/b
^:CxC --> C
(a,b) |-> a^b
[Note: 0^0=1. This convention can't lead to contradiction, and in fact
is something you can _prove_ if you construct the numbers and define ^
from set theory.]
Example 1:
The following numbers are nicely represented:
(i) 3
(ii) 5^(7/3)
(iii) 7^(2^(1/65537)-1) / 3^(4/337)
These numbers are not nicely represented:
(iv) 1 + 1/2 + 1/4 + 1/8 + ...
This is algebraic, and a nice representation exists [namely: 2],
but it has not been nicely represented, since it violates two
conditions; +:CxC-->C has been applied infinitely many times, to the
set F={1,1/2,1/4,1/8,....}, which itself is not finite.]
(v) pi
Nicely represented applies only to algebraic numbers.
(vi) The 7th root of 7x^201 - 3x + 4 =0, if you order all the
roots a+bi lexicographically. (a+bi < c+di iff. a<c or a=c and b<d).
The 7th root is certainly algebraic, and has been unambiguously
specified, but it is not nicely represented, since english and
and an ordering scheme have been introduced to represent it.
My first question is: can every algebraic number be nicely represented?
Obviously, the proof can't give the representation explicitly for an
arbitrary algebraic z, because then you would have demonstrated the
solubility by radicals of any polyniomial. More precisely, if z is
algebraic and given
a_1*z^n + a_2*z^(n-1) + ... + a_n*z + a_{n+1} = 0
it has been proved that you can't write z in terms of the symbols
a_1,...,a_{n+1} by applying the above listed functions finitely many
times. (For then in a certain sense we didn't even really use the
assumption that z is algebraic: z could have been an inderterminate x
and we could have solved for x in terms of a_1,...,a_{n+1} and given a
solution to the general polynomial by means of radicals, which is
impossible by the work of Abel and Galois, et. al.) So I suppose the
proof that a nice representation exists would have to go along the lines
of, "suppose z is algebraic and we don't have a nice representation...."
QUESTION 2: It seems intuitively evident to me that given any
a_1*x^n + a_2*x^(n-1) + ... + a_n*x + a_{n+1} = 0
that numerical methods exist for approximating all of the n roots to as
many degrees of decimal accuracy as we please. (If these methods do not
exist, then that would be a tremendous shocker to me, and also answer
this question immediately for me.)
But I am interested in the exact solutions. With Question 1, I was
basically asking if you are always guaranteed that there is a nice way
to write exact solutions to polynomials, rather than something like my
example where you have to say "the 7th root when all the roots are
ordered lexicographically" or something like that. Now by Abel and
Galois, given a polynomial in one indeterminate over the rationals we
can't get exact roots by the method of radicals, but I don't see why
that implies that we can't get exact roots by more sophisticated
algorithmic methods. That is, given a polynomial in one indeterminate
over the rationals I want to know if there is, or can ever be, or why
there can't ever be, an algorithm for finding all the exact solutions. I
don't think the work on Hilbert's 10th problem applies to this, since
I'm not only looking for integer solutions with a large number of
indeterminates and integer coefficients (if that was the hypothesis of
Hilbert's 10th, I don't remember), but rather I am looking for all
solutions in one indeterminate with rational coefficients.
If they can be nicely represented, great. If not, perhaps there exists
some sort of "normal form" the algorithm could express the roots in that
in a way is a "nice representation" and allows them to be computed to
arbitrary accuracy quickly or something.
Anyways, thank you to anyone that actually just read all that, and extra
thanks in advance if you are knowledgable enough to know the answers to
some of these things and could reply.
Chip Eastham
lemma_one,
Sorry, I couldn't understand your "clarification" of this question, so
let me give a reply to this original post.
> Okay, I am aware that Abel (and later Galois, I guess) showed that
> general polynomials of degree > 4 don't have solutions by the method
of
> radicals. This brings up two questions in my mind:
>
> (1) Any algebraic number can still be _represented_ by starting with
> the rationals and performing a finite number of adds, multiplies,
> divisions, nth-root extractions, etc., right? I've intuitively proved
> to my self that this is necessarily the case, but I am not sure. In
> other words, if someone asks you for the roots of some monster
> polynomial like ax^4007 + ... + qx + z , you in principle could guess
> them all (if there is no algorithm, my next question below...) and
give
> them to the person in a nice form like
>
> (nthroot(4007, 345)/sqrt(2)) / nthroot(2001, 326) + ...
>
> you know, something that looks like that, instead of having to give
the
> root by a power series or some other "infinitary" or
> "nonexplicit" representation or something because it doesn't have
such a
> nice representation. Is this all right?
>
No, you cannot express all algebraic numbers this way, using the
ordinary operations of arithmetic plus whole number roots. That's the
essence of what Abel and Galois proved (Galois went further and gave a
characterization of equations for which one can express all roots in
this way).
If instead of the simple n'th root, you had a primitive operation that
gives real x > 0 such that x^n = x + a for input real a > 0, this would
allow you to express all algebraic numbers in terms of formulas (using
this new "operation").
> (2) You can't solve polynomials of degree > 4, but this doesn't
> necessarily imply that the problem is algorithmically unsolvable, in
the
> sense of the halting problem or Hilbert's 10th and diophantine
> equations, right? Well, is it algorithmically unsolvable, or could a
> computer algebra system in principle find all the roots of the
biggest,
> ugliest polynomial you can give it, and moreover give them to you in
the
> kind of representation I tried to define above (but it is sort of
> difficult to precisely articulate). I hope I'm being clear enough so
> that you all understand what I'm trying to ask.
>
>
See my comment above, on a different kind of "explict" formula that
would allow you to represent roots of a general polynomial.
Regards,
Chip
ha...@mailhost.tcs.tulane.edu
lemm...@my-deja.com wrote:
> In article <93dnmi$knc$1...@nnrp1.deja.com>,
> lemm...@my-deja.com wrote:
> > Okay, I am aware that Abel (and later Galois, I guess) showed that
> > general polynomials of degree > 4 don't have solutions by the method
> of
> > radicals. This brings up two questions in my mind:
> >
> > (1) Any algebraic number can still be _represented_ by
> > starting with
> > the rationals and performing a finite number of adds, multiplies,
> > divisions, nth-root extractions, etc., right?
No.
> > I've intuitively proved
> > to my self that this is necessarily the case, but I am not sure. In
> > other words, if someone asks you for the roots of some monster
> > polynomial like ax^4007 + ... + qx + z , you in principle could guess
> > them all (if there is no algorithm, my next question below...) and
> give
> > them to the person in a nice form like
> >
> > (nthroot(4007, 345)/sqrt(2)) / nthroot(2001, 326) + ...
> >
> > you know, something that looks like that, instead of having to give
> the
> > root by a power series or some other "infinitary" or
> > "nonexplicit" representation or something because it doesn't have such
> a
> > nice representation. Is this all right?
No.
> > (2) You can't solve polynomials of degree > 4,
You can't solve *some* polynomials of degree > 4 by *radicals*.
You can solve some polynomials of degree > 4 by radicals.
Gauss constuction of the regular 17-gon does exactly this
(solves a polynomial of degree 16 by square roots only).
You can solve polynomials of degree 5 and 6 by elliptic functions.
> QUESTION 1: Let us begin by defining the term "nicely represented."
> We shall say that an algebraic number z is "nicely represented" if and
> only if there exists a finite set of rational numbers F={q_1,...,q_n}
> such that z is the result of applying the following finite collection of
> functions to the elements of F a finite number of times. (C denotes the
> set of complex numbers. CxC is the cartesian product of C with itself.)
>
> +:CxC --> C
> (a,b) |-> a+b
>
> -:CxC --> C
> (a,b) |-> a-b
>
> *:CxC --> C
> (a,b) |-> a*b
>
> %:Cx(C\{0}) --> C
> (a,b) |-> a/b
>
> ^:CxC --> C
> (a,b) |-> a^b
Do you really want b to be complex?
I think that you do. But, then I think Galois theory won't apply.
I may not be understanding your question correctly.
I had similar or same idea: Maybe z can be expressed in terms of
radicals, but not as a function of the a's. Maybe different
polynomials of degree 5, say, would need different expressions
for its root z in terms of the a's. Or maybe there is an expression
in radicals for the root, but it doesn't use the coefficients of
the polynomial at all: it is just chance grouping of numbers within
the radicals.
However, Galois theory proves that this cannot occur. If a root
is "nicely represented" in any kind of way, then the group of
its equation is solvable (but not all polynomials have solvable
equations). In fact, now I am worrying about how exactly the
expression of the root in terms of the *coefficient* comes about.
I will have to look this up. Of course, I am not allowing complex
radicals for "nicely represented", but only radicals like a^(p/q)
where p and q are positive integers.
--
Bill Hale
Bob Silverman
> general polynomials of degree > 4 don't have solutions by the method
of
> radicals. This brings up two questions in my mind:
>
> (1) Any algebraic number can still be _represented_ by starting with
> the rationals and performing a finite number of adds, multiplies,
> divisions, nth-root extractions, etc., right?
Huh? You said above you KNOW that not all algebraic numbers
can be represented, then turn around and directly contradict yourself!
All algebraic numbers can NOT be thusly represented.
I've intuitively proved
> to my self that this is necessarily the case,
You are hallucinating.
but I am not sure. In
> other words, if someone asks you for the roots of some monster
> polynomial like ax^4007 + ... + qx + z , you in principle could guess
> them all (if there is no algorithm, my next question below...) and
give
> them to the person in a nice form like
>
> (nthroot(4007, 345)/sqrt(2)) / nthroot(2001, 326)
No you CAN'T. You clearly do not understand that general
polynomials of degree > 4 can NOT be solved, or you would not
be repeating this.
>
> (2) You can't solve polynomials of degree > 4, but this doesn't
> necessarily imply that the problem is algorithmically unsolvable,
"algorithmically unsolvable is gibberish".
Any polynomial can be solved in terms of theta functions, but
finding the exact theta series is complicated.
in the
> sense of the halting problem or Hilbert's 10th and diophantine
> equations, right? Well, is it algorithmically unsolvable,
What do you MEAN by this? Are you asking if there is an algorithm
which can find a representation of the zeros in terms of a finite
number of ordinary arithmetic operations plus root extraction?
You said in the very first sentence that you knew this was
IMPOSSIBLE.
Algorithms do exist that will find such representations WHEN THE
GALOIS GROUP IS SOLVABLE.
or could a
> computer algebra system in principle find all the roots of the
biggest,
> ugliest polynomial you can give it, and moreover give them to you in
the
> kind of representation I tried to define above (but it is sort of
> difficult to precisely articulate). I hope I'm being clear enough
You are spouting gibberish.
so
> that you all understand what I'm trying to ask.
I don't think that even you understand what you are trying to ask.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Christoph Koegl
> In article <93dnmi$knc$1...@nnrp1.deja.com>,
> lemm...@my-deja.com wrote:
> > Okay, I am aware that Abel (and later Galois, I guess) showed that
> > general polynomials of degree > 4 don't have solutions by the method
> of
> > radicals. This brings up two questions in my mind:
> >
> > (1) Any algebraic number can still be _represented_ by starting with
> > the rationals and performing a finite number of adds, multiplies,
> > divisions, nth-root extractions, etc., right?
>
> Huh? You said above you KNOW that not all algebraic numbers
> can be represented, then turn around and directly contradict yourself!
>
> All algebraic numbers can NOT be thusly represented.
>
> I've intuitively proved
> > to my self that this is necessarily the case,
>
> You are hallucinating.
> [more ranting by Bob removed]
>
>
> You are spouting gibberish.
>
> so
> > that you all understand what I'm trying to ask.
>
> I don't think that even you understand what you are trying to ask.
Bob, I do not think that your reply is very helpful. Unless
I am missing something entirely in this thread it is obvious
that your are unnecessarily rude. Especially as a respected
scientist (if you are *the* Bob Silverman) it is IMHO your
responsibility to try to help rather than to ridicule posters
in this forum. If you cannot bear with (seemingly) criminally
ignorant posts just delete them.
Lemma_one (what's your name, anyway?), please have a look
at the following literature:
L. Gaal, Classical Galois Theory (various publishers, 3rd ed.
with Chelsea Publ., 5th ed. with AMS (?)).
S. Landau/G. Miller, Solvability by Radicals is in Polynomial
Time, JCSS 30(2), 179-208 (1985).
A. Weber, Computing radical expressions for roots of unity,
SIGSAM bulletin 30, 117 (1996), 11-20.
F. Lehobey, Resolvent Computations by Resultants Without
Extraneous Powers. ISSAC 1997, 85-92.
S. Landau, Polynomial time algorithms for Galois groups,
EUROSAM 1984, 225-236 (in LNCS 174, Springer, 1984).
The reason why this has not been implemented (a student of
mine did a partial implementation) in popular CAS might be
that the perceived benefit from knowing exact solutions in
terms of radical expressions (applications, anyone?) does
not justify the necessary effort (which *is* enormous) to
efficiently implement the above algorithms. Our partial
implementation (done in MuPAD) is *very* inefficient. Pro-
gress is still being made in the field (cf. the last ISSACs).
I suppose an implementation in GAP, Magma, or even C++ is
necessary to achieve some degree of practicality here.
Cheers, Christoph
David C. Ullrich
>In article <93dnmi$knc$1...@nnrp1.deja.com>,
> lemm...@my-deja.com wrote:
>> Okay, I am aware that Abel (and later Galois, I guess) showed that
>> general polynomials of degree > 4 don't have solutions by the method
>of
>> radicals. This brings up two questions in my mind:
>>
>> (1) Any algebraic number can still be _represented_ by starting with
>> the rationals and performing a finite number of adds, multiplies,
>> divisions, nth-root extractions, etc., right?
No.
>> I've intuitively proved
>> to my self that this is necessarily the case, but I am not sure.
Well your proof is wrong. I'm sure.
You don't give any hint how your intuitive proof goes...
Whether the question is clear is not clear to me. Here's why:
If the question is "Is the problem of finding the roots of a
polynomial solvable in an abstract CS way?" the answer
is "The question doesn't quite make sense until you explain
a little more. To solve an equation is to find the roots.
But one cannot even _represent_ a typical real number
in a computer, much less 'find' it!"
If otoh you mean to ask whether a computer can find
a representation of the roots of an arbitrary polynomial
(with rational coefficients) in terms of roots, etc, that
question is clear. The answer is it's impossible, has
nothing to do with computational this or halting that -
it's impossible because in general there _is_ no such
representation for the roots! A computer cannot find
things that aren't there.
(Of course a program can find rational approximations
to the roots.)
>Since my two questions have not generated any answers, and since I am
>sure that at least one reader could give a quick answer of "yes," "no,"
>or "it is unknown" if they understood the two questions, I'll ask my
>questions again, but this time with a precise mathematical formulation.
>[I will also cross-post to sci.math, since it might not be bad
>netiquette after all.]
Cross-posting to a small number of groups can be a good thing,
_if_ the question is on-topic in all of them. It's better than
posting the same message separately in both groups for
various reasons (one being that readers in one group
can see that the question has been answered in the
other group.)
> QUESTION 1: Let us begin by defining the term "nicely represented."
>We shall say that an algebraic number z is "nicely represented" if and
>only if [...]
>
>My first question is: can every algebraic number be nicely represented?
No.
[...]
>
>
>QUESTION 2: It seems intuitively evident to me that given any
>
> a_1*x^n + a_2*x^(n-1) + ... + a_n*x + a_{n+1} = 0
>
>that numerical methods exist for approximating all of the n roots to as
>many degrees of decimal accuracy as we please.
Yes, that's easy. (With a wrinkle or two: One can give an algorithm
that takes a polynomial and an eps>0 as input and outputs n rationals
r_1,...r_n such that |r_j-z_j|<eps for j=1,...n, where the z_j are
the real roots. This doesn't mean that one can, for example,
determine whether a fifth-degree polynomial has 5 distinct
roots or some repeated roots. If the roots are all distinct then
we will discover that by taking eps small enough, but it seems
to me that it could happen that there was a repeated root
but we never know for certain it's a repeated root, instead of
just two roots that we haven't separated yet.
I could well be wrong about that.)
> (If these methods do not
>exist, then that would be a tremendous shocker to me, and also answer
>this question immediately for me.)
>
>But I am interested in the exact solutions. With Question 1, I was
>basically asking if you are always guaranteed that there is a nice way
>to write exact solutions to polynomials, rather than something like my
>example where you have to say "the 7th root when all the roots are
>ordered lexicographically" or something like that. Now by Abel and
>Galois, given a polynomial in one indeterminate over the rationals we
>can't get exact roots by the method of radicals, but I don't see why
>that implies that we can't get exact roots by more sophisticated
>algorithmic methods.
Before you can "get" an exact root you have to say what sort
of representation you're going to use for the root. You can
"get" an exact root in terms of _what_?
> That is, given a polynomial in one indeterminate
>over the rationals I want to know if there is, or can ever be, or why
>there can't ever be, an algorithm for finding all the exact solutions.
Whether you can find an exact solution depends on what functions
you're going to allow in the representation of the solution. If you
just allow roots, etc, you can't. If, to give a slighlty silly
example, you allow yourself to use functions like
SmallestRealRootOfPolynomial
in your "representation" then of course you _can_ "get"
the roots exactly, in terms of that function.
The reason I point this out is to point out that the
decision of what's allowed really is arbitrary. Using
the SmallestRealRootOfPolynomial function seems
a little silly, since it just tells you that the root is
"the root". But the SmallestRealRoot function is
a perfectly valid function mathematically, it's
really no different from the sqrt function.
Really isn't any different: When we say that
x=sqrt(2) the only reason we think that tells us
what x "is" "exactly" is that it's a _familiar_
function - saying x=sqrt(2) doesn't really give
us x "exactly" any more than saying
x=SmallestRealRoot('x^5-x^2+x=0')
does.
> I
>don't think the work on Hilbert's 10th problem applies to this, since
>I'm not only looking for integer solutions with a large number of
>indeterminates and integer coefficients (if that was the hypothesis of
>Hilbert's 10th, I don't remember), but rather I am looking for all
>solutions in one indeterminate with rational coefficients.
>
>If they can be nicely represented, great. If not, perhaps there exists
>some sort of "normal form" the algorithm could express the roots in that
>in a way is a "nice representation" and allows them to be computed to
>arbitrary accuracy quickly or something.
The function SmallestRealRoot has this property.
David M Einstein
: Yes, that's easy. (With a wrinkle or two: One can give an algorithm
: that takes a polynomial and an eps>0 as input and outputs n rationals
: r_1,...r_n such that |r_j-z_j|<eps for j=1,...n, where the z_j are
: the real roots. This doesn't mean that one can, for example,
: determine whether a fifth-degree polynomial has 5 distinct
: roots or some repeated roots. If the roots are all distinct then
: we will discover that by taking eps small enough, but it seems
: to me that it could happen that there was a repeated root
: but we never know for certain it's a repeated root, instead of
: just two roots that we haven't separated yet.
: I could well be wrong about that.)
If it is technicaly feasible to find the GCD's of polynomials
then GCD(P,P') tells you where the repeated roots are. Taking the GCD
with further derivatives will tell you the degree of those roots.
David C. Ullrich
Bob Silverman <bo...@my-deja.com> wrote:
> In article <93dnmi$knc$1...@nnrp1.deja.com>,
> lemm...@my-deja.com wrote:
> > Okay, I am aware that Abel (and later Galois, I guess) showed that
> > general polynomials of degree > 4 don't have solutions by the method
> of
> > radicals. This brings up two questions in my mind:
> >
> > (1) Any algebraic number can still be _represented_ by starting
with
> > the rationals and performing a finite number of adds, multiplies,
> > divisions, nth-root extractions, etc., right?
>
> Huh? You said above you KNOW that not all algebraic numbers
> can be represented, then turn around and directly contradict
yourself!
I started to say that in my reply, which hasn't appeared
yet. I decided just in time that it's not so clear that
he's contradicting himself: It _could_ be a priori that
any algebraic number has such a representation even though
there's no formula for the solution of the general
n-th degree polynomial.
(It seems unlikely, and of course it's not true. But
I don't quite see any actual _contradiction_ between
what he says he knows and what he asks here. Although
it looked contradictory to me too at first.)
> All algebraic numbers can NOT be thusly represented.
>
> I've intuitively proved
> > to my self that this is necessarily the case,
>
> You are hallucinating.
I'll agree that this seems likely.
--
Oh, dejanews lets you add a sig - that's useful...
David C. Ullrich
"David L. Johnson" <david....@lehigh.edu> wrote:
> lemm...@my-deja.com wrote:
> >
> > Okay, I am aware that Abel (and later Galois, I guess) showed that
> > general polynomials of degree > 4 don't have solutions by the method
of
> > radicals. This brings up two questions in my mind:
> >
> > (1) Any algebraic number can still be _represented_ by starting
with
> > the rationals and performing a finite number of adds, multiplies,
> > divisions, nth-root extractions, etc., right?
>
> That is more or less the definition of an algebraic number.
No, not only is it not more or less the definition it's also
not true.
--
Oh, dejanews lets you add a sig - that's useful...
David C. Ullrich
To be fair, it looked to me as well as though lemma_one was saying
"I understand that this is impossible, but is it possible?"
I don't think that what l_o wrote is _actually_ self-contradictory
that way, but it looked that way to me at first as well - if
he _was_ contradicting himself in such an obvious way then it
would be good if someone pointed out to him that he was making
utterly no sense at all.
--
Oh, dejanews lets you add a sig - that's useful...
Bob Silverman
> >
> > Okay, I am aware that Abel (and later Galois, I guess) showed that
> > general polynomials of degree > 4 don't have solutions by the
method of
> > radicals. This brings up two questions in my mind:
> >
> > (1) Any algebraic number can still be _represented_ by starting
with
> > the rationals and performing a finite number of adds, multiplies,
> > divisions, nth-root extractions, etc., right?
>
> That is more or less the definition of an algebraic number.
Huh? Where, oh where did you hear THIS??? Please cite a source!
It is not true. An algebraic number is one that is the root of
a polynomial with rational coefficients. Gauss's theorem allows
us to replace "rational coefficients" with "integer coefficients".
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
too_sc...@my-deja.com
David C. Ullrich <ull...@math.okstate.edu> wrote:
> In article <3A5A8523...@lehigh.edu>,
> "David L. Johnson" <david....@lehigh.edu> wrote:
> > lemm...@my-deja.com wrote:
> > >
> > > Okay, I am aware that Abel (and later Galois, I guess) showed that
> > > general polynomials of degree > 4 don't have solutions by the
method
> of
> > > radicals. This brings up two questions in my mind:
> > >
> > > (1) Any algebraic number can still be _represented_ by starting
> with
> > > the rationals and performing a finite number of adds, multiplies,
> > > divisions, nth-root extractions, etc., right?
> >
> > That is more or less the definition of an algebraic number.
>
> No, not only is it not more or less the definition it's also
> not true.
>
with the rationals, in the field of the complex numbers close with
respect to the arithmetic operations and taking all nth roots (i.e. -
take the smallest subfield of C which is contains all nth roots of its
members). Intersect the resulting field with R. Is there a name for
this subfield?
lemm...@my-deja.com
> lemm...@my-deja.com wrote:
> > Okay, I am aware that Abel (and later Galois, I guess) showed that
> > general polynomials of degree > 4 don't have solutions by the method
> of
> > radicals. This brings up two questions in my mind:
> >
> > (1) Any algebraic number can still be _represented_ by starting
with
> > the rationals and performing a finite number of adds, multiplies,
> > divisions, nth-root extractions, etc., right?
>
> Huh? You said above you KNOW that not all algebraic numbers
> can be represented, then turn around and directly contradict
yourself!
>
> All algebraic numbers can NOT be thusly represented.
>
> I've intuitively proved
> > to my self that this is necessarily the case,
>
> You are hallucinating.
After all the replies I have received, I now see that. Let me explain my
hallucination a bit more, though. I realized that if given
the expression,
a_n*z^n + a_{n-1}*z^{n-1} + ... + a_1*z + a_0 = 0
that I couldn't write z in terms of the _symbols_ a_i with only
algebraic operations (adds, multiplies, root extractions, etc.). But I
thought that it was possible that if given any particular instance in
the concrete, with each a_i replaced by an actual specific rational like
7/22 or 1/3, instead of just the abstract symbol "a_i" which represents
an _arbitrary_ rational, then that additional information would give you
enough to actually write z in the desired "nice representation." For
example, let n be an integer. It's 323rd root is either rational or it
isn't. Which is it? You don't know until I either tell you what n is
explicitly, or give you more information about it.
I thought somehow, that while with the symbols a_i just left as symbols
you could not find the "nice representation," you might somehow be
guaranteed to always succeed if they are replaced by actual concrete
rationals. (I knew that if this was the case, the proof would probably
be by contradiction and kinda complicated, as I indicated in my original
post.)
I suppose that before hearing all that I have heard in replies, I could
have reasoned as follows: if the above _were_ the case; that is, you
_could_ actually always find the nice representation when the a_i's are
replaced by actual rationals, then by dividing into many cases for
all the (countably many) combinations of a_i's, you would have an
extremely complicated solution by radicals for the general nth degree
polynomial. That is, you could have have an infinite tree representing
the general solution like
Case I: a_0 = 0
(i) a_1 = 0
(i.i) a_2 = 0
(i.ii) a_2 = 1
...
(ii) a_1 = 1
...
Case II: a_0 = 0
(i) a_1 = 0
(ii) a_1 = 1
...
...
Here each case and subcase assumes the progression
0,1/1,-1/1,1/2,-1/2,2/1,-2/1,3/1,-3/1,2/2,-2/2,1/3,-1/3,... which is a
countable sequence containing all the rationals from a diagnolization of
1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4 2/5 ...
3/1 3/2 3/3 3/4 3/5 ...
... ... ... ... ... ...
So just knowing that there is no general solution by radicals for degree
> 4 equations, I suppose the argument I just gave is a proof that there
can also be no nice representation.
David C. Ullrich
Of course this raises the question of whether it _is_ possible
to find the GCD... Oh, right. If the coefficients of P are rational
we can find GCD(P,P') by the euclidean algorithm. Duh.
Dik T. Winter
> On Wed, 10 Jan 2001 17:21:38 GMT, Dei...@world.std.com (David M
> Einstein) wrote:
> >David C. Ullrich (ull...@math.okstate.edu) wrote:
> >: to me that it could happen that there was a repeated root
> >: but we never know for certain it's a repeated root, instead of
> >: just two roots that we haven't separated yet.
> >
> >: I could well be wrong about that.)
> >
> > If it is technicaly feasible to find the GCD's of polynomials
> >then GCD(P,P') tells you where the repeated roots are. Taking the GCD
> >with further derivatives will tell you the degree of those roots.
>
> Of course this raises the question of whether it _is_ possible
> to find the GCD... Oh, right. If the coefficients of P are rational
> we can find GCD(P,P') by the euclidean algorithm. Duh.
Well, obviously we can find the GCD. But how do we decide whether the
zero we find in the GCD is indeed equal to the zero of the original
equation? Note that if the GCD is of higher degree than four we can
again *not* find in general an exact formulation of that zero, nor
do we have an exact formulation of the original zero. Hence when we
find equality to (say) a certain precision, we may be suspicious that
we have indeed a multiple zero, but still can not be certain.
(Interesting though, as a corollary we find that if a high degree
polynomial with rational coefficients has all zeros distinct except
for one double zero, the coordinates of that zero are rational. And
we *can* proof that it is a double zero and find it exactly.)
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
David C. Ullrich
wrote:
>In article <3a5db3a9....@nntp.sprynet.com> ull...@math.okstate.edu writes:
> > On Wed, 10 Jan 2001 17:21:38 GMT, Dei...@world.std.com (David M
> > Einstein) wrote:
> > >David C. Ullrich (ull...@math.okstate.edu) wrote:
> > >: but it seems
> > >: to me that it could happen that there was a repeated root
> > >: but we never know for certain it's a repeated root, instead of
> > >: just two roots that we haven't separated yet.
> > >
> > >: I could well be wrong about that.)
> > >
> > > If it is technicaly feasible to find the GCD's of polynomials
> > >then GCD(P,P') tells you where the repeated roots are. Taking the GCD
> > >with further derivatives will tell you the degree of those roots.
> >
> > Of course this raises the question of whether it _is_ possible
> > to find the GCD... Oh, right. If the coefficients of P are rational
> > we can find GCD(P,P') by the euclidean algorithm. Duh.
>
>Well, obviously we can find the GCD. But how do we decide whether the
>zero we find in the GCD is indeed equal to the zero of the original
>equation? Note that if the GCD is of higher degree than four we can
>again *not* find in general an exact formulation of that zero, nor
>do we have an exact formulation of the original zero.
So you think maybe I was taken in by Einstein's nonsense, eh?
Wouldn't be the first time... but I don't think so. Supposing that
P has rational coefficients, and keeping in mind that here we're
not talking about finding zeroes exactly, we have a sequence
of rationals converging to each zero (or rather we have as
many terms as we want in such sequences) and we're curious
whether the roots are distinct:
I'm not going to formulate the algorithm carefully but it seems
clear to me that it exists. Say P has degree 5. I assume we
can check whether there is a quintuple zero<g>. Assume not.
Now there is a quadruple zero if and only if the degree of
GCD(P,P',P'',P''') is at least one. If there _is_ a quadruple
zero we examine our five sequences of rationals converging
to the five zeros. Eventually we will show that _one_ of
the zeroes is dictinct from all four of the others. Now we
know that that one sequence is converging to one zero
and the other four sequences are converging to the
quadruple zero.
Suppose next that there is no quadruple zero. We look
at GCD(P.P'.P'') to see if there is a triple zero. If there
is then eventually _two_ of the sequences turn out to
have a limit distinct from the other three - now we
know that two sequences are converging to z1 and
z2 (we don't know yet whether z1 = z2) and the
other three are all converging to z3=z4=z5. Now
to find whether z1=z2 we look at zeroes of GCD(P,P').
We know that GCD(P,P',P'') has a double zero at the
point z3=z4=z5. So if the degree of GCD(P,P') is
two then it has no other zeroes, hence z1 <> z2, while
if the degree of GCD(P,P') is three then it has
"another" zero, and hence z1=z2.
Suppose next there is no triple zero. We look at the
zeroes of GCD(P,P') to see if there are any double
zeroes. If the degree of GCD(P.P') is 0 there are
no double zeroes so all five zeroes are distinct.
If the degree of GCD(P.P') is 1 there is exactly
one double zero and three simple zeroes. Hence
when we look at those sequences there will be
three that eventually become separated from the
others and two that we never quite distinguish -
now we know that those three sequences
converge to the simple zeroes and the other
two sequences converge to the double zero.
What if the degree of GCD(P.P') is two?
Well actually at this point we already know
there are no triple zeroes so we must have
two double zeroes and a simple zero, and
looking at the sequences we eventually see
which are which. But in some higher-order
case we wouldn't already know that there
are no triple zeroes. So we set Q=GCD(P,P')
and apply the same sort of analysis to
determine whether Q has multiple zeroes...
That's not a general proof, it's also not the most
elegant possible version, but it seems to me
it's clear we _can_ determine the multiplicity
of our approximate roots this way.
> Hence when we
>find equality to (say) a certain precision, we may be suspicious that
>we have indeed a multiple zero, but still can not be certain.
But that's not exactly how it goes. If we know, say, that there
are three simple zeroes and one double zero then it
only takes finitely much precision to find which is which:
If |z1 - 1| < 0.01, |z2 - 2| < 0.01, |z3 - 3| < 0.01,
|z4-i|<0.01 and |z5-i|<0.01 then we know that z4=z5.
We don't know that the root is i, but we know that
there is a root near 1, a root near 2, a root near 3, and
a double root near i.
Richard Fateman
takes a polynomial P and decomposes it into a product of (powers of)
factors each of which has no repeated roots.
Look in Knuth's ARt of computer programming vol 2, for example.
RJF
David C. Ullrich
Sure enough it's an [M25]. Thanks.
> RJF
>
--
Oh, dejanews lets you add a sig - that's useful...
David C. Ullrich
Thinking this might be possible is one thing. What you said was
not that it might be possible, what you said was that you had
"intuitivly" _proved_ that it was actually _so_!
I don't see how this follows at all. You should note that
I know no algebra, but it's not at all clear to me that the
fact that there exist algebraic numbers with no "nice
representation" follows from the non-existence of a general
formula. It's a _finite_ expression we're talking about.
Of course the implication in the other direction is clear -
if we know that there exist algebraic numbers with no
"nice representation" then it follows that there's no
formula for the general solution. I'm not sure because
I know laughably little about these matters, but I
_think_ that this is how the proof of the non-existence
of the general formula goes - my impression is that the
reason we know there's no general formula is that we
know there are algebraic numbers without a nice
representation.
If that's false someone will say so. If it's true it
would explain why some people thought you were contradicting
yourself - if it's true then the someone who really knows
this stuff will hear "number with no nice representation"
when you say "no general formula", because the proof is
not like rocket science, it's one of those things that's
at the start of everything for people who know about these
things, something they know so well that thay can't imagine
someone knowing that there's no general formula without
knowing the proof.
--
Oh, dejanews lets you add a sig - that's useful...
denis-feldmann
Dik T. Winter <Dik.W...@cwi.nl> a écrit dans le message :
G704C...@cwi.nl...
> In article <3a5db3a9....@nntp.sprynet.com> ull...@math.okstate.edu
writes:
> > On Wed, 10 Jan 2001 17:21:38 GMT, Dei...@world.std.com (David M
> > Einstein) wrote:
> > >David C. Ullrich (ull...@math.okstate.edu) wrote:
> > >: but it seems
> > >: to me that it could happen that there was a repeated root
> > >: but we never know for certain it's a repeated root, instead of
> > >: just two roots that we haven't separated yet.
> > >
> > >: I could well be wrong about that.)
> > >
> > > If it is technicaly feasible to find the GCD's of polynomials
> > >then GCD(P,P') tells you where the repeated roots are. Taking the GCD
> > >with further derivatives will tell you the degree of those roots.
> >
> > Of course this raises the question of whether it _is_ possible
> > to find the GCD... Oh, right. If the coefficients of P are rational
> > we can find GCD(P,P') by the euclidean algorithm. Duh.
>
> Well, obviously we can find the GCD. But how do we decide whether the
> zero we find in the GCD is indeed equal to the zero of the original
> equation?
What? Did you notice the D in GCD ? If a is a root of GCD(P,Q), then
P(a)=Q(a)=0 !
The only problem is to explicitly find a (well, if a is not real, there is
another problem). But as for the *existence* of multiple roots, there is no
possibility of trouble.
David M Einstein
: So you think maybe I was taken in by Einstein's nonsense, eh?
All my nonsense comes with a double your errors back guarantee.
Virgil
wrote:
> Well, obviously we can find the GCD. But how do we decide whether the
> zero we find in the GCD is indeed equal to the zero of the original
> equation?
Why is a decision needed?
IF you are considering polynomials over any subring of the complex
numbers, the only non-constant divisors of such polynomials are products
of linear or irreducible quadratic polynomials.
Under these constriants, how can a GCD of 2 or more polynomials have
zeroes other that those of all the given polynomials?
Dik T. Winter
> Dik T. Winter <Dik.W...@cwi.nl> a écrit dans le message :
> G704C...@cwi.nl...
> > Well, obviously we can find the GCD. But how do we decide whether the
> > zero we find in the GCD is indeed equal to the zero of the original
> > equation?
>
> What? Did you notice the D in GCD ? If a is a root of GCD(P,Q), then
> P(a)=Q(a)=0 !
Indeed, I was not thinking far enough.
Dave L. Renfro
[sci.math.symbolic Thu, 11 Jan 2001 18:03:51 GMT]
<http://forum.swarthmore.edu/epigone/sci.math.symbolic/playzerdblar>
wrote (in part):
> I don't see how this follows at all. You should note that
> I know no algebra, but it's not at all clear to me that the
> fact that there exist algebraic numbers with no "nice
> representation" follows from the non-existence of a general
> formula. It's a _finite_ expression we're talking about.
>
> Of course the implication in the other direction is clear -
> if we know that there exist algebraic numbers with no
> "nice representation" then it follows that there's no
> formula for the general solution. I'm not sure because
> I know laughably little about these matters, but I
> _think_ that this is how the proof of the non-existence
> of the general formula goes - my impression is that the
> reason we know there's no general formula is that we
> know there are algebraic numbers without a nice
> representation.
[I almost never read this group, but I have a little extra
time right now (I'm waiting for my wife to finish with
something), and so I read some of the posts in this thread
and decided to toss in my own two cents worth.]
I also know very little algebra and have long been confused by
discussions of this topic in books. For example, here's what
one finds on page 125 of James Pierpont "Lectures on the Theory
of Functions" (volume I, 1905), which is typical of what I'm
talking about:
"... equations of degree n > 4 cannot, in general, be solved by
the extraction of roots, or, as we say, do not admit of an
algebraic solution."
The two versions that David Ullrich brings up seem very different
to me, but the type of comment I quoted leads me to wonder if
these authors are even aware of the possibilities. [They probably
are, and I'm sure Pierpont was, but I wonder if they've thought
through the logical implications of what they're writing from
the standpoint of a beginner.]
Here are several interpretations of what Pierpont is saying:
Version #1: For some n > 4, including n=5 and perhaps some other
values of n as well, there exists no general explicit
"algebraic formula" for the roots of an arbitrary
n'th degree polynomial in terms of its coefficients.
Version #2: For each n > 4, there exists no general explicit
"algebraic formula" for the roots of an arbitrary
n'th degree polynomial in terms of its coefficients.
Version #3: For some n > 4, including n=5 and perhaps some other
values of n as well, there exists a specific n'th degree
polynomial with integer coefficients that has at
least one real root that cannot be expressed using
a finite sequence of additions, subtractions,
multiplications, divisions, and positive integer
root extractions applied to the coefficients of
the polynomial in question.
Version #4: For some n > 4, including n=5 and perhaps some other
values of n as well, there exists a specific n'th degree
polynomial with integer coefficients that has at
least one real root that cannot be expressed using
a finite sequence of additions, subtractions,
multiplications, divisions, and positive integer
root extractions applied to the set of integers.
Version #5: For each n > 4, there exists a specific n'th degree
polynomial with integer coefficients that has at
least one real root that cannot be expressed using
a finite sequence of additions, subtractions,
multiplications, divisions, and positive integer
root extractions applied to the coefficients of
the polynomial in question.
Version #6: For each n > 4, there exists a specific n'th degree
polynomial with integer coefficients that has at
least one real root that cannot be expressed using
a finite sequence of additions, subtractions,
multiplications, divisions, and positive integer
root extractions applied to the set of integers.
Versions 1 and 2 are equivalent. Obviously, Version 2
implies Version 1. For the other direction, suppose there
was a general formula for the roots of all (say) 9'th degree
polynomials. Then we could get a formula for the roots of all
5'th degree polynomials by applying the 9'th degree formula
to the special case of (x^4)*(ax^5 + bx^4 + cx^3 + dx^2 + ex + f),
contradicting Version 1. This argument obviously generalizes from
n = 9 to any n > 5.
The same idea also shows that Version 3 is equivalent to Version 5,
and that Version 4 is equivalent to Version 6.
Version 3 is equivalent to Version 4, and Version 5 is equivalent
to Version 6. As long as we have a nonzero polynomial, we can
divide one of its nonzero coefficients by itself to get 1. From 1
we can get any integer by finitely many (depending on the integer,
of course) additions and/or subractions of 1. So if there were a
"finite representation using integers" of all solutions to a
given nonzero polynomial, we could also come up with a finite
representation of each solution using only the coefficients of
that particular polynomial.
Therefore, the six versions I gave reduce to the two versions
David Ullrich mentioned, Version 2 and Version 6.
Unless I'm greatly mistaken, I'm fairly sure that Version 6 (which
clearly implies all the other versions) is true. I think the
solvability of the Galois group for the polynomial (the meaning
of which I don't remember any details of), which can sometimes be
proved for certain polynomials (but which I also suspect there's no
constructive way of doing this in general), corresponds to all
the real roots (Or is it all the real and complex roots?) of that
polynomial being "finitely expressible using integers".
Below is a sci.math post of mine that might be of interest.
[The URL for this post's thread is given in the post itself.]
Dave L. Renfro
##################################################################
##################################################################
Subject: Re: Does surd form implies non-transcendental?
Author: Dave L. Renfro <dlre...@gateway.net>
Date: 25 Apr 00 09:53:58 -0400 (EDT)
Goat <goat...@hotmail.com>
[sci.math Mon, 24 Apr 2000 16:10:20 +0800]
<http://forum.swarthmore.edu/epigone/sci.math/poxcrimpvo>
wrote
> If a number is a combination of positive integers and
> powers of = reciprocal of integers (i.e. in surd form),
> can we conclude that this = number must be a root of a
> polynomial with integral coefficient?
>
> Furthermore, I am also finding an expression for
> sin(100 degree) in surd = form.
>
> Thanks!
What you're describing are called "explicit algebraic numbers",
and every explicit algebraic number is an algebraic number
("algebraic number" means being a root of a polynomial with
integer coefficients). This can be proved with the use of
some linear algebra and the observation that an n'th root
of an explicit algebraic number is algebraic. [One poster
mentioned Galois theory, but you don't need that for what
you're asking.] For a proof that the algebraic numbers form
a field, see theorem 9.2 on page 199 (in Section 9.2: "Algebraic
Numbers") of [1] OR theorem 7.2 on page 84 (in Section 7.1:
"Closure properties of algebraic numbers") of [2].
[1] Ivan Niven and Hrbert S. Zuckerman, AN INTRODUCTION TO THE
THEORY OF NUMBERS, 2'nd edition, John Wiley and Sons, 1966.
[2] Ivan Niven, IRRATIONAL NUMBERS, Carus Mathematical
Monograph 11, The Mathematical Association of America,
1956.
The fact that any positive integer root of an explicit algebraic
number is algebraic, suppose b is an explicit algebraic
number and p(x) is a polynomial with integer coefficients
verifying this (i.e. p(b) = 0). Then b^(1/n) is a root of
the polynomial q(x) defined by q(x) = p(x^n).
There are algebraic numbers that are not explicit algebraic
and, as far as I know, you DO NEED Galois theory for this.
No such example exists satisfying an equation of degree 4 or
less (since there are explicit algebraic formulas for the
roots of these equations in terms of their coefficients), but
there are roots of some 5'th degree polynomials that are
algebraic and not explicit algebraic.
For cubic and quartic equation formulas, see my Dec. 11, 1999
k12.ed.math post at
<http://forum.swarthmore.edu/epigone/k12.ed.math/phorglimquar>.
For an example of a 5'th degree equation with integer
coefficients that has a non-explicit algebraic root, see
page 258 of [3] (end of Section 5.8: "Galois Groups over the
Rationals") or Richard Carr's Feb. 5, 2000 sci.math post at
the link below.
<http://forum.swarthmore.edu/epigone/sci.math/creldcharwhox>
[3] I. N. Herstein, TOPICS IN ALGEBRA, 2'nd edition, Xerox
College Publishing, 1975.
The set of algebraic numbers satisfy a stronger property than
simply being a field--they form an "algebraically closed
field". What this means is that any solution to a polynomial
whose coefficients are algebraic numbers is an algebraic number.
This too seems to require Galois theory to prove. At least,
I'm not aware of a more elementary proof.
Finally, I don't know off-hand whether sin(100 degrees) is an
explicit algebraic number, but I do know that sin(n degrees)
is an explicit algebraic number for any integer divisible by 3.
A table of these values appears on page 74 (end of Chapter V)
of [4].
[4] E. W. Hobson, A TREATISE ON PLANE AND ADVANCED TRIGONOMETRY,
7'th edition, Dover Publications, 1928/1957.
However, it is not difficult to see that any trig. function
evaluated at a rational number of degrees is an algebraic
number using multiple angle expressions of sine and cosine.
[e.g. sin(n*x) and cos(n*x) are n'th degree polynomials in
sin(x) and cos(x).] For more details, see my July 11 and July 12,
1999 alt.math.undergraduate posts at
<http://forum.swarthmore.edu/epigone/alt.math.undergrad/vogoubril>.
Dave L. Renfro
##################################################################
##################################################################
Dave L. Renfro
[sci.math.symbolic 14 Jan 01 01:00:53 -0500 (EST)]
<http://forum.swarthmore.edu/epigone/sci.math.symbolic/playzerdblar>
wrote some stuff (all snipped) about explicit algebraic real
numbers and algebraic real numbers.
When I read my post the next day, after it appeared, I noticed
that some of what I wrote can be made a lot clearer. Specifically,
some stuff about explicit algebraic numbers and algebraic numbers
from my April 24, 2000 sci.math post. [A copy of this earlier post
was included in my sci.math.symbolic post that I'm presently
responding to.]
1. The explicit algebraic real numbers form a subfield of
the reals.
This is trivial.
2. The algebraic real numbers form a subfield of the reals.
This can be proved using some linear algebra and a proof can
be found in references [1] and [2] (given in my other post).
3. Every explicit algebraic real number is an algebraic real
number. Hence, the explicit algebraic real numbers form a
subfield of the algebraic real numbers.
I believe an inductive proof of this can be extracted from the
proof of #2 above (the specific proofs that I reference, that
is) and the observation that every positive integer root of an
algebraic real number is an algebraic real number. [I gave a
proof of this latter fact in my other post. In that proof,
however, I made the assumption that 'b' was an explicit
algebraic real number. For our present purposes we should
assume that 'b' is an algebraic real number. In fact, it's
not clear to me that I actually proved what I claimed in
that other post.]
4. The explicit algebraic real numbers form a PROPER subfield
of the algebraic real numbers.
This requires Galois theory, in the sense that I don't think
any "elementary proof" is known, and is a consequence of
"Version 6" in my other post.
5. Both of the subfields in #4 are not only closed under the
(+,*)-field operations of the reals, but they are also closed
under the operation of taking positive integer roots. That is,
if F denotes a fixed choice of one of these two fields, n is
a positive integer, and b belongs to F, then all real solutions
to x^n - b = 0 belong to F.
This is immediate for the explicit algebraic real numbers.
For the algebraic real numbers, see my comment to #3 above.
6. The algebraic real numbers satisfy a stronger closure property
than what appears in #5--they form an "algebraically closed
field". What this means is that any real solution to a polynomial
whose coefficients are algebraic real numbers is an algebraic
real number.
I believe this "requires" Galois theory to prove, in the sense
that I don't think any "elementary proof" is known.
7. The explicit algebraic real numbers do not form an
algebraically closed field.
In fact, one doesn't need a polynomial with "exotic" explicit
algebraic coefficients to demonstrate this. An example can
be found using integer coefficients. [This is the content of
#4 above.]
8. No proper subfield of the algebraic real numbers is
algebraically closed.
Being a stronger result than #7 (and hence, stronger than #4),
I'm pretty sure that Galois theory is "needed" to prove this
in the sense that I don't think any "elementary proof" is known.
9. The real numbers form an algebraically closed field (trivial)
that properly contains the algebraic numbers (there exist
transcendental numbers). I don't know off-hand if there are
other algebraically closed subfields of the reals, let alone
what their inclusion lattice structure is, aside from the easy
to see fact (in light of the results above) that the algebraic
real numbers will be the minimum element and the real
numbers will be the maximum element. Maybe a straightforward
argument involving a transcendence basis for the reals over
the rationals can be used to answer the first part of the
previous question, but I haven't given this any thought.
Dave L. Renfro
P.S. There is a well known field that properly lies between the
rational numbers and the explicit algebraic real numbers--the
(ruler-and-compass) constructible real numbers. These are
defined just like the explicit algebraic real numbers,
except in place of "positive integer root" you use "square
root". Note that 2^(1/2) is constructible and not rational,
and 2^(1/3) is explicit algebraic and not constructible
(this is the "duplication of the cube" non-constructibility
result). And, of course, fields such as Q[2^(1/2)],
Q[2^(1/3)], Q[2^(1/2), 7^(1/8)], etc. lie properly between
the rational numbers and the constructible real numbers.
Hummm... It just occurred to me that the Turing real numbers
(i.e. the recursive real numbers) form an algebraically
closed field that lies properly between the algebraic real
numbers and the real numbers. I would guess, then, that there
are lots of other algebraically closed subfields of the
reals, probably 2^c many of them.
Virgil
(Dave L. Renfro) wrote:
> 9. The real numbers form an algebraically closed field (trivial)
The reals do not even contain the roots to all polynomial equations with
integer coefficients, for example, x^2 + 1 = 0.
I have heard that the complexes are an algebraically closed field, but
never that the reals were. Wasn't it at least partly to get algebraic
closure that the complexes were invented?
If the reals are to be an algebraically closed field, it requires a
definition of algebraic closure that I am not familiar with.
Perhaps you could be so kind as to furnish me with such a definition.
Dave L. Renfro
[sci.math.symbolic Sun, 14 Jan 2001 16:28:10 -0700]
<http://forum.swarthmore.edu/epigone/sci.math.symbolic/playzerdblar>
wrote
I wanted to stay in the set of real numbers because, regarding
the "constructible complexity" of the fields, nothing new appears
when you consider subfields of the complex numbers. But you might
be right in that I'm parting from standard terminology. I don't
have any algebra books with me--now and when I wrote those
posts--but I thought the notion of an algebraically closed
subfield of the reals was something that appears in the
literature. I did an internet search for "real closed field",
but this happens to mean something else. In any event, I did
give a definition of what I meant:
*********************************************************************
6. The algebraic real numbers satisfy a stronger closure property
than what appears in #5--they form an "algebraically closed
field". What this means is that any real solution to a polynomial
whose coefficients are algebraic real numbers is an algebraic
real number.
*********************************************************************
Note that I said "any real solution".
In summary, since my focus was not on solving polynomials, but
rather on the "structural properties" of real numbers that
satisfy polynomial equations of various sorts (e.g. are they
ruler-and-compass constructible, are they explicit algebraic, etc.),
I decided to avoid complex numbers. However, I may have misused
the term "algebraically closed" in doing this.
Dave L. Renfro