Art of de Bruijn Sequences

Year: 2018 Authors: Karl Kattchee

Core claim

De Bruijn sequences can be transformed into mathematical art through circular renderings, graph drawings, and grid-based circuits.

Topics

de Bruijn sequences, binary strings, grid-based design, mathematical art

Domains

combinatorics on words, graph theory, Hamilton circuits, permutations, mathematical art, generative drawing, grid-based design, circular composition

Methods

sequence enumeration, graph representation, radial rendering, permutation-based circuit design

Media

binary strings, drawings, grids, circles

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2018 Conference Proceedings

Art of de Bruijn Sequences

Karl Kattchee

Mathematics and Statistics, Univ of Wisconsin-La Crosse, USA; kkattchee@uwlax.edu

Abstract

It is possible to pack all binary strings of length $n$ into a sequence of length $2^n$ . A sequence with this remarkable property is called a de Bruijn sequence. In this paper, we discuss the basics of de Bruijn sequences and present some drawings and grid-based designs inspired by them.

de Bruijn Basics

In his 1946 paper [1], N. G. de Bruijn used the term $P_n$ -cycle to refer to a binary string of length $2^n$ with the property that its contiguous substrings of length $n$ are all different (taking “wraparound” into account). It follows that every binary string of length $n$ appears as a substring.

The binary string 00011101, for example, is a $P_3$ -cycle, since its substrings of length three,

form the complete list. Note that $P_n$ -cycles are ideally represented in circular form (see Figure 1), so we should be careful not to distinguish between $P_n$ -cycles which only differ by a “rotation.”

Figure 1: The $P_3$ -cycle 00011101 in circular form. Read clockwise to correspond to (1).

We will customarily write $P_n$ -cycles starting with $n$ zeros.

The $P_n$ -cycles have come to be known as de Bruijn sequences of order $n$ . They have been researched extensively and have found many applications in computer sciences. We will look for clever ways to use them for purposes of art and design.

de Bruijn’s Main Result

The only de Bruijn sequence of order one is 01, and the only de Bruijn sequence of order two is 0011. The main result of de Bruijn’s paper settled the conjecture that the number of de Bruijn sequences of order $n$ equals $2^{2^{n-1}-n}$ . See Table 1.

The two de Bruijn sequences of order three are 00011101 and 00010111. Since each of these can be obtained from the other by reversing the order, they contain the same information, so in some sense there is really only one de Bruijn sequence of order three.

Kattchee

Table 1: Number of de Bruijn Sequences of Order n

Table 2 displays four of the 16 de Bruijn sequences of order four. Four more of them are found by reversing the order of each sequence in Table 2. By swapping 0’s and 1’s in each of these eight, we acquire the rest of the order-four de Bruijn sequences. We thus have four equivalence classes under the relation of order-reversal and/or 0-1-swapping. The sequences in Table 2 are representatives of these equivalence classes, chosen because they are the least in their class in lexicographic order.

Table 2: Four de Bruijn Sequences of Order 4 with Corresponding Permutations

Each sequence in Table 2 is accompanied by a list of numbers which are decimal forms of its consecutive length-four substrings. Because of the defining property of de Bruijn sequences, these lists are permutations. The drawing in Figure 2 below is derived from the information in Table 2. With the clue that open central circles represent 0’s and solid central dots represent 1’s, the reader is invited to try and decode the sketch. The idea of the sketch is to present an array of seemingly random information that is in fact precisely determined.

Figure 2: A Drawing Based on the Order-Four Equivalence Classes

According to Table 1, there are 2048 de Bruijn sequences of order 5. One example is

00000111110101001101100101110001,

and it is featured in Figure 3 below. The drawing consists of five concentric circular versions of the entire sequence (black=0 and white=1). As you work your way outwards, each sequence is rotated by one. Consequently, all length-five binary strings are radiating out from the center. I was inspired by images of a similar type found in [3, pp. 570-71].

de Bruijn Graphs

