Pieces minus holes on a random surface

Counting targets by their holes used the Euler characteristic as a measuring instrument. It adds up like an area: glue two regions together and the Euler characteristic of the union is the sum of theirs minus that of their overlap. That additivity let a field of sensors count targets from the shapes of the regions where readings were high. The sequel found the instrument’s weakness: random errors add pieces and holes, and the count drifts.

This essay turns the weakness round. If randomness creates pieces and holes, what does a purely random surface look like when it is cut at a height? How many pieces does the region above the cut have, and how many holes? The answer is a surprise of a particular kind. The number of pieces has no formula, and neither does the number of holes. Their difference — the Euler characteristic — has an exact one.

A landscape with no edges #

The surface in the figure is a smooth random landscape: at every point of a square there is a height, and the heights vary smoothly but unpredictably. It is built by adding together waves of many directions and wavelengths with random amplitudes, which makes it a Gaussian random field — at each point the height has the bell-shaped distribution with mean 0 and variance 1, and any collection of heights has a joint bell-shaped distribution. The waves all repeat exactly across the square, so the left edge matches the right and the top matches the bottom. The square is really a torus, the surface whose Euler characteristic is zero, and the landscape has no edges to worry about.

The region above height 1 is outlined in orange. It has 14 separate pieces — islands, in the landscape picture, with the surface below 1 as sea — and none of them has a hole. So its Euler characteristic, pieces minus holes, is 14. The theory says that, averaged over all landscapes of this kind, it should be 13.8. This particular landscape is close to the average, but the point is that the average is known at all: for pieces alone, or holes alone, it is not.

Cutting at four heights #

Lowering the cut changes the region completely. At height 1.5 there are 12 small islands and no holes: the Euler characteristic is 12. At 0.5 the islands have grown and merged into 8 larger ones, still without holes, and the Euler characteristic is 8. At −0.5 the picture has turned inside out: the region is one connected sheet covering most of the square, with 10 holes where the landscape dips below −0.5, and the Euler characteristic is $1 - 10 = -9$. At −1.5 it is still one piece with 10 holes, the holes now smaller, and again −9.

So the Euler characteristic of the region above height $u$ is large and positive at high cuts, where the region is islands, large and negative at low cuts, where it is a sheet full of holes, and passes through zero near $u = 0$, where it is a tangle that is neither. For a Gaussian field, high and low are mirror images — the field $-f$ has exactly the same distribution as $f$ — and the holes at height $-u$ are the islands of $-f$ at height $u$. On average, then, the Euler characteristic at $-u$ is the negative of that at $u$.

Averages over two hundred surfaces #

Averaging over two hundred independent surfaces of the same kind gives smooth curves. The average number of pieces rises from 1 at low cuts, where the region is everything, to a peak of about 14 near $u = 1$, then falls to 0 at high cuts. The average number of holes does the reverse. The two curves cross near zero and have no evident simple shape: the number of pieces at a given height depends on how the islands merge as the cut descends, which depends on the whole landscape and not on any local property.

The Euler characteristic does have a simple shape, and the black curve is its formula:

$$E\big[\chi(\{f > u\})\big] = \frac{A\sqrt{\det \Lambda}}{(2\pi)^{3/2}}\; u\, e^{-u^2/2}.$$

Here $A$ is the area of the square, and $\Lambda$ is the covariance matrix of the slope of the surface — a measure of how steep it typically is, which is fixed by the mix of wavelengths in it. The dots, measured by counting pieces and holes, sit on the curve to within 0.30 everywhere, with extremes of ±13.8 at $u = \pm 1$. At the very lowest cuts the region is the whole glued square, which has one piece and, on a torus, two loops that wrap round it; those count as holes, and the Euler characteristic of the whole torus is 0.

Peaks, pits and saddles #

Why should the difference have a formula when neither term does? Because the Euler characteristic can be counted without knowing how anything is connected.

Imagine lowering the cut slowly from far above the landscape. Nothing happens until the cut passes the highest peak, when a small island appears: the Euler characteristic goes from 0 to 1. Each further peak the cut passes starts another island, adding 1. When the cut passes a saddle point — a mountain pass — one of two things happens: two islands that were separate join into one, or an island’s two arms meet round a lake, enclosing a hole. Either way the Euler characteristic drops by 1. When the cut passes a pit, the bottom of a lake, the lake’s last water disappears and the hole it made closes: the Euler characteristic rises by 1. Between those critical points, the region grows without changing shape at all.

