Let $f$ be a function that maps $\mathbb{Z}^2$ to $\mathbb{R}$ and consider the operator $T$ which replaces the value of $f$ at $(i,j)$ by the average of the values of $f$ at its four neighbors (left, right, down, up): $$ Tf(i,j) = \frac{f(i-1,j) + f(i+1,j) + f(i,j-1) + f(i,j+1)}{4}.$$ The discrete-version of Liouville's theorem say that the equation $$ Tf = f$$ does not have any solutions $f$ which are bounded.

My question is whether its possible to prove this by demonstrating that $T$ is a contraction mapping in some sense.

Specifically, let $\mathbb{S}$ be the set of bounded $f: \mathbb{Z}^2 \rightarrow \mathbb{R}$ with the equivalence relation $f = g$ whenever $f-g$ is a constant. Is there a metric on $\mathbb{S}$ with respect to which $T$ is a strict contraction?

Note that is related, but not identical with, my other question. In particular, a positive answer to this question would likely imply an answer to that question as well.


No. If such a metric existed then $T^2$ would also be a contraction, hence would also have a unique fixed point (namely the equivalence class of constant functions), which it doesn't: $T^2$ fixes every function such that $f(i, j) = g(i + j \bmod 2)$ for some $g$, and there are infinitely many equivalence classes of such functions.

(More generally, in order for such a metric to exist for a general set map $T : X \to X$ it is necessary that $T^n$ has a unique fixed point for all $n \in \mathbb{N}$. As it turns out, this is sufficient.)

  • $\begingroup$ Very nice. Actually, I had meant $Tf(i,j)$ to include $f(i,j)$ besides the four neighboring points, so that $T^2$ (and higher powers) all have a unique fixed point. The inverse fixed point theorem you cite then implies such a metric exists. $\endgroup$ – morgan Jun 7 '12 at 5:30
  • $\begingroup$ I hope you don't mind a follow up question: for the case I mentioned in the previous comment (i.e., $Tf(i,j) = (1/5) (f(i,j) + f(i+1,j) + f(i-1,j) + f(i,j-1) + f(i,j+1)$) is there an explicit expression for the metric that turns $T$ into a contraction? $\endgroup$ – morgan Jun 7 '12 at 5:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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