What the grid settles

The rung below makes the case for box pleating as folders make it. Put every crease on a lattice and at forty-five degrees to it, accept that the packing is worse than a free one, and buy back something worth more: creases that land where they are supposed to, on a design with hundreds of them, where error accumulates until a free packing cannot be folded at all.

That is a true account and it is not the whole one. There is a second thing the lattice buys, and it is invisible from inside the folding tradition because the tradition never had the tool to notice it.

Two numbers that are not the same kind of number #

Look at the six-flap row. The free search reaches a circle radius of 0.1876; the four-division lattice reaches 0.1250 and the eight-division lattice 0.1398. Read as a comparison of packings, the lattice loses a third and then a quarter, which is a lot.

Read as a comparison of claims, they are not comparable at all.

The lattice figure is the answer to a finite question. There are 81 points on an eight-division lattice and 325 million ways to choose six of them; each choice has a radius; the largest of those radii is 0.1398, and that sentence is a fact rather than a report. The search that established it visited fifteen thousand partial arrangements, because a partial choice already fixes a smallest gap and no later point can widen it — so a branch already at or below the best complete answer cannot contain a better one, and it is discarded whole. Nothing is sampled. The bound is an argument about all 325 million.

The free figure is the output of a search over a continuum. It is the best arrangement simulated annealing found from a hundred and twenty starts, and for most flap counts the true optimum is unknown — not unknown to this site, unknown to anybody. Circle packing in a square is a subject with a literature and a table of proved cases, and the table has gaps in it that have been open for decades.

So the grid does not merely cost paper. It converts an open problem into a closed one.

What “the optimum is unknown” actually means #

The phrase deserves unpacking, because it is easy to hear as a technicality and it is not.

A designer using a free packing has an arrangement and a claim: these circles are as large as they can be for this tree. The claim is supported by a search having failed to do better. That is genuine evidence and it is not a proof, and the difference bites in exactly the case a designer cares about — a design that is nearly good enough, where the question is whether a little more flap length exists to be found or whether the sheet is simply too small.

On a lattice that question has an answer. Not a better answer — usually a worse one — but an answer, and one that closes the question rather than leaving it open. A design that fails at 0.1398 on an eight-division lattice fails, and no amount of further searching will rescue it; the sheet must get bigger, the grid finer, or the model must change.

Where the loss is, and where it is not #

The loss is not uniform, and the pattern of it is more interesting than its size.

At four flaps the lattice costs nothing. Four circles in a square go in the four quarters, the quarter-points are on any even lattice, and the free optimum is the lattice optimum: 0.2500 against 0.2500. At three flaps the lattice costs 1.7%, because the free optimum puts three circles in a slightly rotated arrangement that no lattice contains.

At five flaps it costs 14.6% and at six flaps 33.4% on a four-division lattice. Those are the counts whose free optima are irrational arrangements — five circles want a diagonal, six want a staggered pattern — and a lattice cannot approximate an irrational arrangement cheaply.

Refining the lattice recovers some of it — six flaps go from 0.1250 to 0.1398 when the lattice is halved — and refining a box-pleated design is not free either, since a finer grid means more creases and the accuracy argument the rung below makes runs the other way. Halving the grid never costs more than the coarser grid did, because every coarse arrangement is still available on the refinement, and that is worth checking rather than assuming: a lattice that is not a refinement of another can genuinely do worse, and a six-division lattice beats a four-division one at some counts and loses at others.

Why enumeration works here and not there #

There is a temptation to ask why the same exhaustive treatment cannot be given to the free problem, and the answer is instructive.

The lattice problem is finite because the positions are finite. Nothing else about it is easier — it is still a question about the largest minimum distance among a set of points, still combinatorial, still growing very fast. Six flaps on an eight-division lattice is 325 million arrangements and seven flaps is 3.5 billion, which is where the enumeration used here stops being run.

