The cheapest tree costs ζ(3)

One, plus a quarter, plus a ninth gave $n$ workers $n$ jobs at random costs and found that the cheapest way to pair them costs, on average, exactly $1 + 1/4 + 1/9 + \cdots + 1/n^2$ — a total that does not grow with $n$ and tends to $\pi^2/6$. That essay ended by pointing at a sibling result with a different shape of problem: the cheapest way to connect $n$ points when every link between them has a random cost.

The problem is the oldest in network design. Given $n$ towns and a cost for building a road between each pair, find the cheapest set of roads that lets every town reach every other. The answer is always a tree — a cycle would contain a road that could be removed — so it uses exactly $n - 1$ roads out of $\binom{n}{2}$ possible. When the costs are drawn independently and evenly from nought to one, how much does the cheapest tree cost?

The tree in the figure costs 1.064, though it uses 39 links and an average link costs a half. Its dearest link costs 0.06. Almost every link in it is among the cheapest few per cent of the 780 available, and as the number of points grows the total does not grow with it: Alan Frieze proved in 1985 that it tends to

$$\zeta(3) = 1 + \frac{1}{8} + \frac{1}{27} + \frac{1}{64} + \cdots = 1.2020569\ldots$$

Two greedy methods that cannot go wrong #

Cheapest trees are among the few optimisation problems that greed solves exactly. Joseph Kruskal’s method of 1956 takes the links in order of cost, cheapest first, and keeps each one unless it would close a cycle with links already kept. Robert Prim’s of 1957 grows one tree from a single point, each time adding the cheapest link from the tree to a point outside it. Both are exact, for the same reason: for any way of splitting the points into two groups, the cheapest link crossing between the groups belongs to some cheapest tree, and each method only ever adds such a link.

The computations behind every figure here use Prim’s method, which on a full table of $\binom{n}{2}$ costs takes time proportional to $n^2$, and check it against Kruskal’s on the first figure’s table. They agree to the last digit, as they must.

The argument for that crossing property is a short exchange. Suppose a cheapest tree does not contain the cheapest link crossing between two groups. Adding that link to the tree closes a cycle, and the cycle must cross between the groups at least once more, by some other link that costs at least as much. Removing that other link leaves a tree again, no dearer than before. So some cheapest tree contains the cheapest crossing link, and Kruskal’s and Prim’s methods only ever add links that are cheapest across some split.

That greed works here and fails almost everywhere else — for the cheapest tour, for instance, no fast exact method is known — is a fact about the structure of the problem: the sets of links containing no cycle form what is called a matroid, and on a matroid the greedy method is always optimal. The random version of the problem inherits that luck. A random instance of a problem greed solves can be analysed by following the greedy method as it runs, and that is exactly what Frieze’s proof does.

The cost settles #

Averaged over many random tables, the cost is 0.968 at five points, 1.112 at ten, 1.169 at twenty, 1.195 at a hundred and 1.198 at two thousand, against $\zeta(3) = 1.2021$. The tree has $n - 1$ links, so the average link in it costs about $\zeta(3)/n$: each link is about as cheap as the cheapest of $n$ random costs, which is about $1/n$. The tree manages to be built almost entirely out of links that are each nearly the cheapest available at their point.

The smallest cases can be done by hand. With two points there is one link and the tree is that link, costing a half on average. With three points the cheapest tree takes the two cheapest of three links, and the expected values of the smallest and middle of three even draws are a quarter and a half, so the tree costs three quarters. With four points the tree takes three of six links, but not always the three cheapest — those might form a triangle — and the exact average is already an awkward rational number. The simulation’s 0.968 at five points continues the climb, and by twenty points the cost is within three hundredths of its limit.

Why the constant is $\zeta(3)$, and not some other number of about the same size, is the content of the theorem, and the proof shows it with unusual clarity.

Kruskal’s method is a growing random graph #

Run Kruskal’s method and watch the links it considers, in order of cost. By the time it has considered every link costing at most $p$, it has looked at a graph on $n$ points in which each link is present independently with probability $p$ — exactly Erdős and Rényi’s random graph. The links Kruskal keeps are the ones that join two previously separate pieces of that graph. So every time the number of pieces $\kappa(p)$ drops by one, Kruskal adds a link costing $p$, and the total cost of the tree is

$$\sum_{\text{kept links}} p = \int_0^1 \big(\kappa(p) - 1\big)\, dp,$$

the area under the curve of pieces, less the final single piece. The cost of the cheapest tree is a statement about how fast a random graph comes together.

The pieces come together on the scale $p = c/n$, where the average point has $c$ links. At that scale almost every piece is a tree, and the expected number of tree-shaped pieces with $k$ points is about

