A no costs more than a yes

Four questions can be asked about one sheet and this site asks all of them: does a pattern fold flat, can a machine reach the folded state, how many folded states are there, and which assignment produces one. Each has two answers, and the answers are treated as though they were the same kind of thing.

They are not. In this subject a yes and a no are asymmetric, and the asymmetry is not a technicality about computation — it is about what each answer hands over.

What a yes hands over #

Ask whether a crease pattern has a mountain-valley assignment satisfying the local conditions, and suppose the answer is yes. What comes back is a labelling: one letter per crease.

That labelling can be checked by somebody who did not run the search, and checking it is a single pass. At each interior vertex, count the mountains and valleys and confirm they differ by two; find the sectors that are strictly smaller than both their neighbours and confirm that the creases bounding each of them differ. Every vertex, once. Nothing about the search that found it needs to be trusted, understood, or even known about.

This is what makes a yes cheap to believe. The site’s whole practice rests on it: every pattern published here has been past four conditions at every interior vertex, and the ledger of what each generator actually checked is produced by running the check rather than by describing it.

What a no hands over #

Now suppose the answer is no.

What comes back is a program’s word that it looked everywhere. There is no object. There is nothing to hand to a reader, nothing to check in a pass, nothing that survives the program being deleted. The claim is entirely about the method, and the method is exactly the part a reader cannot see.

That is uncomfortable and it is not fatal. Exhaustive searches are real, their exhaustiveness can be argued, and a well-constructed one settles a question as firmly as a proof. The trouble is that an exhaustive search and a search that gave up produce identical output.

What happened here #

This phase produced a false negative and it is worth recounting exactly, because the failure is the ordinary one rather than an exotic one.

The site needed a labelling for patterns far too large to enumerate — a patch of twist tessellation has several hundred free creases against the twenty-two the brute-force enumerator will handle. So a constraint solver was written: enumerate the labellings of each vertex’s own four creases that pass, propagate to a fixed point, branch where propagation stalls.

It carried a step budget, as such things do, to stop a runaway search hanging a build. The budget was a single counter shared across the whole recursion, and when it ran out the propagation returned false — which the search read as a contradiction and reported as “no assignment exists”.

So a sheet folded flat at random ten times, whose crease pattern is by construction the pattern of a flat-folded object, came back as having no valid assignment. The search had not looked everywhere. It had looked for two seconds and then said no.

The bug was caught by a control and not by inspection. The crumple work had a population of patterns whose answer was known in advance from how they were made, and the solver disagreed with the construction. Without that, the false negatives would have been indistinguishable from results, and the interesting finding — that certain patterns have no assignment — would have been reported at the wrong angles for the wrong reason.

Two negatives from this phase, and why one is worth more #

Two claims of the form “no such thing exists” came out of this work, and they stand on very different footings.

The first is checkable and stands. A twist tessellation past its ceiling has pleats of negative width. That is a measurement: compute the gap between two facing sides and read the sign. Anybody can repeat it with one subtraction, and no search is involved anywhere.

The second is a search result and needs its method. A twist tessellation below its floor has no mountain-valley assignment at all. That rests on the solver returning nothing, on the solver being complete, and on the budget bug being fixed. It is supported by the negative persisting on patches of seven, eleven and twenty-three twists, by its disappearing sharply at a threshold the geometry predicts, and by the same solver finding assignments instantly on either side of it — but every one of those supports is still about the search.

That is the general form of the repair. A negative cannot be handed over, so what is handed over instead is a reason — a geometric statement that predicts where the negative should start and stop, checked against where it does.

The middle case: a no that is really a “not yet” #

Between a checkable no and an unsupported one sits a third thing, and this subject is full of it.

The oldest open problem is a counting question whose answers are known term by term and whose general form is not. Each term is an exhaustive count — 8 foldings of a two-by-two map, 60 of a two-by-three, 1,368 of a three-by-three — and each is a positive result about a specific size. What is not known is anything about the next size, and that gap is not a negative claim at all; it is an absence of a claim, which is a third status and reads like the other two on a page.

The three statuses are easy to run together in prose and they carry very different weight: here is one, there is none, and nobody knows. This site’s own habit of putting a number next to every claim helps with the first, does nothing for the second, and is silent on the third.

The refusal that has to be built #

The site’s habit for this is old and it applies with particular force here: an assertion that has never rejected anything proves nothing, so every checker is fed something it must refuse.

For a search the refusal has a second job. It has to establish not only that the search can say no, but that its no is about the input. A search that says no to everything is useless; a search that says no when it is tired is worse than useless, because its output is correlated with size rather than with truth.

So the machinery now does two things it did not. The budget throws rather than returning false, which turns a silent wrong answer into a loud absence of one; and the negative results are stated with the size of the instance they were established on, because a no that has only been established at one size is a no about that size.

Where the model stops #

A yes here is still local. The labelling a search returns satisfies the conditions at every vertex and that has never been sufficient — a pattern can pass everywhere and have no folded state. So the asymmetry described above sits inside a larger one: the checkable yes is a yes to a weaker question than the one anybody wants answered.

None of this is a statement about how hard the problem is. How the work grows with the size of the pattern, what algorithm would do it faster, and which complexity class the question belongs to are algorithms-data-structures.com’s subject, and nothing above measures a cost or names a class. What is claimed is about the shape of the two answers — one is an object and one is a promise — which is true whatever the cost of obtaining either.

Exhaustive is a property of the argument, not of the program. The branch-and-bound search behind this phase’s lattice packings visits fifteen thousand arrangements out of 325 million and settles all of them, because the ones it skips are excluded by an argument. The same program without the argument would be a sampler with an identical printout.

