Difference between revisions of "07081300/Class notes for Tuesday, October 30"
(→Complexity of FixedPoint search Algorithms) 
(→First Hour) 

Line 99:  Line 99:  
'''Definition 2'''  '''Definition 2'''  
−  If <math>Y\subset X</math>, a ''retract'' is a continuous  +  If <math>Y\subset X</math>, a ''retract'' is a continuous function <math>f:X\rightarrow Y</math> such that <math>r_Y = id_Y</math> 
Line 126:  Line 126:  
''Proof of Brouwer's Theorem''  ''Proof of Brouwer's Theorem''  
−  Assume not. We define a function from <math>D^n</math> to <math>S^{n1}</math> in the following way. Consider <math>x\in D^n</math> and consider <math>f(x)\in D^n</math>. These points are different by assumption. Consider the line from f(x) towards x. Let r(x) be the point on this line intersecting the boundary (choosing the point going from f(x) to x not the reverse). While we have not (but could) written down a precise formula for this, it is apparent that it is a smooth function from <math>D^n</math> to <math>S^{n1}</math> that is fixed on the boundary. Hence this is a retract, which is proved could not exist and thus establishing the contradiction.  +  Assume not. We define a function from <math>D^n</math> to <math>S^{n1}</math> in the following way. Consider <math>x\in D^n</math> and consider <math>f(x)\in D^n</math>. These points are different by assumption. Consider the line from f(x) towards x. Let r(x) be the point on this line intersecting the boundary (choosing the point going from f(x) to x not the reverse). While we have not (but could) written down a precise formula for this, it is apparent that it is a smooth function from <math>D^n</math> to <math>S^{n1}</math> that is fixed on the boundary. Hence this is a retract, which is proved could not exist and thus establishing the contradiction. 
===Second Hour===  ===Second Hour=== 
Revision as of 21:58, 7 November 2007

