Weaves

A window of five is fooled at nine ends

Seven ends were enough to hide a moved end from a window of four, and the anatomy of the hiding predicted the next case: a stretch of three, its copy, the moved end and the moved end twice more, nine ends in all. Built directly at six picks by nine ends, the recipe defeats a window of five — wider than half the repeat — in 193 pairs of cloths, every one of them sharing its windows exactly and every one told apart by a window of six. At eight ends nothing it builds even shares a census. The same recipe, rerun at seven ends with a stretch three picks deep, finds 26 pairs where the first search found four.

Worth reading first: Hiding a moved end takes seven ends · The window that names a cloth is half its repeat · A cloth's derivation class is its census of small patches.

Hiding a moved end takes seven ends took apart the one exception to a tidy rule and found a mechanism inside it. The rule, from the walk over eleven small repeats, is that a census of square windows names every derivation family of a repeat once the window is wider than half the repeat’s ends. The exception was a pair of cloths at four picks by seven ends that a window of four could not tell apart. The mechanism was a stretch of ends that a slide along the picks leaves alone, a copy of that stretch, an end between them that sits in a different place along the picks in the two cloths, and — the part that took the most finding — that same end written twice more beyond the copy, once as it stands and once slid.

That essay ended with a prediction precise enough to be wrong. If the anatomy is the whole of the mechanism, a window of five should be fooled the same way, by a stretch of three ends rather than two, and that needs nine ends exactly: three for the stretch, one for the moved end, three for the copy and two for the moved end in both of its positions. The picks must allow a slide that leaves the stretch alone and must be at least five, for the window to fit, so six picks is the least. Six picks by nine ends should hold a confused pair. Six by eight should not.

Both halves hold.

Two 6-by-9 cloths a window of 5 cannot tell apart, end by end. A pair of 6-pick, 9-end cloths in different derivation orbits whose censuses of 5-by-5 windows agree, built from a stretch of 3 ends that a slide of 2 picks leaves alone, the moved end, the stretch's copy written straight, and the moved end twice more. They differ only in end 4, which reads 100000 down the picks in one and 000010 in the other, the same end slid 2 picks. Ends 8 and 9 are the moved end in its two positions, so each cloth holds both and they differ only in which stands between the stretches. A window 5 ends wide that holds the moved end holds at most one copy of the stretch, so every window of one cloth is a window of the other. 19,488 confused pairs at this shape are writings of 193 pairs of cloths. What the drawing cannot show is the census, which is a list of counts.
Fig. 1 One of the 193 pairs: two cloths of six picks by nine ends, drawn end by end. Ends one to three are a stretch that a slide of two picks leaves unchanged, ends five to seven its copy, end four the moved end and ends eight and nine the moved end in both of its positions. The cloths differ only in end four, and every five-by-five window of one is a window of the other.

Why a window one end wider needs two ends more

The earlier account explains why the count of ends climbs by two and not by one. A window that sees the moved end and both copies of the stretch on either side of it can compare them and notice which of the moved end’s two positions stands in the middle. Hiding the move means making the window too narrow for that, so the stretch has to be long enough that a window holding the moved end can never also hold the whole of the stretch on the near side and the whole of the copy on the far side. For a window kk ends wide that means a stretch of k−2k - 2 ends.

Count what the recipe then asks for: k−2k - 2 ends of stretch, one moved end, k−2k - 2 ends of copy, and two more for the moved end as it stands and slid. That is

2(k−2)+3=2k−12(k-2) + 3 = 2k - 1

ends, which is seven for a window of four and nine for a window of five. The walk’s rule says a window wider than half the ends is enough, and 2k−12k - 1 ends is the largest repeat for which a window of kk is wider than half. So the recipe is built to sit exactly on the boundary the rule draws, one end inside it, at every window size — which is why the exception was ever possible and why it should recur.

Which repeats have room to hide a moved end from a window of four or five. The ends the construction needs to hide a moved end from a window k ends wide: a stretch of k − 2 ends that a slide of some whole number of picks leaves alone, the moved end, the stretch's copy, and the moved end as it stands and slid — 2k − 1 ends, seven for a window of four and nine for a window of five — and picks with a divisor, for the slide, and at least k of them, for the window. 6 × 7 with a window of 4: the 7 ends fit, and slides of 2 or 3 picks; 6 × 8 with a window of 5: 1 end short, and slides of 2 or 3 picks; 6 × 9 with a window of 5: the 9 ends fit, and slides of 2 or 3 picks; 5 × 9 with a window of 5: the 9 ends fit, and no slide, the picks being prime. What the diagram cannot show is any other way of hiding a move.
Fig. 2 The ends the recipe needs against four repeats. A window of four needs seven and six by seven has them; a window of five needs nine, so six by eight falls one end short and six by nine fits. Five by nine has the ends but no slide, because five picks are prime and no slide short of the whole repeat leaves an interlacing end unchanged.

