Nearly every cutting fails at one crane

Which cranes can stay joined counts the arrangements behind the 1797 book’s connected cranes. A square sheet is slit into an n-by-n grid, and the cranes folded from its squares stay attached at interior lattice points, each of which holds the four squares meeting there. Of the sixteen ways to choose which of a three-by-three’s four joins to keep, one leaves the piece in one object. At five by five, 785 of 65,536.

It stops at five by five, where the exhaustion is sixty-five thousand subsets, and says the sixth grid — thirty-three million subsets — needs a smarter count than an exhaustion. That turns out not to be so: with each crane’s joins written as a bitmask the exhaustion takes a fifth of a second. But running it shows something the count alone did not, which is how the arrangements that fail, fail.

Two ways to come apart #

A subset of joins can leave the piece in more than one object in two quite different ways.

A crane can be left hanging. Every crane touches at most four joins — the lattice points at its corners that are interior to the grid — and a corner crane touches only one. If none of the joins at a crane’s corners is kept, that crane is attached to nothing. Finding this out means looking at one crane and at most four points, and it can be done crane by crane without thinking about the rest of the sheet.

Or every crane can be held and the piece still come apart. Each crane keeps at least one of its joins, but the joins kept form islands: a cluster of cranes in one corner joined to one another and to nothing else. Finding this out means following joins across the sheet, which is a global question about the arrangement.

The first kind is a local failure and the second a global one, in the sense this subject has used those words since the flat-folding conditions: a local test looks at one place at a time, and a global property is one no amount of looking at places one at a time can settle.

Six by six, exhausted #

The census runs to six by six. Twenty-five joins give 33,554,432 subsets. For each subset the local test is one comparison per crane — does the crane’s bitmask of joins share anything with the subset? — and only the subsets that pass it go on to a union-find over their joins. The whole census takes about a fifth of a second.

The table in the first figure gives the four sizes.

Three by three: 16 subsets. One leaves no crane hanging, and it is the one that holds together. The local test is the whole answer.

Four by four: 512 subsets. 32 leave no crane hanging; 21 hold together.

Five by five: 65,536 subsets. 1,215 leave no crane hanging; 785 hold together.

Six by six: 33,554,432 subsets. 260,625 leave no crane hanging; 141,621 hold together — 0.42 per cent of all subsets.

Almost every failure is local #

Read the table as failures and the split is lopsided. At six by six, 33,412,811 subsets fail to hold the cranes together. Of those, 33,293,807 leave a crane hanging from nothing — 99.64 per cent. Only 119,004 hold every crane by something and still come apart.

The share is 100 per cent at three by three, where every failure leaves a crane hanging; 97.8 per cent at four by four; 99.34 per cent at five by five; 99.64 per cent at six by six. It is high and it rises.

That says something practical about the object. A maker deciding which joins to leave in a slit grid, and checking the choice by looking at each crane in turn to see that it keeps at least one corner, would catch almost every mistake available. Nearly all of the thirty-three million ways to get it wrong are ways that leave a crane obviously loose.

And the local check decides less as the grid grows #

The other reading of the same table points the opposite way, and both are true.

Among the subsets that pass the look at each crane, the share that actually hold together is 100 per cent at three by three, 65.6 per cent at four by four, 64.6 per cent at five by five and 54.3 per cent at six by six. So a maker whose arrangement passes the local check has an arrangement that holds only a little better than half the time at six by six, and the proportion falls with the size.

That is the familiar shape of a necessary condition. The check never refuses an arrangement that works — every subset that holds the cranes together keeps a join at every crane, and the census confirms it on every size — and the arrangements it lets through are increasingly a mixture. The local test catches almost every failure and decides a shrinking fraction of the question, and both halves of that sentence come from the same thirty-three million subsets.

The two readings reconcile once the numbers are put together. Failures vastly outnumber successes, so a test that removes 99.6 per cent of failures still leaves a pool of failures comparable to the number of successes. At six by six the pool is 119,004 global failures against 141,621 successes.

The same split in a crease pattern #

The two ways a cutting fails have exact counterparts in folding, and the counterpart explains why this subject keeps meeting the same shape.

A crease pattern can fail to fold flat in two ways as well. It can fail at a vertex — the angles do not balance, the letters do not split three to one — which is a fact about one point and a few creases, checked by looking at that point. Or every vertex can pass and the pattern still fail, because its layers cannot be ordered consistently across the sheet, which is a fact about the whole.

In folding the local failures are also the common ones, and the pieces a pattern falls into are also found by a global walk the local conditions cannot replace. The slit cranes are a smaller, cleaner instance: one kind of local check, one kind of global property, and a census small enough to count both exactly. The census puts numbers on a relation the rest of this subject can only illustrate, at the size where it can still be exhausted.

It also sits beside the other arguments about cutting a sheet. What one cut buys prices a cut in the design currency, a cut is a licence says what it permits, and one cut short of falling apart is the same question — which cuts leave a sheet in one piece — asked of a sheet slit for folding rather than for cranes. The folklore piece is the case where the question was answered by practice two centuries before anybody counted.

A result about random networks #

A classical theorem says that this lopsidedness is not special to cranes, and it is worth knowing because it predicts which way the numbers go.

For a random network built by joining pairs of points independently with some probability, Paul Erdős and Alfréd Rényi showed in 1959 that the network becomes connected at essentially the same moment its last isolated point disappears. The obstacle to connectivity, as a network fills in, is overwhelmingly local: a point with no connections, rather than a clean split of the network into two large halves.

The cranes are a different kind of network — each join connects four cranes at once rather than two, and the joins are kept with probability a half rather than at a threshold — but the census shows the same character. The failures that leave a crane isolated dominate the failures of every other kind, and they dominate more as the grid grows. Coming apart is overwhelmingly a matter of one crane, and holding together is overwhelmingly a matter of every crane being held, even though the second is not quite enough.

