What it costs to know

The oldest open problem

In how many ways can a map be folded? The question needs no notation to state, the answer is a small integer for small maps, and after sixty years there is still no formula — only a list of numbers, each one found by searching every possibility.

The fold a machine can make

A theorem that says a folded state exists says nothing about getting there. A machine that folds every layer at once is stopped by a strip with two creases in it — one that folds flat perfectly well, and that a pair of hands folds in about four seconds.

The patient machine is the weak one

A machine that folds one layer at a time sounds like a machine with more freedom, not less. It has less, and the reason is the most ordinary fact about paper there is: it is joined, so whatever a machine declines to hold it also cannot move.

A machine that can only crimp

Change the atom and the whole picture changes. A machine whose single move folds two adjacent creases at once reaches strips no simple-fold machine reaches, is defeated by strips they handle easily, and cannot fold an odd number of creases at all — for reasons that are pure arithmetic.

The machine that may choose

Three restricted machines lose patterns that fold perfectly well. Give one of them a choice — any block of layers, top or bottom — and the loss vanishes: over a hundred and seventeen spacings, every flat folding of every strip became reachable. Being forced was the whole problem.

Four questions about one sheet

Deciding, counting, listing and optimising are not four difficulties of one problem. They are four problems, and folding is the subject that proves it: a ruled map is trivial to decide and unsolved to count, while a general crease pattern is the other way round.

Hardness is about the worst one

Flat-foldability is NP-hard, and every crease pattern on this site is decided in under a second. Both are true, and holding them together is the difference between using the result and repeating it: hardness is a statement about the worst instance a family contains, and nobody folds the worst one.

The answer is bigger than the question

A twelve-square strip of stamps is twelve numbers of input and 146,376 objects of output. No algorithm writes that faster than it can be written, so 'efficient' has to be measured against the answer rather than against the question — and in folding that is the normal case.

Where the exponent comes from

The number of ways a strip of stamps folds grows exponentially, and the base of the exponential is a number nobody has proved exists. The ratio of one term to the last climbs past three and is still climbing where the computation stops — which is the only structural handle anybody has on the sequence.

What a checker cannot check

Every crease pattern on this site is run past four theorems before it is allowed onto a page, and passing all four proves nothing. The gap is not a bug to be closed: it is the NP-hardness result, arriving as a property of a hundred lines of code.

What universality costs

The fold-and-cut theorem says any straight-line drawing can be flattened onto a single line. It says nothing about how much crease pattern that takes, and the amount is a measurable quantity — computed here by running the construction rather than by estimating it.

Getting close instead of getting it right

When the best answer is out of reach the question stops being what it is and becomes how much is lost. For packing discs into a square the loss is measurable: a seeded search in this repository comes within a fifth of a percent of the best radius anybody has proved, and proves nothing.

A no costs more than a yes

When a folding question comes back yes, it comes back with an object: a labelling, a stacking, a folded state that anybody can check in one pass. When it comes back no, it comes back with nothing but the assurance that a search looked everywhere — and that assurance is the first thing to break.

Two directions that will not separate

A map has rows and columns, and a strip of stamps is a map with one row. The obvious hope is that the two-dimensional count is built from the one-dimensional one — fold the rows, then fold the columns. It is not: a two-by-three map folds 60 ways against a product of 12, and the discrepancy grows from a factor of two to a factor of thirty-eight over the counts anybody has.

The map that is not a rectangle

Take one square out of a three-by-three map and the number of ways it folds does not go down by an eighth. It goes up — to 848 if the square came from a corner, and to 8,016 if it came from the middle. Two maps of eight squares in the same box, differing by nearly a factor of ten, and no function of the box tells them apart.

A short reason to say no

When a folding question comes back yes it brings an object anybody can check. When it comes back no it usually brings nothing but the assurance that a search looked everywhere. At one vertex that is false: a refusal comes with a witness one or two steps long, out of a search space of a hundred and twelve, and the witness is a vertex the crease pattern does not contain.

Which vertices are the random ones

Every measurement on this site that begins 'over 373 random degree-four vertices' is a statement about a population nobody declared. There is no canonical way to pick a crease pattern at random, four defensible ways of doing it disagree about the same three questions by factors rather than by margins, and the disagreement reaches a sentence this site has published as though it were general.

