One node per panel, with the rim gone

One of this collection’s more surprising measurements is that a repeating pattern costs exactly one node of search per panel — not approximately, not on average, but one, on the grid, on the leaf, on the Miura and on a crumple, at every size measured.

That reading was taken on patches cut out of the plane. This one takes it again with the boundary removed.

The reading, restated #

Searching a pattern for a consistent assignment of mountains and valleys is a tree search: choose a crease, try a letter, propagate what that forces, back up on a contradiction. The nodes of the tree are the units cost is counted in.

For a repeating pattern with degree-four vertices, the vertex conditions leave eight labellings at each vertex, and the propagation stops after exactly one crease per panel. So the search settles in one node per panel with no wrong guesses anywhere, and it does so on families that look nothing like each other.

What the glued sheets read #

Take the Miura’s two-period cell. Cut out of the plane it has twenty-two free letters over fifteen panels and settles in fifteen nodes. Glued across, eighteen letters over ten panels, eleven nodes. Glued along, twenty over twelve, thirteen. Glued both ways, sixteen over eight, ten.

Fifteen, eleven, thirteen, ten: the totals fall as the rim goes.

One, one point one, one point zero eight, one point two five: the cost per panel rises.

Both readings are correct and they answer different questions. How long does this take is answered by the total. How hard is this object, size for size is answered by the ratio, and the ratio is the only one of the two that can be compared between sheets holding different numbers of panels.

Why per panel is the right denominator #

The four sheets are the same drawing and they do not have the same number of panels: a two-period square twist cell holds twenty-five of them cut out and sixteen glued up. So a total is partly a measure of how big the object is.

Dividing by the panel count removes that, and it removes it for a reason rather than by convention. The one-node-per-panel reading says the propagation stops after one crease per panel, so the panel count is the natural unit of work, in the same way that a sorting algorithm’s cost is quoted per element rather than per array.

The letters that were removed #

The explanation for the rising rate is in which letters the gluing takes away.

A crease that the rectangle’s edge divides appears as two crease pieces on the cut sheet, and the two are separate creases as far as that sheet is concerned. Each takes its own letter, and the two letters need not agree — nothing connects them, because the constraint that would have connected them is on the other side of a cut.

So a divided crease supplies a letter the search can set without consequence. It cannot cause a contradiction, it cannot force anything, and it cannot be wrong. It is a free choice in the strong sense.

Gluing rejoins the pieces and removes exactly those letters. What is left is the letters that matter, and the search now has to get all of them right rather than most of them.

That is the reading an earlier measurement reached from one end of the scale — the rim is slack — arrived at here with a middle point and a rate.

The grid, small enough to check #

The plain grid is the case where the arithmetic can be followed all the way.

A two-period cell has four interior vertices, twelve free letters and nine panels cut out, and it settles in nine nodes: one per panel. Glued in one direction, ten letters over six panels, seven nodes, which is one point one seven per panel. Glued both ways, eight letters over four panels, six nodes, one and a half per panel.

Nine to six is a third of the panels gone and nine nodes to six is a third of the nodes gone, so on this cell the two happen to keep pace. At one period they do not — three panels and four nodes for a cylinder — and the small cases are where the ratio is noisiest, because a single backtrack is a large fraction of the work.

Where the reading breaks down #

The one-node-per-panel law is a reading of a cut patch, and it survives the gluing in the sense that the numbers stay in the same neighbourhood. It does not survive as an exact statement, and it is worth saying which of the three ingredients fails.

The law comes from three facts: that the vertex conditions leave eight labellings at a degree-four vertex, that propagation stops after one crease per panel, and that no guess is ever wrong. On a glued sheet the first two are unchanged — the vertices are the same vertices with the same conditions — and the third is not.

Guesses do go wrong on glued sheets. The consistency test a glued sheet needs is not the one a cut sheet uses, it is more expensive, and it rejects letterings the cheaper test accepts. So the search backtracks, and backtracking is where the extra nodes come from.

