A short reason to say no

A no costs more than a yes is about the asymmetry that runs through this whole subject. 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 the assurance that a search looked everywhere — and that assurance is the first thing to break, because it depends on the search having been written correctly and on nobody having pruned too eagerly.

At a single vertex that asymmetry is not there. A no comes with a witness, the witness is short, and it can be checked without running anything.

What the witness is #

Before the mechanism, it is worth being clear about what would count as a witness at all. A refusal is convincing when it hands over something a reader can check, in less work than the search that produced it, without trusting the search. A folded state is such a thing for a yes: lay it out, verify the three rules, done. The corresponding object for a no would be a reason, and reasons are much harder to package than examples.

The reduction that decides a vertex folds the smallest sector away between its neighbours and asks the smaller vertex the same question. When a vertex does not fold, the reduction stops somewhere: at a smaller vertex whose sector strictly smaller than both its neighbours has the same letter on both sides, which the big-little-big lemma forbids.

That smaller vertex is the certificate. It has a list of angles and a list of letters, both short; checking it means finding the smallest sector and comparing two letters, which takes a moment; and it is derived from the original by a sequence of crimps that a reader can verify one at a time.

Crucially, it is not on the paper. The vertex the refusal names does not appear in the crease pattern. It comes into existence when part of the pattern has been folded, which is why the four conditions cannot see it and why the refusal has to be exhibited rather than deduced.

How long the witnesses are #

Short, and the census says how short.

Of the 576 degree-six labellings that pass every condition and have no folded state, every one is refused after exactly one crimp. Of the 512 degree-eight refusals, 192 come after one crimp and 320 after two. Nothing in the census needed three.

Two things are worth separating in that. The depth of the certificate is one or two crimps, which is how many steps a reader has to follow. The size of the certificate is a vertex of degree four or six — a handful of angles and a handful of letters — which is how much has to be written down. Both are small, and neither grows the way the search space does.

Compare that with the search it replaces. Deciding a degree-eight labelling by enumeration means putting every one of the 40,320 orderings of its sectors past three rules, and a no is the report that all 40,320 failed. The certificate is two steps.

There is a second property of the certificate worth naming: it is independent of the search that found it. A refusal by exhaustion is only as trustworthy as the exhaustion — the enumeration has to be complete, the rules have to be right, and nothing may have been pruned. A refusal by certificate hands over an object; the object is checked against the lemma by whoever is reading, and how it was found stops mattering. That is the whole practical difference between the two kinds of no.

Why it does not extend to a sheet #

A pattern is not a vertex, and the certificate does not lift.

The obvious attempt is to run the reduction at each vertex of a pattern and report the first refusal. That works — and it decides nothing, because a pattern whose every vertex folds may still have no folded state at all. Local is not global is exactly the statement that a per-vertex verdict is not a verdict, and a per-vertex certificate is not a certificate.

What a refusal for a sheet would have to exhibit is an obstruction among the layer orderings — a set of constraints with no consistent solution — and there is no bound on how many constraints such a set has to contain. That is the shape of the open question: flat-foldability is NP-hard, so a yes has a short certificate; whether a no does is the question of whether the problem is in co-NP, and nobody knows.

There is a way of measuring how far short the per-vertex approach falls, and it is discouraging in a precise way. Take a pattern all of whose vertices fold — which is what every pattern on this site is, by construction — and the per-vertex reduction produces no refusal anywhere, because there is nothing at any vertex to refuse. The procedure is not merely incomplete on such a pattern; it is silent. It has no output to give, and a decision procedure with no output is not a partial answer but an absence of one.

The shallowness has a cause worth naming. A crimp removes two creases, so a degree-eight vertex is three crimps from the bottom and a degree-six vertex is two; a refusal that took the maximum number of steps would be one where every crimp was available until the very last. What the census shows is that obstructions do not hide at the bottom: if a labelling is going to fail, it fails at the first or second reduction, where the merged sector’s neighbours are still large enough for the ordering to matter.

Where a certificate does exist for a whole object #

There is one case in the subject where a global no is exhibitable, and it is worth putting beside this one because the mechanism is completely different.

A loop of paper with an odd number of creases has no flat folded state, and the reason is a parity: the panels round the hole take two colours only if the crease count is even. The certificate is the count. It is one integer, it is checked by counting, and it settles a whole sheet rather than a vertex.

That certificate exists because the obstruction is a global invariant rather than a local contradiction. The crimp certificate exists because the obstruction is a local contradiction one step away from the surface. Neither method reaches the case in between, which is where the hardness lives.

The sheet’s refusal has a shape, and a length #

The closing section asks how large a set of layer-ordering constraints has to be before it becomes inconsistent, and calls it a measurement nobody has made. Part of it has been made, on a different rung, and it gives a definite answer for one family of obstructions.

A crease says which of its two panels lies above the other. Collect those statements and they are arrows on the panels; if the arrows close a cycle, no ordering satisfies them and the pattern has no folded state. That cycle is a certificate, it is checked by following it round, and its length is the number of panels in it.

So a sheet-level refusal of this kind is exhibitable after all, and the question is how short one can be. The shortest possible chain of panels is the one going round a single interior vertex, and that loop can never close on a pattern satisfying the conditions — the panels alternate in orientation round a vertex, so the arrows agree only if the letters alternate, and Maekawa forbids an alternation.

Four is therefore the shortest refusal that exists, and it is available only where the count has already been broken. A census of five hundred and twelve repeating rules found a hundred and twenty four-panel cycles, every one of them at a degree-four vertex whose letters are two and two — and every one of those rules had failed Maekawa first, so the cycle certifies nothing the count had not already settled.

Which locates what is missing #

That is a useful negative rather than a disappointment, because it says exactly where the gap is.

