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.

Version: v1 · 2026-10-07 · History
Domain-specific #: 13852
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Combinatorics on Words, Combinatorial Design → Mathematics
Aliases: De Bruijn Array

Core Idea¶

A De Bruijn torus is a two-dimensional periodic array over a finite alphabet whose translated windows cover every possible fixed-size pattern exactly once in one fundamental period. Choose an alphabet of size k, a window of m rows by n columns, and periods r and s. Starting at each of the rs positions modulo those periods produces one m × n window. The array is a De Bruijn torus when that position-to-window assignment is a one-to-one correspondence with all k^(mn) possible windows. Consequently rs = k^(mn), and an error-free complete window determines one coordinate modulo the periods.^[1]^[2]

The formal object is the whole periodic array, whether described as a wrapped finite block or its infinite repetition. A generated digital torus can be used as a position code: Schüsselbauer and colleagues made a large exact binary torus and printed parts of its dot pattern for a tabletop sensor. The printed sheet is a slice decoded against the full array; it need not itself contain every window or physically wrap around.^[1]^[2]

Structural Signature¶

Finite symbol alphabet. The k possible cell values set the universe of windows. Changing the alphabet changes the inventory to be covered.^[1]
Two-axis periodic carrier. A fundamental r × s block is read modulo both periods. Windows crossing its apparent right or bottom edge continue across the opposite edge; without both wraparound directions, it is a different object.^[1]
Fixed window shape. One declared m × n local block is read at every starting coordinate. Changing either dimension changes the patterns and the construction problem.^[1]
Translated position-to-window map. Each period coordinate determines exactly one ordered window under the same reading rule. This is the required Function Mapping constituent, prior to judging its coverage.^[1]
Exact-once inventory. The map has neither repeated window values nor missing possible values. At-most-once uniqueness alone would be insufficient; all k^(mn) windows must appear.^[1]^[3]
Inverse coordinate readout. Because of exact-once coverage, a correctly observed full window can be mapped back to its unique period coordinate. This follows from the object; sensing, printing and error handling are optional applications, not defining roles.^[1]^[2]

What It Is Not¶

A De Bruijn torus is not merely an array whose windows happen to be different. Sub-perfect maps require at most one occurrence of each local pattern; they may omit many possible patterns. PuzzleBoard's position-coding map is explicitly sub-perfect, despite using a similar local-uniqueness idea. Conversely, an exact torus permits all possible windows and therefore cannot reserve an unused window as an automatic one-bit error flag.^[3]^[2]

It is not a physical donut, a single printed page, or the one-dimensional De Bruijn sequence. “Torus” refers to periodic indexing in two directions. A sheet bearing a finite part of a digital torus can support lookup against the full digital codebook, but that sheet alone lacks the full periodic inventory. A one-dimensional cyclic word has one modular coordinate, so it is a related boundary rather than this two-axis object.^[1]^[2]

Scope of Application¶

The literal home is combinatorial design of periodic arrays and complete local-pattern inventories. A construction theorem can establish existence for a particular alphabet, window shape and period pair; an explicit block can be checked by enumerating every wrapped window. Hurlbert and Isaak construct at least one suitable two-dimensional period for every natural alphabet size and window dimensions. That does not mean every desired period pair is feasible: the product is fixed and prescribed period shapes need their own conditions or construction.^[1]

Position coding is a second literal use of the same formal object. Dothraki generates a binary 8192 × 4096 torus with each of the 2^25 possible 5 × 5 windows once, then reads a printed portion with an optical mouse sensor to locate a tangible on a tabletop. The exact mathematical guarantee applies to the generated array and correctly read windows; the physical capture and decoding steps have additional conditions.^[2]

Clarity¶

The key distinction is distinct observed patches versus exhaustive exact coverage. A sub-perfect design can let a device identify where it is among the patches actually present without being a De Bruijn torus. To classify an array, list the entire target universe of k^(mn) windows, then check both missing patterns and duplicate positions. If every period position is distinct but rs is smaller than that universe, the design is a useful position code but not an exact torus.^[1]^[3]

