Grid-Based Circuits from de Bruijn Sequences

Year: 2019 Authors: Karl Kattchee

Core claim

De Bruijn sequences induce grid-based circuits whose low-order cases can be classified and whose forms generate visually rich compositions.

Topics

de Bruijn sequences, grid-based design, classification, art composition

Domains

combinatorics, permutations, binary sequences, graphical paths, mathematical art, generative design, hand-drawn illustration, visual composition

Methods

classification by order, permutation rotation, complement transformation, brute-force search

Media

hand-drawn illustrations, grid diagrams, array notation, digital figures

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 2019 Conference Proceedings

Grid-Based Circuits from de Bruijn Sequences

Karl Kattchee

Mathematics, University of Wisconsin-La Crosse, USA; kkattchee@uwlax.edu

Abstract

We define a new kind of grid-based design called a de Bruijn circuit and begin a classification scheme. The text is accompanied by hand-drawn illustrations of de Bruijn circuits, which naturally become more interesting in higher orders. We conclude with a composition based on the de Bruijn circuit forms.

Introduction

At the end of my 2018 Bridges paper “Art of de Bruijn Sequences” [2], I proposed that the permutations which arise naturally from de Bruijn sequences could be deployed in the same manner as in the 2016 paper “Combinatorial Poppies” [3], jointly authored with Craig Kaplan. This paper pursues that idea.

In Figure 1, we see an example of a combinatorial poppy together with a diagram which describes the way it is constructed. Each row of the $2\times 6$ array is a permutation of the numbers 0, 1, 2, 3, 4, 5. Each column (and forward-leaning diagonal) specifies a location on the $6\times 6$ grid. Moving left to right, we form a path through the points $(1,0)$ , $(4,0)$ , $(4,3)$ , $(0,3)$ , $(0,1)$ , etc. The first segment goes across the top row.

Figure 1: A Combinatorial Poppy

We will denote permutations of $0,1,2,\dots ,m$ by Greek letters and write $\alpha =(a_0,a_1,a_2,\dots ,a_m)$

The permutations which induced the $6\times 6$ poppies were alternating in the sense that

and, moreover, they alternated between values above and below $5/2$ .

The permutations we work with in this paper arise from de Bruijn sequences. Recall that a de Bruijn sequence of order $n$ is a binary sequence of length $2^n$ with the property that the list of its contiguous substrings of length $n$ forms a complete list of all binary strings of length $n$ (including wraparound). In his landmark article [1], de Bruijn verified that the number of de Bruijn sequences of order $n$ (then called “ $P_n$ -cycles”) is

Kattchee

Since every substring of length $n$ can be interpreted as a base-two number, we can convert them to decimal form and get a permutation of $0,1,2,\dots ,2^n-1$ , which we will call a de Bruijn permutation. For example, the string 0011 is a de Bruijn sequence of order 2 and gives rise to the permutation $\alpha =(0,1,3,2)$ . It must be the only de Bruijn sequence of order 2, since $f(2)=1$ in de Bruijn’s result (1). Even simpler is the string 01, the only order-1 de Bruijn sequence, whose corresponding de Bruijn permutation is simply $\beta =(0,1)$ .

Figures 2a and 2b display the closed paths which correspond to the arrays $\left(\begin{array}{ll}0& amp;1\\ 0& amp;1\end{array}\right)$ and $\left(\begin{array}{lllc}0& amp;1& amp;3& amp;2\\ 0& amp;1& amp;3& amp;2\end{array}\right)$ , respectively. Since the rows are de Bruijn permutations, we call them de Bruijn arrays, and the corresponding closed paths are called de Bruijn circuits.

Figure 2: de Bruijn circuits

Note that the array $\left(\begin{array}{lllc}2& amp;0& amp;1& amp;3\\ 2& amp;0& amp;1& amp;3\end{array}\right)$ describes the same de Bruijn circuit as $\left(\begin{array}{lllc}0& amp;1& amp;3& amp;2\\ 0& amp;1& amp;3& amp;2\end{array}\right)$ , but if we only shift (“rotate”) the top row, there is a change in the circuit form. For example, $\left(\begin{array}{lllc}2& amp;0& amp;1& amp;3\\ 0& amp;1& amp;3& amp;2\end{array}\right)$ yields the circuit in Figure 2c.