The one case where a no is as good as a yes #

There is an exception and it is worth having, because it shows what the asymmetry actually depends on.

Sometimes a negative comes with a witness for the negative. A pattern whose interior vertex has an odd number of creases cannot fold flat, and the witness is the vertex: point at it, count to five, and the question is closed in a pass. A pattern whose sectors fail Kawasaki fails for the same kind of reason, and the residual is the witness — a number anybody can recompute.

So the distinction is not between yes and no. It is between claims of the form here is a thing and claims of the form there is no thing, and a local condition converts the second into the first: an odd vertex is a thing, and its existence refutes the pattern. What has no witness is the global claim — no labelling of five hundred creases satisfies all ninety vertices at once — because the failure is not located anywhere.

That is exactly the shape of the local-versus-global distinction the site has been making since its foundation, arriving from the side of evidence rather than from the side of theorems.

Every checkable no is a yes about something else #

The exception in the last section can be stated exactly, and stating it exactly turns a list of cases into a rule a reader can apply without knowing anything about the machinery.

Look at the quantifier. Some assignment of this pattern satisfies every vertex is an existential: it asserts that a thing exists, and the thing is the certificate. Every vertex of this pattern satisfies four conditions is a universal: it asserts something about a list, and there is no single object to hand over — a reader has to walk the list.

Negation exchanges the two. The negation of an existential is a universal, which is why no assignment exists has nothing to hand over: it is a claim about every one of an exponential number of labellings, and no member of that set is evidence for it. The negation of a universal is an existential, which is why this pattern has a vertex of odd degree is cheap: it names one vertex, and one vertex is the whole argument.

So the exception is not really an exception. A no with a witness is a yes about an obstruction, and the obstruction is what gets handed over. An odd vertex is a thing; a Kawasaki residual is a number; a pleat of negative width is a measurement. In each case the refutation is an existential claim wearing a negative’s clothes, and it is cheap for the same reason every existential is cheap.

Which sorts the site’s own negatives without running anything #

The rule applies immediately to the three negatives the essay lists, and it sorts them the way their methods do.

No assignment below the floor is the negation of an existential over labellings. There is no obstruction to point at — the pattern’s vertices are individually fine, and what fails is the attempt to satisfy them together — so nothing can be handed over and the claim is worth what the search is worth. That is the one this essay is about, and the quantifier says so before anything is known about the solver.

No pleat of positive width past the ceiling is a universal over pleats whose negation is witnessed by a single pleat. Establishing it means checking every pleat, which is a short list; refuting it would take one. It is cheap in both directions because the list is short, and that is why it is the checkable one.

No flat state for a membrane hinge at any clearance is a universal over a continuum, which no finite check can walk — and the site does not walk it. It is established by evaluating a closed form, which is a proof rather than a search, and a proof is the only thing that settles a universal over an infinite set.

So the three negatives are supported by three different kinds of thing: a search, a finite check, and an argument. The rule for reading them is the quantifier and the size of what it ranges over, and both are visible in the claim itself before any method is described. That is a better test than trusting a printout, and it costs a reader one sentence of attention per claim.

Why folders never needed this distinction #

There is a reason this asymmetry has no traditional form. A folder asking whether something folds does not run a search; they fold it. The answer arrives as an object in their hands, which is a certificate of the most direct kind, and the negative case does not arise as a claim — a folder who cannot make something has not established that nobody can.

The distinction only becomes load-bearing when a program starts making claims on the subject’s behalf. Then a printed “no” looks exactly as authoritative as a printed “yes”, occupies the same line of output, and carries none of the same weight. Every result on this site that takes the form nothing of this kind exists is in that position, and there are more of them than one would expect: no assignment below the floor, no rigid folding for a perturbed Miura, no flat state for a membrane hinge at any clearance.

Each of those is worth what its method is worth, and the methods are not alike: one is a search, one is a residual measured over a perturbation, and one is a closed form evaluated at a limit. Only the first has the failure mode this essay is about, and it is the one that reads most like a fact. The habit that keeps them honest is the one the site already runs on — feed the machinery the case it must refuse — with one addition this phase forced: make it impossible for a search to report exhaustion as a result.

What this costs a reader #

The practical upshot is a rule for reading this site, and it is worth stating rather than leaving implicit.

Every figure here carries a caption, and captions of two kinds appear. Some say this pattern satisfies these conditions at these vertices, and the evidence for them is on the page: the pattern is drawn, the numbers are printed, and a reader with an afternoon could check any of it. Others say no such thing exists, and the evidence for those is a program that was run once on a machine nobody else has access to.

The site’s answer to that is the assertion ledger — what each generator actually checked, produced by running it rather than by describing it — and it helps with the first kind and not much with the second. A ledger entry reading “the search found no assignment” is a faithful record of what the search said.

So the negatives are carried differently: stated with the sizes they were established at, paired wherever possible with a geometric reason that predicts them, and accompanied by a control whose answer is known independently. That is three supports where a positive needs none, which is the honest exchange rate between the two answers.

Where the ladder goes next #

The natural continuation is the certificate for the harder question. A yes to does this pattern fold flat would be a folded state — a placement of every panel with a layer order — and that is checkable in a pass too, by testing for penetration. The site has the folded state machinery and does not yet produce such a certificate for a pattern it has only checked locally, so the strongest thing it can currently say about a large pattern is that nothing local refuses it.

The other direction is the population of negative claims already on the site. Each was established by a different piece of machinery with a different notion of exhaustive, and none of them has been audited for the failure mode above. That audit is a piece of work with a known method and an unknown answer, which is the most interesting kind.