The surface a random gluing makes

A polygon with twenty-four edges can have them paired in 23 × 21 × 19 × … × 1 ways, a little over 316 billion. Choose one at random, glue every pair head to tail, and the result is a closed two-sided surface: a sphere with some number of handles. Twenty-four edges could make anything from a sphere to a surface with six handles. What does a random choice make?

This one makes a surface with five handles. The twenty-four corners collapse to just three vertices, and since the surface has one face and twelve edges, its Euler characteristic is 3 − 12 + 1 = −8 and its genus is five. The largest possible was six.

That is not luck. The census of every gluing showed the weight of each row moving to the high genera as the polygon grows, and this essay follows that drift to its end. For large polygons, a random gluing almost always leaves only a handful of vertices — about the logarithm of the number of edges — and so its genus falls short of the maximum by only about half that logarithm. The surfaces that the classification lists first, the sphere and the torus, are the ones a random gluing essentially never produces.

Vertices are what randomness controls #

For a polygon with 2n edges glued into one face and n edges, the genus is fixed by the vertex count V: g = (n + 1 − V)/2. So the question what surface does a random gluing make? is the question how many vertices does it leave? — and that is a question about a permutation.

Gluing edge i head to tail with its partner sends the corner at the start of i to the corner just after the partner. Following that rule from any corner traces a cycle, and each cycle is one vertex. Written as permutations, the corner map is a rotation of the polygon by one step composed with the pairing, and V is the number of its cycles. A random gluing is a random pairing, so V is the cycle count of a rotation times a random pairing — a permutation built from other permutations, in the way coverings were.

Cycle counts of random permutations are well understood. A uniformly random permutation of m things has, on average, 1 + 1/2 + 1/3 + … + 1/m cycles — the harmonic number H(m), which grows like the natural logarithm of m plus Euler’s constant 0.577. The reason is short. Build the permutation one cycle at a time, following each element to its image: when k elements are still unplaced, the next image closes the current cycle with chance 1/k, so the expected number of cycles is the sum of those chances. And the sum of reciprocals grows without bound but only logarithmically, so a random permutation of a million things has about fourteen cycles.

The corner map is not a uniformly random permutation. It is built from one fixed rotation and one random pairing, and it has a constraint: its cycle count always has the parity of n + 1, because the genus formula must give a whole number. The parity is forced by the sign of the permutation. A rotation of 2n corners by one step is a single cycle of even length, which is an odd permutation; a pairing is n swaps, whose sign is $(-1)^n$; so the corner map has sign $(-1)^{n+1}$. A permutation of 2n things with V cycles has sign $(-1)^{2n-V} = (-1)^V$, so V must have the parity of n + 1. Half of all permutations of the corners are ruled out before the pairing is even chosen.

But apart from the parity, the corner map behaves almost exactly like a uniform random permutation of its 2n corners, and the figures that follow show how closely.

Following one corner round #

The cycle picture can be watched directly, and doing so shows where the logarithm comes from. Start at a corner and apply the rule: move to the corner just after the partner of the edge that begins here. The next corner is, in effect, a random one among those not yet visited — the pairing was random, so where the partner sits is unpredictable — and the walk closes up only if it happens to land back on its starting corner.

Early in the walk, with most corners unvisited, the chance of landing on the start is tiny, and the first cycle usually runs on through a large share of all the corners. Once it closes, the next corner not yet visited starts a new cycle among the corners that remain, and the same thing happens on a smaller scale. The cycles therefore come in sizes that roughly halve: a first one covering a random fraction of the corners — on average half — a second covering a random fraction of the rest, and so on. The number of halvings needed to use up 2n corners is about the logarithm of 2n, and that is the vertex count.

The same process describes a random permutation of cards, where it is the reason that a shuffled pack has a long cycle and a few short ones, and the reason the chance that a shuffle leaves no card in place settles on 1/e. What the gluing adds is the fixed rotation, which makes the next corner not quite uniformly random — it is the corner after the partner, not the partner itself — and the parity constraint. Both change the answer by less than one vertex.

The exact distribution #