Refusals of length four exist and are redundant. Refusals of length eight and twenty-eight also exist — a twist tessellation’s own lettering carried a cycle of twenty-eight panels through several units — and those are not redundant: every vertex of that patch satisfied every condition, and the cycle is the only thing that refuses it.

So the cycle certificate does settle sheets that no local argument reaches, and its length is not bounded by anything local: it ran through several twist units before closing, and there is no reason a larger pattern could not need a longer one. What is not known is whether every unfoldable pattern has a cycle at all. The test is sound and incomplete — a cycle proves failure, and its absence proves nothing — and on the one population where the incompleteness has been measured it caught one failure in four.

That is the honest state of the sheet-level question. There is a certificate, it is short when it exists, it is checked by following arrows, and three quarters of the failures it was measured against had no cycle to exhibit. The gap between a vertex and a sheet is not that a sheet has no exhibitable refusals; it is that most of its refusals are not of the one kind anybody knows how to exhibit.

Which theorem was checked, and how #

The certificate is produced by the same reduction that decides the vertex, and the reduction is checked against an exhaustive stacking search on every vertex and every labelling the census contains — 6,256 pairs, at degrees four, six and eight, with no disagreement.

That check is what makes a certificate a certificate. A refusal produced by a procedure that has not been verified against ground truth is an assertion with extra steps; a refusal produced by a procedure that agrees with brute force everywhere it has been asked is a refusal with a reason attached.

The depth of each refusal is recorded rather than assumed. The reduction reports the step at which it stopped, and the distribution of those depths is the census’s own output — one for every degree-six refusal, one or two for every degree-eight one.

Where the model stops #

The certificate is for a labelled vertex: a set of angles and a set of letters. The question of whether a vertex has any foldable labelling is different, its no would have to exhibit something about all 2ⁿ labellings at once, and the reduction says nothing about it.

The witness is also only as convincing as the crimp step is obvious. Verifying it means accepting that folding the smallest sector away between its neighbours is forced — which is the content of the big-little-big lemma and is a theorem rather than an observation. A reader who does not grant the lemma has to be shown its proof, and then the certificate is short given a theorem rather than short outright.

And this is one vertex, which is a decision problem with a polynomial algorithm anyway. A short certificate is only interesting where the problem is hard, and at a vertex it is not — so what is being demonstrated is the shape of a refutation and not a complexity result.

What the picture cannot show #

The certificate is a vertex that does not exist on the paper, and no figure can show a thing that is not there without drawing it — which makes it look as though it were there. Every frame after the first in the reduction picture is a pattern that the reader is asked to remember is not a crease pattern, and the only device available is the caption.

Nor can a figure show the search the certificate replaces. Forty thousand orderings, all of them failing, is a number.

The generalisation #

The right frame for all of this is the one complexity theory supplies, and it is worth stating carefully because the temptation to overclaim is strong.

A problem is in NP when every yes has a short certificate. Flat-foldability is: hand over a folded state and it is checked in one pass. A problem is in co-NP when every no has one, and whether flat-foldability is in co-NP is not known — which is another way of saying that nobody knows what a refusal would have to exhibit.

What this essay establishes is much smaller and is not a complexity result at all. It is that for one particular family of instances — a single labelled vertex — the refusals do have short certificates, and the certificates have a specific and unusual form: they name an object that is not part of the instance. The obstruction is not visible in the input; it appears one step into a reduction, and the certificate’s job is to point at it.

That form is worth noticing because it suggests where to look for a general one. A refusal that has to be assembled out of the instance’s own parts is a refusal about a local contradiction, and local contradictions are precisely what the hardness construction is built to avoid. A refusal that is allowed to name intermediate objects has more room — and the crimp certificate is the only example in this subject of one that uses it.

Who found it, and when #

The distinction between a problem and its complement, and the observation that a short proof of yes does not imply a short proof of no, is Stephen Cook’s and Leonid Levin’s setting from the early 1970s, and co-NP is the standard name for the other side of it. The complexity of flat-foldability is Marshall Bern and Barry Hayes’s, from 1996.

The crimp reduction is Thomas Hull’s. That it produces a refutation as a by-product does not appear to be remarked on, which is unsurprising: a decision procedure is judged by whether it decides, and what it leaves behind on a failure is only interesting to somebody asking a different question.

One more comparison belongs here, and it is with the site’s own practice rather than with the literature. Every module in this repository ends by feeding its machinery input it must refuse, and the reason is the one this essay is about: an assertion that has never rejected anything proves nothing. What those refusals produce is a thrown error with a message — which is a certificate of exactly this kind, aimed at a reader rather than at a theorem, and short for the same reason.

Two further limits, both about how much the result is worth. A certificate that is short is not automatically a certificate that is findable: the reduction finds this one in one or two steps, which is fortunate, and there is no argument here that a short certificate would always be found quickly if one existed. And a certificate that is short for a reader is not automatically short for a machine, since verifying it requires locating a strictly smallest sector, which is a comparison rather than a lookup.

Neither of those weakens what is claimed. They mark where the claim ends, which is at a single labelled vertex and at the observation that its refusals are exhibitable at all.

Where the ladder goes next #

The obvious continuation is the one nobody can take: a short certificate for a sheet. What is reachable instead is a measurement — for the patterns this site prints, how large a set of layer-ordering constraints has to be before it becomes inconsistent, which is a lower bound on how long a refusal would have to be.

The other direction is the one the last section points at. Two kinds of certificate exist in this subject, a parity that settles a whole sheet and a crimp that settles a vertex, and no method reaches between them. What an obstruction would have to look like to settle a patch — larger than a vertex, smaller than a sheet — is a question with no candidate answer at all.