Where random discs change sign

Drop coins on a large table at random, letting them overlap freely, and look at the region they cover. With a few coins it is a scatter of separate islands. With very many it is one sheet of metal with gaps in it. Somewhere between, the islands join up, and the question this essay asks is whether the simplest topological count of the covered region — the number of pieces minus the number of holes — knows where.

It nearly does. The count has an exact average, it changes sign at a definite density, and that density is close to the one at which the covered region first stretches across the whole table. Close, and not equal: the sign change comes at one coin covering each point on average, and the connection comes about thirteen per cent later. The difference is the subject of the essay, because it is the clearest available example of what a local count can and cannot say about a global event.

The model is the simplest one in stochastic geometry, usually called the Boolean model. Centres are scattered as a Poisson process, independently and uniformly at an average rate of $\lambda$ per unit area, each carries a disc of radius one, and the object of study is the union. Its one parameter is $\eta = \lambda \pi$, the average number of discs covering a point, which is also the number of discs per disc area.

The figure shows one pattern at $\eta = 1$. There are 138 discs in and around the square, and they cover 63% of it. The union falls into 16 pieces inside the square and encloses 3 holes, so pieces minus holes is 13 — positive, but a small number for a square holding well over a hundred discs.

How much of the plane is covered #

The covered fraction has an exact formula, and it is the model for every exact statement that follows. A point is uncovered exactly when no centre falls within distance one of it. The number of centres in a disc of area $\pi$ is a Poisson variable with mean $\lambda \pi = \eta$, so the chance that there are none is $e^{-\eta}$, and the covered fraction is $1 - e^{-\eta}$.

That one line contains the method. The question “is this point covered?” depends only on what happens near the point, and the answer is averaged over the plane by computing it at one point. Area is additive, so the average area covered in a window is the window’s area times the chance that a single point is covered. At $\eta = 1$ the uncovered fraction is $1/e$, which is the 37% of the square the figure leaves pale.

The same method gives the average length of the boundary of the union, and the essay on the lines that cross a curve explains why boundary length is accessible in exactly the same way: a length can be counted by local crossings, and local events have averages that are computed at a point. Integral geometry is the study of which measurements of a shape have that property, and in the plane there are exactly three of the kind that matter here — area, perimeter and the Euler characteristic. Hadwiger’s theorem, which the essay on counting targets by their holes leans on, says that every additive measurement that does not depend on position and changes continuously is a combination of those three. So if the Boolean model has exact averages for area and perimeter, it should have one for pieces minus holes too, and it does.

Pieces minus holes, exactly #

The exact average Euler characteristic of the union, per disc area, is

$$\chi(\eta) = \eta\, e^{-\eta}(1 - \eta).$$

It is a classical result of integral geometry, and a sketch of why it holds shows where each factor comes from. Sweep a horizontal line up the plane and watch the union change. A new piece begins at the lowest point of a disc, provided no other disc covers that point; two pieces merge, or a loop closes around a hole, at a point where two circles cross with both discs lying above the crossing, provided no third disc covers it. The Euler characteristic of the whole union is the number of events of the first kind minus the number of the second, because each is a local change of one in pieces minus holes. Both kinds of event are points that must be left uncovered by every other disc, so each carries the factor $e^{-\eta}$. Lowest points of discs come at the rate of discs, $\eta$ per disc area. Crossings of two circles come at a rate proportional to the square of the density, and the share of crossings that are of the merging kind brings their rate to $\eta^2$ per disc area. The difference is the formula.

The figure checks the formula against counting, and the counting is done in a way that does not depend on drawing anything. The union of a collection of discs has the same Euler characteristic as a combinatorial object built from the discs: one vertex for each disc, one edge for each pair that overlaps, one triangle for each three that share a point, and so on, alternately added and subtracted. Whether a set of unit discs shares a point is decided exactly by the smallest circle around their centres, which must have radius at most one. Counting those sets in random patterns gives 0.1532 at $\eta = \tfrac12$ against the exact 0.1516, $-0.0093$ at $\eta = 1$ against nought, and $-0.2948$ at $\eta = 3$ against $-0.2987$, every count within a few standard errors of the curve.