We customarily write de Bruijn arrays so that a zero appears in the lower left entry. To indicate that a de Bruijn permutation $\alpha$ has been rotated by $k$ steps, write $\alpha +k$ . For example, if $\alpha =(0,1,3,2)$ , then $\alpha +1=(2,0,1,3)$ and we can abbreviate $\left(\begin{array}{cccc}2& amp;0& amp;1& amp;3\\ 0& amp;1& amp;3& amp;2\end{array}\right)=\left(\begin{array}{c}\alpha +1\\ \alpha \end{array}\right)$ . The reader can check that Figures 2d and 2e correspond to the arrays $\left(\begin{array}{c}\alpha +2\\ \alpha \end{array}\right)$ and $\left(\begin{array}{c}\alpha +3\\ \alpha \end{array}\right)$ .

We conclude this section with a useful definition and property:

If $\alpha =(a_0,a_1,a_2,\dots ,a_m)$ is a permutation of the digits $0,1,2,\dots ,m$ , then the complement is defined by $\overline{\alpha }=(m-a_0,m-a_1,m-a_2,\dots ,m-a_m)$ .

It is not hard to see that if $\alpha$ is a de Bruijn permutation, then $\overline{\alpha }$ is also a de Bruijn permutation. For example, the de Bruijn permutation $\alpha =(0,1,2,5,3,7,6,4)$ arises from the order-3 de Bruijn sequence 00010111. If we swap 0s and 1s, we get a new de Bruijn sequence 11101000, whose associated de Bruijn permutation is the complement $\overline{\alpha }=(7,6,5,2,4,0,1,3)$ , which can in turn be considered as the permutation $\beta +5$ , where $\beta =(0,1,3,7,6,5,2,4)$ .

Classification in Order One and Order Two

Since $\beta =(0,1)$ is the only de Bruijn permutation of order 1, the only arrays we need to consider are $\left(\begin{array}{c}\beta \\ \beta \end{array}\right)=\left(\begin{array}{cc}0& amp;1\\ 0& amp;1\end{array}\right)$ and $\left(\begin{array}{c}\beta +1\\ \beta \end{array}\right)=\left(\begin{array}{cc}1& amp;0\\ 0& amp;1\end{array}\right)$ . Both of those arrays correspond to the circuit in Figure 2a, and the order-1 case is settled. It’s just a square.

Similarly, we know that Figures 2b, 2c, 2d, and 2e comprise the full set of de Bruijn circuits of order 2, since $\alpha =(0,1,3,2)$ is the only de Bruijn permutation of order 2, and we only need to consider the arrays

Grid-Based Circuits from de Bruijn Sequences

$\left(\begin{array}{c}\alpha \\ \alpha \end{array}\right),\left(\begin{array}{c}\alpha +1\\ \alpha \end{array}\right),\left(\begin{array}{c}\alpha +2\\ \alpha \end{array}\right),$ and $\left(\begin{array}{c}\alpha +3\\ \alpha \end{array}\right)$ . These four circuits are pictured in Figure 2. But, since they differ by orientation and not in structure, we really only have one de Bruijn circuit of order 2. This completes the classification in order 1 and order 2.

Classification in Order Three

To handle the order-3 case, note that there are only two de Bruijn sequences of order 3 (because $f(3)=2$ ), and they are 00010111 and 00011101. The associated de Bruijn permutations are $\alpha =(0,1,2,5,3,7,6,4)$ and $\beta =(0,1,3,7,6,5,2,4)$ . As noted above, they are complements of each other, up to a rotation. In particular,

