A tie is not a decision

Crimp it away and ask again settled what the four local conditions are worth. At a vertex of degree four they are the whole answer; above it they are not, and what decides the case is not a fifth condition but a reduction — find a sector strictly smaller than both its neighbours, fold it away between them, and ask the smaller vertex the same question.

That essay was about whether the reduction is right. This one is about what it costs, and the cost turns out to be decided by something the reduction was never designed around.

Where the move is forced and where it is not #

The reduction’s move is forced by the big-little-big lemma. A sector strictly smaller than both its neighbours must be flanked by creases of opposite letters, because the paper on either side of it has to fold across it; so at such a sector there is nothing to choose. Fold it away, merge its two neighbours into one of angle prev + next − here, and a vertex of two fewer creases is left.

Where two sectors tie for smallest, the lemma says nothing at all. Where the lemma says nothing took that silence as its subject and found it everywhere: the preliminary base’s four sectors are all equal, the waterbomb’s degree-six vertex has four sectors of forty-five degrees, and the lemma constrains none of them.

The silence arrives again one level down, and this time it is not a gap in what is known — it is a gap in what to do. With no strictly smallest sector, every weakly smallest one is a candidate, and the procedure has to try them.

How often that happens, and to which vertices #

The pattern in that figure is stark enough to be worth stating without hedging. At angles drawn at random the reduction is never offered a choice. Over 9,056 vertex-and-letter pairs at degrees four, six and eight, with sectors produced by cutting half a turn into random pieces twice, not one of them branched: there was always a strictly smallest sector, the lemma always named it, and the reduction walked a single path from the vertex to its answer.

At the vertices origami is made of, it branches almost always. The preliminary base’s centre — four right angles, the first vertex anybody folds — branches on fourteen of its sixteen letterings. The degree-eight vertex at the middle of that base branches on 254 of its 256. The waterbomb tessellation’s odd vertex branches on forty-four of sixty-four, and this site prints nine of them on one sheet.

That is not a coincidence about those particular vertices. A tie between two sectors is an equality, equalities between continuous quantities hold with probability zero, and a design drawn on a grid is nothing but equalities: every sector a whole multiple of forty-five degrees, drawn from a set of four or five values, with dozens of chances for two of them to coincide.

It is worth putting that beside what almost every pattern fails established. Flat-foldability itself is a coincidence of measure zero — a random vertex does not satisfy Kawasaki, and the ones that do were arranged. So every vertex in this subject is already the result of an arrangement, and the question is only which arrangement. Arrange a vertex by solving Kawasaki with the sector sizes otherwise free and the ties never happen. Arrange it by laying creases on a grid, which is how designs are actually drawn, and they happen constantly. The subject’s own construction methods put it in the expensive case.

Eighty-three per cent, on a catalogue that is not a sample of anything: it is every vertex a box-pleated design can contain. At thirty degrees the figure is 2,088 of 3,744, which is fifty-six per cent, and the difference between the two is itself instructive — a thirty-degree grid has more distinct sector sizes to draw from, so its vertices tie less often.

What the search costs #

A vertex of degree n is decided by n / 2 − 1 crimps. A reduction that never had to choose therefore visits n / 2 vertices and stops. The hero figure is what actually happens at the worst case — the vertex whose every sector equals every other, where every position is a weak minimum and every one of them is a candidate.

Three visits at degree four. Ten at degree six. Forty-one at eight, 206 at ten, 1,237 at twelve. The ratio between consecutive rows is 3.3, 4.1, 5.0, 6.0 — rising by about one each time, which is the signature of a factorial rather than of a power. The work required rises by one per row.

None of that matters for a figure on this site, because nothing here draws a vertex above degree eight and 10,496 visits is a fraction of a second. It matters for what the reduction is. A decision procedure whose cost is factorial in the size of its input is a different object from one whose cost is linear, and the difference here is not caused by the problem being hard — it is caused by the angles being round numbers.

There is a second reason to care, and it is about how a result is read rather than how long it takes. The reduction is the thing that made Crimp it away and ask again an essay rather than an observation: the four conditions stop being sufficient at degree six, and what replaces them is a procedure. A procedure that runs in a walk is a satisfying replacement for a test. A procedure that searches is a different kind of object, and somebody reading the earlier essay would be entitled to ask whether the reduction is really an answer or merely an enumeration wearing a better coat. The measurement in this essay is what settles that, and it settles it in the reduction’s favour — but only because of a fact about the moves, and not because the search was small.