So the Euler characteristic of the region above $u$ is the number of peaks above $u$, minus the number of saddles above $u$, plus the number of pits above $u$. This is the principle of Morse theory, and on the pixel grid the figures use it holds exactly, not approximately: each grid point gets an index — 1, less the number of edges to higher neighbours, plus the number of squares whose other three corners are higher — and the Euler characteristic of the region above $u$ is the sum of the indices of the grid points above $u$, checked at every height in the figure. The surface drawn has 41 peaks, 31 pits and 72 saddles, and $41 - 72 + 31 = 0$, the Euler characteristic of the whole torus, as it must be.

Pieces and holes depend on how critical points are linked: whether a particular saddle joins two islands or closes a loop is decided by the global geography. But peaks, pits and saddles are local: a point is a peak if it is higher than everything nearby. The expected number of peaks above $u$ is therefore an integral, over the square, of the probability that a peak sits at each point, and that probability depends only on the joint distribution of the height, the slope and the curvature at one point. For a Gaussian field those are jointly Gaussian with known covariances, and the integral can be done. The method is the Kac–Rice formula, which counts zeros of a random function by integrating the density of zeros point by point, applied to the slope. The pieces cannot be counted that way; the Euler characteristic can, which is why only it has a formula.

Why the curve has this shape #

The shape $u\,e^{-u^2/2}$ comes out of the peaks-pits-saddles count in a few lines. Count each critical point with a sign — plus for peaks and pits, minus for saddles — and ask for the density of signed critical points at height $v$: how many, per unit area, sit at heights near $v$. For a Gaussian field the answer is proportional to

$$(v^2 - 1)\, e^{-v^2/2}.$$

That single expression says where each kind of critical point lives. Far above zero, $v^2 - 1$ is positive and the critical points are mostly peaks. Far below, it is positive again and they are mostly pits. Between $-1$ and $1$ it is negative: the saddles, the passes between peaks and the necks between lakes, crowd into the middle heights. The figure of peaks, pits and saddles shows it — the saddle count climbs most steeply as the cut passes through the middle range.

The Euler characteristic of the region above $u$ adds up the signed critical points above $u$, so its average is the integral of that density from $u$ to infinity. And $(v^2 - 1)e^{-v^2/2}$ is exactly the derivative of $-v\,e^{-v^2/2}$, so the integral is $u\,e^{-u^2/2}$ — the bell curve multiplied by $u$. The sign of the average Euler characteristic, negative below zero and positive above, is the sign of the surplus of pits or peaks over saddles above the cut. The constant in front collects the area and how steep the surface is, because a steeper surface packs more critical points into the same area.

None of this needs to know which saddle connects which islands. The local count is all that enters, and the theory of the bell curve supplies the joint distribution of height, slope and curvature at a point. The number $v^2 - 1$ is the second Hermite polynomial, and in higher dimensions the same calculation produces the higher ones: the average Euler characteristic of the region above $u$ in a random three-dimensional field is a constant times $(u^2 - 1)e^{-u^2/2}$, which is the shape cosmologists fit to the distribution of galaxies.

The same theorem as combing hair #

The step from critical points to the Euler characteristic is not a special trick for random surfaces. It is the theorem that nothing on a sphere can be combed flat in another form. The slope of a surface is a field of arrows on it, pointing uphill, and its zeros are exactly the critical points; the Poincaré–Hopf theorem says that the zeros of any field of arrows on a closed surface, counted with their indices, add up to the surface’s Euler characteristic. Peaks and pits have index $+1$ and saddles $-1$, and on the torus they must add to 0, as the 41 peaks, 31 pits and 72 saddles do.

And the angle defects of seven hundred and twenty degrees of gap, which added up to $2\pi$ times the Euler characteristic of a solid, are the same idea at the corners of a polyhedron: a local quantity at each point whose total is a global one. The Euler characteristic began as corners minus edges plus faces, and every theorem about it since has been a way of computing it from local data. The random-field formula is that habit applied to an average: if the Euler characteristic is a sum of local contributions, its average is a sum of local averages, and those can be computed.