The curve has a shape worth reading. It rises like $\eta$ while discs are scarce, because each disc is then its own piece. It peaks at $\eta = (3 - \sqrt5)/2 = 0.382$, passes through nought at exactly $\eta = 1$, and is most negative at $\eta = (3 + \sqrt5)/2 = 2.618$, the square of the golden ratio, where holes outnumber pieces by the largest margin. After that it climbs slowly back towards nought, because the plane is almost entirely covered and the holes themselves are disappearing.

Islands below one, holes above #

The sign of the curve describes what a typical pattern looks like, and three patterns at three densities show it directly.

At $\eta = \tfrac12$ the square holds 70 discs covering 39% of it. The union is 25 islands and not one hole: clusters of two or three discs overlap, but a ring of discs closing around uncovered ground is rare when there are this few. Pieces minus holes is simply the number of pieces.

At $\eta = 1.6$ the square holds 219 discs covering 80% of it. The union is nearly one sheet: only 4 pieces fall in the square, and 18 holes are enclosed by it, so pieces minus holes is $-14$. The roles have reversed. Below one disc a point, the covered ground is the islands and the uncovered ground is the sea; well above it, the uncovered ground is the islands — the holes — and the covered ground is the sea.

So the sign of the Euler characteristic is a summary of which phase is made of islands. The exact formula says the summary flips at $\eta = 1$, where the covered fraction is $1 - 1/e = 63.2\%$. That much is the formula. The question is whether the flip is the same event as the covered ground first joining into an unbounded sea.

Neither count turns at one #

The Euler characteristic is a difference, and the two counts it is the difference of tell their own story.

The pieces rise while discs are scarce, peak at about 0.166 per disc area near $\eta = \tfrac12$, and fall as islands merge, to 0.0571 at $\eta = 1$ and nearly nought by $\eta = 2$. The holes start at nothing, are 0.0557 at $\eta = 1$, and climb to about 0.29 per disc area around $\eta = 2.5$ to 3. Neither curve does anything special at $\eta = 1$. The pieces are still falling steadily there and the holes still rising; they simply cross. Their difference follows the exact curve throughout, passing through nought where the two counts happen to be equal.

This is the same situation the essay on the pieces no formula counts found for random waves. There, too, pieces minus holes had an exact average while the number of pieces had none, because whether two islands are joined depends on the whole path between them and not on anything at a point. The Boolean model makes the contrast sharper, because its exact formula is elementary and its pieces are still beyond any formula. Nobody has a closed expression for the density of pieces of the union of random discs, and the figure’s pieces curve is a measurement.

The counting itself carries a warning. Near $\eta = 1$ the holes become large and some of them are cut by the window’s edge, which removes them from the count. In windows thirty radii across, that loss was enough to push the measured difference visibly above the exact curve at $\eta = 1$; it took windows fifty radii across to bring it back. A count that depends on whole pieces is sensitive to the window in a way that a count of local events is not, and that sensitivity is the first sign that the pieces and the Euler characteristic are measuring different things.

The connection comes later #

Whether the union stretches across the plane is a question about crossings: in a large square, does a path in the covered region join the left side to the right? Below a critical density the chance goes to nought as the square grows, and above it the chance goes to one.

In a square ten radii across, the curve is gentle: 35% of patterns cross at $\eta = 1$ and 81% at $\eta = 1.5$. As the square grows the curve steepens. At 80 radii across, only 4.5% of patterns cross at $\eta = 1$, while 96.5% cross at $\eta = 1.3$. The four curves pass close to one another near $\eta = 1.15$, at 0.507, 0.540, 0.532 and 0.580 — the place where the share crossing stops depending on the size of the square, and the step in the limit. Long computations put that step at $\eta_c \approx 1.1281$, where 67.6% of the plane is covered.

At $\eta = 1$, where pieces minus holes changes sign, the biggest square is crossed less often than the smallest. The union is still a collection of finite islands there, and the sea is still the uncovered ground. The connection comes at a density about 13% higher. This is the same lesson the two thresholds of a random graph teach in a different setting: two events that sound like one — the islands outnumbered by holes, and one island reaching to infinity — happen at different densities, and only a calculation can say which comes first.

Why the two need not agree #