A second distinction separates mathematical coordinates from sensor outputs. The exact array makes an ideal complete window identify one position. A sensor can misread a printed value; exactness does not certify its observation. Dothraki therefore compares four overlapping 5 × 5 windows from a sensed 6 × 6 patch, accepts a position when at least three indicate neighboring locations, and withholds it when the decoded locations are dispersed. That extra check belongs to the application, not to the torus definition.^[2]

Manages Complexity¶

The torus rule compresses an enormous pattern list into four parameters, a fundamental block, and one test: read each window modulo the periods and compare the resulting multiset with the complete window universe. The equation rs = k^(mn) is a necessary size check; a construction or exhaustive verification must still establish the no-repeat and no-gap property. This separates a plausible array dimension from a proven exact design.^[1]

The inverse map also compresses location search. In Dothraki, one decoded local window can be looked up in the generated digital torus instead of identifying location from a large visual landmark. The implementation's generation and lookup algorithms, print resolution and overlapping-window consistency add work beyond the formal invariant; the abstraction tells which part of that work supplies unique coordinates.^[2]

Abstract Reasoning¶

Given a proposed torus, specify alphabet, periods and window dimensions first. Count whether the period has exactly as many starting coordinates as possible windows. Enumerate or prove the translated position-to-window map, including windows that cross both boundaries. A collision or an omitted pattern defeats the exact-once claim. When the map passes, invert it to infer a unique coordinate from a correctly read full window; the inference is modulo the periods, not an unlimited physical position claim.^[1]^[2]

A construction question adds a second branch. Hurlbert and Isaak's theorem shows that some period is available for each natural k, m and n; asking for one chosen r × s shape requires checking the theorem or another construction's conditions. This corrects the seed's broad suggestion that alphabet and window dimensions alone may lack any torus. Historical statements about particular prescribed periods should not be read as an exhaustive present-day map of open cases.^[1]

Knowledge Transfer¶

Within combinatorics, the same exact-once test transfers from the small binary 4 × 4 example to a much larger 8192 × 4096 binary construction. Their window sizes and construction methods differ, but both use two modular axes and a complete position-to-window correspondence. Within position encoding, the Dothraki codebook lets a printed finite region carry globally distinguishable local patches when the sensor can capture and decode them reliably. The decoding method and physical error rates do not transfer automatically from the small formal example.^[1]^[2]

Beyond this domain, the portable constituents are Function Mapping and Invariance: a rule relates positions to outputs, and repeating a block preserves the array under period translations. That does not make every periodic signal or every one-to-one identifier a De Bruijn torus. The specific alphabet, two-dimensional windows and exact complete inventory remain the domain-bound structure.^[1]

Examples¶

Small formal binary torus. A binary 4 × 4 torus with 2 × 2 windows has 16 period positions and 16 possible windows; Hurlbert and Isaak's construction theorem specializes to this parameter set, and Dothraki illustrates such a block. Mapped back: alphabet = {0,1}; periodic carrier = 4 rows by 4 columns read modulo 4; window = 2 × 2; position-to-window map = one wrapped block at each of 16 starts; exact inventory = every binary 2 × 2 pattern once; inverse readout = each complete pattern names one modulo-(4,4) coordinate. This is a formal exact object, not a claim about sensor performance.^[1]^[2]

Dothraki position-code torus. Its generated binary array has periods 8192 and 4096, so 33,554,432 positions match the 2^25 possible 5 × 5 binary windows. A mouse sensor observes a printed part and the system looks up the recovered local pattern against the digital codebook. Mapped back: alphabet = binary black/white values; periodic carrier = the full generated digital array; window = 5 × 5; position-to-window map = one pattern per toroidal coordinate; exact inventory = every 5 × 5 pattern once; inverse readout = a correctly decoded patch gives a codebook coordinate. The physical sheet is a slice, and recognition can fail.^[2]

Structural Tensions¶

T1 — Desired period shape versus exact construction. An application may want a particular aspect ratio, while exact coverage fixes the period product and a prescribed pair needs a valid construction. Choosing freely on one axis constrains the other and may fall outside known conditions. Diagnostic: Has this specific period pair been constructed, or only some torus for the alphabet and window dimensions?^[1]

