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

• To: mathgroup at smc.vnet.net
• Subject: [mg72787] Re: [mg72728] Re: [mg72668] Re: [mg72644] Re: [mg72620] Re: Limit and Root Objects
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Sat, 20 Jan 2007 02:24:25 -0500 (EST)

```I hope my paraphrase of Adam Strzebonski's proof has made it easier
for those who are interested to follow, but since I feel a little
embarrassed as an algebraic topologist that I did not notice this
topological proof immediately myself and had to rely on help form an
algebraic geometer  I would like to atone for this by providing a
topological interpretation of Adam's argument. While this is not
directly relevant to Mathematica, I think it can be quite
illuminating for anyone interested in solutions of polynomial
equations (and in particular in the question why we need things like
Root objects). Besides it shows that even elementary topology can
teach us some quite useful things.

Let me start with an object, which I think must be the most familiar
to the general public and non-trivial, object from algebraic topology
- the Moebius band. In fact, the Moebius band is very closely related
to Adam's proof. The Moebius band can easily be contructed by anyone:
all you need to do is to cut a rectangular piece of paper and then
glue two opposite sides. If you glue them in the straight forward way
you will get a topological space called the (cartesian) product of a
circle and an interval. If you give the band a twist before gluing
the ends you will get a "twisted product" or a Moebius band; let's
call it M. Now, both the untwisted product and the twisted product
can be continuously mapped ("projected") onto a circle X so that the
inverse image of each point on a circle is an interval. This kind of
projection p: M -> X is called a fibre bundle; in the untwisted case
you have a trivial fibre bundle and in the twisted case one that is
only "locally trivial". The inverse images p^(-1)(x) of the points x
on the circle X are called "fibres" - note that as you go over a
circle the fibres of the trivial bundle all "point in the same
direction" but the fibres of the twisted one keep turning until when
you travel all the way round the circle you find that the fibre has
turned through 180 degrees and is pointing the opposite way. The
projection map of the twisted product onto a circle admits a
continuous section, that is a map s: X-> M such that p(s(x)) == x for
each point x in X. For example for each x in X you take as s(x) the
midpoint of the interval that is the fibre over x. Of course the same
is true for the non-twisted product. But now, let's remove from the
twisted (and the untwisted) product all the points except those on
the boundary. In the case of the untwisted product you will get a
pair of disjoint circles. But in the case of the twisted product you
will get a single twisted circle. This twisted circle is mapped by
the restriction of the projection map p onto the original base circle
X forming a so called non-trivial double covering. It has the
property that the fibre over any point in X now consists of just two
points. The same of course is true for the trivial covering that maps
two disjoint circle onto the original base circle X. However, the
trivial covering admits of course two continuous sections: you can
map the points on the base circle either into one or the other of the
circles that map onto it. On the other hand, for the non-trivial
covering no such continuous section can exist. If you try to
construct one by starting at a point of the base circle and going
around it you will find that by the time you arrive at that same
point having traversed the entire circle you will be on the wrong
sheet of the covering. Such connected non-trivial coverings of a
circle exist for any positive integer n, there are connected double
coverings, triple coverings and there are connected non-trivial d-
fold coverings. And it is this fact that lies behind Adam's proof.

In Adam's proof one first constructs a "circle" in the space of
polynomials with the discriminant removed. Not just any circle will
do: you have to choose a circle which has the property that it cannot
be continuously contracted to a point without passing through a
polynomial (remember, the points of the space are all polynomials of
degree d) which has multiple roots. The roots of the polynomials that
form the points of this circle together make up a "twisted d-fold
covering" over this circle, and this covering, as we have seen
earlier does not admit a continuous section. If you could choose
continuously a root of each polynomial on the circle than of course
you would have such a section - and this is impossible.

Andrzej Kozlowski

On 17 Jan 2007, at 12:00, 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,
>> 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
>>> 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
>>>
>>> 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
>>>
>>> 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.
>>>>>
>>>>>
>>>>> 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
>>>>> 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:
>>>>>
>>>>>>
>>>>>> 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).
>>>>>>
>>>>>>
>>>>>> 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
>>>>>>>
>>>>>>> David Park
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> 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?
>>>>>>>
>>>>>>>
>>>>>>> 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
>>>>>>> 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
>>>>>>>>
>>>>>>>> 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,
>>>>>>>>> [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
>>>>>>>> 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: NIntegrate and the number of grid points used
• Next by Date: Re: a old post again
• Previous by thread: Re: Re: Re: Re: Limit and Root Objects
• Next by thread: Re: FullSimplify and HypergeometricPFQ