A page that knows where it is

A de Bruijn sequence is a cycle of letters in which every word of a fixed length appears exactly once. The two-dimensional version replaces cycle with array cyclic in both directions and word with rectangular block, and everything else is the same sentence.

The counting is immediate and it is tight. There are $2^{rs}$ binary blocks of size $r \times s$, and an $R \times S$ array has $RS$ positions to put them in, so any such array must have $RS = 2^{rs}$ exactly. For two-by-two blocks that is sixteen cells, which a four-by-four array has and nothing smaller does.

Why existence is a separate question #

In one dimension the counting condition is also sufficient, and the graph settles it: an Eulerian circuit exists because every vertex has equal in-degree and out-degree, and there is one for every alphabet and every word length. Nothing corresponding is available here.

The obstruction is that a two-dimensional window has no single direction to be walked in. A sequence’s windows overlap in one way — each shares $n-1$ letters with the next — so the transitions form a graph. An array’s blocks overlap in two ways at once, and the constraint linking them is not a walk in anything.

So existence in two dimensions is a genuine question, and the answer is known for large families of parameters and not in general. What the figure does is settle the smallest case by exhaustion: all $2^{16}$ arrays generated, the sixteen blocks of each collected, and one kept whose blocks are all different. That is a proof for those parameters and evidence for nothing else.

What the array is not #

The tempting reading of a de Bruijn torus is that it is four de Bruijn sequences stacked, or a sequence folded up. Both are wrong, and the figure checks the first of them: no row of the array is a de Bruijn sequence in its own right.

That is worth dwelling on. A row of the array, read cyclically, is four bits and there are four two-bit windows in it; for the row to be a de Bruijn sequence of order two those four windows would have to be 00, 01, 10 and 11. None of the four rows manages it, and there is no reason it should — the array’s blocks are made of pairs of rows, and the property is a joint one.

Nor is the array a folded sequence. Writing the sixteen letters of a de Bruijn sequence of order four into a four-by-four grid gives an array whose two-by-two blocks are some sixteen blocks with repeats, essentially always. The two properties are about different windows and the one does not imply the other.

How the larger ones are built #

Since exhaustive search stops almost immediately, the arrays that get used are constructed, and the standard construction is worth describing because it shows what the extra dimension costs.

Take a de Bruijn sequence for the rows: a cyclic sequence whose windows of length $s$ are the $k^s$ possible rows of a block. Write it along the first row of the array. Then take a second sequence — over a different alphabet, whose letters are shifts — and use it to decide how far each subsequent row is rotated relative to the one above.

A block of the array is then determined by two things: which window of the row sequence it starts at, and which shifts the rows between its top and bottom underwent. If the shift sequence has the property that every window of $r-1$ shifts is distinct, the pair determines the block and the block determines the pair. The array’s two-dimensional property is manufactured out of two one-dimensional ones, held together by an argument about which pairs can collide.

That is the shape of every published family, and the conditions under which the argument closes are exactly the parameter sets for which existence is known. There is no reason to think the condition $RS = k^{rs}$ fails outside them — the belief is that tori exist far more widely than the constructions reach — and no proof either.

Reading a patch as an address #

The reason to want such an array is that it turns a small local observation into a global position.

Print the array over and over across a page. Any two-by-two patch of the printed page shows one of the sixteen blocks, that block occurs at exactly one position of the array, and so the patch determines its own coordinates modulo four in each direction. A reader that can see four marks knows where it is looking, to within one tile.

The modulo is the whole limitation, and scaling it away is the design problem. To address a page rather than a tile, the array has to be as large as the page, which by the counting condition means the window has to be large enough that $2^{rs}$ exceeds the number of positions. A page of a million addressable positions needs $rs \ge 20$: a window of four by five marks, or five by four.

Real position-coding patterns are built exactly this way and with a larger alphabet. Give each mark four possible states rather than two — a dot displaced in one of four directions, say — and a window of six by six marks carries $4^{36}$ possibilities, which is enough to address an area vastly larger than any page. The decoding is then not a search over sixteen positions but an arithmetic computation, and it has to be, because a search over $4^{36}$ is not a search.

What the window has to be worth #

The arithmetic of how large a window must be is worth doing once, because it is the whole of the design.

A window of $r \times s$ marks over an alphabet of $k$ states carries $rs \log_2 k$ bits. To address $N$ positions uniquely the window must carry at least $\log_2 N$ bits, so

$$rs \log_2 k \ge \log_2 N.$$

Everything else is a trade between the three quantities. Increasing $k$ means finer distinctions between marks, which costs printing precision and reading resolution. Increasing $r$ and $s$ means the reader must see a larger patch, which costs field of view and makes the reader more vulnerable to a smudge. Increasing neither means addressing less.

A binary window of two by two addresses sixteen positions, which is the figure above and is a toy. A binary window of five by four addresses about a million — a page at a coarse resolution. A four-state window of six by six addresses $4^{36}$, which is about $5 \times 10^{21}$, and that is the regime a real position-coding pattern works in: enormous overcapacity, spent on making the decoding robust rather than on addressing more.

The overcapacity matters more than it sounds. A pattern with exactly enough addresses has no error detection at all — every window is a valid address, so a misread mark produces a confident wrong answer. Spending some of the space, exactly as a code spends its length on distance between codewords, buys the ability to notice that a patch was misread.

