Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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: $$ Tf(i,j) = \frac{f(i-1,j) + f(i+1,j) + f(i,j-1) + f(i,j+1)}{4}.$$ Now we know that the equation $$ Tf = f$$ does not have any solutions $f$ that are bounded. I'm looking for a stronger version of this fact. In particular, I want to know if there is a quantitative statement to the effect that if $$\inf_{(i,j) \in \mathbb{Z}^2} f(i,j) = 0 , ~~~~~~\sup_{(i,j) \in \mathbb{Z}^2} f(i,j) = 1, ~~~~~~~~~~~~~~~(*)$$ then $Tf$ is in some sense far from $f$?

One naive way to make this work would be to define $$ d_{\infty}(f,g) = \sup_{(i,j) \in \mathbb{Z}^2} |f(i,j) - g(i,j)| $$ and consider $$ \inf_f d_{\infty}(f,Tf) $$ where the infimum is taken over all $f$ satisfying $(*)$. But it isn't hard to see that this infimum is $0$, so this attempt fails. Perhaps a more sophisticated notion of distance would make this sort of statement true?

share|improve this question
    
what is $x_i$. Moreover all norms in $\mathbb{R}^2$ are equivalent so what do you mean by more sophisticated notion of distance? –  Alex R. Jun 5 '12 at 23:48
    
I rewrote the question is a more explicit and clearer way. –  alex Jun 6 '12 at 0:07
    
It seems that $d_1(f,g)=\sum_{(i,j)\in\mathbb Z^2}|f(i,j)-g(i,j)|$ would work, in the sense that $d_1(f,Tf)\ge c>0$ for all $f$ with normalization (*). "Proof by example": if $f(i,j)=(1-\epsilon\max(|i|,|j|))^+$, then $|f-Tf|$ is of size about $\epsilon$ on the boundary (and diagonals) of a square of size $1/\epsilon$. So the $\ell_1$ norm appears to be the right thing to use here. I don't have a proof, but could try if you are interested in this kind of result. –  user31373 Jun 9 '12 at 23:51

3 Answers 3

If an $L^2$ treatment is feasible one could try Fourier transform. On a purely formal level any $f:\ {\mathbb Z}^2\to{\mathbb C}$ has a Fourier transform $\hat f:\ T^2\to {\mathbb C}$ which is nothing else but the doubly periodic function $$f(x,y):=\sum_{k,l} f(k,l)e^{i(k x+ly)}\qquad\bigl((x,y)\in ({\mathbb R}/(2\pi))^2\ \bigr)\ .$$ One easily checks that $$\widehat{Tf}(x,y)={1\over2}(\cos x+\cos y)\hat f(x,y)\ ,$$ so that in the "Fourier domain" the "convolution operator" $T$ acts as multiplication with a simple function. As $f$ was assumed real its Fourier transform has certain symmetry properties which might simplify the resulting expressions.

share|improve this answer

There are no non-constant bounded harmonic functions on $\mathbb{Z}^d$. This is referred to as the Liouville property (more generally for other types of graphs). You can see some proofs here:

A stronger version of discrete "Liouville's theorem"

http://mathoverflow.net/questions/51949/liouville-property-in-zd

share|improve this answer
4  
Thanks for the links to various proofs of this fact - perhaps there is something there that I'll find useful. Note, however, that I explicitly said in the body of my question that I knew this and asked for the possibility of stronger versions of this fact. –  alex Jun 6 '12 at 0:21

It's more convenient to consider $Tf - f$, which is just a scaled version of the discrete Laplacian $\nabla^2 f$. Here is a simple lower bound for the one-dimensional version of the problem. Sorry if you already know about this; I couldn't tell from the statement of your question.

In one dimension, let the first and second finite differences be $\nabla f_{i+1/2}=f_{i+1}-f_i$ and $\nabla^2 f_i=\nabla f_{i+1/2}-\nabla f_{i-1/2}=f_{i-1}-2f_i+f_{i+1}$, and the corresponding maximum norms be $F=\lVert f\rVert_\infty$, $G=\lVert\nabla f\rVert_\infty$, and $H=\lVert\nabla^2f\rVert_\infty$. The difference you care about, $Tf-f$, is just $2\nabla^2f$ in this one-dimensional case. Then one can show that $$f_{i+n} \ge f_i + n\nabla f_{i+1/2} - \frac{n^2}2H.$$ This is simply an expression of the fact that if your acceleration is bounded, you will keep going at least a certain distance even when slamming on the brakes. Let's take $i$ at the point where $\nabla f_{i+1/2}$ attains its maximum absolute value $G$. Given the discrete nature of the domain, the maximum of the right-hand side is attained within $\frac12$ unit of $n=G/H$, where we get $$f_{i+n}\ge f_i+\frac{G^2}{2H}-\frac H8\ge f_i+\frac{G^2}{2H}.$$ Of course, $f_{i+n}-f_i\le2F$, which immediately implies that $H\ge G^2/4F,$ or returning to conventional notation, $$\lVert\nabla^2f\rVert_\infty \ge \frac{\lVert\nabla f\rVert_\infty^2}{4\lVert f\rVert_\infty}.$$

Intuitively, you could have expected to get this just from "dimensional correctness" considerations: if you want to relate $f$ and $f''$, you'll need $(f')^2$ somewhere in there to make the units match. It's basically the same thing as $v^2-u^2=2as$ in classical mechanics, anyway. The same argument should work unchanged in the continuous domain too, but I don't know if it will generalize to multiple dimensions.

share|improve this answer

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.