What the net heuristic cannot find

The previous rung found that most unfoldings of a subdivided solid are not nets at all — the faces land on top of one another — and that a simple heuristic, unfolding outwards breadth-first from a chosen face, finds a valid net far more often than a random tree does. It closed by recording what it could not say: how good that net is. Beating guessing is a low bar, and nothing had computed what the best available net would have been.

This rung pays that. For a solid small enough, every net can be listed, so the question has an exact answer rather than a hope.

What a net is scored on #

Validity is not a score, it is a filter, and for the Platonic solids it filters nothing: every unfolding of a Platonic solid is a net, all 384 of the cube’s included. So the ranking has to be on something else.

The quantity used here is the one rung six introduced: the separation a net costs. Every edge that is cut appears twice on the page, and the two copies land some distance apart. Sum that distance over every cut, in units of the net’s own edge length, and the result says how far a reader has to look to find the other half of something the cut went through.

It cannot be zero. The number of cuts is fixed by the solid — a net of an F-faced solid always cuts E − F + 1 edges — so what varies is not how much is cut but where the cuts put things.

Every net of the three smallest solids #

Enumerating every spanning tree of the face graph and scoring each:

Two results, and the second was not the one this rung was written to find.

The choice of net is worth up to 1.71×. All of these nets are valid, all of them are printable, and one of them scatters a solid’s neighbours 71 per cent further than another. Nothing in the picture of a net says which kind it is.

And the heuristic finds the best one, exactly. Rank one of 384, on both six-face and eight-face solids. The plan for this rung expected a gap — a percentage by which the heuristic falls short — and there is none to report.

That is the stronger answer and it changes what the limit of the heuristic is. The question is no longer how much worse; it is up to what size is it known at all.

The distribution, not only its ends #

The best and the worst are the extremes of a distribution, and the shape between them decides how much a good method is worth.

Sorted, the curve rises steeply at first, flattens across most of its length, and rises steeply again at the top. That shape says the space is not a plateau with a few outliers: a net drawn at random from the valid ones lands, on the octahedron, around 8.0 against a best of 6.06 and a worst of 10.39 — about 32 per cent above the optimum, in the middle of a broad band.

So a method that reliably lands at the bottom of the curve is worth roughly a third of the separation, and a method that lands anywhere in the middle is worth nothing in particular. That is the value the heuristic is capturing on the small solids, and it is the value whose capture is unmeasured on the large ones.

Where the enumeration stops #

The count of nets is a determinant rather than a search — Kirchhoff’s matrix–tree theorem turns it into the determinant of a reduced Laplacian, so the number is available without listing a single tree:

The dodecahedron and the icosahedron have the same number, and the reason is that each one’s face graph is the other’s vertex skeleton — the two are duals, and a spanning tree of one graph is a spanning tree of the other. Dividing 5,184,000 by the 120 symmetries of either solid gives 43,200, against the 43,380 distinct nets that are usually quoted; the difference is the trees that a symmetry maps to themselves, which are counted once rather than 120 times.

The ceiling is at twelve edges in the face graph, which is the cube and the octahedron. Everything above it is unreachable by listing: 3.5 × 10²⁸ is not a number a computer gets through, whatever the computer.

The number that is fixed before any choice is made #

Before any net is chosen, one number is already decided, and it is worth putting beside the ranking so the ranking is read at the right size.

A net keeps exactly F − 1 edges joined and cuts the other E − F + 1, whichever spanning tree it is. The cube has twelve edges and six faces, so every one of its 384 nets cuts seven of them — not most, not usually, every one. The icosahedron cuts eleven of its thirty. A geodesic solid at the second subdivision cuts forty-one of its hundred and twenty.

So the choice being optimised here is not how much to cut, which is fixed, but where the cut ends up putting things. That is a smaller decision than it first appears, and the 1.33 to 1.71 spread above is the whole of what is available to win — the other, larger quantity was spent before the search began.

It is also why the search is combinatorial rather than continuous. There is no net that cuts a little less; there is a finite set of nets, each cutting the same total length, differing only in arrangement. More faces buys less distortion and costs more cutting is the continuous trade; this is the discrete one underneath it, and it has no dial.

What a sample can and cannot say #

The standard move when a search space is too large is to sample it: try a few thousand at random, take the best, and report the heuristic’s gap against that.

Done on the ν = 2 geodesic solid, with eighty faces, the sample does not reach the heuristic at all:

The heuristic’s net is 10 per cent better than the best of eight hundred random ones, and the sample is closing on it from above rather than passing it. Only 203 of those 800 random trees were valid nets at all, which is the previous rung’s finding restated.

So the sample says two things and neither is the one wanted:

It cannot show the heuristic is beatable, because it never beats it.

It cannot show the heuristic is optimal, because a sample of 800 out of 3.5 × 10²⁸ is not evidence about the other 3.5 × 10²⁸.

Those two possibilities look identical from inside a sample, and nothing about running more samples separates them. That is the difference between a search and a certificate, and it is the same distinction the covering ladder keeps running into: finding a good arrangement is easy, and proving nothing better exists is a different kind of problem this site does not solve.

What the limit actually is, stated exactly #

The shortfall this rung pays asked for the heuristic’s limit. It is three sentences:

Up to eight faces the heuristic is provably optimal, by exhaustion, on every solid the ceiling admits — rank one of 16, 384 and 384.

Above eight faces nothing is proved. The heuristic is better than any sample taken, by 10 per cent on the eighty-face solid, and that is a statement about the sample.

And the gap between best and worst valid net is 1.33 to 1.71× on the solids where it is known. So the thing the heuristic is doing well is worth doing well — a randomly chosen valid net really is much worse — and how much of that value it is capturing above the ceiling is unmeasured and, by this method, unmeasurable.

