Pattern · craft · the program that makes the cloth

Two Threads That Never Disagree

A weaving draft is not a picture of cloth. It is the program that makes it, written down two centuries before anybody had a word for a program. And the loom it runs on has a hard limit that turns out to be an exact statement about information: a pattern needs precisely as many shafts as its cloth has different columns, and not one fewer.

Below is a loom. Drive it, and cloth appears. Or draw the cloth you want and watch the loom that makes it assemble itself around your drawing. Those two directions are the same theorem, read forwards and backwards.

What the loom actually stores

A hand loom holds the warp under tension, a few hundred to a few thousand parallel threads called ends. Each end passes through the eye of a wire heddle, and the heddles are hung on frames called shafts. Press a treadle and it lifts some shafts; the ends on those shafts rise, the rest stay down, and the gap that opens between them is the shed. Throw the shuttle through the shed and you have laid one pick of weft. Change treadle, throw again. That is the entire machine.

So the cloth is a grid of yes and no. Write it as a matrix D with one row per pick and one column per end, where D[i][j] = 1 means end j rode over the weft on pick i. Weavers have drawn exactly this grid for centuries and call it the drawdown.

Here is the thing worth noticing. The loom does not contain the drawdown. It cannot. It contains three much smaller objects:

A four shaft loom weaving a metre of cloth at forty picks to the centimetre executes that line about three hundred thousand times, from a threading of a few hundred numbers, a tie-up of twenty-four bits, and a treadling you can hum. The cloth is the output. The draft is the source.

Two threads that never disagree

Now ask the question a weaver asks in a shop, holding a pattern book and looking at the loom they actually own: can I weave this on four shafts?

The answer is exact, and it is short.

