Half the slack

The rim is slack, and slack is what makes a search cheap. That was measured between two objects — a rectangle cut out of the plane and the same rectangle glued into a torus — and it left an obvious question that two objects cannot answer: is half the rim worth half as much?

The letters say yes. What one glued pair of edges removes is what the other removes, and the two add.

The search says no, and not by a little.

The measurement #

Take a three-period cell of the square twist tessellation and search it for a consistent lettering under one fixed variable order, on each of the four sheets its edges can be glued into.

Cut out of the plane: eighty-four free letters, forty-nine panels, thirty nodes.

Glued along one pair: seventy-eight letters, forty-two panels, twenty-four nodes one way and eighty-five the other.

Glued both ways: seventy-two letters, thirty-six panels, six hundred and twenty-five nodes.

Six letters removed takes the cost from thirty to somewhere between twenty-four and eighty-five. The next six take it to six hundred and twenty-five.

Why the letters are linear and the cost is not #

The letters are a count of cuts and cuts made by different edges are different cuts, so they add. That is arithmetic and it holds exactly.

Cost is not a count of anything. A search over letterings walks a tree, and what governs the size of that tree is whether the search ever has to back up. A search that never backtracks is linear in its input; one that does is not, and the difference between them is not a matter of degree.

What a free letter supplies is a place where a contradiction can be absorbed. A crease the rim divides appears as two letters that need not agree, so setting one of them wrongly costs nothing: nothing downstream depends on it. Whenever the propagation runs into trouble near the edge, there is a free letter nearby to take the strain.

Take away half of them and there are still enough. Take away the last of them and there are none, and every wrong guess has to be undone.

The threshold, not the slope #

That is the shape of the result and it is worth stating as such. The rim does not contribute to the search in proportion to its size. It contributes a capacity to absorb, and capacity is useful until it runs out.

Below the threshold the search walks straight to an answer and the cost is the number of decisions, which is about one per panel. Above it the search explores, and what it costs is a question about the tree rather than about the drawing.

At one and two periods the four sheets are within a factor of one and a half of each other. At three they are within a factor of twenty-six. The variable that changed is not which sheet but how much drawing there is, and the threshold is crossed somewhere between.

What a threshold looks like from below #

The one- and two-period cells are the useful half of this measurement, because they show what the world looks like when there is enough slack to go round.

At one period the square twist’s cell has twelve free letters over nine panels cut out, and eight over four glued up. The searches cost five, four, four and three nodes. At two periods: forty letters over twenty-five panels cut out, thirty-two over sixteen glued; thirteen, eleven, eleven and nine nodes.

Every one of those is a search that walked straight to an answer. The node counts differ by a few because the objects differ by a few panels, and per panel they run from half to three quarters — flat, and flat across all four sheets.

Nothing in those two rows would suggest that the next row up contains a six hundred and twenty-five. That is what a threshold does: below it the quantity being measured is not the quantity that will eventually matter, and no amount of care with the small cases reveals which.

It is also why the collection reports both sizes rather than the interesting one. A result quoted only at the size where it is dramatic is a result whose reader cannot tell whether the effect was always there.

What happens at four periods #

The largest cell of this family that has been searched is four periods across, and the two ends of the scale there are forty-eight nodes cut out and fifty-six thousand seven hundred and seventy-two glued into a torus.

Those numbers are three orders of magnitude apart, and they are the reason the rim was described as slack in the first place. What was missing was the middle, and the middle at three periods says the two halves of the rim are not interchangeable — twenty-four one way and eighty-five the other, on a drawing symmetric between them.

Extending the middle to four periods has not been done. The cut and torus ends are known; the two cylinders are not; and the reason is cost rather than difficulty, since a search that has to be given a budget of hundreds of thousands of nodes takes long enough that four of them per figure is a real expense in a build.

That is recorded as owed rather than done.

Why slack works the way it does #

The mechanism is worth spelling out, because slack is a metaphor and the thing underneath it is mechanical.

A search assigns letters one at a time and propagates. Propagation is the cheap part: given a letter, the vertex conditions force some of its neighbours, those force more, and the wave spreads until it stops. If the wave ever reaches a vertex whose conditions cannot be satisfied, the current assignment is wrong and the search backs up.

A crease the rim divides is a crease with a vertex on one side only. The wave arriving at it has nowhere to go, so it stops — and stopping is exactly what prevents a contradiction from being discovered. The letter on that crease is never contradicted because nothing far enough away ever gets asked about it.

So the rim is a set of places where propagation terminates harmlessly. Remove them and the waves travel further, meet each other, and disagree.

That also explains the abruptness. Waves that stop at the rim never interact; waves that wrap around meet themselves. There is no halfway state in which a wave partly wraps.

The three regimes #

Putting the collection’s measurements together, a repeating pattern’s cell sits in one of three states and the state is not a property of the pattern alone.

Plenty of slack. The search never backtracks, the cost is about one node per panel, and the four sheets differ by tens of per cent. Every one- and two-period cell measured is here, and so are the Miura’s and the grid’s cells at every size tried.

On the edge. The search backtracks a little. Costs differ between sheets by factors of a few, and between the two cylinders of one drawing by factors of a few — which is where the three-period square twist sits.

No slack. The search explores. Costs are in the thousands or beyond, budgets start being hit, and node counts stop being a stable property of anything. The four-period torus is here.

Nothing here predicts which regime a given cell will be in, and the collection’s experience is that the transition happens between three and four periods on the twist tessellations and has not been reached at all on the grid or the Miura.

Which half is removed matters too #