The visit counts have a closed form #

“The signature of a factorial” can be made exact, because five numbers are enough to determine the rule that produces them.

Write $a(k)$ for the visits at degree $2k$, so the measurements are $a(2) = 3$, $a(3) = 10$, $a(4) = 41$, $a(5) = 206$, $a(6) = 1237$. Then

$$a(k) = k \, a(k-1) + 1, \qquad a(1) = 1,$$

and it reproduces every one of them: $3\times3+1 = 10$, $4\times10+1 = 41$, $5\times41+1 = 206$, $6\times206+1 = 1237$. Four consecutive confirmations from a rule with no free constant in it.

Unrolling gives a closed form,

$$a(k) = k! \sum_{j=1}^{k} \frac{1}{j!},$$

and the sum converges to $e - 1$. So $a(k) \to (e-1)\,k!$, and in fact $a(k) = \lfloor (e-1)\,k! \rfloor$ at every degree measured. The worst case is a factorial with the constant $e - 1 = 1.7183$ in front of it.

That also names the ratios. $a(k)/a(k-1) \to k$ exactly, which is the observed 3.3, 4.1, 5.0, 6.0 approaching 3, 4, 5, 6 from above — the $+1$ is what keeps each ratio a little over its limit, and the excess shrinks because the term it is added to is growing factorially.

And a number the next run can refute #

The recurrence’s value is that it predicts rather than describes. A degree-fourteen vertex of equal sectors should be visited

$$a(7) = 7 \times 1237 + 1 = \mathbf{8{,}660}$$

times, where seven crimps would do — and $\lfloor (e-1) \times 5040 \rfloor = 8660$ agrees, which is the two forms checking each other rather than a second reading.

Nothing on this site draws a degree-fourteen vertex, so the prediction costs one run of a routine that already exists and settles whether the rule is the rule or a coincidence that five points could not tell apart.

The recurrence also explains the overhead figure the hero states. Dividing, $a(k)/k \approx a(k-1)$: the wasted work at degree $2k$ is almost exactly the total work at degree $2k-2$. At degree twelve that is $1237/6 = 206.2$ against $a(5) = 206$. The reduction is not merely expensive at the top; each degree carries the whole of the previous degree’s search as its own overhead, which is the clearest statement of why a confluence argument is worth more here than any amount of pruning.

The thing that makes all of it unnecessary #

Here is the measurement this essay exists for. Every one of those searches explores a tree; a tree is explored because different branches might give different answers; and no branch has ever given a different answer.

The check behind that picture is exhaustive over the grid catalogue: every lettering of every vertex, every pair of crimps available at once, taken in both orders, and the resulting vertices compared up to the rotation that removing two creases leaves behind. 1,648 pairs, no disagreement.

And the reason is one line of arithmetic. Crimping the sector at i replaces its two neighbours with a single sector of prev + next − here, and since here is a minimum, that merged sector is at least as large as either neighbour was. Sectors only grow. So a second minimum elsewhere on the loop still has its own neighbours, unchanged or larger, and is still a minimum; the crimp at i cannot destroy the crimp at k, and the two commute.

The consequence is that the search tree is a diamond rather than a branching one, and everything below its first level is a re-derivation of a vertex already reached by another route. The 10,496 visits at the degree-eight vertex are 256 letterings’ worth of walking a lattice whose every path ends in the same place.

That also explains a number that would otherwise look odd. The widest choice ever offered is exactly the vertex’s degree — eight candidates at a degree-eight vertex of equal sectors, six at a Yoshimura’s — because when every sector ties with every other, every position is a weak minimum. The width is not a measure of how hard the vertex is; it is a count of how many indistinguishable descriptions of the same move there are.

Which theorem was checked, and how #

Three routines are involved and they must agree. reduce is the crimp, written as a recursion on angles. stackings is brute force: a vertex folded flat is a closed loop of paper folded onto a line, so its layer orderings can be enumerated and each one put past the three non-crossing rules. tree is the whole search rather than the first success. They share no line of code, and the site’s gate requires all three to give the same verdict on every vertex and every lettering it is given — 9,056 pairs at the last run.

The commuting claim is checked separately and differently. It does not ask whether two branches reach the same verdict; it asks whether they reach the same vertex, which is stronger and is the thing that makes the verdict claim inevitable rather than lucky.

