Folding a strip into thirds

Halving a strip of paper is trivial: bring the ends together. Dividing it into thirds is not, and the difference between the two is the whole content of this essay.

The method is Shuzo Fujimoto’s and it is not a construction. It does not produce the exact point at any stage; it produces a sequence of points converging on it, and stops when the error is beneath what anybody can see. Whether that counts as dividing the paper into thirds is a question worth taking seriously, and the answer turns out to be yes for a reason that has nothing to do with paper.

Why it cannot be constructed #

The seven axioms list every way a single fold can be specified by alignments of existing points and lines, and folding a strip into thirds is not among the things they reach in one step from an unmarked strip.

That is not the same as saying a third is inconstructible. A third is a perfectly ordinary rational number and the axioms reach every rational division given enough folds — Haga’s theorem gets a third in two folds from a square, using a corner and an edge as references. What the strip lacks is references. An unmarked strip has two ends and nothing else, and the only alignment available is end-to-end, which halves.

So the situation is: with a square and its corners there are constructions, and with a bare strip there are not. Fujimoto’s method is what one does with a bare strip, and it turns out to be more interesting than the construction.

The map #

Mark a guess somewhere near a third of the way along. Now fold the right-hand piece in half: its midpoint is a new mark, at

$$x \mapsto \frac{1 + x}{2}.$$

Fold the left-hand piece of that in half — meaning the piece from the near end to the new mark — and the mark moves to

$$x \mapsto \frac{x}{2}.$$

Two folds, composed: $x \mapsto (1 + x)/4$. Its fixed point is $x = 1/3$, and its derivative is $1/4$, so the distance to the fixed point is quartered every two folds and halved every one.

That is the entire method, and everything else is bookkeeping about which piece to halve.

The word #

The bookkeeping generalises, and it generalises to something with a pleasing amount of arithmetic in it.

Each fold is one of two maps: halve toward the near end, $x \mapsto x/2$, or halve toward the far end, $x \mapsto (1+x)/2$. Compose a word of $k$ such folds with digits $b_1, \dots, b_k$ and the result is

$$x \mapsto \frac{x + m}{2^k}, \qquad m = \sum_j b_j 2^{\,j-1},$$

whose fixed point is $m/(2^k - 1)$.

To divide into $n$ parts, then, find the smallest $k$ for which $n$ divides $2^k - 1$, set $m = (2^k - 1)/n$, and read the word off $m$ in binary, least significant digit first — because the least significant digit is the fold made first.

For thirds: $k = 2$, $m = 1$, word far, near. For fifths: $k = 4$, $m = 3$, word far, far, near, near. For sevenths: $k = 3$, $m = 1$. For ninths: $k = 6$, $m = 7$. Even denominators do not appear because they need no method — halving alone gets them, which is why the powers of two are the grid sizes everybody uses.

What each fold is aiming at #

Here is the part that is easy to get wrong, and the figure is drawn the way it is in order to make it visible.

A single fold does not aim at $1/n$. It aims at wherever $1/n$ goes under that fold. Halving the far piece takes the true third to two thirds, so after the first fold the mark should be near two thirds, and it is; the second fold takes two thirds back to a third.

So the mark tours the strip and returns. Reading the method as “each fold gets closer to the third” is wrong on every fold but the last of each round, and it is a natural misreading, because the error does get smaller every fold — measured against the moving target rather than against the third.

The figure marks the moving target as well as the mark, with a solid rule where the fold really is aiming at $1/n$ and a dashed one where it is aiming at the third’s image. The generator asserts the halving against that orbit, to a part in $10^{12}$, and asserts that the orbit returns to $1/n$ after a full period. Both would fail loudly if the word were built in the wrong order — which it was, the first time, and the assertion is what caught it.

The word’s length is the order of two #

“The smallest $k$ for which $n$ divides $2^k - 1$” is a quantity with a name, and naming it settles which divisions are cheap.

That condition says $2^k \equiv 1 \pmod n$, so $k$ is the multiplicative order of 2 modulo $n$. It exists exactly when $n$ is odd, which is the arithmetic reason even denominators never appear: they are not coprime to two, and halving alone reaches them anyway.

The orders are not monotone in $n$, and that is the surprise:

