The longest climb in a cube

The longest climb of a shuffle followed John Hammersley’s picture of a random permutation: scatter $n$ points at random in a square and look for the longest chain of them climbing up and to the right, each point higher and further right than the last. Its length is about $2\sqrt n$. The constant 2 took from 1972 to 1977 to establish, by Anatoly Vershik and Sergei Kerov and independently by Benjamin Logan and Larry Shepp, and the fluctuations around it took until 1999, when Jinho Baik, Percy Deift and Kurt Johansson found that they follow the Tracy–Widom law of random matrices. The planar problem is one of the most completely solved in probability.

One dimension up it is almost entirely open. Scatter $n$ points in a cube and look for the longest chain climbing in all three directions at once — each point further right, further back and higher than the one before. Its length grows like $c_3\, n^{1/3}$ for a constant $c_3$, and nobody knows what $c_3$ is. The same is true in every dimension above two. What is known is a single theorem that holds for all of them, and a single count behind it.

Chains in a cube #

A chain is a set of points that can be listed so that every coordinate increases along the list. In one dimension every set of distinct numbers is a chain, so the longest chain among $n$ points has all $n$. In two dimensions it is the longest increasing subsequence of a permutation: sort the points by their first coordinate and read off the second, and a chain is an increasing run within that sequence, not necessarily consecutive. In three dimensions, sorting by the first coordinate leaves two sequences, and a chain must increase in both — the longest increasing subsequence common to two permutations, in effect, for which the longest common subsequence of two strings is the closest well-studied cousin.

Finding the longest chain is easy for a computer — far easier than counting the ways to sort a partial order, which is hard in general. Sort the points by their first coordinate; then for each point in turn, its longest chain ending there is one more than the longest chain ending at any earlier point that it exceeds in every other coordinate. That takes a number of comparisons proportional to $n^2$, a fraction of a second for eight thousand points, and the figures use it on every sample.

Four hundred points in a cube give a chain of 14. In a square the same number of points would give a chain of about 35. The difference is that a chain in a cube must climb in three directions at once, and two random points are comparable — one above the other in every coordinate — with probability $2/2^d$: a half in the square, a quarter in the cube, an eighth in four dimensions. Fewer comparable pairs leave room for fewer long chains. The cube’s chain is $c_3 n^{1/3}$ with $n^{1/3} = 7.4$, and the measured ratio of 14 to 7.4 is near 1.9.

A chain in a cube is two climbs at once #

Sorting the points by their first coordinate turns a cloud in the cube into two sequences, the second and third coordinates read in that order, and a chain is a set of positions where both sequences increase. That is why the cube is not simply the square twice over. In the square the longest chain is the longest increasing subsequence of one random sequence, about $2\sqrt n$. Each of the cube’s two sequences has such a subsequence, of the same length, but the two are almost never in the same places, and a chain must use positions that serve both.

The comparison with strings is close. The longest common subsequence of two random strings asks for positions where two sequences agree, and its length is a constant times $n$ for a constant that is also unknown. The cube’s chain asks for positions where two sequences both climb, and its length is a constant times $n^{1/3}$. Both problems are about two independent random sequences forced to cooperate, both have answers that grow like a known power of $n$ times an unknown constant, and in both the constant has resisted every exact method. What makes the plane special is that one sequence is enough: there is nothing to cooperate with, and the tableau correspondence can count its climbs exactly.

The cooperation also explains the shrinking chains numerically. A pair of points is comparable in the square half the time, in the cube a quarter, in $d$ dimensions $2^{1-d}$ of the time, so the comparability graph thins out exponentially with the dimension, and the longest chain drops from $n$ in one dimension to about $2\sqrt n$ in two and about $n^{1/3}$ times a constant in three. In high dimensions most pairs of points are incomparable, and the widest set of mutually incomparable points becomes most of the cloud.

The constants nobody knows #

The hero follows the ratio $L/n^{1/d}$ as $n$ grows from 250 to 8,000, in dimensions two to five. In the plane it climbs from 1.77 to 1.92, towards the proved limit of 2. In the cube it climbs from 1.85 to 2.13; in four dimensions from 1.77 to 2.14; in five from 1.69 to 2.03. None has stopped climbing at eight thousand points, and in every dimension the limit is somewhere above the last value.

