Todd Trimble
discrete harmonic functions

This is something I got wind of at MathOverflow; the question was shut down pretty quickly as off-topic, but I actually got some enjoyment out of thinking about this problem, which (obviously) I hadn’t seen before.


Suppose that for all (m,n)L= 2(m, n) \in L = \mathbb{Z}^2 we have

(1)f(m,n)=14(f(m+1,n)+f(m1,n)+f(m,n+1)+f(m,n1)) f(m, n) = \frac1{4}(f(m+1, n) + f(m-1, n) + f(m, n+1) + f(m, n-1))

and f0f \geq 0. Then ff is constant.

What helped me is noticing that the equation (1) can be rewritten as

([f(m+1,n)2f(m,n)+f(m1,n)]+[f(m,n+1)2f(m,n)+f(m,n1)])=0([f(m+1, n) - 2f(m, n) + f(m-1, n)] + [f(m, n+1) - 2f(m, n) + f(m, n-1)]) = 0

which is a way of say ff is “discrete harmonic”: (Δ x 2+Δ y 2)(f)=0(\Delta_x^2 + \Delta_y^2)(f) = 0 for the discrete Laplacian. This gives some useful keywords with which one can do a Google search, if one is so inclined; for example, the topic crops up at various places in MO and Math.SE. We can think of the theorem above as a version of the Liouville theorem akin to the one for ordinary (continuous) harmonic functions, but using finite differences in place of derivatives. It turns out there is a bit of a literature on this type of thing; for the above theorem, see this for instance.

But we can prove this directly: what follows is my own write-up based on a nice idea of “orl” over at AoPS. Consider the space HH of such nonnegative discrete harmonic functions as a subspace of the product space L\mathbb{R}^L, which is a locally convex TVS.


Put K λ{gH:g(0)λ}K_\lambda \coloneqq \{g \in H: g(0) \leq \lambda\}. Then K λK_\lambda is compact and convex.


Convexity is clear; we check compactness. By an easy consequence of equation (1), g(y)4g(x)g(y) \leq 4g(x) if yy is adjacent to xx on the 2\mathbb{Z}^2-grid. This implies g(x)4 |x|g(0)g(x) \leq 4^{{|x|}}g(0) where |x|{|x|} is the l 1l_1 norm, so

(2)K λ xL[0,4 |x|λ] K_\lambda \subseteq \prod_{x \in L} [0, 4^{{|x|}}\lambda]

where the right side product is compact. Furthermore the space HH is defined as an equalizer in the category of Hausdorff spaces and so is closed in L\mathbb{R}^L; therefore K λK_\lambda, which is the intersection in L\mathbb{R}^L of a closed subspace HH and the compact product subspace, is also compact.


If gHg \in H and g(0)=0g(0) = 0, then g=0g = 0, i.e., g(x)=0g(x) = 0 for all xLx \in L.


If g(x)=0g(x) = 0 then gK 0={0}g \in K_0 = \{0\} by inclusion (2).


A point xx in a convex cone CC in a locally convex TVS is conically extreme in CC if, whenever y,zCy, z \in C with x=y+zx = y + z, it follows that y,zy, z are nonnegative multiples of xx.


Suppose ff is an extreme point of K={gH:g(0)=1}K= \{g \in H: g(0) = 1\}. Then ff is conically extreme in HH.


Say f=g+hf = g + h with g,hHg, h \in H and g(0)=λ,h(0)=μg(0) = \lambda, h(0) = \mu. Assume gg and hh are both nonzero, so by corollary 1, λ=g(0)\lambda = g(0) and μ=h(0)\mu = h(0) are both nonzero. Then putting g=1λg,h=1μhg' = \frac1{\lambda}g, h' = \frac1{\mu}h, we have g(0)=1g'(0) = 1 and h(0)=1h'(0) = 1 and f=λg+μhf = \lambda g' + \mu h'. But since ff is an extreme point of {gH:g(0)=1}\{g \in H: g(0) = 1\}, this convex combination forces g=f=hg' = f = h'. Hence g=λfg = \lambda f and h=μfh = \mu f.

Proof of Theorem

We will show K={gH:g(0)=1}K = \{g \in H: g(0) = 1\} consists of a single point, the constant g1g \equiv 1. Since KK is convex, and compact by applying Lemma 1, it will suffice by the Krein-Milman theorem to show KK has at one most extreme point ff. Such ff is conically extreme in HH by Proposition 1. If we define the operators TT and SS on L\mathbb{R}^L by T(g)(x)=g(x+(1,0))T(g)(x) = g(x + (1, 0)) and S(g)(x)=g(x+(0,1))S(g)(x) = g(x + (0, 1)), then HH is invariant under T,ST, S, and their inverses. Then, since we have

f=14(T(f)+T 1(f)+S(f)+S 1(f))f = \frac1{4}(T(f) + T^{-1}(f) + S(f) + S^{-1}(f))

the conical extremality of ff forces T(f)=λfT(f) = \lambda f and S(f)=μfS(f) = \mu f for some λ,μ>0\lambda, \mu \gt 0. Then from

f=14(λ+λ 1+μ+μ 1)ff = \frac1{4}(\lambda + \lambda^{-1} + \mu + \mu^{-1})f

we conclude

4=λ+λ 1+μ+μ 14 = \lambda + \lambda^{-1} + \mu + \mu^{-1}

and hence λ=1,μ=1\lambda = 1, \mu = 1. Since T(f)=fT(f) = f and S(f)=fS(f) = f, we conclude f:Lf: L \to \mathbb{R} is constant, namely the constant f1f \equiv 1, and we are done.

Revised on January 8, 2015 at 02:29:50 by Todd Trimble