How many ways a curve can cross itself

The turns a tangent makes sorted closed curves by one number. A curve that keeps moving — never stopping, never forming a cusp — can be deformed into another such curve exactly when their tangents turn the same number of times, and the deformation is allowed to make and destroy crossings as it goes. By that measure there are only countably many kinds of curve, one for each whole number, and a circle and a curve with forty crossings may be the same.

Hold the crossings fixed instead, and the question changes completely. Two curves are now the same only when a homeomorphism of the plane, or of the sphere, carries one onto the other — so they must have the same number of crossings, met in the same pattern, with the same regions between them. Counted that way, how many different closed curves have $n$ crossings? The question has been asked since Gauss, and it has no formula. It does have an algorithm, and the algorithm is the subject of this essay.

There are six. Each of them, sent into the plane, can have any of its five regions as the unbounded outside, and some of those choices give curves that no homeomorphism of the plane can identify, so in the plane there are twenty. The most symmetric of the six, the curve shaped like a three-leaved figure, gives only two plane curves, because every one of its regions looks like one of two others; the least symmetric gives five.

A curve is a word and a few bits #

Walk once round a closed curve with $n$ crossings, writing down the name of each crossing as it is passed. Every crossing is passed twice, so the walk spells a word of length $2n$ in which each of $n$ letters appears twice: a figure-eight spells $aa$, the three-leaved curve $abcabc$. Gauss studied these words in the 1830s, and they are called Gauss words.

The word does not determine the curve. At each crossing the second passage crosses the first either from right to left or from left to right, and that is an independent bit. With the bits added, the cyclic order of the four branches leaving every crossing is fixed, and a set of cyclic orders at the vertices of a graph is exactly what is needed to say how the graph sits on a surface. The rule is the one that reads regions off a map drawn by its corners: start along a branch, and at every crossing turn to the next branch in the cyclic order; the walk closes up around one region, and the regions found this way are the faces of the surface the curve has been drawn on.

Which surface that is depends on how many regions there are. The curve is a graph with $n$ vertices of degree four and $2n$ edges, so if it has $F$ regions its surface has Euler characteristic $n - 2n + F = F - n$. The word and bits describe a curve on the sphere exactly when there are $n + 2$ regions; with fewer, the walk has found a curve on a torus or a surface with more handles, which cannot be flattened into the plane.

That makes the census an exhaustive search with a short program. List every Gauss word on $n$ letters — there are 1, 3, 15, 105, 945 and 10,395 of them for $n = 1$ to $6$, once letters are named in order of first appearance — try all $2^n$ choices of bits, count the regions, and keep the choices that find $n + 2$. For three crossings, 15 words and 8 bit patterns give 120 candidates, of which 42 close up on a sphere.

Telling two curves apart #

The 42 are not 42 different curves. The same curve, walked from a different starting crossing or in the other direction, spells a different word; reflected in a mirror, it flips every bit. To count curves rather than descriptions of curves, each candidate is turned into a canonical code: a breadth-first walk over the map’s half-edges, starting from every half-edge in turn and with both orientations, records the order in which half-edges are reached, and the least of those records is the curve’s canonical code. Two candidates are the same curve on the sphere exactly when their codes agree, because a homeomorphism of the sphere carrying one curve to the other is the same thing as a relabelling of half-edges carrying one map’s cyclic orders to the other’s, possibly reversed.

The same walk also counts symmetries: the number of starting points and orientations that achieve the least code is the number of ways the curve can be mapped onto itself. The three-leaved curve has twelve — three rotations, times two directions of travel, times a reflection — while the least symmetric three-crossing curve has two.

Those numbers make the census check itself. Each curve with $s$ symmetries is spelled by exactly $8n/s$ of the candidates — $2n$ starting passages, two directions, two mirror images, divided by the symmetries that make some of those coincide — and so the candidates must equal the sum of $8n/s$ over the classes found. For three crossings, $24/12 + 24/6 + 24/4 + 24/4 + 24/2 + 24/2 = 42$. It is the same orbit-counting identity that turned unlabelled trees into labelled ones and necklaces into a theorem about primes, and it holds at every size the census reaches, which is a check that no class was split or merged by mistake.

Drawing a curve from its word #

A word and its bits say what the curve is and not what it looks like. To draw it, the census uses the method of placing every point at the average of its neighbours: pin one region’s boundary to a circle, let every other vertex sit at the average position of the vertices it is joined to, and solve. William Tutte proved in 1963 that for a well-connected planar graph this never makes two edges cross. The curve’s own graph is not well-connected enough — a figure-eight’s outer region touches the crossing twice — so it is first refined twice, adding a point in every edge and every region and joining them up, which turns it into a triangulation where the theorem applies. The curve is then drawn as a smooth spline through its crossings and the points along its edges, with each loop that returns to its own crossing redrawn as a rounded petal, because the averaging squeezes such loops nearly flat.