Texture drops out #

The formula has two parts: a constant, depending on the area and the steepness, and a shape, $u e^{-u^2/2}$, depending on nothing at all. The figure tests that split. Rough surfaces, with 5 waves across the square, have many more islands and holes than smooth ones, with 2, and their average Euler characteristic peaks at 37.9 instead of 6.2. Divided by the formula’s constant, all three curves fall on one, within 0.040. Everything about the landscape except the distribution of its heights and the typical size of its slope has dropped out.

That universality is what makes the formula useful. In brain imaging, a scan of blood flow is a noisy random field over the brain, and an analyst looking for regions of real activity has to decide how high a peak must be before it is unlikely to be noise. At high cuts the region above $u$ is a scatter of small islands with no holes, so its Euler characteristic counts the islands — and the chance that any island exists at all, the chance that the field’s maximum exceeds $u$, is very close to the average Euler characteristic. Keith Worsley and others turned this into the standard thresholds for such scans in the 1990s: the expected Euler characteristic, with the area and steepness estimated from the data, gives the probability that a peak of a given height is noise, without simulating anything.

A test of being Gaussian #

The shape $u e^{-u^2/2}$ is specific to Gaussian fields, and the last figure shows a field that is not Gaussian failing to follow it. Squaring a Gaussian surface and rescaling gives a landscape that cannot go below −0.71, because a square is never negative; below that level the region is everything, with Euler characteristic 0. Just above it, the region is already a scatter of islands, because every peak and every pit of the original surface becomes a peak of the square. The orange curve has no negative half at all.

Most departures from Gaussianity are subtler than this one, and the Euler characteristic curve detects them as a tilt or an asymmetry. Cosmologists use exactly this test on the temperature of the cosmic microwave background, a random field on the sky that the simplest theories of the early universe predict should be Gaussian — each patch’s temperature being the sum of very many independent small fluctuations, which is the shape that averaging leaves alone. In 1986 J. Richard Gott and his colleagues proposed measuring the genus — the three-dimensional cousin of this count — of the regions above and below a threshold in maps of how galaxies are distributed, and the two-dimensional version became one of the standard instruments for searching the microwave sky for non-Gaussian signatures. The maps match the Gaussian shape closely, and the measured curve is one of the pieces of evidence that the fluctuations began as Gaussian noise.

What the figures establish #

The figures generate exactly Gaussian fields on a 64-by-64 grid, compute the Euler characteristic of each region both as vertices minus edges plus squares and as a sum of point indices, and check that the two always agree. They count pieces by following connections across the grid and holes as pieces minus the Euler characteristic. The averages are over 200 surfaces for the main curve and 80 or 120 for the others, and the agreement with the formula is to the precision those numbers of surfaces allow.

The formula itself is a theorem: for smooth stationary Gaussian fields it follows from the Kac–Rice formula and Morse theory, and Robert Adler and Jonathan Taylor’s Gaussian kinematic formula extends it to fields on any domain, where the boundary contributes further terms that vanish on the torus. The figures check the theorem on finite grids; they do not prove it, and the agreement depends on the grid being fine compared with the wavelengths in the field, which it is here.

Still open: the pieces themselves #

The average number of pieces of the region above a given height, for a smooth Gaussian random field in the plane, has no known formula, and neither has the average number of holes. Their difference is exact, and so are the averages of the area of the region and the length of its boundary, the other two quantities additive in the same way. But the pieces are a global quantity, decided by which saddles join islands and which close loops, and no local integral computes them.

What is known is partial. At high cuts, the pieces are almost all small islands without holes, and the average Euler characteristic approximates the average number of pieces very well. At the middle cut, $u = 0$, the region is in the act of connecting up across the whole plane, and the behaviour is that of percolation. Fedor Nazarov and Mikhail Sodin proved in 2009 that for the simplest such field, built from waves of a single wavelength — the standard model for a random vibrating membrane — the number of pieces of $\{f > 0\}$ grows in exact proportion to the area. The constant of proportionality has been computed numerically, to a few digits, and a prediction from percolation theory turned out to be close to it but not equal. Its exact value is not known, and whether it has any closed form is open.