10
$\begingroup$

Q. Do there exist De Bruijn tori in dimension $d > 2$?

A De Bruijn torus is a two-dimensional generalization of a De Bruijn sequence. A De Bruijn sequence is, for two symbols, a cyclical bit-string that contains all bit strings of length $n$ as consecutive, left-to-right bits (with wrap-around). For example, here is a sequence of $8$ bits that contains all $2^3$ bit strings of length $3$: $$ \begin{matrix} \color{red}{0} & \color{red}{0} & \color{red}{0} & 1 & 1 & 1 & 0 & 1\\ 0 & \color{red}{0} & \color{red}{0} & \color{red}{1} & 1 & 1 & 0 & 1\\ \color{red}{0} & 0 & 0 & 1 & 1 & 1 & \color{red}{0} & \color{red}{1}\\ 0 & 0 & \color{red}{0} & \color{red}{1} & \color{red}{1} & 1 & 0 & 1\\ \color{red}{0} & \color{red}{0} & 0 & 1 & 1 & 1 & 0 & \color{red}{1}\\ 0 & 0 & 0 & 1 & 1 & \color{red}{1} & \color{red}{0} & \color{red}{1}\\ 0 & 0 & 0 & 1 & \color{red}{1} & \color{red}{1} & \color{red}{0} & 1\\ 0 & 0 & 0 & \color{red}{1} & \color{red}{1} & \color{red}{1} & 0 & 1 \end{matrix} $$

Here is a De Bruijn torus that includes all $2 \times 2$ bit-matrices exactly once (from here): $$ \begin{matrix} 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{matrix} $$ A $4 \times 4$ De Bruijn torus has been explicitly constructed.

My question is: Is it known that there exist De Bruijn tori in dimensions larger than $d=2$? Perhaps for every dimension? For example, a three-dimensional pattern of bits that includes every $k \times k \times k$ bit-(hyper)matrix?

$\endgroup$
3
  • $\begingroup$ Did you code $d=2$ as d{=}2 on purpose, or were you using one of those software packages that writes the code for you? I looked at it and the fact that it had less space before and after the "equals" sign was conspicuous, so then I looked at how it was coded. Those packages sometimes write code that looks as if a lunatic wrote it (although this instance is not that extreme). $\endgroup$ Commented Apr 16, 2017 at 17:17
  • $\begingroup$ @MichaelHardy: I wrote d{=}2 on purpose, but it is fine to retain your edit. $\endgroup$ Commented Apr 16, 2017 at 20:30
  • $\begingroup$ What purpose was intended to be served by writing it that way? $\endgroup$ Commented Apr 17, 2017 at 3:02

1 Answer 1

9
$\begingroup$

Yes. See "New constructions for de Bruijn tori" by Hurlbert and Isaak

$\endgroup$
1
  • 3
    $\begingroup$ Thanks! Here's a PDF link, perhaps a draft of the journal article to which you link. $\endgroup$ Commented Apr 16, 2017 at 0:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .