Maximum discrepancy conjecture for the de Bruijn sequence DB_max

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

(n1n/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 10n2510\leq n\leq 25; the source does not provide a proof of equality or of global maximality.

Sources & referencesView supporting material

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.