Four ways to draw a pattern

Every sentence here of the form over some crease patterns is a statement about a construction nobody declared, and it is worse than the same problem at a vertex because a pattern has a shape as well as angles. Four ways of producing a pattern that satisfies every condition disagree about how far it shrinks by a factor of twelve, about how much creasing it costs by a factor of six, and about how much of it is edge by a factor of two.

The cost is in the coincidences

How big an instance is, is what a hardness statement is about, and it is the weaker predictor of what deciding one costs. Hold the degree fixed and vary only how many of a vertex's sectors are equal: the work of deciding it rises by a factor of nearly three, against a factor of two for doubling the number of creases. The expensive instances are the ones a designer draws on a grid.

The count counts labels

One, two, six, sixteen, fifty, a hundred and forty-four: the oldest sequence in the subject counts foldings of a strip of numbered stamps. A folded strip of blank paper has no first stamp and no top side, and neither of those operations ever leaves a folding alone — so the count of objects is 1, 2, 5, 14, 38, 120, and it is not the count over four.

Where the machine catches up

The weakest machine in the subject folds every layer at once and is stopped by a strip with two creases in it. On a strip of equal stamps it is stopped by almost nothing: every one of the 288 folded states a six-stamp strip has is reachable by a sequence of all-layers folds, and on every unevenly creased strip tried it reaches none of them. At seven stamps the completeness ends, and finding out where it ended is what checking it past six was for.

The map counted from the layers

The classical map-folding counts are computed from a rule that never places a panel: work out which edge of the folded square each fold wraps around, and refuse the orderings that interleave two folds at one edge. Place the panels instead and order them by the general non-crossing rules, and the same numbers come out — 2, 6, 16, 50, 144, 8, 60, 320, 1368 — on nine sizes, by machinery that shares no line of code with the first.

The patterns a checker is tested on

This site keeps four populations of crease patterns and runs its checkers over them, which is what makes a claim about typical instances measurable rather than rhetorical. Asked whether the members actually fold, the populations answer: thirteen of thirty-three do, six place and cannot be ordered, five cannot be placed at all, and nine are past what the search will finish.

The order the refusals come in

This collection can say no to a crease pattern in five ways, and they cost wildly different amounts: a sweep over pairs of creases, a pass over the vertices, a walk over the panels, a pass over the crease list, and an enumeration of every ordering of the panels. Run all five over the thirty-three patterns in the four test populations and the cheapest refuses five, the most expensive refuses six, and the three in between refuse nothing at all.

Drawn by the same hand

Two straight segments dropped on a square cross about 23% of the time; four of them cross 74% of the time; twelve cross with certainty, about fifteen times over. Every crease pattern in this collection's four test populations has none — not because the checkers were catching them, but because the same rules that drew the patterns were incapable of producing one, and nothing looked until a construction finally did.

The refusal that reads the list once

There are five ways of saying no to a crease pattern here, and their costs are two hundred and eighty-two, a hundred and twenty-six, a hundred and fifty-seven, thirty-nine thousand six hundred and twenty-one — and a search that is refused outright. On the largest patch the four cheap tests together do less work than one of them looks like it should, and the fifth cannot be started. A refusal that reads the crease list once is the only kind that scales.

A population that cannot fail

Thirty-three crease patterns are kept here to run the checkers over, and every one of them has letters that agree with themselves. That is not a property of the patterns. It is a property of how they were made: each came from a construction that returns a lettering, so a test looking for letters that contradict themselves has nothing to fire on. Reletter the same thirty-three and the failure is available at once — on one member, four of sixty redraws.

Stopping is cheaper than finishing

A search whose cost varies by a factor of two hundred with nothing but the order of its guesses should not be waited out. Give up after a hundred steps, reseed and start again, and the whole job costs five hundred and twelve steps in expectation; run each attempt to twenty thousand and it costs sixteen thousand two hundred and ninety-one. Patience is thirty-two times more expensive than impatience.

Four populations with nothing to separate

