Welcome to MathOverflow

Question

1

A binary De Bruijn sequence of index $n$ is a circular sequence $S=a_1 a_2 \dots a_{2^n},$ with $a_i \in {0,1},$ and such that each of the $2^n$ binary $n$-uples occurs exactly once in $S.$

Is there an infinite binary sequence $b_1 b_2 b_3 \dots$ such that $b_1 \dots b_{2^n}$ is a binary De Bruijn Sequence of index $n$ for all $n$ ?

flag	asked Jun 11 2011 at 18:01 Donatien Beneat 13●2

2

WLOG the sequence starts 01. Now the first four terms have to be 0110. But this can never be part of an index 3 De Bruijn sequence, because an index 3 De Bruijn sequence has to have precisely four 1s and three of them had better be consecutive, but this can't happen with a 0110. So, sadly, the answer is "no". – Kevin Buzzard Jun 11 2011 at 18:20

Are there at least interesting subsequences $n_1,n_2,\ldots$ of the natural numbers so that $b_1b2_\ldots b_{2^{n_i}}$ is a binary De Bruijn sequence for each $n_i$? For example, can this work if $n_i=2^i$? – Simon Jul 9 2011 at 13:08

Aaron Meyerowitz · Accepted Answer · 2011-06-11 18:29:04Z UTC

1

No. It may as well start with 0 in which case it is forced to be 01 for order 2 and then be 0110 for order 4. In order to include 111 it could only continue to be 01101110 or 01100111 but both of those have 011 twice and miss 000.

answered Jun 11 2011 at 18:29

Aaron Meyerowitz
11.6k●1●10●31

Nested De Bruijn Sequences

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.