The window that names a cloth is half its repeat

The manuals’ derivations — reversing a draft, turning it a quarter, counterchanging it — cut the 426 cloths of the four-by-four repeat into 157 families, and a cloth’s derivation class is its census of small patches found a way to name a family without searching for the operations that join it. Slide a three-by-three window over every position of the repeat, count the patterns it sees, and take the counts up to the turnings and reflections of the square and a counterchange. Two four-by-four cloths derive into each other exactly when those counts agree. Nothing coarser does it: a census of two-by-two windows confuses 49 of the 157 families.

That essay ended on the obvious worry. Three is one less than four, and a three-by-three window on a four-by-four repeat sees more than half the cloth at once. Whether three is still enough when the repeat grows is a question about every larger cloth a weaver designs, and it has a definite answer for every repeat small enough to walk.

The answer is neither of the two guesses. The window does grow, and it grows as half the repeat.

Two easy answers, and why neither is safe #

The first easy answer is that three stays enough. A three-by-three window sees nine intersections, which is a great deal of arrangement — every float of up to three, every turn of a twill line, every crossing of a basket — and a weaver reading a swatch would expect to recognise a cloth from far less. If it were true, derivation would be a genuinely local relation: two cloths would be relatives exactly when their small neighbourhoods matched, at any size.

The second easy answer is that the window is always one less than the repeat, which is what happened at four by four. If that were true the census would be barely better than the draft itself. A window of seven on an eight-end cloth is the whole cloth with one thread missing, and naming a family by it would be a formality.

Both answers are tempting because the four-by-four repeat cannot tell them apart: three is both a small constant and one less than four. The only way to separate them is a larger repeat, and the repeats that can be walked whole are larger in one direction or both.

Eleven repeats, walked whole #

A repeat of three picks by three ends has 512 drafts; one of four picks by seven ends has 268 million. The walk takes eleven shapes between those — three picks by three to eight ends, four picks by four to seven ends, and five by five — and keeps every draft in which every end and every pick interlaces, so that no thread lies loose on one face. Two drafts that are one cloth started elsewhere or seen from the back are one cloth, as how many cloths are there counted them.

Each shape has its own group of derivations, and the group is stated rather than borrowed. On every shape the slides, the reversal of the ends, the reversal of the picks and the counterchange are allowed; on a square repeat the quarter turn is allowed as well, since it keeps the shape. A rectangular repeat cannot be turned a quarter without becoming a different shape, so that operation is not in its group. These are the same operations whose symmetries the seventeen groups a draft can have sorted; here they act between drafts rather than on one. The families are the orbits of that group, and each is kept once, at its least writing.

The orbits run from 3 at three by three to 447,756 at four by seven. At four by four the walk gives back the 157 found by closing the manuals’ operations as functions, and on three smaller shapes its counts agree with a second count made by building every orbit explicitly from the generators — two routes to the same partition, neither borrowing the other’s arithmetic.

Then, for every shape and every window of two, three and four intersections square that fits inside it, the census of every family is taken and the families are sorted by census. A window names every family on a shape when no two families share a census there. The grid above is the whole of the result, and it has a pattern in it that is not about three at all.

Three is enough at five ends #

Along the four-pick row and the five-by-five square, three holds. At four picks by five ends there are 2,875 families and a census of three-by-three windows tells every one of them from every other. At five by five there are 45,077 families, and three-by-three windows still name every one. A window of nine intersections reads a cloth of twenty-five exactly, up to derivation.

That alone rules out the second easy answer. Five by five is the first square repeat where one less than the repeat is four, and four is not needed: a window three-fifths of the way across names every cloth the repeat can hold.

It also shows how little the smaller window can do. A two-by-two census on five by five confuses 42,480 of the 45,077 families, in 6,121 groups. Two-by-two windows see each intersection with its three neighbours and nothing further, and nearly every five-by-five cloth has a stranger elsewhere in the catalogue built from the same little squares in the same numbers. Three-by-three windows see each intersection with its eight neighbours, and on five by five that is enough.

Three fails at six #

Along the three-pick row, three holds at four and five ends and fails at six. Three picks by six ends has 365 families, and twelve of them fall into six pairs that share a three-by-three census. At four picks by six ends the same window confuses 204 of 36,380 families, in 102 pairs.

The pair is worth looking at because it is so slight. The two cloths differ in one end, and in that end only by a mark moved one pick down — the same end slid by a pick. The three-by-three windows that hold the moved end are not the same windows at the same places; they are the same windows at different places, so that the census, which counts windows without remembering where they were, cannot see the move.

That is the failure mode in its general form, and it is the reason a census is weaker than a draft. A census is a bag of views, and a bag loses the order the views came in. It recovers the order only when the views overlap each other enough that there is just one way to lay them end to end, and at six ends three-thread views do not always overlap enough.

The cloths confused are a mark apart #