This collection keeps four standing populations of crease patterns to test its machinery against. Twenty-eight patterns, sampled forty times each for a lettering that agrees with itself and then searched for one — and on every single member the two methods return the same verdict in the same breath. The patterns that separate them are in none of the four, and the reason they are not is what the populations are for.

The test that never fires on a map

The cheapest refusal this collection has reads a crease list once and reports that no arrangement of the layers exists. Enumerate every labelling of every map from two panels to nine and it fires on four of the four hundred and fifty-four — all four on the largest map, none at all below it. On the oldest open problem in the subject, the cheap test has essentially nothing to say.

Which choice the cost lives in

A backtracking search takes two decisions at every step — which thing to decide, and what to decide about it. The literature is almost entirely about the first. On these crease patterns the whole of the cost was in the second, and the structural improvement everybody reaches for first makes matters worse on fifty-two patterns out of eighty-seven.

The order that proves nothing exists

Twelve crease patterns with no consistent lettering at all. Proving it takes fifteen steps under one rule and half a million under another — and on three of the twelve the two rules swap places, so neither is the good one. The cost of a negative is two to the power of how many free choices sit above the contradiction.

A population nobody chose

Five crease patterns were measured over and over because somebody had drawn five. Ninety-six drawn from a stated grid of tiling, turn and pleat width say something the five could not: nine of them have no consistent lettering at all, and the phenomenon the collection had spent so long measuring belongs to the one tiling the grid leaves out.

Restarting what cannot be restarted

Stopping a search early and starting it again with a fresh seed costs five hundred and twelve steps in expectation against sixteen thousand for patience. Every number in that is right. The distribution it is right about was made by the search's own coin, and taking the coin out costs eighty — with nothing left to reseed.

What the rim was doing

One rectangle of a twist tessellation, cut out of the plane in the ordinary way, gives up a consistent lettering in forty-eight steps. Join its opposite edges so that no crease is divided and the same drawing, at the same vertices, under the same conditions, takes fifty-six thousand seven hundred and seventy-two. The edge of the paper was never the difficulty. It was the slack.

Pruning on proofs alone

A search that discards a branch it cannot prove wrong is not a search. Deciding whether a periodic pattern's layer relations really contradict themselves is far dearer than the disc's one-pass test, so the cheap test is asked first — it is sufficient, so it settles almost everything — and the expensive one runs only on what the cheap one rejects. Five of nine steps on a small cell, fifty thousand of fifty-seven on a large one.

The cost of proving something false

A search closing its whole tree is the strongest result this collection can produce, and on a glued tessellation it produces one that is wrong. What it costs to reach is three steps at one period, thirty-five at four, three thousand four hundred and fifty-five at nine, and more than two hundred thousand at sixteen — growing far faster than the cost of finding the lettering it says does not exist.

Where you cut hardly matters

Slide the same rectangle across one whole period of the same tessellation and every position gives a different patch: different creases divided, different half-panels round the edge, panel counts from forty-nine to sixty-one. The cost of lettering them runs from twenty-five steps to thirty-three. Whether a cut is made changes the answer by three orders of magnitude; where it falls changes it by a third.

Half the slack

Gluing one pair of a cell's edges removes half the free letters and costs almost nothing. Gluing the second pair removes the other half and costs three orders of magnitude. The letters go linearly and the search does not, and the reason is that the last free letter is worth more than all the others.

Which pair is glued

A cell's two cylinders have the same Euler number, the same amount of rim and the same name. On a symmetric drawing they have identical counts of letters, panels and vertices — and searching them costs twenty-four nodes one way and eighty-five the other. Half the rim is a description of the topology and not of the object.

A proof in no nodes at all

A parity refuses a sheet before any search begins. It costs one addition, it is certain, and it says nothing about why — while a search that exhausts on the same sheet costs thousands of nodes and produces a proof of the same fact. Two proofs of one thing, and the cheap one is available only where somebody has noticed the invariant.

The cost of asking the wrong sheet

A test written for a sheet with an edge, run on a sheet without one, does not fail. It exhausts — proving, at three, thirty-five and three thousand four hundred and fifty-five nodes, that no lettering exists — and the letterings it proved impossible fold, on the collection's own machinery, at every size they were tried at.