T2 — Code capacity versus readable patch size in an application. Increasing window area grows the possible-position inventory exponentially, but a fixed sensor field and print resolution limit how many cells can be read reliably. Dothraki chose 5 × 5 windows with a larger sensed 6 × 6 region to permit overlapping checks rather than rely on a single maximal window. This is an engineering tension, not a theorem about all tori. Diagnostic: Can the sensor read the required whole window and enough context to validate it?^[2]

T3 — Exact mathematical uniqueness versus noisy recognition. Every legal window appears, so a corrupted window can itself be another legal window and point somewhere else. Dothraki trades some simple single-window decoding for an agreement test among overlaps and may emit no coordinate when they conflict. This tension arises when an exact torus is used through a fallible channel. Diagnostic: Is the claimed coordinate derived from an ideal pattern or a validated physical reading?^[2]

Structural–Framed Character¶

The entry sits near the structural end of the structural–framed spectrum: a finite alphabet, modular translation and exact-once inventory are mathematically checkable without a favored application. Evaluative weight appears in judgments such as whether a code is convenient or robust, not in whether the array meets its definition. Human-practice dependence arises in choosing parameters, constructing a codebook and printing or sensing it; the invariant itself is independent of those practices. Institutional origin does not enter the membership test.^[1]^[2]

Vocabulary travel is literal between combinatorial construction and two-dimensional position coding because both use the same array and window relation. It ceases to be literal when “torus” is applied to a merely periodic signal or “De Bruijn” to an at-most-once position pattern. Import versus recognition: an analyst recognizes this class by checking two periodic axes and exhaustive exact window coverage, not by importing a prestige label from a paper title. Its character: a strongly structural but domain-specific combinatorial object whose physical uses add contingent sensing and error conditions.^[1]^[2]^[3]

Structural Core vs. Domain Accent¶

The core is the complete correspondence between toroidal starting positions and all fixed-size local patterns over a finite alphabet. The two-dimensional periodic carrier and window operation make this a specific combinatorial design, not merely a generic code or uniqueness property. Dothraki's optical mouse, dot size, paper, lookup routine and overlapping error check are application accents. The exact coverage of its generated array is part of the core; successful recognition on every print is not.^[1]^[2]

Function Mapping and Invariance are the live Prime constituents that travel broadly: many things map inputs to outputs, and many structures stay unchanged under transformations. This named entry does not clear the Prime bar because its diagnostic and construction mechanism require an alphabet array, two modular coordinates, a declared local window and complete enumeration of that window universe. Remove those commitments and only the parent skeletons remain.^[1]

This entry is part of Function (Mapping) and is part of Invariance.

The strict child-to-Function Mapping edge is composition/part of, parent in child. A coordinate determines one window under a declared rule; exact-once coverage is a special constraint on this required function. The torus is an array with additional periodic and enumeration commitments, so it is not taxonomically just a mapping. Function mappings also exist without tori.^[1]

The strict child-to-Invariance edge has the same composition direction. Repeating the block preserves cell values and window structure under translations by either period. Without that two-axis invariance, a finite distinct-window grid would lose the toroidal identity. Invariance occurs independently in geometry and other settings. Periodicity is related in ordinary language, but its live full signature includes signal-centered roles that were not imposed on this formal array. Injectivity and Surjectivity describe the no-collision and no-gap halves of the position-to-window map; they are explanatory related primes, while the accepted strict edges identify the mapping and periodic invariance constituents.^[1]

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)

Show alternative path (1)

Neighborhood in Abstraction Space¶

De Bruijn Torus sits in a sparse region of the domain-specific corpus (93^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Sub-perfect map, including PuzzleBoard's code: observed windows may be distinct while some possible windows are absent; exact completeness is the decisive test.^[3]
A finite printed slice: it can be decoded against a complete digital torus without itself wrapping or covering all patterns.^[2]
A one-dimensional De Bruijn sequence: one modular index and contiguous words replace two axes and rectangular windows.^[1]
An arbitrary periodic binary picture: repeating a block supplies periodicity but does not prove every possible window occurs once.^[1]
An error-correcting code by definition: ideal uniqueness supplies coordinate lookup, while noisy sensing needs additional checks or redundancy.^[2]

References¶

[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z

[2] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s

[3] 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. registry ↩a ↩b ↩c ↩d ↩e