Thermodynamics

The cluster that grows where the walkers arrive

Let particles wander in one at a time from far away, each sticking where it first touches a growing clump. The rule has nothing in it about shape, and the clump that results is a lacy, branched thing whose mass grows more slowly than its area, so it gets emptier the bigger it gets. The reason is that a random walker reaches the outermost tips long before it can find its way into a gap between branches. The same arithmetic — the probability that a walker arrives is a solution of Laplace's equation — shapes electrodeposits, lightning-like discharges in plastic, fingers of water pushed into oil, and colonies of bacteria short of food.

14 min read 5 figures Order out of the random The shape decides

Assumes: The walk that comes home · The potential is where the wanderers stop

The walk that comes home followed a single random walker and found that in a plane it returns, eventually, to wherever it started, while in space it may wander off for good. The potential is where the wanderers stop used random walkers to solve Laplace’s equation: start many walkers at a point, let each wander until it hits a boundary, and the average of the boundary values they collect is the potential at the point. In both essays the boundaries were fixed and the walkers only measured them.

Let the walkers change the boundary instead. Start with a single sticky particle. Release a second far away and let it wander until it touches the first; there it sticks. Release a third, which wanders until it touches either, and sticks. Go on. Thomas Witten and Leonard Sander proposed this rule in 1981 as a model of how soot particles clump, and called it diffusion-limited aggregation. Nothing in it mentions direction, shape or branching. What it grows is a fractal, and the reason it is a fractal is the same reason the walkers measure a potential.

A rule with no shape in it

A cluster grown by random walkers. 3000 particles, each released far away to wander at random on a square grid until it first touches the cluster and sticks there, starting from one seed at the centre. Colour marks the order of arrival: the first third (violet), the second (blue), the last (red). The cluster is 220 grid steps across, branched and open, and almost every late arrival is at the outer tips: walkers wander into the outer branches long before they can find their way into the gaps between them. The gaps never fill. — Fig. 1 Three thousand particles grown on a square grid, each released far away to wander at random until it first touches the cluster and sticks, starting from one seed. Colour marks order of arrival: first third violet, second blue, last red. The cluster is 220 grid steps across, branched and open, and nearly all late arrivals are at the outer tips.

The cluster in the figure was grown by exactly that rule, with three thousand particles on a square grid and a seeded random number generator. It has a few main arms, each splitting into side branches, each of those splitting again, with wide gaps between them that never fill. The colours, which mark the order in which particles arrived, show how it grew: the first third of the particles form a compact core, the second third the inner arms, and the last third almost entirely the outer tips. Particles that arrive late do not find their way into the interior; they stick at the outside.

Nothing about the square grid chose that shape. A rule in which each new particle is placed at a random empty site touching the cluster, with no wandering — an Eden cluster, after Murray Eden’s 1961 model of a growing colony of cells — grows a compact, roughly round blob.

The same number of particles, with and without wandering. Left: 3000 particles added one at a time at random empty sites touching the cluster, with no wandering (an Eden cluster): it grows into a compact, roughly round blob 80 steps across. Right: the same number, each arriving by a random walk from far away: an open, branched cluster 220 steps across. The only difference is how a particle chooses where to stick, and wandering makes the cluster about 2.8 times wider. — Fig. 2 The same 3,000 particles grown two ways. Left: each added at a random empty site touching the cluster, with no wandering — a compact blob 80 steps across. Right: each arriving by a random walk from far away — an open, branched cluster 220 steps across, 2.8 times wider.

The two rules differ only in how a particle chooses where to stick. In the Eden rule every site on the surface is equally likely. In the walker rule the chance of sticking at a site is the chance that a random walk from far away reaches that site before any other, and that chance is very unequal. That difference alone turns a blob into a fractal.

Why the tips win

A walker coming in from far away does not head for any particular site; it diffuses in, and it is most likely to touch whatever sticks out furthest. A protruding tip is surrounded by open space from which walkers can reach it from many directions; a site at the bottom of a gap between two branches can be reached only by a walker that wanders into the gap without touching either side on the way down, and most walkers that enter a gap touch a side first. The gaps are screened by the branches around them.

