Curves that cross a line and close

How many ways a curve can cross itself counted the closed curves in the plane with $n$ self-crossings, every Gauss word on up to six letters tried, and found that the counts grow exponentially at a rate known only numerically. It ended by naming a close relative in the same state: meanders, closed curves that do not cross themselves at all but cross a fixed straight line, whose growth rate has been estimated to many decimal places and whose conjectured exponent comes from a field theory. This essay counts them.

The definition is simple enough to draw. Take a horizontal line — a river, in the picture that gave meanders their name, with a road winding across it — and a closed curve that crosses the line at $2n$ points, transversally, and never crosses itself. Two such curves are the same meander if one can be deformed into the other without changing the order of the crossings along the line or making the curve touch itself. How many meanders cross the line $2n$ times?

A pair of arch systems #

The question becomes combinatorial the moment the curve is cut along the line. Above the line the curve falls into $n$ pieces, each running from one crossing to another without meeting the others, so the pieces are non-crossing arches joining the $2n$ crossings in pairs. Below the line the same is true. A meander is therefore a pair of arch systems — one above, one below — and conversely any pair of arch systems glues into a set of closed curves that cross the line at those $2n$ points and nowhere cross each other.

The arch systems on $2n$ points are counted by the Catalan numbers, $C_n = \binom{2n}{n}/(n + 1)$: 1, 2, 5, 14, 42, 132, …, the count counting the paths that go wrong found for paths that never dip below their start, and for exactly the same reason — reading the points left to right, each arch opens or closes like a step up or down, and the arches never cross precisely when the path never goes below the line. So there are $C_n^2$ pairs, and the question is how many of them glue into one curve rather than several. For the hero, $C_6 = 132$, there are $17{,}424$ pairs, and $1{,}828$ of them are single curves.

The test is mechanical. Start at the leftmost crossing, follow its arch above the line to its partner, then that point’s arch below the line to its partner, then above again, and so on. The walk must return to the start, because each point has one arch above and one below; the pair is a meander exactly when the walk visits all $2n$ points before it does. The figures count meanders by forming every pair of arch systems and following every walk.

All eight of order three #

The smallest interesting case can be seen whole. With six crossings there are $C_3 = 5$ arch systems on each side and 25 pairs, and the figure draws the eight that make a single curve. The rest make two or three separate loops: a pair of identical systems, one reflected below the line, always makes $n$ small loops, each arch closing on its own mirror image, and that accounts for five of the seventeen failures.

The eight meanders fall into families under the two reflections, left to right and top to bottom. One is the simple snake, crossing back and forth like a sine curve and closing round the end; the others spiral, one arch nested inside another, so that the curve winds in towards the middle of the line and out again. That is the source of the counting difficulty in miniature: a meander can nest arches to any depth, and whether the nesting above meshes with the nesting below to make one curve depends on the whole arrangement, not on any local feature.

The curves are also an exercise in which side of the line is inside. A meander is a simple closed curve, so by the Jordan curve theorem it has an inside and an outside, and the straight line passes alternately in and out at each crossing. The $n$ segments of the line inside the curve are themselves non-crossing chords of the disc the curve bounds, which is another way to see the arch systems: a meander is a disc with $n$ chords drawn across it and $n$ more on the outside.

Counted to eighteen crossings #

The table carries the count to order nine, eighteen crossings, where there are $C_9 = 4{,}862$ arch systems and $23{,}639{,}044$ pairs to follow. The meanders number

$$1,\ 2,\ 8,\ 42,\ 262,\ 1{,}828,\ 13{,}820,\ 110{,}954,\ 933{,}458,$$

matching the counts published since the 1990s. Two things are visible. The share of pairs that close into a single loop falls steadily — 32% at order three, 10.5% at order six, 3.95% at order nine — because the pairs grow like $16^n$, the square of the Catalan growth rate of 4, while the meanders grow more slowly. And the ratio of each count to the last is climbing, from 2 to 4 to 5.25, through 6.98 at order six to 8.41 at order nine, and still rising.

That rising ratio is the whole difficulty. If the counts grow like $R^n$ for some rate $R$, the ratios must tend to $R$; but at order nine they are nowhere near any limit, and the obvious guess from the table — that they might level off near 9 or 10 — is wrong. The limit, from much longer computations, is about $12.26$.

