The fold a machine can make

Every theorem on this site so far has been an existence statement. Kawasaki and Maekawa say a vertex can collapse; a strip’s layer order can be solved and the solver returns a stacking; a Miura has a folded state and the state is computed. None of them says anybody can get there, and it turns out that this is not a quibble.

That strip is the smallest object this repository has found that separates two ideas usually run together: a crease pattern that folds flat, and a crease pattern something can fold. Anybody with the paper folds it immediately, because hands are not restricted the way the machine in the figure is. What the machine has that hands do not is a rule, and the rule is worth stating precisely, because everything in this field that is tractable lives inside one restriction or another.

What a simple fold is #

A simple fold picks a straight line, picks some of the layers of paper crossing that line, and rotates everything on one side of the line through 180°. That is the entire move. It is the one a sheet-metal brake makes, the one a paper folder following a diagram makes when the diagram says “fold in half”, and the one a laminating machine makes when it doubles a web of material back on itself.

Three versions of it appear in the literature — the taxonomy is due to Esther Arkin, Michael Bender, Erik Demaine, Martin Demaine, Joseph Mitchell, Saurabh Sethia and Steven Skiena, in their 2004 paper on the folding of maps — and they differ only in which layers the machine is holding:

• all-layers: every layer crossing the line folds. Nothing may be left behind.
• some-layers: any contiguous block of layers at the top or the bottom of the pile.
• one-layer: exactly one, top or bottom.

The word “simple” is doing real work. It excludes the move a person makes without noticing — reaching into the middle of a pile, easing two flaps apart, collapsing four creases at once because the paper wants to. A simple fold is atomic and it is flat: after it, the paper is again a flat pile.

Two things follow immediately, and the second is the interesting one.

First, a machine restricted this way is weaker than the theorems, because the theorems constrain the destination and the machine constrains the route. Second — and this is not obvious at all — taking fewer layers is a restriction rather than a licence. That is the subject of the next rung and it goes against every intuition about patience.

The two-crease strip, in full #

Take a strip a hundred millimetres long. Crease it at forty millimetres and at fifty. Call the first crease a mountain and the second a valley. The three segments then measure forty, ten and fifty.

It folds flat. The ten-millimetre segment turns back on itself between its neighbours, the fifty-millimetre segment comes to rest on top, and the layer solver — which knows nothing about sequences and only searches stackings — reports one legal arrangement.

Now hand it to a machine that must take every layer.

The machine has four opening moves, because there are two creases and each can be folded with either side travelling. Take the first: fold at the forty-millimetre mark, right side over. The fifty and the ten travel together and land back across the forty, so the pile is now two layers deep from the ten-millimetre mark leftward. The remaining crease has moved with the paper, and it now sits underneath the first segment.

To fold there, the machine would have to fold the first segment too. The first segment has no crease at that point. It is solid paper, and solid paper does not fold at a place where there is no crease.

The other three openings fail the same way with the parts exchanged, and the figure at the top of this essay draws all four. There is no fifth. The machine is not being unlucky; it is being told to hold everything, and holding everything means it cannot fold anything the bottom layer disagrees with.

Why the length matters #

Change the numbers and the obstruction goes away. Crease the same strip at twenty-five and fifty millimetres — segments of twenty-five, twenty-five and fifty — and the all-layers machine folds it without difficulty, because after the first fold the two creases coincide on the line and the machine can take them both.

That is the shape of the whole result. Even spacing is the case where the creases keep lining up, and lining up is exactly what an all-layers machine needs, because after each fold the creases still to be folded have to agree across every layer. Uneven spacing scatters them, and once they are scattered the machine’s first fold buries the rest.

The figure shows the effect at four creases: evenly spaced, every one of the sixteen assignments folds flat and every one is reachable. Move the creases so that no two gaps are equal and the all-layers count drops to zero while the flat-folding count stays at eight. The paper has not changed. The question has.

Over 117 randomly generated spacings at two, three, four and five creases, this repository found the all-layers machine strictly weaker than flat-foldability on 83 of them. The other 34 were the ones whose spacings happened to be commensurate.

