2
$\begingroup$

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$ ?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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". $\endgroup$
    – Kevin Buzzard
    Commented Jun 11, 2011 at 18:20
  • $\begingroup$ 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$? $\endgroup$
    – Simon
    Commented Jul 9, 2011 at 13:08

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I've upvoted you. However, according to the MO clock, @Kevin Buzzards equivalent comment has appeared 9m before yours. $\endgroup$
    – Wlod AA
    Commented Sep 30, 2018 at 22:06
1
$\begingroup$

A natural generalization of this problem is the the question about nested perfect necklaces which are a variant of the classical de Bruijn sequences. For positive integers $k$ and $m$ a necklace is $(k, m)$-perfect if each word of length $k$ occurs exactly $m$ times at positions which are different modulo $m$ for any convention on the starting point. The length of a $(k, m)$-perfect necklace is $m|A|^k$ where $|A|$ denotes the cardinality of the given alphabet $A$.

The paper Normal numbers and nested perfect necklaces by Verónica Becher, Olivier Carton is devoted to nested perfect necklaces with applications to normal numbers with small discrepancy. A word $w$ is a $(k, m)$-nested perfect necklace if for each integer $\ell = 1, 2, \ldots , k$, each block of $w$ of length $m|A|^\ell$ which starts at a position congruent to $1$ modulo $m|A|^\ell$ is a $(\ell, m)$-perfect necklace.

Improve this answer
$\endgroup$

You must log in to answer this question.

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