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
    what is $x_i$. Moreover all norms in $\mathbb{R}^2$ are equivalent so what do you mean by more sophisticated notion of distance?2012-06-05
  • 0
    I rewrote the question is a more explicit and clearer way.2012-06-06
  • 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.