Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2007
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Re: Re: Limit and Root Objects

  • To: mathgroup at smc.vnet.net
  • Subject: [mg72729] Re: [mg72668] Re: [mg72644] Re: [mg72620] Re: Limit and Root Objects
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Wed, 17 Jan 2007 06:04:33 -0500 (EST)
  • References: <NDBBJGNHKLMPLILOIPPOEEEDFFAA.djmp@earthlink.net> <4573B174-8F5A-445B-8E1F-51E3F53A8683@mimuw.edu.pl> <04F49FA6-5BAF-4FCD-9A82-4B17C58794D4@mimuw.edu.pl>

I just noticed that I changed my notation near the end of the proof,  
switching from the name R for the hypothetical continuous root  
function to root. In case this causes again  some confusion the line

g(t) = root(f(t)) = root(x^d- Exp[2Pi I t])

should be

g(t) = R(f(t)) = R(x^d- Exp[2Pi I t])

and the line

root(f(0)) == root(f(1))

should be

R(f(0)) == R(f(1))


Andrzej

On 16 Jan 2007, at 09:12, Andrzej Kozlowski wrote:

> I have decided to make one more attempt, although I really can't  
> afford to spend this time - I am under a lot of pressure form other  
> things I have to do. But if this does not work than nothing else will.
>
> I am simply going to re-write Adam's proof using more words, which  
> ought to make it a little clearer.
>
> Consider again the space of all monic polynomials of degree d, with  
> complex coefficients. These are object of the form:
>
> x^d + a(1) x^(d-1)+ ... + a(d), where a(i) are complex numbers. Any  
> such polynomial can be identified wiht the ordered d-tuple
> (a(1),...,a(d)) , so the space of polynomials has a topology which  
> is just the topology of C^d - the d-fold Cartesian product of the  
> complex numbers. We shall therefore identify the space of  
> polynomials with C^d.
> In the usual way we will remove from this space the space S   
> consisting of all those monic polynomials with multiple roots. We  
> will show that one cannot define a continuous root function on the  
> space C^d-S . Since C^d-S is a subspace of C^d, if one cannot  
> define a continuous root function on C^d-S then one obviously can't  
> do so on the larger space C^d.
> Now suppose there is a continuous function, lets call it R (nothing  
> to do with Mathematica's  Root - it was unfortunate that Adam used  
> this name), from C^d-S to the complex numbers C, which has the  
> property that for any polynomial p in C^d-S, R(p) is a root of p.  
> We will show that the assumption that such an R exists leads to a  
> contradiction. O.K> so suppose we have R: C^d-S -> C and R(p) is a  
> root of p and R is continuous. Now consider the following loop in  
> the space C^d-S; going from the polynomial x^d -1 to itself. A loop  
> on a space X is a continuous function f:[0,1] -> X such that f(0)=f 
> (1), where [0,1] denotes the unit interval. Our loop is defined as  
> follows f(t) = x^d- Exp[2Pi I t] . Note that this is always always  
> a polynomial wihtout multiple roots, and that f(0) = f(1) = x^d -  
> 1, in  other we start with the polynomial x^d -1 and then  
> continuously move in the space of polynomials until we get back to  
> the same polynomial. (A technical comment: homotopy classes of such  
> loops form a group called the fundamental group of the space on  
> which these loops are defined. If this group is the zero group then  
> the space is simply connected. The main point of the argument is  
> that the space C^d-S is not simply connected and its fundamental  
> group is a famous group called Artin's group on d -strings). O.K.,  
> now we compose out loop with our continuous function root, which we  
> are assuming to exist. So we get a continuous function g(t) = root(f 
> (t)) = root(x^d- Exp[2Pi I t]). Note that since g(t) is a root of  
> x^d- Exp[2Pi I t]. that means that it must satisfy this equation,  
> that is g(t)^d == Exp[2Pi I t]. so in particular the values of g(t) 
> lie in the unit circle. O.K. now since g(t)^d = Exp[2Pi I t], we  
> must have
> g(t) == E^((2 I Pi t+2 I Pi k(t))/d)
> where k(t) is some integer depending on t. But since g(t) must be  
> continuous and k(t) must always be an integer, then it clearly must  
> be always constant. So actually g(t)=E^((2 I Pi t+2 I Pi k )/d),  
> where k is a fixed integer. O.K. now put into this t=0 and t=1. We  
> get g(0)= E^((2 I Pi k )/d) and g(1) = E^((2 I Pi ( k+1 )/d), which  
> are not equal. But look, f is a loop, so f(0) = f(1). But that mean  
> root(f(0)) == root(f(1)). But that means we must have g(0) = g(1).  
> So we have a contradiction. This means that no such function root  
> can exists.
> The proof is complete, and no animation or anything else can  
> disprove it.
>
> ANdrzej Kozlowski
>
> On 15 Jan 2007, at 19:22, Andrzej Kozlowski wrote:
>
>> I am sorry but I am about to give up. Let me explain  it again but  
>> for the last time really. And please do not send me any animations  
>> because I never look at them. To tell the truth I have not even  
>> looked at one of them. Everything I have written and am writing is  
>> well known mathematics and it is you who are completely confused.
>>
>> The point is this. It is possible to define a continuous function  
>> from the set of complex polynomials of degree d with the topology  
>> given by considering the coefficients as elements of C to the  
>> topological space consisting of unordered d-tuples {x1,x2,...,xd},  
>> with the topology of the so called symmetric product of C. In  
>> intuitive language, the set of roots as set or un-ordered d-tuple  
>> does depend continuously on the coefficients of the polynomial.  
>> But it is impossible to continuously choose one root out of this  
>> unordered set and obtain in this way a continuous function on the  
>> space of all complex polynomials (or even on the smaller space of  
>> polynomials minus the determinant). It is impossible intuitively  
>> because  there is no natural way to choose one root out of an  
>> unordered set. In more precise topological language the reason is  
>> that you are dealing with a non trivial covering space, which does  
>> not have a global continuous section. This is what Adam's proof  
>> shows. It has nothing whatever to do with Root objects,  
>> Mathematica but it is only mathematics and well known mathematics,  
>> so there can be no dispute about it.
>>
>> As I wrote above, I definitely give up. If you can't follow this  
>> then you should just accept that topology, even basic one is not  
>> something that very congenial to you, and leave it at that.
>>
>> Anyway, I can't devote any more time or effort to this matter. If  
>> any body else would like to try (Adam) then please do.  
>> Alternatively, perhaps you should write to a mathematical site,  
>> for example you could try the Hopf topology group run by Don  
>> Davies, dmd1 at lehigh.edu , and ask about this matter and perhaps  
>> you will find somebody with better pedagogical skills then mine.  
>> There are also other sites run by professional mathematicians who  
>> answer general questions of this kind. Or you could try writing to  
>> Dave Rusin (rusin at math.niu.edu), he is a topologist and I think he  
>> likes answering questions of this kind. Also, he has much more  
>> experience, patience and pedagogical skill than me.
>> Perhaps some other mathematicians on the list (Adam, Daniel ?)  
>> might want to explain it better, but as for me I am form now on  
>> only willing to discuss mathematica and not mathematics, and  
>> definitely not anything remotely topological.
>>
>>
>> Andrzej Kozlowski
>>
>>
>> On 15 Jan 2007, at 17:06, David Park wrote:
>>
>>> Well, I'm glad you didn't give up (and I didn't think you would).  
>>> I might
>>> actually learn some formal mathematics. But as yet, I do not  
>>> follow Adam
>>> Strzebonski's proof - nor am I certain exactly what the claims of  
>>> the proof
>>> are. So let me state the matter in my own words.
>>>
>>> Given a one-parameter, say a, finite order, say order d,  
>>> polynomial with
>>> real or complex coefficients, can we find a set of d root  
>>> functions which
>>> are each continuous and which give the complete set of roots for the
>>> polynomial for each value of a?
>>>
>>> I claim that the answer is yes. Let's say that it is not possible  
>>> to obtain
>>> continuous exact algebraic roots, say with the Mathematica Root  
>>> function
>>> (and I think that's what you and Strzebonski are saying). So with  
>>> Root we
>>> obtain an indexed set of discontinuous root functions. But the
>>> discontinuities are not unrelated. There are global relationships  
>>> between
>>> the root functions. And specifically I'm claiming that we can  
>>> introduce a
>>> pointwise reindexing function that will reindex the roots for  
>>> each value of
>>> a, and that these new root functions can be made continuous. We  
>>> can even
>>> make up a table of the new roots and fit an InterpolatingFunction  
>>> to them so
>>> that we will have a set of true numerical root functions that are  
>>> each
>>> continuous.
>>>
>>> Here are the examples again.
>>>
>>> Needs["Graphics`Animation`"]
>>> Needs["Graphics`Colors`"]
>>>
>>> Routine to reindex at each value of a.
>>>
>>> rootindexedset[a_] :=
>>>   Module[{roots = rootset[a], newroots, rootpermutations,  
>>> distances, pick},
>>>     If[memoryrootset === Null, newroots = roots,
>>>       rootpermutations = Permutations[roots];
>>>       distances =
>>>         Plus @@ Abs[Part[roots, #] - memoryrootset] & /@  
>>> basepermutations;
>>>       pick = Part[Position[distances, Min[distances], 1], 1, 1];
>>>       newroots = Part[roots, Part[basepermutations, pick]]];
>>>     memoryrootset = newroots;
>>>     {a, #} & /@ newroots
>>>     ]
>>>
>>> Case 1
>>>
>>> polynomial = x^5 - a x - 1 == 0;
>>> displaypoly = polynomial /. a -> HoldForm[a];
>>> rootset[a_] = x /. Solve[polynomial, x]
>>>
>>> Calculating the reindexed root functions.
>>>
>>> memoryrootset = Null;
>>> basepermutations = Permutations[Range[5]];
>>> roottables = Transpose@Table[rootindexedset[a], {a, -6., 10, 0.25}];
>>> Do[root[i] = Interpolation[Part[roottables, i]], {i, 1, Length 
>>> [roottables]}]
>>>
>>> Plot routine and animation
>>>
>>> frame[a_] :=
>>>   Module[{locations},
>>>     locations = {Re[#], Im[#]} & /@ Table[root[i][a], {i, 1, 5}];
>>>     Show[Graphics[
>>>         {LightCoral, AbsolutePointSize[15],
>>>           Point /@ locations,
>>>           Black,
>>>           MapThread[Text[#1, #2] &, {Range[5], locations}],
>>>
>>>           Text[SequenceForm["a = ",
>>>               NumberForm[a, {3, 2}, NumberPadding -> {" ", "0"}]],
>>>             Scaled[{0.1, 0.95}], {-1, 0}]}],
>>>
>>>       AspectRatio -> Automatic,
>>>       TextStyle -> {FontFamily -> "Courier", FontSize -> 12,
>>>           FontWeight -> "Bold"},
>>>       Frame -> True,
>>>       PlotRange -> {{-3, 3}, {-3, 3}},
>>>       PlotLabel -> SequenceForm["Continuous Roots of" ,  
>>> displaypoly],
>>>       ImageSize -> 400]
>>>     ]
>>>
>>> Animate[frame[a], {a, -6, 10, 0.25}]
>>> SelectionMove[EvaluationNotebook[], All, GeneratedCell]
>>> FrontEndTokenExecute["OpenCloseGroup"]; Pause[0.5];
>>> FrontEndExecute[{FrontEnd`SelectionAnimate[200,  
>>> AnimationDisplayTime -> 0.1,
>>>       AnimationDirection -> ForwardBackward]}]
>>>
>>> Case 2
>>>
>>> polynomial = x^5 + (1 + I) x^4 - a x - 1 == 0;
>>> displaypoly = polynomial /. a -> HoldForm[a];
>>> rootset[a_] = x /. Solve[polynomial, x];
>>>
>>> memoryrootset = Null;
>>> basepermutations = Permutations[Range[5]];
>>> roottables = Transpose@Table[rootindexedset[a], {a, -6., 10, 0.50}];
>>> Do[root[i] = Interpolation[Part[roottables, i]], {i, 1, Length 
>>> [roottables]}]
>>>
>>> Animate[frame[a], {a, -6, 10, 0.25}]
>>> SelectionMove[EvaluationNotebook[], All, GeneratedCell]
>>> FrontEndTokenExecute["OpenCloseGroup"]; Pause[0.5];
>>> FrontEndExecute[{FrontEnd`SelectionAnimate[200,  
>>> AnimationDisplayTime -> 0.1,
>>>       AnimationDirection -> ForwardBackward]}]
>>>
>>> I'm not claiming that I know for certain that this can be done in  
>>> all cases,
>>> or whether it might depend on how the parameter a enters into the
>>> polynomial. I leave it to the mathematicians to correct me if  
>>> necessary or
>>> make it sharper.
>>>
>>> But I think that it is very worthwhile doing this kind of thing.  
>>> It changes
>>> our viewpoint of what is happening. For example, the jumping of  
>>> the initial
>>> root functions is something of an artifact of algebra. It  
>>> confuses what is
>>> really happening, say in a physical problem. When we take a  
>>> global view of
>>> the solution set, the discontinuities lose their importantance.  
>>> What is more
>>> important is that when the parameter a passes through a point  
>>> that produces
>>> degenerate roots, then the solution set branches. If there is a  
>>> p'th order
>>> root at the degeneracy, then there are p! branches to the  
>>> solution set. If a
>>> physical solution corresponded to following a single root, then this
>>> branching would certainly have significance - much more than the
>>> discontinuities in the original root functions.
>>>
>>> And there is a lot of good mathematics that flowed out of visual and
>>> graphical thinking.
>>>
>>> I'm sure I won't hear from Paul Abbott who posed these particular  
>>> cases in
>>> the first place.
>>>
>>> David Park
>>> djmp at earthlink.net
>>> http://home.earthlink.net/~djmp/
>>>
>>> From: Andrzej Kozlowski [mailto:akoz at mimuw.edu.pl]
>>>
>>> On 15 Jan 2007, at 08:02, Andrzej Kozlowski wrote:
>>>
>>>> One further (I hope last) comment.
>>>
>>> As usual I am unable to stick to this kind of promise ;-(
>>>
>>> In fact, it is clear that if we want to consider all roots of a
>>> polynomial as a continuous function of the parameter we do not even
>>> need to remove the discriminant. We can simply consider the map
>>>
>>> f: C^d -> S^d(C)
>>>
>>> where S^d(C) is the so called symmetric product on C (C stands for
>>> the complex numbers). You can think of it as the space whose  
>>> elements
>>> are unordered tuples (c1,c2,...,cd) of complex numbers - in other
>>> words sets with d elements. So the map f assigns to a polynomial  
>>> x^d+
>>> a(d-1) x^(d-1)+...+a(0)  the unordered tuple (a(d-1), a(d-2),..., a
>>> (0)). The symmetric product has a natural topology (in fact the d-th
>>> symmetric product on C happens to be homeomorphic to C^d but this is
>>> not the case for other spaces, for example the d-th symetric product
>>> on R is not R^d). Anyway, the map f is indeed a continuous map, and
>>> this formalizes the statement that the set of roots of a complex
>>> polynomial depends continuously on the coefficients. However,  
>>> this is
>>> quite different from saying that you can define one continuous root
>>> on the space of all polynomials, which is certainly impossible (see
>>> again Adam Strzebonski's proof).
>>>
>>> I suspect this was the source of all the confusion here and we have
>>> been arguing without understanding what the other side is talking
>>> about. At least in my case this is the kind of situation that is
>>> likely to lead to a loss of patience or even (as happened briefly
>>> this time) temper. I think it also shows the great advantage of  
>>> using
>>> formal mathematics rather than intuitive arguments, even if  
>>> supported
>>> by very skillful animations. In 30 years of doing mathematics I  
>>> can't
>>> recall coming across anyone loosing his temper over a strictly  
>>> formal
>>> mathematical argument. When something like this does happen it  
>>> always
>>> turns out that someone was simply not being formal enough.
>>>
>>> Andrzej Kozlowski
>>>
>>>
>>>
>>>> There is of course a sense in which the roots of a polynomial are
>>>> continuous in the coefficients. Formally one has to use the concept
>>>> of the symmetric product to state this. Let again X be the space
>>>> C^d-S of monic polynomials of degree d with the determinant remove.
>>>> Now we construct a space Y as follows. We first consider the
>>>> subspace Z of the Cartesian product C^d, consisting of complex
>>>> numbers (c_1,c_2,...,c_d) which are all distinct. The symmetric
>>>> group on d elements (the permutation group) S(d) acts on Z, and we
>>>> let Y be the set of orbits of the action Y=Z/S(d). So now we have a
>>>> map f: X -> Y which assigns to a polynomial p in X, the unordered
>>>> set of its roots (z_1,z_2,...,z_d). This map is certianly
>>>> continuous with respect to the natural topologies on X and Y.
>>>> Intuitively this says that the set of unordered roots (all of them)
>>>> is indeed a continuous function of the parameters of the
>>>> polynomials (but not the individual roots themselves).
>>>>
>>>> If, what you have been saying is in some way related to the above
>>>> than of course I agree, but I can't see how this fact can in any
>>>> way be useful in a computer program like Mathematica.
>>>>
>>>>
>>>> Andrzej Kozlowski
>>>>
>>>>
>>>> On 15 Jan 2007, at 07:35, Andrzej Kozlowski wrote:
>>>>
>>>>> I think I should have expressed myself  differently. So here it is
>>>>> again.
>>>>>
>>>>> I am sure that if you read and think about
>>>>>
>>>>> http://forums.wolfram.com/mathgroup/archive/2006/Dec/msg00496.html
>>>>>
>>>>>  you will certianly know what I have been talking about. I don't
>>>>> beleive you have done that.  I can't explain it any better or
>>>>> simpler. However, I can again state in a formal way what I am
>>>>> asserting to be true.
>>>>>
>>>>>  To talk of "continuity" of anything you have to specify three
>>>>> things. One is a topological space X - the source space. The
>>>>> second is a topological space Y - the target space. The third a
>>>>> map (function)  f: X -> Y. The statement of the theorem is:
>>>>> Let X = C^d -S be the space of all complex monic polynomials with
>>>>> the discriminant (the set of polynomials with a double root)
>>>>> removed. Let Y = C (the complex numbers). Then there cannot exists
>>>>> a continuous map f :X -> Y such that for any polynomial p in X, f
>>>>> (p) is a root of p.
>>>>>
>>>>> This is proved by Adam Strzebonski in the above link. The theorem
>>>>> of Vassiliev says that if d is a power of prime than you will need
>>>>> at lead d open Sets U_1,U_2, ..., U_d whose union is all of X,
>>>>> such that there is a map f_i: U_i -> C with the property that f(p)
>>>>> is a root of p.
>>>>>
>>>>> I can also prove the following. Let X= R^d-S - the space of real
>>>>> polynomials of degree d with the discriminant removed. Let Y=C.
>>>>> Then there does exist a continuous map f: X -> Y such that for
>>>>> each real polynomial p in X, f(p) is a root of p. (There are in
>>>>> fact many such maps, exactly d over each connected component of  
>>>>> X).
>>>>>
>>>>> I think this is as clear as it can be made. Now, of course it is
>>>>> quite possible that what you are trying to say is perfectly
>>>>> sensible and correct. However, to make it mathematics you must be
>>>>> able to make a formal statement like the above. An animation is
>>>>> not a substitute for this. I have no idea form you animation what
>>>>> is your X, what is your Y, and what is your function f that you
>>>>> claim can be a continuous function. An animation or a graphic can
>>>>> be useful once you only if they illustrate some formal mathematica
>>>>> notions like these.
>>>>>
>>>>> Andrzej Kozlowski
>>>>>
>>>>>
>>>>> On 14 Jan 2007, at 18:47, Andrzej Kozlowski wrote:
>>>>>
>>>>>> As I already suggested: read
>>>>>>
>>>>>> http://forums.wolfram.com/mathgroup/archive/2006/Dec/ 
>>>>>> msg00496.html
>>>>>>
>>>>>> and then think about what it says. (Obviously the issue concernst
>>>>>> each individual root being continuous).
>>>>>>
>>>>>> I think I have written about this as much as I am willing to do.
>>>>>>
>>>>>> Andrzej Kozlowski
>>>>>>
>>>>>> On 14 Jan 2007, at 17:58, David Park wrote:
>>>>>>
>>>>>>> Paul Abbot asked: "Again, ignoring root ordering, why
>>>>>>> isn't it possible for all these roots to maintain their identity
>>>>>>> and so
>>>>>>> be continuous functions of the parameter? And wouldn't such
>>>>>>> continuity
>>>>>>> be nicer than enforcing root ordering?"
>>>>>>>
>>>>>>> (I'm not certain if I exactly understand Paul's question. Does
>>>>>>> he mean that
>>>>>>> each individual root function, in the set of root functions,
>>>>>>> must be
>>>>>>> continuous, or does he allow global reindexing on the entire set
>>>>>>> to achieve
>>>>>>> continuity?)
>>>>>>>
>>>>>>> So, what exactly does your mathematical theorem say? Does it say
>>>>>>> that given
>>>>>>> a one-parameter finite order polynomial it is not possible to
>>>>>>> continuously
>>>>>>> reindex the set of root solutions so that the reindexed roots
>>>>>>> will vary
>>>>>>> continuously in the complex plane as a function of the
>>>>>>> parameter? Or that
>>>>>>> you can't do this when the polynomial contains a complex
>>>>>>> coefficient? If it
>>>>>>> says that, I don't believe it.
>>>>>>>
>>>>>>> It certainly is possible to arrange things so that the roots  
>>>>>>> vary
>>>>>>> continuously, and it can even be useful.
>>>>>>>
>>>>>>> It reminds me of a Groucho Marx quip, something about: "Are you
>>>>>>> going to
>>>>>>> listen to me or are you going to go by what you see in front of
>>>>>>> your eyes?"
>>>>>>>
>>>>>>> David Park
>>>>>>> djmp at earthlink.net
>>>>>>> http://home.earthlink.net/~djmp/
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> From: Andrzej Kozlowski [mailto:akoz at mimuw.edu.pl]
>>>>>>>
>>>>>>> I don't understand what you mean by "continuous enough" and  
>>>>>>> why you
>>>>>>> think and animation can "disprove" a mathematical proof?
>>>>>>>
>>>>>>> Please read the argument:
>>>>>>>
>>>>>>> http://forums.wolfram.com/mathgroup/archive/2006/Dec/ 
>>>>>>> msg00496.html
>>>>>>>
>>>>>>> It is very simple. Remember the point is that you cannot define
>>>>>>> such
>>>>>>> a function that will be continuous over the entire 6  
>>>>>>> dimensional (3
>>>>>>> complex dimensions) space of polynomials of degree 3 with  
>>>>>>> complex
>>>>>>> roots (we actually normally remove the discriminant from the
>>>>>>> space).
>>>>>>> You are using a smaller subspace ( you have just one complex
>>>>>>> parameter) and over a smaller subspace naturaly it is  
>>>>>>> possible to
>>>>>>> have a continuous root.
>>>>>>> If you look carefully at Adam's argument you will be easily  
>>>>>>> able to
>>>>>>> see what must go wrong over the entire space of complex cubics.
>>>>>>>
>>>>>>> This in fact is a good illustration of what a double edged  
>>>>>>> weapon
>>>>>>> graphics and animations are in studying mathematics: they can
>>>>>>> just as
>>>>>>> easily mislead your intuition and lead you to wrong conclusions
>>>>>>> as to
>>>>>>> right ones. Which is one reason why I think one should never
>>>>>>> rely too
>>>>>>> much on such tools when teaching mathematics. Proofs are  
>>>>>>> proofs and
>>>>>>> no number of "convincing animations" and "experimental  
>>>>>>> mathematics"
>>>>>>> can replace them.
>>>>>>>
>>>>>>> Andrzej Kozlowski,
>>>>>>>
>>>>>>> Department of Mathematics, Informatics and Mechanics
>>>>>>> Warsaw University, Poland
>>>>>>>
>>>>>>>
>>>>>>> On 14 Jan 2007, at 01:54, David Park wrote:
>>>>>>>
>>>>>>>> This looks continuous enough to me, with and without complex
>>>>>>>> coefficients.
>>>>>>>>
>>>>>>>> Needs["Graphics`Animation`"]
>>>>>>>> Needs["Graphics`Colors`"]
>>>>>>>>
>>>>>>>> frame[a_] :=
>>>>>>>>   Module[{roots = rootset[a], newroots, rootpermutations,
>>>>>>>> distances, pick,
>>>>>>>>       locations},
>>>>>>>>     If[memoryrootset === Null, newroots = roots,
>>>>>>>>       rootpermutations = Permutations[roots];
>>>>>>>>       distances =
>>>>>>>>         Plus @@ Abs[Part[roots, #] - memoryrootset] & /@
>>>>>>>> basepermutations;
>>>>>>>>       pick = Part[Position[distances, Min[distances], 1], 1,  
>>>>>>>> 1];
>>>>>>>>       newroots = Part[roots, Part[basepermutations, pick]]];
>>>>>>>>     memoryrootset = newroots;
>>>>>>>>     locations = {Re[#], Im[#]} & /@ newroots;
>>>>>>>>
>>>>>>>>     Show[Graphics[
>>>>>>>>         {LightCoral, AbsolutePointSize[15],
>>>>>>>>           Point /@ locations,
>>>>>>>>           Black,
>>>>>>>>           MapThread[Text[#1, #2] &, {Range[5], locations}],
>>>>>>>>
>>>>>>>>           Text[SequenceForm["a = ",
>>>>>>>>               NumberForm[a, {3, 2}, NumberPadding -> {" ",  
>>>>>>>> "0"}]],
>>>>>>>>             Scaled[{0.1, 0.95}], {-1, 0}]}],
>>>>>>>>
>>>>>>>>       AspectRatio -> Automatic,
>>>>>>>>       TextStyle -> {FontFamily -> "Courier", FontSize -> 12,
>>>>>>>>           FontWeight -> "Bold"},
>>>>>>>>       Frame -> True,
>>>>>>>>       PlotRange -> {{-3, 3}, {-3, 3}},
>>>>>>>>       PlotLabel -> SequenceForm["Continuous Roots of" ,
>>>>>>>> displaypoly],
>>>>>>>>       ImageSize -> 400]
>>>>>>>>     ]
>>>>>>>>
>>>>>>>> Case 1
>>>>>>>>
>>>>>>>> polynomial = x^5 - a x - 1 == 0;
>>>>>>>> displaypoly = polynomial /. a -> HoldForm[a];
>>>>>>>> rootset[a_] = x /. Solve[polynomial, x]
>>>>>>>>
>>>>>>>> memoryrootset = Null;
>>>>>>>> basepermutations = Permutations[Range[5]];
>>>>>>>> Animate[frame[a], {a, -6, 10, 0.25}]
>>>>>>>> SelectionMove[EvaluationNotebook[], All, GeneratedCell]
>>>>>>>> FrontEndTokenExecute["OpenCloseGroup"]; Pause[0.5];
>>>>>>>> FrontEndExecute[{FrontEnd`SelectionAnimate[200,
>>>>>>>> AnimationDisplayTime -> 0.1,
>>>>>>>>       AnimationDirection -> ForwardBackward]}]
>>>>>>>>
>>>>>>>> Case 2
>>>>>>>>
>>>>>>>> polynomial = x^5 + (1 + I) x^4 - a x - 1 == 0;
>>>>>>>> displaypoly = polynomial /. a -> HoldForm[a];
>>>>>>>> rootset[a_] = x /. Solve[polynomial, x];
>>>>>>>>
>>>>>>>> memoryrootset = Null;
>>>>>>>> basepermutations = Permutations[Range[5]];
>>>>>>>> Animate[frame[a], {a, -6, 10, 0.5}]
>>>>>>>> SelectionMove[EvaluationNotebook[], All, GeneratedCell]
>>>>>>>> FrontEndTokenExecute["OpenCloseGroup"]; Pause[0.5];
>>>>>>>> FrontEndExecute[{FrontEnd`SelectionAnimate[200,
>>>>>>>> AnimationDisplayTime -> 0.1,
>>>>>>>>       AnimationDirection -> ForwardBackward]}]
>>>>>>>>
>>>>>>>> But this is a combinatoric algorithm and if there are too many
>>>>>>>> roots it
>>>>>>>> might begin to get costly. But it is perfectly practical for  
>>>>>>>> these
>>>>>>>> examples.
>>>>>>>>
>>>>>>>> David Park
>>>>>>>> djmp at earthlink.net
>>>>>>>> http://home.earthlink.net/~djmp/
>>>>>>>>
>>>>>>>> From: Andrzej Kozlowski [mailto:akoz at mimuw.edu.pl]
>>>>>>>>
>>>>>>>> On 12 Jan 2007, at 11:05, Paul Abbott wrote:
>>>>>>>>
>>>>>>>>> In article <em8jfr$pfv$1 at smc.vnet.net>,
>>>>>>>>>  Andrzej Kozlowski <andrzej at akikoz.net> wrote:
>>>>>>>>>
>>>>>>>>>> What you describe, including the fact that the numbering or
>>>>>>>>>> roots
>>>>>>>>>> changes is inevitable and none of it is not a bug. There  
>>>>>>>>>> cannot
>>>>>>>>>> exist
>>>>>>>>>> an ordering of complex roots that does not suffer from this
>>>>>>>>>> problem.
>>>>>>>>>> What happens is this.
>>>>>>>>>> Real root objects are ordered in the natural way. A cubic can
>>>>>>>>>> have
>>>>>>>>>> either three real roots or one real root and two conjugate
>>>>>>>>>> complex
>>>>>>>>>> ones. Let's assume we have the latter situation. Then the
>>>>>>>>>> real root
>>>>>>>>>> will be counted as being earlier then the complex ones. Now
>>>>>>>>>> suppose
>>>>>>>>>> you start changing the coefficients continuously. The  
>>>>>>>>>> roots will
>>>>>>>>>> start "moving in the complex plane", with the real root
>>>>>>>>>> remaining on
>>>>>>>>>> the real line the two complex roots always remaining  
>>>>>>>>>> conjugate
>>>>>>>>>> (symmetric with respect to the real axis). Eventually they  
>>>>>>>>>> may
>>>>>>>>>> collide and form a double real root. If this double real root
>>>>>>>>>> is now
>>>>>>>>>> smaller then the the "original real root" (actually than the
>>>>>>>>>> root to
>>>>>>>>>> which the original real root moved due the the changing of  
>>>>>>>>>> the
>>>>>>>>>> parameter), there will be a jump in the ordering; the former
>>>>>>>>>> root
>>>>>>>>>> number 1 becoming number 3.
>>>>>>>>>> This is completely unavoidable, not any kind of bug, and I am
>>>>>>>>>> not
>>>>>>>>>> complaining about it. It takes only elementary  topology of
>>>>>>>>>> configuration spaces to prove that this must always be so.
>>>>>>>>>
>>>>>>>>> But is there a continuous root numbering if the roots are not
>>>>>>>>> ordered?
>>>>>>>>>
>>>>>>>>> What I mean is that if you compute the roots of a polynomial,
>>>>>>>>> which
>>>>>>>>> is a
>>>>>>>>> function of a parameter, then if you assign a number to each
>>>>>>>>> root,
>>>>>>>>> can
>>>>>>>>> you follow that root continuously as the parameter changes?  
>>>>>>>>> Two
>>>>>>>>> examples
>>>>>>>>> are presented below.
>>>>>>>>>
>>>>>>>>> Here is some code to animate numbered roots using the standard
>>>>>>>>> root
>>>>>>>>> ordering, displaying the root numbering:
>>>>>>>>>
>>>>>>>>>  rootplot[r_] := Table[ListPlot[
>>>>>>>>>    Transpose[{Re[x /. r[a]], Im[x /. r[a]]}],
>>>>>>>>>    PlotStyle -> AbsolutePointSize[10],
>>>>>>>>>    PlotRange -> {{-3, 3}, {-3, 3}},
>>>>>>>>>    AspectRatio -> Automatic,
>>>>>>>>>    PlotLabel -> StringJoin["a=", ToString[PaddedForm[Chop 
>>>>>>>>> [a], {2,
>>>>>>>>> 1}]]],
>>>>>>>>>    Epilog -> {GrayLevel[1],
>>>>>>>>>     MapIndexed[Text[#2[[1]], {Re[#1], Im[#1]}] & , x /. r 
>>>>>>>>> [a]]}],
>>>>>>>>>       {a, -6, 10, 0.5}]
>>>>>>>>>
>>>>>>>>> First, we have a polynomial with real coefficients:
>>>>>>>>>
>>>>>>>>>   r1[a_] = Solve[x^5 - a x - 1 == 0, x]
>>>>>>>>>
>>>>>>>>> Animating the trajectories of the roots using
>>>>>>>>>
>>>>>>>>>   rootplot[r1]
>>>>>>>>>
>>>>>>>>> we observe that, as you mention above, when the complex  
>>>>>>>>> conjugate
>>>>>>>>> roots
>>>>>>>>> 2 and 3 coalesce, they become real roots 1 and 2 and root 1
>>>>>>>>> becomes
>>>>>>>>> root
>>>>>>>>> 3. But, ignoring root ordering, why isn't it possible for  
>>>>>>>>> these
>>>>>>>>> roots to
>>>>>>>>> maintain their identity (I realise that at coelescence, there
>>>>>>>>> is an
>>>>>>>>> arbitrariness)?
>>>>>>>>>
>>>>>>>>> Second, we have a polynomial with a complex coefficient:
>>>>>>>>>
>>>>>>>>>   r2[a_] = Solve[x^5 + (1+I) x^4 - a x - 1 == 0, x]
>>>>>>>>>
>>>>>>>>> Animating the trajectories of the roots using
>>>>>>>>>
>>>>>>>>>   rootplot[r2]
>>>>>>>>>
>>>>>>>>> we observe that, even though the trajectories of the roots are
>>>>>>>>> continuous, the numbering switches:
>>>>>>>>>
>>>>>>>>>   2 -> 3 -> 4
>>>>>>>>>   5 -> 4 -> 3
>>>>>>>>>   3 -> 4 -> 5
>>>>>>>>>   4 -> 3 -> 2
>>>>>>>>>
>>>>>>>>> and only root 1 remains invariant. Again, ignoring root
>>>>>>>>> ordering, why
>>>>>>>>> isn't it possible for all these roots to maintain their  
>>>>>>>>> identity
>>>>>>>>> and so
>>>>>>>>> be continuous functions of the parameter? And wouldn't such
>>>>>>>>> continuity
>>>>>>>>> be nicer than enforcing root ordering?
>>>>>>>>>
>>>>>>>>> Cheers,
>>>>>>>>> Paul
>>>>>>>>>
>>>>>>>>> ______________________________________________________________ 
>>>>>>>>> ___
>>>>>>>>> ____
>>>>>>>>> _
>>>>>>>>> _
>>>>>>>>> Paul Abbott                                      Phone:  61 8
>>>>>>>>> 6488
>>>>>>>>> 2734
>>>>>>>>> School of Physics, M013                            Fax: +61 8
>>>>>>>>> 6488
>>>>>>>>> 1014
>>>>>>>>> The University of Western Australia         (CRICOS  
>>>>>>>>> Provider No
>>>>>>>>> 00126G)
>>>>>>>>> AUSTRALIA                               http://
>>>>>>>>> physics.uwa.edu.au/
>>>>>>>>> ~paul
>>>>>>>>
>>>>>>>>
>>>>>>>> In the cases of polynomials with real coefficients it is indeed
>>>>>>>> possible to define a continuous root. It is certianly not
>>>>>>>> possible to
>>>>>>>> do so for polynomials with complex coefficients. For a proof
>>>>>>>> see my
>>>>>>>> and Adam Strzebonski's posts in the same thread. Adam  
>>>>>>>> Strzebonski
>>>>>>>> gave a very elementary proof of the fact that a continuous root
>>>>>>>> cannot be defined on the space of complex polynomials of degree
>>>>>>>> d. I
>>>>>>>> quoted a more powerful but not elementary theorem of Vassiliev,
>>>>>>>> which
>>>>>>>> describes the minimum number of open sets that are needed to  
>>>>>>>> cover
>>>>>>>> the space of complex polynomials of degree d, so that there  
>>>>>>>> is a
>>>>>>>> continuous root defined on each open set. In fact, Vassiliev  
>>>>>>>> gives
>>>>>>>> the exact number only in the case when d is prime, in which  
>>>>>>>> case d
>>>>>>>> open sets are needed. For example, for polynomials of degree  
>>>>>>>> 3 at
>>>>>>>> least 3 sets are needed . If it were possible to define a
>>>>>>>> continuous
>>>>>>>> root, then of course only one set would suffice. In the case
>>>>>>>> when d
>>>>>>>> is not prime no simple formula seems to be known, but it is
>>>>>>>> easy to
>>>>>>>> prove that that the number is >1, (e.g. by means of Adam
>>>>>>>> Strzebonski's proof).
>>>>>>>>
>>>>>>>> Andrzej Kozlowski
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>>
>>
>


  • Prev by Date: Re: speed of multiplying polynomials
  • Next by Date: Decision tree algorithm
  • Previous by thread: Re: Re: Re: Re: Limit and Root Objects
  • Next by thread: Re: Re: Re: Re: Re: Limit and Root Objects