De Bruijn torus
In combinatorial mathematics, a De Bruijn torus, named after Nicolaas Govert de Bruijn, is an array of symbols from an alphabet (often just 0 and 1) that contains every m-by-n matrix exactly once. It is a torus because the edges are considered wraparound for the purpose of finding matrices. Its name comes from the De Bruijn sequence, which can be considered a special case where n is 1 (one dimension).
One of the main open questions regarding De Bruijn tori is whether a De Bruijn torus for a particular alphabet size can be constructed for a given m and n. It is known that these always exist when n = 1, since then we simply get the De Bruijn sequences, which always exist. It is also known that "square" tori exist whenever m = n and even (for the odd case the resulting tori cannot be square). ^{[1]} ^{[2]} ^{[3]}
The smallest possible binary "square" de Bruijn torus, depicted above right, denoted as (4,4;2,2)_{2} de Bruijn torus (or simply as B_{2}), contains all 2×2 binary matrices.
Contents
B_{2}
Apart from "translation", "inversion" (exchanging 0s and 1s) and "rotation" (by 90 degrees), no other (4,4;2,2)_{2} de Bruijn tori are possible - this can be shown by complete inspection of all 2^{16} binary matrices (or subset fulfilling constrains such as equal numbers of 0s and 1s) . ^{[4]}
Larger example: B_{4}
An example of the next possible binary "square" de Bruijn torus, (256,256;4,4)_{2} (abbreviated as B_{4}), has been explicitly constructed.^{[5]}
The image below shows an example of a (256,256;4,4)_{2} de Bruijn torus / array, where the zeroes have been encoded as black and the ones as white pixels respectively.
Practical consideration for construction of de Bruijn tori B_{6} & B_{8}
This section needs to be updated. (September 2017) |
The paper in which an example of the (256,256;4,4)_{2} de Bruijn torus / array was constructed contained over 10 pages filled essentially only with 0s and 1s, even though the font size was reduced compared with the main text, each row of the array printed over 3 lines.
The subsequent possible binary "square" de Bruijn torus, containing all binary 6×6 matrices, would have 2^{36} = 68,719,476,736 entries, yielding a square array of dimension 262,144x262,144, this would be denoted a (262144,262144;6,6)_{2} de Bruijn torus / array or simply as B_{6}. It should be possible to construct an example, which would fit onto a moderate computer (printing it out where each entry would be represented by a pixel of size 0.1 mm would require an area of approx 26×26 [square metre]s).
The object B_{8}, containing all binary 8×8 matrices, with a total of 2^{64} = 18,446,744,073,709,551,616 entries, denoted (4294967296,4294967296;8,8)_{2} is currently too large for even a supercomputer, requiring of order 18 Exabytes, outside a 64-bit address space (assuming 1 byte of storage for each element, in theory only 1 bit would be sufficient for each element, only of order 2 Exabytes would be required, which is still 3 orders of magnitude larger than total memory / storage of some of the largest computers as of late 2013).
See also
References
- ^ Fan, C. T.; Fan, S. M.; Ma, S. L.; Siu, M. K. (1985). "On de Bruijn arrays.". Ars Combinatoria A. 19: 205–213.
- ^ Chung, F.; Diaconis, P.; Graham, R. (1992). "Universal cycles for combinatorial structures.". Discrete Mathematics. 110 (1): 43–59. doi:10.1016/0012-365x(92)90699-g.
- ^ Jackson, Brad; Stevens, Brett; Hurlbert, Glenn (Sep 2009). "Research problems on Gray codes and universal cycles". Discrete Mathematics. 309 (17): 5341–5348. doi:10.1016/j.disc.2009.04.002.
- ^ Eggen, Bernd R. (1990). "The Binatorix B2.". Private communication.
- ^ Shiu, Wai-Chee (1997). "Decoding de Bruijn arrays constructed by the FFMS method.". Ars Combinatoria. 47 (17): 33–48.
External links
- Minimal arrays containing all sub-array combinations of symbols: De Bruijn sequences and tori