The comparison between the two figures is the essay in one glance. Same machine, same number of creases, same alphabet of moves. One strip has its creases at quarters and folds; the other has one short segment in the middle and does not.

Which makes the agreeing case the rare one #

The census over a hundred and seventeen spacings is reported as a majority and it is worth reading as a genericity statement, because that is what it is.

Eighty-three of the hundred and seventeen have the machine strictly weaker than flat-foldability. The thirty-four that agree are the ones whose gaps are commensurate — whose crease positions are whole multiples of a common length — and that is not a property a spacing has by accident.

Two real numbers are commensurate with probability zero. So a strip whose creases are placed without regard to one another is, with certainty, a strip on which the machine’s creases stop lining up after the first fold, and the all-layers machine reaches nothing at all on it. Seventy-one per cent is what the measure-zero statement looks like when the spacings are drawn from a generator that produces round numbers; a generator with no such habit would give a hundred per cent.

That puts this result in the same family as the genericity argument about flat-foldability itself, one level up. There the observation is that a drawn pattern satisfies an equation with probability zero and every pattern that folds was constructed to. Here it is that a drawn pattern has commensurate gaps with probability zero and every pattern a machine can fold was constructed to.

And says which patterns those are #

The construction is the same one in both cases, and it is the reason the whole subject looks easier than it is.

A folder builds a grid by halving: fold edge to edge, unfold, fold again. Every crease so produced is at a dyadic fraction of the strip, so every gap is a multiple of the smallest, and the spacing is commensurate by construction rather than by luck. The same is true of a strip divided into thirds or fifths by any exact construction — the divisions are rational and the gaps share a unit.

So the patterns a machine can fold are precisely the patterns a folder makes by dividing the paper, which is nearly all of the traditional repertoire and all of manufacturing. A production line folding a map is folding a strip whose creases are at exact fractions of its length, because that is what a printing and cutting process produces.

The measure-zero set is the entire practice. Everything anybody folds lives inside it, and the strip at the top of this essay — forty, ten and fifty — is what it takes to step outside: three segments whose lengths share no common divisor, which is a thing nobody would draw and which is what almost every crease pattern in the space of crease patterns looks like.

The obstruction is not local #

There is a tempting way to summarise the two-crease failure — the second crease got covered up — and it is worth resisting, because it suggests a local fix. It suggests that a machine with a slightly longer reach, or one that looks one move ahead, would get through.

It would not, and the reason is that the obstruction is a property of the whole state rather than of a place in it. The machine’s difficulty is that after its first fold the pile has a layer with a crease and a layer without one at the same point, and no amount of looking ahead changes what is underneath. The only escape is to be allowed to hold fewer layers, which is a change to the machine rather than to its strategy.

This is the same distinction that separates the local vertex conditions from the global question, arriving in a different guise. There the local tests could not see the layer ordering; here the machine cannot see past the layer it is pressing.

Existence and reachability #

It is worth saying plainly what has been separated, because the words are used loosely everywhere else in the subject.

A crease pattern is flat-foldable when a legal folded state exists: an assignment of every face to a layer such that no two pieces of paper pass through one another. That is a statement about a configuration.

A crease pattern is foldable by a machine when some sequence of that machine’s moves ends in such a state. That is a statement about a path through a space of configurations, and paths are strictly harder to have than endpoints.

Nothing about the first implies the second. The strip at the top of this essay is the proof, and it is two creases long.

The reverse implication does hold, and it is not free either: a machine’s moves are physical, so any state a machine reaches must be a legal flat folding. This repository checks that rather than assuming it. Every finished state the simulator reaches is handed to the stacking search’s own legality test — written for that search, before any of this existed, which knows nothing about sequences — and the state must pass. It always does, which is the correctness argument for the simulator and the reason the counts above can be trusted against each other.

What this costs the subject #

Three consequences, in increasing order of how much they matter.

