A map with no edges

How many ways can a rectangular map be folded flat along its creases is the subject’s oldest open problem. It is exactly stated, it has been attacked since the eighteenth century, and the answer is known only for small sizes and by brute force.

Every statement of it assumes the map has an edge, and until recently there was no way to ask it otherwise.

The question, restated #

A map is a grid of squares with creases along every line between them. A folding is an assignment of mountain and valley to each crease together with an ordering of the layers, such that no two panels pass through each other.

The count is enormous and grows fast: a one-by-$n$ strip of stamps has a known and rapidly growing count, and a two-dimensional map has a count nobody has a formula for.

Gluing the map #

Take a rectangle of the grid $n$ squares across and $n$ up, placed so its edges fall midway between creases, and declare its left edge to be its right edge and its top to be its bottom.

That is a map with no edges: a torus of paper ruled into squares, with $n^2$ panels and $n^2$ interior vertices of degree four.

Half the sizes have nothing to count #

The first thing that happens is that the question becomes vacuous for half its instances.

A path running once round the torus crosses $n$ creases. Crossing a crease exchanges which face of the paper is up, so an odd $n$ returns the paper the other way up, and a sheet on which that happens has no two-colouring and no flat folded state at all.

So there is no count to ask for at $n = 1$, $3$, $5$ and so on. Not zero foldings in the sense of an enumeration returning nothing after searching — the object has no folded state, and the enumeration has no space to search.

That already distinguishes the glued question from the ordinary one, where every size has a positive count.

Why an odd map cannot fold, in one paragraph #

The parity argument is short enough to give in full, and it is worth having because it is the only complete result in the essay.

Fold the sheet flat and look down at it. Every panel shows the reader one of the paper’s two faces, and crossing a crease swaps which. So the panels take two colours, alternating across every crease.

Now walk once round the torus. The walk crosses $n$ creases and returns to the panel it started on. If $n$ is odd the colour has flipped an odd number of times and the panel has to be both colours at once, which is a contradiction.

If $n$ is even, no contradiction arises from that loop. The same argument applies to a loop in the other direction, giving a second condition, and on a square cell the two conditions are the same condition because the two directions are alike.

There is nothing in that requiring the pattern to be a grid, and nothing requiring the creases to be evenly spaced. It applies to any drawing on any torus and it costs an addition.

The physical version #

A toroidal map is not a thing anybody can make, and it is worth saying why, since the essay is otherwise about an object with no physical realisation.

A rectangle of paper with both pairs of edges joined would have to be a doughnut, and a flat rectangle cannot be bent into a doughnut without stretching — the outside of the ring has to be longer than the inside, and paper does not do that.

The cylinder is a different matter. Joining one pair of a map’s edges gives a tube, tubes are easy to make, and the map-folding problem on a tube is a real question about a real object.

So of the two glued versions, one is physical and one is not, and the parity applies to both. That is a fair description of a great deal of this collection’s recent work: the cylinder is the object and the torus is the control.

What the strip’s answer suggests #

The one-dimensional case has been solved and its answer is instructive about what the glued question is like.

Folding a strip of $n$ stamps is counting the ways a sequence can be folded onto itself. The counts are known, they grow roughly like $n!$ divided by something, and no closed form exists. Joining the strip into a ring changes the object: the ends are now adjacent, the count is of cyclic arrangements, and the sequence is different.

The important structural change is not the count. It is that a ring’s foldings have no outermost layer, so two arrangements differing by a rotation of the layer stack are the same folding. That collapses the count by roughly a factor of the number of layers, and it means an enumeration has to identify equivalent arrangements rather than simply listing them.

The two-dimensional glued problem inherits exactly that difficulty and adds the two-dimensional one on top. Which is a reasonable prediction of why nobody has done it.

Where the hardness of the original problem might live #

The point of varying the sheet is diagnostic, so it is worth saying what the diagnosis might be.

The map-folding problem has three parts: choose an assignment, choose a layer order, and check that no two panels pass through each other. The first is a search over $2^E$ possibilities constrained locally; the second is a search over orderings constrained globally; the third is a geometric condition coupling them.

Gluing the sheet changes the first part hardly at all — the vertices are the same and the letter counts fall a little. It changes the second a great deal, by removing the least element the enumeration is built on. It leaves the third alone.

So if the glued problem turns out to be much harder, the difficulty is in the ordering. If it turns out to be about the same, the difficulty is in the assignment or the interaction.

Nobody knows which, because the glued problem has not been enumerated. What is established is that the question is well posed for half the sizes and vacuous for the other half, which is a start.

What the enumeration loses #

For the even sizes, where a folded state exists, the counting machinery does not simply carry over.

Enumerating the foldings of an ordinary map works outward from the bottom: find the panel with nothing below it, then the one above that, and so on. The bottom panel exists because the paper has an edge, and the bottom of a stack turns out to live at the rim.

A torus has no rim. The layer order has no least element, and what replaces which panel is at the bottom is in which direction do the layers climb — a question with an answer, and not the question the enumeration knows how to ask.

So the glued problem is not the old problem on a new object. It is a different problem: the thing being counted is not a stack from a bottom panel upward but an arrangement that repeats, and the collection has no enumeration for that.

What can be said #

Three things, all of them about the parts that do survive.

The parity condition. Odd sizes have no folded state, computed from the drawing in one addition, both directions independently.

The letterings. The assignment half of the problem — which creases are mountains — can be searched on a glued sheet, and is. A two-period grid cell settles in six nodes and has consistent letterings.

The vertex conditions. Unchanged, because the vertices are unchanged. Every one of them is a degree-four grid vertex with three of one letter and one of the other, exactly as on a flat map.

