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