% Infinite resistive lattice --- see resistor.txt, resist.txt, resist.map 
% Subject "xkcd points out dangers of math fun" Fred Lunnon 02/01/08 

Off and on over the Christmas vacation, I've ruminated upon the purported Google 
aptitude test at http://www.xkcd.com/356/ introduced a fortnight ago by Steve 
Witham; I hope people might be mildly entertained by the resulting ramblings. 
The problem boiled down to finding the point-to-point resistance between two 
specified nodes [separated by a knight's move] of an infinite square lattice with unit resistances along each edge. 

Well now, we're bright, ambitious young men (I wish) after a job, so what's the 
obvious strategy? Cheat, of course: seeing that it's a job at Google, we'll browse away, a casual perorbination turning up the following references. 
[How could we ever manage without the internet, newslists, search engines, etc? 
Well for one thing, Steve wouldn't have been able to pass on this deceptively 
innocent conundrum; and for another, Google wouldn't have been there to pose 
it in the first place; so the problem would never have arisen ...] 

[Cse00] J\'ozsef Cserti (2000) 
  "Application of the lattice Green�s function for calculating the resistance of 
  infinite networks of resistors", URL http://aps.arxiv.org/abs/cond-mat/9909120 
including an introductory survey mentioning earlier work, and connnections with 
other areas; 

[Atk99] D. Atkinson, F. J. van Steenwijk (1999) 
  "Infinite Resistive Lattices" Am. Jour. Phys. vol. 67 pp 486-492, 
  URL http://atkinson.fmns.rug.nl/public_html/dapubl.html 
covering largely similar ground using slightly different methods; 

OEIS A089165 --- broken link to [Atk99] --- attn NJAS?; 

OEIS A049034 --- mention connection below --- attn NJAS?. 

Denote by u^{kl} the resistance beteen nodes (0,0) and (k,l). From table I of 
[Atk99] for example, we are at liberty to read off explicit results such as 

        u^{00} = 0,   u^{01} = 1/2,   u^{11} = 2/\pi, 

the exact value of u^{12} [no, I'm not telling you --- go crib it yourself] 
etc., all of the form a-b/\pi with a,b rational. 

OK, end of story --- aspirant googlies stop reading here. 

                    ________________________________________

The diagonal entries u^{kk} in this table are rational multiples of 2/\pi, 
and [Cse00] equation (32) gives a 3-term recurrence for these numbers; 
feeding them instead into OEIS turns up at A049034 the explicit but seemingly 
previously overlooked 

[Ukk]  u^{kk} = ( 1 + 1/3 + 1/5 + ... + 1/(2k-1) ) 2/\pi . 

A nice direct proof of this case would be much appreciated, since the remainder 
of the somewhat cumbersome-looking recurrence gives all u^{kl} in terms of the 
u^{kk} together with u^{01}, via lattice symmetries and the elegant "discrete 
Laplacian" relation [of which more later]

[Del2]  \del^2 u^{kl} = 0, where we define \del^2 u^{kl} 

        == u^{k,l-1} + u^{k,l+1} + u^{k-1,l} + u^{k+1,l} - 4 u_{kl} . 

Just how useful a "solution" is provided by the table and recurrence? 
For the case u^{12} originally posed, and more generally near the diagonal 
k = l, it's serviceable enough; further along the axis k = 0 however, severe 
cancellation afflicts any attempt to evaluate numerically the formal 
expressions developed. For example, using our trusty 8-digit slide-rule we find 
    u^{9,9}  = 3186538/765765\pi ~ 1.3245663, correct to all places shown; 
but 
    u^{0,12} = 306528145/2-1668374215352/3465\pi ~ 0, instead of 1.3309766. 
Conversion to numerical values along the diagonal prior to applying [Del2] 
improves the situation only slightly. 

Making the plausible assumption that resistance depends asymptotically only on 
the radius n, and applying standard results to [Ukk], it can easily be seen 
for large n^2 = k^2 + l^2 that 
        u^{kl} ~ (log(8 n^2)/2 + \gamma) / \pi, 
\gamma denoting Euler's constant. For the cases above this gives 
    u^{6,6} ~ 1.3244030, u^{0,12} ~ 1.3311356, 
the second approximation being a considerable improvement on our previous 
attempt. 

The formal expressions for the resistances are integrals arising from what 
looks to be a fairly straightforward exercise in Fourier transform and college 
integration, though I have to admit I found the combination of terseness and 
unfamiliar notation [Atk99] accompanied by an occasional suspected misprint 
[Cse00] made these computations hard to follow. Confidence in [Atk99] is also 
somewhat shaken by what I can anly describe as smoke-and-mirrors [following 
equation (4)] as the author attempts to explain why his integral turns out to 
give half the desired value. Nonetheless, the outcomes look surely OK. 

                    ________________________________________

Though not initially apparent, an unlooked-for complication soon intrudes on 
any attempt to develop a solution from scratch: to wit, just how well-posed 
is this problem anyway? Although intuitively it appears perfectly unambiguous, 
further progress proves in practice dependent upon making one of a number of 
further plausible assumptions; such as 

[Pos1] The current at infinity vanishes [Atk99]; 

[Pos2] Periodic boundary conditions at the edges of the (finite square) region 
  [Cse00];  

[Pos3] The resistances at vertices along any shortest path from (0,0) to (k,l) 
  increase monotonically [WFL]; 

[Pos4] The requisite distribution of resistance is the limit of that in a n x n 
  square network, connected at the edges to form a torus [WFL]; 

and [Atk99] hints at further possiblities lurking in the literature cited by 
the papers above. 

[I'm perfectly prepared to believe that the euphonious prestidigitations [Pos1], 
[Pos2] do indeed represent concrete mathematical constraints of some kind, 
however presently impenetrable to this reader.] Their importance lies less in 
their detail, than in that all appear to lead to an essentially common outcome. 
Does not a situation where a unique solution evidently exists, yet cannot be 
constructed except via a mysterious coincidence of conclusions from numerous 
apparently disparate scenarios, suggest that the its investigators may still 
be some way short of a full understanding of its essential character? 

                    ________________________________________


Rather than attempt to emulate the "Green's function" integrals they derive, 
I prefer to rely on the low-tech tools discussed in an earlier math-fun thread 
discussing resistance networks generally, circa 1998. [Whaddya mean, you hadn't 
been born then? Sit up and pay more attention!] These were almost certainly 
known to Kirchhoff, though I can't supply references. Given a network of m 
nodes, denote by a_{ij} the admittence (reciprocal of resistance) along edge 
joining node i with node j, and by u_{ij} the total point-to-point resistance; additionally, set a_{ii} = u_{ii} = 0 for all i. 

Then the inner product law states 

        \sum_{i,j} a_{ij} u_{ij} = m-1; 

and the symmetric bilinear relation fixing edge 12 (say) states 

        \sum_j (a_{1j}+a_{2j}).u_{12} + (a_{1j}-a_{2j})(u_{1j}-u_{2j}) = 4. 

Applying these to a finite n x n toroidal network, after some algebra 

[Tor1]  u^{00} = 0; 

[Tor2]  u^{01} = (1/2)(1-1/n^2); 

[Tor3]  \del^2 u^{kl} = -2/n^2 for (k,l) <> (0,0); 

noting that 
    both of i,j range over all pairs (k,l) in the lattice; 
    all nodes are isomorphic; 
    and a_{ij} = 1 if i,j have a common lattice edge, 0 otherwise. 

Letting n -> oo, for the infinite lattice 

[Lat1]  u^{00} = 0; 

[Lat2]  u^{01} = 1/2; 
 
[Lat3]  \del^2 u^{kl} = 0 for (k,l) <> (0,0). 

                    ________________________________________

Looking at the set [Lat1]--[Lat3] for the octant 0 <= k <= l <= n [after 
casting out lattice symmetries] where n is some finite bound, we find 
(n+1)(n+2)/2 variables connected by n-1 fewer simultaneous linear equations. 
Not much can be done with these as they stand; but hauling in an extra 
n(n+1) inequalities in the form of the monotonicity assumption [Pos3] converts 
them into a feasible set of "linear programming" constraints. 
The simplex algorithm (say) can then output a solution set of values such that 
a specified variable u^{kl} achieves its max (alternatively min) compatible 
with the constraints, yielding strict upper and lower bounds for any chosen 
resistance. 

It appears that in order to compute bounds for m different nodes by this method, 
we should have to solve 2m distinct simplex problems. Remarkably however, 
max, min solutions for u^{11} prove also to be max, min (or min, max) solutions 
for most of the other variables as well --- though frustratingly, this can't 
presently be guaranteed without undertaking the other computations anyway! 
In practice, the resulting lower bounds prove noticeably closer than the 
upper to the exact values discussed earlier. 

Simplex with n = 12, after correct limiting values: 

        u00 = 0          ~ 0.         +/- 0. 
        u01 = 0.50000000 ~ 0.50000000 +/- 0. 
        u11 = 0.63661977 ~ 0.63663228 +/- 0.00001935 
        u02 = 0.72676046 ~ 0.72673545 +/- 0.00003870 
        u12 = 0.77323954 ~ 0.77326455 +/- 0.00003870 
        u22 = 0.84882636 ~ 0.84897656 +/- 0.00023233 
        u03 = 0.86056273 ~ 0.86041268 +/- 0.00023220 
        u13 = 0.88075159 ~ 0.88071393 +/- 0.00005818 
        u23 = 0.92441318 ~ 0.92468856 +/- 0.00042596 
        u33 = 0.97615032 ~ 0.97686566 +/- 0.00110528 
        u04 = 0.95398729 ~ 0.95348741 +/- 0.00077374 
        u14 = 0.96479089 ~ 0.96448993 +/- 0.00046517 
        u24 = 0.99192446 ~ 0.99219810 +/- 0.00042439 
        u34 = 1.02788745 ~ 1.02904275 +/- 0.00178461 
        u44 = 1.06709600 ~ 1.06931833 +/- 0.00342505 

                    ________________________________________

In contrast, for the finite torus of given diameter n, [Tor1]--[Tor3] give 
a bunch of sparse simultaneous linear equations which may be solved rationally 
or numerically to determine all the resistances. [Torus --- borus. Klein bottle 
or projective plane, anyone?] Even accepting [Pos4] however, as approximations 
to the infinite case these bare estimates [plausibly also lower bounds] are 
doomed to be unimpressive: from the equations themselves it is plain that they 
will be O(1/n^2) adrift from the infinite solution. 

Torus with n = 100, after correct limiting values: 

        u00 = 0          ~ 0. 
        u01 = 0.50000000 ~ 0.49995000 
        u11 = 0.63661977 ~ 0.63651979 
        u02 = 0.72676046 ~ 0.72656043 
        u12 = 0.77323954 ~ 0.77298957 
        u22 = 0.84882636 ~ 0.84842654 
        u03 = 0.86056273 ~ 0.86011255 
        u13 = 0.88075159 ~ 0.88025154 
        u23 = 0.92441318 ~ 0.92376351 
        u33 = 0.97615032 ~ 0.97525118 
        u04 = 0.95398729 ~ 0.95318669 
        u14 = 0.96479089 ~ 0.96394053 
        u24 = 0.99192446 ~ 0.99092479 
        u34 = 1.02788745 ~ 1.02663884 
        u44 = 1.06709600 ~ 1.06549865 

But a remedy is to hand: the "number wall" algorithm (aka Rutishauser QD) 
may be employed to extrapolate to the limit from a sequence of such 
approximations. In practice, extrapolation reduces the deficit in the 
final torus by at best by a factor 10 or so: extrapolating from the first 
100 even n using order 13 Hankel determinants and 20-digit precision, 
the estimate for u^{11} is improved from 0.63651979 to 0.63661078, against 
a target of 0.63661977. 

________________________________________________________________________________

Dunno whether 10^-5 would be good enough to get me that job at Google; but then, 
I'm not sure I wanted one just yet anyway. Reckon I'll just wait around until 
they winkle out that devious sadist from the hiring department, strap him down 
to an infinite resistive lattice, then crank up the power! 

          Fred Lunnon, Maynooth 02/01/08 

________________________________________________________________________________