display | more...

Give Zn the "normal" grid-like graph structure (i.e. every point (a1,...,an) is adjacent to the 2n points (a1,...,ai±1,...,an)). When n=2, we just get the square grid found on graph paper.

Now define a harmonic function on a graph to be a function f such that f(x) is the average value of f on the neighbours of x in the graph. For instance, f(x,y)=2x-3y is such a function (for n=2).

One immediate property of such a function is that it cannot have a strict local maximum, i.e. a point x such that f(x) > f(y) for all neighbours y of x. This is because f(x) is the average value of f on x's neighbours, and therefore cannot be larger than all of them.

It seems plausible, in light of theorems like Liouville's theorem from complex analysis, that no nonconstant bounded harmonic function can exist in Zn. However, this is somewhat difficult to prove. It is also true that no nonconstant positive harmonic function exists on Zn; this requires some serious machinery from mathematical analysis to prove.

#### Proof:

Let f be a harmonic function on Zn. Consider a simple random walk X0, X1, ... on Zn, starting from 0 (this simply means that X0=0, and Xn+1 is one of Xn's neighbours, picked at random). Then the expected value of f(X1) is exactly f(X0), and a little thought shows that the expected value of f(Xt) is always f(X0), for any constant t.

We'll show that f is constant on 2Zn (i.e. only points with all coordinates even); it will immediately follow that f is constant, since a harmonic function cannot have a local maximum (or minimum). To prove this, it is sufficient to prove that f(x)=f(x+2*k*ei) for all x, k and all standard basis vectors ei (ei is (0,...,0,1,0,...,0), with the 1 in the i'th place).

So start a simple random walk from x, and define another (dependent) simple random walk starting from x+2*k*ei by reflecting the random walk in the plane through x+k*ei which separates x and x+2*k*ei. Then this X't is another simple random walk. We know from the preceding remarks that f(X0) is the expected value of f(Xt), and f(x+2*k*ei) is the expected value of f(X't).

The projection of Xt on the ei axis is a random walk, the projection of X't on that axis is its mirror image, and it is easy to see that Xt must meet X't almost surely (this is why we require that x and x+2*k*ei be an even distance apart). Now define X''t to be X't until it meets Xt, and then Xt. Then X''t is also a simple random walk, and f(x+2*k*ei) is again the expected value of f(X''t).

Now suppose f is bounded. Pick some positive ε. For large enough t, the probability that X't hasn't yet hit Xt is smaller than ε. So for such a t,

f(Xt)-f(X''t) < ε*(f(Xt)-f(X't)) + 0,
since if Xt has already hit X't, then X''t=Xt, and the other case happens with probability <ε. So |f(Xt)-f(X''t)| < 2*ε*supremum(f), which is arbitrarily small. But |f(x)-f(x+2*k*ei)| is bounded by the average value of |f(Xt)-f(X''t)|, so it too is arbitrarily small. Hence it must be 0.

#### Proving the positive case

To prove that f is constant when we are only given that it is positive (i.e. bounded on one side), we can apply this reasoning regarding the values of f along a simple random walk: f(Xt) turns out to be a martingale, which we need to show must converge. But the limit cannot depend on the initial location, and by averaging this limit must be f itself - hence f is constant.

Log in or register to write something here or to contact authors.