One direction is almost too easy to notice. If end j and end j' are threaded on the same shaft, then t[j] = t[j'], so U[t[j]][r[i]] and U[t[j']][r[i]] are the same number for every pick i. Two ends on one shaft rise together and fall together, always, with no exception and no way around it. Their columns in the cloth are identical. The shaft count therefore cannot be smaller than the number of columns that genuinely differ.

The other direction is the useful one, and it is constructive: given any cloth at all, sort the ends into groups that have identical columns and hang each group on its own shaft; sort the picks into groups with identical rows and give each group its own treadle. The tie-up is then forced, every one of its cells read straight off the cloth, and it reproduces the cloth exactly. Nothing is chosen and nothing is lost. That is what the instrument above is doing every time you draw in the lower left panel: it is factoring your drawing back into the loom that makes it.

So a shaft is not a piece of hardware. It is an equivalence class. It is precisely a maximal set of warp threads that never disagree with one another anywhere in the whole cloth. The loom is a physical realisation of a quotient by that relation, and the number of shafts you need is the size of the quotient.

We checked this the blunt way, which is the only way worth trusting. For several small loom sizes the verifier enumerates every threading, every tie-up and every treadling the loom admits, collects the complete set of cloths it can physically make, and compares that set against the set the theorem predicts. On a four pick by four end cloth with three shafts and three treadles the loom can make 12,040 of the 65,536 possible cloths; the theorem predicts the same 12,040, with zero disagreements. Five such exhaustive sweeps are in the verifier, and the proof itself is machine-checked in Lean for all sizes at once.

Who got here first

None of the above is new, and the honest thing is to say who had it, because we went looking and found them.

The flattest statement we found is Ralph Griswold's, in a note written for weavers at the University of Arizona in 2000:

The number of treadles required is the number of different row patterns. The number of shafts required is the number of different column patterns.

Ralph E. Griswold, "From Drawdown to Draft: A Programmer's View" (2000, rev. 2004).¹

He gives a program that computes it, and states the corollary that falls straight out of it: "You can rearrange the rows and columns of a drawdown or delete duplicates without affecting the number of treadles and shafts required."

Before that came the algebra. Janice Lourie, at IBM, put the problem in front of the ACM in 1969, in a paper whose abstract states it in almost the words this page uses:

This paper presents an algebraic solution to the problem: given a diagrammatic representation of a woven design (weave), determine (1) the size and type of loom patterning mechanism necessary to produce it; (2) the initial conditions of this loom, i.e., the way the threads are connected to the patterning mechanism; and (3) the dynamic control information to this mechanism.

Janice R. Lourie, "Loom-constrained designs: an algebraic solution," Proc. ACM National Conference (1969), 185-192.²

We could not obtain that paper. It is behind a paywall with no open copy anywhere, and the abstract above comes from a bibliographic index rather than from the publisher. So we can tell you Lourie asked the question in 1969 and we cannot tell you what she proved.

The statement in the exact form used here is Shelley Rasmussen's, in the Electronic Journal of Combinatorics in 2008, and she says it more compactly than we have:

In general, we will call a fabric structure a k-harness design if k is the minimum number of harnesses required to weave it. A basic block generating a k-harness design has exactly k distinct columns.

All warp threads corresponding to the same column coloring are threaded through the same harness; they rise and fall together as a unit, as the harness rises and falls.

Shelley L. Rasmussen, "On 3-Harness Weaving," Electronic Journal of Combinatorics 15 (2008), #R1, which attributes the algebraic formulation to Lourie 1969.³

J. A. Hoskins published "Factoring binary matrices: a weaver's approach" in 1982, and that title alone tells you the framing was standard by then. And the weaving software has shipped it for decades. From the WeavePoint manual, under Reanalyze Shafts/Treadles:

Use these commands to reanalyze the pattern (fabric). The threading or treadling/tie-up will be entirely reconstructed, using as few shafts or treadles as possible. These commands are useful to check if a pattern can be woven with less shafts or treadles.

WeavePoint 8 User's Guide, p. 72.⁴

So this page is not reporting a discovery, and if you weave, none of it will have surprised you, because the practical version is what you already do when you look at a draft and count how many different columns are in it. What the page adds is the thing made operable in both directions, a proof that a machine has checked rather than a person having read, and the arithmetic in the second half.

Order is cheap, noise is expensive

Read the theorem again as a statement about information and it says something a weaver already knows in the hands. The number of shafts is not a measure of how big your pattern is, or how beautiful, or how fine. It is a measure of how much your pattern repeats itself down the warp. Two ends cost one shaft between them if their entire life histories agree.

Here is what that costs, measured, on the same 32 by 32 patch of cloth:

Stripes are almost free: two shafts, and only one treadle, because every pick of a striped cloth is identical to every other pick and one treadle pressed over and over will do. Random noise is the worst case there is, and it is the worst case exactly because no two of its threads ever agree. A forty end square of noise needs forty shafts. There is no loom in the world with forty shafts and a warp of only forty threads; you have built a machine with one moving part per thread, which is to say you have stopped compressing and started listing.

Type your own name into the instrument above and watch the number climb. Then pull the shaft slider down to four and watch what a real loom would have made of it.

The loom with no compression left

That last thought is not a metaphor. It is a machine, and it was built.

The Jacquard attachment, demonstrated in Lyon at the start of the nineteenth century, throws away shafts entirely. Instead of frames each carrying many heddles, it gives every warp end its own hook, and a punched card decides, hole by hole, which hooks rise for the next pick. In the language above, S = n: one shaft per end, and the tie-up becomes the identity. The theorem then says the loom can weave anything, because the condition "at most n distinct columns" is satisfied by every cloth that exists.

Which is the same as saying the Jacquard card deck is not a program at all in the compressed sense. It is the raw drawdown, one card per pick, holes where the cloth has ones. The shaft loom stores a pattern; the Jacquard stores a picture. Everything you gain in freedom you pay for in cards, which is why a Jacquard portrait needs its cards counted in the tens of thousands while a coverlet on four shafts needs a threading you can write on the back of an envelope.

Drafting, then, is data compression, practised as a trade for centuries before anyone wrote down what compression was. And the weaver's rule of thumb, that a pattern with many independent stripes is "hard on shafts", is a statement about the entropy of a binary matrix.

The portrait, and a number worth not repeating

In 1839 the Lyon firm of Didier, Petit et Cie had Michel-Marie Carquillat weave a portrait of Jacquard himself in silk, after a painting by Claude Bonnefond. It is the standard illustration of the point, and the figure attached to it is always 24,000 punched cards. We tried to source that number and the result is worth reporting. The Computer History Museum states it, and the Science History Institute states it twice in editorial prose, hedged both times. Meanwhile the catalogue records of the Metropolitan Museum, the Science Museum Group, the Smithsonian and the Henry Ford, all four of which hold an example, give no card count at all. Nothing contradicts 24,000 and we have no reason to doubt it. But if you have seen the figure repeated, you have probably not seen it sourced.⁵

Charles Babbage owned one, and used it as a teaching aid. His own account of showing it to Prince Albert and the Duke of Wellington in 1842:

'Oh! that engraving?' remarked the Duke of Wellington. 'No!' said Prince Albert to the Duke; 'it is not an engraving.'

The portrait of Jacquard was, in fact, a sheet of woven silk, framed and glazed, but looking so perfectly like an engraving, that it had been mistaken for such by two members of the Royal Academy.

Charles Babbage, Passages from the Life of a Philosopher (1864), ch. XI.⁶

He had gone to Lyon in 1840 specifically to watch the loom that made it: "I passed many hours in watching its progress." And it was to explain his own machine that he kept it hanging in the drawing room, which is the context for the most quoted sentence in the history of computing, written by his translator three years later:

We may say most aptly that the Analytical Engine weaves algebraical patterns just as the Jacquard-loom weaves flowers and leaves.

Ada Lovelace, Note A to her translation of Menabrea's "Sketch of the Analytical Engine," Scientific Memoirs vol. 3 (1843), p. 696. The italics are hers, and only on the first half.⁷

That line is usually read as a poet's flourish about computing. Read it the other way round for once. In 1843 the loom was the machine everyone had already agreed ran on a program, because you could hold the program in your hands and it was made of card. Lovelace was not lending the engine some borrowed romance from the textile trade. She was explaining an unbuilt machine by pointing at the only working one there was.

The satin that cannot exist

Now a second, sharper fact, and one where the arithmetic reaches somewhere unexpected.

A satin is the weave that gives silk and sateen their surface: the interlacing points are scattered so thinly and so evenly that the eye cannot find a line in them, and the cloth reads as unbroken sheen. You build one on n ends by choosing a move number m and stepping the interlacing point m shafts further along on every pick. Two conditions have to hold. The move must be coprime to n, or the interlacings land on only some of the shafts and clump. And the move must not be 1 or n − 1, because either of those steps the point along by one each time and draws the diagonal line of a twill, which is the very thing a satin exists to avoid.

That is not our rule. It is the trade's, and three public-domain textile texts state it in three different vocabularies. Posselt calls the move number the counter, Watson calls it the step, move, or count, and Nisbet calls it the interval of selection. Watson's wording is the closest to the arithmetic:

From the example the following rule for the construction of regular sateens may be drawn:—Any number (with the exception of one, and a number that is one less than the number of threads in the repeat) may be counted which has no measure in common with the number of threads in the repeat of the weave.

William Watson, Textile Design and Colour, p. 18. (The scan checked here is the 1921 printing.)⁸

Turn the dial.

Set n = 4. The only numbers below 4 that share no factor with it are 1 and 3, and 3 is n − 1. Both are the twill. There is no regular four end satin. Set n = 6 and the same thing happens: the residues coprime to 6 are 1 and 5, which are again the two forbidden ones. Set n = 5 and suddenly there are two good moves, 2 and 3, and you get the classic satin of the silk trade. Seven gives four moves, eight gives two, and from then on they never run out again.

The weavers knew. They say it flatly, and they say it with the reason:

Irregular Sateen Weaves.—Regular sateens cannot be constructed on four and six threads, because no number can be counted which has not a measure in common with four and six.

Watson, Textile Design and Colour, p. 19.

The lowest satin that can be produced is found in the five-harness satin; after this the same can be made "regular" on any number of harness, with the exception of six. The four-leaf broken twill is also sometimes classified as a "satin," but against the rules of construction for these weaves, as on two successive picks the interwoven threads are next to each other.

E. A. Posselt, Technology of Textile Design (Philadelphia, 1888), p. 25.⁹

Posselt's objection is not an opinion, it is a measurement, and it is one we can run. His four-leaf weave interlaces in the order 1, 2, 4, 3; step through it and two of its consecutive picks do land on neighbouring shafts, exactly as he says. The six-end weave the trade uses instead, order 1, 3, 5, 2, 6, 4, printed identically by Posselt in 1888 and by Watson in 1921, never does. The dial shows you both when you set it to 4 or 6, and the verifier checks both claims. A textile author's stated reason from 1888, tested and standing.

So the impossible cases are exactly n = 1, 2, 3, 4 and 6. Everything else has a satin. The condition, stated properly, is that the residues coprime to n must include something other than 1 and n − 1, which is to say φ(n) > 2 in Euler's notation, which is to say that the only invertible numbers mod n are not just ±1.

The crystal that can

That set, {1, 2, 3, 4, 6}, has been sitting in a different drawer of this site for months.

It is the crystallographic restriction: the complete list of rotational symmetries a repeating pattern is allowed to have. Wallpaper, a tiled floor, the atoms in a crystal, all of them can turn onto themselves by a half turn, a third, a quarter or a sixth, and by nothing else. Never a fifth. The reason is that a rotation carrying a lattice to itself is an integer matrix in a lattice basis, so its trace is a whole number, and the trace of a rotation by 2π/n is 2·cos(2π/n). That quantity lies in (−2, 2], so if it is a whole number it is one of −2, −1, 0, 1, 2, which pins n to 2, 3, 4, 6 or 1 and nothing else. Shechtman's forbidden fivefold spots won a Nobel prize precisely because they were on the wrong side of that list.

And that same condition, unwound, is φ(n) ≤ 2: the trace 2·cos(2π/n) is rational exactly when the only units mod n are ±1, which is exactly when the move numbers available to a satin weaver are only 1 and n − 1, which is exactly when there is no satin.

We are not claiming the two facts are the same fact, or that one causes the other. They are two different questions that both reduce to one arithmetic condition, and the reduction runs through different territory in each case: through the integrality of a trace on one side, and through the existence of a nontrivial unit on the other. What is true and checkable is that the two lists are the same list, and that at the bottom of each is the same sentence. The panel on the right of the dial is that bottom: it shows the units mod n, and both verdicts are read off the same row.

Is the connection new? We went looking, and what we found is better than a yes.

The arithmetic of satins is old. In November 1867 a twenty-five year old assistant astronomer at the Paris Observatory published a monograph on it, Application de l'arithmétique à la construction de l'armure des satins réguliers. It was his first publication, and his name was Édouard Lucas, years before the Lucas sequences and the primality test that carry it. A number theorist's career opens on the shop floor, prompted, he says on his first page, by a "remarkable and entirely original" paper by a weaving teacher in Amiens.¹⁰

And Lucas has the whole thing. He excludes the two bad moves for the reason we gave: "Lorsque a = 1 ou a = p − 1, les pions se trouvent rangés en diagonale, et la figure formée représente l'armure de la toile." He states an impossibility in words: "il n'existe pas de satin de module 2 ni de module 4." And he has a section headed Nombre de satins distincts de module donné in which, for a prime number of ends, he counts them: "nous comptons p − 3 ... satins en supprimant les cas a = 1 et a = p − 1 qui donnent l'armure de la toile." For a prime, p − 3 is exactly φ(p) − 2. He had the count. He wrote it in the only notation that could possibly have been simpler.

So here is the narrow strip of ground left, stated as narrowly as we can make it. We found no source, textile or mathematical, that names Euler's totient in connection with satin move numbers, none that gives the count for a composite number of ends, and none at all that connects any of this to the crystallographic restriction. That is a negative result from a search, not a proof of absence, and we will name the two places it could still be hiding: the rest of Lucas's own text, which we could read only through an unreliable optical index, and Grünbaum and Shephard's 1980 paper Satins and twills, which is paywalled and which we never read at all.¹¹ If it is in either, it is theirs.

What the theorem does not know

A draft can pass the shaft test perfectly and still not be cloth. Three things the arithmetic cannot see, all of which the instrument measures anyway, and none of which it pretends to settle:

Floats. A thread that passes over several others without interlacing is a float. Long floats are how satin gets its sheen, and also how a sleeve catches on a door handle and pulls a loop out of your cloth. The instrument reports the longest float it finds so you can watch the trade happening. We wanted to tell you the number at which a float becomes a problem, went looking for it in both the craft literature and the textile engineering literature, and did not find one. The craft sources treat it as a judgement rather than a limit, and the best answer we can honestly give you is the one a teacher gives: decide how long you are willing to let your floats be. The engineering literature agrees on the direction, that longer floats abrade faster and destabilise the cloth, and names no maximum. So there is no number here, because we could not source one.

Hanging together. If a warp end never goes under the weft anywhere in the repeat, it is not woven in at all, it is simply lying on the surface. The same for a pick. A draft that does this produces two separate objects, a cloth and a heap of loose threads. The theorem is perfectly happy with it. The instrument flags it.

Which way the shed opens. Everything above assumes a rising shed, where a tied shaft lifts. Counterbalance looms sink instead, and a draft written for one is the complement of the draft for the other. It changes not one word of the mathematics, and it will absolutely ruin your afternoon if you get it wrong.

There is also a real limit on the other side of the theorem, and it is worth naming because the instrument runs into it. Knowing the minimum number of shafts is easy. Finding the best pattern you can weave when you have fewer shafts than that is a different problem: it is a clustering problem, choosing which threads to force into agreement, and choosing optimally is computationally hard in general. The shaft slider does what a weaver does, which is repeated local improvement from several starting points, and it reports how many cells of your cloth came out wrong. When it says zero, the fit is exact and that is a proof. When it says anything else, it is the best it found, not the best there is, and the page says so on the panel.