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

I have casually almost (i.e. up to details that shoud work) proved the following discrete version of Brouwer's fixed point theorem. I should have obtained this result as a corollary of quite complicated things and I do not understand if the result is trivial and can be easily proved directly or it deserves to be stressed. I would like to hear your opinion about that.

Let $n\geq1$ be a fixed integer and denote by $X=[-n,n]^2\subseteq\mathbb Z^2$. Given $(x,y)\in X$ I denote by $A(x,y)$ the set formed by the following at most five points: $(x-1,y),(x,y),(x+1,y),(x,y-1),(x,y+1)$. At most means that if one of those points does not belong to $X$, I will not consider it.

The result would be: let $f:X\rightarrow X$ such that for all $(x,y)\in X$ one has $f(A(x,y))\subseteq A(f(x,y))$. Then $f$ has a fixed point.

Is that trivial?

Thank you in advance,

Valerio

share|improve this question
1  
You probably mean to universally quantify that condition: $\forall (x, y) \in X^2 (f(A(x, y)) \subseteq A(f(x, y))$. –  Todd Trimble Oct 14 '11 at 13:20
1  
When writing $[−n,n]$, do you mean $\{-n,-n+1,\dots,n\}$ or the real interval? –  Emil Jeřábek Oct 14 '11 at 13:23
1  
yes, thanks. I ve just corrected –  Valerio Capraro Oct 14 '11 at 13:24
    
Did you check $n=1$? –  Andreas Thom Oct 14 '11 at 14:20
1  
Actually, I am quite convinced that I have misunderstood my own property! The right formulation of my application is little different. If you are interested, I have opened another topic: mathoverflow.net/questions/78147/… –  Valerio Capraro Oct 14 '11 at 16:42

2 Answers 2

up vote 6 down vote accepted

I believe the following is a counter-example:

$f: \lbrace -1,0,1\rbrace^2 \to \lbrace -1,0,1\rbrace^2$

$\forall x:$

$ f(-1,x) = (1,x)$

$f(0,x)=(1,x)$

$f(1,x)=(0,x)$

share|improve this answer
    
Well I agree that this is a counter-example and I have also understood where was my mistake (the devil is in the details!). I am trying to add a simple condition in order to make the details working.. –  Valerio Capraro Oct 14 '11 at 14:16
1  
I am wondering ... Maybe it is still possible to get a version of Brouwer's fixed point theorem. The condition $f(A(x,y))\subseteq A(f(x,y))$ looks a lot like continuity. If you equip $X$ with the Euclidean metric, it just says that whenever $d(x,y) \leq 1$ it follows that $d(f(x),f(y)) \leq 1$. My intuition suggests that it should still be possible to prove that there is an almost-fixed point $x_0$ in the sense that $d(f(x_0),x_0) \leq 1$. This certainly works for the one-dimensional analog of the problem ($X = \lbrace 1,2, ..., n \rbrace $). –  Dejan Govc Oct 15 '11 at 16:50
    
this is a nice idea! Indeed I have thought about that condition as a discrete version of continuity. I will think about that. –  Valerio Capraro Oct 15 '11 at 20:57
    
I have thought about it some more and $d(f(x_0),x_0)\leq 1$ won't always work, but I am quite sure you can prove that there always exists a point $x_0$ such that $d(f(x_0),x_0)\leq C$ where $C$ is a constant depending only on the dimension $d$. This is because you can extend your function by piecewise linear interpolation to a continuous function on $[-n,n]^d \subseteq \mathbb{R}^d$ and then use the original Brouwer fixed point theorem obtaining a fixed point. Now choose the closest lattice point. This point has the property we seek (this follows from your property and piecewise linearity). –  Dejan Govc Oct 16 '11 at 1:58
    
It is a beautiful problem, I must say. –  Dejan Govc Oct 16 '11 at 1:59

Wouldn't the Tietze extension theorem (with range $X$) show that any permutation of $A$ extends to a function $f$?

share|improve this answer
    
I don't understand: in that case the extension has a fixed point but it might not belong to $X$. Indeed it is not true that any permutation of $X$ has a fixed point. Am I missing something? –  Valerio Capraro Oct 14 '11 at 13:23
    
Yes, that was my point. As originally stated, I don't believe what you are hoping for is true. But I see that you have edited your question in the meantime, and I'm not sure what you are asking any more. –  Carl Offner Oct 14 '11 at 13:25

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.