An analogy that is nearly right #

There is a way of thinking about the slack that helps and has to be handled carefully.

A cut patch is like a system of equations with more unknowns than constraints. The extra unknowns are the divided creases; they appear in no equation that the patch can see, so any values will do, and a solver assigning them arbitrarily is never contradicted.

Gluing adds the missing equations. The unknowns that were free become determined, the system becomes square, and a solver has to satisfy everything rather than most things.

Where the analogy misleads is in suggesting that a square system is merely a bit more work. The search here is combinatorial, not linear: adding constraints can turn a problem that walks straight to an answer into one that has to explore, and the growth is not proportional to anything. On these small cells it costs a node or two. On a four-period twist cell it costs three orders of magnitude.

So the analogy is right about the mechanism and useless about the cost, which is a fair description of most intuitions about search.

Measured on which sheets #

The claim is about three families and it is worth listing which cells were actually built, since the ones that refuse outright do not appear in any ratio.

The grid: one, two and three periods. Odd cells are refused on orientation grounds before any search runs, so only the two-period cell contributes glued readings.

The Miura: one, two and three periods, glued across, along and both ways. The across gluing refuses at odd sizes; the along gluing never does; so the two-period cell contributes all four sheets and the others contribute the along-glued cylinder.

The Yoshimura: one, two and three periods. It is never refused on orientation and it is refused at most sizes for a different reason — its folded state turns rather than slides — so only the three-period cell contributes.

That is a thin slate for a general claim, and it is stated as such. The cut readings are the ones with many measurements behind them; the glued readings are a handful of cells, and what they establish is a direction rather than a law.

The other reason a total can fall #

There is a second explanation for the falling totals that has to be ruled out, and ruling it out is quick.

Fewer letters could simply mean fewer variables to assign, in which case the total would fall for a reason that has nothing to do with what kind of letters they were. That is worth taking seriously: sixteen letters is fewer than twenty-two whatever their character.

The reason it is not the explanation is that the panel count falls too, and it falls further. Nodes track panels rather than letters — that is what the one-node-per-panel reading says — so the interesting quantity is nodes against panels, and that ratio goes the other way.

Put another way: if the totals were falling merely because there were fewer letters, the rate per panel would stay flat. It rises, and the rise is what needs explaining.

What a boundary is, in this account #

Reading the measurement backwards gives a description of what a rim actually is to a search, and it is not the description one would guess.

A boundary is not an obstacle. It does not add conditions, it does not make anything harder to satisfy, and it does not constrain the pattern at all.

A boundary is a supply of unconstrained choices. Each crease it divides becomes two letters that need not agree, and a letter that need not agree with anything is a place where a contradiction can be absorbed rather than propagated.

That is why a patch is cheap and a torus is dear, why the cheapness scales with how much boundary there is, and why the earlier reading that called the rim an obstacle was backwards. It is also a reasonable description of what a boundary does in a great many places: an edge is where a rule stops applying, and rules that have stopped applying cost nothing to satisfy.

The measurement’s own limits #

Three, stated plainly.

Small numbers. The searches quoted here run from three nodes to twenty-eight. Differences of one or two nodes are visible in a ratio and are not evidence of much, and the essay’s claim is about the direction of the effect rather than its size.

Few glued cells. As above: a handful, because most of the cells that could have contributed are refused for reasons that have nothing to do with cost.

One variable order. Every search here uses the same rule for choosing which crease to letter next. A different rule would give different node counts, and the collection has shown that the choice of order matters a great deal. Holding it fixed is what makes the four sheets comparable and it means the numbers are about this order rather than about the objects.

What the numbers do not support #

Two claims that the table looks like it makes and does not.

It does not say a glued sheet is harder in general. These are small cells and small searches — six to fifteen nodes — and the differences are a node or two. At larger cells the picture changes completely: a four-period square twist cell costs forty-eight nodes cut out and fifty-six thousand seven hundred and seventy-two glued up, which is not a ratio of one to one and a quarter.