There are two further conditions, both about the picks. The stretch must be unchanged by a slide of some whole number of picks short of the whole repeat, which needs the picks to have a divisor: five picks are prime and offer none, so five by nine has room for the ends and no way to build the stretch. And the window cannot be taller than the repeat, so a window of five needs five picks at least. Six picks is the smallest count that meets both, with slides of two and of three.

Building the recipe instead of searching for it

The earlier search let the ends beyond the copy be any ends at all and found the anatomy in what came back. At nine ends that freedom is unaffordable: with two free ends of sixty-two possible kinds, every stretch and every moved end, it runs to tens of millions of cloths a family, each needing a census of fifty-four windows read through eight symmetries. So this time the anatomy is the input rather than the output. The two ends beyond the copy are fixed to the moved end and the moved end slid, in both orders, and everything else is taken exhaustively: every stretch of three ends that a slide of two or three picks leaves alone, the copy written straight and mirrored, every interlacing moved end and every slide of it.

That changes what a result can say, and it is worth being exact about it. A confusion found this way is a confusion — two cloths that genuinely share a census and genuinely lie in different families. But a failure to find one says only that this recipe does not produce one, not that no pair of cloths at that shape is confused. The prediction was about the recipe, so the recipe is the right thing to test; whether some quite different arrangement also fools a window of five is a separate question, and it is left open below.

The moved-end construction at a window of four and a window of five. Cloths built from a stretch of k − 2 ends a slide leaves alone, the moved end, the stretch's copy and the moved end twice more, every choice of each, read with censuses of k-by-k windows. 4 × 7, window 4: 416 pairs, 304 sharing a census, 32 in different orbits, writings of 1 pairs of cloths. 6 × 7, window 4: 25,056 pairs, 10,608 sharing a census, 2,304 in different orbits, writings of 26 pairs of cloths. 6 × 8, window 5: 153,048 pairs, 0 sharing a census, none in different orbits. 6 × 9, window 5: 198,624 pairs, 53,952 sharing a census, 19,488 in different orbits, writings of 193 pairs of cloths. What the chart cannot show is a cloth outside the construction.
Fig. 3 What the recipe built and what it found, on a log scale: pairs of cloths, pairs whose censuses agree, and pairs in different families. At four by seven it finds the walk’s one pair; at six by seven, twenty-six; at six by eight not one pair of the 153,048 even shares a census; at six by nine, 19,488 confused pairs, writings of 193 pairs of cloths.

Six by nine: a window of five is fooled

At six picks by nine ends the recipe builds 198,624 pairs of cloths in which every pick and every end interlaces. In 53,952 of them the two censuses of five-by-five windows agree. Most of those are one cloth written two ways — sliding the moved end sometimes produces a writing of the same cloth, turned or reversed — and the orbit test throws out 34,464 of them. That leaves 19,488 pairs that share every five-by-five window and lie in different derivation families, and taken up to the symmetries they are 193 distinct pairs of cloths.

A window of five is wider than half of nine. So the half-repeat rule, which held on every repeat small enough to walk whole save one, fails here not in one pair but in nearly two hundred, and it fails in exactly the shape the seven-end account said it would.

The pair drawn at the top is the plainest of them. Its stretch is three ends that alternate up and down the picks — two in step and one out of step — and a slide of two picks leaves each of them as it was. The moved end rises on a single pick, the first in one cloth and the fifth in the other. Ends eight and nine are the moved end as it stands and slid. Every window of five ends that includes end four includes at most one whole copy of the stretch, and from the far side of the stretch that view occurs in the other cloth too.

They share their windows outright

There is a stronger statement available, and it holds for every one of the 19,488 confused pairs. The census compares windows up to the symmetries of the square: a window of one cloth may match a window of the other reflected, reversed or counterchanged. None of that is needed here. Read with no symmetry at all — the fifty-four windows of each cloth, coded and sorted — the two lists are identical, entry for entry, in every confused pair.

The same was true of the walk’s exceptional pair at four by seven, and it is what the mechanism predicts. Nothing in it reflects or inverts anything. It slides an end along the picks, and the stretch absorbs the slide because the stretch does not see it. Every window that differs between the two cloths in position differs only by where along the repeat it sits, and a census is a count that has forgotten positions.

A window of six tells every pair apart