How different are the cloths a census confuses? Not very, and that is itself informative.

Of the 102 confused classes at four by six, 67 are pairs of cloths two intersections apart, which is one mark moved one place along its end; 30 are four apart and 5 are six apart. None is a gross difference. A census of three-by-three windows never mistakes a twill for a basket or a satin for a hopsack. What it misses is a small displacement inside a cloth that is otherwise the same, of exactly the kind a mispick or a mis-entered end produces — a fault that leaves every neighbourhood looking ordinary and moves one neighbourhood to the wrong place.

So the confusion is not random noise in the census. It is a specific blindness: a census cannot see a local change that the cloth’s own repetition has a copy of elsewhere.

The rule is half the repeat #

Laid out against the number of ends, the failures fall in one place.

A window of two fails from four ends. A window of three fails from six. A window of four holds at six and slips at seven. In every row the first failure comes where the repeat is twice as wide as the window, and from there the share confused climbs steeply — the three-by-three window confuses 3 per cent of the three-pick families at six ends, 13 at seven and 26 at eight.

Stated as a rule over everything walked: on every one of the eleven shapes, a window no wider than half the ends confuses some families. There is no exception to that half of the rule anywhere in the grid. And a window wider than half the ends names every family on every shape but one.

The rule has a reason that does not depend on weaving. On a repeat of n ends, two windows k ends wide can be laid side by side without sharing an end exactly when 2k is no more than n. A window no wider than half the repeat therefore allows the cloth to be read as two halves that never meet in any one view, and a census of such views cannot say which way round the halves are joined. A window wider than half the repeat overlaps every other window it could be paired with — by at least 2k − n ends — and the overlaps tie the views into a single arrangement.

At four by four a three-by-three window overlaps any other by at least two ends. At five by five, by at least one. And at five by five one end of overlap is enough.

One pair at seven ends breaks it #

One end of overlap is the knife-edge, and the grid has five shapes that sit on it: three by three with a window of two, three by five and four by five and five by five with a window of three, and four by seven with a window of four. Four of the five name every family. At four picks by seven ends one pair of the 447,756 families shares a census of four-by-four windows.

The pair is checked a second way, with no table and no symmetry applied: the four-by-four windows of the two drafts, read off as strings and sorted, are the same list, and the slow route that builds every writing of one cloth from its generators does not reach the other.

The mechanism is exact and can be read off the drawing. Two ends occur twice in each cloth — the stretch shaded — and both are ends that read the same after a slide of two picks, since each lifts on alternate picks. The moved end sits between the two copies. In the first cloth it reads one mark on the top pick; in the other, the same mark two picks lower. A window four ends wide that holds the moved end can hold one whole copy of the stretch beside it and only half of the other, and from inside such a window the first cloth’s view to the left of the moved end is indistinguishable from the second cloth’s view to its right, slid two picks.

So every window that sees the change sees it as a view the other cloth also has, just from the far side of the stretch. A window of five ends would hold the moved end with both copies whole and see the arrangement directly. A window of four cannot, and an overlap of a single end between windows is not enough to carry the order across a stretch that has a copy.

The assembler’s problem, in two dimensions #

That last sentence is a familiar one in a field with nothing to do with cloth.

A genome is sequenced by breaking it into short overlapping reads and putting them back together from their overlaps, and the work of Idury and Waterman in the 1990s, followed by the de Bruijn graph method of Pevzner, Tang and Waterman, made the central difficulty precise: reads determine a sequence only if no repeated stretch is long enough to hide which copy a read came from. A read that starts inside one copy of a repeat and ends inside it could have come from either, and if it does not reach past the repeat into unique sequence on both sides, the assembler cannot say how the copies are arranged.

The four-by-seven pair is that failure, in two dimensions and on a circle. The two-end stretch is the repeat; the windows are the reads; four ends is a read that cannot span the stretch and both its flanks. The half-repeat rule is the reason most cloths are safe, and the repeat inside a cloth is the reason a few are not. The assembler’s remedy is longer reads; the census’s is a wider window, and at four picks there is no wider square window to have.

The naming window is never a small piece #

The practical content of the rule is about scale. A complete census at four by four needed a window of nine intersections in sixteen, more than half the repeat by area.

The smallest share any shape reaches is 36 per cent, at five by five: a nine-intersection window on a twenty-five-intersection repeat. Everywhere else the naming window covers between 44 and 75 per cent of the repeat, and on four shapes no square window smaller than the repeat itself is complete, because the picks are too few for a window wider than half the ends.

So the hope that derivation is a local relation — that two cloths are relatives exactly when their small neighbourhoods match — survives only in a relative sense. A window wider than half the repeat in its longer direction is not a small neighbourhood. On a twelve-end cloth it would be seven ends wide. The census remains a different kind of test from a search over the derivation group — counting windows rather than trying operations — but it is not a reading of the cloth from fragments much smaller than the cloth.