$$n \cdot \frac{k^{k-2}\, c^{k-1}\, e^{-kc}}{k!}$$

— Cayley’s count of $k^{k-2}$ labelled trees on $k$ points, times the chance that a particular such tree’s $k - 1$ links are present, times the chance that none of the roughly $kn$ links leaving it are. The figure’s line is the sum over all $k$, and the shaded columns, measured on 3,000 points, follow it to within a few hundredths everywhere and to much better away from $c = 1$, where the random graph is in the window in which its giant piece is born and finite sizes matter most.

Scaling back from $c$ to $p$ multiplies the area by $1/n$ and the pieces by $n$, so the tree’s cost tends to the area under the limiting curve:

$$\int_0^\infty \sum_{k \ge 1} \frac{k^{k-2}\, c^{k-1}\, e^{-kc}}{k!}\, dc = \sum_{k \ge 1} \frac{k^{k-2}}{k!} \cdot \frac{(k-1)!}{k^{k}} = \sum_{k \ge 1} \frac{1}{k^3}.$$

Each size of tree contributes exactly $1/k^3$. Pieces of one point contribute 1, pieces of two points contribute 1/8, pieces of three contribute 1/27, and so on, and the cost of the cheapest spanning tree is the sum. The figure integrates the limiting curve numerically to 1.20205.

Most of the cost is paid by loners #

The sum has a reading that is easy to miss. The term $1/k^3$ is the area contributed by pieces of $k$ points, and the first term, 1, comes from pieces of a single point — points that have not yet been joined to anything. Of the total 1.202, the isolated points account for 1, or 83%. Pairs account for $1/8$, about 10%, and every larger size together for the remaining 7%.

That says where the money goes. Most of the tree’s cost is spent on the moment each point stops being alone: the link by which a lone point first joins anything. In the random graph growing by cost, a point stays isolated until its cheapest link appears, which happens at a cost of about $1/n$ — and the integral of the isolated points’ share, $\int_0^\infty e^{-c}\,dc = 1$, is exactly the sum of those first links, scaled. The rest of the tree, joining pairs to pairs and small trees to small trees, costs the remaining fifth.

A crude bound tells the same story from the other side. Every spanning tree contains, at every point, at least one link at that point, so it costs at least half the sum, over all points, of each point’s cheapest link — half because a link can be the cheapest at both its ends. Each point’s cheapest link costs about $1/n$, so the bound is about $1/2$. The true value, 1.202, sits a little above twice the bound, and the sum over $k$ says exactly how much more than the loners’ links a connected network needs.

How much it varies #

The cost of a tree on 400 points is the sum of 399 random link costs, but not independent ones, since each link was chosen because it was cheap given the others. It nevertheless follows a bell curve, and a remarkably narrow one: the 1,500 trees in the figure have a standard deviation of 0.064, which times $\sqrt{400}$ is 1.288. Svante Janson proved in 1995 that the cost is asymptotically normal with variance $(6\zeta(4) - 4\zeta(3))/n$, whose square root times $\sqrt n$ is 1.298. The whole tree varies less than a single link does, which is the general habit of an average of many weakly dependent pieces, and the variance has its own zeta values, one argument higher.

Only the cheapest links matter #

The cheapest tree never uses a link that costs more than a few multiples of $1/n$, so it never consults the cost distribution anywhere except near nought. Frieze’s theorem says exactly this: if the costs have density $f$ with $f(0) > 0$, the cost tends to $\zeta(3)/f(0)$. Exponential costs, with density 1 at nought, give the same limit as costs spread evenly from 0 to 1 — 1.194 against 1.207 at 500 points, both within sampling error of 1.202. Costs spread evenly over twice the range give twice the limit, and so does a distribution that adds a half to half its draws, though the two look nothing alike above $1/2$; at 500 points they cost 2.400 and 2.426, against 2.404.

A distribution with no density at nought — the larger of two independent even draws, whose density near nought is $2x$ — gives no limit at all: the cheapest tree on 500 points costs about 22, and the cost grows like $\sqrt n$. The behaviour of the whole optimisation is decided by the shape of the cost distribution in an interval of width a few times $1/n$, and the rest of the distribution could be anything.

The growth like $\sqrt n$ follows from the same picture. For the random graph of usable links to come together, each point needs on the order of one link of usable cost, which means a cost $x$ with $n\,F(x)$ of order one. When $F(x)$ behaves like $x^2$ near nought, that cost is about $n^{-1/2}$ rather than $n^{-1}$, and a tree of $n - 1$ links each costing about $n^{-1/2}$ costs about $\sqrt n$. Wherever the density at nought vanishes, the tree’s cost grows; wherever it is infinite, the cost falls to nought; and only when it is a positive finite number does the answer settle on a constant, $\zeta(3)/f(0)$.