The proof of de Bruijn’s main result relies on de Bruijn graphs. The order-three de Bruijn graph is neatly rendered in Figure 4a. The vertices are the eight binary strings of length three, and a directed edge connects two different vertices if the initial string can be transformed into the terminal string by deleting the first digit and adding a new digit to the end. Each de Bruijn sequence of order three corresponds to a Hamilton circuit.

Art of de Bruijn Sequences

Figure 3: An Order-Five de Bruijn Sequence Displayed Radially

For example, the list of strings in Eq. (1) describes a Hamilton circuit on Figure 4a which corresponds to the de Bruijn sequence 00011101.

(a)

(b) Figure 4: de Bruijn graphs: (a) order three (b) order four.

The order-four de Bruijn graph has 16 vertices. It can also be rendered neatly, but I’ve made no attempt to do so in the drawing shown in Figure 4b. I’ve also ignored vertex labeling. The result is intriguing.

Grid-Based Designs

In “Combinatorial Poppies” [2, Bridges 2016], the author and Craig Kaplan devised a way to take a pair of permutations and form a grid-based design. Because the permutations were “alternating,” the resulting forms resembled poppies. See Figure 5 for an example, and refer to the article for details.

The permutations which arise from de Bruijn sequences (see Table 2) are not alternating, but the same scheme as used in [2] can be employed to create a new kind of grid-based form. Figure 6a shows the closed path which arises from the array $\left(\genfrac{}{}{0ex}{}{01376524}{01253764}\right)$ , whose rows are the permutations corresponding to the two order-three de Bruijn sequences (namely, 00010111 and 00011101).

The de Bruijn sequences of order four can be similarly employed. Figure 6b is the path deter

Kattchee

(140325) 031524

Figure 5: A Combinatorial Poppy

(a)

(b)

(c) Figure 6: Grid-Based Circuits: (a) derived from the two order-three de Bruijn sequences, (b) derived from 0000111100101101 and 0000111101001011, (c) derived from 0000110101111001 and 0000110111100101.

mined by the array $\left(\begin{array}{cccccccccccccccc}0& amp;1& amp;3& amp;7& amp;15& amp;14& amp;12& amp;9& amp;2& amp;5& amp;11& amp;6& amp;13& amp;10& amp;4& amp;8\\ 0& amp;1& amp;3& amp;7& amp;15& amp;14& amp;13& amp;10& amp;4& amp;9& amp;2& amp;5& amp;11& amp;6& amp;12& amp;8\end{array}\right)$ and Figure 6c shows the path determined by $\left(\begin{array}{cccccccccccccccc}0& amp;1& amp;3& amp;6& amp;13& amp;10& amp;5& amp;11& amp;7& amp;15& amp;14& amp;12& amp;9& amp;2& amp;4& amp;8\\ 0& amp;1& amp;3& amp;6& amp;13& amp;11& amp;7& amp;15& amp;14& amp;12& amp;9& amp;2& amp;5& amp;10& amp;4& amp;8\end{array}\right)$ . These drawings arose from my experiments constructing circuits derived from pairs of de Bruijn sequences that reside in the same equivalence class.

Conclusion and Acknowledgement

In general, combinatorics is fertile ground for mathematical art. The topic of de Bruijn sequences resides in the field of combinatorics on words, and it has inspired me to try some new ideas in drawing. I thank the referees for improving this paper with their suggestions.

References

[1] N. G. de Bruijn. “A Combinatorial Problem.” Koninklijke Nederlandsche Akademie Van Wetenschappen, vol. 49, no. 6, 1946, pp. 758-764. [2] C. S. Kaplan and K. Kattchee. “Combinatorial Poppies.” Bridges Conference Proceedings, Jyväskylä, Finland, Aug. 9-13, 2016, pp. 111-118. http://archive.bridgesmathart.org/2016/bridges2016-111.. [3] B. Stevens, A. Williams. “The Coolest Way to Generate Binary Strings.” Theory Comput. Syst., Vol. 54 (2014), pp. 551-577.