That is a cleaner statement of what no cloth derives into more than three others found from the other side. Derivation is a small group acting on a large catalogue, and its orbits are almost all tiny; the census that tells those tiny orbits apart has to look at most of a repeat, because what separates two families is usually a single displaced mark, and only a view that spans the cloth can say where the mark belongs.

What a specification can carry #

A lifting plan says nothing without a threading, and a specification that names a cloth by measures rather than by its draft is only as good as the measures. The earlier census showed that a list of local counts can be a complete specification at four by four. The rule here says how large the counts must be on a larger cloth: windows wider than half the repeat in both directions, and a check that the cloth has no repeated stretch long enough to defeat them.

The second clause is not idle. The four-by-seven pair is a cloth of an ordinary kind — four plain-weave ends and three that lift on one pick in four, a small figure on a plain ground — and a specification by four-by-four windows would admit both members of the pair as the same cloth. A reader who wanted to know whether a swatch is derived from a reference has a usable rule of thumb for the ordinary case and a stated hazard for the case where a cloth repeats a stretch of itself.

And the census never confuses cloths that look unalike. Every confusion in the walk is between drafts a few intersections apart, so a specification by windows fails, when it fails, by admitting a near neighbour — the same kind of near neighbour that which weave hides a fault found the eye does not catch either.

How the walk was taken #

Each draft is a row of integers, one to a pick, an end being a bit of its pick’s row — the draft as a matrix, packed so that a slide along the ends is a rotation of bits. The walk keeps a draft only if it is the least writing of its family: every slide of every allowed symmetry is tried, and the draft is dropped at the first writing smaller than itself, so no family is ever built whole. A pruning step uses the fact that the top pick of a least writing can be no larger than any row’s least slid, reversed or counterchanged form; the full test is still made on everything the pruning keeps.

A window is a code of four, nine or sixteen bits, read at every position of the repeat; a census is the sorted list of a repeat’s window codes; and its name is the least such list over the shape’s symmetries, each applied to the codes through a table. A symmetry of the square moves windows about and turns their contents, and a census does not know where the repeat starts, so the symmetries can be applied to the windows instead of the draft.

Required of it: the 157 families at four by four, and the two-by-two classes the earlier census counted from strings; the orbit counts of three shapes again by building every orbit from its generators; every window no wider than half the ends confusing something; every wider window naming everything except the one pair at four by seven; that pair confirmed in different orbits by the slow route, with identical windows read as strings; and, at six by six, the first three-pick pair written twice down the picks, still in different families once the quarter turn is allowed and still sharing every three-by-three window.

What the walk cannot reach #

Square repeats stop at five by five. Six by six has 2^36 drafts — sixty-nine thousand million — and is not walked. What is known there comes from the shapes inside it: a six-by-six repeat contains every three-pick cloth written twice down the picks, so the pair drawn above is a six-by-six pair as well, and three is not enough at six by six. Whether four is enough there is not known.

The half-repeat rule is observed, not proved. Its failing half — no window of half the ends or less names every family — holds on every shape walked, and the overlap argument makes it expected; nothing here proves it for every repeat. Its naming half has a counterexample, and the counterexample is the more instructive result: the rule is the ordinary case, and a cloth that repeats a stretch of itself can defeat a window that the rule says is wide enough.

The group is each shape’s own. A derivation that changes the repeat — doubling a weave, reversing a twill across a width it does not fill — is outside it, and so is setting two weaves side by side, which what combining two weaves reaches found manufactures windows neither weave had.

And the windows are square. A rectangular window — four picks by five ends at four by seven, say — is a different census and might name what the square one cannot. The question asked was the one the four-by-four result left, about square windows, and the answer is about them.

Who worked out which part #

The manuals’ derivations, plane groups and orbit counting are long established, and sequence assembly from overlapping reads has its theory from Idury and Waterman (1995) and Pevzner, Tang and Waterman (2001). The four-by-four census of three-by-three windows was the earlier account’s. Walking the eleven shapes whole, finding that three holds to five ends and fails at six, that every window no wider than half the repeat fails and every wider one holds except at one pair, and taking that pair apart as a repeat inside a cloth, was done here.

Still open: whether a window of four names every six-by-six cloth #

Six by six is the first square repeat where the rule predicts a window of four, and it is the first that cannot be walked. A three-pick cloth written twice down the picks already defeats three there. Whether some six-by-six cloth defeats four — whether the stretch-inside-a-cloth mechanism that broke four at seven ends can be built inside a six-by-six repeat with an overlap of two ends to beat — is a search for a structured family rather than a census, and a random sample of six-by-six drafts would almost certainly miss it: the four-by-seven pair is one in nearly half a million. A search over cloths built from a stretch, its copy and a moved end between them would settle whether the overlap of two ends that holds at four by six also holds when the picks catch up.