De Bruijn Torus¶
A two-dimensional periodic symbol array in which every possible fixed-size window appears exactly once per period, so each window identifies one position.
Core Idea¶
A De Bruijn torus is a two-dimensional symbol array read with wraparound in both directions. Pick a fixed window size. Within one full period, every possible window of that size appears exactly once. Thus a correctly read complete window identifies one position in the array. With k symbols and m × n windows, there are k^(mn) possible patterns, so a complete torus has that many starting positions in one period.[ref-98ba14249301][ref-65666557ed96]
Constitutive roles. The alphabet supplies the possible cell values; two modular periods give the wraparound array; the fixed window states what is read; the position-to-window map assigns one pattern to each starting coordinate; and exact-once coverage forbids both repeats and omissions. Unique position lookup follows from these roles. Printing and sensing are uses of the array, not requirements for its existence.[^ref-98ba14249301]
Scope of Application¶
Combinatorics studies how to construct and verify these exact periodic arrays. Hurlbert and Isaak show that some two-dimensional period can be constructed for every natural alphabet size and window dimensions, while a requested specific period shape still needs its own feasibility check.[^ref-98ba14249301]
Position coding uses the same object. Dothraki generates a binary 8192 × 4096 torus containing every possible 5 × 5 window once, then prints portions as dot patterns for a tabletop sensor. The generated digital array is the complete torus; a printed page can be only a slice of it.[^ref-65666557ed96]
Clarity¶
At most once and exactly once answer different questions. PuzzleBoard's sub-perfect map can identify positions among the patterns it uses, but it does not contain every possible pattern and therefore is not a De Bruijn torus. The exact test asks whether the entire possible-window inventory appears once in the whole period.[ref-10a32f30a395][ref-98ba14249301]
Ideal window uniqueness is also different from error-free sensor recognition. Dothraki accepts a location when at least three of four overlapping decoded windows indicate neighboring positions; dispersed results cause it to withhold a location. The extra consistency rule handles physical reading errors, which the torus definition alone does not prevent.[^ref-65666557ed96]
Manages Complexity¶
The rule replaces a long list of patterns with an alphabet, two periods, one window shape and a coverage check. The number-of-cells equation is necessary, but it does not prove that no window repeats. A construction or enumeration must still show the exact-once relation. Once shown, one local pattern can serve as a coordinate key for the full array.[ref-98ba14249301][ref-65666557ed96]
Abstract Reasoning¶
To test a proposed torus, first compute the number of possible windows and compare it with the number of period positions. Read windows modulo both periods, including ones crossing an edge. If any pattern repeats or any possible pattern is absent, the candidate fails. If each appears once, a complete correctly read window determines its coordinate modulo the periods. A sensor needs its own evidence that the window was read correctly.[ref-98ba14249301][ref-65666557ed96]
Knowledge Transfer¶
The exact-once test applies literally to both a small binary 4 × 4 mathematical torus and Dothraki's large digital position code. Their sizes and uses differ; neither example makes a finite printed slice a complete torus or guarantees perfect physical recognition. Function Mapping and Invariance are the broader Prime constituents, while the two-dimensional alphabet-and-window construction remains domain-specific.[ref-98ba14249301][ref-65666557ed96]
Example¶
Formal 4 × 4 torus. With binary values and 2 × 2 windows, 16 wrapped starting coordinates match the 16 possible patterns. Hurlbert and Isaak's theorem supplies this parameter case, and Dothraki illustrates it. Mapped back: alphabet = two values; periods = 4 and 4; window = 2 × 2; position-to-window map = one wrapped block at every start; exact inventory = all 16 patterns once; inverse = a pattern names one modulo-(4,4) position.[ref-98ba14249301][ref-65666557ed96]
Dothraki torus. Its full generated binary 8192 × 4096 array has one position for each of the 2^25 possible 5 × 5 patterns. Mapped back: alphabet = two values; periods = 8192 and 4096 in the digital array; window = 5 × 5; map = one pattern per coordinate; inventory = all patterns once; inverse = a correctly decoded printed patch identifies a digital coordinate. The printed sheet is a portion of this array.[^ref-65666557ed96]
Relationships to Other Abstractions¶
Current abstraction De Bruijn Torus Domain-specific
Parents (2) — more general patterns this builds on
-
De Bruijn Torus is part of Function (Mapping) Prime
A fixed translation rule maps each torus coordinate to one window; exact-once coverage is a property of that required map.
-
De Bruijn Torus is part of Invariance Prime
Repeating the fundamental block preserves the infinite array under translations by either period, a required two-axis invariance.
Hierarchy paths (2) — routes to 2 parentless roots
- De Bruijn Torus → Function (Mapping)
- De Bruijn Torus → Invariance
Neighborhood in Abstraction Space¶
De Bruijn Torus sits in a sparse region of the domain-specific corpus (93rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Factor Complexity Function — 0.81
- Block walking — 0.79
- Turing Machine — 0.79
- Finite subdivision rule — 0.78
- Aztec Diamond — 0.78
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Sub-perfect position map: local patterns may be unique among those present without covering every possible pattern.[^ref-10a32f30a395]
- One-dimensional De Bruijn sequence: a cyclic word has one periodic axis, not two.[^ref-98ba14249301]
- A printed torus slice: it can be read against a complete digital codebook without itself wrapping around.[^ref-65666557ed96]
- An inherently error-correcting code: exact coverage gives ideal unique positions; noisy reading requires added checks.[^ref-65666557ed96]
References¶
[^ref-98ba14249301]: Glenn Hurlbert and Garth Isaak, “New Constructions for De Bruijn Tori”, Designs, Codes and Cryptography 6 (1995), 47–56, doi:10.1007/BF01390770. Full original author manuscript inspected. Its introduction, PDF pp. 1–2, defines the periodic k-ary array, fundamental block and exact-once window relation; Theorem 1.1 on PDF p. 2 gives a two-dimensional construction for every natural alphabet size and window dimensions with a specified period. Sections 2–3 give distinct construction mechanisms. The 4 × 4 binary, 2 × 2-window case follows by specializing the theorem's parameters.
[^ref-65666557ed96]: Dennis Schüsselbauer, Andreas Schmid and Raphael Wimmer, “Dothraki: Tracking Tangibles Atop Tabletops Through De-Bruijn Tori”, TEI 2021, article 37, doi:10.1145/3430524.3440656. Full original author version inspected. Figure 3 and §4.1, PDF p. 4, show the 4 × 4 example and define the exact binary torus; §4.1, PDF pp. 4–5, describes the generated 8192 × 4096, 5 × 5-window torus and printed excerpt; §§4.2–4.3, PDF pp. 5–6, describe patch capture, overlapping checks and decoding; §5 reports fallible physical recognition.
[^ref-10a32f30a395]: Peer Stelldinger, Nils Schönherr, and Justus Biermann (2024), “PuzzleBoard, A New Camera Calibration Pattern with Position Encoding”, original manuscript, arXiv:2409.20127. The original work is titled “PuzzleBoard: A New Camera Calibration Pattern with Position Encoding.” Full original article inspected. Section 3 distinguishes at-most-once sub-perfect maps from exactly-once perfect maps and states that PuzzleBoard uses a 501 × 501 sub-perfect map; it is a near-miss counterexample here, not an exact-torus positive.