In a 2-dimensional deBruijn array, we fix a window size (say 2 X 2) and have a 2-dimensional array where every subgrid of that size (with wrap-arounds) shows a different pattern: a 4 X 4 binary array has 16 cells, and a 2 X 2 binary window has 16 possible patterns, so each cell can anchor a distinct window.
Cross Patterns
What if we use a different window shape? Let’s try a cross pattern instead of a square: the window at a cell consists of its four neighbours to the north, south, east and west.
Unlike the 2×2 window, it turns out that with a cross-shaped window, it’s impossible to create a pattern where every position has a unique signature.
De Bruijn Combs
A “comb” is a pattern where certain positions are transparent (open blocks) and others are opaque (shaded blocks). Imagine having a 8-length window where the first, second, fourth and eighth positions are exposed and the others are opaque. Now imagine sliding this window over a 16-bit sequence (with wrap-arounds).At every step of the slide, you can read off four bits from the exposed positions. Can you find a 16-bit sequence so that every read is distinct? It turns out that there is exactly one such sequence (not counting cyclic shifts or complements).
This opens up a host of puzzles: what about other comb patterns? For a given comb pattern, is it solvable? If yes, how many morally distinct solutions are there?
Session notes
Chapter 3 of Magical Mathematics has no new tricks. The first half works through applications of de Bruijn sequences – robotic navigation, 2-D arrays, cross patterns, combs, and smart pens – and closes with a read-through of the cryptography section that we didn’t discuss in depth.
0:30 We recapped the 32-card trick and the Euler-tour method for generating de Bruijn sequences, then opened chapter 3. The authors frame this chapter as recreational mathematics that kept spilling into research.
2:39 Robotic vision: a robot traversing a long corridor can read the five floor-coloured bits underfoot and recover its global position from the de Bruijn sequence, rather than updating stored coordinates after each step. The book leaves the corridor endpoints unaddressed; we assumed wraparound.
5:49 A binary window has patterns; a binary grid has 16 cells. A 2-D de Bruijn array assigns a distinct window pattern to every anchor position (with wraparound). The tricky anchor is the bottom-right cell, whose window wraps to collect the four corners of the grid.
11:00 Wraparound is easiest to see on a torus: roll the sheet into a cylinder so the rightmost column meets the leftmost, then bend it into a doughnut (or a vada) so the bottom row meets the top.
14:16 How 2-D arrays are generated is unclear. In 1-D each Euler-tour edge emits one bit; in 2-D, cutting a 16-bit de Bruijn string into four rows does not obviously guarantee every window is distinct, since a window may read non-consecutive positions of the string. The book says little on this.
16:21 A binary window has patterns, so the grid should be with , say . No square grid works exactly: is too small and forces repeats.
18:34 The book’s quip: ask a random mathematician and you get “I don’t do stuff like that”; combinatorialists are the ones who worry about such things. Most 2-D generation questions were open at time of writing.
19:34 Generalisations go in two directions: bigger windows and more colours. Three colours with a window give patterns (target: ); a window gives (target: ). Existence, construction, and counting are all open in general.
21:38 A cross-window idea from a student: on a city map where each city is sunny or cold, can reporting the four cardinal neighbours’ weather always identify the chosen city? The book says no such binary array exists, and that this is proved – without giving the proof.
23:47 We played the two accompanying games on a live grid. Given a colouring with eight cells of each colour, find two cells sharing a cross pattern (wraparound; own colour excluded). Participants found cells 6 and 15, then 7 and 14. I have no proof; a counting argument does not work, because 16 cells could in principle hold 16 distinct cross patterns, so the impossibility must be structural.
29:07 Other polyomino windows remain open; only the cross is explicitly ruled out by the book.
30:09 De Bruijn combs: a length-8 comb with positions 1, 2, 4, 8 open slides (with wraparound) over a 16-bit sequence, reading four bits at a time. The book gives one sequence achieving all-distinct reads, unique up to complement and cyclic shift, found by computation. Existence and count for general combs are open.
33:07 Smart pens: paper printed with an invisible 2-D de Bruijn pattern lets a sensor at the pen tip read a small neighbourhood of its position and localise itself on the page, digitising strokes as you write.
35:19 The authors close by noting that applications motivated 2-D arrays, trick-seeking motivated combs and crosses, and the questions that fell out remain mostly unanswered – which I found relatable.
36:23 The cross non-existence result is stated without proof, and I could not find one. Brute force is feasible (about 65,000 colourings to check), but a combinatorial argument would be nicer.
37:24 We read rather than discussed the cryptography section: XOR plaintext with a shared corrupting string to encrypt; XOR again to decode. One-time pads and agreed newspaper sentences each have well-known limitations. The book recommends Leo Marks, Between Silk and Cyanide.
39:33 De Bruijn sequences as key streams: from seed 001, append and drop the leading bit – Sunita’s rule from the previous session – cycling through all eight 3-bit strings. The book says DES used de Bruijn cycles and gives a 20-bit recurrence (last bit plus bits two and five back) claimed not to repeat for steps; I did not verify this.
42:36 Diaconis and Graham were involved in a de Bruijn-based chip for protecting special-event television broadcasts.
43:40 Up next: DNA strings and the rest of chapter 3, then chapter 4.
45:37 Two things came up after the main content. Sunita noted that one specific 16-bit de Bruijn sequence, cut into four rows of four, gives a valid 2-D array – the claim is for that sequence specifically, not for all de Bruijn sequences of order 4. If it holds more broadly, Euler-tour generation might extend to 2-D after all. Akash suggested thinking of the grid as a torus throughout to keep the wraparound arithmetic clean.
To think about
- Prove that no binary array has sixteen distinct cross patterns.
- Which 16-bit de Bruijn sequences, cut into four rows of four, give valid 2-D arrays, and why?
- Find a three-colour 2-D de Bruijn array for the window.
- For a given comb, decide whether a suitable sequence exists.