The cost is in the coincidences

A hardness result is about the worst instance a reduction can construct, the instances a reduction constructs are engineered rather than typical, and so a worst case says little about the case in hand. That is the standard complaint and it is correct.

The complaint leaves a question open. If size is not what makes an instance expensive, what is?

For this subject there is an answer, it is measurable, and it is a property of the individual vertex rather than of its size: how many of its sectors are exactly equal.

What a coincidence is, and why it is where the work is #

A coincidence here is two sectors of exactly the same size. It sounds like a curiosity of the arithmetic and it is the precise point at which the subject’s decision procedure stops deciding.

The big-little-big lemma asks which sector is strictly smallest and forbids its two creases from agreeing. Where two sectors tie for smallest, no sector is strictly smallest, and the lemma forbids nothing — it falls silent.

The crimp reduction, which is how a vertex is actually decided, works by finding the smallest sector, crimping it away, and asking again about the smaller vertex that remains. Where two are offered at once there is no forced move, and the procedure has to try both — which is where the branching comes from.

So a coincidence is not correlated with difficulty. It is the difficulty, in the exact sense that a vertex with none is decided by a chain of forced moves and a vertex with several is decided by a search.

Holding the size fixed #

The measurement that makes the claim is the one where nothing but the coincidences moves.

Every vertex here has degree six. Each is asked about all sixty-four of its letterings, and the cost recorded is the total number of nodes the reduction visits over all of them — so what is reported is a property of the vertex rather than of whichever lettering happened to be asked about.

From no coincidences to seven, at one degree, the cost is 2.9 times higher.

Against that, doubling the instance: from degree four to degree six — sixteen letterings to sixty-four — the cost per lettering rises from 1.71 to 3.29, a factor of 1.9. And that comparison is generous to size, because the degree-six population contains the gridded vertices whose coincidences are doing part of the work.

Where the coincidences come from #

Nobody puts coincidences into a vertex on purpose. They arrive with the grid.

A vertex whose sectors are whole multiples of forty-five degrees draws them from three values — 45°, 90°, 135° — so a degree-six vertex draws six sectors from three and at least two must coincide. Every degree-six vertex on a forty-five-degree grid has a tie, necessarily and by pigeonhole. A thirty-degree grid offers five sizes and ties are common rather than certain; a vertex whose angles are cut at random has none at all, because equality between two continuous quantities happens with probability zero.

So the ordering of the table is also an ordering of populations, and which population a measurement is about turns out to decide this one too. The cheap vertices are the ones a sampler produces and the expensive ones are the ones a designer draws, which is an awkward direction for the subject’s usual reassurance to run in.

No vertex on a forty-five degree grid escapes #

The pigeonhole argument above is stated for degree six and it is true at every degree, for a reason that is worth writing out because it turns a remark about one row of the table into a statement about a whole design discipline.

Measure sectors in units of the grid’s quantum. On a forty-five degree grid a full turn is eight units and every sector is a whole number of them, at least one. For a vertex of degree $d$ to have no coincidence at all, its $d$ sectors must be $d$ distinct positive whole numbers, and the smallest total $d$ distinct positive whole numbers can have is $d(d+1)/2$. At degree four that is ten, and a full turn is eight.

So there is no room. A degree-four vertex on a forty-five degree grid cannot have four distinct sectors, and neither can any vertex of higher degree, since the requirement only grows. Every interior vertex of every box-pleated design carries at least one tie, at every degree, necessarily — which is why the catalogue of six letters that grid admits contains three tied ones and three whose ties are elsewhere in the sector list, and none that is free of them.

At degree eight it is worse than a tie. Eight sectors of at least one unit each summing to eight forces every sector to be exactly one unit, so the eight-crease grid vertex has all its sectors equal and every one of its twenty-eight pairs coincident. It is the most degenerate vertex the discipline can contain and it is the centre of the preliminary base.

The threshold, and which grid crosses it #

The same arithmetic gives the condition for any grid, and it explains the finer-grid result the ladder already has.