Four crossings give nineteen curves on the sphere. The eight drawn first are the symmetric ones, with four or eight symmetries each — a circle with four outward petals among them, and the same circle with two of its petals turned inward. Of the other eleven, nine have a single non-trivial symmetry and two have none at all, and the number of plane curves each gives rises towards its number of regions, six.

Every curve has a small region #

The count of regions that decides whether a curve lies on a sphere has a consequence that can be read off every drawing in the figures. Each crossing has four corners and each edge has two sides, so the regions of a curve with $n$ crossings have $4n$ sides between them, and there are $n + 2$ regions. Give each region a deficit of four minus its number of sides; then

$$\sum_{\text{regions}} (4 - \text{sides}) = 4(n + 2) - 4n = 8,$$

whatever the curve. A region with four sides costs nothing, a triangle contributes one, a two-sided region two, a petal — a region bounded by a single arc from a crossing back to itself — three, and regions with more than four sides contribute negative amounts that the small ones must make up.

So every closed curve on the sphere with at least one crossing has a region with at most three sides, and in fact enough of them to account for a total deficit of eight. The three-leaved curve of the first figure shows the balance exactly: a triangle in the middle and a triangle outside contribute one each, and its three two-sided lobes contribute two each. A curve with no petals and no two-sided regions needs at least eight triangles; one whose only small regions are petals needs at least three of them.

The identity is the curve’s version of Descartes’ theorem that the corners of a convex solid fall short of flatness by seven hundred and twenty degrees in total, and for the same reason: both are Euler’s formula with the curvature gathered into the places where it lives. And the small regions it guarantees are exactly the ones the moves on knot diagrams act on: Reidemeister’s first move removes a petal, his second a two-sided region, his third reflects a triangle — so the identity says every knot diagram offers small regions where the moves can be tried, even when, as for a reduced alternating diagram, none of them can lower the number of crossings.

One curve on the sphere, many in the plane #

A curve on the sphere becomes a curve in the plane when one point of the sphere, not on the curve, is sent to infinity, and which region that point lies in is the only choice that matters.

The five drawings in the figure are one sphere curve and five plane curves. In the first the largest region, bounded by five arcs, is outside, and the curve looks like a figure-eight with one petal tucked inside a lobe and another hanging outside. Put one of the small petals outside instead, and everything else is inside that petal: the drawing turns inside out, the old outside becoming a bounded region nestled within. The step from one drawing to the next is an inversion in a circle, which is a homeomorphism of the sphere and so changes nothing about the curve as a sphere curve — and is not a homeomorphism of the plane, because it moves infinity.

A plane curve, then, is a sphere curve with one region marked, and two marked regions give the same plane curve exactly when a symmetry of the sphere curve carries one to the other. That is why the plane counts run ahead of the sphere counts by a factor that grows: a curve with $n$ crossings has $n + 2$ regions, and as symmetry becomes rare almost every one of them gives a different plane curve. The same marking turns the regions’ sizes into an invariant of the plane curve: the turning number of the essay on tangents depends on which region is outside, and a sphere curve’s five plane drawings need not all turn the same number of times.

The counts #

On the sphere the census finds 1, 1, 2, 6, 19, 76 and 376 curves with nought to six crossings; in the plane, 1, 2, 5, 20, 82, 435 and 2,645. Both sequences agree with the values tabulated in the 1990s, when Vladimir Arnold revived the problem as part of his theory of plane curves, and both grow faster than any power of $n$: the ratio of successive sphere counts is 2, 3, 3.2, 4, 4.9, and still rising at six.

Counting maps of this kind is a well-developed subject — pairs of trees count the planar maps with a given number of edges exactly, and Tutte’s formulas give the number of four-regular planar maps in closed form — but the restriction that the map be traced by a single curve, going straight through every vertex, destroys the structure that makes those formulas work. A four-regular map traced straight through generally falls apart into several closed curves, and asking for exactly one is like asking for a Hamiltonian circuit: easy to check, with no known way to count. The counts have been extended by computer far beyond these sizes, using transfer-matrix methods borrowed from statistical physics, and the growth rate they reveal is known numerically, while its exact value, and the power of $n$ that corrects it, rest on conjectures from physics rather than on proof.

Which words a curve can spell #