What does not survive is the count, which is the whole point of the original problem.

Why this is worth asking anyway #

Not because anybody folds a toroidal map, which nobody does.

Because the original problem’s difficulty has never been located. It is known to be hard and it is not known which part is hard — the assignment, the ordering, the interaction, or the sheer size of the search space. Varying the sheet is one of very few ways to take the problem apart, since it changes exactly one thing and leaves the drawing alone.

And it produces a fact worth having: half the instances of the glued problem are refused by a parity that the original problem does not have. That is a structural difference between the two, arrived at without solving either.

The strip, and the ring of stamps #

There is a one-dimensional version of the same move and it has a literature.

A strip of $n$ stamps folded flat is the one-dimensional map-folding problem, and its counts are known to reasonable sizes. Joining the strip’s two ends gives a ring of stamps, and the ring’s counts are a different sequence — one that has been studied under the name of folding a closed band.

The parity appears there too: a ring of stamps has to have an even number of them to fold, for exactly the reason a loop of paper does, and the odd rings are refused before any enumeration.

So the one-dimensional case has been asked and answered and the two-dimensional one has not, which is the same relationship the original problem has to its own strip.

The problem’s age, and why it survived #

The map-folding problem is old enough that its assumptions are invisible, and that is part of why the glued version had not been asked.

It is usually traced to the eighteenth century and it has been posed in essentially the same words ever since: given a rectangular map with creases along its lines, how many ways can it be folded flat. Every word of that is about a rectangle, and a rectangle has an edge.

There is nothing wrong with the problem. It is exactly stated and it is about the object anybody would ask about. What is worth noticing is that its hardness has been attributed to the size of the search space for three centuries, and the search space is defined by an enumeration that assumes an outermost layer — so nobody has separated the difficulty of the counting from the difficulty of the object.

Varying the sheet is one of the few available ways to make that separation, and it becomes available only when there is a way to say which boundary points are the same point. That is a small piece of machinery and it did not exist here until it was built for a different reason entirely.

Two conditions, not one #

On a square cell the two directions are alike and the two parity conditions coincide, which makes the result look simpler than it is.

Take a cell three squares across and two up. The horizontal loop crosses three creases and the vertical crosses two. So the sheet is refused, and it is refused by the horizontal condition alone.

Glue only the top and bottom edges, leaving the left and right as rim: the resulting cylinder’s loop crosses two, which is even, and that cylinder folds.

So a rectangle can be foldable as one cylinder, unfoldable as the other, and unfoldable as a torus, all from one drawing. The number of conditions is the number of loops that cannot be shrunk, and a torus has two.

That is worth having because it is the general form. A square cell is the special case where the two conditions agree, and reading the result off a square cell alone gives odd sizes fail, which is true and is a coincidence of the shape.

What a folded toroidal map would look like #

It is worth trying to picture the object, since it cannot be made.

Four panels of a two-period cell, stacked. Each panel is a unit square. The stack has no bottom and no top: walking upward through the layers, the fifth layer is the first again, one cell over in the paper.

So the folded object is a stack of infinitely many squares, periodic, with the paper spiralling through it. That is the same picture a glued corrugation gives, and it is why the layer order has a direction of climb rather than a bottom.

Counting such objects means counting the arrangements up to that shift, which is why the enumeration has to be rebuilt rather than adapted. An enumeration that lists stacks from a bottom would list each arrangement once per layer, and dividing out afterwards is only correct if every arrangement has the same number of layers, which they do not.

An honest accounting of what was measured #

The essay makes one negative claim and several observations, and it is worth separating them by how well supported each is.

Measured: grid cells at one, two, three, four and six periods, glued across, along and both ways. Odd cells are refused by two computations that share no code — a count of creases crossed by a swept family of paths, and a comparison of the folded motions of two identified panels. They agree at every size.

Measured: the letter search on the even cells. A two-period cell settles in six nodes with a consistent lettering; a four-period cell in eighteen.

Not measured: the number of folded states of any glued cell. No enumeration exists that works without a least element.

Not measured: whether the glued problem is harder than the original. That would need the enumeration.

Argued but not measured: that the difficulty of the original problem could be located by comparing the two. That is a reason to want the enumeration rather than a result.

The reason for laying that out is that a phrase like the map-folding problem on a torus invites the reading that the problem has been solved there, and it has not been posed there in any form that could be solved.

The vocabulary, tidied #

Three terms get used interchangeably in this area and they are not the same.

Stamp folding is the one-dimensional problem: a strip of stamps, folded along the lines between them.

Map folding is the two-dimensional problem: a rectangular grid, folded along all its lines.

Simple folding is a restriction on the moves rather than on the object — folds made all the way through the stack, one at a time — and it is a different question from both, with its own literature and its own answers.

The glued versions of the first two are what this essay is about. There is a glued version of the third and it is worth a moment: a simple fold on a sheet with no edge has nowhere to start, since a simple fold is defined by a line and a side, and a line on a torus does not separate it into two sides. That is a genuinely different situation and nothing here addresses it.

What is left open #

The count on the even sizes. A two-period glued grid has four panels and an order with no bottom; how many arrangements of those four panels are valid folded states is a question this collection cannot currently answer, because every enumeration it has starts from a least element.

Writing one that does not would mean deciding what to count. Two arrangements that differ by which panel is called the bottom are the same folded state on a torus, since there is no bottom; so the count is of cyclic arrangements rather than linear ones, and the machinery would have to be rebuilt round that.

It is recorded as owed. What is done here is the parity, which halves the instances, and the observation that the remaining half is a different problem rather than a smaller one.