Can we actually find any fixed points with Brouwer's theorem? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T08:40:18Z http://mathoverflow.net/feeds/question/105883 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105883/can-we-actually-find-any-fixed-points-with-brouwers-theorem Can we actually find any fixed points with Brouwer's theorem? Vidit Nanda 2012-08-29T21:39:32Z 2012-08-31T19:12:10Z <h2>Background</h2> <p>At the risk of greatly oversimplifying matters, let me state a heuristic from Granas and Dugundji's beautiful <a href="http://www.amazon.com/Fixed-Point-Theory-Andrzej-Granas/dp/0387001735" rel="nofollow">book</a>: <em>fixed point theorems fall into two broad categories</em>. The first class is usually functional analytic and imposes strong conditions on the <em>map</em> $f:X \to X$ whereas the second class is usually algebraic topological and imposes strong conditions on the <em>space</em> $X$ itself.</p> <p>A typical example of the first class of theorems is the <a href="http://en.wikipedia.org/wiki/Banach_fixed-point_theorem" rel="nofollow">fixed point theorem of Banach</a>. While the spaces it applies to are fairly general (complete metric spaces), the function must have a Lipschitz constant strictly less than $1$. On the other hand, <a href="http://en.wikipedia.org/wiki/Brouwer_fixed-point_theorem" rel="nofollow">Brouwer's theorem</a> falls into the second class. Any continuous map works, but the domain must be a compact and convex subset of Euclidean space (originally a disk). Of course, both these theorems have been <em>vastly</em> generalized from the versions that I am stating here.</p> <h2>Question</h2> <p>One fundamental advantage of the Banach theorem is that it actually provides a recipe for converging to the fixed point as part of the standard proof: just start at an initial point and iterate. The proofs of the Brouwer theorem that I have seen do no such thing. The best known proof (I think) is the one by contradiction: assuming the domain is a disk, if $f(x)$ and $x$ are always distinct then the ray from $f(x)$ through $x$ to the boundary of said disk provides a deformation-retraction from the disk to its boundary, aha!</p> <p>Here is my question:</p> <blockquote> <p>Is there any way to actually find a fixed point when using Brouwer's theorem?</p> </blockquote> <h2>A Possible Idea</h2> <p>One scheme that unfortunately fails is as follows. Consider the sequence of iterates $f^n(x)$ for $n \in \mathbb{N}$ and any initial $x$ in the domain. We have an infinite sequence in a compact set, and hence a convergent subsequence, so the limit point is a candidate. This won't work since <strong>a</strong>) we haven't used convexity at all, and <strong>b</strong>) one may just be converging to a periodic orbit of $f$. </p> <p>Sorry if this is too half-baked or elementary, but I have reduced an annoying problem to finding (any!!) fixed point of a map on the unit disk in $\mathbb{R}^n$. But this infernal map is absolutely hideous and in no way satisfies the hypotheses for the Banach fixed point theorem, so I have to use Brouwer's theorem. There is also no Earthly hope of discretizing the domain and approximating this monstrosity by a simplicial map. If the question sounds desperate, that's because it is... All help is greatly appreciated.</p> <h2>Update</h2> <p>Thanks to all the answerers and commenters for various helpful and constructive suggestions. If either of the articles referenced by Aaron or Willie turn out to contain directly useful information, I will write a brief summary of the relevant content here.</p> http://mathoverflow.net/questions/105883/can-we-actually-find-any-fixed-points-with-brouwers-theorem/105884#105884 Answer by Johannes Hahn for Can we actually find any fixed points with Brouwer's theorem? Johannes Hahn 2012-08-29T21:43:30Z 2012-08-29T21:43:30Z <p>There is a constructive version of Brouwer's theorem via Sperner's theorem. This gives an actual way to compute fixed points. (Not a very efficient one, granted, but an algorithm nonetheless)</p> http://mathoverflow.net/questions/105883/can-we-actually-find-any-fixed-points-with-brouwers-theorem/105888#105888 Answer by Aaron Meyerowitz for Can we actually find any fixed points with Brouwer's theorem? Aaron Meyerowitz 2012-08-29T22:54:25Z 2012-08-29T22:54:25Z <p>There are other constructive proofs <a href="http://www.jstor.org/stable/2156239" rel="nofollow">Here</a> is an article with a method which , according to the authors, does not require a simplicial decomposition,is similar to Newton's method, and has been applied up to dimension $60$. </p> http://mathoverflow.net/questions/105883/can-we-actually-find-any-fixed-points-with-brouwers-theorem/105889#105889 Answer by Will Sawin for Can we actually find any fixed points with Brouwer's theorem? Will Sawin 2012-08-29T22:54:33Z 2012-08-29T22:54:33Z <p>This is perhaps silly, but the obvious algorithm for $\mathbb R^1$ is to compute $f(1/2)$. If it's larger than $1/2$, compute $f(3/4)$. If it's smaller, compute $f(1/4)$. Keep going dyadically and you will compute the binary digits of a fixed point to an arbitrary level of accuracy. But it's very unclear how to generalize this.</p> <p>If all we can do is sample the function at finitely many points, it should be impossible to guess the location of a fixed point with any degree of accuracy. To see this, take a function with a single fixed point, like $f(x)=.99x$. Take a long but very thin tube containing that point and another point, and change the function on the tube so that the other point is now the fixed point.</p> <p>Since the measure of the tube can be made arbitrarily small, and the tube can be chosen to avoid any finite set, any strategy for sampling finitely many points will, with high probability, be unable to distinguish the function from $.99x$ and so will be unable to guess the location of the fixed point.</p> <p>Thus, you need some way to show the function is not malevolent, like some understanding of the $\epsilon$s and $\delta$s in the function's uniform continuity, or maybe a probabilistic model of a random function.</p> http://mathoverflow.net/questions/105883/can-we-actually-find-any-fixed-points-with-brouwers-theorem/105909#105909 Answer by Willie Wong for Can we actually find any fixed points with Brouwer's theorem? Willie Wong 2012-08-30T07:31:48Z 2012-08-30T07:31:48Z <p>(This answer is in a similar direction to that of Johannes Hahn's and to Will Sawin's)</p> <p>I think (I am not 100% sure) that one may get away without doing the triangulation and simplicial approximation (of the "usual" Sperner's Lemma proof) if you take the approach using van Maaren's version of Sperner's Lemma (there is an outline of the proof in Schechter's <em>Handbook of Analysis and its Foundations</em> with some typos). </p> <p>One first obtains the van Maaren's version of Sperner's Lemma, which is purely combinatorial/order theoretical and is a constructive statement on finite sets (the proof just gives the algorithm). </p> <p>Using that one gets an approximate fixed point statement (roughly speaking for every $\epsilon$ you find a point that is $\epsilon$ away from being a fixed point). To get the approximate fixed point at size $1/k, k\in\mathbb{N}$ you only need to consider <em>the</em> finite subset formed by the lattice of spacing $1/(3kn)$ where $n$ is the dimension. In this step the convexity comes into play (but not continuity; compactness only enters via Heine-Borel as boundedness). </p> <p>Note that this does not require being able to approximate the function $f$: it just requires being able to evaluate $f(x)$ for given $x$ to arbitrary accuracy (in particular you need to know whether the $i$-th coordinate of $f(x)$ is less than or equal to the $i$-th coordinate of $x$). </p> <p>Then you take limit as $k\to \infty$ (and here continuity and compactness are used, by convexity is no longer relevant) (the practicality of this last step, of course, is questionable; and as Noam Elkies and Michael Greinecker alluded to, this method gives no rate of convergence, so cutting off the computation at a finite $k$ doesn't guarantee that you are near a bona fide fixed point at all). </p> http://mathoverflow.net/questions/105883/can-we-actually-find-any-fixed-points-with-brouwers-theorem/106011#106011 Answer by Quinn Culver for Can we actually find any fixed points with Brouwer's theorem? Quinn Culver 2012-08-31T01:36:03Z 2012-08-31T01:36:03Z <p>Here's a paper worth checking out: <a href="http://arxiv.org/abs/1206.4809" rel="nofollow">http://arxiv.org/abs/1206.4809</a>. It essentially shows that finding a fixed point of a continuous $f:[0,1]^{n} \to [0,1]^{n}$ is as hard as finding a point in a nonempty connected closed subset of $[0,1]^{n}$.</p> <p>They also mention (after Theorem 1.1) that the Brouwer fixed point theorem is non-constructive.</p> http://mathoverflow.net/questions/105883/can-we-actually-find-any-fixed-points-with-brouwers-theorem/106044#106044 Answer by Moe Hirsch for Can we actually find any fixed points with Brouwer's theorem? Moe Hirsch 2012-08-31T14:59:16Z 2012-08-31T19:12:10Z <p>The paper "Exponential lower bounds for finding Brouwer fixed points"</p> <p><em>Addendum by original poster:</em> It was non-trivial to find a copy of this great paper of Hirsch, Papadimitriou and Vavasis. It does answer my general question quite clearly: finding Brouwer fixed points is exponentially hard in the worst case no matter what algorithm you use. <a href="https://dl.dropbox.com/u/74531549/HPVBrouwer.pdf" rel="nofollow">Here</a> is a link to this paper for all those who are interested and don't want to run into many, many pay-walls. I will take it down in a few days. -VN</p>