De Bruijn episode

De Bruijn sequence for k  = 2 and n  = 2.

A De Bruijn sequence is a word of an alphabet with symbols with the following property: Every possible word of length formed from the symbols in appears as a connected partial word of , and is the shortest word with this property. is called the order of . There is no distinction between different ones that emerge from one another through cyclical swapping of the symbols. A De Bruijn sequence contains all words of length from symbols (in connected form) exactly once, whereby the word is viewed cyclically, i.e. the symbols at the end may be continued with those at the beginning to form a partial word. ${\displaystyle B(k,n)}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle k}$

Bulk

De Bruijn sequences exist for each . An example is for (two symbol alphabet, 0 and 1) and the De Bruijn sequence . Here all the words are the length before: . For there are two possible de Bruijn sequences: and . Every De Bruijn sequence has length , and there are different De Bruijn sequences of order . ${\displaystyle (n,k)}$ ${\displaystyle k=2}$ ${\displaystyle n=2}$ ${\displaystyle B=(0,0,1,1)}$ ${\displaystyle n=2}$ ${\displaystyle (0,0),(0,1),(1,1),(1,0)}$ ${\displaystyle n=3}$ ${\displaystyle (00010111)}$ ${\displaystyle (11101000)}$ ${\displaystyle k^{n}}$ ${\displaystyle {\frac {(k!)^{k^{n-1}}}{k^{n}}}}$ ${\displaystyle n}$

De Bruijn sequences can be represented graphically as Euler paths or Hamilton paths of a De Bruijn graph . These are directed graphs whose nodes represent all words of length from the alphabet with symbols, and whose nodes are connected if these words overlap. For and all nodes are, for example, up to and connected to each other. ${\displaystyle k^{n}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k=2}$ ${\displaystyle n=2}$ ${\displaystyle (0,0)}$ ${\displaystyle (1,1)}$

De Bruijn episodes have applications e.g. B. in the construction of card tricks, in cryptography , genetics and bioinformatics (for example Pavel Pevzner ), with telegraphs, error-correcting codes , computer memory hashing and robot vision . They can also be generated by shift register sequences.

generalization

Analog objects can be defined and constructed for higher dimensions , especially the case has been investigated by several authors and this is called De-Bruijn-Torus . ${\displaystyle d}$ ${\displaystyle d=2}$

It is a matrix with entries from an alphabet (often only the two symbols 0 and 1 ) that contains all possible sub-matrices (also: sub-matrices) exactly once. Opposite sides of the matrix are identified with each other, hence the name torus . For one receives De Bruijn sequences as a special case. ${\displaystyle m\times n}$ ${\displaystyle n=1}$

If one restricts oneself to quadratic, binary tori, De Bruijn tori, which contain all binary sub-matrices, can easily be constructed. The nearest square De Bruijn torus is and was designed by W.-C. Shiu inductively constructed. ${\displaystyle (4,4;2;2)_{2}}$ ${\displaystyle 2\times 2}$ ${\displaystyle (256,256;4;4)_{2}}$

De Bruijn torus

Higher De Bruijn Tori are not yet known, e.g. B. for all binary sub-matrices ( possibilities) one would need, that is just within the realm of what is feasible: if the representation requires 0.1 mm per pixel (matrix entry), one would need an area of ​​approx. 26 square meters . ${\displaystyle 6\times 6}$ ${\displaystyle 2^{36}=68719476736}$ ${\displaystyle (262144,262144;6;6)_{2}}$

Naming

De Bruijn episodes are named after Nicolaas Govert de Bruijn , who published about them in 1946 and in 1951 with Tatjana van Aardenne-Ehrenfest . De Bruijn, in turn, states that they were first treated in case k = 2 by Camille Flye Sainte-Marie in 1894. The first De Bruijn episodes appeared in ancient India in connection with Sanskrit - prosody . There were also other publications before De Bruijn, so by MH Martin (in connection with dynamics), IJ Good (1946), Karl Popper (1934), NM Korobov, by the telegraph engineer Émile Baudot (1888). They were also known to wizards, but they were often wrongly called Gray codes .

literature

• Donald Knuth The art of computer programming , 4 A, Part 1, Addison-Wesley 2011
• Hal Frederickson, Anthony Ralston A survey of full length nonlinear shift register cycle algorithms , SIAM Review, Volume 24, 1982, pp. 195-221
• Anthony Ralston De Bruijn Sequences - a model example of the interaction of discrete mathematics and computer science , Mathematics Magazine, Volume 55, 1982, pp. 131-143
• Sherman K. Stein Mathematics, the man made universe , Freeman 1963, Dover 1999, Chapter 9 (Memory Wheels), with further historical references
  • The chapter is based on an earlier version: Sherman K. Stein The mathematician as an explorer , Scientific American, May 1961, pp. 149-158

Individual evidence

1. ^ De Bruijn Graph, Mathworld
2. ↑ Persi Diaconis , Ron Graham Magical Mathematics , Princeton University Press 2012
3. ↑ Sherman Stein Mathematics, the man made universe
4. ↑ CT Fan, SM Fan, SL Ma, MK Siu On de Bruijn arrays , Ars Combinatoria, Volume 19, 1985, pp. 205-213
5. ↑ F. Chung, Persi Diaconis, Ronald Graham Universal cycles for combinatorial structures , Discrete Mathematics, Volume 110, 1992, pp. 43-59
6. ^ Wai-Chee Shiu Decoding de Bruijn arrays constructed by the FFMS method , Ars Combinatoria, Volume 47, 1997, pp. 33-48
7. ^ De Bruijn A combinatorial problem , Koninklijke Nederlandse Akademie van Wetenschappen, Volume 49, 1946, 758-764. The problem was posed by the Dutch telephone engineer K. Posthumus. De Bruijn's work is online on his homepage
8. ^ De Bruijn, Van Aardenne-Ehrenfest Circuits and trees in oriented linear graphs , Simon Stevin, Volume 28, 1951, pp. 203-217
9. ^ Report TU Eindhoven 1975
10. ↑ Sainte-Marie Solution to question No. 48 , L'Intermédiaire des Mathématiciens, Volume 1, 1894, pp. 107-110
11. ^ Rachel Hall Math for Poets and Drummers , 2007, pdf . See also Sherman Stein Mathematics, the man made universe , chapter 9. He refers to a mention in Curt Sachs Rhythm and Tempo , Norton 1953, pp. 98-101
12. ↑ Martin A problem of arrangements , Bulletin AMS, Volume 40, 1934, pp. 859-864
13. ↑ Good Normal recurring decimals , J. London Math. Soc., Volume 21, 1946, pp. 167-169, and a note on this by D. Rees, ibid., Pp. 169-172
14. ↑ He also mentions them in The Logic of Scientific Discovery , Basic Books 1959, pp. 162/163, 292
15. ↑ Korobov Normal periodic sequences , AMS Translations, Volume 4, pp. 31-58, first in Russian 1951
16. ↑ Diaconis, Graham Magical Mathematics , Princeton University Press, p. 25. Chapter 2 of the book describes a remarkable card trick referring to the magic trick inventor and chicken farmer Charles T. Jordan (1888–1944) in a 1919 publication ( Thirty Card Mysteries ) (called Coluria by him), his biography and photo can be found in the book p. 189f.