The mechanism is a statement about one window size, and it should stop working as soon as the window has room for one more end than the recipe was built to keep out of view. A window of six on nine ends can hold the moved end together with the whole of the stretch and part of the copy, or the whole of the copy and both of the moved end’s later appearances — the comparisons the stretch’s length was chosen to prevent. Read with a census of six-by-six windows, all 193 pairs come apart. Not one survives the wider window, which is the behaviour of a boundary rather than of an accident.

So at six by nine the least window that names every cloth the recipe builds is six, not five — one more than the half-repeat rule predicts, the same single end of excess that the seven-end pair showed against a window of four.

Six by eight: not even a shared census

The other half of the prediction was that nothing between seven ends and nine should be fooled by a window of five, and the only repeat between them with six picks is six by eight. There the recipe can only be built short: a stretch of three, the moved end, the copy and one end left, which can hold the moved end in only one of its two positions.

Of the 153,048 pairs it builds, not one shares a census. It is not that the shared censuses are all one cloth written twice, as most were at six by nine; the windows themselves disagree in every pair. Remove one of the moved end’s appearances and the windows that would have matched across the stretch have nothing to match against. That is a sharper outcome than the prediction asked for, and it is the strongest evidence here that the third appearance of the moved end is not decoration but the load-bearing part of the anatomy.

Six by eight is a window of five on a repeat of eight, where five is wider than half by one end. The half-repeat rule says five names everything there. As far as this recipe can see, it does.

The stretch that does the work is three picks deep

The earlier search at six by seven tried only stretches that a slide of two picks leaves alone, with the copy written straight, and found four pairs of cloths. Rerun now with the other slide six picks allow — three — and with the copy mirrored as well, the recipe at six by seven finds twenty-six.

Which stretches hide a moved end. The pairs of cloths the construction confuses, by family — the slide that leaves the stretch alone, two picks or three, and whether its copy is written straight or mirrored. 6 × 7 with a window of 4: slide of 2, copy straight, 4; slide of 2, copy mirrored, 0; slide of 3, copy straight, 22; slide of 3, copy mirrored, 0. 6 × 9 with a window of 5: slide of 2, copy straight, 12; slide of 2, copy mirrored, 1; slide of 3, copy straight, 181; slide of 3, copy mirrored, 0. A pair of cloths can arise in more than one family, so a shape's families can sum to more than its pairs. The search at six by seven that first found this anatomy tried only the slide of two with a straight copy.
Fig. 4 The confused pairs by how the stretch was built: the slide that leaves it alone, two picks or three, and whether its copy is written straight or mirrored. At six by seven the slide of two gives the four pairs already known and the slide of three twenty-two more. At six by nine the slide of three gives 181 of 193. A mirrored copy gives one pair in all.

The four the earlier search found are all among them — the construction is required to rebuild every one, and does — and the other twenty-two have stretches three picks deep. At six by nine the imbalance is larger still: 12 pairs from a slide of two and 181 from a slide of three.

The reason is a count, not a subtlety. On six picks an end that a slide of two leaves alone must repeat every two picks, and only two such ends interlace: up-down-up-down-up-down and its counterchange. An end that a slide of three leaves alone repeats every three picks, and six of those interlace. A stretch of three ends therefore has eight possible fillings at a period of two and 216 at a period of three. The mechanism did not change between the two searches; the earlier one looked at the corner of it where there was least to find.

That is a correction to the count the earlier essay gave for six by seven, and it is worth putting plainly. Four pairs of orbits was the right number for the family it searched, and that family was a fraction of the anatomy. The anatomy itself confuses at least twenty-six.

A mirrored copy hides nothing

The copy can be written in the order of the stretch or reversed, and the earlier search tried both at four by seven, where only the straight copy worked. Here the pattern holds and sharpens. Across both shapes a mirrored copy produces exactly one confused pair of cloths, and that pair is not really mirrored: its stretch reads up-down, down-up, up-down along the ends, the same in both directions, so its mirrored copy is its straight copy and the pair is one the straight recipe builds as well. That is the one pair the figure above counts twice.

The account explains why reversal fails. The moved end’s view from the near side reads the stretch in one direction, and the matching view in the other cloth reads it from the far side — through the copy, approaching from its other end. Reverse the copy and that view reads the ends in the opposite order, and the windows no longer coincide. The hiding needs a stretch that repeats, not one that reflects.

