Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
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. – alexx Jun 7 '12 at 5:30
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? – alexx Jun 7 '12 at 5:31

Your Answer


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.