4
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ You probably mean to universally quantify that condition: $\forall (x, y) \in X^2 (f(A(x, y)) \subseteq A(f(x, y))$. $\endgroup$
    – Todd Trimble
    Oct 14, 2011 at 13:20
  • 1
    $\begingroup$ When writing $[−n,n]$, do you mean $\{-n,-n+1,\dots,n\}$ or the real interval? $\endgroup$ Oct 14, 2011 at 13:23
  • $\begingroup$ Did you check $n=1$? $\endgroup$ Oct 14, 2011 at 14:20
  • $\begingroup$ Andreas, see the counterexample below. I have the bad custom to check in vey few examples! I used (in my mental proof) a property which is not always true and I am trying to find a simple way to require it in order to keep the result interesting. $\endgroup$ Oct 14, 2011 at 14:38
  • 1
    $\begingroup$ 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/… $\endgroup$ Oct 14, 2011 at 16:42

2 Answers 2

6
$\begingroup$

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)$

$\endgroup$
4
  • $\begingroup$ 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.. $\endgroup$ Oct 14, 2011 at 14:16
  • 1
    $\begingroup$ 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 $). $\endgroup$
    – Dejan Govc
    Oct 15, 2011 at 16:50
  • $\begingroup$ this is a nice idea! Indeed I have thought about that condition as a discrete version of continuity. I will think about that. $\endgroup$ Oct 15, 2011 at 20:57
  • $\begingroup$ 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). $\endgroup$
    – Dejan Govc
    Oct 16, 2011 at 1:58
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Oct 14, 2011 at 13:23
  • $\begingroup$ 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. $\endgroup$ Oct 14, 2011 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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