A tree, a pairing and a tour #

The tree is the cheapest of three classic structures on random costs, and each has a limit that does not grow with $n$. The cheapest assignment of $n$ workers to $n$ jobs tends to $\pi^2/6 = 1.645$, as Parisi’s formula showed exactly; at 120 points the computation gives 1.621. The cheapest tour through all the points, a closed path visiting each once, tends to 2.0415…, a constant that Johan Wästlund proved in 2010 is the solution of an equation from statistical physics and that has no known closed form. The tree is cheapest because it is least constrained — it need not return to its start, pair anything, or visit each point exactly twice — and its constant is the most explicit.

The tree is also a floor under the tour in every single instance, not just on average. Remove any one link from a tour and what is left is a path through every point, which is a spanning tree; so the cheapest tour always costs at least as much as the cheapest tree, and on random costs at least $\zeta(3)$. That inequality is the starting point of the classical approximations for tours, which build a cheap tour out of a cheap tree, and it is why the tree’s constant is the easiest of the three: it is the relaxation the others are measured against.

The appearance of $\zeta(2)$ for the assignment and $\zeta(3)$ for the tree is tempting to read as a pattern, and it is not one in any simple sense: the two come from different proofs, the assignment’s from a recursive structure discovered by Parisi and proved by Linusson, Wästlund, Nair, Prabhakar and Sharma, the tree’s from the component count above. That $\zeta(3)$ is irrational at all is Apéry’s theorem of 1978, and nothing is known about it beyond that — so the cost of a random cheapest tree is a number that is known to be irrational and not known to be anything else.

Where ζ(3) turns up #

The constant has a habit of appearing where something three-dimensional is being counted or something cubed is being summed. Piling cubes into the corner of a room gives partition counts whose growth is governed by $\zeta(3)$ where flat partitions had $\pi$. The integral $\int_0^\infty x^2/(e^x - 1)\,dx = 2\zeta(3)$ counts the photons in a box of radiation. And here the cubes come from three separate powers of $k$ that cancel against Cayley’s $k^{k-2}$: one from the size of a piece, two from the $k$ links leaving it that must all still be absent. The appearance is the end of a calculation rather than a reason, and the calculation is the explanation.

What the computations show and assume #

Every cost in the figures comes from an exact cheapest tree on a fresh random table; nothing is approximated except by sampling. The theorems are about the limit, and the figures show where finite sizes stand: the mean is within a few thousandths of $\zeta(3)$ by two thousand points, the component curve within three hundredths at three thousand, the spread within one per cent of Janson’s value at four hundred.

The model assumes every pair of points can be linked and every link’s cost is independent of every other’s. Real networks are neither: the towns sit in a plane, and the cost of a road depends on the distance, which makes nearby links correlated through shared endpoints. For points scattered at random in a square with costs equal to distances, the cheapest tree grows like $\sqrt n$, with a constant known only numerically, and the elegant independence that gives $\zeta(3)$ is lost. The figures cannot show the geometric case, and its constant remains a measured number.

Still open: the corrections, and the geometric constant #

How does the expected cost approach $\zeta(3)$? For costs drawn evenly from 0 to 1 the expected cost of the cheapest tree on $n$ points has an exact formula as a finite sum, found by Colin Cooper, Alan Frieze and collaborators in 2016, and its expansion in powers of $1/n$ is known to its first terms; for other distributions only the leading constant is known in general. The geometric versions — points in a square, costs equal to distances — are further from understood: the constant multiplying $\sqrt n$ for the cheapest tree, and the analogous constants for the cheapest matching and the shortest tour through random points, the last of which goes back to Beardwood, Halton and Hammersley in 1959, are known only by simulation, and no formula for any of them is in sight.

The area under the pieces #

On random link costs the cheapest spanning tree costs ζ(3), and the reason is visible in Kruskal’s method. Adding links cheapest first is watching a random graph grow, each kept link joins two pieces, and so the cost is the area under the number of pieces; at the scale where each point has $c$ links the pieces are trees of every size, the trees of size $k$ contribute exactly $1/k^3$ to the area, and the sum is $1 + 1/8 + 1/27 + \cdots$. The cost varies by $\sqrt{(6\zeta(4) - 4\zeta(3))/n}$, depends on the cost distribution only through its density at nought, and sits below the cheapest assignment’s $\pi^2/6$ and the cheapest tour’s 2.0415 because a tree is the least that connecting everything can demand.