Two 6-by-9 cloths a window of 5 cannot tell apart, end by end. A pair of 6-pick, 9-end cloths in different derivation orbits whose censuses of 5-by-5 windows agree, built from a stretch of 3 ends that a slide of 3 picks leaves alone, the moved end, the stretch's copy written straight, and the moved end twice more. They differ only in end 4, which reads 001000 down the picks in one and 000001 in the other, the same end slid 3 picks. Ends 8 and 9 are the moved end in its two positions, so each cloth holds both and they differ only in which stands between the stretches. A window 5 ends wide that holds the moved end holds at most one copy of the stretch, so every window of one cloth is a window of the other. 19,488 confused pairs at this shape are writings of 193 pairs of cloths. What the drawing cannot show is the census, which is a list of counts.
Fig. 5 A pair whose stretch a slide of three picks leaves alone, the commonest kind at six by nine. Each stretch end repeats every three picks, and the moved end rises on one pick, slid three between the two cloths, which the stretch does not see. Ends eight and nine again hold the moved end as it stands and slid.

How the moved end slides

In 185 of the 193 pairs at six by nine the moved end slides by a multiple of the stretch’s own period — by two picks where the stretch repeats every two, by three where it repeats every three — so the stretch cannot see the slide. That is the mechanism as described. In the other eight the moved end slides by a single pick, and the stretch can see that. They are genuine confusions, checked like the rest: the censuses agree and neither cloth is a writing of the other. The account given here does not explain them, and rather than invent a reason they are left as found; a slide of one that still hides suggests a second, smaller mechanism living inside the first, perhaps one that uses the moved end’s own repetition.

How close the confused cloths come

Two cloths a census confuses are by construction close: they differ in one end. How close, measured as the fewest intersections in which any writing of one differs from the other, is a property of the moved end.

How close the cloths a window confuses come to each other. For every pair of cloths the construction confuses, the fewest intersections in which some writing of one differs from the other: 6 × 7 with a window of 4, 10 pairs at 2, 14 pairs at 4, 2 pairs at 6; 6 × 9 with a window of 5, 76 pairs at 2, 94 pairs at 4, 23 pairs at 6. The moved end differs from itself slid in at least two intersections, so two is the least a pair can differ; most differ in four. What the chart cannot show is which intersections, which the drawings of the pairs do.
Fig. 6 For every pair of cloths the recipe confuses, the fewest intersections in which some writing of one differs from the other. At six by nine: 76 pairs two apart, 94 four apart, 23 six apart. At six by seven: 10, 14 and 2. No confused pair is further apart than six intersections.

A moved end differs from itself slid in at least two places — where it was up and where it now is — so two is the floor. At six by nine 76 pairs sit on it, cloths that differ in two intersections out of fifty-four and that no census of five-by-five windows can separate. The others differ in four or six, by moved ends with more than one raised pick. None differs in more, because the moved end is the only thing that changes and it has only six picks to change in.

That puts a practical edge on an abstract result. Two intersections is the size of difference a single fault in the loom’s instructions can make — the kind counted in the census of mispicks and the three mistakes a loom can hold — and a census of patches is the kind of summary a machine reading cloth would keep. A reader with a five-thread window would not merely miss such an error; it would have no way to know the cloth had changed family.

What the window is, as a reader

Behind the arithmetic is a model of reading. A cloth’s draft repeats, and a repeat tiles the plane with no edge to start counting from, so a census of windows is what a reader who can see only a small square of cloth at a time, and who does not know where on the cloth each square came from, could collect. A cloth’s derivation class is its census of small patches showed that on four-by-four repeats such a reader needs a window of three to know which family it is looking at. The walk then showed the window must grow with the repeat, to a little over half of it.

These results say what the “little over” is. On a repeat of 2k−12k - 1 ends whose picks allow a stretch, a reader with a window of kk is fooled and a reader with a window of k+1k + 1 is not, at least by this recipe, for both sizes now tested. The safe rule is a window wider than half of one more than the ends, and the gap between it and the naive rule is the moved end’s third appearance.

Where the first window escapes

The recipe can be asked about a window of three, and its answer is instructive. A window of three needs a stretch of one end, and five ends in all. At four picks by five ends the recipe builds 48 pairs, 32 share a census, and every one of the 32 is the same cloth written two ways. A stretch of a single end, unchanged by a slide of two picks, is an alternating end, and sliding the moved end between two copies of it produces a cloth that is the original turned about. So the walk was right that a window of three names every four-by-five cloth: the mechanism needs a stretch of at least two ends before it has anywhere to hide.

That makes the pattern begin at a window of four and continue at five, and nothing found so far says where, or whether, it stops.

The same ambiguity, one dimension down