The two cylinders in the three-period measurement cost twenty-four and eighty-five nodes, which is a factor of three and a half between two sheets with the same Euler number, the same number of edges and the same amount of rim.

On this drawing the two cylinders have identical counts, so the difference is entirely in the order the search happens to try things in. That is a separate result and a large one, and it is a warning about reading any single node count as a property of an object.

What a cut sheet is doing that a glued one is not #

Reading the measurement backwards gives a description of a patch that is more useful than the usual one.

A rectangle cut out of a tessellation is normally described as a sample: a piece of the pattern, small enough to draw, standing in for the whole. On that description the rim is an artefact — a place where the sample was cut, carrying no information, to be ignored.

The measurement says the opposite. The rim is where the sample is easiest, because it is where the constraints stop. A search on a patch spends most of its time in a region where nothing can go wrong, and the region is exactly the part that is not the pattern.

That inverts the usual worry about patches, which is that the rim makes them unrepresentative because it has odd vertices and truncated features. The rim does make them unrepresentative, and the direction is that it makes them easy.

The one-node-per-panel reading, and where it stops #

A cut patch of a repeating pattern costs one node of search per panel, on every family measured and at every size. That reading is the sound of a search that never backtracks.

The glued sheets read more, and the amount more is not a constant.

So there are two regimes and the collection has now measured both. Below the threshold, gluing raises the cost per panel by tens of per cent. Above it, gluing raises the cost by factors that are not worth quoting as ratios because they are not stable.

Which regime a cell is in depends on its size, its family and the variable order, and there is no rule here for predicting it.

What is not being claimed #

Three limits, since a factor of twenty-six invites over-reading.

One order. Every search quoted uses the same rule for choosing the next crease to letter. The collection has established that the order is where most of the cost lives, and holding it fixed is what makes the four sheets comparable rather than what makes the numbers general.

One family, at the interesting size. The three-period comparison is on the square twist tessellation. The Miura and the grid are cheap at every size measured, so they show the linear regime and say nothing about the threshold.

Small numbers below the threshold. Thirty nodes against twenty-four is a difference of six, and a difference of six is not evidence of much.

A note on comparing node counts at all #

Node counts are the currency of every cost claim in this collection and they are a currency with an exchange rate that moves, so it is worth saying what makes two of them comparable.

Two searches are comparable when they use the same propagation, the same vertex tables and the same rule for choosing what to decide next. Change any of the three and the counts are measuring different procedures rather than different objects.

All four sheets here share the first two by construction: the vertex tables are built from angles and letters at each vertex, no gluing moves a vertex, so the tables are identical. The third is held fixed deliberately.

What differs is only which creases are the same crease — which is exactly the variable the comparison is about, and is the reason these four numbers can be set beside each other when most node counts in this subject cannot.

It is also why the two cylinders differing by a factor of three and a half is a real finding rather than noise. They have the same counts, the same tables and the same order, and they are the same drawing; there is nothing left for the difference to be except the identification.

Slack elsewhere in the subject #

The pattern here is not confined to glued sheets and it is worth naming, because the collection has met it twice before under other descriptions.

A coin decides the tail of a search’s cost distribution: a search that breaks ties at random has a long tail, and the tail is where the time goes. That is the same phenomenon from the other side — a search with nothing to absorb its wrong guesses has a cost that depends on luck.

A patch is the cheapest object in the collection, per panel, which was measured before there was any account of why. This is the account: a patch is mostly edge at small sizes, and edge is where propagation stops.

And acyclicity answers nearly every node while the expensive decision runs on the rest. A cheap test that settles most cases and an expensive one that settles the remainder is the same architecture as a search that mostly walks and occasionally backtracks, and the cost of both is set by how often the expensive branch is taken rather than by how expensive it is.

Three descriptions of one thing: what governs a search’s cost is not the size of what it has to decide but the frequency with which it is wrong.

The reading this replaces #

Before the middle of the scale existed, the collection’s account of the rim had one sentence in it and the sentence was a rate: four free letters per cell of rim, buying three orders of magnitude.

Both halves of that were doing different work and only one of them was safe. The letters really are four per cell of rim, and they really do add across the two pairs of edges. The three orders of magnitude were a measurement at one size on one family between the two ends of the scale, presented in the same breath as though the two were parts of one statement.

They are not parts of one statement. One is arithmetic on a drawing and holds exactly; the other is the behaviour of a search near a threshold and holds at one size.

The correction is not that the earlier number was wrong. It is that two quantities were being reported as though they varied together, and the middle of the scale is what shows that one of them is linear and the other has a cliff in it.

What would settle the shape #

The measurement above establishes that the cost is not linear in the rim. It does not establish what it is, and it is worth being explicit about what would.

The cheapest experiment is a size sweep at fixed family and fixed order, on all four sheets, from one period to five. That would put the threshold somewhere and show whether the cut sheet crosses it too — which would say whether the effect is about gluing at all or about size, with gluing merely bringing the threshold closer.

The second is the same sweep under several variable orders, which would say how much of the factor of twenty-six belongs to the sheets and how much to the order. Given that two orders on one object can differ by more than that, the honest expectation is that a good deal of it belongs to the order.

Neither has been run. The first is affordable and the second is not, at the budgets a four-period torus needs.

The sentence that survives #

Not the rim costs so much per unit, which the letters support and the cost does not.

The sentence that survives is: a boundary supplies unconstrained choices, and a search is cheap while it has some. How many it needs depends on the drawing and the order, the requirement is not proportional to anything, and the transition from having enough to having none is abrupt.

That is a less tidy statement than a rate, and it is the one the middle of the scale actually supports.