Return to Question

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?

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?

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?

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?