A brute-force search for all possible order-3 de Bruijn circuits is feasible. Nevertheless, we claim that it is sufficient to focus our search to arrays of the form $\left(\begin{array}{c}\beta +k\\ \alpha \end{array}\right)$ . To see why this is the case, consider an arbitrary de Bruijn circuit induced by the de Bruijn array $\left(\begin{array}{c}\delta \\ \gamma \end{array}\right)$ . The reader can verify the following:

$\left(\begin{array}{l}\delta \\ \gamma \end{array}\right)\to \left(\begin{array}{l}\tilde{\delta }\\ \gamma \end{array}\right)$ is a horizontal flip (Figure 2b $\to$ Figure 2d, for example); $\left(\begin{array}{c}\delta \\ \gamma \end{array}\right)\to \left(\begin{array}{c}\delta \\ \overline{\gamma }\end{array}\right)$ is a vertical flip; and $\left(\begin{array}{c}\delta \\ \gamma \end{array}\right)\to \left(\begin{array}{c}\tilde{\delta }\\ \overline{\gamma }\end{array}\right)$ is a $180^{\circ }$ rotation.

Now, by means of one of these transformations, any de Bruijn circuit of the form $\left(\begin{array}{c}\alpha +k\\ \alpha \end{array}\right),\left(\begin{array}{c}\beta +k\\ \beta \end{array}\right)$ , or $\left(\begin{array}{c}\alpha +k\\ \beta \end{array}\right)$ can be converted into the form $\left(\begin{array}{c}\beta +k\\ \alpha \end{array}\right)$ without changing the type of circuit, only its orientation. Figure 3 shows the four distinct de Bruijn circuits of that form, and the classification of order 3 is complete.

(a) $\left(\begin{array}{l}\beta \\ \alpha \end{array}\right)$

(b) $\left(\begin{array}{l}\beta +2\\ \alpha \end{array}\right)$

(c) $\left(\begin{array}{c}\beta +6\\ \alpha \end{array}\right)$

(d) $\left(\begin{array}{c}\beta +7\\ \alpha \end{array}\right)$ Figure 3: de Bruijn circuits of order 3

Order Four

There are $f(4)=16$ de Bruijn sequences of order 4, so classification in this case is a larger task, and we’ll leave that to a future project. In the meantime, note that the 16 de Bruijn permutations of order 4 organize themselves into 8 complementary pairs. For example, the two de Bruijn sequences 0000111101001011 and 0000101101001111 induce the permutations $\alpha =(0,1,3,7,15,14,13,10,4,9,2,5,11,6,12,8)$ and $\beta =(0,1,2,5,11,6,13,10,4,9,3,7,15,14,12,8)$ , which are complements of each other in the sense that $\overline{\alpha }=\beta +4$

Kattchee

and $\overline{\beta }=\alpha +12$ . The beginning of a classification of order-4 de Bruijn circuits appears in Figure 4, where the de Bruijn circuits $\left(\begin{array}{c}\beta \\ \alpha \end{array}\right),\left(\begin{array}{c}\beta +2\\ \alpha \end{array}\right),\left(\begin{array}{c}\beta +4\\ \alpha \end{array}\right),\dots ,\left(\begin{array}{c}\beta +14\\ \alpha \end{array}\right)$ are gathered. Those are all the distinct ones of that form. One begins to see recurring motifs in the de Bruijn circuit forms.

Figure 4: Order four de Bruijn Circuits

Order Five and Conclusion

To conclude this paper, we present an example, in Figure 5, from among the vast number of de Bruijn circuits of order 5. It is accompanied by a lively image composed of de Bruijn circuit forms, one of my first artworks based on the concept.

Figure 5: Order five example and artistic composition

References

[1] N. G. de Bruijn. “A Combinatorial Problem.” Koninklijke Nederlandsche Akademie Van Wetenschappen, vol. 49, no. 6, 1946, pp. 758-764. [2] K. Kattchee. “Art of de Bruijn Sequences.” Bridges Conference Proceedings, Stockholm, Sweden, July 25-29, 2018, pp. 447-450. https://archive.bridgesmathart.org/2018/bridges2018-447.. [3] 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..