Most pairs make several loops #

The meanders are rare because a random pair of arch systems makes several loops. The figure sorts all $2{,}044{,}900$ pairs of order eight by the number of loops: 110,954 make one, 406,012 make two, the peak is at three loops with 624,240, and the tail runs to the 1,430 pairs — $C_8$ of them — that make eight loops, each system paired with its own mirror image. A pair chosen at random makes 3.38 loops on average.

The full distribution is a meandric polynomial: weighting each pair by $q$ to the power of its number of loops gives a polynomial whose coefficient of $q$ counts the meanders, and whose value at $q = 1$ is $C_n^2$. Philippe Di Francesco, Orlando Golinelli and Emmanuel Guitter studied these polynomials in the 1990s and found that they are the traces of a natural algebra, the Temperley–Lieb algebra of statistical physics, in which joining two arch systems and counting the loops is the multiplication. The meanders are the coefficient of the lowest power of $q$, the far tail of this distribution, and the far tail of a distribution is always the hard part to count.

A growth rate known only by extrapolation #

If the counts behave like $C R^n n^{-\alpha}$, as the counts of most combinatorial objects do, then the ratio $M_n/M_{n-1}$ is approximately $R(1 - \alpha/n)$, a straight line in $1/n$. The figure plots the ratios against $1/n$ and draws a line through the last four. It reaches $11.26$ at $1/n = 0$ — an underestimate, because the ratios are still curving, and nine terms are too few for the line to have straightened.

Longer series do better. Iwan Jensen enumerated meanders by a transfer-matrix method, building them crossing by crossing and keeping only the information about how the arches already drawn are connected, and pushed the counts far beyond what pairing arch systems could reach. His series put the growth rate at $R = 12.2628\ldots$, the dashed line in the figure. The exponent is the stranger number. Di Francesco, Golinelli and Guitter argued in 2000, from the theory of two-dimensional quantum gravity — random surfaces coupled to matter fields — that meanders correspond to a pair of loop models on a random surface, and that the exponent is

$$\alpha = \frac{29 + \sqrt{145}}{12} = 3.4201\ldots,$$

an irrational number from the formula that gives the scaling dimensions of such theories. The longest enumerations agree with it to the precision they can measure. Neither the growth rate nor the exponent has a proof. Even that the limit $R$ exists is known only because the counts are supermultiplicative — two meanders can be joined into a larger one — which proves a limit without saying what it is.

Why counting meanders is hard #

Many counts of planar objects have exact formulas — the Catalan numbers themselves, the triangulations of a polygon, the planar maps that pairs of trees that count planar maps built from pairs of trees. Meanders resist because the condition “one loop” is global. For a planar map, the defining conditions are local at each vertex and face, and a recursive decomposition — remove an edge, split the map — reduces the count to smaller counts of the same kind. For a meander, removing an arch leaves a pair of systems that may make two loops, and the count of one-loop pairs does not decompose into counts of one-loop pairs.

The field theory explains what kind of object a meander is. Gluing two arch systems is like laying two independent systems of loops on a random surface; asking for one loop is like asking a loop model with weight $q$ per loop to have $q \to 0$, a “dense polymer” limit, and the two arch systems contribute two such models. Field theories of this kind have universal exponents computed from their central charges, and the $\sqrt{145}$ comes from two central charges of $-2$ each. That is a prediction with an excellent record in similar problems, and in this one it agrees with every number computed, but it rests on a correspondence between discrete counts and continuum theories that no one has made rigorous.

What an irrational exponent would say #

The conjectured exponent has a consequence that is worth spelling out, because it would separate meanders from almost every other planar object whose count is known. The Catalan numbers satisfy $C_n \sim 4^n/(\sqrt\pi\,n^{3/2})$, with the exponent $3/2$; their generating function $C(x) = \sum C_n x^n$ satisfies the quadratic equation $xC^2 - C + 1 = 0$, which the equation a sequence satisfies used to read off the formula. That is no accident. A sequence whose generating function is algebraic — a root of a polynomial equation with polynomial coefficients — always grows like $R^n n^{-\alpha}$ with $\alpha$ a rational number, and so does one whose generating function satisfies a linear differential equation with polynomial coefficients. The rational exponents of the Catalan numbers, of the planar maps, of the triangulations all reflect generating functions of this tame kind.