A grid whose full turn is $q$ units admits a coincidence-free vertex of degree $d$ only when $d(d+1)/2 \le q$. So there is a threshold degree of about $\sqrt{2q}$, and every vertex above it has a tie no matter how it is drawn.

On a forty-five degree grid $q$ is eight and the threshold is three — below the smallest degree a flat-foldable interior vertex can have, which is why nothing escapes. On a thirty-degree grid $q$ is twelve, the threshold is four, and a degree-four vertex can be drawn with four distinct sectors — one, two, four and five units — while a degree-six vertex cannot, since six distinct units need twenty-one. On a fifteen-degree grid $q$ is twenty-four and even degree six can escape.

That is the mechanism behind the earlier finding that the share of letterings needing a search falls from sixty per cent to twenty-two as the grid is refined. It is not a gradual thinning of coincidences; it is a threshold moving up through the degrees that actually occur, letting degree four out first and then degree six. And it says exactly what a designer buys by refining a grid, in a currency that has nothing to do with resolution: each refinement lifts the threshold by roughly the square root of the refinement, and everything below the threshold is decided by a chain rather than by a search.

What this does and does not say about hardness #

Deciding whether a whole crease pattern folds flat is intractable, which is a theorem about the worst case over all patterns. Nothing measured here bears on it: the vertices above are decided in milliseconds, the reduction always terminates, and no claim is being made about any complexity class.

What is measured is where the work goes in a procedure that runs, on instances that exist — which is the difference a no costs more than a yes measures on a different axis of the same procedure. That is a different question from the theoretical one and it is the question a person with a pattern in front of them has.

The two answers point in opposite directions in a specific way. The theoretical answer says the difficulty grows with the size of the instance, because that is what asymptotic statements are about. The measured answer says that at the sizes anybody folds, the variation in cost between one instance and another of the same size is larger than the variation between one size and the next — so the useful predictor is a feature and not a dimension.

The same fact, from four other directions #

The coincidence is not a new object. It is the one this collection keeps arriving at, and it is worth putting the arrivals side by side because each was found while looking for something else.

Where the lemma says nothing. A degree-four vertex whose two smallest sectors are equal admits eight letterings under the conditions and folds in six, so the conditions stop being sufficient exactly at the tie.

A tie is not a decision. The crimp reduction has no forced move where two smallest sectors are offered, and the branching it then does is measured over four hundred and thirty thousand vertex-and-lettering pairs.

Which vertices are the random ones. Four populations of vertex disagree about three questions by factors, and every one of the disagreements is traceable to how often their sectors coincide.

The other grid. The share of letterings needing a search falls from 60 to 22 per cent as a grid gets finer, because a finer grid offers more sector sizes and therefore fewer coincidences.

Four measurements, four rungs, one mechanism. What this rung adds is the comparison with size — the quantity that would otherwise be assumed to be the explanation, held fixed so that it cannot be.

Which theorem was checked, and how #

The cost is counted, not timed. What is reported is the number of nodes the reduction visits, which is a property of the instance and the procedure rather than of the machine; timings would measure something else entirely.

Every lettering of every vertex is asked, so the number is the vertex’s own cost rather than the cost of a lettering somebody chose.

The coincidences are counted on the angles, before any letter is written — they are a property of the vertex and not of the question being asked about it.

Both groupings are reported. Grouping by degree mixes populations that differ in coincidence, and grouping by coincidence mixes degrees; the comparison the argument rests on is the one with the degree held fixed, and the other two are shown so that the choice is visible rather than made silently.

The instances are the ones this collection already uses. The samplers are the ones four populations of vertex were drawn from, unchanged, so the rows here can be read beside that essay’s rows without reconciling anything.

The verdicts are checked against an independent search. The reduction’s answer for each lettering is required to agree with an exhaustive stacking enumeration, which shares no code with it — so a cheap decision is a correct decision and not a shortcut.

Where the model stops #

Degree six, and three points of degree. The comparison holds the size fixed at one value; the size comparison itself runs over degree four and six only, because deciding a vertex means enumerating stackings and the enumerator refuses above degree nine.

