7
$\begingroup$

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?

  • 0
    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.2012-06-09

3 Answers 3

1

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.

0

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"

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

  • 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.2012-06-06
0

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.