Fig. 3 For the finished cluster, divided into five rings by distance from the seed: the share of its particles in each ring (light), and the share of 3,000 further walkers, released as in the growth, that would stick in each ring (dark). The outermost ring holds 5 per cent of the cluster and catches 19 per cent of the arrivals; the inner three rings hold 79 per cent and catch 24.

The figure measures the screening directly. After the cluster had grown, three thousand more walkers were released exactly as before, and the place each would have stuck was recorded without adding it. The outermost ring of the cluster, which contains only a twentieth of its particles, would catch almost a fifth of the arrivals. The inner three rings, which contain four fifths of the cluster, would catch less than a quarter. The tips, few as they are, take most of the growth.

It is the same screening that lets a cage of thin wires leak a quarter of a field: seen through walkers, a wire is hard to hit and the gaps let walkers through. Here the roles are reversed. The cluster is what the walkers are trying to reach, and its outer branches are so good at catching them that almost none get through to the inside.

That is an instability, and it is self-reinforcing. A tip that sticks out a little catches more walkers than its neighbours, grows faster, sticks out further, and catches more still. Any small bump on a smooth surface grows into a branch, and the branch’s own surface sprouts bumps of its own, which grow into side branches. William Mullins and Robert Sekerka found the same instability in 1963 for a crystal growing from a solution or a melt, where the growing surface is fed by diffusion of material or heat towards it: a flat front is unstable to bumps of every size above a minimum set by surface tension. Diffusion-limited aggregation is that instability with no surface tension at all, so that bumps of every size grow, down to a single particle.

Mass that grows slower than area

$How the mass grows with the radius. The number of particles within a distance r of the seed, against r, on logarithmic axes, for the walker-grown cluster and for an Eden cluster of the same size grown by adding particles at random empty sites on its edge, with no wandering. The Eden cluster fills its disc and its mass grows as r^2.00, close to 2. The walker-grown cluster's grows as r^1.65 — a fractal dimension near the 1.71 that large simulations find — so its density falls as r^−0.35: the bigger it gets, the emptier it is.$

Fig. 4 The number of particles within a distance r of the seed, against r, on logarithmic axes. The Eden cluster’s mass grows as r^2.00, filling its disc. The walker-grown cluster’s grows as r^1.65 — a fractal dimension near the 1.71 that large simulations find — so its density falls as r^−0.35.

The open structure has a number. Count the particles within a distance $r$ of the seed and plot the count against $r$ on logarithmic axes. For the Eden cluster the points lie on a line of slope two: mass proportional to area, a solid disc. For the walker-grown cluster the slope is 1.65 in this small simulation, and simulations of clusters with millions of particles settle on 1.71. That is a fractal dimension: a cluster in the plane whose mass grows as though it were somewhere between a line and an area. Its mean density within radius $r$ falls as $r^{-0.29}$ , so the bigger it gets, the emptier it is — not because anything removes particles, but because the gaps between branches grow faster than the branches fill them.

$How fast each cluster widens as it grows. The radius of gyration — the root-mean-square distance of the particles from their centre — against the number of particles, on logarithmic axes, for the walker-grown cluster and the Eden cluster, each read off its own history. The Eden cluster widens as N^0.48, the square root a filled disc gives. The walker-grown cluster widens as N^0.60, close to 1/1.71 = 0.58: it reaches out faster than it fills in, which is the same fact as its fractal dimension, read the other way.$

Fig. 5 The radius of gyration, the root-mean-square distance of the particles from their centre, against the number of particles, from each cluster’s own history, on logarithmic axes. The Eden cluster widens as N^0.48; the walker-grown cluster as N^0.60, close to 1/1.71 = 0.58.

The same fact can be read from the growth. As particles are added, the Eden cluster widens as the square root of their number, the rate a filled disc requires. The walker-grown cluster widens as the number to the 0.60 — the reciprocal of its fractal dimension — reaching out faster than it fills in. A cluster grown in three dimensions by the same rule has a fractal dimension of about 2.5, between a sheet and a solid, and the same screening makes it open.

