COMPUTING SCIENCE

# How to Avoid Yourself

# Rigorous Self-Avoidance

Computational studies of self-avoiding walks have produced a rich harvest of empirical results. Theorems have been harder to come by. For example, studies of the mean-squared end-to-end displacement, based on both complete enumerations and on random samples, strongly support the hypothesis mentioned above that the displacement grows as *n*^{3/2}. Indeed, everyone "knows" that this result is correct and exact. But so far no one has proved it; no one has even proved that the exponent must be greater than 1 or less than 2.

Rigorous results on the counting of self-avoiding walks are also scarce. The empirical evidence suggests that for large *n* the number of walks grows as *n*^{2.638}, but this growth law has not been explained from first principles. Until recently, it wasn't even certain that the number of walks invariably increases as *n* gets larger; because walks can become trapped, it seemed possible that there might be some range of values where there are fewer (*n* + 1)-step walks than *n*-step walks. In 1990, however, George L. O'Brien proved that the series increases monotonically.

Even if the asymptotic growth law is correct, however, it is only an approximation—perhaps good enough for chemists and physicists but not wholly satisfying to mathematicians. Ideally, one would like a formula for calculating the exact number of walks for any value of *n*, without all the laborious counting. Is that too much to ask? Most likely it is. Conway and Guttmann have given compelling arguments (though not quite a proof) that no simple analytic function predicts the exact number of self-avoiding walks.

Perhaps the absence of such a function tells us something important about the nature of self-avoiding walks. The number of walks is perfectly definite and knowable; there is nothing random or uncertain about the number of ways to arrange a nonintersecting path on a lattice. So why can't we calculate it? I don't know the answer, but I would point out that there are many objects in mathematics that exhibit the same curious mixture of determinism and unpredictability. The prime example is the prime numbers. Again there is nothing uncertain or statistical about what makes a number prime, but if there is any pattern in the distribution of the primes, it remains totally inscrutable. As with the self-avoiding walks, there are good approximations for the number of primes, but no one has found (or expects to find) an exact formula that will reliably point to every prime. This stubborn resistance to total analysis is part of what makes the primes interesting. Perhaps self-avoiding walks belong in the same category of perpetually tantalizing mathematical structures.

© Brian Hayes

**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Feature Article**: Twisted Math and Beautiful Geometry

**Feature Article**: Simulating Star Formation on a Galactic Scale

**Feature Article**: Digital Forensics