Re: equations
- To: mathgroup at smc.vnet.net
- Subject: [mg32044] Re: equations
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Thu, 20 Dec 2001 03:42:07 -0500 (EST)
- References: <BD4BAAFD-F42E-11D5-A0A7-00039311C1CC@tuins.ac.jp>
- Sender: owner-wri-mathgroup at wolfram.com
Andrzej Kozlowski wrote:
>
> I am sure you must be right. I guessed I was confused because I have
> never considered carefully how root isolation and their numbering as
> Root[f,1], ....Root[f,n] work. Of course we know that :
>
> In[2]:=
> Solve[a + b*x^2 + c*x^3 + d*x^4 + e*x^5 == 0, x]
>
> Out[2]=
> {{x -> Root[a + b*#1^2 + c*#1^3 + d*#1^4 + e*#1^5 & , 1]},
> {x -> Root[a + b*#1^2 + c*#1^3 + d*#1^4 + e*#1^5 & , 2]},
> {x -> Root[a + b*#1^2 + c*#1^3 + d*#1^4 + e*#1^5 & , 3]},
> {x -> Root[a + b*#1^2 + c*#1^3 + d*#1^4 + e*#1^5 & , 4]},
> {x -> Root[a + b*#1^2 + c*#1^3 + d*#1^4 + e*#1^5 & , 5]}}
>
> means no more than that there are 5 roots of a fifth degree equation. At
> this point the ordering of the roots is purely formal. It's only when
> you substitute values for the parameters than Mathematica isolates the
> roots and the ordering acquires a meaning (so one can think of these
> "solutions" as (topologically badly behaved) functions of the parameters
> that return roots). I was not sure that this however would be remain
> true when you have a complex system of equations and solutions involve
> root objects with coefficients that themselves involve root objects and
> so on. It does not seem quite obvious to me that a root of a system of
> equations can be consistently represented as something like Root[f, 5]
> where f again involves other root objects, in such a way that this
> returns a root of the system for all values of the parameters (it's the
> choice of numbering that worried me). Presumably there is some theorem
> here, perhaps a rather trivial one. On the other hand, it now seems that
> nothing very sophisticated is going on in such a case, a suitable
> Groebner basis is found which eliminates variables in turn and then the
> roots are simply numbered purely formally, just as in the above
> example. Still, I am puzzled by Fred's claim that the solutions
> obtained by means of ELiminate in th eexample that started this
> discussion do not work for some values of the parameters (I may be still
> misunderstanding him). Since I think they must be solutions (by
> elimination theory) I assumed that was something to do with the above
> discussion. Of course it may be due to something quite different, for
> example problems with precision in numerical computations.
>
> Andrzej Kozlowski
> Toyama International University
> JAPAN
> http://platon.c.u-tokyo.ac.jp/andrzej/
Let me make two clarifications (well, I hope they are seen as such).
(1) Whatever I said applies under the assumption that we begin with
polynomials in the variables for which we solve (as opposed to having
them appear, for example, inside radicals). Symbolic parameters are on a
different footing. They may live inside radicals, Root[] objects,
nestings of the above, and so forth. As you say, the solutions expressed
in terms of Root[] functions that themselves involve such things are
just formal objects, and indeed these formal parametrized solutions are
not (in general) topologically well behaved functions of the underlying
parameters. Once parameters are assigned values e.g. via ReplaceAll, you
get algebraic numbers that are well behaved entities.
(2) I believe Fred Simons referred to the following situation. You are
given a system in n variables that has finitely many solutions. You
eliminate all but one to get a univariate polynomial in the remaining
variable, solve it, and so obtain solutions in that variable. Now do the
same thing for all other variables. You then have a problem: how to
patch solutions in the various variables together to get solutions in
all variables at once.
To get some idea of how hopeless this is I will point out two issues.
(i) Take the "generic" setting (radical ideal, general position with
respect to all variables, I'm not going to define what all that means;
those who do not know but anyway read this far should just take my word
that it is a common scenario). In this case any lexicographic Groebner
basis will look like
polynomial in x[n] of degree d
x[n-1] - poly in x[n] of degree < d
...
poly in x[1] of degree < d.
In particular we have d solutions. If you eliminated all variables but
x[n] then you get the d roots in that variable. Now do the same for each
other variable. You obtain exactly d roots for each. So we have d^n
possible ways to combine roots from various solutions, but only d give
actual solutions to the system. What a headache. In fact I believe it
was this issue that lead to the so-called FGLM conversion method for
converting from a differently ordered Groebner basis to lexicographic
(knowing from earlier work by Buchberger how to find the univariate
polynomials helped alot in coming up with the complete conversion).
(ii) This next issue is, I think, what has led to some of your
questions. The possibility of combining solutions in individual
variables, discussed in (i) above, is utterly hopeless if they happen to
be these formalized Root[] functions in parameters. The reason, as you
suspect, is that we do indeed have a "branch jumping" problem (or so I
am fairly certain). In other words, some parameter values would cause us
to patch together certain univariate solutions, but these would need to
change for other parameter values.
This problem does not arise if we solve for all variables at once using
either lexicographic Groebner basis with back substitution, or the
eigensystem approach I referred to in a previous post; thos methods will
give a needed consistency by forcing individual solutions to be in terms
of a specific parametrized Root[] function. That is why I can claim that
it all (magically) works out. I certainly agree, however, that one
cannot hope to patch together parametrized solutions in individual
variables.
Daniel Lichtblau
Wolfram Research