Where the extra dimension makes things harder #

Three things get worse going up a dimension, and none of them is the counting.

Existence. In one dimension a de Bruijn sequence exists for every alphabet and length. In two, the necessary condition $RS = k^{rs}$ is not known to be sufficient, and the constructions that are known produce particular shapes rather than all of them.

Construction. The one-dimensional object has three constructions of different characters — a walk, an alphabetical list and a machine. The known two-dimensional constructions largely work by combining one-dimensional ones cleverly: take a sequence for the rows and a different one for the shifts between them, and check that the product has the property. They are constructions and they are not as clean.

Decoding. Locating a window in a one-dimensional maximum-length sequence is a discrete logarithm, which is at least a well-studied problem with structure to exploit. Locating a patch in a two-dimensional array built by combining sequences means solving two such problems and reconciling them, and the reconciliation is where practical decoders spend their effort.

What does not get worse is the counting argument, and that asymmetry is the point of this rung. The condition $RS = k^{rs}$ is as easy to state in two dimensions as $L = k^n$ is in one, and it stops carrying the whole answer.

The same shape elsewhere #

A local observation that determines a global position is a recurring design, and the constraint is always a counting one.

An error-correcting code is the same trade in a different direction: the codeword’s redundancy is spent so that a corrupted word determines the original. A position code spends its redundancy so that a fragment determines the whole. Both are asking a small window to carry information about something larger than itself, and both are limited by the same arithmetic — the window cannot distinguish more possibilities than it has states.

The distinguishing feature here is that the information wanted is where, and that the answer is supplied by the pattern rather than by anything measured. A ruler answers where by being read along its length; a de Bruijn torus answers it from any patch, without a reference point, without an origin, and without the reader having seen anything else.

The same idea appears wherever a system must recover its position in a stream it joined late. A rotary encoder on a shaft reads a few tracks and knows the shaft’s absolute angle rather than counting from a home position; a Gray code is the neighbouring construction, solving a different half of the same problem — its consecutive words differ in one place, so a reader catching a transition cannot be badly wrong, while a de Bruijn window is what tells the reader where the transition was.

The counting condition, and what it does not decide #

It is worth being precise about where the arithmetic stops, because the gap is the subject of this rung.

The condition $RS = k^{rs}$ is necessary and it is not an existence argument. Compare the one-dimensional case, where the corresponding condition $L = k^n$ is also necessary and the graph then supplies sufficiency for free. Here there is no supplier.

It is not even sufficient in the weak sense of picking out a unique shape. Sixteen cells can be arranged as $4 \times 4$, as $2 \times 8$, as $8 \times 2$ or as $16 \times 1$, and the question of which of these hold every two-by-two block is four separate questions. The $16 \times 1$ case is not a torus at all in the sense wanted — its blocks would have to wrap round a single row, which makes the two rows of the block equal. So the counting condition can be met by an arrangement in which the objects being counted collapse.

That is the general shape of the difficulty, and it is why the next rung is about the same failure in a cleaner setting. Move from words to subsets and the counting condition becomes a divisibility, it is still necessary, and there are parameter sets where it holds and no cycle exists — which can be shown rather than merely suspected, because the counterexamples are small enough to exhaust.

What the pictures cannot show #

Nothing here is drawn at a useful size. A sixteen-cell array is to a position-coding pattern what a graph on four vertices is to a real network: the smallest instance in which the property is visible at all, and small enough that the method used to find it is one no larger instance could use.

Only the smallest case is exhibited. All 65,536 arrays are tested and one is kept, which settles two-by-two blocks in a four-by-four array and nothing else. The parameter sets that matter in practice are far beyond exhaustive search, and their arrays are constructed rather than found.

The torus is drawn as a square with a wrapped row and column. A torus has no edge, and the faint extra row and column are the drawing’s way of admitting that the blocks straddling the boundary are blocks like any other.

The decoding is a search over sixteen positions. That is the whole of the decoding problem at this size and none of it at any useful size, where the search is replaced by arithmetic that this figure does not contain.

And the printed sheet is four tiles. The claim it illustrates is about a patch determining its position within the array; determining which tile it is in is a different problem, and the figure’s caption says so rather than letting the picture suggest otherwise.

Where the ladder goes next #

The rung above asks the question this one has been circling: which families of objects admit such a cycle at all. Words are the easy case because their overlaps form a graph with equal degrees everywhere. Two-dimensional blocks are harder because their overlaps do not form a graph. And subsets, permutations and partitions are harder still — for those there is a counting condition, it is not sufficient, and there are parameter sets where the condition holds and no cycle exists, which is a sharper failure than anything in this rung.

What is worth carrying away #

A theorem’s proof and the reason a reader believes the theorem are often different, and generalising is what separates them.

Everyone who meets de Bruijn sequences believes them because the counting works out: there are $k^n$ words and $k^n$ positions and the fit is exact. That is not the proof. The proof is that the overlaps form a graph in which every vertex has equal in- and out-degree, and the counting is a consequence. Going up a dimension keeps the counting and destroys the graph — and the result is a subject where the easy argument still holds, the conclusion often still holds, and the connection between them has to be rebuilt case by case.