The free problem is not finite in any sense a computer can attack directly. The positions form a twelve-dimensional continuum for six circles, and a search can only ever report where it has been. The known optima in the literature are established by very different means — geometric arguments about which circles touch which, followed by algebra — and each one is essentially a separate piece of work.

The bound is the whole trick #

It is worth saying how a search over 325 million arrangements finishes in a few thousand steps, because the method is the reason the word “optimum” is allowed at all.

Choose points one at a time. As soon as two of them are placed, the arrangement has a smallest gap, and every point added afterwards can only make that gap smaller or leave it alone — a new point cannot push two existing ones apart. So a partial arrangement whose smallest gap is already no better than the best complete arrangement found so far cannot be extended into a better one, and the entire subtree below it is discarded without being visited.

That is not a heuristic and it is not sampling. Every arrangement is accounted for: visited, or excluded by an argument that covers all of its descendants at once. The count of arrangements actually scored is a few thousand and the count settled is the full binomial.

The distinction between a search that has been everywhere and a search that has been somewhere is the whole of what separates the two columns of the first figure, and it is easy to lose. Both are programs that ran and printed a number.

Finite is not the same as finished #

The argument so far is that the lattice problem is finite and therefore closable, and both halves are true. What is worth adding is that the closing has only been done at grids much coarser than any real design uses, and the arithmetic says how far the method reaches.

An enumeration over a $g$-division lattice chooses $n$ points from $(g+1)^2$. Six flaps on an eight-division lattice is a choice of six from eighty-one, which is the three hundred and twenty-five million quoted; seven from eighty-one is three and a half billion, which is where the run above stops. Refine the lattice and the base grows: six from a sixteen-division lattice’s two hundred and eighty-nine points is about seven hundred and seventy billion, and six from a thirty-two-division lattice’s one thousand and eighty-nine is over two thousand million million.

The pruning is what decides whether those are reachable, and it can be measured rather than guessed at. The eight-division run scored fifteen thousand arrangements out of three hundred and twenty-five million, which is a reduction of about twenty thousand to one. Carry that ratio across: the sixteen-division case comes out around thirty-five million scored arrangements, which is an afternoon. The thirty-two-division case comes out around a hundred thousand million, which is not.

Which is a real limit on the practical claim #

That matters because sixteen and thirty-two are the grids box-pleated designs are actually drawn on, and four and eight are not.

So the useful statement a designer wanted — this grid has nothing more to give, go finer or get a bigger sheet — is available at the resolutions the table reports and probably at the next one up, and is not available at the resolutions a complex design uses. The finiteness is genuine and the closure is not yet.

The honest form of the essay’s claim is therefore about status rather than availability. A lattice arrangement is the kind of thing that can be settled, and a free arrangement is not; whether it has been settled at a particular grid is a separate question with a separate answer, and at thirty-two divisions the answer is no. That is a much better position than the free problem’s, where the answer is no at every resolution and will stay no until somebody proves a theorem.

It also says where the effort should go, and it is not toward finer grids. The pruning ratio is the whole of what makes any of this reachable, and a bound that used more than the smallest gap — one that knew about the sheet’s corners, or about how many points remain to place — would buy more than a factor of two in resolution. Twenty thousand to one gets the method to sixteen divisions; a hundred million to one would get it to thirty-two, and that is a question about the bound rather than about the machine.

What a designer does with this #

Not very much directly, and that is worth being honest about. A box pleater is not going to enumerate 325 million arrangements before folding; they are going to draw a grid, place the flaps sensibly, and fold.

What changes is the status of what they have drawn. A hand-placed lattice arrangement can be checked against the lattice optimum, and the check terminates. That is a different relationship with a design than the one a free packing offers, where the honest statement is always “nothing better has been found”.

The practical form of the argument is about stopping. A designer working freely never knows whether to keep pushing; a designer working on a grid can be told that the grid has nothing more to give, and that the next move is a finer grid or a bigger sheet. Knowing which constraint is binding is most of what an optimisation is for, and the free version cannot say.

