Ground Truth · combinatorics ↔ random matrices

The Longest Climb

Shuffle a deck 1..n and pull out the longest run of cards that only climbs — the longest increasing subsequence. Its length is not random noise: it homes in on 2√n. Deal the cards into piles by one greedy rule and the number of piles IS that length, exactly. This immersive page computes it live, watches the 2√n law emerge (exact for small n, Monte Carlo out to n=4000), and then crosses a seam no one expects: the tiny leftover wobble around 2√n follows the Tracy–Widom law — the very same distribution as the largest eigenvalue of a random quantum-mechanical matrix. A card game and a random matrix, one hidden law. A committed verifier recomputes every number, 20/20.

Take a deck numbered 1 to n and shuffle it. Now cross out cards until what remains only ever climbs — each kept card larger than the last, though they need not be neighbours. Keep as many as you can. That longest kept run is the longest increasing subsequence, and its length Lₙ is the quiet hero of this page. It looks like it should be a coin-toss of a number. It isn't. It knows exactly where it's going, and where it's going turns out to be the same place a random matrix goes.

I · the game that measures it

Deal it into piles

Here is a rule a child can follow. Turn the shuffled deck face up, one card at a time. Place each card on the leftmost pile whose top card is larger than it; if no such pile exists, start a new pile to the right. That's the whole game — it's the solitaire ritual called patience.

The astonishing part, proved by Hammersley and made famous by the theory of patience sorting: when the deck is gone, the number of piles is exactly Lₙ — the length of the longest climb. You never searched for the climb; the greedy piling found its length for free. Deal a few and watch.

II · where the length is going

It homes in on 2√n

One shuffle tells you little. Average Lₙ over all shuffles and a law appears: E[Lₙ] → 2√n (Vershik–Kerov and Logan–Shepp, 1977, independently). For small decks we can be exact — average the longest climb over every one of the n! orderings. The integer totals below are OEIS A003316; our brute force reproduces them, and dividing by n! gives E[Lₙ] to the last digit.

The ratio E[Lₙ]/√n climbs toward 2 — but slowly, and always from below. Beyond a handful of cards, exact enumeration is hopeless (13! already dwarfs a second's compute), so we shuffle: millions of seeded deals, out to a four-thousand-card deck. Drag n and deal to watch your own sample land on the committed curve.

III · the seam no one expects

The wobble is a random matrix

Center and magnify the leftover: look at (Lₙ − 2√n) · n^1/6, the tiny wobble the mean leaves behind. In 1999 Baik, Deift and Johansson proved what it converges to — not a bell curve, but the Tracy–Widom distribution F₂: lopsided, with a soft right shoulder and a cliff on the left.

That distribution has a day job. It is the law of the largest eigenvalue of a large random Hermitian matrix — the Gaussian Unitary Ensemble, the toy model physicists use for the energy levels of a heavy nucleus and the statistics of quantum chaos. A shuffled deck's longest climb and a random quantum Hamiltonian's top energy level have no shared machinery whatsoever. They share a limiting law. That is what universality means, and it is one of the strangest true facts in mathematics.

Below, both are sampled and standardized (shifted and scaled to a common footing). Watch two utterly different random systems pour into one silhouette.

The fingerprints agree with the published law. Tracy–Widom F₂ has skewness 0.2241 and excess kurtosis 0.0934. Our shuffle wobble (n=4000, 12,000 deals) measures skew 0.266, excess kurtosis 0.098; our random matrices (800×800, 12,000 draws) measure skew 0.183, excess kurtosis 0.090. Two systems, one shape, straddling the same limit from opposite finite-size sides.

And it closes the loop on Movement II. The reason E[Lₙ]/√n crawls toward 2 from below is that the mean of Tracy–Widom is negative — -1.7711 — so E[Lₙ] ≈ 2√n -1.771·n^1/6. At n=4000 that predicts a ratio of 1.8884; the shuffles delivered 1.8964. The same constant that governs the wobble governs the slowness of the climb. The card game was doing random-matrix theory all along.

If this bridge feels like a one-off, it isn't. The same Gaussian Unitary Ensemble statistics surface in the spacings between the zeros of the Riemann zeta function — the deepest unproven pattern in number theory. That coincidence has its own layer of this ground: the harmonics of the primes.