The fewest joins #

The six-by-six census also completes the sequence of minima, and the new term changes its shape.

A join merges at most four pieces into one, so a piece of $n^2$ cranes needs at least $\lceil (n^2 - 1)/3 \rceil$ joins — the counting floor the earlier census derived. The fewest joins that actually hold each grid together are:

• three by three: 4, against a floor of 3 — one above it, reached in one way;
• four by four: 5, against a floor of 5 — at the floor, in one way;
• five by five: 10, against a floor of 8 — two above it, in 50 ways;
• six by six: 12, against a floor of 12 — at the floor, in one way.

So the even grids meet the counting floor exactly and meet it uniquely, and the odd grids fall short of it. Four by four and six by six each have one best arrangement and no slack; five by five has fifty arrangements that are all worse than the arithmetic allows.

Meeting the floor has a precise meaning. Every kept join has to merge four pieces that were separate until it was added, so no join may close a loop among joins already kept — the kept joins form a tree of fours. The corners constrain where that tree can go, since each corner crane hangs from exactly one join and those four joins are compulsory. At four by four the tree is easy to see: the four corner joins hold four separate blocks of four cranes, and the one join at the centre touches one crane of each block and merges all four.

Why the even grids meet the floor and the odd ones do not is found by the census rather than derived here, and the uniqueness at four and six is found the same way. The pattern invites a prediction the census cannot test: if it held, eight by eight would need exactly $\lceil 63/3 \rceil = 21$ joins and have one way to spend them.

What a maker actually checks #

It is worth being clear about what the census says about the 1797 plates and what it does not.

It says the plates’ makers had an easy check and a hard question. Looking at each crane to see that it kept a corner catches almost every bad arrangement, and a maker would do it without calling it anything. Whether a sound-looking arrangement really held together was a genuinely global question — one that at six by six the local look answers correctly only a little over half the time — and the reliable way to answer it is to cut and see.

It does not say what the plates show. The oldest book draws particular arrangements, and whether they are minimal, sound, or chosen for their appearance is a documentary question — the kind a record is not a proof insists stays separate from anything a census computes. The census counts what a slit grid permits.

The other famous folk object in the same book answers to a material bound rather than a combinatorial one. How many wedges the paper allows finds the five-pointed star cut before it was proved limited by how many thicknesses scissors will shear. Between them the two objects show the tradition meeting both kinds of limit: a star stopped by the stack, and a crane grid whose makers had a cheap local check that caught nearly every mistake and decided only half the rest.

And the counts are counts of arrangements that hold together in the sense of being one object. A cut is not local in its effect on what can be folded, and a piece hanging together through a single join is connected and fragile. The census treats every connected arrangement alike.

What the census cannot show #

The census is exhaustive for the sizes it covers and silent past them. Seven by seven has thirty-six joins and sixty-nine billion subsets, which is past what a bitmask exhaustion finishes in a reasonable time, and the trends above — the rising local share, the falling share of sound arrangements that hold — are not extrapolated.

Nor can it show strength. Two arrangements that both hold the cranes together, one through a dense block of joins and one through a thin chain, are counted identically, and a folder would not treat them identically. A census weighted by how much of each crane’s edge stays attached would be a different and more useful count for a maker, and it would need a model of how a join fails.

And the local test here is one particular local test. A maker might check pairs of neighbouring cranes, or rows, and a stronger local test would catch more of the global failures. The census reports what the simplest check — one crane at a time — catches, which is the check a maker would make first.

The grid the census assumes #

The sheet is slit along every internal grid line except at the joins, and a join is a point at which the four squares meeting there remain attached. That is the arrangement whose arithmetic the book’s own counts fit, and a different kind of join — along an edge, say — would give a different census.

Every subset of joins is equally counted. The shares are shares of all arrangements, as if joins were kept or cut at random with even chances, and a maker’s choices are nothing of the kind. The counts of arrangements are exact regardless; the shares are a way of describing the space, not a model of a maker.

And holding together means one object. No crane needs any particular amount of attachment.

How the census was checked #

Every subset is tried. Thirty-three million at six by six, each tested crane by crane for a hanging crane and, if none, unioned join by join.

The local test is required never to refuse a working arrangement — every subset that holds the cranes together keeps a join at every crane — which is the property that makes it a necessary condition rather than a heuristic.

The three-by-three is required to be decided entirely by the local test, the local share of failures at six by six to exceed 99 per cent, the share of sound arrangements that hold to fall with the size, and the even grids to meet the counting floor in exactly one way. A census in which any of these failed would not draw.

Still open: what the local share tends to #

Two trends in the table run in opposite directions and both need more sizes to read.

The share of failures that are local rises: 97.8, 99.34, 99.64 per cent. The share of locally sound arrangements that hold falls: 65.6, 64.6, 54.3 per cent. If the random-network theorem is a guide, the first tends to one. Whether the second tends to zero, or settles at some share, is the question the sixth grid raises and cannot answer, and it is the question that decides whether a local check becomes useless for large slit grids or remains a coin toss.

Seven by seven cannot be exhausted, but it can be counted differently. A transfer-matrix count sweeps the grid column by column, keeping track only of which cranes in the current column are already joined to one another, and it turns an exponential count of subsets into a count that grows with the number of ways a column’s cranes can be grouped. That is the smarter count the earlier census asked for, and it is now needed rather than merely wanted.

The habit worth carrying is about reading a necessary condition’s record. Ask both how many failures it catches and how much of what it lets through is sound. A test can catch nearly every failure and still decide only half the question, and the two numbers come from the same census read two ways.