Sevenths take a shorter word than fifths. Fifteenths take four folds a round and elevenths take ten, so a division into fifteen parts is easier bookkeeping than one into eleven. The cost is set by how quickly two cycles modulo $n$, which has nothing to do with how large $n$ is — the worst cases are the primes for which two is a primitive root, where the word runs to $n - 1$.

And the word’s length is not the accuracy #

The important half is what the order does not control.

Every fold is a halving whatever the word says, so the error falls by a factor of two per fold regardless of $n$. Ten folds put the mark within a thousandth of the strip whether the target is a third or an eleventh.

So the order decides only how often the mark comes back to the neighbourhood of $1/n$ — every two folds for thirds, every ten for elevenths — and a folder who stops mid-word has a good approximation to some other point of the orbit rather than a poor approximation to $1/n$.

That is the practical rule the arithmetic gives: stop at a multiple of the order, and until then the mark is exactly where it should be and nowhere near where it is wanted.

Why the error halves exactly #

The contraction is not approximate and does not depend on how good the first guess was, which is the property that makes the method usable.

Each map is affine with slope $1/2$. An affine map with slope $s$ scales the distance between any two points by exactly $|s|$, and the true division is one of those two points. So

$$|x_j - t_j| = \frac{|x_0 - t_0|}{2^{\,j}}$$

with $t_j$ the orbit of the target. Six folds divide the error by sixty-four; ten folds by a thousand and twenty-four.

A first guess ten per cent of the strip out of place is therefore within a sixth of a millimetre after ten folds on a strip of a hundred millimetres, which is well below the width of a crease. That is what “exact enough” means here and it is why the method is not a compromise in practice.

What the method is worth on a square #

A strip is a convenient object for exposition and a rare one on a desk. What folders actually divide is a square, and there the method competes with constructions rather than replacing them.

Haga’s theorem gets a third of a side from a corner and an edge in two folds, exactly, and there are similar constructions for fifths and sevenths. They are shorter than a round of Fujimoto’s method and they are exact rather than convergent, so on a square with corners available they win.

Fujimoto’s method wins in three situations, and they are the ones that come up. When the paper is a long strip, as it is for a tessellation, there are no useful corners. When the division is into many parts — sixteenths, thirty-seconds — the constructions become long chains in which each step’s error feeds the next, while the iteration’s error keeps halving regardless. And when the denominator is awkward, the iteration needs only the binary expansion, while a construction needs somebody to have found one.

That third case is the interesting one. The method is uniform in $n$: the same procedure, with a different word. A collection of exact constructions is not uniform in anything, and each new denominator is a small research problem.

Which theorem was checked, and how #

The figure computes the word from $n$ rather than taking it as an argument, so a reader changing the denominator gets the right sequence of folds automatically, and there is no table of special cases to be wrong.

Three things are asserted before anything is drawn. The denominator must be odd and greater than one, since even denominators are plain halving and the method has nothing to say about them. There must be a $k$ within twenty-four for which $n$ divides $2^k - 1$; there always is for odd $n$, and the bound stops the search rather than expressing a doubt. And the orbit must return to $1/n$ after exactly $k$ folds, which is the check that the word and the fixed point agree.

Then the halving itself is asserted at every fold, not only at the end. That is the claim the essay makes and it is the one a subtly wrong implementation would break in the middle while still arriving somewhere plausible.

What the picture cannot show #

The figure draws marks on a line. A fold is not a mark; it is a crease, and a crease has a width and a position that depends on how the paper was held.

That matters here more than in most figures on this site, because the method’s whole appeal is that it defeats accumulated error — and the error it defeats is the error in the guess, not the error in the folding. Each fold introduces its own small inaccuracy, and those do not halve. They accumulate like any other measurement error, at a rate set by how carefully somebody works.

The honest statement is therefore: the method removes the error in the initial estimate geometrically, and leaves the per-fold error to accumulate arithmetically. After enough folds the second dominates, and doing more folds stops helping. Where that crossover sits depends on the folder, and it is usually around six or seven.

The idealisation underneath #

Zero thickness, and this time it is the reason the crossover exists at all.

A real strip folded in half has an inner layer and an outer layer, and the outer one has further to go — the crease has a radius, and the radius means the two halves are not the same length. Bringing the ends together therefore does not put the crease exactly at the midpoint; it puts it a little to one side, by an amount proportional to the paper’s thickness.

