Maximum discrepancy conjecture for the de Bruijn sequence DB_max

About 6 years old · traced to

Let DBmax⁡(n)\mathcal{DB}_{\max}(n) denote the de Bruijn sequence of order nn defined in the source, and let the discrepancy of a binary sequence be the maximum, over all prefixes, of the absolute difference between the numbers of 11s and 00s.

Maximum discrepancy conjecture. The sequence DBmax⁡(n)\mathcal{DB}_{\max}(n) has discrepancy equal to

(n−1⌊n/2⌋)+⌊n/2⌋,{n-1 \choose \lfloor n/2 \rfloor}+\lfloor n/2\rfloor,

and this is the maximum possible discrepancy over all de Bruijn sequences of order nn.

The claim is motivated by an established lower bound and exact computations for 10≤n≤2510\leq n\leq 25; the source does not provide a proof of equality or of global maximality.

References

Primary source

Daniel Gabric and Joe Sawada, “Investigating the discrepancy property of de Bruijn sequences”, arXiv:2005.01638 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.