Why the heuristic works, as far as anyone can say #

An optimum attained on every case that can be checked invites an explanation, and the honest position is that there is a plausible one and it is not a proof.

Unfolding breadth-first from a root face cuts the edges furthest from the root in the face graph, because the tree keeps every edge it can reach first and cuts what is left over. The separation a cut costs grows with how far apart in the tree its two faces are, so cutting the edges that are already far from the root is cutting where the cost is lowest — a greedy argument on the right quantity.

What that argument does not do is bound the loss. Greedy on the right quantity is optimal for a matroid and this is not one: a spanning tree with a cost that depends on the geometry of the unfolding rather than on the edges chosen is a much less structured object. The plausible story explains why the heuristic is good and gives no reason it should be exactly best, and the enumeration says it is exactly best three times out of three.

What the score does not capture #

Every ranking is a ranking on something, and it is worth naming what this one leaves out, because a different score could put a different net first.

It is blind to the shape of the outline. A net that fits a rectangular sheet and one that sprawls diagonally can have identical separation totals. For anything printed that is the first practical constraint, and what the cut has to go somewhere establishes is that the cut’s position on the globe matters more than either — a net that is compact and puts its cuts through the Atlantic is better than a tidier one that cuts through Asia.

It is blind to which neighbours are separated. The total treats every cut edge alike. A reader following a coastline cares about the cuts that cross the coastline, and nothing in this score knows where anything is. The net that loses the fewest neighbours is the version of the question that does know, and it is a different optimum.

And it is blind to distortion entirely. The separation is a property of the unfolding, not of the projection onto the faces, so two nets of the same solid have exactly the same distortion — which is set by the face count and the map onto each face and not by how the faces are laid out. Choosing a net is a layout decision with no metric consequence at all, which is precisely why it is decided by combinatorics.

The scope of the result is therefore narrow and exact: on the quantity defined here, on solids up to eight faces, the heuristic is optimal. Whether it is optimal on a score that weights cuts by what they cross is a different enumeration, over the same 384 trees, and it is one this rung does not run.

What this changes about choosing a net #

More faces means less distortion and more cutting, and the practical question at every face count is which net to print. Three readings follow.

On a small solid, use the heuristic and stop. It is optimal, it is checked, and the check is exhaustive rather than statistical.

On a large one, use the heuristic and say so. It is the best method available and its optimality is unknown; a paper that says “chosen by breadth-first unfolding from face k” is reproducible and one that says “chosen for compactness” is not — which is report the map, not the parameters applied to a combinatorial choice rather than a continuous one.

And do not report a sampled gap as a gap. The heuristic is within x per cent of the best of ten thousand random nets is a sentence about ten thousand random nets. Here it would be negative, which is at least honest about which direction the ignorance runs.

Two kinds of answer to one question #

The distinction the closing paragraphs draw is worth stating as a general point about what a measurement can return, because a boundary is a legitimate answer and is easily mistaken for a failure.

A quantitative answer says how much. The heuristic falls short by four per cent is what the shortfall expected, and it is what a comparison against a known optimum produces. It requires the optimum to be knowable, which here means enumerable.

A boundary answer says up to where. The heuristic is optimal for every solid whose nets can be enumerated, and above that nothing can be said by this method is a different shape of statement, and it is the honest one when the enumeration runs out — as it does at eight faces, against a count of 3.5 × 10²⁸.

The two are not interchangeable and only one of them is available. No amount of further computation converts the second into the first, because the obstacle is the size of the search space rather than the effort applied to it. A larger sample explores a vanishing fraction of a set that grows faster than any sampling budget.

It is also worth noticing that the boundary is the more durable of the two. A quantity measured against an enumerable optimum is a fact about the solids small enough to enumerate today, and a faster machine moves it; the statement that enumeration runs out and sampling cannot substitute is a fact about how the count grows, and no machine moves that at all.

And reporting the boundary is what keeps the shortfall queue honest. A queue that only accepts quantities encourages a number to be produced where none exists — a sampled optimum quoted as an optimum, which is precisely the trap this rung avoids. Recording the question changes shape here, and here is where discharges the debt correctly and tells the next reader what to build.

What this rung establishes #

Every net of the tetrahedron, cube and octahedron, enumerated and scored: 16, 384 and 384, all valid, with a spread of 1.33 to 1.71 between the best and the worst.

The heuristic attains the optimum on all three, which is a stronger result than the shortfall asked for and converts the question from how much worse to up to what size is it known.

The ceiling is eight faces, because the dodecahedron already has 5,184,000 nets and an eighty-face geodesic solid has 3.5 × 10²⁸, counted exactly by a determinant and never listed.

The gap between best and worst is 1.33 to 1.71×, so the optimum is worth attaining: a valid net drawn at random sits about a third above the best, in a broad band rather than near either end.

And above the ceiling, sampling is the wrong instrument. Eight hundred random nets do not reach the heuristic’s own, so a sample can neither beat it nor certify it, and the two cases are indistinguishable from inside the sample. That is the limit, and it is a limit of the method rather than a number about the answer.

It is worth ending on which of the two the shortfall wanted. It asked for the heuristic’s own limit, expecting a quantity — the amount by which a good method falls short of a perfect one. What came back is a boundary instead: a face count, above which the question changes from arithmetic to proof. Recording that as the answer is the right response rather than a failure to find the number, because the number does not exist above the ceiling and the ceiling is a fact about the problem. The next thing worth building here is not a larger sample; it is a bound that argues rather than counts, and this collection has declined that kind of argument seven times for the same reason each time.