Contents 
Today's Agenda
Debts
A bit more about proper functions on locally compact spaces.
Smooth Retracts and Smooth Brouwer
Theorem. There does not exist a smooth retract .
Corollary. (The Brouwer Fixed Point Theorem) Every smooth has a fixed point.
Suggestion for a good deed. Tell Dror if he likes the Brouwer fixed point theorem, for he is honestly unsure. But first hear some drorpaganda on what he likes and what he doesn't quite.
Corollary. The sphere is not smoothly contractible.
Challenge. Remove the word "smooth" everywhere above.
Continuous Brouwer's FixedPoint Theorem Proof: Let be a continuous function. By Weierstrass theorem and since is compact there is a sequence of polynomials converging uniformly to f. By the smooth Brouwers' Theorem each has a fixed point . By the compactness of there is cluster point of which should be a fixed point of f.
Smooth Approximation
Theorem. Let be a closed subset of a smooth manifold , let be a continuous function whose restriction to is smooth, and let be your favourite small number. Then there exists a smooth so that and . Furthermore, and are homotopic via an small homotopy.
Theorem. The same, with the target space replaced by an arbitrary compact metrized manifold .
Tubular Neighborhoods
Theorem. Every compact smooth submanifold of has a "tubular neighborhood".
Entertainment
A student told me about this clip on YouTube (lyrics). Enjoy!
There is this one too but it is in Spanish. Romance of the Derivative and the Arctangent
Further Notes
With Brouwer's fixed point theorem you can prove amazing things
1) There are two antipodal points in the equator with the same temperature.
2) There are two antipodal points with the same temperature and the same pressure.
3) You can through three potatoes in the air and with just one swing cut all of them in half.
4) Every nonbold person has a swirl of hair or some other problem ordering their hair...
5) If you have a car with a loose antenna and you always go in your car in a trip exactly the same way every day then there is an initial position of the antenna such that it wont fall during your trip.
6) It doesn't matter how much you stir your coffee at least one point will be in the same position.
Constructive proof of Brouwer's FixedPoint Theorem
Several proves of Brouwer's theorem had been given. See A Constructive Proof of the Brouwer FixedPoint Theorem and Computational, R. B. Kellogg; T. Y. Li; J. Yorke
Most of them motivated by the fact that the first proof of the fixedpoint theorem was a nonconstructive indirect proof i.e. using reductio ad absurdum and hence using the excluded middle axiom. This axiom is rejected by Brouwer's itself paradigm of Foundations of Mathematics and the intuitionist school of which Brouwer is one of the founders.
Complexity of FixedPoint search Algorithms
The complexity of finding fixedpoint approximations is related to the search of solutions of the Sperner's Lemma (It ensures that a certain labelling rule on vertices of a simplicial partitioning of a simplex Sn guarantees the existence of a subsimplex with all vertices differently labelled.) Many algorithms for solving the Sperner's Lemma have exponential time. It was conjectured the existence of better approaches but Hirsch, Papadimitriou and Vavasis proved lower exponential bounds for this problem in Exponential lower bounds for finding Brouwer fixed points. J.Complexity, 5:379–416, 1989.
References
Typed Class Notes
The notes below are by the students and for the students. Hopefully they are useful, but they come with no guarantee of any kind.
First Hour
Claim 1:
Consider to be continuous and proper and Y being locally compact. Then it is closed.
Definition 1
A set (X a topological space) is called locally closed if every has a neighbourhood U such that is closed in U.
Claim 2:
Locally closed closed.
Proof of Claim 2:
() is tautological
() If then such that is closed in U so is open in U and hence also in X. Thus, x has a neighbourhood in so is open and thus F is closed.
Proof of Claim 1:
To be repeated next class.
Definition 2
If , a retract is a continuous function such that
Theorem 1
There is no smooth retract where
Proof of Theorem 1
Assume not. Then such that r is a smooth retract. By Sard's theorem we can find a non critical value y of r. So is a submanifold (with boundary) of dimension 1 of .
Previously we proved that such things were manifolds but only if they were without boundary. The proof with boundary works in exactly the same was, that is, use the theorem that immersions looks like projections in only this time allow neighborhoods to be homeomorphic to the half space .
Now the classification theorem for 1 dimensional manifolds shows that must be homeomorphic to a closed interval (as it has at least one boundary point at y) and hence it must also have a second boundary point. But and hence this second boundary point must be some other point y' on . But such points map to themselves by assumption so . This establishes the contradiction.
Theorem 2
Brouwer's Fixed Point Theorem
Consider a function , f being smooth. Then such that f(p)=p, i.e., there exists a fixed point of the function.
Proof of Brouwer's Theorem
Assume not. We define a function from to in the following way. Consider and consider . These points are different by assumption. Consider the line from f(x) towards x. Let r(x) be the point on this line intersecting the boundary (choosing the point going from f(x) to x not the reverse). While we have not (but could) written down a precise formula for this, it is apparent that it is a smooth function from to that is fixed on the boundary. Hence this is a retract, which is proved could not exist and thus establishing the contradiction.
Second Hour
Theorem 3
Let A be a closed subset of M and let be continuous such that is smooth. Then, such that and and g is smooth.
Corollary 1
This implies that there doesn't not exist such continuous retracts which in turn implies the continuous version of Brouwer's Theorem.
Proof of theorem 3
The idea is as follows: It is obviously locally true and hence it is globally true. Lets justify this.
First off, by "locally true" what we mean is that such that such that the rest of the conditions are true.
Why is this locally true? Well, if , by smoothness of smooth extension g of to a neighborhood of x. Lets take this extension. Now if then let y = f(x) and set . This works in a neighborhood of x.
We now want to extend this to being globally true. To do this we use a partition of unity to assemble the local property to a global property.
Consider our previous cover . such that supp and .
Set . Smoothness is obvious.
Now, if then
Now, if then
Q.E.D
We can now generalize the previous theorem with the following theorem.
Theorem 4
Let N be a compact metrized manifold (i.e. we have actually specified a metric not just claimed one can exist which we always know for manifolds). Also let be closed in the manifold. Let f be a continuous function such that is smooth. Let then a smooth such that
1)
2) .
Proof of Theorem 4
By the Whitney embedding theorem we let N be a submanifold of . We consider our function f from M to N but thought of as going into . By the previous theorem we can approximate this by a smooth function g' going into . The problem is that this may not take points actually onto N but near by it in the ambient space. We then want to construct from g' a smooth function g that actually goes into N as we would want. To do this we will use the idea of tubular neighbourhoods.
Definition 3
Let N be a (compact) submanifold of . Then the normal bundle of N in is where from an immersion (also an embedding as N is compact).
is a manifold of dimension n+ (kn) = k. We of course would need to verify that this is in fact a manifold.
Theorem 5
Tubular Neighbourhood Theorem
is a smooth homeomorphism of with for small .