That bias is systematic rather than random, which is worse. It does not average out over folds, and it is the reason a strip halved eight times is visibly not in equal sixteenths. Fujimoto’s method inherits the bias, and it is why folders make the last round of folds by eye against the previous crease rather than by bringing the ends together.

Folding the whole strip at once #

There is a variant that folders use and that changes the arithmetic slightly, and it is worth describing because it explains why the method feels faster in the hand than on paper.

Instead of marking one point and refining it, mark the guess and then fold the whole strip into $n$ parts using it — for thirds, fold at the guess, then fold the remainder in half against the first crease. Every crease so made is wrong by an amount proportional to the original error, and every one of them is corrected at the next round.

The advantage is that the strip ends up creased everywhere it needs to be, rather than carrying one accurate mark that then has to be propagated. The disadvantage is that the intermediate creases are visible in the finished piece — a Fujimoto grid has more creases in it than the design requires, and the extra ones are the working.

For a grid-based design the extra creases are usually harmless, since the grid lines are all going to be folded anyway. For a display piece they are not, and this is why some folders make the divisions on a scrap strip and transfer them.

The same reasoning explains a preference that looks like superstition. Grids in this tradition are powers of two — sixteen, thirty-two, sixty-four — far more often than they are twenty-fours or forty-eights, and the reason is that a power of two needs no method at all. Every division is a halving, every halving is an alignment of two edges, and nothing has to converge. A grid of twenty-fourths needs a third first, and the third is where whatever error there is enters and stays.

The surprising connection #

The method is a fixed-point iteration, and fixed-point iteration is the standard way to solve equations that cannot be solved directly. Newton’s method is one; so is the algorithm inside a calculator’s square-root key.

What makes this instance unusual is that the iteration is exactly linear. Most fixed-point methods have a contraction factor that varies with position and that has to be estimated; this one is exactly one half everywhere, forever, because a fold is a reflection and a reflection is affine. There is no convergence analysis to do — the answer is $2^{-j}$ and it is not asymptotic.

There is a second connection, to a place with no paper at all. The word of halvings is the binary expansion of $m/(2^k-1)$, which is to say the eventually-periodic binary expansion of $1/n$. The period $k$ is the multiplicative order of 2 modulo $n$: two for a third, four for a fifth, three for a seventh, six for a ninth. So the number of folds in a round of Fujimoto’s method is a fact of elementary number theory, and a folder who notices that sevenths take three folds per round and fifths take four has noticed that $2^3 \equiv 1 \pmod 7$.

What convergence is worth against exactness #

There is a real philosophical question underneath the practice, and it is worth a paragraph rather than a shrug.

An exact construction produces a point that is the third. Fujimoto’s method produces a sequence of points none of which is. On any ordinary reading of “divide this strip into three equal parts”, the construction does it and the method does not.

The reply is that the distinction has no content on paper. A crease is a physical object about a tenth of a millimetre wide, and two marks closer together than that are the same mark. After ten folds the iteration’s error is far below that threshold, so the method produces a crease that is the third to within the only resolution the medium has. The exact construction produces a crease that is the third to within the same resolution, because it too is made by hand.

What survives the reply is a difference in kind of guarantee. The construction’s error is bounded by the folder’s care; the iteration’s error is bounded by the folder’s care plus a term that vanishes. In a subject where the idealisations are the interesting part, that is a distinction worth keeping even after conceding that it makes no difference to the finished piece.

Who found it, and when #

Shuzo Fujimoto developed the method in Japan in the 1970s, in the course of the tessellation work he is better known for; it appears in his self-published books of the late 1970s and spread through the folding community before it was written down anywhere formal. The technique is often called Fujimoto approximation, which undersells it — the convergence is exact, and only the stopping is approximate.

The underlying arithmetic is much older and belongs to nobody in particular. That the binary expansion of $1/n$ has period equal to the order of 2 modulo $n$ is standard, and predates paper folding as a subject of study by a long way.

The ladder from here #

This rung answers what to do when no reference exists. The rung below it, dividing without measuring, answers what to do when references do exist, and gets exact answers in a fixed number of folds.

Above, the ladder leaves rationals behind entirely. A third is easy in the sense that it is rational; the interesting divisions are the ones that are not, and those need the axiom that solves a cubic rather than an iteration.