From: David Bernier Subject: Re: Resistance between points in infinite resistor maze Date: Tue, 11 Jul 2000 23:37:29 GMT Newsgroups: sci.math Summary: [missing] In article <395FD329.5EBB5AF3@hetnet.nl>, Jan.Stuyt@philips.com wrote: > Anybody, > > I have an infinite maze of equal resistors of 1 ohm. The maze exists of > horizontal and vertical resistors only. I want to know what is the > resistance measured between any two points in the maze. One point is > taken as the origin (0,0), the other point is (m,n). The resistance to > be calculated is R(m,n). > > Becauses of symmetry reasons, R(m,n) = R(m,-n) = R(-m,n) = R(-m.-n) = > R(n,m). > We immediately know that R(0,0) = 0. > >From simple analysis we know that R(1,0) = 1/2. > I managed to find that on the diagonal: > > R(n,n) = 2/pi * Sum{k=1...n: 1/(2*k-1)} > > R(1,1) = 2/pi > R(2,2) = 2/pi * (1 + 1/3) > R(3,3) = 2/pi * (1 + 1/3 + 1/5) > etcetera > > I also found that the following recurrence equation must hold: > > R(m-1,n) + R(m+1,n) + R(m,n-1) + R(m,n+1) = 4*R(m,n) + 2*d(m,0)*d(n,0) > > where d(i,j) is the Kronecker symbol: d(i,j) = 1 if i = j, and d(i,j) = > 0 otherwise. > But I fail to find the general solution R(m,n). > Is there anyone familiar with this problem, or knows the solution? [...] We can represent the grid by ZxZ, and define: e1 = (1,0), e2 = (0, 1). Let x be a generic point in ZxZ. Then x is adjacent to x+e1, x-e1, x+e2 and x-e2. Suppose u: ZxZ->R denotes a (real-valued) electric potential function. From Ohm's Law, the current leaving x is: 4*u(x) - u(x+e1) - u(x-e1) - u(x+e2) - u(x-e2). It's convenient to define, given u, the discrete Laplacian of u by: (Lu)(x):= 4*u(x) - u(x+e1) - u(x-e1) - u(x+e2) - u(x-e2). So for any x in ZxZ, (Lu)(x) is the current leaving x, where we assume all resistors are 1 Ohm. Suppose (m,n) is in ZxZ, and (m,n) is not (0, 0). We would like an u such that: { u(0, 0) = 0 } { (Lu)(0,0) = 1 } { (Lu)(m,n) = -1 } (1) { (Lu)(x) = 0 if x is not (0, 0) or (m, n) } This corresponds to the situation where a unit of current enters at (0, 0) and exits at (m, n). By definition, the equivalent resistance between (0, 0) and (m, n) is then: R_(m, n) = u(0, 0) - u(m, n) (2). Note: Since L is linear, if v:ZxZ->R ---- satisfies (Lv)(x) = 0 for all x, and u satisfies (1), then u + v - v(0,0) satisfies (1) also. In Spitzer's book [1], some polynomials p(x,y) are given such that (Lp)(x) == 0. For example, p(x,y)=x, p(x, y)= y, p(x,y) = x^2 - y^2, p(x,y)= x*y, and others. This means that if (1) has a solution, it has infinitely many (continuum many). Maybe uniqueness can be achieved by requiring |u(x)| = o(|x|). I am not sure if this is enough. In Chapter 3, section 15, Spitzer defines a(k,l):= 1/(4*pi^2)*[ \int_{-pi}^{pi}\int_{-pi}^{pi} {(1- cos(k*t1+ l*t2))/(1-(cos t1+ cos t2)/2)} dt1 dt2 ]. He notes that a(0, 0)=0, and that a(k,l) = a(k, -l)= a(-k, l) = a( -k, -l) among other things. In the notation used here, he also writes something that is equivalent to: (La)(0, 0) = -4 , (La)(k, l) = 0 if (k, l) is not (0,0). So there exists a solution to (1), namely u(k,l):= [a((k,l)-(m,n)) - a(k,l)]/4 +C , for some constant C which will make u(0,0)=0. So by (2), R_(m,n) = a(m, n)/2 after simplification. As a special case, Spitzer shows that for n>0, a(n, n)= 4/pi * (1 + 1/3 + ... + 1/(2n -1) ). Also, a recursive procedure for computing a(k,l) for (k,l) in the first quadrant is given. From this procedure, I get a(k,l) = A(k,l) + B(k,l)/pi, where A is integer-valued and B is rational-valued. For n>0, A(n,n) = 0 is clear. I can also show, e.g. A(n, n-1) = (-1)^(n+1). As |k-l| gets larger, both A(k,l) and B(k,l) seem to get more and more complicated. Spitzer gives the asymptotic expression: a(x) ~= 1/pi *[ 2*log(|x|) + log(8) + 2* \gamma ], where |x| is the Euclidean norm of x and \gamma is Euler's constant. David Bernier --- REFERENCE: [1] Spitzer, F.: ``Principles of Random Walk", 1964, QA 273... especially Chapter 3. Sent via Deja.com http://www.deja.com/ Before you buy.