Not every Gauss word is spelled by a curve, and the question of which ones are is the one Gauss himself asked.

Gauss noticed that in every word a curve spells, each letter has an even number of letters between its two occurrences. The reason is a parity argument of the Jordan curve theorem’s kind: the part of the curve between the two passages through a crossing is itself a closed loop, and the rest of the curve enters and leaves it an even number of times. The condition cuts the words down sharply — to 2, 6, 24, 120 and 720 for two to six letters, against 3, 15, 105, 945 and 10,395 in all.

It is not sufficient. For one to four letters every word that passes Gauss’s test is spelled by some curve, and the census finds the first failures at five: 7 of the 120 words that pass it are spelled by no curve with any choice of directions. At six letters 128 of 720 fail. The complete answer needed more than parity. Max Dehn gave one in 1936; Ronald Read and Pierre Rosenstiehl gave a characterisation in 1976 in terms of a graph built from the word’s interlacings, and the criterion has since been reduced to a few conditions checkable in linear time. The census does not need any of them, because it simply tries every choice of directions, but it confirms the classical fact that parity alone runs out at five.

Symmetry becomes rare #

Up to three crossings every curve is symmetric. At four, 2 of 19 have no symmetry; at five, 20 of 76; at six, 198 of 376 — more than half. Symmetry here is a coincidence, and coincidences become rare as curves grow. That is worth contrasting with trees, where the opposite happens: almost every large tree can be turned over, because somewhere among its many leaves two hang from the same point and can be swapped. A curve has no such cheap symmetry. Its petals are attached at crossings with a definite cyclic order, and swapping two of them moves the rest of the curve too, so a symmetry has to be global or nothing. The orbit count checks this figure too, since the classes weighted by one over their symmetries must add to the number of candidates divided by $8n$: 0.25, 0.5, 1.75, 8.125, 44.9 and 279.08 for $n = 1$ to $6$.

As symmetry dies out the counts approach a simple relation: almost every curve is spelled by exactly $8n$ candidates, so the number of curves on the sphere is roughly the number of planar candidates over $8n$, and the number in the plane roughly $n + 2$ times that. At six crossings, 13,396 candidates over 48 is 279, against 376 curves, and the gap is the symmetric minority, which still holds almost half.

What the census does not show #

The census is exact for the sizes it reaches and silent beyond them; nothing here is a statement about seven crossings or a thousand. The drawings are pictures of the right curves but not canonical pictures: Tutte’s method places the crossings by averaging, so the shapes are faithful in their pattern of regions and arbitrary in their proportions, and a different choice of outer region or of weights would give a different-looking drawing of the same curve.

Nor does the census see the other ways of holding curves equal. Arnold’s theory distinguishes curves that can be deformed into one another without passing through a tangency of two branches or a triple point, and those finer classes carry invariants — his $J^+$, $J^-$ and $St$ — that change in controlled ways at each forbidden event. The curves counted here are the cells of that theory, each a region of curves that can be deformed into one another with no event at all, and the invariants are what remember how the cells are glued together. Knot diagrams are these same curves with an over-and-under choice at every crossing, and three moves on diagrams then decide when two diagrams tie the same knot — a third, coarser equivalence on the same drawings.

Still open: the rate of growth #

How fast does the number of closed curves with $n$ crossings grow? Exponentially, certainly — it lies between the number of four-regular planar maps, which grows like $12^n$, and a constant fraction of a smaller count — but the base of the exponential is known only numerically. Gilles Schaeffer and Paul Zinn-Justin computed the counts far beyond the sizes here and estimated it in 2004, and they conjectured, from the physics of random surfaces, the power of $n$ that multiplies the exponential — an irrational exponent built from $\sqrt{13}$, a prediction that agrees with the computations and has no proof. The closely related count of meanders — a closed curve crossing a straight line — is in the same state: its growth rate has been estimated to many decimal places and its conjectured exponent comes from a field theory, and no one has proved either.

A curve is a word that closes on a sphere #

A closed curve with $n$ crossings is a Gauss word and one bit per crossing, and it lies on a sphere exactly when tracing its regions finds $n + 2$ of them. Trying every word with every bit, and identifying the results by a canonical code, gives 1, 1, 2, 6, 19, 76 and 376 curves on the sphere and 1, 2, 5, 20, 82, 435 and 2,645 in the plane, where a curve gains one plane form for each of its regions that its symmetries do not identify. Gauss’s parity condition is necessary and first fails to be sufficient at five crossings; symmetric curves fall from all of them to fewer than half by six; and how fast the counts grow is known by computation and conjecture, not by proof.