The Harer–Zagier recurrence gives the number of pairings of every genus for any polygon, so the chance of each vertex count can be computed exactly without sampling anything.

For twenty edges, more than half of all gluings leave exactly three vertices, and almost all leave one, three or five. For a hundred edges the peak has moved to five; for five hundred it sits at seven. The distributions are strikingly narrow: a polygon with five hundred edges could in principle leave anything from one vertex to 251, and virtually every gluing leaves between one and thirteen.

The drift is the logarithm at work. Multiplying the number of edges by five adds ln 5 ≈ 1.6 to the mean, and the curves in the figure step right by about that much each time. A polygon with a million edges would still leave, on average, only about fourteen vertices.

The narrowness is the other half of the same fact. For a random permutation, the number of cycles has variance also close to the logarithm, so its spread grows like the square root of the logarithm — slower still. For gluings the same holds, and it has been proved that the vertex count, suitably centred and scaled, is asymptotically normal, like a sum of many small independent effects — which, in the cycle picture, is what it is.

Four thousand gluings of a 200-gon #

The exact distribution comes from a recurrence. Sampling pairings directly and gluing them is an independent check, and it shows the distribution as an experiment would find it.

Each of the four thousand gluings was made by shuffling the two hundred edges and pairing them off in order, which gives every pairing the same chance; then the corners were followed round their cycles and counted. The bars match the dots: more than a third of the gluings leave five vertices, nearly a third seven, a sixth three, and fewer than one in a hundred leave only one. The sampled mean and the exact mean agree to within the sampling error.

So a random gluing of a 200-gon, a polygon that could make any surface up to genus fifty, typically makes a surface of genus 47 or 48. The four thousand samples include not one sphere, not one torus, and nothing with fewer than forty-three handles. The first essay on this topic presented every surface as a sphere with handles, listing them from the sphere up; the random gluing starts at the other end of that list and barely leaves it.

The mean, against the harmonic number #

The mean vertex count can be computed exactly for any polygon size from the recurrence, and compared with the harmonic number that a uniformly random permutation of the same number of corners would give.

The two curves separate visibly only at the smallest polygons, and from twenty edges on they are indistinguishable at this scale. At every size up to a thousand edges the exact mean exceeds H(2n) by less than 1/n. So a random gluing’s corners behave, to a very good approximation, like the cycles of a random permutation of the corners, and the average number of vertices is about ln(2n) + 0.58.

That gives the average genus directly. With V averaging about ln(2n) + 0.58,

$$\mathbb{E}[g] \approx \frac{n + 1 - \ln(2n) - 0.58}{2},$$

which is the maximum, about n/2, less half a logarithm. For a thousand edges, n = 500, the maximum genus is 250 and the average is about 247. The shortfall from the ceiling grows, but so slowly that relative to the ceiling it vanishes: the random surface has, in proportion, all the handles it can have. Nathan Linial and Tahl Nowik proved it in 2011 in the language of random chord diagrams — which are exactly these gluings — showing that the expected genus is n/2 less a term that grows like half the logarithm.

Where the sphere goes, and where one vertex stays #

The two ends of the census behave in opposite ways, and the contrast is the clearest picture of what randomness does.

The sphere is a gluing with no crossing chords, and those are counted by the Catalan numbers, which grow like $4^n$. The total number of pairings, (2n − 1)!!, grows like a factorial. Their ratio falls faster than any exponential: one gluing in three for the square, one in about thirty-nine thousand for twenty edges, and about one in 10³⁷ for eighty. The chance that a random pairing of a thousand edges makes a sphere has 986 zeros after the decimal point before its first significant digit.

The single vertex, the other extreme, is not rare at all. For even n it holds exactly one pairing in n + 1: one in five for the octagon, one in 101 for two hundred edges. That is almost exactly the chance a uniformly random permutation of 2n things is a single cycle, 1/(2n), doubled — 1/n against the true 1/(n + 1) — and the doubling is the parity constraint: a single cycle of even length is an odd permutation, so when n is even every permutation the corner map can be has the parity a single cycle needs, and half of all permutations have been ruled out. The permutation picture accounts for the size of the one-vertex share in a line; the exact 1/(n + 1), rather than 1/n, is where the fixed rotation leaves its mark.