One population, four sheets

A population of patterns is a way of asking what is typical, and it has always been a population of drawings. Put the same drawings on four different sheets and the verdicts move — not because the drawings changed but because the sheet did, which means a population has two halves and only one of them was ever chosen.

A map with no edges

Counting the ways a rectangular map folds is the oldest open problem in the subject, and every version of it assumes the map has an edge. Join the map's opposite edges and the question changes shape: half the sizes have no folded state at all, and the ones that do have no bottom layer to count from.

The tube a map makes

Join one pair of a map's edges and the result is a tube — a real object, foldable in the hand, and neither the strip's problem nor the torus's. It has one loop that cannot be shrunk instead of two, it keeps its bottom layer because it keeps half its rim, and half its sizes are refused by a parity the flat map does not have.

Deciding is not making

Four earlier essays here ask which machines can flatten a strip at all, and the answer sorts them into a lattice with one column full and three with holes in it. Asked instead what each machine can produce, the three sort completely differently: the machine that may choose its block reaches every folded state of every strip tried, the machine that takes one layer reaches exactly four whatever the strip is and however long, and the machine that takes the whole pile is the only one whose answer depends on the spacing at all.

The easiest strip needs the deepest reach

The patient machine and the machine that may choose are the two ends of one number: how many layers of the pile a machine is allowed to hold. At one it reaches four states whatever the strip; at the pile's full depth it reaches everything. In between it is a machine nobody has defined, and measuring where completeness arrives inverts these essays' own ordering — the evenly creased strip, which the machine that takes everything folds perfectly, needs the deepest reach of all, and one uneven strip is complete at two.

A shallow machine pays in states, not folds

A machine allowed to take only a few layers of the pile at a time reaches fewer folded states, and the natural fear is that it also reaches the ones it does by much longer sequences. Walked breadth first, so that every state's shortest sequence is found, it does not. On unevenly creased strips every state takes exactly one fold per crease at every depth, because no two creases ever lie on one line. On strips of equal stamps a shallower machine needs one fold more for a minority of states and two more for eight of the 924 states at seven stamps — and never more than the crease count, which no machine can exceed.

Fourteen states are one pile

A machine that folds every layer at once reaches every folded state of a strip of six equal stamps and misses fourteen piles at seven. The fourteen are not fourteen things. Taking a pile's bottom stamp and putting it on top maps foldings to foldings, so the 462 piles of seven stamps fall into 33 classes of exactly fourteen, and the missed piles are one whole class: the pile 0 6 1 2 3 4 5 — an accordion of five stamps with the last stamp wrapped round it and slid into the fold that holds the first — seen from each of its seven stamps. At eight stamps the machine misses 64 piles, and they are exactly the piles that leave that one when an end stamp is removed.

Each drawing has its own threshold

Gluing a cell's edges was measured once, at one size, and found to cost three orders of magnitude — which cannot tell a threshold from a slope, nor say whether a cut sheet has one further out. Swept from one period to five on four tilings, every sheet starts at about a third of a node per free letter and every drawing leaves that behaviour at a size of its own: four periods on the square grid, three on the honeycomb, two on the triangular grid and two on the rhombille, where even the cut sheet crosses.

The route, not the sheet

Every cost measured for a glued sheet has been one number from one branch order, and a backtracking search's cost belongs to the pair. Asked under eight orders instead of one, a cut cell's cost barely moves — 42 to 55 nodes — while the torus over the same drawing runs from 69 to 24,636, with one order giving up entirely. The glued sheet's best order costs less than twice the cut sheet's, so most of what a single order charged to the gluing belongs to the route through it.

The cheapest route crosses later

A search for a consistent lettering has a threshold: below it the letters propagate and the cost is a third of a node per crease, above it the search backtracks and the cost explodes. The threshold was measured with one branch order. Measured with eight, the cheapest route never starts searching before the typical one, and on most sheets it starts a period or two later — so part of every threshold on the record belongs to the route. And the one cut sheet past its threshold, the rhombille's, spreads across nearly three orders of magnitude of cost, which moves the spread off the gluing and onto the threshold.