It does not say the rate is a constant. One point one, one point zero eight, one point two five and one and a half are not one number, and nothing here suggests they should be. What is a constant, to three decimal places, is the cut reading; the glued readings are a spread.

The honest summary is that the cut sheets have a law and the glued ones have a range, and the range starts where the law leaves off.

Why the law was ever exact #

It is worth asking why the cut reading is so clean, since a search settling in exactly one node per panel with no backtracking at all is not a thing searches usually do.

The reason is the slack. On a cut patch, every crease the boundary divides is a free letter, and there are many of them — a two-period square twist cell has eight of them out of forty. Whenever the propagation reaches a contradiction, there is almost always a free letter nearby that can absorb it, so the search never has to back up.

Remove the slack and the search has to be right. That is the whole of why the rate rises, and it is also why the rim reads as making a search easy rather than as making it hard, which was the reading before the middle of the scale existed.

A note on what a node is #

Since every number here is a count of them, it is worth being precise about what is being counted.

A node is one decision: the search picks an undecided crease, gives it a letter, and propagates the consequences through the vertex tables until nothing more is forced. If a contradiction appears, the node fails and the search backs up; if not, it moves to the next undecided crease.

So a node is not a crease and it is not an assignment. A single node can determine dozens of letters through propagation, which is exactly why the one-node-per-panel reading is interesting: it says the propagation from each decision reaches about a panel’s worth of the drawing and then stops.

It also means the count depends on the propagation being the same on every sheet, and it is. The vertex tables are built from the angles and the letters at each vertex, the vertices are unchanged by any gluing, and the tables are therefore identical across the four sheets. What differs is only which creases are the same crease.

That is the last of the controls, and it is the one that makes the comparison a comparison rather than four separate measurements.

Where the big numbers are #

The cells in this essay are small on purpose — they are the ones whose arithmetic can be followed — and the effect they show is a fraction of what happens at size.

The largest comparison this collection has made is a four-period cell of the square twist tessellation. Cut out of the plane it settles in forty-eight nodes. Glued into a torus it takes fifty-six thousand seven hundred and seventy-two.

That is the same phenomenon and it is three orders of magnitude of it. Eight free letters per cell of rim, removed, and the search goes from walking straight to an answer to exploring a substantial tree.

The reason the small cells show a factor of one and a quarter and the large one shows a factor of a thousand is that the slack does not merely help a bit — it prevents backtracking altogether, and a search that never backtracks is linear in its input while a search that does is not. Removing the last of the slack changes which of those two the search is, and the size at which that becomes visible is a size at which the numbers stop being checkable by hand.

So the small cells are where the mechanism is legible and the large ones are where it matters, which is an ordinary relationship between an illustration and a phenomenon.

Against the alternative reading #

Before the middle of the scale existed, the same comparison supported a different story, and it is worth saying why that story is now hard to hold.

The story was: a rim makes a search hard, because a rim has boundary vertices with fewer constraints on them and irregular geometry near the edge, and irregularity is what searches struggle with. On that reading, gluing tidies the object up and the cost falls.

The costs do fall, so the story fits the totals. It does not fit the rates, and it does not fit the direction of the letter count: gluing removes letters, and removing letters from a search cannot make it harder unless the letters removed were the ones doing the work — which is precisely the opposite of the story’s claim that they were noise.

The measurement that settles it is holding the panel count fixed and varying only the rim, which is what a middle rung of the scale makes possible and what two objects at the two ends cannot do.

What a reader should carry #

The measurement is three sentences.

A rectangle of repeating pattern cut out of the plane costs one node of search per panel, exactly, on every family measured.

Gluing its edges removes the letters the boundary divided, which are the letters that could not have been wrong.

The total therefore falls and the rate rises, and the rate rises because what is left has to be right.