The mechanism has an older relative, in a field that reads strings rather than cloths. In sequencing by hybridisation a string is recovered from its census of short substrings — every run of ll letters it contains, counted, with their positions forgotten — and the question of when two strings share such a census was settled in the 1990s. Ukkonen conjectured in 1992 that a short list of operations — transpositions and rotations — produces every string with the same census, and Pevzner proved it in 1995: in essence, wherever a run of l−1l - 1 letters occurs twice, the stretches it separates can be exchanged without any window noticing.

The moved end is that exchange in two dimensions. The stretch occurring twice plays the part of the repeated run, and what is exchanged is which of the moved end’s two positions stands between the copies. The extra difficulty in a cloth is the second axis: the windows are squares, so the repeated stretch has to be unchanged along the picks as well, which is where the slide and its divisor come from. A string has no such axis, and no analogue of five picks being prime.

How the search was made

Ends are written as columns read down the picks, rows as integers across the ends — the draft read as a matrix, one bit to an intersection. For a window of kk the stretch is k−2k - 2 ends, each unchanged by a slide of pp picks for each proper divisor pp of the picks; the copy is the stretch written straight or reversed; the moved end is every end that interlaces; its slide is every amount from one pick to one less than the repeat; and the two ends beyond the copy are the moved end and the moved end slid, in both orders. Where only one end fits beyond the copy, as at six by eight, each of the two is tried in it.

A census reads every window of a cloth at every position of the repeat, applies each symmetry of the shape to the whole draft rather than through a table of window codes — a table for a five-by-five window would have thirty-three million entries a symmetry — and keeps the least of the sorted lists. The orbit test builds every writing of the first cloth under slides, reversals and counterchange and asks whether the second is among them. Required of the procedure, not shown: that at four by seven it rebuild the walk’s one exceptional pair; that at six by seven every pair the exhaustive search found be among those it builds; that at six by eight it build nothing confused; that at six by nine every confused pair share its raw windows and come apart at a window of six; and that it refuse a window as wide as the repeat, a stretch that does not fit, and a repeat too wide to write as a number.

What this does not settle

It does not settle the six-by-nine census. A census of every six-by-nine cloth would have to take the whole repeat, two to the fifty-fourth drafts before symmetry, and nobody is going to walk it. The 193 pairs are pairs the recipe builds; there may be others, built some other way, and there may be windows of five fooled at repeats the recipe calls safe. Six by eight in particular is safe only as far as this recipe can see.

It does not show the pattern continues. A window of six needs a stretch of four and eleven ends, at six picks or more with a divisor, and that is a definite construction of the same kind and a good deal heavier. Two cases agreeing is a pattern; it is not a proof, and the window-of-three case, where the recipe produces nothing, is a reminder that the pattern has edges.

And it says nothing about any loom. A census of windows is a model of a reader with a small field of view, and the draft it reads already leaves out everything a matrix cannot say about yarn and tension. Whether any real instrument — a camera inspecting cloth, a weaver’s eye at the fell — reads cloth that way is a separate question, and the derivation families themselves are a quotient the trade’s manuals never quite drew.

Who found which part

The derivations and the families they cut are the weaving manuals’, counted in the catalogue of four-by-four and made exact in the essay on how few cloths derive into one another. The census of windows, the half-repeat rule, the seven-end anatomy and its prediction are the earlier essays’ own. The interchange of repeated runs in strings is Ukkonen’s conjecture of 1992 and Pevzner’s theorem of 1995. What is added here is the recipe built directly and its results: 193 pairs at six by nine fooling a window of five, none sharing a census at six by eight, every confusion sharing its raw windows and separated by a window of six, the twenty-six pairs at six by seven where four were known, and the window of three where the recipe finds nothing to hide in.

Still open: whether a window of six is fooled at eleven ends

The recipe makes a third prediction as definite as the second. A window of six needs a stretch of four ends that a slide leaves alone, the moved end, the copy and the moved end twice more: eleven ends, at six picks — the least that are at least six and have a divisor. If the anatomy is the whole of the mechanism, six picks by eleven ends should hold confused pairs and six by ten should not.

Two things could break it. A window of six on six picks is as tall as the repeat, so every window sees every pick of the ends inside it, and a slide along the picks that the stretch does not see is also one the window cannot see within the moved end’s column; that may make the hiding easier or impossible. And the eight pairs at six by nine that slide by a single pick hint at a second mechanism the recipe stumbles on rather than builds. A search that lets the moved end’s slide be anything and records which slides hide would say whether those eight are a curiosity or the beginning of a larger family.

Shares its objects with

Essays naming at least two of the same things, that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

CensusDerivationDraftOrbitRepeatSymmetry