That the limits exist at all is a theorem. Béla Bollobás and Peter Winkler proved in 1988 that for every $d$ the ratio converges to a constant $c_d$, that $c_d < e$, and that $c_d \to e$ as $d \to \infty$. Beyond that, only bounds and estimates are known: simulations with far more points than these, extrapolated, place $c_3$ clearly above the values reached here, and the higher constants are known less precisely still. The figures here do not attempt that extrapolation: at eight thousand points the corrections are too large, and the next figure shows how large they are even where everything is known.

Where e comes from #

The bound $c_d < e$ comes from counting chains, and the count is short enough to do in full. Take any $k$ of the $n$ points. Sorted by their first coordinate, they form a chain exactly when each of the other $d - 1$ coordinates is also sorted in the same order. For random points each coordinate’s order is an independent random permutation of the $k$ points, which matches the first coordinate’s order with probability $1/k!$. So the probability that $k$ given points form a chain is $(1/k!)^{d-1}$, and the expected number of $k$-point chains among all the points is

$$\binom{n}{k} \frac{1}{(k!)^{d-1}}.$$

When the expected number of $k$-chains is less than one, the chance that any exists is less than one too, and when it is much less than one there is almost certainly none. So the longest chain is almost never longer than the $k$ at which the count falls through one. Counting what is expected is the first-moment method in its simplest form. With $\binom{n}{k} \approx n^k/k!$, the count is about $n^k/(k!)^d$, and by Stirling’s formula $k! \approx (k/e)^k$, so it is about $(e^d n / k^d)^k$, which falls through one at $k = e\, n^{1/d}$. That is where $e$ comes from: the factorial’s growth, raised to the power of the dimension. For 8,000 points in a cube the exact count crosses one after $k = 51$, a little below $e\,n^{1/3} = 54.4$, because Stirling’s approximation is not exact at these sizes.

The longest chains actually found fall well short: 42.5 on average. The first moment counts chains that might overlap — many chains share most of their points — and the expected count can be large while the actual count is usually zero, because the chains that exist come in large clumps. Bollobás and Winkler’s proof that $c_d$ approaches $e$ in high dimensions is the statement that, as the dimension grows, the clumping becomes negligible and the first moment tells the truth.

In the plane the overshoot is exact and known: the first moment says $e$, the truth is 2. The gap between $e$ and 2 is the cost of ignoring clumping in two dimensions, and Bollobás and Winkler’s theorem says the corresponding gap closes as the dimension grows. How fast it closes, and what the constants are in between, is the open part.

Stirling at small sizes #

The first-moment threshold is exact as a count and approximate as a formula, and the gap between the two is instructive. The count crosses one after $k = 51$ for 8,000 points in a cube, and the formula $e\,n^{1/3}$ says 54.4. In the square the count crosses after 237 and the formula says 243. Both differences come from the same place: Stirling’s formula is $k! \approx \sqrt{2\pi k}\,(k/e)^k$, and the square-root factor, ignored in the quick calculation, makes the factorials a little larger than $(k/e)^k$ and the threshold a little smaller than $e\,n^{1/d}$. The correction is a factor that tends to one, but slowly, like a power of $\log k$ over $k$.

So there are three numbers for each dimension: the first-moment threshold, which tends to $e$; the true constant $c_d$, below it; and the finite-size measurement, below that. In the plane they are $e$, 2 and 1.92 at eight thousand points. In the cube they are about 2.55 as a count at that size, $c_3$ unknown, and 2.13 measured. The theorem that $c_d \to e$ says that the first two meet as the dimension grows; nothing says how fast.

The other side of a Ramsey statement #

A long chain is one half of an inevitable kind of order. Leon Mirsky observed in 1971 that the fewest antichains — sets of mutually incomparable points — needed to cover a partial order is exactly the length of its longest chain, so a set of $n$ points with longest chain $L$ must contain an antichain of at least $n/L$ points. For random points in a cube that is an antichain of at least $n^{2/3}/c_3$ points: in a cloud of 8,000 points with a longest chain of about 42, some 190 points are pairwise incomparable. Either a long chain or a wide antichain must exist in every partial order, which is the shape of every statement in Ramsey theory, and random points show which side wins: in the cube, overwhelmingly the antichain.

Even the plane converges slowly #

A simulation’s ratio at eight thousand points is a poor estimate of its limit, and the plane, where the limit is known, shows by how much.