Coincidence is exact equality. Two sectors that differ by a millionth of a degree count as different here and are the same angle to any folder. Nothing in the measurement is about near-coincidence, which is a real and different question — and one that has no natural threshold, which is why it is not attempted.

The rows are unbalanced. Forty-three vertices at seven coincidences and three at six: the populations that produce coincidences produce particular numbers of them, so some rows of the table are thin and the figure marks how thin by the size of each point.

And the two predictors are confounded, deliberately. Vertices with no coincidence come from the random sampler and vertices with seven come from the grid, so the comparison is between populations as well as between coincidence counts. Holding the degree fixed removes size from the comparison and does not remove everything else; what it establishes is that size is not the explanation, rather than that coincidence is the only one.

What the picture cannot show #

A scatter of cost against coincidence cannot show why the relation holds; the mechanism is a fact about a procedure — which move is forced and which is a choice — and a plot of outcomes has no procedure in it.

Nor can it show the shape of the individual searches. A vertex costing five nodes per lettering may be doing that by branching once at the top or by branching three times near the bottom — and whether the branch ever changes the answer is a separate question with its own measurement — and those are different experiences for anybody watching a solver run. The tree figure shows one such search and cannot show a population of them.

The idealisation, named #

The vertex is a set of exact angles. Every coincidence in this essay is an exact equality between two real numbers, and paper folded by hand has no exact equalities in it at all.

That is not a small caveat and it does not weaken the finding, because the object that carries the coincidence is the pattern as drawn. A design drawn on a grid has exactly equal sectors by construction — the grid is what makes them exact — and the decision procedure is run on the drawing rather than on the paper. So the expensive instances are expensive in the software, which is where deciding actually happens.

What a solver should do with this #

Three consequences, each one a line of code rather than a research programme.

Report coincidences with the instance. A solver handed a vertex knows its sector sizes before it starts, so counting the equal pairs costs nothing and predicts the work better than the degree does. A queue ordered by that count runs its cheap instances first.

Expect the grid instances to be the slow ones. A design system built for box pleating is a system whose every instance is at the expensive end of the table, and a benchmark assembled from randomly drawn vertices will report timings from the other end. That is a benchmark that will look good and predict nothing.

Do not tighten the tolerance to make ties go away. A tie is exactly equality, and a solver that treats near-equal sectors as unequal converts a branch into a forced move — which is faster and is sometimes the wrong answer, because the lemma really does say nothing there. The cost is the subject’s rather than the implementation’s.

The generalisation #

Instance size is the wrong axis for practical cost, and the right axis is usually a structural feature the theory does not mention. Complexity statements are about size because size is what asymptotics need; the feature that predicts cost on real instances is a property of their structure, and there is no reason for the two to coincide.

Here the feature has an unusually clean identity: it is exactly the place where the subject’s own decision rule has no forced move. That is worth stating as a heuristic. Find where the procedure’s rule has a tie, and count the ties — that is the cost. A procedure that decides by finding an extremum is expensive exactly when the extremum is not unique, whatever the extremum is of.

The half that is uncomfortable for this subject is the population. The instances with no coincidences are the ones produced by drawing angles at random, and the instances stuffed with them are the ones produced by drawing on a grid — which is how every complex design is drawn. So the reassurance that hard instances are engineered and rare has, in this subject, exactly the wrong shape: the engineered instances are the cheap ones, and the ones a designer makes on purpose are the expensive ones.

Where the ladder goes next #

The obvious continuation is near-coincidence. Two sectors a thousandth of a degree apart are two sectors for the reduction and one for a folder, so a procedure that treated near-ties as ties would be cheaper and would sometimes be wrong; how much cheaper and how often wrong is a measurement nobody here has made, and it needs a threshold that does not exist naturally.

The other is the whole pattern. Everything above is a vertex, and a pattern is not its vertices: its cost is not the sum of theirs — the interactions between them are the intractable part, and whether coincidence predicts anything there is a question this measurement cannot reach.