The refusals matter as much. A vertex whose two smallest sectors are equal must offer two candidates and not one — a routine that quietly returned the first weak minimum would make every number in this essay read zero and nothing else would notice. A vertex with one strictly smallest sector must offer exactly one, so that a report of no branching is a report about the vertex rather than about the code. Both are asserted, and so is the arithmetic of the crimp itself: folding a sector away must leave a vertex of exactly two fewer creases, and a merge that would produce a negative sector is not a crimp and is refused.

One more control is worth naming because it is what makes the branching counts comparable across patterns. A tessellation repeats one vertex hundreds of times, so counting each repetition would report the waterbomb tessellation as fifty times harder than a preliminary base for a reason that is about its size. The pattern census groups by kind of vertex instead, which is the same grouping the earlier rung used and is the only one that answers the question being asked.

Where the model stops #

The commuting argument is a statement about two crimps available at the same vertex, and it has been checked exhaustively on a finite catalogue and by sampling elsewhere. It is not a proof for every vertex of every degree. The awkward case is two weak minima that are adjacent, where crimping one consumes a crease the other needs; those pairs are reported by the check as “the other crimp did not survive” and are excluded from the commuting count rather than being shown to commute.

So the honest statement is narrower than the one the numbers invite. Over everything measured — the whole forty-five-degree and thirty-degree catalogues, 2,424 vertices with sectors deliberately tied at angles that are not on any grid, 428,928 letterings between them — a first-candidate rule has never got a vertex wrong, from either end of the list. That is strong evidence and it is not a theorem, and the difference is the sort this site is obliged to keep saying out loud.

What the picture cannot show #

None of these figures shows a search. They show its size — a bar, a count, a width — and a search is a thing that happens over time, in an order, with a stack. The commuting figure comes closest and it draws two paths where the real object has as many as eight at a degree-eight vertex.

Nor does anything here show the paper. A crimp is a physical move — fold the smallest sector between its neighbours and press — and the reduction’s later steps operate on vertices that are not on the sheet: they are cones, with sectors summing to less than a full turn, and no paper has ever been in that shape. The reduction is exact and its intermediate objects are fictions, which is exactly what makes it a proof technique rather than an instruction.

The generalisation #

The shape of this result is familiar from elsewhere and worth naming, because naming it is what makes it usable. A rewriting procedure whose moves commute has a property: whatever order the moves are applied in, the same thing is reached. So a procedure that looks as though it needs to search does not, and an implementation that searches is doing exponential work it can be shown not to need.

A machine that can only crimp treated crimping as a folding primitive and found it reduces to a rewriting rule. This is the same observation arriving one level up: not that a machine’s moves can be written as rewrites, but that the decision procedure for a vertex is a rewriting system, and its confluence is what makes it cheap.

Who found it, and when #

The reduction is Justin’s, from the same 1986 work that gives the big-little-big lemma, and the silence at a tie is stated there. The literature’s treatment of what to do about the silence is brief, which is reasonable: for the decision problem the answer is that any choice works, and a result that says “it does not matter” tends to be recorded as an aside rather than as a theorem.

What is not an aside is the measurement. Nothing appears to record how often the case arises, and the answer — never at generic angles, on eighty-three per cent of the letterings a box-pleating grid admits — is the kind of number that changes how a procedure is implemented rather than whether it is correct.

Where the ladder goes next #

The obvious continuation is the adjacent case: two weak minima that share a crease, which the commuting check excludes rather than settles. Characterising when a crimp destroys another crimp rather than preserving it would turn the evidence above into an argument, and it is a finite question about four sectors.

The other direction is the cost itself. A reduction that knows its moves commute takes the first candidate and stops, which makes deciding a vertex of any degree a walk of n / 2 steps — and puts the local question firmly on the easy side of a subject whose global question is NP-hard. The distance between those two facts is where the difficulty of this subject actually lives: every vertex can pass and the sheet still fail, and it is the assembling and not the deciding that is expensive.

There is a third direction, and it is the one this measurement found by accident. A vertex that branches is a vertex with a tie, a tie is what the big-little-big lemma is silent at, and the number of letterings a vertex admits is decided by which sectors are smallest and by nothing else about the angles. The branching measured here and the counting measured there are two readings of one object, which is a better reason to have measured both than either of them had on its own.