If the meander exponent really is $(29 + \sqrt{145})/12$, which is irrational, then the meanders’ generating function is neither algebraic nor even differentially finite: no polynomial equation, and no linear differential equation, can capture it. The same conclusion would hold for the closed curves of the previous essay, whose conjectured exponent is built from $\sqrt{13}$. That is a strong statement about a sequence defined by drawing curves across a line, and it is the precise sense in which meanders are harder than the objects that look like them. One word and four objects found that the Catalan numbers count paths, trees, triangulations and bracketings because all of them decompose recursively in the same way; meanders, if the exponent is right, admit no decomposition of that kind at all.

The simple closed curves on a torus, which the loops that never cross themselves classified completely by a slope in lowest terms, are at the other extreme: a single condition, coprimality, describes them all. A meander is also a simple closed curve, and also classified by how it meets something fixed — a line instead of a pair of generating loops — and the difference between the two classifications is the difference between a condition that can be checked locally, digit by digit of a fraction, and one that can only be checked by following the curve all the way round.

Older than its name #

The problem is older than its modern study. The stamp folding problem, which Édouard Lucas posed in 1891 and Jacques Touchard studied in 1950, asks in how many ways a strip of $n$ stamps can be folded into a pile, and a folding is a meander of a particular kind, a semi-meander, the curve crossing a half-line rather than a full one. Vladimir Arnold revived the closed meanders in 1988 in connection with the topology of real algebraic curves, and Sergei Lando and Alexander Zvonkin gave them their combinatorial theory in 1993, relating them to the Temperley–Lieb algebra and to the counts of closed curves crossing themselves, which are the same kind of object seen from the other side: a meander is a simple curve with a line through it, and a self-crossing curve is a curve that is its own line.

Nine terms cannot fix a limit #

The counts are exact. Every arch system is generated, every pair is followed round, and the meanders of orders one to nine match the published values; the loop distribution at order eight is exact for every pair, and its total and its top bar are checked against $C_8^2$ and $C_8$. The extrapolation in the last figure is a fit, and its value of 11.26 is a statement about nine terms, not about the limit; the 12.2628 and the exponent are quoted, not computed here.

Nothing in these figures shows that the ratios converge to 12.26, or that the counts follow a power law at all. Nine terms are consistent with the conjectured asymptotics and with many others, and the curvature of the ratios against $1/n$ is the visible sign that the leading behaviour has not yet taken over at order nine. The figures also count only closed meanders on an infinite line; meanders with several components, open meanders crossing a ray, and meanders on the sphere with two lines each have their own counts and their own conjectured exponents.

Still open: a proof of the exponent #

The open problems are the ones the essay began with. Is the growth rate $12.2628\ldots$ a number with a closed form, and is it determined by some equation the way the Catalan growth rate 4 is? Is the exponent really $(29 + \sqrt{145})/12$? A proof of either would need a way to count meanders that respects the global one-loop condition, and the most promising routes go through the Temperley–Lieb algebra and its determinants, where exact formulas exist for the full meandric polynomial’s structure but not for the coefficient that counts single loops.

There is also an intermediate question with a concrete answer still missing. The share of pairs that make a single loop falls like $(R/16)^n$, and the expected number of loops in a random pair grows linearly in $n$, with the order-eight mean 3.38. The distribution of the number of loops — whether it is approximately normal with mean and variance proportional to $n$, as heuristics suggest — has been studied numerically and through the field theory, and a proof that the number of loops satisfies a central limit theorem, with its constants, is not known.

One loop among many #

A closed curve crossing a straight line $2n$ times without crossing itself is a pair of non-crossing arch systems, one above and one below, that close into a single loop; there are $C_n^2$ pairs and the meanders among them number 1, 2, 8, 42, 262, 1,828, 13,820, 110,954 and 933,458 for $n$ up to nine, every pair followed round. A random pair makes several loops, and the meanders are the far tail — 3.95% of the pairs at order nine and falling. The ratio of successive counts is still climbing at 8.41, towards a growth rate estimated at 12.2628 from much longer series, with an exponent of $(29 + \sqrt{145})/12$ predicted by the physics of loops on random surfaces; neither number is proved, and the counts that grow like them are known exactly only as far as computers can follow every curve.