Xref: utzoo sci.physics:17076 sci.math:15449 sci.electronics:18087
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!mintaka!snorkelwacker.mit.edu!spool.mu.edu!uwm.edu!bionet!agate!garnet.berkeley.edu!greg
From: greg@garnet.berkeley.edu (Greg Kuperberg)
Newsgroups: sci.physics,sci.math,sci.electronics
Subject: Re: Effective Resistance on an Infinite Mesh (Random Walk Question)
Message-ID: <1991Feb28.203048.13891@agate.berkeley.edu>
Date: 28 Feb 91 20:30:48 GMT
References: <callahan.667353668@newton.cs.jhu.edu>
Sender: usenet@agate.berkeley.edu (USENET Administrator)
Reply-To: greg@math.berkeley.edu
Organization: U.C. Berkeley
Lines: 84

In article <callahan.667353668@newton.cs.jhu.edu> callahan@cs.jhu.edu (Paul Callahan) writes:
>Is there a closed form solution for the effective resistance between two
>points on an infinite 2-D mesh whose edges are unit resistors?

Both this problem and the related problems that you are interested in
boil down to the following:

Given an infinite mesh with unit resistors at the edges and a 1 amp
current sink at the origin, what is the voltage at each point
(assuming the voltage at the origin is 0)?

Let v(i,j) be the voltage at (i,j).  The problem boils down to finding
the unique solution to the equations:

v(i+1,j)+v(i-1,j)+v(i,j+1)+v(i,j-1)-4*v(i,j) = 0 for (i,j)!=(0,0),
v(1,0)+v(-1,0)+v(0,1)+v(0,-1)-4*v(0,0) = 1

with the property that v(i,j)-v(i,j+1) and v(i,j)-v(i+1,j) go to 0
as you go out to infinity (i.e. the currents asymptote to 0).  As
Brendan McKay pointed out, the voltages for the solution are unbounded
as you go to infinity.  But it's a well-posed mathematical problem
anyway.

To find the effective resistance between two vertices, you have to find
the voltages when there is a current source and a current sink at the
two vertices.  To do that, all you have to do is subtract the above
solution from a translate of itself.  The upshot is that the effective
resistance from (0,0) to (i,j) is simply v(i,j)+v(-i,-j) = 2*v(i,j).
Among other things, this lets us immediately conclude that the e.r.
between two *adjacent* vertices is 1/2, because by symmetry v(1,0) =
1/4.

There is no such trick for the general problem.  Nevertheless Noam
Elkies discovered independently that it has a tractable solution and he
posed the problem to me as a puzzle a few years ago.  Here is the
solution as I remember it.

We start by rotating the mesh by 45 degrees.  Specifically,
we let v(x,y) = v((x+y)/2,(x-y)/2) when x+y is even.  Next, we attempt
to guess solutions of the form v(x,y) = f(y)*exp(i*theta*x) with
no current source or sinks anywhere (for the moment we'll have to drop
the vanishing-at-infinity condition).

From the equation v(x+1,y+1)+v(x+1,y-1)+v(x-1,y+1)+v(x-1,y-1)-4*v(x,y)=0,
we get f(y+1)*2*cos(theta)-4*f(y)+f(y-1)*2*cos(theta) = 0, or
f(y+1)-2*sec(theta)*f(y)+f(y-1) = 0.  This is a recurrence relation
very similar to that for Fibonacci numbers.  In the spirit of the
Fibonacci sequence, we further guess an answer of the form
f(y) = r^y.  We get a quadratic equation for r which miraculously
factors into r=sec(theta)+tan(theta) and r=sec(theta)-tan(theta).
So we get two solutions (sec(theta)+tan(theta))^y*exp(i*theta*x)
and (sec(theta)-tan(theta))^y*exp(i*theta*x).  Any linear combination
of solutions is of course another solution.

The next step is to piece together these solutions to get a set of
voltages which doesn't blow up at infinity and which also has current
sources.  If we let 0<theta<pi/2, then we see that
sec(theta)-tan(theta)<1, and sec(theta)+tan(theta) is just the
reciprocal.  Thus, the solution

v_theta(x,y) = (sec(theta)-tan(theta))^|y|*exp(i*theta*x)

has good behavior at infinity and no current sources in the upper or
lower half plane.  However, we can check that it has a current source of
4*sin(theta)*exp(i*theta*x) amps at the vertex (x,0) (with x even, of
course).  The voltage function 1-Re(v_theta(x,y)) is equally nice,
actually, and it has the extra advantage of being real everywhere and
equal to 0 at (0,0). It has a current sink of 4*sin(theta)*cos(theta*x)
at (x,0).

In the last step, we integrate 1-Re(v_theta(x,y)) to get the
pattern of current sources we want.  Specifically, if we let

v(x,y) = integral_0^pi/2
        (1-(sec(theta)-tan(theta))^|y|*cos(theta*x))/2/pi/sin(theta) dtheta,

the current sinks cancel out everywhere except at the origin, and in
fact v(x,y) is the solution to the original set of equations.

So, for example, the e.r. between two diagonally separated vertices
is simply 2*v(2,0) = 2/pi.
----
Greg Kuperberg                 Reply only to postings you like.
greg@math.berkeley.edu         Ignore postings you dislike.