The lattice a folder can actually make #

One more thing separates the lattices in the table from the lattices in a design, and it is a constraint the packing problem knows nothing about.

A folder builds a grid by folding it, and the cheapest grid to fold is one built by repeated halving: two, four, eight, sixteen, thirty-two. Every division is a fold to a crease already made, so the error at each step is the error of aligning two edges and nothing compounds badly. A grid of thirds is a different piece of work — reachable, and reachable exactly, but by a construction rather than by a habit.

So the lattices box pleaters use are almost always powers of two, and the table above uses four and eight for that reason rather than because those numbers are natural to the packing problem. A twelve-division grid would sit between them, would be foldable, and is not what anybody draws.

That is a small historical accident with a measurable consequence: the grids the subject searches are a sparse subset of the grids it could search, chosen for how they are built rather than for what they pack.

Where the model stops #

Equal circles are not a design. Everything above packs circles of one size, which corresponds to a tree whose flaps are all the same length. Real designs have flaps of different lengths, rivers between groups of them, and a tree condition that is stronger than non-overlap. The lattice’s finiteness survives all of that — the positions are still finitely many — and the enumeration does not, since the bound above is specific to equal radii.

The lattice optimum is the optimum of the lattice problem. It is not a bound on the free problem in either direction, and reading it as “the best a designer can do” would be wrong twice over: a free design does better, and a design with unequal flaps does something else entirely.

Nothing here is about the cost of computing. How the enumeration’s work grows, and what algorithm would do it faster, are questions belonging to algorithms-data-structures.com and none of them is asked above. What is claimed is that the lattice problem has an answer and the free one is not known to, which is a statement about the questions rather than about the effort.

The circles remain necessary and not sufficient. A packing is a lower bound on what the paper can do, not a guarantee that the base exists, and a lattice packing inherits that limitation unchanged.

Why nobody says this #

Box pleating arrived in the folding world as a practice — Neal Elias and Max Hulme in the 1960s and 70s, then the box-pleated designs of the 1990s that made the technique famous — and its defenders defended it in the terms practitioners cared about: it folds, it is accurate, it scales to designs with a thousand creases.

The optimality argument requires a computer and a willingness to think of a design as a search, and both of those arrived in the subject with the tree method rather than with box pleating. By the time anybody was running searches, the two techniques had settled into a division of labour — free packings for organic subjects, box pleating for angular ones — and the question of which one could be finished was not being asked of either.

It is worth asking because the answer is unusual. Most disciplines take a discrete approximation to a continuous problem because the continuous one is intractable, and accept a worse answer for a computable one. Box pleating does exactly that, arrived at it for entirely different reasons, and got the computability as a side effect nobody was looking for.

What the same argument does elsewhere #

The shape of this result is not special to packing, and it is worth noticing where else it appears in this subject.

Deciding whether a marked crease pattern folds flat is hard in general and easy on a strip, because a strip’s foldings are a finite list that can be walked. The stamp-folding numbers are known term by term and have no formula, because each term is an exhaustive count and nobody has an argument that covers all of them at once. In each case the same trade appears: restrict the object until the question is finite, answer it completely, and be honest that the answer is about the restriction.

Box pleating is that trade applied to design, arrived at by folders who wanted their creases to line up.

Where the ladder goes next #

The obvious continuation is unequal flaps on a lattice, where the enumeration above stops working and the finiteness does not. A tree with flaps of several lengths still has finitely many lattice arrangements, and the bound that prunes the search has to be replaced by one that knows about radii — a piece of work, and one whose result would be the first optimality claim anybody could make about a real box-pleated design.

The other direction is the grid itself. Every figure here uses a lattice whose divisions are a power of two, because that is what a folder can construct by repeated halving, and what a folder can construct is a considerably richer set than that. A design on a grid of thirds or fifths is foldable, is not a box-pleated design in the usual sense, and has never been searched.