De Bruijn Sequences with Minimum Discrepancy

The discrepancy of a binary string is the maximum (absolute) difference between the number of ones and the number of zeroes over all possible substrings of the given binary string. In this note, we prove that the minimum discrepancy achievable by a binary de Bruijn sequence of order n n is exactly n n . This was an open problem until now. We give an algorithm that constructs a binary de Bruijn sequence with minimum discrepancy. A slight modification of this algorithm deals with arbitrary alphabets, yielding de Bruijn sequences of order n n with discrepancy at most 1 1 above the trivial lower bound n n .