So the sphere, which is the classification’s starting point, is lost among the pairings, while the surface of maximal genus — every corner glued to one point — keeps a share that shrinks only like the reciprocal of the size. A random gluing is far more likely to reach the ceiling than the floor, by a margin that grows beyond any exponential.

A larger random gluing #

At sixty edges the picture is denser, but the count is the same kind of number.

Sixty corners, three vertices: genus fourteen out of a possible fifteen. The chord diagram is a tangle in which nearly every chord crosses most of the others, which is the visual form of the fact that crossings are handles. A non-crossing chord — two neighbouring edges glued to each other, xx⁻¹ — would fold shut and remove a vertex’s worth of complexity, but among sixty edges paired at random there are few such neighbours, and in this sample there are none.

The same count of three vertices appeared for twenty-four edges and appears again here; the typical count has barely moved while the number of edges more than doubled. That is what logarithmic growth looks like from inside a single example. The difference between the two surfaces is almost entirely in the number of handles — five against fourteen — because the handles scale with the polygon and the vertices do not.

A typical member of an infinite family #

The classification of surfaces is a statement about every surface at once, and it treats them all alike: each is a sphere with handles, named by one number. Asking which surface is typical adds something the classification does not contain — a way of choosing surfaces at random — and the answer depends entirely on that choice.

Choosing the genus uniformly from zero up to the maximum would make the average surface have n/4 handles. Choosing a pairing uniformly, as here, gives nearly n/2. Neither is more correct; they are different questions. What the pairing model has in its favour is that it is the model the polygon itself suggests, with no weighting added, and that it is the one in which the counts come from a recurrence and the averages from a harmonic number. It is also the model in which a large random surface stops being random in any visible way: the vertex count concentrates, and a single sample of a large polygon tells almost everything about the next — as a running average of independent trials does once it has run long enough.

That concentration is the sense in which randomness produces order here. No gluing is predictable, but the surface it makes is: genus close to n/2, less about half the logarithm of 2n, with fluctuations of a vertex or two.

What the samples cannot show #

The shape of the surface. A gluing determines a surface only up to topology, and the figures record only its genus. Random surfaces can also be given a geometry — each polygon made a regular hyperbolic polygon, for instance — and then questions about their shortest loops, their diameters and their spectra become meaningful. Those have been studied, by Robert Brooks and Eran Makover among others, and they are not what a vertex count sees.

Whether the corner map is exactly uniform. The mean comparison shows the corner map behaving like a random permutation of the right parity to within 1/n, and the one-vertex share agrees with it to within a factor of (n + 1)/n. The full statement — how close the distribution of the corner map’s cycle type is to uniform on its parity class — is a theorem about characters of the symmetric group and is not drawn.

Non-orientable gluings. Letting each pair be glued either way round doubles the choices per pair and brings in one-sided surfaces. A random gluing of that kind is almost always non-orientable, and its cross-cap count has an analogous logarithmic shortfall; neither is computed here.

Random surfaces are the most complicated ones #

The classification lists the closed orientable surfaces in order of complexity: the sphere, the torus, two handles, three. A polygon of 2n edges can make any of them up to n/2 handles, and the natural instinct is to picture a random gluing somewhere in the middle of that range.

The census and the samples say otherwise. The vertex count of a random gluing is the cycle count of a permutation that behaves almost exactly like a random one, so it is about the logarithm of the number of edges, with a spread that is smaller still. The genus is therefore within half a logarithm of its ceiling. At a thousand edges the average surface has about 247 of a possible 250 handles, and the sphere — the first entry in the list — turns up about once in 10⁹⁸⁶ gluings.

What makes this more than a curiosity is that the answer is a harmonic number. The average vertex count of a random gluing tracks 1 + 1/2 + … + 1/(2n) to within 1/n — the same sum that governs cycles of shuffled cards and how many people in a room get their own hat back. Gluing polygons into surfaces turns out to be a way of shuffling corners, and the surface is recorded in how few cycles the shuffle leaves.