The walkers solve Laplace’s equation

The chance that a walker from far away first touches the cluster at a given site is not an arbitrary distribution. It is the harmonic measure of the cluster’s surface, and it is fixed by Laplace’s equation: hold the cluster at potential zero and the far boundary at potential one, solve for the potential in between, and the probability of arrival at each surface site is proportional to the gradient of the potential there — the electric field at the surface, if the cluster were a conductor. That is the content of the potential is where the wanderers stop, read in reverse.

So diffusion-limited aggregation is growth at a rate proportional to the local field at the surface of a conductor. The field at the surface of a conductor is largest at its sharp points — the effect that makes a sharp metal tip pull electrons from cold metal at fields a flat surface could not — and smallest in its hollows, which is the screening again. Any growth process in which the growth rate is set by a field that obeys Laplace’s equation outside the growing body, and that body is held at a fixed value of the field’s potential, grows the same way. Lucian Niemeyer, Luciano Pietronero and Hans Wiesmann showed in 1984 that the branching tree of a discharge burned into a block of plastic, a Lichtenberg figure, is grown by the same rule with the electric potential in place of the walkers’ probability, and has the same dimension. The spark that needs room to start found where a discharge can begin; here is the shape it takes once it has.

Smoke, and clusters that meet clusters

Witten and Sander were trying to explain a measurement. Stephen Forrest and Witten had photographed, in 1979, the tiny aggregates of iron and zinc oxide that form in metal smoke — particles a few nanometres across, colliding by the same jostling that proved atoms exist and sticking where they touched — and found that their mass grew with their size to a power well below three. Diffusion-limited aggregation, with single particles wandering onto a single cluster, was the simplest model with that property.

Real smoke is a little different. In a smoke the clusters themselves wander, and two clusters meeting stick together just as a particle and a cluster do. Paul Meakin, and independently Max Kolb, Rémi Botet and Rémi Jullien, simulated this cluster–cluster aggregation in 1983 and found clusters even more open than Witten and Sander’s, with a dimension of about 1.8 in three dimensions against 2.5 for particles joining one cluster, because two branched objects meeting tip to tip leave even more empty space between them. Measurements on soot, colloidal gold and silica aggregates give that value, and it is now used routinely to describe how such particles scatter light and how they settle.

Growth that cannot be undone

The fractal depends on the sticking being permanent. A particle that touches the cluster stays where it touched, even if it would be more comfortable somewhere else, and it is the accumulation of these first contacts that builds the branches. Allow particles to come unstuck, with a small probability, and to wander off and land elsewhere, and the cluster slowly rearranges itself towards a compact shape, because particles at the exposed tips, held by few neighbours, detach more easily than particles in the interior. Given long enough, a reversible cluster forgets its branching entirely.

So the branching is a frozen record of the order in which the walkers arrived — a structure that exists because diffusion only runs forwards and attachment was not allowed to run backwards. It is far from equilibrium in the most literal sense: no energy minimum looks like a diffusion-limited aggregate, and no amount of waiting at constant temperature would produce one from a compact clump. That is why the same shapes appear in processes as different as electrodeposition and bacterial growth: what they share is not a free energy but a kinetics.

Where the shape appears

The examples are many, and in each the physics is different and the equation the same.

Zinc grown on an electrode from a thin layer of zinc sulphate solution forms dendrites that look like the figure, because the zinc ions diffuse to the growing metal and the electric field concentrates on its tips; Mitsugu Matsushita and colleagues measured their fractal dimension in 1984 and found 1.66. Water pushed into oil between two closely spaced glass plates — a Hele-Shaw cell — forms fingers that branch repeatedly, because the pressure in the oil obeys Laplace’s equation and the interface advances fastest where the pressure gradient is steepest; Lincoln Paterson pointed out the correspondence the same year. Colonies of the bacterium Bacillus subtilis, grown on a hard, nutrient-poor gel, spread as branched fractals because the nutrient diffuses to the colony’s edge and the bacteria at the tips eat first. Mineral dendrites, the fern-like dark patterns on the surfaces of some rocks that are often mistaken for fossil plants, are manganese oxides that grew by diffusion through a thin film of water. And snow crystals grow by water vapour diffusing to their tips, which is why their arms branch — though surface tension and the crystal’s six-fold structure discipline the branching into the familiar regular shapes rather than a random tree.