There is a case in which the sign change and the connection threshold are the same, and it explains why they are close here and why they differ. If the covered and uncovered ground were statistically interchangeable — if the picture looked the same with the colours swapped — then the Euler characteristic would have to be nought exactly where the covered fraction is a half, and by the same symmetry the covered ground and the uncovered ground would connect at the same moment. That is what happens for a smooth random surface cut at its middle height, where the region above and the region below are mirror images and the average Euler characteristic is nought at precisely the level where both sides are poised to connect.

Random discs have no such symmetry. The covered ground is made of round pieces and the holes are curved triangles and polygons with sharp corners, and nothing exchanges them. The zero of the Euler characteristic comes at 63.2% coverage and the connection at 67.6%, and neither is a half. The sign change is a natural estimate of the threshold, and has been used as a cheap one, because it is exact and costs nothing to compute; for discs it is low by about 11% of the threshold density. That is good for a quantity that takes one line, and wrong for a quantity that is supposed to be the threshold. The sign of an average says which phase dominates the local count, not whether any piece is infinite.

The giant component of a random graph appears at a threshold that a simple branching calculation gets exactly right, because a sparse random graph looks like a tree from any vertex. Random discs in the plane are full of short loops, and no local calculation captures the threshold. That is why $\eta_c$ is known only numerically.

The shape of the grain moves the zero #

The exact formula generalises to grains of any convex shape, turned at random. If the grains have area $A$ and perimeter $L$, the average Euler characteristic per grain area is

$$\chi(\eta) = \eta\, e^{-\eta}\left(1 - \eta\,\frac{L^2}{4\pi A}\right),$$

where $\eta$ is now the number of grains covering a point on average. The first term still counts lowest points; the second still counts merging crossings, and the number of crossings between two randomly turned grains depends on their perimeters, which is where $L^2$ enters. For a disc, $L^2 = 4\pi A$ and the formula reduces to the one above.

So the zero moves to $\eta = 4\pi A/L^2$. The ratio $L^2/(4\pi A)$ is the quantity the isoperimetric inequality is about: it is at least one for every shape and equals one only for the disc. Every other shape turned at random therefore changes sign earlier than the disc. For a square the zero is at $\pi/4 = 0.785$, and the counts give 0.012 at $\eta = 0.75$, just above the exact 0.016. For a four-by-one rectangle the zero is at $4\pi/25 = 0.503$, and the counts give $-0.013$ at $\eta = \tfrac12$ against the exact 0.0016. Long thin grains cross one another often relative to their area, so they make holes sooner.

Squares that all point the same way behave differently: they follow the disc’s curve, with counts of $-0.011$ at $\eta = 1$ and $-0.261$ at $\eta = 2$ against the disc’s $-0.009$ and $-0.260$. Turning the grains at random is what brings in the perimeter. For copies of one shape that all point the same way and look the same upside down, the crossing term depends only on the area, and the zero returns to one.

The same quantity appears in the problem of dropped needles, where the chance that a randomly turned needle crosses a line is its length over $\pi$ times the spacing, and $\pi$ enters through the averaging over directions. Here the averaging over directions turns the number of crossings between two grains, summed over every relative position, into $2L^2/\pi$, and the disc, being the same in every direction, is the shape for which the averaging does nothing.

What the sign does and does not say #

The Euler characteristic of a random union of discs has an exact average because it is a sum of local events, each weighed by the chance $e^{-\eta}$ that nothing else covers it. That average changes sign at exactly one disc a point, it peaks and bottoms out at the golden-ratio densities $0.382$ and $2.618$, and for other shapes its zero moves by exactly the factor the isoperimetric inequality measures.

What it does not do is locate the moment the union connects. That comes at $\eta \approx 1.128$, a number with no known formula, set by the loops of overlapping discs that no local count sees. The two are close because the sign change and the connection both mark the point where the covered ground stops being made of islands, and they differ because the first asks about the average balance of islands and holes and the second asks whether a single island is infinite. The sensor count of targets used the additivity of the Euler characteristic to recover an exact number from local readings. The random discs show the limit of that power: additivity yields every average the local events determine, and the threshold of connection is not one of them.

The covered fraction at the sign change, $1 - 1/e$, is the share of a circle that many short random arcs cover, in the limit, when their total length equals the circumference. Both are the probability that a Poisson count with mean one is not nought, and both come from asking a question at a single point.