A folding diagram is a machine model. The step-by-step diagrams that origami is taught with are sequences of moves, and the moves are mostly simple folds. That is why so many traditional bases are made of halvings and quarterings: those are the patterns whose creases line up, which is the condition an all-layers sequence needs. The tradition selected for machine-foldable patterns long before anybody defined the term.

Manufacturing lives entirely inside the restriction. A sheet-metal brake is an all-layers machine with a hard limit on how many layers it can close on. A production line folding a map, an airbag or a stent is executing a fixed sequence of simple folds. When an origami mechanism gets built, the question that decides whether it can be made is not whether the pattern folds flat but whether a machine’s sequence reaches it — and the second question has a different answer.

“Foldable” in a paper’s title usually means the first thing. A result asserting that some family of patterns is flat-foldable is not a result about making them. This is not a criticism of anybody; it is a reason to read the definition each time.

What the figure cannot show #

The figures here are one-dimensional. Every strip in this essay is a line with creases on it, and the reason is not simplicity of exposition — it is that one dimension is where these questions can be decided.

In two dimensions the simulator would have to track pieces of a plane rather than intervals of a line, and the layer ordering it maintains would be the partial order that has no local answer. The all-layers restriction does not rescue the two-dimensional problem: deciding whether a general crease pattern can be simple-folded is itself hard, and the tractable results in the literature are for maps ruled into a grid rather than for patterns in general.

So this essay’s claim is exactly as wide as its figures: in one dimension, with an all-layers machine, here is a strip that folds flat and cannot be made. Everything about the two-dimensional case is inherited from that by analogy, and analogy is not proof.

The other thing the figure cannot show is the folding itself. A pile of layers drawn as a stack of horizontal lines is a diagram of a cross-section, and the paper’s turns at the creases are drawn as curves for legibility rather than because the paper has that radius. The crease has a radius, and it is not this one.

The idealisation that is doing the work #

One assumption underlies the whole model and is worth naming rather than leaving implicit: the machine can close on any number of layers.

A real brake cannot. Layer count is the binding constraint in every manufacturing process that folds anything, which is why thickness gets its own field on this site. A model that lets a machine press forty layers as easily as two is a model of geometry rather than of manufacturing, and the results here are geometric results.

That cuts both ways, pleasingly. The strip at the top of this essay is unfoldable by an all-layers machine with unlimited strength. Restricting the machine further — as reality does — can only make things worse. The negative result survives the idealisation being removed, which is the good direction for a negative result to survive in.

Who found this, and when #

The machine models come from the map-folding paper of Esther Arkin, Michael Bender, Erik Demaine, Martin Demaine, Joseph Mitchell, Saurabh Sethia and Steven Skiena, first circulated in 2001 and published in 2004. That paper’s central results are about maps ruled into a grid — the two-dimensional case — and it is where the all-layers, some-layers and one-layer distinction is set out.

The one-dimensional case has been folklore for longer, largely because it is the case anybody working on the general problem checks first. What this essay adds is not a result but an object: a two-crease witness, found by exhaustive search over spacings and assignments in this repository, drawn from the simulator’s own states, and small enough to fold.

The two solvers that produce it were written for different reasons. The layer solver came from the strip’s decidability and searches stackings. The sequence simulator came from this essay and searches sequences. They share no code, they answer different questions, and where they disagree — which is often — the disagreement is the subject.

Where the ladder goes next #

Three directions, and the next essay takes the one that is most surprising.

The machine models can be compared, and the comparison does not come out as a chain. Taking fewer layers turns out to weaken a machine rather than free it, because paper is joined: what a machine declines to hold, it also cannot move.

A different primitive gives a different power. A machine that can only crimp — folding two adjacent creases as one motion — reaches patterns the all-layers folder cannot, and is defeated by patterns the all-layers folder handles easily. Neither is a restriction of the other.

And the loss can be recovered. A machine allowed to choose its layers reaches every flat folding of every strip this repository has tested, which locates all of the difficulty in being forced rather than in folding one line at a time.