A walker that lives on the cluster, rather than arriving at it, has a hard time. Confined to the branches, it spends long stretches wandering into dead ends and back out, and its mean square distance from its starting point grows more slowly than time — the anomalous slowing found in crowded and disordered media, here caused by the cluster’s own geometry. Heat, electric current and fluid flowing through such a structure inherit the same slowness, which is why the conductivity of fractal aggregates, and of the porous materials made from them, is far lower than their solid fraction alone would suggest.

What sets the dimension

The dimension 1.71 is one of the oddest numbers in statistical physics. It comes out of simulations with great reproducibility, for any lattice and off lattice, and it has proved almost impossible to derive. Large clusters are self-similar — a branch looks like a smaller copy of the whole — and their dimension is a property of the growth rule alone, independent of the lattice or the size of the particles. But the screening that makes them fractal is a long-range effect: whether a given tip grows depends on the shape of the whole cluster, through the potential it sets up. There is no local rule from which to start a calculation.

A mathematically exact formulation came in 1998, when Matthew Hastings and Leonid Levitov represented the growth as a sequence of conformal maps, each adding one particle to the image of a disc, which made very large clusters computable and allowed the dimension to be measured to three decimal places, but did not explain it. Whether the dimension is a simple number in disguise — some proposed formulas give 1.71 or close to it — or a constant with no closed form, and whether the clusters are truly self-similar in the limit or slowly change their character as they grow, have been argued over for forty years.

What the pictures cannot show

The cluster is small — three thousand particles on a square grid — and its measured exponents, 1.65 for the dimension and 0.60 for the widening, differ from the asymptotic values found in simulations of millions of particles by the amounts small clusters always show. On a square grid, large clusters also develop a faint four-armed anisotropy aligned with the lattice, visible in the figure’s four main arms, which is an artefact of the grid and is absent in clusters grown off a lattice. The walkers in the simulation are released on a circle just outside the cluster and abandoned if they wander far away, standard shortcuts that do not change the statistics of where they stick.

The probability-of-arrival figure counts walkers by ring, which measures the screening only coarsely; the harmonic measure itself is much more uneven, concentrated on a small fraction of the tips, and its own statistics are a multifractal whose description needs a whole spectrum of exponents rather than one.

The domain of the argument is growth fed by a diffusing supply, or driven by a potential, with the growing body absorbing everything that reaches it and no surface tension or crystal structure to smooth it. Inside it, the result is a fractal of dimension about 1.71 in a plane. Where surface tension matters, or the supply is not purely diffusive, the branching is tamed: snowflakes, dendrites in casting metals, and the fingers in viscous fluids all have a characteristic width that pure aggregation lacks.

Still open: why 1.71

The question of what fixes the fractal dimension of diffusion-limited aggregation is one of the oldest open problems in non-equilibrium statistical physics. Theories based on renormalising the growth at successive scales give values near the simulations’ but depend on approximations that are hard to justify; field theories of Laplacian growth reproduce the branching but not the number. Related questions — how the harmonic measure on the cluster’s surface is distributed, what the dimension is in three or more dimensions, and how the clusters cross over to compact growth when particles may stick with less than certainty on first contact — are better understood numerically than analytically.

The rule itself is one sentence long. Let particles wander in one at a time and stick where they first touch, and the chance of sticking at each site is the field at a conductor’s surface — largest at the tips, smallest in the hollows — so the tips grow, the hollows are screened, and the cluster becomes a fractal whose mass grows as r^1.71 in the plane: 3,000 particles reach 220 steps across where the same number placed at random on the edge fill a blob of 80. The branching of a Lichtenberg figure, a zinc dendrite and a starving bacterial colony is the same branching, because their supplies obey the same equation.