The correction $-1.7711\, n^{1/6}$ comes from the Tracy–Widom distribution, whose mean is $-1.7711$: the longest chain is $2\sqrt n$ plus fluctuations of size $n^{1/6}$ whose average is negative. Divided by $\sqrt n$, the correction is $-1.7711\, n^{-1/3}$, which at 8,000 points is still $-0.09$ — the gap between the measured 1.92 and the limit of 2. It shrinks only as the cube root of $n$, so a simulation would need about ninety thousand points to get within two per cent of the limit and ninety million to get within 0.2 per cent.

In three dimensions nothing is known about the correction: not its sign for certain, not the power of $n$ it scales with. If it behaves as it does in the plane, the measured 2.13 at eight thousand points is several per cent below $c_3$. The hero’s curves climbing to the right at their last points are the visible sign that the limits lie beyond the reach of the picture.

Fluctuations that shrink #

The plane has one more celebrated feature: the longest chain fluctuates by about $n^{1/6}$, far less than the $n^{1/4}$ that a sum of independent pieces of its size would give, and the shape of the fluctuations is the Tracy–Widom law. In the cube the fluctuations are smaller again.

Over the range simulated, the square’s fluctuations grow from about 2 to about 4.7 and the cube’s from about 1.1 to about 1.5. The square’s slope of 0.24 is above its asymptotic $1/6$ because of the same slow corrections; the cube’s slope is near 0.1. Whether the cube’s fluctuations follow a law with a universal shape, as the plane’s do, and what power of $n$ governs them, are not known. Few samples at the largest sizes make the slopes here uncertain, and they are drawn to show the difference between the two dimensions, not to measure either exponent.

The constant in three dimensions is unknown #

The constants. The figures show that $c_3$ is above 2.13 and almost certainly well above it, and that it is below $e$. They do not estimate it to any useful precision, and an extrapolation from these sizes would be a guess about a correction nobody has computed.

Exact chains, random points. Every chain drawn is exactly the longest in its sample; the samples are random and seeded, so the drawings repeat, but they are samples. With 8 samples at 8,000 points, the mean in the hero is uncertain by about half a point of chain length, roughly 0.02 in the ratio.

Only cubes and uniform points. Bollobás and Winkler’s theorem is about points spread evenly in a cube. Points spread unevenly, or in a region of another shape, give different constants, and in the plane the dependence on the shape and density is known exactly; in higher dimensions it is not.

The sizes are set by the method. The quadratic comparison that finds each longest chain is exact and simple, and it is the reason the figures stop at eight thousand points: doubling the points quadruples the work. In the plane the longest chain can be found in time proportional to $n \log n$ by patience sorting, which is how planar simulations reach billions of points. In three dimensions the same trick needs a data structure that answers, for a new point, the longest chain among earlier points below it in two coordinates at once — a two-dimensional range query — and with it simulations reach millions of points. The figures trade that reach for transparency; every chain they report can be checked by eye against its definition.

Still open: the constant in three dimensions #

What is $c_3$? The plane’s answer came from a correspondence that has no three-dimensional analogue: Robinson and Schensted’s bijection between permutations and pairs of tableaux, which turns the longest chain into the length of the first row of a random tableau, whose shape has a limit that can be computed. A set of points in a cube is a pair of permutations relative to the first coordinate, and no bijection is known that turns the longest common chain of two permutations into something with a computable limit shape. The poset of points under the coordinatewise order is a partial order with a longest chain and a widest antichain, and in the plane those two are linked by Greene’s theorem through the tableau; in three dimensions the link breaks.

A second question sits alongside: is there a law for the fluctuations in three dimensions with the universality that Tracy–Widom has in two? The plane’s fluctuations are the same for random points, random permutations, last-passage percolation and the largest eigenvalue of a random matrix, a coincidence that is now a theory. Nothing comparable is known for chains in a cube, and the figures here are too small to suggest what it might be. The contrast with the worst case is instructive too: Erdős and Szekeres’s staircase guarantees a chain or a falling chain of length about $\sqrt n$ in every arrangement of points in the plane, so the random case sits only a factor of two above the guaranteed one — and in higher dimensions the guarantees for every arrangement are far weaker, while the random chains keep growing like $c_d\,n^{1/d}$.