Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given $\epsilon > 0$ and $f : [0, 1]^{\omega} \rightarrow [0, 1]^{\omega}$, can we find $x$ such that $x \in \textrm{Conv}\left( \left\{f(y) : ||y - x||_{\infty} < \epsilon\right\}\right)$?

In finite dimensions this is straightforwardly equivalent to Brouwer's fixed point theorem. In the infinite dimensional case they are not equivalent, and I don't even know whether to expect the claim to be true or false (I was expecting it to be much more straightforward to settle).

I would actually be happy to solve the problem for the simpler case of maps $f : [0, 1]^{\omega} \rightarrow \left\{0, 1\right\}^{\omega}$, since I'm imagining each coordinate of $f$ as returning the truth of a certain predicate applied to $x$. And we could just as well work with the discrete setting, of $f : \left\{0, 1, \ldots, m\right\}^{\omega} \rightarrow \left\{0, m\right\}^{\omega}$.

I'm aware of this result, but it doesn't seem to help very much here.

Edit: I would actually be happy to find an $x$ which isn't separated from $\left\{ f(y) : ||y - x||_{\infty} < \epsilon\right\}$ by any hyperplane parallel to the coordinate axes. This seems like it should be much easier.

share|improve this question
    
Why do you take the convex hull? The question is to determine whether the set is empty or non-empty and the answer to this question doesn't change after taking the convex hull, right? –  Qiaochu Yuan Oct 25 '13 at 0:25
    
I'm trying to find $x$ which is in the convex hull of its neighbors' images. If the function $f$ is very messy, there is no way that $x$ will actually be the image of one of its neighbors, so we definitely need to take the convex hull. –  Paul Christiano Oct 25 '13 at 1:34
    
Oh, I see. Sorry, I misread. I thought you were taking the convex hull of the $\epsilon$-fixed points. –  Qiaochu Yuan Oct 25 '13 at 2:37
add comment

2 Answers

up vote 1 down vote accepted

In fact the property fails on any non-compact closed convex set $K$ of a Banach space : there exists a Lipschitz map $f:K\to K$ with no approximate fixed point, that is $\inf_{x\in K}\|f(x)-x\|=\delta > 0$ (See Geometric Nonlinear Functional Analysis- Part 1 by Benyamini and Lindenstrauss, Thm 3.4 ). If we take $\epsilon:=\delta/\mathrm{lip}(f)$ there holds $\operatorname{co}f\big(B(x,\epsilon)\big)\subset B\big(f(x), \delta\big)\not\ni x ,$ for any $x\in K$.

share|improve this answer
    
This is surely too much to ask, but do you know what happens if every coordinate of $f$ is continuous in the product topology, except for one of them? Intuitively there are two kinds of obstructions from infinite dimension, and it seems like this eliminates one of them (we no longer have to intersect infinitely many sets in a non-compact space). I don't understand the counterexamples to the approximate fixed point property well enough to see whether they work in this setting. (For my purposes, this case would be almost as good as the whole thing.) –  Paul Christiano Oct 30 '13 at 3:29
    
But will you make at least some weaker assumption on the special coordinate? (something is needed, otherwise $f$ could be a trivial map that maps everything to $(0,0,\dots)$ but the point $(0,0,\dots )$ itself, sent to $(1,0,0,\dots )$, with no fix point. Every coordinate of $f$ is constant but the first one, which is discontinuous). –  Pietro Majer Nov 4 '13 at 11:15
add comment

In fact there is a Lipschitz map which has no approximate fixed point in this sense.

Take some Lipschitz retraction $f$ from the interior of the cube into its exterior, and take $\epsilon$ much smaller than $1 /$ the Lipschitz constant of $f$. Consider the map $g$ which sends $x$ to its reflection about the point $(1/2, 1/2, \ldots)$.

Then $g$ has no fixed point in my sense. Any point close to a boundary can't be a fixed point because $f$ fixes the boundaries (so $g$ moves them far). So if $x$ is a fixed point, it must be strictly in the interior (it has to be pretty far from the exterior because $f$ is Lipschitz). Since $f$'s image is the exterior, there is a coordinate $i$ with $f(x)_i \in [-1, -1 + \epsilon] \cup [1 - \epsilon, 1]$. By the Lipschitz property $f(y)_i$ must be in one of these two intervals for all $y$ in the $\epsilon$-neighborhood of $x$. But $x_i$ is in $(-1 + \epsilon, 1 + \epsilon)$, since $x$ was far in the interior of the cube. Contradiction.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.